The objective of the optimised robust correlation is to find the global
extremum in a multi-dimensional search space that corresponds to the
best match between a pair of images. This search space is defined by the
set of all valid geometric and photometric transformations. In our
implementation of the proposed method the geometric transformations are
translation, scaling and rotation
. Given a point in the multi-dimensional search space, a combined score
function is evaluated. This function and some of its properties are
described in Section
2.1
. To find the global optimum of the score function a search technique
based on random exponential perturbations is employed. This optimisation
method, which was shown to be particularly suitable for the given search
problem (see Section
3
), is discussed in Section
2.2
. Finally in Section
2.3
, a quasi-random sampling technique used for estimating the value of the
score function is outlined.
Given a transformation
t
, a match score
s
is computed as a weighted sum of two scores, an area score
and a grey level score
:
where
denotes a constant in the interval [0,1]
. The area score is included to encourage large overlaps and is defined
as
where
and
denote the sampling sets corresponding to the reference and test images,
and
, respectively. The derivation of this function is based on
probabilistic arguments [
8
]. The grey level score, which measures the similarity between the
intensity distributions, is defined as
where
denotes the robust kernel,
the intensity transformation,
the projection function and
the maximum response of the robust kernel. The kernel function
used in the experiments reported in Section
3
is a simple quadratic function and is defined as
where
and
denote the compared grey levels and
the cut-off distance. The latter defines the width of the kernel and
grey level differences greater than this constant will not contribute to
the final score. The intensity transformation
implements a linear mapping between grey levels in the reference and
test images. It is defined as
where
g
denotes a grey level. Pixels are projected from the reference image to
the test image using an affine projection function
where
p
denotes the pixel to be projected and
the result of the projection. The horizontal and vertical coordinates of
the projection are defined as
where
denotes the centre of gravity computed from the sampling set.
The search technique we employ is based on random exponential perturbations (see Algorithm 1 ). In each iteration, the transformation between reference and test image is perturbed by adding a random vector drawn from an exponential distribution. The new transformation is accepted only if the score was increased.
The approach described above is similar to simulated annealing [ 10 ] at zero temperature. Successful applications of simulated annealing within the areas of object detection and recognition have been reported in [ 9 ] and [ 1 ].
If the object under consideration can be adequately represented using only a fraction of the pixels then this is clearly advantageous since the execution time of the method is directly dependent on the number of samples used. In our application this is certainly the case since an image of a face contains a high degree of redundant information, and large regions can often be represented with only a few points.
A sampling technique commonly used in Monte Carlo integration is based
on Sobol sequences [
15
]. A Sobol sequence is a quasi-random sequence of numbers maximally
spread out over a given hyper-cube. The sequence is generated
number-theoretically, rather than randomly, and successive points at any
stage fill in the gaps in the previously generated distribution. The use
of Sobol sequences leads to faster convergence compared to uniformly
distributed random numbers since the fractional error of the
approximation decreases as
instead of
[
15
], where
N
is the number of samples and
d
the dimensionality of the approximated function. In Figure
1
, three Sobol sequences are shown.
Figure 1:
Two-dimensional Sobol sequences at three different sampling rates.
Combining the optimised robust correlation method with random sampling yields several benefits. The quasi-random nature of the process implies that the sampling points will not interfere with (and possibly cancel out) a specific frequency. In contrast, if sampling points are positioned on a grid, aliasing is much more likely. Furthermore, it is possible to continuously increase the sampling density -- until some convergence criterion is met -- and at the same time maintain approximately uniform density throughout the image. This is because the sampling points are avoiding the chance clustering that occurs with random points drawn from a uniform distribution. A direct consequence of this property is that Sobol sequences can be used for continuous multi-resolution matching. By varying the sampling density the image can be represented in different resolutions.
Kenneth Jonsson
