The Maximum Consensus Problem: Recent Algorithmic Advances

[Publication info] - [Abstract] - [Table of contents] - [Sample chapter] - [Sample code] - [Errata]

Publication info

T.-J. Chin and D. Suter
The maximum consensus problem: recent algorithmic advances
Synthesis Lectures on Computer Vision (Eds. Gerard Medioni and Sven Dickinson)
Morgan & Claypool Publishers, San Rafael, CA, U.S.A., Feb 2017

Publisher's page (for purchasing/subscription information), Publisher's promo sheet

Book on Amazon


Outlier-contaminated data is a fact of life in computer vision. For computer vision applications to perform reliably and accurately in practical settings, the processing of the input data must be conducted in a robust manner. In this context, the maximum consensus robust criterion plays a critical role by allowing the quantity of interest to be estimated from noisy and outlier-prone visual measurements. The maximum consensus problem refers to the problem of optimizing the quantity of interest according to the maximum consensus criterion. This book provides an overview of the algorithms for performing this optimization. The emphasis is on the basic operation or "inner workings" of the algorithms, and on their mathematical characteristics in terms of optimality and efficiency. The applicability of the techniques to common computer vision tasks is also highlighted. By collecting existing techniques in a single article, this book aims to trigger further developments in this theoretically interesting and practically important area.

Table of contents

  1. The Maximum Consensus Problem
    1. Introduction
    2. Relation to other robust fitting methods
    3. Problem difficulty
    4. Bibliographical remarks
  2. Approximate Algorithms
    1. Introduction
    2. Random sample consensus
    3. L1 minimisation
    4. Chebyshev approximation
    5. LP-type problems
    6. The K-slack method
    7. Exact penalty method
    8. Evaluation
    9. Bibliographical remarks
  3. Exact Algorithms
    1. Introduction
    2. Optimal line fitting
    3. Integer linear programming method
    4. Robust point set registration
    5. Tractable algorithms with subset search
    6. Tree search
    7. Bibliographical remarks
  4. Preprocessing for Maximum Consensus
    1. Introduction
    2. Geometrically-inspired approaches
    3. Integer linear programming approach
    4. Bibliographical remarks

Sample code