Method for automatic recognition of two-dimensional shapes

• US 4,573,197 A
• Filed: 12/13/1983
• Issued: 02/25/1986
• Est. Priority Date: 12/13/1983
• Status: Expired due to Term

• Current Assignee: Environmental Research Institute of Michigan
• Original Assignee: Environmental Research Institute of Michigan
• Inventors: Crimmins, Thomas R.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Todd, Jacqueline
• Application Number:
  US06/561,156
• Time in Patent Office: 805 Days
• Field of Search: 382/22, 382/31, 382/43, 364/726
• US Class Current: 382/197
• CPC Class Codes: G06V 10/478 Contour-based spectral representations or scale-space representations, e.g. by Fourier analysis, wavelet analysis or curvature scale-space [CSS]

Abstract

A method of automatically recognizing objects in a digital image. The pixel coordinates of the boundary of the objects are identified and stored as data. A series of Fourier coefficients describing the boundary of the object are calculated and used to generate a set of descriptors. The descriptors are stored and compared with similarly generated descriptors of other objects to determine correspondence therebetween.

Claims

1. A method of automatically recognizing objects comprising:

a. scanning said objects with a scanning means such as a video camera to produce signals representing each of said objects;

b. converting the signals into a digital image where the pixel coordinates of the boundary of each object have been identified and stored as data;

c. calculating from said data a series of Fourier coefficients c₁ associated with the boundary of the object;

d. testing a given number N of the Fourier coefficients, except for the zero order Fourier coefficient, in a predetermined order for absolute values which exceed a predetermined value and generating a series of integers s_n with values corresponding to the subscript of each coefficient tested having an absolute value exceeding the predetermined value, so that;

s₁ =the subscript value of the first Fourier coefficient tested whose absolute value exceeds the predetermined value;

s₂ =the subscript value of the next Fourier coefficient tested whose absolute value exceeds the predetermined value;

etc

e. calculating a first descriptor S as the number of Fourier coefficients c_s.sbsb.n, whose absolute values exceed the predetermined value, identified in step b;

f. calculating the greatest common divisor r of the integers;

space="preserve" listing-type="equation">s.sub.n -s.sub.1, n=2, . . . , S Eq. 9

g. calculating an integer J which is the smallest of all integers R which satisfy the condition that r is the greatest common divisor of the integers;

s_n -s₁, n=2, . . . , R Eq. 10

h. calculating second descriptors a_n as the absolute values of the Fourier coefficients c₁ whose absolute value exceeds the predetermined value, according to the definition;

space="preserve" listing-type="equation">a.sub.n Δ

|c.sub.s.sbsb.n |, n=1, . . . , J Eq. 11

i. calculating a series of third descriptors b_n,j according to the following definition;

space="preserve" listing-type="equation">b.sub.n,jΔ

c.sub.s.sbsb.1.sup.(s.sbsp.n.sup.s.sbsp.j.sup.)/r c.sub.s.sbsb.j.sup.(s.sbsp.1.sup.-s.sbsp.n.sup.)/r c.sub.s.sbsb.n.sup.(s.sbsp.j.sup.-s.sbsp.1.sup.)/r, n=J+1, . . . , S;

j=2, . . . , J

j. storing at least the first, second and third descriptors in a digital memory; and

k. comparing the stored descriptors with descriptors of other objects calculated according to steps c-i to thereby automatically recognize objects of the same shape.

2. The method of claim 1 wherein an orientation descriptor α

is also calculated according to the following formulae;

p_n, n=2, . . . , S, is any sequence of integers for which ##EQU24## θ

Δ

phase of ##EQU25## storing the orientation descriptor; and

comparing the stored orientation descriptor with similarly calculated orientation descriptors of other objects.

3. The method of claim 1 which further comprises:

calculating a size descriptor associated with the size of the object in the digital image;

storing the size descriptor; and

comparing the stored size descriptor with similarly calculated size descriptors of other objects.

4. The method of claim 1 which further comprises:

calculating a location descriptor associated with the location of the object in the digital image;

storing the location descriptor; and

comparing the stored location descriptor with similarly calculated location descriptors of other objects.

5. In a method of automatically recognizing objects in a digital image, the method comprising:

a. Scanning objects with a scanning means such as a camera to produce signals representing the objects;

b. converting the signals into a digital image;

c. detecting the boundaries of each object in the digital image to produce data representing the boundaries;

d. converting said data to data representing the pixel coordinates of the polygons defining the boundary of each of the objects, with x and y coordinates of the vertices of the boundaries being defined as

space="preserve" listing-type="equation">v.sub.n =(x.sub.n, y.sub.n), n=1, . . . , N Eq. 1

where N is the number of vertices;

e. calculating parameters according to the following formulae;

space="preserve" listing-type="equation">x.sub.0 Δ

x.sub.N, y.sub.0 Δ

y.sub.N Eq. 2

space="preserve" listing-type="equation">z.sub.n Δ

x.sub.n +iy.sub.n, n=0, . . . , N(i=√

-1) Eq. 3 ##EQU26## f. calculating a series of Fourier coefficients where the zero order coefficient is defined as;

##EQU27## and wherein other Fourier coefficients are calculated according to the formula;

for m≠

0, |m|≦

M, ##EQU28## g. calculating a series of first descriptors s_n by testing a given number of the Fourier coefficients, excepting the zero order Fourier coefficient, in a predetermined order for absolute values which exceed a predetermined value, and assigning the first descriptors with integer values corresponding to the subscript of each Fourier coefficient tested having an absolute value exceeding the predetermined value, so that;

s₁ =the subscript value of the first Fourier coefficient tested whose absolute value exceeds the predetermined value;

s₂ =the subscript value of the next Fourier coefficient tested whose absolute value exceeds the predetermined value;

etc.

h. calculating a second descriptor S as the number of the first descriptors identified in step c;

i. calculating the greatest common divisor r of the integers;

space="preserve" listing-type="equation">s.sub.n -s.sub.1, n=2, . . . , S Eq. 9

j. calculating an integer J which is the smallest of all integers R which satisfy the condition that r is the greatest common divisor of the integers;

space="preserve" listing-type="equation">s.sub.n -s.sub.1, n=2, . . . , R Eq. 10

k. calculating a series of third descriptors a_n according to the formula;

space="preserve" listing-type="equation">a.sub.n Δ

|c.sub.s.sbsb.n |, n=1, . . . , J Eq. 11

l. calculating a series of fourth descriptors b_n,j according to the following definition;

space="preserve" listing-type="equation">b.sub.n,jΔ

c.sub.s.sbsb.1.sup.(s.sbsp.n.sup.-s.sbsp.j.sup.)/r c.sub.s.sbsb.j.sup.(s.sbsp.1.sup.-s.sbsp.n.sup.)/r c.sub.s.sbsb.n.sup.(s.sbsp.j.sup.-s.sbsp.1.sup.)/r, n=j+1, . . . , S;

j=2, . . . J Eq. 12

m. calculating an orientation descriptor * according to the following formulae;

p_n, n=2, . . . , S, is any sequence of integers for which ##EQU29## θ

Δ

phase of ##EQU30## φ

Δ

phase of c_s.sbsb.1 (0≦

φ

<

2π

) ##EQU31## n. storing the first, second, third, fourth and orientation descriptors in a digital memory; and

o. comparing the stored descriptors with descriptors of other objects calculated according to steps e-l to thereby detect similarities and differences between the objects.

6. The method of claim 5 which further comprises the steps of:

calculating size and location descriptors of the object;

storing the size and location descriptors in the digital memory; and

comparing the size and location descriptors with similarly calculated size and location descriptors of other objects.