Saturday, June 28, 2008

Interest Points

Recent algorithms for detection of scale and rotation invariant interest points have produced fantastic advances in many computer vision fields. For instance, explicit segmentation is no longer required in some object recognition applications.

Interest points are typically computed as local extrema in the scale-space of an appropriate response function. The celebrated SIFT by D. Lowe is based on the Laplacian, which is approximated by differences of gaussians in an image pyramid.

I'd like to include in the easyVision library a reference implementation of a good interest point detector. Some experiments indicate that the determinant of the Hessian obtains very satisfactory results. In a first stage I am not very worried about speed, so we will explicitly work with the full image smoothed at different levels, without any downsampling.

The following screenshot shows the interest points detected on a 640x480 image by analyzing 15 scales up to sigma=25. Blobs of different sizes are detected with excellent accuracy.

Woody Allen's Interest Points

This extremely unoptimized algorithm is however quite fast. With half-size images (320x240) we get more than 15fps in a modern laptop, and at 640x480 it runs at 3fps. This is of course not real-time, although it could be acceptable for some live video applications. In any case, note that the program currently runs single threaded. Most of the time is required by the Gaussian filters, which can be done in parallel. (This is the next step I will try to solve, but first I must consolidate a few things in the library.)

A simple local descriptor based on local gradient distributions is also computed for each point, which can be used for object recognition and image matching:

(The current implementation of the rotation invariant descriptor, based on explicit image warping, is quite slow. In the above examples we work with a scale-only invariant descriptor.)

I am currently preparing more detailed installation instructions and other information about the library.

In a future post I will describe some low level algorithms implemented directly in Haskell.