Lossless shape coding using the four colors theorem

This paper presents an original approach to the lossless encoding of an exhaustive image partition. The method is based on a preliminary quad-tree description of the partition that associates adaptive sized blocks to the leaves of the tree. The generated blocks can have a minimum dimension of one pixel, in order to fit every possible region shape. Using such a preliminary quad-tree, coded with just a few bits, we univocally describe the partition using some additional information that relates together the leaves. Every leaf of the quad-tree is given a label, with the rule that two neighboring leaves share the same label only if they belong to the same region. By exploiting a classical result of the planar geometry, known as the four colors theorem, it is possible to reduce the number of labels (i.e., colors) to a theoretical limit of four. A simple and efficient color allocation algorithm is also proposed, which uses more than four colors, but that reduces the entropy to less than 2 bits per color. The achieved representation is particularly useful in region-based image coders, for it greatly reduces the code dimension as compared to classical edge-based methods