Apparatus and method for processing an image

• US 4,764,974 A
• Filed: 09/22/1986
• Issued: 08/16/1988
• Est. Priority Date: 09/22/1986
• Status: Expired due to Term

• Current Assignee: Perceptics Corporation Pellissippi Center Knoxville Tennessee 37922
• Original Assignee: Perceptics LLC
• Inventors: Woods, Richard E.
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): Parker, Michael D.
• Application Number:
  US06/910,077
• Time in Patent Office: 694 Days
• Field of Search: 382/31, 382/43, 364/576, 364/726, 364/827
• US Class Current: 382/280
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 5/10 using non-spatial domain filtering
• CPC Class Codes: G06T 5/70 Denoising; Smoothing

Abstract

The specification discloses an apparatus and method for processing an image as part of a fast Fourier transform (FFT) operation. An image processor includes a first and second memory, each for storing the data representing an image as an array of numbers in a format having rows and columns of data positions. A controller is provided for scrolling the data in each row of the second memory with respect to the first memory by at least one data position and for outputting the data of both memories to a data processor. The data processor combines every other group of at least one number of each row of the scrolled data with a corresponding every other group of at least one number of each row of the data from the first memory and passes to its output the data from the first memory for the remaining data positions, whereby a new array of data is produced that is useful as part of a fast Fourier transform operation.

Claims

1. An image processor for processing data representing an image, comprising:

a first memory for storing the data as an array of numbers in a format having rows and columns of data positions;

a second memory for storing the data as an array of numbers in a format having rows and columns of data positions;

means for scrolling the data in each row of the second memory with respect to the first memory by at least one data position;

a data processor;

means for outputting the scrolled data of the second memory and the data of the first memory to the data processor; and

said data processor being operable to combine every other group of at least one number of each row of the scrolled data with a corresponding every other group of at least one number of each row of the data from the first memory and for passing the data from the first memory for the remaining data positions to produce a new array of data.

2. The image processor of claim 1 further comprising means for reordering the data stored in the first and second memories in accordance with a predetermined reordering sequence prior to scrolling or outputting the data.

3. The image processor of claim 1 further comprising:

means for supplying a set of coefficients;

means for selecting data from the first or second memories; and

means for multiplying every other number of the selected data by a selected one of the coefficients prior to combining the scrolled data and the data of the first memory.

4. The image processor of claim 1 wherein said means for combining comprises means for adding and subtracting.

5. The image processor of claim 1 wherein said groups contain only one number.

6. The image processor of claim 1 wherein said groups contain a count of numbers equal to a power of two.

7. The image processor of claim 1 wherein said means for scrolling is operable to selectively scroll the data in each row of the second memory forwardly and rearwardly with respect to the first memory by a selected number of data positions;

and

said data processor is operable to combine the odd groups of each row of the scrolled data with the corresponding odd groups of each row of the data from the first memory when the data is scrolled forwardly and is operable to combine the even groups in each row of the scrolled data with the corresponding even groups of the data from the first memory when the data is scrolled rearwardly.

8. The image processor of claim 7 wherein the count of numbers in each group is equal to the selected number of data positions by which the data of the second memory is scrolled forwardly or rearwardly.

9. An image processor for performing a Fourier transform operation on data representing an image comprising:

a first memory for storing the data as an array of numbers in a format having x rows and y columns;

a second memory for storing the data as an array of numbers in a format having x rows and y columns;

means for scrolling the data in each row of the second memory in a selected direction, forwardly or rearwardly, with respect to the first memory by a selected scroll number, n, of data positions;

control means for generating control signals and for selecting the direction of scrolling and the number n of data positions by which the data is scrolled;

a data processor;

means for outputting the data of the first memory and the scrolled data of the second memory to the data processor;

said data processor being operable in response to the control signals to define a data group as n numbers, to combine odd groups of n numbers in each row of data from the first memory with corresponding odd groups of n numbers in each row of the scrolled data from the second memory and to pass even groups of n numbers in each row of data from the first memory when the data in said second memory is scrolled forwardly by n data positions and being operable to combine even groups of n numbers in each row of data from the first memory with corresponding even groups of n numbers of scrolled data from the second memory and to pass odd groups of n numbers in each row of data from the first memory when said data is scrolled rearwardly by n data positions; and

said control means being operable to cause the circulation of the data from said first and second memories to the data processor and back to the first and second memories for a series of circulation sets, where a circulation set is defined as a sufficient number of passes of the data through the data processor to combine the odd groups and pass the even groups to produce an intermediate array, store the intermediate array in a first memory and, then, to combine the even groups and pass the odd groups to produce a result array and store the result array in the first and second memories.

10. The processor of claim 9 further comprising said control means being operable to select said scroll number n for each circulation set to be equal to the number "2" raised to a power of one less than the circulation set number so that n=1 on the first circulation set, n=2 on the secod circulation set, n=4 on the third circulation set, n=8 on the fourth circulation set and n=2 raised to the number of the last circulation set minus 1 for the last circulation set.

11. The processor of claim 9 further comprising said control means being operable to circulate the data for a series of c circulation sets where two raised to the c power equals y, the number of columns of data.

12. The processor of claim 9 further comprising said control means being operable to circulate the data for a series of c number of circulation sets where 2 raised to the c power equals x, the number of rows of data.

13. The processor of claim 9 further comprising said data processor being operable in response to the control signals to reorder the data in accordance with a predetermined reordering sequence.

14. The processor of claim 9 further comprising said data processor being operable in response to the control signals to reorder the data by transposing the rows and columns so that each column becomes a row with the first column becoming the first row, the second column becoming the second row, and the last column becoming the last row.

15. The processor of claim 9 further comprising said data processor being operable to combine the odd groups by multiplying the scrolled data by predetermined coefficients to produce products and adding the products to the data from the first memory.

16. The processor of claim 9 further comprising said data processor being operable to combine the even groups by multiplying the data from the first memory by predetermined coefficients to produce a product and subtracting the product from the oppositely scrolled data.

17. A method for processing data representing an image using first and second memories and a data processor, comprising:

storing the image in each memory by storing the data in the first and second memories as an array of numbers in a format having rows and columns of data positions;

scrolling the data in each row of the second memory with respect to the first memory by at least one data position to produce scrolled data;

outputting the data of the first memory and the scrolled data of the second memory to the data processor;

grouping each row of data into groups of at least one number; and

combining every other group (defined as the odd groups) of each row of the data from the first memory with a corresponding group of each row of the scrolled data and passing the data from the first memory for the remaining data positions (the even groups) to produce a new array of data.

18. The method of claim 17 further comprising:

storing the new array of data in the first memory;

oppositely scrolling the data in each row of the second memory with respect to the first memory by at least one data position and in an opposite direction from the previous scrolling to produce oppositely scrolled data;

outputting the new array of data and the oppositely scrolled data from the first and second memories to the data processor;

grouping each row of the new array of data and the oppositely scrolled data into groups of numbers of the same size as the groups produced by the other grouping; and

combining the even groups of each row of the new data array, which is the data that was passed in the other combining and passing step, with a corresponding group of each row of the oppositely scrolled data and passing the data from the first memory for the remaining data positions (the odd groups) to produce a resulting array of data.

19. The method of claim 17 further comprising reordering the data in accordance with a predetermined reordering sequence for each row of data prior to initially storing the data in the first and second memories.

20. A method for processing an array of data having x rows and y columns representing an image as part of a fast Fourier transform process using first and second memories and a data processor, comprising:

reordering the data in accordance with a predetermined reordering sequence to produce reordered data;

storing the reordered data in first and second memories as an array of numbers in a format having x rows and y columns where x and y are both powers of two, each of said first and second memories containing all of the reordered data corresponding to the image;

circulating the data from the memories to the data processor and back to the memories for a first series of circulation sets where the number of circulation sets in the first series equals c1 and two raised to the c1 power equals y to produce a one dimensional FFT array;

transposing the one dimensional FFT array by rows and columns so that the rows become columns and the columns become rows;

reordering the data again in accordance with a predetermined reordering sequence to produce second reordered data and storing the second reordered data in the first and second memories;

circulating the second reordered data again from the memories to the data processor and back to the memories for a second series of circulation sets where the number of circulation sets in the second series equals c2 and two raised to the c2 power equals x, whereby the fast fourier transform of the image is produced;

each circulation set of the first and second series comprising;

scrolling the data in each row of the second memory with respect to the first memory by s data positions where s equals 2 raised to the power of the number of the circulation set in a series of circulation sets, so that s equals one on a first circulation set, s equals two on a second circulation set, s equals four on a third circulation set and, on the last circulation set, s equals two raised to the power of one less than the number of a last circulation set;

outputting the data of the first memory and the scrolled data of the second memory to the data processor;

grouping each row of the data of the first memory and the scrolled data of the second memory into alternating groups with s numbers in each group;

combining every other group (defined as the odd groups) of each row of the data from the first memory with a corresponding group of each row of the scrolled data and passing the data from the first memory for the remaining data positions (the even groups) to produce an intermediate array of data;

storing the intermediate array of data in the first memory;

oppositely scrolling the data in each row of the second memory with respect to the first memory by s data positions and in an opposite direction from the previous scrolling to produce oppositely scrolled data;

outputting the intermediate array of data from the first memory and the oppositely scrolled data from the second memory to the data processor;

grouping in the data processor each row of the data from the first and second memories into alternating groups with s numbers in each group;

combining the remaining every other group (the even groups) of each row of the intermediate data array, which is the data that was passed in the other combining and passing step, with a corresponding group of each row of the oppositely scrolled data and passing the data of the odd groups to produce a resulting array of data.

21. The method of claim 20 wherein said reordering step comprises reordering the data of each row according to a binary bit reversal reordering sequence.

22. The method of claim 20 wherein said reordering step includes transposing the rows and columns so that the rows become columns and the columns become rows.

23. The method of claim 20 wherein both combining steps include multiplying the data from one of the groups by a predetermined coefficient to produce a product and selectively adding or subtracting the product from the data of the corresponding groups.