Chain Coding with a Hexagonal Lattice

This paper investigates the performance of chain code quantization of general curves using a hexagonal lattice structure, as a means of improving efficiency over the standard square lattice. Performance is first computed theoretically, assuming a generalization of grid-intersect quantization, and the curve to be quantized is assumed to be a straight line. An algorithm is then developed to perform chain coding using the hex lattice. Computer simulations were performed to evaluate hexagonal chain coding for a variety of curves, including circles of various curva-ture, straight lines, and a stochastic curve model. We find that the straight-line theory is substantiated for curves whose radius of curvature is roughly twice the lattice constant. For a given peak error in quanti-zation, hexagonal coding reduces the bit rate about 15 percent relative to the square lattice codes, and exhibits qualitative improvements in fidelity as well.