> I'm not sure about GPGPU implementations, but for generalized FFT there are > algorithms that can operate on multiples of 3, 5, and maybe even 7s or > higher (and then there's the completely general but slow-as-all-get-out DFT > algorithm that works on any size). Then, you just implement butterflies for > all the underlying factors, and composite them (that's why Powers of Two are > so popular -- you just have 1 butterfly that you keep reusing). So if you > wanted to do 100, for example, it would factorize to 2*2*5*5, so you'd need > butterflies for radix-2 and radix-5. 1025 would require 5*5*41, so you'd > need a 5 and a 41 (radix-41 would be hard, I'm guessing ;).
Hmm.. that's making my head hurt just thinking about it ;) > If you filter with nearest neighbor, I don't _think_ you add frequencies, > technically (as long as you keep the scaling in mind) -- you're just adding > gaps to the FFT output. That said, it's been a _long_ time since I took any > DSP courses, so I'm very rusty, and might be totally wrong. You're right > about borders though, those will break things. If I recall correctly, the > way to handle edges is to reflect about the edge (so you get the same > pixels, but in reverse)? that's what JPEG does for non-multiples-of-8 sized > images, I think (though JPEG uses DCT, a relative of FFT). Hopefully > someone more on top of DSP (or even math in general? ;) can set me straight > here. Hmm.. ok, the reflected edges are certainly possible (I'm sure there's a filter already for doing that). It must introduce some changes around the edges, but I guess it will be minimal compared to a border. I'll have to try. > If you're seriously going to want high speed, high quality 2D FFTs, you > _might_ want to look at Accelerate.framework, which has optimized 1D and 2D > FFT functions (Though they're definitely limited to powers of two -- but > reflecting the image in 2 dimensions to the next highest power of two might > help you there, if my above fuzzy recollection of edge reflection is > accurate)), or even FFTW (http://www.fftw.org) which has multidimensional > non-power-of-two DFT support. Perhaps not as fast as GPU with POT > dimensions, but the genericness might be worth the tradeoff. Ahh, I keep seeing vimage stuff and wondering what it is. vDSP sounds pretty good - it's POT as you say, but could be a good option if I need to do FFT on the CPU (quite possible if I use FFT for the image recognition part). FFTW sounds interesting too. Any idea how fast these things are in practice? FFTW has a benchmark page but everything's measured in MFLOPs. How long it took to do something would be more useful. Is it reasonable to expect it to handle say 1024x1024 images at 15fps? Thanks once again for the tips :) Chris > -- > [ christopher wright ] > [email protected] > http://kineme.net/ > > _______________________________________________ Do not post admin requests to the list. They will be ignored. Quartzcomposer-dev mailing list ([email protected]) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/quartzcomposer-dev/archive%40mail-archive.com This email sent to [email protected]
