Computer Vision MT25, Lucas-Kanade tracking

We have:

• An image $I$ (the game screen)
• A template $T$, which we wish to locate within the image (a small patch of Pac-Man)
• A guess of the current location of the template within the image, given by $W(\pmb x, \pmb p)$, where:
  • $\pmb x$ is an arbitrary point in the template
  • $W(\cdot, \pmb p)$ is a warp from the template coordinates to the image coordinates, parameterised by $\pmb p$
  • (e.g. $W$ is affine, mapping $x$ to $x + (t _ x, t _ y)$, which we hope to be the location of Pac-Man in image coordinates)

We want:

• Some update $\Delta \pmb p$ such that $ \vert \vert I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x) \vert \vert _ 2$ is minimised over all $\pmb x$ (i.e. an improvement to our guess of where Pac-Man is inside the image)

In general, we have:

Lucas-Kanade tracking approximates this via a first-order Taylor expansion as:

The optimality condition $\partial E / \partial \Delta \pmb p = \pmb 0$ gives the normal equations $\pmb M \Delta \pmb p = \pmb b$, hence

For each template pixel $\pmb x \in T$, define the steepest-descent vector ($n = \dim \pmb p$) and the residual:

Then

Evaluation points:

• $\pmb x$ ranges over template-domain coordinates.
• $\frac{\partial W}{\partial \pmb p}$ is the $2 \times n$ warp Jacobian at $(\pmb x, \pmb p)$, depending on $\pmb x$ directly through the warp formula.
• $\nabla I$ is the image gradient sampled at the warped point $W(\pmb x, \pmb p)$, not at $\pmb x$.
• $T(\pmb x)$ uses the template at $\pmb x$, while $I(W(\pmb x, \pmb p))$ uses the image at the warped point.

Both $\pmb M$ and $\pmb b$ also depend on the current $\pmb p$, so they are recomputed each iteration.

Write the per-pixel steepest-descent row vector and linearised residual

so the Taylor-approximated energy is just a sum of squares, $E(\Delta \pmb p) = \sum _ {\pmb x \in T} r(\pmb x)^2$.

Differentiate: each summand is a square, so the chain rule produces an extra factor of the residual $r(\pmb x)$ (the summand itself) alongside the derivative of the inside:

Only the term $J(\pmb x)\,\Delta \pmb p$ inside $r(\pmb x)$ depends on $\Delta \pmb p$, and $r(\pmb x)$ is a scalar while $\Delta \pmb p$ is a vector, so $\dfrac{\partial r(\pmb x)}{\partial \Delta \pmb p} = J(\pmb x)^\top$ (an $n \times 1$ column — this is where the transpose comes from). Substituting, and keeping the residual fully inside the bracket (all three terms, including $-T(\pmb x)$):

Set to zero and rearrange: split the residual into its $\Delta \pmb p$-dependent part $J(\pmb x)\,\Delta \pmb p$ and its constant part $I(W(\pmb x, \pmb p)) - T(\pmb x)$, then move the constant to the right-hand side:

Since $J(\pmb x) = \nabla I^\top \frac{\partial W}{\partial \pmb p}$, the left factor $J(\pmb x)^\top$ is exactly $\big(\nabla I^\top \frac{\partial W}{\partial \pmb p}\big)^\top$, so this matches the stated $\pmb M$ and $\pmb b$. The Gauss-Newton matrix $\pmb M$ is symmetric positive semi-definite, and is invertible whenever the template has gradient content in $n$ independent directions, giving

The brightness constancy assumption says: when a scene point moves between frames, its observed image intensity doesn’t change. Formally, for a pixel at $(x, y, t)$ that moves by $(\Delta x, \Delta y)$ in time $\Delta t$:

This is the only equation tying the unknown motion to observable data. It’s strong enough to convert an under-determined correspondence problem into a tractable optimisation, but breaks under:

• Lighting changes: a moving point’s intensity changes if illumination shifts.
• Specular highlights: glints move with the camera, not the scene.
• Occlusion: a previously-visible point disappears.
• Large motion: the linearisation (1st-order Taylor) only works for small $\Delta x, \Delta y$.

These are the standard failure modes for both LK tracking and optical flow.

Drift: if the template is updated each frame to compensate for genuine appearance changes (e.g. rotation, scale, lighting), small errors accumulate over time. The template gradually picks up background pixels, then more background, until the tracker “sticks” to the background and loses the actual object.

Mitigations:

1. Keep the original template fixed (do not update). Works well when appearance is stable but fails on long sequences with real appearance change.
2. Mask the template using a segmentation mask (foreground only). The mask suppresses background pixels so they cannot leak into the template even if updates are applied.
3. Periodically re-detect with an independent detector to correct the tracker (used in TLD-style tracking-by-detection).

This is a $2 \times 3$ matrix evaluated at each pixel $\pmb x = (x, y)$. The Jacobian enters the LK update via the per-pixel “steepest descent image” $\nabla I^\top (\partial W / \partial \pmb p)$.

Translation ($\pmb p = (t _ x, t _ y)$, $W = (x + t _ x,\ y + t _ y)$):

Translation + rotation ($\pmb p = (t _ x, t _ y, \theta)$, $W = (x\cos\theta - y\sin\theta + t _ x,\ x\sin\theta + y\cos\theta + t _ y)$):

Translation + scaling ($\pmb p = (t _ x, t _ y, s)$, $W = (sx + t _ x,\ sy + t _ y)$):

Affine ($\pmb p = (p _ {11}, \ldots, p _ {23})$, $W = (p _ {11}x + p _ {12}y + p _ {13},\ p _ {21}x + p _ {22}y + p _ {23})$):

Each Jacobian is $2 \times n$, with rows $\partial W _ x / \partial \pmb p$ and $\partial W _ y / \partial \pmb p$, evaluated at the pixel $\pmb x = (x, y)$. It enters the LK update through the steepest-descent image $\nabla I^\top \frac{\partial W}{\partial \pmb p}$ (∆lk-update-rule-statement).

Naive template matching evaluates

for every candidate offset $(u, v)$ — i.e. every pixel position in the image.

Complexity: per frame, this is $O(\#\text{image pixels} \times \#\text{template pixels})$. For a $1000 \times 1000$ image and a $50 \times 50$ template, that’s $10^6 \times 2500 = 2.5 \times 10^9$ pixel-difference operations per frame. Unaffordable for real-time tracking at 30 fps.

LK avoids this by starting from a guess $(t _ x, t _ y)$ (e.g. the previous frame’s detected location) and refining it iteratively via gradient-based update $\Delta \pmb p$ — typically a handful of iterations per frame, each $O(\#\text{template pixels})$. Total cost is dramatically lower.

• Linearise: replace the non-linear residual $I(W(\pmb x, \pmb p + \Delta \pmb p)) - T(\pmb x)$ with its first-order Taylor expansion around the current $\pmb p$, producing a quadratic-in-$\Delta \pmb p$ objective $E(\Delta \pmb p)$.
• Recognise as least squares: stacking the per-pixel residuals into a vector, $E(\Delta \pmb p) = \|A \Delta \pmb p - r\|^2$ where each row of $A$ is the “steepest descent image” $\nabla I^\top \partial W / \partial \pmb p$ at one pixel and $r$ is the temporal-difference residual $T(\pmb x) - I(W(\pmb x, \pmb p))$.
• Set the gradient to zero: $\partial E / \partial \Delta \pmb p = 0$ gives the normal equations $A^\top A \, \Delta \pmb p = A^\top r$, i.e. $\pmb M \Delta \pmb p = \pmb b$.
• Invert: $\Delta \pmb p = \pmb M^{-1} \pmb b$, with $\pmb M$ the Gauss-Newton approximation to the Hessian and $\pmb b$ proportional to the (negative) gradient at $\Delta \pmb p = 0$. Iterate by updating $\pmb p \leftarrow \pmb p + \Delta \pmb p$.

This is just one step of Gauss-Newton on the original non-linear least-squares problem; the LK iteration is re-linearise + solve repeated until $\Delta \pmb p$ is small.