Vision coprocessing

• US 5,657,403 A
• Filed: 06/01/1992
• Issued: 08/12/1997
• Est. Priority Date: 06/01/1992
• Status: Expired due to Fees

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Schott, Jean-Pierre, Rosenthal, Steven Mark, Wolff, Robert Anthony, Silver, William Michael
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US07/891,955
• Time in Patent Office: 1,898 Days
• Field of Search: 382/41, 382/49, 382/27, 382/276, 382/302, 382/303, 382/304, 382/307, 382/308, 382/205, 395/502, 395/503, 395/504, 395/505, 395/506, 364/131, 364/132, 364/133, 364/134
• US Class Current: 382/302
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A coprocessor in an image processing system is coupled to the bus to which a CPU and RAM holding image data are also coupled. The coprocessor extracts an input pixel stream corresponding to input images from selected bus transactions, performs computations on the input stream to produce output pixel streams corresponding to output images, and inserts the output pixel streams into selected CPU-to-memory bus transactions so that the memory stores the data. The CPU generates the selected bus transactions with specially marked address and/or control signals. The coprocessor includes a lookup table, and a first row delay. The row delay accumulates the three most recent rows of input pixels, which are sent to Sobel and rank processing sections for neighborhood processing. The results are thresholded and formatted, and are either output directly or passed through an additional pair of row delays to accumulate three rows of result data for neighborhood peak detection.

Claims

1. A digital image processing system including

A. bus means for carrying control, data and address signals,

B. memory means, coupled to said bus means, for storing digital image data and for responding to access control signals on said bus means for transferring digital image data therewith,

C. CPU means, coupled to said bus means, for applying said access control signals thereto for controlling the transfer of digital image data therewith, said CPU means including address means for applying address signals to the bus means, in connection with said access control signals, to locate data being transferred therewith,

D. video input means, coupled to said memory means, for acquiring digital image data and for storing said digital image data in said memory means, and

E. image data co-processing means, coupled to said bus means, for responding to said control and address signals on said bus means for processing digital image data received therefrom,

F. said address means including means for applying an address signal from a first selected set of address signals to the bus means in connection with an access control signal,

said memory means including means for responding to that address signal for transferring data in accord with that access control signal,

said image data co-processing means including means for responding to that address signal for ignoring data transfer with said bus means, and

G. said address means includes means for applying an address signal from a second selected set of address signals to the bus means in connection with an access control signal,

said image data co-processing means including means for responding to that address signal for transferring digital image data to said bus means,

said memory means including means for responding to that address signal for transferring data from said bus means for storage therein.

2. In a system according to claim 1, the further improvement wherein said image data co-processing means includes

A. at least one neighborhood processor for processing an input array of digital image data words to generate an output array of digital image data words, wherein said input array of digital image data words is no larger in a first principal dimension than NW pixels, and no larger in a second principal dimension, normal to the first, than NH pixels, where NW is no larger than an image width, IW, where NW, NH and IW are integers greater than or equal to one,

B. said neighborhood processor including means for generating a word of said output array corresponding to each respective word of said input array, and

C. said neighborhood processor further including means for generating each such word of said output array based on values of words in a neighborhood of the respective word of said input array, wherein said neighborhood comprises a plurality of digital image words corresponding to adjacent pixels in the corresponding acquired digital image data.

3. In a system according to claim 2, the further improvement wherein said image data co-processing means includes

A. buffer memory means for storing digital image words in an array of NH rows of IW columns;

B. control circuits for storing into said buffer memory means one or more input digital image data words and for simultaneously retrieving therefrom a neighborhood of NW by NH digital image data words; and

C. computational elements for computing, from said neighborhoods, one or more output digital image data words representing at least a portion of said enhanced digital image data.

4. In a system according to any of claims 2 or 3, the further improvement wherein said neighborhood processor includes rank value filter means comprising:

A. input means for inputting a neighborhood of digital image data words, each said candidate digital image data word comprising a plurality of bits, from most significant to least significant bits,

B. storage means for at least initially storing a predetermined rank of word to be selected from said plurality of candidate digital image data words,

C. mask means for storing a mask associated with each of said input digital image data words, each said mask being at least initially set to identify input words as candidate,

D. iterative ranking means, coupled with said input, storage and mask means, for iteratively testing bits of the same significance from all of the candidate digital image data words, and generating a corresponding bit portion of a resultant digital word of the desired rank, and

E. means for generating said resultant digital word as representative of said predetermined rank.

5. In a system according to any of claims 2 or 3, the further improvement wherein said neighborhood processor includes grey scale morphology means comprising:

A. preprocessor means coupled to said input means for performing a selected mathematical function on an input neighborhood of digital image words to form a preprocessed neighborhood of digital image words,

B. rank value filter means coupled with said preprocessor means for selecting from said preprocessed neighborhood of digital image words a digital word of predetermined rank,

C. said rank value filter means including

(i) mask means for storing a mask associated with each of said preprocessed neighborhood of digital image data words, each said mask being at least initially set to identify input words as candidates,

(ii) iterative ranking means, coupled with said input, storage and mask means, for iteratively testing bits of the same significance from all of said candidates, and generating a corresponding bit portion of a resultant digital word of the desired rank, and

(iii) means for generating said resultant digital word as representative of said predetermined rank, and

D. means coupled with said rank value filter means for generating said selected digital value as representative of one or more values in said input neighborhood of digital values.

6. A digital image processing system comprising

A. image source means generating digital image data representative of one or more images,

B. image data co-processing means, coupled to said image source means, for processing digital image data received therefrom, and

C. CPU means, coupled to said image source means and to said image data co-processing means, for generating and applying thereto signals to

i) control the transfer of rows of digital image data from said image source means to said image data co-processing means, each said row comprising adjacent portions of an image along a first axis thereof, said transferred rows being any of (a) successive rows of a single image adjacent along a second axis, and (b) single corresponding rows of successive images, and

ii) control the processing of said transferred rows by said image data co-processing means,

D. said image data co-processing means comprising

i) input means for inputting said rows of said digital image data,

ii) row delay means, coupled to said input means, for accumulating said rows digital image data, said accumulated rows being any of (a) said successive rows of a single image adjacent along a second axis, and (b) said single corresponding rows of successive images,

iii) neighborhood processing means, coupled to said row delay means, for responding to control signals received from said CPU means to selectively process successive rows of a single image received therefrom, and

iv) row processing means, coupled to said row delay means, for responding to control signals received from said CPU means to selectively process said single corresponding rows of successive images.

8. A digital image processing system according to claims 6 or 7, wherein said neighborhood processing means and said row processing means comprise reconfigurable processing means selectively actuable in response to control signals received from said CPU means for (i) processing successive rows of a single image received therefrom, and (ii) processing said single corresponding rows of successive images.

7. A digital image processing system comprising

A. bus means for carrying control and data and address signals,

B. image source means, coupled with said bus means, for generating digital image data representative of one or more images and for transferring that data with said bus means,

C. image data co-processing means, coupled to said bus means, for processing digital image data received therefrom,

D. CPU means, coupled to said bus means, for generating and applying thereto signals to

i) control the transfer of rows of digital image data from said image source means to said bus means, each said row comprising adjacent portions of an image along a first axis thereof, said transferred rows being any of (a) successive rows of a single image adjacent along a second axis;

and (b) single corresponding rows of successive images,

ii) control the processing of said transferred rows by said image data co-processing means,

E. said image data co-processing means comprising

i) input means, coupled to said bus means, for inputting said rows of said digital image data,

ii) row delay means, coupled to said input means, for accumulating said rows of digital image data, said accumulated rows being any of (a) said successive rows of a single image adjacent along a second axis, and (b) said single corresponding rows of successive images,

iii) neighborhood processing means, coupled to said row delay means, for responding to said control signals to selectively process successive rows of a single image received therefrom,

iv) row processing means, coupled to said row delay means, for responding to control signals received from said CPU means to selectively process said single rows of corresponding successive images, and

v) means, coupled to said neighborhood processing means and said row processing means, for selectively transferring processed image data to said bus means.

9. A digital image processing apparatus comprising:

A. a programmable computational element;

B. a random access memory;

C. a bus for carrying address, data, and control signals, that connects said computational element to said memory for the purpose of transferring data between them under control of said computational element;

D. input circuits capable of acquiring one or more digital input images and storing said input images in said memory;

E. a pixel processor operatively connected to said bus, having;

i) extracting means for extracting an input pixel stream, corresponding to one or more input images, from selected bus transactions that are specially marked by at least one of selected address and control signals reserved for that purpose;

ii) performing means for performing some computation on said input pixel stream to produce one or more first output pixel streams, corresponding to one or more output images, wherein each output value is some function of one or more input values; and

iii) inserting means for inserting said one or more first output pixel streams into selected computational element-to-memory bus transactions that are specially marked by at least one of selected address and control signals reserved for that purpose, and in such a way that the memory stores the data supplied by the pixel processor, and

F. said computational element having means to generate the said selected bus transactions with the said specially marked address and control signals.

10. An apparatus according to claim 9 where said pixel processor includes a first neighborhood processor, wherein:

A. the input image is no longer in a first principal dimension than IW pixels;

B. each pixel of each output image is computed based on the values of the input pixels that lie within a neighborhood corresponding to the position of the output pixel, that is no larger in a first principal dimension than NW pixels, and that is no larger in a second principal dimension, normal to said first principal dimension, than NH pixels, where NW and NH are integers greater than or equal to one;

C. the first neighborhood processor contains a buffer memory configured for storing digital image words in an array of NH rows of IW columns, where IW is an integer greater than or equal to one;

D. the first neighborhood processor contains control circuits that store the input pixel stream into the buffer memory and simultaneously read out from the buffer memory successive neighborhoods;

E. the first neighborhood processor contains computational elements that compute one or more second output pixel streams from said neighborhoods of input pixel values;

F. said computational element having means for generating bus transactions of a type and in a sequence appropriate for neighborhood processing.

11. An apparatus according to claim 9 where the pixel processor contains a first row processor, wherein:

A. one or more input images are processed;

B. the input images have the same first principal dimension;

C. the input images are no larger in a first principal dimension than IW pixels;

D. each pixel of each output image is computed based on a set of pixel values, where said set contains one pixel from each of the input images corresponding to the position of the output pixel and where the number of input images is no larger than NH;

E. the first row processor contains control circuits that store the input pixel stream into the buffer memory and simultaneously read out from the buffer memory successive sets of input pixels;

F. the first row processor contains control circuits that store the input pixel stream into the buffer memory and simultaneously read out from the buffer memory successive sets of input pixels;

G. the first row processor contains computational elements that compute one or more second output pixel streams from said sets of input pixel values;

H. said computational element having means for generating bus transactions of a type and in a sequence appropriate for row processing of one or more images.

12. An apparatus according to claim 10 or 11 wherein said first neighborhood processor or said row processor include means for processing input images which are wider than IW in said first principal dimension, by processing those images, in strips no larger in the first principal dimension than IW pixels.

13. An apparatus according to claim 10 wherein:

A. the pixel processor contains a second neighborhood processor, comprising a buffer memory, control circuits and computational elements similar in form to the first neighborhood processor;

B. said second neighborhood processor reads one of the third output pixel streams from the formatter;

C. said second neighborhood processor produces one or more fourth output pixel streams that are derived as some function of one or more of the third output pixel streams and the second neighborhood results;

D. the first output pixel streams can be a selected subset of the fourth output pixel streams.

14. An apparatus according to claim 10 wherein the computational elements of the first neighborhood processor are configured as a pixel rank processor, wherein:

A. pixels from said neighborhood are ranked in value, said value being minimum, maximum, median or other selected value, and

B. two second output pixel streams are produced, the first representing the selected rank value and the second indicating which pixel or pixels in the neighborhood contain that rank value.

15. An apparatus according to claim 11 wherein the computational elements of the first row processor are configured as a pixel rank processor, wherein:

A. multiple input images are processed;

B. corresponding pixels from said multiple input images are ranked;

C. two second output pixel streams are produced, one representing the selected ranking pixel'"'"'s value, said selected value being minimum, maximum, median or other selected value, and the other indicating which image or images contained the ranking pixel'"'"'s value.

16. An apparatus according to claim 10 wherein the computational elements of the first neighborhood processor are configured for Sobel cartesian gradient computation, producing two second output pixel streams containing intensity gradient components in each principal dimension.

17. An apparatus according to claim 10 wherein the computational elements of the first neighborhood processor are configured for Sobel polar gradient computation, producing two second output pixel streams containing intensity gradient magnitude and direction.

18. An apparatus according to claim 17 wherein said two second output pixel streams correspond to gradient magnitude and direction pairs, with the improvement wherein if the gradient magnitude of any pair does not exceed some predetermined threshold value, then both members of the pair are set to some reserved value not otherwise used to represent magnitude and direction.

19. An apparatus according to claim 10 wherein the computational elements of the first neighborhood processor are configured for gauss/laplace, producing two second output pixel streams, one containing a gaussian filtration of the input image and the other containing a laplacian filtration of the input image.

20. An apparatus according to claim 11 wherein the computational elements of the first row processor are configured for summation of two input pixel streams, producing a second output pixel stream containing the sum of said two input streams.

21. An apparatus according to claim 11 wherein the computational elements of the first row processors are configured for subtraction of corresponding pixels of two output streams, producing one second output pixel stream containing the difference of the two input pixel streams.

22. An apparatus according to claim 11 wherein the computational elements of the first row processor are configured to compute a Golden Template Comparison (GTC) function of three input streams, producing one second output pixel stream containing a GTC function value resulting from such computation.

23. An apparatus according to claim 10 or 11 where the pixel processor includes a formatter, wherein

A. the formatter produces one or more third output pixel streams that are derived as some function of one or more of the second output pixel streams,

B. the first output pixel streams can be a selected subset of the third output pixel stream,

C. whether the absolute value of the selected second pixel stream values is computed is selectable,

D. absolute value, if selected, is applied to all second pixel streams,

E. each second pixel stream, as modified by said selectable absolute value step, is divided by an independently selectable power of two,

F. each second pixel stream, as modified by said selectable absolute value step and further modified by said independently selectable division by a power of two, is processed according to an independently selectable saturation rule, to produce corresponding third pixel stream values.

24. An apparatus according to claim 13 wherein said second neighborhood processor is configured for peak detection.

25. An apparatus according to claim 13 wherein said second neighborhood processor is configured for peak detection and two fourth output pixel streams are produced, similar to the said selected second or third output pixel streams,

with the improvement wherein for any magnitude/direction pixel pair where the magnitude value is not a peak value according to one of four selectable criteria:

the magnitude value is a peak in the first principal dimension, the magnitude value is a peak in the second principal dimension, the magnitude value is a peak in either the first or the second principal dimension, or the magnitude value is a peak in both the first and the second principal dimensions, then both members of the pair are set to some reserved value not otherwise used to represent magnitude and direction.

26. An apparatus according to claim 17 comprising a CORDIC circuit means for generating said magnitude and direction values as a function of the Sobel cartesian gradient components in each principal dimension.

27. An apparatus according to claim 9 wherein said input pixel stream is selectively mapped by means of a lookup table before taking part in any computation.

28. An apparatus according to claim 9 wherein said computational element can store one or more computed images in said memory, such that a computed image can be substituted for an input image.

29. An apparatus according to claim 9 wherein said programmable computational element, random access memory, and data bus are of sufficient bit width so that more than one pixel can be transferred in one bus data transfer cycle, wherein:

A. said pixel processing element is capable of extracting an input pixel stream from bus transactions of width greater than 1 pixel;

B. said pixel processing element is capable of storing said first output pixel streams into memory using bus transactions of width greater than 1 pixel;

C. said computational element having means to minimize the number of bus transactions necessary to process images using said pixel processing element, by using multi-pixel bus transactions of the greatest possible width whenever possible.

30. A method for processing digital image data in a system of the type having

a bus for carrying control, data and address signals,

a memory coupled to said bus, for storing digital image data and for responding to access control signals on said bus for transferring digital image data therewith,

a video input, coupled to said bus, for acquiring digital image data and for responding to access control signals on said bus for transferring digital image data thereto,

an image data coprocessor, coupled to said bus, for responding to access control signals on said bus for processing digital image data received therefrom for enhancement thereof,

a CPU, coupled to said bus, for applying said access control signals to the bus for controlling said transfer of digital image data with said bus, said CPU including an address element for applying address signals to the bus, in connection with said access control signals, to locate data being transferred in connection therewith,

the method comprising:

A. signalling, when certain preselected image data from said memory is on said bus, that the data be written to the coprocessor,

B. providing for processing of the image data by the coprocessor, and

C. at a preselected time later, signalling that image data output from said coprocessor be written to the memory means.

31. A method according to claim 30 wherein said step of providing for processing of the image data includes:

A. processing an input array of digital image words by a neighborhood processor to generate an output array of digital image words, wherein the input array of digital image words is no larger in a first principal dimension than NW pixels, and no larger in a second principal dimension, normal to the first, than NH pixels, where NW is no larger than an image width, IW, where NW, NH and IW are integers greater than or equal to one,

B. said processing including generating a word of the output array corresponding to each respective word of the input array, and

C. said processing further including generating each such word of said output array based on values of words in a neighborhood of the respective word of said input array, wherein said neighborhood comprises a plurality of digital image words corresponding to adjacent pixels in the corresponding acquired digital image data.

32. A method according to claim 31, including

A. providing buffer memory for storing digital image words in an array of NH rows of IW columns;

B. storing into said buffer memory one or more input digital image data words and simultaneously retrieving therefrom a neighborhood of NW by NH digital image words;

C. computing from said neighborhoods, one or more output digital image words representing at least a portion of said enhanced digital image data.

33. A method according to claims 31 or 32, including rank value filtering comprising:

A. inputting a neighborhood of digital image words, each said candidate digital image data word comprising a plurality of bits, from most significant to least significant bits,

B. initially storing a predetermined rank of word to be selected from said plurality of candidate digital image data words,

C. storing a mask associated with each of said input digital image data words, each said mask being at least initially set to identify input words as candidates,

D. iteratively testing bits of the same significance from all of the candidate digital image data words, and generating a corresponding bit portion of a resultant digital word of the desired rank, and

E. generating said resultant digital word as representative of said predetermined rank.

34. A method according to claims 31 and 32, including gray scale morphology steps including:

A. performing a preprocessing selected mathematical function on an input neighborhood of digital image words to form a preprocessed neighborhood of digital image words,

B. performing rank value filtering for selecting from said preprocessed neighborhood of digital image words a digital word of predetermined rank,

C. said rank value filtering step including;

(i) storing a mask associated with each of said digital image data words, each said mask being at least initially set to identify input words as candidates,

(ii) iteratively testing bits of the same significance from all of the candidate digital image data words, and generating a corresponding bit portion of a resultant digital word of the desired range, and

(iii) generating said resultant digital word as representative of said predetermined rank, and

D. generating said selected digital value as representative of one or more values in said input neighborhood of digital values.

35. A method for digital image processing in a system comprising

image source means generating digital image data representative of one or more images,

image data co-processing means, coupled to said image source means, for processing digital image data received therefrom,

CPU means, coupled to said image source means to said image data co-processing means, for generating and applying thereto control signals to

i) control the transfer of rows of digital image data from said image source means to said image data co-processing means, each said row comprising adjacent portions of an image along a first axis thereof, said transferred rows being any of (a) successive rows of a single image adjacent along a second axis, and (b) single corresponding rows of successive images,

ii) control the processing of said transferred rows by said image data co-processing means,

the method comprising

A. inputting said rows of said digital image data,

B. accumulating said rows of digital image data, said accumulated rows being any of (a) said successive rows of a single image adjacent along a second axis, and (b) said single corresponding rows of successive images,

C. selectively responding to said control signals to selectively process successive rows of a single image received therefrom,

D. selectively responding to control signals received from said CPU means to selectively process said single corresponding rows of successive images.

36. A method according to claim 35, including providing reconfigurable processing means selectively actuable in response to control signals received from said CPU means for (i) processing successive rows of a single image received therefrom, and (ii) processing said single rows of successive images.