A GENERAL CODING SCHEME FOR FAMILIES OF DIGITAL CURVE SEGMENTS

This paper deals with sets consisting of digital curve segments which are presented on an n x n grid. The main result is a general coding sc heme which can be applied to the sets of digital curve segments, which may consist even of digital curve segments that result from digitizat ion of curves of different kinds. If h is an upper bound for the numbe r of intersection points of two digitized curves, then h + 3 integer p arameters are sufficient for the coding. The proposed coding scheme pr eserves 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 num ber of bits used for the coding is O(h(2).log n). In addition, the aut hors show that the coding of digital curve segments by their least-squ ares polynomial fits is possible. It turns out that such a coding is a special case of the general coding scheme proposed here. (C) 1998 Aca demic Press.