# US 7,525,552 B2 · Method, system and software product for color image encoding > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,525,552 B2 - Document ID: US7525552B2 - Status: Granted - Kind: B2 - Application number: 10/831,656 - Filed: 2004-04-23 - Published: 2005-10-27 - Granted: 2009-04-28 - Earliest claimed: 2004-04-21 - Assignees: Slipstream Data Inc. - Inventors: En-Hui Yang; Jianfen Zeng - Web page: https://patentgrep.com/patent/US7525552B2 ## CPC - H04N 19/186: the unit being a colour or a chrominance component - G06T 9/40: Tree coding, e.g. quadtree, octree - H04N 19/126: Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers - H04N 19/136: Incoming video signal characteristics or properties - H04N 19/19: using optimisation based on Lagrange multipliers - H04N 19/94: Vector quantisation - H04N 19/96: Tree coding, e.g. quad-tree coding - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract The present invention relates to the compression of color image data. A combination of hard decision pixel mapping and soft decision pixel mapping is used to jointly address both quantization distortion and compression rate while maintaining low computational complexity and compatibility with standard decoders, such as, for example, the GIF/PNG decoder. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method as defined in claim 1 wherein the new index sequence provides a soft decision pixel mapping such that, for each pixel in the new digitized color image, the color value assigned to the pixel by the new index sequence and the new output function depends on the location of the pixel in the color image. ### Claim 3 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. ### Claim 4 (depends on 3) The method as defined in claim 3 wherein step (c) comprises (i) setting a counter k equal to one; (ii) for a k.sup.th index sequence, determining a (k+1)th index sequence by optimizing the cost function, for a kth output function and a kth transition probability function, over all possible index sequences; (iii) determining a (k+1)th output function and a (k+1)th transition probability function from the (k+1)th index sequence; (iv) determining a (k+1)th cost from the (k+1)th index sequence, the (k+1)th output function and the (k+1)th transition probability function; and, (v) calculating a (k+1)th cost difference between the (k+1)th cost and a kth cost, and, when the (k+1)th cost difference is less than a selected threshold, selecting the (k+1)th index sequence and the (k+1)th output function as the new index sequence and the new output function respectively, otherwise, increasing k by 1 and repeating sub-steps (ii) to (v). ### Claim 5 (depends on 4) The method as defined in claim 4 wherein in step (ii), the step of determining the (k+1)th index sequence by optimizing the cost function, for the given kth output function and kth transition probability function, over all possible index sequences comprises using a Viterbi algorithm. ### Claim 6 (depends on 5) The method as defined in claim 5 wherein step (a) further comprises grouping the M disjoint clusters into M′ disjoint groups, M′ being less than M; and, step (c) comprises applying the soft decision optimization process relative to the M′ disjoint groups. ### Claim 7 (depends on 6) The method as defined in claim 6 wherein the cost function depends on both M and M′. ### Claim 8 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. ### Claim 9 (depends on 8) The data processing system as defined in claim 8 wherein the new index sequence provides a soft decision pixel mapping such that, for each pixel in the new digitized color image, the color value assigned to the pixel by the new index sequence and the new output function depends on the location of the pixel in the color image. ### Claim 10 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. ### Claim 11 (depends on 10) The data processing system as defined in claim 10 wherein the iterative soft decision optimization process comprises (i) setting a counter k equal to one; (ii) for a kth index sequence, determining a (k+1)th index sequence by optimizing the cost function, for a kth output function and a kth transition probability function, over all possible index sequences; (iii) determining a (k+1)th output function and a (k+1)th transition probability function from the (k+1)th index sequence; (iv) determining a (k+1)th cost from the (k+1)th index sequence, the (k+1)th output function and the (k+1)th transition probability function; and, (v) calculating a (k+1)th cost difference between the (k+1)th cost and a k.sup.th cost, and, when the (k+1)th cost difference is less than a selected threshold, selecting the (k+1 )th index sequence and the (k+1)th output function as the new index sequence and the new output function respectively, otherwise, increasing k by 1 and repeating sub-steps (ii) to (v). ### Claim 12 (depends on 11) The data processing system as defined in claim 11 wherein, in step (ii), the step of determining the (k+1)th index sequence by optimizing the cost function, for the given k.sup.th output function and kth transition probability function, over all possible index sequences comprises using a Viterbi algorithm. ### Claim 13 (depends on 12) The data processing system as defined in claim 12 wherein the hard decision module is operable to group the M disjoint clusters into M′ disjoint groups, M′ being less than M; and, the hard decision module is operable to apply the soft decision optimization process relative to the M′ disjoint groups. ### Claim 14 (depends on 13) The data processing system as defined in claim 13 wherein the cost function depends on both M and M′. ### Claim 15 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. ### Claim 16 (depends on 15) The computer program product as defined in claim 15 wherein the new index sequence provides a soft decision pixel mapping such that, for each pixel in the new digitized color image, the color value assigned to the pixel by the new index sequence and the new output function depends on the location of the pixel in the color image. ### Claim 17 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. ### Claim 18 (depends on 17) The computer program product as defined in claim 17 wherein step (c) comprises (i) setting a counter k equal to one; (ii) for a kth index sequence, determining a (k+1)th index sequence by optimizing the cost function, for a kth output function and a kth transition probability function, over all possible index sequences; (iii) determining a (k+1)th output function and a (k+1)th transition probability function from the (k+1)th index sequence; (iv) determining a (k+1)th cost from the (k+1)th index sequence, the (k+1)th output function and the (k+1)th transition probability function; and, (v) calculating a (k+1)th cost difference between the (k+1)th cost and a kth cost, and, when the (k+1)th cost difference is less than a selected threshold, selecting the (k+1)th index sequence and the (k+1)th output function as the new index sequence and the new output function respectively, otherwise, increasing k by 1 and repeating sub-steps (ii) to (v). ### Claim 19 (depends on 18) The computer program product as defined in claim 18 wherein in step (ii), the step of determining the (k+1)th index sequence by optimizing the cost function, for the given kth output function and kth transition probability function, over all possible index sequences comprises using a Viterbi algorithm. ### Claim 20 (depends on 19) The computer program product as defined in claim 19 wherein step (a) further comprises grouping the M disjoint clusters into M′ disjoint groups, M′ being less than M; and, step (c) comprises applying the soft decision optimization process relative to the M′ disjoint groups. ### Claim 21 (depends on 20) The computer program product as defined in claim 20 wherein the cost function depends on both M and M′.