Methods and apparatus for centroid based object segmentation in object recognition-type image processing system

• US 5,604,822 A
• Filed: 11/12/1993
• Issued: 02/18/1997
• Est. Priority Date: 11/12/1993
• Status: Expired due to Term

• Current Assignee: Laser Signals LLC (Intellectual Ventures LLC)
• Original Assignee: Martin Marietta Corporation
• Inventors: Lofgren, John D., Pearson, William A., Benton, Richard W.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/150,829
• Time in Patent Office: 1,194 Days
• Field of Search: 382/22, 382/9, 382/25, 382/16, 382/103, 382/197, 382/199, 342/90
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10048 Infrared image
• CPC Class Codes: G06T 2207/30212 Military
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/66 of image moments or centre of gravity

Abstract

A digital signal processing system which uses an input image including a plurality of pixels to establish boundaries of objects in the input image. Each of the pixels has a gradient value and the object includes a centroid. Using a segmentation process, the digital signal processing system decides on a perimeter surrounding the object in the input image and then repeatedly searches for a pixel having the highest gradient value and marks that pixel having the highest gradient value as an edge pixel of the object.

Claims

1. A method of establishing the boundaries of an object in an input image including a plurality of image pixels having gradient values predetermined gray scale, wherein the object includes a centroid, the method, performed by a signal processing system, comprising the steps of:

deciding on a perimeter surrounding the object in the input image;

repeatedly searching, from an image pixel corresponding to the centroid of the object to image pixels of the perimeter, for an image pixel having a highest gradient value of the gradient values of the searched pixels;

marking, as an edge pixel, the image pixel having the highest gradient value for each of the repeated searches when said highest gradient value exceeds a predetermined threshold; and

locating and connecting gaps, if any are located between marked edge pixels.

2. A method of determining whether a pixel of an input image corresponds to part of an object, wherein the input image includes a plurality of image pixels having gradient values of a predetermined gray scale, wherein the object includes a centroid, the method, performed by a signal processing system, comprising the steps of;

deciding on a perimeter surrounding the object in the input image;

deciding on a minimum object area of the input image around a pixel of the input image corresponding to the centroid;

repeatedly searching, along a sweep hand extending from the pixel corresponding to the centroid of the object to the perimeter, for an image pixel having a highest gradient value of the gradient values of the searched pixels;

marking, as an edge pixel, the image pixel having the highest gradient value for each of the repeated searches when said highest gradient value exceeds a predetermined threshold and provided the image pixel is outside the minimum object area; and

locating and connecting gaps, if any are located between marked edge pixels.

3. A method of determining whether a pixel of an input image corresponds to part of an object, wherein the input image includes a plurality of pixels, each of the pixels having a gradient value of a predetermined gray scale, and wherein the object includes a centroid, the method, performed by a signal processing system, comprising the steps of:

receiving the input image and a location of a pixel corresponding to the centroid of the object within the input image;

sweeping an imaginary clock hand fixed an the location of the pixel corresponding to the centroid of the object around the input image to locate a pixel underneath each position of the imaginary clock hand that has a highest gradient value of the gradient values of the pixels underneath each position of the imaginary clock hand;

marking, as an edge pixel, the pixel having the highest gradient value for each position of the imaginary clock hand when said highest gradient value exceeds a predetermined threshold; and

locating and connecting gaps, if any are located between marked edge pixels.

4. The method of claim 3 further including the step of:

denoting a minimum object box, wherein the sweeping step locates the edge pixel outside the minimum object box.

5. An image processing system for establishing the boundaries of an object in an input image including a plurality of image pixels having gradient values of a predetermined gray scale, wherein the object includes a centroid, the system comprising:

means for deciding on a perimeter surrounding the object in the input image;

means for repeatedly searching, from an image pixel in the input image corresponding to the centroid of the object to image pixels of the perimeter, for an image pixel having a highest gradient value of the gradient values of the searched pixels;

means for marking, as an edge pixel, the image pixel, having the highest gradient value for each of the repeated searches when said highest gradient value exceeds a predetermined threshold; and

means for locating and for connecting gaps, if any are located between marked edge pixels.

6. An image processing system for determining whether a pixel of an input image corresponds to part of an object, wherein the input image includes a plurality of image pixels, each having a gradient value of a predetermined gray scale, and wherein the object includes a centroid, the system comprising:

means for deciding on a perimeter surrounding the object in the input image;

means for deciding a minimum object area of the input image around a pixel of the image corresponding to the centroid;

means for repeatedly searching, along a sweep hand extending from the pixel corresponding to the centroid of the object to the perimeter, for an image pixel having a highest gradient value of the gradient values of the search pixels;

means for marking as edge pixel, the image pixel having the highest gradient value for each of the repeated searches when said highest gradient value exceeds a predetermined threshold and provided that image pixel is outside the minimum object area; and

means for locating and for connecting gaps, if any are located between marked edge pixels.

7. An image processing system for determining whether a pixel of an input image corresponds to part of an object, wherein the input image includes a plurality of pixels, each of the pixels having a gradient value of a predetermined gray scale, and wherein the object includes a centroid, the system comprising:

receiving means for receiving the input image and a location of a pixel corresponding to the centroid of the object within the input image;

sweeping means for sweeping an imaginary clock hand fixed at the location of the pixel corresponding to the centroid of the object around the input image to locate a pixel underneath each position of the imaginary clock hand that has a highest gradient value of the gradient values of the pixels underneath each position of the imaginary clock hand;

means for marking, as an edge pixel, the pixel having the highest gradient value for each position of the imaginary clock hand when said highest gradient value exceeds a predetermined threshold; and

means for locating and for connecting gaps, if any are located between marked edge pixels.

8. The system of claim 7 further including:

means for denoting a minimum object box, wherein the sweeping means locates the edge pixel outside the minimum object box.

9. A method of establishing a perimeter of an object in an input image including a plurality of pixels having gradient values of a predetermined gray scale, wherein a subset of the pixels establishes a boundary of the input image and each of the pixels has a gradient value, and wherein one of the pixels identifies a centroid of the object, the method, performed by a signal processing system comprising the steps of:

receiving data identifying a minimum object pixel subset of the pixels within both the pixels of the boundary input image and the pixels of the image that correspond to the object;

repeatedly scanning the pixels outside the pixels of the minimum object pixel subset but within the pixels of the boundary of the input image to identify high-gradient pixels having a gradient value that exceed a predetermined threshold level;

marking the identified high-gradient pixels as edge pixels; and

locating and connecting gaps, if any are located between marked sage pixels.

10. An image processing system for establishing a perimeter of an object in an input image including a plurality of pixels having gradient values of a predetermined gray scale, wherein a subset of the pixels establishes a boundary of the input image and each of the pixels has a gradient value, and wherein one of the pixels identifies a centroid of the object the system comprising:

means for receiving data identifying a minimum object pixel subset of the pixels within both the pixels of the boundary input image and the pixels of the image that correspond to the object;

means for repeatedly scanning the pixels outside the pixels of the minimum object pixel subset but within the pixels of the boundary of the input image to identify high-gradient pixels having a gradient value that exceed a predetermined threshold level;

means for marking the identified high-gradient pixels as edge pixels; and

means for locating and for connecting gaps, if any are located between marked edge pixels.

11. A method of determining whether a pixel of an input image corresponds to part of an object, wherein the input image includes a plurality of pixels, each of the pixels having a gradient value, and wherein the object includes a centroid, the method, performed by a signal processing system, comprising the steps of:

receiving the input image and a location of the centroid within the input image;

fixing an imaginary clock hand fixed at the location of the centroid;

sweeping, beginning at a first position, the imaginary clock hand clockwise or counterclockwise around the input image to locate a pixel underneath each position of the imaginary clock hand that has a highest gradient value;

determining whether the highest gradient value exceeds a predetermined threshold gradient value; and

marking the pixel having the highest gradient value that exceeds the predetermined threshold gradient value as an edge pixel;

repeatedly performing the sweeping step, the determining step, and the marking step on successive positions of the imaginary clock hand until reaching the first position; and

locating and connecting gaps, if any are located between marked edge pixels.