Generating and using a color palette

• US 6,518,981 B2
• Filed: 11/12/1997
• Issued: 02/11/2003
• Est. Priority Date: 11/12/1997
• Status: Expired due to Fees

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Zhao, Jun, Kohler, Timothy L., Hui, Jonathan
• Primary Examiner(s): Huynh, Ra
• Application Number:
  US08/969,058
• Publication Number:
  US 20020080153A1
• Time in Patent Office: 1,917 Days
• Field of Search: 382/162, 382/164, 382/166, 382/168, 382/171, 382/163, 382/165, 382/170, 345/199, 345/431, 345/589, 345/590, 345/591, 345/593, 345/597, 345/600, 345/601, 345/604, 345/682, 358/525
• US Class Current: 715/764
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space

Abstract

To generate a color palette having m colors (such as 2⁸=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.

Claims

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 a product of the frequency of occurrence of the color in the pixel image times a weighting factor, the 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 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 a product of the frequency of occurrence of the quantized color times 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.

10. A method according to claim 9, wherein in said quantizing step the three least significant bits of each color component are set to zero.

11. A method according to claim 9, wherein the color space has been partitioned into approximately 216 cells.

12. A method according to claim 9, 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.

13. A method according to claim 9, further comprising a step of sorting the quantized colors in each cell according to relative frequencies of occurrence.

14. A method according to claim 9, further comprising a step of sorting the unselected colors according to vote values.

15. 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 a product of the frequency of occurrence of the color in the pixel image times a weighting factor, the 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.

16. Computer-executable process steps according to claim 15, wherein the colors in the pixel image data correspond identically to the colors in the color image.

17. Computer-executable process steps according to claim 15, wherein the colors in the pixel image are obtained by quantizing the colors in the color image.

18. Computer-executable process steps according to claim 17, wherein the quantization step includes a step to set to zero the three least significant bits of each color component.

19. Computer-executable process steps according to claim 15, wherein the frequency of occurrence of a color is determined by counting the number of pixels in the pixel image data having that color.

20. Computer-executable process steps according to claim 15, wherein the color space has been partitioned into approximately 216 cells.

21. Computer-executable process steps according to claim 15, 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.

22. Computer-executable process steps according to claim 21, 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.

23. 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 a product of the frequency of occurrence of the quantized color times 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.

24. Computer-executable process steps according to claim 23, wherein in said quantizing step the three least significant bits of each color component are set to zero.

25. Computer-executable process steps according to claim 23, wherein the color space has been partitioned into approximately 216 cells.

26. Computer-executable process steps according to claim 23, 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.

27. Computer-executable process steps according to claim 23, further comprising a step of sorting the quantized colors in each cell according to relative frequencies of occurrence.

28. Computer-executable process steps according to claim 23, further comprising a step to sort the unselected colors according to vote values.

29. 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 a product of the frequency of occurrence of the color in the pixel image times 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.

30. An apparatus according to claim 29, wherein the colors in the pixel image data correspond identically to the colors in the color image.

31. An apparatus according to claim 29, wherein the colors in the pixel image are obtained by quantizing the colors in the color image.

32. An apparatus according to claim 31, wherein the quantization step includes a step to set to zero the three least significant bits of each color component.

33. An apparatus according to claim 29, wherein the frequency of occurrence of a color is determined by counting the number of pixels in the pixel image data having that color.

34. An apparatus according to claim 29, wherein the color space has been partitioned into approximately 216 cells.

35. An apparatus according to claim 29, 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.

36. An apparatus according to claim 35, 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.

37. 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 a product of the frequency of occurrence of the quantized color times the assigned weighting factor for the quantized color, and (8) select m-n palette colors as the unselected colors with the highest vote values.

38. An apparatus according to claim 37, wherein in said quantizing step the three least significant bits of each color component are set to zero.

39. An apparatus according to claim 37, wherein the color space has been partitioned into approximately 216 cells.

40. An apparatus according to claim 37, 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.

41. An apparatus according to claim 37, further comprising a step to sort the quantized colors in each cell according to relative frequencies of occurrence.

42. An apparatus according to claim 37, further comprising a step to sort the unselected colors according to vote values.

43. A method for generating a color palette having m palette colors from a color image described in a color space, comprising:

selecting n palette colors as representative colors from a number of cells into which the color space has been partitioned and colors of the input image have been assigned, wherein a color selection associated with a cell is made independent of another cell'"'"'s color selection, each color selection based on a frequency of occurrence of colors within the cell; and

selecting m-n palette colors from remaining colors based at least in part on the frequency of occurrence of the remaining colors across the entire input image.

49. A method according to claim 43, wherein the m-n palette colors are selected based on a ranking of the remaining colors across all of the cells, the ranking is based at least in part on the frequency of occurrence of a remaining color relative to other remaining colors in a cell.

50. A method according to claim 49, wherein the ranking comprises a weighted frequency which is based at least in part on a frequency ranking within the cells.

44. 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:

a first selecting step to select n palette colors as representative colors from a number of cells into which the color space has been partitioned and colors of the input image have been assigned, wherein a color selection associated with one cell is made independent of another cell'"'"'s color selection, each color selection based on a frequency of occurrence of colors within the cell ; and

a second selecting step to select m-n palette colors from remaining colors based at least in part on the frequency of occurrence of the remaining colors in the input image.

51. Computer executable process steps according to claim 44, wherein the m-n palette colors are selected based on a ranking of the remaining colors across all of the cells, the ranking is based at least in part on the frequency of occurrence of a remaining color relative to other remaining colors in a cell.

52. A method according to claim 51, wherein the ranking comprises a weighted frequency which is based at least in part on a frequency ranking within the cells.

45. A method for generating a color palette having m palette colors from a color image described in a color space, comprising:

selecting n palette colors as representative colors from a number of cells into which the color space has been partitioned and colors of the input image have been assigned, based on a first criteria that selects a representative color from a cell, one cell'"'"'s color selection being independent of another cell'"'"'s color selection, the first criteria includes a frequency of occurrence of colors within the cell; and

selecting m-n palette colors from remaining colors based on a second criteria that is different from said first criteria.

46. A method according to claim 45 wherein the second criteria comprises a weighted frequency which is based at least in part on a frequency ranking within the cells.

48. Computer-executable process steps according to claim 46 wherein the second criteria comprises a weighted frequency which is based at least in part on a frequency ranking within the cells.

47. 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:

a first selecting step to select n palette colors as representative colors from a number of cells into which the color space has been partitioned and colors of the input image have been assigned, based on a first criteria that selects a representative color from a cell, one cell'"'"'s color selection being independent of another cell'"'"'s color selection, the first criteria includes a frequency of occurrence of colors within the cell; and

a second selecting step to select m-n palette colors from remaining colors based on a second criteria that is different from said first criteria.