US 4,618,989 AGranted

Method and system for detecting elliptical objects

AssigneesMichio Kawata, Director-General of Agency of Industrial Science and Technology, Meidensha Corporation

InventorsHideo Tsukune, Keisuke Goto

Life of this patent

Estimating the term…

Loading patent…

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.

Claims18

Dependent claims

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=(.differential.I/.differential.x, .differential.I/.differential.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.sub.1 +n.sub.2 =0) between the two selected mate edge vectors;
(e) selecting a center signal having a center peak value (x.sub.o, y.sub.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.sub.o, y.sub.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.sup.2 -B<0) on the (H, B) space for detecting an ellipse;
(i) calculating coefficients G=-X.sub.o -Hy.sub.o and F=-Hx.sub.o -By.sub.o of an ellipse group having the same center on the basis of the selected coefficients H, B and the selected center locations (x.sub.o, y.sub.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.

9 more elements

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=(.differential.I/.differential.x, .differential.I/.differential.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.sub.1 +n.sub.2 =0) between the two extracted mate edge vectors;
(e) means (14) for detecting a peak value (x.sub.o, y.sub.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.sub.o, y.sub.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.sup.2 -B<0);
(i) means (25) for calculating coefficients G, F of the edge vector group, in response to the center location (x.sub.o, y.sub.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.sub.o, y.sub.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.

9 more elements

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=(.differential.I/.differential.x, .differential.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.sub.1 +n.sub.2 =0) between the two selected mate edge vectors;
(e) selecting a center signal having a center peak value (x.sub.o, y.sub.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.sub.o, y.sub.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.sup.2 -B<0) on the (H, B) space;
(j) calculating coefficients G=-x.sub.o -Hy.sub.o and F=-Hx.sub.o -By.sub.o of an ellipse group having the same center on the basis of the selected coefficients H, B and the selected center locations (x.sub.o, y.sub.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 (.DELTA.x=x.sub.2 -x.sub.1, .DELTA.y=y.sub.2 -y.sub.1) and orientation (.DELTA..theta.=.theta..sub.2 -.theta..sub.1);
(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;

16 more elements

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=(.differential.I/.differential.x, .differential.I/.differential.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.sub.1 +n.sub.2 =0) between the two extracted mate edge vectors;
(e) means (14) for detecting a peak value (x.sub.o, y.sub.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.sub.o, y.sub.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.sup.2 -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.sub.o, y.sub.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.sub.o, y.sub.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.

11 more elements

Dependencies are inferred from the claim text.