Method and system for detecting elliptical objects

• US 4,618,989 A
• Filed: 01/19/1984
• Issued: 10/21/1986
• Est. Priority Date: 01/21/1983
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Meidensha, Kawata Michio Director-General of Agency of Industrial Science and Technology
• Original Assignee: Kabushiki Kaisha Meidensha, Michio Kawata Director-General of Agency of Industrial Science and Technology
• Inventors: Goto, Keisuke, Tsukune, Hideo
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Todd, Jacqueline
• Application Number:
  US06/572,535
• Time in Patent Office: 1,006 Days
• Field of Search: 382/18, 382/22, 382/25, 382/41, 364/725, 364/721
• US Class Current: 382/203
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

In order to define the contour of an ellipse, it is necessary to determine five unknown parameters in the general equation representative of centered conics. When directly applying Hough transformation method to the above equation, since a five-dimensional space is required, it is practically impossible to detect an ellipse because a long processing time and a great amount of memory capacity are inevitably required. To overcome these problems, the geometric properties of an ellipse are determined separately on three parameter sub-spaces obtained on the basis of edge vector field: two-dimensional center histogram and two-dimensional (H, B) histogram, one-dimensional C histogram. A peak value on the center histogram represents a group of ellipse having the same center locations; a peak value on the (H, B) histogram represents a group of concentric ellipse having the same eccentricity and axis slope; a peak value on the C histogram defines a single ellipse. By sequentially selecting these peaks in the three sub-spaces, it is possible to define geometric properties of an ellipse under practical processing conditions. In order to define a plurality of ellipses efficiently, several novel methods have been adopted: separation of the rotation directions of edge vector field, recovery of edge vectors having no mate edge vectors; adoption of least mean square method, etc., in particular.

Claims

1. A method of detecting an elliptical object, which comprises the following steps of:

(a) transducing optical energy representative of image brightness of all locations (x, y) on an image plane including the elliptical object into electric brightness signals;

(b) partially differentiating the transduced brightness signals with respect to x and y to obtain gradient signals representative of edge image brightness gradient I=(∂

I/∂

x, ∂

I/∂

y);

(c) generating edge vector signals representative of locations (x,y) and directions (dx,dy) of an edge vector field in perpendicular to the edge image brightness gradient I in a direction such that the bright image will always be on one side of the vector signals;

(d) selecting the edge vector signals representative of all pairs of mate edge vectors having opposite directions to each other and calculating all midpoints (n₁ +n₂ =0) between the two selected mate edge vectors;

(e) selecting a center signal having a center peak value (x_o, y_o) from the calculated midpoints;

(f) selecting vector signals representative of the locations (x, y) and directions (dx, dy) of the edge vectors supporting the centered conics having the selected center peak value (x_o, y_o) from the edge vector field signals;

(g) transforming the selected values (x, y, dx, dy) of the edge vector signals to a first two-dimensional (p=(YdX+XdY)/YdY, Q=XdX/YdY) space to form a first straight line and calculating all intersections of second straight lines corresponding to each transformed point on the first straight line in a second two-dimensional (H, B) space in accordance with a Hough transformation method;

(h) selecting a signal having a peak value located within a specific range (H² -B<

0) on the (H, B) space for detecting an ellipse;

(i) calculating coefficients G=-X_o -Hy_o and F=-Hx_o -By_o of an ellipse group having the same center on the basis of the selected coefficients H, B and the selected center locations (x_o, y_o);

(j) calculating coefficients C on the basis of the calculated coefficients H, B, G, F and the edge vector locations (x, y); and

(k) selecting a peak value from the calculated coefficients C to identify a detected ellipse.

2. A method of detecting an elliptical object as set forth in claim 1, which further comprises the following steps of:

(a) selecting all edge vector signals contributed to the selected (H, B) peak value;

(b) selecting edge vector signals having no mate edge vectors but lying within a predetermined small angle range in the direction of the mate edge vectors of a concentric ellipse group determined by the selected (H, B) peak value;

(c) calculating coefficients H, B, G, F again on the basis of the detected edge vector locations (x, y) and calculated coefficients H, B based on least mean square method;

(d) selecting all the edge vector signals contributed to the selected C peak value; and

(e) calculating a coefficient C again on the basis of the detected edge vector locations (x, y) and coefficients H, B, G, F already calculated in step (c) above based on least mean square method.

3. A method of detecting an elliptical object as set forth in claim 1, wherein in step (h) of selecting a peak value signal on the (H, B) space, the range from which an (H, B) peak value is selected is limited to a narrower practical range such that the ratio R of minor axis length b to major axis length a lies between 0.2 and 1.

4. A method of detecting an elliptical object as set forth in claim 1, wherein the edge vector signals below a predetermined threshold are eliminated.

5. A method of detecting an elliptical object as set forth in claim 1, wherein the center signals below a predetermined threshold are eliminated.

6. A method as recited in claim 1 comprising the further step of producing an output signal indicating detection of the ellipse.

7. A method as recited in claim 1 wherein said optical energy representation is produced in a two dimensional image plane by an image pick up tube.

8. A method of detecting an elliptical object as set forth in claim 1, wherein in step (h) of selecting a peak value signal on the (H, B) space, the range from which an (H, B) peak value is selected is limited to a narrower practical range such that the ratio R of minor axis length b to major axis length a lies between 0.2 and 1, thereby detecting an ellipse corresponding to a shape of mechanical contour when projected on an image plane.

10. A system for detecting an elliptical object as set forth in claim 6, which further comprises:

(a) means (18) for recovering edge vectors having no mate edge vectors but lying within a predetermined small angle range in the direction of the mate edge vectors of a concentric ellipse group determined by the (H, B) peak value detected on the (H, B) histogram and extracted by said edge vector extracting means;

(b) means (19) for calculating coefficients (H, B, G, F) in response to the edge vector filed (x, y, dx, dy) from said edge vector generating means, and the center (x_o, y_o) and the coefficients (H, B) detected by said peak value detecting means on least mean square method;

(c) means (23) for extracting all edge vectors which support the detected C peak value on the C histogram from the edge vector field;

(d) means (24) for calculating coefficient C in response to the edge vector field (x, y) from said edge vector generating means and the coefficients (H, B, G, F) already estimated by said H, B, G, F calculating means on least means square method.

16. A method of detecting a plurality of elliptical objects as set forth in claim 1, wherein the center signals below a predetermined threshold are eliminated.

9. A system for detecting an elliptical object, which comprises:

(a) means (10) for transducing optical energy representative of the image brightness of the elliptical object into electric image signals corresponding thereto on an image plane (x, y);

(b) means (11) for generating an edge vector field n having locations (x, y) and directions (dx, dy) and perpendicular to the obtained edge image brightness gradient I in an direction that the bright image will always be on a one side, in response to the image signals from said transducing means, by partially differentiating the detected image signals with respect to x and y to obtain an edge image brightness gradient I=(∂

I/∂

x, ∂

I/∂

y) and by extracting the differentiated image signals beyond a predetermined threshold;

(c) means (12) for outputting common signals to sequentially control the processing procedure of the entire system itself;

(d) means (13) for constructing a two-dimensional center histogram by extracting all pairs of mate edge vectors having opposite directions to each other from the generated edge vector field and by calculating all midpoints (n₁ +n₂ =0) between the two extracted mate edge vectors;

(e) means (14) for detecting a peak value (x_o, y_o) on the center histogram constructed by said center histogram constructing means;

(f) means (15) for extracting all the edge vectors supporting the centered conics having the detected center peak value (x_o, y_o) from the edge vector field;

(g) means (17) for contructing an (H, B) histograms by mapping the values (x, y, dx, dy) of the edge vectors to a first two-dimensional (P=(YdX+XdY)/YdY, Q=XdX/dY) space to form a first straight line and by calculating all intersections of second straight lines corresponding to each mapped point on the first straight lines in a second two-dimensional (H, B) space in accordance with Hough transformation method;

(h) an (H, B) peak value on the (H, B) histogram being deteced by the peak value detecting means, independently, within a predetermined range (H² -B<

0);

(i) means (25) for calculating coefficients G, F of the edge vector group, in response to the center location (x_o, y_o) and the coefficients detected by said peak value detecting means;

(j) means (21) for constructing a C histogram of the selected concentric ellipse group in a one-dimensional space in response to the edge vectors (x, y) from said edge vector field generating means, the center (x_o, y_o) and coefficients H, B detected by said peak value detecting means and the coefficients G, F calculated by said coefficient calculating means; and

(k) means (22) for detecting a peak value on the histogram of the one-dimensional space constructed by said C histogram constructing means.

11. A method of detecting a plurality of elliptical objects which comprises the following steps of:

(a) transducing optical energy representative of image brightness of the elliptical objects into electric brightness signals corresponding thereto at all locations (x, y) on an image plane;

(b) partially differentiating the transduced brightness signals with respect to x and y to obtain gradient signals representative of edge image brightness gradient I=(∂

I/∂

x, ∂

I/y);

(c) generating edge vector signals representative of locations (x, y) and directions (dx, dy) of an edge vector field n perpendicular to the edge image brightness gradient I in the direction that the bright image will always be on the one-hand side;

(d) selecting the edge vector signals representative of all pairs of mate edge vectors having opposite directions to each other and calculating all midpoints (n₁ +n₂ =0) between the two selected mate edge vectors;

(e) selecting a center signal having a center peak value (x_o, y_o) from the calculated midpoints;

(f) selecting vector signals representative of the locations (x, y) and directions (dx, dy) of the edge vectors supporting the centered conics having the selected center peak value (x_o, y_o) from the edge vector field signals;

(g) separating all the selected edge vector signals into a clockwise-rotating vector field and a counterclockwise-rotating vector field;

(h) transforming the selected values (x, y, dx, dy) of the edge vectors signals to a first two-dimensional (P=YdX+YdY)/YdY, Q=XdX/YdY) space to form a first straight line and calculating all intersections of second straight line corresponding to each transformed point on the first straight line in a second two-dimensional (H, B) space in accordance with Hough transformation method;

(i) selecting a peak value signal located within a specific range (H² -B<

0) on the (H, B) space;

(j) calculating coefficients G=-x_o -Hy_o and F=-Hx_o -By_o of an ellipse group having the same center on the basis of the selected coefficients H, B and the selected center locations (x_o, y_o);

(k) similarly executing the above same procedure from (h) to (j) for counterclockwise-rotating vector field;

(l) determining the concentricity of the two calculated clockwise and counterclockwise concentric ellipse groups on the basis of the differences in center locations (Δ

x=x₂ -x₁, Δ

y=y₂ -y₁) and orientation (Δ

θ

=θ

₂ -θ

₁);

(m) if the two concentric ellipse groups are determined to be a single group, calculating the coefficient C on the basis of the calculated merged coefficients H, B, G, F and the edge vector locations (x, y);

(n) selecting a peak value from the calculated coefficients C to identify a detected ellipse;

(o) if the above two concentric ellipse groups are determined to be two different groups, constructing two one-dimensional C space groups separately for each ellipse group by calculating each coefficient C on the basis of the estimated coefficients H, B, G, F and edge vector locations (x, y);

(p) selecting each peak value from the calculated coefficients C for each ellipse group separately;

(q) neglecting all the edge vector signals supporting the detected ellipse from the detected edge vectors; and

(r) repeating the above steps to detect a plurality of ellipses one by one;

12. A method of detecting a plurality of elliptical objects as set forth in claim 11, which further comprises the following steps of:

(a) selecting all edge vector signals contributed to the selected (H, B) peak value;

(b) selecting edge vector signals having no mate edge vectors but lying within a predetermined small angle range in the direction of the mate edge vectors of a concentric ellipse group determined by the selected (H, b) peak value;

(c) calculating coefficients H, B, G, F again on the basis of the detected edge vector locations (x, y) detected directions (dx, dy), selected center (s_o, y_o) and calculated coefficients H, B on least means square method;

(d) selecting all the edge vector signals contributed to the selected C peak value; and

(e) calculating a coefficient C again on the basis of the detected edge vector locations (x, y) and coefficients H, B, G, F already estimated in step (c) above based on least mean square method.

13. A method of detecting a plurality of elliptical objects as set forth in claim 11, wherein in the step (e) of selecting a center peak value signal (x_o, y_o) on the center space, a peak value (x_o, y_o) located farthest from a gravity center G of a plurality of center peaks is first selected and thereafter a peak value (x_o, y_o) having a maximum sum of a distance to the first selected peak value is selected.

14. A method of detecting a plurality of elliptical objects as set forth in claim 11, wherein in the step (i) of selecting a peak value signal on the (H, B) space, the range from which an (H, B) peak value is selected is limited to a narrower practical range such that the ratio r of minor axis b to major axis length a lies from 0.2 to 1.

15. A method of detecting a plurality of elliptical objects as set forth in claim 11, wherein the edge vector signals below a predetermined threshold are eliminated.

17. A system for detecting a plurality of elliptical objects, which comprises:

(a) means (10) for transducing optical energy representative of the image brightness of elliptical objects into electric image signals corresponding thereto on an image plane (x, y);

(b) means (11) for generating an edge vector field n having locations (x, y) and directions (dx, dy) and perpendicular to an obtained edge image brightness gradient I in the direction that the bright image will always be on a one side, in response to the image signals from said transducing means, by partially differentiating the detected image signals with respect to x and y to obtain an edge image brightness gradient I=(∂

I/∂

x, ∂

I/∂

y) and by extracting the differentiated image signals beyond a predetermined threshold;

(c) means (12) for outputting common signals to sequentially control the processing procedure of the entire system itself.

(d) means (13) for constructing a two-dimensional center histogram by extracting all pairs of mate edge vectors having opposite directions to each other from the generated edge vector field and by calculating all midpoints (n₁ +n₂ =0) between the two extracted mate edge vectors;

(e) means (14) for detecting a peak value (x_o, y_o) on the center histogram constructed by said center histogram constructing means;

(f) means (15) for extracting all the edge vectors supporting the centered conics having the detected center peak value (x_o, y_o) from the edge vector field;

(g) means (16) for separating all the edge vectors extracted by said edge vector extracting means into clockwise-rotating vectors and counterclockwise-rotating vectors;

(h) means (17) for constructing two different (H, B) histograms by mapping the values (x, y, dx, dy) of the clockwise-rotating and counterclockwise-rotating edge vectors separated by said edge vector separating means onto two different first two-dimensional (P=(YdX+XdY)/YdY, Q=XdX/dY) spaces independently to form first straight lines and by calculating all intersections of second straight lines corresponding to each mapped point on the first straight lines in two different second two-dimensional (H, B) spaces in accordance with Hough transformation method;

(i) an (H, B) peak value on each (H, B) histogram being detected by said peak value detecting means, independently, within a predetermined range (H² -B<

0);

(j) means (25) for calculating coefficients G, F of the clockwise- and counterclockwise-rotating edge vector groups separately, in response to the center location (x_o, y_o) and the coefficients detected by said peak value detecting means;

(k) means (20) for evaluating the concentricity of two estimated clockwise- and counterclockwise-rotating concentric ellipse group having the same coefficients H, B, G, F in accordance with an empirical expression by which the differences in center locations and axis orientations are checked, the edge vector fields separated by said edge vector field separating means being determined to be two different concentric ellipse groups if the differences are beyond a predetermined value and to be an equivalent concentric ellipse group if the difference are below the predetermined value;

(l) means (21) for constructing a C histogram of each concentric ellipse group in a one-dimensional space in response to the edge vectors (x, y) from said edge vector field generating means, the center (x_o, y_o) and coefficients H, B detected by said peak value detecting means and the coefficients G, F calculated by said coefficient calculating means; and

(m) means (22) for detecting a peak value on each C histogram in the one-dimensional space constructed by said C histogram constructing means.

18. A system for detecting a plurality of elliptical objects as set forth in claim 17, which further comprises:

(a) means (10) for recovering edge vectors having no mate edge vectors but lying within a predetermined small angle range in the direction of the mate edge vectors of a concentric ellipse group determined by the (H, B) peak value detected on the (H, B) histogram and extracted by said edge vector extracting means;

(b) means (19) for calculating coefficients (H, B, G, F) in response to the edge vector field (x, y, dx, dy) from said edge vector generating means, and the center (x_o, y_o) and the coefficients (H, B) detected by said peak value detecting means on least mean square method;

(c) means (23) for extracting all edge vectors which support the detected C peak value on the C histogram from the edge vector field;

(d) means (24) for calculating coefficient C in response to the edge vector field (x, y) from said edge vector generating means and the coefficients (H, B, G, F) already estimated by said H, B, G, F calculating means on least means square method.