Corner Detection

tags: image processing

Corner are the most important features of an object, detecting the corners let’s you do matching to the object for example if its pose changes, it can also used for motion tracking, it has many important applications.

Moravec Corner Detector

If I looked through a small window and shifted the image a bit, if the change in intensity between the two “looks” then what I looked at was a corner. The window function is the same size as my image but it only gives a value of 1 in the place where I want to check the edge, and gives 0 elsewhere.

We apply the equation for four shifts and we take the minimum number between them, if it is a large number then most probably what I looked at was a corner. - according to Moravec.

We calculate the cornerness of all the pixels by the method stated above, and then apply thresholding so only pixels with high cornerness values are taken: $C(x,y)=min(E_{x,y}(u,v))$ After thresholding we apply non-maximal suppression to find local maxima of all the corners and reduce the detected corners to a single pixel.

Problems with Moravec

There was 3 major problems in Moravec’s corner detector:

1. Due to our window being a binary function, the $E$ function can be noisy since we look at everything and the picture may have noise.
2. We only consider shift in $45°$ direction
3. Only the minimum value of E is taken into consideration And Harris came to fix these problems.

Harris Corner detector

The Harris corner detector fixes the problems of the Moravec detector by introducing:

1. A smooth Gaussian window, to give a smoother response
2. Consider all shifts by using Taylor expansion
3. We don’t take the minimum value, we investigate the shape of the function.

Applying Taylor-expansion to the error function

$M$ here is called the auto-correlation/structure tensor. It is called the structure tensor because after doing SVD to it, it decomposes into a rotation and scaling matrices that represent the eigen vectors and eigen values of this matrix.

Also it can be thought as fitting an ellipse to the gradient points of the image. Remember the MIT lecture.

If we draw $u^{T}Mu=1$, we will get a shape of an ellipse whose principal axis are as the following image It can be confusing at first why the larger eigen value has the shorter axis, but it is because the larger eigen value represents a higher value derivative which represent a faster change which means a faster increase in error to the value 1. The error here is the difference in intensity values.

Corner Response

Instead of calculating the eigen values or graphing the ellipse, we can simply calculate the corner response by: $R=det(M)-k\ast trace(M{)}^2$ This will give a value for some pixels cornerness and after that we can apply thresholding and non-maximal suppression to get single pixels that represent the corners.

NOTE: In the lab, non-maximal suppression was done by an morphological opening operation

NOTE: We know that the cornerness is for some pixel because we use a window function that is only applied to the region of the pixel we are trying to calculate its cornerness.

Variation effect on Harris Corner detector

1. Change in intensity

Since the structure tensor only depends on the derivatives, the corner detector is invariant to intensity shift, but it is variant to intensity shift.

2. Rotation variance

Corner response is invariant to intensity changes, but the eigen vectors will change, their values won’t.

3. Image scaling

The corner detector is variant to scale changes, because scaling a corner much can make it look like an edge if the window is small.

There is a way for scale invariant detection and it is to use different window sizes.

Feature matching

After we have found the features, we will have to match them, the simplest solution is to match upon the intensities of the neighbor pixels. This is not robust to brightness changes.