2. Examples of Motion Estimation algorithms
In this section, a brief survey of
some of existimg optical flow/motion estimation algorithms is done. I will
focuse more on the applications which has some connection with the proposed
algorithm that will be explained in the later sections.
Block matching is the most popular method
for practical motion estimation due to its relatively low complexity hardware.
As a result, this is used for MPEG and other standards. The displacement
for a pixel is determined by considering a NxN block containing the pixel.
The best match for the block is found by searching the next frame for the
location of the best-matching block of the same size. The search is usually
limited to a search region. The algorithm varies in the matching criteria
( e.g. MSE, MAD or cross-correlation ) and search strategy. The problem
with this approach is that although it is rather fairly simple to implement,
it is limited by the used of a fixed shape window that cannot adapt to
irregular surface boundaries. Also, this algorithm performs poorly when
multiple motions are present in the block.
Some minor modifications to alleviate
this problem has been reported. Image segmentation is done before performing
block matching and this imformation is used to calculate the motion vectors
for the edges. Still, this is inherently limited by the performance of
the block matching algorithm.
Feature based approches calculate the
features for each frame and try calculate the sparse optical flows that
is computed only for a subset of image points. The optical flow for other
image points can be calculated by performing interpolation. To solve
the correspondence problem, a number of parameters are assigned to each
feature and we argue that the feature points with similar values of parameters
correspond to each other. The most important part of this approach is in
choosing the feature. An example of a feature can be a corners of an image.
( A line of an image cannot be a good candidate for a feature because there
are ambiguities for a line moving normal to the gradient.)
This method assumes a intensity conservation
constraint. This can be used to derive the relationship between intensity
derivatives and is shown above. Here the subscripts indicate partial derivatives
of the brightness function with respect to x,y, and t.This constraint combined
with the constraints from the neighboring pixels can be used to calculate
the flow at each pixels. One way is to do a least squares estimate to find
the flow for the pixels. Choosing a region for this can be challenging
because multiple motion can be present in that region. This can be alleviated
by considering the residual of the least square solution. Also, instead
of minimizing the square of the gradient constrint, minimizing with another
function can be applied to give less weight to outliers.
-
Model-based method and etc.
There are several other methods such as
pel-recursive methods, bayesian method, model based method. One interesting
method is model-based method, which tries to estimate parameters of models
over a large image neighborhood. An interesting work by Adelson et al.
assume this. Authors assume that an image region is model by a set of overlapping
layers which somewhat corresponds to objects. They use clustering to group
motion estimates into regions of consistent affine motion. This is close
to high-level perception, but it requires a lot of computations.