A simple algorithm for digital line recognition in the general case

This paper is concerned with the digital line recognition problem for lines of fixed thickness in the naive and general cases. Previous incremental algorithms from Debled-Rennesson and Reveillès [A linear algorithm for segmentation of digital curves, Int. J. Pattern Recognition Artif. Intell. 9(6) (1995)] and from Buzer [A linear incremental algorithm for naive and standard digital lines and planes recognition, Graphical Models 65(1–3) (2003) 61–76] deal with the 8-connected case or with sophisticated machinery coming from linear programming. We present the first elementary method that works with any set of points (not necessarily 8-connected) and we propose a linear time algorithm under some restrictions. This paper deals with implementation details giving pseudo-code of our method. We insist on linking the recognition problem to the intrinsic properties of convex hulls.