Fast recognition of a Digital Straight Line subsegment: Two algorithms of logarithmic time complexity

Given a Digital Straight Line (DSL) of known characteristics (a,b,μ)(a,b,μ), we address the problem of computing the characteristics of any of its subsegments. We propose two new algorithms that use the fact that a digital straight segment (DSS) can be defined by its set of separating lines. The representation of this set in the Z2Z2 space leads to a first algorithm of logarithmic time complexity. This algorithm precises and extends existing results for DSS recognition algorithms. The other algorithm uses the dual representation of the set of separating lines. It consists of a smart walk in the so called Farey fan, which can be seen as the representation of all the possible sets of separating lines for DSSs. Indeed, we take profit of the fact that the Farey fan of order nn represents in a certain way all the digital segments of length nn. The computation of the characteristics of a DSL subsegment is then equivalent to the localization of a point in the Farey fan. Using fine arithmetical properties of the fan, we design a fast algorithm of theoretical complexity O(log(n))O(log(n)) where nn is the length of the subsegment. Experiments show that our algorithms are also efficient in practice, with a comparison to the ones previously proposed by Lachaud and Said (2013): in particular, the second one is faster in the case of “small” segments.