Robust Fitting in Computer Vision: Easy or Hard?

Tat-Jun Chin, Associate Professor, School of Computer Science, University of Adelaide
Chaired by
Dr LEE Gim Hee, Assistant Professor, School of Computing

  21 Sep 2018 Friday, 02:00 PM to 03:00 PM

 Executive Classroom, COM2-04-02


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.


Tat-Jun Chin received his BEng degree in mechatronics engineering from Universiti Teknologi Malaysia (UTM) in 2003, where he received the Vice Chancellor's Commendation Award, and his PhD in computer systems engineering from Monash University in 2007, which was supported by the Endeavour Australia-Asia Award. He is currently an Associate Professor at The University of Adelaide. He is also an Associate Editor of the IPSJ Transactions on Computer Vision and Applications (TCVA) and Journal of Imaging (J. Imaging). Tat-Jun's research interest lies in optimisation for geometric vision, which covers areas such as 3D reconstruction, SLAM, and augmented reality. He has published more than 80 research articles on the subject, including an invited book submission. Tat-Jun has won significant awards for his research: a CVPR Award in 2015, and two DST Awards (2015 and 2017).