2

ABSTRACT: This paper 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 for dimension , where , together with space complexity where is the number of points. Key words: line fitting; plane fitting; digital geometry; discrete optimization; consensus set I