Automatic detection of elliptical shapes

• US 5,189,711 A
• Filed: 09/09/1991
• Issued: 02/23/1993
• Est. Priority Date: 11/24/1989
• Status: Expired due to Fees

• Current Assignee: Azriel Rosenfeld, Isaac Weiss
• Original Assignee: Azriel Rosenfeld, Isaac Weiss
• Inventors: Weiss, Isaac, Rosenfeld, Azriel
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Stellrecht, Barry
• Application Number:
  US07/800,472
• Time in Patent Office: 533 Days
• Field of Search: 382/8, 382/25, 382/46
• 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

A method is described for automatic detection of a large class of industrial parts, whch is faster and more reliable than current methods. Many industrial parts have visible outlines which are either circular or elliptical or contain segments of these. Circles are seen as ellipses unless viewed head-on. Thus the ability to detect ellipses in an image of an industrial part, quickly and reliably, can be of great help in identification of this part by a robotic assembly process. In our method one first scans the image electronically by a video camera. When a scan line goes through an image of some object one can detect the edges of this image by detecting changes in the light intensity at these edges. For an object of the shape of a conic section (e.g. an ellipse), generally two edges will appear on each scan line and the midpoints between them will all lie on one straight line. This straight line can be detected with Hough'"'"'s method.

Claims

1. A method of detection of a plurality of objects, or parts of objects, having circular, elliptical, parabolic or hyperbolic shapes, within an image containing many different objects, comprising of the following steps:

a) transducing an optical image into an electrical signal representing the grey level (brightness) of the image at each point (x, y) using a camera;

b) finding local changes in brightness along x which are large enough to be regarded as edges of an object;

c) finding the midpoint between any two edges lying on the same scan line, i.e. a line that is parallel to the image'"'"'s x axis;

d) feeding all the midpoints from above into a straight line detector;

keeping a record of the parameters of each skew-symmetry line thus detected, as well as the skew symmetric set of edges that gave rise to it;

e) rotating the camera around its optical axis using a motor and repeating previous steps (a) through (d), to find from the edges in memory sets of edges that have a second line of skew symmetry;

keeping in memory each such set of edges and its two skew symmetry lines;

f) rotating the camera again, repeating previous steps (a) through (d) and finding all sets of edges having three skew symmetry lines;

thus finding sets consisting possibly of ellipses with the same center, orientation and eccentricity;

g) calculating from the parameters of the skew symmetry lines of the sets found in (f), and from the scan line rotation angles, the intersection point of the lines (the center), the orientation and the eccentricity of the possible ellipses;

h) eliminating the orientation and eccentricity found in (g) by means of of a geometrical transformation for each elliptical set found in (f), transforming the ellipses into circles;

i) histograming the distances of the edges from the center for each circular set found in (h), and separating the set of edges into subsets of edges having the same distance from the center;