（信息与通信工程专业论文）h264编码算法与解码器存储结构优化.pdf

浙江大学硕士学位论文 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图表索引 h 2 6 4 的三种档次 一5 h 2 6 4 编码器框图 5 采用f m o 的片划分 8 菱形搜索算法 1 3 8 x 8 块的1 4 采样 1 4 子集在参考帧中的匹配位置 1 4 二维块的一维垂直映射 1 5 像素点位置 一1 6 图2 6 a 最优整像素点位于预测中心 图2 6 1 0 水平或垂直平移 1 8 图2 6 e 对角方向的平移 1 9 图2 7 小菱形搜索模式 s d s p 2 2 图2 8 最优点 次优点更新过程 2 4 图3 1五帧参考的全遍历模式 2 8 图3 2 运动矢量重用过程 2 9 图3 3 多参考帧中的搜索窗 2 9 图3 4 也f 4 中的多参考帧预测算法 3 0 图3 5 运动对象在各帧中的运动矢量 3 1 图3 6 相邻宏块位置关系 3 2 图3 7 邻近块最佳参考帧相关性统计 3 3 图3 8 a 1 6 1 6 块划分模式的预测 3 5 图3 8 b 1 6 x 8 块划分模式的预测 3 5 图3 8 c 8 1 6 块划分模式的预测 3 5 图3 8 d 8 x 8 及以下块划分模式的预测 3 6 图3 9 全参考帧搜索和基于预测 不带阈值 的最佳参考帧选择结果 3 6 图3 1 0 极端情况下全参考帧搜索和基于预测 无闽值 的参考帧选择结果 3 7 图3 1 1c l a i r e 序列中一帧 3 9 图4 1h 2 6 4 解码流程图 4 2 图4 2 当前块与临近块位置关系 4 3 图4 3 当前和临近4 x 4 分块 4 4 图4 44 x 4 和1 6 x 1 6 模式的帧内预测 亮度 4 4 图4 5 滤波边界 4 5 图4 6 行宏块缓存的示意图 4 6 图4 7 改进的邻近块存储结构 4 7 图4 8 用于存储滤波前像素的行像素缓存 亮度 一 4 d 图4 9 改进的解码器存储结构与数据流图 一 利 图4 1 0 数据搬运与数据处理任务时问分布 5 2 图4 1 1 双缓存机制示意图 z 图4 1 2 双缓存结构下数据搬运任务与数据处理任务的时问分布 一5 3 图4 1 3 重构帧缓存与邻近块缓存数据分布 5 4 v i 浙江大学硕士学位论文 表2 1 水平或垂直平移方式下运动搜索的平移次数和搜索点数 1 8 表2 2 对角平移方式下的平移次数和搜索点数 2 0 表2 3 各种情况所占的比例 2 0 表2 4s d s p 和d s 的编码效率比较 一2 1 表2 5 最优点位置分布概率 2 2 表2 6 次优点位置更新 2 4 表2 7l p p d s d s s d s p 编码效率比较 2 5 表3 1 各种块划分模式的多参考帧候选集 3 4 表3 2 每次平均搜索的参考帧数目 3 8 表3 3 本文算法和多参考帧全遍历模式的编码速率比较 4 0 表3 4 本文算法和多参考帧全遍历模式的p s n r 码流长度的比较 4 0 表4 1 行宏块缓存的存储需求 4 7 表4 2 改进的邻近块存储结构的空间需求 4 9 表4 3 采用直接存储器读写时数据搬运时间与总时间的关系 5 7 表4 4 采用d m a 数据搬运与采用直接存储器读写的总解码时间比较 5 7 i 浙江大学硕士学位论文 第一章绪论 随着存储 通信等技术的日趋完善 以及互联网的高速发展 个人用户对多媒体业务 的需求不断增长 多媒体不再局限于文本 语音和图片 视频图像将为用户提供功能更强 大 更完善的服务 由于数字视频在存储 编辑 传输等各个方面都明显优于模拟视频 因此被广泛地应用于视频会议 可视电话 电子商务 广播电视 安全监控等多个领域 然而用来表示这些视频图像信息的数据量很大且对带宽的要求非常高 这将对存储器 通 信信道以及处理器等都带来很大的压力 因此 视频数据的高效压缩意义重大 是降低存 储成本 缓解网络带宽 突破存储空间和处理器主频限制的关键技术 1 1 视频压缩编码原理和主要技术 未经压缩的原始图像数据是高度相关的 存在很大的冗余 在同一幅图像中 规则物 体和规则背景的表面物理特性具有相关性 这些相关性的光成像结构在数字化图像中就表 现为空间冗余 图像序列中的两幅相邻的图像之间有较大的相关性 这反映为时间冗余 1 由于人类视觉系统的特性 对某些图像的变化无法感知 因此存在视觉冗余 2 平均编码 长度和信源熵之间的偏差 称为熵冗余 3 此外 对于某些特殊类型图像而言 可能还存 在结构冗余和知识冗余等其它形式的数据冗余 视频压缩技术就是这种压缩可能性变为现 实的技术 具体的视频压缩方法有很多分类 常用的压缩编码方法可以分为 熵编码 4 预测编码 5 变换编码 6 以及其它的编码方法 1 1 1 熵编码 熵编码又称为统计编码 它是根据信源符号出现概率的分布特性而进行的压缩编码 它的基本思想是在信源符号和码字之间建立明确的一一对应关系 以便在恢复时能准确地 再现原信号 同时要使平均码长或码率尽量小 常用的熵编码有h u f f m a n 编码 算术编码 和游程编码 h u f f m 编码在编码前需要统计信源概率分布 对具有等概率分布的信源编 码 该方法是最优的 算术编码是将被编码的信息映射到实数0 与l 之间的一个间隔 信 息越长 编码表示它的间隔就越小 表示这一间隔所需的二进制 x 浙江大学硕士学位论文 1 1 2 预测编码 预测编码根据时空相关特性可分为时域帧间预测和空域帧内预测两大类 帧问预测编 码是利用图像序列之间的时间相关性 每个像素可以根据已编码帧内的像素来作预测 帧 内预测是利用空间中相邻数据的相关性来预测未来点的数据 因此在预测编码中 编码和 传输的并不是像素采样值本身 而是这个采样值的预测值与其实际值之间的差值 1 1 3 变换编码 变换编码的基本原理在于通过数据空间变换 改变数据的表示形式或分布 使能量集 中在变换域中少数变换系数上 从而在变换空间实现数据压缩 主要采用正交变换编码技 术 如k l 变换 k a r h u n e n l o e v et r a n s f o r m d f t 变换 d i s c r e t ef o u r i e rt r a n s f o r m d c t 变换 d i s c r e t ec o s i n et r a n s f o r m h a d 删a r d 变换 w a l s h h a d 锄a r d 变换等 其中 k l 变换后的各系数相关性小 能量分布集中 忽略低值系数的误差小 一般认为是最佳变 换 但其计算复杂度大 工程上难以实现 实际中采用的主要是与k l 变换性能最为接近的 d c t 1 1 4 其他编码 其它的编码方法还有诸如子带编码 子采样编码 统计分块编码 分形编码与模型编 码等 综上所述 在一幅图像中 各种冗余信息是并存的 不能片面地强调某种形式在图像 编码方法中地作用 在实际压缩过程中一般采用结合预测 变换 量化和熵编码等多种方 法结合的混合编码方案 以达到最佳的编码效率 1 2 数字视频编码标准 在当前广播数字化 网络宽带化 通讯无线化 存储高密度化的大趋势下 多媒体技 术正在进人流媒体的新时期 而标准化则是上述产业化活动成功的前提 2 0 世纪9 0 年代 以来 国际电信联盟r r u t 和国际标准化组织l s o 相应制定了一系列视频压缩编码标准 极大地推动了多媒体技术的实用化和产业化 按推出时间的先后顺序有h 2 6 l m p e g l m p e g 2 h 2 6 3 m p e g 4 和h 2 倒拍 c 等 2 浙江大学硕士学位论文 1 2 1h 2 6 1 h 2 6 l 7 是i t u t 于1 9 9 0 年制定的针对可视电话和视频会议等要求实时编解码和低延 时的视频压缩标准 它的输出码率为p 6 4 k b i t s 其中p 为o 到3 l 的整数 h 2 6 l 采用 的算法主要是帧间预测和二维d c t 变换的混合编码方法 具有压缩比高 算法复杂度低等 优点 1 2 2m p e g 1 标准 m p e p l 8 由i s 0 i e c 于1 9 9 1 年制定 是基于一般低端应用的视频 音频编解码标准 它主要针对c i f 格式 3 5 2 像素 2 8 8 行 和每秒3 0 帧的图像质量 将视频信号和相应的 伴音在可以接受的质量要求下编码成l 涮b p s 的数据流 类似于h 2 6 l 标准 m p e g l 也 采用运动补偿和二维d 凹变换 量化后的d c t 系数进行变长编码 同时对每个数据块的直 流分量进行预测差分编码 i p e g l 与h 2 6 l 由于应用的侧重点不同 故采用的编码方式也 有不同 最主要的差别是h 2 6 l 有两种类型的帧 帧内编码帧 i 帧 和预测编码帧 p 帧 而m p e g l 采用的图像有三种类型 帧内编码图 i 图 预测编码图 p 图 和双向预测 编码图 b 图 1 2 3m p e g 2 1 1 2 6 2 标准 m p e g 一2 9 是由i t u t 和活动图像专家组于1 9 9 4 年共同制定的 它的视频编码部分就 是h 2 6 2 m p e g 一2 标准广泛应用于多媒体 视频会议 可视电话 数字电视 高清晰度电视 广播 通信和网络等领域 它的成功之处在于提出了通用的压缩编码方法 定义了不同的 档次 口r o f i l e 和等级 1 e v e l 可满足不同图像分辨率及相应的存储成本和处理器速 度的需要 m p e g 2 向下兼容m p e g 一1 增加了基于帧 场的运动补偿 空间可伸缩编码 x 浙江大学硕士学位论文 h 2 6 4 采用的新技术 1 5 卜 1 7 主要有 1 树状螬构 1 4 鲁素精度的运动补偿 h 2 6 4 采用了不同大小和形状的宏块分割和亚分割方法 1 8 一个宏块的1 6 1 6 亮度 块可以按照1 6 1 6 1 6 8 8 1 6 或8 8 进行分割 而如果选择了8 8 分割 那么还可 以按照8 8 8 4 4 8 或4 4 进行亚分割 宏块分割为不同尺寸的运动补偿子块称为 树状结构的运动补偿 宏块中色度块的分辨率为亮度块的一半 因此除了分割尺寸在 水平和垂直方向上都是亮度的一半外 其分割方法与亮度块相同 这种多模式划分具有灵 活和细致的特点 更符合图像中实际运动物体的形状 大大提高了运动估计的精确程度 h 2 6 4 采用l 4 像素精度的运动补偿 高精度的运动补偿可以在参考帧中找到与当前 块更匹配的块 从而减少运动预测残差值 提高压缩效率 另外 在得到l 4 像素精度时 由于使用了增强内插滤波器可以有效地减少高频噪声 2 新的 内瑗 对i 帧的编码是通过利用空间相关性来实现的 1 9 以前的标准只利用了一个宏块内 部的相关性 而忽视了宏块之间的相关性 因此一般编码后的数据量较大 为了能进一步 利用空间相关性 h 2 6 4 利用周围邻近的像素值来预测当前的像素值 然后对预测误差进 行编码 在h 2 6 4 标准中 亮度块可以有9 种4 x 4 块的帧内预测模式和4 种1 6 1 6 的帧 内预测模式 而色度8 8 块的4 种模式与亮度的4 种1 6 1 6 块模式相似 3 多参考帧预测 l 2 6 4 标准采用多参考帧预测技术 使运动搜索范围从原来的一个参考帧扩展到多个 解码后的参考帧 这样通常能找到更精确的匹配块 从而有助于获得更高的编码效率 多 参考帧技术在周期性运动 平移封闭运动和两个不同场景之间来回切换的场合可以得到比 较好的应用 另外多参考帧技术还能够实现更好的误码恢复 2 0 改善视频图像质量 但 是该技术的引入同样增加了编码器的计算复杂度 并对存储容量提出了更高的要求 4 码 h 2 6 4 标准采用了两种类型的熵编码方法 2 l 统一的变长编码 u v l c 和基于内容 自适应的二进制算术编码c a b a c 统一的变长编码是指需要编码的各种参数 残差数据信息都采用统一的可变长码表 而不是像以往的标准那样 针对每一个符号集合构建单独的v l c 表 因此使问题得到简化 基于内容自适应的二进制算术编码是一种新型的高教熵编码方法 它相对于u v l c 可 以获得更好的压缩性能 主要通过以下三个方面来实现 2 2 a 上下文建模 对h 2 6 4 中所定义的各种编码元素按照元素的上下文选择概率模型 利 用合适的上下文模型 按照当前编码字符和邻近已编码字符之问的条件概率充分减少编 码字符间的冗余度 b 自适应概率估计 允许熵编码器自适应非稳态的字符统计 即基于实际统计的自动概 6 浙江大学硕士学位论文 率估计 c 二进制算术编码 算术编码允许给每个字符分配非整数个比特数 尤其是出现概率大 于0 5 的这些字符 用v l c 编码至少要分配不小于1 比特的信息 而算术编码则可以 分配小于1 比特的信息 c a b a c 的编码性能虽然要比u v l c 好 但计算复杂度高 不利于并行实现 5 奠羹变换和量化 h 2 6 4 标准与先前的标准一样 都是采用基于块的变换编码 不同的是在h 2 6 4 中采 用了整数变换 2 3 相比于d c t 变换由于新变换中只有整数操作而不是浮点运算 因此不 会产生反变换误差 另外 由于运动补偿的最小块划分为4 4 因此整数变换的块单位也 为4 4 由于变换块的尺寸缩小 运动物体的划分更精确 不但变换计算置较小 而且在 物体边缘处的衔接误差也大大减少 h 2 6 4 采用了5 2 个梯状的量化系数 量化值的设计使得q p 每增加1 量化步长相应增 加1 2 5 而不是以固定的增幅增长 从而使码率控制的能力得到提高 同时 h 2 6 4 将 变换中的尺度变换计算并入量化中进行 从而避免了除法计算 减少了计算复杂度 b 去块效应滤波嚣 传统基于块的视频编码系统 在相对码率较低的视频编码时总会遇到块效应这个问题 这是由基于块的预测 补偿 变换和量化造成的 2 4 h 2 6 4 在编码环中引入了去块效应滤 波系统 该系统也是h 2 6 4 在相对码率较低的情况下依旧能保持较好的主观视觉效果的重 要因素之一 另外 由于滤波后的帧用于后续帧的运动补偿预测 从而避免了虚假边界的 积累 减少了预测残差 7 新型杖格式 h 2 6 4 除了支持以往标准中提出的i 帧 p 帧和b 帧外 还支持转换编码帧 2 5 1 s p s w i t c hp f r a m e s i s w i t c hi f r a m e 它允许某些解码器的解码处理与其它解码器产生的 正在进行的视频流准确同步 它可以在不同数据速率的视频内容之间切换解码器 恢复数 据的丢失或误码 以及支持随机切入和快速回放模式 h 2 6 4 还提出了跳过 s k i p p e d 模 式和直接 d i r e c t 模式两种利用时间关系直接预测的运动估计方法 8 片 片组 f m o h 2 6 4 将一幅图像分成了若干个片 每片包含一系列的宏块 宏块的排列可按光栅扫 描顺序 也可不按扫描顺序 每个片独立解码 不同片的宏块不能用于当前片中做预测参 考 从而防止了误码在片之间的扩散 h 2 6 4 支持灵活的宏块顺序 f m o f l e x i b l em a c r o b l o c ko r d e r i n g 允许宏块分配到不 按扫描顺序的片中 如图1 3 所示 阴影宏块和白色宏块分别属于不同的片 当白片丢失 时 可以利用邻域相关性 阴影宏块的某种加权可以来代替白片相应宏块 这种技术可以 使误码掩盖技术更容易实现 7 浙江大学硕士学位论文 钐形彰 影形 钐形篓参 形彩 图1 3 采用f m o 的片划分 9 囊据分期 h 2 6 4 利用数据分割技术适应传输信道的码率变化 通过在编码器中使用基于语法的 数据分割方法 将每帧数据按其重要性分为三部分 在必要时可以丢弃不太重要的信息 以确保重要信息的准确传输 1 4 编解码器优化 1 4 1 优化背景与目的 通信技术和信号处理技术的发展 为数字视频提供了越来越多的机会 在实现高效视 频压缩的同时 如何降低视频编解码器的复杂度 保证编解码过程的实时性 确保得到低 延时高质量的解码图像 日益受到关注 高质量实时视频编解码成为重要的研究课题 1 4 2i i 2 6 4 编码器算法优化 优秀的算法实现效率高 运算速度快 占用资源小 是视频编解码器优化计算复杂模 块的主要方法 优化算法可以分为两类 即保持编码效率不变的无损优化方法和适当降低 编码效果加快速度的有损优化方法 对h 2 6 4 编码器进行算法优化的关键是找出编码过程中的主要耗时模块并对其进行优 化 从而降低整个编码器的计算复杂度 h 2 6 4 采用了七种块划分模式 1 4 像素精度的运 动估计 以及采用多参考帧预测技术 使得运动估计模块的计算量相比以往的标准有大幅 度的提高 研究表明 运动估计模块是h 2 6 4 编码器的主要耗时模块 2 6 当采用单个参考 帧预测时 该模块耗时占整个编码器的6 0 当采用五个参考帧预测时 运动估计模块的 耗时比例可以达到8 0 运动矢量搜索和多参考帧预测是运动估计模块的两个主要组成部分 也可以认为这两 部分是结合在一起的 目前针对运动矢量搜索的研究比较多 有通过沿块匹配误差梯度下 降方向进行搜索来减少搜索点数的 如菱形搜索法 2 9 1 三步搜索法 2 8 1 等 也有通过某些 判决准则提前结束搜索的 如基于全零块检测的运动搜索提前退出算法 2 6 3 4 1 等 以及快 浙江大学硕士学位论文 速块匹配误差计算法等 相比之下 通过沿块匹配误差梯度下降方向搜索的算法最为高效 也是研究最多的 本文将提出的快速搜索算法也是基于该类思想的 多参考帧预测技术可 以节省5 1 0 的码率 但是该技术的引入却使得运动估计的计算复杂度随参考帧数目成 线性增长 因此 研究多参考帧预测的快速算法是非常有必要的 目前针对多参考帧预测 技术的研究没有针对运动矢量搜索的多 很多是结合多参考帧预测技术特点提出的适用于 多参考帧预测的快速运动矢量搜索算法 如e l l e n 等人在文献1 4 3 中提出的算法 还有小部 分是专门针对多参考帧预测技术提出的 这类算法一般利用一些判决条件 跳过对某些参 考帧的搜索 从而达到减少运动估计计算时间的目的 本文将提出的算法就是基于后者的 通过选择部分参考帧来减少运动估计时间 1 4 3 基于d s p 的h 2 6 4 解码器存储结构优化 由于解码器主要用于网络流媒体和移动视频通信等直接面向客户的应用服务 用户终 端设备受到处理能力 电池容量和存储空间等多种因素的限制 使h 2 6 4 解码器本身不可 能提供与编码器相似的硬件设备 用户终端手持设备的上述特点决定了h 2 6 4 视频解码器 本身尺寸应尽可能小 功耗尽量降低 在提供优质解码图像质量的同时 尽量消除解码时 延 以及提供有效的错误隐藏机制 和可灵活升级等功能 在视频编解码器优化过程中 优秀的算法可以在保持编码效率的基础上 有效地减少 计算复杂度 同时 系统的性能与程序的实现方式也密切相关 优化代码也可以有效地提 高运算效率 因此对程序而言也是至关重要的 代码实现优化主要包括程序结构优化 数 据存储结构优化 循环展开 数据类型选择等多种方法 其中 数据存储结构的设计非常 重要 合理的存储结构既有利于提高数据访问的速度又有利于程序在不同平台的移植 本 文对h 2 6 4 解码器的优化主要针对数据存储结构的设计 对于一个基于d s p 的存储结构设计 除了要进行片内 片外存储器资源的合理规划外 还需要考虑片内和片外的数据调度问题 d m a 直接存储器存取 是提高计算机系统工作 效率的一项重要技术 可以在d s p 核不参与的情况下 完成存储器空间内部或者存储器空 间与外设之间的数据传输 从而使处理器从数据传输任务中解脱出来 而发挥d m a 数据 传输机制优势的关键在于数据传输任务与数据处理任务的合理安排 只有这样才能避免 d m a 数据传输时的处理器等待 使系统性能得到最大程度的提升 1 5 本文的内容安排及主要贡献 本文从h 2 6 4 a v c 实时视频应用的角度出发 针对编码过程中的主要耗时模块运动矢 量搜索和多参考帧预测以及基于0 s p 的解码器实现进行了深入的研究与分析 提出了快速 运动矢量搜索算法 快速多参考帧选择算法以及基于d s p 平台的h 2 6 4 解码器存储结构优 浙江大学硕士学位论文 化策略 本文的章节内容安捧t 第二章在介绍了目前主要的快速运动矢量搜索算法的基础上 总结了快速整像素运动 矢量搜索的特点 以及快速分像素运动矢量搜索的适用条件 通过理论分析和实验比较对 菱形搜索算法做了两步改进 提出了基于线性预测的准菱形搜索算法 实验证明 该算法 不仅能有效地降低整像素运动矢量搜索的时间 还能与现有的某些快速分像素运动矢量搜 索算法很好的衔接 从而避免中间过程的计算开销 第三章首先对目前主要的一些快速多参考帧预测算法进行了介绍和分类 然后从另一 个角度出发 利用邻近块最佳参考帧之间的关系提出了一种基于空间预测的多参考帧选择 算法 同时在分析了预测不命中带来的后果的基础上 为该算法引入了一个自适应的阂值 从而既保证了最佳参考帧选择的准确性又有效地降低了计算时间 第四章首先分析了h 2 6 4 解码过程中涉及到的当前宏块与邻近块的信息交互情况 然 后对如何在d s p 片内存储空间中开辟一个用于存放邻近块信息的缓存进行了讨论 出于节 省d s p 片内存储空间的考虑舍弃了在片内开辟一行宏块缓存的做法 提出了一种基于d m a 数据调度的邻近块信息存储方式 同时 为了充分发挥d m a 数据调度的优势 需要尽量 使d s p 数据处理任务与d m a 数据传输任务在时间上达到并行 为此 文中引入了双缓存 机制 开辟了两个同样大小的片内空间用于存放邻近块信息 最后通过实验证明基于该双 缓存机制的解码器存储结构的合理性 本文的主要贡献和刨新点 i 在菱形搜索算法的基础上提出了基于线性预测的准菱形搜索算法 该算法依据 s a d 分布的空间方向性采用线性预测来确定每轮小菱形搜索的最佳中心点 从而 更快的找到最优整像素点 实验证明 该算法在不牺牲图像质量和压缩性能的前 提下 使搜索点数相比于菱形搜索算法平均减少了约一半 同时该算法能很好地 与y i n 3 8 等人提出的第二种分像素快速搜索算法结合使用 而不需要任何中间步 骤 从而使整个运动矢量搜索时间得到最大程度地降低 2 在实验中发现邻近块的最佳参考帧选择存在较大的相关性 在此基础上提出了基 于空间预测的参考帧选择算法 该算法利用邻近块的最佳参考帧信息来预测当前 块的虽佳参考帧 建立最佳参考帧候选集 通过只在参考帧候选集中搜索最佳参 考帧来减少多参考帧选择的时间 同时为了减少最佳参考帧被漏选的情况 本文 为该算法引入了一个自适应的闽值 当在参考帧候选集中搜索到的匹配块的运动 补偿代价过大超过阈值时 将继续对候选集外的其它参考帧进行搜索 3 通过分析h 2 6 4 解码器的解码流程 总结出解码过程中涉及到的当前宏块与邻近 块的信息交互情况 并根据d s p 片内存储资源有限的特点 以及利用d m a 进行 数据调度时数据处理任务与数据传输任务的时间分配情况 提出了一种合理的解 1 0 浙江大学硕士学位论文 码器存储结构 该结构对系统存储空间要求不高 回时基于该结构的解码器基本 上可以达到数据搬运任务与数据处理任务的完全并行 使利用d m a 进行数据调度 的优势得到很好的发挥 浙江大学硬士学位论文 第二章快速运动矢量搜索算法 对于视频图像序列 由于相邻帧之间存在很大的时间相关性 因此通过减少时间冗余 可以太幅提高视频编码的效率 从第一章的介绍中知道 七种块划分模式和l 像素精度 的运动补偿技术的采用能有效地提高h 2 6 4 的编码效率 然而这也是h 2 6 4 编解码器复杂 度大大增加的主要原因之一 c h e n 2 6 等人指出在i i 2 6 4 编码器中运动估计模块是主要的 耗时模块 当采用单个参考帧预测时 该模块耗时占整个编码器的6 0 当采用五个参 考帧预测时 运动估计模块的耗时比例可以达到8 0 因此 减少运动估计的计算量是 减少整个h 2 6 4 编解码器计算量的关键 运动矢量搜索分为整像素运动搜索和分像素运动搜索两个部分 本章先介绍目前主要 的整像素和分像素快速运动矢量搜索算法 然后通过理论分析和实际测试在菱形搜索算法 的基础上提出了一种基于线性预测的准菱形搜索算法 最后通过实验证明该算法在不牺牲 图像质量和压缩效率的基础上使搜索点数大大减少 2 1快速整像素运动搜索算法综述 基于块匹配的运动估计算法是减少视频序列时间冗余的有效方法 已被许多视频编 码标准所采纳 它的基本思想是将当前帧划分成若于个子块 对于其中的每一块 在参考 帧中某一给定搜索区域搜索该块的最佳匹配块 若找到这样的块 则当前块与匹配块之间 的相对位移即为该块的运动矢量 这样当前帧中的每一块都可以用一个残差块和一对运动 矢量来表示 从而实现高倍压缩 全搜索 f u l ls e a r c h f s 算法是块匹配运动估计最直接的实现方法 f s 算法通过 对搜索窗内的所有点进行搜索 可以达到最佳匹配 但是f s 算法的计算量巨大不利于满 足实时应用的要求 因此针对运动矢量搜索的优化算法是目前研究的热点 运动矢量搜索 算法可分为整像素运动矢量搜索和分像素运动矢量搜索两个部分 由于整像素运动矢量搜 索在整个运动矢量搜索过程中耗时比重比较大 因此这方面的研究非常多 目前的整像素 快速运动搜索算法主要可分为以下三类 1 沿块匹配误差梯度下降方向进行搜索 从而减少搜索点数的快速算法 这类算法中比较有代表性的有2 维对数搜索法 2d i m e n s i o nl o g a r i t h m i cs e a r c h 2 d l o g s 2 7 3 步搜索法 t h r e es t e ps e a r c h s t t 2 8 菱形搜索法 d i a m o n ds e a r c h d s 2 9 改进的菱形搜索法 3 0 六边形搜索法 h e x a g o n b a s e d s e a r c h h b s 3 1 四 步法搜索法 f o u rs t e ps e a r c h f s s 3 2 等 这类算法大多都是基于误差表面单调变换这 一假设的 但是由于在现实世界的视频序列中这一假设不一定总是成立 所以 为了解决 这一问题 该类算法一般都会使用运动矢量初始值估计 使运动搜索的起始点更加接近全 1 2 浙江大学硕士学位论文 局最优点 从而使搜索速度和准确度大大提高 减少陷入局部最优的概率 3 3 下面以菱 形搜索法为例说明这类算法的基本思想 菱形搜索法 d s 在搜索时采用了大菱形搜索模式和小菱形搜索模式 大菱形搜索 模式有9 个搜索点 中心点及周围按菱形分布的8 个围绕点 小菱形搜索模式有5 个点 中心点及中心点上 下 左 右4 个相邻的点 d s 算法先利用邻近块的运动矢量得到 当前块运动矢量的预测值 以该预测值指向的参考帧中的相应位置为搜索中心 进行大菱 形搜索 计算9 个点 如果9 个点中的最优点不在大菱形中心 则将大菱形的中心移至该 点 重复大菱形搜索 直到最优点处于大菱形中心为止 然后在该点切换到小菱形搜索模 式搜索 共搜索5 个点得到最终的搜索结果作为运动估计的最优匹配点 整个过程如图 2 1 所示 a 沿水平或垂直方向 移动的大菱形搜索模式 需要再搜索5 个点 b 沿4 5 方向移动 的大菱形搜索模式 需要再搜索3 个点 图2 1 菱形搜索算法 c 由大菱形模式切 换到小菱形搜索模式 2 通过利用代数不等式排除不可能成为最佳匹配的待搜索点 或通过某些判决准则 在 某个点当特定准则被满足的时候 跳过对该点的搜索或直接提前退出搜索过程 如基于全 零块检测的运动搜索提前退出算法 2 6 1 3 4 全零块是指编码块的残差信号在经过变换 量化后的系数全部为零的块 显然对于全 零块而言 变换 量化 反变换和反量化都是冗余操作 因此可以提前检测出全零块 就 可以跳过变换 量化 反变换和反量化 减少变换和量化模块的计算量 王 3 4 等人将全 零块检测算法应用到运动搜索过程中 当检测到当前的匹配块为全零块时就停止整像素搜 索 从而减少运动搜索的计算量 该算法虽然可以有效的降低运动的计算复杂度 但由于 基于全零块检测而获得的运动矢量通常不是最优的 因此一方面造成p s n r 随q p 的增加 而下降 另一方面在率失真模式选择时帧内预测块的数量也因此而增加 使得比特率在高 量化值时有所增加 1 3 浙江大学硕士学位论文 3 快速块匹配误差计算法 如子集匹配法d 5 1 和基于投影的方法 3 6 1 子集匹配法的基本思想是先对当前块进行采样 以8 x 8 块模式为例 1 4 的采样结 果如图2 2 所示 其中a b c d 分别为像素 由所有a 像素组成的8 x 8 块的子集称为 子集a 类似地 b c d 组成的8 x 8 块的子集分别记为子集b 子集c 和子集d 假 如只使用子集a 寻找匹配块的方式和全搜索算法一样 只是在计算均方差和时只计算 6 4 1 4 1 6 个点 即只计算1 6 个a 像素点的均方差和 显然采用这种方式计算量可以减少 到原来的l 4 为了得到更准确的匹配块 文献 3 5 1 采用的方法是将子集b 子集c 和子 集d 都利用起来 只是对每个对应位置的匹配块一次只采用一个子集 如图2 3 所示 当 匹配块左上角像素位于1 位置时采用子集a 位于2 位置时采用子集b 其他位置类似 最后每个子集都得到一个最佳匹配块 再对这四个匹配块进行全搜索确定最终的最佳匹配 块 子集匹配法能够达到与全搜索算法相当的图像质量和码率 但搜索速度与的一类算法 相比还是存在一定的差距 ababab ab dcd cdd bb盎b a b dd c dd bb abab cd cd c dcd b ab a b ab c dd cdcd 414 l 32 32 4 l41 3 23 2 图2 28 x8 块的h4 采样图2 3 于集在参考帧中的匹配位i 文献 3 6 1 中提出了基于投影的算法 其基本思想是先将每个块的二维信号映射成一维 信号 假设块大小为b xb 并设b x y 表示左上角坐标为 工 y 的二维块 雪i 表示此 块中第j 行 第i 列的像素值a 定义bx 的垂直一维映射为曙 1 它的第i 个分量为丑 的 第i 列像素值的和 o 芝1 口 2 1 o 口 2 1 t 0 式中 0 i b h 并且o s j 鼠 通过映射 一个b b 的二维信号就变成了b 1 的一维信号t 如图2 4 所示 该算法认为如果两个块的一维累加信号不能很好的匹配 则这两个块的二维信号也不会很 1 4 浙江大学硕士学位论文 好的匹配 因此可以利用一维信号先进行粗略的搜索匹配 快速排除部分不匹配的位置 然后对剩余的位置再使用二维匹配准则进行精细的搜索 该算法也能比较好的维持图像质 量与低码率 但搜索速度也不如第一类算法 i 匦 匝 口匿卫口匝盈口 图2 4 二维块的一维垂直映射 以上这些算法相对于全搜索算法都大幅的减少了计算时间 但相比之下第一类算法最 为高教 也是目前使用最多的 因此本文提出的改进算法将基于第一类算法 另外 由于 运动估计包括整像素运动搜索和分像素运动搜索两部分 只有使两部分的快速搜索算法很 好地结合才能使整个运动估计的计算复杂度得到最大程度的降低 因此下面将介绍目前主 要的快速分像素运动搜索算法 以此来得到一种能兼顾到分像素运动搜索的快速整像素运 动搜索算法 2 2 快速分像素运动搜索算法综述 以前的标准只采用整像素精度的运动估计 如h 2 6 1 或采用1 2 像素精度的运动估 计 如h 2 6 3 m p e g l 因此用于分像素运动预测的时间相对较少 研究的热点也主要 集中在快速的整像素运动预测算法上 随着整像素运动预测快速算法的发展 整像素运动 预测的计算时间已大大降低 一些基于中心偏置的快速整像素运动搜索算法已经将每次整 像素搜索的平均搜索点数降到了l o 点 3 0 相比之下分像素运动预测所占的比重已变得 不容忽视 且h 2 6 4 标准中采用了1 4 像素精度的运动预测 色度采用l 8 像素精度 如 果对分像素运动搜索仍采用全搜索算法 如图2 5 所示 先搜索最佳整像素点周围的8 个 点 上 下 左 右 左上 右上 左下 右下 得到最佳1 2 像素点 再搜索最佳1 2 像素点周围的8 个点得到最佳1 4 像素点 因此对于1 4 像素精度的亮度块分像素运动搜 索需搜索1 6 个点 而对于1 8 像素精度的色度块则需搜索2 4 个点 可见 随着高精度运 动估计的引入 对于分像素快速运动搜索算法的研究是非常有必要的 1 5 浙江大学硕士学位论文 圈2 5 像素点位置 一 m o1 4 抖l 赢滞删 目前已有一些学者提出了分像素运动搜索的快速算法 如c h e n 等人 3 7 1 提出的基于 抛物面预测的分像素搜索 p a r a b o l o i dp r e d i c t i o nb a s e df r a c t i o n a lp i x e ls e a r c h p p f p s 策略 该策略的基本思想是利用最佳整像素点上 下 左 右四个整像素点的绝对误差和 s u m o f a b s o l u t e d i f f e r e n c e s a d 预测1 2 像素点搜索的方向 只搜索该方向上的3 个1 1 2 像 素点即可 而不是搜索全部的8 个1 2 像素点 在1 4 像素搜索中利用前面1 2 像素搜索 中得到的最佳1 2 像素点位置和次最佳1 2 像素点位置 只搜索这两个位置之间的3 个1 4 像素点即可 因此利用该分像素运动搜索算法每次只需要搜索共6 个点 c h e r t 等人还在文献 2 6 1 q b 提出了另外一种分像素快速运动搜索算法 该算法非常类似 于前面介绍的第一类快速整像素运动搜索算法 先利用临近块运动矢量预测得到当前块运 动矢量的预测值 将该预测矢量的分像素部分作为当前块分像素运动搜索的起点 然后进 行小菱形搜索 显然 该算法的复杂度很大程度上取决于预测点的准确度 另外 y i n 等人 3 8 j 提出了两种分像素运动搜索算法 第一种算法是基于一个假设的 该假设认为在最佳整像素点周围的8 个1 2 像素点中 位于4 个对角上的1 2 像素点没有 其他的4 个1 2 像素点重要 因此该算法先将这4 个重要的1 2 像素点与中心的最佳整像 素点比较 如果最佳整像素点优于这4 个1 2 像素点则结束1 2 像素点的运动搜索 否则 继续搜索这4 个1 2 像素点中的最佳i 2 像素点周围的2 个对角位置上的1 2 像素点 得 到最终的最优1 2 像素点 1 4 像素运动搜索也采用类似的做法 可见 采用这种方法 最坏的情况需要搜索6 6 1 2 个点 y i n 等人 3 8 1 提出的第二种分像素运动搜索算法的基本思想比较类似于c h e n 等人 3 7 1 的算法中的对1 4 像素的处理 该算法需要得到整像素搜索中最优整像素点周围 上 下 左 右 四个点中的最优点位置 也即全局的次优整像素点位置 然后搜索最优整像素点 位置和次优整像素点位置之间的3 个l 2 像素点位置 得到最优的1 2 像素点位置 1 4 像素搜索采用类似的做法 该方法也只需搜索6 个点 1 6 浙江大学硕士学位论文 情况二 最佳整像素点和预测中心处于同一水平或垂直线上 从图2 6 b 中可以看到l d s p 每平移一次需要再搜索5 个点 s d s p 每平移一次需要 再搜索3 个点 两者寻找到最佳整像素点需要平移的次数及搜索的点数如表2 1 所示 从 表2 1 中可以看到 当最优点距离预测中心为2 n 2 n l 和2 n 1 时 其中n 为大干0 的 整数 d s 都需要搜索5 n 1 3 个点 平均每像素距离需要搜索约 5 n 1 3 2 n 个点 s d s p 则分别需要搜索6 n 5 6 n 2 和6 n 8 个点 平均每像素距离需要搜索 6 n 5 2 n 个 点 因此 只有当最优点离预测点距离大于等于9 个像素点时 d s 的搜索效率才会比s d s p 高 li l j n l1 x 未 x 羔苫 未互未 l x x 毒莲 k j j 王p 坚 丫x 丫 n 1 j 弧 丫 r 丫忑 叉 2 2 n 2 n 一1 一 一 点 丫 丫尚 h l 烹t f j 二 a乒格i 格j v qe 融 ll i l 群三恐黑1 2 j u n l l t t 了 v 1 一 图2 6 c 对南方向的平移 情况三 最佳整像素点位于预测中心4 5 角方向上 由于s d s p 不能直接向对角方向平移 因此每向对角方向平移一步需要一次水平平移 和一次垂直平移 而d s 中的l d s p 则可以向对角方向直接平移 如图2 6 c 所示 表 2 2 是两者找到最佳整像素点所需平移的次数及搜索点数 从表2 2 中可以看到 当最佳整 像素点位于预测中心4 5 角方向上 并离预测中心水平和垂直距离都为n 时 既绝对距离 为 2n 时 s d s p 平移的次数和情况二中绝对距离为2 n 时的一样 需要平移2 n 步 搜索 的点数也需要6 n 5 点 可见 s d s p 在对角位置上的搜索效率比较低 每像素距离搜索的 点数达到 6 n 5 2n 点 而d s 中的l d s p 在距离为4 2 1 1 的对角方向上平移的步数虽 然也和情况二中距离为2 n 时的一样 但搜索点数却大大降低 只需3 n 1 3 点 每像素距 1 9 浙江大学硕士学位论文 离需要搜索的点数为 3 n 1 3 m 虿n 点 因此 当对角上的绝对距离大于等于3 个像素点 距离时 d s 的搜索效率将超过s d s p 表2 2 对角平移方式下的平移次数和搜索点数 最优点离预测的中 搜索模式菱形平穆的次数 总搜索点数 心距离 x 归 n l n d s l d s p s d s p 9 3 n 4 3 n 十1 3 或伍y 净 n n 1 s d s p2 n 15 2 n 1 3 6 n 2 d s l d sp 心d s p 9 3 n 4 3 n 1 3 伍y 1 1 n s d s p2 n5 2 n x 3 6 n 5 墨y n l n d s l d s p s d s p 9 3 n 4 3 n 1 3 或 x y n n 1 s d s p2 n l5 2 i l 1 x 3 6 n 8 情况四 最佳整像素点与预测中心成一定角度但不等于4 5 在这种情况下 s d s p 和d s 的搜索效率都将介于情况二和情况三之间 为了比较s d s p 与d s 的搜索效率 本文统计了四个具有不同运动特性的测试序列的运 动矢量分布情况 以 l 2 6 4 的一个实现软件1 r 2 6 4v 0 1 0 3 9 为测试平台 采用全搜索算法 七种块大小 l 4 像素精度的运动补偿 运动搜索范围为 一1 6 1 6 各编码1 5 0 帧 测得 以上四种情况所占的比例如表2 3 所示 从表中可以看到 大多数情况下 最佳整像素点 都位于预测中心 其次是位于预测中心的水平或垂直方向上 而其它两种情况所占的比例 很少 表2 3 还给出了在情况二中 最佳整像素点和预测中心距离大于等于9 的情况占情 况二中的比例 可见 这种情况发生的概率很低 因此结合前面的理论分析 本文认为只 使用s d s p 比d s 中使用两种搜索模式的效率高 裹2 3 各种情况所占的比例 c a r d h o n ec l a i m s 吡 em v o r 情况一 8 0 5 9 0 6 8 4 6 8 6 7 情况二 1 6 8 9 0 1 2 3 1 1 1 情况三 0 7 0 0 3 0 7 o 5 情况四2 o 0 3 2 1 4 1 6 情况二中 2 0 5 1 1 3 1 8 距离大于等于9 2 0 浙江大学硕士学位论文 2 3 3 基于线性预测的准菱形搜索算法 基于以上两步的改进 本节将提出对d s 的晟终改进算法 基于线性预测的准菱形 搜索 l p p d s l i n ep r e d i c t i o nb a s e dp s e u d o d i 加o n ds e a r c h 算法 2 3 3 1 算法描述 本文提出的l p p d s 算法具体步骤如下 1 见图2 7 先以预测到的搜索中心 假设为c 点 为中心 进行小菱形搜索 记录 该轮中的整像素最优点和次优点的s a d 值 s a d b e s t s a d s e c b e s t 及位置 b e s t p o s s e c b e n p o s 其中中心点位置记为一1 左 右 上 下分别记为o 1 2 3 2 查看最优点位置 当最优点位于搜索中心 c 点 则停止整像素搜索 转到分像素搜索 当最优点不位于中心 假设位于c 点 则继续第3 步 3 查看次优点位置 当次优点位于中心 c 点 时 求出最优点与次优点连线方向上的点 假设为r 点 的s a d 值作为下一轮搜索中心的线性预测值 s a d p r e d s a d r 预测位置p r e d o s 1 当次优点不位于中心 假设位于t 点 时 则求出离最优点和次优点最近的 假设 为t 点 点处的s a d 值作为下一轮搜索中心的线性预测值 s a p p r e d s a d t 预 测位置p r e d p o s 2 注意 这里只考虑最优点和次优点相邻的情况 对于最优点和次优点之间隔着中心 点的情况在实际序列里占的比例极少 这里不予考虑 4 比较s a d p r e d 与s a d b e s t 当s a d r e d s a d b e s t 则表示预测成功 将搜索中心直接移至p r e q p o s 进行 下一轮小菱形搜索 而跳过以上一轮最优点 c 点 为中心的一轮搜索 反之 则表示预测不成功 将搜索中心移至上一轮最优点 c 点 进行小菱形搜索 这时只需再搜索其它两点 5 返回第2 步继续搜索直到找到全局最优整像素点为止 2 3 3 2 次优点的更新 运用以上算法在每个新的一轮搜索开始前都需要更新次优点位置及其s a d 值 为了 使算法实 x 浙江大学硕士学位论文 2 4 本章小结 运动估计是h 2 6 4 编解码器中的主要耗时模块 为了满足实时应用的需求 已有多种 快速运动矢量搜索算法被提出 其中沿块匹配误差梯度下降方向搜索来减少搜索点数的快 速算法最为高效 也是目前研究最多 应用最广的 同时 更高像素精度的运动补偿使得 分像素运动搜索的计算时间大大增加 但是目前主要的一些快速分