US4764974A — Apparatus and method for processing an image

Claim 1

Independent Claim 167 words

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.

Claim 2

Dependent Claim 167 words

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.

Claim 3

Dependent Claim 34 words

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.

Claim 4

Dependent Claim 56 words

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.

Claim 5

Dependent Claim 17 words

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

Claim 6

Dependent Claim 13 words

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

Claim 7

Dependent Claim 20 words

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

Claim 8

Dependent Claim 113 words

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.

Claim 9

Dependent Claim 36 words

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.

Claim 10

Dependent Claim 392 words

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.

Claim 11

Dependent Claim 392 words

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.

Claim 12

Dependent Claim 85 words

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.

Claim 13

Dependent Claim 38 words

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.

Claim 14

Dependent Claim 40 words

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.

Claim 15

Dependent Claim 29 words

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.

Claim 16

Dependent Claim 58 words

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.

Claim 17

Dependent Claim 39 words

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.

Claim 18

Dependent Claim 41 words

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.

Claim 19

Independent Claim 160 words

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.

Claim 20

Independent Claim 160 words

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.

Claim 21

Dependent Claim 167 words

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.

Claim 22

Dependent Claim 34 words

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.

Claim 23

Independent Claim 604 words

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.

Claim 24

Independent Claim 604 words

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.

Claim 25

Dependent Claim 24 words

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

Claim 26

Dependent Claim 26 words

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.

Claim 27

Dependent Claim 40 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1991-08-16	1992-02-15	1992-08-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1995-08-16	1996-02-15	1996-08-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1999-08-16	2000-02-15	2000-08-16	$7700.00	Window Closed / Lapsed

Apparatus and method for processing an image

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag