Added to Favorites

Related Searches

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.

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 regions, Maximally Stable Extremal Regions, Kadir brady saliency detector, edge-based regions (EBR) and intensity extrema-based (IBR) regions.

Mikolajczyk and Schmid (2002) first described the Harris-Affine detector as it is used today in An Affine Invariant Interest Point Detector Earlier works in this direction include use of affine adapted feature points for matching by Baumberg and the first use of scale invariant feature points by Lindeberg . The Harris-Affine detector relies on the combination of corner points detected thorough 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:

- Identify initial region points using scale-invariant Harris-Laplace Detector.
- For each initial point, normalize the region to be affine invariant using affine shape adaptation.
- Iteratively estimate the affine region: selection of proper integration scale, differentiation scale and spatially localize interest points..
- Update the affine region using these scales and spatial localizations.
- Repeat step 3 if the stopping criterion is not met.

- $A(mathbf\{x\})\; =\; sum\_\{x,y\}\; w(x,y)$

where $I\_\{x\}$ and $I\_\{y\}$ are the respective derivatives (of pixel intensity) in the $x$ and $y$ direction. The off-diagonal entries are the product of $I\_\{x\}$ and $I\_\{y\}$, while the diagonal entries are squares of the respective derivatives. The weighting function $w(x,y)$ can be uniform, but is more typically an isotropic, circular Gaussian,

- $w(x,y)\; =\; g(x,y,sigma)\; =\; frac\{1\}\{2pi\; sigma\}\; e^\{\; left\; (-frac\{\; x^2\; +\; y^2\}\{2sigma\}\; right\; )\}$

that acts to average in a local region while weighting those values near the center more heavily.

As it turns out, this $A$ matrix describes the shape of the autocorrelation measure as due to shifts in window location. Thus, if we let $lambda\_1$ and $lambda\_2$ be the eigenvalues of $A$, then these values will provide a quantitative description of the how the autocorrelation measure changes in space: its principal curvatures. As Harris and Stephens (1988) point out, the $A$ 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 $alpha$ 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.

- $begin\{align\}$

where $\{x\_c\}$ are the set of all corner points, $R(x)$ is the Harris measure calculated at $x$, $W(x\_c)$ is an 8-neighbor set centered around $x\_c$ and $t\_\{threshold\}$ is a specified threshold.

- $$

where $G(s)$ 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, $s$, 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 $m$, $D\_\{i\_1,\; ...\; i\_m\}$, must be normalized by a factor $s^m$ 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 $nth$ scale is $s\_n\; =\; k^n\; s\_0$. See scale space for a more complete description.

- $$

where $g(sigma\_I)$ is the Gaussian kernel of scale $sigma\_I$ and $mathbf\{x\}\; =\; (x,y)$. Similar to the Gaussian-scale space, $L(mathbf\{x\})$ is the Gaussian-smoothed image. The $mathbf\{otimes\}$ operator denotes convolution. $L\_\{x\}(mathbf\{x\},sigma\_\{D\})$ and $L\_\{y\}(mathbf\{x\},\; sigma\_\{D\})$ are the derivatives in their respective direction applied to the smoothed image and calculated using a Gaussian kernel with scale $sigma\_D$. In terms of our Gaussian scale-space framework, the $sigma\_I$ 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.

- $$

Mikolajczyk and Schmid (2004) use $k\; =\; 1.4$. For each integration scale, $sigma\_I$, chosen from this set, the appropriate differentiation scale is chosen to be a constant factor of the integration scale: $sigma\_D\; =\; ssigma\_I$. Mikolajczyk and Schmid (2004) used $s\; =\; 0.7$ . Using these scales, the interest points are detected using a Harris measure on the $mu(mathbf\{x\},\; sigma\_\{mathit\{I\}\},\; sigma\_\{mathit\{D\}\})$ 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.

- Choose the scale $sigma\_I^\{(k+1)\}$ that maximizes the Laplacian-of-Gaussians (LoG) over a predefined range of neighboring scales. The neighboring scales are typically chosen from a range that is within a two scale-space neighborhood. That is, if the original points were detected using a scaling factor of $1.4$ between successive scales, a two scale-space neighborhood is the range $t\; in\; [0.7,\; dots,\; 1.4]$. Thus the Gaussian scales examined are: $sigma\_I^\{(k+1)\}\; =\; t\; sigma\_I^k$. The LoG measurement is defined as:
- $$

where $L\_\{xx\}$ and $L\_\{yy\}$ are the second derivatives in their respective directions. The $sigma\_I^2$ factor (as discussed above in Gaussian scale-space) is used to normalize the LoG across scales and make these measures comparable, thus making a maximum relevant. Mikolajczyk and Schmid (2001) demonstrate that the LoG measure attains the highest percentage of correctly detected corner points in comparison to other scale-selection measures . The scale which maximizes this LoG measure in the two scale-space neighborhood is deemed the characteristic scale, $sigma\_I^\{(k+1)\}$, and used in subsequent iterations. If no extrema, or maxima of the LoG is found, this point is discarded from future searches.

- Using the characteristic scale, the points are spatially localized. That is to say, the point $mathbf\{x\}^\{(k+1)\}$ is chosen such that it maximizes the Harris corner measure (cornerness as defined above) within an 8×8 local neighborhood.
- Stopping criterion: $sigma\_I^\{(k+1)\}\; ==\; sigma\_I^\{(k)\}$ and $mathbf\{x\}^\{(k+1)\}\; ==\; mathbf\{x\}^\{(k)\}$.
If the stopping criterion is not met, then the algorithm repeats from step 1 using the new $k+1$ 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).

It's important to note that although, Harris points may not be localized across scales, they ultimately all converge to the same scale-invariant point. That is to say, a corner point that might be detected at multiple scales may not be at the same coordinates at each scale. However, through the selection of characteristic scale and spatial localization, the points will converge .

- $$

where $Sigma\_I$ and $Sigma\_D$ are covariance matrices defining the differentiation and the integration Gaussian kernel scales. Although this make look significantly different than the second-moment matrix in the Harris-Laplace detector; it is in fact, identical. The earlier $mu$ matrix was the 2D-isotropic version in which the covariance matrices $Sigma\_I$ and $Sigma\_D$ were 2x2 identity matrices multiplied by factors $sigma\_I$ and $sigma\_D$, 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. Simiarly, 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 $mathbf\{x\}\_L$ and the transformed point $mathbf\{x\}\_R\; =\; Amathbf\{x\}\_L$, where A is an affine transformation. In the case of images, both $mathbf\{x\}\_R$ and $mathbf\{x\}\_L$ live in $R^2$ space. The second-moment matrices are related in the following manner :

- $begin\{align\}$

where $Sigma\_\{I,b\}$ and $Sigma\_\{D,b\}$ are the covariance matrices for the $b$ reference frame. If we continue with this formulation and enforce that

- $begin\{align\}$

where $sigma\_I$ and $sigma\_D$ are scalar factors, one can show that the covariance matrices for the related point are similarly related:

- $begin\{align\}$

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, $M^\{tfrac\{1\}\{2\}\}$ will transform the original anisotropic region into isotropic regions that are related simply through a pure rotation matrix $R$. These new isotropic regions can be thought of as a normalized reference frame. The following equations formulate the relation between the normalized points $x\_R^\text{'}$ and $x\_L^\text{'}$:

- $begin\{align\}$

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, $M\; =\; mu(mathbf\{x\},\; Sigma\_I,\; Sigma\_D)$ 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 $lambda$ denote eigenvalues. This measure has the range $[0\; dots\; 1]$. A value of $1$ corresponds to perfect isotropy.

- The detector initializes the search space with points detected by the Harris-Laplace detector.

$U^\{(0)\}\; =\; mathit\{identity\}$ and $mathbf\{x\}^\{(0)\}$, $sigma\_D^\{(0)\}$, and $sigma\_I^\{(0)\}$ are those from the Harris-Laplace detector. - Apply the previous iteration shape adaptation matrix, $U^\{(k-1)\}$ to generate the normalized reference frame, $U^\{(k-1)\}mathbf\{x\}\_w^\{(k-1)\}\; =\; mathbf\{x\}^\{(k-1)\}$. For the first iteration, you apply $U^\{(0)\}$.
- Select the integration scale, $sigma\_I^\{(k)\}$, using a method similar to the Harris-Laplace detector. The scale is chosen as the scale that maximizes the Laplacian of Gaussian (LoG). The search space of the scales are those within two scale-spaces of the previous iterations scale.
- $$

It's important to note that the integration scale in the $U-normalized$ 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.

- Select the differentiation scale, $sigma\_D^\{(k)\}$. In order to reduce the search space and degrees of freedom, the differentiation scale is taken to be related to the integration scale through a constant factor: $sigma\_D^\{k\}\; =\; s\; sigma\_I^\{k\}$. For obvious reasons, the constant factor is less than one. Mikolajczyk and Schmid (2001) note that a too small factor will make smoothing (integration) too significant in comparison to differentiation and a factor that's too large will not allow for the integration to average the covariance matrix . It is common to choose $s\; in\; [0.5,0.75]$. From this set, the chosen scale will maximize the isotropic measure $mathcal\{Q\}\; =\; frac\{lambda\_\{min\}(mu)\}\{lambda\_\{max\}(mu)\}$.
- $$

where $mu(mathbf\{x\}\_w^\{(k)\},\; sigma\_I^\{k\},\; sigma\_D)$ is the second-moment matrix evaluated in the normalized reference frame. This maximization processes causes the eigenvalues to converge to the same value.

- Spatial Localization: Select the point $mathbf\{x\}\_w^\{(k)\}$ that maximizes the Harris corner measure ($mathit\{cornerness\}$) within an 8-point neighborhood around the previous $mathbf\{x\}\_w^\{(k-1)\}$ point.
- $$

where $mu$ is the second-moment matrix as defined above. The window $W(mathbf\{x\}\_w^\{(k-1)\})$ 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 $U$-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:

- $$

- As mentioned above, the square-root of the second-moment matrix defines the transformation matrix that generates the normalized reference frame. We thus need to save this matrix: $mu\_i^\{(k)\}\; =\; mu^\{-tfrac\{1\}\{2\}\}(mathbf\{x\}\_w^\{(k)\},\; sigma\_I^\{(k)\},\; sigma\_D^\{(k)\})$. The transformation matrix $U$ is updated: $U^\{(k)\}\; =\; mu\_i^\{(k)\}cdot\; U^\{(k-1)\}$. In order to ensure that the image gets sampled correctly and we are expanding the image in the direction of the least change (smallest eigenvalue), we fix the maximium eigenvalue: $lambda\_\{max\}(U^\{(k)\})\; =\; 1$. Using this updating method, one can easily see that the final $U$ matrix takes the following form:
- $$

- If the stopping criterion is not met, continue to the next iteration at step 2. Because the algorithm iteratively solves for the $U-normalization$ matrix that transforms an anisotropic region into an isotropic region, it makes sense to stop when the isotropic measure, $mathcal\{Q\}\; =\; frac\{lambda\_max(mu)\}\{lambda\_max(mu)\}$, is sufficiently close to its maximum value 1. Sufficiently close implies the following stopping condition:
- $$

Mikolajczyk and Schmid (2004) had good success with $epsilon\_C\; =\; 0.05$.

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 $s$ from a set of factors, the sped-up algorithm chooses the scale to be constant across iterations and points: $sigma\_D\; =\; s\; sigma\_I,;\; s\; =\; constant$. Although this reduction in search space might decrease the complexity, this change can severely effect the convergence of the $U$ matrix.

Mikolajczyk and Schmid (2004) showed that often the initial points (40%) do not coverage. The algorithm detects this divergence by stopping the iterative algorithm if the inverse of the isotropic measure is larger than a specified threshold: $tfrac\{lambda\_max(U)\}\{lambda\_min(U)\}\; >\; t\_text\{diverge\}$. Mikolajczyk and Schmid (2004) use $t\_\{diverge\}\; =\; 6$. Of those that did converge, the typical number of required iterations was 10 .

- $$

where $C(A,B)$ are the number of corresponding points in images $A$ and $B$. $n\_B$ and $n\_A$ 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; $n\_A$ and $n\_B$ only count those points such that $x\_A\; =\; H\; cdot\; x\_B$. For a pair of two images related through a homography matrix $H$, two points, $mathbf\{x\_a\}$ and $mathbf\{x\_b\}$ are said to correspond if:

- Error in pixel location is less than 1.5 pixels: $|\; mathbf\{x\_a\}\; -\; Hcdot\; mathbf\{x\_b\}\; |\; <\; 1.5$
- The overlap error of the two affine points ($epsilon\_S$) must be less than a specified threshold (typically 40%). For affine regions, this overlap error is the following:
- $$

where $mu\_a$ and $mu\_b$ are the recovered elliptical regions whose points satisfy: $mu^T\; mathbf\{x\}\; mu\; =\; 1$. Basically, this measure takes a ratio of areas: the area of overlap (intersection) and the total area (union). Perfect overlap would have a ratio of one and have an $epsilon\_S\; =\; 0$. Different scales effect the region of overlap and thus must be taken into account by normalizing the area of each region of interest. Regions with an overlap error as high as 50% are viable detectors to be matched with a good descriptor .

A second measure, a matching score, more practically assesses the detector's ability to identify matching points between images. Mikolajczyk and Schmid (2005) use a SIFT descriptor to identify matching points. In addition to being the closest points in SIFT-space, two matched points must also have a sufficiently small overlap error (as defined in the repeatability measure). The matching score is the ratio of the number of matched points and the minimum of the total detected points in each image:

- $M\_\{score\}\; =\; frac\{M(A,B)\}\{min(n\_A,n\_B)\}$ ,

where $M(A,B)$ are the number of matching points and $n\_B$ and $n\_A$ are the number of detected regions in the respective images.

- Viewpoint Angle Change: The Harris-Affine detector has reasonable (average) robustness to these types of changes. The detector maintains a repeatability score of above 50% up until a viewpoint angle of above 40 degrees. The detector tends to detect a high number of repeatable and matchable regions even under a large viewpoint change.
- Scale Change: The Harris-Affine detector remains very consistent under scale changes. Although the number of points declines considerably at large scale changes (above 2.8), the repeatability (50-60%) and matching scores (25-30%) remain very constant especially with textured images. This is consistent with the high-performance of the automatic scale selection iterative algorithm.
- Blurred Images: The Harris-Affine detector remains very stable under image blurring. Because the detector does not rely on image segmentation or region boundaries, the repeatability and matching scores remain constant.
- JPEG Artifacts: The Harris-Affine detector degrades similar to other affine detectors: repeatability and matching scores drop significantly above 80% compression.
- Illumination Changes: The Harris-Affine detector, like other affine detectors, is very robust to illumination changes: repeatability and matching scores remain constant under decreasing light. This should be expected because the detectors rely heavily on relative intensities (derivatives) and not absolute intensities.

- Harris-affine region points tend to be small and numerous. Both the Harris-Affine detector and Hessian-Affine consistently identify double the number repeatable points as other affine detectors: ~1000 regions for a 800x640 image . Small regions are less likely to be occluded but have a smaller chance of overlapping neighboring regions.
- The Harris-Affine detector responds well to textured scenes in which there are a lot of corner-like parts. However, for some structured scenes, like buildings, the Harris-Affine detector performs very well. This is complementary to MSER that tends to do better with well structured (segmentable) scenes.
- Overall the Harris-Affine detector performs very well, but still behind MSER and Hessian-Affine in all cases but blurred images.
- Harris-Affine and Hessian-Affine detectors are less accurate than others: their repeatability score increases as the overlap threshold is increased.
- The detected affine-invariant regions may still differ in their rotation and illumination. Any descriptor that uses these regions must account for the invariance when using the regions for matching or other comparisons.

- Content-based image retrieval
- Model-based recognition
- Object retrieval in video
- Visual data mining: identifying important objects, characters and scenes in videos
- Object recognition and categorization

- Affine Covariant Features: K. Mikolajczyk maintains a web page that contains Linux binaries of the Harris-Affine detector in addition to other detectors and descriptors. Matlab code is also available that can be used to illustrate and compute the repeatability of various detectors. Code and images are also available to duplicate the results found in the Mikolajczyk et al. (2005) paper.

- Cordelia Schmid's Computer Vision Lab

- Code, test Images, bibliography of Affine Covariant Features maintained by Krystian Mikolajczyk and the Visual Geometry Group from the Robotics group at the University of Oxford.

- Bibliography of feature (and blob) detectors maintained by USC Institute for Robotics and Intelligent Systems

- Digital implementation of Laplacian of Gaussian

- Hessian-affine
- MSER
- Kadir brady saliency detector
- Scale-space
- Isotropy
- Corner detection
- Interest point detection
- Affine shape adaptation
- Computer vision

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 17, 2008 at 10:24:57 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday September 17, 2008 at 10:24:57 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.