Method for resolving redundant identifications of an object

• US 6,058,209 A
• Filed: 12/05/1994
• Issued: 05/02/2000
• 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: Whitcomb, James Arthur, Vaidyanathan, Akhileswar Ganesh
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/349,581
• Time in Patent Office: 1,975 Days
• Field of Search: 382/128, 382/133, 382/134, 382/224, 382/225, 382/203, 382/204, 382/286, 382/201
• US Class Current: 382/203
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 2207/10056 Microscopic image
• CPC Class Codes: G06T 2207/30024 Cell structures in vitro; Tissue sections in vitro
• CPC Class Codes: G06T 7/0012 Biomedical image inspection
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 20/69 Microscopic objects, e.g. biological cells or cellular parts
• CPC Class Codes: G09G 5/06 using colour palettes, e.g. look-up tables

Abstract

When identifying an object in an image, very often redundant identifications of the object may occur. The present invention relates to methods of image analysis for resolving such redundant identifications of an object. More specifically, the present invention relates to object identification schemes which obtain multiple representations of the same object. In addition, such identification schemes may identify void, or donut-shaped objects when a single search, or multiples searches, of the image are performed. Further, the present invention is useful in resolving several distinct objects where other identification schemes employing either single or multiple searching have identified these distinct objects as a single clumped object. The present invention may be used, for instance, to determine whether a smaller object is contained within another, larger object.

Claims

1. A method for resolving redundant identifications of an object in an image, comprising the steps of:

(a) identifying a group of potentially redundant objects in an image;

(b) sorting the identified objects in a predetermined order to create a sorted list of objects, the initial object in the list having an initial characteristic value and the last object in the list having a last characteristic value;

(c) defining an object status variable, the object status variable having one of a first and a second value;

(d) assigning the first value of the object status variable to the initial object in the sorted list;

(e) comparing each respective object subsequent to the initial object to each object having a characteristic value less than the characteristic value of the respective, subsequent object and having the first value of the object status variable, wherein each respective, subsequent object is defined as a first object and each object having a characteristic value less than the characteristic value of the first object is defined as a second object for each comparison;

(f) determining whether each respective second object has a characteristic value contained within a predetermined range of the characteristic value of the first object, thereby assigning one of the first and the second status values of the object status variable to each respective first object and to each respective second object in order to resolve redundant identifications of an object in the image; and

(g) identifying the objects having the first value of the object status variable of step (f) as non-redundant objects and retaining the non-redundant objects.

2. The method of claim 1, wherein the determining step comprises the sub-steps of:

(i) retaining the first object and setting the object status variable of the first object to the first value if no second object has a characteristic value within the predetermined range of the characteristic value of the first object,

(ii) retaining the first object and setting the object status variable of the first object to the first value if only one second object has a characteristic value within the predetermined range of the characteristic value of the first object and deleting the second object, and

(iii) deleting the first object and setting the object status variable of the second object to the first value if more than one second object has a characteristic value within the predetermined range of the characteristic value of the first object.

3. The method of claim 1, wherein the determining step comprises the sub-steps of:

(i) retaining the first object and setting the object status variable of the first object to the first value if no second object has a characteristic value within the predetermined range of the characteristic value of the first object,

(ii) retaining the first object and setting the object status variable of the first object to the first value if only one second object has a first characteristic value within the predetermined range of the characteristic value of the first object and the first object has a greater second characteristic value of the first object and deleting the second object,

(iii) retaining the second object and setting the object status variable of the second object to the first value if only one second object has a first characteristic value within the predetermined range of the characteristic value of the first object and the first object has a lesser second characteristic value and deleting the first object, and

(iv) deleting the first object and setting the object status variable of the second object to the first value if more than one second object has a first characteristic value within the predetermined range of the first characteristic value of the first object.

4. The method of claim 2, wherein the first object is a larger object as compared to the second object, and the second object is a smaller object as compared to the first object, and the determining step comprises determining whether the smaller object is contained within the larger object and further includes the sub-steps of:

(iv) determining the perimeter points of the larger object,

(v) creating a perimeter buffer, the perimeter buffer comprising the perimeter points of the larger object, each perimeter point having a row-position coordinate value, a column-position coordinate value and a direction code vector, the direction code vector comprising a first and a second direction code value for each perimeter point, the first direction code value describing the relationship of each respective perimeter point to the next perimeter point and the second direction code value describing the relationship of each respective perimeter point to the previous perimeter point,

(vi) sorting the perimeter points in the perimeter buffer in a predetermined order to create a row-column sorted perimeter buffer,

(vii) assigning to each perimeter point in the buffer a perimeter point status variable having one of a first and a second value, the value of the perimeter point status variable being determined by the first and second direction code values,

(viii) designating the smaller object as being contained within the larger object if the column-position coordinate value of a predetermined point of the smaller object lies between the values of the column-position coordinate value of a perimeter point having the first value of the perimeter point status variable and the column-position coordinate value of the next perimeter point in the sorted perimeter buffer, wherein the perimeter points have the same row-position coordinate value as the predetermined point of the smaller object.

5. The method of claim 3, wherein the first object is a larger object as compared to the second object, and the second object is a smaller object as compared to the first object, and the determining step comprises determining whether the smaller object is contained within the larger object and further includes the sub-steps of:

(v) determining the perimeter points of the larger object,

(vi) creating a perimeter buffer, the perimeter buffer comprising the perimeter points of the larger object, each perimeter point having a row-position coordinate value, a column-position coordinate value and a direction code vector, the direction code vector comprising a first and a second direction code value for each perimeter point, the first direction code value describing the relationship of each respective perimeter point to the next perimeter point and the second direction code value describing the relationship of each respective perimeter point to the previous perimeter point,

(vii) sorting the perimeter points in the perimeter buffer in a predetermined order to create a row-column sorted perimeter buffer,

(viii) assigning to each perimeter point in the buffer a perimeter point status variable having one of a first and a second value, the value of the perimeter point status variable being determined by the first and second direction code values,

(ix) designating the smaller object as being contained within the larger object if the column-position coordinate value of a predetermined point of the smaller object lies between the values of the column-position coordinate value of a perimeter point having the first value of the perimeter point status variable and the column-position coordinate value of the next perimeter point in the sorted perimeter buffer, wherein the perimeter points have the same row-position coordinate value as the predetermined point of the smaller object.

6. The method of claim 4, wherein the sub-step of designating the smaller object as being contained within the larger object further includes the following sub-steps performed prior to sub-steps (iv)-(viii):

(ix) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(x) constructing a rectangle bounding the larger object by using the row and column-position coordinate values of the four extremum points,

(xi) determining a predetermined point on the smaller object, the predetermined point having a row-position coordinate value and a column-position coordinate value,

(xii) determining the position of the predetermined point of the smaller object with respect to the rectangle bounding the larger object,

(xiii) performing steps (iv)-(viii) only if the predetermined point of the smaller object is contained within the rectangle bounding the larger object, and

(xiv) designating the smaller object as not contained within the larger object if the predetermined point of the smaller object is not contained within the rectangle bounding the larger object.

7. The method of claim 2, wherein the first object is a larger object as compared to the second object, and the second object is a smaller object as compared to the first object, and the determining step comprises determining whether the smaller object is contained within the larger object and the determining step further includes the sub-steps of:

(ix) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(x) constructing a rectangle bounding the larger object by using the row and column-position coordinate values of the four extremum points,

(xi) determining a predetermined point on the smaller object, the predetermined point having a predetermined row-position coordinate value and a predetermined column-position coordinate value,

(xii) determining the position of the predetermined point of the smaller object with respect to the rectangle bounding the larger object, and

(xiii) designating the smaller object as contained within the larger object if the predetermined point of the smaller object is contained within the rectangle.

8. The method of claim 5, wherein the first object is a larger object as compared to the second object, and the second object is a smaller object as compared to the first object, and the determining step comprises determining whether the smaller object is contained within the larger object and further includes the following sub-steps performed prior to sub-steps (v)-(ix):

(x) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(xii) constructing a rectangle bounding the smaller object by using the row and column-position coordinate values of the four extremum points,

(xiii) determining the four extremum points of the smaller object, and

(xiv) ignoring the smaller object if any extremum point of the smaller object is not contained within the boundary of the rectangle.

9. The method of claim 3, wherein the first object is a larger object as compared to the second object, and the second object is a smaller object as compared to the first object, and the determining step comprises determining whether the smaller object is contained within the larger object and further includes the sub-steps of:

(iv) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(v) constructing a rectangle bounding the smaller object by using the row and column-position coordinate values of the four extremum points,

(vi) determining the four extremum points of the smaller object, and

(vii) ignoring the smaller object if any extremum point of the smaller object is not contained within the boundary of the rectangle.

10. The method of claim 6, wherein the predetermined point is contained within the rectangle bounding the larger object if both of the following conditions are met:

(A) the row-position coordinate value of the predetermined point of the smaller object lies between the minimum and the maximum values for the row-position coordinate values of the rectangle bounding the larger object, and

(B) the column-position coordinate value of the predetermined point of the smaller object lies between the minimum and maximum values for the column-position coordinate values of the rectangle bounding the larger object.

11. The method of one of claims 5, 6 or 10, wherein the predetermined point is the center of mass of the smaller object.

12. The method of claim 5, 6 or 10, further including the steps of:

(h) determining a characteristic attribute of at least one predetermined point of the smaller object contained within the larger object;

(i) determining the characteristic attribute of the larger object; and

(j) retaining the larger object and the smaller object and setting the object status variable of each of the larger and smaller objects to the first value if the difference in the characteristic attribute of the at least one predetermined point of the larger object with respect to the characteristic attribute of the predetermined point of the smaller object contained within the larger object exceeds a predetermined minimum number.

13. The method of claim 12, further including the steps of:

(k) determining at least one average characteristic attribute of the interior points of the smaller object;

(l) determining the average characteristic attribute of the interior points of the larger object; and

(m) retaining the larger object and the smaller object and setting the object status variable of each of the larger and smaller objects to the first value if the difference in the average characteristic attribute of the interior points of the larger object with respect to the average characteristic attribute of the interior points of the smaller object contained within the larger object exceeds a predetermined minimum number.

14. The method of claim 13, wherein determining step (k) comprises determining the interior points of the larger object, excluding the interior points of the smaller object.

15. The method of claim 12, wherein the characteristic attribute is hue.

16. The method of claim 13, wherein the average characteristic attribute is the average hue of the interior points of each of the larger and the smaller object.

17. The method of claim 1, wherein the step of identifying a group of potentially redundant objects in an image comprises the sub-steps of:

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

(ii) defining a multi-dimensional data space comprising a plurality of sub-spaces;

(iii) selecting at least one sub-space based on the attributes of at least one candidate object;

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

(v) validating the candidate object having the predetermined attribute value to identify the valid object.

18. The method of claim 17, wherein:

(A) the multi-dimensional data space is a gray level histogram representative of the entire image, the gray level histogram having an entropy function, and a plurality of gray level upper and lower histograms, each having a respective entropy function is generated from the histogram, and

(B) the at least one sub-space is a plurality of pairs of threshold gray level values for each upper and lower histogram such that the entropy function of each upper and lower histogram is maximized, and the image is multiply searched using the selected threshold gray level pair for each upper and lower histogram for at least one representation of a candidate object.

19. A method of resolving redundant identifications of object in an image, comprising the steps of:

(a) identifying a group of potentially redundant objects;

(b) comparing the area of two identified objects and designating one of the objects as a larger object as compared to the other object and the other object as a smaller object as compared to the larger object; and

(c) determining whether the smaller object is contained within the larger object by;

(i) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(ii) constructing a rectangle bounding the larger object by using the row and column-position coordinate values of the four extremum points,

(iii) determining a predetermined point on the smaller object, the predetermined point having a predetermined row-position coordinate value and a predetermined column-position coordinate value, and

(iv) determining the position of the predetermined point of the smaller object with respect to the rectangle bounding the larger object, and

(v) designating the smaller object as contained within the larger object if the predetermined point of the smaller object is contained within the rectangle, thereby resolving the redundant identifications of each identified object in the image.

20. The method of claim 19, wherein the predetermined point is contained within the rectangle bounding the larger object if both of the following conditions are met:

(A) the row-position coordinate value of the predetermined point of the smaller object lies between the minimum and the maximum values for the row-position coordinate values of the rectangle bounding the larger object, and

(B) the column-position coordinate value of the predetermined point of the smaller object lies between the minimum and maximum values for the column-position coordinate values of the rectangle bounding the larger object.

21. A method of identifying a valid object having at least one predetermined attribute value in a background and for resolving redundant identifications of a valid object, comprising the steps of:

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

(b) generating a gray level histogram of the image, the gray level histogram having an entropy function;

(c) entropically selecting a threshold gray level value such that the entropy function of the histogram is maximized;

(d) searching the image using the entropically selected threshold gray level value for at least one representation of a candidate object, wherein the candidate object has at least one candidate object attribute value; and

(e) validating the candidate object having the valid object predetermined attribute value to identify the valid object by;

(i) comparing the areas of two valid objects and designating one of the valid objects as a larger valid object as compared to the other valid object and the other valid object as a smaller valid object as compared to the larger object,

(ii) determining the four extremum points of the larger object, each extremum point having a row-position coordinate value and a column-position coordinate value,

(iii) constructing a rectangle bounding the larger object by using the row and column-position coordinate values of the four extremum points,

(iv) determining a predetermined point on the smaller object, the predetermined point having a row-position coordinate value and a column-position coordinate value,

(v) determining the position of the predetermined point of the smaller object with respect to the rectangle bounding the larger object, and

(vi) designating the smaller object as being contained within the larger object if the predetermined point of the smaller object is contained within the rectangle bounding the larger object.

22. The method of claim 21, wherein the validating step is performed to resolve redundant identifications of inhomogeneous objects and further includes the sub-step of deleting the larger object when the larger object contains more than one smaller object.

23. The method of claim 21, wherein the validating step is performed to resolve redundant identifications of inhomogeneous objects and further includes the sub-steps of:

(vi) calculating the average edge contrast of the larger and smaller valid objects, and

(vii) deleting the object having the smaller edge contrast when the larger valid object contains only one smaller valid object.

24. The method of claim 21, wherein the validating step is performed to resolve redundant identifications of homogeneous objects and further includes the sub-steps of:

(vi) calculating the average edge contrast of the larger and smaller valid objects, and

(vii) deleting the larger object where the average edge contrast of the larger object is less than the average edge contrast of the smaller object and is less than a predetermined minimum edge contrast.

25. The method of claim 22, wherein the validating step is performed to resolve redundant identifications of inhomogeneous objects and further includes the sub-steps of:

(vi) calculating the edge contrast of the larger and smaller valid objects, and

(vii) deleting the smaller valid object where the average edge contrast of the larger valid object is greater than the average edge contrast of the smaller valid object and is greater than a predetermined maximum edge contrast.