对焦方法、装置、计算机可读存储介质和计算机设备

(19)中华人民共和国国家知识产权局

(12)发明专利申请

(10)申请公布号CN111684812A

(43)申请公布日2020.09.18

(21)申请号201880088756.2(72)发明人伊万・马科夫

巴拉日•凯斯特海伊

(22)申请日2018.12.06

斯特尔乔斯•保拉拉基斯

优先权数据

(30)米歇尔•桑纳罗伯特•埃廷格

17386046.12017.12.06EP

(74)专利代理机构北京康信知识产权代理有限

18386002.22018.02.08EP

责任公司11240

1812407.32018.07.30GB

代理人刘彬

1815437.72018.09.21GB

(51)lnt.CI.

(85)PCT国际申请进入国家阶段日

H04N7"%(2006.01)

2020.08.06

HO4N7£//7<5(2006.01)

(86)PCT国际申请的申请数据

H04N7^779(2006.01)

PCT/GB2018/0535512018.12.06

H04N7^<5(2006.01)

(87)PCT国际申请的公布数据HO4N7力729(2006.01)

W02019/111009EN2019.06.13H04N7"746(2006.01)

(71)申请人V-诺瓦国际有限公司H04N7^7<57(2006.01)

地址英国伦敦H04N7H36(2006.01)

权利要求书2页说明书27页附图19页

(54)发明名称

分级数据结构

(57)摘要

一种对经编码数据流进行解码的方法，所述

方法包括在解码器处:接收包括多个图块的经编

码数据集;接收数据结构，所述数据结构指示编

码多个图块所需的数据量;通过以下步骤识别经

编码数据集的要解码的一部分:识别与要解码的

部分相关联的图块;基于编码所述图块所需的数

据量来确定与所述图块有关的数据的位置;从所

述经编码数据集中提取所述经编码数据集的识

别部分;以及对所述经编码数据集的所述识别部

分进行解码。

V

Z

I

S

C9O

三

g

CN111684812A权利要求书1/2页

1.一种解码经编码数据流的方法,所述方法包括在解码器处：

接收包括多个图块的经编码数据集；

接收数据结构，所述数据结构指示编码多个图块所需的数据量；

通过以下步骤识别所述经编码数据集的要解码的一部分：

识别与要解码的所述部分相关联的图块；

基于编码所述图块所需的数据量来确定与所述图块有关的数据的位置；

从所述经编码数据集中提取所述经编码数据集的识别部分；以及

解码所述经编码数据集的所述识别部分。

2.根据权利要求1所述的方法，其中，所述数据集是按层组织的，其中，第一层还包括：

指示所述数据在所述数据集内的分布的信息。

3.根据权利要求1或2所述的方法，其中，所述数据集的所述第一层包括残差数据。

4.根据权利要求2或3中任一项所述的方法，所述方法还包括第二层，所述第二层还包

括与编码多个图块所需的数据量有关的信息。

5.根据权利要求4所述的方法,所述方法还包括以下步骤:基于所述第二层中的所述信

息，确定要解码的图块数据在经编码流内的位置。

6.根据权利要求5所述的方法，其中，所述数据被顺序地编码，并且所述方法还包括以

下步骤:基于对任一先前的图块进行编码所需的数据量的总和，确定图块数据在所述经编

码流中的位置。

7.根据权利要求6所述的方法，所述方法还包括在所述图块数据的确定的位置处解码

所述经编码数据流。

8.根据任一前述权利要求所述的方法，所述方法还包括：识别所述经编码数据流的要

解码的第二部分，以及解码所述第二部分，其中，所述第一部分被第一解码器解码，并且所

述第二部分被不同的第二解码器解码。

9.一种对经编码数据流进行解码的方法,所述方法包括在解码器处：

接收包括多个图块的经编码数据集；

接收数据结构，所述数据结构指示大于、小于或等于所述多个图块的阈值的数据的分

布；

识别所述数据结构中要解码的具有大于或等于所述阈值的数据的所述图块；

解码识别的图块。

10.根据权利要求9所述的方法，其中，所述数据集是按层组织的，其中，第一层还包括

指示所述数据在所述数据集内的分布的所述数据结构,并且第二层包括与编码多个图块所

需的数据量有关的信息。

11.根据权利要求10所述的方法，所述方法还包括以下步骤:基于所述第二层中的所述

信息，确定要解码的图块数据在经编码流内的位置。

12.根据权利要求10所述的方法，其中，所述图块被顺序地编码,所述方法包括以下步

骤:基于对任一先前的图块进行编码所需的数据量的总和，确定所述图块数据在所述经编

码流中的位置。

13.根据权利要求12所述的方法，所述方法还包括在所述图块数据的确定的位置处解

码所述经编码数据流。

2

CN111684812A权利要求书2/2页

14.根据权利要求8至13中任一项所述的方法，其中，接收的经编码视频数据流以多个

量化级被编码，其中，所述方法包括：以第一量化级对所述经编码视频数据流的第一图块进

行解码，以及以不同的第二量化级对第二图块或区域进行解码。

15.一种用于对经编码视频数据流进行解码的解码器，所述解码器被配置成执行根据

权利要求1至15中任一项所述的方法。

3

CN111684812A说明书1/27页

分级数据结构

技术领域

[0001]本发明广泛地涉及对数据诸如图像数据和视频数据进行编码和解码以及内容传

递的领域。特别地，本发明涉及一种以高效方式对视频数据和元数据进行编码的方法，其允

许编码和解码过程的并行化。

背景技术

[0002]已知对数据诸如图像数据和视频数据进行编码以用于存储或流传输，以便减少存

储数据所需的存储空间量或数据传输所需的带宽。举例来说,编码和解码视频数据的技术

是众所周知的并且被广泛使用，例如H.264/AVC标准使用图像压缩和基于运动的估计技术

的组合将视频数据编码为经编码视频流,然后将经编码视频流解码为与原始视频数据非常

接近的近似值。

[0003]经编码视频流通常以比特率编码。比特率将取决于若干因素而变化，其中之一是

可用于流传输经编码视频流的带宽。带宽越小，经编码视频流的可用比特率就越小。最终，

带宽定义了所传递的视频流的质量，因为相对较小的比特率需要相对粗略的量化，即相对

较大的量化参数(QP)。在大带宽可用的情况下，则可以使用较精细的量化，即相对较小的量

化参数(QP)。该过程是创建经编码视频流时采用的较广泛的速率控制机制的一部分。

[0004]视频数据可以根据编码器和解码器之间的可用带宽量以变化的比特率被实时编

码，也可以在有需求之前被编码和存储,然后作为单个比特率经编码视频流或以代表以不

同比特率编码的视频数据的分段进行解码，使得存在多个视频流，并且基于可用带宽来选

择流。解码器可以随着带宽的变化在不同的比特率流之间动态切换。以分级的方式编码视

频数据也是已知的。在这种编码技术中，残差数据(即纠正基础层中存在的低质量信息所需

的数据)将以逐渐提高的质量级使用。所有这些导致了用于编码和解码数据诸如图像或视

频数据的技术越来越复杂和精细。

[0005]元数据可以用于提供对基础数据的更好的理解，尤其是在解码器处，因此可以改

进速率控制技术并最终提高数据再现质量。但是，使用元数据引起的数据再现质量的提高

必须与计算元数据的关联的处理和时间成本、用于存储元数据的存储成本以及用于传输元

数据的带宽成本相权衡。需要用于数据编码器和解码器的改进的元数据技术以减轻这些问

题中的一个或多个问题，尤其是对于图像或视频编码和解码。特别地，需要新的元数据结

构，该元数据结构允许实现以下中的至少一项:生成元数据时的处理成本较低，用于存储元

数据的存储成本较低以及用于传输元数据的带宽要求较低。另外，需要创建一种元数据结

构,该元数据结构能够更高效地对经编码数据流进行解码。

发明内容

[0006]因此，为了减轻上述问题中的一些问题，在本发明的第一方面中提供了一种编码

信号的编码器和方法，所述方法包括:获得要编码的数据集，所述数据集指示所述信号的一

个或多个特性;将所述数据集映射到数据结构中，所述数据结构定义数据的例子，其中，所

4

CN111684812A说明书2/27页

述数据的映射包括以下步骤:将所述数据集细分为多个图块,每个图块在所述数据集中定

义元素块;将每个图块细分为多个子块;为所述多个子块中的每个子块定义对应的节点;为

每个节点分配值，所述值指示与所述节点相对应的所述子块是否包含大于、等于或小于阈

值的数据；以及将分配值映射到所述数据结构的第一级中。

[0007]根据本发明的另一方面，提供了一种解码经编码数据流的解码器和方法，所述方

法包括在解码器处:接收包括多个图块的经编码数据集;接收数据结构，所述数据结构指示

编码多个图块所需的数据量;通过以下步骤识别所述经编码数据集的要解码的一部分：识

别与要解码的所述部分相关联的图块;基于编码所述图块所需的数据量来确定与所述图块

有关的数据的位置；从所述经编码数据集中提取所述经编码数据集的识别部分；以及解码

所述经编码数据集的所述识别部分。

[0008]根据本发明的又一方面,提供了一种对经编码数据流进行解码的解码器和方法，

所述方法包括在解码器处:接收包括多个图块的经编码数据集;接收数据结构，所述数据结

构指示大于、小于或等于所述多个图块的阈值的数据的分布；识别所述数据结构中要解码

的所述图块，所述图块具有大于或等于对识别图块进行解码的所述阈值的数据。

[0009]根据本发明的又一方面，提供了一种对经编码数据流进行解码的解码器和方法，

所述方法包括:接收包括多个图块的经编码数据集;接收数据结构，所述数据结构指示对所

述多个图块中的每个图块进行编码所需的数据量;通过以下步骤识别所述经编码数据集的

要解码的多个部分:识别与要解码的每个部分相关联的图块;对于每个部分，基于对与所述

部分相关联的所述图块进行编码所需的数据量,确定与所述部分的所述图块相关的数据的

位置;对于每个所述识别部分，从所述经编码数据集中提取所述部分；以及用第一解码器对

所述经编码数据集的所述第一部分进行解码，并使用不同的第二解码器对所述经编码数据

集的第二部分进行解码。

[0010]还提供了一种用于编码图像的分级数据结构，所述数据结构包括多个质量级，每

个质量级包括多个层，每个层包括一个或多个数据元素。可选地，其中，每个质量级定义相

应的一组经编码数据，所述相应的一组经编码数据在被解码时使得解码器能够将所述图像

重构到期望的质量级;每一层包括一个或多个数据元素，所述数据元素取决于层的类型被

定义，并且其中：对于第一类型的层，第一类型的数据元素被定义为包括所述一组经编码数

据的子集;并且对于第二类型的层，第二类型的数据元素被定义为包括与所述第一类型的

数据元素相关联的一个或多个属性。

[0011]通过对映射在数据帧内出现残差数据的例子所需的数据结构进行定义，可以提供

较快的解码和编码方法。特别地，对用于编码数据的数据量稀疏化，从而减少了在解码期间

需要读取的数据量。此外，数据和描述数据结构的元数据允许在不参考帧的其他部分的情

况下选择性地解码帧的各个部分。因此，可以并行化解码过程。

[0012]根据所附权利要求，本发明的其他方面将显而易见。

附图说明

[0013]现在将参考附图描述本发明的实施例,其中：

[0014]图1是示出用于执行示例编码方法的系统的框图；

[0015]图2是残差数据的NxN像素的图块的代表性示例；

5

CN111684812A说明书3/27页

[0016]图3是示例密集四叉树；

[0017]图4示出了根据本发明一方面的一行残差数据的密集四叉树和稀疏四叉树表示；

[0018]图5是根据本发明一方面的编码视频流的方法的流程图；

[0019]图6是根据本发明一方面的16x16级的稀疏化的代表性示例；

[0020]图7是示出16x16级的稀疏化和2x2四数据集之间的关系的示例；

[0021]图8是根据本发明一方面的8x8级的稀疏化的代表性示例；

[0022]图9是根据本发明一方面的不同级的稀疏化数据的示例；

[0023]图10是根据本发明一方面的在遍历树期间出于编码目的使用映射函数的示例；

[0024]图11是根据本发明一方面的Tesserae网格的流长度的画面与经编码流之间的关

系的示例；

[0025]图12是根据本发明一方面的层-0和层TTesserae之间的关系的示例；

[0026]图13是根据本发明一方面的如何从画面中解码流长度的示例；

[0027]图14是根据本发明一方面的解码器如何使用画面的流长度来并行解码的示例；

[0028]图15是根据本发明一方面的用于创建层T表示的流程图；

[0029]图16是根据本发明一方面的帧内的活动区域的示例；

[0030]图17是根据本发明一方面的用于解码活动区域的流程图；

[0031]图18是根据本发明一方面的被分配有单独的活动区域的并行解码器的示例；

[0032]图19是根据本发明一方面的数据结构的示例；以及

[0033]图20是根据本发明一方面的数据结构的另一示例。

具体实施方式

[0034]现在将参考附图描述本发明的实施例。要注意的是，以下描述仅用于使得技术人

员能够理解本发明，而无意将本发明的适用性限制于读者可以容易地理解和/或设想的其

他实施例。

[0035]本发明提供了一种用于编码和解码数据的方法和设备，所述数据尤其是但不限于

图像和视频数据。具体地,本发明提供了一种用于对要编码的数据进行编码以及以高效方

式提供和编码关联元数据的方法。另外，本发明提供了一种用于以高效方式使用编码数据

的关联元数据对所述经编码数据进行解码的方法。为了便于参考,在以下描述中，要编码的

数据被视为残差数据，但是也可以使用其他要编码的合适的数据，例如RGB值、YUV值等。

[0036]在图1中，以示例的方式示出了系统100,系统100包括经由网络连接到多个客户端

装置130、132的流服务器102。

[0037]流服务器102包括编码器104,该编码器被配置成利用本文描述的方法来接收和编

码第一数据信号。为了便于理解，以下参考作为数据信号的视频数据进行描述，然而也可以

编码其他类型的数据（诸如，例如，图像）。流服务器104被配置成将经编码数据流例如视频

流106传递到多个客户端装置130和132,诸如机顶盒、智能TV、智能电话、平板计算机、笔记

本电脑等。每个客户端装置130和132被配置成对经编码视频流106进行解码和渲染。在其他

实施例中，经编码数据流包括不同的数据，诸如图像/图片。

[0038]为了便于理解，参考单个流服务器102和两个接收方客户端装置130、132来示出图

1的系统100。在未示出但本领域技术人员将理解的其他实施例中，系统100可以包括多个服

6

CN111684812A说明书4/27页

务器和数万个客户端装置。

[0039]流服务器102可以是能够通过网络将经编码数据传递到客户端装置的任何合适的

数据存储和传递服务器。流服务器在本领域中是已知的，并且使用单播和/或多播协议。流

服务器被布置成编码且经常存储视频数据，并且以一个或多个经编码数据流106将经编码

视频数据提供给客户端装置130和132。每个经编码视频流106由编码器104生成。图1中的编

码器104位于流服务器102上，然而在其他实施例中，编码器104位于系统100中的其他地方。

流服务器102可以提供实况视频内容或视频点播（VoD）视频内容中的一个或多个。编码器

104利用本文描述的技术生成经编码视频流。如在比特率控制系统中已知的，编码器104接

收关于目标比特率（即，希望视频被编码的比特率）的信息。

[0040]编码器104还包括速率控制器108。速率控制器108是确定视频数据要被编码的比

特率的软件模块。在实施例中，速率控制器108管理单通编码器104的速率控制，然而在其他

实施例中，编码器104是多通编码器。速率控制器108的部分功能是获取目标比特并确定相

关参数（诸如量化参数（QP）），以使编码器106以目标比特率或接近于目标比特率产生经编

码数据流。这种速率控制器108的功能在本领域中是已知的。

[0041]速率控制器108还包括速率控制器管理器110。速率控制器管理器110是确定速率

控制器108的目标比特率的软件模块。下面参考图3和图4详细描述速率控制器管理器110的

功能。速率控制器管理器110接收初始目标比特率（即，将由编码器104生成的期望比特率），

并确定由速率控制器108和编码器106使用的经修改的目标比特率，从而以该目标比特率编

码数据流。如下面进一步详细描述的，速率控制器管理器110利用了机器学习原理，以便确

定速率控制器108和编码器106的最佳的经修改的目标比特率。由于对流进行编码所使用的

参数和编解码器,编码器106的获得的或输出的比特率通常将与目标速率的比特率不同。因

此,为了获得目标比特率，确定了经修改的比特率,所述经修改的比特率被改变，以便考虑

期望比特率与由于编码过程而获得的实际比特率之间的差异。

[0042]客户端装置130和132是本领域中已知的装置,并且包括接收和解码视频流所需的

已知元件，诸如处理器、通信端口和解码器。解码器被配置成对经编码数据流106进行解码。

[0043]在编码器104处接收并编码视频流，以生成经编码数据流106。如下面详细描述的，

通过速率控制器管理器110和速率控制器108确定用于编码视频流的参数。

[0044]本发明的一方面在于创建一种数据结构，该数据结构用于编码数据信号，并且对

以小带宽且高效的解码方式解码数据信号所需的元数据进行编码。在以下描述中，为了便

于参考，我们将参考特定类型的数据信号，即视频数据，但是应该理解，这不是限制性的，并

且本发明同样适用于任何合适类型的信号，包括例如静态图片、图像、3D扫描、层析图片、卫

星图像、雷达图像、遥测数据、声音信号等。

[0045]视频数据可以根据需要具有任何合适的帧大小。每个帧被细分为多个图块，优选

地，每个图块具有相等的大小。图块大小可以是任何大小，并且在本文中被定义为NxN图块。

在实施例中，图块大小可以是64x64、32x32、16xl6、8x8等中的一个。为了便于理解，参考

16x16元素的图块描述以下过程，然而,这仅仅是示例性的。

[0046]本发明的一方面定义了一种数据结构,该数据结构使得数据信号诸如视频数据能

够以稀疏方式被编码，以减小以质量级流传输视频数据所需的带宽，并且该数据结构允许

解码器更高效地对经编码数据流进行解码（或者，在存储视频数据的情况下，减少存储和解

7

CN111684812A说明书5/27页

码所需的数据存储量）。如下面更详细描述的，视频数据使用树结构以自下而上的方式被编

码。为了便于参考，在下文中，我们将该树称为四叉树，但是也可以使用其他结构。从概念上

讲，数据结构识别视频数据中存在要编码的数据的例子，并且在存在该数据的情况下进行

映射。因此，还以低成本的方式识别没有要编码的数据的区域。结果，可以减小发送经编码

数据流和关联元数据信息所需的带宽。如下面详细解释的，数据结构还允许数据被并行编

码并且并行地被分别解码。数据结构还允许较高效的解码。通过阅读以下描述，这些优点将

变得更加清楚。

[0047]为了解码数据结构，需要对数据结构进行描述的元数据，以便允许解码器理解经

编码数据的结构并解码数据。

[0048]要注意的是,本发明可以与要编码的任何类型的数据一起使用。在视频信号的示

例性情况下，要编码的数据的类型可以取决于视频信号的处理方式而变化。例如，在分级方

法中——诸如本文或者例如专利号为8,977,065、8,948,248、8,711,943、9,129,411、8,

531,321、9,510,018、9,509,990的美国专利中进一步详细讨论的分级方法，上述美国专利

通过引用并入本文一一视频信号通常被分为各个帧，每个帧包括一定数量的值（例如，像

素）。然后可以对信号进行递归处理以减小其大小（例如，将YxZ像素的完整帧（例如，层0）

下采样到Y/2xZx2像素的第一下采样帧（例如，层T）中，然后又在Y/4xZx4像素的第二下

采样帧中（例如，层-2），依此类推），然后再进行编码。被编码的内容不一定是像素的绝对

值，而是例如与像素值之间的相对差相关联的值。例如，可以取相同位置的层T处的像素的

值与层-2处的像素的上采样版本的值之间的差。该差有时可以被称为残差。可以使用变换

来进一步处理残差以生成经变换的残差（例如，参见专利号为9,509,990的美国专利作为这

种变换的示例），例如以进一步减小端并提高编码过程的效率。在本说明书和权利要求书

中，我们提到术语“残差”或“残差数据”以描述残差或经变换的残差，因为本发明将同等地

适用于两者。因此，在上述示例性分级结构中，如本专利申请中所述,可以将残差视为要编

码的数据的类型。在其他示例中，视频信号的帧的像素值可以在不相对于参考帧取任何差

的情况下被直接编码（从而生成某种形式的残差），或者可以对不同类型的残差进行编码

（例如，时间残差，诸如MPEG标准（如H.264）中的时间残差）。在那种情况下，像素值或其他类

型的残差可以被视为要编码的数据的类型。

[0049]本文描述的过程提供了一种用于将要编码的数据帧映射到稀疏分级结构的方法。

如上所述,这些数据可以是残差、像素值等。通过以下述方式进行映射，可以将视频数据帧

“切片”为独立的图块。每个图块可以被单独地编码和解码，从而实现并行化。此外，当以多

个质量级编码和解码数据时，以下描述的方法允许在不了解先前的质量级的情况下解码每

个质量级。这是重要的优点，并且熟练的读者将理解，该能力增加了解码器的效率和灵活

性。

[0050]为了便于理解，以下关于要编码的数据的单个帧进行描述，其采用第一质量级的

残差数据的形式。在其他实施例中，帧可以包含原始像素值、亮度、色度等。这样的帧可以具

有任何大小，并且可以被细分为多个图块，每个图块的尺寸为NxN。为了便于理解，以下参考

16x16元素例如16x16残差的图块进行描述。

[0051]本文描述的过程引起对数据（诸如残差数据）以及数据结构的编码，该数据结构用

于映射数据在经编码数据中的出现情况。还提供了在其他数据结构中编码元数据（诸如，编

8

CN111684812A说明书6/27页

码残差数据所需的位数）并描述结构元数据的能力。因此，编码过程引起对数据、元数据的

编码，所述元数据描述数据和数据结构以映射数据和元数据。还描述了一种解码过程，其

中，解码器使用数据结构来读取经编码数据。如下面通过将元数据和数据结构提供给解码

器所详细描述的，解码器可以确定数据在经编码数据流内的位置并且选择性地对数据流的

感兴趣的部分进行解码。

[0052]图2是残差数据的图块的示例，所述图块的大小为NxN。为了便于理解，以下参考残

差数据的16x16图块进行描述。如前所述，该原理适用于其他大小为NxN的图块。

[0053]如从图2中可以看到的，图块的元素具有各种残差数据值。在其他实施例中，图块

的元素可以是与视频数据的属性（例如亮度、色度、噪声、比特大小等）有关的其他数据和/

或元数据。

[0054]如图2所示，许多元素的值为零，并且其余元素的值为非零。图2中所示的值仅作为

示例示出，并且所示的值可以是任何合适的值。

[0055]残差数据的存在通常指示图像数据中特征或边缘的存在（因为已知这样的特征的

频率太高而无法以较低的质量级捕获）。如下面进一步详细解释的，以下过程允许以高效方

式对所有对应的像素编码残差数据。特别地，数据结构识别图块内具有残差数据的区域或

区（例如，存在边缘之处）。

[0056]众所周知，在编码残差数据时，附近元素的某些组将具有全零值（表明没有理由将

残差数据与这些元素相关联），而某些元素将具有非零值。因此，并非图块内的每一个元素

都将为非零。所描述的过程的一方面是，例如在元素具有零值或者具有等于或小于阈值的

值的情况下，不需要对高比例的元素进行编码（并因此进行解码）。所描述的过程识别图块

上的残差数据的块，并且仅编码（并且因此解码）必要的块，从而稀疏化数据。这种稀疏性在

图2中由图块内取值为“0”的元素来表示。所描述的过程的另一方面在于，除了稀疏化残差

数据之外，还提供稀疏树结构形式的元数据，其然后允许解码残差数据，特别是高效地解码

残差数据。

[0057]因此，可以通过仅编码和解码非零值来利用这种稀疏性以提高编码和解码的速

度。相反，密集方法将对图块内的每个值进行编码和解码，而不管其是否为零。当大量数据

为零时，这种方法可能效率不高。此外，如下面详细解释的，该过程允许在不参考其他元素

的情况下单独地对帧的各个部分或元素进行解码。因此，可以利用多个单独的解码器对以

所述方式被编码的数据进行解码，从而允许解码过程的并行化。

[0058]因此，本发明的一方面在于高效的方式，通过所述方式可以识别和使用图块的非

零元素。

[0059]在实施例中，稀疏四叉树数据结构用于在编码和解码期间识别包含非零值的图块

的元素。

[0060]图3示出了密集四叉树300的代表性示例。四叉树由节点（例如302、306）和将节点

（诸如父节点302）连接到子节点306的边缘（例如304）组成。在图3的四叉树中，每个父节点

具有正好四个子节点。四叉树可以包含多个叶节点308。叶节点被定义为不包含任何子节点

的节点。四叉树还可以包含根节点302,其被定义为没有父节点的节点。根节点302被称为树

300的最低级节点302。叶节点308被称为树的最高级节点。包含父节点和子节点两者的节点

（例如306）被称为内部节点。

9

CN111684812A说明书7/27页

[0061]在图4中，示出了用于对一行残差数据402进行映射的四叉树400。所述四叉树400

由叶节点403、内部节点412和根节点406组成。四叉树400的每个叶节点403对应于行402上

特定残差数据项的位置。

[0062]作为示例,叶节点403映射到残差数据404的项。通过以设置的遍历顺序（例如深度

优先）从根节点406遍历四叉树，可以在编码和解码期间以相同的顺序读取行402上的每个

元素。如上所述，以上述方式读取行上的残差数据的每一项可能是低效的。当只有一些残差

为非零时,这种低效尤其明显。

[0063]本发明的一方面在于识别在树上的最低可能级处为空的图块的区（即，该区内的

每一个元素的残差值为零），以提高编码和解码过程的效率。返回图4,行402上的区410和

410A仅包含值为零的残差。在这种情况下，当解码行402时，遍历可能在节点412处中断，并

且在412A处再次中断，因为它们的所有子节点都映射到零残差。

[0064]因此，使用稀疏四叉树400A。稀疏四叉树以与密集四叉树相同的方式被定义，但节

点为空。在稀疏四叉树中，每个父节点具有恰好四个子节点，或者没有子节点。这与图3中每

个父节点具有恰好四个子节点的四叉树相反。如果内部节点的所有子节点都同样为空，则

该内部节点被视为空。如果叶节点的对应残差值为零，或者对应残差值小于某个阈值，则该

叶节点被视为空。

[0065]作为示例，内部节点414为空，因为其叶节点全部映射到为零的残差值，例如416、

416A。在遍历稀疏四叉树期间，仅当节点不为空时才访问所述节点的子节点。因此，如果在

遍历期间访问空节点，则遍历不会继续至所述空节点的子节点，因为根据定义，它们全部将

同样为空。

[0066]在解码期间，以自下而上的定义遍历树400A；即，从最低级到最高级遍历树400A。

在实施例中，以深度优先的方式遍历树。这样做等效于以z顺序遍历来访问NxN图块的元

素。这允许将空间信息用作编码和解码过程的一部分。其还确保以与编码元素相同的顺序

解码元素。在其他实施例中，可以采用其他遍历方法来利用图块的结构的其他方面。

[0067]因此，稀疏四叉树数据结构定义了残差数据的例子和位置。

[0068]图5是根据本发明一方面的构造稀疏四叉树的过程的流程图。然后可以将稀疏四

叉树编码为经编码数据流的一部分。

[0069]参考图5描述的过程是用于以稀疏方式映射残差数据的例子的过程。该映射过程

确定用于对数据进行编码的数据结构的第一层（层-0）。

[0070]为了便于参考，以下参考数据的图块例如残差值进行描述，所述图块的大小为

16x16像素。在其他实施例中，以下过程可以用于不同大小的图块，例如8x8、32x32、64x64

等。

[0071]本文所述的过程提供了一种方法，该方法用于以分级树结构将来自视频数据的第

一帧的数据（残差数据、元数据或任何其他形式的数据）的图块映射为稀疏四叉树。如下面

详细描述的，通过以下面描述的方式进行映射，减少了要编码（并且因此随后被解码）的数

据的量。此外，当该过程用于以分级方式以多个质量级对数据流进行编码时，所描述的数据

结构消除了对先前或进行中的质量级的任何要求。因此，可以单独地且在不参考任何其他

层的情况下编码和解码质量级。因此，与许多已知的分级编码方案相反一一在已知的分级

编码方案中，需要解码最低质量级以便解码任何较高质量级一一所描述的方法不需要解码

10

CN111684812A说明书8/27页

任何其他质量层。

[0072]一方面是，分级树结构定义了何时存在数据（并且因此需要进行编码）的例子并提

供了映射以识别存在这种数据的位置（在图块中的位置）。如下所述，由于以从下到上的方

式进行编码，因此以减少要编码的数据的量的方式来识别不存在数据的帧区域，从而稀疏

化数据。

[0073]为了便于理解，以下关于以第一质量级被编码的视频数据的单个帧进行描述。

[0074]在步骤S102,接收要编码的视频数据的第一帧。视频数据可以存储在本地，也可以

从外部来源诸如服务器被接收。

[0075]视频的第一帧已与视频数据、元数据或描述该帧的第一特性的数据相关联。

[0076]确定与视频数据的第一帧相关联的残差数据的步骤可以通过使用本领域中任何

已知的合适方法来执行。本发明定义了一种方法，该方法用于以高效方式对帧的残差数据

和任何其他元数据进行编码。由于数据可以与残差数据有关，因此本文所述的过程可以用

于对视频数据的帧的增强进行编码。

[0077]在步骤S104,确定残差数据。确定残差数据的步骤可以使用任何已知的过程来进

行，例如，从重构信号中减去参考信号的过程,诸如公告号为W02013011494的专利中所描述

的，该专利的内容通过引用并入本文。

[0078]因此,在步骤S104,在实施例中，对于每个像素确定视频的第一帧的残差数据，从

而定义残差帧。

[0079]在其他实施例中，残差帧已经被预先确定，并且被存储在存储器中。在这样的实施

例中，残差帧在步骤S104被发送到编码器并且被编码为经编码数据流的一部分。

[0080]该方法的以下步骤定义了一种新颖的方法，该方法用于定义和存储对残差数据的

分布进行映射的元数据。

[0081]在步骤S106,残差帧被细分为多个图块。在优选的实施例中，整个帧上的图块的大

小是规则的，并且定义了16x16像素图块。

[0082]图2示出了残差数据的图块的示例。

[0083]如参考图2所描述的，本发明的一方面在于定义一种数据结构，该数据结构定义用

于视频数据帧的元数据的例子和位置。

[0084]为了定义残差数据的例子在图块上出现的位置，在步骤S108,通过执行二进制映

射操作将残差的16x16图块转换为二进制值。取决于元素的值,为每个元素分配二进制值。

如果元素具有非零残差值，则为二进制映射中的等效元素分配值“1”，否则为其分配值“0”。

在其他实施例中，使用非零阈值。例如，如果确定某个非零残差值可以被认为是可接受的，

则可以将该值用作阈值，因此，如果元素大于非零阈值,则为其分配值“1”，如果该元素小于

非零阈值，则为其分配值“0”（取决于如何实施过程，可以为等于非零阈值的值分配“0”或

“1”）。注意，“0”和“1”只是用于识别两种替代方案的等效的逻辑二进制数字一一换句话说,

它们可以是实数（零和一），也可以是两个等效的逻辑值。

[0085]根据定义，在步骤S108产生的二进制映射具有与残差数据的图块相同的大小（例

如16x16），并且对包含残差数据图块内的残差数据的元素的位置进行了定义。由于以稀疏

方式定义数据，因此该数据定义了映射残差数据的16x16的稀疏化级（L0S）。在实施例中，鉴

于层-0中保存的残差数据，16x16的L0S不被编码为经编码数据流的一部分，因为这样的数

11

CN111684812A说明书9/27页

据在经编码数据流中是冗余的。但是，这种数据用于定义稀疏化的其他级。

[0086]以下过程用于识别图块内不包含任何残差信息的最大可能区域。如果可以将图块

的一部分（例如8x8元素）识别为不包含任何残差信息,则描述该部分的数据需求将减少为

零。因此，可以将步骤S112至S118视为定义不包含残差数据的图块的区域。

[0087]图6示出了图2的16x16的L0S的示例。从图6中可以看到，图2中的任何非零值都将

转换为值1,并且因此映射残差数据。

[0088]因此，在残差数据存在的情况下，逐个像素映射16x16的L0S。

[0089]因此，其定义了四叉树数据结构600A的最高级节点。

[0090]在步骤S110,将16x16的L0S细分为多个数据集。每个数据集优选地是2x2像素的四

元组。因此，将16x16的L0S细分为8x8布置的非重叠2x2四数据集。该8x8结构定义了8x8的

LOSo

[0091]因此，其定义了四叉树数据结构中下方的下一级。

[0092]此外，在步骤S110,将数据集分组为节点。每个节点包括2x2的数据集分组。

[0093]图7是图6的16x16的LOS的8x8的LOS600的表示，其中，像素已被分组为数据集，每

个数据集是2x2像素的四元组。图7中示出了四个数据集A、B、C、D。为了便于理解，图7中未示

出所有的数据集。

[0094]每个数据集与2x2数据集的节点相关联。在图7所示的示例中，数据集A、B、C和D将

节点定义为2x2的四元组。这被识别为节点N。

[0095]在步骤S112,每个数据集与节点相关联。在优选的实施例中，节点被定义为数据集

的2x2四元组。

[0096]节点N的示例在图7中用虚线框示出，其中包含数据集A、B、C、D。

[0097]在步骤S114,为每个数据集分配单个值，所述单个值指示定义每个数据集的像素

是否包含任何大于阈值的残差信息或非零值。如果执行步骤S108并且发生二进制映射，则

阈值是任何大于“0”的值。在其他实施例中，阈值可以是任何值。

[0098]图8表示将阈值应用于元数据的步骤。在图8中，数据集A、B和D都具有至少一个具

有非零值的元素，因此,A、B和D中的每个具有值“1"。数据集C完全包含0值，因此数据集C被

分配值“0”。因此，图8为图块定义了8x8的LOS,其中，数据定义了是否存在任何其他残差信

息。在图8中，还示出了A、B、C、D的节点N。在替代实施例中，可以确定如果数据集包括大于特

定阈值的多个非零值，则将值“1”分配给该数据集，而如果数据集包括小于特定阈值的多个

非零值，则将值“0”分配给该数据集（如果数据集具有等于阈值的多个非零值,则可以取决

于如何实施过程来分配值“0”或“1”）。例如，如果阈值是2并且如果数据集具有大于2的多个

非零值则将分配值1,则图7中的数据集A、B和C将被分配值“0”，并且图7中的数据集D将被分

配值T。

[0099]本发明的一部分是使用最小量的信息经由树结构来定义元数据的结构。本发明的

一方面在于，如果确定定义节点N的所有四数据集（例如,A、B、C、D）不包含任何残差数据，则

可以将形成该节点的所有像素识别为不包含残差数据。这样，节点就完成了，并且不需要对

树结构进行进一步的高级定义。但是，可以识别该节点是否是不包含任何残差信息的较大

结构的一部分。相反，如果形成节点的四数据集中的任一四数据集包含残差数据，则需要其

他高级数据来定义残差数据出现的位置。

12

CN111684812A说明书10/27页

[0100]在步骤S116,为该结构确定4x4的LOS。与通过从较高级（即16x16的LOS）中分组数

据而创建的8x8的LOS的创建一样,通过将8x8的LOS分组到定义2x2四元组的数据集或子节

点中来创建4x4的LOS,并且基于形成四元组的8x8的LOS元素的值为每个四元组分配二进制

值。在图8所示的示例中，数据结构A、B、C和D在4x4的LOS中定义2x2四元组。

[0W1]以与8x8的LOS相同的方式确定4x4的LOS。基于任何元素是否包含非零值,为数据

结构的每个2x2四元组或后代节点分配二进制值。在图8所示的示例中，由于元素A、B和D具

有非零值，因此整个四元组被分配非零值。对于定义4x4的LOS的所有其他四元组或后代节

点（未示出）重复此过程。与8x8的LOS相似，在替代实施例中，可以确定，如果2x2四元组包含

大于特定阈值的多个非零值，则将值“1”分配给该数据集,而如果2x2四元组包含小于特定

阈值的多个非零值，则将值“0”分配给该2x2四元组（如果2x2四元组具有等于阈值的多个非

零值，则可以取决于如何实施过程来分配值“0”或“1”）。例如，如果阈值是1并且如果2x2四

元组具有大于1的多个非零值则将分配值1,则图8中的由A、B、C和D形成的2x2四元组将被分

配值“1”，并且对于其他2x2四元组依此类推。

[0102]在步骤S118,还基于4x4的LOS值来定义2x2的LOS,这以相同的方式进行。

[0103]从以上过程可以看出，如果2x2的LOS的元素之一被识别为没有残差数据，则在编

码过程中，由于没有要编码的数据，因此可以实质上忽略或绕过帧的四分之一。

[0104]图9是整个结构的示意图。以这样的方式描述数据：定义残差数据（在16x16图块

中）902,然后定义8x8的LOS904、4x4的LOS906和2x2的LOS908。

[0105]在级902、904和906的每个级处的每个2x2四元组用于以分级方式在进行的级中定

义元素。例如，级902处的2x2四元组910用于定义级904处的元素912的值。在2x2四元组910

内，存在至少一个非零值，因此在912处记录值1。然后使用8x8的LOS904处的2x2四元组914

内的值来定义值916。随后，使用4x4的LOS906处的2x2四元组918内的值来定义2x2的LOS

908处的值920。

[0106]如上所述，由于定义了残差数据，因此16x16的LOS是冗余的，因为该信息已存在于

残差数据中。但是，如上所示,在确定8x8的LOS的过程中可以使用16x16的LOS。

[0107]返回图5,在步骤S120,对与图块和稀疏四叉树结构有关的数据进行编码。数据被

编码为值序列，所述值序列定义了2x2的L0S、4x4的L0S、8x8的LOS和残差数据。所述一系列

值被称为流、比特流或字节流。

[0108]因此,稀疏四叉树拓扑被编码到数据流中。在实施例中，可以为节点的每个四元组

（即2x2节点结构）分配节点值以指示该节点是否具有数据。该值被称为T节点值。如果该节

点没有数据，则无需发送与空节点有关的任何其他数据来定义稀疏四叉树结构，因为这种

信息是冗余的。

[0109]例如，如果16x16的图块包含一个不具有稀疏元素的四元组，则该图块的流（包含

稀疏四叉树的拓扑和残差数据）可以按以下方式被编码：

[0110]0100（2x2的LOS的T节点）

[0111]1000（T节点，4x4的LOS）

[0112]0100（T节点，8x8的LOS）

[0113]Resl

[0114]Res2

13

CN111684812A说明书11/27页

[0115]Res3

[0116]Res4

[0117]2x2的LOS的T节点定义只有单个四元组具有残差数据。由于四个四元组中的三个

四元组没有小于2x2的LOS的数据，因此无需为四叉树拓扑定义任何其他数据。因此，由于所

有其他值均为空，所以4x4的LOS和8x8的LOS仅存在单个T节点。最后，定义残差数据值

（Resl、Res2、Res3和Res4）。因此，以稀疏方式提供该结构以去除数据中的任何冗余。

[0118]再举一个示例，如果两个相邻的四元组未被稀疏化，则数据流可以具有以下形式：

[0119]0100（T-节点）

[0120]1000（T-节点）

[0121]0110（T-节点）

[0122]Resl

[0123]Res2

[0124]Res3

[0125]Res4

[0126]Res5

[0127]Res6

[0128]Res7

[0129]Res8

[0130]其中，在上述相同的方式中，可以看出冗余数据没有被编码。

[0131]在实施例中，在T节点的所有值都包含数据的情况下，可以用元数据的单个位替换

T节点的数据，以指示Tessera的所有T节点都具有值1111。在这种情况下，无需对树进行编

码或解码，因为所有节点的值都是恒定的。

[0132]在步骤S122,进行检查以测试在步骤S106产生的所有图块是否已经被编码。如果

仍然剩下要编码的图块，则该过程进入步骤S108,并且针对下一个图块重复上述过程。如果

没有剩下要编码的图块，则该过程终止。

[0133]这样，该过程以稀疏方式定义了对残差数据的例子进行定义的数据结构。

[0134]如上所述的数据结构被认为属于层-0。对于视频数据帧，层-0对应于使用上述过

程创建的所有数据结构的集合，以定义残差数据的例子。

[0135]本发明的一方面在于上述图块和四叉树结构是本文中被称为Tessera的通用抽象

数据类型的特定示例。

[0136]Tessera被定义为用于表示固定大小的编码单元的抽象数据类型。编码单元可以

是NxN的任意大小，诸如如2x2、4x4、8x8、16xl6、32x32等。Tessera用于表示固定大小的

数据块的值和结构。

[0137]Tessera包括固定大小的数据块，并且还包括用于将数据的位置映射在所述数据

块上的结构。如上所述,在实施例中,Tessera包括稀疏四叉树以映射数据的位置。在其他实

施例中，可以使用其他结构，诸如八叉树。

[0138]在实施例中，Tessera还可以包括与编码和解码所需的Tessera的其他方面有关的

其他信息，诸如报头信息。

[0139]如上所述，用于表示残差数据的Tessera被称为残差数据的Tessera。因此，个别的

14

CN111684812A说明书12/27页

Tessera具有参数类型。参数类型定义在Tessera的固定大小的块上存储的内容。在实施例

中，该参数类型是残差信息。在其他实施例中，可以使用其他参数类型，诸如元数据、亮度、

色度等。

[0140]在实施例中，Tessera还可以包括在编码和解码期间对Tessera上保存的值应用的

映射函数。

[0141]在实施例中，当编码Tessera时，可以使用映射函数来计算要编码的值。在NXN块

上的特定位置i处,其中，i处于[0,N2)的范围内，处于所述位置处的元素的值被表示为Ui,并

且要编码的值被表示为Vi。映射函数f()可以用于根据元素的值计算要编码的值，使得

[0142]Vi=f(ui)(2)

[0143]在实施例中，映射函数被设置为识别，使得

[0144]/="3⑶

=%

[0145]在另一实施例中，映射函数被设置为前缀差函数，使得

[0146]/=')、(4)

=(%-%1)

[0147]其中uo=O。

[0148]因此，如下所述，通过选择不同的映射函数，可以对不同的数据进行编码且随后进

行解码。对要编码的数据的选择为利用本文描述的方法的系统提供了进一步的灵活性。

[0149]图10示出了使用映射函数的代表性示例。在图10所示的示例中，该函数是如上所

述的前缀差函数。在其他实施例中，使用其他映射函数。

[0150]在图10中，示出了具有叶节点1002的四叉树1000,所述叶节点映射到残差值1004。

映射函数1006用于根据残差值1004确定要编码的值1008。要编码的值1008可以用作下一映

射函数1010的输入。

[0151]遍历四叉树1000,使得按设置的顺序访问其叶节点，即A、B、C、D、E和F。当访问节点

1002时，将函数1006应用于其值1004以产生要编码的值1008。在实施例中，该函数如等式3

中所定义的，其将要编码的值映射为等于节点的值，即，识别函数。

[0152]当以上面参考图5和步骤S120描述的方式将四叉树拓扑编码到数据流中时，使用T

节点对数据进行编码以避免对冗余数据的编码。

[0153]在实施例中，当使用等式4中定义的前缀差函数时，先前编码的值可以馈入下一个

函数调用1010。前缀差函数允许以高效的方式对具有较大残差值的数据块进行编码。如果

所述数据块包含较大的残差值但残差值之间的变化很小，则前缀差将对这些值之间的差进

行编码。

[0154]参考数据的编码描述了上述方法，并且使用相同的原理解码数据。在实施例中，可

以以相同的方式解码Tessera,其中编码映射函数的反函数用于计算要在特定位置处解码

的值。

[0155]在实施例中,当将等式4中描述的前缀差函数用于编码时，可以将前缀和函数用于

解码。前缀和函数被定义为

15

CN111684812A说明书13/27页

勺