Features and Matching - Computer Vision for Visual Effects - page 124

Before creating the feature descriptor, we can warp the detected affine-covariant
ellipse to a circle, and be confident that the circle produced by the same feature in
a different image contains the same set of pixels (up to a rotation). The fundamen-
tal theory of affine-invariant regions was first proposed by Lindeberg and Gårding
[ 287 ] and applied by other researchers including Baumberg [ 32 ], Schaffalitzky and
Zisserman [ 423 ], and Mikolajczyk and Schmid [ 327 ].
We can find affine-invariant elliptical regions around feature points with a
straightforward iterative procedure called affine adaptation :

1. Detect the feature point position and its characteristic scale (e.g., usingHarris-
Laplace or Hessian-Laplace).
2. Compute the local second-moment matrix H at the given scale (i.e., the
scale-normalized Harris matrix in Equation ( 4.20 )). Scale H so it has unit
determinant. 9
3. Compute the Cholesky factorization H CC , where C is a lower-triangular

matrix with non-negative diagonal elements. 10 C is sometimes called the
matrix square root of H .
4. Warp the image structure around the feature point using the linear transfor-
mation C . That is, the new image coordinates are related to the old ones by
I new (

=

.
5. Compute the local second-moment matrix H for the new image and scale H
so it has unit determinant.

x new ) = I old ( Cx old )

6. If H is sufficiently close to the identity (i.e., its eigenvalues are nearly equal),

stop. Otherwise, go to Step 3.

We obtain the desired ellipse by mapping the unit circle back into the original
image coordinates by inverting the chain of scalings and matrix square roots. Linde-
berg and Gårding showed that under an ideal affine transformation of the image and
using Harris-Laplace features, the process will indeed produce covariant elliptical
regions. If we consider the same feature before and after an affine transformation,
the circular regions resulting from the affine adaptation process will be identical up
to a rotation. We will describe one way to account for this rotation when describing
the feature in Section 4.2.4 .
Mikolajczyk and Schmid [ 327 ] proposed to simultaneously detect feature point
locations and corresponding affine-invariant regions using an iterative algorithm,
resulting in Harris-Affine features . The basic idea is the same as the algorithm
described earlier, except that within each iteration the location and characteristic
scale of the feature point are re-estimated. They proposed the ratio of the smaller
eigenvalue to the larger one in Step 6 as a measure of the local isotropy of the region,
stopping when the ratio was above a threshold (e.g., 0.95). On the other hand, fea-
tures can be rejected when the ratio of eigenvalues in the original image is too low,
indicating a highly elliptical (i.e., edge-like) region. If we use the Hessian matrix in

9 This normalization was suggested by Baumberg [ 32 ]; Lindeberg and Gårding [ 287 ] instead
recommended dividing H by its smallest eigenvalue.
10 The factorization exists since H is symmetric with non-negative eigenvalues, but it is not unique
unless the eigenvalues are both positive.