H.264算法的优化策略

文章来源： http://www.tichinese.com/Article/Video/200909/2150.html 编辑：小乙哥

1 代码优化的主要方法

通过代码移植能够获得在DSP上初步运行的代码，但是它由于没有考虑到DSP自身的硬件特点，不适合DSP强大的并行处理能力，因此执行效率低下，不能满足我们的实时要求，需要对其进行进一步优化。

对DSP代码进行优化的手段有以下三个层次，分别是：项目级(Project)优化，算法级(algorithm)优化，指令级(instruction)优化。下面对这三种优化手段分别进行介绍。

1)项目级优化

项目级优化，是对项目的整体优化，主要手段有以下几点：
首先是在对整个项目进行编译链接生成DSP代码时，合理选择配置编译器选项，并针对这些参数选择，对程序进行调整和修正。其中进行的工作有：

• 项目编译时，通过-o3选项来调用最高级别的软件流水线优化，通过-mw选项来调用软件流水线循环反馈，从而增大软件编译成DSP代码的并行性。
• 项目编译时，用-pm，-o3和-mt选项来改善循环，多重循环，庞大循环体循环的性能。
• 只读变量声明成const型，循环计数器定义为int型，从而加大DSP代码的并行性。

其次对程序结构进行调整，对不适合DSP执行的语句进行改写，以提高代码的并行性。例如，DSP处理器并行性很高，能够对代码进行流水线处理，但是原始代码存在大量条件判断语句，会对流水线造成中断，不利于代码的并行处理，因此，可以采用判断提前，去除不必要的判断等方式减少判断语句对流水线的中断。

2)算法级优化

算法级优化，就是利用H.264的自身特点，采用一些快速算法，在不影响编码质量的前提下，提高编码器速度，从而在速度和质量上达到一个较好的平衡。

3)指令级优化

上述方法无法达到要求时，就要进行指令级优化。C64x系列DSP有丰富的具有高度并行性处理能力的指令。下面介绍一些C64x系列DSP媒体处理相关指令。

• ADD4：加法指令，一次执行4对8位数的加法。一个寄存器有32位，可以存放4个8位数据。计算中，两个源寄存器中的四组对应8位数据 分别相加，结果存放在目标寄存器中。
• AVGU4：一次执行4对8位无符号数据求平均运算。计算中，两个源寄存器中的4组8位无符号型紧缩字求平均，结果以4个8位紧缩字的 形式存放在目标寄存器中。
• DOTPU4：一次执行4对8位无符号数据点乘运算。计算中，两个源寄存器中的4组8位无符号型紧缩字对应相乘，乘积相加，所得结果存放 在32位寄存器中
• SUBABS4：一次执行4对8位无符号数据求差绝对值运算。计算中，两个源寄存器中的4组8位无符号型紧缩字对应相减，差值求绝对值，所得结果以4个8位紧缩字的形式存放在目标寄存器中。
• LDB/LDH/LDW/LDDW：将8位，16位，32位或64位数据读入目标寄存器中，所读取的数据在内存中是地址align(32位对齐)的数据。
• LDNW/LDNDW：将一个32位或64位的非对齐数据读入目标寄存器中。
• STB/STH/STW/STDW：将8位，16位，32位或64位数据写入内存中，所写入的数据在内村中是地址align(32位对齐)的数据。
• STNW/STNDW：将一个32位或64位的非对齐数据写入内存中。

除了这些高并行度的指令，TI还提供了丰富的算法库[37]，如Image/Video Processing Library图像/视频处理库(IMGLib)，Digital signal processor Library数字信号处理库(DSPLib)等。这些算法库中的函数都是已经充分优化过的算法模块，而且大都提供对应的C、线性汇编和汇编源代码，并有文档进行API介绍。所以要充分利用。

2 算法关键模块的优化

对模块的优化分三步进行。先认真分析代码，并进行相应的调整，例如尽量减少有判断跳转的代码，特别是在for循环中，因为判断跳转会打断软件流水。可以用查表或者用_cmpgtu4、_cmpeq4等intrinsic来代替比较判断指令，从而巧妙地替代判断跳转语句。同时还可以采用TI的CCS中所提供的#pragma，为编译器提供尽量多的信息。这些信息包括for循环的次数信息、数据对齐信息等。如果经过这部分优化后还无法满足系统要求，则对这部分模块使用线性汇编来实现。

2.1 整数变换和量化

整数变换和反变换的运算步骤见下表：

图1 DCT与IDCT的运算步骤

整数运算和反变换的次数极多，比如，在D1格式下，4?4DCT等要做21600次，如果算上其他大小宏块的这些变换，时间消耗还是很多的，所以仍然有优化的必要。下面以整数变换为例介绍如何用线性汇编对C语言代码进行优化：

1)预测残差的输入

DCT和IDCT优化的关键是在数据的读和写上。读写指令是和存储器操作相关的，所以要尽量减少其操作的次数。优化时可以用LDNW（无边界调整字（四字节）读取）和STNW（无边界调整字（四字节）存储）来代替单字节读取和存储，然后在寄存器内部再对数据进行打包处理，这样可以大大提高速度。读入方法如下：

LDNDW *A4, a1:a0 ；第一行数据

LDNDW *+A4(8), a3:a2 ；第二行数据

LDNDW *+A4(16), b3:b2；第三行数据

LDNDW *+A4(24), b1:b0；第四行数据

寄存器A4是系统指定用来保存函数返回值的。8字节的数据的读入要保存到寄存器对中。

2)行变换的实现

C64x里面有多种加法指令，寄存器内容可作为32位数据相加，也可作为两个16位数据相加，也可以作为四个8位数据相加。对应于上面的数据输入方法，我们采用16位相加，并使用.S功能单元。实现方法如下：

加法指令

ADD2 a0, b0: r_00 ；a + d

ADD2 a1, b1: r_01 ；

ADD2 a2, b2: r_10 ；b + c

ADD2 a3, b3: r_11 ；

减法指令

SUB2 a2, b2: r _20 ； b - c

SUB2 a3, b3: r_21 ；

SUB2 a0, b0: r_30 ； a - d

SUB2 a1, b1: r_31 ；

另外，因为在C64x指令中没有对两个16位数据同时左移的指令，同时DM642的乘法指令可 以在一个周期内完成，所以在表1中求B, D时要使用MPY2指令实现向左的移位运算。由于乘法运算后数据的位数要进行扩展，因此MPY2的结果需要放入一个寄存器对，但实际有效数据不会超过16 位，因此完成乘法后我们又把数据两两打包在一个寄存器里，以方便在下面的列变换中进行数据的并行处理。实现方法如下：

MPY2 r_30, r _t，r_tl:r_ t0 ；2*(a-d) r_ t=0x00020002

MPY2 r-31, r_t，r_t3:r_t2

PACK2 r_t 1, r_t0, r_t0

PACK2 r_t3, r_t2, r_t2

3)列变换的实现

行变换后数据以行优先方式存放在4个寄存器对内。所以在进行列变换前要对寄存器内的数据进行转置调整，以方便我们使用上述的数据并行处理指令。

第一列

PACK2 .S1 a2, a0, r_ m00

PACK2 .S2 b0, b2, r_ m01

第二列

PACKH2 .Ll a2, a0, r_ m10

PACKH2 .L2 b0, b2, r ml l

第三列

PACK2 .S1 a3，a1，r -m20

PACK2 .S2 b1，b3，r_ m21

第四列

PACKH2 .Ll a3，a1，r -m30

PACKH2 .L2 b1，b3，r_ m31

经过寄存器中数据的转置处理后，我们就可以使用与行变换类似的程序进行列变换的实现。

4)输出变换结果

列变换的结果即为整数变换的结果，但是输出之前必须进行第二次转置处理，使得输出数据仍然为行优先方式存储。

STNDW r_mOut0l:r mOut00, *A4

STNDW r_mOut1l:r mOut10, *A4(8)

STNDW r_mOut2l:r mOut20, *A4(16)

STNDW r_mOut3l:r mOut30, *A4(24)

5)检查生成的汇编代码并对线性汇编代码进行相应的调整，以提高效率。如，避免使用A16~A31和B16~B31寄存器，因为这两组寄存器需要被保护，如果被使用，编译器会花额外的时间对这些寄存器进行保护操作，这会打断流水，降低效率。

线性汇编代码中用“.cproc” 和“.endproc”命令限定了需要优化器优化的代码段，“.reg”命令允许使用将要存入寄存器的数值描述名字，也就是为寄存器设定了一个标识符。寄存器A4是系统指定用来保存函数返回值的。

量化（DCT）和反量化（IDCT）与整数变换相比多了if判断，如下所示：

for(i = 0 ; i < 16 ; i ++)

{

if (data[i] > 0)

{

data[i] = (data[i] * quant[mf_index][i] ) >> qbits;

}

else

{

data[i] = -(-(data[i] * quant[mf_index][i]) >> qbits);

}

}

而判断指令会打断软件流水，所以应该避免使用。观察代码可知，进行移位操作的都是正数，所以优化时可以对绝对值进行操作，而把符号放在另外的存储器中，移位计算后再将符号加上去。

比较线性汇编优化前后的性能，我们可以发现效果相当明显。

图2 优化前后比较

DCT和量化实际上是两个相关联的部分，总是成对出现，我们可以把DCT和量化一起完成，这样数据可以在寄存器中完成运算，节省了数据存储和读取时间。

2.2 熵编码和解码

2.2.1 查表方法的改进

CAVLC编码按如下步骤进行：

1．编码非零系数的个数（TotalCoeffs）和TrailingOnes的个数（Coeff_token）

通过查表进行，表有5个，定义在结构h264_coeff_token[5][17*4]中，选择码表的依据是当前块上面和左面块的非零系数个数（N0和N1）。由这两个值计算一个参数N来查表。这就是所谓的基于上下文自适应（context adaptive）。

2．对每个TrailingOnes的符号进行编码

对于每个TrailingOnes都要用一个比特来表示它的符号 (0代表正，1代表负)。符号的编码是逆序进行的，即从最高频的TrailingOnes开始编码。

3．对除TrailingOnes之外的非零系数的level值进行编码

当前块中每个余下的非零系数的level值 (符号和绝对值) 都将按照逆序进行编码，即从最高频的系数开始到DC系数结束。编码每个level所用的查找表是依据先前己编码系数的level的绝对值来决定的(上下文自适应)。按原来的做法，此处将查7个表Level_VLC0到Level_VLC6。Level_VLC0适合编码较小的绝对值；Level_VLC1 适合编码稍大的绝对值，依此类推。现在采用一种新的查表方式，将非零系数的幅值（Levels）分成两部分：前缀（level_prefix）和后缀（leve_suffix）。前缀和后缀的求法和一个变量suffixLength有关，如下公式：

变量suffixLength是基于上下文模式自适应更新的，它的更新与当前的 suffixLength的值以及已经解码好的非零系数的值（Level）有关。这样可通过更新suffixLength的值将各种非零系数的前缀都控制在一个较小的范围内，这样既有利于码表的构建又有利于提高查表的速度，更新后的算法仅需要一个level_prefix的码表，码表如下。

图3 level_prefix码表

文章来源： http://www.tichinese.com/Article/Video/200909/2150.html 编辑：小乙哥
level_suffix的编码只需先按照公式4.1计算出数值，然后根据suffixLength的值来确定后缀的长度即可，无需另外建立码表。

总体来说，更新的查表方法有以下两个特点：

1) 大的码表分解成若干小码表，缩小了搜索范围。

2) 利用小码表中码字的规律快速确定参数在码表中的位置。

4．对TotalZero进行编码

TotalZero代表DC系数与最高频的非零系数之间零系数的个数。之所以要单独对TotalZero进行编码是因为在系数序列的低频部分往往会含有多个非零系数，而如果编码TotalZero就可以避免去编码系数序列低频部分的一些零游程。

5．对每个run-before进行编码

run-before表示当前非零系数与下一个非零系数之间零系数的个数。 run-before需要按照逆序编码。从高频系数开始，每个非零系数的run-before都要进行编码，但有两个例外：

(1)如果没有余下的零系数需要编码，则没必要再编码任何zero-run( 即之前编码的run-before之和等于TotalZero)。

(2)没有必要对最后一个 (最低频) 非零系数的run-zero进行编码。

至此，完成了CAVLC编码。

在熵解码时，TotalCoeff、TrailingOnes、TotalZeros和 Run_before的值都是直接查表求的，过程比较简单，此处不进行介绍。在解码除拖尾系数之外的非零系数幅值时先从当前解码位置起逐个比特进行检测，直到找到第一个比特“1”为止。此比特之前，经检测为“0”的比特的个数就是前缀值。通过前缀值找到对应的码表，并决定后缀的长度。最后读入后缀值。利用上面公式反向计算就可得到非零系数的幅值。

2.2.2 函数的优化

CAVLC编码前要将4×4的残差块转换成zig-zag排列，如图4所示。

图4 4×4亮度的zig-zag扫描

Zig-zag扫描后，按步骤是先对扫描后数据的进行逆序遍历，求出非零系数和拖尾系数的数目之后再开始编码写码流。

函数调用时，要将PC和一些寄存器压栈保存，函数返回时，则要将这些寄存器出栈返回，增加了一些不必要的操作，因此要对这部分函数进行修改。

C代码中，zig-zag扫描是由一组赋值语句完成的，将顺序排列的16个数的数组转换成 zig-zag顺序排列的数组。编译器将这段代码转化为汇编代码是将16个数读入寄存器后再进行排列后写回的，这时要读写一次寄存器，之后遍历数组求非零系数和拖尾系数时又要读写一次寄存器。我们可以将zig-zag扫描的函数改写成线性汇编代码，将数据读入到寄存器后就进行遍历，另外用寄存器作计数器，记下非零系数和拖尾系数的数目，然后将zig-zag排列的数据和求得的系数一次写回，这样就省掉了一次寄存器的读写，多次累计起来省掉的时间开销还是相当可观的。

CAVLC编码和解码中多次调用写码流函数和读码流函数，由于调用次数很多，可以将这些函数表示成内联函数，优化效果也相当明显。比如，完成100次C代码的写码流函数BitstreamPutBits花费4075个cycle，而表示成内联函数后仅需要2600个cycle。

2.3 帧内预测

2.3.1 帧内4×4 预测模式判别方法的改进

计算4×4 预测模式的过程就是对4×4 块的9 种预测模式进行计算的过程，分别求出各个模式的SAD值，选取SAD 值最小的预测模式为最优预测模式，因此编码器的计算复杂度很高。

参考相关文献可以对判别方法进行如下改进：由于在H.264 中，残差矩阵量化前后的变换系数都是整数，只要4×4 变换前的残差矩阵满足如下条件，其残差系数量化后的值就是全零。

公式1

其中 为残差矩阵对应位置的值，，QE是量化参数矩阵，对于给定的为中的最小值。根据相邻块的预测模式预测当前4×4 块的最可能预测模式为predmode。根据此预测模式取其残差矩阵，对其残差做，并判断是否。如果不等式成立，则当前最可能的预测模式predmode 就是最优预测模式bestmode，结束此4×4 块的预测模式判断。否则，对此4×4 块的其他预测模式进行判断。对其中的一种预测模式计算它的预测残差矩阵，判断不等式是否成立，如果成立，则此预测模式为此前4×4 块的最优预测模式bestmode，结束此4×4 块的预测模式判断。否则对此4×4 块的其他预测模式进行同样处理，直至9 种预测模式都进行了判断，获得一个最优的预测模式。

同时，在改进算法中，对于那些判断残差进行变换量化后结果为全零的4×4 块进行了特别处理。由于这些4×4 块的残差经过变换量化后结果为全零，对它们的残差再进行变换、量化、反量化和反变换就失去了意义，因此可以对这些处理过程进行简化。具体操作为：对这些 4×4块的残差矩阵直接全赋值为零，并对Z 扫描的结果也同样赋值为零，从而省去了变换、量化、反变换和反量化，并且对编码结果和图像的重构结果都不会有影响，能够进一步减少计算复杂度。

2.3.2 亮度预测的并行实现和线性汇编优化

4×4子块亮度预测除在汇编指令级采用超长指令字VLIW并行执行8条指令外，主要采用数据并行、线性汇编优化和使用软件流水进行优化处理。

4×4子块亮度预测时的数据都是0～255，即unsigned char，在DSP中占一个字节：采用寄存器组A、B并行处理4×4子块前两行与后两行两块数据，采用寄存器高低位并行处理两行数据，如图5所示。这样并行处理得到近似为4的加速比。

图5 4×4亮度块预测数据并行

观察4×4子块亮度预测的九种预测模式，我们会发现后6种预测模式16个像素点的预测有很强的相关性，使用软件流水线可以得到较好的效果。以模式3 (左下对角线模式)为例，16个像素点分别由公式2得出。

公式2

线性汇编的编写过程如下：

1．用四字节的读写指令代替单字节的读写指令

利用LDNW指令用两次将ABCD和EFGH读入到两个寄存器中，利用STNW指令分四次将数据存储。

2．重新组装寄存器里的数据

ABCD和EFGH并不是分开的，总是四个一组进行计算。公式4.2中1、2式的操作数是 ABCD，3、4式是CDEF，5、6、7式是EFGH。因而我们不需要将ABCD与EFGH完全拆开存储，只需要将ABCD中的高半字和EFGH中的低半字拆出来存到一个独立的寄存器中。这条指令是PACKHL2。

3．分析运算式规律，选择最简单的运算指令

所有的运算中，都存在一个计算式X+2Y+Z，同时有三个unsigned char型数据参加运算，下面一条C6400系列的汇编指令正好可以用于此处。

DOTPU4 (.M) src1, src2, dst

这条指令求src1和src2中的两个无符号数的4个字节对应的积，再相加，和数送入dst 中。在这里我们可以用src2 = 0x0121分别与ABCD、CDEF和EFGH做DOTPU4运算，可直接得出B+2C+D、D+2E+F和F+2G+H，用src2 = 0x1210分别与ABCD、CDEF和EFGH做DOTPU4运算，可直接得出A+2B+C、C+2D+E和E+2F+G。运算后的结果加2后右移2位即可。

对4×4子块亮度预测的后6种预测模式进行优化后，性能有明显提高，如下表所示（-o3，no –mu允许软件流水的条件下）。

font>

图6 优化性能比较

16×16宏块亮度预测基本上与4×4块亮度预测一致，但对早期终止策略进行了优化处理。

16×16宏块亮度预测按照模式0(垂直预测)→模式1(水平预测) →模式2 (直流预测) →模式3 (平面预测) 编码顺序进行，并在每种预测模式中采用早期终止策略后，流程为[34]：16×16宏块第i列数据预测、第i列数据求残差、计算第i列数据SAD值、判别是否进行下一模式预测 (当SAD值大于16个4×4子块的最优模式下的SAD之和min_cost时)。这样最多会增加了15次判断，有测试中表明83%的宏块在计算了12列数据SAD值才满足判决条件，15%的宏块在计算了16列数据SAD值才满足判决条件，2%的宏块在计算了8列数据SAD值就满足判决条件。故实际编程中仅在计算了12列数据SAD值后增加判决，仅增加一次判决，16×16宏块编码效率提高20.04%。流程见图7所示。

图7 16×16宏块亮度预测流程

2.4 运动估计

在视频编码中，运动估计和补偿起着最为关键的作用，通常占一个压缩编码方案总计算量的60%～ 80%。块匹配法是目前最为广泛应用的运动估计方法。在H. 264 中，运动补偿部分与之前的标准有很大的不同。它支持更大范围的运动补偿块，以达到高精度匹配，充分消除时域冗余度，最大程度减小预测误差。而这是以极高的运算量和复杂度为代价的，仅以整像素搜索为例，H. 264 共允许多种大小的补偿块 (最小可到4×4)，对一个16×16 的宏块采用某一种分块方式进行全搜索，搜索范围为16，则求匹配差值的计算次数为：

(2 × 16 + 1) × (2 × 16 + 1) × 16 × 16= 2. 79×105

这样大的计算量显然会给实时视频处理带来巨大困难，所以要寻找快速的搜索算法和判决策略。

H. 264 标准规定对16×16 的宏块可以采用16×16、16×8、8×16、8×8 的分块方式，而对8×8 的分块又可进一步分成8×8、8×4、4×8、4×4 的小块。每个独立的分块分别进行运动搜索，这样的处理固然可以达到最好的匹配效果，但要求巨大的运算量。16×8 和8×16 分块方式的运算量各自与16×16 分块方式的运算量大致相当，而8×8 分块方式由于其每一个小块都要独立作4 种方式的搜索，其总的运算量大致相当于16×16 的4倍。而通过对H.264标准测试序列测试的结果来看，对Foreman 这类运动剧烈的序列，8×8 分块方式为最优模式的宏块数只占总宏块数的不到10% ，对Akiyo这类平缓的序列，8×8 方式的宏块百分比更是在2%，因此在优化中可以放弃8×8这种分块模式。

运动估计的实现采用分步计算加提前终止的方法。其步骤如下：

1．搜索的上下文信息都存放在一个结构体H264_search_context_t 中，context里存储有推荐的运动矢量（通常有5个：标准预测值、上、右上三个块运动向量和0向量），首先尝试context->vec[0] 标准向量，计算RD_cost（这里算得sad），若RD_cost < th0＝256，则设置最优vec_best为vec[0]，并返回sad值。

2．然后尝试运动向量的其他预测值，找到最小的SAD，若该SAD小于刚才找到的sad，则设置context->vec_best = context->vec[best]，如果该SAD < th0，则返回SAD。

3．若上面都没有找到小于阈值的SAD，则调用small_diamond_search，进行小菱形搜索，实际就是搜索上下左右四个点，直到当前点为5个点中SAD的最小点。如下图所示。

图8 小菱形搜索

H．264解码器中CAVLC码表查找算法的分析与优化

0 引言
近年来，随着信息技术飞速发展和互联网的日益普及，尤其是以视频为信息主要来源的多媒体领域越来越受到人们的关注。H．264是ITU-T的视频编码专家组(VCEG)和ISO／IEC的活动图像编码专家组(MPEG)的联合视频组(Joint Video Tearn，JVT)开发的一个新的数字视频编码标准，它既是ITU-T的H．264，又是ISO／IEC的MPEG-4的一部分。H．264和以前的标准一样，也是DPCM加变换编码的混合编码模式。H．264标准可分为三档：基本档次(其简单版本，应用面广)；主要档次(采用了多项提高图像质量和增加压缩比的技术措施，可用于SDTV、HDTV和DVD等)；扩展档次(可用于各种网络的视频流传输)。
H．264／AVC的编解码框架的基本结构与早期的编码标准(H．263、MPEG4等)相似，都是由运动估计、变换、量化、熵编码、环路去块效应滤波器等功能单元组成的。H．264视频编码框架的主要变化包括：引入了环内去块效应滤波器，去块效应处理后的宏块被保存在内存中用于对后续宏块的预侧；采用了多参考帧运动估计，需要在内存中保留多个参考视频帧；引入了帧内预测机制，可以通过同一帧内的宏块进行预测；采用了新的整型变换方式，取代了以前的离散余弦变换(DCT)；H．264与以前视频标准在运动估计的模式上也有了较大的变化，H．264支持7种模式的可变块运动估计。此外，在熵编码中还引入了上下文自适应的变长编码(CAVLC)和二进制算术编码(CABAC)。
在熵编码方面，H．264使用了CABAC和CAVLC两种不同的编码方式。CABAC熵编码是一种基于区间划分的算术编码方式。这种编码方式的效率很高，接近信息熵值，但算法相对复杂，编解码速度较慢。CAVLC是一种可变长编码，它根据已编码语法元素的情况动态调整编码中使用的码表，在编码过程中有些语法元素是组合编码的，当对这些元素进行查找时就会耗费很长的时间。因此对CAVLC的优化显得格外重要。

1 原码表查找算法
原码表的存储结构为二维表结构。存储的内容为码字，二维坐标分别代表解码后的两个语法元素。对于二维表结构。若通过坐标查找内容是很容易的；而通过内容查找坐标，就需要对整个表进行遍历。JM中的码表查找算法就是通过遍历整个码表实现的，步骤如下：
(1)取码表的中的一个码字；
(2)根据码字长度从码流中取出相应长度的bit；
(3)比较此码字和bit串，若相同则查找成功，否则若码表中还有码字，回步骤(1)，否则查找失败。

2 算法的优化分析
2．1 基于前缀零分组子表搜索算法
基于上下文自适应的变长编码的解码算法需要不断的读取码流，判断，直到在码表中找到该码字，如此反复，直至解码整个块。由此可见该过程的时间空间复杂度都是相当高的。由于变长码为霍夫曼前缀码，所以可以根据码表的特性，按照码字长度将原来的一个码表，按照码字长度对原码表进行分割，以Coeff_token码表为例，原码表如表1所示，表中NC=-1。

在参考模型中，搜索码表算法过程如下：
(1)从最短码长开始，读出该长度二进制数据流对应的码字；
(2)遍历码表，如找到该码字进行步骤(4)，否则进入(3)；
(3)码字长度加1，重定位指针位置，重复步骤(2)；
(4)读取该码字对应值，更新指针位置。
从上面过程中不难发现，码字长度的不确定性使得在读取字节流时只能一次次的试探，导致了效率的下降。如果可以将变长码的读取采取固定的策略，一次读取固定的长度，之后再做判断，再读取一定长度，这样将判断的次数也固定，从理论上可以降低不断搜索和重定位指针带来的时间和空间复杂性。利用可以利用码表中码字前缀零数目的不同，将表1拆分为两个子表，如表2，表3所示NC为-1。

改进后的码表搜索算法如下：
(1)读取最大码字长度的二进制流；
(2)根据不同的前缀零位数、右移位、判零以确定码字所在子表；
(3)直接根据码值读取对应值，更新指针位置。
新的搜索过程不但避免了不确定性，而且无需遍历码表，这样可以在一定程度上提高变长解码的效率。

按照改进的算法步骤，解码时，首先从字节流中读取8位码字，由于前缀零个数分为大于3和小于3的两种情形，所以右移5位，若为零，则查找表2，否则查找表 1，根据码值直接解码出±1个数，非零系数数目。此外在设计代码时，还可利用二叉搜索树的特性，设计搜索过程，提高解码效率.

2．2 二叉树一子表混合法
拆分成子表后建立的数组中存在冗余现象。如当0≤N<2且Pre-Zeros<6时，一共有13个码字。为了保留原先的查表方式以TC和 Tls为矩阵下标的特点，必须要用4×7矩阵，多余位置零。由于实际搜索的对象是矩阵，怎么确定Pre-Zeros值，以保证在分块数一定的情况下，使用的矩阵较小，成为提高搜索效率的关键。从表中可以看到，对不同的N值对应的列，子表之间的Pre-zeros的分界点选取了不同的阈值。按照表2中的分块方法，矩阵的平均大小为4×6．5。相比JM中使用一个4×17矩阵，搜索效率理论上可以提高(17-6．5)／6．5=1．615倍(假设每张子表的使用概率相同)。以0≤N<2的一张VLC表为例，共分成4张子表。从查找一个码字的比较次数来看。

可知，子表法查找比较次数的理论最小值为此时要求n=s2。如果在第一个步骤(确定子表)中改为采用二分法，则这种情况下就可以对以上码表中前缀连零再细化，将相同连零个数的码字放在一起，增加子表数而减少子表中的码字结点数，可以进一步提高查找效率。
从以上分析可见，二叉树的查找效率是最高的。因此可以将二叉树应用到子表法中，对每一张子表分别建树。对于二叉树来说，查找时间与树的深度有关。观察子表中的码字，发现它们都有不同长度的连零作为前缀，如果直接建树将导致树的不平衡并增加了树的深度。为了解决这个问题，可以考虑在同一张子表中为每个码字去除相同个数的连零前缀，然后建立二叉树。在解码时，先忽略这些连零个数，再进行树的查找。在最理想情况下，这种查找方法的一次查找的平均比较次数为：

对第一张VLC表采用二叉树一子表法的最大比较次数：

几种算法的对比与复杂度分析如表4所示。

空间复杂度也是需要考虑的问题。JM参考实现中为Tls和TC的联合码表建立了2个3×4×17的三维数组共需要408 B的存储空间。二叉树法经过统计，一棵树共有124个结点，其中叶结点62个，其余62个结点为根结点或枝结点。建3棵二叉树所需要的空间为 (62×4+62×2)×3=1 116 B。子表法将码表分成12张子表，每张子表用2个二维数组表示，而数组的平均大小为4×6．5，则共要4×6．5×12×2=624 B。

3 结 语
H．264是现在视频编解码领域研究的热点也是未来发展的方向，它将代替MPEG2成为主流的信源压缩标准。H．264应用领域非常广泛。将H．264的编解码速度尽可能的提高，可以使其在更多的领域中应用，如数字电视，消费电子类产品，网络通信，可视电话等现在热门领域。在此专门对于CAVLC码表查找给出了改进方案，通过这三种改进方案，避免了对整个码表的查找，对码表的查找在效率上有了很大提高。具有明显的实用意义.

文章来源： http://www.tichinese.com/Article/Video/200909/2150.html 编辑：小乙哥

1 代码优化的主要方法

通过代码移植能够获得在DSP上初步运行的代码，但是它由于没有考虑到DSP自身的硬件特点，不适合DSP强大的并行处理能力，因此执行效率低下，不能满足我们的实时要求，需要对其进行进一步优化。

对DSP代码进行优化的手段有以下三个层次，分别是：项目级(Project)优化，算法级(algorithm)优化，指令级(instruction)优化。下面对这三种优化手段分别进行介绍。

1)项目级优化

项目级优化，是对项目的整体优化，主要手段有以下几点：
首先是在对整个项目进行编译链接生成DSP代码时，合理选择配置编译器选项，并针对这些参数选择，对程序进行调整和修正。其中进行的工作有：

• 项目编译时，通过-o3选项来调用最高级别的软件流水线优化，通过-mw选项来调用软件流水线循环反馈，从而增大软件编译成DSP代码的并行性。
• 项目编译时，用-pm，-o3和-mt选项来改善循环，多重循环，庞大循环体循环的性能。
• 只读变量声明成const型，循环计数器定义为int型，从而加大DSP代码的并行性。

其次对程序结构进行调整，对不适合DSP执行的语句进行改写，以提高代码的并行性。例如，DSP处理器并行性很高，能够对代码进行流水线处理，但是原始代码存在大量条件判断语句，会对流水线造成中断，不利于代码的并行处理，因此，可以采用判断提前，去除不必要的判断等方式减少判断语句对流水线的中断。

2)算法级优化

算法级优化，就是利用H.264的自身特点，采用一些快速算法，在不影响编码质量的前提下，提高编码器速度，从而在速度和质量上达到一个较好的平衡。

3)指令级优化

上述方法无法达到要求时，就要进行指令级优化。C64x系列DSP有丰富的具有高度并行性处理能力的指令。下面介绍一些C64x系列DSP媒体处理相关指令。

• ADD4：加法指令，一次执行4对8位数的加法。一个寄存器有32位，可以存放4个8位数据。计算中，两个源寄存器中的四组对应8位数据 分别相加，结果存放在目标寄存器中。
• AVGU4：一次执行4对8位无符号数据求平均运算。计算中，两个源寄存器中的4组8位无符号型紧缩字求平均，结果以4个8位紧缩字的 形式存放在目标寄存器中。
• DOTPU4：一次执行4对8位无符号数据点乘运算。计算中，两个源寄存器中的4组8位无符号型紧缩字对应相乘，乘积相加，所得结果存放 在32位寄存器中
• SUBABS4：一次执行4对8位无符号数据求差绝对值运算。计算中，两个源寄存器中的4组8位无符号型紧缩字对应相减，差值求绝对值，所得结果以4个8位紧缩字的形式存放在目标寄存器中。
• LDB/LDH/LDW/LDDW：将8位，16位，32位或64位数据读入目标寄存器中，所读取的数据在内存中是地址align(32位对齐)的数据。
• LDNW/LDNDW：将一个32位或64位的非对齐数据读入目标寄存器中。
• STB/STH/STW/STDW：将8位，16位，32位或64位数据写入内存中，所写入的数据在内村中是地址align(32位对齐)的数据。
• STNW/STNDW：将一个32位或64位的非对齐数据写入内存中。

除了这些高并行度的指令，TI还提供了丰富的算法库[37]，如Image/Video Processing Library图像/视频处理库(IMGLib)，Digital signal processor Library数字信号处理库(DSPLib)等。这些算法库中的函数都是已经充分优化过的算法模块，而且大都提供对应的C、线性汇编和汇编源代码，并有文档进行API介绍。所以要充分利用。

2 算法关键模块的优化

对模块的优化分三步进行。先认真分析代码，并进行相应的调整，例如尽量减少有判断跳转的代码，特别是在for循环中，因为判断跳转会打断软件流水。可以用查表或者用_cmpgtu4、_cmpeq4等intrinsic来代替比较判断指令，从而巧妙地替代判断跳转语句。同时还可以采用TI的CCS中所提供的#pragma，为编译器提供尽量多的信息。这些信息包括for循环的次数信息、数据对齐信息等。如果经过这部分优化后还无法满足系统要求，则对这部分模块使用线性汇编来实现。

2.1 整数变换和量化

整数变换和反变换的运算步骤见下表：

图1 DCT与IDCT的运算步骤

整数运算和反变换的次数极多，比如，在D1格式下，4?4DCT等要做21600次，如果算上其他大小宏块的这些变换，时间消耗还是很多的，所以仍然有优化的必要。下面以整数变换为例介绍如何用线性汇编对C语言代码进行优化：

1)预测残差的输入

DCT和IDCT优化的关键是在数据的读和写上。读写指令是和存储器操作相关的，所以要尽量减少其操作的次数。优化时可以用LDNW（无边界调整字（四字节）读取）和STNW（无边界调整字（四字节）存储）来代替单字节读取和存储，然后在寄存器内部再对数据进行打包处理，这样可以大大提高速度。读入方法如下：

LDNDW *A4, a1:a0 ；第一行数据

LDNDW *+A4(8), a3:a2 ；第二行数据

LDNDW *+A4(16), b3:b2；第三行数据

LDNDW *+A4(24), b1:b0；第四行数据

寄存器A4是系统指定用来保存函数返回值的。8字节的数据的读入要保存到寄存器对中。

2)行变换的实现

C64x里面有多种加法指令，寄存器内容可作为32位数据相加，也可作为两个16位数据相加，也可以作为四个8位数据相加。对应于上面的数据输入方法，我们采用16位相加，并使用.S功能单元。实现方法如下：

加法指令

ADD2 a0, b0: r_00 ；a + d

ADD2 a1, b1: r_01 ；

ADD2 a2, b2: r_10 ；b + c

ADD2 a3, b3: r_11 ；

减法指令

SUB2 a2, b2: r _20 ； b - c

SUB2 a3, b3: r_21 ；

SUB2 a0, b0: r_30 ； a - d

SUB2 a1, b1: r_31 ；

另外，因为在C64x指令中没有对两个16位数据同时左移的指令，同时DM642的乘法指令可 以在一个周期内完成，所以在表1中求B, D时要使用MPY2指令实现向左的移位运算。由于乘法运算后数据的位数要进行扩展，因此MPY2的结果需要放入一个寄存器对，但实际有效数据不会超过16 位，因此完成乘法后我们又把数据两两打包在一个寄存器里，以方便在下面的列变换中进行数据的并行处理。实现方法如下：

MPY2 r_30, r _t，r_tl:r_ t0 ；2*(a-d) r_ t=0x00020002

MPY2 r-31, r_t，r_t3:r_t2

PACK2 r_t 1, r_t0, r_t0

PACK2 r_t3, r_t2, r_t2

3)列变换的实现

行变换后数据以行优先方式存放在4个寄存器对内。所以在进行列变换前要对寄存器内的数据进行转置调整，以方便我们使用上述的数据并行处理指令。

第一列

PACK2 .S1 a2, a0, r_ m00

PACK2 .S2 b0, b2, r_ m01

第二列

PACKH2 .Ll a2, a0, r_ m10

PACKH2 .L2 b0, b2, r ml l

第三列

PACK2 .S1 a3，a1，r -m20

PACK2 .S2 b1，b3，r_ m21

第四列

PACKH2 .Ll a3，a1，r -m30

PACKH2 .L2 b1，b3，r_ m31

经过寄存器中数据的转置处理后，我们就可以使用与行变换类似的程序进行列变换的实现。

4)输出变换结果

列变换的结果即为整数变换的结果，但是输出之前必须进行第二次转置处理，使得输出数据仍然为行优先方式存储。

STNDW r_mOut0l:r mOut00, *A4

STNDW r_mOut1l:r mOut10, *A4(8)

STNDW r_mOut2l:r mOut20, *A4(16)

STNDW r_mOut3l:r mOut30, *A4(24)

5)检查生成的汇编代码并对线性汇编代码进行相应的调整，以提高效率。如，避免使用A16~A31和B16~B31寄存器，因为这两组寄存器需要被保护，如果被使用，编译器会花额外的时间对这些寄存器进行保护操作，这会打断流水，降低效率。

线性汇编代码中用“.cproc” 和“.endproc”命令限定了需要优化器优化的代码段，“.reg”命令允许使用将要存入寄存器的数值描述名字，也就是为寄存器设定了一个标识符。寄存器A4是系统指定用来保存函数返回值的。

量化（DCT）和反量化（IDCT）与整数变换相比多了if判断，如下所示：

for(i = 0 ; i < 16 ; i ++)

{

if (data[i] > 0)

{

data[i] = (data[i] * quant[mf_index][i] ) >> qbits;

}

else

{

data[i] = -(-(data[i] * quant[mf_index][i]) >> qbits);

}

}

而判断指令会打断软件流水，所以应该避免使用。观察代码可知，进行移位操作的都是正数，所以优化时可以对绝对值进行操作，而把符号放在另外的存储器中，移位计算后再将符号加上去。

比较线性汇编优化前后的性能，我们可以发现效果相当明显。

图2 优化前后比较

DCT和量化实际上是两个相关联的部分，总是成对出现，我们可以把DCT和量化一起完成，这样数据可以在寄存器中完成运算，节省了数据存储和读取时间。

2.2 熵编码和解码

2.2.1 查表方法的改进

CAVLC编码按如下步骤进行：

1．编码非零系数的个数（TotalCoeffs）和TrailingOnes的个数（Coeff_token）

通过查表进行，表有5个，定义在结构h264_coeff_token[5][17*4]中，选择码表的依据是当前块上面和左面块的非零系数个数（N0和N1）。由这两个值计算一个参数N来查表。这就是所谓的基于上下文自适应（context adaptive）。

2．对每个TrailingOnes的符号进行编码

对于每个TrailingOnes都要用一个比特来表示它的符号 (0代表正，1代表负)。符号的编码是逆序进行的，即从最高频的TrailingOnes开始编码。

3．对除TrailingOnes之外的非零系数的level值进行编码

当前块中每个余下的非零系数的level值 (符号和绝对值) 都将按照逆序进行编码，即从最高频的系数开始到DC系数结束。编码每个level所用的查找表是依据先前己编码系数的level的绝对值来决定的(上下文自适应)。按原来的做法，此处将查7个表Level_VLC0到Level_VLC6。Level_VLC0适合编码较小的绝对值；Level_VLC1 适合编码稍大的绝对值，依此类推。现在采用一种新的查表方式，将非零系数的幅值（Levels）分成两部分：前缀（level_prefix）和后缀（leve_suffix）。前缀和后缀的求法和一个变量suffixLength有关，如下公式：

变量suffixLength是基于上下文模式自适应更新的，它的更新与当前的 suffixLength的值以及已经解码好的非零系数的值（Level）有关。这样可通过更新suffixLength的值将各种非零系数的前缀都控制在一个较小的范围内，这样既有利于码表的构建又有利于提高查表的速度，更新后的算法仅需要一个level_prefix的码表，码表如下。

图3 level_prefix码表

文章来源： http://www.tichinese.com/Article/Video/200909/2150.html 编辑：小乙哥
level_suffix的编码只需先按照公式4.1计算出数值，然后根据suffixLength的值来确定后缀的长度即可，无需另外建立码表。

总体来说，更新的查表方法有以下两个特点：

1) 大的码表分解成若干小码表，缩小了搜索范围。

2) 利用小码表中码字的规律快速确定参数在码表中的位置。

4．对TotalZero进行编码

TotalZero代表DC系数与最高频的非零系数之间零系数的个数。之所以要单独对TotalZero进行编码是因为在系数序列的低频部分往往会含有多个非零系数，而如果编码TotalZero就可以避免去编码系数序列低频部分的一些零游程。

5．对每个run-before进行编码

run-before表示当前非零系数与下一个非零系数之间零系数的个数。 run-before需要按照逆序编码。从高频系数开始，每个非零系数的run-before都要进行编码，但有两个例外：

(1)如果没有余下的零系数需要编码，则没必要再编码任何zero-run( 即之前编码的run-before之和等于TotalZero)。

(2)没有必要对最后一个 (最低频) 非零系数的run-zero进行编码。

至此，完成了CAVLC编码。

在熵解码时，TotalCoeff、TrailingOnes、TotalZeros和 Run_before的值都是直接查表求的，过程比较简单，此处不进行介绍。在解码除拖尾系数之外的非零系数幅值时先从当前解码位置起逐个比特进行检测，直到找到第一个比特“1”为止。此比特之前，经检测为“0”的比特的个数就是前缀值。通过前缀值找到对应的码表，并决定后缀的长度。最后读入后缀值。利用上面公式反向计算就可得到非零系数的幅值。

2.2.2 函数的优化

CAVLC编码前要将4×4的残差块转换成zig-zag排列，如图4所示。

图4 4×4亮度的zig-zag扫描

Zig-zag扫描后，按步骤是先对扫描后数据的进行逆序遍历，求出非零系数和拖尾系数的数目之后再开始编码写码流。

函数调用时，要将PC和一些寄存器压栈保存，函数返回时，则要将这些寄存器出栈返回，增加了一些不必要的操作，因此要对这部分函数进行修改。

C代码中，zig-zag扫描是由一组赋值语句完成的，将顺序排列的16个数的数组转换成 zig-zag顺序排列的数组。编译器将这段代码转化为汇编代码是将16个数读入寄存器后再进行排列后写回的，这时要读写一次寄存器，之后遍历数组求非零系数和拖尾系数时又要读写一次寄存器。我们可以将zig-zag扫描的函数改写成线性汇编代码，将数据读入到寄存器后就进行遍历，另外用寄存器作计数器，记下非零系数和拖尾系数的数目，然后将zig-zag排列的数据和求得的系数一次写回，这样就省掉了一次寄存器的读写，多次累计起来省掉的时间开销还是相当可观的。

CAVLC编码和解码中多次调用写码流函数和读码流函数，由于调用次数很多，可以将这些函数表示成内联函数，优化效果也相当明显。比如，完成100次C代码的写码流函数BitstreamPutBits花费4075个cycle，而表示成内联函数后仅需要2600个cycle。

2.3 帧内预测

2.3.1 帧内4×4 预测模式判别方法的改进

计算4×4 预测模式的过程就是对4×4 块的9 种预测模式进行计算的过程，分别求出各个模式的SAD值，选取SAD 值最小的预测模式为最优预测模式，因此编码器的计算复杂度很高。

参考相关文献可以对判别方法进行如下改进：由于在H.264 中，残差矩阵量化前后的变换系数都是整数，只要4×4 变换前的残差矩阵满足如下条件，其残差系数量化后的值就是全零。

公式1

其中 为残差矩阵对应位置的值，，QE是量化参数矩阵，对于给定的为中的最小值。根据相邻块的预测模式预测当前4×4 块的最可能预测模式为predmode。根据此预测模式取其残差矩阵，对其残差做，并判断是否。如果不等式成立，则当前最可能的预测模式predmode 就是最优预测模式bestmode，结束此4×4 块的预测模式判断。否则，对此4×4 块的其他预测模式进行判断。对其中的一种预测模式计算它的预测残差矩阵，判断不等式是否成立，如果成立，则此预测模式为此前4×4 块的最优预测模式bestmode，结束此4×4 块的预测模式判断。否则对此4×4 块的其他预测模式进行同样处理，直至9 种预测模式都进行了判断，获得一个最优的预测模式。

同时，在改进算法中，对于那些判断残差进行变换量化后结果为全零的4×4 块进行了特别处理。由于这些4×4 块的残差经过变换量化后结果为全零，对它们的残差再进行变换、量化、反量化和反变换就失去了意义，因此可以对这些处理过程进行简化。具体操作为：对这些 4×4块的残差矩阵直接全赋值为零，并对Z 扫描的结果也同样赋值为零，从而省去了变换、量化、反变换和反量化，并且对编码结果和图像的重构结果都不会有影响，能够进一步减少计算复杂度。

2.3.2 亮度预测的并行实现和线性汇编优化

4×4子块亮度预测除在汇编指令级采用超长指令字VLIW并行执行8条指令外，主要采用数据并行、线性汇编优化和使用软件流水进行优化处理。

4×4子块亮度预测时的数据都是0～255，即unsigned char，在DSP中占一个字节：采用寄存器组A、B并行处理4×4子块前两行与后两行两块数据，采用寄存器高低位并行处理两行数据，如图5所示。这样并行处理得到近似为4的加速比。

图5 4×4亮度块预测数据并行

观察4×4子块亮度预测的九种预测模式，我们会发现后6种预测模式16个像素点的预测有很强的相关性，使用软件流水线可以得到较好的效果。以模式3 (左下对角线模式)为例，16个像素点分别由公式2得出。

公式2

线性汇编的编写过程如下：

1．用四字节的读写指令代替单字节的读写指令

利用LDNW指令用两次将ABCD和EFGH读入到两个寄存器中，利用STNW指令分四次将数据存储。

2．重新组装寄存器里的数据

ABCD和EFGH并不是分开的，总是四个一组进行计算。公式4.2中1、2式的操作数是 ABCD，3、4式是CDEF，5、6、7式是EFGH。因而我们不需要将ABCD与EFGH完全拆开存储，只需要将ABCD中的高半字和EFGH中的低半字拆出来存到一个独立的寄存器中。这条指令是PACKHL2。

3．分析运算式规律，选择最简单的运算指令

所有的运算中，都存在一个计算式X+2Y+Z，同时有三个unsigned char型数据参加运算，下面一条C6400系列的汇编指令正好可以用于此处。

DOTPU4 (.M) src1, src2, dst

这条指令求src1和src2中的两个无符号数的4个字节对应的积，再相加，和数送入dst 中。在这里我们可以用src2 = 0x0121分别与ABCD、CDEF和EFGH做DOTPU4运算，可直接得出B+2C+D、D+2E+F和F+2G+H，用src2 = 0x1210分别与ABCD、CDEF和EFGH做DOTPU4运算，可直接得出A+2B+C、C+2D+E和E+2F+G。运算后的结果加2后右移2位即可。

对4×4子块亮度预测的后6种预测模式进行优化后，性能有明显提高，如下表所示（-o3，no –mu允许软件流水的条件下）。

font>

图6 优化性能比较

16×16宏块亮度预测基本上与4×4块亮度预测一致，但对早期终止策略进行了优化处理。

16×16宏块亮度预测按照模式0(垂直预测)→模式1(水平预测) →模式2 (直流预测) →模式3 (平面预测) 编码顺序进行，并在每种预测模式中采用早期终止策略后，流程为[34]：16×16宏块第i列数据预测、第i列数据求残差、计算第i列数据SAD值、判别是否进行下一模式预测 (当SAD值大于16个4×4子块的最优模式下的SAD之和min_cost时)。这样最多会增加了15次判断，有测试中表明83%的宏块在计算了12列数据SAD值才满足判决条件，15%的宏块在计算了16列数据SAD值才满足判决条件，2%的宏块在计算了8列数据SAD值就满足判决条件。故实际编程中仅在计算了12列数据SAD值后增加判决，仅增加一次判决，16×16宏块编码效率提高20.04%。流程见图7所示。

图7 16×16宏块亮度预测流程

2.4 运动估计

在视频编码中，运动估计和补偿起着最为关键的作用，通常占一个压缩编码方案总计算量的60%～ 80%。块匹配法是目前最为广泛应用的运动估计方法。在H. 264 中，运动补偿部分与之前的标准有很大的不同。它支持更大范围的运动补偿块，以达到高精度匹配，充分消除时域冗余度，最大程度减小预测误差。而这是以极高的运算量和复杂度为代价的，仅以整像素搜索为例，H. 264 共允许多种大小的补偿块 (最小可到4×4)，对一个16×16 的宏块采用某一种分块方式进行全搜索，搜索范围为16，则求匹配差值的计算次数为：

(2 × 16 + 1) × (2 × 16 + 1) × 16 × 16= 2. 79×105

这样大的计算量显然会给实时视频处理带来巨大困难，所以要寻找快速的搜索算法和判决策略。

H. 264 标准规定对16×16 的宏块可以采用16×16、16×8、8×16、8×8 的分块方式，而对8×8 的分块又可进一步分成8×8、8×4、4×8、4×4 的小块。每个独立的分块分别进行运动搜索，这样的处理固然可以达到最好的匹配效果，但要求巨大的运算量。16×8 和8×16 分块方式的运算量各自与16×16 分块方式的运算量大致相当，而8×8 分块方式由于其每一个小块都要独立作4 种方式的搜索，其总的运算量大致相当于16×16 的4倍。而通过对H.264标准测试序列测试的结果来看，对Foreman 这类运动剧烈的序列，8×8 分块方式为最优模式的宏块数只占总宏块数的不到10% ，对Akiyo这类平缓的序列，8×8 方式的宏块百分比更是在2%，因此在优化中可以放弃8×8这种分块模式。

运动估计的实现采用分步计算加提前终止的方法。其步骤如下：

1．搜索的上下文信息都存放在一个结构体H264_search_context_t 中，context里存储有推荐的运动矢量（通常有5个：标准预测值、上、右上三个块运动向量和0向量），首先尝试context->vec[0] 标准向量，计算RD_cost（这里算得sad），若RD_cost < th0＝256，则设置最优vec_best为vec[0]，并返回sad值。

2．然后尝试运动向量的其他预测值，找到最小的SAD，若该SAD小于刚才找到的sad，则设置context->vec_best = context->vec[best]，如果该SAD < th0，则返回SAD。

3．若上面都没有找到小于阈值的SAD，则调用small_diamond_search，进行小菱形搜索，实际就是搜索上下左右四个点，直到当前点为5个点中SAD的最小点。如下图所示。

图8 小菱形搜索

0 引言
近年来，随着信息技术飞速发展和互联网的日益普及，尤其是以视频为信息主要来源的多媒体领域越来越受到人们的关注。H．264是ITU-T的视频编码专家组(VCEG)和ISO／IEC的活动图像编码专家组(MPEG)的联合视频组(Joint Video Tearn，JVT)开发的一个新的数字视频编码标准，它既是ITU-T的H．264，又是ISO／IEC的MPEG-4的一部分。H．264和以前的标准一样，也是DPCM加变换编码的混合编码模式。H．264标准可分为三档：基本档次(其简单版本，应用面广)；主要档次(采用了多项提高图像质量和增加压缩比的技术措施，可用于SDTV、HDTV和DVD等)；扩展档次(可用于各种网络的视频流传输)。
H．264／AVC的编解码框架的基本结构与早期的编码标准(H．263、MPEG4等)相似，都是由运动估计、变换、量化、熵编码、环路去块效应滤波器等功能单元组成的。H．264视频编码框架的主要变化包括：引入了环内去块效应滤波器，去块效应处理后的宏块被保存在内存中用于对后续宏块的预侧；采用了多参考帧运动估计，需要在内存中保留多个参考视频帧；引入了帧内预测机制，可以通过同一帧内的宏块进行预测；采用了新的整型变换方式，取代了以前的离散余弦变换(DCT)；H．264与以前视频标准在运动估计的模式上也有了较大的变化，H．264支持7种模式的可变块运动估计。此外，在熵编码中还引入了上下文自适应的变长编码(CAVLC)和二进制算术编码(CABAC)。
在熵编码方面，H．264使用了CABAC和CAVLC两种不同的编码方式。CABAC熵编码是一种基于区间划分的算术编码方式。这种编码方式的效率很高，接近信息熵值，但算法相对复杂，编解码速度较慢。CAVLC是一种可变长编码，它根据已编码语法元素的情况动态调整编码中使用的码表，在编码过程中有些语法元素是组合编码的，当对这些元素进行查找时就会耗费很长的时间。因此对CAVLC的优化显得格外重要。

1 原码表查找算法
原码表的存储结构为二维表结构。存储的内容为码字，二维坐标分别代表解码后的两个语法元素。对于二维表结构。若通过坐标查找内容是很容易的；而通过内容查找坐标，就需要对整个表进行遍历。JM中的码表查找算法就是通过遍历整个码表实现的，步骤如下：
(1)取码表的中的一个码字；
(2)根据码字长度从码流中取出相应长度的bit；
(3)比较此码字和bit串，若相同则查找成功，否则若码表中还有码字，回步骤(1)，否则查找失败。

2 算法的优化分析
2．1 基于前缀零分组子表搜索算法
基于上下文自适应的变长编码的解码算法需要不断的读取码流，判断，直到在码表中找到该码字，如此反复，直至解码整个块。由此可见该过程的时间空间复杂度都是相当高的。由于变长码为霍夫曼前缀码，所以可以根据码表的特性，按照码字长度将原来的一个码表，按照码字长度对原码表进行分割，以Coeff_token码表为例，原码表如表1所示，表中NC=-1。

在参考模型中，搜索码表算法过程如下：
(1)从最短码长开始，读出该长度二进制数据流对应的码字；
(2)遍历码表，如找到该码字进行步骤(4)，否则进入(3)；
(3)码字长度加1，重定位指针位置，重复步骤(2)；
(4)读取该码字对应值，更新指针位置。
从上面过程中不难发现，码字长度的不确定性使得在读取字节流时只能一次次的试探，导致了效率的下降。如果可以将变长码的读取采取固定的策略，一次读取固定的长度，之后再做判断，再读取一定长度，这样将判断的次数也固定，从理论上可以降低不断搜索和重定位指针带来的时间和空间复杂性。利用可以利用码表中码字前缀零数目的不同，将表1拆分为两个子表，如表2，表3所示NC为-1。

改进后的码表搜索算法如下：
(1)读取最大码字长度的二进制流；
(2)根据不同的前缀零位数、右移位、判零以确定码字所在子表；
(3)直接根据码值读取对应值，更新指针位置。
新的搜索过程不但避免了不确定性，而且无需遍历码表，这样可以在一定程度上提高变长解码的效率。

按照改进的算法步骤，解码时，首先从字节流中读取8位码字，由于前缀零个数分为大于3和小于3的两种情形，所以右移5位，若为零，则查找表2，否则查找表 1，根据码值直接解码出±1个数，非零系数数目。此外在设计代码时，还可利用二叉搜索树的特性，设计搜索过程，提高解码效率.

2．2 二叉树一子表混合法
拆分成子表后建立的数组中存在冗余现象。如当0≤N<2且Pre-Zeros<6时，一共有13个码字。为了保留原先的查表方式以TC和 Tls为矩阵下标的特点，必须要用4×7矩阵，多余位置零。由于实际搜索的对象是矩阵，怎么确定Pre-Zeros值，以保证在分块数一定的情况下，使用的矩阵较小，成为提高搜索效率的关键。从表中可以看到，对不同的N值对应的列，子表之间的Pre-zeros的分界点选取了不同的阈值。按照表2中的分块方法，矩阵的平均大小为4×6．5。相比JM中使用一个4×17矩阵，搜索效率理论上可以提高(17-6．5)／6．5=1．615倍(假设每张子表的使用概率相同)。以0≤N<2的一张VLC表为例，共分成4张子表。从查找一个码字的比较次数来看。

可知，子表法查找比较次数的理论最小值为此时要求n=s2。如果在第一个步骤(确定子表)中改为采用二分法，则这种情况下就可以对以上码表中前缀连零再细化，将相同连零个数的码字放在一起，增加子表数而减少子表中的码字结点数，可以进一步提高查找效率。
从以上分析可见，二叉树的查找效率是最高的。因此可以将二叉树应用到子表法中，对每一张子表分别建树。对于二叉树来说，查找时间与树的深度有关。观察子表中的码字，发现它们都有不同长度的连零作为前缀，如果直接建树将导致树的不平衡并增加了树的深度。为了解决这个问题，可以考虑在同一张子表中为每个码字去除相同个数的连零前缀，然后建立二叉树。在解码时，先忽略这些连零个数，再进行树的查找。在最理想情况下，这种查找方法的一次查找的平均比较次数为：

对第一张VLC表采用二叉树一子表法的最大比较次数：

几种算法的对比与复杂度分析如表4所示。

空间复杂度也是需要考虑的问题。JM参考实现中为Tls和TC的联合码表建立了2个3×4×17的三维数组共需要408 B的存储空间。二叉树法经过统计，一棵树共有124个结点，其中叶结点62个，其余62个结点为根结点或枝结点。建3棵二叉树所需要的空间为 (62×4+62×2)×3=1 116 B。子表法将码表分成12张子表，每张子表用2个二维数组表示，而数组的平均大小为4×6．5，则共要4×6．5×12×2=624 B。

3 结 语
H．264是现在视频编解码领域研究的热点也是未来发展的方向，它将代替MPEG2成为主流的信源压缩标准。H．264应用领域非常广泛。将H．264的编解码速度尽可能的提高，可以使其在更多的领域中应用，如数字电视，消费电子类产品，网络通信，可视电话等现在热门领域。在此专门对于CAVLC码表查找给出了改进方案，通过这三种改进方案，避免了对整个码表的查找，对码表的查找在效率上有了很大提高。具有明显的实用意义.