Generating and using a color palette

A method for generating a color palette having m colors from a color image comprising plural pixels, each pixel described in a color space, comprising:

• quantizing the color of each pixel in the color image by zeroing least significant bits of each color component for the pixel;
• counting the frequency of occurrence of each quantized color;
• assigning each quantized color in the color image to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m;
• a first selecting step of selecting the most commonly occurring quantized color in each cell in which a quantized color exists, based on the count, so as to obtain n palette colors;
• ranking the unselected colors in each cell based on their relative frequencies of occurrence, with higher ranking colors occurring more frequently than lower ranking colors in the same cell, the unselected colors being the quantized colors not selected in the first selecting step;
• calculating a weighting factor for each unselected color, the weighting factor being based on the rank of the unselected color, with higher ranking colors receiving a greater weighting factor than lower ranking colors;
• assigning a vote value to each unselected color, the vote value being based at least in part on the frequency of occurrence of the quantized color and the assigned weighting factor for the quantized color;
• and
• a second selecting step of selecting m-n palette colors as the unselected colors with the highest vote values.

Computer-executable process steps stored on a computer readable medium to generate a color palette having m colors from a color image described in a color space, comprising:

• an obtaining step to obtain pixel image data corresponding to the color image;
• a determining step to determine a frequency of occurrence for each color in the pixel image data;
• an assigning step to assign each color in the pixel image data to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m;
• a first selecting step to select the most commonly occurring color in each cell in which a color exists, so as to obtain n palette colors;
• a calculating step to calculate a vote value for each unselected color, the vote value being based at least in part on the frequency of occurrence of the color in the pixel image and a weighting factor based on a rank of the color in its corresponding cell, the unselected colors being the colors not selected in the first selecting step;
• and
• a second selecting step to select m-n colors as the unselected colors with the highest vote values.

Computer-executable process steps stored on a computer readable medium to generate a color palette having m colors from a color image comprising plural pixels, each pixel described in a color space, comprising:

• a quantizing step to quantize the color of each pixel in the color image by zeroing least significant bits of each color component for the pixel;
• a counting step to count the frequency of occurrence of each quantized color;
• a cell assigning step to assign each quantized color in the color image to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m;
• a first selecting step to select the most commonly occurring quantized color in each cell in which a quantized color exists, based on the count, so as to obtain n palette colors;
• a ranking step to rank the unselected colors in each cell based on their relative frequencies of occurrence, with higher ranking colors occurring more frequently than lower ranking colors in the same cell, the unselected colors being the quantized colors not selected in the first selecting step;
• a calculating step to calculate a weighting factor for each unselected color, the weighting factor being based on the rank of the unselected color, with higher ranking colors receiving a greater weighting factor than lower ranking colors;
• a vote value assigning step to assign a vote value to each unselected color, the vote value being based at least in part on the frequency of occurrence of the quantized color and the assigned weighting factor for the quantized color;
• and
• a second selecting step to select m-n palette colors as the unselected colors with the highest vote values.

An apparatus for generating a color palette having m colors from a color image described in a color space, comprising:

• input means for inputting pixel image data corresponding to the color image;
• a memory for storing the pixel image data and executable process steps;
• and
• a processor for executing the process steps stored in said memory so as to (1) determine a frequency of occurrence for each color in the pixel image data, (2) assign each color in the pixel image data to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m, (3) select the most commonly occurring color in each cell in which a color exists, so as to obtain n palette colors, (4) calculate a vote value for each unselected color, the vote value being based at least in part on the frequency of occurrence of the color in the pixel image and a weighting factor based on a rank of the color in its corresponding cell, the unselected colors being the colors not selected in the first selecting step, and (5) select m-n colors as the unselected colors with the highest vote values.

An apparatus for generating a color palette having m colors from a color image comprising plural pixels, each pixel described in a color space, comprising:

• input means for inputting pixel image data corresponding to the color image;
• a memory for storing the pixel image data and executable process steps;
• and
• a processor for executing the process steps stored in said memory so as to (1) quantize the color of each pixel in the color image by zeroing least significant bits of each color component for the pixel, (2) count the frequency of occurrence of each quantized color, (3) assign each quantized color in the color image to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m, (4) select the most commonly occurring quantized color in each cell in which a quantized color exists, based on the count, so as to obtain n palette colors, (5) rank the unselected colors in each cell based on their relative frequencies of occurrence, with higher ranking colors occurring more frequently than lower ranking colors in the same cell, the unselected colors being the quantized colors not selected in the first selecting step, (6) calculate a weighting factor for each unselected color, the weighting factor being based on the rank of the unselected color, with higher ranking colors receiving a greater weighting factor than lower ranking colors, (7) assign a vote value to each unselected color, the vote value being based at least in part on the frequency of occurrence of the quantized color and the assigned weighting factor for the quantized color, and (8) select m-n palette colors as the unselected colors with the highest vote values.

An apparatus for mapping input colors in a color image described in a color space to a reduced palette of m colors derived by partitioning the color space into a predetermined number of cells, there being at least one palette color assigned to each cell, comprising:

• input means for inputting pixel image data corresponding to the color image;
• a memory for storing the pixel image data, the palette and executable process steps;
• and
• a processor for executing the process steps stored in said memory so as to (1) determine in which cell each input color lies, and (2) map each input color to the closest palette color from among all palette colors assigned to the cell identified for that input color in said determining step.