Method and device for automatic matching of planar point patterns

• US 5,991,430 A
• Filed: 11/26/1996
• Issued: 11/23/1999
• Est. Priority Date: 11/26/1996
• Status: Expired due to Term

• Current Assignee: Wen-Hsing Hsu
• Original Assignee: Wen-Hsing Hsu
• Inventors: Hsu, Wen-Hsing, Chang, Shih-Hsu
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/756,526
• Time in Patent Office: 1,092 Days
• Field of Search: 382/226, 382/228, 382/227, 382/298, 382/296, 382/124, 382/125, 382/201, 382/205, 382/209, 340/146
• US Class Current: 382/124
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A method for automatic matching of planar point patterns in a reference pattern with a test pattern includes course mating, calculation of a mated possibility for one point in each pattern, preliminary selection of mated pairs based on these possibilities, and calculation of a similarity value based upon the number of mated pairs, the mated rate of the reference and test patterns, and the average mating possibility and average distance between mated points.

Claims

1. A method for automatic matching of planar point patterns to decide whether two patterns (P and q) consisting of points distributed in respective coordinate plans are similar;

wherein P={p1,p2, . . . pm} is a reference pattern including m points and Q={q1,q2, . . . qn} is a test pattern including n points and wherein every point of the pattern is expressed by (x,y,D) wherein (x, y) is the coordinate of the point and D is the feature direction of the point;

said method comprising;

a mating process to locate an only point pi in the P pattern for every point qj in the Q pattern thereby pi and qj are overlapped or within a very short distance from each other, if they were in a same coordinate plan;

a similarity calculation process to calculate the similarity of the two patterns according to the result of said mating process; and

a determination process to determine whether the two patterns are similar by comparing the index of similarity with a threshold;

wherein said mating process comprises;

calculating the mated possiblity of every point in the Q pattern (qj, j=1, 2, . . . , m) and every point in the P pattern (pi, i=1, 2, . . . , n), comprising;

designating a point in the Q pattern (qj) to be mated with a point in the P pattern (pi);

calculating the mated possibility of every point, other than said qj point, in the Q pattern (qk, k=1, 2, . . . , m. k≠

j) to be mated with every point, other than said pi point, in the P pattern (ph, h=1, 2, . . . , m, h≠

i), under a transformation angle;

accumulating the mated possibilities of qk points and ph points under the premise that pi and qj are mated and making the result the mated possibility of qj and pi; and

selecting the mated parts according to the values of mated possibility of qj points and pi points;

wherein the mated possibility of qj and pi while pattern Q is rotated at angle θ

(S[i][j][θ

]) is calculated according to the following equation;

##EQU10## wherein;

##EQU11## wherein;

C_ijkh (θ

) represents the mated possibility of qk (k=1, 2, . . . m, k≠

j) and ph (h=1, 2, . . . , h≠

i), θ

=θ

qjqk-θ

piph, Ds represents the difference between the difference between the feature direction of pi and the direction of piph and the difference between the feature direction of qj and the direction of qiqk, De represents the difference between the difference between the feature direction of ph and the direction of piph and the difference between the feature direction of qk and the direction of qiqk, d1 represents the difference between the lengths of piph and qiqk, and w, w1 and w2 are constants; and

wherein the similarity value (Score) of the two patterns is calculated according to the following equation;

Score=C*K2*S₁ *S₂ *S₃ *md, wherein

C is a constant;

K is the number of mated pairs;

S₁ is the mated rate of the reference pattern, K/n;

S₂ is the mated rate of the test pattern, K/m;

md is the average mated possibility of all the mated pairs; and

S₃ =1.01(1.0+average distance of the mated points).

wherein the planar point patterns are automatically matched based upon said similarity value (Score) of the two patterns.

2. The method according to claim 1 wherein said reference pattern and said test pattern are abstracted from planar image files and are the terminal points or cross points of lines or curves in said planar image;

wherein said feature direction represents the tangent direction of said line or curve while the corresponding point is a terminal point and represents the bisector direction of said line or curve while the corresponding point is a cross point; and

wherein said feature direction is the angle between it and the horizontal direction.

3. The method according to claim 1 or 2 further comprising a coarse mating process before the mating process wherein said coarse mating process comprises:

setting maximum tolerances for the difference in the feature directions and distance between points to be mated supposing said points are in a same coordinate; and

determining a pair of points belonging to respective patterns not mated if the difference of their feature directions or the distance thereof is greater than said maximum tolerances.

4. The method according to claim 3 wherein the Cijhk(θ

) of said pair of points is set to 0 if said points are determined not mated and wherein S[i][j][θ

] is set to be 0 if Cijhk(θ

) is 0.

5. The method according to claim 4 wherein w1 and w2 are both 0.

6. The method according to claim 3 further comprising a fine mating process before said mating process, comprising:

setting at least one requirement for mated points; and

determining pairs of points qk and ph to be not mated and the C_ijhk thereof to be 0 if said at least one requirement is not satisfied;

wherein said at least one requirement comprises;

distance requirement T1;

d1<

=T1;

rotation requirement θ

T;

|θ

|<

=θ

T;

direction requirement for starting points DR;

Ds<

=DR; and

direction requirement for ending points DR;

De<

=DR.

7. The method according to claim 1, further comprising an adjustment process after said mating process, wherein said adjustment process comprises:

obtaining a transformation (tx, ty, θ

) such that function E(tx, ty, θ

) will be the minimum;

transforming said test pattern with said transformation; and

mating the at least two pairs of points of the pattern according to the result of said transformation;

wherein;

x_qj =tx+x_pi cos θ

-y_pi sin θ

,

Y_qj =tx+x_pi sin θ

-y_pi cos θ

, and

D_qj =(D_pi +Dr)+θ

;

wherein (x_pi y_pi) and (x_qj y_qj) represent coordinates of pi and qj, D_pi and D_qj represent the feature directions of pi and qj respectively, and Dr is the difference between the feature directions of pi and qj after the transformation; and

##EQU12## wherein x'"'"'_op[i] =tx+x_op[i] cos θ

-y_op[i] sin θ

represents the x coordinate of op[i] being transformed by E(tx, ty, θ

); and

y'"'"'_op[i] =tx+x_op[i] sin θ

+y_op[i] cos θ

represents the y coordinate of opfil being transformed by E(tx, ty, θ

); and

op[i] represents the G reference pattern points belonging to mated pairs with the highest mating possibilities; and

G is a predetermined value greater than or equal to 4.

8. The method according to claim 7 wherein said adjustment process is applied to the G pairs of points and wherein pairs of points with distances exceeding a decided value are determined not mated.

9. The method according to claim 8 wherein the adjustment process is operated at least two times.

10. The method according to claim 7 wherein the adjustment process is operated at least two times.

11. A device for automatic matching of planar point patterns to decide whether two patterns (P and Q) consisting of points distributed in respective coordinate plans are similar wherein P={p1,p2, . . . pm} is a reference pattern including m points and Q={q1,q2, . . . qn} is a test pattern including n points and wherein every point of the pattern is expressed by (x,y,D) wherein (x, y) is the coordinate of the point and D is the feature direction of the point;

said device comprising;

a mating means to identify an only point (pi) in the P pattern for every point in the Q pattern, according to the coordinates and feature directions of the points;

a similarity calculation means to calculate the similarity of the two patterns according to the result of said mating process; and

a determination means to determine whether the two patterns are similar by comparing the result of said similarity calculation with a threshold;

wherein mating of said mating means comprises;

calculating the mated possibility of every point in the Q pattern (qj, j=1, 2, . . . , m) and every point in the P pattern (pi, i=1, 2, . . . , n), comprising;

designating a point in the Q pattern (qj) to be mated with a point in the P pattern (pi);

calculating the mated possibility of every point, other than said qj point, in the Q pattern (qk, k=1, 2, . . . , m. k≠

j) to be mated with every point, other than said pi point, in the P pattern (ph. h=1, 2, . . . , m, h≠

i), under a transformation angle; and

accumulating the mated possibility of qk points anci pn points under the premise that pi and qj are mated and making the result the mated possibility of qj and pi; and

selecting the mated parts according to the values of mated possibility of qj points and pi points;

wherein said mating means calculates the mated possibility of aj and pi while pattern Q is rotated at angle θ

(S[i][j][θ

]) according to the following equation;

##EQU13## wherein;

##EQU14## wherein;

C_ijkh (θ

) represents the mated possibility of qk (k=1, 2, . . . , m, k≠

j) and ph (h=1, 2, . . . , n h≠

i), θ

=θ

qjqk-θ

piph, Ds represents the difference between the difference between the feature direction of pi and the direction of piph and the difference between the feature direction of qj and the direction of qiqk, De represents the difference between the difference between the feature direction of ph and the direction of piph and the difference between the feature direction of qk and the direction of qiqk, d1 represents the difference between the lengths of piph and qiqk, and w, w1 and w2 are constants; and

wherein the similarity value calculation device calculates the similarity value (Score) of the two patterns is calculated according to the following equation;

Score=C*K*S₁ * S₃ *md, wherein

C is a constant;

K is the number of mated pairs;

S₁ is the mated rate of the reference pattern, K/n;

S₂ is the mated rate of the test pattern, K/m;

md is the average mated possibility of all the mated pairs; and

S₃ =1.0/(1.0 +average distance of the mated points).

wherein the planar point patterns are automatically matched based upon said similarity value (Score) of the two patterns.

12. The device according to claim 11 wherein said reference pattern and said test pattern are abstracted from planar image files and are the terminal points or cross points of lines or curves in said planar image;

wherein said feature direction represents the tangent direction of said line or curve while the corresponding point is a terminal point and represents the bisector direction of said line or curve while the corresponding point is a cross point; and

wherein said feature direction is the angle of it and the horizontal direction.

13. The device according to claim 11 or 12 further comprising a coarse mating means to determine whether a point of said pattern P and a point of said pattern Q are not mated wherein the determination of said coarse mating means comprises:

setting maximum tolerances for the difference in the feature directions and distance between points to be mated supposing said points are in a same coordinate; and

determining a pair of points belonging to respective patterns not mated if the difference of their feature directions or the distance thereof is greater than said maximum tolerances.

14. The device according to claim 13 wherein said coarse mating means sets the Cijhk(θ

) of a pair of points to be 0 if they are determined not mated and wherein the S[i][j][θ

] is set to 0 if Cijhk(θ

) is 0.

15. The device according to claim 14 wherein w1 and w2 are both 0.

16. The device according to claim 13 further comprising a fine mating means to determine whether Cijhk(θ

) is 0, said determination comprising;

setting at least one requirement for mated points; and

determining pairs of points qk and ph to be not mated and the C_ijhk thereof to be 0 if said at least one requirement is not satisfied;

wherein said at least one requirement comprises;

distance requirement T1;

d1<

=T1;

rotation requirement θ

T;

|θ

|<

=θ

T;

direction requirement for starting points DR;

Ds<

=DR; and

direction requirement for ending points DR;

Ds<

=DR.

17. The device according to claim 11 or 12, further comprising an adjustment process to transform said pattern Q after said mating, said transformation comprising:

obtaining a transformation (tx,ty,θ

) such that function E(tx,ty,θ

) has the least value;

transforming said test pattern with said transformation; and

mating the pattern according to the result of said transformation;

wherein;

x_qj =tx+x_pi cos θ

-y_pi sin θ

,

Y_qj =tx+x_pi sin θ

-y_pi cos θ

, and

D_qj =(D_pi +Dr)+θ

;

wherein (x_pi y_pi) and (x_qj y_qj) represent coordinates of pi and qj, D_pi and D_qj represent the feature directions of pi and qj respectively, and Dr is the difference between the feature directions of pi and qj after the transformation; and

##EQU15## wherein x'"'"'_op[i] =tx+x_op[i] cos θ

-y_op[i] sin θ

represents the x coordinate of op[i] being transformed by E(tx,ty,θ

);

y'"'"'_op[i] =tx+x_op[i] sin θ

+y_op[i] cos θ

represents the y coordinate of op[i] being transformed by E(tx,ty,θ

); and

op[i] represents the G reference pattern points belonging to mated pairs with the highest mating possibilities; and

G is a predetermined value greater than or equal to 4.

18. The device according to claim 17 wherein said adjustment means transforms G points of said pattern Q and determines pairs of points with distances exceeding a decided value not mated.