On Image Matching and Feature Tracking for Embedded Systems: A State-of-the-Art - Advances in Heuristic Signal Processing and Applications - page 359

It follows that the given image region has a high saliency if v( 1 ) contains a signifi-
cant amount of information about the feature vector of the matching image region.
A match to the given image region can be selected using a log likelihood ratio. In de-
tail, let v( 2 , 1 ),...,v( 2 ,N) be a set of vectors obtained from N candidate matches
to the given image region. The best match v( 2 ,j) is defined such that:

v( 1 ),B . (16.3)
Experiments with stereo images show that the accuracy of matching based on the
above log likelihood ratio is similar to the accuracy of matching based on the sum
of absolute differences of pixel values.
The iterative closest point (ICP) algorithm [ 9 , 19 ] is one of the most popular
recent algorithms for 3D point matching. The algorithm makes an iterative search
for the best 3D transform which links two sets of 3D features, for example, points,
curves, or surfaces. Each iteration has two steps, namely feature matching and 3D
transform estimation. The list of the matched points found in the current iteration is
used as input for the next iteration. The algorithm finishes when the distance error
between the matched points is less than a predefined threshold. The choice of an
initial 3D transform is difficult because it must be accurate enough to ensure that
the algorithm does not yield a locally optimal solution which is not globally opti-
mal. Several improvements have been proposed. Weik [ 96 ] restricts ICP to points
at which there is a large luminosity gradient. Masuda et al. [ 60 ] select at each itera-
tion a random subset of points with few outliers. Rusinkiewicz and Levoy [ 80 ]have
investigated the relationship between the convergence of the ICP and spatial distri-
bution of the mesh points. They showed that the random subset should be replaced
by the normal-space sampling in order to obtain high precision real time algorithm
(recall: in normal-space sampling points are chosen such that the distribution of
normals among the selected points is as large as possible).

ln p v( 2 ,i) v( 1 ),H /p v( 2 ,i)

= → | |

j argmax i

16.2.4 Hardware Systems for Image Matching

Several “universal” hardware systems exist for efficient image processing and anal-
ysis. Three systems which efficiently support graph-based processing are presented.
These are the μ DP circuit for DP matching, the Sphinx pyramid for multiresolution
processing, and the MAO for image processing and vision graph operations.
The μ DP circuit (Fig. 16.6 , left) simulates in hardware the local path parallel
development (Fig. 16.6 , right) when comparing two vectors. μ DPisa2Dmeshof
N × N elementary processors (PE ij ) each evaluating the local cost of matching two
selected features. In order to be able to develop paths in three possible directions,
two orthogonal and one diagonal, for the global matching of a line, each PE is 3-
connected to its east, south, and south-east neighbors.
Suppose that it is required to match two vectors U, V. The calculations of all
distances d ij =|

between any two components can be performed in paral-
lel, leading to a reduction of the sequential complexity of the matching algorithm

U i − V j |