# Optical Flow Optical flow is motion estimation from images. Uses: - Track object behavior - Correct for camera jitter (stabilization) - Align images (mosaics) - 3D shape reconstruction - Special effects ![[optical-flow.jpg]] Problem: How to estimate pixel motion from image H to image I? - Solve pixel correspondence problem - given a pixel in H, look for nearby pixels of the same color in I Key assumptions: - color constancy: a point in H looks the same in I - For grayscale images, this is brightness constancy - $\mathrm{H}(\mathrm{x}, \mathrm{y})=\mathrm{I}(\mathrm{x}+\mathrm{u}, \mathrm{y}+\mathrm{v})$ - small motion: points do not move very far - suppose we take the [[Taylor Expansion]] of I: - $I(x+u, y+v)=I(x, y)+\frac{\partial I}{\partial x} u+\frac{\partial I}{\partial y} v+$ higher order terms From these two assumpitons we have, $ \begin{aligned} O &=I(x+u, y+v)-H(x, y) \quad \text { shorthand: } I_{x}=\frac{\partial I}{\partial x} \\ & \approx I(x, y)+I_{x} u+I_{y} v-H(x, y) \\ & \approx(I(x, y)-H(x, y))+I_{x} u+I_{y} v \\ & \approx I_{t}+I_{x} u+I_{y} v \\ & \approx I_{t}+\nabla I \cdot[u v] \end{aligned} $ In, the limit as u and v go to zero, this becomes exact $ O=I_{t}+\nabla I \cdot\left[\frac{\partial x}{\partial t} \frac{\partial y}{\partial t}\right] $ In RGB version, $ 0=I_{t}\left(\mathrm{p}_{\mathrm{i}}\right)[0,1,2]+\nabla I\left(\mathrm{p}_{\mathrm{i}}\right)[0,1,2] \cdot[u \quad v] $ Two problems: - We have two unknowns but one equation. - Aperture problem: If we have only small observation, we cannot estimate motion properly. For example: In a Barber-pole, the motion is happening from left to right (cylindrical), but it looks to us like the motion is happening from top to bottom. Solutions: To get more equations per pixel, Impose additional constraints - most common is to assume that the flow field is smooth locally - one method: pretend the pixel's neighbors have the same (u,v) - If we use a 5x5 window, that gives us 25 equations per pixel! $ \left[\begin{array}{cc} I_{x}\left(\mathrm{p}_{1}\right) & I_{y}\left(\mathrm{p}_{1}\right) \\ I_{x}\left(\mathrm{p}_{2}\right) & I_{y}\left(\mathrm{p}_{2}\right) \\ \vdots & \vdots \\ I_{x}\left(\mathrm{p}_{25}\right) & I_{y}\left(\mathrm{p}_{25}\right) \end{array}\right]\left[\begin{array}{l} u \\ v \end{array}\right]=-\left[\begin{array}{c} I_{t}\left(\mathrm{p}_{1}\right) \\ I_{t}\left(\mathrm{p}_{2}\right) \\ \vdots \\ I_{t}\left(\mathrm{p}_{25}\right) \end{array}\right] $ ## Lukas-Kanade flow Solve least squares problem: $ \begin{array}{ll} A \quad d=b & \longrightarrow \quad \operatorname{minimize} \end{array}\|A d-b\|^{2} $ $ \left[\begin{array}{cc} \sum I_{x} I_{x} & \sum I_{x} I_{y} \\ \sum I_{x} I_{y} & \sum I_{y} I_{y} \end{array}\right]\left[\begin{array}{l} u \\ v \end{array}\right]=-\left[\begin{array}{c} \sum I_{x} I_{t} \\ \sum I_{y} I_{t} \end{array}\right] $ - The summations are over all pixels in the $\mathrm{K} \times \mathrm{K}$ window - This technique was first proposed by Lukas \& Kanade (1981) When is this $A^{T} A = -A^{T} b$ solvable? - $A^TA$ should be invertible - $A^TA$ should not be too small due to noise - eigenvalues $\lambda_{1}$ and $\lambda_{2}$ of A'A should not be too small - $A^TA$ should be well-conditioned $-\lambda_{1} / \lambda_{2}$ should not be too large $\left(\lambda_{1}=\right.$ larger eigenvalue $)$ $A^TA$ is solvable when there is no apperture problem. $ A^{T} A=\left[\begin{array}{ll} \sum I_{x} I_{x} & \sum I_{x} I_{y} \\ \sum I_{x} I_{y} & \sum I_{y} I_{y} \end{array}\right]=\sum\left[\begin{array}{l} I_{x} \\ I_{y} \end{array}\right]\left[I_{x} I_{y}\right]=\sum \nabla I(\nabla I)^{T} $ This is a two image problem BUT - Can measure sensitivity by just looking at one of the images! - This tells us which pixels are easy to track, which are hard - very useful later for feature tracking ### Challenges in Lukas-Kanade What are the potential causes of errors in this procedure? - Suppose $\mathrm{A}^{\mathrm{T}} \mathrm{A}$ is easily invertible - Suppose there is not much noise in the image When our assumptions are violated - Brightness constancy is not satisfied - The motion is not small - A point does not move like its neighbors - window size is too large - what is the ideal window size? ### Iterative Lukas-Kanade Algorithm To make sure the assumptions are not violated, we use iterative improvement: 1. Estimate velocity at each pixel by solving Lucas-Kanade equations 2. Warp H towards I using the estimated flow field (use image warping techniques) 3. Repeat until convergence ### Aliasing Temporal aliasing causes ambiguities in optical flow because images can have many pixels with the same intensity. I.e., how do we know which 'correspondence' is correct? ![[opticalflow-aliasing.jpg]] Solution: Coarse-to-fine estimation (Reduce the resolution!) ![[of-coarse 1.jpg]] --- ## References