Coarse-to-fine Optical Flow (Lucas & Kanade)

OPTICAL FLOW

We are always interested in finding the movement of objects from videos, optical flow is one of the most famous methods to do this. Optical flow has lots of uses, such as tracking object, camera correction, mosaics and so on.

All optical flow methods are based on the following assumptions:

  • Color constancy (brightness constancy for single-channel images);
  • Small motion.

With these assumptions, if we have two images (say two adjacent frames of a video), what we need to do is simply find pixel correspondences between the two images. Because of color constancy, we don’t need to consider the RGB value’s change between two images, and because of small motion, we can find the corresponding point of a pixel within a very little neighborhood.

Assume brightness constancy:

111

Assume small motion: (first order Taylor expansion)

222

Then we can get the Constraint Equation of Optical flow:

333

444

HORN & SCHUNCK METHOD

http://en.wikipedia.org/wiki/Horn%E2%80%93Schunck_method is the detail of Horn&Schunck method.

First I calculate fx, fy, ft using derivative masks:

555

  • Apply mask1 to both images, add the responses to get fx;
  • Apply mask2 to both images, add the responses to get fy;
  • Apply mask4 to image1, apply mask3 to image2, add the responses to get ft.

Repeat calculating the following values until converges.

666

777

In which, Xav is the average value of X‘s four neighbors (details can be found in following code).

LUCAS & KANADE METHOD

http://en.wikipedia.org/wiki/Lucas_Kanade_method Here’s detail of Lucas&Kanade method.

Lucas&Kanade’s methods uses small windows (in my code, I used 3 by 3 window), and least squares method.

888

999

1212

1313

Because when implementing coarse-to-fine, I used Lucas&Kanade method, so you can find the implementation of this method in the following coarse-to-fine code.

COARSE-TO-FINE

Because the small motion assumption, regular optical flow methods work bad if the object we are tracking moves a long distance, under this circumstance, coarse-to-fine method helps a lot.

What coarse-to-fine is simply building image pyramids for each images, and by doing optical flow on each layer of pyramid, to get rid of the small motion constraint. For example, if we get a 3-layer pyramid, then one pixel in the top layer, can represent 4 pixels of distance in the lowest layer. The following figure shows how this method works:

1414

It’s simple, and works very well.

CODE

https://github.com/xingdi-eric-yuan/optical-flow

 TEST RESULT

Two test images: car and table, I’m using the flow visualization code from Baker et al. 2007.

1515

Car test result:

car_input

Horn & Schunck result:

hs1

Lucas & Kanade result:

lk1

Lucas & Kanade with Coarse-to-fine result:

c1

 Table test result:

table_input

 

Horn & Schunck result:

hs2

Lucas & Kanade result:

lk2 Lucas & Kanade with Coarse-to-fine result:

c2

p.s.   I would like to thank tpys for pointing out a bug for me. Thanks buddy.

This entry was posted in Algorithm, OpenCV and tagged , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

19 Comments

  1. Avi
    Posted July 13, 2014 at 10:56 am | Permalink

    The same coarseToFine function can be used for Horn and Schunck also, right?

    • Eric
      Posted July 13, 2014 at 1:21 pm | Permalink

      Yeah I think so.

  2. tpys
    Posted August 6, 2014 at 8:34 am | Permalink

    It’s easy to implement with your tutorial. I found you saved optical flow as two txt file in your code, But how to visuliza them? Can you explain more details, thanks!

    • Eric
      Posted August 6, 2014 at 5:12 pm | Permalink

      Check ur email 🙂

      • Justin
        Posted May 23, 2015 at 12:29 pm | Permalink

        Could you also send me the method or code for the flow visualization?

      • Allen
        Posted July 3, 2016 at 9:45 am | Permalink

        Can you also help me for the flow visualization? Thanks!

  3. tpys
    Posted August 6, 2014 at 10:12 pm | Permalink

    Hi Eric, There seem to be a mistake in your corase to fine code, line 191~192 ‘warped1.copyTo(pyr1[i]), warped2.copyTo(pyr2[i])’. Because when I comment these lines, still get same result.

    • Eric
      Posted August 6, 2014 at 11:45 pm | Permalink

      Ok I’ll check it, thanks for pointing out.

  4. Unais
    Posted November 26, 2014 at 2:29 pm | Permalink

    How can I do seam carving using Gradient Vector Flow

  5. Sam
    Posted January 11, 2015 at 3:41 pm | Permalink

    Coarse 2 fine is implementation when both camera and object is on motion??

    Sorry, if lame question. I am just introduced to thi topic

    • Eric
      Posted January 12, 2015 at 3:57 am | Permalink

      Hi Sam,
      Coarse to fine is just a method which reduces the computation(pyramid) and improves the result(interpolation). We actually don’t care whether both the camera and object are on motion, because what is represented by the two images are relative displacements of each pixel.

  6. Francisco
    Posted April 4, 2015 at 6:27 pm | Permalink

    Can you send me the code for get result store in for example .png?

    • Eric
      Posted April 13, 2015 at 4:18 pm | Permalink

      Hi Francisco,

      Actually you can directly use OpenCV FileStorage methods to store result into, say, XML file, or maybe you want to use imwrite method.

  7. Rjv
    Posted July 8, 2015 at 1:42 am | Permalink

    You the optical flow in two different text files. Can you please mail me code to visualize the optical flow from those text files?

  8. Chicku
    Posted May 28, 2016 at 9:20 am | Permalink

    How to implement it in a video?

  9. davood
    Posted July 18, 2016 at 10:49 am | Permalink

    Hi Eric
    I want to realize your code. Do you have any documentation or guidance for your code?

    thank you

  10. Jin
    Posted July 27, 2016 at 1:57 am | Permalink

    Can you also help me for the flow visualization? Thanks!

  11. kisoo
    Posted September 20, 2016 at 5:10 am | Permalink

    two file of U.txt,V.txt , how to visuliza them
    please I want to display method of them.

  12. Ali
    Posted November 3, 2016 at 5:47 pm | Permalink

    Hi,
    thanks for your helpful document.

    these methods are methods of optical flow calculation.

    I want to use Histogram of Optical Flow(HOF) for my own data.

    do you have any code for HOF???

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*