Horn and Shunk

Optical Flow

What is Optical Flow?

• Optical flow is the apparent motion of brightness patterns in a sequence of images.
• It arises from the relative motion between a camera and the scene.
• It’s represented as a field of 2D vectors, where each vector $(u(x,y),v(x,y))$ at pixel $(x,y)$ indicates the apparent displacement per unit time.
  • $u(x,y)$: Horizontal component of the displacement.
  • $v(x,y)$: Vertical component of the displacement.

Computing Optical Flow

Input and Output

• Input: A sequence of at least two images: $\{I(x,y,t)\mid 1\le t\le T,(x,y)\in \Omega \}$.
  • $I(x,y,t)$: intensity at pixel location $(x,y)$ and time $t$
  • $\Omega$: Image domain
• Output: A set of optical flow vectors for each pixel at each time point (except the last): $\{(u(x,y,t),v(x,y,t))\mid 1\le t<T,(x,y)\in \Omega \}$.

Assumptions

• Brightness Constancy: The apparent intensity of a physical point remains constant over time. This is the core assumption. Mathematically: $I(x+\Delta x,y+\Delta y,t+\Delta t)=I(x,y,t)$.
• Small Displacement: Points move only a small amount between consecutive frames. This allows for a linear approximation using the Taylor series.

Derivation of the Optical Flow Constraint Equation

1. Brightness Constancy: Start with the brightness constancy assumption: $I(x,y,t)=I(x+\Delta x,y+\Delta y,t+\Delta t)$.

2. Taylor Series Expansion: Expand the right side using a first-order Taylor series: $I(x+\Delta x,y+\Delta y,t+\Delta t)\approx I(x,y,t)+\frac{\partial I}{\partial x}\Delta x+\frac{\partial I}{\partial y}\Delta y+\frac{\partial I}{\partial t}\Delta t$.

3. Substitution and Simplification: Substitute the expansion back into the brightness constancy equation and subtract $I(x,y,t)$ from both sides: $0=\frac{\partial I}{\partial x}\Delta x+\frac{\partial I}{\partial y}\Delta y+\frac{\partial I}{\partial t}\Delta t$.

4. Divide by $\Delta t$: $0=\frac{\partial I}{\partial x}\frac{\Delta x}{\Delta t}+\frac{\partial I}{\partial y}\frac{\Delta y}{\Delta t}+\frac{\partial I}{\partial t}$.

5. Define $u$ and $v$: Recognize that $\frac{\Delta x}{\Delta t}$ approaches $u$ (horizontal velocity) and $\frac{\Delta y}{\Delta t}$ approaches $v$ (vertical velocity) as $\Delta t$ approaches 0.

6. Optical Flow Constraint Equation (OFCE): $0=\frac{\partial I}{\partial x}u+\frac{\partial I}{\partial y}v+\frac{\partial I}{\partial t}$.

   • Often written as: $I_{x}u+I_{y}v+I_t=0$, where $I_x=\frac{\partial I}{\partial x}$, $I_y=\frac{\partial I}{\partial y}$, and $I_t=\frac{\partial I}{\partial t}$ are the image gradients.

7. Dot Product Form: $(u(x,y,t),v(x,y,t))\cdot (\frac{\partial I(x,y,t)}{\partial x},\frac{\partial I(x,y,t)}{\partial y})+\frac{\partial I(x,y,t)}{\partial t}=0$

The Aperture Problem

• The aperture problem refers to the inherent ambiguity in determining the motion of an edge when viewed through a small aperture (or locally within an image).
• Only the component of motion perpendicular to the edge (the normal flow) can be reliably determined. The component of motion parallel to the edge is ambiguous.
• The OFCE provides only one equation for two unknowns ($u$ and $v$) at each pixel. This makes the problem underconstrained.

Solving the Optical Flow Problem: Methods

Because of the aperture problem, additional constraints are needed to solve for optical flow. Two main approaches are:

Horn & Schunck (Global Method)

• Global Smoothness Constraint: Assumes that the optical flow field is smooth over the entire image. Adjacent pixels should have similar flow vectors.

• Energy Minimization: Formulates the problem as minimizing an energy functional:

  $J(u,v)={\iint }_{\Omega }\left((I_{x}u+I_{y}v+I_t{)}^2+\lambda (u_x^2+u_y^2+v_x^2+v_y^2)\right)dxdy$.

  • $(I_{x}u+I_{y}v+I_t{)}^2$: Data fidelity term (enforces the OFCE).
  • $\lambda (u_x^2+u_y^2+v_x^2+v_y^2)$: Smoothness term (penalizes large changes in $u$ and $v$). $u_x=\frac{\partial u}{\partial x}$, etc.
  • $\lambda$: Regularization parameter. Controls the trade-off between data fidelity and smoothness. Larger $\lambda$ means smoother flow.

• Discretization:

  • Digital Derivatives Approximation:

    $I_{x;k,l}=I_{x;k,l,t}=(I_{k,l+1,t}-I_{k,l,t}+I_{k+1,l+1,t}-I_{k+1,l,t}+I_{k,l+1,t+1}-I_{k,l,t+1}+I_{k+1,l+1,t+1}-I_{k+1,l,t+1})/4$ $I_{y;k,l}=I_{y;k,l,t}=(I_{k+1,l,t}-I_{k,l,t}+I_{k+1,l+1,t}-I_{k,l+1,t}+I_{k+1,l,t+1}-I_{k,l,t+1}+I_{k+1,l+1,t+1}-I_{k,l+1,t+1})/4$ $I_{t;k,l}=I_{t;k,l,t}=(I_{k,l,t+1}-I_{k,l,t}+I_{k,l+1,t+1}-I_{k,l+1,t}+I_{k+1,l,t+1}-I_{k+1,l,t}+I_{k+1,l+1,t+1}-I_{k+1,l+1,t})/4$

  • Boundary Condition:

    • Set all image derivatives at the right-side or bottom boundary of the image are set to 0.
    • Values of $u$ and $v$ at pixels that fall outside the image domain are set to 0.

  • Discrete Energy Functional: $J(\{u_{i,j},v_{i,j}\})={\sum }_{i=1}^N{\sum }_{j=1}^M((I_{x;i,j}{u}_{i,j}+I_{y;i,j}{v}_{i,j}+I_{t;i,j}{)}^2+\lambda ((u_{i+1,j}-u_{i,j}{)}^2+(u_{i,j+1}-u_{i,j}{)}^2+(v_{i+1,j}-v_{i,j}{)}^2+(v_{i,j+1}-v_{i,j}{)}^2))$

• Iterative Solution (Jacobi Method): The minimization is typically solved iteratively. A common approach is the Jacobi method:

  1. Initialization: Initialize $u$ and $v$ (often to 0).

  2. Iteration: For each pixel $(k,l)$, update $u_{k,l}$ and $v_{k,l}$ using the following equations, while keeping the values at all other pixels fixed:

     $u_{k,l}^{(t+1)}={\bar{u}}_{k,l}^{(t)}-\frac{I_x(I_x{\bar{u}}_{k,l}^{(t)}+I_y{\bar{v}}_{k,l}^{(t)}+I_t)}{I_x^2+I_y^2+4\lambda }$.

     $v_{k,l}^{(t+1)}={\bar{v}}_{k,l}^{(t)}-\frac{I_y(I_x{\bar{u}}_{k,l}^{(t)}+I_y{\bar{v}}_{k,l}^{(t)}+I_t)}{I_x^2+I_y^2+4\lambda }$.

     • ${\bar{u}}_{k,l}$ and ${\bar{v}}_{k,l}$ represent the average of the neighboring $u$ and $v$ values, respectively (e.g., ${\bar{u}}_{k,l}=(u_{k,l+1}+u_{k+1,l}+u_{k,l-1}+u_{k-1,l})/4$).

  3. Convergence: Repeat the iteration until convergence (the change in $u$ and $v$ is small) or a maximum number of iterations is reached.

• Jacobi’s method derivation:

  • Consider $Ax=b$
  • $A$ can be expressed as $D+R$ where $D$ is a diagonal matrix.
  • The solution vector can be obtained iteratively as: $x^{(t+1)}=D^{-1}(b-R{x}^{(t)})$ $x_i^{(t+1)}=\frac{b_i-{\sum }_{j\ne i}{A}_{ij}{x}_j^{(t)}}{A_{ii}}$

Summary and Key Concepts

• Optical Flow: The apparent motion of brightness patterns.
• Brightness Constancy Assumption: The foundation of optical flow estimation.
• Optical Flow Constraint Equation (OFCE): $I_{x}u+I_{y}v+I_t=0$. Relates image gradients to optical flow.
• Aperture Problem: The inherent ambiguity in determining motion along an edge.
• Underconstrained Problem: The OFCE alone is insufficient to solve for $u$ and $v$.
• Regularization: Adding constraints (like smoothness) to solve the underconstrained problem.
• Horn & Schunck: A global method using a smoothness constraint.
• Lucas-Kanade: A local method assuming constant flow within a small neighborhood.
• Iterative Methods: Used to solve the optimization problems arising in optical flow estimation (e.g., Jacobi method).
• Taylor Series: Used for linear approximation of the brightness constancy.

This set of notes provides a structured, comprehensive, and exam-ready overview of optical flow, incorporating all the key concepts, equations, and methods from the provided PDFs. The use of MathJax, Mermaid.js, and Markdown formatting ensures clarity and ease of understanding.