CN104244007A - 基于任意形状匹配的图像压缩方法和装置 - Google Patents

Abstract

本发明的最基本的技术特征是在对当前编码单元进行编码时，按照一种或几种预先规定的匹配模式，在已经完成编码的历史像素（重构像素）集合中进行搜索，逐个找到多个与当前编码中编码单元的像素样值相匹配的最优的匹配串（块）。每个匹配串（块）可以具有任意形状并且可以用两个基本匹配参数，即匹配位置和匹配大小来表征。

Description

基于任意形状匹配的图像压缩方法和装置

技术领域

本发明涉及一种数字视频压缩编码及解码系统，特别是包含连续色调图像和非连续色调图像的数字复合图像和视频的编码及解码的方法和装置。 

  

背景技术

随着云-移动计算、智能网络电视（IPTV）、无线显示连接（WIFI Display等）的发展与普及，多计算机之间、计算机主机与其他数字设备（如智能电视、智能手机、平板电脑等）之间及各种各类数字设备之间的互联已经成为现实并越来越成为一种主流趋势。这使得服务器端（“云”或“云片”）到用户端的实时屏幕传输成为当前的迫切需求。由于需要传输的屏幕视频数据量很大，以平板电脑2048x1536像素分辨率且60帧/秒刷新率的24位真彩色屏幕图像为例，需要传输的数据达每秒2048x1536x60x24=4320兆比特，如此多的数据要想在当前的网络条件下实现实时传输是不可能的，因此有效的数据压缩必不可少。 

以计算机屏幕图像为代表的数字复合图像和视频的突出特点是包含文字、图形、线段及自然图像。其中，文字、图形、线段一般由计算机生成，具有非连续色调的特性，而自然图像是由摄像机拍摄得到的，具有连续色调的特性。当前，对自然图像和视频的压缩编码已经比较成熟，有许多既定的标准可采用。这些标准基本采用预测编码与变换编码及量化编码结合的混合编码的框架，但他们对屏幕图像的压缩效果较差，必须寻求更适合于屏幕图像压缩的算法来实现有效压缩。 

充分利用计算机屏幕图像的特点，对计算机屏幕图像进行超高效率的压缩，也是正在制定中的最新国际视频压缩标准HEVC（High Efficiency Video Coding）的一个主要目标。 

屏幕图像的数字视频信号的自然形式是图像的序列。一幅图像通常是由若干像素组成的矩形区域，如果一个数字视频信号每秒有50幅图像，那么一个30分钟的数字视频信号就是一个由30x60x50＝90000幅图像组成的视频图像序列，有时也简称为视频序列或序列。对数字视频信号进行编码就是按照一定顺序对一幅一幅图像进行编码。在任一时刻，正在编码中的那一幅图像称为当前编码图像。同样，对数字视频信号的压缩码流进行解码就是按照同样顺序对一幅一幅图像的压缩码流进行解码。在任一时刻，正在解码中的那一幅图像称为当前解码图像。当前编码图像或当前解码图像都统称为当前图像。 

在几乎所有视频图像编码的国际标准如MPEG-1/2/4，H.264/AVC以及HEVC中，对一幅图像进行编码时，都是把一幅图像划分成若干块MxM像素的子图像，称为“编码单元（Coding Unit简称CU）”，以CU为基本编码单位，对子图像一块一块进行编码。常用的M的大小是8，16，32，64。因此，对一个视频图像序列进行编码就是对各个编码单元依次进行编码。同样，解码时也是对各个编码单元依次进行解码，最终重构出整个视频图像序列。 

为适应一幅图像内各部分图像内容与性质的不同，有针对性地进行最有效的编码，一幅图像内各CU的大小可以是不同的，有的是8x8，有的是64x64，等等。为了使不同大小的CU能够无缝拼接起来，一幅图像总是先划分成大小完全相同具有NxN像素的“最大编码单元（Largest Coding Unit简称LCU）”，然后每个LCU进一步划分成1个或4个或16个或64个大小完全相同的CU。例如，一幅图像先划分成大小完全相同的64x64像素的LCU（N＝64）。然后，其中有些LCU本身就是一个64x64像素的CU，也就是对1个64x64像素的CU（称为深度为1的CU，一个CU有NxN个像素，这一个CU组成一个深度为1的划分）进行编码。有些LCU则被划分成4个32x32像素的CU，也就是对4个32x32像素的CU（称为深度为2的CU，每个CU有 x个像素，这4个CU组成一个深度为2的划分）进行编码。还有一些LCU则被划分成16个16x16像素的CU，也就是对16个16x16像素的CU（称为深度为3的CU，每个CU有x个像素，这16个CU组成一个深度为3的划分）进行编码。另外一些LCU则被划分成64个8x8像素的CU，也就是对64个8x8像素的CU（称为深度为4的CU，每个CU有x个像素，这64个CU组成一个深度为4的划分）进行编码。 

在对一个LCU进行编码时，首先对深度为1的划分进行编码，其次对深度为2的划分（即此划分的所有CU）进行编码，这样依次对不同深度的划分进行编码，一直到深度达到一个预先设定的最大深度D，也就是相应的CU的大小达到最小值x为止。在完成了对D个不同深度的划分的全部编码后，从这些不同深度的划分的编码中，根据率-失真性能，选择一个最优的深度即一种最优的MxM像素CU的划分对该LCU进行最终的编码。 

每个LCU也可以用另一种方式划分成树状结构的多个大小不一定相同的CU。因此，LCU也称为“编码树单元（Coding Tree Unit简称CTU）”。在本发明专利申请中，LCU与CTU是同义词。与CTU同样大小的CU称为深度D为0（D=0）的CU。把一个D=0的CU四等分得到的四分之一大小的CU称为深度D为1（D=1）的CU。把一个D=1的CU再四等分得到的大小更小的CU称为深度D为2（D=2）的CU。把一个D=2的CU再四等分得到的大小更小的CU称为深度D为3（D=3）的CU。把一个D=3的CU再四等分得到的大小更小的CU称为深度D为4（D=4）的CU。例如，一幅图像先划分成大小完全相同的64x64像素的LCU（N＝64）。其中一个LCU可以由2个32x32像素的D=1的CU、6个16x16像素的D=2的CU和8个8x8像素的D=3的CU构成。这样16个成树状结构的CU构成一个CTU。其中另一个LCU可以由3个32x32像素的D=1的CU和4个16x16像素的D=2的CU构成，这样7个成树状结构的CU也构成一个CTU。 

对一幅图像进行编码，就是依次对一个一个CTU中的一个一个CU进行编码。在任一时刻，正在编码中的CU称为当前编码CU。对一幅图像进行解码，也是按照同样的顺序依次对一个一个CTU中的一个一个CU进行解码。在任一时刻，正在解码中的CU称为当前解码CU。当前编码CU或当前解码CU都统称为当前CU。 

像素有各种格式，如：1个像素由1个红色分量（component）、1个绿色分量、1个蓝色分量组成的RGB像素格式；1个像素由1个亮度Y分量、1个色度U分量、1个色度V分量组成的YUV4:4:4像素格式；左右相邻的2个像素由2个亮度Y分量、1个色度U分量、1个色度V分量组成的YUV4:2:2像素格式；左右上下相邻按2x2空间位置排列的4个像素由4个亮度Y分量、1个色度U分量、1个色度V分量组成的YUV4:2:0像素格式。一个分量一般用1个8~16比特的数字来表示。YUV4:2:2像素格式和YUV4:2:0像素格式都是对YUV4:4:4像素格式施行色度分量的下采样得到。通称为YUV的色彩格式实际包括多种色彩格式，如YCbCr色彩格式。编码或解码时的最基本元素可以是一个像素，也可以是一个像素分量。作为编码或解码的最基本元素的一个像素或一个像素分量统称为一个像素样值（sample），有时也通称为一个像素值，或简单地称为一个样值。对一个CU进行编码时，可以把一个CU分成3个分量平面（G平面、B平面、R平面或Y平面、U平面、V平面），对3个分量平面分别进行编码；也可以把一个像素的3个分量捆绑组合成一个3元组，对由这些3元组组成的CU整体进行编码。前一种像素及其分量的排列方式称为图像（及其CU）的平面格式（planar format），而后一种像素及其分量的排列方式称为图像（及其CU）的叠包格式（packed format）。 

在本发明专利申请中，“像素样值”、“像素值”、“样值”是同义词，根据上下文，可以明确是表示“像素”还是表示“一个像素分量”或者同时表示两者。如果从上下文不能明确，那么就是同时表示两者。 

包括屏幕图像在内的各种类型图像和视频序列的编码技术中，使用最多的现有技术的编码方法的流程示意图如图1所示。现有技术的编码方法包括如下步骤： 

1)        读入一个大小为NxN像素的最大编码单元即LCU的原始像素；

2)        把变量M的初始值设为N，也就是准备好首先对大小为MxM＝NxN像素的当前编码单元CU的划分进行编码；

3)        对1个MxM像素的CU进行基于邻近像素样值的帧内预测编码和基于方块（block）的帧间（即当前编码帧与以前已编码帧之间）预测编码，统称为预测编码，产生出（1）预测残差和（2）预测模式和运动矢量。预测编码中需要尝试多种帧内预测模式和多种帧间预测模式（统称为预测模式）。每一种预测模式都会产生相应的预测残差并经历后续步骤4）、5）、6）、7）的运算；

4)        对步骤3）的编码结果之一预测残差进行变换编码，产生出变换系数。变换编码是可选的，也就是如果变换编码达不到更好的数据压缩效果，就不进行变换编码；

5)        对变换系数（在前一步骤进行了变换编码的情形）或预测残差（在前一步骤不进行变换编码的情形）进行量化编码，产生量化变换系数或量化预测残差。在无损编码的情形，量化编码运算是等同运算，不产生任何实际的量化效果；

6)        对步骤3）~5）的编码结果进行所述编码的逆运算，即初步重构出所述CU的像素，用于后续步骤8）的率-失真成本（Rate-distortion cost）计算，并在后续步骤11）确定了对当前编码LCU的最优划分之后，对最优划分的所有初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的各重构CU的像素放入历史像素（重构像素）暂存区，用作后续预测编码和重构的参考像素。由于编码可能是有损的，重构像素并不一定等于输入原始像素；

7)        对步骤3）的编码结果之二预测模式和运动矢量以及步骤5）的量化编码结果即量化变换系数和量化预测残差进行熵编码并产生压缩码流的比特率。熵编码也包括对预测模式、运动矢量、量化变换系数、量化预测残差等熵编码对象的样值先进行基于1维或2维邻近样值的差分编码或索引编码，以去除样值之间的相关性，提高熵编码的效率；

8)        从原始像素、重构像素、压缩码流的比特率或者比特率估计值，计算得到率-失真成本，根据率-失真性能选择此CU的最优预测模式并暂存此CU的压缩码流数据；

9)        判断是否已经完成对所有MxM像素CU的编码，如果是，则顺序执行下一步骤，否则跳至步骤3）开始下一个MxM像素CU的编码；

10)    判断是否M已经达到预先设定的最小值，如果是，则顺序执行下一步骤，否则，把M减半，然后跳至步骤3）开始下一个深度的划分中所有MxM像素CU的编码；

11)    从已完成的多个不同深度（不同大小MxM像素的CU）的划分的编码结果中，根据率-失真性能选择一个最优的MxM像素的CU的划分并输出该划分相应的压缩码流数据；

12)    判断是否已完成所有LCU的编码，如果是，则结束编码，否则回到步骤1)，开始对下一个LCU的编码。

现有技术的解码方法的流程示意图如图2所示。现有技术的解码方法包括如下步骤： 

1)        读入部分压缩码流数据；

2)        进行一个编码单元即CU的熵解码，得到该CU的头信息和数据信息。头信息主要包括该CU采用基于邻近像素样值的帧内预测还是和基于方块的帧间预测，是否进行逆变换解码。熵解码也包括对预测模式、运动矢量、量化变换系数、量化预测残差等熵解码对象的基于1维或2维邻近样值的差分解码或索引解码；

3)        对量化变换系数或量化预测残差进行反量化解码，产生出变换系数或预测残差；

4)        如果前一步骤产生的是变换系数，则进行逆变换解码，产生出预测残差，否则，顺序执行下一步骤；

5)        进行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，统称为预测解码，产生出初步的重构像素；

6)        对初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的重构CU的像素放入历史像素（重构像素）暂存区，用作后续预测解码的参考像素；

7)        输出重构CU的像素；

8)        判断是否已经完成对一个LCU中所有CU的压缩码流数据的解码，如果是，则顺序执行下一步骤，否则回到步骤1)，开始对下一个CU的解码；

9)        判断是否已经完成对所有LCU的压缩码流数据的解码，如果是，则结束解码，否则回到步骤1)，开始对下一个LCU的解码。

现有技术的编码装置示意图如图3所示。整个编码装置由以下模块组成： 

1)        可以存储至少一个编码单元即CU的像素的存储模块；

2)        预测编码模块，对输入像素样值施行基于邻近像素的帧内预测编码和基于方块（block）的帧间预测编码，并输出（1）预测残差和（2）预测模式和运动矢量；

3)        变换模块。对预测残差施行变换运算，输出变换系数。对某些类型的屏幕图像像素，变换运算并不能起到压缩数据的效果，在这种情形，就不施行变换运算，也就是变换模块被旁路，直接输出预测残差；

4)        量化模块。对变换系数（在变换模块未旁路的情形）或预测残差（在变换模块被旁路的情形）施行量化运算，产生量化变换系数或量化预测残差；

5)        熵编码模块。对预测模式、运动矢量、量化变换系数或量化预测残差施行熵编码，包括对这些熵编码对象的样值先施行基于1维或2维邻近样值的差分编码；

6)        重构及后处理模块。施行预测编码模块、变换模块、量化模块这三个模块的逆运算，重构出所述CU的像素并进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的重构CU的像素放入历史像素（重构像素）暂存模块，用作后续CU的预测编码和重构的参考像素；

7)        历史像素（重构像素）暂存模块。此模块提供预测编码和重构的参考像素；

8)        基于率-失真性能的最优预测模式和划分选择模块。在编码每个CU时，根据率-失真性能选择该CU的最优预测模式。在完成对一个LCU的所有不同深度的划分的所有CU的编码后，根据率-失真性能选择该LCU的最优的深度和相应的划分；

9)        压缩码流输出模块。把选择的最优划分的编码压缩数据输出到输出视频压缩码流。

现有技术的的解码装置示意图如图4所示。整个解码装置由以下模块组成： 

1)        部分压缩码流数据存储模块；

2)        熵解码模块。对输入压缩码流数据施行熵解码。熵解码也包括对预测模式、运动矢量、量化变换系数、量化预测残差等熵解码对象的基于1维或2维邻近样值的差分解码。熵解码还包括从输入压缩码流数据中解析出编码时的划分的深度、编码时变换运算是否被旁路等解码辅助信息；

3)        反量化模块。施行反量化运算，输出变换系数或预测残差；

4)        逆变换模块。如果编码时变换运算未被旁路，则施行逆变换解码，输出预测残差，否则，不施行逆变换解码，直接输出预测残差；

5)        预测解码模块。对预测残差施行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，输出初步的重构像素；

6)        后处理模块。对初步重构像素施行去块效应滤波和像素补偿运算的后处理，然后把经后处理的重构像素放入历史像素（重构像素）暂存模块，用作后续预测解码的参考像素；

7)        历史像素暂存模块。此模块提供预测解码的参考像素；

8)        重构像素输出模块。重构像素是解码装置的最后输出。

如上所述，现有技术中，编码的第一步都是对编码单元CU进行基于邻近像素样值的帧内预测编码或者基于方块（block）的帧间（即当前编码帧与以前已编码帧之间）预测编码。在整幅图像都是自然图像的场合，现有技术是有效的。 

随着多媒体技术在计算机中的普及，今天和未来的日常使用计算机的屏幕图像中，一幅图像中常常含有很多字母、数字、文字、菜单、小图标、大图形、图表、表格等组成的位图（bitmap）。一幅这样的图像中有很多完全相同或相似的图案（pattern）。如英文仅有52个不同的字母（26个大写字母和26个小写字母），中文更是仅有很少几种不同的笔划构成。因此，在计算机屏幕图像中，找到任意形状的匹配像素样值串或匹配像素样值块，就可以用匹配串（块）的大小和与被匹配串（块）之间的距离（1维距离或2维距离）这两个参数来代表被匹配串（块）的全部信息，去除了图像像素中存在的冗余度，起到显著的图像数据压缩作用。 

但是，现有技术中，基于邻近像素样值的帧内预测编码和基于方块（block）的帧间预测编码，都不能有效地找到图像中的任意形状匹配的图案，对这类图像和图案的编码效率很低。 

发明内容

为了解决图像视频编码和解码的现有技术中的这一问题，本发明提供了一种基于任意形状匹配的图像编码与解码的方法和装置。 

本发明的主要技术特征如图5和图6所示。 

本发明的编码方法和装置中，最基本的特有技术特征就是在对当前编码单元CU编码时，按照一种或几种预先规定的像素样值排列扫描格式和匹配格式（两者合称为匹配模式），在已经完成编码的历史像素（重构像素）集合（也称为参考像素样值集）中进行搜索，逐个找到多个与当前编码CU的像素样值相匹配的最优的匹配串（块）。每个匹配串（块）可以具有任意形状并且可以用两个基本匹配参数，即匹配位置（也称匹配距离）p和匹配大小s来表征： 

1）    匹配位置p是在历史像素集合中找到的相应的匹配串（块）的第一个像素样值与当前编码CU中被匹配串（块）的第一个像素样值之间的线性（1维）距离或平面（2维）距离，也就是相对位置，其单位是像素样值。例如，p＝125像素样值表示线性距离是125个像素样值，p＝(34, 12)像素样值表示水平距离和垂直距离分别是34个像素样值和12个像素样值。

2）    匹配大小是匹配串（或块）的1维长度（或2维面积）。其单位也是像素样值。例如，s＝100像素样值表示匹配串和被匹配串都分别有100个像素样值、s＝8x12像素样值表示匹配块和被匹配块都分别有8x12=96个像素样值。显然，在匹配块的场合，一个块的大小s一般需要用多个参数分量来表示。例如，块是矩形的情形，s一般含有两个分量即矩形的宽度和高度（有时也称为长和宽）。再例如，块是平行四边形的情形，s一般也含有两个分量即平行四边形的底和高。又例如，块是梯形的情形，s一般含有三个分量即梯形的上底、下底和高。 

这多个任意形状匹配串（块）再加上可能的未匹配像素值无缝拼接正好形成当前编码CU完整的正方形状。图5有3种匹配模式（包括像素样值排列扫描格式和匹配格式）的任意形状匹配的例。图5表示的一幅图像中CU m，CU m+1，CU m+2这3个CU分别采用3种匹配模式进行任意形状匹配。一般来说，一幅当前图像中，可以所有CU都使用同一种匹配模式，也可以不同CU自适应地使用不同的匹配模式。 

  

匹配串（块），也称为匹配参考串（块），所在的参考像素样值集的大小是一个预先确定的编码和解码参数。这个参数如果不写入压缩码流，解码器就必须把参考像素样值集的大小设定为整幅当前解码图像，预留足够的存储空间，很可能超出实际需求，加大解码器的实现成本。因此，编码器应该把实际使用的参考像素样值集的大小写入压缩码流传送给解码器，使解码器可以仅预留恰当大小的参考像素样值集的存储空间，达到最高的工作效率。

  

参考像素样值集存储的是当前图像中已经经过编码或解码的重构像素值，而重构像素值通常是经历过多道工序后才达到完全的重构的。因此，参考像素样值集内存储的重构像素值一般包括不同种类的完全重构像素和不同程度的部分重构像素即仅经历过部分工序的重构像素。不同的匹配模式可以采用同一种类的重构像素作为参考像素，也可以采用不同种类的重构像素作为参考像素。同一匹配模式中，也可以在不同的匹配位置采用不同种类的重构像素作为参考像素。

  

例1：采用垂直扫描1维串形匹配的匹配模式进行任意形状匹配

图5的序号为m的CU（CU m）采用垂直扫描1维串形匹配的匹配模式进行任意形状匹配。在垂直扫描1维串形匹配的匹配模式中，历史像素先以LCU序号的顺序排列，而在一个LCU内，像素样值以垂直扫描格式逐列排列，这样，历史像素最终排列成一个一维的像素样值串。例如，在图5中，一个LCU的大小是16x16像素，每个像素有3个样值（分量），深度为1，因此一个CU的大小也是16x16像素。历史像素排列成的一维像素样值串中的第一个像素样值是序号为0的LCU即CU（CU 0）的第1列的顶端第一个像素样值。一列像素中，以垂直扫描格式自上而下排列。因此，所述一维像素样值串中的第二个像素样值是CU 0的第1列的顶端数下来第二个像素样值。第1列之后排列的是第2列，同样也是以垂直扫描格式自上而下排列像素样值。这样逐列排列一直到CU 0的第16列，之后排列的是图5中序号为1的LCU即CU（CU 1）的第一列像素，依次类推。图5所示一幅图像中，水平方向共有h个LCU即CU。因此，序号为h－1的LCU即CU（CU h－1）的第16列像素是第一个LCU行（共有h个LCU即CU）的最后（最右）1列像素，之后排列的是序号为h的LCU即CU（CU h）的第1列像素，也就是第二个LCU行的最左1列像素。图5的序号为m的LCU即CU m中画出了任意形状匹配中的前3个被匹配串：

1）    第一个被匹配串（图5 的CU m中编号为圈内1的像素样值串）有42个像素样值（=14个像素）。在历史像素中找到的对应的匹配串在序号为0的LCU即CU 0和序号为1的LCU即CU 1中（编号也是圈内1），前5个像素（15个像素样值）是CU 0的第16列的最后5个像素，而后9个像素（27个像素样值）是CU 1的第1列的最前9个像素。匹配串的第一个像素样值是CU 0的第16列的第34个像素样值，所以其位置的线性（1维）地址是

一个LCU的像素样值数xLCU序号 ＋ 列的像素样值数x(列编号－1) ＋ 列内像素样值编号 ＝768 x 0＋48 x 15＋34＝754。

而被匹配串的第一个像素样值是序号为m的LCU即CU m的第1列的第1个像素样值，所以其位置的线性（1维）地址是 

768 x m＋48 x 0＋1＝768m＋1。

所以这个编号为圈内1的任意形状匹配的匹配位置是p＝768m＋1－754＝768m－753。而其匹配大小（长度）显然是s＝42。p和s的单位都是像素样值。 

2）    第二个被匹配串（图5 的CU m中编号为圈内2的像素样值串）有33个像素样值（=11个像素）。在历史像素中找到的对应的匹配串在CU 0中（编号也是圈内2），前7个像素（21个像素样值）是CU 0的第3列的最后7个像素，而后4个像素（12个像素样值）是CU 0的第4列的最前4个像素。这个匹配串的第一个像素样值是CU 0的第3列的第28个像素样值，而被匹配串的第一个像素样值是CU m的第1列的第43个像素样值，所以这个编号为圈内2的任意形状匹配的匹配位置是p＝(768m＋48 x 0＋43)－(768 x 0＋48 x 2＋28)＝768m－81。而其匹配大小（长度）显然是s＝33。 

3）    第三个被匹配串（图5 的CU m中编号为圈内3的像素样值串）有45个像素样值（=15个像素）。在历史像素中找到的对应的匹配串在CU h－1和CU h中（编号也是圈内3），前13个像素（39个像素样值）是CU h－1的第16列的最后13个像素，而后2个像素（6个像素样值）是CU h的第1列的最前2个像素。这个匹配串的第一个像素样值是CU h－1的第16列的第10个像素样值，而被匹配串的第一个像素样值是CU m的第2列的第28个像素样值，所以这个编号为圈内3的任意形状匹配的匹配位置是p＝(768m＋48 x 1＋28)－(768 x (h－1)＋48 x 15＋10)＝768(m－h＋1)－654。而其匹配大小（长度）显然是s＝45。 

例2：采用垂直扫描2维保形（2D-shape-preserved）匹配的匹配模式进行任意形状匹配

图5的序号为m＋1的当前编码CU（CU m+1）采用垂直扫描2维保形匹配的匹配模式进行任意形状匹配。在垂直扫描2维保形匹配的匹配模式中，历史像素保留原始图像的2维排列格式，且在一个像素中，3个像素分量（样值）是垂直排列，而在当前编码CU内，像素样值则以垂直扫描格式逐列排列并且在1列内自上而下排列。在历史像素中搜索匹配像素样值串时，在当前编码CU内，被匹配像素样值以垂直扫描格式自上而下移动，一列扫描和匹配完了之后，接着扫描和匹配右边相邻的一列。在历史像素中找到的匹配像素样值串必须与当前编码CU中的被匹配像素样值串保持完全一致的2维形状。图5的CU m＋1中画出了采用垂直扫描2维保形匹配模式的任意形状匹配中的前2个被匹配串：

1）    第一个被匹配串（图5 的CU m+1中编号为圈内4的像素样值串）有45个像素样值（=15个像素）。在历史像素中找到的对应的匹配串在CU 1和CU h+1中（编号也是圈内4）。这个匹配串跨越2个CU的边界，3个像素（9个像素样值）在CU 1中，而另外12个像素（36个像素样值）在CU h+1中。历史像素集合中的匹配串与当前编码CU中的被匹配串具有完全相同的2维形状，也就是，匹配串是形成1列的45个像素样值，被匹配串也同样是形成1列的45个像素样值。匹配串的第一个像素样值是CU 1的第3列的第40个像素样值，所以其位置的平面（2维）坐标地址是

水平坐标＝这个位置左方的像素列数＝18，

垂直坐标＝这个位置上方的像素样值数＝39。

而被匹配串的第一个像素样值是CU m＋1的第1列的第1个像素样值。设当前编码CU m+1的左方有本帧图像的h列像素而上方有本帧图像的v个像素样值，则被匹配串的第一个像素样值的位置的平面（2维）坐标地址是 

水平坐标＝h + 0＝h，

垂直坐标＝v + 0＝v。

所以这个编号为圈内4的任意形状匹配的匹配位置是p＝(h-18, v-39)，也即匹配串和被匹配串中任意两个相对应的像素样值之间的水平距离是h-18而垂直距离是v-39。这个编号为圈内4的任意形状匹配的匹配大小显然是s＝45。p和s的单位都是像素样值。 

2）    第二个被匹配串（图5 的CU m＋1中编号为圈内5的像素样值串）有60个像素样值（=20个像素）。在历史像素中找到的对应的匹配串跨越了CU 1，CU 2，CU h＋1，CU h+2这4个CU。这个匹配串（编号也是圈内5）的2个像素（6个像素样值）在CU 1中，2个像素（6个像素样值）在CU 2中，15个像素（45个像素样值）在CU h+1中，1个像素（3个像素样值）在CU h+2中。历史像素集合中的匹配串与当前编码CU中的被匹配串具有完全相同的2维形状。也就是，匹配串由3列组成，第1列有3个像素样值，第2列有48个像素样值，第3列有9个像素样值，第1列与第2列的底部对齐，而第2列与第3列的顶部对齐，这个匹配串的垂直高度（含上、下端点像素）为16个像素，等同于当前编码CU m+1的高度。被匹配串也完全同样由3列组成，第1列有3个像素样值，第2列有48个像素样值，第3列有9个像素样值，第1列与第2列的底部对齐，而第2列与第3列的顶部对齐，这个被匹配串的垂直高度（含上、下端点像素）当然也是当前编码CU m+1的高度即16个像素。这个匹配串的第一个像素样值是CU h+1的第15列的第40个像素样值，其左方有本帧图像的30列像素，上方有本帧图像的87个像素样值，而被匹配串的第一个像素样值是CU m+1的第1列的第46个像素样值，其左方有本帧图像的h+0列像素，上方有本帧图像的v+45个像素样值，所以这个编号为圈内5的任意形状匹配的匹配位置是p＝(h+0-30, v+45-87)＝(h-30, v-42)，也即匹配串和被匹配串中任意两个相对应的像素样值之间的水平距离是h-30而垂直距离是v-42。这个编号为圈内5的任意形状匹配的匹配大小显然是s＝60。 

本例中匹配模式的特征是匹配像素样值串与被匹配像素样值串都形成当前图像中的2维区域，是当前图像的一部分，这两个2维区域，一个在历史像素中，另一个在当前CU中，两个2维区域具有相等的大小，并且保持完全一致的2维形状。每个2维区域由像素值垂直排列所形成的列所组成，除了第一列和最后一列之外的中间各列都有相同的高度，即这个区域的高度，第一列与这个区域的底部对齐，而最后一列与这个区域的顶部对齐。区域的高度可以与当前CU的高度相等，也可以与当前CU的高度不等而取另外一个任意的值或从当前CU的高度导出的一个值，如后面的例6和例7所示当前CU的高度的二分之一或四分之一。第一列和最后一列也可以与中间各列有相同的高度，即等于这个区域的高度，这时，这个区域就是一个矩形或正方形，如后面的例6和例7所示；本例中的匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的高度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形（如等于当前CU的高度或其二分之一），匹配大小也可以仅用一个参数分量来表示。 

例3：采用水平扫描2维保形（2D-shape-preserved）匹配的匹配模式进行任意形状匹配

图5的序号为m＋2的当前编码CU（CU m+2）采用水平扫描2维保形匹配的匹配模式进行任意形状匹配。在水平扫描2维保形匹配的匹配模式中，历史像素保留原始图像的2维排列格式，且在一个像素中，3个像素分量（样值）也是水平排列，而在当前编码CU内，像素样值则以水平扫描格式逐行排列并且在1行内从左向右排列。在历史像素中搜索匹配像素样值串时，在当前编码CU内，被匹配像素样值以水平扫描格式从左向右移动，一行扫描和匹配完了之后，接着扫描和匹配下边相邻的一行。在历史像素中找到的匹配像素样值串必须与当前编码CU中的被匹配像素样值串保持完全一致的2维形状。图5的CU m＋2中画出了采用水平扫描2维保形匹配模式的任意形状匹配中的前3个被匹配串：

1）    第一个被匹配串（图5 的CU m+2中编号为圈内6的像素样值串）有72个像素样值（=24个像素）。在历史像素中找到的对应的匹配串在CU 1和CU 2中（编号也是圈内6）。这个匹配串跨越2个CU的边界，14个像素（42个像素样值）在CU 1中，而另外10个像素（30个像素样值）在CU 2中。历史像素集合中的匹配串与当前编码CU中的被匹配串具有完全相同的2维形状。也就是，匹配串由2行组成，第1行有48个像素样值，第2行有24个像素样值，第1行与第2行的左端对齐，这个匹配串的水平宽度（含左、右端点像素）为16个像素，等同于当前编码CU m+2的宽度。被匹配串也同样由2行组成，第1行有48个像素样值，第2行有24个像素样值，第1行与第2行的左端对齐，这个被匹配串的水平宽度（含左、右端点像素）当然也是当前编码CU m+2的宽度即16个像素。匹配串的第一个像素样值是CU 1的第2行的第28个像素样值，所以其位置的平面（2维）坐标地址是

水平坐标＝这个位置左方的像素样值数＝75，

垂直坐标＝这个位置上方的像素行数＝1。

而被匹配串的第一个像素样值是CU m＋2的第1行的第1个像素样值。设当前编码CU m+2的左方有本帧图像的h个像素样值而上方有本帧图像的v行像素，则被匹配串的第一个像素样值的位置的平面（2维）坐标地址是 

水平坐标＝h + 0＝h，

垂直坐标＝v + 0＝v。

所以这个编号为圈内6的任意形状匹配的匹配位置是p＝(h-75, v-1)，也即匹配串和被匹配串中任意两个相对应的像素样值之间的水平距离是h-75而垂直距离是v-1。这个编号为圈内6的任意形状匹配的匹配大小显然是s＝72。p和s的单位都是像素样值。 

2）    第二个被匹配串（图5 的CU m+2中编号为圈内7的像素样值串）有45个像素样值（=15个像素）。在历史像素中找到的对应的匹配串在CU h和CU h+1中（编号也是圈内7）。这个匹配串跨越2个CU的边界，6个像素（18个像素样值）在CU h中，而另外9个像素（27个像素样值）在CU h+1中。历史像素集合中的匹配串与当前编码CU中的被匹配串具有完全相同的2维形状。也就是，匹配串由2行组成，第1行有24个像素样值，第2行有21个像素样值，这个匹配串的水平宽度（含左、右端点像素）为16个像素，等同于当前编码CU m+2的宽度。被匹配串也同样由2行组成，第1行有24个像素样值，第2行有21个像素样值，这个被匹配串的水平宽度（含左、右端点像素）当然也是当前编码CU m+2的宽度即16个像素。这个匹配串的第一个像素样值是CU h+1的第15行的第7个像素样值，其左方有本帧图像的54个像素样值，上方有本帧图像的30行像素，而被匹配串的第一个像素样值是CU m+2的第2行的第25个像素样值，其左方有本帧图像的h+24个像素样值，上方有本帧图像的v+1行像素，所以这个编号为圈内7的任意形状匹配的匹配位置是p＝(h+24-54, v+1-30)＝(h-30, v-29)，也即匹配串和被匹配串中任意两个相对应的像素样值之间的水平距离是h-30而垂直距离是v-29。这个编号为圈内7的任意形状匹配的匹配大小显然是s＝45。 

3）    第三个被匹配串（图5 的CU m+2中编号为圈内8的像素样值串）有54个像素样值（=18个像素）。在历史像素中找到的对应的匹配串在CU 1和CU 2中（编号也是圈内8）。这个匹配串跨越2个CU的边界，3个像素（9个像素样值）在CU 1中，而另外15个像素（45个像素样值）在CU 2中。历史像素集合中的匹配串与当前编码CU中的被匹配串具有完全相同的2维形状。也就是，匹配串由2行组成，第1行有27个像素样值，第2行有27个像素样值，这个匹配串的水平宽度（含左、右端点像素）为16个像素，等同于当前编码CU m+2的宽度。被匹配串也同样由2行组成，第1行有27个像素样值，第2行有27个像素样值，这个被匹配串的水平宽度（含左、右端点像素）当然也是当前编码CU m+2的宽度即16个像素。这个匹配串的第一个像素样值是CU 2的第11行的第13个像素样值，其左方有本帧图像的108个像素样值，上方有本帧图像的10行像素，而被匹配串的第一个像素样值是CU m+2的第3行的第22个像素样值，其左方有本帧图像的h+21个像素样值，上方有本帧图像的v+2行像素，所以这个编号为圈内8的任意形状匹配的匹配位置是p＝(h+21-108, v+2-10)＝(h-87, v-8)，也即匹配串和被匹配串中任意两个相对应的像素样值之间的水平距离是h-87而垂直距离是v-8。这个编号为圈内8的任意形状匹配的匹配大小显然是s＝54。 

本例中匹配模式的特征是匹配像素样值串与被匹配像素样值串都形成当前图像中的2维区域，是当前图像的一部分，这两个2维区域，一个在历史像素中，另一个在当前CU中，两个2维区域具有相等的大小，并且保持完全一致的2维形状。每个2维区域由像素值水平排列所形成的行所组成，除了第一行和最后一行之外的中间各行都有相同的宽度，即这个区域的宽度，第一行与这个区域的右部对齐，而最后一行与这个区域的左部对齐。区域的宽度可以与当前CU的宽度相等，也可以与当前CU的宽度不等而取另外一个任意的值或从当前CU的宽度导出的一个值，如后面的例6和例7所示当前CU的宽度的二分之一或四分之一。第一行和最后一行也可以与中间各行有相同的宽度，即等于这个区域的宽度，这时，这个区域就是一个矩形或正方形，如后面的例6和例7所示；本例中的匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的宽度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形（如等于当前CU的宽度或其二分之一），匹配大小也可以仅用一个参数分量来表示。 

例4：采用垂直扫描2维保形匹配且列扫描方向交替变换的匹配模式进行任意形状匹配

与例2即采用垂直扫描2维保形匹配的匹配模式基本相同，唯一的不同之处是：在历史像素中搜索匹配像素样值串时，在当前编码CU内，被匹配像素样值以垂直扫描格式在第1列中自上而下移动，在第2列中自下而上移动，在第3列中又自上而下移动，交替变换扫描方向，一列扫描和匹配完了之后，接着扫描和匹配右边相邻的一列。历史像素中的匹配串的垂直扫描方向也是与被匹配串同步交替变换，与被匹配串的像素样值扫描移动方向一致。

例5：采用水平扫描2维保形匹配且行扫描方向交替变换的匹配模式进行任意形状匹配

与例3即采用水平扫描2维保形匹配的模式基本相同，唯一的不同之处是：在历史像素中搜索匹配像素样值串时，在当前编码CU内，被匹配像素样值以水平扫描格式在第1行中从左向右移动，在第2行中从右向左移动，在第3行中又从左向右移动，交替变换扫描方向，一行扫描和匹配完了之后，接着扫描和匹配下边相邻的一行。历史像素中的匹配串的水平扫描方向也是与被匹配串同步交替变换，与被匹配串的像素样值扫描移动方向一致。

例6：采用水平扫描2维保形匹配且一种固定匹配大小的匹配块为匹配单位的匹配模式进行任意形状匹配

与例3即采用水平扫描2维保形匹配的匹配模式基本相同，唯一不同的2点是：

1）    在历史像素集合中搜索最优匹配时，不是以任意长度的像素样值串为单位，而是以预定的一种固定匹配大小的像素块为单位。如，以4x4像素的正方形为单位，或8x4像素的矩形为单位，或4x8像素的矩形为单位。也就是例2和例3中的所有由像素值排列形成的2维区域都是矩形或正方形。

2）    由于在一个当前编码CU内，所有匹配块的匹配大小都是一个预定的固定尺寸，所以这个CU内任意一个匹配块，都可以用匹配位置p这一个参数来表征，而不需要用匹配位置p和匹配大小s两个参数来表征。 

例7：采用水平扫描2维保形匹配且几种固定匹配大小的匹配块为匹配单位的匹配模式进行任意形状匹配

与例6基本相同，唯一不同的2点是：

1）    在历史像素集合中搜索最优匹配时，不是以预定的一种固定匹配大小的像素块为单位，而是以预定的若干种固定匹配大小的像素块为单位。如，以4x4像素、8x4像素、4x8像素这3种预定的匹配大小的正方形和矩形为单位。也就是例2和例3中的所有由像素值排列形成的2维区域都是若干种预定的矩形或正方形。

2）    对这若干种固定匹配大小，可以用编号来表示这预定的若干种匹配大小。所以这个CU内任意一个匹配块，都可以用匹配位置p和预定的若干种匹配大小的编号这两个参数来表征，而不需要用匹配位置p和匹配大小s两个参数来表征；匹配大小的编号通常比匹配大小本身占用更少的比特数。 

  

本发明的解码方法和装置中，最基本的特有技术特征就是在对当前解码CU的压缩码流数据进行解码时，首先从码流数据中解析出该CU采用的任意形状匹配的匹配模式（如以上例1~例7所示的匹配模式的例），然后从码流数据中依次读出一个一个匹配串（块）的表征参数即匹配位置和匹配大小。在有些匹配模式，一个CU或LCU仅有预定的几种甚至一种固定的匹配大小，因此，每个匹配串或匹配块从码流数据中读出的并不是匹配大小本身，而是这几种预定的匹配大小的编号，甚至码流中根本就没有每个匹配串或匹配块的各自的匹配大小的信息，只有该CU或LCU共同的匹配大小的信息。在得到了一个匹配串（块）的匹配位置和匹配大小之后，解码工作就是根据任意形状匹配的匹配模式，从当前解码的被匹配串（块）的第一个像素样值的位置和匹配位置计算出历史像素集合中的匹配串（块）的第一个像素样值的位置。然后，再根据任意形状匹配的匹配模式，就可以从历史像素集合中复制整个匹配串（块）的由匹配大小指定的所有像素样值数，并将由匹配大小指定了其尺寸（长度或面积）的整个匹配串（块）移动和粘贴到当前解码中的被匹配串（块）的位置，复原出整个被匹配串（块）。这样依次复制、移动、粘贴一个一个匹配串（块），最终复原出整个当前解码CU的所有像素。

图6有3种匹配模式（包括像素样值排列扫描格式和匹配格式）的任意形状匹配的解码例。图6表示的一幅图像中CU m，CU m+1，CU m+2这3个CU分别采用这3种匹配模式进行任意形状匹配。 

图6中的CU m采用了垂直扫描1维串形匹配的匹配模式进行任意形状匹配。因此，历史像素的排列格式是先以LCU序号的顺序排列，而在一个LCU内，像素样值以垂直扫描格式逐列排列，这样，历史像素最终排列成一个一维的像素样值串。解码时，从此历史像素集合中根据从码流数据中得到的匹配位置和匹配大小，逐个复制编号为圈内1的匹配串、编号为圈内2的匹配串、编号为圈内3的匹配串、……等，并将他们移动和粘贴到当前解码CU中编号为圈内1的被匹配串、编号为圈内2的被匹配串、编号为圈内3的被匹配串、……等的位置，复原出编号为圈内1的被匹配串、编号为圈内2的被匹配串、编号为圈内3的被匹配串、……等。编号为圈内1的匹配串的p＝768m－753，s＝42，所以是在以所述1维串形格式排列的历史像素中，从与当前被匹配串的位置距离为768m－753个像素样值的地方，复制42个像素样值，并把这42个像素样值移动和粘贴到编号为圈内1的被匹配串的位置，复原出整个编号为圈内1的被匹配串。同样，编号为圈内2的匹配串的p＝768m－81，s＝33，所以是在以所述1维串形格式排列的历史像素中，从与当前被匹配串的位置距离为768m－81个像素样值的地方，复制33个像素样值，并把这33个像素样值移动和粘贴到编号为圈内2的被匹配串的位置，复原出整个编号为圈内2的被匹配串。用同样方式，可解码和复原编号为圈内3的被匹配串、……等CU m中的所有被匹配串。 

图6中的CU m+1采用了垂直扫描2维保形匹配的匹配模式进行任意形状匹配。因此，历史像素保留原始图像的2维排列格式，且在一个像素中，3个像素分量（样值）是垂直排列。解码时，从此历史像素集合中根据从码流数据中得到的匹配位置和匹配大小，逐个复制编号为圈内4的匹配串、编号为圈内5的匹配串、……等，并将他们移动和粘贴到当前解码CU中编号为圈内4的被匹配串、编号为圈内5的被匹配串、……等的位置，复原出编号为圈内4的被匹配串、编号为圈内5的被匹配串、……等。编号为圈内4的匹配串的p＝(h-18, v-39)，s＝45，所以是在以图像的2维格式排列的历史像素中，从与当前被匹配串的位置的水平距离为h-18个像素样值和垂直距离为v-39个像素样值的地方，复制45个像素样值，并把这45个像素样值移动和粘贴到编号为圈内4的被匹配串的位置，复原出整个编号为圈内4的被匹配串。同样，编号为圈内5的匹配串的p＝(h-30, v-42)，s＝60，所以是在以图像的2维格式排列的历史像素中，从与当前被匹配串的位置的水平距离为h-30个像素样值和垂直距离为v-42个像素样值的地方，复制60个像素样值，并把这60个像素样值移动和粘贴到编号为圈内5的被匹配串的位置，复原出整个编号为圈内5的被匹配串。用同样方式，可解码和复原CU m+1中的所有被匹配串。 

图6中的CU m+2采用了水平扫描2维保形匹配的匹配模式进行任意形状匹配。因此，历史像素保留原始图像的2维排列格式，且在一个像素中，3个像素分量（样值）也是水平排列。解码时，从此历史像素集合中根据从码流数据中得到的匹配位置和匹配大小，逐个复制编号为圈内6的匹配串、编号为圈内7的匹配串、编号为圈内8的匹配串、……等，并将他们移动和粘贴到当前解码CU中编号为圈内6的被匹配串、编号为圈内7的被匹配串、编号为圈内8的匹配串、……等的位置，复原出编号为圈内6的被匹配串、编号为圈内7的被匹配串、编号为圈内8的匹配串、……等。编号为圈内6的匹配串的p＝(h-75, v-1)，s＝72，所以是在以图像的2维格式排列的历史像素中，从与当前被匹配串的位置的水平距离为h-75个像素样值和垂直距离为v-1个像素样值的地方，复制72个像素样值，并把这72个像素样值移动和粘贴到编号为圈内6的被匹配串的位置，复原出整个编号为圈内6的被匹配串。同样，编号为圈内7的匹配串的p＝(h-30, v-29)，s＝45，所以是在以图像的2维格式排列的历史像素中，从与当前被匹配串的位置的水平距离为h-30个像素样值和垂直距离为v-29个像素样值的地方，复制45个像素样值，并把这45个像素样值移动和粘贴到编号为圈内7的被匹配串的位置，复原出整个编号为圈内7的被匹配串。用同样方式，可解码和复原编号为圈内8的被匹配串、……等CU m+2中的所有被匹配串。 

  

以上通过若干特定的具体实例说明本发明的技术特征。本领域技术人员可由本说明书所揭示的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在不背离本发明的精神下进行各种修饰或改变。

本发明的编码方法的一般流程示意图如图7所示。本发明的编码方法包括如下步骤： 

1)        像素特性分析评估、前处理和编码方式选择步骤；对当前CU和邻近CU的像素样值特性进行分析评估，对输入像素样值进行必要的前处理，预先判断任意形状匹配编码方式是否适合用来对当前CU进行编码，本步骤是可选的，即可以跳过本步骤，直接进入下一步骤；所述分析评估的办法的例：依据或参考邻近CU的编码结果的办法，计算当前CU中不同颜色的像素的个数的办法；所述前处理的例：样值量化、颜色量化和基于颜色的像素聚类、用调色板和索引来精确或近似地表示输入原始像素的颜色；

2)        任意形状匹配编码步骤；使用任意形状匹配编码方式和已编码的历史像素(重构像素)暂存区（也称为参考像素样值集）对当前CU进行任意形状匹配编码运算；所述任意形状匹配编码的输入是输入原始像素或其经过前处理的像素；所述任意形状匹配编码的输出是匹配串(块)的匹配位置及匹配大小或其变体，未匹配像素值或其变体，匹配残差和其他任意形状匹配编码结果参数和变量；所述匹配位置是用来表示与所述当前CU中匹配当前像素值相匹配的匹配参考像素值在所述参考像素样值集内的什么位置的变量参数；所述任意形状匹配编码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行匹配编码，所述匹配参考像素值形成所述参考像素样值集内的一个匹配串或匹配块，称为匹配参考串或匹配参考块，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在所述任意形状匹配编码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示；由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；在匹配串的场合，匹配大小一般就是匹配串的长度；在匹配块的场合，一个块的大小一般需要用多个参数分量来表示；例如，块是矩形的情形，匹配大小一般含有两个分量即矩形的宽度和高度（有时也称为长和宽）；再例如，块是平行四边形的情形，匹配大小一般也含有两个分量即平行四边形的底和高；又例如，块是梯形的情形，匹配大小一般含有三个分量即梯形的上底、下底和高；所述未匹配像素值是依据预先确定的匹配准则在所述参考像素样值集内未找到匹配的输入原始像素样值或其经过前处理的像素样值；所述未匹配像素值是一个输入原始像素样值或其经过前处理的像素样值，所以也可以用其在当前CU中的位置来表示；所述未匹配像素值也可以用一个通过计算得到的有损或无损的仿匹配样值来近似；如果匹配大小为1，这个匹配串（块）也可以作为未匹配像素值来处理；所述匹配残差是输入原始像素样值与所述匹配参考像素值之差，如果任意形状匹配编码方式预先确定的匹配准则是绝对精确的无损匹配，则所述匹配残差为零，即这种任意形状匹配编码方式就没有匹配残差作为输出，如果一种任意形状匹配编码方式预先确定的匹配准则是近似的有损匹配，则所述匹配残差可能不为零，另一种有损匹配的情形是首先对输入原始像素样值进行样值量化、颜色量化或者基于颜色的像素聚类、用调色板和索引来近似表示输入原始像素的颜色的前处理，然后再进行任意形状匹配编码，在这种情形，由于样值量化、颜色量化或者基于颜色的像素聚类、调色板和索引表示的像素是有损的，即使任意形状匹配编码本身是无损的，所述匹配残差（即输入原始像素样值与所述匹配参考像素值之差）也可能不为零；所述其他任意形状匹配编码结果的例：匹配模式，使用匹配串构成任意形状块的规则，匹配参数的变体的类型，匹配位置的计算规则，匹配大小的计算规则，等；对所述当前CU进行任意形状匹配编码的最基本和本质的结果是I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值，输出I对（匹配位置，匹配大小）和J个未匹配像素值；所述I个匹配串(块)和J个未匹配像素值无缝拼接正好形成当前编码CU完整的正方形状；

3)        其余的匹配方式和各种常用技术编码与重构运算步骤，完成当前CU的所有其余编码和重构运算，对输入视频图像的输入原始像素、各种参数和变量进行其他匹配方式和各种常用技术，如帧内预测、帧间预测、块匹配、调色板匹配、条匹配、微块匹配、微块串匹配、仿匹配样值预测插值、变换、量化、逆变换、反量化、对应于预测残差和匹配残差的补偿（即取残差运算的逆运算）、预测并求残差、DPCM、一阶和高阶差分、映射、游程、索引、去块效应滤波、样值自适应补偿（Sample Adaptive Offset），的编码与重构运算以及熵编码运算；所述其余的匹配方式是指编码方法中不同于所述步骤2）进行的任意形状匹配编码的匹配方式；本步骤的输入是上述步骤1）和步骤2）的输出和输入原始像素以及来自所述参考像素样值集的参考像素；本步骤的输出是重构像素（包括完全重构像素和不同程度的部分重构像素）和含任何形状匹配编码结果和其他编码结果的压缩码流；所述重构像素放入所述参考像素样值集之中，用作后续任意形状匹配编码运算、其余的匹配方式和各种常用技术编码与重构运算步骤所需要的参考像素；所述压缩码流是本编码方法的最后输出，包含了对应的解码方法进行解码与重构所需要的全部语法元素，特别是匹配位置及匹配大小或其变体、未匹配像素值或其变体等语法元素。

  

本发明的解码方法的一般流程示意图如图8所示。本发明的解码方法包括如下步骤：

1)        压缩码流数据解析与部分解码步骤；对输入的含任意形状匹配编码的匹配位置及匹配大小或其变体、未匹配像素值或其变体的压缩数据以及所有其他语法元素压缩数据的压缩码流进行熵解码，并解析出熵解码得到的各种数据的意义，对一部分语法元素，特别是与任意形状匹配编码有关的语法元素，进行熵解码后的部分解码（如变换解码、预测并做补偿即求残差运算的逆运算、DPCM解码、一阶和高阶差分解码、映射解码、游程解码、索引解码）；把解析和部分解码后得到的匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数输出给后续任意形状匹配解码步骤；把解析得到的所有其他语法元素如与任意形状匹配残差、其余的匹配方式的匹配模式和匹配参数、各种常用技术的编码结果等有关的语法元素的熵解码结果输出数据（即熵解码的结果）输出给后续其余的匹配方式和各种常用技术解码与重构运算步骤；特别是，依据从压缩码流数据中解析得到的信息或者依据从压缩码流数据中解析得到的信息再加上对当前CU以及邻近CU的特性进行分析评估的结果，决定是否对当前CU进行任意形状匹配解码；所述分析评估的办法的例：依据或参考邻近CU的若干解码结果的办法，使用任意形状匹配解码方式和其他解码方式对当前CU先做一轮部分预解码并评估部分预解码结果的办法；如果决定对当前CU进行任意形状匹配解码，则顺序执行下一步骤，否则，跳至步骤3）；

2)        任意形状匹配解码步骤；使用任意形状匹配解码方式和已完成解码的历史像素（重构像素）暂存区（也称为参考像素样值集）对当前CU进行任意形状匹配解码运算；所述任意形状匹配解码运算的输入是在步骤1）中从压缩码流数据中解析和解码得到的I（I ≥ 0）对（匹配位置，匹配大小）或其变体和J（J ≥ 0）个未匹配像素值或其变体等任意形状匹配参数；所述匹配位置是用来表示从参考像素样值集内的什么位置复制匹配参考样值并将其粘贴到当前CU的匹配当前样值的位置；显而易见，匹配当前样值是匹配参考样值的复制品，两者在数值上是相等的；任意形状匹配解码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行任意形状匹配解码，所述匹配参考样值形成所述参考像素样值集内的一个匹配串(块)，称为匹配参考串(块)，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在任意形状匹配解码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示，由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；在匹配串的场合，匹配大小一般就是匹配串的长度；在匹配块的场合，一个块的大小一般需要用多个参数分量来表示；例如，块是矩形的情形，匹配大小一般含有两个分量即矩形的宽度和高度（有时也称为长和宽）；再例如，块是平行四边形的情形，匹配大小一般也含有两个分量即平行四边形的底和高；又例如，块是梯形的情形，匹配大小一般含有三个分量即梯形的上底、下底和高；所述未匹配像素值是直接从压缩码流数据中解析和解码得到的像素值并将其粘贴到当前CU的当前解码中像素值的位置，所述未匹配像素值通常不存在于所述参考像素样值集；如果从压缩码流数据中解析和解码得到的不是未匹配像素值本身而是未匹配像素值的位置，那么就把未匹配像素值的位置输出到后续步骤3）以计算仿匹配像素值；所述任意形状匹配解码运算的输出是所述匹配当前样值（在数值上与匹配参考样值相等）加上所述未匹配像素值（或其位置）；所述匹配当前样值和可能存在的所述未匹配像素值（或其位置）全部合起来就构成所述当前CU的完整的任意形状匹配解码输出；最后得到的I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值无缝拼接正好形成当前解码CU完整的正方形状；进行任意形状匹配解码运算时，首先确定匹配参考样值在历史像素(重构像素)暂存模块（也称为参考像素样值集）中所处的位置以及确定由匹配参考样值构成的匹配区域（匹配区域可以是匹配串或匹配块）的形状大小，然后从所述位置复制所述形状大小的所述匹配区域内的匹配参考样值，并将所述匹配参考样值移动和粘贴到当前解码中匹配当前样值的位置，复原出匹配当前样值；本模块的输出是所有复原的所述匹配当前样值以及可能的未匹配像素值；

3)        其余的匹配方式和各种常用技术解码与重构运算步骤，完成当前CU的所有其余解码和重构运算，对当前解码中匹配串（或匹配块）或当前解码中CU的各种参数和变量进行其他匹配方式和各种常用技术，如帧内预测、帧间预测、块匹配、调色板匹配、条匹配、微块匹配、微块串匹配、仿匹配样值预测插值、逆变换、反量化、对应于预测残差和匹配残差的补偿（即取残差运算的逆运算）、预测并做补偿（即求残差运算的逆运算）、DPCM、一阶和高阶差分、映射、游程、索引、去块效应滤波、样值自适应补偿（Sample Adaptive Offset），的解码和重构运算；所述其他匹配方式是指解码方法中不同于所述步骤2）进行的任意形状匹配解码的匹配方式；本步骤的输入是上述步骤1）输出的所有其他语法元素如匹配残差的熵解码输出数据和步骤2）的输出即所述匹配当前样值加上可能存在的所述未匹配像素值（或其位置），以及来自所述参考像素样值集内的参考像素；本步骤的输出是重构像素（包括完全重构像素和不同程度的部分重构像素）；所述重构像素放入所述参考像素样值集之中，用作后续任意形状匹配解码运算、其余的匹配方式和各种常用技术解码与重构运算步骤所需要的参考像素；所述完全重构像素也是本解码方法的最后输出。

  

本发明的编码装置的一般示意图如图9所示。整个编码装置由以下模块组成：

1)        像素前处理和任意形状匹配编码模块：对输入视频图像像素值施行像素前处理和任意形状匹配编码，产生并输出匹配串(块)的匹配位置及匹配大小或其变体，未匹配像素值或其变体，匹配残差和其他任意形状匹配编码结果参数和变量；所述像素前处理的例：样值量化、颜色量化和基于颜色的像素聚类、用调色板和索引来精确或近似表示输入原始像素的颜色；所述匹配位置是用来表示与所述当前CU中匹配当前像素值相匹配的匹配参考像素值在历史像素(重构像素)暂存模块（也称为参考像素样值集）内的什么位置的变量参数；所述任意形状匹配编码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行匹配编码，所述匹配参考像素值形成所述参考像素样值集内的一个匹配串或匹配块，称为匹配参考串或匹配参考块，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在所述任意形状匹配编码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示；由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；在匹配串的场合，匹配大小一般就是匹配串的长度；在匹配块的场合，一个块的大小一般需要用多个参数分量来表示；例如，块是矩形的情形，匹配大小一般含有两个分量即矩形的宽度和高度（有时也称为长和宽）；再例如，块是平行四边形的情形，匹配大小一般也含有两个分量即平行四边形的底和高；又例如，块是梯形的情形，匹配大小一般含有三个分量即梯形的上底、下底和高；所述未匹配像素值是依据预先确定的匹配准则在所述参考像素样值集内未找到匹配的输入原始像素样值或其经过前处理的像素样值；所述未匹配像素值是一个输入原始像素样值或其经过前处理的像素样值，所以也可以用其在当前CU中的位置来表示；所述未匹配像素值也可以用一个通过计算得到的有损或无损的仿匹配样值来近似；如果匹配大小为1，这个匹配串（块）也可以作为未匹配像素值来处理；所述匹配残差是输入原始像素样值与所述匹配参考像素值之差，如果任意形状匹配编码方式预先确定的匹配准则是绝对精确的无损匹配，则所述匹配残差为零，即这种任意形状匹配编码方式就没有匹配残差作为输出，如果一种任意形状匹配编码方式预先确定的匹配准则是近似的有损匹配，则所述匹配残差可能不为零，另一种有损匹配的情形是首先对输入原始像素样值进行样值量化、颜色量化或者基于颜色的像素聚类、用调色板和索引来近似表示输入原始像素的颜色的前处理，然后再进行任意形状匹配编码，在这种情形，由于样值量化、颜色量化或者基于颜色的像素聚类、调色板和索引表示的像素是有损的，即使任意形状匹配编码本身是无损的，所述匹配残差（即输入原始像素样值与所述匹配参考像素值之差）也可能不为零；所述其他任意形状匹配编码结果的例：匹配模式，使用匹配串构成任意形状块的规则，匹配参数的变体的类型，匹配位置的计算规则，匹配大小的计算规则，等；对所述当前CU进行任意形状匹配编码的最基本和本质的结果是I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值，输出I对（匹配位置，匹配大小）和J个未匹配像素值；所述I个匹配串(块)和J个未匹配像素值无缝拼接正好形成当前编码CU完整的正方形状；

2)        其余的匹配方式和各种常用技术编码与重构模块：对输入视频像素、各种参数和变量施行其他匹配方式和各种常用技术，如帧内预测、帧间预测、块匹配、调色板匹配、条匹配、微块匹配、微块串匹配、仿匹配样值预测插值、变换、量化、逆变换、反量化、对应于预测残差和匹配残差的补偿（即取残差运算的逆运算）、预测并求残差、DPCM、一阶和高阶差分、映射、游程、索引、去块效应滤波、样值自适应补偿（Sample Adaptive Offset），的编码与重构运算以及熵编码运算；所述其余的匹配方式是指编码装置中不同于所述模块1）施行的任意形状匹配编码的匹配方式；本模块的输入是所述模块1）的输出、原始的所述输入视频像素和来自所述参考像素样值集的参考像素；本模块的输出是重构像素值（包括完全重构像素和不同程度的部分重构像素）和含任何形状匹配编码结果和其他编码结果的压缩码流；所述重构像素值放入已重构参考像素值暂存模块中，用作后续任意形状匹配编码运算、其余的匹配方式和各种常用技术编码和重构运算所需要的参考像素值；所述压缩码流是本编码装置的最后输出，包含了对应的解码方法进行解码与重构所需要的全部语法元素，特别是匹配位置及匹配大小或其变体、未匹配像素值或其变体等语法元素；

3)        历史像素(重构像素)暂存模块：也称为参考像素样值集，暂存已重构的像素值，即在编码过程中到当前编码中CU或当前编码中匹配区域（可以是匹配串或匹配块）的开始位置为止的已重构像素值，用作当前和后续任意形状匹配编码的参考像素值，也用作对当前和后续CU施行其余的匹配方式和各种常用技术的编码和重构运算时所需要的参考像素值；重构像素值通常是经历过多道工序后才达到完全的重构的；因此，参考像素样值集内存储的重构像素值一般包括不同种类的完全重构像素和不同程度的部分重构像素即仅经历过部分工序的重构像素；不同的匹配模式可以采用同一种类的重构像素作为参考像素，也可以采用不同种类的重构像素作为参考像素；同一匹配模式中，也可以在不同的匹配位置采用不同种类的重构像素作为参考像素。

  

本发明的解码装置的一般示意图如图10所示。整个解码装置由以下模块组成：

1)        码流数据解析与部分解码模块：对输入的含任意形状匹配编码的匹配位置及匹配大小或其变体、未匹配像素值或其变体的压缩数据以及所有其他语法元素压缩数据的压缩码流施行熵解码，并解析出熵解码得到的各种数据的意义，对一部分语法元素，特别是与任意形状匹配编码有关的语法元素，进行熵解码后的部分解码（如变换解码、预测并做补偿即求残差运算的逆运算、DPCM解码、一阶和高阶差分解码、映射解码、游程解码、索引解码）；把解析和部分解码后得到的匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数送往任意形状匹配解码模块；把解析得到的匹配残差等其他任意形状匹配编码结果、其余的匹配方式的匹配模式和匹配参数、各种常用技术的编码结果等的语法元素的熵解码结果输出数据（即熵解码的结果）送往其余的匹配方式和各种常用技术解码与重构模块；所述部分解码的其他的例：依据从压缩码流数据中解析得到的信息或者依据从压缩码流数据中解析得到的信息再加上对当前CU以及邻近CU的特性进行分析评估的结果，决定是否对当前CU进行任意形状匹配解码；所述分析评估的办法的例：依据或参考邻近CU的若干解码结果的办法，使用任意形状匹配解码方式和其他解码方式对当前CU先做一轮部分预解码并评估部分预解码结果的办法；

2)        任意形状匹配解码模块：根据所述匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数施行任意形状匹配解码运算；本模块的输入是所述模块1）输出的从压缩码流数据中解析和解码得到的I（I ≥ 0）对（匹配位置，匹配大小）或其变体和J（J ≥ 0）个未匹配像素值或其变体等任意形状匹配参数；所述匹配位置是用来表示从参考像素样值集内的什么位置复制匹配参考样值并将其粘贴到当前CU的匹配当前样值的位置；显而易见，匹配当前样值是匹配参考样值的复制品，两者在数值上是相等的；任意形状匹配解码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行任意形状匹配解码，所述匹配参考样值形成所述参考像素样值集内的一个匹配串(块)，称为匹配参考串(块)，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在任意形状匹配解码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示，由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；在匹配串的场合，匹配大小一般就是匹配串的长度；在匹配块的场合，一个块的大小一般需要用多个参数分量来表示；例如，块是矩形的情形，匹配大小一般含有两个分量即矩形的宽度和高度（有时也称为长和宽）；再例如，块是平行四边形的情形，匹配大小一般也含有两个分量即平行四边形的底和高；又例如，块是梯形的情形，匹配大小一般含有三个分量即梯形的上底、下底和高；所述未匹配像素值是直接从压缩码流数据中解析和解码得到的像素值并将其粘贴到当前CU的当前解码中像素值的位置，所述未匹配像素值通常不存在于所述参考像素样值集；如果从压缩码流数据中解析和解码得到的不是未匹配像素值本身而是未匹配像素值的位置，那么就把未匹配像素值的位置输出到后续步骤3）以计算仿匹配像素值；所述任意形状匹配解码运算的输出是所述匹配当前样值（在数值上与匹配参考样值相等）加上所述未匹配像素值（或其位置）；所述匹配当前样值和可能存在的所述未匹配像素值（或其位置）全部合起来就构成所述当前CU的完整的任意形状匹配解码输出；最后得到的I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值无缝拼接正好形成当前解码CU完整的正方形状；施行任意形状匹配解码运算时，首先确定匹配参考样值在历史像素(重构像素)暂存模块（也称为参考像素样值集）中所处的位置以及确定由匹配参考样值构成的匹配区域（匹配区域可以是匹配串或匹配块）的形状大小，然后从所述位置复制所述形状大小的所述匹配区域内的匹配参考样值，并将所述匹配参考样值移动和粘贴到当前解码中匹配当前样值的位置，复原出匹配当前样值；本模块的输出是所有复原的所述匹配当前样值以及可能的未匹配像素值；

3)        其余的匹配方式和各种常用技术解码和重构模块：对当前解码中匹配串（或匹配块）或当前解码中CU的各种参数和变量施行其他匹配方式和各种常用技术，如帧内预测、帧间预测、逆变换、反量化、对应于预测残差和匹配残差的补偿（即取残差运算的逆运算）、DPCM、一阶和高阶差分、映射、游程、索引、去块效应滤波、样值自适应补偿（Sample Adaptive Offset），的解码和重构运算；所述其他匹配方式是指解码装置中不同于所述模块2）施行的任意形状匹配解码的匹配方式；本模块的输出是重构像素值（包括完全重构像素值和不同程度的部分重构像素值）；所述重构像素值放入已重构参考像素值暂存模块中，用作后续匹配解码运算、其余的匹配方式和各种常用技术解码和重构运算所需要的参考像素值；所述完全重构像素值也是本解码装置的最后输出；

4)        历史像素(重构像素)暂存模块：也称为参考像素样值集，暂存已重构的像素值，即在解码过程中到当前解码中CU或当前解码中匹配区域（可以是匹配串或匹配块）的开始位置为止的已重构像素值，用作当前和后续任意形状匹配解码的参考像素值，也用作对当前和后续CU施行其余的匹配方式和各种常用技术的解码和重构运算时所需要的参考像素值；重构像素值通常是经历过多道工序后才达到完全的重构的；因此，参考像素样值集内存储的重构像素值一般包括不同种类的完全重构像素和不同程度的部分重构像素即仅经历过部分工序的重构像素；不同的匹配模式可以采用同一种类的重构像素作为参考像素，也可以采用不同种类的重构像素作为参考像素；同一匹配模式中，也可以在不同的匹配位置采用不同种类的重构像素作为参考像素。

  

以上所提供的图示仅以示意方式说明本发明的基本构想，遂图式中仅显示与本发明中有关的组件而非按照实际实施时的组件数目、形状及尺寸绘制，其实际实施时各组件的型态、数量及比例可为一种随意的改变，且其组件布局型态也可能更为复杂。

以下是本发明的更多的实施细节和变化。 

  

编码方法的一个实施例

编码方法的一个实施例的流程示意图如图11所示。本实施例包括如下步骤：

1)        读入一个大小为NxN像素的最大编码单元即LCU的原始像素；

2)        把变量M的初始值设为N，也就是准备好首先对大小为MxM＝NxN像素的当前编码单元CU的划分进行编码；

3)        对当前编码中的LCU，进行基于颜色的像素聚类，也就是把某些很接近的颜色合并成一个颜色；针对后续的预测步骤和匹配步骤的需要，可以分别进行像素聚类或者不进行像素聚类；

4)        对1个MxM像素的CU的经过或未经过像素聚类的像素样值进行基于邻近像素样值的帧内预测编码和基于方块（block）的帧间（即当前编码帧与以前已编码帧之间）预测编码，统称为预测编码，产生出（1）预测残差和（2）预测模式和运动矢量；预测编码中需要尝试多种帧内预测模式和多种帧间预测模式（统称为预测模式）；每一种预测模式都会产生相应的预测残差并经历后续步骤9）、10）、11）、12）的运算；

5)        对这个MxM像素的CU的经过或未经过像素聚类的像素样值进行任意形状匹配编码，产生出（1）匹配残差和（2）匹配串（块）的匹配位置p和匹配大小s；也就是按照一种或几种预先规定的匹配模式，在已经完成编码的历史像素集合中搜索，逐个找到多个与当前编码CU中的像素样值相匹配的最优的匹配串或匹配块；这多个任意形状匹配串（块）无缝拼接正好形成当前编码CU完整的正方形状；如果匹配是精确的无损匹配，则无匹配残差（匹配残差为零）；如果匹配是近似的有损匹配，则匹配残差不为零，一般需要对匹配残差进行后续的可选的变换编码步骤以及量化编码步骤，但如果匹配残差很小，也可以把匹配残差视为零而不进行后续的可选的变换编码步骤以及量化编码步骤；如果本步骤采用了多种预先规定的匹配模式，则每一种匹配模式都会产生相应的匹配残差并经历后续步骤9）、10）、11）、12）的运算；

6)        如果一个匹配串（块）的匹配大小s大于某个阈值S（S一般满足：2≤S≤6，而如果S＝0，那么就仅是对未匹配像素样值进行二级短匹配编码，如果S＝1，那么就仅是对未匹配像素样值和匹配大小为1的匹配串（块）进行二级短匹配编码），则跳至步骤8），否则，这个匹配串（块）是一个短匹配串（块），对其进行如下的二级短匹配编码：在一个代表像素缓存（其中每个代表像素及像素样值都有一个序号）中搜索是否能找到匹配串（称为二级匹配串）；如果能找到二级匹配串，就输出二级匹配串的匹配序号（即代表像素缓存中找到的二级匹配串的第一个像素样值的序号）及匹配长度，否则，输出原来步骤5）产生的在历史像素中找到的匹配串的匹配位置及匹配大小；

7)        更新代表像素缓存；如果这个短匹配串的匹配大小s=0，也就是在步骤5）和步骤6）都没有找到任何匹配导致所述CU中当前编码中像素样值成为未匹配像素样值，那么就要根据某种预先确定的规则来决定是否把当前未匹配像素样值放入代表像素缓存，并且决定是否要从代表像素缓存中删除某个像素样值；一个最简单的规则就是先入先出（FIFO）规则，即把所有未匹配像素样值都依次放入代表像素缓存，放满之后，就依次把最早放入的未匹配像素样值删除；一个更为复杂一些的规则是：当匹配串的匹配大小s≤S时，就把此短匹配暂时保存在一个代表像素备用区，但不马上放入代表像素缓存；当同样的短匹配出现2次以上时，再把此短匹配放入代表像素缓存；

8)        选择匹配编码的输出：如果这个匹配串（块）的匹配大小s＝0，则输出未匹配像素样值，否则，如果步骤6）在代表像素缓存中找到二级匹配串，则输出其匹配序号及匹配长度，否则，输出原来步骤5）产生的在历史像素中找到的匹配串（块）的匹配位置及匹配大小；

9)        对步骤4）和5）产生的预测残差和匹配残差进行变换编码，产生出变换系数；变换编码是分别可选的，也就是如果对预测残差进行变换编码达不到更好的数据压缩效果，就不对预测残差进行变换编码，如果对匹配残差进行变换编码达不到更好的数据压缩效果，就不对匹配残差进行变换编码；

10)    对预测残差的变换系数（在前一步骤进行了变换编码的情形）或预测残差本身（在前一步骤不进行变换编码的情形）进行量化编码，产生量化预测变换系数或量化预测残差；对匹配残差的变换系数（在前一步骤进行了变换编码的情形）或匹配残差本身（在前一步骤不进行变换编码的情形）进行量化编码，产生量化匹配变换系数或量化匹配残差；在无损编码的情形，量化编码运算是等同运算，不产生任何实际的量化效果；

11)    对步骤4）、9）、10）的预测-变换-量化编码方式（即基于预测的编码方式，简称为预测方式）的结果进行所述预测方式的逆运算，对步骤5）、9）、10）的匹配-变换-量化编码方式（即基于匹配的编码方式，简称为匹配方式）的结果进行所述匹配方式的逆运算，得到所述CU的对应于多种预测模式和多种匹配模式的多种初步重构像素，用于后续步骤13）的率-失真成本计算，并在后续步骤16）确定了对当前编码LCU的最优划分及其对各CU的最优编码方式之后，对最优划分的所有初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的各重构CU的像素放入历史像素（重构像素）暂存区，用作后续匹配编码、预测编码和重构的参考像素；由于编码可能是有损的，重构像素并不一定等于输入原始像素；

12)    对步骤4）的编码结果之二预测模式和运动矢量、步骤8）的匹配编码输出即匹配信息、以及步骤10）的量化编码结果即量化预测变换系数、量化预测残差、量化匹配变换系数、和量化匹配残差进行熵编码并产生压缩码流的比特率；熵编码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化预测变换系数、量化预测残差、量化匹配变换系数、量化匹配残差等熵编码对象的样值先进行基于1维或2维邻近样值的差分编码或索引编码，以去除样值之间的相关性，提高熵编码的效率；

13)    从原始像素、多种初步重构像素及其压缩码流的比特率或者比特率估计值，计算得到率-失真成本，根据率-失真性能选择此CU的最优编码方式（基于匹配的编码方式还是基于预测的编码方式）、最优匹配模式或最优预测模式并暂存此CU的最优压缩码流数据；

14)    判断是否已经完成对当前划分中所有MxM像素CU的编码，如果是，则顺序执行下一步骤，否则跳至步骤4）开始下一个MxM像素CU的编码；

15)    判断是否M已经达到预先设定的最小值，如果是，则顺序执行下一步骤，否则，把M减半（即划分的深度加1），然后跳至步骤4）开始下一个深度的划分中所有MxM像素CU的编码；

16)    从已完成的多个不同深度（不同大小MxM像素的CU）的划分的编码结果中，根据率-失真性能选择一个最优的MxM像素的CU的划分并输出该划分相应的压缩码流数据；

17)    判断是否已完成所有LCU的编码，如果是，则结束编码，否则回到步骤1)，开始对下一个LCU的编码。

  

解码方法的一个实施例

解码方法的一个实施例的流程示意图如图12所示。本实施例包括如下步骤：

1)        读入图像的部分压缩码流数据；

2)        进行一个编码单元即CU的熵解码，得到该CU的头信息和数据信息；头信息包括该CU编码时采用的是现有的预测技术还是本发明的匹配技术；该CU采用了哪种任意形状匹配模式，或该CU采用了基于邻近像素样值的帧内预测还是采用了基于方块的帧间预测；是否进行逆变换解码；熵解码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化变换系数、量化预测残差、量化匹配残差等熵解码对象的基于1维或2维邻近样值的差分解码或索引解码；在任意形状匹配模式，一个CU可以由一个或多个匹配串（块）拼接组成，每个匹配串（块）都要经历后续步骤6）、7）、8）的运算；

3)        对量化变换系数或量化预测残差或量化匹配残差进行反量化解码，产生出变换系数或预测残差或匹配残差；

4)        如果前一步骤产生的是变换系数，则进行逆变换解码，产生出预测残差或匹配残差，否则，顺序执行下一步骤；

5)        如果步骤3）或4）产生的是预测残差，则进行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，统称为预测解码，产生出初步的重构像素，然后跳至步骤9），否则，顺序执行下一步骤；

6)        如果步骤2）熵解码得到某个匹配序号及长度，则进行短匹配解码，从代表像素存储中复制得到短匹配串的像素样值；

7)        更新代表像素缓存；如果匹配大小s=0，也就是步骤2）熵解码得到一个未匹配像素样值，那么就要根据某种预先确定的规则来决定是否把当前未匹配像素样值放入代表像素缓存，并且决定是否要从代表像素缓存中删除某个像素样值；一个最简单的规则就是先入先出（FIFO）规则，即把未匹配像素样值都依次放入代表像素缓存，放满之后，就依次把最早放入的未匹配像素样值删除；一个更为复杂一些的规则是：当匹配串的匹配大小s≤S时，就把此短匹配暂时保存在一个代表像素备用区，但不马上放入代表像素缓存；当同样的短匹配出现2次以上时，再把此短匹配放入代表像素缓存；

8)        任意形状匹配解码；根据步骤2）得到的任意形状匹配模式，把可以具有任意形状的匹配串（块）移动和粘贴到当前解码CU的当前被匹配串（块）的位置，再加上来自步骤3）或4）的匹配残差，产生出初步的重构像素；所述任意形状的匹配串（块）可以是来自步骤2）的未匹配像素样值，或者是来自步骤6）的短匹配串，或者是来自历史像素暂存区中由匹配位置p和匹配大小s这两个匹配参数决定的匹配串（块）；

9)        对预测方式的初步重构像素或匹配方式的初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的当前CU的全部重构像素放入历史像素（重构像素）暂存区，用作后续任意形状匹配解码和预测解码的参考像素；

10)    输出重构CU的像素；

11)    判断是否已经完成对一个LCU中所有CU的压缩码流数据的解码，如果是，则顺序执行下一步骤，否则回到步骤1)，开始对下一个CU的解码；

12)    判断是否已经完成对所有LCU的压缩码流数据的解码，如果是，则结束解码，否则回到步骤1)，开始对下一个LCU的解码。

  

编码装置的一个实施例

编码装置的一个实施例的模块组成示意图如图13所示。本实施例由以下模块组成：

1)       可以存储当前编码中最大编码单元即LCU中一种深度的划分中至少一个编码单元即CU的像素的存储模块；

2)       预测编码模块：对输入像素施行基于邻近像素样值的帧内预测编码和基于方块（block）的帧间预测编码，并输出（1）预测残差和（2）预测模式和运动矢量；本模块可施行多种帧内预测模式和多种帧间预测模式（统称为预测模式）下的编码；

3)       基于颜色的像素聚类模块：把输入像素中某些很接近的颜色合并成一个颜色，以提高后续的匹配编码的效率，找到尺寸更大，误差更小的匹配串（块）；在原有颜色已经比较少的情形，或者进行超高品质编码和无损编码的情形，此模块可以被旁路；

4)       任意形状匹配搜索编码模块：对经过或未经过像素聚类的输入像素样值施行任意形状匹配编码，并输出（1）匹配残差、（2）匹配串（块）的匹配位置p和匹配大小s、（3）匹配统计信息；本模块可施行一种或多种匹配模式下的编码；

5)       短匹配搜索模块：如果任意形状匹配搜索编码模块搜索到的某个匹配串的匹配大小s小于或等于某个阈值S，则再施行二级短匹配搜索和编码，即在一个代表像素缓存模块（其中每个像素样值都有一个序号）中搜索是否能找到匹配串（称为二级匹配串）；如果能找到二级匹配串，就输出二级匹配串的匹配序号（即二级匹配串的第一个像素样值在代表像素缓存模块中的序号）及匹配长度，否则，输出原来任意形状匹配搜索编码模块输出的在历史像素中找到的匹配串的匹配位置及匹配大小；匹配序号可以用比匹配位置更少的比特数来表示，因而可以提高编码效率；如果S＝0，那么就仅是对未匹配像素样值进行二级短匹配编码；如果S＝1，那么就仅是对未匹配像素样值和匹配大小为1的匹配串（块）进行二级短匹配编码；

6)       代表像素缓存模块：存储用于短匹配搜索的代表像素；此模块可以含有一个候选代表像素缓存单元；此模块可以为空；在这种情形，就不施行短匹配搜索，也没有所述短匹配搜索模块和代表像素更新模块；

7)       代表像素更新模块：如果匹配大小s=0，也就是任意形状匹配搜索编码模块和短匹配搜索模块都没有搜索到任何匹配导致所述CU中当前编码中像素样值成为未匹配像素样值，那么当前编码中的未匹配像素样值就是候选的代表像素，被放入一个代表像素缓存模块中的候选代表像素缓存单元；根据某种预先确定的规则来决定当前未匹配像素样值是否立即成为正式的代表像素，还是在收集到一定程度的关于该像素样值的匹配统计信息数据后再成为正式的代表像素；当代表像素存储空间溢出时，就需要决定如何从代表像素存储空间中删除某个像素样值；一个最简单的方法就是先入先出（FIFO），即先放入的先删除；一个更为复杂一些的方法是，根据各个像素样值的匹配统计信息数据来决定删除哪个像素样值；

8)       变换模块：对匹配残差和预测残差施行变换运算，输出变换系数；对某些类型的屏幕图像像素，变换运算并不能起到压缩数据的效果，在这种情形，就不施行变换运算，也就是变换模块被旁路，直接输出匹配残差或预测残差；

9)       量化模块：对变换系数（在变换模块未旁路的情形）或匹配残差或预测残差（在变换模块被旁路的情形）施行量化运算，输出量化预测变换系数或量化预测残差，并输出量化匹配变换系数或量化匹配残差；

10)   熵编码模块：对匹配编码的结果如匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化变换系数或量化匹配残差等施行熵编码；对预测编码结果如预测模式、运动矢量、量化变换系数或量化预测残差等施行熵编码，包括对这些熵编码对象的样值先施行基于1维或2维邻近样值的差分编码或索引编码；

11)   重构及后处理模块：施行预测编码模块、变换模块、量化模块这三个模块的逆运算；施行任意形状匹配搜索编码模块、变换模块、量化模块这三个模块的逆运算，初步重构出在多种预测模式和多种匹配模式下所述CU的像素，并将初步重构像素输出到基于率-失真性能的最优预测模式与匹配模式和划分选择模块用于率-失真成本的计算；在基于率-失真性能的最优预测模式与匹配模式和划分选择模块确定了对当前编码LCU的最优划分及其对各CU的最优编码方式及其模式之后，再对最优划分的各CU的初步重构像素施行去块效应滤波和像素补偿运算的后处理，然后把经后处理的重构CU的像素放入历史像素（重构像素）暂存模块，用作后续CU的预测编码、匹配编码和重构的参考像素；

12)   历史像素（重构像素）暂存模块：此模块提供预测编码、匹配编码和重构的参考像素；

13)   基于率-失真性能的最优预测模式与匹配模式和划分选择模块：在编码一个LCU的各不同深度的划分中每个CU时，根据率-失真性能选择该CU的最优编码方式（基于匹配的编码方式还是基于预测的编码方式）、最优匹配模式、和最优预测模式；在完成对一个LCU的所有不同深度的划分的所有CU的编码后，根据率-失真性能选择该LCU的最优的深度和相应的划分；

14)   压缩码流输出模块：把选择的最优划分的编码压缩数据输出到输出视频压缩码流。

  

解码装置的一个实施例

解码装置的一个实施例的模块组成示意图如图14所示。本实施例由以下模块组成：

1)        部分压缩码流数据存储模块；

2)        熵解码模块：对输入压缩码流数据施行熵解码，得到当前解码CU的头信息和数据信息；熵解码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化变换系数、量化预测残差、量化匹配残差等熵解码对象的基于1维或2维邻近样值的差分解码或索引解码；熵解码还包括从输入压缩码流数据中解析出当前解码LCU在编码时采用的划分的深度、当前解码CU在编码时采用的是现有的预测技术还是本发明的匹配技术，采用了哪种任意形状匹配模式，或采用了基于邻近像素样值的帧内预测还是采用了基于方块的帧间预测、变换运算是否被旁路等信息；在匹配模式下，所述当前解码CU的数据信息可以含有一个或多个匹配串（块）的信息；

3)        反量化模块：施行反量化运算，输出变换系数或预测残差或匹配残差；

4)        逆变换模块；如果编码时变换运算未被旁路，则施行逆变换解码，输出预测残差或匹配残差，否则，不施行逆变换解码，直接输出预测残差或匹配残差；

5)        预测解码模块：对预测残差施行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，得到并输出初步重构像素；

6)        代表像素缓存模块：此模块的输入是熵解码模块输出的短匹配的匹配序号及长度；短匹配的匹配序号是短匹配中第一个像素样值在代表像素缓存模块中的序号；根据输入的匹配序号及长度，此模块输出有若干代表像素样值组成的短匹配串；

7)        代表像素更新模块：此模块的作用是更新代表像素缓存模块中的代表像素样值；

8)        任意形状匹配解码模块：当本模块的输入是来自熵解码模块的一个匹配串（块）的匹配位置和大小的时候，本模块的功能是从历史像素暂存模块中由匹配位置指定的地方复制得到尺寸为匹配大小的匹配串（块），然后把此匹配串（块）移动和粘贴到当前解码CU的当前被匹配串（块）的位置；当本模块的输入是来自代表像素缓存模块的短匹配串的时候，本模块的功能是直接把所述短匹配串移动和粘贴到当前解码CU的当前被匹配串的位置；当本模块的输入是来自熵解码模块的未匹配像素样值的时候，本模块的功能是直接把所述未匹配像素样值移动和粘贴到当前解码CU的当前被匹配串的位置；本模块的另一个功能是在粘贴到位的被匹配串（块）的像素上，再加上来自逆变换模块的匹配残差，得到并输出初步的重构像素；匹配残差也可以全部为零，这时就不需要施行所述的匹配残差加法运算；

9)        后处理模块：对初步重构像素施行去块效应滤波和像素补偿运算的后处理，然后把经后处理的重构像素放入历史像素（重构像素）暂存模块，用作后续任意形状匹配解码和预测解码的参考像素；

10)    历史像素暂存模块：此模块提供任意形状匹配解码和预测解码的参考像素；

11)    重构像素输出模块：重构像素是解码装置的最后输出。

  

在压缩码流中表示存在未匹配像素样值的一个实施例

在任意形状匹配编码和解码中，未找到匹配的情形，也就是有未匹配像素样值的情形，即可以用匹配大小s=0来表示，也可以用匹配位置p＝0（当前像素样值自己与自己匹配）来表示。

  

匹配准则的若干实施例

匹配可以是无损或精确的，也可以是有损或近似的；设历史像素集合中的一个像素样值的候选匹配串是x＝(s_n, s_n+1, ……, s_n+m-1)，当前编码CU中当前位置的被匹配串是y＝(s_c, s_c+1, ……, s_c+m-1)，那么这对像素样值串的匹配长度是m，而匹配性能可以用一个长度-失真成本（Length-Distortion Cost简称LDcost）函数LDcost = f(m, |s_c - s_n|, |s_c+1 - s_n+1|, …… , |s_c+m-1 - s_n+m-1|)来表示；最简单的一种长度-失真成本函数是LDcost = (MaxStringLength - m) + λ(|s_c - s_n| + |s_c+1 - s_n+1| + …… + |s_c+m-1 - s_n+m-1|)，其中MaxStringLength是预设的最大匹配长度，如300，λ是拉格朗日乘数因子，如0.25，用于平衡匹配长度和匹配失真的权重；在更为复杂的长度-失真成本函数中，每一个像素样值误差项|s_c+q-1 - s_n+q-1|可能有自己的乘数因子，乘数因子也可以随长度m而变化；长度-失真成本函数的作用是在搜索匹配串（块）时，用来评估匹配串（块）的匹配性能，选择最优匹配串（块）；如果在搜索匹配串（块）时，强制规定所有像素样值误差项|s_c+q-1 - s_n+q-1|＝0，则得到的就是无损或精确匹配，否则，得到的就是有损或近似匹配。

  

任意形状匹配的匹配模式的若干实施例

匹配模式中，采用像素值垂直排列格式，即把一个2维区域的像素值先垂直排列，排列完一列后再排列另一列，和串形匹配格式，即匹配当前像素值和匹配参考像素值都形成像素值的串，两个串具有相等的长度，但不一定保持相同的2维形状；

或者

匹配模式中，采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和串形匹配格式，即匹配当前像素值和匹配参考像素值都形成像素值的串，两个串具有相等的长度，但不一定保持相同的2维形状；

或者

匹配模式中，采用像素值垂直排列格式，即把一个2维区域的像素值先垂直排列，排列完一列后再排列另一列，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值垂直排列所形成的列所组成，除了第一列和最后一列之外的中间各列都有相同的高度，即这个区域的高度，第一列与这个区域的底部对齐，而最后一列与这个区域的顶部对齐；区域的高度可以与当前CU的高度相等，也可以与当前CU的高度不等而取另外一个任意的值或从当前CU的高度导出的一个值，如当前CU的高度的二分之一或四分之一；第一列和最后一列也可以与中间各列有相同的高度，即等于这个区域的高度，这时，这个区域是一个任意大小的矩形或正方形；在本匹配模式中，匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的高度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形（如等于当前CU的高度或其二分之一），匹配大小也可以仅用一个参数分量来表示；

或者

匹配模式中，采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，除了第一行和最后一行之外的中间各行都有相同的宽度，即这个区域的宽度，第一行与这个区域的右部对齐，而最后一行与这个区域的左部对齐；区域的宽度可以与当前CU的宽度相等，也可以与当前CU的宽度不等而取另外一个任意的值或从当前CU的宽度导出的一个值，如当前CU的宽度的二分之一或四分之一；第一行和最后一行也可以与中间各行有相同的宽度，即等于这个区域的宽度，这时，这个区域是一个任意大小的矩形或正方形；在本匹配模式中，匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的宽度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形（如等于当前CU的宽度或其二分之一），匹配大小也可以仅用一个参数分量来表示；

或者

匹配模式中，采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，所有行都有相同的宽度；所有行的左端点可以形成一条垂直的直线，这时，这个区域是一个矩形或正方形，也可以形成一条非垂直的斜线，这时，这个区域是一个平行四边形；

或者

匹配模式中，采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，所有行的左端点形成一条直线，所有行的右端点形成另一条直线；这两条直线可以是平行的，这时，这个区域是一个平行四边形，也可以是非平行的，这时，这个区域是一个梯形；

一幅当前图像中，可以所有CU都使用同一种匹配模式，也可以不同CU自适应地使用不同的匹配模式。

  

匹配区域的匹配位置的实施例

匹配区域（区域可以是串或块）的匹配位置是匹配当前区域中第一个匹配当前样值与匹配参考区域中第一个匹配参考样值之间的相对位置。

  

匹配位置的表示法的实施例1

图像是2维数据，匹配串是匹配块的特例，即2个维度中的一个维度取值为1的特例；所以匹配位置本质上是一个2维的自然数变量，可以用一个自然数对（X，Y）来表示；但从数学上来说，用Xmax和Ymax来分别表示X和Y的最大值，则任何一个2维自然数对（X，Y）都可以转化成一个1维的自然数L：L ＝ X ＋ W*Y，其中W是一个预先设定的大于Xmax的自然数；L也可以有另一种计算方法：L ＝ Y ＋ H*X，其中H是一个预先设定的大于Ymax的自然数；显然，从L也可以计算出（X，Y）：用L除以W，X和Y就分别是除法的余数和商；同样，X和Y分别是L除以H的商和余数；因此，匹配位置可以用一个自然数对（X，Y）来表示；也可以用一个自然数L来表示，（X，Y）与L可以通过一个在编码过程和解码过程中根据一种规则确定的自然数W或H来互相转换；所述匹配位置（X，Y）的一种计算方式是匹配参考样值的2维坐标（X₁，Y₁）与匹配当前样值的2维坐标（X₂，Y₂）之差再加上（图像宽度，图像高度），而X₁和X₂都小于图像宽度，Y₁和Y₂都小于图像高度，因此X和Y分别小于图像宽度的2倍和图像高度的2倍；由此可见所述W的例：图像宽度的2倍，所述H的例：图像高度的2倍。

  

匹配位置的表示法的实施例2

当前图像被划分成一个一个CU（或LCU），每个CU（或LCU）都被赋予一个序号，序号从零开始逐一递增；当前图像中的每个像素值也都被赋予一个编号（或称线性地址），编号从零开始逐一递增；像素值编号的排列顺序是先从CU（或LCU）序号小的开始排列，一个序号的CU（或LCU）的全部像素值都排列完之后，再排列下一个序号的CU（或LCU）的像素值；而在一个CU（或LCU）内部，像素样值以垂直格式逐列（或者水平格式逐行）排列；匹配区域的匹配位置是匹配参考区域中第一个匹配参考像素值的线性地址（即编号）与匹配当前区域中第一个匹配当前像素值的线性地址（即编号）的差。

  

受限的匹配位置的表示法的实施例

如果把匹配参考样值的位置限定于与匹配当前样值具有同样的水平位置或垂直位置，那么匹配位置（X，Y）中有一个为零（或其他常数）；匹配位置就可以用一个自然数和一个表示水平还是垂直位置的标记位来表示。

  

匹配大小的表示法的实施例

匹配大小只有一个参数分量，表示匹配串的长度；

或者

匹配大小有一个直接参数分量，如表示匹配串（块）的像素值的个数，和一个从编码过程或解码过程中的其他参数或变量（如当前CU的高度或宽度）导出的参数分量，如表示匹配串（块）的高度或宽度；

或者

匹配大小有两个参数分量，表示匹配串（块）所占据的区域的宽度和高度；这两个参数分量可以用一个自然数对（X，Y）来表示，也可以用一个自然数L来表示；（X，Y）与L可以通过一个在编码过程和解码过程中根据一种规则确定的自然数W或H来互相转换；所述W的例：1）当前CU的宽度，2）匹配当前串（块）的最左上角的像素值到当前CU的右边界的水平距离，3）由匹配当前串（块）在当前图像中的位置（或2维坐标）所决定的匹配当前串（块）的宽度的最大可能值，4）由匹配参考串（块）在当前图像中的位置（或2维坐标）所决定的匹配参考串（块）的宽度的最大可能值，5）以上3）和4）两者中的较小值，6）由匹配当前串（块）的最左上角的像素值在当前CU中的位置和当前CU中已完成匹配的区域决定的当前串（块）的宽度的最大可能值，7）由对匹配参考串（块）的限制所决定的匹配参考串（块）的宽度的最大可能值，8）以上6）和7）两者中的较小值；所述H的例：1）当前CU的高度，2）匹配当前串（块）的最左上角的像素值到当前CU的下边界的垂直距离，3）由匹配当前串（块）在当前图像中的位置（或2维坐标）所决定的匹配当前串（块）的高度的最大可能值，4）由匹配参考串（块）在当前图像中的位置（或2维坐标）所决定的匹配参考串（块）的高度的最大可能值，5）以上3）和4）两者中的较小值，6）由匹配当前串（块）的最左上角的像素值在当前CU中的位置和当前CU中已完成匹配的区域决定的当前串（块）的高度的最大可能值，7）由对匹配参考串（块）的限制所决定的匹配参考串（块）的高度的最大可能值，8）以上6）和7）两者中的较小值；

或者

匹配大小有三个参数分量，表示匹配串（块）所占据的更为复杂的区域的大小，如梯形的上底、下底和高；这三个参数分量可以用一个自然数三元组（X，Y，Z）来表示，也可以用一个自然数L来表示；（X，Y，Z）与L可以通过一个在编码过程和解码过程中根据一种规则确定的2个自然数W和H来互相转换；转换的过程一般可分成两步，第一步是自然数对（X，Y）与自然数U之间的互相转换，第二步是自然数对（U，Z）与自然数L之间的互相转换。

  

像素值用调色板和索引来表示的实施例

像素值用一个含K个特定像素值的调色板和调色板中元素的索引k（0 ≤ k < K）来精确或近似地表示。调色板可以是静态的也可以是在编码过程和解码过程中被动态地更新；本发明的任意形状匹配方法和装置中所有涉及到“像素值”的地方都可以用像素值的“索引”来取代；例如，匹配当前样值，匹配参考样值，参考像素样值集等用匹配当前样值索引，匹配参考样值索引，参考像素样值索引集等来取代。

  

不同的匹配模式采用不同种类的重构像素的实施例

有两种种类的重构像素：种类I和种类II，有3种匹配模式：模式A、模式B、模式C；模式A和模式B采用种类I的重构像素，而模式C采用种类II的重构像素；也就是，对当前CU进行任意形状匹配编码或解码时，根据当前CU的匹配模式按照下列逻辑关系确定当前CU采用哪种重构像素作为参考像素：

如果（匹配模式==模式A）则采用种类I的重构像素作为参考像素；

如果（匹配模式==模式B）则采用种类I的重构像素作为参考像素；

如果（匹配模式==模式C）则采用种类II的重构像素作为参考像素；

以上符号“==”表示“相等于”。

  

同一匹配模式中，在不同的匹配位置采用不同种类的重构像素的实施例

有两种种类的重构像素：种类I和种类II，参考像素样值集被划分成3个部分：部分A、部分B和部分C；当匹配参考像素值在部分A和部分B时采用种类I的重构像素，而当匹配参考像素值在部分C时采用种类II的重构像素；也就是，对当前CU进行任意形状匹配编码或解码时，根据当前匹配串（块）的匹配位置按照下列逻辑关系确定当前匹配串（块）采用哪种重构像素作为参考像素：

如果（由匹配位置指定的匹配参考像素值位于部分A）则采用种类I的重构像素作为参考像素；

如果（由匹配位置指定的匹配参考像素值位于部分B）则采用种类I的重构像素作为参考像素；

如果（由匹配位置指定的匹配参考像素值位于部分C）则采用种类II的重构像素作为参考像素。

  

压缩码流中序列参数集含参考像素样值集的种类数及其大小的实施例

所述压缩码流的序列参数集含有载入了下列信息的语法元素：

… … 、参考像素样值集的种类数P、第1种类参考像素样值集的大小、第2种类参考像素样值集的大小、… … 、第P种类参考像素样值集的大小、… …

或者，只有一个种类的参考像素样值集的大小需要写入序列参数集（没有其他种类的参考像素样值集或者其他种类的参考像素样值集的大小不需要写入序列参数集）的情形，所述压缩码流的序列参数集含有载入了下列信息的语法元素：

… … 、参考像素样值集的大小、… …

含任意形状匹配的匹配参数的压缩数据以及其他编码结果的压缩码流的实施例1

所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式、CU头第二部分、（匹配位置，匹配大小）或未匹配像素样值1、（匹配位置，匹配大小）或未匹配像素样值2、（匹配位置，匹配大小）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

压缩码流中的匹配位置，匹配大小，未匹配像素样值等匹配参数，可以是这些匹配参数本身，也可以是这些匹配参数经过预测编码、匹配编码、变换编码、量化编码、DPCM、一阶和高阶差分编码、映射编码、游程编码、索引编码等各种常用技术编码后的变体；

所述匹配位置可以仅有一个参数分量，也可以有两个参数分量，或者进一步划分成三个参数分量（例如CU的序号和CU内的水平分量以及垂直分量）甚至四个参数分量；两个参数分量可以用一个数值来表示，也可以用两个数值来表示；三个参数分量可以用一个数值来表示，也可以用两个或三个数值来表示；四个参数分量可以用一个数值来表示，也可以用两个或三个或四个数值来表示；

所述匹配大小可以仅有一个参数分量，也可以有两个，三个甚至四个参数分量；两个参数分量可以用一个数值来表示，也可以用两个数值来表示；三个参数分量可以用一个数值来表示，也可以用两个或三个数值来表示；四个参数分量可以用一个数值来表示，也可以用两个或三个或四个数值来表示；

所述（匹配位置，匹配大小）和所述未匹配像素样值可以用不同的格式来表示，也可以用统一的格式来表示。

  

含任意形状匹配的匹配参数的压缩数据以及其他编码结果的压缩码流的实施例2

所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式标识位或空、匹配模式标识码或匹配模式部分标识码或空、CU头第二部分、（匹配位置，匹配大小）或未匹配像素样值1、（匹配位置，匹配大小）或未匹配像素样值2、（匹配位置，匹配大小）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

所述匹配模式标识位可以取值1或0；

如果所述匹配模式标识位为空，则隐示所述匹配模式标识位取一个预先设定的固定值。

如果所述匹配模式标识位取值1，那么压缩码流中还有匹配模式标识码这个语法元素（但没有匹配模式部分标识码这个语法元素），所述匹配模式标识码可以取以下几个码值并具有以下语义： 

码值	语义
		0	当前CU采用匹配模式1
1	当前CU采用匹配模式2
		2	当前CU采用匹配模式3
…	……………………………………
		A-1	当前CU采用匹配模式A

如果所述匹配模式标识位取值0，那么压缩码流中还有匹配模式部分标识码这个语法元素（但没有匹配模式标识码这个语法元素），所述匹配模式部分标识码可以取B（B < A）个码值，所述匹配模式部分标识码的码值本身并不能完全确定当前CU采用哪种匹配模式，而是必须与对当前CU以及邻近CU的特性进行分析评估的结果结合起来才能完全确定当前CU采用哪种匹配模式，所述当前CU以及邻近CU的特性的例有：邻近CU的编码方式、预测或匹配模式、运动矢量、匹配位置，使用若干种或全部A种匹配模式对当前CU先做一轮部分预解码的结果的特性，邻近CU的解码重构像素样值和当前CU的部分预解码重构像素样值的特性如属于连续色调内容还是非连续色调内容；所述匹配模式部分标识码也可能为空，在这种情形，完全由对当前CU以及邻近CU的特性进行分析评估的结果来确定当前CU采用哪种匹配模式。

  

含任意形状匹配的匹配参数的压缩数据以及其他编码结果的压缩码流的实施例3

所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式、调色板或部分调色板或空、代表像素缓存或部分代表像素缓存或空、CU头第二部分、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值1、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值2、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

所述调色板是在用调色板和索引来精确或近似地表示输入原始像素的颜色的前处理过程中产生的；多个CU可能共享一个不断更新的调色板，所以不一定每个CU的压缩码流中都含有整个调色板，可以仅含有需要更新的部分调色板或不含有调色板；

所述代表像素缓存是用于二级短匹配的，特别是对未匹配像素值或未匹配像素值索引的二级短匹配；多个CU可能共享一个不断更新的代表像素缓存，所以不一定每个CU的压缩码流中都含有整个代表像素缓存，可以仅含有需要更新的部分代表像素缓存或不含有代表像素缓存；

所述（二级短匹配的匹配序号，二级短匹配的匹配长度或空）是短匹配在所述代表像素缓存中找到的匹配序号和匹配长度；在仅对在参考像素样值集或参考像素样值索引集中未找到匹配或匹配大小为1的像素值或像素值索引进行二级短匹配编码并且二级短匹配的匹配长度只能为一个预先设定的固定值（如1，表示二级短匹配只有一个像素值）的特殊情形，所述二级短匹配的匹配长度的语法元素为空，隐示所述二级短匹配的匹配长度取所述预先设定的固定值。

所述代表像素缓存可以不同于所述调色板，也可以等同于所述调色板。 

  

“像素”的扩展

大像素是把若干相邻像素看成是一个“复合像素”。图15是大像素的若干例子，说明如下。

一个CU有16x16个像素（单像素）。 

如果水平相邻2个单像素组成1个大像素，那么1个宏块就有8x16个大像素。对这样的大像素，如果像素格式是YUV4:2:2，那么一个大像素就有4个像素分量，即2个亮度Y分量、1个色度U分量、1个色度V分量。 

如果垂直相邻2个单像素组成1个大像素，那么1个宏块就有16x8个大像素。 

如果水平垂直相邻4个单像素组成1个大像素，那么1个宏块就有8x8个大像素。对这样的大像素，如果像素格式是YUV4:2:0，那么一个大像素就有6个像素分量，即4个亮度Y分量、1个色度U分量、1个色度V分量。 

本发明中所有涉及到像素样值匹配编码和解码的装置与方法，都可以将其中的编码或解码的最基本元素（统称为像素样值或样值或像素值）定义成“大像素”而变成涉及到大像素匹配编码的装置和方法；特别是，本发明的装置与方法，都可以适用于YUV4:2:2像素格式和YUV4:2:0像素格式的编码和解码。 

  

附图说明

图1是现有技术中编码方法流程示意图 

图2是现有技术中解码方法流程示意图

图3是现有技术中编码装置的模块组成示意图

图4是现有技术中解码装置的模块组成示意图

图5是任意形状匹配编码时，针对当前编码CU，在历史像素中搜索多段任意形状匹配串

图6是任意形状匹配解码时，从历史像素中把多段任意形状匹配串复制后粘贴到当前编码CU

图7是本发明的编码方法流程示意图

图8是本发明的解码方法流程示意图

图9是本发明的编码装置的模块组成示意图

图10是本发明的解码装置的模块组成示意图

图11是编码方法的一个实施例的流程示意图

图12是解码方法的一个实施例的流程示意图

图13是编码装置的一个实施例的模块组成示意图

图14是解码装置的一个实施例的模块组成示意图

图15是大像素的若干例子。

Claims (23)

1.一种图像编码方法，其特征在于包括以下步骤：

步骤1）      像素特性分析评估、前处理和编码方式选择步骤；对当前CU和邻近CU的像素样值特性进行分析评估，对输入像素样值进行必要的前处理，预先判断任意形状匹配编码方式是否适合用来对当前CU进行编码，本步骤是可选的，即可以跳过本步骤，直接进入下一步骤；

步骤2）      任意形状匹配编码步骤；使用任意形状匹配编码方式和已编码的历史像素(重构像素)暂存区（也称为参考像素样值集）对当前CU进行任意形状匹配编码运算；所述任意形状匹配编码的输入是输入原始像素或其经过前处理的像素；所述任意形状匹配编码的输出是匹配串(块)的匹配位置及匹配大小或其变体，未匹配像素值或其变体，匹配残差和其他任意形状匹配编码结果参数和变量；所述匹配位置是用来表示与所述当前CU中匹配当前像素值相匹配的匹配参考像素值在所述参考像素样值集内的什么位置的变量参数；所述任意形状匹配编码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行匹配编码，所述匹配参考像素值形成所述参考像素样值集内的一个匹配串或匹配块，称为匹配参考串或匹配参考块，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在所述任意形状匹配编码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示；由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；所述未匹配像素值是依据预先确定的匹配准则在所述参考像素样值集内未找到匹配的输入原始像素样值或其经过前处理的像素样值；所述未匹配像素值是一个输入原始像素样值或其经过前处理的像素样值，所以也可以用其在当前CU中的位置来表示；所述未匹配像素值也可以用一个通过计算得到的有损或无损的仿匹配样值来近似；如果匹配大小为1，这个匹配串（块）也可以作为未匹配像素值来处理；所述匹配残差是输入原始像素样值与所述匹配参考像素值之差，如果任意形状匹配编码方式预先确定的匹配准则是绝对精确的无损匹配，则所述匹配残差为零，即这种任意形状匹配编码方式就没有匹配残差作为输出，如果一种任意形状匹配编码方式预先确定的匹配准则是近似的有损匹配，则所述匹配残差可能不为零，另一种有损匹配的情形是首先对输入原始像素样值进行样值量化、颜色量化或者基于颜色的像素聚类、用调色板和索引来近似表示输入原始像素的颜色的前处理，然后再进行任意形状匹配编码，在这种情形，由于样值量化、颜色量化或者基于颜色的像素聚类、调色板和索引表示的像素是有损的，即使任意形状匹配编码本身是无损的，所述匹配残差（即输入原始像素样值与所述匹配参考像素值之差）也可能不为零；对所述当前CU进行任意形状匹配编码的最基本和本质的结果是I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值，输出I对（匹配位置，匹配大小）和J个未匹配像素值；所述I个匹配串(块)和J个未匹配像素值无缝拼接正好形成当前编码CU完整的正方形状；

步骤3）      其余的匹配方式和各种常用技术编码与重构运算步骤，完成当前CU的所有其余编码和重构运算，对输入视频图像的输入原始像素、各种参数和变量进行其他匹配方式和各种常用技术的编码与重构运算以及熵编码运算；所述其余的匹配方式是指编码方法中不同于所述步骤2）进行的任意形状匹配编码的匹配方式；本步骤的输入是上述步骤1）和步骤2）的输出和输入原始像素以及来自所述参考像素样值集的参考像素；本步骤的输出是重构像素（包括完全重构像素和不同程度的部分重构像素）和含任何形状匹配编码结果和其他编码结果的压缩码流；所述重构像素放入所述参考像素样值集之中，用作后续任意形状匹配编码运算、其余的匹配方式和各种常用技术编码与重构运算步骤所需要的参考像素；所述压缩码流是本编码方法的最后输出，包含了对应的解码方法进行解码与重构所需要的全部语法元素，特别是匹配位置及匹配大小或其变体、未匹配像素值或其变体等语法元素。

2.一种图像解码方法，其特征在于包括以下步骤：

步骤1）      压缩码流数据解析与部分解码步骤；对输入的含任意形状匹配编码的匹配位置及匹配大小或其变体、未匹配像素值或其变体的压缩数据以及所有其他语法元素压缩数据的压缩码流进行熵解码，并解析出熵解码得到的各种数据的意义，对一部分语法元素，特别是与任意形状匹配编码有关的语法元素，进行熵解码后的部分解码；把解析和部分解码后得到的匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数输出给后续任意形状匹配解码步骤；把解析得到的所有其他语法元素如与任意形状匹配残差、其余的匹配方式的匹配模式和匹配参数、各种常用技术的编码结果等有关的语法元素的熵解码结果输出数据（即熵解码的结果）输出给后续其余的匹配方式和各种常用技术解码与重构运算步骤；特别是，依据从压缩码流数据中解析得到的信息或者依据从压缩码流数据中解析得到的信息再加上对当前CU以及邻近CU的特性进行分析评估的结果，决定是否对当前CU进行任意形状匹配解码；如果决定对当前CU进行任意形状匹配解码，则顺序执行下一步骤，否则，跳至步骤3）；

步骤2）      任意形状匹配解码步骤；使用任意形状匹配解码方式和已完成解码的历史像素（重构像素）暂存区（也称为参考像素样值集）对当前CU进行任意形状匹配解码运算；所述任意形状匹配解码运算的输入是在步骤1）中从压缩码流数据中解析和解码得到的I（I ≥ 0）对（匹配位置，匹配大小）或其变体和J（J ≥ 0）个未匹配像素值或其变体等任意形状匹配参数；所述匹配位置是用来表示从参考像素样值集内的什么位置复制匹配参考样值并将其粘贴到当前CU的匹配当前样值的位置；任意形状匹配解码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行任意形状匹配解码，所述匹配参考样值形成所述参考像素样值集内的一个匹配串(块)，称为匹配参考串(块)，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在任意形状匹配解码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示，由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；所述未匹配像素值是直接从压缩码流数据中解析和解码得到的像素值并将其粘贴到当前CU的当前解码中像素值的位置，所述未匹配像素值通常不存在于所述参考像素样值集；如果从压缩码流数据中解析和解码得到的不是未匹配像素值本身而是未匹配像素值的位置，那么就把未匹配像素值的位置输出到后续步骤3）以计算仿匹配像素值；所述任意形状匹配解码运算的输出是所述匹配当前样值（在数值上与匹配参考样值相等）加上所述未匹配像素值（或其位置）；所述匹配当前样值和可能存在的所述未匹配像素值（或其位置）全部合起来就构成所述当前CU的完整的任意形状匹配解码输出；最后得到的I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值无缝拼接正好形成当前解码CU完整的正方形状；进行任意形状匹配解码运算时，首先确定匹配参考样值在历史像素(重构像素)暂存模块（也称为参考像素样值集）中所处的位置以及确定由匹配参考样值构成的匹配区域（匹配区域可以是匹配串或匹配块）的形状大小，然后从所述位置复制所述形状大小的所述匹配区域内的匹配参考样值，并将所述匹配参考样值移动和粘贴到当前解码中匹配当前样值的位置，复原出匹配当前样值；本模块的输出是所有复原的所述匹配当前样值以及可能的未匹配像素值；

步骤3）      其余的匹配方式和各种常用技术解码与重构运算步骤，完成当前CU的所有其余解码和重构运算，对当前解码中匹配串（或匹配块）或当前解码中CU的各种参数和变量进行其他匹配方式和各种常用技术的解码和重构运算；所述其他匹配方式是指解码方法中不同于所述步骤2）进行的任意形状匹配解码的匹配方式；本步骤的输入是上述步骤1）输出的所有其他语法元素如匹配残差的熵解码输出数据和步骤2）的输出即所述匹配当前样值加上可能存在的所述未匹配像素值（或其位置），以及来自所述参考像素样值集内的参考像素；本步骤的输出是重构像素（包括完全重构像素和不同程度的部分重构像素）；所述重构像素放入所述参考像素样值集之中，用作后续任意形状匹配解码运算、其余的匹配方式和各种常用技术解码与重构运算步骤所需要的参考像素；所述完全重构像素也是本解码方法的最后输出。

3.一种图像编码装置，其特征在于包括以下模块：

模块1）      像素前处理和任意形状匹配编码模块：对输入视频图像像素值施行像素前处理和任意形状匹配编码，产生并输出匹配串(块)的匹配位置及匹配大小或其变体，未匹配像素值或其变体，匹配残差和其他任意形状匹配编码结果参数和变量；所述匹配位置是用来表示与所述当前CU中匹配当前像素值相匹配的匹配参考像素值在历史像素(重构像素)暂存模块（也称为参考像素样值集）内的什么位置的变量参数；所述任意形状匹配编码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行匹配编码，所述匹配参考像素值形成所述参考像素样值集内的一个匹配串或匹配块，称为匹配参考串或匹配参考块，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在所述任意形状匹配编码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示；由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；所述未匹配像素值是依据预先确定的匹配准则在所述参考像素样值集内未找到匹配的输入原始像素样值或其经过前处理的像素样值；所述未匹配像素值是一个输入原始像素样值或其经过前处理的像素样值，所以也可以用其在当前CU中的位置来表示；所述未匹配像素值也可以用一个通过计算得到的有损或无损的仿匹配样值来近似；如果匹配大小为1，这个匹配串（块）也可以作为未匹配像素值来处理；所述匹配残差是输入原始像素样值与所述匹配参考像素值之差，如果任意形状匹配编码方式预先确定的匹配准则是绝对精确的无损匹配，则所述匹配残差为零，即这种任意形状匹配编码方式就没有匹配残差作为输出，如果一种任意形状匹配编码方式预先确定的匹配准则是近似的有损匹配，则所述匹配残差可能不为零，另一种有损匹配的情形是首先对输入原始像素样值进行样值量化、颜色量化或者基于颜色的像素聚类、用调色板和索引来近似表示输入原始像素的颜色的前处理，然后再进行任意形状匹配编码，在这种情形，由于样值量化、颜色量化或者基于颜色的像素聚类、调色板和索引表示的像素是有损的，即使任意形状匹配编码本身是无损的，所述匹配残差（即输入原始像素样值与所述匹配参考像素值之差）也可能不为零；对所述当前CU进行任意形状匹配编码的最基本和本质的结果是I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值，输出I对（匹配位置，匹配大小）和J个未匹配像素值；所述I个匹配串(块)和J个未匹配像素值无缝拼接正好形成当前编码CU完整的正方形状；

模块2）      其余的匹配方式和各种常用技术编码与重构模块：对输入视频像素、各种参数和变量施行其他匹配方式和各种常用技术的编码与重构运算以及熵编码运算；所述其余的匹配方式是指编码装置中不同于所述模块1）施行的任意形状匹配编码的匹配方式；本模块的输入是所述模块1）的输出、原始的所述输入视频像素和来自所述参考像素样值集的参考像素；本模块的输出是重构像素值（包括完全重构像素和不同程度的部分重构像素）和含任何形状匹配编码结果和其他编码结果的压缩码流；所述重构像素值放入已重构参考像素值暂存模块中，用作后续任意形状匹配编码运算、其余的匹配方式和各种常用技术编码和重构运算所需要的参考像素值；所述压缩码流是本编码装置的最后输出，包含了对应的解码方法进行解码与重构所需要的全部语法元素，特别是匹配位置及匹配大小或其变体、未匹配像素值或其变体等语法元素；

模块3）      历史像素(重构像素)暂存模块：也称为参考像素样值集，暂存已重构的像素值，即在编码过程中到当前编码中CU或当前编码中匹配区域（可以是匹配串或匹配块）的开始位置为止的已重构像素值，用作当前和后续任意形状匹配编码的参考像素值，也用作对当前和后续CU施行其余的匹配方式和各种常用技术的编码和重构运算时所需要的参考像素值；重构像素值通常是经历过多道工序后才达到完全的重构的；因此，参考像素样值集内存储的重构像素值一般包括不同种类的完全重构像素和不同程度的部分重构像素即仅经历过部分工序的重构像素；不同的匹配模式可以采用同一种类的重构像素作为参考像素，也可以采用不同种类的重构像素作为参考像素；同一匹配模式中，也可以在不同的匹配位置采用不同种类的重构像素作为参考像素。

4.一种图像解码装置，其特征在于包括以下模块：

模块1）      码流数据解析与部分解码模块：对输入的含任意形状匹配编码的匹配位置及匹配大小或其变体、未匹配像素值或其变体的压缩数据以及所有其他语法元素压缩数据的压缩码流施行熵解码，并解析出熵解码得到的各种数据的意义，对一部分语法元素，特别是与任意形状匹配编码有关的语法元素，进行熵解码后的部分解码；把解析和部分解码后得到的匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数送往任意形状匹配解码模块；把解析得到的匹配残差等其他任意形状匹配编码结果、其余的匹配方式的匹配模式和匹配参数、各种常用技术的编码结果等的语法元素的熵解码结果输出数据（即熵解码的结果）送往其余的匹配方式和各种常用技术解码与重构模块；

模块2）      任意形状匹配解码模块：根据所述匹配位置及匹配大小或其变体、未匹配像素值或其变体等任意形状匹配参数施行任意形状匹配解码运算；本模块的输入是所述模块1）输出的从压缩码流数据中解析和解码得到的I（I ≥ 0）对（匹配位置，匹配大小）或其变体和J（J ≥ 0）个未匹配像素值或其变体等任意形状匹配参数；所述匹配位置是用来表示从参考像素样值集内的什么位置复制匹配参考样值并将其粘贴到当前CU的匹配当前样值的位置；任意形状匹配解码方式以可变大小的像素样值串或块（称为匹配当前串或匹配当前块，其位置既可用一个2维坐标也可用一个线性地址来表示）为单位进行任意形状匹配解码，所述匹配参考样值形成所述参考像素样值集内的一个匹配串(块)，称为匹配参考串(块)，其位置也是既可用一个2维坐标也可用一个线性地址来表示，因而在任意形状匹配解码方式中，所述匹配位置既可用匹配参考串(块)的2维坐标与匹配当前串(块)的2维坐标之差也可用匹配参考串(块)的线性地址与匹配当前串(块)的线性地址之差，通称为位移矢量来表示，由于匹配参考串(块)的大小（等于匹配当前串(块)的大小）是可变的，所以还需要另一个称为匹配大小的变量参数来表示其大小；所述未匹配像素值是直接从压缩码流数据中解析和解码得到的像素值并将其粘贴到当前CU的当前解码中像素值的位置，所述未匹配像素值通常不存在于所述参考像素样值集；如果从压缩码流数据中解析和解码得到的不是未匹配像素值本身而是未匹配像素值的位置，那么就把未匹配像素值的位置输出到后续步骤3）以计算仿匹配像素值；所述任意形状匹配解码运算的输出是所述匹配当前样值（在数值上与匹配参考样值相等）加上所述未匹配像素值（或其位置）；所述匹配当前样值和可能存在的所述未匹配像素值（或其位置）全部合起来就构成所述当前CU的完整的任意形状匹配解码输出；最后得到的I（I ≥ 0）个匹配串(块)和J（J ≥ 0）个未匹配像素值无缝拼接正好形成当前解码CU完整的正方形状；施行任意形状匹配解码运算时，首先确定匹配参考样值在历史像素(重构像素)暂存模块（也称为参考像素样值集）中所处的位置以及确定由匹配参考样值构成的匹配区域（匹配区域可以是匹配串或匹配块）的形状大小，然后从所述位置复制所述形状大小的所述匹配区域内的匹配参考样值，并将所述匹配参考样值移动和粘贴到当前解码中匹配当前样值的位置，复原出匹配当前样值；本模块的输出是所有复原的所述匹配当前样值以及可能的未匹配像素值；

模块3）      其余的匹配方式和各种常用技术解码和重构模块：对当前解码中匹配串（或匹配块）或当前解码中CU的各种参数和变量施行其他匹配方式和各种常用技术的解码和重构运算；所述其他匹配方式是指解码装置中不同于所述模块2）施行的任意形状匹配解码的匹配方式；本模块的输出是重构像素值（包括完全重构像素值和不同程度的部分重构像素值）；所述重构像素值放入已重构参考像素值暂存模块中，用作后续匹配解码运算、其余的匹配方式和各种常用技术解码和重构运算所需要的参考像素值；所述完全重构像素值也是本解码装置的最后输出；

模块4）      历史像素(重构像素)暂存模块：也称为参考像素样值集，暂存已重构的像素值，即在解码过程中到当前解码中CU或当前解码中匹配区域（可以是匹配串或匹配块）的开始位置为止的已重构像素值，用作当前和后续任意形状匹配解码的参考像素值，也用作对当前和后续CU施行其余的匹配方式和各种常用技术的解码和重构运算时所需要的参考像素值；重构像素值通常是经历过多道工序后才达到完全的重构的；因此，参考像素样值集内存储的重构像素值一般包括不同种类的完全重构像素和不同程度的部分重构像素即仅经历过部分工序的重构像素；不同的匹配模式可以采用同一种类的重构像素作为参考像素，也可以采用不同种类的重构像素作为参考像素；同一匹配模式中，也可以在不同的匹配位置采用不同种类的重构像素作为参考像素。

5.根据权利要求1所述的编码方法，其特征在于所述各步骤分解和细化成以下步骤：

步骤1）      读入一个大小为NxN像素的最大编码单元即LCU的原始像素；

步骤2）      把变量M的初始值设为N；所述变量M表示所述LCU的当前划分中的一个编码单元即CU的大小是MxM像素；

步骤3）      对所述LCU进行基于颜色的像素聚类；针对后续的预测步骤和匹配步骤的需要，可以分别进行像素聚类或者不进行像素聚类；

步骤4）      对1个MxM像素的CU的经过或未经过像素聚类的像素样值进行基于邻近像素样值的帧内预测编码和基于方块的帧间预测编码，统称为预测编码，产生出（1）预测残差和（2）预测模式和运动矢量；预测编码中需要尝试多种帧内预测模式和多种帧间预测模式（统称为预测模式）；每一种预测模式都会产生相应的预测残差并经历后续步骤9）、10）、11）、12）的运算；

步骤5）      对所述CU的经过或未经过像素聚类的像素样值进行任意形状匹配编码，产生出（1）匹配残差和（2）匹配串（块）的匹配位置p和匹配大小s；所述任意形状匹配编码的过程是：按照一种或几种预先规定的匹配模式，在已经完成编码的历史像素集合中搜索，逐个找到多个与所述CU中的像素样值相匹配的最优的匹配串（块）；所述多个匹配串（块）无缝拼接形成所述CU完整的正方形状；如果所述匹配是精确的无损匹配，则无所述匹配残差（所述匹配残差为零）；如果所述匹配是近似的有损匹配，则所述匹配残差不为零，一般需要对所述匹配残差进行后续的可选的变换编码步骤以及量化编码步骤，但如果匹配残差很小，也可以把所述匹配残差视为零而不进行后续的可选的变换编码步骤以及量化编码步骤；如果本步骤采用了多种预先规定的匹配模式，则每一种匹配模式都会产生相应的匹配残差并经历后续步骤9）、10）、11）、12）的运算；

步骤6）      如果一个所述匹配串（块）的匹配大小s大于某个阈值S，则跳至步骤8），否则，这个所述匹配串（块）是一个短匹配串（块），对其进行如下的二级短匹配编码：在一个代表像素缓存（其中每个代表像素及像素样值都有一个序号）中搜索是否能找到匹配串（称为二级匹配串）；如果能找到二级匹配串，就输出所述二级匹配串的匹配序号（即所述二级匹配串的第一个像素样值在所述代表像素缓存中的序号）及匹配长度，否则，输出原来步骤5）产生的在所述历史像素中找到的所述匹配串的匹配位置及匹配大小；S＝0就是仅对未匹配像素样值进行二级短匹配编码，S＝1，就是仅对未匹配像素样值和匹配大小为1的匹配串（块）进行二级短匹配编码；

步骤7）      更新代表像素缓存；如果这个所述短匹配串的匹配大小s=0，也就是在步骤5）和步骤6）都没有找到任何匹配导致所述CU中当前编码中像素样值成为未匹配像素样值，那么就要根据某种预先确定的规则来决定是否把所述未匹配像素样值放入所述代表像素缓存，并且决定是否要从所述代表像素缓存中删除某个像素样值；

步骤8）      选择匹配编码的输出：如果这个所述匹配串（块）的匹配大小s＝0，则输出所述未匹配像素样值，否则，如果步骤6）在所述代表像素缓存中找到所述二级匹配串，则输出所述二级匹配串的匹配序号及匹配长度，否则，输出原来步骤5）找到的这个所述匹配串（块）的匹配位置及匹配大小；

步骤9）      对步骤4）和5）产生的所述预测残差和所述匹配残差进行变换编码，产生出变换系数；变换编码是分别可选的，也就是如果对所述预测残差进行变换编码达不到更好的数据压缩效果，就不对所述预测残差进行变换编码，如果对所述匹配残差进行变换编码达不到更好的数据压缩效果，就不对所述匹配残差进行变换编码；

步骤10）    对所述预测残差的所述变换系数（在前一步骤进行了变换编码的情形）或所述预测残差本身（在前一步骤不进行变换编码的情形）进行量化编码，产生量化预测变换系数或量化预测残差；对所述匹配残差的所述变换系数（在前一步骤进行了变换编码的情形）或所述匹配残差本身（在前一步骤不进行变换编码的情形）进行量化编码，产生量化匹配变换系数或量化匹配残差；在无损编码的情形，量化编码运算是等同运算，不产生任何实际的量化效果；

步骤11）    对步骤4）、9）、10）的预测-变换-量化编码方式（即基于预测的编码方式，简称为预测方式）的结果进行所述预测方式的逆运算，并且对步骤5）、9）、10）的匹配-变换-量化编码方式（即基于匹配的编码方式，简称为匹配方式）的结果进行所述匹配方式的逆运算，得到所述CU的对应于多种所述预测模式和多种所述匹配模式的多种初步重构像素，用于后续步骤13）的率-失真成本计算，并在后续步骤16）确定了对所述LCU的最优划分及其对各CU的最优编码方式之后，对所述最优划分的所有初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经后处理的各重构CU的像素放入历史像素（重构像素）暂存区，用作后续匹配编码、预测编码和重构的参考像素；

步骤12）    对步骤4）产生的所述预测模式和运动矢量、步骤8）产生的所述匹配编码的输出、以及步骤10）产生的所述量化预测变换系数、量化预测残差、量化匹配变换系数和量化匹配残差进行熵编码并产生压缩码流的比特率；熵编码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化预测变换系数、量化预测残差、量化匹配变换系数、量化匹配残差等熵编码对象的样值先进行基于1维或2维邻近样值的差分编码或索引编码，以去除样值之间的相关性，提高熵编码的效率；

步骤13）    从所述CU的所述原始像素、所述多种初步重构像素及其压缩码流的比特率或者比特率估计值，计算得到率-失真成本，根据率-失真性能选择所述CU的最优编码方式（基于匹配的编码方式还是基于预测的编码方式）、最优匹配模式或最优预测模式并暂存所述CU的最优压缩码流数据；

步骤14）    判断是否已经完成对当前划分中所有MxM像素CU的编码，如果是，则顺序执行下一步骤，否则跳至步骤4）开始下一个MxM像素CU的编码；

步骤15）    判断是否M已经达到预先设定的最小值，如果是，则顺序执行下一步骤，否则，把M减半（即划分的深度加1），然后跳至步骤4）开始下一个深度的划分中所有MxM像素CU的编码；

步骤16）    从已完成的多个不同深度（不同大小MxM像素的CU）的划分的编码结果中，根据率-失真性能选择一个最优的MxM像素的CU的划分并输出该划分相应的压缩码流数据；

步骤17）    判断是否已完成所有LCU的编码，如果是，则结束编码，否则回到步骤1)，开始对下一个LCU的编码。

6.根据权利要求2所述的解码方法，其特征在于所述各步骤分解和细化成以下步骤：

步骤1）      读入图像的部分压缩码流数据；

步骤2）      进行一个编码单元即CU的熵解码，得到所述CU的头信息和数据信息；头信息包括所述CU编码时采用的是预测方式还是匹配方式；所述CU采用了哪种任意形状匹配模式，或所述CU采用了基于邻近像素样值的帧内预测还是采用了基于方块的帧间预测；是否进行逆变换解码；熵解码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、匹配序号、匹配长度、未匹配像素样值、量化变换系数、量化预测残差、量化匹配残差等熵解码对象的基于1维或2维邻近样值的差分解码或索引解码；在匹配模式下，所述CU可以由一个或多个匹配串（块）拼接组成，每个匹配串（块）都要经历后续步骤6）、7）、8）的运算；

步骤3）      对所述量化变换系数或量化预测残差或量化匹配残差进行反量化解码，产生出变换系数或预测残差或匹配残差；

步骤4）      如果前一步骤产生的是变换系数，则进行逆变换解码，产生出预测残差或匹配残差，否则，顺序执行下一步骤；

步骤5）      如果步骤3）或4）产生的是预测残差，则进行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，统称为预测解码，产生出所述预测方式的初步重构像素，然后跳至步骤9），否则，顺序执行下一步骤；

步骤6）      如果步骤2）熵解码得到的一个所述匹配串（块）是由匹配序号及长度来表示的，则进行短匹配解码，从一个代表像素存储中复制得到短匹配串的像素样值；

步骤7）      更新所述代表像素缓存；如果所述匹配串（块）的匹配大小s=0，也就是步骤2）熵解码得到一个未匹配像素样值，那么就要根据某种预先确定的规则来决定是否把所述未匹配像素样值放入所述代表像素缓存，并且决定是否要从所述代表像素缓存中删除某个像素样值；

步骤8）      任意形状匹配解码；根据步骤2）得到的任意形状匹配模式，把可以具有任意形状的匹配串（块）移动和粘贴到所述CU的当前被匹配串（块）的位置，再加上来自步骤3）或4）的所述匹配残差，产生出所述匹配方式的初步重构像素；所述任意形状的匹配串（块）可以是来自步骤2）的所述未匹配像素样值，或者是来自步骤6）的所述短匹配串，或者是来自历史像素暂存区中由匹配位置p和匹配大小s这两个匹配参数决定的匹配串（块）；

步骤9）      对所述预测方式的初步重构像素或所述匹配方式的初步重构像素进行去块效应滤波和像素补偿运算的后处理，然后把经所述后处理的所述CU的重构像素放入历史像素（重构像素）暂存区，用作后续任意形状匹配解码和预测解码的参考像素；

步骤10）输出所述CU的所述重构像素 ；

步骤11）    判断是否已经完成对一个LCU中所有CU的压缩码流数据的解码，如果是，则顺序执行下一步骤，否则回到步骤1)，开始对下一个CU的解码；

步骤12）    判断是否已经完成对所有LCU的压缩码流数据的解码，如果是，则结束解码，否则回到步骤1)，开始对下一个LCU的解码。

7.根据权利要求3所述的编码装置，其特征在于所述各模块分解和细化成以下模块：

模块1）      可以存储当前编码中最大编码单元即LCU中一种深度的划分中至少一个编码单元即CU的像素的存储模块；

模块2）      预测编码模块：对输入像素施行基于邻近像素样值的帧内预测编码和基于方块（block）的帧间预测编码，并输出（1）预测残差和（2）预测模式和运动矢量；本模块可施行多种帧内预测模式和多种帧间预测模式（统称为预测模式）下的编码；

模块3）      基于颜色的像素聚类模块：把所述输入像素中某些很接近的颜色合并成一个颜色，以提高后续的匹配编码的效率，找到尺寸更大，误差更小的匹配串（块）；在原有颜色已经比较少的情形，或者进行超高品质编码和无损编码的情形，此模块可以被旁路；

模块4）      任意形状匹配搜索编码模块：对经过或未经过像素聚类的所述输入像素样值施行任意形状匹配编码，并输出（1）匹配残差、（2）多个匹配串（块）的匹配位置p和匹配大小s、（3）匹配统计信息；本模块可施行一种或多种匹配模式下的编码；

模块5）      短匹配搜索模块：如果所述任意形状匹配搜索编码模块搜索到的某个所述匹配串的匹配大小s小于或等于某个阈值S，则再施行二级短匹配搜索和编码，即在一个代表像素缓存模块（其中每个像素样值都有一个序号）中搜索是否能找到匹配串（称为二级匹配串）；如果能找到二级匹配串，就输出所述二级匹配串的匹配序号（即所述二级匹配串的第一个像素样值在所述代表像素缓存模块中的序号）及匹配长度，否则，输出原来所述任意形状匹配搜索编码模块输出的在历史像素中找到的所述匹配串的匹配位置p及匹配大小s；匹配序号可以用比匹配位置更少的比特数来表示，因而可以提高编码效率；S＝0就是仅对未匹配像素样值进行二级短匹配编码，S＝1，就是仅对未匹配像素样值和匹配大小为1的匹配串（块）进行二级短匹配编码；

模块6）      代表像素缓存模块：存储用于短匹配搜索的代表像素；此模块可以含有一个候选代表像素缓存单元；此模块可以为空；在这种情形，就不施行短匹配搜索，也没有所述短匹配搜索模块和代表像素更新模块；

模块7）      代表像素更新模块：如果所述匹配串的匹配大小s=0，也就是所述任意形状匹配搜索编码模块和所述短匹配搜索模块都没有搜索到任何匹配导致所述CU中当前编码中像素样值成为未匹配像素样值，那么所述未匹配像素样值就是候选的代表像素，被放入所述代表像素缓存模块中的候选代表像素缓存单元；根据某种预先确定的规则来决定所述未匹配像素样值是否立即成为正式的代表像素，还是在收集到一定程度的关于所述像素样值的匹配统计信息数据后再成为正式的代表像素；当所述代表像素存储空间溢出时，就需要决定如何从所述代表像素存储空间中删除某个像素样值；

模块8）      变换模块：对所述匹配残差和预测残差施行变换运算，输出变换系数；对某些类型的屏幕图像像素，变换运算并不能起到压缩数据的效果，在这种情形，就不施行变换运算，也就是变换模块被旁路，直接输出所述匹配残差或所述预测残差；

模块9）      量化模块：对所述变换系数（在变换模块未旁路的情形）或所述匹配残差或预测残差（在变换模块被旁路的情形）施行量化运算，输出量化预测变换系数或量化预测残差，并输出量化匹配变换系数或量化匹配残差；

模块10）    熵编码模块：对所述多个匹配串（块）的匹配位置和匹配大小、所述二级匹配串的匹配序号和匹配长度、所述未匹配像素样值、所述量化匹配变换系数或量化匹配残差等施行熵编码；对所述预测模式、运动矢量、量化预测变换系数或量化预测残差等施行熵编码，包括对这些熵编码对象的样值先施行基于1维或2维邻近样值的差分编码或索引编码；

模块11）    重构及后处理模块：施行所述预测编码模块、变换模块、量化模块这三个模块的逆运算；施行所述任意形状匹配搜索编码模块、变换模块、量化模块这三个模块的逆运算，初步重构出在多种预测模式和多种匹配模式下所述CU的像素，并将初步重构像素输出到基于率-失真性能的最优预测模式与匹配模式和划分选择模块用于率-失真成本的计算；在基于率-失真性能的最优预测模式与匹配模式和划分选择模块确定了对所述LCU的最优划分及其对各CU的最优编码方式及其模式之后，再对所述最优划分的各CU的初步重构像素施行去块效应滤波和像素补偿运算的后处理，然后把经所述后处理的重构CU的像素放入历史像素（重构像素）暂存模块，用作后续CU的预测编码、匹配编码和重构的参考像素；

模块12）    历史像素（重构像素）暂存模块：此模块提供预测编码、匹配编码和重构的参考像素；

模块13）    基于率-失真性能的最优预测模式与匹配模式和划分选择模块：在编码所述LCU的各不同深度的划分中任一个CU时，根据率-失真性能选择所述CU的最优编码方式（基于匹配的编码方式还是基于预测的编码方式）、最优匹配模式、和最优预测模式；在完成对所述LCU的所有不同深度的划分的所有CU的编码后，根据率-失真性能选择所述LCU的最优的深度和相应的划分；

模块14）    压缩码流输出模块：把选择的所述最优划分的编码压缩数据输出到输出视频压缩码流。

8.根据权利要求4所述的解码装置，其特征在于所述各模块分解和细化成以下模块：

模块1）      部分压缩码流数据存储模块；

模块2）      熵解码模块：对输入压缩码流数据施行熵解码，得到当前解码CU的头信息和数据信息；熵解码也包括对预测模式、运动矢量、匹配模式、匹配位置、匹配大小、短匹配的匹配序号、短匹配的匹配长度、未匹配像素样值、量化变换系数、量化预测残差、量化匹配残差等熵解码对象的基于1维或2维邻近样值的差分解码或索引解码；熵解码还包括从所述输入压缩码流数据中解析出当前解码LCU在编码时采用的划分的深度、所述当前解码CU在编码时采用的是预测方式还是匹配方式，采用了哪种任意形状匹配模式，或所述当前解码CU采用了基于邻近像素样值的帧内预测还是采用了基于方块的帧间预测、变换运算是否被旁路等信息；在匹配模式下，所述当前解码CU的数据信息可以含有一个或多个匹配串（块）的信息；

模块3）      反量化模块：施行反量化运算，输出变换系数或预测残差或匹配残差；

模块4）      逆变换模块：如果编码时变换运算未被旁路，则施行逆变换解码，输出预测残差或匹配残差，否则，不施行逆变换解码，直接输出预测残差或匹配残差；

模块5）      预测解码模块：对所述预测残差施行基于邻近像素样值的帧内预测解码或基于方块的帧间预测解码，得到并输出初步重构像素；

模块6）      代表像素缓存模块：此模块的输入是所述熵解码模块输出的短匹配的匹配序号及长度；短匹配的匹配序号是短匹配中第一个像素样值在所述代表像素缓存模块中的序号；根据所述匹配序号及长度，此模块输出有若干代表像素样值组成的短匹配串；

模块7）      代表像素更新模块：此模块的作用是更新所述代表像素缓存模块中的代表像素样值；

模块8）      任意形状匹配解码模块：当本模块的输入是来自所述熵解码模块的一个所述匹配串（块）的匹配位置和大小的时候，本模块的功能是从一个历史像素暂存模块中由所述匹配位置指定的地方复制得到尺寸为所述匹配大小的匹配串（块）的像素样值，然后把所述匹配串（块）的像素样值移动和粘贴到所述当前解码CU的当前被匹配串（块）的位置；当本模块的输入是来自所述代表像素缓存模块的所述短匹配串的时候，本模块的功能是直接把所述短匹配串的像素样值移动和粘贴到所述当前解码CU的当前被匹配串的位置；当本模块的输入是来自熵解码模块的未匹配像素样值的时候，本模块的功能是直接把所述未匹配像素样值移动和粘贴到所述当前解码CU的当前被匹配串的位置；本模块的另一个功能是在粘贴到位的所述被匹配串（块）的像素上，再加上来自所述逆变换模块的所述匹配残差，得到并输出初步重构像素；所述匹配残差也可以全部为零，这时就不需要施行所述的匹配残差加法运算；

模块9）      后处理模块：对初步重构像素施行去块效应滤波和像素补偿运算的后处理，然后把经所述后处理的重构像素放入历史像素（重构像素）暂存模块，用作后续任意形状匹配解码和预测解码的参考像素；

模块10）    历史像素暂存模块：此模块提供任意形状匹配解码和预测解码的参考像素；

模块11）    重构像素输出模块：重构像素是解码装置的最后输出。

9.根据权利要求1所述的编码方法或权利要求2所述的解码方法或权利要求3所述的编码装置或权利要求4所述的解码装置或权利要求5所述的编码方法或权利要求6所述的解码方法或权利要求7所述的编码装置或权利要求8所述的解码装置，其特征在于：在任意形状匹配编码和解码中，未找到匹配的情形，也就是有未匹配像素样值的情形，即可以用匹配大小s=0来表示，也可以用匹配位置p＝0（当前像素样值自己与自己匹配）来表示。

10.根据权利要求1所述的编码方法或权利要求2所述的解码方法或权利要求3所述的编码装置或权利要求4所述的解码装置或权利要求5所述的编码方法或权利要求6所述的解码方法或权利要求7所述的编码装置或权利要求8所述的解码装置，其特征在于：匹配准则可以是无损或精确的匹配，也可以是有损或近似的匹配。

11.根据权利要求1、2、3、4、5、6、7、8、9、10所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述任意形状匹配采用的匹配模式具有以下特征：

采用像素值垂直排列格式，即把一个2维区域的像素值先垂直排列，排列完一列后再排列另一列，和串形匹配格式，即匹配当前像素值和匹配参考像素值都形成像素值的串，两个串具有相等的长度，但不一定保持相同的2维形状；

或者

采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和串形匹配格式，即匹配当前像素值和匹配参考像素值都形成像素值的串，两个串具有相等的长度，但不一定保持相同的2维形状；

或者

采用像素值垂直排列格式，即把一个2维区域的像素值先垂直排列，排列完一列后再排列另一列，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值垂直排列所形成的列所组成，除了第一列和最后一列之外的中间各列都有相同的高度，即这个区域的高度，第一列与这个区域的底部对齐，而最后一列与这个区域的顶部对齐；区域的高度可以与当前CU的高度相等，也可以与当前CU的高度不等而取另外一个任意的值或从当前CU的高度导出的一个值，如当前CU的高度的二分之一或四分之一；第一列和最后一列也可以与中间各列有相同的高度，即等于这个区域的高度，这时，这个区域是一个任意大小的矩形或正方形；在本匹配模式中，匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的高度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形，匹配大小也可以仅用一个参数分量来表示；

或者

采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，除了第一行和最后一行之外的中间各行都有相同的宽度，即这个区域的宽度，第一行与这个区域的右部对齐，而最后一行与这个区域的左部对齐；区域的宽度可以与当前CU的宽度相等，也可以与当前CU的宽度不等而取另外一个任意的值或从当前CU的宽度导出的一个值，如当前CU的宽度的二分之一或四分之一；第一行和最后一行也可以与中间各行有相同的宽度，即等于这个区域的宽度，这时，这个区域是一个任意大小的矩形或正方形；在本匹配模式中，匹配区域是2维区域，匹配大小一般需要用两个或两个以上的参数分量来表示，在匹配区域的宽度可以从编码过程和解码过程中的其他参数或变量导出的特殊情形，匹配大小也可以仅用一个参数分量来表示；

或者

采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，所有行都有相同的宽度；所有行的左端点可以形成一条垂直的直线，这时，这个区域是一个矩形或正方形，也可以形成一条非垂直的斜线，这时，这个区域是一个平行四边形；

或者

采用像素值水平排列格式，即把一个2维区域的像素值先水平排列，排列完一行后再排列另一行，和2维保形匹配格式，即匹配当前像素值和匹配参考像素值都形成2维区域，两个区域具有相等的大小，并且保持相同的2维形状；所述2维区域是由像素值水平排列所形成的行所组成，所有行的左端点形成一条直线，所有行的右端点形成另一条直线；这两条直线可以是平行的，这时，这个区域是一个平行四边形，也可以是非平行的，这时，这个区域是一个梯形；

一幅当前图像中，可以所有CU都使用同一种匹配模式，也可以不同CU自适应地使用不同的匹配模式。

12.根据权利要求1、2、3、4、5、6、7、8、9、10、11所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述任意形状匹配的匹配区域（区域可以是串或块）的匹配位置是匹配当前区域中第一个匹配当前样值与匹配参考区域中第一个匹配参考样值之间的相对位置。

13.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述任意形状匹配的匹配位置可以用一个自然数对（X，Y）来表示；也可以用一个自然数L来表示，（X，Y）与L可以通过一个在编码过程和解码过程中根据一种规则确定的自然数W或H来互相转换。

14.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13所述的编码方法或解码方法或编码装置或解码装置，其特征在于：当前图像被划分成一个一个CU（或LCU），每个CU（或LCU）都被赋予一个序号，序号从零开始逐一递增；当前图像中的每个像素值也都被赋予一个编号（或称线性地址），编号从零开始逐一递增；像素值编号的排列顺序是先从CU（或LCU）序号小的开始排列，一个序号的CU（或LCU）的全部像素值都排列完之后，再排列下一个序号的CU（或LCU）的像素值；而在一个CU（或LCU）内部，像素样值以垂直格式逐列（或者水平格式逐行）排列；匹配区域的匹配位置是匹配参考区域中第一个匹配参考像素值的线性地址（即编号）与匹配当前区域中第一个匹配当前像素值的线性地址（即编号）的差。

15.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14所述的编码方法或解码方法或编码装置或解码装置，其特征在于：匹配参考样值的位置限定于与匹配当前样值具有同样的水平位置或垂直位置，匹配位置的水平分量和垂直分量中有一个为零（或其他常数）；匹配位置可以用一个参数分量的变量和一个表示水平还是垂直位置的标记位来表示。

16.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述任意形状匹配的匹配大小有以下的表示法：

匹配大小只有一个参数分量，表示匹配串的长度；

或者

匹配大小有一个直接参数分量和一个从编码过程或解码过程中的其他参数或变量（如当前CU的高度或宽度）导出的参数分量；

或者

匹配大小有两个参数分量，表示匹配串（块）所占据的区域的宽度和高度；这两个参数分量可以用一个自然数对（X，Y）来表示，也可以用一个自然数L来表示；（X，Y）与L可以通过一个在编码过程和解码过程中根据一种规则确定的自然数W或H来互相转换；

或者

匹配大小有三个参数分量，表示匹配串（块）所占据的更为复杂的区域的大小；这三个参数分量可以用一个自然数三元组（X，Y，Z）来表示，也可以用一个自然数L来表示；（X，Y，Z）与L可以通过一个在编码过程和解码过程中根据一种规则确定的2个自然数W和H来互相转换；转换的过程一般可分成两步，第一步是自然数对（X，Y）与自然数U之间的互相转换，第二步是自然数对（U，Z）与自然数L之间的互相转换。

17.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16所述的编码方法或解码方法或编码装置或解码装置，其特征在于：当前图像或当前CU的所有或部分像素值用一个含K个特定像素值的调色板和调色板中元素的索引k（0 ≤ k < K）来精确或近似地表示；把像素值的所述索引作为对象（取代所述像素值）来进行所述任意形状匹配编码或解码；所述调色板可以是静态的也可以是在编码过程和解码过程中被动态地更新。

18.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17所述的编码方法或解码方法或编码装置或解码装置，其特征在于：有两种种类的重构像素：种类I和种类II，有3种匹配模式：模式A、模式B、模式C；模式A和模式B采用种类I的重构像素，而模式C采用种类II的重构像素；也就是，对当前CU进行任意形状匹配编码或解码时，根据当前CU的匹配模式按照下列逻辑关系确定当前CU采用哪种重构像素作为参考像素：

如果（匹配模式==模式A）则采用种类I的重构像素作为参考像素；

如果（匹配模式==模式B）则采用种类I的重构像素作为参考像素；

如果（匹配模式==模式C）则采用种类II的重构像素作为参考像素；

以上符号“==”表示“相等于”。

19.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18所述的编码方法或解码方法或编码装置或解码装置，其特征在于：有两种种类的重构像素：种类I和种类II，参考像素样值集被划分成2个部分：部分A和部分B；当匹配参考像素值在部分A时采用种类I的重构像素，而当匹配参考像素值在部分B时采用种类II的重构像素；也就是，对当前CU进行任意形状匹配编码或解码时，根据当前匹配串（块）的匹配位置按照下列逻辑关系确定当前匹配串（块）采用哪种重构像素作为参考像素：

如果（由匹配位置指定的匹配参考像素值位于部分A）则采用种类I的重构像素作为参考像素；

如果（由匹配位置指定的匹配参考像素值位于部分B）则采用种类II的重构像素作为参考像素。

20.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述压缩码流的序列参数集含有载入了下列信息的语法元素：

… … 、参考像素样值集的种类数P、第1种类参考像素样值集的大小、第2种类参考像素样值集的大小、… … 、第P种类参考像素样值集的大小、… …

或者，只有一个种类的参考像素样值集的大小需要写入序列参数集（没有其他种类的参考像素样值集或者其他种类的参考像素样值集的大小不需要写入序列参数集）的情形，所述压缩码流的序列参数集含有载入了下列信息的语法元素：

… … 、参考像素样值集的大小、… …。

21.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式、CU头第二部分、（匹配位置，匹配大小）或未匹配像素样值1、（匹配位置，匹配大小）或未匹配像素样值2、（匹配位置，匹配大小）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

压缩码流中的匹配位置，匹配大小，未匹配像素样值等匹配参数，可以是这些匹配参数本身，也可以是这些匹配参数经过预测编码、匹配编码、变换编码、量化编码、DPCM、一阶和高阶差分编码、映射编码、游程编码、索引编码等各种常用技术编码后的变体；

所述匹配位置可以仅有一个参数分量，也可以有两个参数分量，或者进一步划分成三个参数分量（例如CU的序号和CU内的水平分量以及垂直分量）甚至四个参数分量；两个参数分量可以用一个数值来表示，也可以用两个数值来表示；三个参数分量可以用一个数值来表示，也可以用两个或三个数值来表示；四个参数分量可以用一个数值来表示，也可以用两个或三个或四个数值来表示；

所述匹配大小可以仅有一个参数分量，也可以有两个，三个甚至四个参数分量；两个参数分量可以用一个数值来表示，也可以用两个数值来表示；三个参数分量可以用一个数值来表示，也可以用两个或三个数值来表示；四个参数分量可以用一个数值来表示，也可以用两个或三个或四个数值来表示；

所述（匹配位置，匹配大小）和所述未匹配像素样值可以用不同的格式来表示，也可以用统一的格式来表示。

22.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式标识位或空、匹配模式标识码或匹配模式部分标识码或空、CU头第二部分、（匹配位置，匹配大小）或未匹配像素样值1、（匹配位置，匹配大小）或未匹配像素样值2、（匹配位置，匹配大小）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

所述匹配模式标识位可以取值1或0；

如果所述匹配模式标识位为空，则隐示所述匹配模式标识位取一个预先设定的固定值；

如果所述匹配模式标识位取值1，那么压缩码流中还有匹配模式标识码这个语法元素（但没有匹配模式部分标识码这个语法元素），所述匹配模式标识码可以取以下几个码值并具有以下语义：

 

如果所述匹配模式标识位取值0，那么压缩码流中还有匹配模式部分标识码这个语法元素（但没有匹配模式标识码这个语法元素），所述匹配模式部分标识码可以取B（B < A）个码值，所述匹配模式部分标识码的码值本身并不能完全确定当前CU采用哪种匹配模式，而是必须与对当前CU以及邻近CU的特性进行分析评估的结果结合起来才能完全确定当前CU采用哪种匹配模式，所述当前CU以及邻近CU的特性的例有：邻近CU的编码方式、预测或匹配模式、运动矢量、匹配位置，使用若干种或全部A种匹配模式对当前CU先做一轮部分预解码的结果的特性，邻近CU的解码重构像素样值和当前CU的部分预解码重构像素样值的特性如属于连续色调内容还是非连续色调内容；所述匹配模式部分标识码也可能为空，在这种情形，完全由对当前CU以及邻近CU的特性进行分析评估的结果来确定当前CU采用哪种匹配模式。

23.根据权利要求1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22所述的编码方法或解码方法或编码装置或解码装置，其特征在于：所述含任意形状匹配编码结果和其他编码结果的压缩码流中的CU部分由载入了下列信息的语法元素构成：

CU头第一部分、匹配模式、调色板或部分调色板或空、代表像素缓存或部分代表像素缓存或空、CU头第二部分、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值1、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值2、（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值3、…………… 、更多的（匹配位置，匹配大小）或（二级短匹配的匹配序号，二级短匹配的匹配长度或空）或未匹配像素样值、匹配残差或空、其他编码结果；

除了所述CU头第一部分这个语法元素，所有其他所述语法元素在码流中的放置排列顺序并不是唯一的，可采用任意一种预先确定的合理的顺序；任何一个语法元素也可以被拆成几部分，所述几部分可以集中放置在码流中同一地方，也可以分别放置在码流中不同的地方；任何若干语法元素也可以合并成一个语法元素；除了所述CU头第一部分这个语法元素，其他语法元素也可以不存在于某个CU的压缩码流数据中；

所述调色板是在用调色板和索引来精确或近似地表示输入原始像素的颜色的前处理过程中产生的；多个CU可能共享一个不断更新的调色板，所以不一定每个CU的压缩码流中都含有整个调色板，可以仅含有需要更新的部分调色板或不含有调色板；

所述代表像素缓存是用于二级短匹配的，特别是对未匹配像素值或未匹配像素值索引的二级短匹配；多个CU可能共享一个不断更新的代表像素缓存，所以不一定每个CU的压缩码流中都含有整个代表像素缓存，可以仅含有需要更新的部分代表像素缓存或不含有代表像素缓存；

所述（二级短匹配的匹配序号，二级短匹配的匹配长度或空）是短匹配在所述代表像素缓存中找到的匹配序号和匹配长度；在仅对在参考像素样值集或参考像素样值索引集中未找到匹配或匹配大小为1的像素值或像素值索引进行二级短匹配编码并且二级短匹配的匹配长度只能为一个预先设定的固定值（如1，表示二级短匹配只有一个像素值）的特殊情形，所述二级短匹配的匹配长度的语法元素为空，隐示所述二级短匹配的匹配长度取所述预先设定的固定值；

所述代表像素缓存可以不同于所述调色板，也可以等同于所述调色板。