Detecting corners

Let’s use a corner detector as an example. Corner detection is an important image processing task: corners are good things to track over several frames of an image sequence. Once you’ve tracked them you can infer 3-d positions for them.

One classic method of corner detection was developed by Harris and Stephens – it performs well, but it relatively straightforward computationally. Which is not unsurprising, since that paper was written in 1988! Fundamentally a 2×2 matrix is generated for each pixel in the image, and some computations are performed on the matrix.

From this, Shi and Tomasi demonstrated (in 1994) a similar detector, which involves calculating a very similar matrix and using the minimum of its two eigenvalues as a measure of “cornerness”. The Shi-Tomasi detector is interesting as (as the paper’s title implies) they define features which are good to track.

In these pages, we’ll build a corner detector from scratch in the following steps:

• using a very high-level description in Octave
• developing a low-level description, still in Octave, which produces the same results (or close enough)
• translating that octave description into VHDL, and simulating to show it produces the same answers as the low-level Octave
• targetting the VHDL at an FPGA to see some real results.

We will use the same image as before for the test case:

[img_assist|nid=45|title=Test image|link=popup|align=none|width=600]

Begin at the beginning

Intuitively, a corner is the meeting of two lines. If we were to measure the horizontal edginess and the vertical edginess of each region of the image, then by combining these we should be able to establish corners. This is how the Shi-Tomasi corner detector works.

Finding edges

The classic method of detecting edges is using the Sobel edge detector we met before.

Here’s some Octave code which calculates the horizontal and vertical “edginess” images, which we’ll call Ix and Iy. The corner detector requires three measures, generated by multiplying each pixel in Ix by the corresponding pixel in Ix and Iy, and each pixel in Iy by Ix and Iy. This gets us three images Ix2, Iy2 and Ixy – we also have Iyx, but that’s the same as Ixy :)

[matlab]
sobelx=[1 2 1; 0 0 0; -1 -2 -1];
Ix=filter2(sobelx ,img);
Iy=filter2(sobelx’,img);
[/matlab]

We then smooth out these images – in our case by convolving with a 3×3 matrix of all ones. Other methods are sometimes used, which are more resource intensive, but this will suit well for now.

[matlab]
window_size=1; % increase this for a bigger smoothing window
window_range=-window_size:window_size;
mask=ones(length(window_range));
a=filter2(mask, Ix2);
b=filter2(mask, Iy2);
c=filter2(mask, Ixy);
[/matlab]

For each pixel in the scene, we now create a matrix made up of pixels taken from a, b, and c.

Z = [ a b ]
    [ b c ]

And the cornerness measure is the minimum of the eigenvalues of that matrix.

What’s an eigenvalue?

Well, for our purposes, it suffices to know that you can calcuate the 2 eigenvalues of a 2×2 matrix thus (see this Wikipedia page for details):

let ix2 = ix*ix and iy2 = iy*iy and ixy=ix*iy

then the eigenvalues are given by (ix2+iy2)/2 +/- sqrt(4*ixy*ixy + (ix2-iy2)^2)/2

The /2 s can be dropped as we are not interested in the absolute values. And as we are only interested in the smaller of the two values, we can calculate cornerness as:

cornerness = ix2+iy2 - sqrt(4*ixy*ixy + (ix2-iy2)^2)

Simple!

Doing it in Octave

Here’s the Octave code, and the results:

[matlab]

c1=(a+b);
c2=(4 * (c.*c) + ((a-b).^2)).^0.5;
cornerness=c1-c2;
[/matlab]

imshow(cornerness) gives a result like this:

[img_assist|nid=57|title=Cornerness|desc=|link=node|align=none|width=600]

This image doesn’t localise the corners – it produces a bright patch around them. The next stage is to find the “peaks” of those patches and isolate them to a single pixel.

All the code from this series is available via git from here