Method, system and computer program product for entropy constrained color splitting for palette images with pixel-wise splitting

A physical computer-readable device for use on a computer system to progressively encode a digitized color image with M distinct colors allocated to a set of pixels, the digitized color image being provided by assigning each of the M distinct colors to an associated subset of pixels in the set of pixels, the physical computer-readable device comprising:

• a non-transitory recording medium;
• and,
• means recorded on the recording medium for instructing the computer system to perform the steps of:
• a) initializing a tree structure by providing at least one starting leaf node comprising a subset of pixels from the set of pixels;
• b) determining at least one representative color for each starting leaf node;
• c) based on the at least one representative color for each starting node, initializing a reconstructed image with fewer than M colors, and
• d) iteratively growing the tree structure and updating the reconstructed image by
• i) based on an associated achievable cost, selecting a leaf node n to become a non-leaf node n linked to two new leaf nodes, wherein the associated achievable cost is determined by
• determining an associated change in distortion resulting from turning the leaf node n into the non-leaf node n linked to the two new leaf nodes;
• based on the reconstructed image, determining an associated increase in entropy rate resulting from turning the leaf node n into the non-leaf node n linked to the two new leaf nodes;
• and,
• based on the associated change in distortion and the associated increase in entropy rate, determining the associated achievable cost;
• ii) creating the two new leaf nodes by allocating each pixel in leaf node n to one of the two new leaf nodes;
• iii) determining a respective representative color for each of the two new leaf nodes;
• iv) encoding the index information associated with the leaf node n and the respective representative colors of the two new leaf nodes;
• v) based on the reconstructed image, encoding color updating information regarding each pixel, of the digitized color image, corresponding to the respective representative colors of the two new leaf nodes;
• and
• vi) updating the reconstructed image by updating the color of each pixel associated with leaf node n with the representative color corresponding with one of the two new leaf nodes according to the allocation of pixels in leaf node n to one of the two new leaf nodes in step d)ii).

A system for progressively encoding a digitized color image with M distinct colors allocated to a set of pixels, the digitized color image being provided by assigning each of the M distinct colors to an associated subset of pixels in the set of pixels, the system comprising:

• a recording medium;
• and,
• means including a processor for performing the steps of:
• a) initializing a tree structure by providing at least one starting leaf node comprising a subset of pixels from the set of pixels;
• b) determining at least one representative color for each starting leaf node;
• c) based on the at least one representative color for each starting node, initializing a reconstructed image with fewer than M colors, and
• d) iteratively growing the tree structure and updating the reconstructed image by
• i) based on an associated achievable cost, selecting a leaf node n to become a non-leaf node n linked to two new leaf nodes, wherein the associated achievable cost is determined by
• determining an associated change in distortion resulting from turning the leaf node n into the non-leaf node n linked to the two new leaf nodes;
• based on the reconstructed image, determining an associated increase in entropy rate resulting from turning the leaf node n into the non-leaf node n linked to the two new leaf nodes;
• and,
• based on the associated change in distortion and the associated increase in entropy rate, determining the associated achievable cost;
• ii) creating the two new leaf nodes by allocating each pixel in leaf node n to one of the two new leaf nodes;
• iii) determining a respective representative color for each of the two new leaf nodes;
• iv) encoding the index information associated with the leaf node n and the respective representative colors of the two new leaf nodes;
• v) based on the reconstructed image, encoding color updating information regarding each pixel, of the digitized color image, corresponding to the respective colors of the two new leaf nodes;
• and
• vi) updating the reconstructed image by updating the color of each pixel associated with leaf node n with the representative color corresponding with one of the two new leaf nodes according to the allocation of pixels in leaf node n to one of the two new leaf nodes in step d)ii).