Patent ID: 7177464

Claim:
A method for generating an optimized color palette having a target number of colors for a display comprised of a specification of color values for a plurality of pixels, wherein each pixel has a specific color value, the method comprising: (a) obtaining a color octree corresponding to a mapping of pixel color values, wherein the color octree includes a plurality of leaf nodes tracking a cumulative color value for a plurality of pixels in the display and wherein the color octree includes unique color lock thresholds for levels of the color octree; (b) for each node in the color octree having all children that are leaf nodes, determining whether the number of pixels tracked by a current node is less than a merging threshold; (c) if a number of pixels tracked by the current node is less than a merging threshold, determining whether a number of unique colors represented by the node is greater than a unique color lock threshold corresponding to the node; (d) if the number of unique colors represented by the current node is greater than the unique color lock threshold, merging all the child leaf nodes into the current node; (e) for each node in the color octree having at least one child that is a leaf node, determining whether the number of pixels tracked by a leaf node child is less than a merging threshold; (f) if a number of pixels tracked by the leaf node child is less than a merging threshold, determining whether a number of unique colors represented by the leaf node child is greater than a unique color lock threshold corresponding to the node; (g) if the number of unique colors represented by the leaf node child is greater than the unique color lock threshold, merging the leaf node child into a sibling node; (h) increasing the merging threshold and repeating (a)–(d), until the number of leaf nodes is less than the target number of colors in the optimized color palette, and (i) if the number of leaf nodes is less than or equal to the target number of colors in the optimized color palette, generating a color palette corresponding to a mapping each remaining leaf node color value.