System and method for the detection of a circle image for pattern recognition

• US 6,021,222 A
• Filed: 01/08/1998
• Issued: 02/01/2000
• Est. Priority Date: 08/16/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Yamagata, Hideaki
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/004,663
• Time in Patent Office: 754 Days
• Field of Search: 382/199, 382/203, 382/266, 382/197
• US Class Current: 382/199
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

The present invention generally relates to pattern recognition systems, and particularly to the detection of a circle from a complex image that combines circles, straight lines, and other shapes. The system of the invention determines whether a pixel in an image being scanned is an edge pixel, and derives a gradient vector associated with the edge pixel. The direction of the gradient vector is modified toward a center of a circle incorporating the edge pixel, and then whether the edge pixel is a circle edge pixel is determined. If the edge pixel is a circle edge pixel, coordinates of a center of a circle for the edge pixel are calculated, and stored in memory. After the above steps are repeated for the other pixels in the image being scanned, the system determines whether coordinates of a calculated center of a circle for any circle edge pixel are the same for other circle edge pixels. If so, a circle is considered to be detected based on the circle edge pixels having calculated centers within a predetermined range of each other and within a predetermined frequency of occurrence.

Claims

1. A method for detecting a predetermined sized circle in an image being scanned with an image analyzing and pattern recognition system, comprising the steps of:

(a) determining whether a pixel in an image being scanned is an edge pixel;

(b) determining a gradient vector associated with said edge pixel based upon an intensity of said edge pixel and on intensities of a predetermined number of pixels near said edge pixel;

( c) modifying at least a direction of said gradient vector based upon the intensity of a pair of pixels located perpendicularly to said gradient vector and at a predetermined distance from said edge pixel, said pair of pixels having a substantially similar intensity value;

(d) determining whether said edge pixel has a lower intensity value than that of said pair of pixels, said edge pixel with the lower intensity value defining a circle edge pixel;

(e) determining coordinates of a center of the predetermined sized circle based upon said circle edge pixel and said modified gradient vector;

(f) storing said coordinates in memory;

(g) repeating steps (a)-(f) for each of a plurality of pixels in the image being scanned;

(h) determining whether said coordinates of said center of said predetermined sized circle for said circle edge pixel are the same as other sets of said coordinates for other ones of said circle edge pixel; and

(i) detecting a circle defined by said circle edge pixels having said centers within a predetermined range of each other.

2. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 1, wherein said step (b) of determining a gradient vector for said edge pixel includes the steps of:

deriving illumination intensity values for said edge pixel and a neighborhood of pixels adjacent to and surrounding said edge pixel,

arranging the illumination intensity values in a matrix representative of said edge pixel and said neighborhood of pixels, and

applying a Sobel operator to said matrix to generate said gradient vector for said edge pixel.

3. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 1, wherein said step (c) of modifying at least a direction of said gradient vector includes the steps of:

generating left and right side pixel intensity values and coordinates representative of left and right side pixels each located at a predetermined distance from said edge pixel and along an axis orthogonal to said gradient vector of said edge pixel,

determining a rotation value with which to modify the direction of the gradient vector based on said left and right side pixel intensity values and coordinates, and deriving a modified direction of the gradient vector directed toward the center of a circle incorporating said edge pixel.

4. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 3, wherein said step (d) of determining whether said edge pixel has a lower intensity than that of said pair of pixels includes the steps of:

calculating a difference in intensity values between said edge pixel and each of said left and right side pixels,

calculating a difference in intensity values between said left side pixel and said right side pixel, and

determining whether said edge pixel is a circle edge pixel based on said calculated intensity value differences.

5. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 1, wherein said step (c) of modifying at least a direction of said gradient vector includes the steps of:

generating first left and right side pixel intensity values and coordinates representative of first left and right side pixels each located at a predetermined inner distance from said edge pixel and along an axis orthogonal to said gradient vector of said edge pixel,

determining a rotation value with which to modify the direction of the gradient vector based on said first left and right side pixel intensity values and coordinates, and

deriving a modified direction of the gradient vector directed toward the center of a circle incorporating said edge pixel.

6. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 5, wherein step (d) of determining whether said edge pixel has a lower intensity than that of said pair of pixels includes the steps of:

generating second left and right side pixel intensity values and coordinates representative of second left and right side pixels each located at a predetermined outer distance from said edge pixel and along an axis orthogonal to said gradient vector of said edge pixel,

calculating a difference in intensity values between said edge pixel and each of said second left and right side pixels,

calculating a difference in intensity values between said second left side pixel and said right side pixel, and

determining whether said edge pixel is a circle edge pixel based on said calculated intensity value differences.

7. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 1, wherein said step (d) of determining whether said edge pixel has a lower intensity than that of said pair of pixels includes the steps of:

determining whether circle edge pixels have calculated centers within a predetermined range of each other, and

determining whether circle edge pixels having calculated centers within a predetermined range of each other has a frequency of occurrence that exceeds a predetermined minimum frequency of occurrence.

8. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 1, further comprising additional steps of:

(j) determining said coordinates for each of a plurality of pixels in the image being scanned;

(k) determining whether said coordinates of said calculated center of a hypothetical circle are substantially identical for said circle edge pixel; and

(l) detecting an actual circle defined by said circle edge pixels if said coordinates are within a predetermined range of deviation.

9. A method for detecting a predetermined sized circle in an image being scanned with an image analyzing the pattern recognition system, comprising the steps of:

(a) determining whether a pixel in an image being scanned is an edge pixel;

(b) determining a gradient vector associated with said edge pixel based on an intensity of said edge pixel and on intensities of a predetermined number of pixels near said edge pixel, said predetermined number of pixels having a substantially similar intensity value;

(c) determining whether said edge pixel has a lower intensity value than that of said predetermined number of pixels, said edge pixel with the lower intensity value defining a circle edge pixel;

(d) determining coordinates of a center of a predetermined sized circle based upon said circle edge pixel and said gradient vector;

(e) repeating steps (a)-(d) for each of a plurality of pixels in the image being scanned;

(f) determining whether said coordinates of said center of said predetermined sized circle for said circle edge pixel are the same as other sets of said coordinates for other ones of said circle edge pixel; and

(g) detecting a circle defined by said circle edge pixels having said centers within a predetermined range of each other.

10. A method for detecting a predetermined sized circle in an image being scanned as claimed in claim 9, further comprising the additional steps of:

(h) determining said coordinates for each of a plurality of pixels in the image being scanned;

(i) determining whether said coordinates of said center of said circle are substantially identical for said circle edge pixel; and

(j) detecting a circle defined by said circle edge pixels if said coordinates are within a predetermined range of deviation.

11. A system for detecting a predetermined sized circle in a gray image being scanned by an image detecting and analyzing device, the device detecting and analyzing individual pixels in the gray image, said system comprising:

a gradient vector calculator for calculating for calculating a gradient vector for each pixel in a gray image being scanned, said gradient vector calculator including a gradient vector buffer for storing data on said gradient vector;

an edge detector that determines whether each pixel in the gray image being scanned is an edge pixel based upon intensities of a predetermined number of pixels near said edge pixel;

a rotator in response to said edge detector to modify a direction of said gradient vector based upon the intensity of a pair of pixels located perpendicularly to said gradient vector and at a predetermined distance from said edge pixel, said pair of pixels having a substantially similar intensity value;

a circle edge detector connected to said rotator to determine whether said edge pixel has a lower intensity value than that of said pair of pixels, said edge pixel with the lower intensity value defining a circle edge pixel;

a circle center calculator in response to said circle edge detector to calculate a center of the predetermined sized circle based upon said circle edge pixel and said modified gradient vector;

an accumulator connected to said circle center calculator to store data on the calculated circle center, said accumulator including an accumulator buffer; and

a circle detector connected to said accumulator to determine whether a circle is present in the gray image being scanned based on the data on the calculated circle centers in said accumulator.

12. A system for detecting a predetermined sized circle in a gray image as claimed in claim 11, further comprising:

a balance operator accessed by said rotator and that generates position and illumination intensity data on left and right side pixels positioned relative to the image pixel being scanned, said balance operator further determining modification data for said rotator to modify the gradient vector direction of the image pixel being scanned based on the position and illumination intensity data.

13. A system for detecting a predetermined sized circle in a gray image as claimed in claim 12, wherein said balance operator is further accessed by said circle edge detector to generate illumination intensity difference data on left and right side pixels positioned relative to the image pixel being scanned and on the image pixel, said circle edge detector determining whether an image pixel is a circle edge pixel based on the illumination intensity difference data.

14. A system for detecting a predetermined sized circle in a gray image being scanned by an image detecting and analyzing device, the device detecting and analyzing individual pixels in the gray image, said system comprising:

a gradient vector calculator that calculates a gradient vector for each pixel in a gray image being scanned, said gradient vector calculator including a gradient vector buffer for storing data on calculated gradient vectors;

an edge detector that determines whether each pixel in the gray image being scanned is an edge pixel based upon intensities of a predetermined number of pixels near said edge pixel;

a circle edge detector that determines whether said edge pixel has a lower intensity value than that of said predetermined number of pixels which have a substantially similar intensity value, said edge pixel with the lower intensity value defining a circle edge pixel;

a circle center calculator activated by said circle edge detector to calculate a center of the predetermined sized circle based upon said circle edge pixel and said gradient vector;

an accumulator connected to said circle center calculator to store data on calculated circle centers, said accumulator including an accumulator buffer; and

a circle detector connected to said accumulator to determine whether a circle is present in the gray image being scanned based on the data on calculated circle centers in said accumulator.

15. A system, for detecting a predetermined sized circle in a gray image as claimed in claim 14, further comprising:

a balance operator accessed by said circle edge detector and that generates position and illumination intensity data on left and right side pixels positioned relative to the image pixel being scanned,

said balance operator being further accessed by said circle edge detector to generate illumination intensity difference data on left and right side pixels positioned relative to the image pixel being scanned and on the image pixel, said circle edge detector determining whether an image pixel is a circle edge pixel based on the illumination intensity difference data.