Category Archives: Uncategorised

Image processing #002

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

Change of plan – from Scilab to Octave

OK, I started out on Scilab, but got frustrated! It’s too different to Matlab – which has its flaws, but at least I’m familiar with them. I’m always going to be annoyed by the 1-based indexing of Matlab, but I’ve learned to deal with it.

I’ve been using Matlab for the last 15 years at work, the syntax is built into my fingers. Using // for comments (the Scilab notation) felt bizarre! This despite me being a proficient C++ programmer who uses double-slash comments all the time – it’s just wrong in (what my mind was telling me was still) a Matlab script.

So I’ve turned to Octave for my home-based image-processing work. Octave was aimed at being more of a Matlab-clone from the start, whereas Scilab was designed as an open-source competitor, but doing things in its own way. Familiarity is a powerful motivator when tool selection is concerned!

Will this reduce the spam?

Thanks to Ignacio Segura I have a new anti-spambot measure. Users won’t notice it (unless they browse with CSS turned off, or other such unusualness). Hopefully this will mean that a) I don’t have to “disapprove” loads of comment span every day, and b) I can allow anonymous commenting without having to approve it before it becomes visible.

If this doesn’t work, then maybe I’ll use one of the more formally defined modules like Spamicide or Hidden CAPTCHA, although they seem to do much the same!

We’ll see….