Patent Document ID: 8260071
Application ID: 13186857
Patent Status: 1

Claim One:
1. 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 an associated subset of pixels in the set of pixels, the method comprising: (a) initializing a tree structure by providing at least one starting leaf node comprising a set of colors from the M distinct colors; (b) determining at least one representative color for each starting leaf node; and (c) growing the tree structure 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; 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 color in leaf node n to one of the two new leaf nodes by determining, for each of the two new leaf nodes, an associated biased distortion measure based on rate and distortion for allocating the color to that new leaf node, and allocating the color in leaf node n to the new leaf node having a lower associated biased distortion measure wherein, for each of the two new leaf nodes, the associated biased distortion measure is determined by; determining an associated change in distortion resulting from allocating the color to the new leaf node; determining an associated increase in entropy rate resulting from allocating the color to the new leaf node, wherein the step of determining an associated increase in entropy rate resulting from allocating that color to the new leaf node comprises, determining, for each pixel in the subset of pixels for that color, a set of neighboring pixels, wherein each pixel in the set of neighboring pixels borders the pixel; based on the set of neighboring pixels, determining an entropy rate increase for the pixel; based on entropy rate increases of all pixels in the subset of pixels for that color, determining an associated increase in entropy rate resulting from allocating that color to the new leaf node; and, based on the associated change in distortion and the associated increase in entropy rate, determining the associated biased distortion measure. (iii) determining a representative color for each of the two new leaf nodes; and (iv) encoding the index information associated with the leaf node n, the representative colors of the two new leaf nodes, and color updating information regarding a plurality of pixels of the digitized color image corresponding to the respective representative colors of the two new leaf nodes.