OF IMP

Q: Define optical flow. What are the two basic assumptions you consider before computing optical flow? Explain in detail the working principle of Horn and Shunck method for computing optical flow. What are the differences between Horn-Shunck method and Lucas-Kanade method employed for optical flow? (Marks: 2+4+8+2 = 16)

Answer:

1. Definition of Optical Flow (2 Marks)

Optical flow is the pattern of apparent motion of brightness patterns in an image sequence. It represents the projection of the 3D motion of scene points onto the 2D image plane. It is typically represented as a dense 2D vector field, $\mathbf{v}(x,y)=(u(x,y),v(x,y))$, where each vector $(u,v)$ indicates the instantaneous velocity (image displacement in $x$ and $y$ directions per unit time) of the brightness pattern located at pixel coordinates $(x,y)$ between two consecutive frames.

2. Basic Assumptions for Computing Optical Flow (4 Marks)

Two fundamental assumptions are typically made when deriving basic optical flow computation methods:

• (i) Brightness Constancy: The perceived brightness (intensity) of a moving object point remains constant over time, at least for short durations between consecutive frames. If $f(x,y,t)$ represents the image intensity at pixel $(x,y)$ at time $t$, then for a displacement $(dx,dy)$ over a time interval $dt$, this assumption is mathematically stated as: $f(x,y,t)=f(x+dx,y+dy,t+dt)$

• (ii) Small Motion: The displacement $(dx,dy)$ of image points between consecutive frames is small (typically only a few pixels). This assumption allows the use of first-order Taylor series expansions to linearize the relationship between intensity changes and motion, simplifying the computation.

3. Working Principle of Horn & Schunck Method (8 Marks)

The Horn and Schunck method is a classic variational approach to compute a dense optical flow field. Its working principle involves combining the brightness constancy assumption with a global smoothness constraint to resolve the ambiguities inherent in local motion estimation (the aperture problem).

• Step 1: Optical Flow Constraint Equation (OFCE): Starting with the brightness constancy assumption: $f(x,y,t)=f(x+dx,y+dy,t+dt)$ Assuming small motion, we perform a first-order Taylor series expansion of the right side around $(x,y,t)$: $f(x+dx,y+dy,t+dt)\approx f(x,y,t)+\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy+\frac{\partial f}{\partial t}dt$ Substituting this back into the brightness constancy equation and simplifying gives: $\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy+\frac{\partial f}{\partial t}dt\approx 0$ Let $f_x=\frac{\partial f}{\partial x}$, $f_y=\frac{\partial f}{\partial y}$, $f_t=\frac{\partial f}{\partial t}$. Dividing by $dt$ and defining the optical flow velocity components $u=\frac{dx}{dt}$ and $v=\frac{dy}{dt}$, we get the Optical Flow Constraint Equation (OFCE): $f_{x}u+f_{y}v+f_t=0$ This equation relates the unknown flow $(u,v)$ to the measurable spatial ($f_x,f_y$) and temporal ($f_t$) image intensity derivatives. However, this single equation provides only one constraint for two unknowns ($u,v$) at each pixel, leading to the aperture problem (only the flow component normal to the image gradient can be determined locally).

• Step 2: Smoothness Constraint: To overcome the aperture problem, Horn and Schunck introduced a global smoothness constraint. This assumes that the optical flow field varies smoothly across the image, meaning neighbouring pixels tend to have similar flow vectors. This constraint is mathematically expressed by penalizing large spatial gradients of the flow components $u$ and $v$. The measure of non-smoothness is given by: $E_{smooth}^2=(\frac{\partial u}{\partial x}{)}^2+(\frac{\partial u}{\partial y}{)}^2+(\frac{\partial v}{\partial x}{)}^2+(\frac{\partial v}{\partial y}{)}^2=u_x^2+u_y^2+v_x^2+v_y^2$

• Step 3: Variational Formulation (Minimization): The Horn-Schunck method seeks to find the optical flow field $(u(x,y),v(x,y))$ that minimizes a global error functional $E$, which is a weighted sum of the error in satisfying the brightness constancy constraint and the measure of non-smoothness, integrated over the entire image domain $\Omega$: $E={\iint }_{\Omega }\left[(f_{x}u+f_{y}v+f_t{)}^2+\lambda (u_x^2+u_y^2+v_x^2+v_y^2)\right]dxdy$ Here, $\lambda >0$ is a regularization parameter that controls the trade-off between adherence to the brightness constancy (data term) and the smoothness of the flow field (smoothness term).

• Step 4: Solution via Calculus of Variations: The minimization of the functional $E$ is achieved using the calculus of variations, leading to the Euler-Lagrange equations. These result in a pair of coupled partial differential equations (PDEs): $f_x(f_{x}u+f_{y}v+f_t)-\lambda {\Delta }^{2}u=0$ $f_y(f_{x}u+f_{y}v+f_t)-\lambda {\Delta }^{2}v=0$ where ${\Delta }^{2}u=\frac{{\partial }^{2}u}{\partial x^2}+\frac{{\partial }^{2}u}{\partial y^2}=u_{xx}+u_{yy}$ is the Laplacian operator.

• Step 5: Iterative Numerical Solution: These PDEs are typically solved numerically on a discrete pixel grid. The spatial and temporal derivatives ($f_x,f_y,f_t$) are approximated using finite difference masks (e.g., Roberts masks, Sobel masks, or simple differences). The Laplacian is also approximated, often using a local averaging scheme where ${\Delta }^{2}u\approx u_{av}-u$, where $u_{av}$ is the average of $u$ in a small neighbourhood. This leads to an iterative solution: $u^{k+1}=u_{av}^k-f_x\frac{P^k}{D}$ $v^{k+1}=v_{av}^k-f_y\frac{P^k}{D}$ where $k$ is the iteration number, $u_{av}^k$ and $v_{av}^k$ are the local averages of the flow components from the previous iteration, and $P^k=f_x{u}_{av}^k+f_y{v}_{av}^k+f_t$ $D=\lambda +f_x^2+f_y^2$ The iteration starts with an initial guess (e.g., $u^0=v^0=0$) and continues until the flow field converges (changes between iterations are below a threshold). The result is a dense optical flow field, providing a velocity vector $(u,v)$ for every pixel.

4. Differences between Horn-Schunck and Lucas-Kanade Methods (2 Marks)

Feature	Horn-Schunck Method	Lucas-Kanade Method
Constraint Type	Global Smoothness Constraint	Local Constant Flow Constraint
Scope	Considers the entire image simultaneously	Considers a small local window ($N\times N$) around each pixel/feature
Math Formulation	Minimizes global energy functional (Variational Calculus)	Solves local overdetermined system via Weighted Least Squares
Output Density	Naturally Dense (vector per pixel)	Sparse (one vector per window/feature point) in basic form; Dense variants exist
Computation	Iterative solution of PDEs, potentially slow	Often closed-form solution (matrix inversion) per window, generally faster
Assumptions	Brightness constancy, small motion, global flow smoothness	Brightness constancy, small motion, local flow constancy

---