COMPUTATION OF OPTICAL FLOW
Object: Optical flow computation consists in extracting a dense
velocity field from an image sequence assuming that intensity (or color) is
conserved during dis-placement. This result may then be used by other
applications like: 3D reconstruction, time interpolation of image sequences
using motion information, segmentation and tracking.
Content: An algorithm for optical flow computation using dynamic
programming has been developed (1). It is based on the search for successive
approximations of a displacement field between two images that minimizes the
L1 or L2 distance between them while satisfying certain continuity and
regularity constraints. For this, images are sliced in parallel and
overlaping strips. Each strip of an image is optimally aligned with the
corresponding strip of the other image using dynamic programming exactly as
this is classically done in speech recognition for two (time, frequency)
strip representations of speech utterances. Iterations are performed
alternatively with horizontal and vertical slicing while the strips spacing
and width is reduced at each step . The displacement field adjustment is
therefore carried out alternatively for the horizontal and vertical components
with a better and better accuracy. This method is related with classical
correlation-based methods for optical flow computation. The difference
is that correlation is searched here between elastic strips rather than
being searched on rigid squares. The advantage is that dynamic programming
provides a global match with constraints propagation, which is much more
robust. Being correlation based, the algorithm can also be used for color
images
The method has been enhanced in order to be able to operate not only on
image pairs but also on image sequences with arbitrary length. In that case
it is additionally assumed that motion is constant during the portion of the
sequence used. We search automatically the image pair that gives the best
accuracy / distortion compromise (the farther the images are, the more
accurate the displacements are but if the distortion is too large the
algorithm makes errors). Moreover, all intermediate image pairs are
successively used during the iterative search.
Quantitative performance measurements have been made (2)
with images sequences classically used by the scientific community for the
test of optical flow methods (available on the site:
ftp://csd.uwo.ca/pub/vision).
For the seven calibrated synthetic sequences, we got the best results.
Figure 1 shows the obtained velocity fields for the four real sequences.
First sequence: lateral displacement of the
camera with a fixed point in the distance.
Second sequence: displacement of the camera towards the scene.
Third sequence: rotation of the plate.
Fourth sequence: Three vehicles are moving but
one is behind the tree (which is motionless).
Several enhancements are currently being studied. One of them consists
in using simultaneously all the intermediate images between the selected
extremes instead of successively using all the pairs (this involves the
defintion of a correlation mesure concerning more than two elements).
Another one concerns the search for displacements with a subpixel accuracy.
Several applications using the results of optical flow computation are also
being developed: 3D reconstruction, image interpolation and contours /
regions / motion cooperative segmentation.
Figures (postscript, 1427288 bytes).
References
(1)
The ``Orthogonal Algorithm'' for Optical Flow Detection using Dynamic
Programming [851934 bytes],
Georges M. Quénot,
IEEE International Conference on Accoustics, Speech and Signal Processing,
San Francisco, CA, USA, March 1992.
Abstract.
(2)
Computation of Optical Flow Using Dynamic Programming [1536721 bytes],
Georges M. Quénot,
Machine Vision Applications, Tokyo, Japan, 12-14 nov 1996.
Abstract.