29

Lots of resources say that there are two types optical flow algorithms. And Lucas-Kanade is a sparse technique, but I can't find the meanings of sparse and dense? Can some one tell me what is the difference between dense and sparse optical flow?

nbro
  • 15,395
  • 32
  • 113
  • 196
Yücel Ceylan
  • 382
  • 1
  • 5
  • 10

6 Answers6

40

The short explanation is, sparse techniques only need to process some pixels from the whole image, dense techniques process all the pixels. Dense techniques are slower but can be more accurate, but in my experience Lucas-Kanade accuracy might be enough for real-time applications. An example of a dense optical flow algorithm (the most popular) is Gunner Farneback's Optical Flow.

To get an overview of the flow quality look at the benchmark page e.g. the KITTI or the Middleburry dataset

Tobias Senst
  • 2,665
  • 17
  • 38
Rui Marques
  • 8,567
  • 3
  • 60
  • 91
  • @Stefan Karlsson (see below on this page) says that LKT is a dense optical flow algorithm. While your answer is the most upvoted but says the exact opposite. Is he incorrect? – LandonZeKepitelOfGreytBritn Jun 26 '17 at 17:22
  • I think who is correct is debatable. Maybe the more correct terms would be sparser and denser. You can read in this article how LKT produced sparse flow maps (when compared to other algorithms). http://ai2-s2-pdfs.s3.amazonaws.com/1e8b/2c16e87e1bda7289506670b6f716de8a99a2.pdf – Rui Marques Jun 26 '17 at 17:39
  • 1
    The article mentioned in the previous comment is "Recovering Motion Fields: An Evaluation of Eight Optical Flow Algorithms" (in case the link goes down). – Rui Marques Jan 25 '18 at 08:45
  • @LandonZeKepitelOfGreytBritn, the Lucas-Kanade optical flow technique is dense. However, the KLT algorithm (T from Tomasi, not T from Tracking) is a sparse optical flow technique. The work of Tomasi dealt with the unstable points of Lucas-Kanade by omitting them. It is not a debatable. The LKDemo in OpenCV is poorly named – Stefan Karlsson Oct 14 '19 at 04:27
13

Sparse optical flow gives you the flow vectors of some "interesting features" within the image.

Dense optical flow attempts to give you the flow all over the image - up to a flow vector per pixel.

Martin Thompson
  • 16,395
  • 1
  • 38
  • 56
5

First of all, Lucas-Kanade is NOT a sparse optical flow technique. The reason so many believe it is, is due to a wide spread misunderstanding. The misconception became an accepted truth since the very first implementation of Lucas-Kanade in OpenCV was labelled as SPARSE, and still is to this day. The arguments to why Lucas-Kanade should be called sparse, apply to any dense flow algorithm. If you insist that Lucas-Kanade is sparse, then all flow algorithms are sparse and there is no point in distinguising them.

Sparse flow is the same as point tracking, dense flow consists of vectors over the video, indicating estimates of motion of fixed positions.

You can read more about all of this in this tutorial that I wrote, where I also show how Lucas-Kanade is just as dense as any other algoritm out there (although not as accurate).

Stefan Karlsson
  • 1,092
  • 9
  • 21
4

Sparse optical flow - Lucas-Kanade method computes optical flow for a sparse feature set (e.g. corners detected using Shi-Tomasi algorithm). Dense optical flow - Gunner Farneback's algorithm computes the optical flow for all the points in the frame. This is explained in "Two-Frame Motion Estimation Based on Polynomial Expansion" by Gunner Farneback in 2003.

Example implementation of can be found in opencv docmentation here

razmik
  • 199
  • 1
  • 7
  • 1
    While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. Please read this [how-to-answer](http://stackoverflow.com/help/how-to-answer) for providing quality answer. – thewaywewere Jun 26 '17 at 07:19
3

Sparse optical flow works on features(edges,corners etc). Dense optical flow is designed to work on all the pixels. The advantage of the first is that it is generally faster while the second can give estimates for more pixels than the first.

Mircea Paul Muresan
  • 628
  • 1
  • 9
  • 23
2

Sparse optical flow gives you the velocity vectors for some interesting (corner) points, these points are extracted beforehand using algorithms like Shi-Tomashi, Harris etc. The extracted points are passed into your [optical flow function] along with the present image and next image. Any good optical flow function should check the optical flow in the forward direction using the above corner points and also back track to cross check if it is following the same points.

On the other hand, dense optical flow can referred from here: http://www.cs.toronto.edu/~fleet/courses/cifarSchool09/flowChapter05.pdf

Gopal Sharma
  • 21
  • 2