Method and system of separately identifying clumped homogeneous objects in an image

• US 5,671,290 A
• Filed: 07/29/1994
• Issued: 09/23/1997
• Est. Priority Date: 09/27/1991
• Status: Expired due to Term

• 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
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/283,482
• Time in Patent Office: 1,152 Days
• Field of Search: 382/6, 382/14, 382/18, 382/39, 382/48, 382/51, 382/53, 382/19, 382/52, 382/133, 382/134, 382/173, 382/224, 382/225, 382/270, 382/272, 382/273, 382/271, 382/203, 364/413.13, 364/413.18
• US Class Current: 382/133
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 2207/30024 Cell structures in vitro; Tissue sections in vitro
• CPC Class Codes: G06T 2207/30128 Food products
• CPC Class Codes: G06T 7/0012 Biomedical image inspection
• CPC Class Codes: G06T 7/11 Region-based segmentation
• 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/695 Preprocessing, e.g. image segmentation

Abstract

The present invention relates to an image analysis method and system for separately identifying each clumped homogeneous object in an image. The image includes at least one clump of homogeneous objects and at least one isolated homogeneous object. This image analysis method may be used in image analysis methods and systems for identifying objects in a background by generating a description, which may be either a histogram or co-occurrence matrix, of the gray level space of the image by using an entropic kernel to recursively analyze the gray level space for candidate objects and validating the presence of valid objects by comparing the candidate object attribute values to a defined set of valid object attribute values contained in a driver. The present invention includes recursive, iterative and parallel processing methods. The methods may be used in a wide variety of industrial inspection techniques, including colony counting and the identification of discrete features in carpets and of pigment elements embedded in a polymer.

Claims

1. A method of separately identifying each clumped homogenous object in an image comprising at least one clump of homogeneous objects, comprising the steps of:

(a) identifying at least one candidate clump, wherein the candidate clump has an area greater than a first predetermined area of an isolated homogeneous object and a shape factor less than a predetermined clump shape factor;

(b) creating a distance buffer, wherein the distance buffer comprises a plurality of distance values representing the distance of each perimeter point of the candidate clump to the center of mass of the candidate clump, the distance values including a plurality of peaks and valleys;

(c) searching the buffer for a first valley using a hysteresis-based, valley-finding algorithm;

(d) shifting the distance buffer by a distance equal to the distance to the first valley from a first distance value as defined by a first predetermined point on the perimeter of the candidate clump;

(e) counting the number of peaks in the shifted buffer using a hysteresis-based, peak-finding algorithm to calculate a first value for the number of homogeneous objects in the clump; and

(f) associating each perimeter point corresponding to a given peak in the shifted distance buffer with a homogeneous object in the clump, thereby separately identifying each homogeneous object in the image.

2. The method as claimed in claim 1, wherein the counting step further includes the sub-step of dividing the number of peaks by two to obtain a result, rounding the result up to the next higher integer, and adding one to the next higher integer to calculate the first value.

3. The method as claimed in claim 13, wherein the counting step further includes the sub-step of calculating the area of the candidate clump and dividing the area of the candidate clump by the mean area of the isolated homogeneous object to calculate a second value for the number of homogeneous objects in the clump.

4. The method as claimed in claim 3, wherein the counting step further includes the sub-step of calculating the area of the candidate clump and dividing the area of the candidate clump by a second predetermined area to calculate a third value for the number of homogeneous objects in the clump.

5. The method as claimed in claim 4, wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the average value as the number of homogeneous objects if the average value is greater than the first value.

7. The method as claimed in claim 4, wherein the counting step includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the average value as the number of

homogeneous objects if the first value is greater than three.

8. The method as claimed in claim 4, wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the first value as the number of homogeneous objects if the first value is less than or equal to three.

9. The method as claimed in one of claims 5 or 7, further including the step of tracing the clump in a singular color indicative of the number of homogeneous objects in the candidate clump.

13. The method of claim 1, wherein the image further comprises an isolated homogeneous object and the isolated homogeneous object has a predetermined clump shape factor.

14. The method of claim 1, wherein the second predetermined area is the mean area of the isolated homogeneous object minus one-half the standard deviation of the mean area of the isolated homogeneous object.

15. The method of claim 14, wherein the second predetermined area is the mean area of the isolated homogeneous object minus one-half the standard deviation of the mean area of the isolated homogeneous object.

25. The method as claimed in claim 4, wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the first value as the number of valid, homogeneous objects if the average value is less than or equal to the first value.

29. The method as claimed in one of claims 25 or 27, further including the step of tracing the clump in a plurality of colors indicative of the number of valid, homogeneous objects in the .candidate clump, wherein all the points of the perimeter of the clump of valid, homogeneous objects between the adjacent valleys on the distance buffer are traced in the same color.

6. The method as claimed in claim wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the first value as the number of

homogeneous objects if the average value is less than or equal to the first value.

10. The method as claimed in one of claims 6 or 7, further including the step of tracing the clump in a plurality of colors indicative of the number of homogeneous objects in the candidate clump, wherein all the points of the perimeter of the clump of homogeneous objects between the adjacent valleys on the distance buffer are traced in the same color.

11. A method of identifying the number of homogeneous objects in an image comprising at least one clump of homogeneous objects and at least one isolated homogeneous object, comprising the steps of:

(a) identifying at least one candidate clump, wherein the candidate clump has an area greater than a first predetermined area of an isolated homogeneous object and a shape factor less than a predetermined clump shame factor;

(b) calculating the area of the candidate clump;

(c) calculating the mean area of the at least one isolated homogeneous object;

(d) dividing the area of the candidate clump by the mean area of the isolated homogeneous object to calculate a value for the number of homogeneous objects in the clump;

(e) associating the value for the number of step (d) with the candidate clump, thereby identifying the number of homogeneous objects in the clump;

(f) repeating steps (a) through (e) for each clump; and

(g) summing the number of homogeneous objects in each clump and the number of isolated homogeneous objects, thereby identifying the total number of homogeneous objects in the image.

12. A method of identifying the number of homogeneous objects in an image comprising at least one clump of homogeneous objects and at least one isolated homogeneous object, comprising the steps of:

(a) identifying at least one candidate clump, wherein the candidate clump has an area greater than a first predetermined area of an isolated homogeneous object and a shape factor less than a predetermined clump shape factor;

(b) calculating the area of the candidate clump;

(c) dividing the area of the candidate clump by a predetermined area to calculate a value for the number of homogeneous objects in the clump;

(d) associating the value for the number of step (c) with the candidate clump, thereby identifying the number of homogeneous objects in the clump;

(e) repeating steps (a) through (d) for each clump; and

(g) summing the number of homogeneous objects in each clump and the number of isolated homogeneous objects, thereby identifying the total number of homogeneous objects in the image.

16. A method of separating homogeneous objects from each other in order to determine the number of homogeneous objects in a clump of homogeneous objects in a background, comprising the steps of:

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

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

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

(d) searching the image using the entropically selected threshold gray level for at least one candidate object having at least one candidate object attribute value, wherein the the image comprises at least one candidate clump of candidate objects;

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

(f) identifying as the candidate clump a clump having an area greater than a first predetermined area and a shape factor less than a predetermined clump shape factor; and

(g) separating valid homogeneous objects from each other in order to determine the number of valid homogeneous objects in the candidate clump.

17. The method as claimed in claim 16, wherein the separating step includes the sub-steps of:

(i) creating a distance buffer, wherein the distance buffer comprises a plurality of distance values representing the distance of each perimeter point of the candidate clump to the center of mass of the candidate clump, the distance values including a plurality of valleys and peaks;

(ii) searching the buffer for a first valley using a hysteresis-based, valley-finding algorithm;

(iii) shifting the distance buffer by a distance equal to the distance to the first valley from a first distance value as defined by a first predetermined point on the perimeter of the candidate clump,

(iv) counting the number of peaks in the shifted buffer using a hysteresis-based, peak-finding algorithm to calculate a first value for the number of valid objects in the clump, and

(v) associating each perimeter point corresponding to a given peak in the shifted distance buffer with a homogeneous valid object in the clump, thereby separately identifying each homogeneous valid object in the image.

18. The method as claimed in claim 17, wherein the counting sub-step further includes the sub-step of dividing the number of peaks by two to obtain a result, rounding the result up to the next higher integer and adding one to the next higher integer to calculate the first value.

19. The method as claimed in claim 17, wherein the image further comprises an isolated homogeneous object and the isolated homogeneous object has a predetermined shape factor.

20. The method as claimed in claim 19, wherein the counting step further includes the sub-step of calculating the area of the candidate clump and dividing the area of the candidate clump by the mean area of the isolated homogeneous object to calculate a second value for the number of homogeneous valid objects in the clump.

21. The method as claimed in claim 20, wherein the counting step further includes the sub-step of calculating the area of the candidate clump and dividing the area of the candidate clump by a second predetermined area to calculate a third value for the number of valid, homogenous objects in the clump.

22. The method of claim 19, wherein the first predetermined area is the mean area of the isolated valid object.

23. The method of claim 19, wherein the second predetermined area is mean area of the isolated, valid, homogeneous object minus one-half the standard deviation of the mean area of the isolated, valid homogeneous object.

24. The method as claimed in claim 21, wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the average value as the number of valid, homogeneous objects if the average value is greater than the first value.

26. The method as claimed in claim 21, wherein the counting step includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the average value as the number of valid, homogeneous objects if the first value is greater than three.

27. The method as claimed in claim 21, wherein the counting step further includes the sub-steps of:

(i) computing the average value of the second and third values,

(ii) comparing the average value to the first value, and

(iii) selecting the first value as the number of valid, homogeneous objects if the average value is less than or equal to three.

28. The method as claimed in one of claims 24 or 26, further including the step of tracing the clump in a singular color indicative of the number of valid, homogeneous objects in the candidate clump.