Robust Fitting in Computer Vision: Easy or Hard?
This work addresses a foundational gap for researchers in computer vision by clarifying the theoretical limits of robust fitting algorithms, though it is incremental in providing analysis rather than new methods.
The paper tackles the lack of fundamental analysis on the tractability of consensus maximization for robust model fitting in computer vision, presenting computational hardness results that demonstrate the problem's fundamental intractability and resolve ambiguities in the literature.
Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus maximisation, which strives to find the model parameters that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack of fundamental analysis of the problem in the computer vision literature. In particular, whether consensus maximisation is "tractable" remains a question that has not been rigorously dealt with, thus making it difficult to assess and compare the performance of proposed algorithms, relative to what is theoretically achievable. To shed light on these issues, we present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem, and resolve several ambiguities existing in the literature.