Digital image processing system

• US 4,972,359 A
• Filed: 04/03/1987
• Issued: 11/20/1990
• Est. Priority Date: 04/03/1987
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Wolff, Robert A., Dynneson, Ronald E., Silver, William M.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/034,781
• Time in Patent Office: 1,327 Days
• Field of Search: 364/718, 364/728, 364/735, 364/747, 364/518, 364/728.05, 382/18, 382/31, 382/42, 382/51
• US Class Current: 708/424
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A digital image processing system provides convolution, correlation and normalized correlation functions, without per-pixel multiplication operations, utilizing factorization and moment generation. A first memory array is addressed by image pixel values, and a second memory array is addressed by template pixel values. Logic and control elements increment the array element addressed by the image pixel value, and add the image pixel value to the array element addressed by a corresponding template pixel value. The resulting sums in the first and second arrays are processed to generate convolution and correlation functions.

Claims

1. Image processing apparatus comprising

image input means for receiving an image signal stream, said image signal stream including one or more digital image values representative of pixels of an input image,

model input means for receiving a model signal stream including one or more digital model values representative of pixels of a model, ones of said digital model values being received in temporal correspondence with ones of said digital image values so that ones of said digital model values correspond to ones of said digital image values,

first memory means, in electrical communication with said image input means, and including an array of first memory locations, for accumulating energy values representative of frequency of occurrence of said digital image values, and wherein said memory locations of said first memory means are addressable by said image values,

second memory means, in electrical communication with said model input means, and including an array of second memory locations, for accumulating correlation values representative of results of arithmetic operations on said image values, and wherein said memory locations of said second memory means are addressable by said model values,

first arithmetic means, in electrical communication with said first memory means and said second memory means, for performing arithmetic functions on said energy and correlation values, said arithmetic means including

incrementer means, in electrical communication with the first memory means, for incrementing the energy value stored at each first memory location addressed by said image values, and

adder means, in electrical communication with the second memory means, for adding, to the correlation value stored at each second memory location addressed by a received model value, the image value corresponding to the received model value, to generate output image values, and

controller means in electrical communication with said arithmetic means for controlling the arithmetic functions of said arithmetic means, said controller means including execution means for causing said arithmetic means to execute said incrementation and addition functions on corresponding ones of said energy and correlation values.

2. Apparatus according to claim 1, wherein said arithmetic means further includes means for subtracting, from the correlation value stored at each memory location of said second memory means addressed by a received model value, the digital image value corresponding to the received model value.

3. Apparatus according to claim 2, wherein said first arithmetic means includes means for executing constant time filter functions, and

said controller means contains means for placing said first arithmetic means in a state to execute constant time filter functions.

4. Apparatus according to claim 1, wherein said digital image values are characterized by an 8 bit width,

said digital model values are characterized by an 8 bit width,

said first memory means includes 256 locations characterized by a 16 bit width, and

said second memory means includes 256 locations characterized by a 24 bit width.

5. Apparatus according to claim 1, wherein said controller means is contained in a microprocessor.

6. Apparatus according to claim 1, further comprising

translation memory means, in electrical communication with said first memory means and said second memory means, and including an array of translation memory locations, said translation memory locations being addressable by ones of said digital image values, for translating input image values from a first range of values to a second range of values.

7. Apparatus according to claim 6, wherein said translation memory means includes means for translating input image values from a first range of grey levels to a second range of grey levels, said second range of grey levels being smaller than said first range of grey levels.

8. Apparatus according to claim 1, wherein said controller means includes second arithmetic means for computing moments of values stored in at least one of said first memory means and said second memory means.

9. Apparatus according to claim 8, wherein said second arithmetic means is contained in a microprocessor.

10. Apparatus according to claim 9, wherein said microprocessor contains model compiler means for executing correlation, normalized correlation and convolution functions utilizing binary models.

11. Apparatus according to claim 8, wherein said second arithmetic means includes means for executing moment functions utilizing cascaded accumulators.

12. Apparatus according to claim 8, wherein said first and second arithmetic means collectively include means for executing correlation, normalized correlation, and convolution functions, and

said controller means includes means for placing said first and second arithmetic means in a state to execute correlation, normalized correlation and convolution functions.

13. Apparatus according to claim 1, wherein said first arithmetic means includes means for executing spatial averaging functions, and

said controller means contains means for placing said first arithmetic means in a state to execute spatial averaging functions.

14. Apparatus according to claim 1 wherein said controller means contains means, in electrical communication with said first memory means, for utilizing the energy values accumulated in said first memory means to generate histograms, said energy values being representative of frequency of occurrence of said digital image values.

15. Apparatus according to claim 1, wherein said controller means contains means for controlling the incrementer means and adder means of said first arithmetic means to generate projections from said digital image values and said digital model values.

16. Apparatus according to claim 15, wherein said controller means contains spatial moment means for executing spatial moment functions, said spatial moment means including

second arithmetic means for computing moments of values stored in at least one of said first memory means and said second memory means.

17. Image processing apparatus comprising

first input means for receiving a first signal stream including one or more first digital signal values representative of pixel of an input image,

second input means for receiving a second signal stream including one or more second digitial signal values representative of pixels of a model, ones of said second digital signal values being received in temporal correspondence with ones of said first digital signal values so that ones of said second digital signal values correspond to ones of said first digital signal values,

memory means, in electrical communication with said first and second input means, for storing sums of arithmetic products of said first digital signal values and said second digital signal values in an array of memory locations, said memory locations being addressable by said second digital signal values, and

execution means, in electrical communication with said first input means, said second input means, and said memory means, for executing arithmetic operations on said first digital signal values and said second digital signal values to generate output digital signal values representative of an output image, said arithmetic operations including any of correlation, normalized correlation and convolution, said execution means including

arithmetic means for computing said stored sums,

said arithmetic means including

factorization means for factoring arithmetic products of said first digital signal values and said second digital signal values, and

moment generation means, in electrical communication with said execution means, for computing moments of said array.

18. Apparatus according to claim 17, wherein said second arithmetic means includes means for generating said moments utilizing cascaded accumulators.