Lucas-Kanade Algorithm

The Lucas-Kanade method is an algorithm for estimating optical flow, the apparent motion of brightness patterns between two consecutive video frames, at a sparse set of chosen points rather than across the whole image. It assumes that the true motion is essentially constant within a small neighborhood of each point being tracked, which turns the otherwise underdetermined problem of solving for motion from a single pixel's brightness change into an overdetermined system of equations from every pixel in that neighborhood; the algorithm then finds the horizontal and vertical velocity that best fits all of those equations at once using the method of least squares. Bruce Lucas and Takeo Kanade introduced the technique in 1981 in a paper on image registration for stereo vision, and its local, per-point formulation makes it fast enough to track a modest number of features in real time, at the cost of failing inside large featureless regions where a neighborhood's brightness pattern gives it too little information to pin down a single motion.