CN106797483B - 使用调色板模式的改进编码处理 - Google Patents

Abstract

本发明涉及视频编码和解码，具体地涉及定义调色板编码模式的HEVC SCC。在常规的调色板模式中，使用语法元素来对从编码单元和调色板构建的层级块进行编码，所述语法元素诸如“Pred mode”元素、可选的“Level”元素以及“Run”元素，“Run”元素定义“Pred mode”元素和可选的“Level”元素定义的操作所涉及的索引块的连续索引的数量。在本发明的改进实施例中，用于编码单元的最后一个“Run”元素使用特定的up‑to‑end码字，而不是与定义的连续索引数量相关联的码字，以便对直到索引块的末尾的所有的剩余块位置处的索引执行操作，而不管剩余块位置的数量如何。

Description

使用调色板模式的改进编码处理

技术领域

本发明涉及视频编码和解码。更确切地说，本发明涉及调色板(palette)模式编码方法。调色板模式是最初在HEVC范围扩展的范围中提出的编码方法，现在正在考虑用于HEVC的屏幕内容编码扩展。该编码方法对于以“屏幕内容”视频序列为目标的视频编码是高效的。

背景技术

本发明适用于使用索引块对当前像素块进行编码的编码模式，所述索引块是从所谓的调色板构建的。

本文档中的调色板被定义为具有将索引与像素的值相关联的条目的查找表。通常，但不一定，像素的值由与该像素相关联的每个颜色分量的值构成，从而导致彩色调色板。另一方面，像素的值可以由单个像素分量构成，从而导致单色调色板。

对像素块进行编码的这种模式通常被称为调色板编码模式。例如在高效视频编码(HEVC:ISO/IEC 23008-2MPEG-H Part 2/ITU-T H.265)国际标准的范围扩展中设想采用该模式。该模式现在在HEVC的屏幕内容编码(SCC)扩展的草案规范中被考虑。

当对视频序列中的图像进行编码时，首先将图像划分为相等大小的像素的编码实体，这些编码实体被称为编码树块(CTB)。编码树块的大小通常为64×64个像素。然后可以将每个编码树块分解为大小可以变化、并且是待编码的实际像素块的更小块的分层树。待编码的这些更小块被称为编码单元(CU)。

特定编码单元的编码通常是预测性的。这意味着首先确定预测块(predictorblock)。接下来，计算预测块和编码单元之间的差值。该差值被称为残差或残差块。接下来，对该残差进行压缩。编码单元的实际编码信息由指示被压缩的残差和预测块的确定的方式的一些信息组成。为了得到可以被高效地压缩的小残差，最佳预测块是尽可能类似于编码单元的块。

编码模式是基于用于对于编码单元的预测编码方法确定预测块的方法而定义的。

第一编码模式被称为帧内(INTRA)模式。根据帧内模式，基于紧紧围绕当前图像内的编码单元的像素的值来构建预测块。值得注意的是，预测块不是当前图像的块，而是重构。方向用于确定边际(border)的哪些像素实际用于构建预测块以及它们如何被使用。帧内模式背后的理念是，由于自然图像的通常的相干性，所以紧密围绕编码单元的像素有可能类似于当前编码单元的像素。因而，可以使用基于这些周围的像素的预测块来得到编码单元的像素的值的良好预测。

第二编码模式被称为帧间(INTER)模式。根据帧间模式，预测块是另一图像的块。帧间模式背后的理念是，序列中的连续图像通常是非常类似的。主要差异通常来自于由于照相机滚动或者由于场景中的移动对象而导致的这些图像之间的运动。预测块由矢量确定，该矢量给出预测块在参考图像中相对于当前图像内的编码单元的位置的位置。该矢量被称为运动矢量。根据该模式，使用该模式对这样的编码单元的编码包括运动信息，该运动信息包括运动矢量和压缩的残差。

在本文件中聚焦于被称为调色板模式的第三编码模式。根据调色板模式的先前版本，对于给定编码单元，预测块被定义为来自调色板的索引块：对于预测块中的每个像素位置，预测块包含与调色板中的如下像素值相关联的索引：该像素值最接近编码单元中具有相同位置(即，位于同一处)的像素的值。预测块因而具有与编码单元相同的大小。然后计算表示预测块(在像素域中)和编码单元之间的差值的残差。残差也具有与编码单元和预测块相同的大小。

调色板中的条目索引也被称为“层级(level)”。

在HEVC SCC中被考虑的调色板模式的最近版本中，没有残差被构建并且被发送到解码器(如下述图7中那样)。只有使用调色板形成的索引块被编码在比特流中以表示当前像素块。

一些像素用最佳调色板条目表示可能是糟糕的，这意味着像素和最佳调色板条目之间的差值高。使用索引来表示这样的像素可能是不值得的。

调色板模式因而使得可以识别这样的像素并且对它们的显式像素值进行编码，而不是使用近似索引。在没有残差(表示通过调色板条目得到的近似)被发送的情况下，这样的方法是特别重要的。其像素值被显式地编码的这样的像素被称为“被转义像素(escapedpixels)”，并且在索引块中不提供与调色板中的像素值相关联的对应索引。在HEVC的当前实现中，使用调色板的没有与像素值相关联的条目索引在索引块中标示(signal)“被转义像素”。

在调色板模式的这样的实现中，除了索引块和调色板之外，还构建被转义像素值块来存储被转义像素值。

预测块(即，索引块)、被转义像素值块、可能还有残差和调色板被编码以被添加到表示编码的当前编码单元的比特流。

为了针对调色板模式对索引块进行编码，使用多个语法元素集合，每个集合设置用于生成在索引块中具有连续块位置的对应索引组的操作。

在HEVC的屏幕内容编码扩展的当前草案规范中，提出了“向上拷贝(copy-up)”预测和“左值”预测，以参考或者在块矩阵中的上方、或者在其左侧的索引而对索引块的每个索引进行编码。

被称为“Pred mode”的一个语法元素定义被选择用于索引块中的对应索引组(即，用于该块的每个当前索引)的操作或预测模式，只要上面定义的游程(Run)没有结束即可。可选的(根据“Pred mode”)第二个语法元素(其被称为“Level”)指定仅在“左值”预测模式下用于对应索引组的新索引值。第三个也是最后一个语法元素(其被称为“Run”)指定由“Pred mode”语法元素定义的操作应用在多少个连续的块位置。换言之，它定义对应索引组中的(具有连续块位置的)索引的数量。

本发明的当前的实施例改善了调色板模式的编码效率。

发明内容

在第一方面，本发明提供一种从比特流解码图像中的当前像素块的方法，该方法包括：

获得索引块、被转义像素值以及调色板，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

从索引块、被转义像素值以及调色板形成解码的当前像素块，

其中，获得索引块包括：

从比特流获得语法元素，用于生成在索引块中具有连续块位置的索引组；

基于语法元素生成索引块的索引，

其中，所获得的语法元素包括由up-to-end码字所指示的语法元素，up-to-end码字指示形成索引组中的一个的索引是直到索引块的末尾的所有剩余块位置处的索引，而不管剩余块位置的数量如何。

在第二方面，本发明提供一种对图像中的当前像素块进行编码的方法，该方法包括：

从当前像素块和调色板生成索引块和被转义像素值，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

对索引块和被转义像素值进行编码，

其中，对索引块进行编码包括：

生成语法元素，这些语法元素用于生成在索引块中具有连续块位置的索引组，

其中，语法元素包括由up-to-end码字所指示的语法元素，up-to-end码字指示形成索引组中的一个的索引是直到索引块的末尾的所有剩余块位置处的索引，而不管剩余块位置的数量如何。

在第一方面和第二方面的实施例中，up-to-end码字可以包括标志。被转义像素值可以包括这样的被转义像素值的块。

在实施例中，语法元素使用与定义的数量的索引相关联并且与索引块的索引组对应的预定义码字，并且与索引块中的最后的块位置对应的语法元素使用up-to-end码字。

与预定义的数量的索引相关联的预定义码字可以是短码字，与其他定义的数量的索引相关联的其他预定义码字可以包括公共码字前缀和可变码字后缀；up-to-end码字可以包括公共码字前缀。例如，除了公共码字前缀之外，up-to-end码字还可以包括一位的后缀。

在实施例中，语法元素是以集合提供的，并且生成与语法元素集合相对应的索引组是依赖于该集合的第一语法元素的，用于生成索引的操作是以下操作中的一个：

重复具有正上方的块位置的索引；以及

重复集合的第二个语法元素中编码的索引。

在另一方面，提供一种存储程序的非暂时性计算机可读介质，该程序当被设备中的微处理器或计算机系统执行时使该设备执行上述方面和实施例中的任何一个的方法。

在又一方面，提供一种计算机程序，该计算机程序当执行时使任何前述方面或实施例的方法被执行。该计算机程序可以被实现于诸如机器可读介质之类的载体上。

在其他方面，提供一种使用第二方面或其实施例生成的比特流以及所述比特流存储于其上的存储介质。这样的存储介质可以采取例如蓝光盘、DVD、CD-ROM或另一设备可读介质的形式。

在另一方面，提供一种包括适于执行上面的方面或实施例中的任何一个的方法的部件的设备。

在本发明的另外的方面，提供一种用于从比特流解码图像中的当前像素块的解码设备，该解码设备包括：

用于获得索引块、被转义像素值以及调色板的部件，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

用于从索引块、被转义像素值以及调色板形成解码的当前像素块的部件，

其中，获得索引块包括：

从比特流获得语法元素，用于生成在索引块中具有连续块位置的索引组；及

基于语法元素生成索引块的索引，

其中，所获得的语法元素包括由up-to-end码字所指示的语法元素，up-to-end码字指示形成索引组中的一个的索引是直到索引块的末尾的所有剩余块位置处的索引，而不管剩余块位置的数量如何。

在本发明的又一方面，提供一种用于对图像中的当前像素块进行编码的编码设备，该编码设备包括：

用于从当前像素块和调色板生成索引块和被转义像素值的部件，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

用于对索引块和被转义像素值进行编码的部件，

其中，对索引块进行编码包括：

生成语法元素，用于生成在索引块中具有连续块位置的索引组；

其中，语法元素包括由up-to-end码字所指示的语法元素，up-to-end码字指示形成对应索引组中的一个的索引是直到索引块的末尾的所有剩余块位置处的索引，而不管剩余块位置的数量如何。

在另一方面，本发明提供一种从比特流解码图像中的当前像素块的方法，该方法包括：

获得索引块、被转义像素值以及调色板，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

从索引块、被转义像素值以及调色板形成解码的当前像素块，

其中，获得索引块包括：

从比特流获得语法元素，用于生成在索引块中具有连续块位置的索引组，其中，连续块位置的数量由游程指示；

基于语法元素生成索引块的索引，

其中，所获得的语法元素包括在比特流中的标志，该标志指示索引组的游程什么时候是正被解码的块中的最后的游程。在另一方面，提供一种设备和计算机程序，该设备具有用于执行所述解码方法的部件或被配置为执行所述解码方法的处理器，该计算机程序当被执行时使所述解码方法被执行。

在第二方面，本发明提供一种对图像中的当前像素块进行编码的方法，该方法包括：

从当前像素块和调色板生成索引块和被转义像素值，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

对索引块和被转义像素值进行编码，

其中，对索引块进行编码包括：

生成语法元素，用于生成在索引块中具有连续块位置的索引组，其中，索引组的连续块位置的数量由run指示；

其中，语法元素包括在比特流中的标志，该标志指示索引组的游程何时是正被解码的块中的最后一个游程。在另一方面，提供一种设备和计算机程序，该设备具有用于执行所述编码方法的部件或被配置为执行所述编码方法的处理器，该计算机程序当被执行时使所述编码方法被执行。

最后一个语法元素集合(即，用于编码单元中的最后的像素的集合)通常适用于大量像素(索引)，特别是适用于图像的最后一个编码单元，因为图像的末尾通常是单调的(monotonous)。使用这样的“up-to-end”值或标志因而改进了编码效率，因为它可以避免使用大量位来对表示最后一个“Run”所涉及的大量索引的值进行编码。

另外，可以避免对正在被处理的用于最后一个语法元素集合的索引的数量的控制(特别是在解码循环中)。这是因为由于“up-to-end”值或标志，所有的剩余索引都被涉及是已知的。

在一方面，本发明提供一种从比特流解码图像中的当前像素块的方法，该方法包括：

获得索引块、被转义像素值块以及调色板，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值块包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

从索引块、被转义像素值块以及调色板形成解码的当前像素块，

其中，获得索引块包括：

从比特流获得多个语法元素集合，每个集合设置用于生成在索引块中具有连续块位置的对应索引组的操作；

基于语法元素集合生成索引块的索引，

其中，每个集合中提供的语法元素(例如HEVC的屏幕内容编码草案规范中的Run元素)使用从至少两个可用码字选择的码字，所述至少两个可用码字包括up-to-end码字，up-to-end码字指示形成对应索引组的索引是直到索引块的末尾的所有的剩余块位置处的索引，而不管这样的剩余块位置的数量如何。

码字的使用意味着这样的码字被设置于所提供的语法元素中。

还提供一种对图像中的当前像素块进行编码的方法，该方法包括：

从当前像素块和调色板生成索引块和被转义像素值块，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值块包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

对索引块和被转义像素值块进行编码，

其中，对索引块进行编码包括：

生成多个语法元素集合，每个集合设置用于供解码器生成在索引块中具有连续块位置的对应索引组的操作，

其中，每个集合中提供的语法元素使用从具有至少两个可用码字的集合选择的码字，该至少两个可用码字包括up-to-end码字，up-to-end码字指示形成对应索引组的索引是直到索引块的末尾的所有的剩余块位置处的索引，而不管这样的剩余块位置的数量如何。

对应地，本发明的上述实施例提供一种用于从比特流解码图像中的当前像素块的解码设备，该解码设备包括被配置为执行以下步骤的至少一个微处理器：

获得索引块、被转义像素值块以及调色板，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值块包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

从索引块、被转义像素值块以及调色板形成解码的当前像素块，

其中，获得索引块包括：

从比特流获得多个语法元素集合，每个集合设置用于生成在索引块中具有连续块位置的对应索引组的操作；

基于语法元素集合生成索引块的索引，

其中，每个集合中提供的语法元素使用从至少两个可用码字选择的码字，该至少两个可用码字包括up-to-end码字，up-to-end码字指示形成对应索引组的索引是直到索引块的末尾的所有的剩余块位置处的索引，而不管这样的剩余块位置的数量如何。

还提供一种用于对图像中的当前像素块进行编码的编码设备，该编码设备包括被配置为执行以下步骤的至少一个微处理器：

从当前像素块和调色板生成索引块和被转义像素值块，调色板包括将各个条目索引与对应像素值相关联的条目的集合，被转义像素值块包括在索引块中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

对索引块和被转义像素值块进行编码，

其中，对索引块进行编码包括：

生成多个语法元素集合，每个集合设置用于供解码器生成在索引块中具有连续块位置的对应索引组的操作，

其中，每个集合中提供的语法元素使用从至少两个可用码字的集合选择的码字，该至少两个可用码字包括up-to-end码字，up-to-end码字指示形成对应索引组的索引是直到索引块的末尾的所有的剩余块位置处的索引，而不管这样的剩余块位置的数量如何。

这些实施例的可选特征在所附权利要求中定义。这些特征中的一些在下文中参考方法解释，并且可以调换为专门用于根据本发明的实施例的设备的系统特征。

在一些实施例中，用于所提供的语法元素的至少两个可用码字的集合包括与定义的数量的索引相关联的预定义码字，并且其中，所提供的语法元素对于与索引块的索引组相对应的每个集合使用这样的预定义码字中的一个，除了与索引块中的最后的块位置相对应的集合，该集合被称为最后一个集合，该最后一个集合的所提供的语法元素使用up-to-end码字。

该提供通过对于已知的语法元素插入附加码字(up-to-end码字)来节省编码效率。

根据特定实施方案，与定义的数量的索引相关联的一些预定义码字是短码字，与其他定义的数量的索引相关联的其他预定义码字包括公共码字前缀以及从一个其他的预定义码字到另一个码字不同的码字后缀；并且其中，up-to-end码字包括公共码字前缀。

短码字通常短于或等于公共码字前缀(就位数而言)。

该配置提供高效编码。这是因为，由于up-to-end码字在编码单元(像素块)中最多被用一次，所以对最频繁的索引数量保存短码字更高效。

在特定实施例中，除了公共码字前缀之外，up-to-end码字还包括一位的后缀。换言之，具有公共码字前缀的最短码字被用于“up-to-end”码字。这意图保持编码效率。

在使用包括公共码字前缀和后缀的up-to-end码字的变体中，up-to-end码字可以是特定的短码字(即，没有公共码字前缀)。

在实施例中，用于生成与语法元素集合相对应的索引组的操作依赖于该集合的第一语法元素(例如，Pred_mode元素)，用于生成索引的操作是以下操作中的一个：

重复具有正上方的块位置的索引。这是HEVC的“向上拷贝”或“上方拷贝”模式；以及

重复被编码在集合的第二语法元素(例如，Level元素)中的索引。这是在HEVC标准中被称为“向左拷贝模式”或“左预测模式”或“索引模式”的模式。

本发明的其他实施例针对一种用于对图像中的当前像素块进行编码的方法，该方法包括：

对当前像素块的包括调色板编码模式的两种或更多种编码模式中的每种编码模式的编码进行评估(或测试，即，估计编码成本以便从被测试的编码模式之中选择最佳编码模式)，调色板编码模式使用当前调色板来构建索引块(该索引块用于将当前像素块编码到比特流中)，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

基于评估从两种或更多种编码模式选择对当前像素块进行编码的编码模式，

其中，对当前像素块的使用调色板编码模式的编码的评估包括：连续地考虑当前块的像素，并且对于每个被考虑像素：

给定距离阈值，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；

如果在距离阈值给定的情况下在调色板中找到足够接近被考虑像素的调色板条目，则使用条目索引对被考虑像素进行编码；

如果在距离阈值给定的情况下在调色板中没有找到足够接近被考虑像素的调色板条目，则对被考虑像素进行转义编码，转义编码包括对被考虑像素的值进行显式编码；并且

其中，如果被转义编码的像素的数量超过当前像素块的预定义阈值，则中止对当前像素块的使用调色板编码模式的编码的评估。

对应地，一种用于对图像中的当前像素块进行编码的编码设备包括被配置为执行以下步骤的至少一个微处理器：

对当前像素块的包括调色板编码模式的两种或更多种编码模式中的每种编码模式的编码进行评估，调色板编码模式使用当前调色板来构建索引块，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

基于评估从两种或更多种编码模式选择对当前像素块进行编码的编码模式，

其中，对当前像素块的使用调色板编码模式的编码的评估包括：连续地考虑当前块的像素，并且对于每个被考虑像素：

给定距离阈值，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；

如果在距离阈值给定的情况下在调色板中找到足够接近被考虑像素的调色板条目，则使用条目索引对被考虑像素进行编码；

如果在距离阈值给定的情况下在调色板中没有找到足够接近被考虑像素的调色板条目，则对被考虑像素进行转义编码，转义编码包括对被考虑像素的值进行显式编码；并且

其中，如果被转义编码的像素的数量超过当前像素块的预定义阈值，则中止对当前像素块的使用调色板编码模式的编码的评估。

由于该提供，可以节省处理时间。这是因为大量被转义编码的像素使得调色板编码模式与其他编码模式相比效率非常低。结果，这个大数一被知道，就不值得为了对于当前编码单元的编码而言无用的处理操作浪费时间。

这些实施例的可选特征在所附权利要求中定义。这些特征中的一些在下文中参考方法解释，同时它们可以调换为专门用于根据本发明的实施例的设备的系统特征。

在实施例中，预定义阈值依赖于当前像素块中的像素的数量，例如30％。

在其他实施例中，该过程还包括每次像素被转义编码时递增计数器；其中，计数器一达到预定义阈值，就中止对当前像素块的使用调色板编码模式的编码的评估。该方法对于节省处理时间是最佳的。

在还有的其他的实施例中，对当前像素块的使用调色板编码模式的编码的评估进一步包括：

如果在距离阈值给定的情况下在调色板中没有找到足够接近被考虑像素的调色板条目，则将被考虑像素作为新调色板条目添加到调色板中；

一旦像素块的所有像素都已经被考虑，就从调色板移除至少一个调色板条目。

该提供使得可以动态地构建反映当前编码单元的像素并且满足存储器要求的调色板。

在特定实施例中，对当前像素块的使用调色板编码模式的编码的评估还包括：

当找到调色板条目或添加新的调色板条目时，递增与找到的或新的调色板条目相关联的出现计数器；以及

将被移除的调色板条目的出现计数器的和与预定义阈值进行比较以决定是否中止评估。

本发明的其他创造性的(且独立的)实施例针对一种用于使用调色板编码模式对图像中的当前像素块进行编码的方法，该方法包括：

从当前像素块和当前调色板构建索引块，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

对索引块进行编码，

其中，对当前像素块构建索引块包括：对于当前像素块的每个像素，给定距离阈值，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；将找到的调色板条目的条目索引添加到索引块；并且将当前像素和找到的调色板条目的条目索引存储在存储器中，

其中，如果当前像素的值等于当前像素块中的前面的像素的值，则检索存储在存储器中的用于前面的像素的条目索引，并且将检索的索引添加到预测器索引块作为用于当前像素的条目索引。

对应地，一种用于对图像中的当前像素块进行编码的编码设备包括被配置为执行以下步骤的至少一个微处理器：

从当前像素块和当前调色板构建索引块，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

对索引块进行编码，

其中，对当前像素块构建索引块包括：对于当前像素块的每个像素，给定距离阈值，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；将找到的调色板条目的条目索引添加到索引块；并且将当前像素和找到的调色板条目的条目索引存储在存储器中，

其中，如果当前像素的值等于当前像素块中的前面的像素的值，则检索存储在存储器中的用于前面的像素的条目索引，并且将检索的索引添加到索引块作为用于当前像素的条目索引。

这些创造性实施例使得可以避免在调色板中穷举地搜索索引。平均来说，用于对像素之间的相等性进行测试的附加处理成本小于通过不执行穷举搜索而节省的处理成本，因为图像(特别是屏幕内容图像)通常具有高水平的像素冗余。

尽管“前面的像素”可以是在编码单元中的任何已经处理的像素中，但是为了限制像素比较的量并且限制保存前面的像素所必需的存储器，限制可能的“前面的像素”的数量可能是值得的。在优选实施例中，前面的像素是当前像素块中的当前像素紧邻地前面的像素。换言之，在调色板中找到的最后一个索引被保存在存储器中以供重复用于下一个像素，如果该最后一个索引与被处理的最后一个索引相同的话。在变体中，可以考虑在当前像素紧邻地前面的两个或更多个像素。

注意，优选地，只有一个条目索引和只有一个“前面的”像素在任何时间被存储在存储器中。这减少了对存储器的需要。

在考虑当前像素紧邻地前面的像素的变体中，前面的像素是当前像素块的其调色板条目索引已经被添加到索引块的最后一个像素。该提供使得可以考虑其调色板条目不能被找到因而没有条目索引被添加到层级块的被转义像素。

在另一变体中，前面的像素是当前像素块中位于当前像素上方的像素。

在一些实施例中，该方法还包括：将当前像素的值与存储在存储器中的前面的像素的值进行比较，以确定当前像素的值是否等于前面的像素的值。

注意，通常，最接近的调色板条目(在阈值给定的情况下)被选来提供作为索引块中用于当前像素的索引的对应条目索引。

本发明的其他的创造性的(且独立的)实施例针对一种用于使用调色板编码模式对图像中的当前像素块进行编码的方法，调色板编码模式使用当前调色板，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合，该方法包括：

对当前像素块的使用用于预测当前调色板的两种或更多种调色板预测模式的编码进行评估(或测试，即，估计编码成本以便从被测试的编码模式之中选择最佳编码模式)，其中，第一调色板预测模式使用图像中的前面的像素块的前面的调色板、而不是当前调色板来对当前像素块进行编码；

该方法还包括：

确定前面的调色板的在当前调色板中重复使用的调色板条目的量；以及

如果确定重复使用的调色板条目的量低于预定义阈值，则跳过对当前像素块的使用第一调色板预测模式的编码的评估。

对应地，一种用于使用调色板编码模式对图像中的当前像素块进行编码的编码设备，调色板编码模式使用当前调色板，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合，该编码设备包括被配置为执行以下步骤的至少一个微处理器：

对当前像素块的使用用于预测当前调色板的两种或更多种调色板预测模式的编码进行评估，其中，第一调色板预测模式使用图像中的前面的像素块的前面的调色板、而不是当前调色板来对当前像素块进行编码；

确定前面的调色板的在当前调色板中重复使用的调色板条目的量；以及

如果确定重复使用的调色板条目的量低于预定义阈值，则跳过对当前像素块的使用第一调色板预测模式的编码的评估。

该方法使得可以容易地检测调色板共享评估无效的情况，因而尽可能早地跳过它。

本发明的另一方面涉及一种存储程序的非暂时性计算机可读介质，该程序当被设备中的微处理器或计算机系统执行时使该设备执行如上定义的任何方法。

非暂时性计算机可读介质可以具有与在上面和下面关于该方法和设备陈述的那些特征和优点类似的特征和优点，特别是改进调色板编码模式的编码效率的特征和优点。

本发明的又一方面涉及一种包括适于执行如上定义的任何方法的每个步骤的部件的设备。

本发明的还有的其他的方面涉及一种基本上如本文中参考附图的图17或图18或图19或图20或图21描述的并且如这些图所示的对图像中的当前像素块进行编码或解码的方法。

根据本发明的方法的至少部分可以是计算机实现的。从而，本发明可以采取以下形式：完全硬件实施例、完全软件实施例(包括固件、驻留软件、微码等)或组合软件方面和硬件方面的实施例，这些实施例在本文中全都可以统称为“电路”、“模块”或“系统”。此外，本发明可以采取计算机程序产品的形式，该计算机程序产品实现在任何有形的其中包含有计算机可用程序代码的表达介质中。

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

附图说明

现在将参考以下附图、仅以举例的方式描述本发明的实施例，在附图中：

图1示出HEVC编码器架构；

图2示出HEVC解码器架构；

图3示出因果区域的概念；

图4示出HEVC范围和屏幕内容编码扩展所支持的色度格式；

图5示出编码单元中的编码树块划分以及这些编码单元的扫描次序解码；

图6示出HEVC的屏幕内容编码扩展中的被调查的在解码器端的调色板编码模式的原理；

图7示出解码器端的调色板编码模式的不涉及残差的变体；

图8示出编码单元以及它的对应层级(level)块和相关联的调色板的示例；

图9示出相同的层级块以及用于该层级块的编码的语法元素集合；

图10示出与调色板模式相关的语法元素的解码过程；

图11示出在解码端构建层级块的重构过程；

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

图13示出编码器处用于调色板模式的Pred mode、Level和Run语法元素以及转义编码模式的选择；

图14是用于实现本发明的一个或多个实施例的计算设备的示意性框图；

图15示出对“Run”语法元素进行编码的算法；

图16示出对“Run”元素进行编码的另一算法；

图17示出与图15相比的对“Run”语法元素进行编码的改进算法；

图18示出与图16相比的对“Run”语法元素进行编码的改进算法；

图19示出使用调色板编码模式将编码单元转换为层级块的改进算法，包括标示被转义编码的像素；

图20示出为调色板编码模式构建调色板的改进算法；以及

图21示出对调色板编码模式进行评估的改进算法。

具体实施方式

图1示出HEVC编码器架构。在视频编码器中，将原始序列101划分为像素块102。然后对每个块运用(affect)编码模式。存在HEVC中通常使用的两族编码模式：基于空间预测的模式(帧内模式)103和基于时间预测的模式(帧间、Bidir、Skip模式)，时间预测基于运动估计104和运动补偿105。当前设计的被称为HEVC屏幕内容编码扩展的HEVC的扩展增加了附加编码模式，即，与帧内和帧间编码模式竞争以对像素块进行编码的调色板编码模式。下面特别是参考图6至图13、图15和图16更详细地描述该调色板编码模式。

帧内编码单元通常是通过被称为帧内预测的过程根据在其因果边界(causalboundary)处的已编码像素预测的。

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

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

在帧内预测中，对预测方向进行编码。在时间预测中，对至少一个运动矢量进行编码。但是，为了进一步降低与运动矢量编码相关的比特率成本，运动矢量不被直接编码。实际上，假定运动是均匀的(homogeneous)，特别有趣的是将运动矢量编码为该运动矢量和其周围的运动矢量之间的差值。在例如H.264/AVC编码标准中，相对于在位于当前块的上方和左侧的三个块之间计算的中值矢量(median vector)来对运动矢量进行编码。只有在中值矢量和当前块运动矢量之间计算的差值被编码在比特流中，该差值也被称为残差运动矢量。这在模块“Mv预测和编码”117中被处理。每个已编码矢量的值被存储在运动矢量场118中。用于预测的相邻的运动矢量从运动矢量场118提取。

然后，在模块106中(例如通过使用基于Lambda的标准(诸如D+λ.R，其中D是失真，λ是Lambda或Lagrangian系数，R是速率(rate)))选择对率失真性能进行优化的模式。为了进一步降低冗余度，在模块107中将变换(通常是DCT)应用于残差块，并且在模块108中将量化应用于系数。然后在模块109中对量化的系数块进行熵编码，并且将结果插入在比特流110中。

然后编码器进行已编码的帧的解码以用于在模块111至116中的将来的运动估计。这是编码器处的解码循环。这些步骤使得编码器和解码器可以具有相同的参考帧。为了重构编码的帧，在模块111中对残差进行反量化，并且在模块112中进行反变换，以便提供像素域中的“重构”残差。根据编码模式(帧间或帧内)，将该残差添加到帧间预测器114或帧内预测器113。

然后，在模块115中通过一种或几种后置(post)滤波对这个第一重构进行滤波。这些后置滤波器集成在解码循环中。这意味着它们需要在编码器和解码器处应用于重构的帧以便在编码器和解码器处使用相同的参考帧。该后置滤波的目的是移除压缩伪影。

例如，H.264/AVC使用去块滤波器。该滤波器可以移除由于残差的DCT量化以及块运动补偿而导致的成块伪像。在当前的HEVC标准中，使用两种类型的环路滤波器(loopfilter)：去块滤波器、采样自适应偏移(SAO)。

图2中表示了HEVC解码器的原理。首先在模块202中对视频流201进行熵解码。然后在模块203中对残差数据进行反量化，并且在模块204中进行反变换，以获得形成残差的像素值。模式数据也被熵解码，并且根据模式进行帧内类型的解码或帧间类型的解码。在帧内模式的情况下，从比特流解码帧内预测方向。然后使用预测方向来定位参考区域205。如果模式是帧间，则从比特流解码运动信息202。这由参考帧索引和运动矢量残差构成。将运动矢量预测器添加到运动矢量残差以获得运动矢量210。然后使用运动矢量定位参考帧中的参考区域206。将参考区域添加到残差以重构解码的帧。注意，使用解码的运动矢量更新运动矢量场(field)数据211以便用来预测下一个解码的运动矢量。然后利用与在编码器端使用的后置滤波器完全相同的后置滤波器对解码的帧的这个第一重构进行后置滤波207。解码器的输出是解压缩的视频209。

图3示出从如HEVC中的逐块编码得到的因果原理。

在高层级处，图像被划分为按光栅扫描次序编码的编码单元。因而，当对块3.1进行编码时，区域3.3的所有块都已经被编码，并且可以被认为对于编码器是可用的。类似地，当在解码器处对块3.1进行解码时，区域3.3的所有块都已经被解码，因而被重构，并且可以被认为在解码器处是可用的。区域3.3被称为编码单元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 RExt的HEVC范围扩展是处理扩展视频格式的新视频编码标准HEVC的扩展。

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

对三个颜色分量使用不同的采样比是非常常见的。子采样(subsampling)方案常被表达为三部分比J:a:b(例如，4:2:2)，该三部分比J:a:b描述J个像素宽、2个像素高的概念区域中的亮度采样和色度采样的数量。所述部分是(按它们各自的次序)：

J：水平采样参考(概念区域的宽度)(通常为4)。

a：第一行J个像素中的色度采样(Cr、Cb)的数量。

b：第二行J个像素中的(附加)色度采样(Cr、Cb)的数量。

图4示出HEVC RExt中的被考虑的不同色度格式。这些格式由于三个颜色分量的不同图片大小以及颜色分量的不同类型而是不同的。

在4:2:0YUV色度格式中，如果Y分量区域具有等于W个像素的宽度以及等于H个像素的高度，则U分量区域和V分量区域都具有等于W/2个像素的宽度以及等于H/2个像素的高度。

在4:2:2YUV色度格式中，如果Y分量区域具有等于W个像素的宽度以及等于H个像素的高度，则U分量区域和V分量区域都具有等于W/2个像素的宽度以及等于H个像素的高度。

在4:4:4YUV或RGB色度格式中，三个颜色分量的区域具有相同的宽度W和高度H。

当图片是单色时，其格式被称为4:0:0。

关于作为用于对像素的每个颜色分量进行编码的位的数量的位深，如果当前HEVC标准能够处理具有8位和10位位深(即，256至1,024个可能的颜色)的4:2:0颜色格式，则HEVC RExt将被设计为另外支持4:2:2和4:4:4视频格式，其中这些视频格式具有从8位直到16位的范围的扩展位深(即，多达65,536个可能的颜色)。这对于具有更大动态范围的颜色分量是特别有用的。

HEVC RExt还被设计为提供输入序列的无损编码；这是将使解码的输出209与输入101严格相同。为了实现这一点，与传统的HEVC有损编解码器相比，若干个工具已经被修改或添加。这里在下面提供对无损操作的示例性修改或添加的非穷举列表：

-移除量化步骤108(在解码器处为203)；

-强迫激活旁路(bypass)变换，因为正常的余弦/正弦变换107可能引入误差(在解码器处为204)；

-移除特别针对补偿量化噪声而定制(tailor)的工具，诸如后置滤波115(在解码器处为207)。

在被考虑用于标准化的被称为HEVC的屏幕内容编码(SCC)的新扩展中，附加工具当前被设计为除了自然序列之外还高效地对“屏幕内容”视频序列进行编码。“屏幕内容”视频序列是指具有非常特定的内容的特别的视频序列，其对应于从个人计算机或任何其它设备捕获的包含例如文本、PowerPoint呈现、图形用户界面、表格(例如，截屏)的那些视频序列。通常为4:4:4格式的这些特别的视频序列具有与自然视频序列相比相当不同的统计特性。在视频编码中，当对这样的“屏幕内容”序列进行处理时，常规的视频编码工具(包括HEVC)的性能有时证明是平庸的。

HEVC SCC中当前所讨论的对“屏幕内容”视频序列进行处理的工具包括帧内块拷贝模式和调色板模式。这些模式的原型已经显示出与以自然视频序列为目标的常规方法相比良好的编码效率。在本文件中聚焦于调色板编码模式。

HEVC SCC的调色板模式的实现是基于预测。它可以无差别地应用于任何其他无损或有损编码方法。这意味着调色板方法用于类似于通过运动预测(帧间情况)或帧内预测进行的预测那样构建用于对给定编码单元进行编码的预测器。在生成预测器之后，对残差编码单元进行变换、量化和编码。换言之，与上面参考图1和图2描述的相同的过程适用。

在下面参考图7描述的另一实现中，用调色板模式构建的块被直接编码在比特流中，而不包含任何残差。

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

在编码器端，在SCC中被考虑的调色板模式在于将给定的输入的编码单元的像素值变换为索引，这些索引被称为标识相关联的调色板中的条目的层级。在变换之后，所得的编码单元或索引块由层级组成，然后与相关联的调色板一起被发送到解码器，调色板通常是具有用于表示编码单元的有限数量的颜色三元组的表格。由于调色板定义有限数量的颜色，所以到索引块的变换通常近似于原始的输入编码单元。

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

-例如通过最小化总体失真来找到最好地描述待编码的像素的编码单元的P个三元组；

-然后将P个三元组之中的最接近的颜色与编码单元的每个像素相关联：待编码的值(或层级)则是与相关联的最接近的颜色的条目相对应的索引。

-另外，如果当前处理的像素值远离调色板的任何条目，则不使用调色板可能是值得的。在这样的情形下，SCC提供像素的转义编码，这意味着在应用量化步骤之后将其像素值(被转义编码的像素)显式编码在比特流中。

对于每个编码单元，调色板(即，找到的P个三元组)、索引块或层级块、被转义编码的像素(存储在“被转义像素”块中)、以及可选地还有表示原始编码单元和颜色空间中的索引块(其是块预测器)之间的差值的残差被编码在比特流110中，并且被发送到解码器。

在解码器处，调色板模式在于以相反的方式操作转换。这意味着与编码单元的每个像素相关联的每个解码的索引被调色板的对应颜色或被从比特流解码的被转义像素值(其取决于转义编码是否已经被应用)替换，以便生成编码单元的每个像素的对应颜色。这是在解码器处在颜色空间中的索引块的构建。

图6进一步示出解码器处的调色板编码模式的第一实现的原理。在步骤602从比特流601提取用于当前编码单元的编码模式。当前，调色板模式由比特流中位于跳过(skip)标志之前的标志来标识(其他编码模式已经在上面参考图1和图2进行描述)。该标志是使用单个上下文进行CABAC编码的。如果该模式是调色板模式603，则从比特流601提取并解码604调色板模式605的相关语法，即关于调色板、层级块、被转义像素块、可选地还有残差的信息。

然后，在步骤606期间，从解码的数据构建两个元素：调色板607和层级块608。从该层级块和相关联的调色板，构建609像素域中的编码单元预测器610。这意味着对于层级块的每个层级，颜色(RGB或YUV)与每个像素相关联。

然后，从比特流601对编码单元残差进行解码611。在调色板模式的当前实现中，使用常见的HEVC帧间残差编码方法(即，使用Golomb编码)来对与调色板模式相关联的残差进行编码。为了获得编码单元的残差612，进行传统的反量化和反变换。块预测器610被添加613到该编码单元残差612以便形成重构的编码单元614。

现在参考图7来描述图6的调色板模式预测的HEVC SCC变体，其中，701至708大部分类似于601至608。

在该变体中，本身不存在残差和预测，这意味着只有可以由调色板适当地表示的像素才使用调色板模式的对应条目编码。

在该特定上下文下，不能由调色板适当地表示的像素被不同地编码，而不参考调色板的颜色条目。代替使用调色板的条目，显式地发送量化的像素值。如以上所提到的，这样的像素被称为“被转义值”或“被转义编码的像素”。该转义模式提供在不使用任何调色板条目来标示该像素并因而不浪费调色板条目(调色板的大小可能是有限的)的情况下对非常不频繁的像素进行处理的高效方式。

当像素被编码为被转义值时，如下所述的转义标志被设置为预定值，以使得解码器可以识别编码单元的哪些像素被转义编码以及同一个编码单元的哪些像素使用调色板条目编码。

标示像素的示例是在“Pred mode”元素之前添加“escape”标志，该标志指示像素是被调色板编码(使用来自调色板条目的层级编码)、还是被转义编码(因此具有显式像素值)。“escape”标志后面跟着显式像素值(对于该像素，不提供“Pred mode”、“Level”和“Run”元素)。

在变体中，“escape”信息可以使用索引块中的特定层级值(专用于“被转义编码”像素)来标示哪个像素是“被转义编码的”像素。

在任何实施例中，显式像素值可以被预测地编码(例如，作为与相邻像素值的差值)或者可以不被预测地编码，可以使用可变长度编码进行编码或者可以不使用可变长度编码进行编码，并且可以被量化或者可以不被量化，这对熵编码可能有影响(上下文和位数等)。

与图6相比，几个步骤被修改。

因为语法由于不对残差进行编码而稍有改变，所以步骤704提取与605相比不同的特定语法705。这是因为在图7的调色板模式下只有当像素值用调色板条目适当表示时才使用调色板模式对这些像素值进行编码。否则，即，如果不能使用调色板模式对像素值进行编码(例如因为它不能用调色板条目适当表示，或者调色板已经达到其最大大小并且没有新的值可以被添加)，则该像素值被编码为被转义值。

在步骤706，类似于图6中的步骤606，从解码的数据构建三个元素：调色板707、层级块708以及被转义像素值块。基于所有这些数据，解码器能够生成709当前编码单元714，特别是通过如下方式来生成：即通过对非被转义像素使用调色板并且从已编码的显式像素值解码被转义像素值来重新生成编码单元的像素值。

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

如关于图6和图7所提及的，对于每个编码单元，调色板(以及残差，仅对于图6)被编码和插入在比特流中。以相同的方式，层级块或索引块被编码和插入到比特流中，并且其编码的示例在下面参考图9给出。在该示例中，层级块是按光栅扫描次序处理的。

层级块91与图8中参考802所示的层级块完全相同。表92和表93描述用于对层级块91进行编码的连续的语法元素。表93应被读为表92的继续。该表中的语法元素对应于块91中的被粗线包围的层级组的编码。

层级块被用一组连续的像素按光栅扫描次序编码。通过使用给出预测方向(即，用于重构组的索引的预测或重构模式)的第一语法元素、给出一个像素或多个像素的值(即，层级)的可选的第二语法元素、给出重复的第三语法元素来编码每个组。该重复对应于组中的像素的数量。

这两个表描绘了与调色板模式相关联的当前语法。这些语法元素对应于比特流中的与层级块91相关联的编码信息。在这些表中，三个主要语法元素被用来充分地表示调色板模式的操作，并且当连续地考虑层级块91的层级时被如下使用。

被称为“Pred mode”的第一语法元素使得两种编码模式可以被区分开。在与“Predmode”标志等于“0”相对应的第一模式下，新层级被用于当前像素。该层级在比特流中在该标志之后被立即标示。在与“Pred mode”标志等于“1”相对应的第二模式下，使用“向上拷贝”模式。更具体地，这意味着当前像素层级对应于位于按照光栅扫描次序在相同位置上开始的、紧邻的上方的行处的像素层级。在“Pred mode”标志等于“1”的情况下，不需要在标志之后立即标示层级，因为通过参考层级块91中的正上方的像素的层级的值就知道层级的值。

被称为“Level”的第二语法元素指示仅在“Pred mode”的第一模式下的用于当前像素的调色板的层级值。

被称为“Run”的第三语法元素用于在“Pred mode”的两种模式下对重复值进行编码。考虑层级块91从左上角到右下角逐行地从左到右、从上到下被扫描，Run语法元素给出块91中的具有相同编码的连续像素的数量，即，索引组中的应用当前语法元素的索引的数量。

该“Run”语法元素具有不同的意义，这依赖于“pred mode”标志。当Pred mode为0时，“Run”元素是块的具有相同层级值的连续像素的数量。例如，如果Run＝8，则这意味着当前“Level”应用于当前像素以及后面跟着的8个像素，这些像素与按光栅扫描次序的9个相同的连续采样相对应。

当Pred mode为1时，“Run”元素是块的如下的连续像素的数量，这些连续像素具有与块91中的、它们上方的像素的层级值相对应的层级值(即其中应用“向上拷贝”模式)。例如，如果Run＝31，则这意味着当前像素以及后面跟着的31个像素(这些像素对应于总共32个像素)的层级是从上一行的像素拷贝得到的。

关于表92和93，它们表示使用调色板模式对块91进行编码的八个步骤。每个步骤从对“Pred mode”标志进行编码开始，当“Pred mode”标志等于“0”时，“Pred mode”标志后面是“Level”语法元素，或者当“Pred mode”标志等于“1”时，“Pred mode”标志后面跟着“Run”语法元素。“Level”语法元素后面总是跟着“Run”语法元素。

当对当前块进行解码的编码模式是调色板模式时，解码器首先对与该块相关的语法进行解码，然后对编码单元应用重构过程。

图10示出与调色板模式相关的语法元素的解码过程(上面的步骤605-606或705-706)。首先，从比特流1001提取并解码1002调色板的大小。通过对在步骤1002解码的该大小值加1来获得调色板的准确大小(Palette_size)。实际上，该大小是通过使用值0具有最少位数(1位)的一元码进行编码的，并且调色板的大小不能等于0，否则没有像素值可以用于构建块预测器。

然后，与调色板值解码相对应的过程开始。在步骤1004，将与调色板的索引相对应的变量i设置为等于0，接下来，在步骤1005进行测试以检查i是否等于调色板大小(Palette_size)。如果情况并非如此，则从比特流1001提取一个调色板元素，并且对该调色板元素进行解码1006，然后将该调色板元素与相关联的等于i的层级/索引一起添加到调色板。然后，通过步骤1007递增变量i。如果i等于调色板大小1005，则调色板已经被完全解码。

接下来，进行与层级块91的解码相对应的过程。首先，将与像素计数器相对应的变量j以及变量syntax_i设置为0，1008。然后，进行检查以知道像素计数器是否对应于块中所包含的像素的数量(该数量是已知的，因为解码器知道编码树块分解为编码单元的分解——参见图5)。如果在步骤1009回答为“是”，则该过程在步骤1017结束，否则从比特流1001提取与一种预测模式相对应的标志“Pred mode”的值并且对该值进行解码1010。

“Pred mode”的值在索引syntax_i处被添加到包含所有已解码的“Pred mode”值的表。如果在步骤1011，该“Pred mode”的值等于0，则从比特流1001提取与“Level”相对应的语法元素，并且对该语法元素进行解码1012。该变量“Level”在索引syntax_i处被添加到包含所有已解码的层级的表。与像素计数器相对应的变量j递增1，1013。

接下来，在步骤1014，对“Run”语法元素进行解码。如果在步骤1011，语法元素“Pred mode”等于1，则“Run”值也在步骤1014被解码。该语法元素“Run”在索引syntax_i处被添加到包含所有的解码的游程表。

接下来，在步骤1015，将值j增加在步骤1014解码的Run的值。变量syntax_i被递增1以考虑下一个语法元素集合。如果计数器j等于块中的像素的数量(即，用于当前编码单元的最后一个语法元素集合已经被处理)，则完成1017构建层级块91的语法。在与调色板相关的该过程结束时，解码器知道调色板以及包含与该编码单元的调色板模式相关联的所有的“Pred mode”、“Level”和“Run”语法元素的列表的表。然后解码器可以继续进行如通过图6或图7描述的编码单元的重构过程。

这里提醒的是，索引块中的特定索引值(这些索引对应于不具有与该索引相关联的像素值的调色板条目)可以用于标记被转义编码的像素，并且显式的转义编码值是从比特流提取的。

出于例示的目的，下面给出可以与每个语法元素相关联的码字。当然，其他码字可以用于获得更好的编码效率。

在上面的示例中由三个值(YUV或RGB)构成的每个调色板元素通常是使用三个二进制码编码的(在步骤1016解码)。二进制码的长度对应于每个颜色分量的位深(8位表示256个值)。

在步骤1002解码的调色板大小通常是使用一元码编码的。

“Pred mode”元素是使用一位编码的。

“Level”元素是使用二进制码或截短二进制码编码的。

在本发明的实施例中，“Run”元素是使用可变长度码编码的。例如，Run元素的一些值是使用短码字编码的，其他值是使用由公共码字前缀以及从一个其他码字到另一个码字不同的码字后缀组成的其他码字编码的。

下表给出了用于Run元素的码字的示例。

图15示出根据该表对“Run”元素进行编码的算法，在该表中，用于对“Run”值进行编码的码字依赖于所述值。

在该示例中，Run元素的三个第一可能值，即，0、1和2，是使用短码字编码的(当然，更多的或更少的第一可能值可以被短编码值涉及)，Run元素的其他(后面的)可能值是使用由公共码字前缀以及从一个其他可能码字到另一个码字不同的码字后缀组成的其他码字编码的。

码字的这个设计对在调色板模式下通常是非常频繁的、Run元素的三个第一值(0、1和2)给予优先级。作为结果，Run元素的其他的高值使用相当长的码字。

如图所示，在步骤1501进行第一次检查，在该检查中，将值与0进行比较。如果值等于0，则在步骤1502生成码字“0”，并且当前Run元素的编码在步骤1509结束。

如果步骤1501的答案是否定的，则在步骤1503进行第二次测试以知道Run值是否等于1。如果响应是肯定的，则在步骤1504生成码字“10”，并且下一步是1509。

如果Run值不等于1，则在步骤1505进行进一步的测试，在该测试中，将Run值与2进行比较。如果Run值等于2，则在步骤1506生成码字“110”，并且下一步是1509。

如果步骤1505的响应是否定的，则生成前缀码“111”，并且在步骤1508使用阶数3的截短Rice码(其中，待编码的符号是Run元素的值减3)来对Run值的值进行编码。步骤1508然后跟着步骤1509，步骤1509完成Run值的编码。

可以注意到，码字(任一短码字“0”、“10”、“110”以及前缀+后缀码字“111x…x”)可以被直接插入到比特流中，或者可以通过使用像CABAC的算术熵编码器被编码以减小与Run值的编码相关的信息的最终大小。

图16示出对“Run”元素进行编码的另一算法，该算法仅对Run值0提供短码字，因而包括比图15少的步骤。

该过程开始于步骤1601，在步骤1601期间，将Run值与0进行比较。如果回答是肯定的，则在步骤1602生成码字“0”，并且当前Run元素的编码在步骤1605结束。

如果步骤1601的回答是否定的(Run值不同于0)，则在步骤1603生成码字“1”以形成对于所有不同于“0”的Run值共同的前缀码“1”。接下来，在步骤1604，使用k阶截短Exp-Golomb码来对Run值进行编码，在k阶截短Exp-Golomb码中，待编码的符号是Run元素的值减1，并且阶数k是通过考虑编码单元的大小以及当前Run元素的当前扫描位置而计算的。接下来，当前Run元素的编码在步骤1605结束。

图11示出构建层级块91、然后颜色空间中的对应块(该块将用作用于调色板模式的第一实现的预测器，或者该块是用于调色板模式的另一实现的已解码的当前编码单元)的重构过程。该过程的输入数据是在上面图10的过程中获得的并且包含“Pred mode”、“Level”和“Run”的列表的表格。附加输入数据是编码单元801的大小(其与层级块802/91的大小相同)，编码单元801的大小从比特流中标示的四叉树(图5)知道。

在第一步骤1101中，将表示像素计数器的变量i设置为等于0，并且将连续地考虑每个语法元素集合的变量j也设置为等于0。在步骤1104，对照0检查从“Pred mode”表在索引j处提取的元素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。如果在步骤1108k＝Run[j]，则结束左层级值的传播，并且执行步骤1120(下面描述)。

如果在步骤1104Pred_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/CU 801中的像素的量。如果不等于，则在步骤1121将变量j递增1以考虑下一个语法元素集合，并且该过程循环回到上述步骤1104。

如果在步骤1120所有像素都已经被处理，则在步骤1122获得最终的层级块91；这对应于表Block[]。然后，最后的步骤1123(例如对应于步骤709)在于使用调色板803对颜色值中的每个层级进行转换，调色板803使用图10的过程进行解码。该最后的步骤根据块中每个块位置的层级以及调色板中的对应条目来运用(affect)该位置处的像素值(Y、U、V)或(R、G、B)。

注意，在步骤1123期间，被转义像素被转换为它们的准确像素值。可以使用层级表的特定值来标示转义模式。例如，如果调色板包含32个元素，则最后一个值(31)可以用于标示转义模式，并且没有调色板条目与该特定值相关联，这意味着转义像素在层级块中是使用与调色板中的像素值不关联的值(最后一个值)定义的。

因而，为了识别被转义像素，步骤1123将Block[j]与被分配用于标示被转义像素的特定值进行比较。对于这些被转义像素中的每个，步骤1123从被转义像素的编码单元710检索对应的准确像素值。

在实施例中，可以使用特定层级值来标示转义模式，该值后面跟着定义像素的准确值的三个颜色分量值。

另外，如果被转义像素在编码器处被量化，则在步骤1123执行反量化步骤。

如HEVC SCC中介绍的调色板模式的其他方面涉及编码器对要用于对当前编码单元进行编码的调色板的确定(参见下面的图12)以及编码器处的Pred mode、Level和Run语法元素的选择(参见下面的图13)。

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

在第一步骤1201，将表示像素计数器的变量j设置为0，将当调色板被构建时跟随调色板增长的变量“Palette_size”也设置为0，并且表示阈值的变量“TH”被定义，例如对于有损编码设置为9，或者在无损编码的情况下设置为0。实际上，在无损编码中，完全跳过量化，并且将QP人为地设置为例如0。该无损性质可以在CU层级定义(语法元素cu_transquant_bypass_flag存在，并且如果图片参数集层级(Picture Paremeter Set-level(PPS-level))处的语法元素transquant_bypass_enabled_flag被设置为1，则语法元素cu_transquant_bypass_flag被设置为1)。

在任何情况下，应该提醒的是，如果编码单元CU被无损编码，则将误差限值设置为0，因为这里的目标是保证层级在没有任何不匹配的情况下表示像素。然后在步骤1203，从原始编码单元1204读取像素p_i，即，具有根据扫描次序的索引i的像素。然后，在1205，将变量j设置为等于0，并且在步骤1206，进行检查以确定调色板大小是否等于变量“j”(这意味着在构造中的调色板的所有调色板元素都已经被考虑)。

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

PAL_Y[j]＝(Yi)

PAL_U[j]＝(Ui)

PALV[j]＝(Vi)

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

在步骤1210，将调色板大小(Palette_size)递增1，并且在步骤1211，将出现表格计数器设置为等于1。然后在步骤1213将变量i递增1以考虑当前编码单元的下一个像素“i”。然后在步骤1214进行检查以确定当前编码单元的所有像素是否都已经被处理。如果它们都已经被处理，则通过稍后解释的排序步骤1215完成该过程，否则在上述步骤1203考虑下一个像素。

由步骤1203至1206和1209至1211组成的处理分支迭代地考虑块的每个像素，以便在每次被考虑像素离已经在被构造的调色板中的所有一个元素或多个元素太远时(测试1207)，将具有被考虑像素的值的新元素添加到调色板。

回到步骤1206，如果j不同于palette_size，则执行步骤1207，在步骤1207，对于每个颜色分量计算p_i和索引j处的调色板元素之间的差值的绝对值。公式如图所示。如果所有的绝对差值都严格小于预定义阈值TH，则在步骤1212将关于调色板中的元素“j”的出现计数器递增1。步骤1207为被构造的调色板的每个元素创建类，在容限TH给定的情况下，这样的类包含与该元素的颜色相邻的颜色。因而，步骤1212对每个类的出现进行计数。步骤1212后面跟着已经描述的步骤1213。

由步骤1203至1207和1212组成的处理分支迭代地考虑块的每个像素以递增与足够接近被考虑像素的调色板元素相关联的计数器。

如果不满足步骤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 mode、Level和Run语法元素的选择，图13的过程的输入数据是像素的原始编码单元、通过图12的过程构建的调色板以及编码单元大小。具体地说，当确定在帧内编码、帧间编码和调色板之间哪种编码模式必须被使用时进行该评估。

在第一步骤1301，将表示像素计数器的变量“i”设置为0。下述过程力图确定用于从i开始的像素的语法元素。独立地评估两种预测模式：图的右手部分的“Pred mode”＝0以及图的左手部分的“Pred mode”＝1。

然而，如果这些预测模式失败，则使用上面介绍的转义模式来对一个或几个像素值进行显式编码。

对于“向上拷贝”预测(对应于“Pred mode”＝1)，在步骤1303将用于对当前Run中的层级数量进行计数的变量“i_copy”设置为等于0。然后在步骤1304，将像素位置i+i_copy处的当前层级：Block[i+i_copy]与上一行中的位于正上方的像素的层级：Block[i+i_copy-width]进行比较，其中，“width”对应于当前编码单元的宽度。

注意，在步骤1308，并行地确定编码单元的每个像素的层级Block[i+i_copy]。该步骤在于将如上面已经解释的最接近的调色板元素(在实践中，其索引或层级)与位置i+i_copy处的像素相关联。在变体中，该步骤可以在于选择与位置i处的像素的距离低于预定义阈值的第一个调色板元素。该步骤使用位置i、调色板1306以及原始编码单元1307。

但是，如果当前像素值“远”离调色板的任何条目，则执行步骤1350以标示对该像素激活转义模式。当例如像素的颜色分量值和调色板中最接近的条目之间的差值超过给定阈值时，使用转义模式。步骤1350之后，在循环到步骤1319之前，在步骤1351将像素计数器i递增1。

在微小的变体中，步骤1350在步骤1308的内部以将上面定义的特定层级值赋给被转义像素，并且步骤1351被删除。该方法使得可以使用“向上拷贝”和“左值”预测模式来高效地对用于标示被转义像素的特定值的出现进行编码。

如果在步骤1304处Block[i+i_copy]＝Block[i+i_copy-width]，则在步骤1305将变量“i_copy”递增1以考虑像素块的下一个像素值并且指示位置i+i_copy处的当前像素值可以包括在当前“向上拷贝”游程中。如果在步骤1304，Block[i+i_copy]不同于Block[i+i_copy-width](这意味着“向上拷贝”游程的当前评估已经结束)则将变量“i_copy”发送到决策模块1314。在该过程的这个阶段，变量“i_copy”对应于从正上方一行拷贝的值的数量。

对于左值预测(对应于“Pred mode”＝0)，并行地或顺序地对确定Run值(i_left)的循环进行处理。首先，将用于存储当前像素的索引i的变量“i_Start”设置为“i”，并且将用于连续地考虑索引“i”后面的像素层级的变量“j”也设置为等于“i”，将用于对被构造的当前游程进行计数的变量“i_left”设置为等于0。这是步骤1309。接下来，步骤1310在于确定是否j！＝0、“Pred_mode[j-1]”＝0以及Block[j]＝Block[j-1]。Pred_mode[]是编码器用来存储预测模式(或者为1，或者为0，分别用于“向上拷贝”预测和左值预测)的表格。该表格在下述步骤1317随着连续像素被处理而被渐进地填充，并且已经在步骤1301利用例如零值初始化：对于任何k，Pred_mode[k]＝0。

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

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

在已经计算‘左值预测’和‘向上拷贝’模式的最大游程之后，在步骤1314比较变量“i_left”和“i_copy”。这是要确定是否“i_copy”！＝0以及“i_copy”+2是否高于“i_left”。这是选择向上拷贝模式还是左值预测模式的示例性标准。具体地说，用于补偿左值预测模式的层级的速率成本的参数“2”可以稍有改变。具体地说，可以根据调色板的大小(Paletter_size)设定加性参数(在该示例中为2)，因为调色板的大小与层级的成本直接相关。在一个实施例中，移除操作“+2”，以使得步骤1314的比较检查：“icopy！＝0&&icopy>ileft”。该实施例改进编码效率。

步骤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，计算像素块中待考虑的下一个位置，该下一个位置对应于将当前位置i递增“run”值+1。然后，在步骤1319进行检查以确定编码单元的最后的像素是否已经被处理。如果情况如此，则该过程在步骤1320结束，否则在步骤1303和1309开始对下一个像素位置评估两种预测模式“左预测”和“向上拷贝”的评估以获得新的语法元素集合。

在该过程结束时，编码器知道编码单元的每个采样或像素的层级，并且能够基于三个表格Pred_mode[]、Block[]和Run[]的内容来对层级块的对应语法进行编码。

为了确定块预测器，编码器然后使用调色板来转换定义的层级块，并且还使用在1350被标示为被转义像素的像素的列表。

图17和图18示出编码器处的在调色板模式下对Run语法元素进行编码的示例性算法，图17和图18分别具有与图15和图16中相同的表示。所以，输入数据是相同的。

在这些算法示例中，标志(例如通过用于Run元素的“up-to-end”码字)用于指示当前“Run”是最后一个并且适用于直到当前编码单元的末尾的所有的剩余索引，而不管这样的剩余索引的数量如何，即，不指定形成与当前的最后一个语法元素集合相对应的索引组的这些剩余索引的数量。与需要较长码字对用于最后一组的索引的准确数量(至少对于图像的最后的编码单元，该数量通常很大，因为图像的底部通常是均匀的)进行编码的情形相比，该方法使得可以节省一些位。

根据该方法，每个集合中提供的Run语法元素使用从至少两个可用码字选择的码字，该至少两个可用码字包括up-to-end码字，up-to-end码字指示形成对应索引组的索引是直到索引块的末尾的所有的剩余块位置处的索引，而不管这样的剩余块位置的数量如何。up-to-end码字因而可以针对包括编码单元的最后一个集合中的Run元素设置。但是这不是强制的；对于一些编码单元，仍可以实现如上所述的常规方法。

注意，可以提供与常规Run元素分开的up-to-end二进制标志来标示up-to-end方法。但是，这样的二进制标志与用于Run元素的任何常规码字组合形成嵌入的Run元素的码字。这是本描述集中于用于Run元素的可能的码字的原因。

图17和图18通过用于对Run值进行编码的码字来彼此区分。如这些图所示，用于当前编码单元的最后一个集合中的Run语法元素使用up-to-end码字来标示对当前语法元素集合启用“up-to-end”选项。

在图17的实施例中，步骤1701至1707与图15的对应步骤(步骤1501至1507)是相同的，因而不再进行描述。

在步骤1707生成码字“111”(在该过程的这个位置，将被编码的Run值优于2)之后，步骤1708在于确定当前Run是否是用于当前编码单元的最后一个(即，当前语法元素集合是否是最后一个)。最后一个Run意味着在该最后一个Run的编码之后没有其他的操作(“向上拷贝”或“左值”)将要对当前编码单元执行，因为该过程到达编码单元的最后一个像素(事实上是层级块的最后一个索引)。

例如，最后一个Run可以在图13的过程期间当测试1319是肯定的时被检测到。在这样的情况下，在步骤1317存储在存储器中的最后一个Run是当前编码单元的最后一个。

如果当前Run是最后一个，则本实施例的构思是通过在步骤1710将标志“1”编码在比特流中以指示最后一个Run正在被处理来避免标示Run的值(该值通常高，因而可能导致相当长的码字)。

如果在步骤1708响应是否定的，则下一步是步骤1709，在步骤1709，将表示当前Run不是最后一个的标志“0”编码在比特流中。接下来，在步骤1711对Run减3的值进行编码，类似于步骤1508。

在该配置中，用于Run元素的高值的公共码字前缀(从步骤1707与步骤1709组合得到的“111”)被用来形成up-to-end码字。接下来，使up-to-end码字的后缀部分减小到最小，即，减小到一个位(步骤1710)；up-to-end码字包括公共码字前缀，并且除了公共码字前缀之外还包括一位后缀。

注意，也可以通过使用诸如CABAC的算术熵编码器来对步骤1709和1710中描述的“up-to-end”标志进行编码以改进本发明所描述的方法的编码效率。

在图18的实施例中，up-to-end码字也包括用于对“其他”Run值(即，没有短码字的那些)进行编码的公共码字前缀，并且除了公共前缀二进制值之外还包括一位后缀。步骤1801至1803与图16的对应步骤(步骤1601至1607)是相同的，因而不再进行描述。

在步骤1803生成码字“1”(意味着当前Run值不同于0)之后，步骤1804在于确定当前Run是否是当前编码单元的最后一个(类似于步骤1708)。

如果当前Run是最后一个，则本实施例的构思是通过在步骤1805将标志“1”编码在比特流中以指示最后一个Run正在被处理来避免标示Run长度的值(该值通常高，因而可能导致相当长的码字)。

如果在步骤1804响应是否定的，则下一步是步骤1806，在步骤1806，将表示当前Run不是最后一个的标志“0”编码在比特流中。接下来，在步骤1807对Run的值进行编码，类似于步骤1604。

图17和图18示出从编码器的视角的过程。本领域技术人员将直接推断解码器处的对应解码过程。这暗示对来自比特流的位进行解析以获得用于Run元素的码字，或者是与定义的数量的索引相关联的预定义码字，或者是根据本发明的“up-to-end”码字。例如，当“up-to-end”码字在解码过程的步骤1014被检测到时，要被考虑的Run值可以是Pixels_in_Block-j，以便将该过程驱动到结束该过程的步骤1017。

这两个图的示例为Run元素的第一(以及最频繁的)可能值(即，对于图17为0、1和2，对于图18为0)保持优先级。这暗示分别在步骤1707和1803之后提供标示最后一个Run的up-to-end码字。

其他变体可以在步骤1703和1705之间(在这种情况下，up-to-end码字例如是“110”)、或者在步骤1701和1703之间(在这种情况下，up-to-end码字例如是“10”)或者甚至在步骤1701之前(在这种情况下，up-to-end码字例如是“0”)提供步骤1708。类似地，图18的另一变体可以在步骤1801之前提供步骤1804(在这种情况下，up-to-end码字例如是“0”)。在这些变体中，用来标示最后一个Run的Run元素的up-to-end码字是短码字。

步骤1708和1804分别在步骤1701和1801之前的情况可以被认为是“up-to-end”标志与Run元素分开并且被放置在Run元素正前面的实施例。

HEVC SCC的不依赖于上面使用“up-to-end”标志来标示最后一个Run的构思的其他创造性改进没有被描述，但是可以与其组合来改进使用调色板模式的编码的效率。

在上面已经看出，在一些像素不能用任何调色板条目适当表示的情况下，它们被不同地编码(即，“被转义编码”)，并且提供了特定信令来区别当前编码单元中的被转义像素和调色板编码的像素。

转义编码模式的成本是相当高的，因为它需要对显式像素值进行编码，从而需要使用大量位。这对于编码效率可能是不利的。

另外，返回参考图13，编码器对调色板模式的评估要求对于编码单元的每个像素在调色板中找到索引(层级)。这是步骤1308。该步骤的处理成本可以证明是高的。

为了限制这样的缺点，提出了第一创造性改进，以便当被转义像素的数量达到预定义阈值时中止调色板模式的评估。压缩率一变低，用于这样的评估的处理成本因而就大幅度降低(因为每个被转义像素在比特流中需要大量位)。实际上，如果利用调色板模式对当前编码单元进行编码需要大量被转义像素，则存在用于编码单元的并发编码模式(帧内或帧间)将具有更好的率失真折衷、并且然后将被编码器选择的高可能性。

因而，根据第一创造性改进的过程包括：

对当前像素块的、包括调色板编码模式的两种或更多种编码模式中的每种编码模式的编码进行评估，调色板编码模式使用当前调色板来构建索引块，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

基于评估从两种或更多种编码模式选择编码模式以对当前像素块进行编码；

其中，对当前像素块的使用调色板编码模式的编码的评估包括：连续地考虑当前块的像素，并且对于每个被考虑像素：

在给定距离阈值的情况下，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；

如果在给定距离阈值的情况下在调色板中找到足够接近被考虑像素的调色板条目，则使用条目索引对被考虑像素进行编码；

如果在给定距离阈值的情况下在调色板中没有找到足够接近被考虑像素的调色板条目，则对被考虑像素进行转义编码，转义编码包括对被考虑像素的值进行显式编码(即，不对该像素进行预测)；

其中，如果被转义编码的像素的数量超过当前像素块的预定义阈值，则中止对当前像素块的使用调色板编码模式的编码的评估。

提出了第二创造性改进来通过存储被处理的最后一个像素以及对应的调色板层级加速调色板评估，以便有利于由于连续像素之间的冗余度而以低成本重复使用这样的存储信息。用于每个像素的索引的穷举搜索因而可以被避免。

因而，根据第二创造性改进的过程包括：

从当前像素块和当前调色板构建索引块，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合；

对索引块进行编码，

其中，对当前像素块构建索引块包括：对于当前像素块的每个像素，在给定距离阈值的情况下，在调色板中搜索具有足够接近被考虑像素的对应像素值的调色板条目；将找到的调色板条目的条目索引添加到索引块；并且将当前像素和找到的调色板条目的条目索引存储在存储器中，

其中，如果当前像素的值等于当前像素块中的前面的像素的值，则检索存储在存储器中的用于前面的像素的条目索引，并且将检索到的索引作为用于当前像素的条目索引添加到索引块。

当使用调色板编码模式时，可以组合或分开使用第一创造性改进和第二创造性改进。

图19示出对于调色板编码模式的两个创造性改进的组合。知道当前调色板的编码器确定与像素相对应的层级(或索引)。这例如是上述步骤1308。

步骤1909、1910和1914实现第一创造性改进，第一创造性改进在于在太多像素被转义编码的情况下中止调色板编码模式的评估，以便不浪费处理时间。因而只有有限数量的被转义像素被接受用于调色板编码模式。

步骤1920、1921和1922实现第二创造性改进，第二创造性改进在于至少跟踪找到的最后一个索引。在该图的示例中，只有找到的最后一个索引被保存在存储器中，但是同样的处理可以适用于找到的倒数第二个索引，依此类推。

在开始步骤1901，将表示连续地考虑当前编码单元中的每个像素的像素计数器的变量“i”、以及用于对当前编码单元中的被转义像素的数量进行计数的变量“Count”初始化为0。另外，将定义计数阈值的变量“TH”设置为理想地依赖于在步骤108(图1)使用的量化参数QP的值。最后但同样重要的，像素值变量“Last”和索引变量“LIDX”被设置为存储器中的“未定义”值。

接下来在步骤1903，从原始编码单元1904读取当前像素Pi。在步骤1920将当前像素Pi与Last的当前值进行比较以知道当前像素值是否等于被处理的最后一个像素。

如果它们是相同的，则在步骤1921将用于当前像素的索引设置为LIDX，这意味着当前像素具有与被处理的最后一个像素相同的索引。

否则，在步骤1906在调色板中使用传统搜索算法来搜索最佳索引。例如，搜索可以基于找到基于例如最大分量绝对误差、绝对误差和、平方误差和等得到与Pi相比误差最小的索引。

接下来，步骤1907检查与找到的(通过搜索算法或使用LIDX获得的)索引相对应的调色板条目是否充分表示Pi。该检查可以基于上面定义的阈值TH：可以将上面提到的误差(在搜索1906期间计算)与TH进行比较(这意味着如果使用LIDX，检查1907将总是肯定的)。如果误差低于TH，则调色板条目索引被发现是能够表示的。

如果与找到的索引相对应的调色板条目充分表示Pi，则在步骤1911可以对Pi使用找到的索引，即，可以将找到的索引添加到层级块。然后，该过程继续进行步骤1922。

否则，如上面所解释的，在步骤1908对当前像素Pi进行转义编码。这意味着像素Pi被标示为“被转义”，并且其值被显式编码。接下来，在步骤1909递增转义计数Count。

在步骤1909之后，编码器检查转义计数Count是否已经达到太高的值。为了这样做，在步骤1910，将Count与阈值进行比较，该阈值有利地依赖于当前编码单元中的像素的数量。

在实施例中，阈值表示当前编码单元中的像素的数量的百分比，例如10％、20％、25％或30％。

如果它被发现太高，则在步骤1912中止调色板评估：跳过任何进一步的调色板处理(调色板化、游程确定、编码速率评估等)。

如果它未被发现太高，则该过程继续进行步骤1922。

为了使索引搜索加速，下一步1922在于将分别在Last和LIDX中的当前像素值Pi和对应的找到的索引存储在存储器中。

接下来，在步骤1913，递增变量i以考虑当前编码单元的下一个像素“i”。

接下来，在步骤1914进行检查以知道当前编码单元的所有像素是否都已经被处理。如果它们都已经被处理，则整个编码单元已经被“调色板化”，并且该过程在步骤1915结束。否则，在已经描述的步骤1903考虑下一个像素。

在图19的实施例的变体中，当前像素块中位于当前像素上方的像素、而不是如上面定义的“Last”像素可以用于步骤1920和1922。为了这样做，可以对于编码单元的整行(即，在步骤1922期间被填充)将像素和索引之间的关联存储在存储器中。然后，步骤1920可以检索与当前像素上方的像素相对应的关联，如果它存在的话。

图20示出在调色板确定算法期间发生的对于调色板编码模式的两个创造性改进的另一组合。

编码器的输入是当前编码单元及其大小。在该图的示例中，创建YUV调色板。当然，本领域技术人员可以容易地使该示例适于RGB调色板的构建。

该算法非常类似于图19的算法。步骤2003、2004、2006、2007、2013、2014、2020、2021和2022分别类似于步骤1903、1904、1906、1907、1913、1914、1920、1921和1922。步骤2001类似于步骤1901，除了变量“Palette_size”被初始化为0，同时变量Count不再存在。

步骤2016和2018实现第一创造性改进。步骤2020、2012和2022实现第二创造性改进。

为了如图19中进行的那样使索引搜索加速，在步骤2020将当前像素与Last的当前值进行比较。如果它们是相同的，则在步骤2021将用于当前像素的索引设置为LIDX。否则，在步骤2006在调色板中搜索最佳索引。

图20的过程在步骤2007之后不同于图19的过程，在步骤2007，编码器检查与找到的索引相对应的调色板条目是否足够表示Pi。

因为调色板正在被确定(图20的过程属于调色板确定算法)，所以如果步骤2007的检查是否定的，则在步骤2009将当前像素Pi作为新调色板条目添加到调色板。

换言之，如果在给定距离阈值的情况下在调色板中没有找到足够接近像素Pi的调色板条目，则将被考虑像素Pi作为新调色板条目添加到调色板中，并且将对应的条目索引添加到用于被考虑像素的索引块。这意味着新的调色板元素被设置为等于像素值Pi，并且当前像素Pi变为调色板的条目。更确切地，进行以下赋值：

PAL_Y[j]＝(Yi)；PAL_U[j]＝(Ui)；PAL_V[j]＝(Vi)，其中，Yi、Ui、Vi表示Pi的YUV颜色分量。

接下来，在步骤2010将该新调色板条目的出现次数设置为等于1：Counter[Palette_size]＝1。接下来，在继续进行步骤2022之前，在步骤2011将变量Palette_size递增1。

如果索引表示像素(检查2007是肯定的)，则在步骤2002更新确定调色板所需的任何信息。具体地说，递增用于与索引相对应的条目的计数器(Counter[index])。该过程继续进行步骤2022。

在步骤2022，通过更新变量Last和LIDX来将像素值和找到的索引之间的关联存储在存储器中。

接下来，在步骤2013递增变量i以考虑当前编码单元的下一个像素“i”。在步骤2014进行检查以知道当前编码单元的所有像素是否都已经被处理。

如果它们尚未都被处理，则该过程继续进行已经描述的步骤2003。

如果它们都已经被处理，则该过程继续进行对构建的调色板进行后置处理的步骤2015。在该过程的这个时间，表格“Counter”包含每个调色板元素的出现。

后置处理可以考虑它们的出现和统计特性。

后置处理的示例在上面参考步骤1215进行了描述：例如，调色板元素根据它们的出现(Counter[])被排序，以使得最频繁的元素在调色板中的第一位置(具有最低索引或“层级”的条目)中。

接下来，可以保存N个第一调色板元素，并且可以删除其他的调色板元素。例如，如果调色板的大小限于最大大小，例如24个条目，则通过从排序的调色板中的第25个位置移除元素(条目)来减小所构建的具有多于24个条目的调色板。

在步骤2015之后，步骤2016在于确定当前编码单元的将使用调色板编码的像素的数量的估计或者比特流中将被显式编码的像素(被转义编码的像素)的数量的估计，因为它们的对应调色板条目已经在步骤2015被移除。这些估计可以通过对对应的(保存的或移除的)调色板条目的出现值(在Counter[]中)进行求和容易地获得。

步骤2016还在于将针对转义像素获得的估计与预定义阈值(例如，编码单元中的像素的数量的百分比)进行比较。在所获得的估计超过阈值的情况下，太多被转义编码的像素被设想，并且在步骤2018中止调色板模式评估。否则，调色板模式评估在步骤2017正确地结束。

HEVC SCC的另一创造性改进可以通过(如果评估过程不相关的话)再次中止评估过程来节省处理时间。该另一创造性改进可以独立于上述一个或多个创造性改进实现或者与上述一个或多个创造性改进组合实现。

该改进在当前调色板的编码涉及使用调色板预测器对这样的调色板进行预测的上下文下发生。因而，它涉及用于使用调色板编码模式对图像的当前像素块进行处理的方法，调色板编码模式使用当前调色板，当前调色板包括将各个条目索引与对应像素值相关联的条目的集合，该方法包括从至少一个调色板预测器预测当前调色板的步骤。例如，调色板预测器可以是先前用于对图像中的像素块进行处理的一个调色板，其示例在共同未决的申请GB 1403823.6中被描述。

通常，对用于预测当前调色板的两种或更多种调色板预测模式进行评估以确定最佳的一种调色板预测模式。

调色板预测模式在于从先前使用的调色板(即，对于利用调色板编码模式编码的最后一个编码单元)预测当前调色板。从先前使用的调色板重复使用的每个调色板元素/条目被编码器通过指示哪些条目被重复使用的标志的集合在比特流中标示。该调色板预测模式在编码器端被评估，并且被称为正常调色板评估。

另一调色板预测模式在于充分地使用图像中的前面的像素块的前面的调色板作为对当前像素块进行编码的当前调色板。换言之，调色板实际上重复使用先前使用的调色板的所有条目。在这种情况下，标志可以在编码单元层级上被用来指示编码单元重复使用整个先前使用的调色板，在这种情况下，没有显式调色板元素被发送：调色板只是先前被调色板编码的CU中的一个。该调色板预测模式也在编码器端被评估，并且被称为调色板共享评估。

在编码器端连续地运行两种或更多种调色板预测模式可以导致成本非常高的评估。最期望的是检测调色板共享评估无效的情况，并且尽可能早地跳过它。

这是这个第三创造性改进的目的，该创造性改进的示例通过图21利用创造性步骤1802至1808示出。根据该改进，在进行调色板共享评估之前，确定前面的调色板的在当前调色板中重复使用的调色板条目的量。基于该确定，可以跳过调色板共享评估，即，如果确定重复使用的调色板条目的量低于预定义阈值，则跳过对当前像素块的使用第一调色板预测模式的编码的评估。

图21的过程的输入是完全已知的当前调色板。一旦正常调色板评估2101结束，它就可以是当前调色板。

一旦正常调色板评估已经被执行(2101)，其调色板元素就是已知的。在步骤2102检查调色板编码模式是否是当前编码单元的最佳编码模式。

如果不是，则使用调色板共享将改进事情是不太可能的。结果，调色板评估过程在步骤2110结束。

如果是，则通过循环步骤2103至2106对在当前调色板中重复使用的、来自先前调色板的元素的数量进行计数。

通过在步骤2103将表示当前条目索引的变量“i”和表示重复使用的调色板元素的数目的变量“Count”两者都设置为0来对计数循环进行初始化。接下来，步骤2104在于检查来自先前调色板的第i个调色板元素是否被重复使用。如果是，则在步骤2105递增重复使用的元素的数量，并且该过程进入步骤2106。否则，该过程直接进入步骤2106。

步骤2106在于检查第i个调色板元素是否是先前调色板的最后一个元素。如果不是，则通过在循环回到步骤2104之前在步骤2107递增“i”来选择下一个调色板元素。

如果它是先前调色板的最后一个调色板元素，则步骤2108在于评估调色板共享评估是否可以被跳过。

简单的检查可以在于将Count与当前调色板大小进行比较以确保在授权调色板共享评估之前被重复使用的当前调色板元素的最小比率。

如果未达到最小比率(太少元素被重复使用)，则调色板评估在步骤2110结束，而不进行调色板共享评估。后者因而被跳过。

否则(达到最小比率)，在步骤2110结束该过程之前，在步骤2109以传统的方式进行调色板共享评估。

图14是用于实现本发明的一个或多个实施例的计算设备1400的示意性框图。计算设备1400可以是诸如微计算机、工作站或轻便便携设备的设备。计算设备1400包括连接到以下单元的通信总线：

-中央处理单元1401，诸如被表示为CPU的微处理器；

-被表示为RAM、用于存储本发明的实施例的方法的可执行代码的随机存取存储器1402，以及适于记录实现根据本发明的实施例的方法所必需的变量和参数的寄存器，其存储器容量可以由连接到例如扩展端口的可选RAM扩展；

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

-网络接口1404通常连接到通信网络，将被处理的数字数据通过该通信网络被发送或接收。网络接口1404可以是单个网络接口，或者包括不同的网络接口(例如，有线接口和无线接口，或不同种类的有线或无线接口)的集合。在CPU 1401中运行的软件应用的控制下，数据包被写到网络接口以供发送，或者被从网络接口读取以供接收；

-用户接口1405可以用于接收来自用户的输入或者向用户显示信息；

-被表示为HD的硬盘1406可以作为大容量存储设备提供；

-I/O模块1407可以用于从外部设备(诸如视频源或显示器)接收数据/将数据发送到外部设备(诸如视频源或显示器)。

可执行代码可以被存储在只读存储器1403中、硬盘1406上或可移动数字介质(诸如例如盘)上。根据变体，程序的可执行代码可以经由网络接口1404借助于通信网络被接收，以便在被执行之前被存储在通信设备1400的存储部件中的一个(诸如硬盘1406)中。

中央处理单元1401适于控制和指导根据本发明的实施例的一个或多个程序的指令或软件代码部分的执行，这些指令被存储在前述存储部件中的一个中。在上电之后，CPU1401能够在来自主RAM存储器1402的与软件应用相关的指令已经从例如程序ROM 1403或硬盘(HD)1406被加载之后执行这些指令。这样的软件应用当被CPU 1401执行时，使图17至图21所示的流程图的步骤被执行。

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

尽管上文已经参考特定实施例描述了本发明，但是本发明不限于这些特定实施例，并且落在本发明的范围内的修改对于本领域技术人员将是清楚的。

本领域的熟练技术人员在参考前述说明性实施例时将想到许多进一步的修改和变化，前述说明性实施例是仅以举例的方式给出的，而非意图限制本发明的范围，本发明的范围仅由所附权利要求确定。具体地说，来自不同实施例的不同特征可以在适当的情况下被互换。

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

Claims (14)

1.一种从比特流解码图像中的当前像素块的方法，所述方法包括：

获得块的索引、被转义像素值以及调色板，所述调色板包括将各个条目索引与对应像素值相关联的条目的集合，并且所述被转义像素值包括在条目索引中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

从所述块的索引、被转义像素值以及调色板形成当前像素块；

其中，获得所述块的索引包括：

从所述比特流获得语法元素，以用于生成在块中具有连续位置的索引组；

基于所述语法元素生成所述块的索引，

其中，所获得的语法元素包括由up-to-end码字所指示的语法元素，所述up-to-end码字指示形成所述索引组中的一个的索引是直到所述块的末尾的所有剩余位置处的索引，而不管块中剩余位置的数量如何。

2.根据权利要求1所述的方法，其中，所述语法元素使用与定义的数量的索引相关联并且与所述块的索引的索引组相对应的预定义码字，并且与所述块中的最后位置相对应的语法元素使用所述up-to-end码字。

3.根据权利要求2所述的方法，其中，与定义的数量的索引相关联的预定义码字中的至少一个或多个是短码字，并且与其他定义的数量的索引相关联的至少一个或多个其他预定义码字包括公共码字前缀和可变码字后缀；并且其中，up-to-end码字包括公共码字前缀。

4.根据权利要求3所述的方法，其中，除了公共码字前缀之外，up-to-end码字还包括一位的后缀。

5.根据权利要求1所述的方法，其中，所述语法元素是以集合提供的，并且生成与语法元素集合相对应的索引组是取决于所述集合的第一语法元素的，用于生成所述索引的操作是以下操作中的一个：

重复具有正上方的位置的索引；以及

重复被编码在所述集合的第二语法元素中的索引。

6.一种用于从比特流解码图像中的当前像素块的设备，所述设备包括适于执行权利要求1至5中任一项所述的方法的部件。

7.一种用于对图像中的当前像素块进行编码的方法，所述方法包括：

从所述当前像素块和调色板生成块的索引和被转义像素值，所述调色板包括将各个条目索引与对应像素值相关联的条目的集合，并且所述被转义像素值包括在条目索引中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

对所述块的索引和被转义像素值进行编码；

其中，对所述块的索引进行编码包括：

生成语法元素，以用于生成在块中具有连续位置的索引组，

其中，所述语法元素包括由up-to-end码字所指示的语法元素，所述up-to-end码字指示形成所述索引组中的一个的索引是直到所述块的末尾的所有剩余位置处的索引，而不管块中的剩余位置的数量如何。

8.根据权利要求7所述的方法，其中，所述语法元素使用与定义的数量的索引相关联并且与所述块的索引的索引组相对应的预定义码字，并且与所述块中的最后位置相对应的语法元素使用所述up-to-end码字。

9.根据权利要求8所述的方法，其中，与定义的数量的索引相关联的预定义码字中的至少一个或多个是短码字，并且与其他定义的数量的索引相关联的其他预定义码字中的至少一个或多个包括公共码字前缀和可变码字后缀；并且其中，up-to-end码字包括公共码字前缀。

10.根据权利要求9所述的方法，其中，除了公共码字前缀之外，up-to-end码字还包括一位的后缀。

11.根据权利要求7所述的方法，其中，所述语法元素是以集合提供的，并且生成与语法元素集合相对应的索引组是取决于所述集合的第一语法元素的，用于生成所述索引的操作是以下操作中的一个：

重复具有正上方的位置的索引；以及

重复被编码在所述集合的第二语法元素中的索引。

12.一种用于对图像中的当前像素块进行编码的设备，所述设备包括适于执行权利要求7至11中任一项所述的方法的部件。

13.一种用于从比特流解码图像中的当前像素块的解码设备，所述解码设备包括：

用于获得块的索引、被转义像素值以及调色板的部件，所述调色板包括将各个条目索引与对应像素值相关联的条目的集合，并且所述被转义像素值包括在条目索引中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

用于从所述块的索引、被转义像素值以及调色板形成当前像素块的部件；

其中，获得所述块的索引包括：

从比特流获得语法元素，以用于生成在块中具有连续位置的索引组；及

基于所述语法元素生成所述块的索引，

其中，所获得的语法元素包括由up-to-end码字所指示的语法元素，所述up-to-end码字指示形成索引组中的一个的索引是直到所述块的末尾的所有剩余位置处的索引，而不管块中的剩余位置的数量如何。

14.一种用于对图像中的当前像素块进行编码的编码设备，所述编码设备包括：

用于从所述当前像素块和调色板生成块的索引和被转义像素值的部件，所述调色板包括将各个条目索引与对应像素值相关联的条目的集合，并且所述被转义像素值包括在条目索引中不具有与调色板中的像素值相关联的对应索引的像素的像素值；以及

用于对所述块的索引和被转义像素值进行编码的部件，

其中，对所述块的索引进行编码包括：

生成语法元素，以用于生成在块中具有连续位置的索引组，

其中，所述语法元素包括由up-to-end码字所指示的语法元素，所述up-to-end码字指示形成对应索引组中的一个的索引是直到所述块的末尾的所有剩余位置处的索引，而不管块中的剩余位置的数量如何。