Adaptive vision system using dual thresholding

• US 5,982,944 A
• Filed: 12/16/1997
• Issued: 11/09/1999
• Est. Priority Date: 09/27/1991
• Status: Expired due to Fees

• Current Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Original Assignee: E. I. du Pont de Nemours and Company (Corteva, Inc.)
• Inventors: Vaidyanathan, Akhileswar Ganesh, Whitcomb, James Arthur
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/991,695
• Time in Patent Office: 693 Days
• Field of Search: 382/271, 382/168, 382/172, 382/169, 382/273, 382/274, 382/251, 382/253, 382/270, 358/466, 307/350
• US Class Current: 382/271
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/45 using co-occurrence matrix computation

Abstract

Image analysis methods and systems are used for identifying objects in a background by defining a data space, such as a histogram or a color space. The data space comprises a plurality of sub-spaces, which could be selected based, for example, on a histogram, or on the way pixel values or color parameters cluster in their respective spaces. The threshold values in the data space are selected, a list of all ordered pairs of thresholds is generated to define multiple data sub-spaces, and the image is multiply searched, once in each sub-space for at least one representation of a candidate object, where the candidate object has at least one predetermined attribute value. Valid objects are identified by comparing the candidate object attribute values to a defined set of valid object attribute values contained in a driver.

Claims

1. A method of identifying at least one valid object having at least one predetermined attribute value in a background, comprising the steps of:

(a) generating an image of the object and the background;

(b) defining a data space representative of the image;

(c) generating a list of ordered threshold pairs;

(d) subdividing the data space into a plurality of sub-spaces by using the threshold pairs;

(e) selecting at least one sub-space;

(f) searching the image multiple times using each selected sub-space for at least one representation of a candidate object, wherein the candidate object has at least one predetermined attribute value; and

(g) validating the candidate object having the predetermined attribute value to identify the at least one valid object.

2. The method of claim 1, wherein the step of multiply searching the image comprises scanning the image once using each of the sub-spaces simultaneously.

3. The method of claim 1, wherein the step of multiply searching the image comprises scanning the image multiple times using a selected sub-space for each scan.

4. The method of claim 1, wherein the data space comprises a color space of the image.

5. The method of claim 1, wherein the data space comprises a space resulting from the transformation of pixel values of an image.

6. The method of claim 1, wherein the step of defining the data space comprises generating a gray level histogram of the image, where the gray level histogram has an entropy function.

7. The method of claim 6, wherein the step of selecting a sub-space comprises entropically selecting a threshold gray level such that the entropy function of the histogram is maximized.

8. The method of claim 7, wherein the step of entropically selecting a threshold pixel value includes the sub-steps of:

(i) sequentially partitioning the pixel value histogram at each pixel value into a first partition and a second partition, and

(ii) computing the entropy function for each partition, where the total entropy function of the histogram is defined as the sum of the entropy function of the first partition and the entropy function of the second partition.

9. The method of claim 1, wherein the subdividing step includes subdividing the data space into an upper sub-space and a lower sub-space, further including the steps of recursively repeating the steps of subdividing the data space into an upper sub-space and a lower sub-space, selecting at least one upper or lower sub-space, searching the image multiple times using each selected sub-space for at least one representation of a candidate object, and validating the candidate object having the predetermined attribute value, wherein the repetition of the selection step selects a next successive sub-space, thereby recursively partitioning the data space until a condition for terminating the multiple searching has been reached.

10. The method of claim 1, wherein the validating step comprises performing a redundancy check to prevent multiple identifications of the candidate object of step (g) by:

(i) calculating the candidate object attribute values for each selected representation, and

(ii) comparing the candidate object attribute values in the selected representation to the valid object predetermined attribute values to identify the valid object.

11. The method of claim 1, wherein the step of generating a list of ordered threshold pairs comprises the sub-steps of:

(i) automatically selecting a plurality of threshold pixel values in the data space;

(ii) generating a list of all ordered pairs of threshold pixel values.

12. The method of claim 11, wherein the step of subdividing the data space into a plurality of sub-spaces comprises the sub-steps of:

(i) generating a pixel value histogram of the data space,

(ii) generating a plurality of pixel value upper and lower histograms,

(iii) automatically selecting a threshold pixel value for each upper histogram and each lower histogram,

(iv) generating a list of all ordered pairs of the selected threshold pixel values, and

(v) using the pairs of threshold pixel values as respective lower delimiters and upper delimiters to define the plurality of data sub-spaces.

13. The method of claim 12, wherein the pixel value histogram has an entropy function, each pixel value upper and lower histogram has a respective entropy function, and the threshold pixel value for each upper histogram and each lower histogram is automatically selected such that the entropy function for each histogram is maximized.

14. The method of claim 11, wherein the sub-step of automatically selecting a plurality of threshold pixel values comprises recursively selecting the threshold pixel values for the data space, and further wherein the step of subdividing the data space into a plurality of sub-spaces comprises using the pairs of threshold pixel values as respective lower and upper delimiters to define data sub-spaces in which to search the image.

15. The method of claim 14, wherein the recursively selecting sub-step further comprises the sub-steps of:

(A) generating a pixel value histogram of the data space, the pixel value histogram having an entropy function,

(B) entropically selecting a threshold pixel value such that the entropy function of the histogram is maximized,

(C) subdividing the histogram into an upper histogram and a lower histogram using the threshold pixel value, and

(D) recursively repeating steps (A), (B) and (C) for each of the upper and lower histograms, wherein the repetition of step (B) selects a next threshold pixel value, thereby recursively partitioning the data space until a condition for terminating the recursive selection has been reached.

16. The method of claim 15, wherein the terminating condition is that a minimum pixel value partition width has been reached during the recursive subdividing of the histograms.

17. The method of claim 16, wherein the validating step (g) comprises the sub-step of performing a redundancy check to prevent multiple identifications of the candidate object by:

(i) selecting the optimum representation of the candidate object, and

(ii) comparing the candidate object attribute values in the selected representation to the valid object predetermined attribute values to identify the valid object.

18. The method of claim 16, wherein the searching step (f) comprises the sub-steps of:

(i) selecting a sub-space,

(ii) generating a pixel value histogram of the image, the pixel value histogram having an entropy function,

(iii) entropically selecting a threshold pixel value such that the entropy function of the histogram is maximized,

(iv) searching the image using the entropically selected threshold pixel value for at least one candidate object.

19. The method of claim 18, further comprising the sub-steps of:

(v) subdividing the pixel value histogram into an upper histogram and a lower histogram using the entropic threshold pixel value as defined by step (iii);

(vi) recursively repeating steps (iii)-(v) for each of the upper and lower histograms, wherein the repetition of step (iii) selects the next entropic threshold pixel value, thereby recursively partitioning the pixel value histogram until a condition for terminating the multiple searching has been reached.

20. A method of identifying at least one valid object having at least one predetermined attribute value based on at least one predetermined attribute value of a previously identified object in a background, comprising the steps of:

(a) generating a set of training images in a background;

(b) defining a data space representative of the set of training images, wherein the data space comprises a plurality of sub-spaces which are defined by a list of threshold pairs;

(c) generating a list of ordered threshold pairs;

(d) subdividing the data space into a plurality of sub-spaces using the list of threshold pairs;

(e) searching the set of training images multiple times using once in each selected sub-space, to generate a plurality of representations of candidate objects, wherein each candidate object has at least one predetermined attribute value;

(f) validating the candidate object having the predetermined attribute values to identify at least one valid object for the set of images, wherein each valid object has a sub-space associated therewith;

(g) generating a reduced-size list of the ordered threshold pairs that correspond to each valid object for the set of training images;

(h) generating a set of testing images in another background;

(i) defining a data space representative of the set of testing images;

(j) subdividing the data space of step (i) into a reduced set of data sub-spaces corresponding to each valid object of step (f) by using the reduced-size list of threshold pairs;

(k) searching the set of testing images of step (h) multiple times, using each selected sub-space of the reduced set of sub-spaces, once in each sub-space of the reduced set of data sub-spaces, to generate a plurality of representations of at least one candidate object, wherein the candidate object has the at least one predetermined attribute value; and

(l) validating the at least one candidate object having the valid object predetermined attribute value.