CN102223541B

CN102223541B - 一种混合图像的编码方法

Info

Publication number: CN102223541B
Application number: CN 201110200158
Authority: CN
Inventors: 丁文鹏; 朱维佳; 施云慧; 尹宝才
Original assignee: Beijing University of Technology
Current assignee: Beijing University of Technology
Priority date: 2011-07-14
Filing date: 2011-07-14
Publication date: 2013-07-03
Anticipated expiration: 2031-07-14
Also published as: CN102223541A

Abstract

公开了一种编码效率更高的混合图像的编码方法，将基础颜色和索引表编码方法用于混合图像的帧间编码：在传输基础颜色时，通过对匹配块聚类后得到的基础颜色值和当前编码块聚类得到的基础颜色值排序后对应做差求得基础颜色的残差，进而用指数哥伦布编码传输差值；在传输基础颜色时，采用基础颜色的等长编码方法，并以码率最小为原则自适应地选择基础颜色的传输方式，并用一个比特标明传输方式；在传输索引表时，根据预测块中的每个像素的值和当前编码块的基础颜色值，根据欧式距离最小的原则获得预测块中每个像素的基础颜色索引，作为当前编码块的参考索引，每个像素用一个比特表示其索引是否与对应位置的参考索引匹配。

Description

一种混合图像的编码方法

技术领域

本发明属于图像处理的技术领域，具体地涉及一种混合图像的编码方法。

背景技术

在已有的技术中，混合图像的编码大致可以分为以下三类。

1.基于图像编码的方法：

这种方法还是采用传统的编码框架来对混合图像进行编码，但是针对不同的区域采用不同的量化步长，对于包含文字和图表内容的块，编码后重建效果会非常模糊，所以量化这些块时减少量化步长，为其多分配比特，让其重建的质量尽可能好。但是对于固定的比特数，如果为文字和图表块多分配了比特，那么自然图像块所分配的比特数就会相应地减少，所以总体来说，这种方法仍不能达到很好的效果。

2.基于分层编码的方法：

这种方法采用混合光栅模型来进行压缩。它将一幅图像或者一个图像块分为前景层、背景层和一个二进制算子的平面层。这个二进制算子的平面层表明图像或图像块的每个像素属于前景层还是背景层，并且这个二进制算子平面可以用JBIG标准或JBIG2标准进行压缩。而经过数据填充算法模糊后的前景层和背景层可以用传统的图像编码框架来进行压缩。论文“Compressing compound documents”(The Document and ImageCompression Handbook，M.Barni，Ed.New York：Marcel-Dekker，2005.)提出了这种方法，并通过实验证明这种方法与传统的编解码框架相比，可以取得很大的增益。但是这种方法有一些缺点：首先增益在很大程度上取决于分割的算法，即如何将图像分为前景和背景。第二，分割出来的洞如果不经过任何处理会损害编码的效果。第三，分别编码背景层的文本颜色和二进制算子的文本形状也会降低编码的效率。所以这种方法仍不能满足应用的需要。

3.基于块的编码方法：

这种方法可以分为两类：

一种是利用空域的性质，如直方图统计，梯度，颜色的数目等，可以将当前编码块分为几类中的一种，如文本，图表，自然图像等。然后不同的类别用不同的编码框架来进行压缩以适用于它们的统计特性。

另一种是考虑到混合图像中的文字和图表的直方图较稀疏，将其在时域分解为基础颜色和索引表的形式，即Base color and Index map(BCIM)模式，如图1所示，其中“1”、“0”、“253”、“255”表示四种颜色。论文“Enable efficient compound image compression in H.264/AVC intracoding”(Proc.Int.Conf.Image Processing，Oct.2007，vol.2，pp.337-340)首先将这种方法应用到了H.264标准中，并取得了不错的增益。但是它只考虑了空间的相关性，即只对帧内部分进行了改进，而忽略了时间的相关性，没有将帧间编码的特点考虑进去，并没有设计出针对帧间编码的混合图像的编码方案。

发明内容

本发明的技术解决问题是：克服现有技术的不足，提供一种编码效率更高的混合图像的编码方法。

本发明的技术解决方案是：这种混合图像的编码方法将基础颜色和索引表编码方法用于混合图像的帧间编码：在传输基础颜色时，如果相邻帧的相关性强，则通过对匹配块聚类后得到的基础颜色值和当前编码块聚类得到的基础颜色值分别排序后相减得到基础颜色的残差，进而用指数哥伦布编码传输差值；在传输基础颜色时，如果相邻帧的相关性差，则采用基础颜色的等长编码方法，并以码率最小为原则自适应地选择基础颜色的传输方式，并用一个比特标明传输方式；在传输索引表时，根据预测块中的每个像素的值和当前编码块的基础颜色值，根据欧式距离最小的原则获得预测块中每个像素的基础颜色索引，即预测块中的每个像素的值最接近当前编码块的哪个基础颜色，作为当前编码块的参考索引，每个像素用一个比特表示其索引是否与对应位置的参考索引匹配。由于本方法在已有的基础颜色和索引表编码方法的基础上，利用相邻帧的时间相关性来减少基础颜色和索引表的比特分配，所以编码效率更高。

附图说明

图1示出了现有的BCIM模式；

图2是根据本发明的索引表的一个设计方案的像素位置图；

图3示出了根据本发明的混合图像的编码方法的流程图；

图4是传输索引表的说明图。

具体实施方式

这种混合图像的编码方法将基础颜色和索引表编码方法用于混合图像的帧间编码：在传输基础颜色时，如果相邻帧的相关性强，则通过对匹配块聚类后得到的基础颜色值和当前编码块聚类得到的基础颜色值分别排序后相减得到基础颜色的残差，进而用指数哥伦布编码传输差值；在传输基础颜色时，如果相邻帧的相关性差，则采用基础颜色的等长编码方法，并以码率最小为原则自适应地选择基础颜色的传输方式，并用一个比特标明传输方式；在传输索引表时，根据预测块中的每个像素的值和当前编码块的基础颜色值，根据欧式距离最小的原则获得预测块中每个像素的基础颜色索引，即预测块中的每个像素的值最接近当前编码块的哪个基础颜色，作为当前编码块的参考索引，每个像素用一个比特表示其索引是否与对应位置的参考索引匹配。如果相邻帧的相关性强，则在解码端，首先进行指数哥伦布解码，然后对运动补偿获得的预测块进行聚类以获得基础颜色，用反预测过程来获得基础颜色的值。

基础颜色的数目决定了产生的码率和失真的大小，每个PU由于特点不同应采用不同的基础颜色数目，所以基础颜色从1至MAX遍历，MAX在这里选为4，选出率失真代价最小的基础颜色数目。

如果索引与对应位置的参考索引不匹配，则改变索引值；如果索引与对应位置的参考索引匹配，则索引值不变。

如果索引小于等于参考索引，即索引与对应位置的参考索引匹配，则索引不变；否则将索引减1，以将其范围映射到以0为开始的区间，索引值的公式如下：

NewIndex＝OldIndex if OIdIndex≤RefIndex

NewIndex＝OldIndex-1 if OldIndex＞RefIndex。

上下文的设计方案如下：

需传输一个比特表示是否与参考索引匹配，1表示匹配，0表示不匹配。传输这个比特时总共为其设计16种上下文，上下文的选择是基于当前像素左，上，左上，右上的像素是否与其对应的参考索引匹配进行的。周围邻近的每个像素的匹配性有2种可能，匹配和不匹配，分别用1和0表示，这样的话，我们这里总共获取4个邻近像素，即左方，上方，左上方和右上方，对应的上下文为2⁴＝16。

在不匹配的情况下，需要进行根据周围像素进行上下文的自适应选择以达到更好的编码效果。

图2中为当前像素及其左，左上，上，右上位置的像素。图4是传输索引表的说明图。

为其总共设计15种上下文模型，为了更好的说明，每种上下文用一个四元组表示，四元组分别依次表示左，左上，上，右上位置的像素所表示的索引。这15种上下文分别为{AAAA，AAAB，AABA，ABAA，BAAA，AABB，ABAB，ABBA，AABC，BAAC，BCAA，ABAC，ABCA，BACA，ABCD}。其中A，B，C，D代表4个不同的索引值，例如AAAA代表4个位置的索引是相同的，AAAB代表左方，左上方，上方的3个索引值是一样的，右上方的索引值是与其他三个索引值不一样的。具体做法如下：

首先获得上下左右4个像素对应的索引值，按4个索引的出现频率及其所在位置看其属于15种上下文的哪一种，并用对应的上下文模型进行编码。并且在熵编码之前，我们将当前索引需要进行重映射以达到更好的编码效果。重映射的方法如下：根据其所属上下文模型，将需要频率最高的索引重映射为0，然后按频率递减的顺序重映射所有可能出现的索引，形成一个映射表。最后在映射表中查到当前索引重映射后的索引，并编码这个映射后的索引。

如图3所示，这种方法包括以下步骤：

(1)将每个编码单元CU按照同样的尺寸转换为预测单元PU，对于亮度和色度分量进行同样的处理；

(2)对于每个分量，将CU中的每个PU中的像素进行聚类，获得具有代表性的N个值，N为大于0的整数，这N个值即是N个基础颜色，并按递增顺序排序；然后将当前PU中的每个像素根据欧式距离最近的原则映射到N个基础颜色中的一个，并获得一个索引来表明它映射至哪个基础颜色，并且计算当前CU中每个PU的失真，进而求得CU的失真；

(3)将当前编码块经运动估计和补偿后所找到的匹配块进行与(1)中同样的处理，获得匹配块的N个基础颜色和索引表，并将基础颜色按递增顺序排序。这里的索引表是表明预测块中的每个像素最接近当前编码块的哪个基础颜色，；

(4)计算用哥伦布残差编码和等长编码传输方式传输基础颜色所消耗的比特，选出所耗费比特最小的传输方式，并用一个附加比特来表示用哪种传输方式；

(5)计算传输索引所耗费的比特，传输每个像素的索引时，首先用一个比特表示与匹配块中对应位置的索引是否匹配，如果不匹配再用另外的比特表示是哪个索引，并且自适应的选择上下文；

(6)计算码率；

(7)根据步骤(2)中产生的失真和步骤(6)产生的码率来计算率失真代价；

(8)从1至4遍历N的值，固定N后重复步骤(2)-(7)，使步骤(7)中计算的率失真代价最小；

(9)将选出的率失真代价最小的基础颜色的信息和索引表的信息传送至解码端；

(10)解码端在获得相应的信息后，根据基础颜色和索引表来重建当前PU，进而重建当前CU。

步骤(4)中的传输方式包括(a)如果相邻帧的相关性强，首先传输基础颜色的个数，然后将当前编码块的基础颜色和匹配块的对应基础颜色分别排序后相减得到残差，并用指数哥伦布编码来传输每个残差，例如：当前块的基础颜色排序后的值记为O，预测块的排序后的基础颜色记为P，则基础颜色的残差R通过如下方式获得

R = O - P = (\begin{matrix} 30 \\ 65 \\ 175 \\ 220 \end{matrix}) - (\begin{matrix} 30 \\ 66 \\ 172 \\ 218 \end{matrix}) = (\begin{matrix} 0 \\ - 1 \\ 3 \\ 2 \end{matrix});

(b)如果相邻帧的相关性差，首先传输基础颜色的个数，然后用等长码编码每个基础颜色。

优选地，获得基础颜色的方法为：获得基础颜色的核心问题是如何使得M个元素分配到N个组后的失真最小，数学描述为：

Min (Σ_{i = 0}^{M} Σ_{j = 0}^{N} M_{ij} \times {| | X_{i} - Y_{j} | |}^{2}),

其中

\begin{matrix} M_{ij} = 0 & i &Element; group (j) \\ M_{ij} = 1 & i &NotElement; group (j) \end{matrix}

但是这个问题是NP完全问题，所以我们采用如下的方法求得最优解。具体做法如下：

首先将当前编码块中的像素排成序，统计并记录每个块中的像素值及其出现频率，并且将所有的具有不同值的像素排成一个按照值递增顺序排成区间X，且每个像素值的出现频率也形成一个区间Y，X和Y这两个区间的元素是一一对应的。

假设要分为N类：

β(lowBound，UpBound，N)代表LowBound至UpBound区间内的元素分配到N个类中所产生的失真。

β(lowBound，UpBound，N)＝α(LowBound，p-1)+β(p，UpBound，N-1)N≥2

α(LowBound，UpBound) N＝1

如果N≥2，P点通过下式求得

p = \underset{lowBound < P < UpBound - N + 1}{arg min} (α (LowBound, p - 1) + β (p, UpBound, N - 1)

α (LowBound, p - 1) = Σ_{i = LowBound}^{p - 1} {(X_{i} - avg (LowBound, p - 1))}^{2} \times Y_{i}

avg (LowBound, p - 1) = Σ_{i = LowBound}^{p - 1} \frac{X_{i} \times Y_{i}}{Y_{i}}

具体演算过程如下：

β(lowBound，UpBound，4)＝α(LowBound，p1-1)+β(p1，UpBound，3)

β(p1，UpBound，3)＝α(p1，p2-1)+β(p2，UpBound，2)

β(p2，UpBound，2)＝α(p2，p3-1)+β(p3，UpBound，1)

β(p3，UpBound，1)＝α(p3，UpBound)

通过求得β(p3，UpBound，1)，可得β(p2，UpBound，2)，进而可得β(p1，UpBound，3)和β(lowBound，UpBound，4)，pi即是在每层线性搜索找到的最优点，α(p3，UpBound)，α(p2，p3-1)，α(p1，p2-1)，α(LowBound，p1-1)就是所求得的基础颜色，且这里有LowBound＜p1＜p2＜p3＜UpBound。

以上所述，仅是本发明的较佳实施例，并非对本发明作任何形式上的限制，凡是依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均仍属本发明技术方案的保护范围。

Claims

1.一种混合图像的编码方法，其特征在于：将基础颜色和索引表编码方法用于混合图像的帧间编码：在传输基础颜色时，如果相邻帧的相关性强，则通过对预测块聚类后得到的基础颜色值和当前编码块聚类得到的基础颜色值分别排序后对应做差求得基础颜色的残差，进而用指数哥伦布编码传输差值；在传输基础颜色时，如果相邻帧的相关性差，则采用基础颜色的等长编码方法，并以码率最小为原则自适应地选择基础颜色的传输方式，并用一个比特标明传输方式；在传输索引表时，根据预测块中的每个像素的值和当前编码块的基础颜色值，依据欧式距离最小的原则获得预测块中每个像素的基础颜色索引，即预测块中的每个像素的值最接近当前编码块的哪个基础颜色，作为当前编码块的参考索引，每个像素用一个比特表示其索引是否与对应位置的参考索引匹配。

2.根据权利要求1所述的方法，其特征在于：如果相邻帧的相关性强，则在解码端，首先进行指数哥伦布解码，然后对运动补偿获得的预测块进行聚类以获得预测块的基础颜色，排序后经过反预测过程来获得当前编码块基础颜色的值。

3.根据权利要求1所述的方法，其特征在于：基础颜色从1至4遍历，以选出率失真代价最小的基础颜色数目。

4.根据权利要求1所述的方法，其特征在于：如果索引与对应位置的参考索引匹配，则索引值不变；如果索引与对应位置的参考索引不匹配，为了使利于编码，使索引值可能取值范围从0开始，改变索引值。

5.根据权利要求4所述的方法，其特征在于：如果索引小于等于参考索引，即索引与对应位置的参考索引匹配，则索引不变；否则将索引减1。

6.根据权利要求4所述的方法，其特征在于：编码索引是否与参考索引匹配时，基于当前像素左、上、左上和右上的像素是否匹配来计算选择所用的上下文；当与参考索引不匹配时，编码该索引时，根据左、左上、上和右上位置的像素所表示的索引值组成的四元组，从15个编码上下文中选择一个上下文进行编码。

7.一种混合图像的编码方法，其特征在于：包括以下步骤：

(1)将每个编码单元CU按照同样的尺寸转换为预测块PU，对于亮度和色度分量进行同样的处理；

(3)将当前编码块经运动估计和补偿后所找到的预测块进行与(2)中同样的处理，获得预测块的N个基础颜色和索引表，并将基础颜色按递增顺序排序，其中的索引表是表明预测块中的每个像素最接近当前编码块的哪个基础颜色；

(4)计算用哥伦布残差编码和等长编码传输方式传输基础颜色所消耗的比特，传输方式包括(a)如果相邻帧的相关性强，首先传输基础颜色的个数，然后计算当前编码块的基础颜色和预测块的对应基础颜色排序后得到的残差，并用指数哥伦布编码来传输每个残差；(b)如果相邻帧的相关性差，首先传输基础颜色的个数，然后用等长码编码每个基础颜色；选出所耗费比特最小的传输方式，并用一个附加比特来表示用哪种传输方式；

(5)计算传输索引所耗费的比特，传输每个像素的索引时，首先用一个比特表示与预测块中对应位置的索引是否匹配，当与预测块中对应位置的索引不匹配时，编码像素的索引根据左、左上、上和右上位置的像素所表示的索引值组成的四元组，从15个编码上下文中选择一个上下文进行编码；

(6)计算码率；

8.根据权利要求7所述的方法，其特征在于：步骤(4)中的传输方式包括(a)如果相邻帧的相关性强，首先传输基础颜色的个数，然后计算当前编码块的基础颜色和预测块的对应基础颜色排序后得到的残差，并用指数哥伦布编码来传输每个残差；(b)如果相邻帧的相关性差，首先传输基础颜色的个数，然后用等长码编码每个基础颜色。

9.根据权利要求7所述的方法，其特征在于：获得基础颜色的方法为：首先将当前编码块中的像素排序，统计并记录每个块中的像素值及其出现频率，并且将所有的具有不同值的像素排成一个按照值递增顺序的区间X，且每个像素值的出现次数也形成一个区间Y，X和Y这两个区间的元素是一一对应的，然后基于X，Y这两个区间的值进行聚类算法，进而求得基础颜色。