Method and apparatus for locating the boundary of an object

• US 4,538,299 A
• Filed: 02/28/1983
• Issued: 08/27/1985
• Est. Priority Date: 12/04/1981
• Status: Expired due to Term

• Current Assignee: IRIS International Inc. (Danaher Corporation)
• Original Assignee: IRIS International Inc. (Danaher Corporation)
• Inventors: DeForest, Sherman E.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/470,208
• Time in Patent Office: 911 Days
• Field of Search: 382/6, 382/21, 382/22, 382/54, 382/60, 382/27, 382/41, 358/107, 358/166, 358/96, 358/284, 377/10, 377/11
• US Class Current: 382/197
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges

Abstract

An apparatus and method for automatically locating the boundary of an object in a field of view has a raster scan device to generate an electrical image of the field of view. The electrical image is segmented and digitized to form a first representation. The image is then processed by comparing the digitized signal to a pre-set threshold to form a second representation. A converter combines each value of the pixel of the second representation with the values of the adjacent pixels into a single value and stores it in a corresponding location in a third representation. The values of the pixels in the third representation are read out and compared to a look-up table. A chain code of the boundary of the particle is formed from the look-up table.

Claims

1. An apparatus for automatically locating the boundary of an object in a field of view, said apparatus comprising:

imaging means for forming an electrical image of the field of view;

means for forming a first representation of said image by segmenting said image into a plurality of pixels and digitizing the image intensity of each pixel into an electrical signal representing the greyscale value;

means for processing the electrical signal of each of said greyscale value to form a second representation of said image;

logic means for converting said second representation into a third representation whereby the value of a pixel at a location (hereinafter;

pixel (X,Y)) in the second representation and the values of the nearest adjacent neighbors of said pixel at said location are converted into a single value at said corresponding location (hereinafter;

P(X,Y)) in said third representation;

storage means for storing said third representation; and

table means for storing various possible values of P(X,Y), said table means for receiving a value of P(X,Y) and an input direction value, and for producing an output direction value to indicate the next location of P(X,Y) having a non-zero value;

said non-zero values of P(X,Y) form the boundary of said object.

2. The apparatus of claim 1 wherein said logic means is adapted to convert said second representation in accordance with the following rules:

(1) If pixel (X,Y)=0, then assign 0 to P(X,Y);

(2) If pixel (X,Y)=1 and all eight nearest neighbors of pixel (X,Y)=0, then assign 0 to P(X,Y);

(3) If pixel (X,Y)=1 and all four nearest neighbors of pixel (X,Y)=1, then assign 0 to P(X,Y);

(4) Otherwise assign a non-zero value to P(X,Y) wherein said value assigned to P(X,Y) is a number composed of the values of the eight nearest neighbors of pixel (X,Y).

3. The apparatus of claim 2 wherein said value assigned to P(X,Y) is a number whose value is the sum:

space="preserve" listing-type="equation">a*2.sup.7 +b*2.sup.6 +c*2.sup.5 +d*2.sup.4 +e*2.sup.3 +f*2.sup.2 +g*2+h

where a, b, c, d, e, f, g, h are the values of eight nearest neighbors surrounding the corresponding pixel (X,Y) in the following manner;

space="preserve" listing-type="tabular">______________________________________ g d h c pixel (X,Y) a f b e ______________________________________

4. The apparatus of claim 3 wherein said logic means converts said second representation in accordance with the following formula:

space="preserve" listing-type="equation">P(X,Y)=(1-a*b*c*d)*pixel(X,Y)*(a*2.sup.7 +b*2.sup.6 +c*2.sup.5 +d*2.sup.4 +e*2.sup.3 +f*2.sup.2 +g*2+h).

5. The apparatus of claim 4 wherein said table means is a PROM.

6. The apparatus of claim 1 wherein said second representation consists of a value of "0" everywhere outside of the boundary of said object and a value of "1" everywhere else.

7. The apparatus of claim 6 wherein said processing means comprises

means for comparing the greyscale of each pixel with a preset threshold value.

8. The apparatus of claim 1 wherein said object is a biological particle in a fluid.

9. The apparatus of claim 8 wherein said fluid is urine.

10. The apparatus of claim 8 wherein said fluid is blood.

11. The apparatus of claim 1 wherein said object is a pattern for a semiconductor circuit.

12. The apparatus of claim 1 wherein said object is a biological particle having a time variant quality.

13. A method for automatically locating the boundary of an object in a field of view and filtering out noise, error and the like, said method comprising:

forming an electrical image of said field of view in a device;

reading out said image from said device to produce an electrical waveform;

segmenting said electrical waveform into a plurality of electrical signals, each of said plurality of electrical signals corresponding to a pixel of said image and digitizing the amplitude of each of said signals to form a greyscale signal to form a first representation of said image;

processing each greyscale signal to form a second representation of said image;

converting said second representation into a third representation, whereby the information of each pixel at a location (hereinafter;

pixel (X,Y)) and the nearest adjacent neighbors of said pixel are embedded in a single value assigned to a corresponding location (hereinafter;

P(X,Y)) in the third representation;

scanning said third representation until a first non-zero P(X,Y) value is reached;

comparing said (P(X,Y) value and an input direction value to a look-up table to determine the next location of the non-zero value of P(X,Y) and forming a chaining code; and

continuing said chaining code formation until all non-zero values of P(X,Y) have been located.

14. The method of claim 13 further comprising storing said third representation.

15. The method of claim 13 further comprising the step of assigning a value of zero to P(X,Y) once the value of P(X,Y) has been compared to a look-up table to determine the next location of the non-zero value of P(X,Y).

16. The method of claim 15 wherein said processing step further comprises:

comparing each greyscale signal to a pre-set threshold signal.