Prof. Tat-Jun Chin

University of Adelaide

Why is robust fitting hard, what can be done about it?

Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Despite the active efforts, an important question remains: to what extent is robust fitting computationally solvable? To answer this question, this talk presents several computational hardness results for robust fitting. Unfortunately, the results will show that robust fitting is not only intractable to solve, it is also impossible to approximate. This talk then suggests a way forward, by proposing a new class of solutions that lie between the two extremes of "quick and dirty" randomised algorithms and costly global algorithms. In particular, a novel algorithm that performs the well-understood task of polyhedral vertex search is described.