H.264差错隐藏技术研究及改进+文献综述(6)
② 绝对误差均值（MAD）最小准则：
2.1.3.2 搜索算法
位移 的选取，即运动矢量的搜索算法有很多种。
一种是采用全局搜索算法，即用匹配准则对搜索区内的每一个像素都进行计算。这种方法虽然能找到全局最优算法，但是它的计算量非常大。
还可以采用基于梯度的运动估计，如果视频序列满足梯度约束公式，则可以显著减少搜索次数。令 表示 时刻像素 的亮度值。该像素在空间方向上的运动定义为 和 。当在时间 时，像素运动到 ，得到的运动矢量可定义为：
可以推出，梯度约束公式为：
还有一种分层或树形搜索算法。Jain等人[3]提出这种算法，这种算法是在一个块内构造8个方向的相关矢量，从中找出具有最低MCER值的矢量，然后在那个方向上缩小块大小继续算法，直到最后块大小为3 3为止。这种该算法可以降低运动补偿算法的复杂度。
2.2 变换编码
预测编码的压缩能力是有限的。以DPCM为例，一般只能压缩到每样值2~4比特。20世纪70年代后，科学家们开始探索比预测编码效率更高的编码方法。人们首先讨论了KL变换（Karhunen-Loeve Transform）、傅立叶变换等正交变换，得到了比预测编码效率高得多的结果，但算法的计算复杂性太高，可以用于进行科学研究，而在实际中很难使用。到20世纪70年代后期，研究者发现离散余弦变换DCT与KL变换在某一特定相关函数条件下具有相似的基向量，而用DCT的变换矩阵来做正交变换就可以节省大量的求解特征向量的计算，因而大大简化了算法的计算复杂性。DCT的使用使变换编码压缩进入了实用阶段。小波变换是继DCT之后科学家们找到的又一个可以实用的正交变换，它的时域和空域特性很好，还适应人眼视觉系统，适用于第二代编码技术。
变换编码技术广泛应用于各种静止图像数据压缩，以及运动图像的帧内压缩、帧间残差信号的压缩编码。
2.2.1 变换编码原理
变换编码是通过变换来解除或减弱信源符号间的相关性，再将变换后的样值进行标量量化，或采用对于独立信源符号的编码方法，以达到压缩码率的目的。
变换编码系统中压缩数据有变换、变换域采样和量化三个步骤。变换本身并不进行数据压缩，它只把信号映射到另一个域，使原本具有很强相关性的信号经过适当的坐标旋转和变换，变成统计上彼此较为相互独立的像素矩阵。这样，量化操作通过比特分配可以有效地压缩数据。
下图是变换编码系统方框图。
图5 变换编码、解码原理框图
图中接收端输出信号与输入信号的误差是因为输入端采用量化器的量化误差所致。常见的变换编码有最佳变换，也称Karhunen-Loeve变换（K-L变换），这种变换的协方差矩阵为一对角矩阵，且具有最小均方误差；还有一些协方差矩阵接近对角矩阵的变换，如DCT（离散余弦变换）、DFT（离散傅立叶变换）、WHT等，称为次最佳变换。
2.2.2 K-L变换
离散K-L变换是以图像的统计特征为基础的一种正交变换，也称为特征向量变换。由于其变换基矢量，即变换矩阵是根据输入图像的统计特征性质得出的，所以它具有最佳的去相关性。
设一幅图像阵列 每行用列矢量表示， 。对于不同的图像， 也不同，用其平均值和协方差表征。
的列矢量平均值 。
的协方差矩阵 。
可以求出 的特征值及其归一化特征矢量。再利用这些特征矢量构成正交矩阵 ，对图像 作正交变换后得 。这种变换即为K-L变换。可以证明， 的协方差矩阵是一个对角矩阵，对角线上的值即为 的特征值。