Harris affine region detector

In the fields of computer vision and image analysis, the Harris affine region detector belongs to the category of feature detection. Feature detection is a preprocessing step of several algorithms that rely on identifying characteristic points or interest points so to make correspondences between images, recognize textures, categorize objects or build panoramas.
Overview.
The Harris affine detector can identify similar regions between images that are related through affine transformations and have different illuminations. These "affine-invariant" detectors should be capable of identifying similar regions in images taken from different viewpoints that are related by a simple geometric transformation: scaling, rotation and shearing. These detected regions have been called both "invariant" and "covariant". On one hand, the regions are detected "invariant" of the image transformation but the regions "covariantly" change with image transformation. Do not dwell too much on these two naming conventions; the important thing to understand is that the design of these interest points will make them compatible across images taken from several viewpoints. Other detectors that are affine-invariant include Hessian affine region detector, Maximally stable extremal regions, Kadir–Brady saliency detector, edge-based regions (EBR) and intensity-extrema-based regions (IBR).
Mikolajczyk and Schmid (2002) first described the Harris affine detector as it is used today in Affine Invariant Interest Point Detector". Earlier works in this direction include use of affine shape adaptation by Lindeberg and Garding for computing affine invariant image descriptors and in this way reducing the influence of perspective image deformations, the use affine adapted feature points for wide baseline matching by Baumberg and the first use of scale invariant feature points by Lindeberg; for an overview of the theoretical background. The Harris affine detector relies on the combination of corner points detected through Harris corner detection, multi-scale analysis through Gaussian scale space and affine normalization using an iterative affine shape adaptation algorithm. The recursive and iterative algorithm follows an iterative approach to detecting these regions:
Algorithm description.
Harris–Laplace detector (initial region points).
The Harris affine detector relies heavily on both the Harris measure and a Gaussian scale space representation. Therefore, a brief examination of both follow. For a more exhaustive derivations see corner detection and Gaussian scale space or their associated papers.
Harris corner measure.
The Harris corner detector algorithm relies on a central principle: at a corner, the image intensity will change largely in multiple directions. This can alternatively be formulated by examining the changes of intensity due to shifts in a local window. Around a corner point, the image intensity will change greatly when the window is shifted in an arbitrary direction. Following this intuition and through a clever decomposition, the Harris detector uses the second moment matrix as the basis of its corner decisions. (See corner detection for more complete derivation). The matrix formula_1, has also been called the autocorrelation matrix and has values closely related to the derivatives of image intensity.
where formula_3 and formula_4 are the respective derivatives (of pixel intensity) in the formula_5 and formula_6 direction at point (formula_7,formula_8); formula_7 and formula_8 are the position parameters of the weighting function w. The off-diagonal entries are the product of formula_3 and formula_4, while the diagonal entries are squares of the respective derivatives. The weighting function formula_13 can be uniform, but is more typically an isotropic, circular Gaussian,
that acts to average in a local region while weighting those values near the center more heavily.
As it turns out, this formula_1 matrix describes the shape of the autocorrelation measure as due to shifts in window location. Thus, if we let formula_16 and formula_17 be the eigenvalues of formula_1, then these values will provide a quantitative description of how the autocorrelation measure changes in space: its principal curvatures. As Harris and Stephens (1988) point out, the formula_1 matrix centered on corner points will have two large, positive eigenvalues. Rather than extracting these eigenvalues using methods like singular value decomposition, the Harris measure based on the trace and determinant is used:
where formula_21 is a constant. Corner points have large, positive eigenvalues and would thus have a large Harris measure. Thus, corner points are identified as local maxima of the Harris measure that are above a specified threshold.
where formula_23 are the set of all corner points, formula_24 is the Harris measure calculated at formula_5, formula_26 is an 8-neighbor set centered on formula_27 and formula_28 is a specified threshold.
Gaussian scale-space.
A Gaussian scale space representation of an image is the set of images that result from convolving a Gaussian kernel of various sizes with the original image. In general, the representation can be formulated as:
where formula_30 is an isotropic, circular Gaussian kernel as defined above. The convolution with a Gaussian kernel smooths the image using a window the size of the kernel. A larger scale, formula_31, corresponds to a smoother resultant image. Mikolajczyk and Schmid (2001) point out that derivatives and other measurements must be normalized across scales. A derivative of order formula_32, formula_33, must be normalized by a factor formula_34 in the following manner:
These derivatives, or any arbitrary measure, can be adapted to a scale space representation by calculating this measure using a set of scales recursively where the formula_36 scale is formula_37. See scale space for a more complete description.
Combining Harris detector across Gaussian scale-space.
The Harris-Laplace detector combines the traditional 2D Harris corner detector with the idea of a Gaussian scale space representation in order to create a scale-invariant detector. Harris-corner points are good starting points because they have been shown to have good rotational and illumination invariance in addition to identifying the interesting points of the image. However, the points are not scale invariant and thus the second-moment matrix must be modified to reflect a scale-invariant property. Let us denote, formula_38 as the scale adapted second-moment matrix used in the Harris-Laplace detector.
where formula_40 is the Gaussian kernel of scale formula_41 and formula_42. Similar to the Gaussian-scale space, formula_43 is the Gaussian-smoothed image. The formula_44 operator denotes convolution. formula_45 and formula_46 are the derivatives in their respective direction applied to the smoothed image and calculated using a Gaussian kernel with scale formula_47. In terms of our Gaussian scale-space framework, the formula_41 parameter determines the current scale at which the Harris corner points are detected.
Building upon this scale-adapted second-moment matrix, the Harris-Laplace detector is a twofold process: applying the Harris corner detector at multiple scales and automatically choosing the "characteristic scale".
Multi-scale Harris corner points.
The algorithm searches over a fixed number of predefined scales. This set of scales is defined as:
Mikolajczyk and Schmid (2004) use formula_50. For each integration scale, formula_41, chosen from this set, the appropriate differentiation scale is chosen to be a constant factor of the integration scale: formula_52. Mikolajczyk and Schmid (2004) used formula_53. Using these scales, the interest points are detected using a Harris measure on the formula_54 matrix. The "cornerness," like the typical Harris measure, is defined as:
Like the traditional Harris detector, corner points are those local (8 point neighborhood) maxima of the "cornerness" that are above a specified threshold.
Characteristic scale identification.
An iterative algorithm based on Lindeberg (1998) both spatially localizes the corner points and selects the "characteristic scale". The iterative search has three key steps, that are carried for each point formula_56 that were initially detected at scale formula_41 by the multi-scale Harris detector (formula_58 indicates the formula_59 iteration):
If the stopping criterion is not met, then the algorithm repeats from step 1 using the new formula_72 points and scale. When the stopping criterion is met, the found points represent those that maximize the LoG across scales (scale selection) and maximize the Harris corner measure in a local neighborhood (spatial selection).
Affine-invariant points.
Mathematical theory.
The Harris-Laplace detected points are scale invariant and work well for isotropic regions that are viewed from the same viewing angle. In order to be invariant to arbitrary affine transformations (and viewpoints), the mathematical framework must be revisited. The second-moment matrix formula_73 is defined more generally for anisotropic regions:
where formula_75 and formula_76 are covariance matrices defining the differentiation and the integration Gaussian kernel scales. Although this may look significantly different from the second-moment matrix in the Harris-Laplace detector; it is in fact, identical. The earlier formula_77 matrix was the 2D-isotropic version in which the covariance matrices formula_75 and formula_76 were 2x2 identity matrices multiplied by factors formula_41 and formula_47, respectively. In the new formulation, one can think of Gaussian kernels as a multivariate Gaussian distributions as opposed to a uniform Gaussian kernel. A uniform Gaussian kernel can be thought of as an isotropic, circular region. Similarly, a more general Gaussian kernel defines an ellipsoid. In fact, the eigenvectors and eigenvalues of the covariance matrix define the rotation and size of the ellipsoid. Thus we can easily see that this representation allows us to completely define an arbitrary elliptical affine region over which we want to integrate or differentiate.
The goal of the affine invariant detector is to identify regions in images that are related through affine transformations. We thus consider a point formula_82 and the transformed point formula_83, where A is an affine transformation. In the case of images, both formula_84 and formula_82 live in formula_86 space. The second-moment matrices are related in the following manner:
where formula_88 and formula_89 are the covariance matrices for the formula_90 reference frame. If we continue with this formulation and enforce that
where formula_41 and formula_47 are scalar factors, one can show that the covariance matrices for the related point are similarly related:
By requiring the covariance matrices to satisfy these conditions, several nice properties arise. One of these properties is that the square root of the second-moment matrix, formula_95 will transform the original anisotropic region into isotropic regions that are related simply through a pure rotation matrix formula_96. These new isotropic regions can be thought of as a normalized reference frame. The following equations formulate the relation between the normalized points formula_97 and formula_98:
The rotation matrix can be recovered using gradient methods likes those in the SIFT descriptor. As discussed with the Harris detector, the eigenvalues and eigenvectors of the second-moment matrix, formula_100 characterize the curvature and shape of the pixel intensities. That is, the eigenvector associated with the largest eigenvalue indicates the direction of largest change and the eigenvector associated with the smallest eigenvalue defines the direction of least change. In the 2D case, the eigenvectors and eigenvalues define an ellipse. For an isotropic region, the region should be circular in shape and not elliptical. This is the case when the eigenvalues have the same magnitude. Thus a measure of the isotropy around a local region is defined as the following:
where formula_102 denote eigenvalues. This measure has the range formula_103. A value of formula_104 corresponds to perfect isotropy.
Iterative algorithm.
Using this mathematical framework, the Harris affine detector algorithm iteratively discovers the second-moment matrix that transforms the anisotropic region into a normalized region in which the isotropic measure is sufficiently close to one. The algorithm uses this "shape adaptation matrix", formula_105, to transform the image into a normalized reference frame. In this normalized space, the interest points' parameters (spatial location, integration scale and differentiation scale) are refined using methods similar to the Harris-Laplace detector. The second-moment matrix is computed in this normalized reference frame and should have an isotropic measure close to one at the final iteration. At every formula_58th iteration, each interest region is defined by several parameters that the algorithm must discover: the formula_107 matrix, position formula_108, integration scale formula_109 and differentiation scale formula_110. Because the detector computes the second-moment matrix in the transformed domain, it's convenient to denote this transformed position as formula_111 where formula_112.
 \, \sigma_I^2 \det(L_{xx}(\mathbf{x}, \sigma_I) + L_{yy}(\mathbf{x},\sigma_I))
</math>
It's important to note that the integration scale in the formula_113 space differs significantly than the non-normalized space. Therefore, it is necessary to search for the integration scale as opposed to using the scale in the non-normalized space.
where formula_119 is the second-moment matrix evaluated in the normalized reference frame. This maximization processes causes the eigenvalues to converge to the same value.
where formula_77 is the second-moment matrix as defined above. The window formula_125 is the set of 8-nearest neighbors of the previous iteration's point in the normalized reference frame.
Because our spatial localization was done in the formula_105-normalized reference frame, the newly chosen point must be transformed back to the original reference frame. This is achieved by transforming a displacement vector and adding this to the previous point:
Mikolajczyk and Schmid (2004) had good success with formula_137.
Computation and implementation.
The computational complexity of the Harris-Affine detector is broken into two parts: initial point detection and affine region normalization. The initial point detection algorithm, Harris-Laplace, has complexity formula_138 where formula_139 is the number of pixels in the image. The affine region normalization algorithm automatically detects the scale and estimates the "shape adaptation matrix", formula_105. This process has complexity formula_141, where formula_7 is the number of initial points, formula_32 is the size of the search space for the automatic scale selection and formula_58 is the number of iterations required to compute the formula_105 matrix.
Some methods exist to reduce the complexity of the algorithm at the expense of accuracy. One method is to eliminate the search in the differentiation scale step. Rather than choose a factor formula_31 from a set of factors, the sped-up algorithm chooses the scale to be constant across iterations and points: formula_147. Although this reduction in search space might decrease the complexity, this change can severely effect the convergence of the formula_105 matrix.
Analysis.
Convergence.
One can imagine that this algorithm might identify duplicate interest points at multiple scales. Because the Harris affine algorithm looks at each initial point given by the Harris-Laplace detector independently, there is no discrimination between identical points. In practice, it has been shown that these points will ultimately all converge to the same interest point. After finishing identifying all interest points, the algorithm accounts for duplicates by comparing the spatial coordinates (formula_56), the integration scale formula_41, the isotropic measure formula_151 and skew. If these interest point parameters are similar within a specified threshold, then they are labeled duplicates. The algorithm discards all these duplicate points except for the interest point that's closest to the average of the duplicates. Typically 30% of the Harris affine points are distinct and dissimilar enough to not be discarded.
Mikolajczyk and Schmid (2004) showed that often the initial points (40%) do not converge. The algorithm detects this divergence by stopping the iterative algorithm if the inverse of the isotropic measure is larger than a specified threshold: formula_152. Mikolajczyk and Schmid (2004) use formula_153. Of those that did converge, the typical number of required iterations was 10.
Quantitative measure.
Quantitative analysis of affine region detectors take into account both the accuracy of point locations and the overlap of regions across two images. Mioklajcyzk and Schmid (2004) extend the repeatability measure of Schmid et al. (1998) as the ratio of point correspondences to minimum detected points of the two images.
where formula_155 are the number of corresponding points in images formula_1 and formula_157. formula_158 and formula_159 are the number of detected points in the respective images. Because each image represents 3D space, it might be the case that the one image contains objects that are not in the second image and thus whose interest points have no chance of corresponding. In order to make the repeatability measure valid, one remove these points and must only consider points that lie in both images; formula_159 and formula_158 only count those points such that formula_162. For a pair of two images related through a homography matrix formula_163, two points, formula_164 and formula_165 are said to correspond if:
Robustness to affine and other transformations.
Mikolajczyk et al. (2005) have done a thorough analysis of several state-of-the-art affine region detectors: Harris affine, Hessian affine, MSER, IBR & EBR and salient detectors. Mikolajczyk et al. analyzed both structured images and textured images in their evaluation. Linux binaries of the detectors and their test images are freely available at their webpage. A brief summary of the results of Mikolajczyk et al. (2005) follow; see "A comparison of affine region detectors" for a more quantitative analysis.