Apparatus and method for image processing in symbolic space

• US 5,515,453 A
• Filed: 01/21/1994
• Issued: 05/07/1996
• Est. Priority Date: 01/21/1994
• Status: Expired due to Term

• Current Assignee: ISQA Incorporated, Rudolph Technologies Incorporated (Onto Innovation Inc.)
• Original Assignee: Beacon Systems Ltd., Texas Tech University (Texas Tech University System)
• Inventors: Hennessey, A. Kathleen, Lin, YouLing, Hahn, Kwang-Soo
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/186,750
• Time in Patent Office: 837 Days
• Field of Search: 382/8, 382/9, 382/30, 382/41, 382/16, 382/35, 382/54, 382/22, 382/56, 382/25, 382/26, 382/28, 382/33, 382/141, 382/173, 382/254, 382/209, 395/155, 395/150, 395/127, 364/413.06, 364/443, 364/449
• US Class Current: 382/141
• CPC Class Codes: G06V 10/424 Syntactic representation, e.g. by using alphabets or grammars
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

A method and apparatus (62) for processing images in symbolic space are disclosed. The method may include the steps of capturing a visual image (40), converting the visual image to a digital image (42), decomposing the digital image into image primitives (44), and processing the image primitives in symbolic space (46). The processing of the image primitives may include grouping the image primitives to form higher level image primitives, isolating portions of an image, filtering noise, identifying portions of an image, or adding to a knowledge base. The system or apparatus (62)for processing an image in symbolic space may include a camera (64), a video-to-digital converter (66), and a computer (68) with appropriate memory and software; the processing may include grouping the image primitives to form higher level image primitives, isolating portions of an image, filtering noise, identifying portions of an image, or adding to a knowledge base.

Claims

1. A method of image processing in symbolic space comprising the steps of:

capturing a visual image as a digital image;

decomposing the digital image to form image primitives;

grouping the image primitives to form higher level image primitives comprising the steps of;

(A) passing an operator window through a scope-of-view window for the image primitives with a predetermined search pattern;

(B) for each segment found by the operator window, performing the following;

(i) moving the operator window into contact with a first tangent point with respect to a first segment of the image primitives,

(ii) rotating the operator window with respect to the first tangent point to locate a second segment if one exists,

(iii) if a second segment is found, moving the operator window into contact with a second tangent point which is on the second segment, and

(iv) repeating steps (B) and (iii) for each group of segments of image primitives;

(C) recording primitives for the operator window for each group of consecutive segments found by the operator window to form higher level image primitives representing the outer trace of each group of segments found by the operator window; and

processing the higher level image primitives in symbolic space.

2. A method for isolating portions of images in a digitized image having a plurality of segments, the method comprising the steps of:

decomposing the digitized image to form image primitives; and

linking segments of image primitives by considering the location and texture of the segments.

3. The method of claim 2 wherein the steps of decomposing the digitized image to form image primitives and linking segments of image primitives by considering the location and texture of segments comprises the steps of:

decomposing the digitized image into image primitives for each segment including at least the start point, end point, left texture and right texture for each segment of the image;

forming a first group of segments having approximately the same left texture and right texture;

linking the segments of the first group of segments having end points and start points that substantially coincide to form at least a first linked segment;

forming a second group of segments having approximately the same left texture or right texture as the interior texture of the first linked segment; and

adding the segments of the second group that have approximately the same end points or start points as the end points or start points of the first linked segment to form an isolated image.

4. A method of processing a digitized image in symbolic space comprising the steps of:

decomposing the digitized image to form image primitives based on line and arc segments of the image; and

filtering noise from the image primitives by removing the segments reflecting a standard deviation greater than a predetermined threshold.

5. The method of claim 4 wherein the steps of decomposing and filtering comprise the steps of:

decomposing the digitized image into image primitives of a plurality of segments forming the digitized image, the image primitives including at least the start point, end point and deviation for each segment;

determining the length of each segment;

determining the average length of the plurality of segments; and

filtering noise from the image primitives by eliminating segments having a length less than the average length by a first predetermined threshold value and having a deviation greater than a second predetermined threshold.

6. A method for enhancing a partially occluded first visual image comprising the steps of:

capturing a second visual image as a second digital image;

decomposing the second digital image into image primitives;

adding the image primitives of the decomposed second digital image to a knowledge base as grammar primitives;

capturing a first digital image of the first visual image that is partially occluded;

decomposing the first digital image to form image primitives of the first digital image;

comparing the image primitives of the first digital image with the grammar primitives in the knowledge base of the second digital image;

comparing the image primitives of the first digital image with the grammar primitives to determine differences;

removing from the first digital image the differences between the first digital image and the second digital image that have a texture consistent with an unwanted occlusion; and

filling in the removed portions of the first digital image with corresponding portions of the second digital image based on the grammar primitives therefor.

7. An apparatus for processing an image comprising:

a camera for capturing a visual image in a scope-of-view window;

a video-to-digital converter coupled to the camera for converting the visual image to a digital image;

a computer coupled to the video-to-digital converter for receiving the digital image therefrom;

the computer having memory and software for processing the image, wherein the processing comprises;

(A) passing a decomposition window through the scope-of-view window with a predetermined search pattern until a portion of the image is detected,

(B) tracing the portion of the image that has been detected until a change in gradient greater than a first predetermined threshold is reached to define a first segment,

(C) recording image primitives for the first segment,

(D) continuing the trace if a segment gradient is being sensed by the decomposition window at the end point of the first segment until a change in gradient greater than the first predetermined threshold is reached to define a next segment,

(E) recording image primitives for the next segment,

(F) repeating (D) and (E) until no segment gradient is sensed in the decomposition window;

(G) masking the recorded segments from the search pattern, and

(H) continuing to pass the decomposition window through the scope-of-view window until locating another portion of the image and then repeating (B) through (G) or until the end of the search pattern is reached; and

(I) processing the image by processing image primitives.

8. A method for processing an image comprising the steps of:

(A) capturing a visual image in a scope-of-view window;

(B) converting the visual image to a digital image;

(C) decomposing the digital image into image primitives by;

(i) passing a decomposition window through the scope-of-view window with a predetermined search pattern until a portion of the image is detected,

(ii) tracing the portion of the image that has been detected until a change in gradient greater than a first predetermined threshold is reached to define a first segment,

(iii) recording image primitives for the first segment,

(iv) continuing the trace if a segment gradient is being sensed by the decomposition window at the end point of the first segment until a change in gradient greater than the first predetermined threshold is reached to define a next segment,

(v) recording image primitives for the next segment,

(vi) repeating steps (C)(iv) and (v) until no segment gradient is sensed in the decomposition window;

(vii) masking the recorded segments from the search pattern, and

(viii) continuing to pass the decomposition window through the scope-of-view window until locating another portion of the image and then repeating steps (C)(ii) through (vii) until the end of the search pattern is reached; and

(D) processing the image by processing the image primitives.

9. The method of claim 8 wherein the step of processing the image primitives comprises the step of grouping the image primitives to form higher level image primitives.

10. The method of claim 8 wherein the step of processing the image primitives comprises the steps of linking segments of image primitives by considering the location and texture of the segments.

11. The method of claim 8 wherein the step of processing the image primitives comprises the step linking segments of image primitives by considering the location and texture of segments by:

recording as image primitives at least the start point, end point, left texture and right texture for each segment of the image;

forming a first group of segments having approximately the same left texture and right texture;

linking the segments of the first group of segments having end points and start points that substantially coincide to form at least a first linked segment;

forming a second group of segments having approximately the same left texture or right texture as the interior texture of the first linked segment; and

adding the segments of the second group that have approximately the same end points or start points as the end points or start points of the first linked segment to form an isolated image.

12. The method of claim 8 wherein the step of processing the image primitives comprises the step of filtering noise from the image primitives by removing from the image primitives line or arc segments having a standard of deviation greater than a first threshold.

13. The method of claim 8 wherein the step of processing the image primitives comprises the step of filtering noise from the digitized image by:

determining the length of each segment of the image primitives;

determining the average length of the plurality of segments; and

filtering noise from the image primitives by eliminating segments having a length less than the average length by a first predetermined threshold value and having a deviation greater than a second predetermined threshold.

14. The method of claim 8 wherein the step of processing the image primitives comprises the steps of identifying a portion of the digital image by:

decomposing the digitized image into image primitives;

forming a knowledge base containing grammar primitives corresponding to known images;

comparing the image primitives to the grammar primitives to find the known image represented by grammar primitives in a knowledge base that best match the image primitives; and

identifying the portion of the digitized image as the known image having the best matching grammar primitives.

15. The method of claim 8 wherein the step of processing the image primitives comprises the step of comparing the image primitives with grammar primitives in a knowledge base that represent a known object to determine the differences between the known object and the visual image.