Patent ID: 8022963

Claim:
A method for creating, from a digitized color image with N distinct colors using a data processing system, a tree-structured partitioning of all pixels in the digitized color image into M disjoint clusters, wherein M is less than or equal to N, each color in the N distinct colors is digitally represented in a color palette by a plurality of P-bit bytes, and the P bits in each P-bit byte are ordered from most significant to least significant, the method comprising: (a) providing a root node comprising each color in the N distinct colors; (b) providing a plurality of sibling nodes at a first level of nodes, wherein each sibling node in the plurality of sibling nodes is linked to the root node, and each color in the N distinct colors is allocated by the data processing system to a sibling node in the first level of nodes based on a value of a first bit in each P-bit byte in the plurality of P-bit bytes; (c) for each node in a k th level of nodes, that node at the k th level comprising more than one color in the N distinct colors, providing a distinct plurality of sibling nodes at a (k+1) th level of nodes, wherein each sibling node in the distinct plurality of sibling nodes at the (k+1) th level is linked to that node at the k th level, and each color in that node at the k th level is allocated by the data processing system to a sibling node in the distinct plurality of sibling nodes at the (k+1) th level based on a value of a (k+1) th bit in each P-bit byte in the plurality of P-bit bytes for that color, until each color in the N distinct colors is allocated to a distinct leaf node comprising that color alone; and (d) for each distinct plurality of sibling nodes, and for each pair of leaf sibling nodes included in a distinct plurality of sibling nodes, determining an associated entropy-constrained cost increment to determine a plurality of entropy-constrained cost increments including the associated entropy-constrained cost increment for each pair of leaf sibling nodes, and then selecting and merging pairs of leaf sibling nodes based on the plurality of entropy-constrained cost increments, until there are only M leaf nodes left.