22-05-2014, 04:00 PM
Robust Total Least Squares Based Optic Flow Computation
Robust Total Least .pdf (Size: 65.22 KB / Downloads: 9)
Abstract
This paper considers the problem of finding a robust solution to the optic flow
problem. The optical flow field is recovered by solving a system of over-determined linear
equations with all the data matrices containing both outliers and noise. Here, we present a novel
and very effective solution for this problem called weighted total least squares. The weights for
this method are computed using a new robust statistical method named least median of squares
orthogonal distances. Unlike the total least squares which is only robust to noise, this method is
extremely robust to both noise and outliers and can tolerate up to 50% of equations in the
system to be contaminated by outliers. The proposed weighting method is fast and the total
computation remains inexpensive. To demonstrate the performance of the proposed algorithm,
we compare the accuracy of our algorithm for computing optic flow field for a number of
synthetic and real image sequences and show that the proposed method, despite being very
simple and straightforward, out performs all methods used for comparison.
Introduction
In this paper, we consider the problem of finding a robust solution to a differential
based optic flow problem. The differential techniques invariably involve some form of
what has become known as the Optic Flow Constraint (OFC). The OFC can be written
as (Horn & Schunck, 1981):
Robust TLS Based Technique
The study of robust estimators with high breakdown point, allowing a substantial
portion of the data to be contaminated by outliers, has been actively researched for
decades among statisticians. In 1984, Rousseeuw proposed the method of Least
Median of Squares (LMedS) for the standard regression (SR) problem. LMedS has a
breakdown point of 50%. Although this estimator is very robust to outliers, its
theoretical performance in the presence of noise, and its computational complexity,
are not attractive. Rousseeuw and Leroy (1987) proposed a very powerful method
known as reweighted least squares (RLS). In this method first, a fast approximate
solution to the LMedS problem is found. Then all the data points are categorized into
outliers and inliers, based on their scaled residuals with respect to the LMedS solution.
Finally, the regressor for the inliers is calculated using the LS technique.
Measure of Reliability
Although the LMSOD techniques have the highest possible breakdown point (50%) of
all known robust estimators, it has the potentially fatal flaw in that is still produces an
estimate, even if the number of outliers is more than 50%. Moreover, there are
extreme cases where an image patch may not contain sufficient data (lack of texture)
or data so badly corrupted (aliasing for example) for any estimate to be valid. Thus we
still need to validate the estimate produced by our method. A tool for the validation
process can be modeled on “the coefficient of determination” (Kvalseth, 1985). The
coefficient of determination, denoted R2, has been defined for the Standard regression
problem in at least nine different ways. However, although we are guided by analogy
with the SR problem, we are interested in robust forms of TLS. We define our own
measure, which is also called R2, similar to the one presented by Bab-Hadiashar and
Suter (1997). For the WTLS technique, we want to ensure that the Frobenius norm of
the perturbation matrix ∆=[∆As ∆ds] is small enough for the solution to be acceptable.
Conclusion
This paper presents a novel method for solving a system of over-determined linear
equations when the parameters of the equations are contaminated with both outliers
and noise. The solution to this type of problem is frequently sought in the study of
different computer vision problems. The proposed algorithm uses a new method
named the least median of squares orthogonal distances combined with the
well-known total least squares for dealing with the outliers and noise, respectively. A
fast method for computing an approximate solution to the LMSOD is also proposed
which makes the computation inexpensive. The performance of this method has been
demonstrated by solving the optic flow problem. Although the presented algorithm is
conceptually very straight forward, it out-performs any other (often very sophisticated)
optic flow technique.