Efficient labeling procedures for image partition encoding

A new approach to the lossless encoding of an image partition is presented. The segmented image is first described by a quadtree, whose leaves are then grouped by a labeling procedure to represent any configuration. Label assignment exploits the 'four colors' theorem, thus allowing to encode each label with 2 bits. A simple and efficient label assignment algorithm is also proposed, which further reduces the code entropy. The proposed representation is an effective alternative to region- and edge-based partition encoders, used in II generation image coders. (C) 2000 Published by Elsevier Science B.V. All rights reserved.