Methods for determining the exterior points of an object in a background

• US 5,579,409 A
• Filed: 11/30/1993
• Issued: 11/26/1996
• 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: Kalayeh, Hooshmand M., Vaidyanathan, Akhileswar G.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/159,641
• Time in Patent Office: 1,092 Days
• Field of Search: 382/48, 382/21, 382/22, 382/26, 382/25, 382/197, 382/199, 382/201, 382/203, 382/276, 382/282, 382/204, 395/141
• US Class Current: 382/203
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• 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/12 Edge-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/69 Microscopic objects, e.g. biological cells or cellular parts

Abstract

Accessing the exterior points of an object is used in the area of object identification when it is important to use the information in the local exterior environment of an object in order to extract a feature which may be useful for object recognition. Examples of this type of feature which are important for recognizing and classifying objects occur in the area if bacterial detection. Adaptive classification is a way of making the analysis independent of variations in imaging conditions, such as lighting, positioning, electronic amplification, etc. Two general methods can be used to access the local exterior environment of an object, knowing the perimeter points of the object. In the first method, the shape of an annular exterior region around the object of interest can be made to follow the shape of the object itself. In the second method, an known exterior shape, such as a circle, is used to characterize the exterior contour region, approximating the shape of the object.

Claims

1. A method for determining the exterior points of an object in a background, comprising the steps of:

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

(b) searching the image for the object;

(c) determining the perimeter points of the object, each perimeter point having a row-position coordinate value and a column-position coordinate value;

(d) creating a perimeter buffer, the perimeter buffer comprising the perimeter points;

(e) sorting the perimeter points in the perimeter buffer first by row and then by column to create a row-column sorted perimeter buffer; and

(f) designating as the exterior points of the object all the points on each row which are a first predetermined number of pixels before the perimeter point having the lowest column-position coordinate value and a second predetermined number of pixels beyond the perimeter point having the highest column-position coordinate value for each respective row.

3. The method of claim 1, further comprising the steps of:

(g) sorting the perimeter points in the perimeter buffer by column and then by row to create a column-row sorted perimeter buffer; and

(h) designating as the exterior points of the object all the points in each column which are a predetermined number of pixels before the perimeter point having the lowest row position coordinate value and a predetermined number of pixels beyond the perimeter point having the highest row-position coordinate value for each respective column.

21. The method of one of claims 1, 5, 6, 15, 17, 18, 19 or 20, wherein the step of searching the image includes the sub-steps of:

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

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

(iii) scanning the image for at least one object using the entropically selected threshodl gray level value, and

(iv) tracing the candidate object having boundary gray level values determined by the entropically selected threshold gray level value.

2. A method for determining the exterior points of an object in a background, comprising the steps of:

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

(b) searching the image for the object;

(c) determining the perimeter points of the object, each perimeter point having a row-position coordinate value and a column-position coordinate value;

(d) creating a perimeter buffer, the perimeter buffer comprising the perimeter points;

(e) sorting the perimeter points in the perimeter buffer first by column and then by row to create a column-row sorted perimeter buffer; and

(f) designating as the exterior points of the object all the points on each column which are a first predetermined number of pixels before the perimeter point having the lowest row-position coordinate value and a second predetermined number of pixels beyond the perimeter point having the highest row-position coordinate value for each respective column.

4. The method of claim 2, further comprising the steps of:

(g) sorting the perimeter points in the perimeter buffer by row and then by column to create a row-column sorted perimeter buffer; and

(h) designating as the exterior points of the object all the points in each row which are a predetermined number of pixels before the perimeter point having the lowest column-position coordinate value and a predetermined number of pixels beyond the perimeter point having the highest column-position coordinate value for each respective row.

5. A method for determining the exterior point of an object in a background, comprising the steps of:

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

(b) searching the image for the object;

(c) determining the perimeter points of the object;

(d) determining the interior points of the object;

(e) labeling the interior points of the object with a predetermined gray level value; and

(f) defining an exterior contour region for each object by;

(i) creating a perimeter buffer for the object, the perimeter buffer comprising the perimeter points, each perimeter point having a row-position coordinate value and a column-position coordinate value,

(ii) sorting the perimeter points in the perimeter buffer first by row and then by column to create a row-column sorted perimeter buffer for the object, and

(iii) designating as the exterior points of the object all the points in each row which are a predetermined number of pixels from the perimeter point having the lowest column-position coordinate value and the highest column-position coordinate value for each respective row, wherein each designated exterior points has a value other than the predetermined gray level value.

6. A method for determining the exterior points of an object in a background, comprising the steps of:

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

(b) searching the image for the object;

(c) determining the perimeter points of the object;

(d) determining the interior points of the object;

(e) labeling the interior points of the object with a predetermined gray level valve; and

(f) defining an exterior contour region for the object by;

(i) determining the perimeter points of the contour region,

(ii) creating a contour region perimeter buffer, the contour perimeter buffer comprising the contour region perimeter points, each contour region 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 contour region perimeter point, the first direction code value describing the relationship of each respective contour region perimeter point to the next contour region perimeter point and the second direction code value describing the relationship of each respective contour region perimeter point to the previous contour region perimeter point,

(iii) sorting the contour region perimeter points in the contour region perimeter buffer in a predetermined order to create a sorted contour region perimeter buffer,

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

(v) designating as the exterior points of the object each point on the same line segment as the contour region perimeter point being examined and lying between the examined contour point and the next contour perimeter point in the sorted contour region perimeter buffer, the examined contour region perimeter point being assigned the first value of the status variable, where each designated exterior point has a value other than the predetermined gray level value.

7. The method of claim 6, wherein the step of defining a contour region includes the sub-steps of:

(i) assigning a first predetermined shape to the object,

(ii) assigning a second predetermined shape to an area including the exterior contour region and the object,

(iii) calculating a first size parameter for the object, and

(iv) calculating a second size parameter for the second predetermined shape, wherein the second size parameter is larger than the first size parameter and the second size parameter encompasses the object.

8. The method of claim 7, wherein the first predetermined shape is a circle and the first size parameter is a first equivalent radius.

9. The method of claim 7, wherein the second predetermined shape is a circle and the second size parameter is a second equivalent radius.

10. The method of claim 7, wherein the sub-step of calculating a first size parameter includes the further sub-steps of:

(A) determining the four extremum points of the object,

(B) calculating the maximum distance between the extremum points of the object, and

(C) setting the first size parameter to a diameter which is equal to the maximum distance between the extremum points of the object.

11. The method of claim 6, further including the steps of:

(l) determining the gray level value of each exterior point, and

(m) characterizing the object by using the gray level values of the exterior points.

12. The method of claim 11, wherein the characterizing step comprises determining the color of the exterior points of the object.

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

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

(b) searching the image for at least one candidate object, wherein the candidate object has at least one candidate object attribute value;

(c) determining the perimeter points of the candidate object, each perimeter point having a row-position coordinate value and a column-position coordinate value;

(d) creating a perimeter buffer, the perimeter buffer comprising the perimeter points;

(e) sorting the perimeter points in the perimeter buffer first by row and then by column to create a row-column sorted perimeter buffer;

(f) designating as the exterior points of the object all the points on each row which are a predetermined number of pixels before the perimeter point having the lowest column-position coordinate value and a predetermined number of pixels beyond the perimeter point having the highest column-position coordinate value for each respective row;

(g) characterizing the candidate object by the candidate object attribute value; and

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

14. The method of claim 13, wherein the searching step comprises searching the image using at least one automatically calculated threshold.

15. The method of claim 13, wherein the characterizing step includes the sub-steps of:

(i) determining the gray level value of each exterior point, and

(ii) characterizing the object by using the gray level values of the exterior points.

16. The method of claim 13, further including the step of determining the interior points of the object.

17. The method of claim 16, wherein the characterizing step includes the sub-steps of:

(i) determining the gray level value of each exterior point and the gray level value of each interior point, and

(ii) characterizing the object by the relative normalized difference between the gray level values of the exterior and the interior points.

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

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

(b) searching the image for at least one candidate object using at least one automatically calculated threshold, wherein the candidate object has at least one candidate object attribute value;

(c) determining the perimeter points of the candidate object;

(d) determining the interior points of the candidate object;

(e) labeling the interior points of the candidate object with a predetermined gray level value;

(f) defining an exterior contour region of the candidate object by;

(i) determining the perimeter points of the contour region;

(ii) creating a contour region perimeter buffer, the contour region perimeter buffer comprising the perimeter points of the contour region, each contour region 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 contour perimeter point, the first direction code value describing the relationship of each respective contour region perimeter point to the next contour region perimeter point and the second direction code value describing the relationship of each respective contour region perimeter point to the previous contour region perimeter point;

(iii) sorting the perimeter points in the contour region perimeter buffer in a predetermined order to create a sorted contour region perimeter buffer;

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

(v) designating as the exterior points of the candidate object each point on the same line segment as the contour region perimeter point being examined and lying between the examined contour region perimeter point and the next perimeter point in the sorted contour region perimeter buffer, the examined contour region perimeter point being assigned the first value of the status variable, wherein the designated points have a value other than the predetermined gray level value;

(l) characterizing the candidate object by the candidate object attribute value; and

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

19. The method of claim 18, wherein the characterizing step includes the sub-step of:

(i) determining the gray level value of each exterior point, and

(ii) characterizing the object by using the gray level values of the exterior points.

20. The method of claim 18, wherein the characterizing step includes the sub-steps of:

(i) determining the gray level value of each exterior point and the gray level value of each interior point, and

(ii) characterizing the object by the relative difference between the gray level values of the exterior and the interior points.

22. The method of one of claims 5, 6 or 18, wherein the step of determining the interior points of the object comprises the sub-steps of:

(i) creating a perimeter buffer, the perimeter buffer comprising the perimeter points of the 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,

(ii) sorting the perimeter points in the perimeter buffer in a predetermined order to create a sorted perimeter buffer,

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

(iv) designating as the interior points of the object each point on the same line segement as the perimeter point being examined and lying between the examined perimeter point and the next perimeter point in the sorted perimeter buffer, the examined perimeter point being assigned the first value of the status variable.