Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Robust fitting in computer vision: easy or hard?
Author: Chin, T.-J.
Cai, Z.
Neumann, F.
Citation: Lecture Notes in Artificial Intelligence, 2018 / Ferrari, V., Herbert, M., Sminchisescu, C., Weiss, Y. (ed./s), vol.abs/1802.06464, pp.715-730
Publisher: Springer
Publisher Place: Cham, Switzerland
Issue Date: 2018
Series/Report no.: Lecture Notes in Computer Science; 11216
ISBN: 9783030012571
ISSN: 0302-9743
Conference Name: Computer Vision - ECCV 2018 15th European Conference Munich, Germany, September 8–14, 2018 Proceedings, Part XII (8 Sep 2018 - 14 Sep 2018 : Munich, Germany)
Editor: Ferrari, V.
Herbert, M.
Sminchisescu, C.
Weiss, Y.
Statement of
Tat-Jun Chin, Zhipeng Cai and Frank Neumann
Abstract: 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.
Keywords: Robust fitting; consensus maximisation; inlier set maximisation; computational hardness
Rights: © Springer Nature Switzerland AG 2018
DOI: 10.1007/978-3-030-01258-8_43
Grant ID:
Published version:
Appears in Collections:Aurora harvest 4
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.