Speaker: Jiri Matas

Title:   Wald's Sequential Analysis for Time-constrained Vision Problems

Abstract:

Many computer vision problems involve optimization of two quantities,
one of which is time.  Such problems can be formulated as time-contrained 
optimization or performance-constrianed search of the fastest algorithm.

We show examples where it is possible to obtain quazi-optimal
time-constrained solutions to vision problems by applying Wald's theory of
sequential decision-making. The approach will be demonstrated on there tasks:
(i) face detection, (ii) real-time detection of interest points and (iii) model
search and outlier detection using RANSAC.

In the face detection problem, the objective is learning the fastest detector
satisfying constraints on false positive and false negative rates. We solve the
problem by WaldBoost, a combination of Wald's sequential probability ratio test
and AdaBoost. The solution can be viewed as a principled way to build a
close-to-optimal "cascade of classifiers" of the Viola-Jones type. Naturally,
the approach is applicable to to other class of objects.

In the interest point detection example, we show how a fast (real-time)
implementation of known detectors can obtained by Waldboost. The "mimicked"
detectors provides a training set of positive and negative expamples of interest
points and WaldBoost learns a time-optimised detector formed as a linear
combination of efficiently computable features. The approach will be
demonstrated for the Hessian-Laplace and Kadir detectors; the speed of the
latter is increased 70 times with the same detection peformance.

In RANSAC, we show how to exploit Wald's test in a randomised model
verification procedure to obtain an algorithm significantly faster then
deterministic verification yet with equivalent probabilistic guarantees
of correctness.