# Differential and Statistical Approach to Partial Model Matching

Authors: Kehua Guo; Yongling Liu; Guihua Duan
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Partial model matching approaches are important to target recognition. In this paper, aiming at a 3D model, a novel solution utilizing Gaussian curvature and mean curvature to represent the inherent structure of a spatial shape is proposed. Firstly, a Point-Pair Set is constructed by means of filtrating points with a similar inherent characteristic in the partial surface. Secondly, a Triangle-Pair Set is demonstrated after locating the spatial model by asymmetry triangle skeleton. Finally, after searching similar triangles in a Point-Pair Set, optimal transformation is obtained by computing the scoring function in a Triangle-Pair Set, and optimal matching is determined. Experiments show that this algorithm is suitable for partial model matching. Encouraging matching efficiency, speed, and running time complexity to irregular models are indicated in the study.


---

## Body

## 1. Introduction

Partial model matching has important applications in many cases such as the vision registration for automatic 3D models [1–3], content-based image retrieval from image database [4], assembly and restoration for fractured object [5], docking of proteins in molecular biology [6], and other applications. During the past decade, the problem of finding a partial match between models attracted considerable attention. In many cases, models may be only partially visible because the occlusion or the sensor usually cannot scan all the data, so the goal of partial model matching is to find a transformation of the sample model to overlap a large portion of the object model.This paper focuses on the research of a 3D partial model matching. In 3D space, the models can be represented as 3D surfaces. Therefore, finding a Euclidean geometry rigid transformation of the sample surface to overlap a large portion of the object surface is the goal of 3D partial model matching. In recent years, there has been lots of research on 3D partial surface matching. The literature [7, 8] proposed a scoring schema for 3D partial surface matching, but this paper did not demonstrate a universal and high-efficiency algorithm for the constructing of a scoring factor. The literature [9] proposed an approach based on the Hausdorff and Frehet distance for geometry structure matching. This approach can be well applied in the matching of points and line segments set, but it is unstable and cannot perform well in the presence of noise, occlusion, and clutter. The literature [10] proposed a scoring schema for matching algorithm to a 3D incomplete object. The literature [11–13] proposed some matching algorithm using differential geometry to 3D partial surface matching. In addition, statistical descriptors [14], probabilistic framework [15], and curve analysis [16] were also applied to the recognition of 3D partial surface; these approaches indicated encouraging matching results for 3D points, line segments set, and mesh model; however, they would suffer from high computing complexity. It is worth mentioning that partial model matching has been successfully applied in video processing [17, 18].Our work is motivated by the technique of scoring schema and statistical approaches. This technique, which uses the so-called scoring-function method, was originally introduced for 3D partial surface and volumetric matching. This idea has been applied in some pattern recognition problem [19] and achieved good results. The work proposed in this paper has been partly published in an international conference [20]. Here is a brief sketch of our algorithm.(1)
Represent the inherent characteristic of points in sample and object surface utilizing differential geometry method.(2)
Classify point pair with a similar inherent characteristic form sample and object surface.(3)
Classify triangle pair with a similar shape feature and inherent characteristic based on point pairs and compute the geometry rigid transformation for every triangle pair.(4)
Use scoring function to measure the goodness of every transformation through applying it to other triangle pairs.(5)
Determine the optimal transformation with score of every transformation.Experimental results show that our technique is most successful for the matching of irregular object surface. Encouraging matching efficiency, speed, and running time complexity to irregular models are indicated.


## 2. Compute and Store the Curvature

### 2.1. Represent the Spatial Surface Using Gaussian and Mean Curvature

According to differential geometry principle, curvature is the inherent characteristic of a spatial surface. Therefore, Gaussian curvature and mean curvature are employed for the representation of spatial surface in this paper.In 3D Euclidean space, given a parametric surface defined as(1)S(x,y)=[xyf(x,y)]T,(x,y)∈D,
where X-Y is the reference plane in 3D space, D is projection region of the surface to X-Y plane, and f(x,y) represents the distance from the surface to point (x,y) in X-Y plane.Gaussian curvatureK and mean curvature H can be computed according to the following formulas [18]:
(2)K=fxxfyy-fxy2(1+fx2+fy2)2,H=(1+fx2)fyy+(1+fy2)fxx-2fxfyfxy2(1+fx2+fy2)3/2.For a digital range image surface, approximations can be computed by a local polynomial fitting approach, andn×n operator is usually utilized to the convolution operation with the original range image:
(3)fx=Dx*f,fy=Dy*ffxx=Dxx*f,fxy=Dxy*f,fyy=Dyy*f,
where D is n×n operator. For n=7, the parameters can be computed as follows:
(4)Dx=d0d1T,Dy=d1d0T,Dxx=d0d2T,Dyy=d2d0T,Dxy=d1d1Td0=17[1111111]Td1=128[-3-2-10123]Td2=184[50-3-4-305]T,
where d0, d1, and d2 are column vectors for window operator computing.


### 2.2. Generate the Point-Pair Set

After presenting the acquisition of Gaussian curvatureK and mean curvature H, in our algorithm, point pairs with similar curvature from sample and object surface will be classified, and then the point pairs will be stored into a Point-Pair Set. In order to measure the similarity between two points from sample and object surface, the definition of curvature distance is introduced as follows:Definition 1.
∀
p
i
1
∈
S
1
,
p
j
2
∈
S
2, curvature distance DC between point pi1,pj2 is
(5)DC(pi1,pj2)=12×(|K(pi1)-K(pj2)||K(pi1)|+|K(pj2)|+|H(pi1)-H(pj2)||H(pi1)|+|H(pj2)|).
However, in many cases, a lot of plane points, whose Gaussian curvature and mean curvature are zero, can exist in the surface. They cannot contribute to the matching but will occupy large computing and reduce the matching efficiency, even lead to an error matching. So that these plane points will be discarded before matching.Definition 2.
A Point-Pair Set named PS is a set defined as(6)PS={(pi1,pj2)∣pi1∈S1,pj2∈S2,DC(pi1,pj2)〈εc,|K(pi1)|〉σ}εc=max(DC(pi1,pj2))+min(DC(pi1,pj2))2σ=1n(∑i=1n|K(pi1)|).
Where εc is an average threshold to guarantee the similarity of pi1 and pj2, σ is to discard plane points, and N is the number of the points.
The cardinality of PS could be large in special cases. For instance, cardinality of PS will be|S1|×|S2| when the sample and object surface are congruent sphere surface. A large Point-Pair Set will occupy a large amount of the storage space. Considering the quantity of curvature categories cannot exceed the quantity of pixel points in surface, a list can be employed to store the set.


## 2.1. Represent the Spatial Surface Using Gaussian and Mean Curvature

According to differential geometry principle, curvature is the inherent characteristic of a spatial surface. Therefore, Gaussian curvature and mean curvature are employed for the representation of spatial surface in this paper.In 3D Euclidean space, given a parametric surface defined as(1)S(x,y)=[xyf(x,y)]T,(x,y)∈D,
where X-Y is the reference plane in 3D space, D is projection region of the surface to X-Y plane, and f(x,y) represents the distance from the surface to point (x,y) in X-Y plane.Gaussian curvatureK and mean curvature H can be computed according to the following formulas [18]:
(2)K=fxxfyy-fxy2(1+fx2+fy2)2,H=(1+fx2)fyy+(1+fy2)fxx-2fxfyfxy2(1+fx2+fy2)3/2.For a digital range image surface, approximations can be computed by a local polynomial fitting approach, andn×n operator is usually utilized to the convolution operation with the original range image:
(3)fx=Dx*f,fy=Dy*ffxx=Dxx*f,fxy=Dxy*f,fyy=Dyy*f,
where D is n×n operator. For n=7, the parameters can be computed as follows:
(4)Dx=d0d1T,Dy=d1d0T,Dxx=d0d2T,Dyy=d2d0T,Dxy=d1d1Td0=17[1111111]Td1=128[-3-2-10123]Td2=184[50-3-4-305]T,
where d0, d1, and d2 are column vectors for window operator computing.


## 2.2. Generate the Point-Pair Set

After presenting the acquisition of Gaussian curvatureK and mean curvature H, in our algorithm, point pairs with similar curvature from sample and object surface will be classified, and then the point pairs will be stored into a Point-Pair Set. In order to measure the similarity between two points from sample and object surface, the definition of curvature distance is introduced as follows:Definition 1.
∀
p
i
1
∈
S
1
,
p
j
2
∈
S
2, curvature distance DC between point pi1,pj2 is
(5)DC(pi1,pj2)=12×(|K(pi1)-K(pj2)||K(pi1)|+|K(pj2)|+|H(pi1)-H(pj2)||H(pi1)|+|H(pj2)|).
However, in many cases, a lot of plane points, whose Gaussian curvature and mean curvature are zero, can exist in the surface. They cannot contribute to the matching but will occupy large computing and reduce the matching efficiency, even lead to an error matching. So that these plane points will be discarded before matching.Definition 2.
A Point-Pair Set named PS is a set defined as(6)PS={(pi1,pj2)∣pi1∈S1,pj2∈S2,DC(pi1,pj2)〈εc,|K(pi1)|〉σ}εc=max(DC(pi1,pj2))+min(DC(pi1,pj2))2σ=1n(∑i=1n|K(pi1)|).
Where εc is an average threshold to guarantee the similarity of pi1 and pj2, σ is to discard plane points, and N is the number of the points.
The cardinality of PS could be large in special cases. For instance, cardinality of PS will be|S1|×|S2| when the sample and object surface are congruent sphere surface. A large Point-Pair Set will occupy a large amount of the storage space. Considering the quantity of curvature categories cannot exceed the quantity of pixel points in surface, a list can be employed to store the set.


## 3. Match Algorithm

### 3.1. Measure Similarity for Spatial Triangles

In order to perform the matching, the further work is to separately seek two asymmetrical triangles with similar shape features from the sample and object surface, and then we will design a set named “Triangle-Pair Set” to store these triangle pairs. A plane can be determined by three spatial points, so the asymmetrical triangle can be employed as the skeleton to uniquely confirm the location of a spatial surface. Therefore, we arbitrarily select three points from the object surface to form an asymmetrical triangle and then seek three corresponding points from sample surface to form another asymmetrical triangle, whose features of corresponding vertices and edges are similar to the previous triangle. The similarity of space triangles is measured by the definition as follows.Definition 3.
Consider∀(p11,p12),(p11,p12),(p11,p12)∈PS, |p1mp2m|<|p1mp3m|<|p2mp3m|, m∈{1,2}. The similar distance between Δp11p21p31 and Δp12p22p32 is
(7)DT=13×∑1≤i<j≤3||pi1pj1|-|pi2pj2|||pi1pj1|+|pi2pj2|.
The absolute distance betweenΔp11p21p31 and Δp12p22p32 is
(8)DA=2×∑i=13|pi1pi2|∑1≤i<j≤33(|pi1pj1|+|pi2pj2|).


### 3.2. Compute Geometry Rigid Transformation

Suppose thatΔp11p21p31 and Δp12p22p32 are two similar asymmetrical triangles, (pi1,pi2),andi∈{1,2,3} are corresponding points, we represent the transformation T between Δp11p21p31 and Δp12p22p32 into a translation transformation N and a rotation transformation A:
(9)T(Δp1p2p3)=A[p1p2p3]+N,
where A=(n1n2n3)T is a rotation matrix and N is a translation matrix.We firstly shift the triangle centers to the origin of coordinate, so the transformationT satisfies
(10)⌊p12p22p32⌋-N2=A(⌊p11p21p31⌋-N1),
where N1, N2 is the center location matrix of Δp11p21p31 and Δp12p22p32.Therefore, rotation matrix can be deduced as in the following formula:(11)A=(⌊p12p22p32⌋-N2)(⌊p11p21p31⌋-N1)-1.


### 3.3. Generate Triangle-Pair Set

Similar triangle pairs from two surfaces will be stored in Triangle-Pair Set defined as follows:Definition 4.
A Triangle-Pair Set named TS is a set(12)TS={(Δp11p21p31,Δp12p22p32,T)∣(pi1pi2)∈PS,DT<εt}εt=max(DT)+min(DT)2,
where εt is an average threshold to guarantee the similarity of Δp11p21p31 and Δp12p22p32. T is the transformation from Δp12p22p32 to Δp11p21p31. So we can design the logic structure of Triangle-Pair Set as Figure 1.Figure 1
Logic structure of the Triangle-Pair Set.


### 3.4. Determine Optimal Transformation

The validity of every transformation will be tested through applying it to every other triangle pair in TS. For a specified transformationT0 in PS, we define the scoring function as follows:
(13)Score(T0)=∑S(Δp11p21p31,p12p22p32,T0).Consider(Δp11p21p31,Δp12p22p32) is an arbitrary similar triangle pair in PS, and function S is defined as follows:
(14)S(Δp11p21p31,Δp12p22p32,T0)εa={1DA(T0(Δp11p21p31),Δp12p22p32)<εa0othersεa=max(DA)+min(DA)2,
where εa is an average threshold to determine whether Δp11p21p31 can be transformed to Δp12p22p32 by T0. An optimal transformation TP is the transformation with maximum score satisfying
(15)Score(TP)=max(Score(T)),
where T is an arbitrary transformation in TS.


## 3.1. Measure Similarity for Spatial Triangles

In order to perform the matching, the further work is to separately seek two asymmetrical triangles with similar shape features from the sample and object surface, and then we will design a set named “Triangle-Pair Set” to store these triangle pairs. A plane can be determined by three spatial points, so the asymmetrical triangle can be employed as the skeleton to uniquely confirm the location of a spatial surface. Therefore, we arbitrarily select three points from the object surface to form an asymmetrical triangle and then seek three corresponding points from sample surface to form another asymmetrical triangle, whose features of corresponding vertices and edges are similar to the previous triangle. The similarity of space triangles is measured by the definition as follows.Definition 3.
Consider∀(p11,p12),(p11,p12),(p11,p12)∈PS, |p1mp2m|<|p1mp3m|<|p2mp3m|, m∈{1,2}. The similar distance between Δp11p21p31 and Δp12p22p32 is
(7)DT=13×∑1≤i<j≤3||pi1pj1|-|pi2pj2|||pi1pj1|+|pi2pj2|.
The absolute distance betweenΔp11p21p31 and Δp12p22p32 is
(8)DA=2×∑i=13|pi1pi2|∑1≤i<j≤33(|pi1pj1|+|pi2pj2|).


## 3.2. Compute Geometry Rigid Transformation

Suppose thatΔp11p21p31 and Δp12p22p32 are two similar asymmetrical triangles, (pi1,pi2),andi∈{1,2,3} are corresponding points, we represent the transformation T between Δp11p21p31 and Δp12p22p32 into a translation transformation N and a rotation transformation A:
(9)T(Δp1p2p3)=A[p1p2p3]+N,
where A=(n1n2n3)T is a rotation matrix and N is a translation matrix.We firstly shift the triangle centers to the origin of coordinate, so the transformationT satisfies
(10)⌊p12p22p32⌋-N2=A(⌊p11p21p31⌋-N1),
where N1, N2 is the center location matrix of Δp11p21p31 and Δp12p22p32.Therefore, rotation matrix can be deduced as in the following formula:(11)A=(⌊p12p22p32⌋-N2)(⌊p11p21p31⌋-N1)-1.


## 3.3. Generate Triangle-Pair Set

Similar triangle pairs from two surfaces will be stored in Triangle-Pair Set defined as follows:Definition 4.
A Triangle-Pair Set named TS is a set(12)TS={(Δp11p21p31,Δp12p22p32,T)∣(pi1pi2)∈PS,DT<εt}εt=max(DT)+min(DT)2,
where εt is an average threshold to guarantee the similarity of Δp11p21p31 and Δp12p22p32. T is the transformation from Δp12p22p32 to Δp11p21p31. So we can design the logic structure of Triangle-Pair Set as Figure 1.Figure 1
Logic structure of the Triangle-Pair Set.


## 3.4. Determine Optimal Transformation

The validity of every transformation will be tested through applying it to every other triangle pair in TS. For a specified transformationT0 in PS, we define the scoring function as follows:
(13)Score(T0)=∑S(Δp11p21p31,p12p22p32,T0).Consider(Δp11p21p31,Δp12p22p32) is an arbitrary similar triangle pair in PS, and function S is defined as follows:
(14)S(Δp11p21p31,Δp12p22p32,T0)εa={1DA(T0(Δp11p21p31),Δp12p22p32)<εa0othersεa=max(DA)+min(DA)2,
where εa is an average threshold to determine whether Δp11p21p31 can be transformed to Δp12p22p32 by T0. An optimal transformation TP is the transformation with maximum score satisfying
(15)Score(TP)=max(Score(T)),
where T is an arbitrary transformation in TS.


## 4. Experimental Results and Complexity Analysis

### 4.1. Detect  Partially Occluded Object

The goal of the first experiment is to detect the partially occluded object from a range image using the algorithm proposed in this paper. The image data is established referred to [21].In Figures2(a) and 2(b), two original objects (Duck and Venusm) in 3D space are demonstrated, and the surface is formed by pixel points.Two 3D original and partially occluded models.
(a)
Original object
(b)
3D model of original object
(c)
Duck is partially occluded
(d)
3D model of the sceneIn Figure2(c), the Duck is partially occluded by the Venusm. In order to find the location of the occluded object (Duck) in the 3D scene, we must compute an optimal transformation from the scene to the occluded object, then apply the transformation to the occluded object and reconstruct it in the 3D scene in Figure 2(d).In this experimentation, the computing results are demonstrated in Table1.Table 1
Parameters and computing results.
Pixel point quantity
Duck: 9253
Venusm: 27595
Triangle pair for optimal transformation
p
1
1
(
125,23
,
-
15
)
p
2
1
(
72,4
,
-
10
)
p
3
1
(
68
,
-
71
,
-
23
)
p
1
2
(
132,5
,
98
)
p
2
2
(
83
,
-
18,108
)
p
3
2
(
76
,
-
89,82
)
Transformation
A
=
[
1.2984
-
0.6040
-
0.6944
-
0.6401
1.2802
-
0.6401
-
0.6583
-
0.6763
1.3345
]Optimal triangle in original object is demonstrated in Figure3(a), and the optimal triangle in occluded object is illustrated in Figure 3(b). According to the result in Table 1, we apply the transformation to original object. The reconstruction result is shown in Figure 3(c).Detect  partially occluded object.
(a)
Optimal triangle in original object
(b)
Optimal triangle in occluded object
(c)
Reconstruction result to occluded object


### 4.2. Partial Surface Matching for Two Similar Objects

The second experimentation demonstrates our algorithm applied in a universal case. The two surfaces are partially similar, and the goal is to find a transformation to match the most similar part of the two surfaces.The two surfaces with missing data in Figures4(a) and 4(b) are generated by a Matlab function. In order to match the most similar part of the two surfaces, an optimal transformation from surface 1 to surface 2 needs to be computed.Two partially similar surfaces.
(a)
Surface 1
(b)
Surface 2The computing results in this experimentation are demonstrated in Table2.Table 2
Parameters and computing result.
Pixel point quantity
Object 1: 1215
Object 2: 1452
Triangle pair for optimal transformation
p
1
1
(
10
,
-
5,87
)
p
2
1
(
8
,
-
21,42
)
p
3
1
(
29
,
-
17,32
)
p
1
2
(
12
,
-
69,18
)
p
2
2
(
25
,
-
31,32
)
p
3
2
(
92
,
-
43,28
)
Transformation
A
=
[
0.1028
1.7571
-
1.8599
-
0.2024
1.1216
-
0.9191
0.0996
-
2.8787
2.7791
]Optimal triangle in surface 1 is demonstrated in Figure5(a), and the optimal triangle in surface 2 is illustrated in Figure 5(b). According to the results shown in Table 2, the transformation is applied to surface 1 and the matching and reconstruction result is demonstrated in Figure 5(c).Partial surface matching of two similar surfaces.
(a)
Optimal triangle in surface 1
(b)
Optimal triangle in surface 2
(c)
Matching and reconstruction result


### 4.3. Complexity Analysis

Suppose that the two input sets have comparable sizes, we measure the computing complexity of the algorithm as a function ofN (the cardinality of the input sets); k is the size of Point-Pair Set. Computing the curvature of every point takes O(N) time. Preparing the Point-Pair Set can be executed with expected O(NlogN) running time because we can sort the points based on curvature. In addition, seeking triangle pairs, computing and testing transformation based on Point-Pair Set will cost O(k3) running time. In total, the running time of the whole algorithm is O(N+NlogN+k3).Obviously, the computing efficiency is mainly determined by the size of Point-Pair Setk. The quantity of point pairs will be smaller when the surface processes many different curvatures; in this case, our algorithm will cost less time at this time. So our algorithm is very suitable for the matching of irregular objects.In order to explicitly describe the performance of our algorithm, we perform experimentations for objects with different shapes. Running times of some algorithms forN=900 are demonstrated in Table 3 (CPU: PIV2.0 GHZ, RAM: 1 GB, Software: MATLAB 7.0).Table 3
Performance comparison of some algorithms.
Algorithm
Running time (ms)
Sphere surface
Surface in Figure3
Algorithm in this paper
2635
758
Algorithm in [9]
1932
2575
Algorithm in [10]
2956
3548
Algorithm in [11]
1562
1652
Algorithm in [14]
1457
1238
Algorithm in [16]
3187
4572We can see from Table3 that our algorithm cannot indicate an encouraging matching efficiency for regular objects such as sphere surfaces.


### 4.4. Noise Robustness

The proposed work depends crucially on the Gaussian curvature and means curvature computation, which is notoriously sensitive to noise and local perturbation. In order to analyze the affection of noise to the match results, we perform an experimentation to verify the noise robustness of this algorithm. In this experimentation, we generate 100 similar surfaces by Matlab function, and Gaussian noise(N(0,σ)) is added to each image in the database and σ changes from 0 mm to 2.0 mm. We design the classification rate to represent the percentage of correct matching quantity in the database; the classification rates are shown in Figure 6 for various σ values.Figure 6
Classification rate when Gaussian noise increases.The result shows that the algorithm in this paper does not have good noisy robustness. At present, our approach can get encouraging matching efficiency and running time complexity in case of high signal to noise ratio. Therefore, the future work will concentrate on this problem.


## 4.1. Detect  Partially Occluded Object

The goal of the first experiment is to detect the partially occluded object from a range image using the algorithm proposed in this paper. The image data is established referred to [21].In Figures2(a) and 2(b), two original objects (Duck and Venusm) in 3D space are demonstrated, and the surface is formed by pixel points.Two 3D original and partially occluded models.
(a)
Original object
(b)
3D model of original object
(c)
Duck is partially occluded
(d)
3D model of the sceneIn Figure2(c), the Duck is partially occluded by the Venusm. In order to find the location of the occluded object (Duck) in the 3D scene, we must compute an optimal transformation from the scene to the occluded object, then apply the transformation to the occluded object and reconstruct it in the 3D scene in Figure 2(d).In this experimentation, the computing results are demonstrated in Table1.Table 1
Parameters and computing results.
Pixel point quantity
Duck: 9253
Venusm: 27595
Triangle pair for optimal transformation
p
1
1
(
125,23
,
-
15
)
p
2
1
(
72,4
,
-
10
)
p
3
1
(
68
,
-
71
,
-
23
)
p
1
2
(
132,5
,
98
)
p
2
2
(
83
,
-
18,108
)
p
3
2
(
76
,
-
89,82
)
Transformation
A
=
[
1.2984
-
0.6040
-
0.6944
-
0.6401
1.2802
-
0.6401
-
0.6583
-
0.6763
1.3345
]Optimal triangle in original object is demonstrated in Figure3(a), and the optimal triangle in occluded object is illustrated in Figure 3(b). According to the result in Table 1, we apply the transformation to original object. The reconstruction result is shown in Figure 3(c).Detect  partially occluded object.
(a)
Optimal triangle in original object
(b)
Optimal triangle in occluded object
(c)
Reconstruction result to occluded object


## 4.2. Partial Surface Matching for Two Similar Objects

The second experimentation demonstrates our algorithm applied in a universal case. The two surfaces are partially similar, and the goal is to find a transformation to match the most similar part of the two surfaces.The two surfaces with missing data in Figures4(a) and 4(b) are generated by a Matlab function. In order to match the most similar part of the two surfaces, an optimal transformation from surface 1 to surface 2 needs to be computed.Two partially similar surfaces.
(a)
Surface 1
(b)
Surface 2The computing results in this experimentation are demonstrated in Table2.Table 2
Parameters and computing result.
Pixel point quantity
Object 1: 1215
Object 2: 1452
Triangle pair for optimal transformation
p
1
1
(
10
,
-
5,87
)
p
2
1
(
8
,
-
21,42
)
p
3
1
(
29
,
-
17,32
)
p
1
2
(
12
,
-
69,18
)
p
2
2
(
25
,
-
31,32
)
p
3
2
(
92
,
-
43,28
)
Transformation
A
=
[
0.1028
1.7571
-
1.8599
-
0.2024
1.1216
-
0.9191
0.0996
-
2.8787
2.7791
]Optimal triangle in surface 1 is demonstrated in Figure5(a), and the optimal triangle in surface 2 is illustrated in Figure 5(b). According to the results shown in Table 2, the transformation is applied to surface 1 and the matching and reconstruction result is demonstrated in Figure 5(c).Partial surface matching of two similar surfaces.
(a)
Optimal triangle in surface 1
(b)
Optimal triangle in surface 2
(c)
Matching and reconstruction result


## 4.3. Complexity Analysis

Suppose that the two input sets have comparable sizes, we measure the computing complexity of the algorithm as a function ofN (the cardinality of the input sets); k is the size of Point-Pair Set. Computing the curvature of every point takes O(N) time. Preparing the Point-Pair Set can be executed with expected O(NlogN) running time because we can sort the points based on curvature. In addition, seeking triangle pairs, computing and testing transformation based on Point-Pair Set will cost O(k3) running time. In total, the running time of the whole algorithm is O(N+NlogN+k3).Obviously, the computing efficiency is mainly determined by the size of Point-Pair Setk. The quantity of point pairs will be smaller when the surface processes many different curvatures; in this case, our algorithm will cost less time at this time. So our algorithm is very suitable for the matching of irregular objects.In order to explicitly describe the performance of our algorithm, we perform experimentations for objects with different shapes. Running times of some algorithms forN=900 are demonstrated in Table 3 (CPU: PIV2.0 GHZ, RAM: 1 GB, Software: MATLAB 7.0).Table 3
Performance comparison of some algorithms.
Algorithm
Running time (ms)
Sphere surface
Surface in Figure3
Algorithm in this paper
2635
758
Algorithm in [9]
1932
2575
Algorithm in [10]
2956
3548
Algorithm in [11]
1562
1652
Algorithm in [14]
1457
1238
Algorithm in [16]
3187
4572We can see from Table3 that our algorithm cannot indicate an encouraging matching efficiency for regular objects such as sphere surfaces.


## 4.4. Noise Robustness

The proposed work depends crucially on the Gaussian curvature and means curvature computation, which is notoriously sensitive to noise and local perturbation. In order to analyze the affection of noise to the match results, we perform an experimentation to verify the noise robustness of this algorithm. In this experimentation, we generate 100 similar surfaces by Matlab function, and Gaussian noise(N(0,σ)) is added to each image in the database and σ changes from 0 mm to 2.0 mm. We design the classification rate to represent the percentage of correct matching quantity in the database; the classification rates are shown in Figure 6 for various σ values.Figure 6
Classification rate when Gaussian noise increases.The result shows that the algorithm in this paper does not have good noisy robustness. At present, our approach can get encouraging matching efficiency and running time complexity in case of high signal to noise ratio. Therefore, the future work will concentrate on this problem.


## 5. Conclusion

In this paper, an approach for solving the 3D partial model matching is proposed. Firstly we utilize Gaussian curvature and mean curvature to represent the two object surfaces. Then curvature distance is defined to classify the point pair with similar curvature, and Point-Pair Set is employed to store point pairs. Secondly, we classify triangle pair with similar shape features from the two surfaces based on Point-Pair Set, similar distance is employed to measure the similarity of two triangles, and then the Triangle-Pair Set is generated. Finally, absolute distance and score function are proposed for measuring the goodness of a given transformation in Triangle-Pair Set, and a successful matching is determined based on the score of optimal transformation between the objects. Experimental results indicated our algorithm can be suitable for the matching of natural objects.However, the efficiency of this approach would be reduced when the shape is regular and the robustness to noise is not very good. In future work, we will plan to explore several improvements of the algorithm, including the improvement of noise robustness, design of better distance definition, experimentation with other scoring functions, and further study of statistical approaches.



---

*Source: 249847-2013-02-03.xml*