Generating and using a color palette

Abstract

To generate a color palette having m colors (such as 2 8 =256 colors) from a color image described in a color space, pixel image data corresponding to the color image is first obtained. A frequency of occurrence for each color in the pixel image data is then determined. Each color in the pixel image data is assigned to one of a predetermined number of cells into which the color space has been partitioned, the predetermined number being not greater than m. The most commonly occurring color is selected in each cell in which a color exists, so as to obtain n palette colors. A vote value is calculated 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. Thereafter, m-n colors are selected as the unselected colors with the highest vote values. Also, input colors in a color image described in a color space are mapped 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 in each cell that includes an input color. The mapping is performed by determining in which cell each input color lies, and mapping each input color to the closest palette color from among all palette colors in the cell identified for that input color.

What is claimed is:  
     
         1 . A method for generating a color palette having m colors from a color image described in a color space, comprising: 
 obtaining pixel image data corresponding to the color image;    determining a frequency of occurrence for each color in the pixel image data;    assigning 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 of selecting the most commonly occurring color in each cell in which a color exists, so as to obtain n palette colors;    calculating 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 of selecting m-n colors as the unselected colors with the highest vote values.    
     
     
         2 . A method according to  claim 1 , wherein the colors in the pixel image data correspond identically to the colors in the color image.  
     
     
         3 . A method according to  claim 1 , wherein the colors in the pixel image are obtained by quantizing the colors in the color image.  
     
     
         4 . A method according to  claim 3 , wherein the quantization step includes a step of setting to zero the three least significant bits of each color component.  
     
     
         5 . A method according to  claim 1 , wherein the frequency of occurrence of a color is determined by counting the number of pixels in the pixel image data having that color.  
     
     
         6 . A method according to  claim 1 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         7 . A method according to  claim 1 , wherein the weighting factors monotonically decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         8 . A method according to  claim 7 , wherein the weighting factors linearly decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         9 . A method according to  claim 1 , wherein the vote value calculated for each unselected color is equal to a product of the frequency of occurrence of the color in the pixel image data times the weighting factor for the color.  
     
     
         10 . 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.    
     
     
         11 . A method according to  claim 10 , wherein in said quantizing step the three least significant bits of each color component are set to zero.  
     
     
         12 . A method according to  claim 10 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         13 . A method according to  claim 10 , wherein the weighting factors decrease linearly as the rank decreases from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         14 . A method according to  claim 10 , wherein the vote value assigned to each unselected color is equal to a product of the frequency of occurrence of the color times the weighting factor calculated for the color.  
     
     
         15 . A method according to  claim 10 , further comprising a step of sorting the quantized colors in each cell according to relative frequencies of occurrence.  
     
     
         16 . A method according to  claim 10 , further comprising a step of sorting the unselected colors according to vote values.  
     
     
         17 . A method 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: 
 determining in which cell each input color lies; and    mapping 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.    
     
     
         18 . A method according to  claim 17 , wherein said determining step includes a step of right shifting color component values for an input color by three bits.  
     
     
         19 . A method according to  claim 18 , wherein said determining step further includes a step of determining in which one of plural intervals each right-shifted color component value lies.  
     
     
         20 . A method according to  claim 17 , wherein said mapping step includes the steps of: 
 calculating, for each palette color assigned to the cell identified for a subject input color, a sum of absolute values of differences between color component values for the input color and corresponding color component values for each such palette color; and    mapping the subject input color to the palette color in the cell identified for the subject input color corresponding to the smallest sum calculated in said calculating step.    
     
     
         21 . A method according to  claim 17 , wherein in said determining step a three-dimensional vector corresponding to a cell is determined for each input color by partitioning each color component in the color space into a predetermined number of ranges, and determining into which range each color component of the input color falls.  
     
     
         22 . A method according to  claim 17 , wherein in said mapping step an error is calculated between a subject input color and the palette color to which the subject input color is mapped, and the calculated error is distributed to at least one pixel adjacent to a pixel having the subject input color.  
     
     
         23 . A method according to  claim 22 , wherein the calculated error is distributed to exactly one pixel randomly selected from plural pixels arranged in a predetermined pattern around the pixel having the subject input color.  
     
     
         24 . A method according to  claim 22 , wherein at least one cell has been assigned a palette color whose color components place the palette color in a different cell.  
     
     
         25 . A method according to  claim 22 , wherein a cell which does not include a palette color has been assigned a palette color whose color component values are closest to the center of the cell that does not include a palette color.  
     
     
         26 . 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.    
     
     
         27 . Computer-executable process steps according to  claim 26 , wherein the colors in the pixel image data correspond identically to the colors in the color image.  
     
     
         28 . Computer-executable process steps according to  claim 26 , wherein the colors in the pixel image are obtained by quantizing the colors in the color image.  
     
     
         29 . Computer-executable process steps according to  claim 28 , wherein the quantization step includes a step to set to zero the three least significant bits of each color component.  
     
     
         30 . Computer-executable process steps according to  claim 26 , wherein the frequency of occurrence of a color is determined by counting the number of pixels in the pixel image data having that color.  
     
     
         31 . Computer-executable process steps according to  claim 26 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         32 . Computer-executable process steps according to  claim 26 , wherein the weighting factors monotonically decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         33 . Computer-executable process steps according to  claim 32 , wherein the weighting factors linearly decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         34 . Computer-executable process steps according to  claim 26 , wherein the vote value calculated for each unselected color is equal to a product of the frequency of occurrence of the color in the pixel image data times the weighting factor for the color.  
     
     
         35 . 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.    
     
     
         36 . Computer-executable process steps according to  claim 35 , wherein in said quantizing step the three least significant bits of each color component are set to zero.  
     
     
         37 . Computer-executable process steps according to  claim 35 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         38 . Computer-executable process steps according to  claim 35 , wherein the weighting factors decrease linearly as the rank decreases from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         39 . Computer-executable process steps according to  claim 35 , wherein the vote value assigned to each unselected color is equal to a product of the frequency of occurrence of the color times the weighting factor calculated for the color.  
     
     
         40 . Computer-executable process steps according to  claim 35 , further comprising a step of sorting the quantized colors in each cell according to relative frequencies of occurrence.  
     
     
         41 . Computer-executable process steps according to  claim 35 , further comprising a step to sort the unselected colors according to vote values.  
     
     
         42 . Computer-executable process steps stored on a computer readable medium to map 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: 
 a determining step to determine in which cell each input color lies; and    a mapping step to 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.    
     
     
         43 . Computer-executable process steps to according to  claim 42 , wherein said determining step includes a step to right shift color component values for an input color by three bits.  
     
     
         44 . Computer-executable process steps according to  claim 43 , wherein said determining step further includes a step to determine in which one of plural intervals each right-shifted color component value lies.  
     
     
         45 . Computer-executable process steps according to  claim 17 , wherein said mapping step includes: 
 a calculating step to calculate, for each palette color assigned to the cell identified for a subject input color, a sum of absolute values of differences between color component values for the input color and corresponding color component values for each such palette color; and    a mapping step to map the subject input color to the palette color in the cell identified for the subject input color corresponding to the smallest sum calculated in said calculating step.    
     
     
         46 . Computer-executable process steps according to  claim 42 , wherein in said determining step a three-dimensional vector corresponding to a cell is determined for each input color by partitioning each color component in the color space into a predetermined number of ranges, and determining into which range each color component of the input color falls.  
     
     
         47 . Computer-executable process steps according to  claim 42 , wherein in said mapping step an error is calculated between a subject input color and the palette color to which the subject input color is mapped, and the calculated error is distributed to at least one pixel adjacent to a pixel having the subject input color.  
     
     
         48 . Computer-executable process steps according to  claim 47 , wherein the calculated error is distributed to exactly one pixel randomly selected from plural pixels arranged in a predetermined pattern around the pixel having the subject input color.  
     
     
         49 . Computer-executable process steps according to  claim 47 , wherein at least one cell has been assigned a palette color whose color components place the palette color in a different cell.  
     
     
         50 . Computer-executable process steps according to  claim 47 , wherein a cell which does not include a palette color has been assigned a palette color whose color component values are closest to the center of the cell that does not include a palette color.  
     
     
         51 . 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.    
     
     
         52 . An apparatus according to  claim 51 , wherein the colors in the pixel image data correspond identically to the colors in the color image.  
     
     
         53 . An apparatus according to  claim 51 , wherein the colors in the pixel image are obtained by quantizing the colors in the color image.  
     
     
         54 . An apparatus according to  claim 53 , wherein the quantization step includes a step to set to zero the three least significant bits of each color component.  
     
     
         55 . An apparatus according to  claim 51 , wherein the frequency of occurrence of a color is determined by counting the number of pixels in the pixel image data having that color.  
     
     
         56 . An apparatus according to  claim 51 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         57 . An apparatus according to  claim 51 , wherein the weighting factors monotonically decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         58 . An apparatus according to  claim 57 , wherein the weighting factors linearly decrease as the ranks decrease from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         59 . An apparatus according to  claim 1 , wherein the vote value calculated for each unselected color is equal to a product of the frequency of occurrence of the color in the pixel image data times the weighting factor for the color.  
     
     
         60 . 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.    
     
     
         61 . An apparatus according to  claim 60 , wherein in said quantizing step the three least significant bits of each color component are set to zero.  
     
     
         62 . An apparatus according to  claim 60 , wherein the color space has been partitioned into approximately 216 cells.  
     
     
         63 . An apparatus according to  claim 60 , wherein the weighting factors decrease linearly as the rank decreases from the most frequently occurring unselected color to the least frequently occurring unselected color in a cell.  
     
     
         64 . An apparatus according to  claim 60 , wherein the vote value assigned to each unselected color is equal to a product of the frequency of occurrence of the color times the weighting factor calculated for the color.  
     
     
         65 . An apparatus according to  claim 60 , further comprising a step to sort the quantized colors in each cell according to relative frequencies of occurrence.  
     
     
         66 . An apparatus according to  claim 60 , further comprising a step to sort the unselected colors according to vote values.  
     
     
         67 . 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.    
     
     
         68 . An apparatus according to  claim 67 , wherein said determining step includes a step to right shift color component values for an input color by three bits.  
     
     
         69 . An apparatus according to  claim 68 , wherein said determining step further includes a step to determine in which one of plural intervals each right-shifted color component value lies.  
     
     
         70 . An apparatus according to  claim 67 , wherein said mapping step includes steps to: 
 calculate, for each palette color assigned to the cell identified for a subject input color, a sum of absolute values of differences between color component values for the input color and corresponding color component values for each such palette color; and    map the subject input color to the palette color in the cell identified for the subject input color corresponding to the smallest sum calculated in said calculating step.    
     
     
         71 . An apparatus according to  claim 67 , wherein in said determining step a three-dimensional vector corresponding to a cell is determined for each input color by partitioning each color component in the color space into a predetermined number of ranges, and determining into which range each color component of the input color falls.  
     
     
         72 . An apparatus according to  claim 67 , wherein in said mapping step an error is calculated between a subject input color and the palette color to which the subject input color is mapped, and the calculated error is distributed to at least one pixel adjacent to a pixel having the subject input color.  
     
     
         73 . An apparatus according to  claim 72 , wherein the calculated error is distributed to exactly one pixel randomly selected from plural pixels arranged in a predetermined pattern around the pixel having the subject input color.  
     
     
         74 . An apparatus according to  claim 72 , wherein at least one cell has been assigned a palette color whose color components place the palette color in a different cell.  
     
     
         75 . An apparatus according to  claim 72 , wherein a cell which does not include a palette color has been assigned a palette color whose color component values are closest to the center of the cell that does not include a palette color.