General coding scheme for families of digital curve segments

Abstract

This paper deals with sets consisting of digital curve segments which are presented on an n × n grid. The main result is a general coding scheme which can be applied to the sets of digital curve segments, which may consist even of digital curve segments that result from digitization of curves of different kinds. If h is an upper bound for the number of intersection points of two digitized curves, then h + 3 integer parameters are sufficient for the coding. The proposed coding scheme preserves an asymptotically optimal coding (the minimum possible number of bits is used) when h is assumed to be a constant. If it is allowed that h tends to infinity (when n tends to infinity, too), then the number of bits used for the coding is O(h2 · log n). In addition, the authors show that the coding of digital curve segments by their least-squares polynomial fits is possible. It turns out that such a coding is a special case of the general coding scheme proposed here.