视频编解码器中的句法元素编码所用的方法和设备

摘要

本发明涉及用于在对视频进行编码或解码的处理中预测位移矢量分量句法元素编码的方法和装置。本发明特别涉及HEVC中的调色板模式编码中的“Run”句法元素。本发明更特别地适用于基于利用所谓的调色板进行编码后的或者根据所谓的调色板构建得到的预测结果块来对像素块进行预测编码的编码模式。本发明提出了通过使用可变的Golomb阶次来改进Run句法元素的编码。描述了Golomb阶次根据不同参数而改变的数个实施例。因此，改进了Run句法元素的编码。

说明书

技术领域

本发明涉及用于在对视频进行编码或解码的处理中预测位移矢量分量句法元素编码的方法和装置。本发明特别涉及HEVC中的调色板(palette)模式编码中的“行程(Run)”句法元素。

本发明更特别地适用于基于利用所谓的调色板进行编码后的或者根据所谓的调色板构建得到的预测结果块来对像素块进行预测编码的编码模式。

背景技术

本申请中的调色板被定义为具有使索引与像素的值相关联的条目的查找表。通常、但并非必需地，像素的值包括与该像素相关联的各颜色分量的值，这样得到彩色调色板。另一方面，像素的值可以由单个像素分量构成，这样得到单色调色板。

通常将对像素块进行编码的该模式称为调色板编码模式。例如，在高效视频编码(HEVC:ISO/IEC23008-2MPEG-H第2部分/ITU-TH.265)国际标准的范围扩展中，考虑采用该模式。

在对视频序列中的图像进行编码的情况下，首先将该图像分割成被称为编码树块(CTB)的具有大小相等的像素的编码实体。编码树块的大小通常是64×64个像素。然后，各编码树块可分解成较小块的层级树，其中这些较小块的大小可以改变，并且这些较小块是要编码的实际像素块。将要编码的这些较小块称为编码单元(CU)。

特定编码单元的编码通常是可以预测的。这意味着首先确定预测结果块。接着，计算预测结果块和编码单元之间的差。将该差称为残差。接着，对该残差进行压缩。编码单元的实际编码信息由用以表示确定预测结果块和压缩后的残差的方式的某种信息构成。最佳预测结果块是与编码单元尽可能相似以得到可以高效地进行压缩的小残差的块。

基于用于确定编码单元的预测编码方法所用的预测结果块的方法来定义编码模式。

将第一个编码模式称为INTRA(帧内)模式。根据INTRA模式，基于当前图像内的直接包围编码单元的像素的值来构建预测结果块。值得注意的是，预测结果块不是当前图像的块而是构建物。使用方向来确定构建预测结果块实际使用了边界的哪些像素以及如何使用这些像素。INTRA模式背后的想法是：由于自然图像的通常的连贯性，因此直接包围编码单元的像素有可能与当前编码单元的像素相似。因此，可以基于这些周围像素使用预测结果块来获得编码单元的像素值的良好预测。

将第二个编码模式称为INTER(帧间)模式。根据INTER模式，预测结果块是另一图像的块。INTER模式背后的想法是：序列中的连续图像通常非常相似。主要区别通常源自于由于照相机的滚动或者由于场景中的运动物体所引起的这些图像之间的运动。预测结果块由相对于当前图像内的编码单元的位置、给出该预测结果块在参考图像中的位置的矢量来确定。该矢量被称为运动矢量。根据该模式，使用该模式的这种编码单元的编码包括包含运动矢量和压缩后的残差的运动信息。

在本申请中关注于被称为调色板模式的第三个编码模式。根据调色板模式，可以将给定编码单元的预测结果块定义为来自调色板的索引的块：针对预测结果块中的各像素位置，预测结果块包含与调色板中的如下像素值相关联的索引，其中该像素值最接近于编码单元中位置相同(即，同位置)的像素的值。然后，计算表示预测结果块和编码单元之间的差的残差，并对该残差进行编码。调色板中的条目索引还已知为“等级(level)”。

在使用调色板模式的情况下，必须在位流中传输等级的预测结果块。对于该传输，使用三个句法元素对预测结果块进行二进制编码。被称为“Pred模式”的第一句法元素使得能够区分两个编码模式。在与值为0的Pred模式相对应的第一模式中，必须在位流中传输要编码的等级的值。在与值为1的Pred模式相对应的第二模式中，根据预测结果块中的上方像素的值来获得要编码的等级的值。不必传输该等级。

针对第一模式中的等级的值的传输来定义被称为“等级(Level)”的第二句法元素。使用被称为“Run”的第三句法元素来对重复值进行编码。考虑到从左上角向右下角、从左向右从上向下逐行扫描预测结果块，Run句法元素给出具有相同编码的预测结果块中的连续像素的数量。如果Pred模式是0，则这是具有相同等级值的预测结果块的连续像素的数量。如果Pred模式是1，则这是具有与上方像素的等级值相对应的等级值的预测结果块的连续像素的数量。

针对最低值使用Golomb-Rice(哥伦布-莱斯)码来对Run句法元素进行编码并且针对最高值使用指数Golomb码来对Run句法元素进行编码。这些Golomb码是使用被称为Golomb阶次的参数来定义的。对于Run句法元素的编码，假定该Golomb阶次的值为3。值得注意的是，Golomb熵编码的长度依赖于该阶次。

发明内容

本发明是为了改进调色板模式的“Run”句法元素的编码而设计的。

本发明提出了通过使用可变的Golomb阶次来改进Run句法元素的编码。描述了Golomb阶次根据不同的参数而改变的多个实施例。

根据本发明的第一方面，提供一种用于确定与索引块中的索引相关联的熵编码的至少一个参数的方法，其中所述索引块用于根据调色板对图像的编码单元进行编码，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述熵编码的至少一个参数是至少根据所述索引块的编码处理中所使用的参数来确定的。

在实施例中，所述熵编码的至少一个参数与所述熵编码的长度有关。

在实施例中，所述熵编码是Golomb型码。

在实施例中，所述熵编码的至少一个参数是所述Golomb型码的阶次。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据与所述熵编码相关联的所述至少一个索引的预测模式来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据与所述熵编码相关联的所述至少一个索引的索引值来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据调色板大小来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据编码单元大小来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，其中所述索引块中的各索引与各个像素相关联，并且所述熵编码的至少一个参数是根据与所述索引块中的索引相关联的剩余的像素的数量来确定的。

在实施例中，按扫描顺序以连续像素为组对所述索引块中的至少一个索引进行编码，其中使用给出预测模式的第一句法元素和给出重复次数的第二元素对各组进行编码，并且所述熵编码用于进行重复次数的句法元素的编码。

在实施例中，所述方法包括以下步骤：

-基于所述索引块的编码处理中所使用的至少一个第二参数来确定类别；以及

-针对各类别确定所述熵编码的至少一个参数的值。

在实施例中，所述方法还包括以下步骤：

-基于所述索引块的编码处理中所使用的至少一个第三参数，来改变所确定出的所述熵编码的至少一个参数的值。

在实施例中，所述至少一个第三参数包括针对同一类别所确定出的最后值以及最后编码的重复次数值。

在实施例中，所述至少一个第二参数包括与所述熵编码相关联的像素的预测模式或索引值。

在实施例中，所述熵编码的至少一个参数被确定为对于最后编码或解码的给定元素的编码或解码而言将是最佳的所述熵编码的参数的值，以进行相应的该给定元素的编码。

在实施例中，所述熵编码的至少一个参数的值被限制为固定数量的值。

根据本发明的第二方面，提供一种用于将视频数据编码在位流中的方法，其中所述方法包括以下步骤：

-根据第一方面所述的方法来确定所述熵编码的至少一个参数；以及

-使用所确定出的所述熵编码的参数或者所确定出的所述熵编码的一个参数，在所述位流中写入值。

根据本发明的第三方面，提供一种用于从位流中解码视频数据的方法，其中所述方法包括以下步骤：

-从所述位流中获得索引块的编码处理中所使用的参数；以及

-根据第一方面所述的方法来确定所述熵编码的至少一个参数。

根据本发明的第四方面，提供一种用于确定与索引块中的索引相关联的熵编码的至少一个参数的装置，其中所述索引块用于根据调色板对图像的编码单元进行编码，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述装置包括用于至少根据所述索引块的编码处理中所使用的参数来确定所述熵编码的至少一个参数的部件。

根据本发明的第五方面，提供一种用于将视频数据编码在位流中的装置，包括：用于确定与索引块中的索引相关联的熵编码的至少一个参数的部件，其中所述索引块用于根据调色板对图像的编码单元进行编码，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述装置包括用于至少根据所述索引块的编码处理中所使用的参数来确定所述熵编码的至少一个参数的部件；以及用于使用所确定出的所述熵编码的参数或者所确定出的所述熵编码的一个参数在所述位流中写入值的部件。

根据本发明的第六方面，提供一种用于从位流中解码视频数据的装置，包括：用于从所述位流中获得索引块的编码处理中所使用的参数的部件；以及用于确定与索引块中的索引相关联的熵编码的至少一个参数的部件，其中所述索引块用于根据调色板对图像的编码单元进行编码，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述装置包括用于至少根据所述索引块的编码处理中所使用的参数来确定所述熵编码的至少一个参数的部件。

根据本发明的第七方面，提供一种可编程设备所用的计算机程序产品，其中所述计算机程序产品包括指令序列，所述指令序列用于在被载入所述可编程设备并由所述可编程设备执行的情况下，实现根据第一方面、第二方面和第三方面中的任一方面所述的方法。

根据本发明的第八方面，提供一种用于存储计算机程序的指令的非瞬态计算机可读存储介质，其中所述指令用于实现根据第一方面、第二方面和第三方面中的任一方面所述的方法。

根据本发明的第九方面，提供一种信息存储部件，其能够由用于存储计算机程序的指令的计算机或微处理器进行读取，其中，所述信息存储部件使得能够实现根据第一方面、第二方面和第三方面中的任一方面所述的方法。

根据本发明的另一方面，提供一种用于将视频数据编码在位流中的方法，其中所述方法包括：根据第一方面确定熵编码的至少一个参数；以及将所确定的值写入所述位流中。

根据本发明的另一方面，提供一种用于根据位流解码视频数据的方法，其中所述方法包括：根据第一方面确定熵编码的至少一个参数；以及从所述位流读取所确定的值。

根据本发明的又一方面，提供一种用于确定与根据调色板对图像的编码单元进行编码所使用的索引块中的索引相关联的熵编码的至少一个参数的方法，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述至少一个参数是至少依赖于所述索引块的编码处理中所使用的参数来确定的。因此，改进了Run句法元素的编码。

在实施例中，所述熵编码的至少一个参数与所述熵编码的长度有关。

在实施例中，所述熵编码是Golomb型码。

在实施例中，所述熵编码的至少一个参数是所述Golomb型码的阶次。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据与所述熵编码相关联的所述至少一个索引的预测模式来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据与所述熵编码相关联的所述至少一个索引的索引值来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据调色板大小来确定的。

在实施例中，对所述索引块中的至少一个索引进行预测编码，并且所述熵编码的至少一个参数是根据编码单元大小来确定的。

在实施例中，对所述索引块的至少一个索引进行预测编码，所述熵编码的至少一个参数是依赖于要解码或编码的等级块中剩余的像素的数量来确定的。

在实施例中，按扫描顺序以连续像素为组对所述索引块进行编码，其中使用给出预测模式的第一句法元素和给出重复次数的第二元素来对各组进行编码，并且所述熵编码用于进行重复次数的句法元素的编码。

在实施例中，所述方法包括以下步骤：

-基于所述索引块的编码处理中所使用的至少一个第二参数来确定类别；以及

-针对各类别确定所述熵编码的至少一个参数的值。

在实施例中，所述方法还包括以下步骤：

-基于所述索引块的编码处理中所使用的至少一个第三参数，来改变所确定出的所述熵编码的至少一个参数的值。

在实施例中，所述至少一个第三参数包括针对同一类别所确定出的最后值以及最后编码的重复次数值。

在实施例中，所述至少一个第二参数包括预测模式或者与所述熵编码相关联的像素的索引值。

在实施例中，所述熵编码的至少一个参数被确定为对于最后编码或解码的相应元素的编码或解码而言将是最佳的所述熵编码的参数的值，以进行给定元素的编码。

在实施例中，所述熵编码的至少一个参数的值被限制为固定数量的值。

根据本发明的另一方面，提供一种用于将视频数据编码在位流中或者解码位流中的视频数据的方法，其中所述方法包括以下步骤：

根据本发明的用于确定熵编码的至少一个参数的步骤；以及

用于将所确定的值写入所述位流中、或者从所述位流读取所确定的值的步骤。

根据本发明的另一方面，提供一种用于对根据调色板对图像的编码单元进行编码所使用的索引块进行编码的方法，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，按扫描顺序以连续像素为组来对所述索引块进行编码，使用给出预测模式的第一句法元素和给出重复的第二元素对各组进行编码，所述熵编码用于进行重复的句法元素的编码，所述调色板根据所述索引块中的索引的发生而重新排序，其中针对与比预定义的阈值大的索引相关联的像素的组，不对重复元素进行编码。

根据本发明的另一方面，提供一种用于确定与根据调色板对图像的编码单元进行编码所使用的索引块中的索引相关联的熵编码的至少一个参数的方法，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述至少一个参数被确定为零值。

根据本发明的另一方面，提供一种用于确定与根据调色板对图像的编码单元进行编码所使用的索引块中的索引相关联的熵编码的至少一个参数的装置，所述调色板包括与像素值相关联的索引的集合，所述熵编码用于进行所述索引块的至少一部分的编码，其中，所述装置包括用于至少依赖于所述索引块的编码处理中所使用的参数来确定所述至少一个参数的部件。

根据本发明的另一方面，提供一种可编程设备所用的计算机程序产品，所述计算机程序产品包括指令序列，其中所述指令序列用于在被载入所述可编程设备并由所述可编程设备执行的情况下，实现根据本发明所述的方法。

根据本发明的另一方面，提供一种用于存储计算机程序的指令的非瞬态计算机可读存储介质，其中所述指令用于实现根据本发明所述的方法。

根据本发明的另一方面，提供一种信息存储部件，其能够由用于存储计算机程序的指令的计算机或微处理器进行读取，其中，所述信息存储部件使得能够实现根据本发明所述的方法。

根据本发明的还一方面，提供一种用于确定与图像中的根据调色板模式进行编码后的像素块的像素相关联的熵编码的参数的方法，其中，一个所述参数是依赖于所关联的像素的预测方向来确定的。

在实施例中，所确定的所述参数是所述熵编码的长度。

在实施例中，所确定的所述参数是Golomb码的参数。

在本发明的又一方面中，提供一种用于对图像进行编码的方法，所述方法包括上述的还一方面的用于确定参数的方法。

在本发明的又一方面中，提供一种对图像进行解码的方法，所述方法包括上述的还一方面的用于确定参数的方法。根据本发明的方法的至少一部分可以通过计算机来实现。因此，本发明可以采用完全硬件实施例、完全软件实施例(包括固件、常驻软件、微代码等)、或者组合在此通常均可称为“电路”、“模块”或“系统”的软件和硬件方面的实施例的形式。此外，本发明可以采用使计算机可用程序代码嵌入在介质中的任何有形表现介质中所嵌入的计算机程序产品的形式。

由于本发明可以以软件来实现，因此本发明可以体现为计算机可读代码以任何适当载体介质上提供至可编程设备。有形载体介质可以包括诸如软盘、CD-ROM、硬盘驱动器、磁带装置或固态存储器装置等的存储介质。瞬态载体介质可以包括诸如电气信号、电子信号、光学信号、声学信号、磁信号或者例如微波或RF信号的电磁信号等的信号。

附图说明

现在将仅通过示例的方式并且参考以下附图来说明本发明的实施例，其中：

图1示出HEVC编码器架构；

图2示出HEVC解码器架构；

图3示出原因区域(causalarea)的概念；

图4示出不同的视频格式；

图5示出将编码树块分割成编码单元和这些编码单元的扫描顺序解码；

图6示出HEVC中的句法元素的基于Golomb的二进制编码；

图7示出HEVC范围扩展的研究中的解码器侧的调色板模式预测的原理；

图8示出编码单元以及相应的等级块和关联的调色板的示例；

图9示出同一等级块以及该等级块的编码所使用的句法元素的集合；

图10示出与调色板模式有关的句法元素的解码处理；

图11示出用以构建等级块、然后构建颜色空间中的必须用作预测结果的块预测结果的重建处理；

图12示出编码器中的示例性调色板确定算法；

图13示出编码器中的Pred模式、Level和Run句法元素的选择；

图14示出Order(阶次)值依赖于等级块中剩余的像素的数量的实施例；

图15示出在位流中传输Order值的实施例；

图16示出与用于决定不传输Run值的Level值的阈值的解码有关的实施例；

图17是本发明的一个或多个实施例的实现所用的计算装置的示意框图。

具体实施方式

图1示出HEVC编码器架构。在视频编码器中，将原始序列101分割成像素块(102)。然后，编码模式对各块产生影响。存在HEVC中通常使用的两类编码模式：基于空间预测的模式或者INTRA模式103、以及基于时间预测的模式或基于运动估计104和运动补偿105的INTER模式。通常通过被称为INTRA预测的处理，根据INTRA编码单元的原因边界处的编码后像素来预测INTRA编码单元。已知为HEVCRExt的当前设计中的HEVC的扩展添加了用以对像素块进行编码的附加的编码模式、即与INTRA和INTER编码模式竞争的调色板编码模式。以下特别是参考图7～13来更详细地说明该调色板编码模式。

INTER编码模式的时间预测首先在于：在运动估计步骤104中，在被称为参考帧116的先前帧或将来帧中发现离编码单元最近的参考区域。该参考区域构成预测结果块。接着，在运动补偿步骤105中，使用预测结果块来预测该编码单元以计算残差。

在空间预测和时间预测这两种情况下，通过从原始预测结果块中减去编码单元来计算残差。

在INTRA预测中，对预测方向进行编码。在时间预测中，对至少一个运动矢量进行编码。然而，为了进一步降低与运动矢量编码有关的位率成本，不是直接对运动矢量进行编码。实际上，假定运动是均匀的，则将运动矢量编码成该运动矢量与其周围的运动矢量之间的差，这特别值得关注。例如在H.264/AVC编码标准中，相对于所计算出的位于当前块的上方和左方的三个块之间的中值矢量，对运动矢量进行编码。仅将所计算出的中值矢量和当前块运动矢量之间的还被称为残差运动矢量的差编码在位流中。这是在模块“Mv预测和编码”117中进行处理的。将各编码后矢量的值存储在运动矢量字段118中。从运动矢量字段118中提取预测所使用的相邻运动矢量。

然后，在模块106中选择使率失真性能最优的模式。为了进一步减少冗余，在模块107中对残差块实施通常为DCT的变换，并且在模块108中对系数实施量化。然后，在模块109中对量化后的系数块进行熵编码，并且将该结果插入位流110中。

然后，在模块111～116中，编码器进行编码后的帧的解码，以供将来运动估计所使用。这是编码器中的解码回路。这些步骤使得编码器和解码器能够具有相同的参考帧。为了重建编码后的帧，在模块111中对残差进行逆量化并且在模块112中对残差进行逆变换，从而在像素域中提供“重建”残差。根据编码模式(INTER或INTRA)，将该残差添加至INTER预测结果(114)或INTRA预测结果(113)。

然后，在模块115中，利用一种或数种后滤波对该第一次重建进行滤波。这些后滤波器集成于解码回路中。这意味着，需要在编码器和解码器处将这些后滤波器应用于重建帧，以在编码器和解码器处使用相同的参考帧。该后滤波的目的是去除压缩伪像(compressionartifact)。

在图2中示出了HEVC解码器的原理。首先，在模块202中对视频流201进行熵解码。然后，在模块203中对残差数据进行逆量化并且在模块204中对残差数据进行逆变换，以获得像素值。还可以对模式数据进行熵解码，并且根据模式来进行INTRA型解码或INTER型解码。在INTRA模式的情况下，从位流中解码得到INTRA预测方向。然后，使用该预测方向来定位参考区域(205)。如果模式是INTER，则从位流中解码得到运动信息(202)。该运动信息包括参考帧索引和运动矢量残差。将运动矢量预测结果添加至运动矢量残差以获得运动矢量(210)。然后，使用运动矢量来定位参考帧中的参考区域(206)。注意，利用解码后的运动矢量来更新运动矢量字段数据211以用于下一解码后运动矢量的预测。然后，利用与编码器侧所使用的完全相同的后滤波器来对解码后的帧的该第一次重建进行后滤波(207)。解码器的输出是解压缩视频209。

图3示出通过如HEVC那样的逐块编码所得到的原因原理。

在高等级处，图像分割成按光栅扫描顺序进行编码的编码单元。因而，在对块3.1进行编码的情况下，区域3.3的所有块已进行了编码，并且可被视为可供编码器利用。同样，在解码器处对块3.1进行解码的情况下，区域3.3的所有块已进行了解码并且如此进行了重建，并且可被视为在解码器处可利用。区域3.3被称为编码单元3.1的原因区域。一旦对编码单元3.1进行了编码，则该编码单元3.1将属于下一编码单元的原因区域。该下一编码单元以及接下来的所有编码单元属于作为点状区域示出的区域3.4，并且无法用于对当前编码单元3.1进行编码。值得注意的是，原因区域由重建块构成。用于对给定编码单元进行编码的信息不是图像的原始块，其原因是该信息在解码时不可用。解码时可用的唯一信息是原因区域中的像素块的重建版本、即这些块的解码后版本。由于该原因，在编码时，对原因区域中在先前进行了编码的块进行解码以提供这些块的该重建版本。

在对块3.1进行编码时，可以使用来自原因区域中的块3.2的信息。在HEVC范围扩展草案规范中，可在位流中传输的位移矢量3.5可以表示该块3.2。

图5示出将编码树块分割为编码单元以及用以顺次处理这些编码单元的示例性扫描顺序。在HEVC标准中，利用编码树块(CTB)来组织块结构。帧包含数个非重叠的正方形编码树块。编码树块的大小可以等于64×64～16×16。该大小是在序列层级确定的。在编码效率方面最高效大小是最大大小即64×64。请注意，除图像边界外，所有的编码树块具有相同的大小。边界CTB的大小根据剩余像素的数量而改变。

各编码树块包含一个或多个正方形的编码单元(CU)。编码树块基于四叉树结构而分割成多个编码单元。编码树块中的各编码单元的处理(编码或解码)顺序基于光栅扫描顺序而遵循四叉树结构。图5示出编码单元的处理顺序的示例。在该图中，各编码单元中的数字给出该编码树块的各相应编码单元的处理顺序。

在HEVC中，使用多个方法来对不同的句法元素(例如，块残差、与预测结果块有关的信息(运动矢量、INTRA预测方向等))进行编码。HEVC使用如基于上下文的自适应二进制算术编码(CABAC)、Golomb-rice码或被称为固定长度编码的简单二进制表示那样的多种熵编码。在大多数情况下，进行二进制编码处理以表示不同的句法元素。该二进制编码处理同时也是非常有针对性的，并且依赖于不同的句法元素。

例如，被称为“coeff_abs_level_remaining”的句法元素包含系数残差的绝对值或该绝对值的一部分。该二进制编码处理的想法是针对最初的值使用Golomb-Rice码、并且针对更高的值使用指数Golomb码。更具体地，根据被称为GolombOrder(哥伦布阶次)的给定参数，这意味着为了表示最初的值(例如，0～3的值)，使用Golomb-Rice码，然后对于更高的值(例如，4以上的值)，使用指数Golomb码。GolombOrder是Golomb-Rice码和指数Golomb码这两者所使用的参数。

图6示出解码侧的该原理。解码处理的输入数据是位流601以及GolombOrder或已知为RiceGolomb参数的Order。该处理的输出是解码后符号612。

在步骤602中将前缀(Prefix)值设置为等于1，然后从步骤601中的位流提取1位，并且将变量标志设置为等于解码后的值(603)。如果在步骤604中该标志等于0，则使Prefix值递增(605)，并且从位流提取另一位(603)。在标志值等于1的情况下，决定模块606检查值Prefix是否严格小于3。如果为真，则从位流601提取N位(其中，N＝Order)(608)并且将该N位设置为变量“码字”。这与Golomb-Rice表示相对应。如步骤609所示，将符号(Symbol)值612设置为等于((prefix<<Order)+码字)。其中，“<<”是左移运算符。

如果在步骤606中Prefix大于或等于3，则下一步骤是610，其中在该步骤610中，从位流中提取N位(其中，N＝prefix–3+Order)，并且将这N位设置为变量“码字”(610)。将符号值611设置为等于((1<<(prefix-3))+2)<<Order)+码字。这与指数Golomb表示相对应。

以下，该解码处理和采用对称方式的相应编码处理被称为输入参数与GolombOrder相对应的Golomb_H。可以用简单方式来标注Golomb_H(Order)。

在HEVC中，对于诸如残差等的一些句法元素，更新GolombOrder以使得熵编码适应要编码的信号。在系数的值较大的情况下，更新公式尝试通过增加GolombOrder来减小Golomb码的大小。在HEVC标准中，通过以下公式来给出更新：

Order＝Min(cLastRiceOrder+(cLastAbsLevel＞(3*(1

＜＜cLastRiceOrder))？1:0)，4)

其中，cLastRiceOrder是最后使用的Order，cLastAbsLevel是最后解码的coeff_abs_level_remaining。请注意，对于要编码或解码的第一个参数，cLastRiceOrder和cLastAbsLevel设置为等于0。此外，请注意，在该公式中，参数Order不能超过值4。并且，表达式(C？A:B)在条件C为真的情况下具有值A，并且在条件C为假的情况下具有值B。

通常还被称为HEVCRExt的HEVC范围扩展是新的视频编码标准HEVC的当前正起草的扩展。

该扩展的目的是提供利用附加的颜色格式和位深度并且可以以无损方式对视频序列进行编码的附加工具。特别地，该扩展被设计成除4:2:0视频格式(参见图4)外，还支持4:2:2颜色格式和4:4:4视频格式。彩色图像通常由三个颜色分量R、G和B构成。这些分量通常相关，并且在图像和视频压缩中，在处理对图像之前对颜色分量进行去相关是很常见的。对颜色分量进行去相关的最常见格式是YUV颜色格式。通常，通过向R、G和B输入帧这三个输入应用线性变换，根据图像的RGB表示来创建YUV信号。Y通常被称为亮度分量，U和V通常被称为色度分量。代替术语“YUV”，通常还使用术语“YCbCr”。

关于作为对像素的各颜色分量进行编码所使用的位数的位深度，如果当前HEVC标准能够应对具有8位和10位的位深度(即，256～1024个可能的颜色)的4:2:0颜色格式，则HEVCRExt将被设计成附加地支持具有8位～16位的扩展位深度(即，多达65536个可能颜色)的4:2:2和4:4:4视频格式。这对于具有更大的颜色分量动态而言特别有用。

HEVCRExt还被设计成提供输入序列的无损编码；这是为了使解码输出209严格等于输入101。为了实现此，与传统的HEVC有损编解码器相比，修改或添加了多个工具。这里提供以下用以以无损方式进行工作的示例性修改或添加的非穷尽列表：

-去除量化步骤108(解码器中的203)；

-强制启用旁路变换，这是因为正常余弦/正弦变换107可能引入误差(解码器中的204)；

-去除专用于对量化噪声进行补偿的工具，诸如后滤波115(解码器中的207)等。

对于HEVCRExt，进一步修改了GolombOrder的更新公式，以适应于应对更高的位深度、并且考虑用于应对扩展格式(4:2:2和4:4:4)的包括无损编码的视频压缩的应用程序所要求的非常高的质量。对于HEVCRExt，更新公式已如下所述发生了改变：

Order＝Min(cLastRiceOrder+(cLastAbsLevel

＞＞(2+cLastRiceOrder))，7)

根据该公式，Order的最大值是7。此外，对于变换块的子块所用的coeff_abs_level_remaining的第一次编码，GolombOrder设置为：

Order＝

Max(0，cRiceOrder-(transform_skip_flag||cu_transquant_bypass_flag？1:

2))

其中：

·变量“transform_skip_flag”在针对当前编码单元跳过了变换(例如，DCT107或204)的情况下被设置为1，并且在使用变换的情况下被设置为0，

·变量“cu_transquant_bypass_flag”在对编码单元进行无损编码的情况下被设置为1，否则被设置为0，

·变量“cRiceOrder”被设置为等于来自变换块的另一子块的最后使用的Order，否则被设置为0。

HEVCRExt的附加工具当前正被设计成除自然序列外，还对“画面内容”视频序列进行高效编码。“画面内容”视频序列是指具有与从例如包含文本、PowerPoint演示、图形用户界面和表格的个人计算机或任何其它装置捕获到的内容(例如，屏幕截图)相对应的非常有针对性的内容的特殊视频序列。这些特殊视频序列与自然视频序列相比具有相当不同的统计数据。在视频编码中，包括HEVC的传统视频编码工具的性能在处理这种“画面内容”的情况下有时被证明未给人留下深刻印象。

HEVCRExt中当前讨论的用以处理“画面内容”视频序列的当前工具包括帧内块复制(IntraBlockCopy)模式和调色板模式。这些模式的原型与以自然视频序列作为对象的传统方法相比已表现出良好的编码效率。在本申请中关注于调色板编码模式。

HEVCRExt的调色板模式是预测模式。这意味着与通过运动预测(帧间情况)或通过帧内预测所进行的预测相同，使用调色板方法来构建给定编码单元的编码所用的预测结果。在生成了预测之后，对残差编码单元进行变换、量化和编码。换句话说，以上参考图1和2所述的处理同样适用。

通常利用包含N元组颜色的有限集合的表(例如，参见基于YUV颜色空间的图8中的803)来表示调色板，其中各颜色由该颜色在给定颜色空间中的分量来定义。例如，在典型的RGB格式中，调色板包括P个N元组(其中，对于RGB，N＝3)元素的列表。更精确地，各元素与采用RGB格式的颜色分量的固定三元数组相对应。当然，这不限于RGB或YUV颜色格式。任何其它的颜色格式可以利用调色板来表示，并且可以使用数量更少或更多的颜色分量，这意味着N可以不同于3。

在编码器侧，RExt中所考虑的调色板模式在于：将给定的输入编码单元的像素值变换成被称为标识出关联调色板中的条目的等级的索引。在该变换之后，如此得到的编码单元或块包括等级，然后与该关联调色板(通常是具有用于表示编码单元的有限数量的颜色的三元数组的表)一起被发送至解码器。由于调色板定义有限数量的颜色，因此向索引块的变换通常近似原始的输入编码单元。

为了在编码器侧应用调色板模式，如下所述进行用以对像素的编码单元进行变换的示例性方式：

-例如通过使整体失真最小化，来求出最佳地描述要编码的像素的编码单元的P个三元数组；

-然后使编码单元的各像素与这P个三元数组中最接近的颜色相关联：则要编码的值(或等级)是与所关联的最接近的颜色的条目相对应的索引。

对于各编码单元，调色板(即，所发现的P个三元数组)、索引块或等级块、以及表示原始编码单元和颜色空间中的索引块(也就是块预测结果)之间的差的残差被编码在位流110中，并且发送至解码器。

在解码器处，调色板模式在于以相反方式来操作转换。这意味着利用从位流解码得到的调色板中的相应颜色来替换与编码单元的各像素相关联的各解码后索引，以重建编码单元的各像素的相应颜色。这是颜色空间中的索引块(即，编码单元预测结果)的重建。由于调色板模式是预测模式，因此从位流解码得到关联的残差，然后将该残差与重建编码单元预测结果相加，以构建最终的重建编码单元。

图7还示出解码器处的调色板模式的原理。在步骤702中从位流701提取当前编码单元所用的预测模式。当前，利用位流中的位于跳过标志之前的标志来标识调色板模式(以上参考图1和2已说明了其它编码模式)。该标志是使用单个上下文进行编码得到的CABAC。如果该模式是调色板模式(703)，则从位流701提取并解码得到(704)调色板模式的相关句法705(即，与调色板、等级块和残差有关的信息)。

然后，在步骤706期间，根据解码后数据构建调色板707和等级块708这两个元素。根据该等级块和关联的调色板，构建(709)像素域中的编码单元预测结果710。这意味着对于块等级的各等级，颜色(RGB或YUV)关联至各像素。

然后，从位流701解码得到(711)编码单元残差。在当前实现即调色板模式中，使用常见的HEVC帧间残差编码方法、即使用Golomb编码来对与调色板模式相关联的残差进行编码。为了获得编码单元的残差，进行传统的逆量化和逆变换。将块预测结果710与该编码单元残差712相加(713)，以形成重建编码单元714。

图8示出编码器处的调色板模式的原理。将当前编码单元801转换成代替3个颜色值(Y,U,V)或(R,G,B)而是包含各像素的等级的大小相同的块802。基于编码单元整体失真最小化来构建与该等级块相关联的调色板803，并且该调色板803针对每个条目使条目索引或等级与相应的像素颜色值相关联。请注意，针对单色应用，像素值可以仅包含一个分量。

如与图7有关地所述，针对各编码单元对调色板(和残差)进行编码并且将该调色板(和残差)插入位流中。以相同方式，对(与编码单元预测结果相对应的)等级块进行编码并将该等级块插入位流中，并且以下参考图9给出编码的示例。在该示例中，按水平顺序扫描等级块。

等级块91与图8所示的附图标记802的等级块完全相同。表92和93描述了用于对等级块91进行编码的连续句法元素。表93应被理解为表92的延续。该表中的句法元素与块91中的实线所包围的等级组的编码相对应。

按扫描顺序以连续像素为组来对等级块进行编码。使用给出预测方向的第一句法元素、给出重复次数的第二元素和给出像素值(即，等级)的可选的第三元素来对各组进行编码。该重复次数与组中的像素的数量相对应。

这两个表描述了与调色板模式相关联的当前句法。这些句法元素与等级块91所用的位流中所关联的编码后信息相对应。在这些表中，使用三个主要的句法元素来充分表示调色板模式的操作，并且如下所述在逐次考虑等级块91的等级的情况下使用。

被称为“Pred模式”的第一句法元素使得能够区分两个编码模式。在与等于“0”的“Pred模式”标志相对应的第一模式中，对于当前像素使用新的等级。在位流中，紧挨在该标志之后通知该等级。在与等于“1”的“Pred模式”标志相对应的第二模式中，使用“从上复制(copyup)”模式。更具体地，这意味着当前像素等级与位于紧挨在从针对光栅扫描顺序相同的位置起的上方的行处的像素等级相对应。在等于“1”的“Pred模式”标志的情况下，由于通过参考等级块91中的正上方的像素的等级的值而已知了等级的值，因此不必紧挨在该标志之后通知该等级。

被称为“Level”的第二句法元素表示仅处于“Pred模式”的第一模式下的当前像素所用的调色板的等级值。

使用被称为“Run”的第三句法元素来对“Pred模式”的两个模式中的重复次数值进行编码。考虑到从左上角向右下角并且从左向右从上向下逐行扫描等级块91，因此Run句法元素给出了块91中具有相同编码的连续像素的数量。

该“Run”句法元素具有根据“Pred模式”标志而有所不同的含义。在Pred模式是0的情况下，“Run”元素是预测结果块中具有相同的等级值的连续像素的数量。例如，如果Run＝8，则这意味着当前“Level”适用于当前像素，并且适用于后面的8个像素，其中这9个像素与光栅扫描顺序中的9个相同连续样本相对应。

在Pred模式是1的情况下，“Run”元素是预测结果块中具有与块91中的连续像素上方的像素的等级值相对应的等级值(即，应用了“从上复制”模式)的这些连续像素的数量。例如，如果Run＝31，则这意味着当前像素以及后面的31个像素(与总共32个像素相对应)的等级是从上方的行的像素复制而来的。

关于表92和93，通过使用调色板模式来表示用以表示块91的八个步骤。各步骤从“Pred模式”标志的编码开始，在“Pred模式”标志等于“0”的情况下跟随“Level”句法元素、或者在“Pred模式”标志等于“1”的情况下跟随“Run”句法元素。“Run”句法元素始终跟随在“Level”句法元素之后。

在针对当前块进行解码的预测模式是调色板模式的情况下，解码器首先对与该块有关的句法进行解码，然后针对编码单元应用重建处理。

图10示出与调色板模式有关的句法元素的解码处理。首先，从位流1001提取调色板的大小并对调色板的大小进行解码(1002)。通过将步骤1002中解码得到的该大小值加1来获得调色板的准确大小(Palette_size)。实际上，通过使用值0具有最小位数(1位)的一元码来对该大小进行编码并且调色板的大小不能等于0，否则没有像素值可以用来构建块预测结果。

然后，开始进行与调色板值解码相对应的处理。在步骤1004中将与调色板的索引相对应的变量“i”设置为等于0，接着在步骤1005中进行测试以检查“i”是否等于调色板大小(Palette_size)。如果不是这种情况，则从位流1001中提取一个调色板元素并且进行解码(1006)，然后将该一个调色板元素添加至具有等于“i”的关联等级/索引的调色板。然后，通过步骤107使变量“i”递增。如果“i”等于调色板大小(1005)，则调色板已经完全解码。

接着，进行与等级块91的解码相对应的处理。首先，将与像素计数器相对应的变量j以及变量syntax_i设置为0(1008)。然后，进行检查以获知像素计数器是否与该块中所包含的像素的数量相对应。如果步骤1009中的答案为“是”，则在步骤1017中处理结束，否则从位流1001中提取与一个预测模式相对应的标志“Pred模式”的值并且进行解码(1010)。

将“Pred模式”的值添加至包含解码后的所有“Pred模式”值的表的索引syntax_i处。如果该“Pred模式”的值等于0(步骤1011)，则从位流1001中提取与“Level”相对应的句法元素并且进行解码(1012)。将该变量“Level”添加至包含解码后的所有等级的表的索引syntax_i处。使与像素计数器相对应的变量j递增1(1013)。

接着，在步骤1014中对“Run”句法元素进行解码。如果句法元素“Pred模式”等于1(步骤1011)，则在步骤1014中还对“Run”值进行解码。将该句法元素“Run”添加至包含解码后的所有行程的表的索引syntax_i处。

接着，在步骤1015中，使值j进行大小为步骤1014中进行解码后的行程的递增。使变量syntax_i递增1以考虑句法元素的下一集合。如果计数器j等于块中的像素的数量，则结束用以构建等级块91的句法(1017)。在与调色板有关的该处理结束时，解码器获知调色板以及包含与该编码单元的调色板模式相关联的所有“Pred模式”、“Level”和“Run”句法元素的列表的表。然后，解码器可以继续进行如通过图7所述的编码单元的重建处理。

通常使用三个二进制码来对上述示例中由三个值构成的各调色板元素进行编码。二进制码的长度与各颜色分量的位深度相对应。通常使用一元码来对调色板大小进行编码。使用一位来对“Pred模式”元素进行编码。使用二进制码长度等于b的二进制码来对“Level”元素进行编码，其中2^b是等于或大于调色板大小的最小整数。并且，如以上与图6有关地所述，使用Golomb_H(Order＝3)来对“Run”元素进行编码。

图11示出用以构建等级块911、然后构建颜色空间中的必须用作预测结果的块预测结果的重建处理。该处理的输入数据是以上在图10的处理中所获得的包含“Pred模式”、“Level”和“Run”的列表的表。附加的输入数据是根据位流中所通知的四叉树(图5)而获知的编码单元801的大小(与等级块802/91的大小相同)。

在第一个步骤1101中，将表示像素计数器的变量“i”设置为等于0，并且还将用以逐次考虑句法元素的各集合的变量“j”设置为等于0。在步骤1104中，检查从“Pred模式”的表中的索引j处所提取的元素Pred_mode[j]是否为0。

如果Pred_mode[j]等于0，则针对当前像素“i”编码新的等级。结果，位置“i”处的像素的值被设置为等于等级的表中的索引“j”处的等级；Block[i]＝Level[j]。这是步骤1105。在步骤1106中使变量“i”递增1以考虑下一像素，并且在步骤1107中将专用于对当前Run中已处理的像素进行计数的变量“k”设置为等于0。

在步骤1108中进行检查，以判断k是否等于行程的表中的索引j处的“Run”元素：k＝Run[j]？。如果不相等，则将位置i处的像素的等级设置为等于位置i-1处的像素的等级值：Block[i]＝Block[i-1]。这是步骤1109。然后，在步骤1110和1111中，分别使变量i和变量k递增1。如果在步骤1108中k＝Run[j]，则结束左方等级值的传播并且进行(以下所述的)步骤1120。

如果在步骤1104中Pred_mode[j]不同于0，则在步骤1112中，“从上复制”模式从变量“k”被设置为等于0开始。接着，步骤1113检查(k-1)是否等于行程的表中的索引“j”处的“Run”元素：k＝Run[j]+1？。如果不相等，则将位置i处的像素的等级值设置为等于上方行中的位置i处的像素的等级值：Block[i]＝Block[i-width]，其中“width”是如根据所输入的编码单元的大小推导出的等级块的宽度(与编码单元相同)。这是步骤1114。接着，在步骤1115和1116中，分别使变量“i”和变量“k”递增1。如果在步骤1113中k＝Run[j]+1，则预测模式“从上复制”完成并且处理继续进行步骤1120。

在步骤1120中，进行检查以判断变量i是否等于块91/CU801中的像素的数量。如果不相等，则在步骤1121中使变量j递增1以考虑句法元素的下一集合，并且处理循环回上述的步骤1104。

如果在步骤1120中对所有的像素均进行了处理，则在步骤1122中获得最后的等级块91：这与表Block[]相对应。然后，最后的步骤1123在于：使用利用图10的处理进行解码后的调色板803来将各等级转换成颜色值。该最后的步骤根据各个块位置的等级和调色板中的相应条目而影响该块位置处的像素值(Y,U,V)或(R,G,B)。

如在HEVCRExt中所引入的调色板模式的其它方面涉及：编码器所进行的要用于对当前编码单元进行编码的调色板的确定(参见以下的图12)、以及编码器中的Pred模式、Level和Run句法元素的选择(参见以下的图13)。

图12示出编码器中的示例性调色板确定算法。该处理的输入数据是像素的原始编码单元及其编码单元大小。在该示例中，构建YUV调色板，但其它实现可以得到具有以相同方式构建的RGB调色板。

在第一步骤1201中，将表示像素计数器的变量j设置为0，还将用以在构建调色板时跟随调色板的生长的变量“Palette_size”设置为0，并且将表示阈值的变量“TH”设置为9。然后，在步骤1203中，从原始编码单元1204读取具有与扫描顺序相对应的索引i的像素p_i。然后，在1205中将变量j设置为等于0，并且在步骤1206中，进行检查以判断调色板大小是否等于变量“j”(意味着考虑了构建中的调色板的所有调色板元素)。

如果调色板大小等于j，则在步骤1209中，将索引“j”处的调色板设置为等于像素值p_i。这意味着当前像素p_i变为调色板中与索引j相关联的新元素。更精确地，进行以下的分配：

PAL_Y[j]＝(Yi)

PAL_U[j]＝(Ui)

PAL_V[j]＝(Vi)

其中，PAL_Y,U,V是用以存储颜色值的三个表。

在步骤1210中使调色板大小(Palette_size)递增1，并且在步骤1211中，针对索引“调色板大小”，将发生表计数器设置为等于1。然后，在步骤1213中，使变量i递增1以考虑当前编码单元的下一像素“i”。然后，在步骤1214中进行检查以判断是否处理了当前编码单元的所有像素。如果处理了当前编码单元的所有像素，则通过后面所述的排序步骤1215来完成该处理，否则在上述的步骤1203中考虑下一像素。

返回至步骤1206，如果j不同于palette_size，则进行步骤1207，其中在该步骤1207中，计算p_i和索引j处的调色板元素之间的各颜色分量的绝对值。公式如图所示。如果所有的绝对差均严格小于预定义的阈值TH，则在步骤1212中使与调色板中的元素“j”有关的发生计数器递增1。步骤1207针对构建中的调色板的各元素创建类，其中在给定余量TH的情况下，这种类包含与该元素的颜色相邻的颜色。因而，步骤1212对各类的发生进行计数。在步骤1212之后进行已说明的步骤1213。

在不满足步骤1207的情况下，在步骤1208中使变量j递增1以考虑调色板中的下一调色板元素。这样，通过重新进行步骤1207来将其它调色板颜色元素与当前像素进行比较。如果在调色板中不存在满足步骤1207的标准的元素，则如上所述，参考步骤1209、1210和1211来向调色板添加新的元素。

可以注意到，决定模块1207可以针对4:4:4(YUV或RGB)序列比较各颜色元素，并且可以针对4:2:0序列仅比较亮度颜色分量。

在图12的处理结束时，表“计数器”包含各个调色板元素所定义的类的发生次数。然后，在步骤1215中根据调色板元素的发生来对调色板元素进行排序，使得最频繁的元素处于调色板中的首位(索引或“等级”最低的条目)。

还可以注意到，调色板的大小可以局限于例如24个条目的最大大小。在这种情况下，如果由于步骤1215而引起调色板的大小超过24，则通过去除来自排序后的调色板中的第25个位置的元素(条目)来缩小调色板。结果，这样构建了调色板。

现在转向编码器中的Pred模式、Level和Run句法元素的选择，图13的处理的输入数据是像素的原始编码单元、编码单元大小以及如通过图12的处理所构建的调色板。特别地，在判断必须使用INTRA编码、INTER编码和调色板编码中的哪个编码模式的情况下，进行该评价。

在第一步骤1301中，将表示像素计数器的变量“i”设置为0。以下所述的处理试图确定从i开始的像素的句法元素。独立地评价这两个预测模式：在图的右手部分，“Pred模式”＝0，在图的左手部分，“Pred模式”＝1。

对于“从上复制”预测(与“Pred模式”＝1相对应)，在步骤1303中将用于对当前Run中的等级的数量进行计数的变量“i_copy”设置为等于0。然后，在步骤1304中，将像素位置i处的当前等级即Block[i+i_copy]与位于上方行中的正上方的像素的等级即Block[i+i_copy-width]进行比较，其中“width”与当前编码单元的宽度相对应。注意，在步骤1308中并行地确定编码单元的各像素的等级Block[i+i_copy]。该步骤在于：使如以上已经说明的最接近的调色板元素(实际为其索引或等级)与位置i处的像素相关联。该步骤使用位置i、调色板1306和原始编码单元1307。

如果在步骤1304中Block[i+i_copy]＝Block[i+i_copy-width]，则在步骤1305中使变量“i_copy”递增1，以考虑像素块的下一像素值并且表示位置i+i_copy处的当前像素等级可以包括在当前“从上复制”Run中。如果在步骤1304中Block[i+i_copy]不同于Block[i+i_copy-width](这意味着“从上复制”Run的当前评价已结束)，则将变量“i_copy”发送至决定模块1314。在处理的该阶段，变量“i_copy”与从正上方的行所复制的值的数量相对应。

对于左方值预测(与“Pred模式”＝0相对应)，并行地或顺次地处理用以确定Run值(i_left)的循环。首先，将用于存储当前像素的索引i的变量“i_Start”设置为“i”，并且还将用以逐次考虑索引“i”之后的像素等级的变量“j”设置为等于“i”并将用于对构建中的当前Run进行计数的变量“i_left”设置为等于0。这是步骤1309。接着，步骤1310在于：判断j！＝0、“Pred_mode[j-1]”＝0和Block[j]＝Block[j-1]是否成立。Pred_mode[]是编码器为了存储预测模式(针对“从上复制”预测和左方值预测分别为1或0)所使用的表。在以下所述的步骤1317中，在处理连续像素时，逐渐填充Pred_mode[]，并且Pred_mode[]例如在步骤1301中已经利用零值进行了初始化：针对任意的k，Pred_mode[k]＝0。

如果满足步骤1310中的条件，则在步骤1311中使变量“i_left”递增1，以表示位置j处的当前像素等级可以包括在当前“左方值”Run中，并且在步骤1312中使变量j递增1，以考虑像素块的下一像素值。

如果不满足步骤1310的条件，则将变量“j”与“i_Start”进行比较，以判断“j”是否是针对当前“左方值”Run所要检查的第一个像素值。这是步骤1313。如果“j”等于或小于“i_Start”(这意味着“j”是针对当前Run所要检查的第一个像素值)，则开始当前Run，并且在上述的步骤1312中考虑下一像素值。如果“j”严格高于“i_Start”，这意味着已经检测到与当前“左方值”Run的像素值不同的第一个像素值。将与当前“左方值”Run的长度相对应的变量“i_left”发送至决定模块1314。注意，作为“从上复制”预测所用的循环，在步骤1308中在相同的循环中判断索引i处的等级Block[i]。

在计算了“左方值预测”和“从上复制”模式所用的最大行程之后，在步骤1314中比较变量“i_left”和“i_copy”。这是为了判断“i_copy”！＝0并且“i_copy”+2高于“i_left”是否成立。这是用以选择从上复制模式或左方值预测模式的示例性标准。特别地，参数“2”可以略微改变。

步骤1314的条件表示：如果“i_copy”等于0、或者小于或等于i_left-2，则在步骤1315中选择“左方值预测”模式。在这种情况下，在同一步骤1315中，将“PredMode”变量设置为等于0并且将Run变量设置为等于“i_left”。另一方面，如果“i_copy”不同于0且严格高于“i_left-2”，则在步骤1316中选择“从上复制”模式。在这种情况下，在步骤1316中将“PredMode”变量设置为等于1并且将Run变量设置为等于“i_copy-1”。

然后，在步骤1317中，利用当前值“Pred_mode”和“Run”来更新编码器中的包含“Pred_mode”和“Run”的表。然后，在步骤1318中计算像素块中要考虑的下一位置，其中该下一位置与进行了“行程”值+1的递增的当前位置i相对应。然后，在步骤1319中进行检查，以判断是否处理了编码单元的最后的像素。如果是这种情况，则处理在步骤1320结束，否则从步骤1303和1309开始针对下一像素位置评价“左方预测”和“从上复制”这两个预测模式，以获得句法元素的新集合。

在该处理结束时，编码器获知编码单元的各样本的等级，并且能够基于三个表Pred_mode[]、Block[]和Run[]的内容来对等级块的相应句法进行编码。

一般而言，值较小的Golomb阶次最适合小范围的值的编码，而较高的Golomb阶次最适合对较高范围的值进行编码。如已经说明的，通常使用具有固定值3的Golomb阶次来对Run句法元素进行编码。根据本发明的一个方面，Run值的编码所使用的Golomb阶次基于某些参数而改变。这些参数可以特别包括等级的值、调色板的大小、预测模式、编码单元的大小。这是由于Run值的预期范围可能以某种方式与这些参数相关。

图14示出Run句法元素的GolombOrder的选择与其它参数之间的依赖性。该图基于已经说明的图10。与图10相比，图14包含与行程的解码所用的GolombOrder的确定有关的一个附加模块1418。如以下实施例所述，该Order参数可以依赖于调色板大小、Pred模式、Level的值和编码单元大小1419。

在本发明的一个实施例中，根据“Pred模式”来更新Order。这意味着基于具有2个预测模式的当前实现，可以考虑两个参数Order：与“Pred模式”＝0相对应的“左方预测”模式的Order[0]以及与“Pred模式”＝1相对应的“从上复制”预测模式的Order[1]。然而，可以向所考虑的2个预测模式添加一个或多个预测模式。因而，可以与N个可能的预测模式相对应地考虑N个不同的Order。

在特定实施例中，在N>2的情况下，可以仅使一个Order与2个或更多个预测模式相关联。换句话说，多个预测模式可以映射至同一Order值。由于关联至各个预测模式的Run值通常不同，因此根据预测模式来改变Run编码是高效的。实际上，“从上复制”模式的Run值通常高，并且如图9的示例所示，高于“左方预测”模式的Run值。这也是由于作为唯一能够传输等级的模式的“左方预测”模式的性质而引起的。在优选实施例中，“从上复制”、“Pred模式”的Order大于“左方预测”模式的Order。

在本发明的一个实施例中，根据等级来更新Order。对于“左方预测”模式(“Pred模式”＝0)，最后编码的句法元素是等级。对于该预测模式，使用等级来设置与该等级有关的特定Order。因而，可以考虑的Order的数量等于调色板大小。在特定实施例中，在调色板大小严格大于2的情况下，可以仅使一个Order与两个以上的等级值相关联。换句话说，多个等级可以映射至同一Order值。

对于“从上复制”预测模式，不对等级进行编码，然而可以考虑使用所复制的第一个等级来设置相关的Order。在附加实施例中，可以认为如“左方预测”模式所使用的左方等级使Order发生改变。在根据等级的发生对调色板进行了排序的情况下，Order根据等级的改变特别高效。等级越低，出现得越多。因而，较低等级的预期Run值应高于最高等级值的Run值。在优选实施例中，针对较低等级所定义的Order大于针对最高等级所定义的Order。

在本发明的一个实施例中，基于调色板大小来确定Order。如前面所述，默认设置最大调色板大小。因而，可以考虑的Order的数量等于调色板大小。然而，这不是必须的，并且有利地，在优选实施例中可以考虑更小范围的Order值。由于在等级的数量低的情况下平均Run值增加，因此Order根据调色板大小的改变是高效的。同样，如果等级的数量较高，则平均Run值减小。因而，在调色板大小较低的情况下可以增大Order，并且在调色板大小高的情况下可以减小Order。在优选实施例中，调色板大小值较低的Order大于调色板大小值最高的Order。在特定实施例中，可以利用依赖于调色板大小的公式来确定Order。

在本发明的一个实施例中，基于编码单元大小来确定Order。因而，在考虑当前的编码单元大小64×64、32×32、16×16、8×8的情况下，可以考虑的Order值的数量等于4。然而，这不是必须的，并且在另一实施例中可以考虑数量较小的Order值。由于在编码单元大小低的情况下，预期的Run值应较低，因此Order根据编码单元大小的改变是高效的；同样，如果编码单元大小较高，则预期的Run值应较大。因而，在编码单元大小较低的情况下可以减小Order并且在编码单元大小较高的情况下可以增大Order。在优选实施例中，针对较低的编码单元大小所确定的Order值低于针对最高的编码单元大小值所确定的Order值。在特定实施例中，可以利用依赖于调色板大小的公式来获得Order值。

在一个实施例中，Order值依赖于要解码或编码的等级块中剩余的像素的数量。在图14中，这意味着Order值依赖于值Pixels_in_Block-j。实际上，尚未解码或编码的像素的数量越低，Run元素的预期值越低。

在一个实施例中，可以组合所提出的不同改变方法。

在一个实施例中，例如根据以下的表，基于调色板大小和编码单元大小来确定Order值：

请注意，该表仅是作为可能的示例而给出的。

在一个实施例中，基于预测模式“Pred模式”和Level值来确定Order值。在优选实施例中，通过以下公式给出Order值：

If(pred_mode＝＝1)Order＝Order0

elseif(pred_mode＝＝0ANDlevel＝＝0)Order＝Order1

elseOrder＝Order2

在优选实施例中，Order0＝Order1。实际上，等级等于0是等级块的背景。因而，跟随在等于0的等级之后的预期Run值应高于跟随在其它等级值之后的Run值。在优选实施例中，Order0＝Order1＝2并且Order2＝0。这意味着：预期Run值针对“从上复制”预测模式和等级0(块背景)的情况下的“左方预测”模式应较高，并且针对“左方预测”模式的其它等级值应较低。

在一个实施例中，基于一些参数来定义类别。例如，可以如上所述基于预测模式或者基于预测模式和等级来定义类别。Order值与各类别相关联并且被称为OrderN，其中N是类别的编号。然后，可以基于一些其它参数来改变针对各类别所确定的阶次值。例如，可以基于针对该类别所确定的最后Order值和解码后的最后Run值来改变阶次值。针对各类别，对Order值进行初始化。可以将Order值初始化为默认值或值0。或者，可以使用如针对先前的编码单元所定义的最后Order值来对Order值进行初始化。

在一个实施例中，在使用给定Order值对Run值进行解码之后，编码器和解码器计算作为对于解码后的Run值的编码而言将会是最佳的GolombOrder值的OptOrder。然后，使用该最佳Order值作为所确定的针对下一解码后行程的Order值。

一个替代方案是利用值3对Order值进行初始化。对于各类别的第一个行程，Order值依赖于先前解码后的其它阶次值。

例如，可以使用以下公式：

If(LastRunN＝0)OrderN＝Max(0，LastOrderN-1)

If(LastRunN＞3*(LastOrderN+1))OrderN＝Min(4，LastOrderN+1)

其中，LastOrderN是最后使用的OrderN。LastRunN是针对类别N的最后解码Run值。

在另一实施例中，各类别具有自己的公式以更新OrderN值。例如，利用以下公式，Order2的公式应使Order值与其它两个Order0和Order1的公式相比更快地减小：

If(LastRun2＜＝2)Order2＝Max(0,LastOrder2-1)

代替地，

If(LastRun2＝0)Order2＝Max(0,LastOrder2-1)

在一个实施例中，在位流中传输Order值。图15示出针对当前编码单元的本实施例。因而，在步骤1518中，从位流1501中提取Order值以对行程参数进行解码。图15基于图10。因而，其它模块与图10中所使用的相同。在编码器侧，利用率失真标准来选择该参数。该算法在于测试Order的多个值。选择给出最佳率失真妥协的值。

为了限制针对位率的影响，可以将该值限制为小的固定数量的值。例如，Order值可以仅局限于0、1、2这3个值。因而，可以利用(与该值相对应的)1位或2位的码来对该值进行编码。可以传输一个标志，以获知是否需要改变Order值。在另一实施例中，可以利用另一Order值或所使用的最后Order值来预测该Order值。在另一实施例中，可以通知1位，以通知Order＝0或Order＝2。

本实施例可以与已说明的实施例相组合。在优选实施例中，考虑如在先前部分中所述的Order0、Order1和Order2这3个Order值。因而，对于“Pred模式”、“从上复制”(＝1)，使用Order0；对于先前解码的等级是0的情况下的“Pred模式”左方(＝0)，使用Order1；否则使用Order2。并且，针对各编码单元传输这些OrderN。在优选实施例中，仅传输Order0和Order2并且Order1＝Order0。在图15中示出这些实施例；实际上，模块1518与块即“Pred模式”1510、等级1512具有一些关系。

在一个实施例中，不传输某些Run值，这意味着这些Run值被默认值(例如，值0)替换。通常，不传输的Run值是与不太常用的较高的Level值相关联的Run值。这意味着不太常用的Level值的重复模式不会用于进行编码。等级块中具有相同的高Level值的两个连续像素将如不存在重复那样各自生成编码。不传输给定的Run值的决定可以基于最后解码的Level值。例如，可以针对Level值来定义阈值。该阈值可以是固定的，例如值为4。该阈值可以基于根据编码单元大小和调色板大小的查找表。

在一个实施例中，在序列、帧、CTB或编码单元层级的位流中传输阈值。

图16示出与该图中的被称为“极值”的阈值的解码有关的实施例。

在一个实施例中，利用一元最大码(unarymaxcode)或一元码来对极值进行编码。如果针对各编码单元来对该极值进行编码，则一元最大码的最大大小等于调色板大小。还可以在编码单元层级考虑二进制码，并且位数可以依赖于调色板大小。图16示出这些实施例。该极值是从位流解码得到的(1618)。然后，对于调色板大小，将极值设置为等于解码后的极值+1(1619)。在对“Level”进行解码的情况下(1612)、并且如果“Level”大于或等于极值(1620)，则不对run句法元素进行解码并且将该run句法元素设置为等于0。并且，对模块1615进行处理，否则照常对行程进行解码(1614)。请注意，针对各编码单元对极值进行一次解码。

在另一实施例中，在对调色板大小进行编码之前，利用一元码对极值进行编码。将调色板大小设置为等于解码后的大小+极值+1。

在编码器侧，基于率失真标准来选择该极值。这意味着计算多个测试值以求出在率失真标准方面最佳的极值。在编码器侧，另一解决方案是选择与所有的行程参数均等于0的较低等级相等的极值。这意味着对于大于该极值的所有等级，将关联的行程设置为等于0。

在一个实施例中，无论其它参数的值如何，始终将GolombOrder设置为等于0(Golomb_H(0))。

在一个实施例中，对Run值的值进行限制以避免Golomb码过大。实际上，在值实际上很大的情况下，关联的Golomb码的位数非常大。这样显著增加了熵解码处理复杂度，并且因此增加了最差情况的复杂度。最差的情况用于设计硬件。本实施例的替代是使极限值关联至Golomb码，并且如果对该极限值进行解码，则解码器读取附加的二进制码。这意味着，如果当前值严格小于极值，则通常利用Golomb码对当前值进行编码。并且如果该当前值大于或等于极值，则利用跟随有固定数量的位的Golomb码对该极值进行编码。该固定数量的位是二进制码。在这种情况下，当前值等于极值+关联至附加固定位的数量。

可以组合所述的所有实施例。

在优选实施例中，根据以下公式，基于预测模式和最后解码等级来定义三个类别。

If(pred_mode＝＝1)Order＝Order0

elseif(pred_mode＝＝0ANDlevel＝＝0)Order＝Order1

elseOrder＝Order2

如下所述对Order0、Order1和Order2这三个相应的Order值进行初始化：Order0＝Order1＝2并且Order2＝0。然后，根据以下公式来更新三个order值：

If(LastRunN＝0)OrderN＝Max(0,LastOrderN-1)

If(LastRunN＞3*(LastOrderN+1))OrderN＝Min(4，LastOrderN+1)

其中，LastOrderN是最后使用的OrderN。LastRunN是针对类别N的最后解码Run值。

另外，对于Pred模式＝0，在最后解码Level值严格大于(或者大于或等于)阈值的情况下，不对Run值进行编码和解码。针对各调色板模式编码单元来从位流中提取阈值。

尽管与Golomb码有关地进行了说明，但这同样可以应用于改变任何其它熵编码的长度。例如，使用霍夫曼(Huffman)码，可以根据编码参数来确定霍夫曼码的特定字典。

图17是用于实现本发明的一个或多个实施例的计算装置1700的示意框图。计算装置1700可以是诸如微计算机、工作站或轻盈便携式装置等的装置。计算装置1700包括通信总线，其中该通信总线连接至以下组件：

-诸如微处理器等的表示为CPU的中央处理单元1701；

-表示为RAM的随机存取存储器1702，用于存储本发明实施例的方法的可执行代码以及根据本发明的实施例的如下寄存器，其中这些寄存器被配置为记录实现用于对图像的至少一部分进行编码或解码的方法所需的变量和参数，其中RAM1702的存储器容量例如可以利用连接至扩展口的可选RAM来扩展；

-表示为ROM的只读存储器1703，用于存储实现本发明实施例所用的计算机程序；

-网络接口1704，其通常连接至发送或接收要处理的数字数据所经由的通信网络。网络接口1704可以是单个网络接口、或者包括不同的网络接口(例如，有线接口和无线接口或者不同种类的有线接口或无线接口)的集合。在CPU1701中所运行的软件应用程序的控制下，将数据包写入网络接口以进行发送或者从网络接口读取数据包以进行接收；

-用户接口1705，其可用于从用户接收输入或向用户显示信息；

-表示为HD的硬盘1706，其可被设置为大容量存储装置；

-I/O模块1707，其可用于相对于诸如视频源或显示器等的外部装置进行数据的发送/接收。

可执行代码可以存储在只读存储器1703中、硬盘1706上或者例如盘等的可移除数字介质上。根据变形例，程序的可执行代码可以利用通信网络经由网络接口1704来接收，从而在执行之前存储在通信装置1700的诸如硬盘1706等的存储部件其中之一内。

中央处理单元1701被配置为控制和引导根据本发明实施例的一个或多个程序的指令或软件代码的一部分的执行，其中这些指令存储在上述存储部件其中之一内。在通电之后，CPU1701例如能够在从程序ROM1703或硬盘(HD)1706加载了来自主RAM存储器1702的与软件应用程序有关的指令之后，执行这些指令。这种软件应用程序在由CPU1701执行的情况下，使得进行图10～16所示的流程图的步骤。

图10～16所示的算法的任何步骤可以通过诸如PC(“个人计算机”)、DSP(“数字信号处理器”)或微控制器等的可编程计算机器执行一组指令或程序来以软件方式实现；或者还可以通过诸如FPGA(“现场可编程门阵列”)或ASIC(“专用集成电路”)等的机器或专用组件来以硬件方式实现。

尽管以上已经参考具体实施例说明了本发明，但本发明不限于这些具体实施例，并且本领域技术人员将明白存在于本发明的范围内的变形。

在参考仅以示例方式给出而并不意图限制本发明的范围的前述例示实施例的情况下，许多其它修改和改变对本领域普通技术人员是不言自明的，其中所述范围仅由所附权利要求书来确定。特别地，在适当情况下，可以互换来自不同实施例的不同特征。

在权利要求书中，词语“包括”没有排除其它要素或步骤，并且不定冠词“a”或“an”没有排除多个。在相互不同的从属权利要求中陈述不同的特征的仅有事实并不表明不能有利地使用这些特征的组合。