Patent ID: 8265408

Claim:
A method for progressively encoding a digitized color image with M distinct colors allocated to a set of pixels using a data processing system, the digitized color image being provided by assigning each of the M distinct colors to at least one pixel in the set of pixels, the method comprising: 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 leaf 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).