Objective

2

Graph matching involves establishing a one-to-one correspondence between the feature points of two images on the basis of graph theory. As a basic problem in computer vision

graph matching is closely related to many computer vision areas

such as object tracking

image classification

object recognition

contour matching

and so on. Existing graph matching algorithms are mostly applied to two-dimensional images

and many problems

such as low accuracy rate and slow calculation speed

remain in matching feature points from three-dimensional images. To solve these problems

this study generalized the factorized graph matching algorithm to three-dimensional images.

Method

2

The three-dimensional graph matching method comprises five main steps. In the first step

the feature points of the two three-dimensional images that must be matched are used as the node set of the graph. Then

the three-dimensional feature points are connected by the Delaunay triangulation algorithm

and the obtained edges are used as the edge sets of the graph to establish the directed graph. In the second step

the starting node matrix is computed on the basis of the structure of the directed graph

and each element with a value of 1 represents the starting node of the edge in the graph. The ending node matrix can be computed in the same manner. The starting node matrix and the ending node matrix can be combined to represent which node of each edge in the graph is initiated and which node is terminated. In the third step

we use the graph's degree and eccentricity as the node's feature to build node feature vectors. We also use the edge length and the angle between the edge and

the plane

XOY

as the edge's feature to build edge feature vectors. The node feature adjacency matrix can be calculated according to the node feature vectors. The number of matrix rows is equal to the number of one graph's nodes. The number of matrix columns is equal to the number of the other graph's nodes. The value of each element in the matrix can be calculated on the basis of the Euclidean distance between corresponding nodes from the two graphs and represents the degree of similarity between two nodes in the graphs. Similarly

the edge feature adjacency matrix can be calculated on the basis of edge feature vectors. The node feature adjacency matrix and edge feature adjacency matrix can be used to delineate the degree of similarity between nodes and edges from two graphs. In the fourth step

using the starting node matrix

ending node matrix

node feature adjacency matrix

and edge feature adjacency matrix

we can build a special matrix

K

to transform the three-dimensional graph matching problem into a problem of solving a node matching matrix

X

to maximize an equation

J

. In the fifth step

the maximum value solution of equation

J

is a quadratic assignment Problem; therefore

we use the path following algorithm to obtain the optimal solution by splitting the equation

J

into a series of concave and convex expressions and then find the optimal solution

X

by iterative approximation. The solution matrix

X

is the node matching matrix and represents the feature point matching result from two three-dimensional images.

Result

2

We tested and validated our method in five experiments. In the first experiment

we manually picked 102 feature points from a three-dimensional image in the dataset that comprised nine three-dimensional car images and had a 97.56% average accuracy rate in feature point matching from the same three-dimensional images. In the second experiment

we achieved a 76.39% average accuracy rate from the feature point matching from different three-dimensional images from the dataset. In the third experiment

we rotated the three-dimensional images every 10° from 10° to 180° and matched all 102 manually selected feature points from the same three-dimensional images; the average accuracy rate of matching was 90%. In the fourth experiment

we randomly removed several feature points from the three-dimensional images. During the removal

the accuracy rate of matching decreased. Nevertheless

removing a maximum of 30 feature points still yielded an 80% accuracy rate of matching. In the first four experiments

we used the manually selected feature points from the three-dimensional images; furthermore

we validated our method on the feature points automatically obtained by the 3D scale-invariant feature transform (SIFT) algorithm and achieved a 98.78% average accuracy rate in the feature point matching of the three-dimensional images.

Conclusion

2

The three-dimensional image feature point matching algorithm based on graph theory proposed in this work was tested and validated by five experiments. Results indicate that our method can achieve good matching results for manually selected feature points and automatically calculated feature points.