利用改进的颜色表和索引图编码方法的高级屏幕内容编码

摘要

一种装置用于执行用于屏幕内容编码的方法。所述方法包括基于编码单元(coding unit，CU)导出调色板表和颜色索引图。所述方法还包括对所述调色板表编码以及对所述颜色索引图编码。所述方法还包括将所述已编码调色板表和所述已编码颜色索引图组合以向接收器传输，其中，对所述调色板表和索引图解码以重建像素块。

说明书

技术领域

本发明大体上涉及屏幕内容编码，更具体地，涉及利用改进的颜色(调色板)表和索引图编码的高级屏幕内容编码。

背景技术

由于屏幕内容编码相比于传统视频信号具有不同的信号特征，所以屏幕内容编码给视频压缩带来了新的挑战。有多个现有技术用于高级屏幕内容编码，例如伪字符串匹配、颜色调色板编码和帧内运动补偿或帧内块复制。在这些技术中，伪字符串匹配对于无损编码带来了最高增益，但对于有损编码模式则具极高复杂性开销和极高难度。在假设非摄像机捕获的内容(例如，计算机生成的内容)通常包含数目有限的不同颜色，而不包括在许多视频序列中发现的连续或近乎连续色调的条件下，开发颜色调色板编码用于屏幕内容。即使伪字符串匹配和颜色调色板编码方法表现出巨大的潜力，但是帧内运动补偿或帧内块复制被编入了工作草案(working draft，WD)版本4和正在进行中的高效率视频编码(High Efficiency Video Coding，HEVC)范围扩展的参考软件中以用于屏幕内容编码。然而，帧内块复制的编码性能由于其固定的块分解而受限。执行块匹配(类似于帧内图像中的运动估计)还在计算和存取访问方面显著增加了编码器的复杂性。

发明内容

根据一项实施例，提供了一种用于屏幕内容编码的方法。所述方法包括基于编码单元(coding unit，CU)导出调色板表和颜色索引图。所述方法还包括对所述调色板表编码以及对所述颜色索引图编码。所述方法还包括将所述已编码调色板表和所述已编码颜色索引图组合以向接收器传输。在所述接收器处，对所述调色板表和索引图解码以重建像素块。

根据另一项实施例，提供了一种用于屏幕内容编码的装置。所述装置包括至少一个存储器和耦合至所述至少一个存储器的至少一个处理器。所述至少一个处理器用于基于编码单元(coding unit，CU)导出调色板表和颜色索引图，对所述调色板表编码，对所述颜色索引图编码，以及将所述已编码调色板表与所述已编码颜色索引图组合以向接收器传输。

附图说明

为了更完整地理解本发明及其优点，现在参考下文结合附图进行的描述，相同的数字表示相同的对象，其中：

图1示出了根据本发明的执行屏幕内容编码过程的示例发射器的功能块图；

图2示出了根据本发明的执行屏幕内容解码过程的示例接收器的功能块图；

图3示出了使用调色板表和索引图的各种模块和处理流程的示例；

图4示出了颜色分量单独和交织示出的示例编码单元(coding unit，CU)；

图5A至图5C示出了供屏幕内容编码过程使用的颜色直方图、颜色打包过程和颜色重排序过程；

图6示出了供屏幕内容编码过程使用的参考调色板表和当前调色板表；

图7示出了供屏幕内容编码过程使用的颜色索引图的水平和垂直扫描示例；

图8示出了使用颜色索引图的混合1D和2D颜色索引图编码过程的示例操作；

图9示出了示例已编码图；以及

图10和图11示出了供屏幕内容编码过程使用的参考颜色索引图和当前颜色索引图的示例。

具体实施方式

下面论述的图1至图11以及该专利文档中的各种实施例仅通过举例说明的方式描述本发明的原理，而不应以任何方式理解为对本发明范围的限制。本领域技术人员可以理解的是，本发明的原理可通过任何一种设置合理的设备和系统实现。

下面的文档和标准描述并入本发明中，如同全文在本文中阐述一样：

T.Lin，S.Wang，P.Zhang，K.Zhou，“AHG7:Full-chroma(YUV444)dictionary+hybrid dual-coder extension of HEVC”，JCT-VC文档，JCTVC-K0133，中国，上海，2012年10月(以下简称为“REF1”)；

W.Zhu，J.Xu，W.Ding，“RCE3Test 2:Multi-stage Base Color and Index Map”，JCT-VC文档，JCTVC-N0287，奥地利，维也纳，2013年7月(以下简称为“REF2”)；

L.Guo，M.Karczewicz，J.Sole，“RCE3:Results of Test 3.1on Palette Mode for Screen Content Coding”，JCT-VC文档，JCTVC-N0247，奥地利，维也纳，2013年7月(以下简称为“REF3”)；

L.Guo，M.Karczewicz，J.Sole，R.Joshi,“Non-RCE3:Modified Palette Mode for Screen Content Coding”，JCT-VC文档，JCTVC-N0249，奥地利，维也纳，2013年7月(以下简称为“REF4”)；

D.-K.Kwon，M.Budagavi，“RCE3:Results of test 3.3on Intra motion compensation”，JCT-VC文档，JCTVC-N0205，奥地利，维也纳，2013年7月(以下简称为“REF5”)；

C.Pang，J.Sole，L.Guo，M.Karczewicz，R.Joshi，“Non-RCE3:Intra Motion Compensation with 2-D MVs”，JCT-VC文档，JCTVC-N0256，奥地利，维也纳，2013年7月(以下简称为“REF6”)；

C.Pang，J.Sole，L.Guo，M.Karczewicz，R.Joshi，“Non-RCE3:Pipeline Friendly Intra Motion Compensation”，JCT-VC文档，JCTVC-N0254，奥地利，维也纳，2013年7月(以下简称为“REF7”)；

D.Flynn，J.Soel和T.Suzuki，“Range Extension Draft 4”，JCTVC-L1005，2013年8月(以下简称为“REF8”)；以及

H.Yu,K.McCann，R.Cohen和P.Amon，“Draft call for proposals for coding of screen content and medical visual content”，ISO/IEC JTC1/SC29/WG11N13829，2013年7月(以下简称为“REF9”)。

本发明实施例提供了利用改进颜色表和索引图编码的高级屏幕内容编码过程。所公开的实施例显著优于高效率视频编码(High-Efficiency Video Coding，HEVC)的当前版本(HEVC版本2)。所公开实施例包括具体针对屏幕内容编码的多个算法。这些算法包括调色板表(或等同地，颜色表)的像素表示、调色板表(或等同地，颜色表)压缩、颜色索引图压缩、字符串搜索和残余压缩。本文公开的实施例与HEVC范围扩展(Range Extension，RExt)一起开发、调和和整合，作为未来HEVC扩展，以支持有效屏幕内容编码。然而，这些实施例可通过现有视频标准或任何其它合适的视频标准来另外或可替代地实施。为了便于说明，本文以HEVC RExt为例描述各种实施例。类似地，HEVC RExt软件用于实施各种实施例，展示出最佳的压缩效率。

图1示出了根据本发明的执行屏幕内容编码过程的示例发射器的功能块图。图2示出了根据本发明的执行屏幕内容解码过程的示例接收器的功能块图。发射器100和接收器200的实施例仅用于说明。发射器100和接收器200的其它实施例可在不脱离本发明的范围的情况下使用。

发射器100用于执行可以对比特流中的每个编码单元(coding unit，CU)或编码树单元(coding tree unit，CTU)执行的高效率颜色调色板压缩(color palette compression，CPC)过程。如图1所示，发射器100从比特流中的CU101开始。CU为HEVC和HEVC RExt中的基本操作单元，是包含像素的方块，该方块包括三个分量(例如，本领域熟知的RGB、YUV、XYZ等等)。示例CU 101在图3示出。CU 101为8像素乘以8像素的CU，该CU包括每个像素的显式颜色值(例如，47、48、49等)。在其它实施例中，CU 101的大小可以不是8×8像素(例如，16×16像素、32×32像素等)。在一些实施例中，发射器100可从CTU 101开始而不从CU 101开始。为了便于说明，发射器100将通过CU 101进行描述。本领域技术人员可理解，发射器100可以通过CTU 101执行基本上相同的过程。

图4示出了CU 401的另一示例，其中颜色分量在图中分别示出。CU 401可表示CU 101。CU 401为8像素乘以8像素的CU，其中每个像素包括三个颜色分量，在这里为R、G和B。也就是，CU 401包括在打包过程中交织在一起的不同的红(red，R)颜色分量402、绿(green，G)颜色分量403和蓝(blue，B)颜色分量404。基本打包处理单元包括相同像素位置处的打包G、B、R。在其它实施例中，这三个颜色分量可为Y、Cb和Cr，或者分量的其它合适组合。每个颜色分量可由多个颜色比特表示。例如，GBR颜色分量中的每个颜色分量可由8个比特表示，因此每个像素颜色为24比特颜色。

调色板表创建块103使用CU 101导出或生成调色板表(有时称为颜色表)。示例调色板表303在图3示出。为了导出调色板表303，调色板表创建块103根据一个或多个排序规则对颜色值排序。根据每个颜色值的出现频率、CU 101中每个像素的实际颜色强度或任何其它合适的排序指标可对调色板表303排序，以提高下面编码操作的效率。例如，如图5A所示，调色板表创建块103检查CU 101中每个像素的颜色值，并根据降序排序的每个颜色的出现频率共同使用三个颜色分量，即打包的G、B、R或打包的Y、Cb、Cr创建颜色直方图。为了表示每个24比特颜色，可以相应地位移G和B颜色分量。也就是，根据值(G<<16)+(B<<8)+(R)可表示每个打包的颜色，其中<<x是一个左位移运算。

对于有损编码，调色板表创建块103则对经直方图排序的颜色数据应用相邻颜色成组过程以获得更紧凑的调色板表表示。如图5B所示，根据预定义颜色允许误差可以执行相邻颜色成组过程。可以多级执行颜色成组过程。在每级内，颜色允许误差等于当前级数，其中级数从1增加到预定最大允许误差。在一些实施例中，最大允许误差等于9。也可使用更广义的QP相关颜色允许误差。

在相邻颜色成组之后，调色板表创建块103挑选出现频率最高的N个打包的颜色。N受颜色的预定最大数目(max_num_of_colors)限制。在一些实施例中，max_num_of_colors＝128，即，N≦128。随后如图5C所示，基于每个打包的颜色的值通过按升序对颜色排序来对N个选中的颜色重排序。结果就是调色板表，例如图3示出的调色板表303。调色板表303的大小为4种颜色(即，N＝4)。在许多实施例中，N>4。然而，为了便于说明，在图3中N选定为4。

当在CU 101中表示的颜色的数目大于调色板表303中颜色的数目N时，出现频率少的颜色被排列在调色板表303之外作为残余颜色。例如，颜色值49、53、50和51是调色板表303的一部分，而颜色值48、52、47、54、55和56为调色板表303之外的残余颜色305。

如上所论述，对经直方图排序的颜色数据执行相邻颜色成组过程以获得更紧凑的调色板表表示，尤其是对于有损编码而言。假如直方图H有n个颜色，其中每个颜色包含三个分量，可以通过下面的伪代码来描述相邻颜色成组过程。对于有损编码模式，最大迭代数T等于颜色允许误差。

应该注意的是，这种用于导出调色板表303的过程不仅可应用于当前CU，而且还可应用于相邻CU重建的像素以进行调色板共用过程。

再次转向图1，基于所导出的调色板表303，颜色分类器块105使用CU 101将CU 101的颜色或像素值分配到颜色索引图311和一个或多个预测残余图313中。也就是，颜色分类器块105将调色板表303中的每个颜色分配给调色板表303内的颜色索引。例如，如图3中的307所指示，颜色49分配有颜色索引0(ColorIdx＝0)，颜色53分配有颜色索引1，颜色50分配有颜色索引2，以及颜色51分配有颜色索引3(ColorIdx＝3)。一旦调色板表303中的颜色分配有索引，则通过每个颜色的索引可以从CU 101生成颜色索引图311。同样地，调色板表303之外的每个残余颜色305分配有预测残余值，如309所指示。一旦残余颜色305分配有预测残余值，则可从CU 101生成预测残余图313。

调色板表(或颜色表)编码

对于每个CU 101，发射器100可以从当前CU 101(称为显式调色板表传输)导出调色板表303，或者发射器100可以从当前CU 101的左侧或上部邻居导出调色板表303(称为隐式调色板表传输)。当调色板表303是从相邻CU导出时，调色板表本身不需要包含在比特流中。相反，比特流中携带两个二进制位(一个用于共享标志，另一个用于共享方向)以通知解码器调色板表传输方法。这种隐式调色板表传输方法在本发明中称为调色板共享。

表编码块107接收调色板303并对调色板表303中的项编码。对于显式调色板表传输方法，表编码块107采用表间调色板填充技术或差分颜色编码技术(也称为表内颜色差值脉冲编码调制(differential pulse code modulation，DPCM))依次为所有三个颜色分量对调色板表303中的每项编码。在当前表303和参考表(也称为调色板预测器)之间执行表间调色板(颜色)填充技术，而在当前表303内执行表内颜色编码技术。假如逐项执行填充，在一些实施例中，存在与每个调色板项关联的另一标志，指示是否重用前一调色板预测器中的颜色。

表间调色板填充

即使在没有使用调色板表共享方法时，仍然可能存在调色板表303与调色板预测器之间共用的颜色。因此，采用逐项表间调色板填充技术还可以提高编码效率。这里，调色板预测器从诸如左侧邻近CU或上部邻近CU等相邻块导出。图6示出了根据本发明的可以利用表间调色板填充技术的调色板预测器601和当前调色板表603。当前调色板表603可表示图3的调色板表303。可以从当前CU的左侧邻近CU中构建调色板预测器601。在解码器侧，根据来自参考邻居的调色板预测器601适当更新调色板。在一些实施例中，可以从重建的相邻CU或编码树单元(coding tree unit，CTU)或者从片级或序列级的全局表推断调色板预测器。如在本领域所知，一个片包括图像中的多个CU。一个图像可包括一个或多个片。一个序列包括多个片。

假使c(i)和r(j)分别表示当前调色板表603的第i个项和调色板预测器601中的第j个项。还应该注意的是，每项包含三个颜色分量(GBR、YCbCr，等等)。对于每个颜色项c(i)，i≦N，在当前表603中，表编码块107从调色板预测器601中找到完全匹配r(j)。断然对c(i)、j编码，而不是标识。将预测器确定为大于先前重建的j并满足r(k)[0]≧c(i-1)[0]的最小索引k。预测差值(j–k)在比特流中标识。由于差值(j–k)为非负，所以不需要符号比特。

值得注意的是，如本领域所知，可以使用上下文自适应模式或旁路模式对(j–k)编码。通常情况下，上下文自适应模式是为了高效率目的，而旁路模式是为了高通量和低复杂性需求。在本发明的一些实施例中，可以使用两种上下文自适应模式通过动态截断一元二值化方案对索引预测差值(j–k)编码。

表内颜色DPCM

如果在调色板预测器601中没有找到当前调色板表603中第i个项的匹配，则从前一项(第(i-1)个项)减去第i个项的值，并且针对每个分量使用颜色DPCM对绝对差值(|d(i)|)编码。一般而言，将产生用于绝对预测差值和一个符号比特的少数比特，并使用表内颜色DPCM对它们编码。上下文自适应模式或旁路模式可以用于对绝对预测差值和相关符号比特编码，如本领域所知。另外，可以隐藏符号比特，或者在一些情况下不对其编码。例如，假使当前调色板表603已经以升序排序，Y(或者G)分量差值根本不需要符号比特。同样地，如果对应的Y(或者G)差值为0，则Cb(或者B)分量差值不需要符号比特。此外，如果Y(或者G)和Cb(或者B)差值都为0，则Cr(或者R)分量差值不需要符号比特。又例如，如果绝对差值为0，可以隐藏符号比特。再例如，如果满足以下边界条件，则可以隐藏符号比特。c[i-1]–|d(i)|<0或者c[i-1]+|d(i)|>255。

对于当前表603的第一项c(0)，如果没有使用表间调色板填充技术，则可以使用固定8比特旁路上下文模式对c(0)的每个分量编码。另外或可替代地，可以使用自适应上下文模式对其编码以进一步提高性能。

为了更好地说明表间调色板填充和表内颜色DPCM技术，现将描述一个在当前调色板表603中使用数据的示例。

从当前调色板表603的第一项c(0)开始，即(G，B，R)＝(0，0，192)，可以看到c(0)在调色板预测器601中没有匹配，因此单独对c(0)编码。当前调色板表603中的第二项c(1)(G，B，R)＝(0，0，240)在调色板预测器601中也没有匹配。假使已经对第一项c(0)编码，只有c(1)和c(0)之间的预测差值应该携带在比特流中，即(0，0，240)–(0，0，192)＝(0，0，48)。对于当前表603中的第三项c(2)，在调色板预测器601中识别出精确匹配，其中j＝1。使用先前已编码颜色项的预测索引为0，因此，只有(1–0)＝1需编码。应用这些编码技术，直到对当前表603中的最后一项(即图6中的idx＝12)编码。表1提供了如何使用可用的调色板预测器601对当前表603应用表间共享和表内DPCM的逐步说明。

表1：图6中的示例性表的编码方法

下面的伪代码可以总结调色板表603的编码。

索引图编码

索引图编码块109对由颜色分类器块105创建的颜色索引图311编码。为了对颜色索引图311编码，索引图编码块109执行至少一个扫描操作(水平扫描315或垂直扫描317)以将二维(two-dimensional，2D)颜色索引图311转换为一维(one-dimensional，1D)字符串。然后，索引图编码块109执行(下文所述的)字符串匹配算法以生成多个匹配。在一些实施例中，索引图编码块109执行单独的水平和垂直扫描操作并执行字符串匹配算法以确定哪种提供最佳结果。图7示出了水平和垂直扫描操作的示例。在图7中，示出了示例2D颜色索引图701。颜色索引图701可以表示图3的颜色索引图311。颜色索引图701为8×8的图，但是其它大小的颜色索引图也是可能的。如图7所示，可以对颜色索引图701进行水平扫描702或垂直扫描703。

对于每个(水平或垂直的)扫描操作，还可以执行2D块匹配算法以生成多个匹配块，如下所述。通过1D字符串匹配算法和2D块匹配算法的组合，索引图编码块109执行混合1D和2D颜色索引图编码过程。

在混合编码过程中，先前处理的索引可以用作连续索引搜索的参考。多个CTU(例如3个CTU)至当前CTU的左侧可以用作2D块匹配算法的参考区域。

可为当前颜色索引图311执行1D和2D匹配算法以确定字符串匹配或块匹配319。对于1D匹配结果，索引图编码块109记录匹配长度和对应距离或位置。对于2D匹配结果，索引图编码块109记录匹配块宽度和高度、对应参考CTU索引和参考索引在CTU的位置。

如果索引地图编码块109无法在先前处理的索引值中找到当前索引值的匹配，则通过使用匹配/不匹配标志(设为指示不匹配像素)和索引值自身将当前索引值编码为非匹配索引值。在一些实施例中，匹配/不匹配标志为1比特标志。

例如，图8示出了使用图7的颜色索引图701的混合1D和2D颜色索引图编码过程的示例操作。颜色索引图701中的第一索引图值801为14。假设在参考索引图中没有为第一索引图值801找到匹配(例如，相邻颜色索引图中没有14)，那么第一索引图值801被编码为不匹配。假设是水平扫描过程，第二索引图值802也为14。第一索引图值801有匹配，其现在可以是对第二索引图值802的参考。继续水平扫描，可以看到，第二索引图值802的右边发现另一14。第一索引图值801之后不存在连续的14。因此，索引图值的字符串803表示第一索引图值801的1D匹配字符串。

对于每个索引图值，还执行2D块搜索。例如，对于二维2×2索引图块811(其包括值14、17、17、17)，由于二维2×2索引图块811还包括值14、17、17、17，所以在块810处找到索引图块811的2D块匹配。可替换地，2D块匹配的宽度和高度可以固定到当前CU的宽度和高度。

颜色索引图701中的每个索引图值继续进行1D和2D搜索过程。每个索引图值为非匹配或一部分字符串匹配或块匹配。例如，宽度为4、高度为2的2D块806在图8示出。2D块811与索引图块810匹配。

如果索引图编码块109选择1D匹配字符串作为其对于当前索引值的搜索结果，则通过将匹配/不匹配标志设置为指示匹配像素、将匹配类型标志设为1D以及提供连续匹配索引的距离(例如，当前索引值的位置与匹配字符串的位置之间的偏差)和长度来执行编码。如果当前索引值存在多个1D匹配，则索引图编码块109选择提供最佳率失真(rate-distortion，R-D)性能的匹配。为了降低复杂性，一些实施例使用启发式算法来选择匹配长度最长的匹配。

如果索引图编码块109选择2D匹配块作为其对于当前索引值的搜索结果，则通过将匹配/不匹配标志设置为指示匹配像素、将匹配类型标志设为2D以及提供参考CTU索引和匹配块的距离(参考CTU中的匹配位置的地址)和宽度和高度执行编码。如果当前索引值存在多个2D匹配，则索引图编码块109选择提供最佳R-D性能的匹配块。为了降低复杂性，一些实施例使用启发式算法来选择匹配区域最大的块。

在一些实施例中，在混合1D和2D颜色索引图编码过程中引入编码图。例如，图9示出了示例已编码图900。已编码图900对应于颜色索引图，诸如颜色索引图701。每当在混合1D和2D颜色索引图编码过程期间找到匹配，由1D字符串匹配或2D块匹配表示的区域被标记为在已编码图900中已编码。例如，在已编码图900中，区域901为包括1D字符串匹配和2D块匹配的已编码区域。区域902为还没有编码的未编码区域。在完成当前索引的编码之后，索引图编码块109扫描已编码图900以找到第一未编码位置为待处理的下一索引。在一些实施例中，该位置可标识为curIdx，如图9所示。在混合1D/2D搜索中，如果当前字符串中的任一位置已经在前面的2D搜索中编码，该位置的匹配结果被当作一个匹配，即使当前位置和参考位置之间的索引值可能不同。

再次转向图1，残余编码块111对由颜色分类器块105创建的预测残余图313编码。在一些实施例中，残余编码块111执行自适应固定长度或可变长度的残余二值化，如图3的321所指示。这时，复用(multiplexing，MUX)块113使用字符串/块匹配319和已编码预测残余321生成压缩比特率。在一些实施例中，基于上下文的自适应二进制算术编码(context adaptive binary arithmetic coding，CABAC)方法323可以用来组合字符串/块匹配319和已编码预测残余321，如图3所示。

转向图2，接收器200用于执行如上所述的类似于发射器100执行的屏幕内容编码过程的屏幕内容解码过程。接收器200接收压缩视频比特流，然后使用解复用器201将比特流解析为已编码调色板表、颜色索引图和已编码预测残差。表解码块203和调色板表创建块209执行与表编码块107和调色板表创建块103相反的过程以重建每个CU的完整调色板表。类似地，索引图解码块205和残差解码块207执行与索引图编码块109和残差编码块111相反的过程以重建颜色索引图。颜色解分类器块211通过组合颜色索引图和调色板表导出每个位置的像素值，从而重建CTU或CU 213。

尽管图1和图2示出了执行屏幕内容编码和解码的发射器100和接收器200的示例，但是可对图1和图2进行各种更改。例如，图1和图2中的各种部件可以组合、进一步细分或者省略，而且根据特定需要可以添加额外部件。作为特定的示例，可以在一个外壳内或在一个电路板上排列各种部件，或者由单个处理器或处理单元执行各种部件。

下面的两个伪代码示出了上面所述的混合1D和2D字符串搜索方法。

在下面的1D搜索伪代码中，curIdx为待编码字符串的起始地址，refIdx表示参考字符串的所有可能起始地址。对于每个给定的curIdx和refIdex，处理块执行改进的内存对比操作以找到第一不匹配值。然后对比所有匹配长度并将最长匹配长度(len，refIdx)记录为位置curIdx的1D搜索的入选者。当前1D搜索字符串中的某个位置已经通过2D搜索编码也是可能的。在这种情况下，该位置被视为匹配，不管它的值是多少。不匹配只发生在没有对位置编码以及其ColorMap值不等于参考字符串中对应位置的ColorMap值时。

在下面的2D搜索伪代码中，curIdx为待编码块的左上角，refIdx表示参考块的所有可能左上角。例如，如图11所示，curIdx指示当前颜色索引图1004的待编码块1002的左上角，而refIdx指示参考颜色索引图1008中参考块1006等参考块的左上角。处理块计算当前颜色索引图1004中的最大搜索窗口并将窗口的宽度和高度保存在变量cw0和ch0中。其还计算参考颜色索引图1008中的最大搜索窗口并将宽度和高度保存在变量rw0和rh0中。最终搜索窗口由minw＝min(rw0，cw0)和minh＝min(rh0，ch0)定义，如图11所示。

于每个给定的curIdx和refIdx，搜索过程执行改进的内存对比操作以在搜索窗口(minw，minh)的每行内找到第一未匹配值。然后对比任一高度的所有匹配大小并将最大匹配大小(参考CTU的宽度、高度和索引)记录为“入选者”(即，位置curIdx的2D搜索的最有利匹配)。

当前2D搜索窗口中的某个区域已经通过前一2D搜索编码也是可能的。在这种情况下，该位置被视为一个匹配，不管它的值是多少。参考2D搜索窗口中的某个区域还未编码也是可能的。在这种情况下，该位置被视为未匹配，不管其值为多少。不匹配只发生在该位置未编码以及参考搜索窗口中的该位置未编码，或者其在当前颜色索引图1004中的值不等于参考字符串中对应位置的颜色图值。

//2D search

Int max2DSize＝1；

Int max2DWidth＝1；

Int max2DHeight＝1；

Int d2Dist＝-1；

Int d2Lcu＝-1；

pcRefCU＝pcCU；

for(Int n＝0；n<4；++n){

for(Int ry＝0；ry<uiRefHeight[n]；++ry){

for(Int rx＝0；rx<uiRefWidth[n]；++rx){

refIdx＝rx+ry*uiRefWidth[n]；

Int cw0＝uiWidth-curIdx％uiWidth；

Int ch0＝uiHeight-curIdx/uiWidth；

Int rw0＝uiRefWidth[n]-rx；

Int rh0＝uiRefHeight[n]-ry；

Int minw＝(rw0<cw0)？rw0:cw0；

Int minh＝(rh0<ch0)？rh0:ch0；

Int d2Width＝MAX_INT；

Int d2Size＝0；

Int x＝0；

for(Int y＝0；y<minh；++y){

for(x＝0；x<minw；++x)

if(n＝＝0){

if((pbCodedMap[curIdx+x+y*uiWidth]＝＝0)&&

((CurColorMap[curIdx+x+y*uiWidth]！＝

CurColorMap[refIdx+x+y*uiWidth])||

(pbCodedMap[refIdx+x+y*uiWidth]＝＝0)))

break；

}else{

if((pbCodedMap[curIdx+x+y*uiWidth]＝＝0)&&

(CurColorMap[curIdx+x+y*uiWidth]！＝

RefColorMap[n][refIdx+x+y*uiRefWidth[n]]))

break；

}

d2Width＝(d2Width<x)？d2Width:x；

d2Size＝d2Width*(y+1)；

minw＝d2Width；

if(d2Size>max2DSize){

max2DSize＝d2Size；

max2DWidth＝d2Width；

max2DHeight＝y+1；

d2Dist＝refIdx；

d2Lcu＝n；

}

}

}

}

if((pcRefCU＝pcRefCU->getCULeft())＝＝NULL)

break；

}

在完成对1D字符串匹配和2D区域匹配的搜索之后，如果1D maxLen大于2D max2Dsize，或者2D区域小于阈值区域(当前在伪代码中设为4×4，但是其它区域也是可能的)，那么1D结果用于curIdx。否则，2D结果用于curIdx。更新已编码图900，curIdx前进到下一位置。

由于混合1D/2D搜索的本质，下一curIdx位置可能已经通过前面的2D搜索编码过了。因此，在已编码图900中执行栅格扫描以找到还未编码为新curIdx的第一位置，诸如具有下文所示的伪代码。

while((curIdx<uiTotal)&&(pbCodedMap[curIdx]！＝0))

++curIdx；

为了对1D字符串匹配的长度编码，比特流语法使用调整后的长度而不是maxLen来对1D结果编码。假使maxLen中的一些位置已经在前一D2搜索期间编码，从maxLen移除这些位置，并且将调整后的长度写入比特流。如果调整后的长度等于1，那么该匹配被视为不匹配数据。

为了对2D块的宽度和高度编码，比特流语法使用长度而不是宽度/高度对2D结果编码。这里的长度定义为由(minw，minh)定义的搜索窗口中匹配窗口的右下角的栅格位置。进一步将其修改为反映搜索窗口和匹配窗口的宽度和高度都大于阈值窗口的事实。可以使用下面的伪代码。

ui2DSize＝(pLen[uiIdx]-MIN_2D_WIDTH)+(p2DHeight[uiIdx]-

MIN_2D_HEIGHT)*(1+minw-MIN_2D_WIDTH)；

解码器可以执行相同的已编码图操作以在接收器200中进行正确处理。

在一些实施例中，下面的额外内容需求可应用于执行上面所述的编码或解码操作的发射器100或接收器200。

在一些实施例中，混合1D和2D搜索使用将近80KB的额外内存(例如，对于20个CTU)。

在一些实施例中，8比特CRC哈希可以用来增加编码速度。当然，还可以使用其它类型的哈希函数。对于1D搜索，为每个颜色图索引计算2点哈希，并且使用计算的哈希值格式化哈希词典数组。对于2D搜索，为每个颜色图索引计算4×4块哈希，并且使用计算的哈希值格式化哈希数组和哈希词典数组。

改进的距离和长度编码

取代直接对距离和长度对编码，可以基于距离和长度对的分布使用下面的编码方法。对于距离编码，可以使用1比特标志指示距离是否为有效距离。如果不是有效距离，上面公开的距离编码方法可采用(距离–2)。如果是有效距离，可以使用额外的1比特标志(例如dist_equal_one_flag)来指示有效距离是否为1或者为当前CU的宽度。在一些实施例中，如果dist_equal_one_flag为真，该距离＝1。如果dist_equal_one_flag为假，该距离＝cuWidth。在这里，距离＝cuWidth表明来自上一行的索引复制。其还称为CopyAbove模式。距离＝1表明来自左侧索引的索引复制。其还称为IndexMode。

对于长度编码，可以使用1比特标志指示当前长度是否为有效长度。如果不是有效长度，上面公开的长度编码方法可采用(长度–cuWidth)。如果不是有效长度，可以使用固定二值化方法来对(长度–1)编码。在一些实施例中，距离二值化中的比特数为log2(cuWidth)。

解码器语法

根据本发明的下面解码器符合HEVC RExt的当前委员会草案。

序列参数集RBSP语法

在某些实施例中，一个或多个所述设备的部分或全部功能或流程由计算机可读程序代码构成的且内嵌于计算机可读介质中的计算机程序来实现或提供支持。术语计算机可读程序代码摂包括任意类型的计算机代码，包括源代码、目标代码以及可执行代码。术语计算机可读介质摂包括任何类型的可以被计算机访问的非易失性介质，比如，只读存储器(ROM)、随机存取存储器(RAM)、硬盘驱动器、光盘(CD)、数字化视频光盘(DVD)或者任何其他类型的存储器。

为本专利文档中使用的特定术语和短语进行定义是有帮助的。术语“包括”和“包含”以及它们的派生词表示没有限制的包括。术语“或者”是包容性的，意为和/或。短语“与……关联”和“与其关联”以及其派生的短语意味着包括，被包括在内、与……互连、包含、被包含在内、连接到或与……连接、耦合到或与……耦合、可与……通信、与……配合、交织、并列、接近、被绑定到或与……绑定、具有、具有……属性，等等。

虽然本发明就某些实施例和一般相关方法方面进行了描述，但是对本领域技术人员而言，对实施例和方法的各种更改和变更将是显而易见的。因此，示例实施例的上述描述不限定或约束本发明。正如以下权利要求定义，其它修改、替代以及变更也是可能的，而不偏离本发明的精神和范围。