Harris Corner Detector: Unveiling the Magic of Image Feature Detection

By Fouad Sabry

What is Harris Corner Detector

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. 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. Since then, it has been improved and adopted in many algorithms to preprocess images for subsequent applications.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Harris corner detector

Chapter 2: Corner detection

Chapter 3: Structure tensor

Chapter 4: Harris affine region detector

Chapter 5: Lucas-Kanade method

Chapter 6: Hessian matrix

Chapter 7: Geometric feature learning

Chapter 8: Tensor density

Chapter 9: Mehrotra predictor-corrector method

Chapter 10: Discrete Laplace operator

(II) Answering the public top questions about harris corner detector.

(III) Real world examples for the usage of harris corner detector in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Harris Corner Detector.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 13, 2024

Book preview

Chapter 1: Harris corner detector

Commonly employed in computer vision algorithms for corner extraction and feature inference, the Harris corner detector is a type of corner detection operator. Chris Harris and Mike Stephens initially launched it in 1988, after refining Moravec's corner detector. Since then, it has been refined and implemented in a wide variety of algorithms used to prepare images for use in other contexts.

A corner is a location where there are two main tangential edges meeting. One way to think about a corner is as the meeting point of two edges, where an edge represents a distinct shift in tonal value inside an image. Important picture features, or interest points, are corners because they remain unchanged when the image is translated, rotated, or illuminated. The corners of an image may only make up a small fraction of the whole, but they contain some of the most crucial features for restoring image information and can be used to reduce the amount of data that needs to be processed for tasks like motion tracking, image stitching, building 2D mosaics, stereo vision, image representation, and so on.

Many various corner detectors have been developed by researchers in order to extract the image's corners, but the Kanade-Lucas-Tomasi (KLT) operator and the Harris operator stand out as the simplest, most efficient, and most trustworthy. These two common approaches are related to and dependent on the local structural matrix. The Harris corner detector is preferred for use in stereo matching and picture database retrieval because it maintains high accuracy despite changes in light and rotation. The Harris corner detector is still a crucial and foundational method in many computer vision applications, despite its flaws and restrictions.

Without narrowing the scope, Here, 2-dimensional grayscale images are assumed.

Let this image be given by I .

Consider taking an image patch {\displaystyle (x,y)\in W} (window) and shifting it by {\displaystyle (\Delta x,\Delta y)} .

The SSD compares the distance between these two patches, denoted f , is a result of:

{\displaystyle f(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}}

{\displaystyle I(x+\Delta x,y+\Delta y)} can be approximated by a Taylor expansion.

Let I_{x} and I_y be the partial derivatives of I , such that

{\displaystyle I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y}

The approximation results from this.

{\displaystyle f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},}

whose answers can be represented by matrices:

{\displaystyle f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},}

where M denotes a tensor of structure,

{\displaystyle M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}}

Harris corner detection algorithms are often broken down into five stages.

Color to grayscale

Spatial derivative calculation

Structure tensor setup

Harris response calculation

Reduced suppression

To improve processing speed when using Harris corner detector on a color image, it is first converted to grayscale.

Grayscale image pixel values are just the weighted sums of the corresponding RGB values, {\displaystyle \sum _{C\,\in \,\{R,G,B\}}w_{C}\cdot C} , for instance where,

{\displaystyle w_{R}=0.299,\ w_{G}=0.587,\ w_{B}=1-(w_{R}+w_{G})=0.114.}

Next, The derivatives of interest are those with regard to x and y, and we will determine them, {\displaystyle I_{x}(x,y)} and {\displaystyle I_{y}(x,y)} .

With {\displaystyle I_{x}(x,y)} , {\displaystyle I_{y}(x,y)} , we can construct the structure tensor M .

For {\displaystyle x\ll y} , one has {\displaystyle {\tfrac {x\cdot y}{x+y}}=x{\tfrac {1}{1+x/y}}\approx x.} In this step, Using that approximation, we get the least eigenvalue of the structure tensor:

{\displaystyle \lambda _{\min }\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {\det(M)}{\operatorname {tr} (M)}}}

with the trace {\displaystyle \mathrm {tr} (M)=m_{11}+m_{22}} .

The following is an alternative Harris response computation that is frequently utilized,

{\displaystyle R=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}=\det(M)-k\operatorname {tr} (M)^{2}}

where k is an empirically determined constant; {\displaystyle k\in [0.04,0.06]} .

Finding the local maxima as corners within the window, which is a 3 by 3 filter, allows us to select the best values to signify corners.

Detector of Harris-Laplace-Formed Corners

Corner Detector Utilizing Differential Morphological Decomposition

A Corner Detector Based on Multi-scale Bilateral Structure Tensors

Registration, Stitching, and Alignment of Images

2D Mosaics Creation

Reconstructing and modeling 3D scenes

Motion Detection

Object Recognition

Content-based image retrieval and indexing

Video Tracking

{End Chapter 1}

Chapter 2: Corner detection

In computer vision systems, corner detection is used to infer the nature of an image by extracting specific types of characteristics. Motion analysis, image registration, video tracking, mosaicing, panorama stitching, 3D reconstruction, and object recognition all make use of corner detection in one way or another. There is some duplication of effort between corner detection and interest point detection.

A corner is the point where two edges meet. One alternative definition of a corner is a point with two distinct edge directions immediately adjacent to it.

An interest point is a specific location inside a picture that can be accurately identified. An interest point is not limited to a corner, but might also be something like a local maximum or minimum in intensity, the termination of a line, or a spot on a curve where the curvature is at its maximum.

In practice, most corner detection approaches just detect interest spots, and the terms are used more or less interchangeably in the literature.

Various authors use the terms corner, interest point, and feature interchangeably, further clouding the discussion. Specifically, there are a number of blob detectors that can be called interest point operators, but are more commonly known as corner detectors. Also, the existence of ridge detection to identify linear objects is known.

Due to their inherent fragility, corner detectors typically necessitate the use of considerable amounts of redundancy in order to mitigate the impact of individual errors on the recognition process.

The quality of a corner detector can be gauged by testing its ability to identify the same corner in images that are otherwise comparable but have been subjected to transformations such as scaling, rotation, and lighting changes.

Correlation is a straightforward method for detecting corners in images, but it quickly becomes computationally expensive and inefficient. The method proposed by Harris and Stephens (below), which is an enhancement of a method proposed by Moravec, forms the basis of a popular alternative approach.

This approach, which dates back to the early days of corner recognition, uses a self-similarity threshold to identify corners. The technique examines the proximity of a patch centered on the pixel to other patches that overlap it extensively to determine if a corner is present. Similarity is calculated by summing the squared deviations (SSD) of the related pixels in each patch. When the number is smaller, there is greater agreement.

If the pixel is located in an area of consistent brightness, then neighboring patches will have a similar appearance. If the pixel is near an edge, the appearance of nearby patches perpendicular to the edge will vary significantly, whereas nearby patches parallel to the edge will change appearance just slightly. If the pixel is located on a multidirectionally variable feature, then none of the neighboring patches will share a common appearance.

As the minimum sum of squared differences (SSD) between a patch and its neighbors, the corner strength (horizontal, vertical and on the two diagonals). All surrounding patches will appear different if this value is high since the variation along all shifts will be equal to or greater than this value.

To determine whether or not a feature of interest is present at a given place, the corner strength number must be calculated for all possible locations.

According to Moravec, one of the major drawbacks of this operator is that it is not isotropic, meaning that it will mistakenly