Lucas-Kanade Optical Flow

Here’s a compact “how to think about it” guide tailored to your coding problem.

---

1. Background Knowledge

Optical flow describes the apparent 2D motion of image intensity patterns between two frames, usually represented as a vector field $(u(x,y), v(x,y))$ giving horizontal and vertical motion per pixel. The core assumption is brightness constancy: a point keeps the same intensity as it moves, so $I(x,y,t) = I(x+u, y+v, t+1)$.

By linearizing this assumption for small motions, you get the optical flow constraint equation:

$$I_x u + I_y v + I_t = 0$$

where $I_x, I_y$ are spatial derivatives and $I_t$ is the temporal derivative. This is one equation with two unknowns $(u,v)$ per pixel, so it is underdetermined.

Lucas–Kanade resolves this by assuming constant flow inside a small window around the pixel. That means all pixels in the window share the same $(u,v)$, giving many linear equations of the form $I_{xi} u + I_{yi} v = -I_{ti}$. Stacking them yields an overdetermined linear system $A$\mathbf{v}$= \mathbf{b}$ that can be solved in a least-squares sense.

---

2. Algorithm / General Approach

For a given window:

1. Collect image derivatives $(I_{xi}, I_{yi}, I_{ti})$ for each pixel in the window.
2. Form the matrix $A$ whose rows are $(I_{xi}, I_{yi})$, and vector $\mathbf{b}$ whose entries are $-I_{ti}$.
3. Solve the least squares problem:

$$\min_{\mathbf{v}} \|A\mathbf{v} - \mathbf{b}\|^2$$

which leads to the normal equations:

$$(A^T A)\mathbf{v} = A^T \mathbf{b}$$

4. Since $A^T A$ is $2\times 2$, directly solve for $\mathbf{v} = (u,v)^T$ via closed-form formulas (Cramer’s rule or explicit inverse).

Conceptually, your task is: “Given these derivative samples, compute the best-fitting constant motion vector $(u,v)$ over the window.”

---

3. Step-by-Step Strategy

Assume the problem gives you the derivatives for all pixels in a window, e.g. as arrays Ix, Iy, It or as a list of triplets.

1. Accumulate the components of $A^T A$ and $A^T b$

Let each sample $i$ in the window have derivatives $I_{xi}, I_{yi}, I_{ti}$.

Build the scalar sums:

• $S_{xx} =$\sum$_i I_{xi}^2$
• $S_{yy} =$\sum$_i I_{yi}^2$
• $S_{xy} =$\sum$_i I_{xi} I_{yi}$
• $S_{xt} =$\sum$_i I_{xi} I_{ti}$
• $S_{yt} =$\sum$_i I_{yi} I_{ti}$

Then:

• $A^T A =$\begin{pmatrix} S_{xx} & S_{xy} \ S_{xy} & S_{yy} \end{pmatrix}$
• $A^T$\mathbf{b}$= -\begin{pmatrix} S_{xt} \\ S_{yt} \end{pmatrix}$

2. Solve the 2×2 linear system

You need to solve:

$$\begin{pmatrix} S_{xx} & S_{xy} \\ S_{xy} & S_{yy} \end{pmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = -\begin{pmatrix} S_{xt} \\ S_{yt} \end{pmatrix}$$

Compute the determinant:

$$\Delta = S_{xx} S_{yy} - S_{xy}^2$$

If $|\Delta|$ is sufficiently large (non-degenerate), you can use:

det = S_xx * S_yy - S_xy * S_xy
u = (-S_xt * S_yy + S_xy * S_yt) / det
v = ( S_xx * (-S_yt) - S_xy * (-S_xt)) / det

This is just the analytic solution of the $2\times 2$ system.

3. Return the flow vector

Return $(u, v)$ as the optical flow for that window (often assigned to the center pixel).

---

4. Common Pitfalls

• Ill-conditioned $A^T A$ (aperture problem):

• If all gradients are in one direction or the region is flat (little texture), $\Delta$ is near zero and the system is not reliable.

• In practice, check $|\Delta|$ against a threshold; if too small, treat the flow as undefined or $(0,0)$.

• Sign mistakes:

• Remember that $\mathbf{b} = -I_t$, so $A^T$\mathbf{b}$= -\begin{pmatrix} S_{xt}\\ S_{yt}\end{pmatrix}$.

• A common bug is forgetting the minus sign, which flips motion direction.

• Overflow / precision:

• For large windows or many pixels, sums like $S_{xx}$ can become large; use a suitable numeric type (e.g., float64).

• Assuming the method handles large motion:

• Lucas–Kanade in this basic form assumes small motion; large displacements require pyramids or warping, which is beyond this specific coding task.

---

5. Time & Space Complexity

Let $N$ be the number of pixels in the window.

• Time complexity (per window):

• Computing all sums: $O(N)$.

• Solving the 2×2 system: $O(1)$.

• Total: $O(N)$ per window.

• Space complexity (per window):

• If derivatives are given as input and you only store accumulated sums and the flow vector, you need $O(1)$ extra space.

• If you store derivatives for all pixels in the window yourself, that is $O(N)$ input storage, but the algorithmic extra space is still $O(1)$.

Use this structure to write clean, incremental code: accumulate the five sums, form the 2×2 system, check the determinant, solve for $(u,v)$, and handle the degenerate case carefully.