Corner detection, or the more general terminology interest point detection, is an approach used within computer vision systems to extract certain kinds of features from an image. Corner detection is frequently used in motion detection, image matching, tracking, image mosaicing, panorama stitching, 3D modelling and object recognition.
This code has also been incorporated in Accord.NET Framework, which includes the latest version of this code plus many other statistics and machine learning tools. Introduction
One of the firsts operators for interest point detection was developed by Hans P. Moravec in 1977 for his research involving the automatic navigation of a robot through a clustered environment. It was also Moravec who defined the concept of "points of interest" in a image and concluded these interest points could be used to find matching regions in different images.
The Moravec operator is considered to be a corner detector because it defines interest points as points where there are large intensity variations in all directions. This often is the case at corners. It is interesting to note, however, that Moravec was not specifically interested in finding corners, just distinct regions in an image that could be used to register consecutive image frames.
The Harris Operator
This operator was developed by Chris Harris and Mike Stephens in 1988 as a processing step to build interpretations of a robot's environment based on image sequences. Like Moravec, they needed a method to match corresponding points in consecutive image frames, but were interested in tracking both corners and edges between frames.
Harris and Stephens improved upon Moravec's corner detector by considering the differential of the corner score with respect to direction directly. The Harris corner detector computes the locally averaged moment matrix computed from the image gradients, and then combines the Eigenvalues of the moment matrix to compute a corner measure, from which maximum values indicate corners positions.
A more detailed explanation with diagrams and examples (and a sample code written in Java) can also be found here.
Source Code
Below is the source code for the Harris Corners Detector algorithm. The code utilizes the excellent AForge.NET Framework and is also molded in its same standards.
/// <summary>
/// Process image looking for corners.
/// </summary>
///
/// <param name="image">Source image data to process.</param>
///
/// <returns>Returns list of found corners (X-Y coordinates).</returns>
///
/// <exception cref="UnsupportedImageFormatException">
/// The source image has incorrect pixel format.
/// </exception>
///
public unsafe List<IntPoint> ProcessImage(UnmanagedImage image)
{
// check image format
if (
(image.PixelFormat != PixelFormat.Format8bppIndexed) &&
(image.PixelFormat != PixelFormat.Format24bppRgb) &&
(image.PixelFormat != PixelFormat.Format32bppRgb) &&
(image.PixelFormat != PixelFormat.Format32bppArgb)
)
{
throw new UnsupportedImageFormatException("Unsupported pixel format of the source image.");
}
// make sure we have grayscale image
UnmanagedImage grayImage = null;
if (image.PixelFormat == PixelFormat.Format8bppIndexed)
{
grayImage = image;
}
else
{
// create temporary grayscale image
grayImage = Grayscale.CommonAlgorithms.BT709.Apply(image);
}
// get source image size
int width = grayImage.Width;
int height = grayImage.Height;
int srcStride = grayImage.Stride;
int srcOffset = srcStride - width;
// 1. Calculate partial differences
float[,] diffx = new float[height, width];
float[,] diffy = new float[height, width];
float[,] diffxy = new float[height, width];
fixed (float* pdx = diffx, pdy = diffy, pdxy = diffxy)
{
byte* src = (byte*)grayImage.ImageData.ToPointer() + srcStride + 1;
// Skip first row and first column
float* dx = pdx + width + 1;
float* dy = pdy + width + 1;
float* dxy = pdxy + width + 1;
// for each line
for (int y = 1; y < height - 1; y++)
{
// for each pixel
for (int x = 1; x < width - 1; x++, src++, dx++, dy++, dxy++)
{
// Convolution with horizontal differentiation kernel mask
float h = ((src[-srcStride + 1] + src[+1] + src[srcStride + 1]) -
(src[-srcStride - 1] + src[-1] + src[srcStride - 1])) * 0.166666667f;
// Convolution vertical differentiation kernel mask
float v = ((src[+srcStride - 1] + src[+srcStride] + src[+srcStride + 1]) -
(src[-srcStride - 1] + src[-srcStride] + src[-srcStride + 1])) * 0.166666667f;
// Store squared differences directly
*dx = h * h;
*dy = v * v;
*dxy = h * v;
}
// Skip last column
dx++; dy++; dxy++;
src += srcOffset + 1;
}
// Free some resources which wont be needed anymore
if (image.PixelFormat != PixelFormat.Format8bppIndexed)
grayImage.Dispose();
}
// 2. Smooth the diff images
if (sigma > 0.0)
{
float[,] temp = new float[height, width];
// Convolve with Gaussian kernel
convolve(diffx, temp, kernel);
convolve(diffy, temp, kernel);
convolve(diffxy, temp, kernel);
}
// 3. Compute Harris Corner Response Map
float[,] map = new float[height, width];
fixed (float* pdx = diffx, pdy = diffy, pdxy = diffxy, pmap = map)
{
float* dx = pdx;
float* dy = pdy;
float* dxy = pdxy;
float* H = pmap;
float M, A, B, C;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++, dx++, dy++, dxy++, H++)
{
A = *dx;
B = *dy;
C = *dxy;
if (measure == HarrisCornerMeasure.Harris)
{
// Original Harris corner measure
M = (A * B - C * C) - (k * ((A + B) * (A + B)));
}
else
{
// Harris-Noble corner measure
M = (A * B - C * C) / (A + B + Accord.Math.Special.SingleEpsilon);
}
if (M > threshold)
{
*H = M; // insert value in the map
}
}
}
}
// 4. Suppress non-maximum points
List<IntPoint> cornersList = new List<IntPoint>();
// for each row
for (int y = r, maxY = height - r; y < maxY; y++)
{
// for each pixel
for (int x = r, maxX = width - r; x < maxX; x++)
{
float currentValue = map[y, x];
// for each windows' row
for (int i = -r; (currentValue != 0) && (i <= r); i++)
{
// for each windows' pixel
for (int j = -r; j <= r; j++)
{
if (map[y + i, x + j] > currentValue)
{
currentValue = 0;
break;
}
}
}
// check if this point is really interesting
if (currentValue != 0)
{
cornersList.Add(new IntPoint(x, y));
}
}
}
return cornersList;
}
Using the code
Code usage is very simple. A Corners Marker filter from the AForge Framework can be used to directly draw the detected interest points in the original image as it would be usual within the framework.
// Open a image
Bitmap image = ...
// Create a new Harris Corners Detector using the given parameters
HarrisCornersDetector harris = new HarrisCornersDetector(k);
harris.Threshold = threshold;
harris.Sigma = sigma;
// Create a new AForge's Corner Marker Filter
CornersMarker corners = new CornersMarker(harris, Color.White);
// Apply the filter and display it on a picturebox
pictureBox1.Image = corners.Apply(image);
Sample application
The accompanying sample application is pretty much self-explanatory. It performs the corners detection in the famous Lena Söderberg's picture, but can be adapted to work with other pictures as well. Just add another image to the project settings' resources and change the line of code which loads the bitmap.
It is also very straightforward to adapt the application to load arbitrary images from the hard disk. I have opted to leave it this way for simplicity.
References
P. D. Kovesi. MATLAB and Octave Functions for Computer Vision and Image Processing. School of Computer Science & Software Engineering, The University of Western Australia.
D. Parks and J. P. Gravel. Corner Detectors: The Harris/Plessey Operator. Web. 11 May. 2010.
J. Hutton and B. Dowling. Computer Vision Demonstration Website. Electronics and Computer Science, University of Southampton
H. P. Moravec. Towards Automatic Visual Obstacle Avoidance. Proc. 5th International Joint Conference on Artificial Intelligence, pp. 584, 1977.
H. P. Moravec. Visual Mapping by a Robot Rover. International Joint Conference on Artificial Intelligence, pp. 598-600, 1979.
C. Harris and M. Stephens. A Combined Corner and Edge Detector. Proc. Alvey Vision Conf., Univ. Manchester, pp. 147-151, 1988.
Wikipedia contributors. "Corner detection." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 5 May. 2010. Web. 11 May. 2010.
Disclaimer
Before using any information, applications or source code available in this article, please be sure to have read the site usage disclaimer.
