CN101065779A - 彩色图像编码的方法、系统和软件产品 - Google Patents

Abstract

本发明涉及一种彩色图像数据的压缩。硬判决像素映射和软判决像素映射的组合用于在保持较低计算复杂度和与如GIF/PNG解码器等的标准解码器兼容的同时，联合地解决量化失真和压缩率的问题。

Description

彩色图像编码的方法、系统和软件产品

技术领域

本发明涉及一种彩色图像编码的方法、系统和软件产品。

背景技术

近年来，互联网上彩色图像数据量急速增长。具体地，由于网页、数码摄像机和在线游戏的加速流行，彩色图像数据成为互联网流量的主要部分。另一方面，通过无线信道或通过低功率的小型设备访问彩色图像仍然是耗时且不便的，这主要是由于图像显示设备、存储和传输带宽的限制成为多数多媒体应用的瓶颈，例如，参见J.Barrilleaux，R.Hinkle和S.Wells，“Efficient vector quantization for color image encoding，”Acoustics，Speech，and Signal Processing，IEEE International Conference onICASSP’87，vol.12，pp740-743，April 1987(下面称为“参考[1]”)、M.T.Orchard and C.A.Bouman，“Color quantization of images，”SignalProcessing，IEEE transations on，vol.39，no.12，pp.2677-2690，Dec.1991(下面称为“参考[2]”)、I.Ashdown，“Octree color quantization，”C/C++ UsersJounal，vol.13，no.3，pp.31-43，1994(下面称为“参考[3]”)、X.Wu，“Yiq vectorquantization in new color palette architecture，”IEEE Trans.On ImageProcessing，vol.5，no.2，pp.321-329，1996(下面称为“参考[4]”)、L.Velho，J.Gomes和M.V.R.Sobreiro，“Color image quantization by pairwiseclustering，”Proc.Tenth Brazilian Symp.Comput.Graph.ImageProcess.，L.H.de Figueiredo和M.L.Netto，Eds.Campos do Jordao，Spain，pp.203-210，1997(下面称为“参考[5]”)以及S.Wan，P.Prusinkiewicz和S.Wong，“Variance-based color image quantization for frame buffer display，”Res.Appl.，vol.15，pp.52-58，1990(下面称为“参考[6]”)。

消除以上限制的一种方式是应用高效的彩色图像编码方案，其压缩、优化或重新编码彩色图像。典型的彩色图像编码方案包括调色板、像素映射和无损代码。调色板用作矢量量化码本，并且用于代表原始彩色图像中的所有颜色。像素映射则将图像中的每一种颜色映射至于调色板中的颜色相对应的索引。像素映射可以是硬判决像素映射，其中一旦给定了调色板，则RGB彩色矢量到调色板的颜色的量化是固定的，并且与图像中RGB彩色矢量的像素位置无关，像素映射也可以是软判决像素映射，其中在不同像素位置处RGB彩色矢量被量化为调色板的不同颜色。最后由无损代码对从像素映射产生的索引序列进行编码。

以前，调色板设计、像素映射和编码被分离地研究。在调色板和像素映射的设计中，通常忽略编码部分，并且主要目的是减小量化失真、改进量化图像的可视质量以及降低计算复杂度。在文献中，例如参见参考[1]至[6]，提出了多种树结构的划分和合并彩色图像量化方法，以多少能够实现该目的。

另一方面，当考虑编码时，通常假设调色板和像素映射已经被给定，并且其目的是设计索引序列的有效代码，以便降低压缩率。例如，在A.Zaccarin和B.Liu，“A novel approach for coding color quantized image，”Image Processing，IEEE Transactions on，vol.2，no.4，pp.442-453，Oct.1993(下面称为“参考[7]”)中给出的彩色量化图像的LUV彩色空间中的有损压缩的算法。在N.D.Memon和A.Venkateswaran，“On ordering color maps forlossless predictive coding，”IEEE Transactions on Image Processing，vol.5，no.11，pp.1522-1527，1996(下面称为“参考[8]”)中提出了两个启发式的解决方案，在编码图像之前，通过无损预测编码技术来对彩色图像进行重新编码。根据二进制树结构和基于上下文的熵编码，在X.Chen，S.Kwong和J.fu Feng，“A new compression scheme for color-quantized images，”Circuits and Systems for Video Technology，IEEE Transactionson，vol.12，no.10，pp.904-908，Oct 2002(下面称为“参考[9]”)中提出了一种压缩算法，以提供进步的彩色量化图像的编码。在这些算法中，以压缩的比特流与诸如GIF/PNG解码器之类的标准解码器不兼容为代价，实现了压缩效率。

发明内容

根据本发明的第一方面，提供了一种方法，使用数据处理系统，从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有像素到M个不相交簇(cluster)的树结构划分，其中，M小于或等于N，N个不同颜色中的每种颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的。该方法包括(a)提供包括所有N个不同颜色的根节点；(b)提供与根节点相连的第一级兄弟节点，其中由数据处理系统根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每种颜色分配给第一级兄弟节点中的相关节点；(c)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级提供多个兄弟节点，其中由数据处理系统根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每种颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的这种颜色，存在只包含该颜色的独立叶节点；以及(d)选择并合并叶节点，直到仅剩下M个叶节点为止。

根据本发明的第二方面，提供了一种数据处理系统，用于从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有颜色到M个不相交簇的树结构划分，其中，M小于或等于N，N个不同颜色中的每种颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的。该数据处理系统包括：(a)节点创建装置，用于(i)提供包括所有N个不同颜色的根节点；(ii)提供与根节点相连的第一级兄弟节点，其中根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每种颜色分配给第一级兄弟节点中的相关节点；以及(iii)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级提供多个兄弟节点，其中根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每种颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的这种颜色，存在只包含该颜色的独立叶节点；以及(b)节点合并装置，用于选择并合并叶节点，直到仅剩下M个叶节点为止。

根据本发明的第三方面，提供了一种在计算机系统上使用的计算机程序产品，用于从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有像素到M个不相交簇的树结构划分，其中，M小于或等于N，N个不同颜色中的每种颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的。该计算机程序产品包括：记录介质；记录在介质上的装置，用于指示计算机系统执行以下步骤：(a)提供包括所有N个不同颜色的根节点；(b)提供与根节点相连的第一级兄弟节点，其中由数据处理系统根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每种颜色分配给第一级兄弟节点中的相关节点；(c)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级提供多个兄弟节点，其中由数据处理系统根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每种颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的这种颜色，存在只包含该颜色的独立叶节点；以及(d)选择并合并叶节点，直到仅剩下M个叶节点为止。

根据本发明的第四方面，提供了一种方法，用于针对从原始数字化彩色图像中推导出的新数字化彩色图像，推导出表示像素映射的新索引序列和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分(index member)，新输出函数用于将n个索引组分映射至M种颜色。该方法包括：(a)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；(b)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；(c)对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

根据本发明的第五方面，提供了一种数据处理系统，用于针对从原始数字化彩色图像中推导出的新数字化彩色图像，推导出表示像素映射的新索引序列和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分，新输出函数用于将n个索引组分映射至M种颜色。该数据处理系统包括：(a)硬判决模块，用于(i)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；以及(ii)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；以及(b)软判决模块，用于对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

根据本发明的第六方面，提供了一种在计算机系统上使用的计算机程序产品，以针对从原始数字化彩色图像中推导出的新数字化彩色图像，创建像素映射和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分，新输出函数用于将n个索引组分映射至M种颜色。该计算机程序包括：记录介质；以及装置，记录在介质上，用于指示计算机系统执行以下步骤：(a)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；(b)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；(c)对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

附图说明

下面参考以下附图来提供本发明优选方面的详细描述，附图中：

图1是示出了根据本发明优选方面的计算机系统的方框图；

图2是示出了根据本发明优选方面的八叉树结构的图；

图3是示出了根据本发明软判决优化方面的第一变体的维特比算法的图；

图4是示出了根据本发明软判决优化方面的第二变体的维特比算法的图；以及

图5是示出了图1的计算机系统的CPU的方框图。

具体实施方式

参考图1，示出了根据本发明方面的计算机系统10的方框图。计算机系统包括：存储器12，用于存储彩色图像数据；监视器14，用于显示数字彩色图像；CPU 16，用于图像处理，并且在保持低计算复杂度和与GIF/PNG解码器的兼容的同时，提供联合地优化了量化、失真和压缩权重的颜色数据的压缩；以及编码器20，例如GIF编码器或PNG编码器，用于在通过传输导管20从计算机系统10传输之前，对彩色图像数据进行编码。

彩色图像编码的联合优化问题可以定义如下：设定Ω＝{(r，g，b)|0≤r，g，b≤255}是RGB颜色空间。假设O＝{o₁，o₁，...，o_N-1}是具有N个不同颜色的原始彩色图像的调色板。如果原始图像中的总像素数目是n，则通过从上至下、从左至右扫描彩色图像，获得索引序列I＝(i₀，i₁，...，i_n-1)，其中i_k表示第k个像素的颜色矢量是o_ik。如果限定使用具有M种颜色(M＜N)的新调色板C来再现原始彩色图像，则联合优化编码器致力于找到新调色板C＝{c₀，c₁，...，c_M-1}、新索引序列U＝(u₀，u₁，...，u_n-1)以及无损代码字长度函数I，以再现原始图像，且使下面的代价函数(cost function)最小化：

$n^{-1}l\left(U\right)+\mathrm{\λ}{n}^{-1}\underset{k=0}{\overset{n-1}{\mathrm{\Σ}}}d(o_{i_k},c_{u_k})$

其中，λ是拉格朗日乘子，d是由c_uk表示o_ik所引起的平方误差：

$d(o_i,c_k)={\left|\right|o_i-c_k\left|\right|}^2={(r_{o_I}-r_{c_k})}^2+{(g_{o_i}-g_{c_k})}^2+{(b_{o_i}-b_{c_k})}^2---\left(1.1\right)$

由于在无损代码字长度函数和无损代码之间存在一对一的映射，对无损代码字长度函数的选择等效于对无损代码的选择。

显而易见地，

$\underset{k=0}{\overset{n-1}{\mathrm{\Σ}}}d(o_{i_k},c_{i_k})=\underset{k=0}{\overset{n-1}{\mathrm{\Σ}}}[{(r_{o_k}-r_{c_k})}^2+{(g_{o_k}-g_{c_k})}^2+{(b_{o_k}-b_{c_k})}^2]---\left(1.2\right)$

是总平方误差(TSE)，与量化彩色图像的可视质量紧密相关。注意，TSE或者其它类似失真测量的最小化是在参考[1]至[6]所考虑的面向量化的方法的唯一目的。类似地，给定新调色板C和像素映射(因此有索引序列U)，所有可能的无损代码字长度函数1中比特率n^-1l(U)的最小化是参考[7]至[9]所考虑的颜色量化图像的编码方法的唯一目的。以上给出的代价函数提出了速率和失真的联合优化的问题。量化失真由调色板C和像素映射(即索引序列U)确定；压缩率由像素映射和无损代码字长度函数1确定。当然，在这里，像素映射是软判决像素映射。因此，即使无损代码长度函数1是固定的，通过改变C和U，仍然可以联合地优化速率和失真。

存在多种无损代码字长度函数，每一个函数与不同的熵代码相对应，例如D.A.Huffman，“A method for the construction of minimum-redundancycodes，”Proc.IRE，vol.40，no.9，pp.1098-1101，1952(下面称为“参考[12]”)的Huffman代码、J.Ziv和A.Lempel，“A universal algorithm for sequentialdata compression，”IEEE Trans.On Information Theory，vol.23，pp.337-343，1977(下面称为“参考[11]”)、J.Ziv和A.Lempel IEEETrans.Inform.theory(下面称为“参考[10]”)的Lempel-ziv代码、I.H.Witten，M.Neal和J.G.Cleary，“Arithmetic coding for data compression，”Commun.ACM，vol.30，pp.520-540，June 1987(下面称为“参考[13]”)的算术代码、E.-H.Yang和J.C.Kieffer，“Efficient universal lossless datacompression algorithms based on a greedy sequential grammar transform-part one：without context models，”IEEE Trans.On Information Theory，vol.46，no.3，pp.755-4777，may 2000(下面称为“参考[14]”)以及J.C.Kieffer和E.-H Yang，“Grammer based codes：A new class of universal lossless sourcecodes，”IEEE Trans.on information Theory，vol.46，no.3，pp.737-754，may 2000(下面称为“参考[16]”)的基于语法的代码以及特别针对彩色图像编码而设计的无损代码(参见参考[7]至[9])。由于希望保持与GIF/PNG解码器的兼容，所以在GIF解码器的情况下将l选择为LZ78或其变体的代码字长度，并且在PNG解码器的情况下将l选择为LZ77或其变体的代码字长度，参见J.Miano，“Compressed image file formats：Jpeg，png，gif，xbm，bmp，”ACM Press，2000(下面称为“参考[17]”)，在所有情况下简单地由l_LZ(U)表示。因此，要最小化的代价函数是

$n^{-1}{l}_{\mathrm{LZ}}\left(U\right)+\mathrm{\λ}{n}^{-1}\underset{k=0}{\overset{n-1}{\mathrm{\Σ}}}d(o_{i_k},c_{u_k}).$

以上给出的代价函数具有与熵限制矢量量化(ECVQ)中定义的代价函数类似的形式，参见P.A.Chou，T.Lookabaugh和R.M.Gray，“Entropy-constrained vector quantization，”Acoustic，Speech，and SignalProcessing[还参见IEEE Transactions on Signal Processing]，IEEETransactions on，vol.37，no.1，pp.31-42，Jan.1989(下面称为“参考[18]”)，特别地具有与可变速率格栅信源编码(VRTSE)中定义的代价函数类似的形式，参见E.-H.Yang和Z.Zhang，“Variable rate trellis source encoding，”IEEETrans.on information Theory，vol.45，no.2，pp.586-608，March 1999(下面称为“参考[19]”)。在利用格栅结构且联合地优化产生的速率、失真和选定的编码路径意义上，VRTSE可以被看作熵限制标量量化和矢量量化[18]的概括。其有效的性能，尤其是在低速率区域，使VRTSE特别适用于彩色图像编码，在彩色图像编码中，通常希望有高压缩比以节约存储空间和传输时间。

根据VRTSE，根据本发明的方面，开发出两种方法：可变速率格栅(trellis)颜色量化(VRTCQ)1和VRTCQ2，以在保持低计算复杂度和与GIF/PNG解码器兼容的同时，联合地优化量化失真和压缩率。VRTCQ1和VRTCQ2使用软判决像素映射，并且是递归的。此外，根据本发明的另一个方面，开发出熵限制等级合并量化(ECHMQ)，其使用RGB颜色的八叉树数据结构，并且局部地使量化彩色图像的熵限制代价最小化，以提供VRTCQ1和VRTCQ2的初始彩色图像编码方案。ECHMQ独立地提供了一种平衡量化彩色图像的速率和失真的有效方式。

可变速率格栅信源编码的简要回顾

[19]中给出的可变速率格栅信源编码是固定斜率有损编码对格栅结构解码器的扩展，参见E.hui Yang.，Z.Zhang和T.Berger，“Fixed-slopeuniversal lossy data compression，”IEEE Trans.on Information Theory，vol.43，no.5，pp.1465-1476，Sept.1997(下面称为“参考[20]”)。对于每个实数值信源序列xⁿ＝(x₀，x₁，...，x_n-1)∈Rⁿ，目的在于找到序列uⁿ＝(u₀，u₁，...，u_n-1)∈Mⁿ _set，M_set＝{0，1，...，M-1}，以使以下代价函数最小化：

J(xⁿ)＝n^-1l(uⁿ)+λn^-1p(xⁿ，β(uⁿ))

其中，λ是给定的拉格朗日乘子，l是无损代码字长度函数，β(uⁿ)＝(z₀，z₁，...，z_n-1)是与uⁿ相对应的再现序列，p是由下式定义的平方误差失真

$p(x^n,z^n)\underset{\‾}{\mathrm{\Δ}}\underset{i=0}{\overset{n-1}{\mathrm{\Σ}}}p(x_i,z_i)\underset{\‾}{\mathrm{\Δ}}\underset{0}{\overset{n-1}{\mathrm{\Σ}}}{(x_i-z_i)}^2$

其中xⁿ＝(x₀，x₁，...，x_n-1)，且zⁿ＝(z₀，z₁，...，z_n-1)。

从uⁿ中，通过格栅结构的解码器β＝(f，g)，确定再现序列β(uⁿ)，其中f：S×M_set→S是状态变换函数，S＝{s₀，s₁，...，s_|s|-1}是状态集合，并且g：S×M_set→R是输出函数。函数f和g分别确定了格栅结构和再现等级的集合(与调色板类似)。给定初始状态S_i0，再现序列β(uⁿ)＝(z₀，z₁，...，z_n-1)计算如下：

$z_j=g(s_{i_j},u_j)$

$s_{i_{j+1}}=f(s_{i_j},u_j)$

j＝0，1，...，n-1                         (2.3)

换句话说，当接收到uⁿ时，解码器β在遍历状态序列s_i0，s_i1，...，s_in的同时输出再现序列β(uⁿ)＝(z₀，z₁，...，z_n-1)。

固定β。将l选择为具有k阶变换概率函数W(u|u^k|)的k阶静态算术代码字长度函数L^W _k。然后使用维特比算法来找到最佳序列uⁿ：

$u^n={\arg }_{v^n=(v_0,v_1,...,v_{n-1})\∈M^n}\min [n^{-1}{L^W}_k(v_0,v_1,...,v_{n-1})+\mathrm{\λ}{n}^{-1}p(x^n,\mathrm{\β}\left(v^n\right))]---\left(2.4\right)$

固定f。g、uⁿ和L^W _k的联合优化(或者等效为W(u|u^k|))可以描述如下

$\underset{g,W}{\min }\underset{u^n\∈M^n}{\min }[n^{-1}{L^W}_k\left(u^n\right)+\mathrm{\λ}{n}^{-1}p(x^n,\mathrm{\β}\left(u^n\right))]---\left(2.5\right)$

在[19]中提出了一种可选的算法，以解决联合优化问题(2.5)。这种可选算法的过程如下：

步骤1：设定t＝0。选择输出函数g^(o)和变换概率函数W⁽⁰⁾，满足

W^(o)(u|u^k)＞0，对于任意u∈M_set和u^k∈M^k _set。

步骤2：固定g^(t)和W^(t)。使用维特比算法，由g^(t)替换g，W^(t)替换W，来找到满足方程(2.4)的序列(u_n)^(t)＝(u₀ ^(t)，u₁ ^(t)，..，u_n-1 ^(t))。

步骤3：固定(uⁿ)_(t)。索引序列(uⁿ)^(t)引起变换概率函数和输出函数如下的更新

$W^{(t+1)}\left(u\right|u^k)=\frac{\left|\right\{j:{u_j}^{\left(t\right)}=u,{\left(u_{j-k}^{j-1}\right)}^{\left(t\right)}=u^k,0\&le;i\&le;n\left\}\right|}{\left|\right\{j:{\left(u_{j-k}^{j-1}\right)}^{\left(t\right)}=u^k,0\&le;j<n\left\}\right|},$ $u^k\&Element;M_{\mathrm{set}}^k,$ u∈M_set

以及

$g^{\left(t\right)}(s,u)=\frac{{\mathrm{\&Sigma;}}_{s,u}{x}_j}{\left|\right\{j:s_{i_j}=s,u_j^{\left(t\right)}=u,0\&le;j<n\left\}\right|}$ s∈S，u∈M_set

其中， $u_{j-k}^{j-1}=u_{j-k}...u_{j-1},$ s_ij，j＝0，1，...，n-1是隔栅解码器(f，g^(t))响应于(uⁿ)^(t)而遍历的状态，并且对满足 $s_{i_j}=s$ 且 $u_j^{\left(i\right)}=u$ 的所有j取∑_s，u。

步骤4：对于t＝0，1，2，..重复步骤2至3，直到

$[n^{-1}{L}_k^{W\left(i\right)}\left({\left(u^n\right)}^{\left(i\right)}\right)+{\mathrm{\&lambda;n}}^{-1}p(x^n,{\mathrm{\&beta;}}^{\left(t\right)}\left({\left(u^n\right)}^{\left(i\right)}\right))]-[n^{-1}{L}_k^{W(i+1)}\left({\left(u^n\right)}^{(i+1)}\right)+{\mathrm{\&lambda;n}}^{-1}p(x^n,{\mathrm{\&beta;}}^{(i+1)}\left({\left(u^n\right)}^{(i+1)}\right))]\&le;\mathrm{\&xi;}$

其中，ξ是预定的小阈值，L_k ^W(t)是与k阶变换概率函数W^(t)(u|u^k|)相关的k阶静态算法代码字长度函数。然后输出g^(t+1)、(uⁿ)^(t+1)和W^(t+1)。

VRTSE的性能渐进地接近于如参考[19]中定理3和4所示的有限速率-失真。对高斯、拉普拉斯、高斯-马尔可夫信源的实验结果表示VRTSE尤其适用于低速率编码。为了将VRTSE应用于彩色图像编码，必须解决以下问题：

问题1：VRTSE中使用的无损代码字长度函数是k阶静态算术代码字长度函数L_k。另一方面，在彩色图像编码的本示例中，无损代码字长度函数是Lempel-ziv代码字长度函数L_LZ。

问题2：在VRTSE中，未规定初始化步骤，即步骤1。即，在VRTSE中怎样选择初始函数g⁽⁰⁾和W⁽⁰⁾是开放的。在彩色图像编码设置中，这转变为怎样设计初始彩色图像编码方案。

问题3：为了减小计算复杂度，VRTSE中的索引集合M_set通常被选择为M_set＝2的二进制，使得可以使用高级算术代码字长度。另一方面，在彩色图像编码中，基数M通常相对较大，并且可以大至256。因此，需要一种新方法来降低计算复杂度。

为了避开问题1，给Lempel-ziv代码字长度函数l_LZ定上界。如果L_LZ是LZ78的代码字长度函数，则遵守针对任意序列uⁿ＝(u₀，u₁，...，u_n-1)的无损信源编码文献(例如，参见[14])，

$\frac{1}{n}{l}_{\mathrm{LZ}}\left(u^n\right)\&le;r_k\left(u^n\right)+q_k\frac{\log \log n}{\log n}---\left(2.6\right)$

其中，r_k(uⁿ)是每符号中比特的uⁿ的k阶经验熵，q_k是仅取决于k的常数，log代表底为2的对数。如果l_LZ是LZ77的代码字长度函数，则类似的上限也是有效的。代替使受失真限制的

最小化，使VRTCQ1中受相同失真限制的r_k(uⁿ)最小化。在VRTCQ1中使用不同的上限。下面解决问题2至3。

熵限制等级合并量化

根据本发明的方面，通过熵限制等级合并量化(ECHMQ)来解决问题2，ECHMQ提供了VRTSE的初始彩色图像编码方案。ECHMQ用作VRTCQ1和VRTCQ2的第一阶段，即阶段1。

ECHMQ是硬判决量化，将原始N个颜色划分为M个非交迭的簇，找到每个簇的再现颜色，并确定每个原始颜色的再现颜色，而与原始颜色在2维图像中的位置无关。其利用八叉树数据结构[3]，并通过局部地使下面定义的熵限制代价最小化，来平衡速率和失真。

设定具有调色板O＝{o₁，o₁，...，o_N-1}的n像素彩色图像和所希望的新调色板大小M＜N，使用硬判决量化器q来将N个颜色划分为M簇C₀，C₁，...，C_M-1，其对于i≠j和0≤i，j＜M，满足

C_i∩C_j≡Ф

C₀∪C₁∪...∪C_M-1≡O                (3.7)

簇的质心的整数形式构成了调色板C＝{c₀，c₁，...，c_M-1}，并且从原始颜色到簇的映射明确地将每个像素映射至索引。设定 $u^n=(u_0,u_1,...,u_{n-1})\&Element;M_{\mathrm{set}}^n$ 是将所有像素映射至索引所获得的索引序列。因此，量化图像的熵限制代价定义如下：

J(q)＝R(q)+λD(q)                            (3.8)

其中，λ是拉格朗日乘子。在(3.8)中，D(q)是总平方误差

$D\left(q\right)=\underset{j=0}{\overset{M-1}{\mathrm{\&Sigma;}}}\underset{o_k\&Element;c_j}{\mathrm{\&Sigma;}}F\left(o_k\right)d(o_k,c_j)---\left(3.9\right)$

其中，对于0≤i＜N，F(o_i)是颜色o_i在原始彩色图像中出现的次数，d(o_k，c_j)是两种颜色在RGB空间的欧几里德距离的平方，如方程(1.1)所定义的。R(q)是索引序列uⁿ的代码字长度。由于从颜色至索引的映射与颜色在彩色图像中的位置无关，所以第一阶熵用于计算代码字长度：

$R\left(q\right)=\underset{j=0}{\overset{M-1}{\mathrm{\&Sigma;}}}\left[\left(\underset{o_k\&Element;c_1}{\mathrm{\&Sigma;}}F\left(o_k\right)\right)\log \frac{n}{\underset{o_k\&Element;c_1}{\mathrm{\&Sigma;}}F\left(o_k\right)}\right]---\left(3.10\right)$

方程(3.8)中定义的代价函数与参考[18]中的熵限制矢量量化(ECVQ)中定义的拉格朗日函数类似。主要问题是设计一种具有良好速率失真平衡和较低编码复杂度的硬判决量化器q。使用八叉树来加速合并，并且使用方程(3.8)中定义的代价函数来平衡量化图像的速率和失真。

与扫描每个像素的颜色并将其插入树[3]的高速(on-the-fly)八叉树构建过程不同，获得原始彩色图像的直方图，并一次构建初始八叉树。参考图2，示出了包含原始彩色图像中所有不同的颜色及其出现次数的八叉树22。根节点24，即等级0，包括彩色图像中的不同颜色。由于RGB颜色空间中每个颜色包括三个8比特字节，每个字节代表基本组成，三个字节的最高有效位确定颜色在等级1中的位置。只要多于一个颜色被传递给一个节点，则该节点就是中间节点26，并且应该根据较低有效RGB位的组合来进一步分裂。传递给叶节点28的颜色被称为在该叶节点28的颜色，并且颜色本身实际上是该叶节点的质心。沿每个颜色分量方向，等级k处任何两个叶兄弟节点的质心之间处于(0，2^9-k)的范围内。显而易见地，k越大，这些质心颜色越类似。注意，图2所示的八叉树非常不平衡且不对称，这是由于以下两个原因：第一，普通的彩色图像中出现的颜色数目远小于RGB空间可用的2²⁴个颜色总数目(参见参考[17])；第二，如果只有一种颜色被分配给一个节点，则该节点停止分裂。

现在，将原始彩色图像中每个不同颜色o_i放在八叉树中的不同叶节点Θ_i中。通过重复每次合并两个叶兄弟节点，可以将叶节点的数目从N减少至M。产生的每个叶节点的质心的整数形式是新的调色板中的颜色。注意，在重复合并叶兄弟节点之后，每个叶节点与原始彩色图像的调色板中的颜色子集相对应。

假设O＝{o₁，o₁，...，o_N-1}是原始彩色图像的调色板。设定Θ_i和Θ_j是父节点Θ下的两个叶兄弟节点，其中 ${\mathrm{\&Theta;}}_i=\{o_{i_0},o_{i_1},...,o_{i_{m-1}}\},$ ${\mathrm{\&Theta;}}_j=\{o_{j_0},o_{j_1},...,o_{j_{K-1}}\}.$ 并且Θ_i∩Θ_j≡Ф。设定c_i是Θ_i的质心颜色，c_j是Θ_j的质心颜色。节点Θ_i的出现次数F_i定义为节点Θ_i中每种颜色出现次数的总和

$F_i\underset{=}{\mathrm{\&Delta;}}{F}_{i_0}+F_{i_1}+...+F_{i_{m-1}}$

其中，F_i1表示原始图像中颜色o_i1的出现次数。按照类似的方式计算节点Θ_j的出现次数F_j：

$F_j\underset{=}{\mathrm{\&Delta;}}{F}_{j_0}+F_{j_1}+...+F_{j_{k-1}}$

其中，F_ji表示原始图像中颜色o_ji的出现次数。通过将两个节点Θ_i和Θ_j合并为新的节点Θ_ij，将Θ_i和Θ_j中的所有颜色移到了新的节点Θ_ij，即 ${\mathrm{\&Theta;}}_{\mathrm{ij}}={\mathrm{\&Theta;}}_i\&cup;{\mathrm{\&Theta;}}_j=\{o_{i_0},o_{i_1},...,o_{i_{m-1}},o_{j_0},o_{j_1},...,o_{j_{k-1}},\}.$ 因此，节点Θ_ij的出现次数是F_ij＝F_i+F_j。假设允许实数值颜色。下面的引理给出了从Θ_i和Θ_j合并至Θ_ij的产生的熵限制待机增量。

引理1：通过合并节点Θ_i和Θ_j，熵限制代价增加了

$\mathrm{\&Delta;J}=\mathrm{\&lambda;}(F_{i}d(c_1,c_{\mathrm{ij}})+F_{j}d(c_j,c_{\mathrm{ij}}))+F_{\mathrm{ij}}\log \frac{n}{F_{\mathrm{ij}}}-F_i\log \frac{n}{F_i}-F_j\log \frac{n}{F_j}---\left(3.11\right)$

其中，c_ij是节点Θ_ij的质心，即

$c_{\mathrm{ij}}=\frac{1}{F_{\mathrm{ij}}}(F_i{c}_i+F_j{c}_j)---\left(3.14\right)$

证明：当利用该单元质心来再现该单元中所有元素时实现了最小的总平方误差。这是质心条件，参见在量化方法中广泛使用的S.P.Lloyd，“Leastsquares quantization in pcm，”IEEE Trans.on Information Theory，no.28，pp.127-135，March 1982(下面称为“参考[21]”)。在这篇文章中，使用叶节点的质心作为该节点中所有颜色的量化等级，即再现颜色。通过这种方式，可以计算出每种可能的合并的熵限制代价，而不需要计算合并之前总熵限制代价与合并之后总熵限制代价之间的差值。

由于 $F_i{c}_i={\mathrm{\&Sigma;}}_{p=0}^{m-1}{F}_{i_p}{o}_{i_p}$ 以及 $F_j{c}_j={\mathrm{\&Sigma;}}_{q=0}^{k-1}{F}_{j_q}{o}_{j_q},$ 新节点Θ_ij的质心是

$c_{\mathrm{ij}}=\frac{1}{{\mathrm{\&Sigma;}}_{p=0}^{m-1}{F}_{i_p}+{\mathrm{\&Sigma;}}_{q=0}^{n-1}{F}_{j_q}}(\underset{p=0}{\overset{m-1}{\mathrm{\&Sigma;}}}{F}_{i_p}{o}_{i_p}+\underset{q=0}{\overset{k-1}{\mathrm{\&Sigma;}}}{F}_{j_q}{o}_{j_q})=\frac{1}{F_{\mathrm{ij}}}(F_i{c}_i+F_j{c}_j)$

可以通过分别计算增加的平方误差ΔD和增加的代码字长度ΔR来证明增加的熵限制代价ΔJ的方程(3.11)。设定D_Θi表示使用c_i作为Θ_i的量化等级而引起的总平方误差。则 $D_{{\mathrm{\&Theta;}}_i}={\mathrm{\&Sigma;}}_{p=0}^{m-1}{F}_{i_p}{\left|\right|o_{i_p}-c_i\left|\right|}^2.$ 类似地，有 $D_{{\mathrm{\&Theta;}}_i}={\mathrm{\&Sigma;}}_{q=0}^{k-1}{F}_{j_q}{\left|\right|o_{j_q}-c_j\left|\right|}^2$ 和 $D_{{\mathrm{\&Theta;}}_{\mathrm{ij}}}={\mathrm{\&Sigma;}}_{p=0}^{m-1}{F}_{i_p}{\left|\right|o_{i_p}-c_{\mathrm{ij}}\left|\right|}^2+{\mathrm{\&Sigma;}}_{q=0}^{k-1}{F}_{j_q}{\left|\right|o_{j_q}-c_{\mathrm{ij}}\left|\right|}^2.$ 将c_ij代入方程(3.12)，并简化D(Θ_ij)的表达式，获得 $D_{{\mathrm{\&Theta;}}_{\mathrm{ij}}}=D_{{\mathrm{\&Theta;}}_i}+D_{{\mathrm{\&Theta;}}_j}+F_{i}d(c_1,c_{\mathrm{ij}})+F_{j}d(c_j,c_{\mathrm{ij}}).$ 因此，

$\mathrm{\&Delta;D}=D_{{\mathrm{\&Theta;}}_{\mathrm{ij}}}-(D_{{\mathrm{\&Theta;}}_i}+D_{{\mathrm{\&Theta;}}_j})=F_{i}d(c_i,c_{\mathrm{ij}})+F_{i}d(c_j,c_{\mathrm{ij}})$

设定R_Θi表示对具有节点Θ_i中的颜色的所有像素进行熵编码所产生的总比特数目。则 $R_{{\mathrm{\&Theta;}}_i}=F_i\log \frac{n}{F_i}.$ 类似地，有 $R_{{\mathrm{\&Theta;}}_j}=F_j\log \frac{n}{F_j}$ 和 $R_{{\mathrm{\&Theta;}}_{\mathrm{ij}}}=F_{\mathrm{ij}}\log \frac{n}{F_{\mathrm{ij}}}.$ 因此，

$\mathrm{\&Delta;R}=R\left({\mathrm{\&Theta;}}_{\mathrm{ij}}\right)-(R\left({\mathrm{\&Theta;}}_i\right)+R\left({\mathrm{\&Theta;}}_j\right))=F_{\mathrm{ij}}\log \frac{n}{F_{\mathrm{ij}}}-F_i\log \frac{n}{F_i}-F_j\log \frac{n}{F_j}$

其与ΔD一起暗示了(3.11)。这实现了引理1的证明。

引理1提供了合并两个叶兄弟节点的规则。阶段1的目的是产生给出量化图像的速率和失真之间的有效平衡的硬判决量化器。由于原始调色板是限定的，通过搜索所有可能的组合，可以找到全局最佳硬判决量化器。而，这种方法具有较高的计算复杂度，因此对于实时压缩是不实用的。引理1提出了一种可选方法，即一种贪婪法(greedy method)，以设计一种树结构的硬判决量化器。根据具有N个叶节点的原始八叉树，可以以最小熵限制代价的增加来重复地合并两个叶兄弟节点，直到剩下M个叶节点为止。被称为熵限制等级合并量化(ECHMQ)的这种方法是快速的，且给出了量化图像的速率和失真之间的相当好的平衡。ECHMQ的详细步骤如下：

步骤1：读出n个像素的原始彩色图像X＝(x₀，x₁，...，x_n-1)，并获得调色板O＝{o₁，o₁，...，o_N-1}和每种颜色o_i的出现次数f_i，其中0≤i＜N。

步骤2：通过将每种颜色o_i插入树作为不同的叶节点Θ_i，构建八叉树。对于0≤i＜N的每一个叶节点Θ_i，计算其质心c_i＝o_i， $\mathrm{TSE}{D}_{{\mathrm{\&Theta;}}_i}=0,$ 出现次数F_i＝f_i，并且代码字长度 $R_{{\mathrm{\&Theta;}}_i}=F_i\log \frac{n}{F_i}.$

步骤3：设定k＝N。

步骤4：对于每两个叶兄弟节点Θ_i和Θ_j，通过方程(3.12)计算质心c_ij，通过方程(3.11)计算增加的熵限制代价。

步骤5：在所有叶兄弟节点对中，选择使在前一步骤中计算的增加的熵限制代价最小化的两个叶兄弟节点Θ_p和Θ_q。如果Θ_p和Θ_q是其父节点下仅有的兄弟，则将Θ_p和Θ_q合并为等于Θ_p和Θ_q的父节点的新叶节点Θ_pq，否则将其合并为Θ_p和Θ_q父节点下的新组合叶节点。计算Θ_pq的质心c_pq，

F_pq＝F_p+F_q，

$D_{{\mathrm{\&Theta;}}_{\mathrm{pq}}}=D_{{\mathrm{\&Theta;}}_p}+D_{{\mathrm{\&Theta;}}_q}+F_{p}d(c_p,c_{\mathrm{pq}})+F_{q}d(c_q,c_{\mathrm{pq}})$

以及

$R_{{\mathrm{\&Theta;}}_{\mathrm{pq}}}=F_{\mathrm{pq}}\log \frac{n}{F_{\mathrm{pq}}}.$

步骤6：从八叉树中去除叶节点Θ_p和Θ_q。

步骤7：使k减1。

步骤8：重复步骤4至7，直到k＝M为止。然后将不同的索引i∈M_set分配给最终八叉树中剩下的M个叶节点中的每一个。叶节点的质心的整数形式是新的调色板中的不同颜色，并且该叶节点中的所有颜色映射至与该叶节点相对应的索引。

当达到所希望的颜色数目时，量化原始图像的最终熵限制代价是 $J=J_N+\mathrm{\&Delta;}{J}_N+\mathrm{\&Delta;}{J}_{N-1}+...+\mathrm{\&Delta;}{J}_{M+1}=J_N+\underset{i=N}{\overset{M+1}{\mathrm{\&Sigma;}}}\mathrm{\&Delta;}{J}_i,$ 其中J_N是具有N个不同颜色的原始图像的代价，ΔJ_i是当合并两个选定的叶节点并且将八叉树的叶节点数目从i减为i-1时增加的代价。通过找到每次在合并八叉树中的两个叶兄弟节点时的最小增加熵限制代价，ECHMQ提供了一种使熵限制代价最小化的局部最佳方式。

ECHMQ目的在于(局部)使熵限制代价最小化，而不是使纯失真TSE最小化。因此，由拉格朗日乘子λ控制和平衡量化图像的速率和失真。随着λ增加，平均失真减小，相应的速率增加。实际上，-λ可以解释为产生的速率失真曲线的斜率。因此，在ECHMQ中，可以灵活地使用λ作为平衡因子来改变量化图像的速率和失真。

ECHMQ的另一个优点在于其较低的计算复杂度。为了示出该优点，假设最初有总共256个叶节点，所有叶节点分配在等级7的32个父节点之下的等级8处。为了使叶节点的数目减为255，需要计算 $32\&times;\frac{8!}{2!\&times;6!}=896$ 对叶兄弟节点的增加的熵限制代价。如果不使用八叉树结构，则需要计算 $\frac{256!}{2!\&times;254!}=32640$ 对的增加代价，在[5]中，成对地分簇主要使用该方法。将方程(3.11)改写为

$\mathrm{\&Delta;J}=\mathrm{\&lambda;}\left\{F_1\right[{(r_{c_i}-r_{c_{\mathrm{ij}}})}^2+{(g_{c_i}-g_{c_{\mathrm{ij}}})}^2+{(b_{c_i}-b_{c_{\mathrm{ij}}})}^2]+$

$F_j[{(r_{c_i}-r_{c_{\mathrm{ij}}})}^2+{(g_{c_i}-g_{c_{\mathrm{ij}}})}^2+{(b_{c_j}-b_{c_{\mathrm{ij}}})}^2]\}+$

$F_{\mathrm{ij}}\log \frac{n}{F_{\mathrm{ij}}}-(R_{{\mathrm{\&Theta;}}_i}+R_{{\mathrm{\&Theta;}}_j})$

可见，每对叶兄弟节点的增加代价的计算包括8次加、7次减、10次乘、1次除以及1次对数运算。与其它方法中所需的较高计算相比，如对于每次分裂采用Jocobi方法的基于TSE的等级分裂方法[2]等，ECHMQ享有非常低的复杂度。此外，在步骤8处可以容易地获得调色板和像素的映射；这与如在参考[5]和[6]中所述方法等的文献中的其它方法相比也是有利的，在这些方法中，在调色板设计和像素的映射中包括大量的计算。

如果略过下面所述的进一步的优化，可以直接由GIF/PNG编码器对在ECHMQ结尾处所获得的新的调色板和像素的映射进行编码。为了明确，下面使用PNG编码器作为熵编码器。用可用的GIF编码器代替PNG编码器，可以容易地获得与GIF解码器兼容的输出。

VRTCQ1

在这部分，采用软判决量化，在保持与GIF/PNG解码器兼容的同时，进一步联合地优化量化彩色图像的压缩率和失真。使用在ECHMQ结尾处获得的硬判决量化器作为初始彩色图像编码方案，可以将VRTSE扩展到彩色图像编码，产生VRTCQ1。

设定从VRTCQ1的VRTSE设置开始。由于希望保持与GIF/PNG解码器的兼容，输出函数g不能够依赖于任何状态。换句话说，状态集S仅包括s₀。在这种情况下，可以丢开状态变换函数f，输出函数g仅仅是从M_set至RGB空间的映射，定义了索引和调色板中颜色之间的对应，并且隔栅解码器降为β＝g。给定原始彩色图像xⁿ＝(x₀，x₁，...，x_n-1)，对于 $u^n\&Element;(u_0,u_1,...,u_{n-1})\&Element;M_{\mathrm{set}}^n$ 的任意序列，定义

$d(x^n,g\left(u^n\right))=\underset{i=0}{\overset{n-1}{\mathrm{\&Sigma;}}}d(x_i,g\left(u_i\right))$

使用在(2.6)中给定的上界，并且使受失真限制的r_k(uⁿ)最小化。为了明确，设定k＝1。然而，可以容易地将下面所述的过程扩展到任意k。

可以从在ECHMQ结尾处获得的调色板和像素映射中推导出初始输出函数g⁽⁰⁾和变换概率函数W⁽⁰⁾。VRTCQ1的详细过程描述如下：

步骤1：设t＝0。从ECHMQ中获得(uⁿ)⁽⁰⁾、g⁽⁰⁾和W⁽⁰⁾： ${\left(u^n\right)}^{\left(0\right)}=(u_0^{\left(0\right)},u_1^{\left(0\right)},...,u_{n-1}^{\left(0\right)})$ 是从硬判决量化器产生的量化图像的索引序列，g⁽⁰⁾(j)是在ECHMQ结尾处获得的新调色板中与索引j相对应的颜色，其中0≤j＜M，以及对于任意α∈M_set和w∈M_set，有

$W^{\left(0\right)}\left(\mathrm{\&alpha;}\right|w)=\frac{\left|\right\{i:u_i^{\left(0\right)}=\mathrm{\&alpha;},u_{i-1}^{\left(0\right)}=w,0\&le;i<n\left\}\right|}{\left|\right\{i:u_{i-1}^{\left(0\right)}=w,0\&le;i<n\left\}\right|}$

还计算初始代价 $J^{\left(0\right)}=n^{-1}{L}_1^{W\left(0\right)}\left({\left(u^n\right)}^{\left(0\right)}\right)+{\mathrm{\&lambda;n}}^{-1}d(x^n,g^{\left(0\right)}\left({\left(u^n\right)}^{\left(0\right)}\right))].$

步骤2：固定g^(t)和W^(t)。使用维特比算法来找到满足以g^(t)代替g和以W^(t)代替W的方程(2.4)的序列 ${\left(u^n\right)}^{(i+1)}=(u_0^{(i+1)},u_1^{(i+1)},...,u_{n-1}^{(i+1)}).$

步骤3：固定(uⁿ)^(t+1)。索引序列(uⁿ)^(t+1)使得变换概率函数和输出函数更新如下：对于任意α∈M_set和w∈M_set，有

$W^{(t+1)}\left(\mathrm{\&alpha;}\right|w)=\frac{\left|\right\{i:u_i^{(t+1)}=\mathrm{\&alpha;},u_{i-1}^{(t+1)}=w,0\&le;i<n\left\}\right|}{\left|\right\{i:u_{i-1}^{(t+1)}=w,0\&le;i<n\left\}\right|},$

以及对于任意u∈M_set，有

$g^{(t+1)}\left(u\right)=\frac{{\mathrm{\&Sigma;}}_u{x}_i}{\left|\right\{i:u_i^{(t+1)}=u,0\&le;i<n\left\}\right|}$

其中，对 $u_i^{(t+1)}=u$ 的所有i求和∑_u。注意，x_i代表原始图像中第i个像素的颜色。

步骤4：计算更新的代价

$J^{t+1}=n^{-1}{L}_1^{W^{(t+1)}}\left({\left(u^n\right)}^{(t+1)}\right)+{\mathrm{\&lambda;n}}^{-1}d(x^n,g^{(t+1)}\left({\left(u^n\right)}^{(t+1)}\right))].$

步骤5：对于t＝0，1，2，...重复步骤2至4，直到J^(t)-J^t+1≤ξ为止，其中ξ是预定阈值。

然后输出g^(t+1)和(uⁿ)^(t+1)。

步骤6：使用[17]中描述的PNG编码器对调色板g^(t+1)和索引序列(uⁿ)^(t+1)进行编码。

可以将步骤2至6简称为VRTCQ1的阶段2。图3所示的图示出了此处所用的维特比算法。阶段之间增加的代价计算如下：

-logW(u_i|u_i-1)+d(x_i，g(u_i))            (4.13)

其中对于任意0≤i＜n，s_i＝u_i。在阶段i为了找到达到状态j的优选路径，需要比较M个累加的代价，每个需要3次加、3次减和乘。因此总的计算复杂度是O(nM²)。

[19]中的定理3示出了阶段2的最优性。整体上，VRTCQ1在保持与GIF/PNG解码器的兼容的同时，在一定程度上联合地优化了量化彩色图像的速率和失真。实验示出了收敛非常快；通常，在2至3次迭代之后，J^(t)非常接近于其极限。

考虑VRTCQ1的整体计算复杂度来结束本部分。与阶段2相比，VRTCQ1的阶段1，即ECHMQ，具有非常低的计算复杂度。因此，VRTCQ1的主要计算复杂度在于阶段2，尤其是在维特比算法中。由于维特比算法的每次迭代具有计算复杂度O(nM²)，所以当M较大时，VRTCQ1的总计算复杂度非常不利于实时压缩。因此，希望在大M(large M)的情况下降低计算复杂度。这个问题由VRTCQ2解决。

VRTCQ2

为了在大M的情况下降低VRTCQ1的计算复杂度，现在以不同于(2.6)的方式来定义Lempel-Ziv代码字长度函数的上限。为此，定义与第k阶经验熵r_k(uⁿ)不同的新信息量。设定M’是严格小于M的整数。设定b(·)是从M_set＝{0，1，...，M-1}至M′_set＝{0，1，...，M′-1}的映射。关于b，将M_set划分为M’组{i∈M_set：b(i)＝j}，j＝0，1，...，M′-1。对于任意 $u^n=(u_0,u_1,...,u_{n-1})\&Element;M_{\mathrm{set}}^n,$ 设定b(uⁿ)＝(b(u₀)，b(u₁)，...，b(u_n-1))

定义

$r\left(u^n\right|b\left(u^n\right))\underset{=}{\mathrm{\&Delta;}}\underset{j-1}{\overset{M^{\&prime;}-1}{\mathrm{\&Sigma;}}}\underset{i=0}{\overset{M-1}{\mathrm{\&Sigma;}}}|t:0\&le;t<n,u_t=i,b\left(u_t\right)=j\}|\log \frac{\left|\right\{t:0\&le;t<n,b\left(u_t\right)=j\left\}\right|}{\left|\right\{t:0\&le;t<n,u_t=i,b\left(u_t\right)=j\left\}\right|}$

量r(uⁿ|b(uⁿ))被称为给定b(uⁿ)下的uⁿ的条件经验熵。希望的信息量定义如下

$r_k^{*}\left(u^n\right)=r_k\left(b\left(u^n\right)\right)+r\left(u^n\right|b\left(u^n\right))$

其中，r_k(b(uⁿ))是b(uⁿ)的第k阶经验熵。不难表明

$r_k\left(u^n\right)\&le;r_k^{*}\left(u^n\right)+O\left(\frac{\log n}{n}\right)$

因此，由于(2.6)，Lempel-Ziv代码字长度函数l_LZ的上限为

$\frac{1}{n}{l}_{\mathrm{LZ}}\left(u^n\right)\&le;r_k^{*}\left(u^n\right)+O\left(\frac{\log \log n}{\log n}\right)---\left(5.14\right)$

代替使受失真限制r_k(uⁿ)的最小化，现在使在VRTCQ2中受失真限制的r^{k *}(uⁿ)最小化。与nr_k(uⁿ)是所有k阶静态算术代码字长度函数L^W _k所提供的最小代码字长度的事实类似，nr_k ^*(uⁿ)也与代码字长度函数相关。设定W_S(s|s^k)是从M′_set ^k至M′_set的概率变换函数，W_U(u|s)是从M′_set至M_set的概率变换函数。对于任意 $u^n=(u_0,u_1,...,u_{n-1})\&Element;M_{\mathrm{set}}^n,$ 使

$L_{W_s}^{W_U}\left(u^n\right)=-\underset{t=0}{\overset{n-1}{\mathrm{\&Sigma;}}}[\log W_S\left(b\left(u_t\right)\right|b\left(u_{t-1}\right)...b\left(u_{t-k}\right))+\log W_U\left(u_t\right|b\left(u_t\right))]---\left(5.15\right)$

很容易看出，L_WS ^WU是与无损代码相对应的代码字长度函数，其中首先使用具有变换概率Ws的第k阶静态算术代码来编码b(uⁿ)，然后在给定b(uⁿ)下有条件地编码uⁿ，从而通过无损代码编码uⁿ。此外，不难以表明

$n{r}_k^{*}\left(u^n\right)=\underset{W_S,W_U}{\min }{L}_{W_S}^{W_U}\left(u^n\right)+O\left(\log n\right)$

因此，给定映射b，VRTCQ2中的联合优化问题变为

$\underset{g,W_S,W_U}{\min }\underset{u^n\&Element;M_{\mathrm{set}}^n}{\min }[n^{-1}{L}_{W_S}^{W_U}\left(u^n\right)+\mathrm{\&lambda;}{n}^{-1}d(x^n,g\left(u^n\right))]---\left(5.16\right)$

为了明确，设定k＝1。然而，下面的所有论据和过程也适用于一般的k。给定g、Ws和Wu，则可以由复杂度为O(nM′²)而不是O(nM²)的维特比算法来解决(5.16)中的内部最小化。为了表明的确如此，注意，由于(5.15)，每次t增加时，代价增加

-logW_S(b(u_t)|b(u_t-1))-logW_U(u_t|b(u_t))+λd(x_t，g(u_t))    (5.17)

在(5.17)中，仅第一项取决于通过(past through)b(u_t-1)。因此，可以构建具有状态集SM′_set和两个连续阶段的状态之间的完全连接的隔栅，然后对隔栅执行维特比算法，以解决内部最小化问题。在执行维特比算法之前，计算最小的子代价

$c(s,x)\underset{\&OverBar;}{\mathrm{\&Delta;}}\underset{u\&Element;\{i:0\&le;i<M,b\left(i\right)=s}{\min }[-\log W_U\left(u\right|s)+\mathrm{\&lambda;d}(x,g\left(u\right))]$

对于每个(s，x)组合，其中s∈M′_set和x∈O。将(s，x)对的最小子代价和实现最小子代价的相应颜色索引u保存在查找表中。从隔栅的阶段t-1处的状态s_t-1∈M′_set变换到隔栅的阶段t处的状态s_t的代价是-logW_S(s_t|s_t-1)+c(s_t，x_t)。给定原始图像xⁿ＝(x₀，x₁，...，x_n-1)，如果 $s^n=(s_0,s_1,...,s_{n-1})\&Element;M_{\mathrm{set}}^{\&prime;n}$ 是通过隔栅的最佳路径，则uⁿ＝(u₀，u₁，...，u_n-1)，其中u_t∈{i：0≤i＜M，b(i)＝s_t}实现了最小代价c(s_t，x_t)，其中t＝0，1，..，n-1是实现(5.16)中内部最小化的最佳索引序列。

与VRTCQ1类似，VRTCQ2以迭代方式解决了联合优化问题(5.16)。VRTCQ2的阶段1确定映射b，并提供了初始输出函数g(0)和变换概率函数W_U ⁽⁰⁾和W_S ⁽⁰⁾。然后VRTCQ2的阶段2使用可选过程来解决最小化问题。VRTCQ2的详细过程描述如下。

A.阶段1的过程

步骤1：对原始图像执行ECHMQ，以获得具有M个叶节点、调色板大小为M的八叉树T_M以及相应的硬判决像素映射。

步骤2：根据T_M，重复ECHMQ的步骤4至7，直到剩下M’个叶节点为止。

步骤3：确定从八叉树T_M至在步骤2中获得的具有M’个叶节点的八叉树T_M’的映射b，T_M’是T_M的子集。具体地，当且仅当T_M的第i个叶节点位于以T_M’的第j个叶节点为根的T_M的子树中时，b(i)＝j，i∈M_set并且j∈M′_set。

B.阶段2的过程

步骤1：设定t＝0。从VRTCQ2的阶段1获得b、(uⁿ)⁽⁰⁾、(sⁿ)⁽⁰⁾、g⁽⁰⁾、W_U ⁽⁰⁾和W_S ⁽⁰⁾，其中 ${\left(u^n\right)}^{\left(0\right)}=(u_0^{\left(0\right)},u_1^{\left(0\right)},...,u_{n-1}^{\left(0\right)})$ 时从硬判决像素映射产生的索引序列， ${\left(s^n\right)}^{\left(0\right)}=(s_0^{\left(0\right)},s_1^{\left(0\right)},...,s_{n-1}^{\left(0\right)})=b({\left(u^n\right)}^{\left(0\right)},g^{\left(0\right)}\left(u\right))$ (0≤u＜M)是在阶段1的步骤1中获得的新调色板中与索引u相对应的颜色，

$W_U^{\left(0\right)}\left(u\right|s)=\frac{\left|\right\{i:u_i^{\left(0\right)}=u,s_i^{\left(0\right)}=s,0\&le;i<n\left\}\right|}{\left|\right\{i:s_i=s,0\&le;i<n\left\}\right|},u\&Element;M_{\mathrm{set}},s\&Element;{M^{\&prime;}}_{\mathrm{set}}$

以及

$W_S^{\left(0\right)}\left(\mathrm{\&alpha;}\right|w)=\frac{\left|\right\{i:s_{i-1}=w,s_i=\mathrm{\&alpha;},0\&le;i<n\left\}\right|}{\left|\right\{i:s_{i-1}=w,0\&le;i<n\left\}\right|},\mathrm{\&alpha;}\&Element;{M^{\&prime;}}_{\mathrm{set}},w\&Element;{M^{\&prime;}}_{\mathrm{set}}$

还计算初始代价

$J^{\left(0\right)}=n^{-1}{L}_{W_S^{\left(0\right)}}^{W_U^{\left(0\right)}}\left({\left(u^n\right)}^{\left(0\right)}\right)+{\mathrm{\&lambda;n}}^{-1}d(x^n,g^{\left(0\right)}\left({\left(u^n\right)}^{\left(0\right)}\right))$

步骤2：固定g^(t)和W^(t)。构建查找表。对于每对(s，x)，其中s∈M′_set和x∈O，计算最小子代价

$c(s,x)=\underset{u\&Element;\{i:0\&le;i<M,b\left(i\right)=s\}}{\min }[-\log W_U^{\left(t\right)}v\left(u\right|s)+\mathrm{\&lambda;d}(x,g^{\left(t\right)}\left(u\right))]$

并且记录实现c^(t)(s，x)的颜色索引u∈{i：0≤i＜M，b(i)＝s}。

步骤3：固定g^(t)、W_U ^(t)和W_S ^(t)。使用维特比算法来找到通过隔栅的最佳路径 ${\left(s^n\right)}^{(i+1)}=(s_0^{(i+1)},s_1^{(i+1)},...s_{n-1}^{(i+1)}),$ 其与b以及查找表一起确定了由g^(t)代替g、由W_U ^(t)代替W_U和由W_S ^(t)代替W_S的(5.16)中的内部最小化的最佳索引序列 ${\left(u^n\right)}^{(i+1)}=(u_0^{(i+1)},u_1^{(i+1)},...,u_{n-1}^{(i+1)}).$

步骤4：固定(uⁿ)^(t+1)和(sⁿ)^(t+1)。这两个序列使得变换概率函数和输出函数更新如下：

$W_U^{(i+1)}(u,s)=\frac{\left|\right\{i:u_i^{(i+1)}=u,s_i^{(i+1)}=s,0\&le;i<n}{\left|\right\{i:s_i^{(i+1)}=w,0\&le;i<n\left\}\right|},u\&Element;M_{\mathrm{set}},s\&Element;{M^{\&prime;}}_{\mathrm{set}},$

$W_S^{(i+1)}\left(\mathrm{\&alpha;}\right|w)=\frac{\left|\right\{i:s_{i-1}^{(i+1)}=w,s_i^{(i+1)}=\mathrm{\&alpha;},0\&le;i<n\left\}\right|}{\left|\right\{i:w_{t-1}^{(i+1)}=w,0\&le;i<n\left\}\right|},\mathrm{\&alpha;}\&Element;M^{\&prime;},w\&Element;M^{\&prime;}$

以及

$g^{(t+1)}\left(u\right)=\frac{{\mathrm{\&Sigma;}}_u{x}_i}{\left|\right\{i:u_i^{(t+1)}=u,0\&le;i<n\left\}\right|},u\&Element;M$

其中，对 $u_i^{(t+1)}=u$ 的所有i求和∑_u。

步骤5：计算更新代价

$J^{t+1}=n^{-1}{L}_{W_X^{(t+1)}}^{W_U^{(t+1)}}\left({\left(u^n\right)}^{(t+1)}\right)+{\mathrm{\&lambda;n}}^{-1}d(x^n,g^{(t+1)}\left({\left(u^n\right)}^{(t+1)}\right))].$

步骤6：对于t＝0，1，2，...重复步骤2至5，直到J^(t)-J^t+1≤ξ为止，其中ξ是预定阈值。

然后输出g^(t+1)和(uⁿ)^(t+1)。

步骤7：使用[17]中的PNG编码器对调色板g^(t+1)和索引序列(uⁿ)^(t+1)进行编码。

图4的图示出了步骤3中使用的维特比算法。在图中，每个圆圈代表一组，圆圈中的黑点代表组中的所有颜色索引u∈M_set。

与VRTCQ1类似，VRTCQ2的主要计算复杂度仍然在其阶段2。尽管与VRTCQ1的阶段2相比，VRTCQ2的阶段2具有额外的步骤，即步骤2，但是该步骤并不是计算量密集的。实际上，其计算复杂度是O(NM)，不取决于原始图像的大小n，并因此当n较大时，与维特比算法的复杂度相比可以忽略。VRTCQ2的阶段2的步骤3中的维特比算法现在具有O(nM′²)的计算复杂度，与VRTCQ1中使用的维特比算法的O(nM²)的计算复杂度相比是有利的。因此，当M′＜＜M时，VRTCQ2远比VRTCQ1快。此外，一旦固定M′，则VRTCQ2的计算复杂度就不再依赖于M。这使得对于颜色丰富的图像而言，VRTCQ2更具吸引力。VRTCQ2的代价是由于使用宽松边界来限制Lempel-Ziv代码字长度函数的上界，所以在压缩率和失真之间的平衡方面，压缩性能稍有损失。

参考图5，示出了图1的计算机系统10的CPU 16的方框图。如图所示，CPU 16包括硬判决模块40和软判决模块42。硬判决模块40提供了如上所述的ECHMQ。软判决模块42提供了如上所述的VRTCQ1和VRTCQ2。

如上所述，硬判决模块40包括：节点创建子模块，用于构建八叉树；节点合并子模块，用于选择和合并叶节点；以及代价计算子模块，用于对于叶节点对的可能的合并，计算每个这种合并的熵限制代价增量。与硬判决模块40类似，软判决模块42包括代价计算子模块，用于确定在软判决模块42的每次软判决迭代之后代价的增量减小。

本发明的其它变化和修改也是可以的。例如，如上所述，ECHMQ可以独自使用，而不使用VRTCQ来进行其它的软判决优化，以提供硬判决像素映射。可选地，可以使用VRTCQ，而不使用ECHMQ来提供初始硬判决像素映射。但是，也可以提供一些其它的初始硬判决过程。此外，代替VRTCQ，其它的软判决优化方法可以结合ECHMQ一起使用。此外，尽管以上描述主要涉及怎样在保持较低计算复杂度和与如GIF/PNG解码器等的标准解码器兼容的同时、联合地解决量化失真和压缩率，对于本领域技术人员显而易见的是，在其它上下文中，ECHMQ和VRTCQ也可以应用于彩色图像数据的压缩。所有这种修改或变化被认为处于所附权利要求所限定的本发明的界限和范围内。

Claims (42)

1.一种方法，用于使用数据处理系统，从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有像素到M个不相交簇的树结构划分，其中，M小于或等于N，N个不同颜色中的每个颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的，该方法包括：

(a)提供包括所有N个不同颜色的根节点；

(b)提供与根节点相连的第一级兄弟节点，其中，由数据处理系统根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每个颜色分配给第一级兄弟节点中的相关节点；

(c)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级处提供多个兄弟节点，其中由数据处理系统根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每个颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的每种颜色，存在只包含该颜色的不同叶节点；以及

(d)选择并合并叶节点，直到仅剩下M个叶节点为止。

2.根据权利要求1所述的方法，其中，步骤(d)包括重复选择和合并叶兄弟节点对，直到仅剩下M个叶节点为止。

3.根据权利要求1所述的方法，其中，步骤(d)包括重复选择和合并合并具有最小熵限制代价增量的叶兄弟节点对，直到仅剩下M个叶节点为止。

4.根据权利要求3所述的方法，其中，步骤(d)包括计算最小熵限制代价增量，而不计算合并前总熵限制代价和合并后总熵限制代价之间的差值。

5.根据权利要求1所述的方法，其中，N个不同颜色中每个颜色的多个P比特字节包括多个基色中每个基色的P比特字节。

6.根据权利要求3所述的方法，其中，多个基色包括红、绿和蓝。

7.根据权利要求1所述的方法，还包括创建具有M个不同颜色的新数字化彩色图像，其中在M个不同颜色和完成步骤(d)之后剩下的M个叶节点之间存在一对一的对应。

8.一种数据处理系统，用于从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有颜色到M个不相交簇的树结构划分，其中，M小于或等于N，N个不同颜色中的每个颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的，该数据处理系统包括：

(a)节点创建装置，用于

(i)提供包括所有N个不同颜色的根节点；

(ii)提供与根节点相连的第一级兄弟节点，其中根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每个颜色分配给第一级兄弟节点中的相关节点；以及

(iii)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级处提供多个兄弟节点，其中根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每个颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的每个颜色，存在只包含该颜色的独立叶节点；以及

(b)节点合并装置，用于选择并合并叶节点，直到仅剩下M个叶节点为止。

9.根据权利要求8所述的数据处理系统，其中，节点合并装置操作用于重复地选择和合并叶兄弟节点对，直到仅剩下M个叶节点为止。

10.根据权利要求8所述的数据处理系统，还包括代价计算装置，用于对于叶节点对的可能合并，计算每个这种合并的熵限制代价增量，其中，代价计算装置与节点合并装置相链接，并且节点合并装置操作用于重复地选择和合并由代价计算装置确定其合并具有最小熵限制代价增量的叶兄弟节点对，直到仅剩下M个叶节点为止。

11.根据权利要求10所述的数据处理系统，其中，代价计算装置操作用于计算最小熵限制代价增量，而不计算合并前总熵限制代价和合并后总熵限制代价之间的差值。

12.根据权利要求8所述的数据处理系统，其中，N个不同颜色中每个颜色的多个P比特字节包括多个基色中每个基色的P比特字节。

13.根据权利要求10所述的数据处理系统，其中，多个基色包括红、绿和蓝。

14.根据权利要求8所述的数据处理系统，还包括创建具有M个不同颜色的新数字化彩色图像，其中在M个不同颜色和完成步骤(d)之后剩下的M个叶节点之间存在一对一的对应。

15.一种在计算机系统上使用的计算机程序产品，用于从具有N个不同颜色的数字化彩色图像中创建数字化彩色图像中所有像素到M个不相交簇的树结构划分，其中，M小于或等于N，N个不同颜色中的每个颜色由调色板中的多个P比特字节数字地表示，并且每个P比特字节中的P比特是从最高有效到最低有效排列的，该计算机程序产品包括：

记录介质；

记录在介质上的装置，用于指示计算机系统执行以下步骤：

(a)提供包括所有N个不同颜色的根节点；

(b)提供与根节点相连的第一级兄弟节点，其中由数据处理系统根据所述多个P比特字节中的每个P比特字节的第一比特的值，将N个不同颜色中的每个颜色分配给第一级兄弟节点中的相关节点；

(c)对于包括多于一种颜色的第k级节点中的每个节点，在第k+1级处提供多个兄弟节点，其中由数据处理系统根据该颜色的所述多个P比特字节中的每个P比特字节的第k+1比特的值，将该节点中的每个颜色分配给第k+1级多个兄弟节点中的相关兄弟节点，使得对于N个不同颜色中的每个颜色，存在只包含该颜色的独立叶节点；以及

(d)选择并合并叶节点，直到仅剩下M个叶节点为止。

16.根据权利要求15所述的计算机程序产品，其中，步骤(d)包括重复选择和合并叶兄弟节点对，直到仅剩下M个叶节点为止。

17.根据权利要求15所述的计算机程序产品，其中，步骤(d)包括重复选择和合并合并具有最小熵限制代价增量的叶兄弟节点对，直到仅剩下M个叶节点为止。

18.根据权利要求15所述的计算机程序产品，其中，步骤(d)包括计算最小熵限制代价增量，而不计算合并前总熵限制代价和合并后总熵限制代价之间的差值。

19.根据权利要求15所述的计算机程序产品，其中，N个不同颜色中每个颜色的多个P比特字节包括多个基色中每个基色的P比特字节。

20.根据权利要求15所述的计算机程序产品，其中，多个基色包括红、绿和蓝。

21.根据权利要求15所述的计算机程序产品，还包括创建具有M个不同颜色的新数字化彩色图像，其中在M个不同颜色和完成步骤(d)之后剩下的M个叶节点之间存在一对一的对应。

22.一种方法，用于针对从原始数字化彩色图像中推导出的新数字化彩色图像，推导出表示像素映射的新索引序列和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分，新输出函数用于将n个索引组分映射至M种颜色，该方法包括：

(a)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；

(b)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；

(c)对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

23.根据权利要求22所述的方法，其中，新索引序列提供软判决像素映射，使得对于新数字化彩色图像中的每个像素，由新索引序列和新输出函数分配给像素的颜色值取决于像素在彩色图像中的位置。

24.根据权利要求22所述的方法，其中

步骤(c)包括应用迭代软判决优化过程，并在每次迭代之后，确定代表原始数字化彩色图像的压缩和失真的代价函数中的增量减小，以及

当增量减小降到选定的阈值以下时，步骤(c)终止，确定了新索引序列和新颜色映射。

25.根据权利要求24所述的方法，其中，步骤(c)包括

(i)设定计数器k等于1：

(ii)对于第k个索引序列，通过对于所有可能的索引序列，优化第k个输出函数和第k个变换概率函数的代价函数，来确定第(k+1)个索引序列；

(iii)根据第(k+1)个索引序列，确定第(k+1)个输出函数和第(k+1)个变换概率函数；

(iv)根据第(k+1)个索引序列、第(k+1)个输出函数和第(k+1)个变换概率函数，确定第(k+1)个代价；以及

(v)计算第(k+1)个代价和第k个代价之间的第(k+1)个代价差值，当第(k+1)个代价差值小于选定的阈值时，分别选择第(k+1)个索引速率和第(k+1)个输出函数作为新的索引序列和新的输出函数，否则，使k增加1，并重复子步骤(ii)至(v)。

26.根据权利要求25所述的方法，其中，步骤(ii)，即针对所有可能的索引序列，通过优化给定的第k个输出函数和第k个变换概率函数的代价函数来确定第(k+1)个索引序列的步骤，包括使用维特比算法。

27.根据权利要求26所述的方法，其中，

步骤(a)包括将M个不相交簇分组为M’个不相交簇，其中M’小于M；以及

步骤(c)包括将软判决优化过程应用于M’个不相交簇。

28.根据权利要求27所述的方法，其中，代价函数取决于M和M’。

29.一种数据处理系统，用于针对从原始数字化彩色图像中推导出的新数字化彩色图像，推导出表示像素映射的新索引序列和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分，新输出函数用于将n个索引组分映射至M种颜色，该数据处理系统包括：

(a)硬判决模块，用于

(i)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；以及

(ii)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；以及

(b)软判决模块，用于对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

30.根据权利要求29所述的数据处理系统，其中，新索引序列提供软判决像素映射，使得对于新数字化彩色图像中的每个像素，由新索引序列和新输出函数分配给像素的颜色值取决于像素在彩色图像中的位置。

31.根据权利要求29所述的数据处理系统，其中，软判决模块操作用于(i)应用迭代软判决优化过程，(ii)在每次迭代之后，确定代表原始数字化彩色图像的压缩和失真的代价函数中的增量减小，以及(iii)当增量减小降到选定的阈值以下时，终止迭代软判决优化过程，并确定新索引序列和新颜色映射。

32.根据权利要求31所述的数据处理系统，其中，迭代软判决优化过程包括：

(i)设定计数器k等于1：

(ii)对于第k个索引序列，通过对于所有可能的索引序列，优化第k个输出函数和第k个变换概率函数的代价函数，来确定第(k+1)个索引序列；

(iii)根据第(k+1)个索引序列，确定第(k+1)个输出函数和第(k+1)个变换概率函数；

(iv)根据第(k+1)个索引序列、第(k+1)个输出函数和第(k+1)个变换概率函数，确定第(k+1)个代价；以及

(v)计算第(k+1)个代价和第k个代价之间的第(k+1)个代价差值，当第(k+1)个代价差值小于选定的阈值时，分别选择第(k+1)个索引速率和第(k+1)个输出函数作为新的索引序列和新的输出函数，否则，使k增加1，并重复子步骤(ii)至(v)。

33.根据权利要求32所述的数据处理系统，其中，在步骤(ii)，即在针对所有可能的索引序列，通过优化给定的第k个输出函数和第k个变换概率函数的代价函数来确定第(k+1)个索引序列的步骤，包括使用维特比算法。

34.根据权利要求33所述的数据处理系统，其中，

硬判决模块操作用于将M个不相交簇分组为M’个不相交簇，其中M’小于M；以及

硬判决模块操作用于将软判决优化过程应用于M’个不相交簇。

35.根据权利要求34所述的数据处理系统，其中，代价函数取决于M和M’。

36.一种在计算机系统上使用的计算机程序产品，以针对从原始数字化彩色图像中推导出的新数字化彩色图像，创建像素映射和表示调色板的新输出函数，其中原始和新的数字化彩色图像两者都定义在n个像素上，其中，原始数字化彩色图像由分配给n个像素的N个不同颜色提供，新数字化彩色图像由分配给n个像素的M个不同颜色提供，新索引序列具有表示n个像素的n个索引组分，新输出函数用于将n个索引组分映射至M种颜色，该计算机程序产品包括：

记录介质；以及

记录在介质上的装置，用于指示计算机系统执行以下步骤：

(a)根据原始数字化彩色图像中的每个像素的颜色，通过将原始数字化彩色图像中的所有像素划分为M个不相交簇，来提供第一新索引序列，与像素在原始数字化彩色图像中的位置无关，其中，M小于或等于N；

(b)提供第一新输出函数，用于将M个不同颜色一对一地映射至M个不相交簇中的像素；

(c)对于第一新索引序列的每个组分，分别根据由第一新输出函数分配给该组分的颜色值与由第一新输出函数分配给第一新索引序列的至少一个其它组分的颜色值的相关程度，来对第一新索引序列和第一新输出函数应用软判决优化过程，以提供新的索引序列和新的输出函数。

37.根据权利要求36所述的方法，其中，新索引序列提供软判决像素映射，使得对于新数字化彩色图像中的每个像素，由新索引序列和新输出函数分配给像素的颜色值取决于像素在彩色图像中的位置。

38.根据权利要求36所述的方法，其中

步骤(c)包括应用迭代软判决优化过程，并在每次迭代之后，确定代表原始数字化彩色图像的压缩和失真的代价函数中的增量减小，以及

当增量减小降到选定的阈值以下时，步骤(c)终止，确定了新索引序列和新颜色映射。

39.根据权利要求38所述的方法，其中，步骤(c)包括

(i)设定计数器k等于1：

(ii)对于第k个索引序列，通过对于所有可能的索引序列，优化第k个输出函数和第k个变换概率函数的代价函数，来确定第(k+1)个索引序列；

(iii)根据第(k+1)个索引序列，确定第(k+1)个输出函数和第(k+1)个变换概率函数；

(iv)根据第(k+1)个索引序列、第(k+1)个输出函数和第(k+1)个变换概率函数，确定第(k+1)个代价；以及

(v)计算第(k+1)个代价和第k个代价之间的第(k+1)个代价差值，当第(k+1)个代价差值小于选定的阈值时，分别选择第(k+1)个索引速率和第(k+1)个输出函数作为新的索引序列和新的输出函数，否则，使k增加1，并重复子步骤(ii)至(v)。

40.根据权利要求39所述的方法，其中，在步骤(ii)，即在针对所有可能的索引序列，通过优化给定的第k个输出函数和第k个变换概率函数的代价函数来确定第(k+1)个索引序列的步骤，包括使用维特比算法。

41.根据权利要求40所述的方法，其中，

步骤(a)包括将M个不相交簇分组为M’个不相交簇，其中M’小于M；以及

步骤(c)包括将软判决优化过程应用于M’个不相交簇。

42.根据权利要求41所述的方法，其中，代价函数取决于M和M’。

Images