2013 | OriginalPaper | Chapter
Efficient Robust Digital Annulus Fitting with Bounded Error
Authors : Minh Son Phan, Yukiko Kenmochi, Akihiro Sugimoto, Hugues Talbot, Eric Andres, Rita Zrour
Published in: Discrete Geometry for Computer Imagery
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A digital annulus is defined as a set of grid points lying between two circles sharing an identical center and separated by a given width. This paper deals with the problem of fitting a digital annulus to a given set of points in a 2D bounded grid. More precisely, we tackle the problem of finding a digital annulus that contains the largest number of inliers. As the current best algorithm for exact optimal fitting has a computational complexity in
O
(
N
3
log
N
) where
N
is the number of grid points, we present an approximation method featuring linear time complexity and bounded error in annulus width, by extending the approximation method previously proposed for digital hyperplane fitting. Experiments show some results and runtime in practice.