Parallel processing method and system for identifying valid objects in a background of an image

• US 5,608,820 A
• Filed: 07/29/1994
• Issued: 03/04/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 G.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/283,310
• Time in Patent Office: 949 Days
• Field of Search: 382/168, 382/169, 382/170, 382/291, 382/173, 382/171, 382/172, 358/465, 358/366
• US Class Current: 382/169
• 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 a parallel processing image analysis method and system 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 method 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 identifying at least one valid object having at least one predetermined attribute defined by at least one predetermined attribute value 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;

(c) selecting N global entropic threshold gray levels;

(d) subdividing the gray level histogram into N+1 sub-histograms using each of the global entropically selected threshold gray levels;

(e) searching portions of the image corresponding to each sub-histogram using the global entropically selected gray levels of step (c) for at least one candidate object, each candidate object having at least one candidate object attribute value;

(f) validating the candidate objects found in step (e) having the valid object predetermined attribute values to identify the valid object;

(g) subdividing each sub-histogram into an upper sub-histogram and a lower sub-histogram using the entropic threshold gray level as defined in step (c) as an upper delimiter and a lower delimiter;

(h) selecting an entropic threshold gray level for each sub-histogram to maximize the entropy function of each of the upper and lower sub-histograms;

(i) searching portions of the image corresponding to each sub-histogram using the entropically selected gray level of step (h) for at least one candidate object, each candidate object having at least one candidate object attribute value;

(j) validating the candidate objects found in step (i) having the valid object predetermined attribute values to identify the valid object;

(k) recursively repeating steps (g)-(j) for each of the upper and lower sub-histograms, wherein the repetition of (g) uses the entropic threshold as defined in step (h) and wherein the repetition of step (h) selects a next successive entropic threshold gray level, thereby recursively partitioning each gray level sub-histogram until a predetermined minimum number of new valid objects is identified; and

(l) merging the valid objects identified within each sub-histogram found in step (j).

2. The method as claimed in claim 1, wherein the selecting step (c) includes the sub-steps of:

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

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

(iii) selecting an entropic threshold gray level such that the entropy function of the histogram is maximized,

(iv) subdividing the gray level histogram using the entropic threshold gray level as defined in step (iii) as an upper delimiter and a lower delimiter to create an upper histogram and a lower histogram,

(v) repeating steps (i)-(iii) for each of the upper and lower histograms, wherein the repetition of step (iii) selects a next successive entropic threshold gray level, and

(vi) repeating step (iv) using the next successive entropic threshold gray level as the entropic threshold gray level as defined in step (iii) to iteratively calculate the N global entropic threshold gray levels.

3. The method as claimed in claim 1, wherein the selecting step (h) includes the sub-steps of:

(i) sequentially partitioning each gray level sub-histogram at each gray level into a first and a second partition,

(ii) computing the entropy function for each partition, where the entropy function of each sub-histogram is defined as the sum of the entropy functions of the first and second partitions, and

(iii) selecting an entropic threshold gray level such that the entropy of each sub-histogram is maximized.

4. The method as claimed in claim 1, wherein the searching step of step (e) includes the sub-steps of:

(i) scanning portions of the image corresponding to each sub-histogram using each global entropically selected threshold gray level for at least one candidate object, and

(ii) tracing the candidate object having boundary gray levels determined by each global entropically selected threshold gray level, and the searching step of step (i) includes the sub-steps of;

(iii) scanning portions of the image corresponding to each sub-histogram using each entropically selected threshold gray level for at least one candidate object, and

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

5. The method as claimed in claim 1, wherein the validating step includes the sub-steps of:

(i) calculating the candidate object attribute values, and

(ii) comparing the candidate object attribute values to the valid object predetermined attribute values to find validated candidate objects.

6. The method as claimed in claim 1, wherein the validating step further includes the sub-step of checking for redundancies of the valid object and resolving the redundancies to prevent multiple identification of the valid object.

7. The method as claimed in claim 1, wherein the merging step further includes the sub-step of checking for redundancies of the valid object and resolving the redundancies to prevent multiple identification of the valid object.

8. The method as claimed in claim 1, further including the step of performing a final check for redundancies of the valid object and resolving the redundancies to prevent multiple identification of the valid object.

9. The method as claimed in claim 1, further including the step of filtering the list of candidate objects to find valid objects in the image after step (1).

10. The method as claimed in claim 1, further including the step of determining the number of valid objects in a candidate clump, wherein the candidate clump comprises a plurality of homogenous valid objects.

11. A system for identifying at least one valid object having at least one predetermined attribute defined by at least one predetermined attribute value in a background, comprising:

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

(b) computer means including a plurality of parallel processors, the parallel processors including a main parallel processor and at least one other parallel processor, the main parallel processor including;

(i) a driver for storing the definition of a valid object, and

(ii) an entropic kernel for generating a gray level histogram of the image, for selecting N global entropic threshold gray levels, for subdividing the gray level histogram into N+1 sub-histograms, for searching portions of the image corresponding to each sub-histogram using each global entropically selected gray level as an upper delimiter and a lower delimiter, for validating the candidate objects having the valid object predetermined attribute values found in the search using the global entropic threshold gray levels, and for merging the valid objects found by all the parallel processors, and the other parallel processor including;

(iii) a driver for storing the definition of a valid object, and

(iv) an entropic kernel for subdividing each sub-histogram into an upper and a lower sub-histogram using each global entropic threshold gray level, for selecting an entropic threshold gray level to maximize the entropy function of each of the upper and lower sub-histograms, for searching portions of the image corresponding to each sub-histogram using the entropically selected gray level for at least one candidate object, for validating the candidate objects having the valid object predetermined attribute values found in the search using the entropically selected threshold gray level and for recursively repeating the subdividing, selecting, searching and validating steps to recursively partition each gray level sub-histogram until a predetermined minimum number of new valid objects is identified.