CN100433837C

CN100433837C - Integer Transform Method for Video Coding

Info

Publication number: CN100433837C
Application number: CNB2004100128571A
Authority: CN
Inventors: 朱光喜; 田晓华; 王曜; 刘文予; 喻莉
Original assignee: Huazhong University of Science and Technology
Current assignee: Huazhong University of Science and Technology
Priority date: 2004-03-18
Filing date: 2004-03-18
Publication date: 2008-11-12
Anticipated expiration: 2024-03-18
Also published as: KR20060043435A; CN1564602A; KR100636225B1

Abstract

The present invention belongs to the image processing technique, particularly relates to the integer transformation of the image data compression in the video codec, aiming at the first audio and video coding standard (AVS) that our country will formulate at present, adopts 8 by 8 integer type DCT transformation, proposes a A transform base selection method for integer transforms, comprehensively evaluates the decorrelation efficiency and energy concentration rate of transform bases, as well as the dynamic range and computational complexity of transform base transforms, and proposes two sets of 8×8 integer transforms with excellent performance bases (5, 6, 4, 1) and (4, 5, 3, 1), and obtain a fast algorithm for integer transformation based on these two bases.

Description

Integer Transform Method for Video Coding

技术领域 technical field

本发明属于图象处理技术，特别涉及视频编解码器中图像数据压缩的整数变换。主要包括整数变换的变换基(变换矩阵)的选择方法和基于选定变换基的块变换的实现方法。The invention belongs to image processing technology, in particular to integer transformation of image data compression in video codec. It mainly includes the selection method of the transformation base (transformation matrix) of the integer transformation and the realization method of the block transformation based on the selected transformation basis.

背景技术 Background technique

现有的国际视频标准如H.264、运动图象专家组MPEG-4中，视频信号被按层次划分为序列、帧、条带、宏块、块；最小的处理单元为块。在编码端，通过帧内预测或帧间预测，得到块的预测残差并作块变换，将能量集中到少数几个系数中；再通过量化、扫描、游程编码和熵编码，将图像数据压缩并写入编码码流。在解码端则过程相反，从码流中提取出熵编码的块变换系数，通过反量化和反变换，恢复出块的预测残差，结合预测信息，最终恢复出块的视频数据。在编解码流程中，变换模块是视频压缩的基础，变换性能直接影响编解码器的综合性能。In existing international video standards such as H.264 and Motion Picture Experts Group MPEG-4, video signals are hierarchically divided into sequences, frames, slices, macroblocks, and blocks; the smallest processing unit is a block. On the encoding side, through intra-frame prediction or inter-frame prediction, the prediction residual of the block is obtained and block transformation is performed to concentrate the energy into a few coefficients; and then the image data is compressed by quantization, scanning, run-length coding and entropy coding And write the encoded code stream. At the decoding end, the process is reversed. The entropy-encoded block transformation coefficients are extracted from the code stream, and the block prediction residual is recovered through inverse quantization and inverse transformation. Combined with the prediction information, the block video data is finally restored. In the codec process, the transformation module is the basis of video compression, and the transformation performance directly affects the overall performance of the codec.

早期的国际标准如MPEG-1、H.261采用离散余弦变换DCT。DCT自从1974年提出后，在图像和视频编码领域得到了广泛的应用，其变换性能在所有次优变换中非常显著，能极大地去除图像元素在变换域中的相关性，为高效率的图像压缩奠定了基础。但由于DCT的变换矩阵是用浮点数表示，浮点运算量较大，占用较多系统资源。为了提高变换效率，又发展出用定点计算或者较大的整型变换逼近浮点运算DCT，由于存在精度误差，即使没有经过量化，反变换后也不能完全恢复图像数据，也就是编码的可逆性不强。整数变换的产生，同时解决了计算精度和编码效率的问题，其特点是用整数变换矩阵代替DCT的浮点数变换矩阵，这样变换过程完全是整数运算，不存在精度误差，保证了编码的可逆性；同时整数乘法可用加减法和位移代替，因此变换过程可以完全通过加减法和位移实现，运算量大幅度降低。最新的国际标准H.264/MPEG-4Part 10就采用整数变换，并取得了非常好的变换效果。近年来，在图像和视频处理领域有不少针对整数变换的研究，已有的关于整数变换的国外专利主要有：Early international standards such as MPEG-1 and H.261 adopted discrete cosine transform DCT. Since DCT was proposed in 1974, it has been widely used in the field of image and video coding. Its transformation performance is very significant in all suboptimal transformations, and it can greatly remove the correlation of image elements in the transformation domain, providing high-efficiency images. Compression lays the groundwork. However, since the transformation matrix of DCT is represented by floating-point numbers, the amount of floating-point calculations is relatively large and takes up more system resources. In order to improve the conversion efficiency, fixed-point calculations or large integer transformations have been developed to approach floating-point calculations DCT. Due to the existence of precision errors, even without quantization, the image data cannot be completely restored after inverse transformation, that is, the reversibility of coding. Not strong. The generation of integer transformation solves the problems of calculation accuracy and coding efficiency at the same time. It is characterized by replacing the floating-point number transformation matrix of DCT with an integer transformation matrix. In this way, the transformation process is completely an integer operation, and there is no precision error, which ensures the reversibility of the coding. ; At the same time, integer multiplication can be replaced by addition, subtraction and displacement, so the transformation process can be completely realized by addition, subtraction and displacement, and the amount of calculation is greatly reduced. The latest international standard H.264/MPEG-4Part 10 adopts integer transformation and has achieved very good transformation effect. In recent years, there have been many studies on integer transformation in the field of image and video processing. The existing foreign patents on integer transformation mainly include:

1.U.S.Patent No.5999957A“Lossless Transform System For Digital Signals”；该专利通过对DCT变换矩阵的每一行乘以固定数值，再取整近似，将变换矩阵系数变为整数以实现可逆变换。该变换矩阵推导过程没有考虑变换的正交性，不能保证整数变换是正交变换，从而影响到变换性能。而且量化过程有多次乘除法，计算复杂。快速变换算法中有多次乘法，影响变换效率。1. U.S. Patent No. 5999957A "Lossless Transform System For Digital Signals"; this patent multiplies each row of the DCT transformation matrix by a fixed value, and then rounds the coefficients of the transformation matrix to integers to achieve reversible transformation. The transformation matrix derivation process does not consider the orthogonality of the transformation, and cannot guarantee that the integer transformation is an orthogonal transformation, thus affecting the transformation performance. Moreover, the quantization process has many times of multiplication and division, and the calculation is complicated. There are multiple multiplications in the fast transformation algorithm, which affects the transformation efficiency.

2.WO 01/08001A1“Integer Cosine Transform Using Integer Operations”；2. WO 01/08001A1 "Integer Cosine Transform Using Integer Operations";

3.U.S.Patent No.20020111979A1“Integer Transform Matrix For PictureCoding”；该专利给出一种整数变换矩阵变换性能的评价方法，主要通过比较与DCT变换矩阵的近似程度，该方法保证变换的正交性。专利给出了4乘4、8乘8、16乘16三种情况下理论上最好的变换矩阵。该方法也没有考虑计算复杂度对变换性能的影响，而且为了保证每一行或列的矢量范式相同，所选出的变换矩阵的性能并不是最接近DCT的。3. U.S. Patent No. 20020111979A1 "Integer Transform Matrix For Picture Coding"; this patent provides an evaluation method for the performance of integer transformation matrix transformation, mainly by comparing the degree of approximation with the DCT transformation matrix, and this method ensures the orthogonality of transformation. The patent gives the theoretically best transformation matrix in three cases of 4 by 4, 8 by 8, and 16 by 16. This method also does not consider the impact of computational complexity on the transformation performance, and in order to ensure that the vector paradigm of each row or column is the same, the performance of the selected transformation matrix is not the closest to DCT.

4.U.S.Patent No.2003/0093452A1“Video Block Transform”；该专利给出基于H.26L的4乘4块的正交和非正交形式的整数变换、反变换矩阵，宏块直流系数变换矩阵和正交变换对应的量化步长。该专利的变换矩阵尺度与本发明不同，小尺度的变换矩阵不适合高清晰度电视等应用。4.U.S.Patent No.2003/0093452A1 "Video Block Transform"; this patent provides the integer transformation and inverse transformation matrix of H.26L-based 4 by 4 blocks of orthogonal and non-orthogonal forms, and the macroblock DC coefficient transformation matrix The quantization step size corresponding to the orthogonal transformation. The scale of the transformation matrix in this patent is different from that of the present invention, and the small-scale transformation matrix is not suitable for applications such as high-definition television.

8乘8离散余弦可以用以下公式表示：An 8 by 8 discrete cosine can be represented by the following formula:

$Y Y ((u u,, v v)) = = \frac{11}{44} C C ((u u)) C C ((v v)) {Σ Σ}_{j j = = 00}^{77} {Σ Σ}_{k k = = 00}^{77} X x ((j j,, k k)) cos cos ((πu πu \frac{22 j j + + 11}{1616})) cos cos ((πv πv \frac{22 k k + + 11}{1616})) - - - - - - ((11))$

其中 $C (0) = 1 / \sqrt{2},$ C(w)＝1，(w＝1，…，7)。用矩阵的形式可以表示为：Y＝P₀XP₀ ^T，其中X为8乘8像素预测残差矩阵，Y为变换后的矩阵。in $C (0) = 1 / \sqrt{2},$ C(w)=1, (w=1, . . . , 7). In the form of a matrix, it can be expressed as: Y=P ₀ XP ₀ ^T , where X is an 8 by 8 pixel prediction residual matrix, and Y is a transformed matrix.

${P P}_{00} = = [\begin{matrix} a a & a a & a a & a a & a a & a a & a a & a a \\ b b & d d & e e & g g & - - g g & - - e e & - - d d & - - b b \\ c c & f f & - - f f & - - c c & - - c c & - - f f & f f & c c \\ d d & - - g g & - - b b & - - e e & e e & b b & g g & - - d d \\ a a & - - a a & - - a a & a a & a a & - - a a & - - a a & a a \\ e e & - - b b & g g & d d & - - d d & - - g g & b b & - - e e \\ f f & - - c c & c c & - - f f & - - f f & c c & - - c c & f f \\ g g & - - e e & d d & - - b b & b b & - - d d & e e & - - g g \end{matrix}],,$

其中 $a = \frac{1}{2 \sqrt{2}}$ $b = \frac{1}{2} \cos (\frac{π}{16})$ $c = \frac{1}{2} \cos (\frac{2 π}{16})$ $d = \frac{1}{2} \cos (\frac{3 π}{16})$ in $a = \frac{1}{2 \sqrt{2}}$ $b = \frac{1}{2} \cos (\frac{π}{16})$ $c = \frac{1}{2} \cos (\frac{2 π}{16})$ $d = \frac{1}{2} \cos (\frac{3 π}{16})$

$e e = = \frac{11}{22} cos cos ((\frac{55 π π}{1616}))$ $f f = = \frac{11}{22} cos cos ((\frac{66 π π}{1616}))$ $g g = = \frac{11}{22} cos cos ((\frac{77 π π}{1616}))$

根据国际标准H.264对4x4DCT变换的改写过程，可以改写8x8变换如下：从P₀的每一行提出一个公共系数，得到向量V₈＝[a，m，f，m，a，m，f，m]，其中m为矩阵P₀的偶数行提出的公共系数，m的取值为不大于k4的正数。则变换矩阵改写为：According to the rewriting process of the international standard H.264 to the 4x4DCT transformation, the 8x8 transformation can be rewritten as follows: a common coefficient is proposed from each row of P ₀ to obtain a vector V ₈ =[a, m, f, m, a, m, f, m], where m is the common coefficient proposed by the even row of the matrix P ₀ , and the value of m is a positive number not greater than k4. Then the transformation matrix is rewritten as:

$P_{1} = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ k 1 & k 2 & k 3 & k 4 & - k 4 & - k 3 & - k 2 & - k 1 \\ k 5 & 1 & - 1 & - k 5 & - k 5 & - 1 & 1 & k 5 \\ k 2 & - k 4 & - k 1 & - k 3 & k 3 & k 1 & k 4 & - k 2 \\ 1 & - 1 & - 1 & 1 & 1 & - 1 & - 1 & 1 \\ k 3 & - k 1 & k 4 & k 2 & - k 2 & - k 4 & k 1 & - k 3 \\ 1 & - k 5 & k 5 & - 1 & - 1 & k 5 & - k 5 & 1 \\ k 4 & - k 3 & k 2 & - k 1 & k 1 & - k 2 & k 3 & - k 4 \end{matrix}],$ 其中 $\begin{matrix} k 1 = b / m \\ k 2 = d / m \\ k 3 = e / m \\ k 4 = g / m \\ k 5 = c / f \end{matrix}$ $P_{1} = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ k 1 & k 2 & k 3 & k 4 & - k 4 & - k 3 & - k 2 & - k 1 \\ k 5 & 1 & - 1 & - k 5 & - k 5 & - 1 & 1 & k 5 \\ k 2 & - k 4 & - k 1 & - k 3 & k 3 & k 1 & k 4 & - k 2 \\ 1 & - 1 & - 1 & 1 & 1 & - 1 & - 1 & 1 \\ k 3 & - k 1 & k 4 & k 2 & - k 2 & - k 4 & k 1 & - k 3 \\ 1 & - k 5 & k 5 & - 1 & - 1 & k 5 & - k 5 & 1 \\ k 4 & - k 3 & k 2 & - k 1 & k 1 & - k 2 & k 3 & - k 4 \end{matrix}],$ in $\begin{matrix} k 1 = b / m \\ k \\ 2 = d / m \\ k 3 = e / m \\ k \\ 4 = g / m \\ k 5 = c / f \end{matrix}$

令矩阵E₈＝V₈ ^TV₈，是8乘8矩阵，则变换进一步改写为：Let the matrix E ₈ =V ₈ ^T V ₈ be an 8 by 8 matrix, then the transformation is further rewritten as:

$Y Y = = {P P}_{11} X x {P P}_{11}^{T T} &CircleTimes; &CircleTimes; {E E.}_{88} - - - - - - ((22))$

其中

表示两个矩阵的叉乘(即相同位置的元素对应相乘)。对于(2)式可以将与矩阵E₈的叉乘运算和量化操作放到一起，使变换得到简化。因此变换的重点在于P₁XP₁ ^T的计算，其中X是8x8的像素预测残差矩阵，为整形数据。如果P₁中的变量k1，k2，k3，k4，k5都为整数，则整个变换将全部转化为整数运算。in

Represents the cross product of two matrices (that is, elements in the same position are multiplied accordingly). For formula (2), the cross product operation and quantization operation with the matrix E ₈ can be put together to simplify the transformation. Therefore, the focus of the transformation lies in the calculation of P ₁ XP ₁ ^T , where X is an 8x8 pixel prediction residual matrix, which is shaped data. If the variables k1, k2, k3, k4, and k5 in _P1 are all integers, the entire transformation will be converted into integer operations.

所以下面的工作就需要确定k1，k2，k3，k4，k5等五个参数的选值。本发明通过大量实验证明，当选定k1，k2，k3，k4后，k5取2时的变换性能最好，Cham在他的文章(Development of Integer Cosine Transform by the Principle of DyadicSymmetry.IEE Proceedings，1989，136(4)：276-288)也提出了相似的结论。因而本发明将k5固定取值为2，仅研究其余四个参数的选择，并定义(k1，k2，k3，k4)为整数变换的变换基。对应的变换矩阵P为Therefore, the following work needs to determine the selected values of five parameters such as k1, k2, k3, k4, and k5. The present invention proves through a large number of experiments that when k1, k2, k3, and k4 are selected, the transformation performance when k5 is 2 is the best, Cham wrote in his article (Development of Integer Cosine Transform by the Principle of DyadicSymmetry.IEE Proceedings, 1989 , 136(4):276-288) also made similar conclusions. Therefore, the present invention fixes the value of k5 to 2, only studies the selection of the other four parameters, and defines (k1, k2, k3, k4) as the transformation basis of integer transformation. The corresponding transformation matrix P is

$P P = = (\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ k k 11 & k k 22 & k k 33 & k k 44 & - - k k 44 & - - k k 33 & - - k k 22 & - - k k 11 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 & k k 33 & k k 11 & k k 44 & - - k k 22 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ k k 33 & - - k k 11 & k k 44 & k k 22 & - - k k 22 & - - k k 44 & k k 11 & - - k k 33 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 & k k 11 & - - k k 22 & k k 33 & - - k k 44 \end{matrix})$

发明内容 Contents of the invention

本发明提出了一种视频编码的整数变换方法，针对当前我国将要制定的第一个音视频编码标准(AVS)采用8乘8整数类DCT变换，提出了一种整数变换的变换基选择方法，综合评价变换基的去相关效率和能量集中率两项指标及变换基变换动态范围和计算复杂度，并通过此方法提出两组性能优异的8乘8整数变换基(5，6，4，1)和(4，5，3，1)，并得到基于这两组基的整数变换快速算法。The present invention proposes a method for integer transformation of video coding. Aiming at the first audio and video coding standard (AVS) to be formulated in my country, which adopts 8 by 8 integer DCT transformation, a transformation base selection method for integer transformation is proposed. Comprehensively evaluate the two indicators of decorrelation efficiency and energy concentration rate of the transformation base, as well as the dynamic range and computational complexity of the transformation base transformation, and through this method, two sets of 8×8 integer transformation bases (5, 6, 4, 1 ) and (4, 5, 3, 1), and obtain a fast algorithm for integer transformation based on these two groups of bases.

变换基的选择主要基于以下几项原则：The selection of the transformation base is mainly based on the following principles:

原则1：变换正交性。正交变换的特性保证变换仅仅是对坐标系的旋转，而图像的能量维持不变。为了保证变换的正交性，公式(2)中的P必须满足下式条件：Principle 1: Transform Orthogonality. The characteristics of orthogonal transformation guarantee that the transformation is only the rotation of the coordinate system, while the energy of the image remains unchanged. In order to ensure the orthogonality of transformation, P in formula (2) must satisfy the following conditions:

P·P^T＝Diag (3)P · P ^T = Diag (3)

其中Diag为对角阵，即其非主对角线元素为零。量化过程再通过调整量化矩阵，使变换满足正交性。Among them, Diag is a diagonal matrix, that is, its non-main diagonal elements are zero. The quantization process then adjusts the quantization matrix to make the transformation meet the orthogonality.

原则2：能量集中性。DCT变换的目的在于去除元素之间的相关性，使变换后的能量尽可能集中在少数系数上，以便提高量化后熵编码的压缩效率。整数变换基的选择同样也需要遵循这一原则。Principle 2: Energy Concentration. The purpose of DCT transformation is to remove the correlation between elements, so that the energy after transformation can be concentrated on a few coefficients as much as possible, so as to improve the compression efficiency of entropy coding after quantization. The choice of integer transformation base also needs to follow this principle.

原则3：快速变换算法简单性。要求变换基数值不能太大，快速算法的计算次数尽可能少。Principle 3: Simplicity of fast transformation algorithms. It is required that the transformation base value should not be too large, and the calculation times of the fast algorithm should be as few as possible.

本发明的一种视频编码的整数变换方法，在编码端，通过帧内预测或帧间预测，得到块的预测残差并作块变换，将能量集中到少数几个系数中；再通过量化、扫描、游程编码和熵编码，将图像数据压缩并写入编码码流；在解码端则从码流中提取出熵编码的块变换系数，通过反量化和反变换，恢复出块的预测残差，结合预测信息，恢复出块的视频数据；其特征在于：In the integer transformation method of video coding of the present invention, at the coding end, through intra-frame prediction or inter-frame prediction, the prediction residual of the block is obtained and block transformation is performed, and the energy is concentrated into a few coefficients; and then through quantization, Scanning, run-length coding, and entropy coding compress the image data and write it into the coded code stream; at the decoding end, the block transformation coefficients of the entropy code are extracted from the code stream, and the prediction residual of the block is restored by inverse quantization and inverse transformation , combined with prediction information, recovering block video data; characterized in that:

(1)视频编码中8乘8整数变换采用的变换矩阵P由如下步骤得到：(1) The transformation matrix P adopted by the 8 by 8 integer transformation in the video coding is obtained by the following steps:

(1.1)首先搜索在一定范围内满足正交条件的所有整数变换基，(1.1) First search for all integer transformation bases that satisfy the orthogonality condition within a certain range,

对于8乘8整数变换矩阵P，定义变换基为(k1，k2，k3，k4)，For an 8 by 8 integer transformation matrix P, the transformation basis is defined as (k1, k2, k3, k4),

变换基系数k1、k2、k3、k4的取值范围为k1、k2、k3∈[1，10]，k4∈[1，4]，得到所有满足P·P^T＝Diag的整数正交变换基；The value ranges of transformation base coefficients k1, k2, k3, and k4 are k1, k2, k3∈[1, 10], k4∈[1, 4], and all integer orthogonal transformation bases satisfying P· ^PT =Diag are obtained ;

(1.2)建立输入图像残差数据在互相关系数ρ取0.75、0.8、0.85、0.9、0.95时的协方差矩阵COV(X_v)，(1.2) Establish the covariance matrix COV(X _v ) of the input image residual data when the cross-correlation coefficient ρ is 0.75, 0.8, 0.85, 0.9, 0.95,

设长度为8的图像残差数据一维向量为X_V＝[x₁，x₂，...x₈]，由一阶马尔科夫模型建立X_V元素的协方差矩阵COV(X_v)，COV(X_v)_(i，j)＝ρ^|i-j|(0≤i，j≤7)，其中ρ为X_V相邻元素的互相关系数(ρ≤1)，Let the one-dimensional vector of image residual data with a length of 8 be X _V =[x ₁ , x ₂ ,...x ₈ ], and establish the covariance matrix COV(X _v ) of X _V elements by the first-order Markov model , COV(X _v ) _{(i, j)} = ρ ^|ij| (0≤i, j≤7), where ρ is the cross-correlation coefficient of adjacent elements of X _V (ρ≤1),

(1.3)通过变换基对应的变换矩阵P，得到变换域的协方差矩阵COV(Y_v)，(1.3) By transforming the transformation matrix P corresponding to the base, the covariance matrix COV(Y _v ) of the transformation domain is obtained,

变换基(k1，k2，k3，k4)对应的变换矩阵P，归一化，即P每一行元素除以该行向量的长度，得到正交矩阵P_u。对X_V作正交变换Y_V＝P_uX_V，Y_V的协方差矩阵为：The transformation matrix P corresponding to the transformation basis (k1, k2, k3, k4) is normalized, that is, each row element of P is divided by the length of the row vector to obtain an orthogonal matrix P _u . Make an orthogonal transformation Y _V ＝P _u X _V on X _V , and the covariance matrix of Y _V is:

$COV COV (({Y Y}_{v v})) = = {P P}_{u u} \cdot &Center Dot; COV COV (({X x}_{v v})) \cdot \cdot {P P}_{u u}^{T T} - - - - - - ((44))$

(1.4)通过(2)、(3)计算各组变换基在互相关系数ρ取0.75、0.8、0.85、0.9、0.95时的能量集中率η_E值和去相关效率η_C值，(1.4) Calculate the energy concentration rate η _E value and decorrelation efficiency η _C value when the cross-correlation coefficient ρ gets 0.75, 0.8, 0.85, 0.9, 0.95 by (2), (3) calculation,

定义能量集中率η_E为：Define the energy concentration ratio η _E as:

${η η}_{E E.} = = \frac{11}{\sqrt[88]{{Π Π}_{i i = = 11}^{88} COV COV {(({Y Y}_{v v}))}_{((i i,, i i))}}} - - - - - - ((55))$

去相关效率η_c为：Decorrelation efficiency _ηc is:

${η η}_{c c} = = 11 - - \frac{\underset{j j &NotEqual; &NotEqual; k k}{Σ Σ} | | {COV COV (({Y Y}_{v v}))}_{((j j,, k k))} | |}{\underset{j j &NotEqual; &NotEqual; k k}{Σ Σ} | | {COV COV (({X x}_{v v}))}_{((j j,, k k))} | |} - - - - - - ((66))$

(1.5)计算各个变换基在指定的互相关系数ρ下的能量集中率η_E值和去相关效率η_C归一化的结果，同一个ρ下，第i个变换基能量集中率η_E的归一化结果为：(1.5) Calculate the normalized results of the energy concentration rate η _E value and decorrelation efficiency η _C of each transformation base under the specified cross-correlation coefficient ρ, under the same ρ, the energy concentration rate η _E of the i-th transformation base The normalized result is:

${Eval Eval}_{E E. ((i i))} = = \frac{{η η}_{E E. ((i i))} - - Min Min (({η η}_{E E. ((j j))}))}{Max Max (({η η}_{E E. ((j j))})) - - Min Min (({η η}_{E E. ((j j))}))} - - - - - - ((77))$

第i个变换基去相关效率η_C的归一化结果为：The normalized result of the i-th transformation base decorrelation efficiency η _C is:

${Eval Eval}_{c c ((i i))} = = \frac{{η η}_{c c ((i i))} - - Min Min (({η η}_{c c ((j j))}))}{Max Max (({η η}_{c c ((j j))})) - - Min Min (({η η}_{c c ((j j))}))} - - - - - - ((88))$

(1.6)通过加权求和，得到每组基在各个互相关系数ρ下能量集中率η_E值、去相关效率η_C综合的评价结果Eval_E、、、Eval_C，5点ρ对应的权重分别为1/15、2/15、3/15、4/15、5/15；(1.6) By weighted summation, the comprehensive evaluation results Eval _E , , Eval _C of the energy concentration rate η _E value and decorrelation efficiency η _C of each group base under each cross-correlation coefficient ρ are obtained, and the weights corresponding to 5 points ρ are respectively 1/15, 2/15, 3/15, 4/15, 5/15;

(1.7)通过对Eval_C和Eval_E这两项指标加权求和，得到变换基性能的综合评价值Eval，Eval_C和Eval_E对应的权重分别为0.4、0.6；(1.7) By weighting and summing the two indicators Eval _C and Eval _E , the comprehensive evaluation value Eval of the transformation base performance is obtained, and the corresponding weights of Eval _C and Eval _E are 0.4 and 0.6 respectively;

(1.8)根据所述综合评价值选择变换基，从而获得所述整数变换矩阵；(1.8) selecting a transformation base according to the comprehensive evaluation value, thereby obtaining the integer transformation matrix;

(2)正变换，对8乘8的图像残差数据块做整数变换，形如Y＝PXP^T，变换的基本单元是形如y＝Px的8点一维变换，其中x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，输出的y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，计算过程如下：(2) Forward transformation, an integer transformation is done to the image residual data block of 8 by 8, in the form of Y=PXP ^T , the basic unit of transformation is an 8-point one-dimensional transformation in the form of y=Px, where x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , the calculation process is as follows:

(2.2)a0＝x0-x7，a1＝x1-x6，a2＝x2-x5，a3＝x3-x4，a4＝x0+x7，a5＝x1+x6，a6＝x2+x5，a7＝x3+x4；(2.2) a0=x0-x7, a1=x1-x6, a2=x2-x5, a3=x3-x4, a4=x0+x7, a5=x1+x6, a6=x2+x5, a7=x3+x4 ;

(2.2)b0＝a4+a7，b1＝a5+a6，b2＝a4-a7，b3＝a5-a6；(2.2) b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

(2.3)y0＝b0+b1，y4＝b0-b1，y2＝b2＜＜1+b3，y6＝b2-b3＜＜1；(2.3) y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

(2.4)再完成相当计算下式的计算步骤：(2.4) Complete the calculation steps corresponding to the following formula:

$(\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}),,$

(3)反变换：(3) Inverse transformation:

令一维变换基本单元为x＝P^Ty，其中y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T.一维反变换为：Let the basic unit of one-dimensional transformation be x=P ^T y, wherein y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T . One-dimensional inverse transformation is:

(3.1)m0＝y0+y4；m1＝y0-y4；m2＝y2＜＜1+y6；m3＝y2-y6＜＜1；(3.1) m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

(3.2)b0＝m0+m2；b1＝m1+m3；b2＝m1-m3；b3＝m0-m2；(3.2) b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

(3.3)计算下式的4乘4矩阵乘法：(3.3) Calculate the 4 by 4 matrix multiplication of the following formula:

$(\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix})$

计算过程与正变换的4乘4矩阵乘法完全相同，只是输入输出数据向量交换；The calculation process is exactly the same as the 4 by 4 matrix multiplication of the forward transformation, except that the input and output data vectors are exchanged;

(3.4)x0＝a0+b0；x1＝a1+b1；x2＝a2+b2；x3＝a3+b3；(3.4) x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

x7＝-a0+b0；x6＝-a1+b1；x5＝-a2+b2；x4＝-a3+b3；x7=-a0+b0; x6=-a1+b1; x5=-a2+b2; x4=-a3+b3;

其中“＜＜”表示向左位移运算，其优先级高于加减法。Among them, "<<" represents a leftward shift operation, and its priority is higher than that of addition and subtraction.

所述的视频编码的整数变换方法，其进一步特征在于，所述得到变换矩阵P的步骤(1.7)得到变换基性能的综合评价值Eval后，增加对变换基(k1，k2，k3，k4)的计算复杂度的评价步骤：首先选择综合评价值Eval较高的变换基；如果Eval差距小于0.02，在实时性要求较高的应用中优先考虑计算复杂度有明显优势即加减法和位移次数少的变换基。The integer transformation method of video coding is further characterized in that after the step (1.7) of obtaining the transformation matrix P obtains the comprehensive evaluation value Eval of the transformation base performance, the transformation base (k1, k2, k3, k4) is added The evaluation steps of the computational complexity: first select the transformation base with a higher comprehensive evaluation value Eval; if the Eval difference is less than 0.02, give priority to the computational complexity in applications with high real-time requirements. Fewer transformation bases.

所述的视频编码的整数变换方法，其特征在于：The integer transformation method of the video coding is characterized in that:

(3.1)视频编码中8乘8整数变换采用的变换矩阵P由前述视频编码的整数变换矩阵选择步骤得到，如下式：(3.1) The transformation matrix P that 8 multiplies 8 integer transformations in the video encoding is obtained by the integer transformation matrix selection step of the foregoing video encoding, as follows:

$P P = = (\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 55 & 66 & 44 & 11 & - - 11 & - - 44 & - - 66 & - - 55 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ 66 & - - 11 & - - 55 & - - 44 & 44 & 55 & 11 & - - 66 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ 44 & - - 55 & 11 & 66 & - - 66 & - - 11 & 55 & - - 44 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ 11 & - - 44 & 66 & - - 55 & 55 & - - 66 & 44 & - - 11 \end{matrix})$

相应的整数变换基为(5，6，4，1)；The corresponding integer transformation base is (5, 6, 4, 1);

(3.2)正变换，对8乘8的图像残差数据块做整数变换，形如Y＝PXP^T，变换的基本单元是形如y＝Px的8点一维变换，其中x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，输出的y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，计算过程如下：(3.2) Forward transformation, the image residual data block of 8 is multiplied by 8 is done integer transformation, and the basic unit of transformation is 8 points one-dimensional transformation such as y= ^Px , wherein x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , the calculation process is as follows:

A.a0＝x0-x7，a1＝x1-x6，a2＝x2-x5，a3＝x3-x4，a4＝x0+x7，a5＝x1+x6，a6＝x2+x5，a7＝x3+x4；A. a0=x0-x7, a1=x1-x6, a2=x2-x5, a3=x3-x4, a4=x0+x7, a5=x1+x6, a6=x2+x5, a7=x3+x4;

B.b0＝a4+a7，b1＝a5+a6，b2＝a4-a7，b3＝a5-a6；B.b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

C.y0＝b0+b1，y4＝b0-b1，y2＝b2＜＜1+b3，y6＝b2-b3＜＜1；C.y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

再完成相当计算下式的计算步骤：Then complete the calculation steps equivalent to the following formula:

D.c0＝a0＜＜2+a0+a3；c1＝a2-a1-a1＜＜2；c2＝a1+a2+a2＜＜2；c3＝a3＜＜2+a3-a0；D.c0=a0<<2+a0+a3; c1=a2-a1-a1<<2; c2=a1+a2+a2<<2; c3=a3<<2+a3-a0;

E.y1＝c0-c1+c2；y3＝c0-c2-c3；y5＝c0+c1+c3；y7＝c1+c2-c3；E.y1=c0-c1+c2; y3=c0-c2-c3; y5=c0+c1+c3; y7=c1+c2-c3;

(3.3)反变换，令一维变换基本单元为x＝P^Ty。其中y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，一维反变换为：(3.3) Inverse transformation, let the basic unit of one-dimensional transformation be x=P ^T y. Where y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the one-dimensional inverse transformation is:

A.m0＝y0+y4；m1＝y0-y4；m2＝y2＜＜1+y6；m3＝y2-y6＜＜1；A.m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

B.b0＝m0+m2；b1＝m1+m3；b2＝m1-m3；b3＝m0-m2；B.b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

C.计算下式的4乘4矩阵乘法：C. Compute the 4 by 4 matrix multiplication of:

D.x0＝a0+b0；x1＝a1+b1；x2＝a2+b2；x3＝a3+b3；D. x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

其中“＜＜”表示向左位移运算，其优先级高于加减法，“a＜＜b”表示a向左位移b位。Among them, "<<" represents a leftward shift operation, and its priority is higher than that of addition and subtraction, and "a<<b" represents that a is shifted to the left by b bits.

所述的又一种视频编码的整数变换方法，其特征在于：Another integer transformation method for video coding is characterized in that:

(4.1)视频编码中8乘8整数变换采用的变换矩阵P由前述视频编码的整数变换矩阵选择步骤得到，也可以如下式：(4.1) The transformation matrix P adopted by 8 by 8 integer transformations in video coding is obtained by the integer transformation matrix selection step of the aforementioned video coding, and can also be as follows:

$(\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 44 & 55 & 33 & 11 & - - 11 & - - 33 & - - 55 & - - 44 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ 55 & - - 11 & - - 44 & - - 33 & 33 & 44 & 11 & - - 55 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ 33 & - - 44 & 11 & 55 & - - 55 & - - 11 & 44 & - - 33 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ 11 & - - 33 & 55 & - - 44 & 44 & - - 55 & 33 & - - 11 \end{matrix})$

相应的整数变换基为(4，5，3，1)；The corresponding integer transformation base is (4, 5, 3, 1);

(4.2)正变换，对8乘8的图像残差数据块做整数变换，形如Y＝PXP^T，变换的基本单元是形如y＝Px的8点一维变换，其中x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，输出的y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T。计算过程如下：(4.2) Forward transformation, an integer transformation is done to the image residual data block of 8 by 8, in the form of Y=PXP ^T , the basic unit of transformation is an 8-point one-dimensional transformation in the form of y=Px, where x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T . The calculation process is as follows:

D.c0＝a0＜＜2+a3；c1＝a2-a1＜＜2；c2＝a1+a2＜＜2；c3＝a3＜＜2-a0；D.c0=a0<<2+a3; c1=a2-a1<<2; c2=a1+a2<<2; c3=a3<<2-a0;

(4.3)反变换：(4.3) Inverse transformation:

令一维变换基本单元为x＝P^Ty。其中y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，一维反变换为：Let the basic unit of one-dimensional transformation be x=P ^T y. Where y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the one-dimensional inverse transformation is:

快速算法的计算过程与正变换的4乘4矩阵乘法完全相同，只是输入输出数据向量交换；The calculation process of the fast algorithm is exactly the same as the 4x4 matrix multiplication of the forward transformation, except that the input and output data vectors are exchanged;

本发明提出了一种整数变换基性能的综合评价方法，并依据这一方法筛选出几组性能较好的变换基，并给出两组变换基的快速变换方法。高清晰度视频测试序列的实测结果证明本法明优选的几组变换基的性能优于JVT的ABT 8乘8变换，其中(10，9，6，2)的变换性能最好，(4，5，3，1)的计算复杂度最低，(5，6，4，1)的性能介于两者之间。相对于ABT 8乘8变换，这3组基在变换性能和计算复杂度等两方面都具有一定优势。所选变换基的实测性能也验证了本发明变换基选择方法的准确性和可行性，该方法不仅仅适用于整数变换矩阵，还可用于对各类变换矩阵的性能评估，对于变换矩阵的选择具有很强的指导意义。The invention proposes a comprehensive evaluation method for the performance of integer transformation bases, screens out several groups of transformation bases with better performance according to the method, and provides a fast transformation method for two groups of transformation bases. The measured results of the high-definition video test sequence prove that the performance of several sets of transformation bases selected by this method is better than the ABT 8 by 8 transformation of JVT, and the transformation performance of (10, 9, 6, 2) is the best, and (4, 5, 3, 1) has the lowest computational complexity, and (5, 6, 4, 1) has the performance in between. Compared with the ABT 8x8 transformation, these three groups of bases have certain advantages in both transformation performance and computational complexity. The measured performance of the selected transformation base has also verified the accuracy and feasibility of the transformation base selection method of the present invention. This method is not only applicable to integer transformation matrices, but also can be used for performance evaluation of various transformation matrices. For the selection of transformation matrices Has a strong guiding significance.

说明书附图Instructions attached

图1：变换基评价流程框图。Figure 1: Flowchart of transform base evaluation.

图2：变换基(5，6，4，1)正变换快速算法。Figure 2: Transform basis (5, 6, 4, 1) forward transformation fast algorithm.

图3：变换基(5，6，4，1)反变换快速算法。Figure 3: Transform base (5, 6, 4, 1) inverse transform fast algorithm.

图4：变换基(4，5，3，1)正变换快速算法。Figure 4: Transform basis (4, 5, 3, 1) forward transformation fast algorithm.

图5：变换基(4，5，3，1)反变换快速算法。Figure 5: Transform base (4, 5, 3, 1) inverse transform fast algorithm.

具体实施方式 Detailed ways

(一)变换基的选择(1) Selection of transformation base

变换基的评价流程如图1所示。The evaluation process of the transformation base is shown in Figure 1.

各类图像残差数据的互相关系数ρ主要分布在0.75～0.95之间，通过计算ρ为0.75、0.8、0.85、0.9、0.95五点的每个变换基对应的能量集中率η_E，再将同一ρ下各个基的η_E归一化。对同一变换基在不同互相关系数ρ下η_E归一化结果加权求和，得到该组基能量集中率的综合评价值Eval_E，其中权重是根据不同ρ的概率大小决定。本发明中取五点ρ对应的权重依次为1/15、2/15、3/15、4/15、5/15。同理得到变换基的去相关效率η_c的综合评价结果Eval_C。The cross-correlation coefficient ρ of various image residual data is mainly distributed between 0.75 and 0.95. By calculating the energy concentration ratio η _E corresponding to each transformation base with ρ being 0.75, 0.8, 0.85, 0.9, and 0.95, the The η _E of each base under the same ρ is normalized. The weighted sum of the normalized results of η _E of the same transformation base under different cross-correlation coefficients ρ is used to obtain the comprehensive evaluation value Eval _E of the energy concentration ratio of the group of bases, where the weight is determined according to the probability of different ρ. In the present invention, the weights corresponding to five points ρ are sequentially 1/15, 2/15, 3/15, 4/15, and 5/15. In the same way, the comprehensive evaluation result Eval _C of the decorrelation efficiency η _c of the transformation base is obtained.

最后通过对Eval_E和Eval_C加权求和得到变换基能量集中率和去相关效率的综合评价值Eval。考虑到能量集中率直接影响变换后的压缩性能，权重略大，本发明中定义能量集中率和去相关效率评价值的权重分别为：0.6、0.4。Finally, by weighting and summing Eval _E and Eval _C , the comprehensive evaluation value Eval of the energy concentration ratio and decorrelation efficiency of the transformation basis is obtained. Considering that the energy concentration ratio directly affects the transformed compression performance, the weight is slightly larger. In the present invention, the weights of the energy concentration ratio and decorrelation efficiency evaluation value are defined as 0.6 and 0.4, respectively.

当综合评价值Eval接近时，计算复杂度低的变换基的性能更好。When the comprehensive evaluation value Eval is close, the performance of the transformation basis with low computational complexity is better.

下表中列出了变换基的取值范围为k1、k2、k3∈[1，10]，k4∈[1，4]时，5组基的η_E和η_c综合评价值、完成一次一维8点变换所需要的加法和位移次数(正反变换的远算次数相同)。The following table lists the comprehensive evaluation values of η _E and η _c of the five groups of bases when the value ranges of the transformation bases are k1, k2, k3∈[1, 10], k4∈[1, 4], completed once The number of additions and displacements required for 8-dimensional transformation (the number of remote calculations for positive and negative transformations is the same).

(10，9，6，2)和(6，6，3，2)在有关文献中已被提出。(5，6，4，1)的去相关效率和能量集中率的综合评价值仅次于(10，9，6，2)，而且计算复杂度较小，(4，5，3，1)的综合评价值略低于(6，6，3，2)，但计算复杂度优势最明显。实际的视频序列测试结果表明(5，6，4，1)、(4，5，3，1)、(6，7，5，1)的率失真性能优于(6，6，3，2)，与(10，9，6，2)很接近。(二)8x8整数变换快速算法的实现(10, 9, 6, 2) and (6, 6, 3, 2) have been proposed in related literature. The comprehensive evaluation value of decorrelation efficiency and energy concentration rate of (5, 6, 4, 1) is second only to (10, 9, 6, 2), and the calculation complexity is small, (4, 5, 3, 1) The comprehensive evaluation value of is slightly lower than (6, 6, 3, 2), but the advantage of computational complexity is the most obvious. The actual video sequence test results show that (5, 6, 4, 1), (4, 5, 3, 1), (6, 7, 5, 1) have better rate-distortion performance than (6, 6, 3, 2 ), which is very close to (10, 9, 6, 2). (2) Realization of fast algorithm for 8x8 integer transformation

图2-图5中x0、x1、x2、x3、x4、x5、x6、x7表示整数变换的一维正变换的输入八点数值，同时是反变换的八点输出数值；y0、y1、y2、y3、y4、y5、y6、y7为正变换的八点输出数值，同时是反变换的八点输出数值。数据处理方向从左向右，相交于一圆点的两线表示两数据相加，三线表示三个数据相加。方形表示数据乘一个系数，其中“-”表示取负值，“2”表示乘2，即左移一位，“4”表示乘4，即左移两位。In Figure 2-Figure 5, x0, x1, x2, x3, x4, x5, x6, and x7 represent the input eight-point value of the one-dimensional forward transformation of the integer transformation, and the eight-point output value of the inverse transformation; y0, y1, y2 , y3, y4, y5, y6, and y7 are the eight-point output value of the forward transformation, and are the eight-point output value of the reverse transformation. The direction of data processing is from left to right. Two lines intersecting at a dot represent the addition of two data, and three lines represent the addition of three data. A square means that the data is multiplied by a coefficient, where "-" means to take a negative value, "2" means to multiply by 2, that is, to shift one bit to the left, and "4" means to multiply by 4, that is, to shift to the left by two bits.

1.正变换1. Positive transformation

对8x8的图像残差数据块做整数变换，变换的基本单元是形如y＝Px的8点一维变换，设x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，输出的y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T。计算过程如下：Perform integer transformation on the 8x8 image residual data block, the basic unit of transformation is an 8-point one-dimensional transformation of the form y=Px, set x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T . The calculation process is as follows:

首先计算用各个不同变换矩阵P作变换时，相同的计算步骤：First calculate the same calculation steps when using different transformation matrices P for transformation:

(1)a0＝x0-x7，a1＝x1-x6，a2＝x2-x5，a3＝x3-x4，a4＝x0+x7，a5＝x1+x6，a6＝x2+x5，a7＝x3+x4；(1) a0=x0-x7, a1=x1-x6, a2=x2-x5, a3=x3-x4, a4=x0+x7, a5=x1+x6, a6=x2+x5, a7=x3+x4 ;

(2)b0＝a4+a7，b1＝a5+a6，b2＝a4-a7，b3＝a5-a6；(2) b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

(3)y0＝b0+b1，y4＝b0-b1，y2＝b2＜＜1+b3，y6＝b2-b3＜＜1；(3) y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

相同部分计算需要加减法16次，位移2次。The calculation of the same part requires 16 additions and subtractions and 2 shifts.

再计算不同的计算步骤，该部分相当于计算下式：Then calculate the different calculation steps, this part is equivalent to calculating the following formula:

对于变换基(5，6，4，1)计算步骤为：For the transformation base (5, 6, 4, 1), the calculation steps are:

(1)c0＝a0＜＜2+a0+a3；c1＝a2-a1-a1＜＜2；c2＝a1+a2+a2＜＜2；c3＝a3＜＜2+a3-a0；(1) c0=a0<<2+a0+a3; c1=a2-a1-a1<<2; c2=a1+a2+a2<<2; c3=a3<<2+a3-a0;

(2)y1＝c0-c1+c2；y3＝c0-c2-c3；y5＝c0+c1+c3；y7＝c1+c2-c3；(2) y1=c0-c1+c2; y3=c0-c2-c3; y5=c0+c1+c3; y7=c1+c2-c3;

共需要16次加减法和4次位移。A total of 16 additions and subtractions and 4 displacements are required.

对于变换基(4，5，3，1)计算步骤为：For the transformation base (4, 5, 3, 1), the calculation steps are:

(1)c0＝a0＜＜2+a3；c1＝a2-a1＜＜2；c2＝a1+a2＜＜2；c3＝a3＜＜2-a0；(1) c0=a0<<2+a3; c1=a2-a1<<2; c2=a1+a2<<2; c3=a3<<2-a0;

共需要12次加减法和4次位移。A total of 12 additions and subtractions and 4 displacements are required.

因此对于变换基(5，6，4，1)完成一次y＝Px运算，共用32次加减法和6次位移；变换基(4，5，3，1)共用28次加减法和6次位移。完成一次8x8块的整数变换的运算量是上述单元计算量的16倍。(5，6，4，1)正变换的快速算法如图2所示，(4，5，3，1)正变换的快速算法如图4所示。Therefore, a y=Px operation is completed for the transformation base (5, 6, 4, 1), sharing 32 additions and subtractions and 6 displacements; the transformation base (4, 5, 3, 1) shares 28 additions and subtractions and 6 secondary displacement. The amount of computation for completing an integer transformation of an 8x8 block is 16 times the amount of computation of the above unit. The fast algorithm of (5, 6, 4, 1) forward transformation is shown in Figure 2, and the fast algorithm of (4, 5, 3, 1) forward transformation is shown in Figure 4.

2.反变换2. Inverse transformation

令一维变换基本单元为x＝P^Ty。Let the basic unit of one-dimensional transformation be x=P ^T y.

其中y＝[y0，y1，y2，y3，y4，y5，y6，y7]^T，x＝[x0，x1，x2，x3，x4，x5，x6，x7]^T，下述过程为一次x＝P^Ty运算。Wherein y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the following process is once x= P ^T y operation.

(1)m0＝y0+y4；m1＝y0-y4；m2＝y2＜＜1+y6；m3＝y2-y6＜＜1；(1) m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

(2)b0＝m0+m2；b1＝m1+m3；b2＝m1-m3；b3＝m0-m2；(2) b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

(3)计算下式的4乘4矩阵乘法：(3) Calculate the 4 by 4 matrix multiplication of the following formula:

计算式和正变换中4x4矩阵乘法完全相同，算法一样，只是输入输出数据向量交换。计算量相同。对于变换基(5，6，4，1)需要16次加减法和4次位移；The calculation formula is exactly the same as the 4x4 matrix multiplication in the forward transformation, and the algorithm is the same, except that the input and output data vectors are exchanged. The amount of calculation is the same. For the transformation base (5, 6, 4, 1), 16 additions and subtractions and 4 displacements are required;

对于变换基(4，5，3，1)需要12次加减法和4次位移。For the transformation base (4, 5, 3, 1), 12 additions and subtractions and 4 shifts are required.

(4)x0＝a0+b0；x1＝a1+b1；x2＝a2+b2；x3＝a3+b3；(4) x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

其中“＜＜”表示向左位移运算，其优先级高于加减法，“a＜＜b”表示a向左位移b位，Among them, "<<" means leftward shift operation, and its priority is higher than that of addition and subtraction, "a<<b" means that a is shifted to the left by b bits,

不同变换基公共部分计算量为：加减法16次，位移2次。The calculation amount of the common part of different transformation bases is: 16 times of addition and subtraction, and 2 times of displacement.

因此对于变换基(5，6，4，1)完成一次x＝P^Ty运算，共用32次加减法和6次位移；变换基(4，5，3，1)共用28次加减法和6次位移。(5，6，4，1)反变换的快速算法如图3所示，(4，5，3，1)反变换的快速算法如图5所示。完成一次8乘8块的整数变换反变换的运算量是上述单元计算量的16倍。Therefore, an x=P ^T y operation is completed for the transformation base (5, 6, 4, 1), sharing 32 additions and subtractions and 6 displacements; the transformation base (4, 5, 3, 1) shares 28 additions and subtractions and 6 displacements. The fast algorithm of (5, 6, 4, 1) inverse transformation is shown in Fig. 3, and the fast algorithm of (4, 5, 3, 1) inverse transformation is shown in Fig. 5 . The amount of calculation for completing an integer transformation and inverse transformation of 8 by 8 blocks is 16 times of the calculation amount of the above unit.

Claims

1. An integer transformation method for video coding. At the coding end, through intra-frame prediction or inter-frame prediction, the prediction residual of the block is obtained and block transformation is performed, and the energy is concentrated into a few coefficients; and then through quantization, scanning , run-length coding and entropy coding, the image data is compressed and written into the coded stream; at the decoding end, the block transformation coefficient of the entropy code is extracted from the code stream, and the prediction residual of the block is restored through inverse quantization and inverse transformation. Combining prediction information to restore block-out video data; it is characterized in that:

(1) The transformation matrix P adopted by the 8 by 8 integer transformation in the video coding is obtained by the following steps:

(1.1) First search for all integer transformation bases that satisfy the orthogonal condition within a certain range. For an 8 by 8 integer transformation matrix P, define the transformation base as (k1, k2, k3, k4),

P P = = (\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ k k 11 & k k 22 & k k 33 & k k 44 & - - k k 44 & - - k k 33 & - - k k 22 & - - k k 11 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 & k k 33 & k k 11 & k k 44 & - - k k 22 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ k k 33 & - - k k 11 & k k 44 & k k 22 & - - k k 22 & - - k k 44 & k k 11 & - - k k 33 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 & k k 11 & - - k k 22 & k k 33 & - - k k 44 \end{matrix})

The value ranges of transformation base coefficients k1, k2, k3, and k4 are k1, k2, k3∈[1, 10], k4∈[1, 4], and all integer orthogonal transformation bases satisfying P· ^PT =Diag are obtained , where Diag is a diagonal matrix;

(1.2) Establish the covariance matrix COV(X _v ) of the input image residual data when the cross-correlation coefficient ρ is 0.75, 0.8, 0.85, 0.9, 0.95,

Let the one-dimensional vector of image residual data with a length of 8 be X _V =[x ₁ , x ₂ ,...x ₈ ], and establish the covariance matrix COV(X _v ) of X _V elements by the first-order Markov model , COV(X _v ) _{(i, j)} = ρ ^|ij| (0≤i, j≤7), where ρ is the cross-correlation coefficient of adjacent elements of X _V , ρ≤1;

(1.3) By transforming the transformation matrix P corresponding to the base, the covariance matrix COV(Y _v ) of the transformation domain is obtained,

The transformation matrix P corresponding to the transformation base (k1, k2, k3, k4) is normalized, that is, each row element of P is divided by the length of the row vector to obtain an orthogonal matrix P _u , and an orthogonal transformation Y _V is performed on X _V ＝P _u X _V , the covariance matrix of Y _V is:

COV COV (({Y Y}_{v v})) = = {P P}_{u u} \cdot \cdot COV COV (({X x}_{v v})) \cdot &Center Dot; {P P}_{u u}^{T T}

(1.4) Calculate the energy concentration rate η _E value and decorrelation efficiency η _C value when the cross-correlation coefficient ρ gets 0.75, 0.8, 0.85, 0.9, 0.95 by (2), (3) calculation,

Define the energy concentration ratio η _E as:

{η η}_{E E.} = = \frac{11}{\sqrt[88]{{Π Π}_{i i = = 11}^{88} COV COV {(({Y Y}_{v v}))}_{((i i,, i i))}}}

Decorrelation efficiency _ηc is:

{η η}_{c c} = = 11 - - \frac{\underset{j j &NotEqual; &NotEqual; k k}{Σ Σ} | | COV COV {(({Y Y}_{v v}))}_{((j j,, k k))} | |}{\underset{j j &NotEqual; &NotEqual; k k}{Σ Σ} | | {COV COV (({X x}_{v v}))}_{((j j,, k k))} | |}

(1.5) Calculate the normalized results of the energy concentration rate η _E value and decorrelation efficiency η _C of each transformation base under the specified cross-correlation coefficient ρ, under the same ρ, the energy concentration rate η _E of the i-th transformation base The normalized result is:

{Eval Eval}_{E E. ((i i))} = = \frac{{η η}_{E E. ((i i))} - - Min Min (({η η}_{E E. ((j j))}))}{Max Max (({η η}_{E E. ((j j))})) - - Min Min (({η η}_{E E. ((j j))}))}

The normalized result of the i-th transformation base decorrelation efficiency η _C is:

{Eval Eval}_{c c ((i i))} = = \frac{{η η}_{c c ((i i))} - - Min Min (({η η}_{c c ((j j))}))}{Max Max (({η η}_{c c ((j j))})) - - Min Min (({η η}_{c c ((j j))}))}

(1.6) By weighted summation, the comprehensive evaluation results Eval _E , , Eval _C of the energy concentration rate η _E value and decorrelation efficiency η _C of each group base under each cross-correlation coefficient ρ are obtained, and the weights corresponding to 5 points ρ are respectively 1/15, 2/15, 3/15, 4/15, 5/15;

(1.7) By weighting and summing the two indicators Eval _C and Eval _E , the comprehensive evaluation value Eval of the transformation base performance is obtained, and the corresponding weights of Evak _C and Eval _E are 0.4 and 0.6 respectively;

(1.8) selecting a transformation base according to the comprehensive evaluation value, thereby obtaining the integer transformation matrix;

(2) Forward transformation, an integer transformation is done to the image residual data block of 8 by 8, in the form of Y=PXP ^T , the basic unit of transformation is an 8-point one-dimensional transformation in the form of y=Px, where x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , the calculation process is as follows:

(2.1) a0=x0-x7, a1=x1-x6, a2=x2-x5, a3=x3-x4, a4=x0+x7, a5=x1+x6, a6=x2+x5, a7=x3+x4 ;

(2.2) b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

(2.3) y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

(2.4) Complete the calculation steps corresponding to the following formula:

(\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}),,

(3) Inverse transformation:

Let the basic unit of one-dimensional transformation be x=P ^T y, wherein y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T . One-dimensional inverse transformation is:

(3.1) m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

(3.2) b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

(3.3) Calculate the 4 by 4 matrix multiplication of the following formula:

(\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix})

The calculation process is exactly the same as the 4 by 4 matrix multiplication of the forward transformation, except that the input and output data vectors are exchanged;

(3.4) x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

x7=-a0+b0; x6=-a1+b1; x5=-a2+b2; x4=-a3+b3;

Among them, "<<" represents a leftward shift operation, and its priority is higher than that of addition and subtraction.

2. the integer transformation method of video coding as claimed in claim 1 is characterized in that, after the step (1.7) that obtains transformation matrix P obtains the comprehensive evaluation value Eval of transformation base performance, increase to transformation base (k1, k2 , k3, k4) computational complexity evaluation steps: first select the transformation base with a higher comprehensive evaluation value Eval; if the Eval gap is less than 0.02, give priority to computational complexity in applications with high real-time requirements. Transform basis with few subtractions and shifts.

3. The integer transformation method of video coding as claimed in claim 1 or 2, is characterized in that:

(3.1) The transformation matrix P adopted by 8 by 8 integer transformation in video coding is as follows:

P P = = (\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 55 & 66 & 44 & 11 & - - 11 & - - 44 & - - 66 & - - 55 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ 66 & - - 11 & - - 55 & - - 44 & 44 & 55 & 11 & - - 66 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ 44 & - - 55 & 11 & 66 & - - 66 & - - 11 & 55 & - - 44 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ 11 & - - 44 & 66 & - - 55 & 55 & - - 66 & 44 & - - 11 \end{matrix})

The corresponding integer transformation base is (5, 6, 4, 1);

(3.2) Forward transformation, the image residual data block of 8 is multiplied by 8 is done integer transformation, and the basic unit of transformation is 8 points one-dimensional transformation such as y= ^Px , wherein x=[x0, x1, x2, x3, x4, x5, x6, x7} ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , the calculation process is as follows:

A. a0=x0-x7, a1=x1-x6, a2=x2-x5, a3=x3-x4, a4=x0+x7, a5=x1+x6, a6=x2+x5, a7=x3+x4;

B.b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

C.y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

Then complete the calculation steps equivalent to the following formula:

(\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}),,

D.c0=a0<<2+a0+a3; c1=a2-a1-a1<<2; c2=a1+a2+a2<<2; c3=a3<<2+a3-a0;

E.y1=c0-c1+c2; y3=c0-c2-c3; y5=c0+c1+c3; y7=c1+c2-c3;

(3.3) Inverse transformation:

Let the basic unit of one-dimensional transformation be x=P ^T y, where y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T ,

x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T . One-dimensional inverse transformation is:

A.m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

B.b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

C. Compute the 4 by 4 matrix multiplication of:

(\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix})

D. x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

x7=-a0+b0; x6=-a1+b1; x5=-a2+b2; x4=-a3+b3;

4. The integer transformation method of video coding as claimed in claim 1 or 2, is characterized in that:

(4.1) The transformation matrix P used in the 8 by 8 integer transformation in video coding is as follows:

(\begin{matrix} 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 44 & 55 & 33 & 11 & - - 11 & - - 33 & - - 55 & - - 44 \\ 22 & 11 & - - 11 & - - 22 & - - 22 & - - 11 & 11 & 22 \\ 55 & - - 11 & - - 44 & - - 33 & 33 & 44 & 11 & - - 55 \\ 11 & - - 11 & - - 11 & 11 & 11 & - - 11 & - - 11 & 11 \\ 33 & - - 44 & 11 & 55 & - - 55 & - - 11 & 44 & - - 33 \\ 11 & - - 22 & 22 & - - 11 & - - 11 & 22 & - - 22 & 11 \\ 11 & - - 33 & 55 & - - 44 & 44 & - - 55 & 33 & - - 11 \end{matrix})

The corresponding integer transformation base is (4, 5, 3, 1);

(4.2) Forward transformation, an integer transformation is done to the image residual data block of 8 by 8, in the form of Y=PXP ^T , the basic unit of transformation is an 8-point one-dimensional transformation in the form of y=Px, where x=[x0, x1, x2, x3, x4, x5, x6, x7] ^T , the output y=[y0, y1, y2, y3, y4, y5, y6, y7] ^T , the calculation process is as follows:

B.b0=a4+a7, b1=a5+a6, b2=a4-a7, b3=a5-a6;

C.y0=b0+b1, y4=b0-b1, y2=b2<<1+b3, y6=b2-b3<<1;

Then complete the calculation steps equivalent to the following formula:

(\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}),,

D.c0=a0<<2+a3; c1=a2-a1<<2; c2=a1+a2<<2; c3=a3<<2-a0;

E.y1=c0-c1+c2; y3=c0-c2-c3; y5=c0+c1+c3; y7=c1+c2-c3;

(4.3) Inverse transformation:

A.m0=y0+y4; m1=y0-y4; m2=y2<<1+y6; m3=y2-y6<<1;

B.b0=m0+m2; b1=m1+m3; b2=m1-m3; b3=m0-m2;

C. Compute the 4 by 4 matrix multiplication of:

(\begin{matrix} a a 00 \\ a a 11 \\ a a 22 \\ a a 33 \end{matrix}) = = (\begin{matrix} k k 11 & k k 22 & k k 33 & k k 44 \\ k k 22 & - - k k 44 & - - k k 11 & - - k k 33 \\ k k 33 & - - k k 11 & k k 44 & k k 22 \\ k k 44 & - - k k 33 & k k 22 & - - k k 11 \end{matrix}) (\begin{matrix} y the y 11 \\ y the y 33 \\ y the y 55 \\ y the y 77 \end{matrix})

The calculation process of the fast algorithm is exactly the same as the 4 by 4 matrix multiplication of the forward transformation, except that the input and output data vectors are exchanged.

D. x0=a0+b0; x1=a1+b1; x2=a2+b2; x3=a3+b3;

x7=-a0+b0; x6=-a1+b1; x5=-a2+b2; x4=-a3+b3;