用于编码/解码轻便应用场景表示二进制表示的点序列的方法和装置

摘要

提供一种方法和装置，用于选择性地编码/解码点序列以最大化轻便应用场景表示(LASeR)二进制流的比特效率。该点序列编码方法包括步骤：对于每一个点序列，(a)选择指数—哥伦布(EG)编码和固定长度(FL)编码方案之一；(b)当选择FL编码方案时，使用FL编码方案编码点序列以产生二进制流；和(c)当选择EG编码方案，使用EG编码方案编码点序列以产生二进制流。该二进制流包括用于指示选择哪种编码方案的标志，以及当选择EG编码方案时利用其可以最有效地进行EG编码的参数k。根据该编码方法，能够对LASeR点序列进行有效地编码并且在解码过程中不会将大量的额外开销引入解码器(终端)。

说明书

技术领域

本发明涉及一种用于有效地编码/解码点序列的方法和装置，并且尤其涉及一种有效地编码/解码轻便应用场景表示(lightweight application scenerespresentation，LASeR)点序列的方法和装置。

背景技术

LASeR是一种多媒体内容格式，被定义用于为资源受限的设备诸如移动电话提供简单的多媒体服务。LASeR可以用于诸如地图(map)应用、动画和2维矢量图的应用。这些应用工作具有大量的点数据，因此需要一种有效的编码点数据的方法。为此，应当考虑LASeR的两个主要因素：效率高的二进制表示以及小的解码器存储器。

发表于2004年七月的国际标准化组织/国际电工委员会(ISO/IEC)14496-20委员会草案(CD)的LASeR正文提出一种固定长度(FL)的编码方案用来编码LASeR点数据。根据FL编码方案，当点数，nbPoint，小于3个时，对点数据本身进行解码。当数目，nbPoint，是3或更多时，检查所有的点序列以确定它们的动态范围，并且使用自检测结果导出的固定长度对点序列进行编码。该方法可以很简单的实现。然而，不仅需要十比特的额外开销以给每一个点序列指定长度字段，而且也将许多比特不必要地分配给长度字段后的数据字段。

熵编码和解码可以用于有效地压缩和还原图像数据。信息熵编码是一种考虑了数据能够取的不同值，并且使用小比特数编码经常出现的值。

有各种熵编码方案，这些方案能够粗略分成具有编码表的方案和不具有编码表的方案。哈夫曼编码方案是使用编码表的典型方案。根据哈夫曼编码方案，可以获得最佳压缩比。然而，必须传送解码表，并且在解码器(终端)中有处理开销在于，每次解码点数据时必须访问存储位置。因为LASeR需要具有最小复杂度的小的存储，所以使用编码表的哈夫曼编码方案不适合编码点数据。

作为另外的熵编码方案，即不使用编码表的编码方案，有算术编码和指数哥伦布(exponential golomb，EG)编码方案。算术编码是一种效率高的编码方法，但是由于缺乏差错恢复(error resilience)而很难用于LASeR。

另一方面，EG编码方案具有一些适合于LASeR的特性。根据EG编码方案，可以选择参数k，其给编码器带来低开销并且对于特定的分布是适合的。另外，可以很容易将EG编码转换成可变长度的编码(variable-length coding，VLC)以便增加差错恢复功能(请参见“增加差错恢复的可逆VLC”，由国际标准组织/国际电工委员会联合技术委员会(JTC)1/部门委员会(SC)29/工作组(WG)1(国际电信联盟-无线电通讯标准化部门、研究组8(ITU-T SG8)制定。还有另外一个优点是低的解码器开销。因为解码过程能够仅通过相加(addition)和比特移位操作进行，所以能够将EG编码方案应用到诸如移动电话的低端装置而不引入高开销。

发明内容

本发明针对一种编码点序列的方法和装置，其选择点序列编码方案以提高LASeR二进制表示的压缩效率；编码指示选择哪种编码方案的标志，和当选择EG编码时编码用于EG编码的参数k的值；和与LASeR二进制流一起发送该标志和参数k值。

本发明也针对一种解码点序列的方法和装置，其从编码的LASeR流提取指示使用了哪一种编码方案的标志；基于该标志确定解码方案；当选择了EG解码方案时提取参数k；和解码编码的LASeR流。

技术方案

本发明提出一种选择性编码/解码点序列的方法和装置，以便最大化LASeR二进制表示的比特效率。

本发明的一个方面提供一种用于编码LASeR点序列的方法，包括步骤：对于每一个点序列，(a)选择指数-哥伦布(EG)编码和固定长度(FL)编码方案之一；(b)当选择FL编码方案时，使用FL编码方案编码点序列以产生二进制流；和(c)当选择EG编码方案，使用EG编码方案编码点序列以产生二进制流，其中，该二进制流包括用于指示选择哪种编码方案的标志，以及当选择EG编码方案时利用其可以最有效地进行EG编码的参数k。

本发明的另一方面提供一种用于解码LASeR二进制流的方法，包括步骤：从该LASeR二进制流中提取指示使用了哪种编码方案的信息，并且基于所提取的信息而确定EG解码和FL解码方案之一；和根据所确定的解码方案解码该LASeR二进制流。

本发明的另一方面提供一种服务器，包括：编码装置，用于通过执行上述编码方法而编码表示场景描述的LASeR点序列，以产生编码的LASeR场景描述流；复用装置，用来复用该编码的LASeR场景描述流和组成LASeR场景的其它元素流，以产生复用的LASeR二进制流；和发送装置，用来将该复用的LASeR二进制流发送到用户终端。

本发明的另一方面提供一用户终端，包括：接收装置，用于接收LASeR二进制流；去复用装置，用于从所接收的LASeR二进制流去复用并且输出LASeR场景描述流和其它元素流；解码装置，用于通过执行上述解码方法而解码从该去复用装置输出的LASeR场景描述流，以产生可以单独访问的多个解码的LASeR访问单元；附加的解码装置，用于解码从该去复用装置输出的其它元素流；场景树管理器，用于从解码的访问单元产生场景树；和LASeR表示器，用于使用所产生的场景树和解码的其它元素流提供LASeR服务。

本发明的另一方面提供一种编码的LASeR点序列的数据流的数据结构，包括：用于指示使用FL和EG编码方案哪一个的标志；和当该标志具有指示EG编码方案的值时，参数k，利用该参数k可以最有效地执行EG编码。

有益效果

如上所述，当根据本发明的方法编码/解码点序列时，能够获得6％-17％之间的压缩增益。因此当将依据本发明的编码方法用于图像、动画和矢量图时，使用具有低复杂度的解码器获得相当好的压缩效率。

附图说明

图1示出了依据本发明用于选择性地编码/解码LASeR点序列的系统的框图；

图2示出了依据本发明的编码点序列的过程的流程图；和

图3示出了依据本发明的解码点序列的过程的流程图。

具体实施方式

在下文中，将详细描述本发明实例性实施方式。然而，本不局限于下面公开的实例性实施方式，而是可以以不同形式实现。因此，对于本领域中的技术人员来说，提供本发明的实例性实施方式来完全公开本发明，以及告知本发明的保护范围。

图1示出了依据本发明用于选择性地编码/解码LASeR点序列的系统的框图。如图1中所示，服务器系统10包括LASeR场景编码器11、简单集合格式(simple aggregation format，SAF)复用器12和发送器13。LASeR场景编码器11接收关于场景的场景描述数据，例如，可缩放矢量图形(scalablevector graphics，SVG)数据、LASeR可扩展标记语言(XML)数据等，并且产生压缩(编码的)LASeR场景描述流。将依据本发明选择性地编码LASeR点序列的方法应用于LASeR场景编码器11。

SAF复用器12接收LASeR场景描述流以及其它组成LASeR场景的元素流，例如视频、声频、图像、字体、元数据流等，并且产生复用LASeR二进制流。该发送器13使用网络协议(IP)、无线网络、码分多址(CDMA)网络等将LASeR二进制流发送到用户终端20。

用户终端20包括接收器21、SAF去复用器22、LASeR场景解码器23、其它元素解码器24、场景树管理器25和LASeR表示器(render)26。SAF去复用器22接收由接收器21传输的数据流并且对其去复用以产生LASeR场景描述流和其它元素流。该LASeR场景解码器2 3接收从SAF去复用器22输出的该LASeR场景描述流并且产生解码访问单元。解码访问单元是可以独立访问数据的一部分。依据本发明的编码LASeR点序列的方法可以应用于LASeR解码器23。

另一元素解码器24解码除LASeR描述流之外的另外的元素流，例如视频、声频、图像、字体、元数据流等。场景管理器25接收解码的访问单元并且产生场景树。该场景树指的是场景描述数据的层次(hierarchy)，其示出了组成LASeR场景对象的时间/空间位置。该LASeR表示器26接收场景树和从其它元素解码器24输出的各种形式的其它元素流，并且提供给用户LASeR服务。

图2示出了依据本发明的编码点序列过程的流程图。对于每一个点序列，选择FL(固定长度)编码和EG(指数哥伦布)编码方案之一(步骤210)。具体地，在示例性实施方式中，在进行了EG编码和FL编码方案两者之后，选择产生较小比特数的解码方案。当选择了FL编码方案时，把编码选择标志设置为‘0’(flag＝0)(步骤220)。然后，使用FL编码方案编码点序列(步骤230)。

可以依据以下过程进行FL编码。

当假设一点序列包含(n+1)个点：(x₀，y₀)，(x₁，y₁)，...，(x_n，y_n)，和

1)当点序列中的点数为2或更少时，

i)计算并编码利用之可以编码x₀，y₀ x₁和y₁的比特的最小数目，和

ii)使用上述计算数目的比特编码点坐标(x₀，y₀)和(x₁，y₁)；或

2)当点序列中的点数为3或更多时：

i)计算并编码利用之可以编码第一点(x₀，y₀)的比特的最小数目bits；

ii)使用上述计算数目的比特编码点(x₀，y₀)，

iii)计算dx₁₀，...，dx_nn-1(此处，dx_nn-1＝x_n-x_n-1)，然后计算出对它们进行编码需要的比特数目，bitsx，

iv)计算dy₁₀，...，dy_nn-1(此处，dy_nn-1＝y_n-y_n-1)，然后计算出对它们进行编码需要的比特数目，bitsy，

v)编码该数目bits，bitsx和bitsy，和

vi)对dx₁₀，dy₁₀，...，dx_nn-1，dy_nn-1进行编码

另一方面，当选择了EG方案，将编码选择标志设置为′1′(flag＝1)(步骤240)。随后，计算并编码参数k，利用该参数能够最有效地进行EG编码(步骤250)。接着依据EG编码方案编码点序列(步骤260)。

EG编码，作为熵编码方案之一，具有系统构造机理，通过将较短的代码分配给小的数量对其中出现小的数量的点序列的压缩有利。哈夫曼编码方案，作为另一个熵编码方案，需要指定符号和代码号(code number)之间关系的代码表。此外，应当将代码表存储在用户终端。相反，EG编码方案采用系统构造方法，并且因此不需要编码表。因此，EG编码方案更适合于于LASeR。该EG编码方案不依据准确的符号统计分配代码词。相反地，EG编码方案调整参数k，并且因此能够匹配几何分布的各种散布(dispersion)。根据EG编码方案，如下构造每一个代码：

[M个零][1][INFO]

此处M表示前导零的数目，而INFO表示承载信息的(M+k)比特的后缀偏移值。前导零以及其后的“1”作为分割每一编码的前缀码。代码号CodeNum如下确定：

公式1

CodeNum＝2^M+k+INFO-2^k

因为INFO的值并不影响前导零的长度，所以通过忽略公式1中的INFO项来计算前导零的数目M，如公式2中所示：

公式2

M＝[log₂(CodeNum+2^k)]-k

并且，可以根据由公式2推导出的公式3来计算INFO的值：

公式3

INFO＝CodeNum+2^k-2^M+k

作为一个例子，下表1示出了针对参数k＝0，1，2，和3配置的11个EG编码。

表1

 CodeNum Code(k＝0) Code(k＝1) Code(k＝2) Code(k＝3) 0 1 10 100 1000 1 010 11 101 1001 2 011 0100 110 1010 3 00100 0101 111 1011 4 00101 0110 01000 1100 5 00110 0111 01001 1101 6 00111 001000 01010 1110 7 0001000 001001 01011 1111 8 0001001 001010 01100 010000 9 0001010 001011 01101 010001 10 0001011 001100 01110 010010

如表1所示，编码按照逻辑顺序递增。

因为EG编码仅具有不带符号的代码号，所以具有符号的EG编码应当被映射到不带符号的EG编码。从比特流中检索出不带符号的EG编码的代码号CodeNum，并且将其映射到带符号的EG编码，由此被解析。

If(CodeNum is 0)signed code＝0；

else if(CodeNum is even)signed code＝-CodeNum/2；

else if(CodeNum is odd)signed code＝(CodeNum+1)/2；

下表中说明了将不带有符号的代码号映射到带有符号的代码号的例子。

表2

不带有符号的EG代码号0 1 2 3 4 5 6 7 8 9...带有符号的EG代码号0 1 -1 2 -2 3 -3 4 -4 5...

在该示例性实施方式中，EG编码可以根据以下步骤来实现：

当假设点序列包含(n+1)个点(x₀，y₀)、(x₁，y₁)...(x_n，y_n)时，

(1)计算并编码可以利用其编码(x₀，y₀)的比特的最小数目；

(2)使用该最小数目个比特编码点(x₀，y₀)；和

(3)对于除点(x₀，y₀)之外的每一个点，将在前一个点和当前点之间的x-坐标和y-坐标差值数据映射到EG代码号并且通过使用EG代码号和参数k值产生相应于x-坐标和y-坐标差值数据的EG代码字，由此实现EG编码。

具体地，执行以下步骤以对点(x_i，y_i)进行编码。

(i)根据以下规则将x_i和x_i-1之间的差值，“diffx”映射到不带符号的EG代码号CodeNum：

If(diffx＞＝0)CodeNum＝diffx*2-1；

else CodeNum＝|diffx|*2。

(ii)M表示前导零的数目，由公式2来计算。

(iii)记录M个“0”比特。

(iv)记录一个“1”比特。

(v)由公式3计算承载信息的后缀偏移“INFO”。

(vi)将INFO记录到(M+k)比特中；

(vii)根据以下规则将y_i和y_i-1之间的差值，“diffy”映射到不带符号的EG代码号CodeNum：

If(diffy＞＝0)CodeNum＝diffy*2-1；和

else CodeNum＝|diffy|*2。

(viii)由公式2来计算前导零的编号“M”，

(ix)记录M个“0”比特。

(x)记录一个“1”比特。

(xi)由公式3计算“INFO”。

(vi)将INFO记录到(M+k)比特中。

图3是依据本发明的解码点序列的处理的流程图。如图3所示，对于LASeR二进制流，确定FL解码方案和EG解码方案之一(步骤310)。该确定通过读入包含在LASeR二进制流中的编码选择标志(flag)来进行。如上所述，因为包含在LASeR二进制流中的编码选择标志(flag)表明使用哪一个方案来编码当前点序列，所以基于该标志来确定解码方案。

当确定了FL解码方案时，使用FL解码方案解码点序列(步骤320)。根据以下处理实现FL解码方案：

当假设将LASeR二进制流解码成点序列(x₀，y₀)、(x₁，y₁)...(x_n，y_n)时，

(1)从LASeR二进制流中提取出点序列中的点数；

(2)从LASeR二进制流中提取出点的x-坐标值和y-坐标值所需要的比特数“bits”。

(3)当点数为2或更少时，通过读取“bits”个比特来提取x₀，y₀，x₁，和y₁的每个值；和

(4)当点数为3或更多时：

(i)通过读取“bits”个比特来提取x₀，y₀的每个值；

(ii)提取x-坐标的差值dx所需要的比特数“bitsx”和y-坐标的差值dy所需要的比特数“bitsy”；

(iii)i＝1；

(iv)通过读取“bitsx”个比特和“bitsy”个比特而分别提取dx和dy，然后计算x_i＝x_i-1+dx和y_i＝y_i-1+dy；和

(v)(n-1)次地进行i值加1(i＝i+1)并且执行前一步骤(iv)。

另一方面，当确定EG解码方案时，从LASeR二进制流提取用于EG解码的参数k(步骤330)，并且使用提取的参数k进行EG解码(步骤340)。

在一个示例性实施例中，可以根据以下处理进行EG解码：

当假设将LASeR二进制流解码成点序列(x₀，y₀)、(x₁，y₁)...(x_n，y_n)时，

(1)从LASeR二进制流中提取出点序列的点数、用于编码点的比特数“bits”和参数k；

(2)读取比特的“bits”个比特，然后解码第一个点坐标(x₀，y₀)；

(3)从LASeR二进制流中读取出与前一个点和当前点之间的每个x-坐标和y-坐标差值数据对应的EG代码字，并使用参数k对其进行解码，以及将所解码的差值数据与前一个点的坐标词相加用以计算当前点的坐标；和

(4)把前一个步骤(3)执行除第一个点外的点数那么多次。

具体地，执行以下步骤来解码点(x_i，y_i)：

(i)每次读取一个比特直到检测到“1”，并且将所读出的比特的总数目设置为M；

(ii)丢弃所读取的“1”；

(iii)读取(M+k)个比特数并且将之设置为INFO；

(iv)计算CodeNum＝2^M+k+INFO-2^k；

(v)由CodeNum计算出dx；

(vi)计算x_i＝x_i-1+dx；

(vii)逐一读取比特直到检测到″1″，并将所读出比特的总数目设置为M；

(viii)丢弃所读取的″1″；

(ix)读取(M+k)个比特并将其设置为INFO；

(x)计算CodeNum＝2^M+k+INFO-2^k；

(xi)由CodeNum计算dy；并且

(xii)计算y_i＝y_i-1+dy。

依据本发明的LASeR二进制流解码过程可以用以下伪码的句法和语义表达的语义来表达：

句法：

decodingPointSequence{

nbPoints＝Read(lenBits)；

flag＝Read(1)；

if(flag＝＝0){

if(nbPoints＜3){

bits＝Read(5)；

for(int i＝0；i＜nbPoints；i++){

x[i]＝Read(bits)；

y[i]＝Read(bits)；

 }

 }

else{

bits＝Read(5)；

x[0]＝Read(bits)；

y[0]＝Read(bits)；

bitsx＝Read(5)；

bitsy＝Read(5)；

for(int i＝1；i＜nbPoints；i++){

dx＝Read(bitsx)；

dy＝Read(bitsy)；

x[i]＝dx+x[i-1]；

y[i]＝dy+y[i-1]；

}

}

}

else{

bits＝Read(5)；

x[0]＝Read(bits)；

y[0]＝Read(bits)；

kvalue＝Read(4)；

for(i＝1；i＜nbPoints；i++){

1_zero＝0；

while (Read(1)＝＝0)1_zero++；

Mvalue＝1_zero；

Read(1)；

INFO＝Read(Mvalue+kvalue)；

CodeNum＝2^M+kvalue+INFO-2^kvalue；

if(CodeNum＝＝0)dx＝0；

else if(CodeNum＝＝even)dx＝-CodeNum/2；

else if(CodeNum＝＝odd)dx＝(CodeNum+1)/2；

x[i]＝dx+x[i-1]；

1_zero＝0；

while(Read(1)＝＝0)1_zero++；

Mvalue＝1_zero；

Read(1)；

INFO＝Read(M value+kvalue)；

CodeNum＝2^M+kvalue+INFO-2^kvalue；

if(CodeNum＝＝0)dy＝0；

else if(CodeNum＝＝even)dy＝-CodeNum/2；

else if(CodeNum＝＝odd)dy＝(CodeNum+1)/2；

y[i]＝dy+y[i-1]；

}

}

}

语义：

flag-标志，指示FL编码(flag＝0)或EG编码(flag＝1)。

kvalue-用于EG编码的参数，其根据几何分布而变化。例如，当k值增加时，几何分布的斜率变得平缓。

Mvalue-前导零的数目。

CodeNum-代码号。

dx-当前点和前一个点的x-坐标的差值。

dx＝x[i]-x[i-1]

dy-当前点和前一个点的y-坐标的差值。

dy＝y[i]-y[i-1]

INFO-具有有关dx或dy信息的值。

作为示例性实施方式，依据本发明的LASeR二进制流的解码处理可以使用如下写成伪码的句法来表示：

句法：

decodingPointSequence{

nbPoints＝Read(lenBits)；

flag＝Read(1)；

if(flag＝＝0){

if(nbPoints＜3){

bits＝Read(5)；

for(int i＝0；i＜nbPoints；i++){

x[i]＝Read(bits)；

y[i]＝Read(bits)；

}

}

else{

bits＝Read(5)；

x[0]＝Read(bits)；

y[0]＝Read(bits)；

bitsx＝Read(5)；

bitsy＝Read(5)；

for(int i＝1；i＜nbPoints；i++){

dx＝Read(bitsx)；

dy＝Read(bitsy)；

x[i]＝dx+x[i-1]；

y[i]＝dy+y[i-1]；

}

}

}

else{

kvalue＝Read(4)；

bits＝Read(5)；

x[0]＝Read(bits)；

y[0]＝Read(bits)；

for(i＝1；i＜nbPoints；i++){

1_zero＝0；

while(Read(1)＝＝0)1_zero++；

Mvalue＝1_zero；

Read(1)；

INFO＝Read(Mvalue+kvalue)；

CodeNum＝2^M+kvalue+INFO-2^kvalue；

if(CodeNum＝＝0)dx＝0；

else if(CodeNum＝＝even)dx＝-CodeNum/2；

else if(CodeNum＝odd)dx＝(CodeNum+1)/2；

x[i]＝dx+x[i-1]；

1_zero＝0；

while(Read(1)＝＝0)1_zero++；

Mvalue＝1_zero；

Read(1)；

INFO＝Read(Mvalue+kvalue)；

CodeNum＝2^M+kvalue+INFO-2^kvalue

if(CodeNum＝＝0)dy＝0；

else if(CodeNum＝＝even)dy＝-CodeNum/2；

else if(CodeNum＝＝odd)dy＝(CodeNum+1)/2；

y[i]＝dy+y[i-1]；

}

}

}

作为示例性实施例，依据本发明的LASeR二进制流的解码处理可以使用如下用句法描述性语言(SDL)代码表达的句法来表示：

句法：

decodingPointSequence{

uivlc5 nbPoints；

uint(1)flag；

if(flag＝＝0){

if(nbPoint＜3){

uint(5)bits；

for(int i＝0；i＜nbPoints；i++){

uint(bits)x[i]；

uint(bits)y[i]；

}

}else{

uint(5)bits；

uint(bits)x[0]；

uint(bits)y[0]；

uint(5)bitsx；

uint(5)bitsy；

for(int i＝1；i＜nbPo int s；i++){

uint(bitsx)dx；

uint(bitsy)dy；

x[i]＝dx+x[i-1]；

y[i]＝dy+y[i-1]；

}

}

}

else{

uint(4)kvalue；

uint(5)bits；

uint(bits)x[0]；

uint(bits)y[0]；

int XMvalue，YMvalue＝0；

int CodeNum＝0；

int Diff＝0；

for(i＝1；i＜nbPoints；i++){

//计算X点

do{

bit(1)bitX；

XMvalue++；

}while(bitX＝＝0)；

const bit(1)endX＝1；

uint(XMvalue+kvalue)INFO_dx；

CodeNum＝GetCodeNum(kvalue，XMvalue，INFO_dx)；

Diff＝GetDiff(CodeNum)；

x[i]＝x[i-1]+Diff

//计算Y点

do{

unit(1)bitY；

YMvalue++；

}while(bitY＝＝0)；

const bit(1)endY＝1；

uint(YMvalue+kvalue)INFO_dy；

CodeNum＝GetCodeNum(kvalue，YMvalue，INFO_dy)；

Diff＝GetDiff(CodeNum)；

Y[i]＝y[i-1]+Diff

}

}

}

uint GetCodeNum(int k，int Mvalue，int INFO){

return 2(^k+Mvalue)+INFO-2^k；

}

int GetDiff(int CM){

if((CM％2)＝＝0)return-1*CM/2；

else return CM//2；

}

在上述的语法中，″％″表示模操算符、而算符″//″表示正数相除并且圆整余数。例如1//2的值是1，3//2的值是2，和5//2的值是3。

本发明的上述描述可以作为存储计算机程序的可读计算机介质来提供。该介质可能是软盘、硬盘、光盘(CD)只读存储器(ROM)、闪存卡、可编程序只读存储器(PROM)、随机存取存储器(RAM)、ROM、磁带、等等。通常该可以使用任意程序设计语言来编制该计算机程序，例如C、C++、或JAVA。

尽管本发明已经通过参考其中的特定的示例性实施方式对本发明进行了说明和描述，对于本领域中的普通技术人员来说，其中在形式和细节上可以有各种改变而不会超出由附加权利要求限定的本发明的精神范围。