Extracting Structure from Optical Flow Using the Fast Error Search Technique

摘要

In this paper, we present a robust 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 x N flow field, the FOE can be estimated in O(N2 log N) operations. Since the resulting system is linear, bounded perturbations in the data lead to bounded errors. We support the theoretical development and proof of our algorithm with experiments on synthetic and real data. Through a series of experiments on synthetic data, we prove the correctness, robustness and operating envelope of our algorithm. We demonstrate the utility of our technique by applying it to the problem areas of 3D stabilization, moving object detection, rangefinding, obstacle detection, and generation of 3D models from video.