de-kAn-'str&kt

In 2007, a very nice implementation of a variational implementation of optical flow was described in: A Duality Based Approach for Realtime TV-L1 Optical Flow by C. Zach et. al. I won’t get into the details too much, but the formulation is described by this equation:

E = int_?{?|I0(x) ? I1(x + u(x))| + |?u| dx}

If you are familiar with the seminal work of Horn and Schunck, you will notice it is fairly similar to their variational formulation:

min_u{ int_?{ (|?u1|^2 + |?u2|^2) d? } + ? int_?{ ((I1(x + u(x)) ? I0(x))^2) d? }

And although it looks incredibly simple now, it is in fact fairly difficult computationally since now both terms are not continuously differentiable. To overcome this difficulty, they follow the work of Rudin-Osher-Fatemi energy for total variation image denoising.

Another big contribution comes in their implementation on the GPU. By linearization of the generally non-convex energy functional shown above, the problem is reduced to a pixel-wise convex energy minimization problem. Additionally, by employing coarse-to-fine image pyramids, they are able to account for both small and large movements. Luckily, graphics cards are great at doing both of these sorts of computations very quickly. You can find a release of their implementation here.

In 2009 at the upcoming British Machine Vision Conference, Manuel Werlberger et. al will detail a new formulation which introduces an anisotropic regularization based on the robust Huber norm instead of the total variation regularization term. This extension derives from a key observation: motion discontinuities often occur along object boundaries. By using image-derived information from large gradients, discontinuities from over-smoothing along object boundaries are preserved.

Manuel has also released his code on the aforementioned website. However, since I have been stuck in the world of Matlab, I decided to work on an interface to this library encased in a Matlab mex file. You will need to have installed CUDA, Matlab 2008b or higher, and have successfully installed the CUDA plugin.

For now, it suffers one very big problem: you will receive a segmentation fault if you remove the function. Though, I have been in contact with Manuel and hopefully we’ll figure it out. I’ll post back here on any developments.

[UPDATE] No contact from Manuel in awhile but I suspect he must be very busy. I have played with this library enough now to see that there a a few memory problems within the flowlib library itself not appropriately deleting device memory. There is still a problem with the flowlib destructor on win32 as well. If you are going to calculate optical flow on many images, you will most likely run into the same problems I did. Otherwise, you should not have any problems.

[UPDATE 2] The newest source on Manuel’s website is rock solid!  Get it!

[...]

Changchang Wu has a beautiful implementation of David Lowe’s scale invariant feature transform (SIFT) inspired by Andrea Vedaldi’s sift++ and Sudipta N Sinha et al’s GPU-SIFT. Adam Chapman has also made a MATLAB mex version which will allow you to pass in the filename of an image and retrieve the SIFT descriptors and keys as well as perform the matching. If that sounds like a lot of people have implemented this algorithm, then check this out.

I had tried using Adam Chapman’s version though, unfortunately, I already had my images loaded into the MATLAB workspace after performing some manipulations and didn’t want to keep writing/reading from disk, thinking that it would be a waste of computation time. I was also processing a lot of images in turn and was running into a lot of crashes, perhaps from continually loading and unloading the library? I haven’t seen anyone complain about this version on the mathworks site, so maybe it is just me.

In finding a way to avoid writing and reading to disk, I did not foresee a problem in the way MATLAB and OpenGL handle their image data. After a brief exchange with Changchang Wu, he led me on to the problem of needing the data in row major as opposed to column major format. As it turns out, the overhead of converting the image to row major is slightly worse than writing and reading the image to disk (at least for an 800×600 with jpeg compression) with the SiftGPU library. Though, there is probably a better way of doing this than in MATLAB, (like most tasks).

Not all is lost though (I could have been sleeping!), I slipped in another simple extension of Adam Chapman’s build which will allow you to keep the SiftGPU library loaded in memory and process as many images as you like without fear of crashing (or is it just me?). I’ve also included a demo app which shows how to do this for a grayscale and rgb image and shows the results in timing on a few different ways of finding the sift features. It also includes V340 of the SiftGPU library which will let you do matching on the GPU!

You can download it here.

[update 25/10/10]:  you can get an updated download with the yasift files here.

To run, first compile:

>> mex -setup
>> mex -c yasift.cpp
>> mex yasift.cpp

Now try out the demos:

>> yasiftdemo
>> yasiftmatchdemo

The general idea is to first open or initialize the library by doing:

>> yasift(‘open’)

Then you can set the parameters like so (check out Adam Chapmans .doc file for possible settings):

>> yasift({‘e’, ’10′, ….})

Now you are ready to process any images:

>> img = imread(‘frame0.jpg’);
>> [desc keys] = yasift(img);
>> [desc keys] = yasift(‘frame1.jpg’);
>> [desc keys] = yasift(‘frame2.jpg’);
>> [desc keys] = yasift(‘frame3.jpg’);

You can also do matching by passing in two images at once:

>> img1 = imread(‘frame0.jpg’);
>> img2 = imread(‘frame1.jpg’);
>> [desc1 keys1 desc2 keys2 matches] = yasift(img1, img2);

When you are done, unload the library:

>> yasift(‘destroy’)

I sometimes find that the actual mex file is still in memory and can be cleared with a clear all command.

Hope it works for you

[...]