51. Optimal consensus set for digital line and plane fitting
- Author
-
Akihiro Sugimoto, Yskandar Hamam, Lilian Buzer, Ikuko Shimizu, Rita Zrour, Hugues Talbot, Yukiko Kenmochi, SIC, XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Poitiers, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), French South African Institute of Technology (F’SATI), Tshwane University of Technology [Pretoria] (TUT), Tokyo University of Agriculture and Technology (TUAT), and National Institute of Informatics (NII)
- Subjects
digital geometry ,Line fitting ,Deterministic algorithm ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Set (abstract data type) ,Dimension (vector space) ,0202 electrical engineering, electronic engineering, information engineering ,Digital geometry ,line fitting ,Electrical and Electronic Engineering ,Time complexity ,Mathematics ,Discrete mathematics ,Plane (geometry) ,[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] ,020207 software engineering ,Binary logarithm ,Electronic, Optical and Magnetic Materials ,plane fitting ,[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV] ,discrete optimization ,020201 artificial intelligence & image processing ,Computer Vision and Pattern Recognition ,consensus set ,Software - Abstract
International audience; This article presents a new method for fitting a digital line or plane to a given set of points in a 2D or 3D image in the presence of noise by maximizing the number of inliers, namely the consensus set. By using a digital model instead of a continuous one, we show that we can generate all possible consensus sets for model fitting. We present a deterministic algorithm that efficiently searches the optimal solution with time complexity O(Nd log N) for dimension d, where d = 2,3, together with space complexity O(N) where N is the number of points.
- Published
- 2011
- Full Text
- View/download PDF