Extracting Structure from Optical Flow Using the Fast Error Search Technique

摘要

In this paper, we present a globally optimal and computationally efficient technique for estimating the focus of expansion (FOE) of an optical flow field, using fast partial search. For each candidate location on a discrete sampling of the image area, we generate a linear system of equations for determining the remaining unknowns, viz. rotation and inverse depth. We compute the least squares error of the system without actually solving the equations, to generate an error surface that describes the goodness of fit across the hypotheses. Using Fourier techniques, we prove that given an N × N flow field, the FOE, and subsequently rotation and structure, can be estimated in \(\mathcal{O}(N^2 \log N)\) operations. Since the resulting system is linear, bounded perturbations in the data lead to bounded errors.