# Point Pattern Matching Algorithm for Planar Point Sets under Euclidean Transform

Authors: Xiaoyun Wang; Xianquan Zhang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Point pattern matching is an important topic of computer vision and pattern recognition. In this paper, we propose a point pattern matching algorithm for two planar point sets under Euclidean transform. We view a point set as a complete graph, establish the relation between the point set and the complete graph, and solve the point pattern matching problem by finding congruent complete graphs. Experiments are conducted to show the effectiveness and robustness of the proposed algorithm.


---

## Body

## 1. Introduction

Point pattern matching problem is an important task of computer vision and pattern recognition. It is to find a good correspondence between two point sets inm-dimensional space. In general, it can be classified into two kinds. One is that the point number of the two point sets is the same. The other is that the point numbers are different. The first case is called complete matching, while the second case is called incomplete matching or partial matching. Point pattern matching has found many applications, such as image registration, motion detection, object tracking, automated visual inspection of flat objects, autonavigation, and pose estimation.In the past decades, many researchers have devoted themselves to designing high performance point pattern matching algorithms. Griffin and Alexopoulos [1] present a method for the complete matching problem. They calculate the two pattern controids and align them and then construct a bipartite graph. The point matching is finally found by determining the maximal cardinality matching of the bipartite graph. Vinod and Ghose [2] view point pattern matching problem as 0-1 integer programming problem and then use an artificial neural network to solve the point pattern matching problem under translation and rotation transform. To solve the problem of noisy point pattern matching, Morgera and Cheong [3] propose a hybrid and iterative method accommodating patterns from different dimensions. It exploits singular value decomposition to estimate the rotation matrix and steepest-ascent to find the permutation matrix. In [4], Wang and Chen consider the matching problem of point sets with affine transform and use the intrinsic invariant properties of a line segment to design a pattern-matching method. In another work [5], Chang et al. propose a fast algorithm based on 2D cluster approach. It can find the optimal matching between two point sets under the transform of translation, rotation, and scale. In [6], Chui and Rangarajan propose a robust point matching algorithm based on the softassign and the thin-plate spline. This algorithm can jointly estimate the correspondence and nonrigid transformations between two point sets with different sizes. In [7], Carcassoni and Hancock exploit three ways to improve the recovery of point correspondences using spectral analysis of the point proximity matrix. These ways include an alternative proximity weighting matrix, robust methods for comparing the eigenvectors of the proximity matrix and embedding the correspondence process within the EM algorithm. To solve the incomplete matching problem under affine transform, Zhang et al. [8] design a method combining a genetic algorithm with partial Hausdorff distance.In [9], Van Wamelen et al. propose a fast algorithm for 2D point matching using probabilistic and sorted nearest neighbors. Its time complexity is O(n(log m)3/2), where n and m are the point numbers of the point sets. Li et al. [10] introduce a new similarity K-d tree method to establish a one-to-one match and then apply it to matching nonaffinely-related point sets. To target the optimal transform between point sets, Yin [11] exploits the technique of particle swarm optimization, where the transform parameters are encoded as a real-valued vector called particle. Bishnu et al. [12] present simple and deterministic algorithm for point pattern matching under translation and rotation in 2D. It runs O(n 2log n) time for complete matching and O(mn4/3 log n) time for incomplete matching. In [13], Caetano et al. give a graphical models-based algorithm to achieve point pattern matching in Euclidean spaces of any dimension. This algorithm runs in a polynomial time and is provably optimal for complete matching between noiseless point sets. Later, McAuley et al. [14] present a new graph showing better performance than that of [13] and use it to determine point set matching. Li et al. [15] propose a dynamic segment-based hierarchical point matching algorithm for self-initialising articulated motion reconstruction from sparse feature points. Recently, Bhowmick et al. [16] propose a novel data structure called “angular tree” for supporting point pattern matching algorithms. Aiger and Kedem [17] introduce an efficient algorithm for matching point sets under the transform of translation, rotation, and scale by using the Hausdorff metric as a distance function. In another study [18], Aiger and Kedem propose a matching algorithm based on a simple alignment scheme. It runs roughly in O(n log n+ km log n) time, where m and n are the point number of two point sets and k is the number of matched subsets between the two sets.Most of the above algorithms are designed to solve the matching problem under affine transform or the transform of translation and rotation. These works are not suitable for the point sets under reflection transform. To overcome this problem, we propose an efficient algorithm based on the fact that the Euclidean distance between any two points is invariant. This algorithm is not only suitable for point sets under reflection transform, but also effective for those under translation and rotation transform. The rest of the paper is organized as follows. Section2 introduces congruent complete graph-based algorithm. Section 3 presents the proposed algorithm. Experimental results are given in Section 4 and conclusions are made in Section 5.


## 2. Congruent Complete Graph-Based Algorithm

### 2.1. Congruent Complete Graphs

A point set can be represented by a complete graph as follows. A vertex denotes a point and the weight of an edge connecting two vertices represents the Euclidean distance between the corresponding two points. For a given point set, if the point number isn, the edge number of its corresponding complete graph is n(n−1)/2. Clearly, if V and V′ are two matched point sets under reflection transform, or transform of translation and rotation, the corresponding edges of their complete graphs are equal, and vice versa. In general, translation and rotation transform and reflection transform are collectively called Euclidean transform.Definition 2.1.
If all corresponding edges of two complete graphs are equal, they are congruent graphs.
LetG(V) and G(V′) be the complete graphs of V and V′, respectively, and G(V)≅G(V′) represent that G(V) and G(V′) are congruent graphs. Thus, there is a property of congruent graphs.Property 1.
IfG(V)≅G(V′), the point sets V and V′ are the matching sets under Euclidean transform.
If two point sets are the matching sets under Euclidean transform, corresponding edges of congruent graphs formed by these point sets are equal, and vice versa. As shown in Figure1, since G({p1,p2,p3,p4})≅G({q1,q2,q3,q4}),{p1,p2,p3,p4}, and {q1,q2,q3,q4} are the matching sets under reflection transform. Similarly, {p1,p2,p3,p4} and {v1,v2,v3,v4} are the matching sets under translation and rotation transform since G({p1,p2,p3,p4})≅G({v1,v2,v3,v4}).
Let V  = {v1,v2,…,vk} (k≥3) and V′={v1′,v2′,…,vk′} be two planar point sets. If we use the Euclidean distance between any two points to represent the corresponding edge weight of graph, the complete graph of each point set has k(k-1)/2 edges. Clearly, we can find congruent complete graphs by calculating all edges and establishing their corresponding relations. However, such computational cost is large. To reduce computation, we can calculate matched edges based on the following theorem.Figure 1
Congruent complete graphs and corresponding point sets.Theorem 2.2.
Let(va,va′) and (vb,vb′) be two pairs of matched points between V and V′. Thus, we have G(V)≅G(V′) if they satisfy the following conditions.(1)
|vavi|=|va′vi′|(i=1,2,…,k,i≠a) and |vbvi|=|vb′vi′|(i=1,2,…,k,i≠b).(2)
Ifv1,v2,…,vk(i≠a,i≠b) are on one side of the straight line vavb,  their corresponding points v1′,v2′,…,vk′ are also on the corresponding side of the straight line va′vb′.(3)
Ifva,vb, and vi (i≠a,i≠b) are collinear, their corresponding points va′,vb′, and vi′ are also collinear.Proof.
As shown in Figure2(a), suppose that va, vb, and vi(i≠a,i≠b) are not collinear, and for a given vertex vj, there are also no three collinear vertices among {va, vb, vi, vj}. According to the condition (2), assume that vi and vj are on one side of the straight line vavb. Thus, vi′ and vj′ are on the corresponding side of straight line va′vb′. Using the condition (1), it is deduced that |vavb|=|va′vb′|,|vavi|=|va′vi′|, and |vbvi|=|vb′vi′|. Therefore, G({va,vb,vi})≅G({va′,vb′,vi′}) by Definition 2.1. Similarly, G({va,vb,vj})≅G({va′,vb′,vj′}). The Property 1 shows that ∠vbvavj=∠vb′va′vj′and∠vbvavi=∠vb′va′vi′. Thus, ∠vivavj=∠vi′va′vj′ because ∠vbvavj=∠vbvavi+∠vivavj and ∠vb′va′vj′=∠vb′va′vi′+∠vi′va′vj′. Since |vavi|=|va′vi′|  and |vavj|=|va′vj′|   (Condition 1), G({va,vi,vj})≅G({va′,vi′,vj′}) by Definition 2.1. Thus, |vivj|=|vi′vj′|. This means that the distance between vi and other vertex is equal to that between vi′ and the corresponding vertex. The case that viandvj are on different side of straight line vavb can be proven by using the similar steps.Two pairs of congruent complete graphs.
(a)
va, vb, and vi are not collinear.(b)
va, vb, and vi are collinear.Consider the case that vertices are collinear. Ifva,vb, and vi are collinear, va′,vb′, and vi′ are also collinear (Condition 3). If vj and vj′ are on the straight lines vavb and va′vb′ respectively, it is clearly that |vivj|=|vi′vj′|. If they are not on the straight lines as shown in Figure 2(b), |vivj|=|vi′vj′| is also available.From the above analysis, it can be found that|vivj|=|vi′vj′| can be derived if the vertices vi and vj satisfy the above-mentioned conditions. So G(V)≅G(V′).Obviously, the pattern matching between two point setsP and Q under Euclidean transform can be achieved by calculating their congruent complete graphs. The detailed algorithm is as follows.(1)
For each vertexpi∈P(i=1,2,…,n), calculate the Euclidean distance |pipj|(i≠j)  between pi and pj and sort these distances to make an ascending sequence.(2)
For each vertexqi∈Q(i=1,2,…,m), calculate the Euclidean distance |qiqj|(i≠j) between qi and qj and sort these distances to make an ascending sequence.(3)
Compute the congruent complete graphs betweenG(P) and G(Q) by Theorem 2.2 and determine whether or not P and Q are matched.


### 2.2. Parameters of Congruent Complete Graphs

If two point sets are matched, one can be viewed as the transformed result of the other, where the transform may be translation and rotation transform or reflection transform. Note that Euclidean distance between two points is invariant under these transforms. Parameters of the above transforms are discussed as follows. (1) Translation and rotation transform denoted asTθ,tx,ty: let (x,y) be the coordinates of a point and (x′,y′) the coordinates of its transformed version. If they satisfy the following equation:(2.1)(x′y′)=(txty)+(cos⁡θ-sin⁡θsin⁡θcos⁡θ)(xy),
the transform is called translation and rotation transform, where θ is the rotation angle tx and ty are the translations along x-axis and y-axis, respectively. The θ, tx, and ty are the parameters of translation and rotation transform. (2) Reflection transform denoted as  Tl: if l is the perpendicular bisector of the line segment connecting (x,y) and (x′,y′), the two points are a pair of matched points under the Tl, where l is the symmetry axis and the parameter of the reflection transform. Parameter calculations are as follows.For translation and rotation transform, let (p1, q1) and (p2, q2) be two pairs of matched points under translation and rotation transform, that is, Tθ,tx,ty(qi)=pi(i=1,2), where the coordinates of qi and pi are (xi,yi) and (xi′,yi′), respectively. Substitute the coordinates of each pair of points into (2.1) and then obtain the following equation:(2.2)tx=x1′-x1cos⁡θ+y1sin⁡θ,ty=y1′-x1sin⁡θ-y1cos⁡θ,θ=θq1q2⃗-θq1q2⃗,
where θ is the included angle between q1q2⃗  and p1p2⃗. From (2.2), it is found that the transform parameters tx, ty, and θ can be uniquely determined by two pairs of matched points.For reflection transform, suppose that{q1′,q2′,…,qr′} is the transformed result of {q1,q2,…,qr} under the transform Tl, as shown in Figure 3. If qi(i=1,2,…,r) and qi′ are not the same point, the perpendicular bisector l of the line segment connecting qi and qi′ is the symmetry axis of the reflection transform.Figure 3
Symmetry axis of reflection transform.From the above analysis, it is clearly that the parameterstx, ty, and θ can uniquely determine a translation and rotation transform, and the symmetry axis l can determine a reflection transform. If V′={v1′,v2′,…,vk′}(k≥3) is the transformed result of V={v1,v2,…,vk} under the Euclidean transform, Vand V′ are a pair of matched point sets.


## 2.1. Congruent Complete Graphs

A point set can be represented by a complete graph as follows. A vertex denotes a point and the weight of an edge connecting two vertices represents the Euclidean distance between the corresponding two points. For a given point set, if the point number isn, the edge number of its corresponding complete graph is n(n−1)/2. Clearly, if V and V′ are two matched point sets under reflection transform, or transform of translation and rotation, the corresponding edges of their complete graphs are equal, and vice versa. In general, translation and rotation transform and reflection transform are collectively called Euclidean transform.Definition 2.1.
If all corresponding edges of two complete graphs are equal, they are congruent graphs.
LetG(V) and G(V′) be the complete graphs of V and V′, respectively, and G(V)≅G(V′) represent that G(V) and G(V′) are congruent graphs. Thus, there is a property of congruent graphs.Property 1.
IfG(V)≅G(V′), the point sets V and V′ are the matching sets under Euclidean transform.
If two point sets are the matching sets under Euclidean transform, corresponding edges of congruent graphs formed by these point sets are equal, and vice versa. As shown in Figure1, since G({p1,p2,p3,p4})≅G({q1,q2,q3,q4}),{p1,p2,p3,p4}, and {q1,q2,q3,q4} are the matching sets under reflection transform. Similarly, {p1,p2,p3,p4} and {v1,v2,v3,v4} are the matching sets under translation and rotation transform since G({p1,p2,p3,p4})≅G({v1,v2,v3,v4}).
Let V  = {v1,v2,…,vk} (k≥3) and V′={v1′,v2′,…,vk′} be two planar point sets. If we use the Euclidean distance between any two points to represent the corresponding edge weight of graph, the complete graph of each point set has k(k-1)/2 edges. Clearly, we can find congruent complete graphs by calculating all edges and establishing their corresponding relations. However, such computational cost is large. To reduce computation, we can calculate matched edges based on the following theorem.Figure 1
Congruent complete graphs and corresponding point sets.Theorem 2.2.
Let(va,va′) and (vb,vb′) be two pairs of matched points between V and V′. Thus, we have G(V)≅G(V′) if they satisfy the following conditions.(1)
|vavi|=|va′vi′|(i=1,2,…,k,i≠a) and |vbvi|=|vb′vi′|(i=1,2,…,k,i≠b).(2)
Ifv1,v2,…,vk(i≠a,i≠b) are on one side of the straight line vavb,  their corresponding points v1′,v2′,…,vk′ are also on the corresponding side of the straight line va′vb′.(3)
Ifva,vb, and vi (i≠a,i≠b) are collinear, their corresponding points va′,vb′, and vi′ are also collinear.Proof.
As shown in Figure2(a), suppose that va, vb, and vi(i≠a,i≠b) are not collinear, and for a given vertex vj, there are also no three collinear vertices among {va, vb, vi, vj}. According to the condition (2), assume that vi and vj are on one side of the straight line vavb. Thus, vi′ and vj′ are on the corresponding side of straight line va′vb′. Using the condition (1), it is deduced that |vavb|=|va′vb′|,|vavi|=|va′vi′|, and |vbvi|=|vb′vi′|. Therefore, G({va,vb,vi})≅G({va′,vb′,vi′}) by Definition 2.1. Similarly, G({va,vb,vj})≅G({va′,vb′,vj′}). The Property 1 shows that ∠vbvavj=∠vb′va′vj′and∠vbvavi=∠vb′va′vi′. Thus, ∠vivavj=∠vi′va′vj′ because ∠vbvavj=∠vbvavi+∠vivavj and ∠vb′va′vj′=∠vb′va′vi′+∠vi′va′vj′. Since |vavi|=|va′vi′|  and |vavj|=|va′vj′|   (Condition 1), G({va,vi,vj})≅G({va′,vi′,vj′}) by Definition 2.1. Thus, |vivj|=|vi′vj′|. This means that the distance between vi and other vertex is equal to that between vi′ and the corresponding vertex. The case that viandvj are on different side of straight line vavb can be proven by using the similar steps.Two pairs of congruent complete graphs.
(a)
va, vb, and vi are not collinear.(b)
va, vb, and vi are collinear.Consider the case that vertices are collinear. Ifva,vb, and vi are collinear, va′,vb′, and vi′ are also collinear (Condition 3). If vj and vj′ are on the straight lines vavb and va′vb′ respectively, it is clearly that |vivj|=|vi′vj′|. If they are not on the straight lines as shown in Figure 2(b), |vivj|=|vi′vj′| is also available.From the above analysis, it can be found that|vivj|=|vi′vj′| can be derived if the vertices vi and vj satisfy the above-mentioned conditions. So G(V)≅G(V′).Obviously, the pattern matching between two point setsP and Q under Euclidean transform can be achieved by calculating their congruent complete graphs. The detailed algorithm is as follows.(1)
For each vertexpi∈P(i=1,2,…,n), calculate the Euclidean distance |pipj|(i≠j)  between pi and pj and sort these distances to make an ascending sequence.(2)
For each vertexqi∈Q(i=1,2,…,m), calculate the Euclidean distance |qiqj|(i≠j) between qi and qj and sort these distances to make an ascending sequence.(3)
Compute the congruent complete graphs betweenG(P) and G(Q) by Theorem 2.2 and determine whether or not P and Q are matched.


## 2.2. Parameters of Congruent Complete Graphs

If two point sets are matched, one can be viewed as the transformed result of the other, where the transform may be translation and rotation transform or reflection transform. Note that Euclidean distance between two points is invariant under these transforms. Parameters of the above transforms are discussed as follows. (1) Translation and rotation transform denoted asTθ,tx,ty: let (x,y) be the coordinates of a point and (x′,y′) the coordinates of its transformed version. If they satisfy the following equation:(2.1)(x′y′)=(txty)+(cos⁡θ-sin⁡θsin⁡θcos⁡θ)(xy),
the transform is called translation and rotation transform, where θ is the rotation angle tx and ty are the translations along x-axis and y-axis, respectively. The θ, tx, and ty are the parameters of translation and rotation transform. (2) Reflection transform denoted as  Tl: if l is the perpendicular bisector of the line segment connecting (x,y) and (x′,y′), the two points are a pair of matched points under the Tl, where l is the symmetry axis and the parameter of the reflection transform. Parameter calculations are as follows.For translation and rotation transform, let (p1, q1) and (p2, q2) be two pairs of matched points under translation and rotation transform, that is, Tθ,tx,ty(qi)=pi(i=1,2), where the coordinates of qi and pi are (xi,yi) and (xi′,yi′), respectively. Substitute the coordinates of each pair of points into (2.1) and then obtain the following equation:(2.2)tx=x1′-x1cos⁡θ+y1sin⁡θ,ty=y1′-x1sin⁡θ-y1cos⁡θ,θ=θq1q2⃗-θq1q2⃗,
where θ is the included angle between q1q2⃗  and p1p2⃗. From (2.2), it is found that the transform parameters tx, ty, and θ can be uniquely determined by two pairs of matched points.For reflection transform, suppose that{q1′,q2′,…,qr′} is the transformed result of {q1,q2,…,qr} under the transform Tl, as shown in Figure 3. If qi(i=1,2,…,r) and qi′ are not the same point, the perpendicular bisector l of the line segment connecting qi and qi′ is the symmetry axis of the reflection transform.Figure 3
Symmetry axis of reflection transform.From the above analysis, it is clearly that the parameterstx, ty, and θ can uniquely determine a translation and rotation transform, and the symmetry axis l can determine a reflection transform. If V′={v1′,v2′,…,vk′}(k≥3) is the transformed result of V={v1,v2,…,vk} under the Euclidean transform, Vand V′ are a pair of matched point sets.


## 3. Proposed Algorithm

### 3.1. Calculation of Congruent Complete Graphs

LetP={p1,p2,…,pm} and Q={q1,q2,…,qn} be two matched point sets in a 2D plane. To find the congruent complete graphs containing vertices pa and qb, we calculate the distances |papi| (i=1,2,…,m,i≠a) and |qbqj|(j=1,2,…,n,j≠b), and make these distances in ascending order, where the sorted result of |papi| is {d1,d2,…,dm-1} and that of |qbqj| is {s1,s2,…,sn-1}. Thus, congruent complete graphs can be calculated by the following steps.(1)
Leti=1 and j=1. If di=sj, record the matched points forming the matched sets and let i←i+1. If di>sj, let j←j+1. If di<sj, let i←i+1. Repeat the computation until i=m or j=n.(2)
Select a pair of matched pointspc and qf from the above matched sets, whose distances to pa and qb are equal. Calculate the distances from pc and qf to other corresponding matched points, respectively, and compute the congruent complete graphs by the Theorem 2.2. If the congruent complete graphs are available, we extract other congruent complete graphs from the rest points. Otherwise, we select another matched pair to calculate congruent complete graphs until all matched pairs are used.


### 3.2. Matching Algorithm Based on Complete Graphs

For incomplete matching problem, if we calculate complete graphs of all points to identify congruent graphs, the computational cost is large. In here, nearest neighbor algorithm is exploited to improve efficiency. LetP={p1,p2,…,pm} and Q={q1,q2,…,qn} be two matched point sets, and the matched probability in P is ρ, that is, ρm points of P have matched points in Q. Thus, the matched probability ρ′in Q can be calculated by(3.1)ρ′=ρmn.Note that the minimum point number of congruent complete graphs is 3. Suppose that the selected neighbor point numbers inP and Q are k and t. For each point of P and Q, we apply the method [19] to find its nearest neighbor points. A small number of neighbor points is helpful to improve computational speed. However, average matched point number for each point could not be smaller than 3. In the words, the k or t value must satisfy ρk≥3 or ρ′t≥3. Thus, we have(3.2)k=⌈3ρ⌉,
where  ⌈·⌉ means upward rounding. So we have(3.3)t=⌈3ρ⌉=⌈3nρm⌉.Detailed steps of the proposed matching algorithm are as follows.Step 1.
For each point ofQ, extract t neighbor points by the method [19], calculate the distances to the neighbor points, and sort these distances.Step 2.
Randomly select a point fromP and find its k neighbor points by the method [19] again. Next, calculate its distances to the k neighbor points, and sort these distances. Apply the Theorem 2.2 to determine matched graphs between the complete graph forming by these k+1 points of P and the other complete graph of each point of Q. During the determination, we record the transform parameters and the transform type, that is, translation and rotation transform or reflection transform.Step 3.
Repeat Step2 and merge the congruent complete graphs with the same transform parameters and the same transform type. If the point number of the congruent complete graphs is bigger than a predefined threshold T, we recalculate the transform parameters. If the calculated results are equal to the prior values, the corresponding points forming the congruent complete graphs are the matched points. The algorithm is done. Otherwise, turn to Step 2.


## 3.1. Calculation of Congruent Complete Graphs

LetP={p1,p2,…,pm} and Q={q1,q2,…,qn} be two matched point sets in a 2D plane. To find the congruent complete graphs containing vertices pa and qb, we calculate the distances |papi| (i=1,2,…,m,i≠a) and |qbqj|(j=1,2,…,n,j≠b), and make these distances in ascending order, where the sorted result of |papi| is {d1,d2,…,dm-1} and that of |qbqj| is {s1,s2,…,sn-1}. Thus, congruent complete graphs can be calculated by the following steps.(1)
Leti=1 and j=1. If di=sj, record the matched points forming the matched sets and let i←i+1. If di>sj, let j←j+1. If di<sj, let i←i+1. Repeat the computation until i=m or j=n.(2)
Select a pair of matched pointspc and qf from the above matched sets, whose distances to pa and qb are equal. Calculate the distances from pc and qf to other corresponding matched points, respectively, and compute the congruent complete graphs by the Theorem 2.2. If the congruent complete graphs are available, we extract other congruent complete graphs from the rest points. Otherwise, we select another matched pair to calculate congruent complete graphs until all matched pairs are used.


## 3.2. Matching Algorithm Based on Complete Graphs

For incomplete matching problem, if we calculate complete graphs of all points to identify congruent graphs, the computational cost is large. In here, nearest neighbor algorithm is exploited to improve efficiency. LetP={p1,p2,…,pm} and Q={q1,q2,…,qn} be two matched point sets, and the matched probability in P is ρ, that is, ρm points of P have matched points in Q. Thus, the matched probability ρ′in Q can be calculated by(3.1)ρ′=ρmn.Note that the minimum point number of congruent complete graphs is 3. Suppose that the selected neighbor point numbers inP and Q are k and t. For each point of P and Q, we apply the method [19] to find its nearest neighbor points. A small number of neighbor points is helpful to improve computational speed. However, average matched point number for each point could not be smaller than 3. In the words, the k or t value must satisfy ρk≥3 or ρ′t≥3. Thus, we have(3.2)k=⌈3ρ⌉,
where  ⌈·⌉ means upward rounding. So we have(3.3)t=⌈3ρ⌉=⌈3nρm⌉.Detailed steps of the proposed matching algorithm are as follows.Step 1.
For each point ofQ, extract t neighbor points by the method [19], calculate the distances to the neighbor points, and sort these distances.Step 2.
Randomly select a point fromP and find its k neighbor points by the method [19] again. Next, calculate its distances to the k neighbor points, and sort these distances. Apply the Theorem 2.2 to determine matched graphs between the complete graph forming by these k+1 points of P and the other complete graph of each point of Q. During the determination, we record the transform parameters and the transform type, that is, translation and rotation transform or reflection transform.Step 3.
Repeat Step2 and merge the congruent complete graphs with the same transform parameters and the same transform type. If the point number of the congruent complete graphs is bigger than a predefined threshold T, we recalculate the transform parameters. If the calculated results are equal to the prior values, the corresponding points forming the congruent complete graphs are the matched points. The algorithm is done. Otherwise, turn to Step 2.


## 4. Experimental Results

To validate the proposed algorithm, many experiments are conducted and all results show the effectiveness of our algorithm. In here, typical examples including the synthesized point sets and the real point sets from fingerprints are presented. For the synthesized examples, point sets under the two kinds of Euclidean transform are both considered, where the matched probability inP is 0.8, that is, ρ=0.8. As the points may be perturbed by noises in a real-world situation, we define a threshold ε=4. If the difference between two distances is smaller than the threshold, their corresponding edges are considered as a matched pair.


### 4.1. Reflection Transform

The point sets are produced as follows. Firstly, 40 random points with integer coordinates are generated in a square sized 256 × 256 to form the point setP. A reflection transform with symmetric axis y=2x+3 and a translation transform with tx=7 and ty=4 are then applied to the 40 points. So 40 points of Q are then obtained. To test the robustness of our algorithm, 10 random points in the 256 × 256 square are generated and then added into P. Another reflection is applied to the 10 points to generate their transformed versions, which are then added to Q. Moreover, another 10 points, which do not belong to P, are added to Q. During the point generations, the distance between each two points is not smaller than 10. Furthermore, the coordinates of points in P and Q are both perturbed by Gaussian noises with 0 mean and 1 variance, and the quantization errors caused by the noises are controlled within ±3. Coordinates of the points in P and Q are presented in Tables 1 and 2, where the serial numbers of points are randomly arranged. As expected, the propose algorithm correctly finds 40 matched pairs of points. The matched results are listed in Table 3.Table 1
Coordinates of the points inP.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(132, 225)11(153, 36)21(212, 203)31(125, 73)41(114, 157)2(108, 214)12(94, 13)22(252, 150)32(79, 20)42(128, 126)3(174, 82)13(28, 6)23(245, 69)33(64, 102)43(213, 233)4(144, 73)14(18, 77)24(59, 19)34(208, 107)44(128, 178)5(241, 241)15(200, 67)25(13, 137)35(196, 48)45(234, 201)6(187, 233)16(187, 139)26(10, 28)36(59, 161)46(204, 83)7(235, 179)17(3, 90)27(219, 174)37(34, 246)47(191, 103)8(166, 219)18(125, 9)28(120, 54)38(34, 145)48(20, 214)9(60, 135)19(56, 37)29(253, 18)39(202, 153)49(220, 142)10(12, 62)20(31, 93)30(73, 50)40(2, 185)50(102, 131)Table 2
Coordinates of the points inQ under reflection transform.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(−63, 110)11(−58, 149)21(−23, 164)31(60, 85)41(105, 245)51(12, 284)2(−94, 165)12(−34, 193)22(−13, 266)32(47, 117)42(78, 294)52(−8, 204)3(−71, 166)13(−51, 218)23(21, 30)33(35, 137)43(63, 315)53(106, 97)4(−102, 196)14(−34, 235)24(81, −182)34(48, 165)44(−63, 305)54(116, −96)5(−61, 205)15(−26, 296)25(11, 129)35(61, 190)45(151, 117)55(51, −137)6(−132, 218)16(−7, 31)26(4, 238)36(163, −69)46(163, 149)56(93, −49)7(−109, 228)17(−15, 63)27(6, 258)37(74, 61)47(181, 180)57(1, 72)8(−87, 245)18(−26, 80)28(−75, −45)38(76, 134)48(130, 189)58(130, −189)9(−41, 88)19(1, 93)29(25, 313)39(98, 149)49(163, 199)59(52, 342)10(−48, 127)20(−12, 149)30(47, 52)40(70, 214)50(135, 254)60(135, −254)Table 3
Matched pairs (ni, nj) between Tables 1 and 2, where ni and nj are the serial numbers of points in Tables 1 and 2.
No.(ni, nj)No.(ni, nj)No.(ni, nj)No.(ni, nj)1(11, 11)11(26, 23)21(36, 39)31(22, 8)2(46, 13)12(39, 27)22(44, 40)32(12, 9)3(34, 14)13(27, 51)23(43, 43)33(3, 12)4(22, 15)14(45, 29)24(25, 53)34(4, 21)5(13, 16)15(10, 30)25(40, 45)35(19, 57)6(24, 17)16(20, 31)26(48, 46)36(16, 26)7(32, 18)17(33, 32)27(37, 47)37(5, 59)8(30, 19)18(50, 34)28(18, 1)38(9, 38)9(31, 20)19(41, 35)29(15, 5)39(1, 41)10(49, 22)20(17, 37)30(29, 6)40(6, 42)


### 4.2. Translation and Rotation Transform

The point setP used in Subsection 4.1 is also adopted here. We apply the translation and rotation transform with tx=7,ty=4, and θ=0.716 (radian) to the first 40 points of P and then obtain 40 points of Q. Next, we apply another transform of translation and rotation to the last 10 points of P and add the transformed points to Q. Moreover, another 10 points are added to Q. During generation, the distance between each two points is also not smaller than 10. Similarly, Gaussian noises with 0 mean and 1 variance is also exploited to perturb the points of Q. Table 4 are the coordinates of those points of Q. Our algorithm correctly determines 40 matched pairs of points, as shown in Table 5.Table 4
Coordinates of the points inQ under translation and rotation transform.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(−72, 116)11(−30, 95)21(−4, 303)31(69, 75)41(107, 200)51(37, −206)2(−112, 145)12(−11, 123)22(15, 320)32(68, 154)42(94, 221)52(−94, −81)3(−53, 164)13(−35, 145)23(39, 57)33(57, 232)43(99, 283)53(9, −223)4(−117, 179)14(−12, 222)24(25, 69)34(59, 252)44(137, 140)54(13, −150)5(−76, 210)15(−40, 260)25(29, 90)35(80, 256)45(115, 145)55(101, −45)6(−128, 212)16(24, 27)26(26, 127)36(58, 279)46(152, 168)56(114, 186)7(−107, 228)17(−3, 32)27(−16, −98)37(95, 93)47(186, 184)57(86, −84)8(−67, 275)18(4, 140)28(52, 309)38(85, 113)48(150, −68)58(24, −126)9(−24, 59)19(−1, 170)29(31, 344)39(99, 132)49(165, 198)59(53, 141)10(−49, 74)20(−9, 197)30(54, 71)40(85, 180)50(147, 217)60(−47, −211)Table 5
Matched pairs (ni, nj) between Tables 1 and 4, where ni and nj are the serial numbers of points in Tables 1 and 4.
No.(ni, nj)No.(ni, nj)No.(ni, nj)No.(ni, nj)1(25, 1)11(13, 16)21(16, 33)31(6, 21)2(40, 2)12(26, 17)22(39, 34)32(19, 24)3(36, 3)13(50, 19)23(49, 35)33(5, 29)4(48, 4)14(41, 20)24(27, 36)34(32, 30)5(37, 6)15(43, 22)25(18, 37)35(4, 32)6(10, 9)16(24, 23)26(46, 41)36(11, 39)7(17, 10)17(30, 25)27(34, 42)37(3, 40)8(20, 11)18(31, 27)28(22, 43)38(29, 47)9(33, 12)19(45, 28)29(9, 13)39(15, 48)10(44, 14)20(12, 31)30(1, 15)40(23, 50)


### 4.3. Fingerprint Matching

To view the performance in a real-world situation, the proposed algorithm is applied to fingerprint recognition. Figure4 presents two fingerprint images taken from the same finger of a person. The circled feature points are manually selected and their coordinates are also manually extracted by using the software origin. In this experiment, the circled features represent those points for pattern matching and the total number of used features in each fingerprint image is 42. Our algorithm finds 35 matched pairs of features, indicating the practicability of the proposed algorithm. The results are as shown in Figure 5, where the “×” marks represent the feature points in Figure 4(a), the “+” marks represent the feature points in Figure 4(b), and the circle marks mean the matched pairs.Two different fingerprint images from the same finger with circled features.
(a)
A fingerprint image(b)
Another fingerprint imageFigure 5
Matched pairs between Figures4(a) and 4(b).


## 4.1. Reflection Transform

The point sets are produced as follows. Firstly, 40 random points with integer coordinates are generated in a square sized 256 × 256 to form the point setP. A reflection transform with symmetric axis y=2x+3 and a translation transform with tx=7 and ty=4 are then applied to the 40 points. So 40 points of Q are then obtained. To test the robustness of our algorithm, 10 random points in the 256 × 256 square are generated and then added into P. Another reflection is applied to the 10 points to generate their transformed versions, which are then added to Q. Moreover, another 10 points, which do not belong to P, are added to Q. During the point generations, the distance between each two points is not smaller than 10. Furthermore, the coordinates of points in P and Q are both perturbed by Gaussian noises with 0 mean and 1 variance, and the quantization errors caused by the noises are controlled within ±3. Coordinates of the points in P and Q are presented in Tables 1 and 2, where the serial numbers of points are randomly arranged. As expected, the propose algorithm correctly finds 40 matched pairs of points. The matched results are listed in Table 3.Table 1
Coordinates of the points inP.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(132, 225)11(153, 36)21(212, 203)31(125, 73)41(114, 157)2(108, 214)12(94, 13)22(252, 150)32(79, 20)42(128, 126)3(174, 82)13(28, 6)23(245, 69)33(64, 102)43(213, 233)4(144, 73)14(18, 77)24(59, 19)34(208, 107)44(128, 178)5(241, 241)15(200, 67)25(13, 137)35(196, 48)45(234, 201)6(187, 233)16(187, 139)26(10, 28)36(59, 161)46(204, 83)7(235, 179)17(3, 90)27(219, 174)37(34, 246)47(191, 103)8(166, 219)18(125, 9)28(120, 54)38(34, 145)48(20, 214)9(60, 135)19(56, 37)29(253, 18)39(202, 153)49(220, 142)10(12, 62)20(31, 93)30(73, 50)40(2, 185)50(102, 131)Table 2
Coordinates of the points inQ under reflection transform.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(−63, 110)11(−58, 149)21(−23, 164)31(60, 85)41(105, 245)51(12, 284)2(−94, 165)12(−34, 193)22(−13, 266)32(47, 117)42(78, 294)52(−8, 204)3(−71, 166)13(−51, 218)23(21, 30)33(35, 137)43(63, 315)53(106, 97)4(−102, 196)14(−34, 235)24(81, −182)34(48, 165)44(−63, 305)54(116, −96)5(−61, 205)15(−26, 296)25(11, 129)35(61, 190)45(151, 117)55(51, −137)6(−132, 218)16(−7, 31)26(4, 238)36(163, −69)46(163, 149)56(93, −49)7(−109, 228)17(−15, 63)27(6, 258)37(74, 61)47(181, 180)57(1, 72)8(−87, 245)18(−26, 80)28(−75, −45)38(76, 134)48(130, 189)58(130, −189)9(−41, 88)19(1, 93)29(25, 313)39(98, 149)49(163, 199)59(52, 342)10(−48, 127)20(−12, 149)30(47, 52)40(70, 214)50(135, 254)60(135, −254)Table 3
Matched pairs (ni, nj) between Tables 1 and 2, where ni and nj are the serial numbers of points in Tables 1 and 2.
No.(ni, nj)No.(ni, nj)No.(ni, nj)No.(ni, nj)1(11, 11)11(26, 23)21(36, 39)31(22, 8)2(46, 13)12(39, 27)22(44, 40)32(12, 9)3(34, 14)13(27, 51)23(43, 43)33(3, 12)4(22, 15)14(45, 29)24(25, 53)34(4, 21)5(13, 16)15(10, 30)25(40, 45)35(19, 57)6(24, 17)16(20, 31)26(48, 46)36(16, 26)7(32, 18)17(33, 32)27(37, 47)37(5, 59)8(30, 19)18(50, 34)28(18, 1)38(9, 38)9(31, 20)19(41, 35)29(15, 5)39(1, 41)10(49, 22)20(17, 37)30(29, 6)40(6, 42)


## 4.2. Translation and Rotation Transform

The point setP used in Subsection 4.1 is also adopted here. We apply the translation and rotation transform with tx=7,ty=4, and θ=0.716 (radian) to the first 40 points of P and then obtain 40 points of Q. Next, we apply another transform of translation and rotation to the last 10 points of P and add the transformed points to Q. Moreover, another 10 points are added to Q. During generation, the distance between each two points is also not smaller than 10. Similarly, Gaussian noises with 0 mean and 1 variance is also exploited to perturb the points of Q. Table 4 are the coordinates of those points of Q. Our algorithm correctly determines 40 matched pairs of points, as shown in Table 5.Table 4
Coordinates of the points inQ under translation and rotation transform.
No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)No.(x,y)1(−72, 116)11(−30, 95)21(−4, 303)31(69, 75)41(107, 200)51(37, −206)2(−112, 145)12(−11, 123)22(15, 320)32(68, 154)42(94, 221)52(−94, −81)3(−53, 164)13(−35, 145)23(39, 57)33(57, 232)43(99, 283)53(9, −223)4(−117, 179)14(−12, 222)24(25, 69)34(59, 252)44(137, 140)54(13, −150)5(−76, 210)15(−40, 260)25(29, 90)35(80, 256)45(115, 145)55(101, −45)6(−128, 212)16(24, 27)26(26, 127)36(58, 279)46(152, 168)56(114, 186)7(−107, 228)17(−3, 32)27(−16, −98)37(95, 93)47(186, 184)57(86, −84)8(−67, 275)18(4, 140)28(52, 309)38(85, 113)48(150, −68)58(24, −126)9(−24, 59)19(−1, 170)29(31, 344)39(99, 132)49(165, 198)59(53, 141)10(−49, 74)20(−9, 197)30(54, 71)40(85, 180)50(147, 217)60(−47, −211)Table 5
Matched pairs (ni, nj) between Tables 1 and 4, where ni and nj are the serial numbers of points in Tables 1 and 4.
No.(ni, nj)No.(ni, nj)No.(ni, nj)No.(ni, nj)1(25, 1)11(13, 16)21(16, 33)31(6, 21)2(40, 2)12(26, 17)22(39, 34)32(19, 24)3(36, 3)13(50, 19)23(49, 35)33(5, 29)4(48, 4)14(41, 20)24(27, 36)34(32, 30)5(37, 6)15(43, 22)25(18, 37)35(4, 32)6(10, 9)16(24, 23)26(46, 41)36(11, 39)7(17, 10)17(30, 25)27(34, 42)37(3, 40)8(20, 11)18(31, 27)28(22, 43)38(29, 47)9(33, 12)19(45, 28)29(9, 13)39(15, 48)10(44, 14)20(12, 31)30(1, 15)40(23, 50)


## 4.3. Fingerprint Matching

To view the performance in a real-world situation, the proposed algorithm is applied to fingerprint recognition. Figure4 presents two fingerprint images taken from the same finger of a person. The circled feature points are manually selected and their coordinates are also manually extracted by using the software origin. In this experiment, the circled features represent those points for pattern matching and the total number of used features in each fingerprint image is 42. Our algorithm finds 35 matched pairs of features, indicating the practicability of the proposed algorithm. The results are as shown in Figure 5, where the “×” marks represent the feature points in Figure 4(a), the “+” marks represent the feature points in Figure 4(b), and the circle marks mean the matched pairs.Two different fingerprint images from the same finger with circled features.
(a)
A fingerprint image(b)
Another fingerprint imageFigure 5
Matched pairs between Figures4(a) and 4(b).


## 5. Conclusions

A novel point pattern matching algorithm is proposed in this paper, which views point pattern matching problem as complete graph matching. For each point, the proposed algorithm constructs its complete graph by using its neighbor points. Point pattern matching is then solved by finding congruent complete graphs between the point sets. The proposed algorithm is suitable for the point sets under Euclidean transform. Many experiments are done, and the results show that our algorithm is robust and effective. As finding a matched pair of points in advance is not needed, the proposed algorithm is not influenced by calculation errors causing in point pair determination, and, therefore, achieves robustness. Complete graphs are formed by those points in neighbor. It effectively reduces computational cost and improves speed.



---

*Source: 139014-2012-05-10.xml*