Harris corner detector

Last updated

The Harris corner detector is a corner detection operator that is commonly used in computer vision algorithms to extract corners and infer features of an image. It was first introduced by Chris Harris and Mike Stephens in 1988 upon the improvement of Moravec's corner detector. [1] Compared to its predecessor, Harris' corner detector takes the differential of the corner score into account with reference to direction directly, instead of using shifting patches for every 45 degree angles, and has been proved to be more accurate in distinguishing between edges and corners. [2] Since then, it has been improved and adopted in many algorithms to preprocess images for subsequent applications.

Contents

Introduction

A corner is a point whose local neighborhood stands in two dominant and different edge directions. In other words, a corner can be interpreted as the junction of two edges, where an edge is a sudden change in image brightness. [3] Corners are the important features in the image, and they are generally termed as interest points which are invariant to translation, rotation and illumination. Although corners are only a small percentage of the image, they contain the most important features in restoring image information, and they can be used to minimize the amount of processed data for motion tracking, image stitching, building 2D mosaics, stereo vision, image representation and other related computer vision areas.

In order to capture the corners from the image, researchers have proposed many different corner detectors including the Kanade-Lucas-Tomasi (KLT) operator and the Harris operator which are most simple, efficient and reliable for use in corner detection. These two popular methodologies are both closely associated with and based on the local structure matrix. Compared to the Kanade-Lucas-Tomasi corner detector, the Harris corner detector provides good repeatability under changing illumination and rotation, and therefore, it is more often used in stereo matching and image database retrieval. Although there still exists drawbacks and limitations, the Harris corner detector is still an important and fundamental technique for many computer vision applications.

Development of Harris corner detection algorithm [1]

Without loss of generality, we will assume a grayscale 2-dimensional image is used. Let this image be given by . Consider taking an image patch (window) and shifting it by . The sum of squared differences (SSD) between these two patches, denoted , is given by:

can be approximated by a Taylor expansion. Let and be the partial derivatives of , such that

This produces the approximation

which can be written in matrix form:

where M is the structure tensor,

Process of Harris corner detection algorithm [4] [5] [6]

Commonly, Harris corner detector algorithm can be divided into five steps.

  1. Color to grayscale
  2. Spatial derivative calculation
  3. Structure tensor setup
  4. Harris response calculation
  5. Non-maximum suppression

Color to grayscale

If we use Harris corner detector in a color image, the first step is to convert it into a grayscale image, which will enhance the processing speed.

The value of the gray scale pixel can be computed as a weighted sums of the values R, B and G of the color image,

,

where, e.g.,

Spatial derivative calculation

Next, we are going to find the derivative with respect to x and the derivative with respect to y, and .

Structure tensor setup

With , , we can construct the structure tensor .

Harris response calculation

For , one has In this step, we compute the smallest eigenvalue of the structure tensor using that approximation:

with the trace .

Another commonly used Harris response calculation is shown as below,

where is an empirically determined constant; .

Non-maximum suppression

In order to pick up the optimal values to indicate corners, we find the local maxima as corners within the window which is a 3 by 3 filter.

Improvement [7] [8]

  1. Harris-Laplace Corner Detector [9]
  2. Differential Morphological Decomposition Based Corner Detector [10]
  3. Multi-scale Bilateral Structure Tensor Based Corner Detector [11]

Applications

  1. Image Alignment, Stitching and Registration [12]
  2. 2D Mosaics Creation [13]
  3. 3D Scene Modeling and Reconstruction [14]
  4. Motion Detection [15]
  5. Object Recognition [16]
  6. Image Indexing and Content-based Retrieval [17]
  7. Video Tracking [18]

See also

Related Research Articles

<span class="mw-page-title-main">Pauli matrices</span> Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three 2 × 2 complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

<span class="mw-page-title-main">Hooke's law</span> Physical law: force needed to deform a spring scales linearly with distance

In physics, Hooke's law is an empirical law which states that the force needed to extend or compress a spring by some distance scales linearly with respect to that distance—that is, Fs = kx, where k is a constant factor characteristic of the spring, and x is small compared to the total possible deformation of the spring. The law is named after 17th-century British physicist Robert Hooke. He first stated the law in 1676 as a Latin anagram. He published the solution of his anagram in 1678 as: ut tensio, sic vis. Hooke states in the 1678 work that he was aware of the law since 1660.

Simultaneous equations models are a type of statistical model in which the dependent variables are functions of other dependent variables, rather than just independent variables. This means some of the explanatory variables are jointly determined with the dependent variable, which in economics usually is the consequence of some underlying equilibrium mechanism. Take the typical supply and demand model: whilst typically one would determine the quantity supplied and demanded to be a function of the price set by the market, it is also possible for the reverse to be true, where producers observe the quantity that consumers demand and then set the price.

Linear elasticity is a mathematical model of how solid objects deform and become internally stressed due to prescribed loading conditions. It is a simplification of the more general nonlinear theory of elasticity and a branch of continuum mechanics.

In geodesy, conversion among different geographic coordinate systems is made necessary by the different geographic coordinate systems in use across the world and over time. Coordinate conversion is composed of a number of different types of conversion: format change of geographic coordinates, conversion of coordinate systems, or transformation to different geodetic datums. Geographic coordinate conversion has applications in cartography, surveying, navigation and geographic information systems.

In mathematics, the Hessian matrix, Hessian or Hesse matrix is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term "functional determinants". The Hessian is sometimes denoted by H or, ambiguously, by ∇2.

In mathematics, a Casimir element is a distinguished element of the center of the universal enveloping algebra of a Lie algebra. A prototypical example is the squared angular momentum operator, which is a Casimir element of the three-dimensional rotation group.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

Mehrotra's predictor–corrector method in optimization is a specific interior point method for linear programming. It was proposed in 1989 by Sanjay Mehrotra.

In continuum mechanics, the finite strain theory—also called large strain theory, or large deformation theory—deals with deformations in which strains and/or rotations are large enough to invalidate assumptions inherent in infinitesimal strain theory. In this case, the undeformed and deformed configurations of the continuum are significantly different, requiring a clear distinction between them. This is commonly the case with elastomers, plastically-deforming materials and other fluids and biological soft tissue.

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

In computer vision, the Lucas–Kanade method is a widely used differential method for optical flow estimation developed by Bruce D. Lucas and Takeo Kanade. It assumes that the flow is essentially constant in a local neighbourhood of the pixel under consideration, and solves the basic optical flow equations for all the pixels in that neighbourhood, by the least squares criterion.

<span class="mw-page-title-main">Corner detection</span> Approach used in computer vision systems

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.

In mathematics, the Weyl character formula in representation theory describes the characters of irreducible representations of compact Lie groups in terms of their highest weights. It was proved by Hermann Weyl. There is a closely related formula for the character of an irreducible representation of a semisimple Lie algebra. In Weyl's approach to the representation theory of connected compact Lie groups, the proof of the character formula is a key step in proving that every dominant integral element actually arises as the highest weight of some irreducible representation. Important consequences of the character formula are the Weyl dimension formula and the Kostant multiplicity formula.

In mathematics, the structure tensor, also referred to as the second-moment matrix, is a matrix derived from the gradient of a function. It describes the distribution of the gradient in a specified neighborhood around a point and makes the information invariant respect the observing coordinates. The structure tensor is often used in image processing and computer vision.

In mathematics, the Schur orthogonality relations, which were proven by Issai Schur through Schur's lemma, express a central fact about representations of finite groups. They admit a generalization to the case of compact groups in general, and in particular compact Lie groups, such as the rotation group SO(3).

In mathematics, an eigenvalue perturbation problem is that of finding the eigenvectors and eigenvalues of a system that is perturbed from one with known eigenvectors and eigenvalues . This is useful for studying how sensitive the original system's eigenvectors and eigenvalues are to changes in the system. This type of analysis was popularized by Lord Rayleigh, in his investigation of harmonic vibrations of a string perturbed by small inhomogeneities.

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.

Geometric feature learning is a technique combining machine learning and computer vision to solve visual tasks. The main goal of this method is to find a set of representative features of geometric form to represent an object by collecting geometric features from images and learning them using efficient machine learning methods. Humans solve visual tasks and can give fast response to the environment by extracting perceptual information from what they see. Researchers simulate humans' ability of recognizing objects to solve computer vision problems. For example, M. Mata et al.(2002) applied feature learning techniques to the mobile robot navigation tasks in order to avoid obstacles. They used genetic algorithms for learning features and recognizing objects (figures). Geometric feature learning methods can not only solve recognition problems but also predict subsequent actions by analyzing a set of sequential input sensory images, usually some extracting features of images. Through learning, some hypothesis of the next action are given and according to the probability of each hypothesis give a most probable action. This technique is widely used in the area of artificial intelligence.

<span class="mw-page-title-main">Relativistic angular momentum</span> Angular momentum in special and general relativity

In physics, relativistic angular momentum refers to the mathematical formalisms and physical concepts that define angular momentum in special relativity (SR) and general relativity (GR). The relativistic quantity is subtly different from the three-dimensional quantity in classical mechanics.

References

  1. 1 2 Chris Harris and Mike Stephens (1988). "A Combined Corner and Edge Detector". Alvey Vision Conference. Vol. 15.
  2. Dey, Nilanjan; et al. (2012). "A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique". arXiv: 1209.1558 [cs.CV].
  3. Konstantinos G. Derpanis (2004). The harris corner detector. York University.
  4. "Harris Operator Corner Detection using Sliding Window Method - Google Scholar". scholar.google.com. Retrieved 2015-11-29.
  5. "The Comparison and Application of Corner Detection Algorithms - Google Scholar". scholar.google.com. Retrieved 2015-11-29.
  6. Javier Sánchez, Nelson Monzón and Agustín Salgado (2018). "An Analysis and Implementation of the Harris Corner Detector". Image Processing on Line. 8: 305–328. doi: 10.5201/ipol.2018.229 .
  7. Bellavia, F.; Tegolo, D.; Valenti, C. (2011-03-01). "Improving Harris corner selection strategy". IET Computer Vision. 5 (2): 87. doi:10.1049/iet-cvi.2009.0127.
  8. Rosten, Edward; Drummond, Tom (2006-05-07). Leonardis, Aleš; Bischof, Horst; Pinz, Axel (eds.). Machine Learning for High-Speed Corner Detection. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 430–443. CiteSeerX   10.1.1.64.8513 . doi:10.1007/11744023_34. ISBN   978-3-540-33832-1. S2CID   1388140.
  9. "A Comparison of Affine Region Detectors - Google Scholar". scholar.google.com. Retrieved 2015-11-29.
  10. Gueguen, L.; Pesaresi, M. (2011). "Multi scale Harris corner detector based on Differential Morphological Decomposition". Pattern Recognition Letters. 32 (14): 1714–1719. Bibcode:2011PaReL..32.1714G. doi:10.1016/j.patrec.2011.07.021.
  11. "A Multi-scale Bilateral Structure Tensor Based Corner Detector - Google Scholar". scholar.google.com. Retrieved 2015-11-29.
  12. Kang, Juan; Xiao, Chuangbai; Deng, M.; Yu, Jing; Liu, Haifeng (2011-08-01). "Image registration based on harris corner and mutual information". Proceedings of 2011 International Conference on Electronic & Mechanical Engineering and Information Technology. Vol. 7. pp. 3434–3437. doi:10.1109/EMEIT.2011.6023066. ISBN   978-1-61284-087-1. S2CID   17367248.
  13. "Underwater Mosaic Creation using Video sequences from Different Altitudes - Google Scholar". scholar.google.com. Retrieved 2015-12-02.
  14. "Automated reconstruction of 3D scenes from sequences of images - Google Scholar". scholar.google.com. Retrieved 2015-12-02.
  15. Liu, Meng; Wu, Chengdong; Zhang, Yunzhou (2008-07-01). "Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature". 2008 Chinese Control and Decision Conference. pp. 5287–5291. doi:10.1109/CCDC.2008.4598340. ISBN   978-1-4244-1733-9. S2CID   8085227.
  16. "Object Recognition from Local Scale-Invariant Features - Google Scholar". scholar.google.com. Retrieved 2015-11-29.
  17. "Salient Points for Content Based Retrieval - Google Scholar". scholar.google.com. Retrieved 2015-12-02.
  18. "Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection - Google Scholar". scholar.google.com. Retrieved 2015-12-02.