nitin@ur-laser.uucp (Nitin Sampat) (08/06/85)
FFT's as we know exhibit a nonlinear increase in computation time as
the size of the image increases. Also, the hardware determines the
CPU time you get from the computer. If your record size is too large
for the core the computer starts paging, copying to and fro from disk,
therby increasing the processing time. One solution to this could
be to process the image in sub-sections. Each sub-section of the image
could be so chosen that the record size is large enough to fit in core
memory at one time. This would eliminate any paging. Can this be done
and if so how does one go about chosing the sub-sections ?
After all, theory defines that the image is a function f(x,y) with
a period N(=no. of points). If we divide the image into sections,
we are in effect defying the basis of linear system theory. I was
told that the trick is to overlap one section onto the other is some
fashion, after the FFT operation. Does anybody have any experience with
this ?
I guess the question I am asking is this :
We know that processing small images takes less time. Well, how does
one go about breaking up a large image and process it in sections,
and then most importantly, how does one put all these sections back
to get the FFT of the original image ?
nitin
{seismo,allegra}!rochester!ur-laser!nitin.uucpsher@rochester.UUCP (David Sher) (08/07/85)
In article <360@ur-laser.uucp> nitin@ur-laser.uucp (Nitin Sampat) writes: ... >We know that processing small images takes less time. Well, how does >one go about breaking up a large image and process it in sections, >and then most importantly, how does one put all these sections back >to get the FFT of the original image ? > > nitin > {seismo,allegra}!rochester!ur-laser!nitin.uucp It turns out that on a 2d image applying FFT only requires that a row or collumn of data need be processed at a time. If the image is reflected along a diagonal between the row and collumn processing the paging should be minimized fairly well and the entire transformation is applied. Of course there is still a log n factor that is lost from the nature of the FT. However I would suspect that for the small images (1Kx1K) that are worked on today it would cost more to do the gluing operation that glues together the results of FFT's on partitions of the image than to do the entire FFT. On the topic of FFT vs convolution, my latest TR on doing template matching on the WARP and the Butterfly addresses this issue for these architectures. However it is not classy to push ones own work so enough said. -David Sher sher@rochester seismo!rochester!sher
cdl@mplvax.UUCP (Carl Lowenstein) (08/08/85)
In article <360@ur-laser.uucp> nitin@ur-laser.uucp (Nitin Sampat) writes: >We know that processing small images takes less time. Well, how does >one go about breaking up a large image and process it in sections, >and then most importantly, how does one put all these sections back >to get the FFT of the original image ? Just a little philosophical fuel on the fire: The whole idea behind the FFT (what makes it *F*ast) is that breaking a large dataset into sections, processing the sections, and then recombining them is faster than processing the whole thing all at once. (recursively, down to sections of size 2 or 4). -- carl lowenstein marine physical lab u.c. san diego {ihnp4|decvax|akgua|dcdwest|ucbvax} !sdcsvax!mplvax!cdl
shankar@brand.UUCP (Shankar Chatterjee) (08/09/85)
In most cases, when a 2-D FFT of an image is required, 1-D FFT is performed on one row at a time if the image is too large to fit into the core. After this the image in the disk is 'transposed' using some block allocation strategy. The block size can be fixed or can be determined (alongwith the no. of passes over the image) from the available core. [Note here that the transpostion has to be done block by block to speed up processing. One could refer to J.O. Eklundh (IEEE Tr. on Computers, vol. C-21, 1972) or a more generalized version of it in H.K. Ramapriyan (IEEE Tr. on Comp., Dec. 1972). I had implemented a modified version of the latter in software on a PE-3220 machine.] After this another 1-D FFT is performed on the rows. However some smart addressing scheme is needed (butterfly ?) to center the d.c. term. Shankar Chatterjee USC Signal & Image Processing Institute shankar!brand%oberon%usc-cse@csnet-relay
rhbartels@watcgl.UUCP (Richard Bartels) (08/12/85)
In article <208@mplvax.UUCP> cdl@mplvax.UUCP (Carl Lowenstein) writes: >In article <360@ur-laser.uucp> nitin@ur-laser.uucp (Nitin Sampat) writes: >>We know that processing small images takes less time. Well, how does >>one go about breaking up a large image and process it in sections, >>and then most importantly, how does one put all these sections back >>to get the FFT of the original image ? A possible reference: Fast Transforms: Algorithms, Analyses, Applications D. F. Elliott and K. R. Rao Academic Press, 1982
alan@sun.uucp (Alan Marr, Sun Graphics) (08/14/85)
The transposition of the image on the disk can be combined with the writing and reading of the image between the transform steps.
shep@datacube.UUCP (08/14/85)
In article <360@ur-laser.uucp> nitin@ur-laser.uucp (Nitin Sampat) writes: >We know that processing small images takes less time. Well, how does >one go about breaking up a large image and process it in sections, >and then most importantly, how does one put all these sections back >to get the FFT of the original image ? And carl lowenstein sdcsvax!mplvax!cdl writes: >Just a little philosophical fuel on the fire: The whole idea behind the >FFT (what makes it *F*ast) is that breaking a large dataset into sections, >processing the sections, and then recombining them is faster than processing >the whole thing all at once. (recursively, down to sections of size 2 or 4). Exactly! It is the representation of a one-dimensional string of numbers as a two-dimensional array that allows it to fall together. Two-dimensional image transforms are handled as the linear combination of two one-dimensional passes. (The DFT is separable.) Radix-2 and radix-4 butterflies are common only because of their ease of use on sequence lengths that are highly composite (i.e. powers of two). A radix-5 butterfly might be used for performing a 60 point FFT algorithm. Rabiner and Gold give a good discussion of this in their EE classic "Theory and Application of DSP". Shep Siegel UUCP: ihnp4!datacube!shep Datacube Inc.; 4 Dearborn Rd.; Peabody, Ma. 01960; 617-535-6644