Consensus Maximisation Using Influences of Monotone Boolean Functions

August 11, 2021 · View on GitHub

Code for paper "Consensus Maximisation Using Influences of Monotone Boolean Functions" to be presented at CVPR 2021 - oral presentation.

Installation

The code was tested on a macOS Catalina and Ubuntu 16.04 with MATLAB 2019b. Requires MATLAB communications toolbox.

Install VlFeat (https://www.vlfeat.org/install-matlab.html)

Install SeDuMi: Optimization over symmeric cones. This is required for A*.

 * Download sedumi from the above URL.  
 * Copy sedumi folder in to folder linearASTAR.   
 * run script `install_sedumi.m`

Please note that in the paper the Feasibility/Infeasibility function is represented as $f\{0,1\}^n \to \{0,1\}$ wheras in the code the function is represented as $f\{0,1\}^n \to \{1,-1\}$ . Where $f(x) = -1$ means Infeasible.

Running the code

Simple Example - MBF-MaxCon

Two dimentional linear fitting with synthetic data

Run MaxConMBF_simple_example.m

Synthetic data experiments - MaxCon

Eight dim linear fitting with synthetic data - comparison and ablation studies

Run maxcon_linear_demo.m

Linear Fundamental Matrix Estimation - MaxCon

Run maxcon_linear_fundamental.m

Synthetic data experiments - Fourier Calculations

Calculate Fourier coefficients for a toy 2D line fitting problem using different sampling methods: "Exact", "Uniform sampling", "Goldreich-Levin", "MBF-ODonnell-2005"

Run demo_linear.m in MBF_basics folder

Calculate the error in influence estimation

Comparison between "uniform-sampling" and "exact" influences on a toy 2D line fitting problems Run influence_est_accuracy.m in MBF_basics folder

Code Reference

If you find this work useful in your research, please consider citing:

@inproceedings{tennakoon2021consensus,
  title={Consensus Maximisation Using Influences of Monotone Boolean Functions},
  author={Tennakoon, Ruwan and Suter, David and Zhang, Erchuan and Chin, Tat-Jun and Bab-Hadiashar, Alireza},
  booktitle={Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  pages={2866--2875},
  year={2021}
}

ASTAR code is from [Github Page]

Please acknowledge the original authors by citing in any academic publications that have made use of this package or part of it:

@InProceedings{Cai_2019_ICCV,
author = {Cai, Zhipeng and Chin, Tat-Jun and Koltun, Vladlen},
title = {Consensus Maximization Tree Search Revisited},
booktitle = {Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)},
year = {2019}
}