Multi-Structure Model-Based Fitting in Computer Vision - A Tour

2^nd October 2019, 14:00
David Suter
Edith Cowan University

Abstract

Model Fitting in Computer Vision, that is robust in the presence of multi-structures and/or in the presence of outliers, has a long history: (still) popular methods date to the early 1980’s (RANSAC) or early 1970’s - even arguably late 1950’s(!) Hough Transform.

The speaker has, himself, studied methods for model-based fitting for around 20 years. Variants of algorithms places different emphasis on search vs clustering type characterisations, on different measures of “model-data fidelity” (including whether inlier noise requires estimation), and (though much less rarely) on whether model selection is attempted (amongst…other considerations).

Often heuristics, loose reasoning, intuition, and empirical evidence are the main attributes of how the plethora of methods have been motivated/explained and assessed.”Hard-Core (Theoretical) Computer Science” is usually essentially absent. Therefore, strong guarantees (finding optimal solution is guaranteed running times) are usually absent and the best that can be said is that the popular methods “sort of mostly work”.

Where the approach is based on the maximum consensus approach to model fidelity, and in a slightly restricted setting, the single model version is known to be optimally solvable in O(N^(p+1)), where N is the number of data points and p is the number of parameters in the model. This interpretation of known results in Computational Geometry and the theory of Lp-type problems, along with a novel A*-based approach that often performs much better, was introduced around 5 years ago. The (known) optimal solution is essentially exhaustive search of the (p+1)-sized subsets of N; and the A*-based approach is essentially a top (set of all data) down heuristic guided search of the Hasse-diagram s (of which the (p+1) subsets form one level) of all 2^N subsets. If the optimal solution is “near the top” and if the heuristics in the A* are good, then the A* approach not only has the guarantee of eventually finding the optimal solution (a guarantee absent in almost all other proposed approaches) but it will do so very efficiently. But this, in the context of the problem, is tantamount to assuming “not that many outliers”. In contrast, one can also “do a binary chop search” on the levels of the Hasse Diagram, to try to avoid this limitation but the only such algorithm known to the speaker has some limitations. A lot of other work concentrating on getting close to optimality, generally adopts a strategy of trying to “cheaply” find a guaranteed better solution to a “warm start” (such as RANSAC) - and while they generally have some good guarantees in certain ways, they fall short of promising the optimal. It should also be mentioned that is an approximate solution is all one wants (in terms of precision of model-parameters) - it is sometimes, problem specific - possible to engineer a Branch and Bound solution with guarantees on that precision.

It is reasonably firmly established that finding an algorithm with guaranteed optimality and with guaranteed better than O(N^(p+1)) cost, even in the single structure case, basically rests on P=NP. So the above state of affairs is, in that sense, not surprising. It’s also fairly well established that the basic single structure problem is hard to approximate efficiently (and with approximation quality guarantees). But have we reached the best we can do (in terms of performance - let alone in terms of characterising/understanding the current heuristic-based and empirically advocated methods? Answer this continues to drive the (meta)search.

The exposition of the above will necessarily be an abbreviated and personally biased view. It will draw heavily on work mostly done by Tat-Jun Chin and other colleagues at the University of Adelaide, and with former students and their teams, over roughly the last 5-10 years.
If time permits it will include hints of some more recent/unpublished work.