Consensus maximisation using influences of monotone boolean functions

Author Identifier (ORCID)

David Suter

https://orcid.org/0000-0001-6306-3023

Abstract

Consensus maximisation (MaxCon), which is widely used for robust fitting in computer vision, aims to find the largest subset of data that fits the model within some tolerance level. In this paper, we outline the connection between MaxCon problem and the abstract problem of finding the maximum upper zero of a Monotone Boolean Function (MBF) defined over the Boolean Cube. Then, we link the concept of influences (in a MBF) to the concept of outlier (in MaxCon) and show that influences of points belonging to the largest structure in data would generally be smaller under certain conditions. Based on this observation, we present an iterative algorithm to perform consensus maximisation. Results for both synthetic and real visual data experiments show that the MBF based algorithm is capable of generating a near optimal solution relatively quickly. This is particularly important where there are large number of outliers (gross or pseudo) in the observed data.

Document Type

Conference Proceeding

Date of Publication

2021

Publication Title

2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)

Publisher

IEEE

School

School of Science

RAS ID

36863

Funders

Australian Research Council

Grant Number

ARC Numbers : LP190100165, DP200103448, DP200101675

Comments

Tennakoon, R., Suter, D., Zhang, E., Chin, T. J., Bab-Hadiashar, A. (2021). Consensus maximisation using influences of monotone boolean functions. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 2865-2874). IEEE.

https://doi.org/10.1109/CVPR46437.2021.00289

An open access version of this paper is provided by the Computer Vision Foundation.

Copyright

free_to_read

Share

 
COinS
 

Link to publisher version (DOI)

10.1109/CVPR46437.2021.00289