Method, system and software product for color image encoding

A method for deriving a new index sequence representing a pixel mapping and a new output function representing a color palette for a new digitized color image derived from an original digitized color image both defined on n pixels, wherein the original digitized color image is provided by N distinct colors being allocated to the n pixels, the new digitized color image is provided by M distinct colors being allocated to the n pixels, the new index sequence has n index members for representing the n pixels and the new output function is for mapping the n index members to the M colors, the method comprising:

• (a) directing a data processing device to provide a first new index sequence by partitioning all pixels in the original digitized color image into M disjoint clusters based on a color of each pixel in the original digitized color image without regard to the location of the pixel in the original digitized color image, wherein M is less than or equal to N;
• (b) directing a data processing device to provide a first new output function for providing a one-to-one mapping of the M distinct colors onto the pixels in the M disjoint clusters;
• (c) directing a data processing device to apply a soft decision optimization process to the first new index sequence and the first new output function to provide the new index sequence and the new output function respectively based on, for each member of the first new index sequence, how a color value assigned to that member by the first new output function correlates with the color value assigned to at least one other member of the first new index sequence by the first new output function, and wherein step (c) comprises applying an iterative soft decision optimization process and determining, after each iteration, an incremental reduction in a cost function representing compression and distortion of the original digitized color image, and step (c) terminates and the new index sequence and the new color mapping determined when the incremental reduction falls below a selected threshold.

A data processing system for deriving a new index sequence representing a pixel mapping and a new output function representing a color palette for a new digitized color image derived from an original digitized color image both defined on n pixels, wherein the original digitized color image is provided by N distinct colors being allocated to the n pixels, the new digitized color image is provided by M distinct colors being allocated to the n pixels, the new index sequence has n index members for representing the n pixels and the new output function is for mapping the n index members to the M colors, the data processing system comprising:

• (a) a hard decision module for (i) providing a first new index sequence by partitioning all pixels in the original digitized color image into M disjoint clusters based on a color of each pixel in the original digitized color image without regard to the location of the pixel in the original digitized color image, wherein M is less than or equal to N, and (ii) providing a first new output function for providing a one-to-one mapping of the M distinct colors onto the pixels in the M disjoint clusters;
• and (b) a soft decision module for applying a soft decision optimization process to the first new index sequence and the first new output function to provide the new index sequence and the new output function respectively based on, for each member of the first new index sequence, how a color value assigned to that member by the first new output function correlates with the color value assigned to at least one other member of the first new index sequence by the first new output function.

A data processing system for deriving a new index sequence representing a pixel mapping and a new output function representing a color palette for a new digitized color image derived from an original digitized color image both defined on n pixels, wherein the original digitized color image is provided by N distinct colors being allocated to the n pixels, the new digitized color image is provided by M distinct colors being allocated to the n pixels, the new index sequence has n index members for representing the n pixels and the new output function is for mapping the n index members to the M colors, the data processing system comprising:

• (a) a hard decision module for (i) providing a first new index sequence by partitioning all pixels in the original digitized color image into M disjoint clusters based on a color of each pixel in the original digitized color image without regard to the location of the pixel in the original digitized color image, wherein M is less than or equal to N, and (ii) providing a first new output function for providing a one-to-one mapping of the M distinct colors onto the pixels in the M disjoint clusters;
• and (b) a soft decision module for applying a soft decision optimization process to the first new index sequence and the first new output function to provide the new index sequence and the new output function respectively based on, for each member of the first new index sequence, how a color value assigned to that member by the first new output function correlates with the color value assigned to at least one other member of the first new index sequence by the first new output function, and wherein the soft decision module is operable (i) to apply an iterative soft decision optimization process, (ii) to determine, after each iteration, an incremental reduction in a cost function representing compression and distortion of the original digitized color image, and (iii) to terminate the iterative soft decision optimization process and determine the new index sequence and the new color mapping when the incremental reduction falls below a selected threshold.

A computer program product for use on a computer system to create pixel mapping and a new output function representing a color palette for a new digitized color image derived from an original digitized color image both defined on n pixels, wherein the original digitized color image is provided by N distinct colors being allocated to the n pixels, the new digitized color image is provided by M distinct colors being allocated to the n pixels, the new index sequence has n index members for representing the n pixels and the new output function is for mapping the n index members to the M colors, the computer program product comprising:

• a recording medium;
• means recorded on the medium for instructing the computer system to perform the steps of:
• (a) providing a first new index sequence by partitioning all pixels in the original digitized color image into M disjoint clusters based on a color of each pixel in the original digitized color image without regard to the location of the pixel in the original digitized color image, wherein M is less than or equal to N;
• (b) providing a first new output function for providing a one-to-one mapping of the M distinct colors onto the pixels in the M disjoint clusters;
• and,
• (c) applying a soft decision optimization process to the first new index sequence and the first new output function to provide the new index sequence and the new output function respectively based on, for each member of the first new index sequence, how a color value assigned to that member by the first new output function correlates with the color value assigned to at least one other member of the first new index sequence by the first new output function.

A computer program product for use on a computer system to create pixel mapping and a new output function representing a color palette for a new digitized color image derived from an original digitized color image both defined on n pixels, wherein the original digitized color image is provided by N distinct colors being allocated to the n pixels, the new digitized color image is provided by M distinct colors being allocated to the n pixels, the new index sequence has n index members for representing the n pixels and the new output function is for mapping the n index members to the M colors, the computer program product comprising:

• a recording medium;
• means recorded on the medium for instructing the computer system to perform the steps of:
• (a) providing a first new index sequence by partitioning all pixels in the original digitized color image into M disjoint clusters based on a color of each pixel in the original digitized color image without regard to the location of the pixel in the original digitized color image, wherein M is less than or equal to N;
• (b) providing a first new output function for providing a one-to-one mapping of the M distinct colors onto the pixels in the M disjoint clusters;
• (c) applying a soft decision optimization process to the first new index sequence and the first new output function to provide the new index sequence and the new output function respectively based on, for each member of the first new index sequence, how a color value assigned to that member by the first new output function correlates with the color value assigned to at least one other member of the first new index sequence by the first new output function;
• wherein step (c) comprises applying an iterative soft decision optimization process and determining, after each iteration, an incremental reduction in a cost function representing compression and distortion of the original digitized color image;
• and
• step (c) terminates and the new index sequence and the new color mapping determined when the incremental reduction falls below a selected threshold.