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

Fig. 16.12 NTSS for image matching with sparse convolution step

Fig. 16.13 Convolution
principle for diamond search
algorithm: the search is
centered respectively on
black, east-red, north-east
yellow and north green pixels

where the correlation is calculated. At initialization, the correlation step is 2 pixels
( S 5 window. If the

maximum correlation is obtained at the central pixel, then S is set equal to 1 and the
appropriate correlations are calculated. If the maximum correlation is attained at a
pixel other than the central pixel, then this other pixel is made a new central pixel
and the calculation is repeated with S =

= 2), and the correlation is calculated at nine points in a 5 ×

2.
The constant number of steps of this algorithm is a very attractive characteris-
tic; however, it often fails to find the correct match. Moreover, all search algorithms
based on squares of pixels assume that the displacement vectors are distributed uni-
formly around the search center. The algorithm proposed by [ 102 ], namely diamond
search (DS), replaces the squares used by 4SS with diamonds (Fig. 16.13 ) and pro-
ceeds iteratively until the best match is obtained. The expected number of correla-
tions is reduced significantly. The new cross-diamond search (NCDS) [ 39 ]usesan
asymmetric (horizontal or vertical) diamond search pattern in order to overcome the
restrictions on the displacement imposed by search algorithms based on squares and
find the best match.
Information from additional sensors, such as an Inertial Measurement Unit (IMU)
can be used to guide the selection of matching pairs of pixels. Indeed, as the physi-
cal displacements of 3D scene interest points are limited in size from one image to
the next, the integration of data provided by IMU to a recursive position estimator
allows the prediction of the maximum displacement of scene points relative to the
camera, and the estimation of their projected positions in the image. In this way, the
size of the search window for potential matches can be reduced and the matching
process can be speeded up. This principle is proposed in [ 23 ], and evaluated on real