分段可逆视频编码方法、分段可逆视频译码方法、分段可逆视频编码装置、分段可逆视频译码装置和它们的程序及程序记录媒体

摘要

作为基本部分传送的代码保持与H.264标准的兼容性，同时可进行高效率的可逆译码。正交变换部(12)对残差信号Rorig进行正交变换后，再取得变换系数Xorig，量化部(13)对其进行量化。存在空间决定部(14)根据量化信息求出各系数的上下限信息(变换系数的存在空间)。在系数汇总编码部(16)中，判断将变换系数的存在空间内的格子点作为残差信号的正交变换的结果是否妥当，列举判断为妥当的格子点。按照列举顺序分配序号index，利用序号编码部(166)对和残差信号的变换系数Xorig一致的格子点的序号进行编码。

说明书

技术领域

本发明涉及高效率视频编码、译码技术，特别涉及作为基本部分传送的码保持与H.264标准的兼容性，同时尽量减小附加部分的代码量，可进行与原始信号一致的可逆译码的分段可逆视频编码、译码技术。

本申请对2004年9月30日申请的特愿2004-286412号主张优先权，这里引用其内容。

背景技术

现有的可逆或分段视频编码方式有以下一些方式。MotionJPEG2000标准(参照非专利文献1)的可逆方式或JPEG-LS(参照非专利文献2)因为是基于静止图像，故在帧内进行封闭编码。

H.264标准(参照非专利文献3)的第2版“逼真范围扩展(FidelityRange Extension：FRExt)”在帧内和帧间直接传送(不进行正交变换和量化)预测残差信号。

作为与非可逆编码方式组合的分段编码方式，有对译码图像和原始图像的差分进行编码的方式(参照非专利文献4)。这里，虽然在基本信息中使用了MPEG-2，但也可以适用于其他方式。

此外，还有像MPEG-4标准(参照非专利文献5)的精细可伸缩性(Fine Granularity Scalable：FGS)轮廓方式那样，对施加DCT(离散余弦变换)且取整后的数据进行位面展开并进行逐次传送的方式。

非专利文献1：ISO/IEC 15444-3：2002 Information technology-JPEG2000image coding system-Part 3：Motion JPEG 2000

非专利文献2：ISO/IEC 14495-1：1999 Information technology-Lossless and near-lossless coding of continuous tone still images

非专利文献3：ISO/IEC 14496-10：2003 Information technology-Coding of audio-visual objects-Part 10：Advanced Video coding

非专利文献4：中岛、八岛、小林：“基于MPEG-2编码参数的分段无损编码的研究”信学总大D-11-49，Mar.2000

非专利文献5：ISO/IEC 14496-2：2003 Information technology-Coding of audio-visual objects-Part 2：Visual

上述JPEG2000(参照非专利文献1)虽然可分段传送，但因进行帧内编码，故存在不能进行使用了视频特有的帧间相关的高效率编码的问题。此外，上述JPEG-LS(参照非专利文献2)虽然效率比JPEG2000高，但仍然是帧内封闭编码，效率有限，此外，还存在不能分段传送的问题。

H.264标准(参照非专利文献3)的第2版“逼真范围扩展(FidelityRange Extension：FRExt)”存在不能分段传送的问题。

此外，上述非专利文献4记载的特征因不是以正交变换空间内的残差而是以原始信号空间的残差作为编码对象，故编码时不得不考虑原始信号不该存在的空间，压缩效率有限。

MPEG-4标准(参照非专利文献5)的精细可伸缩性(FineGranularity Scalable：FGS)轮廓方式存在以下问题：

^*因在实数变换DCT之后将系数取整，故即使使用很多附加信息也不可逆。

^*若直接使用使像后述式(6)那样变换后的系数扩展的H.264标准方式，则扩展多少就会浪费多少代码量。

像这样，通过进行帧间预测来提高视频编码效率、具有可测量性且基本信息兼容H.264标准的方式还没有提出来。

发明内容

本发明是鉴于上述问题提出的，其目的在于能够使作为基本部分传送的代码保持与H.264标准的兼容性，同时尽量减小附加部分的代码量，并能够进行可逆译码。

为了解决上述问题，本发明第1形态的分段可逆视频编码方法是进行可实现与原始信号一致的译码的视频编码的可逆视频编码方法，包括如下步骤：根据预先确定的非可逆视频编码方式，对图像信号的每一个块输入从原始信号减去帧内编码的空间预测或帧间编码的时间预测的预测信号而得到的残差信号；求出根据上述非可逆视频编码方式对上述残差信号进行正交变换得到的变换系数和将其量化后的量化系数；指定由上述量化系数、量化时使用的量化参数和量化方法确定的变换系数的存在空间；判断将上述变换系数的存在空间内的某格子点作为残差信号的正交变换的结果是否妥当的妥当性判断；按照规定的格子点的顺序搜索并列举在上述变换系数的存在空间内的格子点中判断较妥当的格子点；按照列举的顺序对列举的格子点分配序号；在列举的格子点中得到与残差信号的变换系数一致的格子点的序号；对与上述残差信号的变换系数一致的格子点的序号进行编码并输出。

本发明的第2形态是，在上述分段可逆视频编码方法中，在列举在上述变换系数的存在空间内的格子点中判断是妥当的格子点的步骤中，对于通过使用变换系数间的整数值的关系从而在上述空间内不能取得变换系数这一点，省略作为残差信号的正交变换的结果是否妥当的判断处理。

本发明的第3形态是，在上述分段可逆视频编码方法中，具有代替输出几个特定的变换系数，而输出除了不能利用该系数和已输出的系数的整数值关系来取得该系数的值的信息的步骤，在列举在上述变换系数的存在空间内的格子点中判断较妥当的格子点的步骤中，列举使用上述预先输出的变换系数将维数缩小后的存在空间内的格子点。

本发明的第4形态是，在上述分段可逆视频编码方法中，在上述妥当性判断步骤中，只使用位运算和整数加减运算来判断妥当性。

本发明的第5形态是，在上述分段可逆视频编码方法中，利用残差信号的存在范围和变换系数的存在范围相交形成凸多面体的情况，当作为判断对象的上述格子点存在于上述凸多面体的外部时，途中中止上述妥当性判断。

本发明的第6形态是，在上述分段可逆视频编码方法中，不执行列举在上述变换系数的存在空间内的格子点中判断较妥当的格子点的步骤，而进行代码量的估计。

本发明的第7形态是对利用上述分段可逆视频编码方法编码后的编码数据流进行译码的译码方法，包括如下步骤：执行与预先确定的非可逆视频编码方式对应的译码方式；指定由量化参数、量化系数和编码时的量化方法、以及当具有已译码的系数时由该系数决定的变换系数的存在空间；译码应译码的系数；判断将上述变换系数的存在空间内的某格子点作为残差信号的正交变换的结果是否妥当的妥当性判断；按照和编码时格子点的搜索相同的顺序搜索并列举在上述变换系数的存在空间内的格子点中上述判断较妥当的格子点；对序号进行译码；在上述列举的格子点中输出与上述译码的序号相等的顺序的格子点。

本发明的第8形态的分段可逆视频编码装置是进行可实现与原始信号一致的译码的视频编码的可逆视频编码装置，包括：根据预先确定的非可逆视频编码方式，对图像信号的每一个块输入从原始信号减去帧内编码的空间预测或帧间编码的时间预测的预测信号而得到的残差信号的单元；求出根据上述非可逆视频编码方式对上述残差信号进行正交变换得到的变换系数和将其量化后的量化系数的单元；指定由上述量化系数、量化时使用的量化参数和量化方法决定的变换系数的存在空间的单元；判断将上述变换系数的存在空间内的某格子点作为残差信号的正交变换的结果是否妥当的妥当性判断单元；按照规定的格子点的顺序搜索并列举在上述变换系数的存在空间内的格子点中判断较妥当的格子点的单元；按照列举的顺序对列举的格子点分配序号的单元；在列举的格子点中得到与残差信号的变换系数一致的格子点的序号的单元；对与上述残差信号的变换系数一致的格子点的序号进行编码并输出的单元。

本发明的第9形态是对利用上述分段可逆视频编码装置编码后的编码数据流进行译码的译码装置，包括：执行与预先确定的非可逆视频编码方式相对应的译码方式的单元；指定由量化参数、量化系数和编码时的量化方法、以及当具有已译码的系数时由该系数决定的变换系数的存在空间的单元；译码应译码的系数的系数译码单元；判断将上述变换系数的存在空间内的某格子点作为残差信号的正交变换的结果是否妥当的妥当性判断单元；按照和编码时格子点的搜索相同的顺序搜索并列举在上述变换系数的存在空间内的格子点中上述判断较妥当的格子点的单元；对序号进行译码的序号译码单元；在上述列举的格子点中输出与上述译码的序号相等的顺序的格子点的输出单元。

以上的分段可逆视频编码和译码的处理可以利用计算机和软件程序来实现，将该程序记录在计算机可读取的记录媒体上再向外提供，也可以通过网络提供。

即，本发明的第10形态是用来在计算机上实现本发明的分段可逆视频编码方法的分段可逆视频编码程序。

本发明的第11形态是用来在计算机上执行本发明的分段可逆视频译码方法的分段可逆视频译码程序。

本发明的第12形态是将用来在计算机上实现本发明的分段可逆视频编码方法的程序记录在计算机可读取的记录媒体上的分段可逆视频编码程序的记录媒体。

本发明的第13形态是将用来在计算机上实现本发明的分段可逆视频译码方法的程序记录在计算机可读取的记录媒体上的分段可逆视频译码程序的记录媒体。

若按照本发明，作为基本部分传送的代码可以保持与H.264标准的兼容性，同时，可以尽量减小附加部分的代码量，并进行与原始信号一致的可逆译码。

此外，若按照本发明，可以以几兆倍的高速来执行上述处理。此外，可以不实际进行编码就能够对代码量进行推测，结果，可以快速进行减小代码量的预测模式的选择。

附图说明

图1是用Ω和Ψ来分别表示R、X的存在范围的图。

图2是Ψ区域的放大图。

图3是表示分段可逆视频编码装置的构成例的图。

图4是表示分段可逆视频译码装置的构成例的图。

图5是表示当将通用可变长度编码用于index编码时的分段可逆视频译码装置的构成例的图。

图6是表示实施例1的处理流程的图。

图7是表示实施例2的处理流程的图。

具体实施方式

下面，参照附图详细说明本发明的实施形态和实施例。但是，本发明不限于以下说明的实施形态和实施例，例如，将它们适当组合的形态也属于本发明的范围。

作为说明本发明的前提，首先说明H.264方式的正交变换。

[H.264方式的正交变换]

在H.264标准中，在预测帧内或帧间的像素值之后，对每一个纵横各4个像素的小块进行残差的正交变换和系数的量化。

将原始信号的小块用4×4的矩阵U来表示，同样用4×4的矩阵Y来表示在帧内和帧间预测该块的信号。而且，设预测残差信号(4×4矩阵R)为

R＝U-Y                                   (1)

它们中的所有的元素都是整数。这里，将残差信号的各元素记为

[数式1]

$>>R>=>\begin{array}{}>>a>>b>>c>>d>\; >>e>>f>>g>>h>\; >>i>>j>>k>>l>\; >>m>>n>>o>>p>\; >\; >.>.>.>>(>2>)>>>s>\end{array}$

对其进行下面的正交变换。

X＝TRT^t                                  (3)

这里，

[数式2]是

$>>T>=>\begin{array}{}>>1>>1>>1>>1>\; >>2>>1>>->1>>->2>\; >>1>>->1>>->1>>1>\; >>1>>->2>>2>>->1>\; >\; >.>.>.>>(>4>)>>>s>\end{array}$

此外，T^t表示矩阵T的转置矩阵。

进而，设X的各元素为

[数式3]

$>>X>=>\begin{array}{}>>A>>B>>C>>D>\; >>E>>F>>G>>H>\; >>I>>J>>K>>L>\; >>M>>N>>O>>P>\; >\; >.>.>.>>(>5>)>>>s>\end{array}$

这里，应注意，T虽然是正交变换，但不是正规的正交变换。正规的正交变换的矩阵始终是1，而T的矩阵(detT)是40，故任何一个16维区域的体积经T映射后变成40倍。式(3)因利用T对R的4行和4列进行变换，故变换后系数X与变换前(残差信号R)相比为延伸了

40⁴⁺⁴＝6,553,600,000,000倍                (6)

被映射到极疏的空间内。H.264中的正交变换系数虽然变成整数，但系数空间的格子点作为残差信号几乎是不合适的(即，即使利用后面的式(8)进行逆变换也得不到整数值)。假如将系数空间的所有的格子点作为对象，对和原始信号对应的格子点进行编码，则每一个像素需要多出用2为底上述数的对数除以像素数(4×4＝16)

log₂(40⁴⁺⁴)/16＝2.66[bit]                  (7)的位。若考虑作为对象的信号是(每1个颜色分量)8位，不得不说增加2.66位明显地阻碍了其实用性。

在H.264方式中，如前所述，通过对放大后的X的各元素进行粗略的量化(使用较宽的幅度)来对该放大部分进行补偿。

若不进行量化，则通过逆变换

R＝T^-1(T^t)^-1                                (8)

残差信号完全复原，虽然利用

U＝R+Y                                 (9)

可以再现原像素值的4×4的矩阵U，但是，对于实际的H.264编码，若在译码侧对量化后系数进行逆量化，则一般地，虽然可以复原成接近原来的值，但不是完全相同的值。这样，X在传送后变成不同的值X’(≠X)，利用式(8)进行逆变换，变成

R≠R′＝T^-1X′(T^t)^-1

虽然在译码侧Y可以和在编码侧相同，但因R不能再现，故也不能再现原像素值U＝R+Y。

因此，为了完全再现U，有必要另外传送对X的量化时损失的信息进行补偿的附加信息。

[实施形态1]

本实施形态是和本发明的第1形态相对应的形态。

实施形态1的分段可逆视频编码方法像下述那样，对该量化后损失的信息有效地进行编码。

例如，式(5)中的系数A的值因经过量化并被传送，译码侧不能准确地知道量化前的A值。这里，编码侧的量化方法已知，知道A的取值范围。即，若以H.264软件JM(参考文献：http：//bs.hhi.de/～suehring/tml/，“JM Reference Software version 8.4”，jul 2004)的量化方法为例，可以像

|level_A|＝(|A|*qc_A+qpconst)＞＞qbits     (10)

那样求出量化后的值level_A。这里，“＞＞”是按位右移运算符。再有，level_A的正负与A一致。这里，qc_A与A的位置、量化参数对应并由JM所确定的整数，qbits与量化参数对应、并由JM确定的整数。

因为在译码侧可以知道量化参数、编码方式和量化方法，所以，可以具有和编码侧公用的level_A、qpconst、qbits。首先，根据level_A的值求出

x＝|level_A|＜＜qbits

y＝x+(1＜qbits)-1

mmin(x-qpconst+qc_A-1)/qc_A

mmax＝(y-qpconst)/qc_A

这里，“＜＜”是按位左移运算符，“/”是舍弃小数点后面的整数除法运算。可以像下述那样求出上下限A_min和A_max。

[数式4]

这样，可以得到量化前系数可取的上下限值

下限值A_min，B_min，C_min，...，P_min              (13)

上限值A_max，B_max，C_max，...，P_max              (14)

这些数值的范围相当于本发明的第1形态的‘变换系数的存在空间’。

通过以该上下限为基础执行下述算法1那样的16次循环(相当于本发明的第1形态的‘列举步骤’)，从而可以将正交变换后的空间内的妥当的格子点无遗漏地全部列举出来。这里，以下的处理相当于本发明的第1形态的‘妥当性判断’。

*‘R的全部元素是整数’

*‘U的全部元素都在8位整数范围(0～255)内’

上述妥当性判断结果，列举的格子点的总数为cases，与残差信号的正交变换系数一致的格子点的‘序号’作为index给出。

[算法1]

1.index←O

2.cases←O

3.for A←A_min to A_max

4.for B←B_min to B_max

5.for C←C_min to C_max

6.for D←D_min to D_max

7.for E←E_min to E_max

8.for F←F_min to F_max

9.for G←G_min to G_max

10.for H←H_min to H_max

11.for I←I_min to I_max

12.for J←J_min to J_max

13.for K←K_min to K_max

14.for L←L_min to L_max

15.for M←M_min to M_max

16.for N←N_min to N_max

17.for O←O_min to O_max

18.for P←P_min to P_max

19.begin

20.R←T^-1X(T^t)^-1(*式(8)*)

21.if R的全部元素是整数

22.then(*A～P作为整数信号的正交变换的结果是妥当的*)

23.U←R+Y(*式(9)*)

24.if U的全部元素是在8位整数的范围内[0～255]

25.then(*A～P作为整数信号的正交变换的结果是妥当的*)

26.if X和原变换系数一致

27.then index←cases

28.endif

29.cases←cases+1

30.endif

31.endif

32.end

33.使用与cases对应的信息量对index进行编码

[实施形态2]：利用变换系数间的整数值关系实现高速化

本实施形态与本发明的第2形态相对应。

在实施形态1中，因在1个间隔中分别执行16次循环，故总循环数非常多。但是，在实施形态2中，通过使用正交变换系数间存在的整数关系，在编码效率相同的条件下，可以大幅度减少循环次数。

首先，利用从顶行到底行按顺序排列的16维的行矢量↑x，像

↑x＝[a，b，c，d，e，f，g，h，i，j，k，l，m，n，o，p]

                                                    (15)

那样，来表现4×4矩阵R。

若使用该16维矢量改写式(3)，则可以写成

A＝↑t_A↑x^t

B＝↑t_B↑x^t

···

P＝↑t_P↑x^t

这里是：

↑t_A＝[1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1]

↑t_B＝[2，1，-1，-2，2，1，-1，-2，2，1，-1，-2，2，1，-1，-2]

↑t_C＝[1，-1，-1，1，1，-1，-1，1，1，-1，-1，1，1，-1，-1，1]

↑t_D＝[1，-2，2，-1，1，-2，2，-1，1，-2，2，-1，1，-2，2，-1]

↑t_E＝[2，2，2，2，1，1，1，1，-1，-1，-1，-1，-2，-2，-2，-2]

↑t_F＝[4，2，-2，-4，2，1，-1，-2，-2，-1，1，2，-4，-2，2，4]

↑t_G＝[2，-2，-2，2，1，-1，-1，1，-1，1，1，-1，-2，2，2，-2]

↑t_H＝[2，-4，4，-2，1，-2，2，-1，-1，2，-2，1，-2，4，-4，2]

↑t_I＝[1，1，1，1，-1，-1，-1，-1，-1，-1，-1，-1，1，1，1，1]

↑t_J＝[2，1，-1，-2，-2，-1，1，2，-2，-1，1，2，2，1，-1，-2]

↑t_K＝[1，-1，-1，1，-1，1，1，-1，-1，1，1，-1，1，-1，-1，1]

↑t_L＝[1，-2，2，-1，-1，2，-2，1，-1，2，-2，1，1，-2，2，-1]

↑t_M＝[1，1，1，1，-2，-2，-2，-2，2，2，2，2，-1，-1，-1，-1]

↑t_N＝[2，1，-1，-2，-4，-2，2，4，4，2，-2，-4，-2，-1，1，2]

↑t_O＝[1，-1，-1，1，-2，2，2，-2，2，-2，-2，2，-1，1，1，-1]

↑t_P＝[1，-2，2，-1，-2，4，-4，2，2，-4，4，-2，-1，2，-2，1]

这里，若计算↑t_A+↑t_C，则变成

↑t_A+↑t_C＝[2，0，0，2，2，0，0，2，2，0，0，2，2，0，0，2]

         ＝2[1，0，0，1，1，0，0，1，1，0，0，1，1，0，0，1]

因此，因为是，

A+C＝(↑t_A+↑t_C)↑x^t

＝2[1，0，0，1，1，0，0，1，1，0，0，1，1，0，0，1]↑x^t

所以，对于任意的整数元素矢量↑x，A+C始终是偶数。

即，当知道A的值时，因知道C的下位第1位和A的该位相同，所以，C的存在范围为

C_min+((C_min+A)&1)≤C≤C_max-((C_min+A)&1)

                                   (16)

在该区域内，C按间隔2稀疏地存在于该区域中。这里，‘&’是按位与运算符。具有相同的位置关系。

E和G

I和K

M和O

也一样。

同样，对于纵方向，因A+I也是偶数，故当A的值已知时，可知I以间隔2存在的范围。具有相同的位置关系。

B和J

C和K

D和L

也一样。

其次，对于任意的整数元素矢量↑x，B+(C＞＞1)+(A＞＞1)始终是偶数。这一点可以通过对使↑x的各元素按0，1，2，3变化的所有的情况进行确认来加以证明。即，当A和C的值已知，因知道B的下位的第1位和(C＞＞1)+(A＞＞1)的该位相同，所以，和上述一样，可知B的存在范围，在那里，B按间隔2存在。具有相同的位置关系，且纵向的位置关系相同。

Fと(E＞＞1)+(G＞＞1)

Jと(I＞＞1)+(K＞＞1)

Nと(M＞＞1)+(O＞＞1)

Eと(A＞＞1)+(I＞＞1)

Fと(B＞＞1)+(I＞＞1)

Gと(C＞＞1)+(K＞＞1)

Hと(D＞＞1)+(L＞＞1)

也一样。

其次，因

2.5(↑t_A+↑t_C)+2↑t_B+↑t_D

＝[10，0，0，0，10，0，0，0，10，0，0，0，10，0，0，0]

＝10[1，0，0，0，1，0，0，0，1，0，0，0，1，0，0，0]故对于任意整数元素矢量↑x，2B+D+2.5(A+C)始终是10的倍数。

即，当A、B、C的值已知时，因D的以10作为除数的余数(Dmod 10)和2.5(A+C)+2B的该值的和是0或10，可知D的存在范围，在其中，以间隔10存在。

相同的位置关系或纵向相同的位置关系，在例如M和A、E、I之间也具有同样的关系。

这里使用的以某整数y作为除数的余数运算符mod y对于非负整数x≥0，和C语言等的余数运算符‘％’相同，是

x mod y ＝x％y

再有，％运算符对于负整数x＜0，像

x％y＝-((-x)％y)

那样变成奇函数，但是，这里使用的mod y结果不会变成负值。

x mod y＝(x％y)+y(x＜0时)

例如是

(-1)mod 10＝9

进而，变成

↑t_A+↑t_C+↑t_I+↑t_K＝[4，0，0，4，0，0，0，0，0，0，0，0，4，0，0，4]

                   ＝4[1，0，0，1，0，0，0，0，0，0，0，0，1，0，0，1]

因此，对于任意整数元素矢量↑x，A+C+I+K始终是4的倍数。

即当A、C、I的值已知时，因K的以4作为除数的余数和(A+C+I)的该值的和是0或4，故可知K的存在范围，在这里，以间隔4存在。

进而还具有以下关系：

↑t_B-↑t_J+↑t_E-↑t_G＝[0，4，4，0，4，4，0，-4，4，0，-4，-4，0，-4，-4，0]

＝4[0，1，1，0，1，1，0，-1，1，0，-1，-1，0，-1，-1，0]

2.5(↑t_A+↑t_C+↑t_I+↑t_K)+2(↑t_E+↑t_G)+↑t_M+↑t_O

＝[20，0，0，20，0，0，0，0，0，0，0，0，0，0，0，0]

＝20[1，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0]

2.5(↑t_A+↑t_C+↑t_I+↑t_K)+2(↑t_B+↑t_J)+↑t_D+↑t_L

＝[20，0，0，0，0，0，0，0，0，0，0，0，20，0，0，0]

＝20[1，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0]

6.25(↑t_A+↑t_C+↑t_I+↑t_K)

+5(↑t_B+↑t_E+↑t_G+↑t_J)

+2.5(↑t_D+↑t_L+↑t_M+↑t_O)

+4↑t_F+2(↑t_H+↑t_N)+↑t_P

＝[100，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0]

＝100[1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0]

即，像

1)使A的范围在1间隔内循环

2)使C的范围在2间隔内循环(利用A)

3)使B的范围在2间隔内循环(利用A、C)

4)使D的范围在10间隔内循环(利用A、B、C)

5)使I的范围在2间隔内循环(利用A)

6)使E的范围在2间隔内循环(利用A、I)

7)使M的范围在10间隔内循环(利用A、I、E)

8)使K的范围在4间隔内循环(利用A、C、I)

9)使G的范围在2间隔内循环(利用E)

10)使F的范围在2间隔内循环(利用E、G)

11)使H的范围在10间隔内循环(利用E、F、G)

12)使J的范围在4间隔内循环(利用B、E、G)

13)使L的范围在20间隔内循环(利用A、B、C、D、I、J、K)

14)使N的范围在10间隔内循环(利用B、F、J)

15)使O的范围在20间隔内循环(利用A、C、E、G、I、K、M)

16)使P的范围在100间隔内循环(利用A～O)

那样，若执行多重循环，则将各for循环与1间隔循环相比，可以将循环次数减至

1/(2*2*10*2*2*10*4*2*2*10*4*20*10*20*100)

＝1/409,600,000,000

具体的顺序像算法2那样。这里，例如如下所示，使用

f(x，y)＝(-x)mod y                         (17)

可以求出C’_min、B’_min和D’_min。

C′_min＝C_min+f(C_min+A，2)                  (18)

B′_min＝B_min+f(B_min+(A＞＞1)+(C＞＞1)，2)  (19)

D′_min＝D_min+f(D_min+2B+2.5(A+C)，10)       (20)

E’_min～P’_min也一样。

[算法2]

1.index←0

2.cases←0

3.for A←A_min to A_max(*只在这里是1间隔*)

4.for C←C′_min to C_max step 2

5.for B←B′_min to B_max step 2

6.for D←D′_min to D_max step 10

7.for I←I′_min to I_max step 2

8.for E←E′_min to E_max step 2

9.for M←M′_min to M_max step 10

10.for K←K′_min to K_max step 4

11.for G←G′_min to G_max step 2

12.for F←F′_min to F_max step 2

13.for H←H′_min to H_max step 10

14.for J←J′_min to J_max step 4

15.for L←L′_min to L_max step 20

16.for N←N′_min to N_max step 10

17.for O←O′_min to O_max step 20

18.for P←P′_min to P_max step 100

19.begin

20.R←T^-1X(T^t)^-1(*式(8)*)

21.if R的全部元素是整数

22.then(*A～P作为整数信号的正交变换的结果是妥当的*)

23.U←R+Y(*式(9)*)

24.if U的全部元素是在8位整数的范围内[0～255]

25.then(*A～P作为残差信号的正交变换的结果是妥当的*)

26.if X和原变换系数一致

27.then index←cases

28.endif

29.cases←cases+1

30.endif

31.endif

32.end

33.使用与cases对应的信息量对index进行编码

[实施形态3]：减少多重循环

本实施形态与本发明的第3形态对应。

上述实施形态1和实施形态2的算法都使用16次循环，但在实施形态3中，为了进一步实现高速化，而减少循环的次数。这里，通过独立地传送A～P的16个系数中

A B  C  D

E · · ·

I · K  ·

M · · ·

的8个系数来除去这些循环。

首先，考虑系数A的传送。例如，作为‘附加信息’，若传送

Z_A＝A-A_min

则通过在译码侧设为

A＝Z_A+A_min

可以复原A。

再有，因这时能取得A的情形的数是

A_max-A_min+1

故对Z_A进行编码所需要的信息量变成

log₂(A_max-A_min+1)[bit]                (21)

因为这是和译码侧共用的，所以可以对Z_A进行译码。

虽然对于B～P可以像该A那样传送，但因残差信号在正交变换后的空间内分布非常稀疏，故代码量大大浪费。因此，例如，对于B，当A、C已知时，与B有关的循环能够以2间隔完成，故若传送

Z_B＝(B-B’_min)/2

则在译码侧可以通过

B＝2Z_B+B’_min

复原B。对Z_B进行编码所需要的信息量变成

log₂((B_max-B’_min)/2+1)[bit]。

对于C～K也一样。因此，通过执行下述步骤

1)利用Z_A对A的值进行编码

2)利用将C的范围缩小到约1/2的Z_c进行编码(利用A)

3)利用将B的范围缩小到约1/2的Z_B进行编码(利用A、C)

4)利用将D的范围缩小到约1/10的Z_D进行编码(利用A、B、C)

5)利用将I的范围缩小到约1/2的Z_I进行编码(利用A)

6)利用将E的范围缩小到约1/2的Z_E进行编码(利用A、I)

7)利用将M的范围缩小到1/10的Z_M进行编码(利用A、E、I)

8)利用将K的范围缩小到约1/4的Z_K进行编码(利用A、C、I)

可以有效地传送X中的

A B  C  D

E · · ·

I · K ·

M · ··

8个系数。像这样范围缩小后的Z_x相当于本发明的第3形态的‘除去不能取得该系数的值的信息’。

对于剩下的8个系数

·· · ·

· F  G  H

· J  · L

· N  O  P

和实施形态1一样，归纳起来用1个数index来表现并传送。

若将它们归纳在一起，则变成算法3所示的步骤。

[算法3]

1.按A、C、B、D、I、E、M、K的顺序编码

2.index←O

3.cases←O

4.for G←G′_min to G_max step 2

5.for F←F′_min to F_max step 2

6.for H←H′_min to H_max step 10

7.for J←J′_min to J_max step 4

8.for L←L′_min to L_max step 20

9.for N←N′_min to N_max step 10

10.for O←O′_min to O_max step 20

11.for P←P′_min to P_max step 100

12.begin

13.R←T^-1X(T^t)^-1(*式(8)*)

14.if R的全部元素是整数

15.then(*A～P作为整数信号的正交变换的结果是妥当的*)

16 U←R+Y(*式(9)*)

17.if  U的全部元素是在8位整数的范围内[0～255]

18.then(*A～P作为残差信号的正交变换的结果是妥当的*)

19.if X和原变换系数一致

20.then index←cases

21.endif

22.cases←cases+1

23.endif

24.endif

25.end

26.使用与cases对应的信息量对index进行编码

如上所述，16次循环减少到8次，处理速度更高。

再有，记述index所需要的信息量为

log₂ cases[bit]                    (22)

该信息是译码侧在没有附加信息的情况下可以具有的，而且，是index译码所必需的信息。

[实施形态4]对应的译码

本实施形态是与本发明的第7形态对应的形态。

在这里，说明与上述实施形态3的编码对应的关于译码的实施形态。在译码侧，通过执行和编码同样的循环，当在最里面的循环的妥当性判断结果是index+1次为真时，A～K和G～P的值变成与原残差信号对应的正交变换系数。

在index编码时，当与具有多少信息量对应进行编码时，在index的译码中，首先，必须知道具有多少信息量。因此，有必要预先得到cases。为此，有必要执行和编码一样的循环。

例如，虽然需要额外的存储器，但是，为了避免再次执行多重循环，通过像算法4那样只执行一次多重循环，可以按顺序取得cases、index和原始信号。这里，Ubuf[]是将4×4矩阵作为元素的排列，假定是动态确保或者是预先确保有足够的量。

[算法4]

1.按A、C、B、D、I、E、M、K的顺序译码

2.cases←O

3.for G←G′_min to G_max step 2

4.fpr F←F′_min to F_max step 2

5.for H←H′_min to H_max step 10

6.for J←J′_min to J_max step 4

7.for L←L′_min to L_max step 20

8.for N←N′_min to N_max step 10

9.for O←O′_min to O_max step 20

10.for P←P′_min to P_max step 100

11.begin

12.R←T^-1X(T^t)^-1(*式(8)*)

13.if R的全部元素是整数

14.then(*A～P作为整数信号的正交变换的结果是妥当的*)

15.U←R+Y(*式(9)*)

16.if U的全部元素是在8位整数的范围内[0～255]

17.then(*A～P作为整数信号的正交变换的结果是妥当的*)

18.Ubuf[cases]←U

19.cases←cases+1

20.endif

21.endif

22.end

23.使用与cases对应的信息量对index进行译码

24.U←Ubuf[index](*原始信号值*)

[实施形态5]代码量的快速推测

本实施形态是与本发明的第6形态相对应的形态。

在H.264方式中，可以选择各种各样的预测模式，对于帧内预测，可以选择多个模式或种类，对于帧间预测可以选择多个块的尺寸等。预测残差信号R也因预测模式而变化，所以，当在代码量对失真的意义上选择最佳预测模式时，有必要合适地估计每一个模式的代码量。

可逆编码时，因失真始终是零，故只需注意使代码量(H.264标准的代码量和附加信息代码量的和)最小即可。

若执行算法1、算法2和算法3所示那样的多重循环，则当然可以估计正确对的附加信息代码量，但是，如果有更高速的代码量推测法，则适于将多个模式进行比较。

实施形态5的目的在于在不执行多重循环的情况下估计附加信息的代码量。

首先，说明像实施形态1、实施形态2那样事前没有传送特定的变换系数的情况。事前求出量化前的系数可取的上下限值(式(13)，式(14))。据此，可以像下面那样求出本发明第6形态的‘变换系数的存在空间’的体积V。

[数式5]

$>>V>=>>\Pi >>x>\in >A>,>·>·>·>P>\; >>(>>x>max>>->>x>min>>+>1>)>>.>.>.>>(>23>)>>>s>$

考虑该V与存在空间中的格子点的个数近似。不是其中所有的都与原残差信号对应，因空间如式(6)所示那样被放大，故V除以该倍数得到的V₀

V₀＝V/40⁴⁺⁴                               (24)

可以与格子点的总数近似。因此，每一个像素的附加信息的代码量I₀变成

l₀＝log₂V₀/16

＝log₂(V/40⁴⁺⁴)/16

＝log₂V/16-2.66[bit]                      (25)

此外，当像实施形态3那样事前传送特定的变换系数时，这些信息量I1和式(21)一样是

[数式6]

$>>>I>1>>=>>\Sigma >>x>\in >A>,>·>·>,>K>\; >>(>>(>>x>max>>-sup>>x>min>\prime sup>>)>>/>>n>x>>+>1>)>>.>.>.>>(>26>)>>>s>$

这里，x是

A B  C  D

E · ··

I · K ·

M · ··的系数。

再有，n_x是使所叙述的空间缩小的量，对于A，...，M分别是12210

2 · ··

2 · 4 ·

10···

A’_min＝A_min，C’_min～M’_min可以像式(18)等那样求出。

此外，剩下的8维的‘变换系数的存在空间’的体积V1如下：

[数式7]

$>>>V>1>>=>>\Pi >>x>\in >F>,>·>·>·>p>\; >>(>>x>max>>->>x>min>>+>1>)>>.>.>.>>(>27>)>>>s>$

这里，和上面的情况一样，与原残差信号对应的格子点稀疏地存在。该空间的放大率应该是用全部乘以n_x(x∈A，...，M)的项除以式(6)所得到的数

[数式8]

$>>>n>0>>=>>40>>4>+>4>>>/>>\Pi >>x>\in >A>,>·>·>·>,>M>\; >>n>x>>=>>40>8>>/>>(>1>*>2>*>2>*>10>*>2>*>2>*>4>*>10>)>>>s>$

$>>=>1,024,000,000>.>.>.>>(>28>)>>>s>$

因此，每一个像素的‘格子点总数’的信息量I₁变成

l₂＝log₂(V₁/n₀)/16

＝log₂V₁/16-1.87[bit]                (29)

结果，每一个像素的附加信息量是两者之和

l₁+l₂[bit]                             (30)

利用像式(25)、式(30)那样估算的值，可以不执行使用多重循环的编码来进行代码量的推测。使用它来选择代码量最小的模式，并只对所选择的模式进行实际的编码，由此，可以实现准最佳的可逆编码。

[实施形态6]：妥当性判断的高速化

本实施形态是与本发明的第4形态相对应的形态。

因T-1是

[数式9]

$>>>T>>->1>>>=>\begin{array}{}>>0.25>>0.2>>0.25>>0.1>\; >>0.25>>0.1>>->0.25>>->0.2>\; >>0.25>>->0>.>1>>->0.25>>0>.>2>\; >>0.25>>->0.2>>0.25>>->0.1>\; >\; >.>.>.>>(>31>)>>>s>\end{array}$

故当直接计算式(8)时，必需要进行浮点运算。但是，若将其放大20倍，则变成

[数式10]

$>>>T>0>>=>20>>T>>->1>>>=>\begin{array}{}>>5>>4>>5>>2>\; >>5>>2>>->5>>->4>\; >>5>>->2>>->5>>4>\; >>5>>->4>>5>>->2>\; >\; >.>.>.>>(>32>)>>>s>\end{array}$

所以，通过用T₀代替T^-1，可以像下面那样只通过整数运算就能够得到正确的R的400(＝20×20)倍的值(记作R₄₀₀)。

R₄₀₀＝400R＝T₀XT^t₀                 (33)

这里，当设

[数式11]

$>>\begin{array}{}>>s>\; >>t>\; >>u>\; >>v>\; >\; >=>To>\begin{array}{}>>a>\; >>b>\; >>c>\; >>d>\; >\; >.>.>.>>(>34>)>>>s>\end{array}\end{array}$

时，式(33)可以纵横8次分解成式(34)，但是该计算可以具体地像算法5那样求出。

[算法5]

1.x₀←5(a+c)

2.x₁←5(a-c)

3.x₂←4b+2c

4.x₃←2b-4c

5.s←x₀+x₂

6.t←x₁+x₃

7.u←x₁-x₃

8.v←x₀-x₂

这里，5x可以像(x＜＜2)+x那样通过1次移位、1次相加求得，4b+2c等也可以作为(b＜＜2)+(c＜＜1)，通过2次移位、1次相加求得，故在式(33)的计算中，乘法一概不需要。

这里，作为前述的‘妥当性判断’之一的‘R的全部元素是整数’和‘R₄₀₀的全部元素是400的倍数’等价。当执行它时，为了确认用400除得的余数是0，除法运算是必需的。但是，因在完成1个循环的时刻除去了作为25的倍数的冗余性，故只要确认是16的倍数即可。这和‘R₄₀₀的全部元素的低位4位全是0’等价。这和‘各元素和15(二进制1111)的按位与运算的结果是0’等价，可以不用除法来进行判断。

这里，是另一个‘妥当性判断’，有必要对‘U的全部元素都在8位整数的范围[0～255]内’进行修正。若将式(9)的两边乘以400，则变成

U₄₀₀＝400U＝R₄₀₀+Y₄₀₀                  (35)

这里，Y₄₀₀是将预测信号Y放大400倍的值，预先准备Y₄₀₀(若使用256元素的查寻表则不需要400倍的乘法运算)，若求出与R₄₀₀的和，则可以得到原始信号的400倍的信号。这里，因255×400＝102,000，故只要确认‘U₄₀₀的全部元素都在[0～102000]之内’即可。

归纳该步骤，便变成算法6。

[算法6]

1.index←0

2.cases←0

3.for A←A_min to A_max(*仅这里是1间隔*)

4.for C←C′_min to C_max step 2

5.for B←B′_min to B_max step 2

6.for D←D′_min to D_max step 10

7.for I←I′_min to I_max step 2

8.for E←E′_min to E_max step 2

9.for M←M′_min to M_max step 10

10.for K←K′_min to K_max step 4

11.for G←G′_min to G_max step 2

12.for F←F′_min to F_max step 2

13.for H←H′_min to H_max step 10

14.for J←J′_min to J_max step 4

15.for L←L′_min to L_max step 20

16.for N←N′_min to N_max step 10

17.for O←O′_min to O_max step 20

18.for P←P′_min to P_max step 100

19.begin

20.R400←T₀XT^t₀(*式(33)*)

21.if R₄₀₀的全部元素的低位4位是0

22.then(*A～P作为整数信号的正交变换的结果是妥当的*)

23.U₄₀₀←R₄₀₀+Y₄₀₀(*式(35)*)

24.if U₄₀₀的全部元素是在[0～102000]之内

25.then(*A～P作为整数信号的正交变换的结果是妥当的*)

26.if X和原变换系数一致

27.then index←cases

28.endif

29.cases←cases+1

30.endif

31.endif

32.end

33.使用与eases对应的信息量对index进行编码

[实施形态7]：利用了凸形状的处理高速化

本实施形态与本发明的第5形态对应。

考虑残差信号

[数式12]

$>>R>=>\begin{array}{}>>a>>b>>c>>d>\; >>e>>f>>g>>h>\; >>i>>j>>k>>l>\; >>m>>n>>o>>p>\; >\; >>s>\end{array}$

的存在空间。若设左上位置的预测像素信号为Y_a，则该位置的元素a满足

0≤a+Y_a≤255                            (36)

-Y_a≤a≤255-Y_a                          (37)的存在范围。b～p也同样决定上限和下限。若考虑16维空间，则R的存在范围Ω变成凸多面体(超长方体)的形状。

即使仍然是利用式(3)将R的存在范围变换后的16维空间，经过旋转、放大后仍然是凸多面体。虽然变换系数X存在于该变换目标的空间内，但各元素的上下限像式(13)、(14)那样求出，所以，X的存在范围Ψ仍然是凸多面体(超长方体)。因此，Ω和Ψ的相交Ω∩Ψ也仍然是凸多面体。为了简化这些关系，若用2维来图示，则如图1所示。

将图1的Ψ区域放大后变成图2。在列举格子点的步骤中，当执行多重循环时，如该图所示，当在A＝A₀的情况下改变B时，妥当性判断的第2轮(U的全部元素都在8位整数的范围[0～255]内)在第5个格子点(灰色)上变成‘真’→‘伪’。因存在范围Ω∩Ψ是凸，故确定在第6个之后是‘伪’，所以，中止B的循环，作为下一次A＝A₁，重新开始B的循环。这里，在第6个格子点(灰色)上变成‘真’→‘伪’，所以，中止循环。这样，可以中止对图中由虚线包围的部分的判断。

若将它们归纳起来，则变成算法7。若示出对全部系数进行中止妥当性判断的步骤，因缩进太深，故为了简单起见，这里只示出对多重循环最内层的3个变量(N，O，P)进行中止妥当性判断的步骤，但是，对于反映其一般特性已经足够了。

[算法7]

1.index←O

2.cases←O

3.for A←A_mintoA_max

4.for B←B_mintoB_max

5.for C←C_mintoC_max

6.for D←D_mintoD_max

7.for E←E_mintoE_max

8.for F←F_mintoF_max

9.for G←G_mintoG_max

10.for H←H_mintoH_max

11.for I←I_mintoI_max

12.for J←J_mintoJ_max

13.for K←K_mintoK_max

14.for L←L_mintoL_max

15.for M←M_mintoM_max

16.begin

17.CheckN←伪

18.for N←N_mintoN_max

19.begin

20.CheckO←伪

21.for O←O_mintoO_max

22.begin

23.CheckP←伪

24.for P←P_mintoP_max

25.begin

26.R←T^-1X(T^t)^-1(*式(8)*)

27.if R的全部元素是整数

28.then(*A～P作为整数信号的正交变换的结果是妥当的*)

29.U←R+Y(*式(9)*)

30.if  U的全部元素是在8位的整数范围[0～255]之内

31.then(*A～P作为整数信号的正交变换的结果是妥当的*)

32.if X和原变换系数一致

33.then index←cases

34 endif

35.CheckN←真

36.CheckO←真

37.CheckP←真

38.cases←cases+1

39.else if CheckP＝真

40.then goto 21(*变成真→伪*)

41.endif

42.endif

43.end

44.if CheckP＝伪and CheckO＝真

45.then goto 18(*变成真→伪*)

46.endif

47.end

48.if CheckP＝伪and CheckO＝伪and CheckN＝真

49.then goto 15(*变成真→伪*)

50.endif

51.end

52.end

53.使用与cases对应的信息量对index进行编码

[实施形态8]：编码装置的构成例

本实施形态与本发明的第8形态对应。

下面，说明实现上述本发明的装置构成。图3是表示本发明的分段可逆视频编码装置的构成例的图。分段可逆视频编码装置1除了根据H.264标准编码方式对每一个块算出原始图像信号和通过帧内编码的空间预测或帧间编码的时间预测所产生的预测图像信号的残差信号Rorig的部分(在图示3中被省略)之外，还包括：初始化cases，index的初始化部11；对残差信号Rorig进行正交变换的正交变换部12、量化正交变换部12的输出的量化部13；求出上下限信息A_min A_max，...，P_min，P_max的存在空间决定部14；对逐次编码传送的系数进行编码处理的系数逐次编码部15；求出表示汇总系数的数index再进行编码的系数汇总编码部16；判定图像内的所有块是否已编码的结束判定部17。

系数汇总编码部16由列举在各系数的上下限内所有的系数组合的多重循环开始部161、对由已编码传送的系数和当前循环中的系数决定的4×4矩阵X进行逆正交变换的逆正交变换部162、求出矩阵和U＝R+Y的预测信号加法部163、更新处理index和cases的内部变量更新部164、判定是否检查了在各系数的上下限内所有的系数组合的多重循环结束判定部165和对index进行编码的序号编码部166构成。

图3所示的分段可逆视频编码装置1像以下那样动作。首先，在初始化部11中分别将‘格子点总数’cases、与残差信号的正交变换系数一致的格子点的‘序号’index初始化为0。

其次，在正交变换部12中对残差信号Rorig进行正交变换并得到Xorig。在量化部13中使用量化参数信息对其进行量化。在存在空间决定部14中根据该量化信息求出上下限信息A_min，A_max，…，P_min，P_max。

其次，在系数逐次编码部15中对逐次编码传送的系数进行编码处理。例如，在上述实施形态1中是0个，在实施形态3中是A、B、C、D、L、E、M、K共8个。

接着，在系数汇总编码部16中求出表示剩余的表示汇总系数的数index再进行编码。即，系数汇总编码部16中的多重循环开始部161列举剩余的系数(例如，实施形态1是A～P的16个，实施形态3是G、F、H、J、L、N、O、P共8个)在各自的上下限内可取的所有范围。这时，也可以像实施形态2那样，在列举时利用系数间的整数值关系跳过不能取得的系数。

在逆正交变换部162中，对由已编码传送的系数和当前循环中的系数A～P所决定的4×4矩阵X进行逆正交变换，并将其作为R。这里，若R中存在不是整数的值，则进入多重循环结束判定部165的处理。

其次，在预测信号加法部163中求出矩阵和U＝R+Y。这里，若U的元素存在不在[0～255]的范围内的值，则进入多重循环结束判定部165的处理。

其次，在内部变量更新部164中，当X和Xorig一致时，进行将cases代入index的处理。此外，cases加1。

在多重循环结束判定部165中，判定是否检查了在上下限内所有系数的组合，若还没有则返回到多重循环开始部161的处理。若已检查完毕，则在序号编码部166中使用与cases对应的信息量对index进行编码。

接着，在结束判定部17中判定是否对图像内的所有块进行了编码，若未完成则转移到下一个块重新开始初始化部11的处理。若完成，则结束编码。

[index的编码使用通用的可变长度编码时]

在本发明中，例如，通过使用通用可变长度编码(参考文献：Y.Itoh，N-M Cheung”Universal Variable length code for DCTcoding”，IEEE Proc.Int.Conf.Image Processing，Vol.1，pp.940-943，2000)等，可以不使用cases而对index进行编码。这时，在内部变量更新部164中，若X和X_orig一致，则对此时的cases的值进行通用可变长度编码，并立即结束系数汇总编码部16的处理。

[实施形态9]：译码装置的构成例

本实施形态与与本发明的第9形态对应。

图4是表示本发明的分段可逆视频译码装置的构成例的图。分段可逆视频译码装置2由在对量化参数和量化系数进行译码的同时生成预测信号Y的初始化译码部21、求出上下限值信息A_min，A_max，...，P_min，P_max的存在空间决定部22、对逐次编码传送的系数进行译码的系数逐次译码部23、对表示汇总系数的数index进行译码的系数汇总译码部24、存储U的值的作为排列存储的Ubuf[]25、和判定图像内的所有决是否已译码的结束判定部26构成。

系数汇总译码部24由列举在各系数的上下限内所有系数的组合的多重循环开始部241、对由已译码的系数和当前循环中的系数决定的4×4矩阵X进行逆正交变换的逆正交变换部242、求出矩阵和U＝R+Y的预测信号加法部243、在将U存储在Ubuf[]25的cases地址中的同时更新cases的内部变量更新部244、判定是否检查了在上下限内所有系数的组合的多重循环结束判定部245、对index进行译码的序号译码部246和将Ubuf[]25的第index个值作为原始图像信号输出的原始信号输出部247构成。

图4所示的分段可逆视频译码装置2像以下那样动作。首先，在初始化译码部21中将‘格子点总数’cases初始化为0，进行对量化参数和量化系数的译码并生成预测信号Y。

在存在空间决定部22中根据量化参数和量化系数求出上下限值信息A_min，A_max，...，P_min，P_max。

其次，在系数逐次编码部23中对逐次编码传送的系数进行译码。例如，在上述实施形态1中不进行译码，在实施形态3中按顺序对A、C、B、D、I、E、M、K共8个进行译码。

接着，在系数汇总编码部24中对表示剩余的汇总系数的数index进行译码和可逆复原。即，系数汇总编码部24中的多重循环开始部241列举剩余的系数(例如，实施形态1的情形，是A～P共16个，实施形态3的情形是G、F、H、J、L、N、O、P共8个)在各自的上下限内可取的所有范围。

这时，也可以像实施形态2那样，在列举时利用系数间的整数值关系跳过不能取得的系数的组合。但是，跳过不能取得的系数的组合而列举的顺序是和对应的编码装置完全相同的顺序。

在逆正交变换部242中，对由已译码的系数和当前循环中的系数A～P决定的4×4矩阵X进行逆正交变换，并将其作为R。这里，若R中存在不是整数的值，则进入多重循环结束判定部245的处理。

其次，在预测信号加法部243中求出矩阵和U＝R+Y。这里，若U的元素中存在不在[0～255]的范围内的值，则进入到多重循环结束判定部245的处理。

其次，在内部变量更新部244中，将U存储在预先确保的Ubuf[]25的cases地址中，并使cases加1。

在多重循环结束判定部245中，判定是否检查了在各系数的上下限内所有的系数组合，若还没有则返回到多重循环开始部241的处理。若已检查完毕，则在序号译码部246中使用与cases相对应的信息量对index进行译码。

接着，在原始信号输出部247中，取出Ubuf[]25的第index号的值，并作为原始图像信号输出。

接着，在结束判定部26中判定是否对图像内的所有块进行了译码，若未完成则转移到下一个块重新开始初始化译码部21的处理。如完成，则结束译码。

[index的编码使用通用的可变长度编码时的译码装置的构成例]

在本发明中，当index的编码使用通用的可变长度编码时，译码侧变成图5所示那样的功能块结构。图5所示的分段可逆视频译码装置3在通用可变长度译码部27中对index进行译码，并在多重循环结束判定部285中判定执行了多重循环的次数是不是第index次，若不是则判定为立即结束，并将此时的U值作为原始信号输出。因此，不需要像图4所示的Ubuf[]25那样的排列存储。其余部分的动作和图4所说明的例子相同。

实施例1

说明与实施形态3对应的实施例1。在该实施例1中，作为核心处理的概况如下：

输入：量化参数，预测信号Y和原残差信号Rorig

处理：对于和原始信号对应的正交变换系数，一部分变成压缩信息，剩下的作为无遗漏地列举所有的能变成原始信号的组合中的序号来表现。

输出：分别表现一部分系数的(A、C、B、D、I、E、M、K)的压缩信息(Z_A～Z_K)，用1个数值代表剩下的汇总系数(G、F、H、J、L、N、O、P)的代码(index)

参照图6所示的处理流程说明实施例1。首先，在步骤S101中输入量化参数，预测信号Y和原残差信号Rorig。其次，在步骤S102中将index和cases同时初始化为0。

其次，在步骤S103中，对Rorig进行正交变换并得到原变换系数Xorig，同时，求出对Xorig进行量化后的量化系数。在步骤S104中，根据前面得到的量化参数和量化系数的信息求出作为反推Xorig的矩阵之X的各元素(A～P)的上下限。在步骤S105中，在此基础上，按顺序对A、C、B、D、I、E、M、K进行压缩编码。

接着，进入G、F、H、J、L、N、O、P的8重循环(步骤S106～步骤S114)。在步骤S107中，利用式(8)对由当前的A～P的值构成的4×4矩阵X进行逆变换，得到R。

在步骤S108中，确认R的元素全部是否是整数，若是‘伪’则进入到S114，若是‘真’则进入到S109，并计算U＝R+Y。

其次，在步骤S110中，确认U的所有元素是否都在[0～255]的范围之内。若是‘伪’则进入S114，若是‘真’则进入S111，确认X是否和原变换系数Xorig相等。若是‘真’则在步骤S112中，将当前的cases值保存在变量index中。接着，在步骤S113中，使cases值加1并进入步骤S114。

在步骤S114中，确认8重循环是否都完成，若是‘伪’则返回到循环开始的步骤S106，若是‘真’则在步骤S115中使用已求出的与cases(格子点总数)对应的信息量(式(22))对index进行编码并结束程序。

这里，示出了预先对部分系数(A、C、B、D、I、E、M、K共8个系数)另外进行编码(步骤S105)的例子，但也可以省略这一步骤，若将从步骤S106到S114作为整个16个系数的多重循环，则变成框架结构和实施形态1或实施形态2完全对应的实施例。

实施例2

说明与实施形态4对应的实施例2。在该实施例2中，作为核心处理的概况如下：

输入：量化参数，预测信号Y和量化系数

处理：对于和原始信号对应的正交变换系数，一部分(A、C、B、D、I、E、M、K)从压缩信息进行译码，剩余的(G、F、H、J、L、N、O、P)作为无遗漏地列举所有的能变成原始信号的组合中的序号来译码。

输出：原图像信号

参照图7所示的处理流程说明实施例2。首先，在步骤S201中将cases初始化为0。其次，在步骤S202中进行量化参数、量化系数的译码并生成预测信号Y。这些是从H.264基本信息位流中得到的信息。

在步骤S203中，根据前面得到的信息求出矩阵X的各元素(A～P)的上下限。在步骤S204中，在此基础上，按顺序对A、C、B、D、I、E、M、K进行译码。

接着，进入G、F、H、J、L、N、O、P的8重循环(步骤S205～步骤S212)。在步骤S206中，利用式(8)对由当前的A～P的值构成的4×4矩阵X进行逆变换，得到R。

在步骤S207中，确认R的元素是否全是整数，若是‘伪’则进入S212，若是‘真’则进入S208，并计算U＝R+Y。

其次，在步骤S209中，确认U的所有元素是否都在[0～255]的范围之内，若是‘真’则在步骤S210中，将当前的U值保存在阵列Ubuf[]的cases地址中，进入到步骤S211使cases值加1，并进入S212，若是‘伪’则进入到步骤S212。

在步骤S212中，确认8重循环是否都完成，若是‘伪’则返回循环开始的步骤S205。若是‘真’，则在步骤S213中使用已求出的与cases(格子点总数)对应的信息量(式(22))对index进行译码，在步骤S214中输出Ubuf[index](相当于原始信号)并结束程序。

在以上实施例中，说明了使用cases对index进行编码的例子，但也可以使用通用可变长度编码(UVLC)或停止代码对index进行编码。当index编码使用通用可变长度编码或停止代码时，译码侧即使不知道cases也可以译码。这时，可以预想index用的代码量增加不到两成，由于不必计算cases的值，故可以中途中断多重循环，具有使编码和译码的时间减半的效果。此外，还具有译码侧不需要排列存储Ubuf[]的效果。

以上，参照附图说明了本发明的实施形态和实施例，但这些只不过是本发明的例子，很明显，本发明不限于这些实施形态和实施例。因此，在不脱离本发明的精神和范围的范围内，可以进行构成要素的增加、省略、置换及其他的变更。

例如，图3～图5所示的装置除了利用专用的硬件来实现的形态之外，也可以利用具有存储器和CPU(中央处理装置)等的计算机系统来构成，通过将用于实现这些装置的处理(例如，图6～图7所示的各步骤)程序安装在存储器中后再执行来实现该功能。此外，也可以将用来实现该功能的程序记录在计算机可读取的记录媒体中，使计算机系统读取记录在该记录媒体中的程序后再执行。

再有，这里所说的计算机系统包含OS或外设等硬件。此外，计算机可读取的记录媒体是指软盘、光磁盘、ROM、CD-ROM等可移动的媒体和内置在计算机内的硬盘等存储装置，还包括经由像经因特网等网络或电话线路等通信线路发送程序时的通信线路那样，动态地保持程序的程序载体(传送媒体乃至传送波)、和像此时的服务器或客户计算机系统内部的易失性存储器那样，在一定时间内保持程序的介质。此外，上述程序也可以是用来实现上述部分功能的程序，进而，也可以是通过与已记录在计算机系统中的程序组合来实现上述功能的、所谓差分文件(差分程序)。

此外，分段可逆视频编码装置和分段可逆视频译码装置例如可以像以下那样构成。

即，分段可逆视频编码装置的构成包括：生成以H.264标准为基准的位流的单元；在对图像信号的各块进行的编码中输入帧内编码的空间预测或帧间编码的时间预测的预测信号的单元；输入从原始信号减去预测信号后的残差信号的单元；求出根据H.264标准方式对残差信号进行正交变换得到的变换系数和将其量化后的量化系数的单元；指定由量化系数、量化参数和量化方法决定的变换系数的存在空间的单元；判断将该空间内的某格子点作为残差信号的正交变换的结果是否妥当的妥当性判断单元；列举在该空间内的格子点中上述判断是妥当的格子点的列举单元；按照列举的顺序从0开始对列举的格子点分配序号的单元；在列举的格子点中得到与残差信号的变换系数一致的格子点的序号的单元；对得到的序号进行编码的单元。

在上述分段可逆视频编码装置中，可以具有在列举格子点时通过使用变换系数间的整数值的关系对在空间内不能取得变换系数的点省略妥当性判断处理的单元。

在上述分段可逆视频编码装置中，可以具有：对特定的几个变换系数，传送除了利用该系数和已传送完成的系数(如果有的话)的整数值的关系而不能取得该系数的值之外的信息，从而代替传送该系数的单元；和列举使用像这样预先已传送的变换系数将维数缩小的存在空间内的格子点的单元。

在上述分段可逆视频编码装置中，可以具有只通过位运算和整数加减运算来等效地实现上述妥当性判断的单元。

在上述分段可逆视频编码装置中，可以具有：利用残差信号的存在范围和变换系数的存在范围相交形成为凸多面体的情况在途中中止上述妥当性判断的单元。

在上述分段可逆视频编码装置中，可以具有不用上述列举装置列举格子点而进行代码量的估计的单元。

与上述分段可逆视频编码装置对应的分段可逆视频译码装置的构成包括：执行H.264标准译码方式的单元；指定由量化参数、量化系数、编码时的量化方法和已复原的系数(如果有的话)决定的变换系数的存在空间的单元；对应译码的系数进行译码的单元；和第1～第3的本发明相同的列举单元和判断单元；对序号进行译码的单元；输出序号与所列举的顺序相等的格子点的单元。

本发明涉及实现高效率视频编码和译码的分段可逆视频编码、译码技术。若按照本发明，可使作为基本部分传送的代码保持与H.264标准的兼容性，同时可以尽量减小附加部分的代码量，可进行与原始信号一致的可逆译码。此外，若按照本发明，能够以几兆倍的高速进行处理。进而，可以不实际进行编码就能够对代码量进行推测，结果，可以快速进行减小代码量的预测模式的选择。