A new characterization of digital lines by least square fits

Abstract

In this paper we prove that digital line segments and their least square line fits are in one-to-one correspondence and give a new simple representation (x1,n,b0,b1) of a digital line segment, where x1 and n are the x-coordinate of the left endpoint and the number of digital points, respectively, while b0 and b1 are the coefficients of the least square line fit Y=b0+b1X for the given digital line segment. An O(n log n) time algorithm for obtaining a digital line segment from its least square line fit is described.