97匹配运动估计的流水线结构及其FPGA实现

中南民族大学 硕士学位论文 基于四步搜索块匹配运动估计的流水线结构及其FPGA实现 姓名：吴平 申请学位级别：硕士 专业：生物医学 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 指导教师：陈心浩 20070524 中南民族大学硕士学位论文 I 摘 要 运动估计是视频信息处理中的关键技术 主要目的是获取视频图像的运动信息 实现视频信息的压缩 然而 在视频压缩编码系统中运动估计的计算量占整个系统计 算量的60-80% 其实现算法直接影响到系统的效率 因此寻找实现简单 快速 高效 的运动估计算法成为视频信息处理领域的一个研究热点 由于基于块匹配的运动估计 容易实现 从而被大多数视频编码国际标准所采用 其中全搜索是一种最简单 最直 接的块匹配算法 但该算法的计算量太高很难满足实时视频处理要求 从而导致了很 多快速块匹配运动估计算法的出现 在这些算法中 四步搜索算法充分考虑了真实的 视频序列中运动矢量的中心偏置特性 从而提高了运动估计的搜索速度和搜索质量 虽然目前研究者提出了一些四步搜索算法的硬件实现 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 但这些方法所需要的硬件 资源较多 数据复用率低 因此寻找有效的实现方法成为研究者的主要任务 针对这 些问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 从算法到硬件实现的角度进行了运动估计硬件结构的研究 本文 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了实现全搜索算法的各种脉动阵列结构以及部分快速搜索算法的硬件 实现结构 发现了脉动阵列虽然能获得很高的吞吐率 但其计算处理会出现较长的延 迟时间 给实际应用带来很多问题 因此不能直接用于快速搜索算法 为了实现四步快速搜索算法硬件结构中对数据流重用 提出了一种新的流水线结 构 该结构利用搜索点之间的候选区数据重叠的特征 将多个搜索点计算重复使用的 数据放在移位寄存器组中 从而实现数据重用 减少对数据的重复访问 加快了处理 速度 满足实际应用要求 根据新的流水线结构 提出以处理单元计算中断 冗余计算消除等技术为基础的 四步运动估计搜索算法硬件实现方法 通过寄存器与处理单元的有效配置 有效地实 现数据行 列复用 从而减少了硬件资源的开销 降低了系统的功耗 本文以现场可编程门阵列(FPGA)为实现平台 通过自上而下的设计方法 实现了 四步搜索块匹配运动估计算法 通过对系统的仿真结果分析 验证了本文提出的方法 与传统的方法相比减少硬件资源 减少43.5%至63.2%的存储器访问次数 从而进一步 表明本文建议的方法是有效的 关键词 块匹配 运动估计 四步法 流水线结构 现场可编程门阵列 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 II A b s t r a c t Due to the fast development of communication technique, transmission of a video sequence has been emphasized in the near future. Considering the limited channel bandwidth and real-time process requirement, it is necessary to apply efficient video source and high compression ratio coding method. Motion estimation is the key technique of video coding which can reduce the temporal redundancies of sequences to make compression efficient. For motion estimation accounts for about 60 to 80 percent of the whole encoding computation, it is the most challenging research topic in video encoding. Block matching motion estimation is relatively simple and can be easily realized, and is adopted by current international video coding standards. As the most direct and simplest motion estimation algorithm, full search (FS) has much high computation complexity and is difficult to be integrated into real time video encoding systems. Many fast block matching methods have been proposed to decrease computation load. Among these algorithms, according to the center biased of the motion vectors distribution, four-step search (4SS) algorithm produces better performance. Because of halfway-stop, it is very efficient to catch small motions appearing in stationary and quasi-stationary blocks. A few implementations of a 4SS motion estimator are proposed in the open literature. The architectures reduce the overall latency at the expense of more area. Furthermore, they do not reuse date effectively to reduce memory accesses. Due to these problems, the research of motion estimation architecture is mainly based on the motion estimation algorithm and its efficient implementation. This paper sums all kinds of systolic array architectures for FS block- matching motion estimation and some appropriative hardware structures based on fast block matching methods. Although the systolic array can attain very high throughput, the latency delay is long. Parallelism is very high requested to algorithm, so a direct implementation of the systolic array suffers latency problems due to the step-dependence problem for fast block matching methods. This paper presents an innovational pipelined architecture for 4SS block-matching motion estimation. The proposed architecture exploits the overlap of candidate area data among the search points. It successively reuses data to reduce memory accesses by using 中南民族大学硕士学位论文 III registers nearby processing elements (PE) and speed the processing speed with the pipeline and parallelism. An efficient implementation of the 4SS model is developed using the new structure. It has few PE numbers and reduces the control overhead. Half-stop and removing redundant calculations techniques are also developed to reduce PE operations. Optimizations are measured by reduction of power consumed by the block or in reduction of memory accesses that occur during the operation. Memory accesses reduction by the proposed architecture varies from 43.5% to 63.2% as compares with the existing 4SS architecture. It produces efficient solution for real-time motion estimation required in low bit-rate video applications. The architecture was implemented with field programmable gate array (FPGA) device as the target device verifying its functionality. Key words: block matching, motion estimation, 4SS, pipelined architecture, FPGA 中南民族大学 学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任何其 他个人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡献的个 人和集体 均已在文中以明确方式标明 本人完全意识到本声明的法律后果 由本人承担 作者签名 日期 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查 阅和借阅 本人授权中南民族大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存和汇编本 学位论文 本学位论文属于 1 保密 在______年解密后适用本授权书 2 不保密 请在以上相应方框内打 作者签名 日期 年 月 日 导师签名 日期 年 月 日 中南民族大学硕士学位论文 1 第 1章 绪论 1.1 研究背景 1.1.1 运动估计研究的必要性 信息技术发展日新月异 尤其是以视频为主要信息来源的数字视频通信越来越受 到人们的重视 数字视频通信应用范围涉及视频监护 远程医疗 视频点播 可视电 话 视频会议和其它形式的视频娱乐和教育等 数字视频通信相对模拟信号视频有很 多的优点 如它可以中继传输和多次复制 不会造成噪声和非线性失真的累积 便于 进行加密 便于用超大规模集成电路 Very Large Scale IC VLSI 芯片实现等[1] 然而 数字视频信号因其对带宽要求高而使得传输和存储都变得非常昂贵甚至极 其困难 从传输角度看 一路广播级彩色数字电视 若按 4 2 2 的分量编码标准 格式 Y U V为 4 2 2 Y为亮度信号 U V为色差信号 用 13.5/6.75/6.75MHz 频率采样 每像素用 8位编码 数码率为 I= 13.5+6.75+6.75 8=216Mb/s 若以 64kbps 的数字话路进行实时传送 需占用 3375 个数字话路[2] 从存储角度看 存储 一小时未经压缩的如上例所述的电视节目需要的存储空间为 97GB 而对于高清电视 图像分辨率为 1280 720 每秒传输 60 帧 一小时未经压缩的电视节目需要的 存储空间为 597GB 这样的数据量是惊人的 由此可见 如果不对数字视频信息进行 压缩 无论是其传输或存储都很难实用化 静止图像具有空间相关性 视频是由许多 幅静止图像按时间序列构成的 每一幅图像称为一帧 frame 它除了具有空间相 关性 帧内 外 还具有时间相关性 帧间 视频压缩即是在时域 空域及频域 变 换域 描述图像的相关性并根据人类视觉特点 去掉空间相关性和时间相关性 信息 冗余 使大部分数据变为零 从而用较少的有值数据有效地表示视频 进而利用信 息编码理论 熵编码 对这些零值数据和有值数据进行的数据压缩[3] 运动估计技术 是减少视频图像帧间冗余信息的最具代表性技术 许多视频图像编码压缩国际标准 如 H.261 H.263 H.264 MPGE-1 MPEG-2 MPEG-4等均采用了运动估计算法[4] 1.1.2 运动估计研究的方法 根据人类视觉系统的特点 人眼对图像的静止部分要求具有高的空间分辨率和较 低的时间分辨率 而对运动部分恰好相反 为了利用以上视觉特性 可将视频图像分 为静止部分和运动部分 对相邻帧之间在时间上的相关性进行帧间预测 对于静止部 分可重复使用前一帧数据 对于运动部分需要设法测定其位移量 根据该位移量进行 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 2 运动部分预测 在预测的过程中需要将位移信息传递下去 并以该位移改善运动部分 的帧间预测结果 构成完整的图像 故称运动估计补偿预测 运动估计的方法较多 如光流场估计的方法[5] 贝叶斯方法 像素递归法和各种 块匹配法[6-14] 光流场估计的方法依据时空图像的亮度梯度得到一个光流场的估计 对于灰度图像 光流场要与合适的时空平滑约束条件联合使用 要求位移矢量在附近 区域缓慢变化 像素递归法是预测校正型的位移估计器 预测值可以作为前一个像素 位置的运动估计值 或作为当前像素领域内的运动估计线性组合 依据该像素上的位 移帧差的梯度最小值 对预测作进一步的修正 在实际编码过程中 单个像素点难以 代表图像的具体内容 像素值相同的像素点并不一定是相同的像素内容 且像素递归 法存在收敛速度慢的问题 块匹配算法 Block Matching Algorithm 是最实用和先进 的运动估计的方法 目前几乎所有的视频编码标准在实际中都采用了块匹配算法 块 匹配算法基本思想如下 把图像帧划分为若干互不重叠的块 宏块 并以块为单位 寻找目标帧中每块 在参考帧 上一帧或者其它帧)中最优匹配的块的相对位置 这个相对位置称为运动 矢量 而参考块和匹配块的差称为残差 因此在视频编码时 不需要对整幅图像进行 处理 而只需要对运动矢量和残差进行编码 这样就可以在解码端恢复参考块的图像 从而达到了压缩的目的 如图 1.1 所示 假设图像中每块的大小为 M×N dxmax 为 参考块水平方向可搜索最大位移 而 dymax为参考块垂直方向可搜索最大位移 那么 基于块匹配的运动估计就是在参考帧(或者其它上一帧)的(M+2dxmax)×(N+2dymax) 候选区搜索窗口中找到和目标帧的当前大小为 M×N的块的最匹配的块 则参考块的 运动矢量可用如下的数学公式描述 ( , )MV Vx Vy= {( , ) | ( ( , ), ( , )) ; [0, 1], [0, 1], [ max, max 1], [ , max 1]} k k ix y R f m n f m x n y Max m M n N x dx dx y dymax dy −= + + = ∈ − ∈ − ∈ − − ∈ − − 1.1 式 1.1 中 R 表示相关性评价函数 i 为整数 可正可负 分别称为前向运动估 计和后向运动估计 一般情况下 i为 1 在论文的后续部分我们只考虑这种情况 因 为人眼对灰度比较敏感 而且灰度反映了运动的信息 所以匹配时只考虑视频帧图像 的灰度值 ( , )kf m n 表示目标帧图像的灰度值 ( , )k if m x n y− + + 表示参考帧图像的灰 度值 x, y的精度越高匹配的越好 但是高精度必然带来高复杂度 目前标准中支持 到 1/8的象素精度 在本文的讨论中 我们以整象素精度为例 1.2 研究目的及意义 H.26X和MPEG-X系列标准大都采用了基于运动补偿的帧间预测和DCT变换相结 合的混合编码方法 即通过帧间预测减少时域冗余 通过DCT变换减少空域冗余 这 中南民族大学硕士学位论文 3 种混合编码方法具有压缩比高 算法复杂度低的优点 在视频通信中得到广泛的应用 其中 基于运动补偿的帧间预测编码可以大大减少时间冗余度 从而提高编码效率 基于运动补偿的帧间预测编码主要包括运动估计和运动补偿两部分 其中 运动估计 在帧间预测编码中占据大部分运算时间 而且运动估计的精度直接影响帧间预测编码 的效率 实现MPEG-2SP@ML simple profile @main level 的编码器时 编码器总共 运算量约为3.7GOPS(十亿操作每秒) 其中运动估计的计算量为2.26GOPS 占到了编 码器总共运算量的60%[15] 如此大的计算量用软件实现是相当困难的 远远不能满足 实时编码的要求 必须设计高速专用硬件系统才能完成该任务 因此 研究能够实时 实现视频压缩编码的运动估计的硬件结构对于视频压缩编码的研究与实现具有重要 意义 目标帧 参考帧 参考帧 dymax dxmax 搜索区域 x,y)M N x,y)M N x,y)M N 运动矢量(Vy,Vx) 图1.1 运动估计块匹配算法示意图 实现运动估计的算法较多 从硬件实现角度看 全搜索算法是首选算法 因为它 具有规则的数据流和固定的运算次数 非常适合于要求连续和规则数据流的脉动 Systolic 阵列[16]实现[17-36] 但是 由于全搜索算法的运算量极大 这种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的运动 估计器需要庞大的处理单元 Processing Element PE 阵列才能达到实时编码所要求 的速度 以三步法为代表的快速搜索算法的运算量相对全搜索算法显著降低 但是它 们通常由多步构成甚至计算步骤不固定 相邻两步之间只能顺序执行 因此算法的并 行性下降 要求硬件不仅具有高的吞吐率而且延滞时间小 脉动阵列虽然能达到很高 的吞吐率 但是延滞的时间长 对算法的并行性要求很高 不能直接用于快速搜索算 法 因此 人们提出了针对快速搜索算法的一些专用的硬件结构[37-58] 这些结构都是 通过有效地重用数据来减少外部存储器的访问 并且通过高度并行处理和流水线来加 快处理速度 目前这些结构都是在某些方面具有优势 而不能说哪一种结构具有绝对 的优势 只能在满足某种应用的情况下 寻找一个比较好的结构 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 4 1.3 本文主要工作 本文工作主要是针对低码率视频应用,提出了一种新的使用四步搜索算法的运动 估计流水线结构并针对新结构提出了一个简单 实用的运动估计模块 完成硬件结构 设计 并通过对标准测试序列的仿真证明我们设计的结构能够有效地实现四步搜索 法 具体来说本文工作主要包括以下几个方面 1. 对运动估计领域进行了较为广泛和深入的学习 分析了运动估计的必要性 学习了运动估计的研究方法 2. 详细介绍了基于块匹配运动估计的各种搜索算法 比较了各种算法的优缺点 3. 分析了实现全搜索算法和其它快速搜索算法的一些硬件结构 4. 针对四步搜索法 分析了算法的数据流 提出了一种新的硬件结构 用硬件 描述语言完成了该算法的寄存器传输级 Register Transfer Level RTL 设计 给出 了仿真实验结果 并对其进行了性能分析 1.4 本文组织结构 全文共分为五个章节 主要内容如下 第一章绪论 概括的介绍了运动估计研究的必要性 运动估计的研究方法 阐明 了研究运动估计硬件结构设计的目的及重要意义 为本文的研究提供理论基础 并介 绍了本文的主要工作及组织结构的安排 第二章首先介绍了块匹配准则 接着详细介绍了用于块匹配运动估计的几种典型 搜索算法 并对全搜索算法和部分快速搜索算法的性能进行了分析 第三章分析了实现全搜索算法和其它快速搜索算法的硬件结构 第四章针对四步搜索法提出了一种新的硬件结构 完成了模块设计 第五章给出了本文所设计硬件结构的仿真测试结果 并对其进行了性能分析 中南民族大学硕士学位论文 5 第 2章 运动估计算法分析 2.1 引言 运动估计是视频压缩编码技术中的关键部分 对于通信 存储和广播等领域来说 其实时性是非常重要的 如何在保证匹配质量的基础上实现实时的运动估计 选择一 个合适的算法是非常关键的 本章介绍了各种块匹配算法并对算法的性能进行了分 析 2.2 块匹配准则 在视频编码过程中 运动估计的估计精度 匹配运算复杂度 数据读取复杂度和 内存管理复杂度取决于所采用的匹配准则[14] 运动估计算法中常用的匹配准则有如下 几种 归一化互相关函数 NCCF 最小均方误差 WSE 最小绝对差 MAD 和 绝对差和 SAD 1. 规一化相关函数 1 1 1 1 / 2 1 / 2 2 2 1 1 1 1 1 ( , ) ( , ) ( , ) ( , ) ( , ) M N k k m n M N M N k k m n m n f m n f m x n y f m n f m x n y N C C F x y − = = − = = = = + +    + +          ∑ ∑= ∑ ∑ ∑ ∑ 2.1 在这种准则下 R(x,y)=NCCF(x,y) 2. 均方误差 [ ]21 1 1 1 ( , ) ( , ) ( , ) M N k kMN m n MSE x y f m n f m x n y− = = = − + +∑∑ 2.2 在这种准则下 R(x,y)=1/ MSE(x,y) 3 均绝对差 1 1 1 1 ( , ) ( , ) ( , ) M N k kMN m n MAD x y f m n f m x n y− = = = − + +∑∑ 2.3 在这种准则下 R(x,y)=1/MAD(x,y) 有些文献中 MAD(x,y)演变为绝对差和 ( , ) * ( , )SAD x y MN MAD x y= 1 1 1 ( , ) ( , ) M N k k m n f m n f m x n y− = = = − + +∑∑ 2.4 在上述匹配准则中 由于 SAD只采用了加法和绝对值计算 便于计算和硬件实 现 而且它的匹配精度与其它三种相差不大 所以大多数算法采用了 SAD匹配准则 本文的设计也选用了 SAD准则 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 6 2.3 运动估计算法 2.3.1 全搜索及其改进算法 到目前为止 人们已经提出了许多最优匹配的搜索算法 其中最简单可靠的是全 搜索算法 全搜索法 Full Search FS)也称穷尽搜索法 是对搜索范围内所有的可能 候选位置计算SAD值 从中找出最小的SAD 其对应偏移量即为所求运动矢量 全搜 索法是穷尽法 在搜索区域内的每一个位置都要被检测到 因此其最大优点是可以保 证全局最优 达到最高的搜索精度 但是 正因为它是穷尽搜索 因此会产生巨大的 计算量 如[ 7 7]的搜索区间 每个宏块 16*16 需计算225个SAD 对于QCIF 176*144 格式的图像 每帧有99个宏块 为此进行一帧运动估计需执行22275次SAD 计算 根据H.263试验统计 如采用全搜索法 运动估计将占到整个编码时间的 50%~80% 这就直接制约了编码的实时实现 后来人们对全搜索算法进行了改进 提出了快速全搜索算法 快速全搜索是属于无失真的 比较典型的两种算法是部分失真算法(PDE)和连续 消除算法(SEA) [17] PDE算法的基本思想是如果当前SAD的计算过程中, 部分SAD的 值已经超过了以前记录的最小SAD, 那么立即终止当前SAD的计算, 进入下一个搜索 点的计算 这种算法的关键是以合适的计算顺序尽快找到一个比较小的SAD,这样就 可以减少更多的计算 SEA算法得到了大量研究,进一步发展到多级连续消除算法 (MSEA) 其主要思想是利用不等式 a b a b+ ≤ + , 其中a, b R, 可以得到 0 0C R SAD− ≤ , 其中C0,R0,是参考块和候选区块的和范数 即 ( )1 10 0 0 , N N i j C a i j − − = = = ∑∑ ( )1 10 0 0 , N N i j R b i m j n − − = = = + +∑∑ 如果一个匹配块满足 0 0 minC R SAD− ≥ 将不是一个好的匹配 块 因此不等式提供了一个边界 在彻底计算匹配误差时过滤掉一些匹配块 这称为 SEA SEA算法的效率依赖快速计算每个块的和范数和一个好的初始运动估计 需要 开发一个快速计算和范数的方法 利用相关性减少计算复杂度从避免多余SAD计算 SEA方法是通过不断计算SAD来限制计算SAD的计算量 这些快速全搜索算法虽然相比全搜索算法计算量有所减少 但本质上还是一种穷 尽搜索法 其计算量仍是相当巨大的 因此一些快速搜索算法相继提出 通过改变搜 索模式来减少搜索点从而达到减少运动估计的计算量 2.3.2 快速搜索算法 2.3.2.1三步法 三步法[7] Three Step Search TSS 是应用得相当广泛的一种次优的运动估计搜 中南民族大学硕士学位论文 7 索算法 它的搜索区间一般为[ 7 7] 即在候选区中与编码块相同坐标位置处为 原点 将参考块在其上下左右距离为7的范围内按照一定规律移动 移到一个位置 就做匹配计算 它总共进行了三步搜索 在下一次搜索时 步长减半 以前一步搜索 得到的最优点为中心 图2.1为三步法的搜索示意图 具体搜索过程如下 图2.1 三步法搜索示意图 第一步 以参考块为中心 以搜索区间的一半为步长 步长为4 搜索以原点 0 0 为中心的中心和外围8个方向共9个搜索点所对应的SAD 这9个搜索点构成 了正方形搜索模板 在图2.1中对应为L0-L8 根据最小SAD的值确定下一步搜索窗口 的中心 第二步 以第一步中求得的最佳匹配点为中心 步长为2 搜索新搜索窗口中心 的外围8个方向共8个搜索点所对应的SAD 根据最小SAD的值确定下一步搜索窗口的 中心 第三步 以第二步中求得的最佳匹配点为中心 步长为1 搜索新搜索窗口中心 的外围8个方向共8个搜索点所对应的SAD 根据最小SAD的值确定所要找的最佳匹配 点 该点与参考块中心的偏移量即为所估计的运动矢量 2.3.2.2 新三步法 TSS假定运动矢量分布特点是在搜索窗口中均匀分布, 但事实证明运动矢量是偏 置中心的,Renxiang Li等人在TSS的基础上提出了一种增强运动矢量中心偏置搜索和 减小补偿误差的新三步法[8] New Three Step Search NTSS 其效果较好 如图 2.2 所示 具体步骤如下 第一步 在原有 TSS第一步 9个搜索点的基础上增加中心区域的 8个搜索点 这 8个搜索点是与中心点相邻的 8个点 第二步 如果第一步 SAD 最小点出现在中心位置 则算法停止 我们称之为一 步停 如果第一步 SAD最小点出现在中心点的 8个领域位置 则以最小 SAD为中心 计算其 8个领域位置对应的 SAD值 找出最小 SAD 算法终止 我们称之为二步停 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 8 如果第一步 SAD最小点出现在 8个边界位置上 则第二步和第三步均与 TSS相同 图 2.2 新三步法搜索示意图 2.3.2.3 四步法 四步法[9] Four Step Search 4SS 由Po Lai-man Ma Wing-chung等人提出 改 三步法的9 9搜索窗为5 5 算法搜索过程如图2.3所示 具体步骤如下 图2.3 四步法搜索示意图 第一步 计算以起始点 0 0 为中心的5 5搜索窗口上的9个搜索点所对应的 SAD值 如果最小SAD点出现在窗口中心 转第四步 否则 继续 第二步 搜索窗口保持5 5大小 但搜索模板依赖于最小SAD出现的位置 如 果最小SAD点出现在窗口四角 要增加五个搜索点 如果最小SAD出现在四边的中 心 要增加3个搜索点 如果最小SAD点出现在窗口中心 转第四步 否则 继续 中南民族大学硕士学位论文 9 第三步 搜索模式与第二步相同 但最后要转第四步 第四步 搜索窗口缩小为3 3 计算8个搜索点所对应的SAD值 SAD最小点即 为最佳匹配点 图2.3中的箭头分别指示了搜索运动矢量 3 -7 和 -7 7 的搜索路径 2.3.2.4 菱形搜索法 Shan Zhu Kai-kuang Ma等人提出了菱形搜索法[10,11] Diamond Search DS 该算法继承了梯度下降法的一个基本假设 全局的最小误差点在搜索中心的邻域内是 单调失真的 它与梯度下降法的最大不同就是搜索策略的不同 菱形搜索法采用两种 搜索模板 分别是有9个搜索点的大菱形模板 Large Diamond Search Pattern LDSP 和5个搜索点的小菱形模板 Small Diamond Search Pattern SDSP 如图2.4所示 菱形法搜索时先采用LDSP计算 当最小SAD点出现在中心点处 将LDSP换为SDSP 再进行匹配计算 这时5个点中SAD最小点即为最优匹配点 否则 改变中心点的位 置 仍用LDSP重复计算 图2.5中箭头指示了寻找运动向量 -4 -2 的搜索过程 (a)大菱形模板 b 小菱形模板 图2.4 菱形法的两种搜索模板 图2.5 菱形法搜索示意图 2.3.3 快速搜索算法性能分析 在所有的快速搜索算法中, 三步法因为简单和有效性是最流行的,特别适合低码 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 10 率视频应用, 如视频会议和视频电话 真实的视频序列中, 运动向量是中心偏置的 为了开发这种特性, 新三步搜索算法修改了第一步的检查点模式, 通过搜索额外的中 心8个点 同时新三步搜索算法使用了中途停止技术(halfway-stop)加速静止块的搜 索 该方法保持了三步算法的简单 规整性,运动补偿误差和鲁棒性比三步法更好 另一种使用中心偏置的搜索模式的是四步搜索, 它在第一步搜索中采用一个较小的 5x5网格, 结果该方法对于搜索窗口为7的只需要4步就到达边界检查点 搜索过程基 本上和三步法相同 四步搜索法相比新三步搜索法需要更少的搜索点 这些快速搜索方法, 都是假定块失真度量都是随着检查点远离全局最小而单调 增加 由于基于中心偏置的全局最小运动矢量分布特性,80%的块的运动矢量被看作是 静态的或者准静态 大多数运动矢量都是接近于搜索窗口的中心, 因此假定运动匹配 误差朝着全局最小点是单调降低的 不同形状和尺寸的搜索模式对搜索性能有非常大 的影响 显然用固定搜索模式不能适应运动的复杂性, 如果仅仅从简单的实验角度分 析运动矢量分布的特点, 从而得出结论是不完整的, 最好的方法是自适应选择搜索模 式 三步法假定运动矢量分布特点是在搜索窗口中均匀分布, 但事实证明运动矢量是 偏置中心的,相比三步法 四步法搜索效率更高 而在菱形方法和十字搜索研究中, 证 明运动矢量的分布呈菱形中心分布和交叉中心分布,因此能获得更好的性能, 尤其对 于静态或准静态运动, 该算法已经被MPEG-4验证模型所采纳 这些快速算法的特点 是以某种搜索模式减少搜索点, 根据已搜索的结果, 决定下一步搜索的方向, 逐渐逼 近全局最优 所有以上算法都是基于单峰误差假设, 容易陷入局部最小 这些算法的 优点是简单 规整 易于实现 快速算法发展的趋势是搜索模式更接近真实分布,搜 索窗口尺寸自适应[12,13] 2.4 本章小结 本章首先介绍了运动估计算法中常用的块匹配准则 然后详细介绍了全搜索及其 改进算法和部分典型的快速搜索算法 最后对这些算法的性能进行了分析比较 中南民族大学硕士学位论文 11 第 3章 块匹配运动估计硬件结构 3.1 引言 由于块匹配运动估计算法的运算量巨大 实时地进行运动估计只能在并行和流水 线的处理结构中才有可能实时实现 为提高系统性能常采用的并行处理技术有三类 流水线技术 阵列处理机技术和多处理机技术 流水线技术通过时间重叠来提高效率 利用了时间并行性 阵列处理机用多个同步工作的算术逻辑部件来获得空间并行性 多处理机系统则通过共享资源的相互作用处理机来获得异步并行性 阵列处理机和多 处理机系统都通过多个处理单元来提高运算能力 流水线结构的特点是把整体运算划 分为若干部分 各部分在同步时钟控制下依次运算 从而提高数据的吞吐率 提高系 统处理能力和硬件利用率 此外 在块匹配运动估计中 数据量巨大 通信带宽大 解决方法有使用片上存储器作为缓冲 合理地配置数据 利用片上存储减少带宽需求 允许并行访问数据 而没有数据冲突 保持数据的局部性对于高性能计算至关重要 从块匹配运动估计的算法而言 有两个基本的标准选择适合硬件实现的算法 其一 算法必须是一个鲁棒的方法,即只需要几个搜索点就可以找到真正的运动矢量 其二 算法必须包括规整的数据流计算和固定的计算步骤 因而适合低价 高速的硬件实现 3.2 全搜索运动估计硬件结构 从硬件实现角度看 全搜索算法是首选算法 因为它具有规则的数据流和固定的 运算次数 非常适合于要求连续和规则数据流的脉动阵列实现 脉动阵列限定数据只 在相邻处理单元之间交换 除了时钟信号是全局的 其它信号都是局域的 由于每个 数据源的负载减小 因此时钟频率可以提高 即处理速度可以提高 但是 由于全搜 索算法的运算量极大 这种方案的运动估计器需要庞大的处理单元阵列才能达到实时 编码所要求的速度 文献[19]设计并实现了第一个运动估计器 该结构的特点是每个PE完成一个固 定搜索点的计算 该结构的优点是通过广播参考像素使参考像素得到重用 大大减少 存储带宽需求 缺点是该结构是一维数据重用 还有很大冗余 文献[22]利用脉动阵 列设计方法学设计了一个两维的脉动阵列结构 其基本处理单元与yang类似 完成相 同的功能 即每个处理单元完成一个搜索点的SAD的计算 不同的是具有两维数据重 用 因此存储访问带宽进一步减少 文献[25 26]提出了一种一维的脉动结构 但是 完成了两维数据重用 该结构与以上两种的区别是广播候选像素 而不是参考像素 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 12 另外是用了多一倍的寄存器来传播候选像素 文献[27]结构使用了一个片上行缓冲来 解决输入带宽问题 该结构的特点是参考像素被存到处理单元中 传播寄存器用于传 播候选像素 候选像素可以有上 下 右三个方向移动 计算过程是首先每个处理单 元计算部分行SAD 部分行SAD在水平方向被传播和累加 加法树用于累加所有行 SAD构成完整的SAD 其缺点是寄存器太多 文献[28]通过脉动阵列映射方法学设计 了一个结构 该结构的特点是当前像素被存到相应的处理单元中 候选像素通过被水 平的传播 列SAD在垂直方向被累加和传播 最后列SAD在水平方向传播和累加形成 一个完整的SAD 该结构优点是不需要行缓冲 很明显的缺点是需要大量的并行访问 存储器 为了进一步减少访问存储器的引脚数量 文献[29]结构使用了行延迟线 这 样允许候选像素串行输入 基本的计算原理如下 首先列部分SAD被传播和累加 最 后所有列SAD被一个加法树在一个周期内完成 这个结构的缺点是需要装载候选像素 的延迟较大 另外使用了大量的传播寄存器来减少内存带宽 文献[35]用六边形图形 的方式比较这些结构 指出了各自的适用性及局限性 3.3 快速搜索运动估计硬件结构 以三步法为代表的快速搜索算法的运算量相对全搜索算法显著降低 但是它们通 常由多步构成甚至计算步骤不固定 相邻两步之间只能顺序执行 因此算法的并行性 下降 要求硬件不仅具有高的吞吐率而且延滞时间小 脉动阵列虽然能达到很高的吞 吐率 但是延滞的时间长 对算法的并行性要求很高 不能直接用于快速搜索算法 因此 人们在脉动阵列结构的基础上进行改进 提出了一些专门针对快速搜索算法的 硬件结构 3.3.1 三步法运动估计硬件结构 有关三步法的硬件结构的文献比较多[37-51,56,57] 这些结构都是通过有效地重用数据 来减少外部存储器的访问 并且通过高度并行处理和流水线来加快处理速度 一些结 构使用了一维的脉动阵列结构 [37,40,41] 由于算法步骤的依赖性 文献[37]的结构延滞 时间较大 针对此问题文献[40,41] 提出了两种可供选择的解决方法 文献[40]提出 对于算法中的每一个点检测三个点 通过增加额外的点来增加精度 以较少的计算代 价增加精度来弥补延时 文献[41]在SAD累加和比较结构中采用树型结构来减少整体 延时 代价是增加了硬件开销 一些专用平行结构更有效地应用了三步法[42-45,47] 文献[42]仅用了3个PE单元 使 用了移位寄存器组重用当前像素 减少了存储带宽需求 硬件资源消耗最小 不足在 于该结构是一维数据重用 还有很大冗余 且延时较大 对于一次块 16*16 运动 估计需2976个时钟周期 文献[44]使用了9个PE单元平行地计算搜索窗内9个点 9个 PE单元分别从9个存储器单元中读取数据 而装载至各个存储器单元中的数据则由存 中南民族大学硕士学位论文 13 储器地址生成系统根据不同的算法步骤来控制分配 文献[43]提出了能使用3-PE 9-PE和27-PE的平行结构族 每套PE处理搜索窗中的一行 通过增加存储器带宽 多 套PE可以同时处理整个搜索窗中的9个点 9-PE 或更大的搜索区 可编程的延时单 元 即可变结构的移位寄存器组 用来保证结构的平行性 其标准的9-PE结构一次块 16*16 运动估计只需768个时钟周期 该结构克服了三步法数据流的不规则形使得 处理效率接近100% 并且其模块化的结构可以方便地组合成更大搜索区的运动估计 器 所以文献[43]的结构最为流行 还有一些结构使用了一种网状结构 解决了平行性与高延时的问题[46,48] 在这种 结构中 9个PE单元相互联接成网状 每个PE单元与它相联的4个PE单元保持数据联 系 每个PE没有直接进行256次计算来得到SAD值 而是每个PE将16次计算后的中间 结果传给相联的PE单元 通过适当的存储器配置 每个PE与指定的存储模块相联 9 个SAD值在256个时钟周期后得到 文献[50]将文献[43]中结构改进用于新三步法 使其速度能够满足高清电视 HDTV 的速度要求并且在速度与硬件开销之间取得了很好的折衷 3.3.2 四步法运动估计硬件结构 使用了中心偏置搜索模式的四步法相对三步法搜索效率更高 然而有关四步法结 构的文献不多[52-54] Wu提出的结构具有一定的代表性[52] 如图3.1所示 3*N的PE单 元构成一个2维的脉动阵列 N为块高 16*16的块 N=16 每列PE计算出1个SAD 一次完成搜索窗中一行3个点的SAD计算 通过可编程延时单元配置当前参考块数据 流 即当前参考块像素在相邻PE之间延迟2个 或1个时钟 根据搜索窗的大小为 5*5 或3*3 来决定 算法每步所需的最大时钟周期为 第一步 或第二步 第三步 需要 N+4 *3+N-1个时钟 第四步需要 N+2 *3+N-1个时钟 Wu的结构延时小, 实现了行数据复用,消除了四步法第二步 第三步中的重复点的计算 降低了功耗 但该结构使用了较多的硬件资源 数据带宽较大 数据装载控制复杂,未实现列数据 复用 3.3.3 其它快速搜索运动估计硬件结构 对于菱形模板类搜索算法来说 由于其搜索点成菱形分布而导致数据重用和存储 器访问次序完全不同于全搜索算法和以前的快速搜索算法[55,58] 从存储成本或者存储 器访问模式来看 现有硬件结构不能用来实现菱形模板类搜索算法或者实现的效率不 高 其中 树形运算结构虽然可以用来实现菱形模板类搜索算法 但是不能利用相邻 搜索点之间的数据重叠的特征 从而导致大量的存储器访问操作使功耗大大增加 文 献[55]提出了一种基于移位寄存器阵列的硬件结构 可以有效地实现菱形模板类搜索 算法 文献[55]提出的数据流利用搜索点之间参考帧数据的重叠来减少存储器访问操 作 从而减少了运动估计中功率消耗最大部分的操作 但该结构基于这样一个观点 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 14 在视频压缩的运动估计的硬件实现中 存储器访问操作是代价最高的操作 然而大量 移位寄存器的使用加大了系统延时 而时钟频率的提高 必将增加本结构含有时序部 件的这部分电路的功耗 对应用有所限制 并对实现这结构的设计提出更高的要求 PE PE PE VDU VDU PE PE PE VDU VDU PE PE PE VDU VDU PE PE PE VDU VDU ACC ACC ACC Controller and Address Generator PE Array 1 PE Array 2 PE Array 3 Data_Can1 Data_Ref1 Data_Can2 Data_Ref2 Data_Can3 Data_Ref3 Data_Can16 Data_Ref16 图3.1 四步法运动估计硬件结构 3.4 本章小结 本章介绍了全搜索块匹配运动估计硬件结构及三步法 四步法和菱形模板类部分 典型的快速块匹配运动估计硬件结构 并对这些结构性能进行了分析 所有目前这些 结构都是在某些方面具有优势 而不能说哪一种结构具有绝对的优势 只能在满足某 种应用的情况下 寻找一个比较好的结构 中南民族大学硕士学位论文 15 第 4章 一种新的四步法运动估计硬件结构 4.1 引言 上文中曾提到 对于低比特率 小运动视频 四步法相比三步法在搜索效率方面 显得更为高效 四步法的HALF-STOP技术使得它的计算量大大减少 WU提出了一种 基于四步法的有代表性的运动估计结构 该结构在降低功耗上采取了一些措施 但该 结构使用了较多的硬件资源 数据带宽较大 数据复用率不高 控制复杂 本课题设 计针对低码率视频应用,提出了一种新的使用四步搜索算法的运动估计流水线结构并 针对新结构提出了一个简单 实用的运动估计模块 4.2 运动估计模块结构 4.2.1 总体框架 本设计中系统要求 运动估计块大小 16*16 像素 搜索范围[-7 7] 搜索区为 30*30像素 用于运动估计的当前帧参考块及前一帧候选区数据放入片内存储器 图 4.1示意了本次设计的运动估计搜索过程 Motion Vector i j 16*16 Candidate Block Previous Frame 16*16 Reference Block Current Frame 0 0 29 0 29 290 29 pe0 pe1 pe2 pe3 pe4 pe5 pe6 pe7 pe8 Search Order for PEs in 4SS Model 图 4.1 运动估计搜索过程示意图 运动估计模块接口定义如下 对接口详细的描述见表 4.1 entity fss_motion is --运动估计模块 fss_motion接口定义 port (CLOCK, ENABLE, RESET: in std_logic; FINISHED: out std_logic; MVX,MVY: out std_logic_vector(3 downto 0); SAD: out std_logic_vector(15 downto 0)) ; 基于四步搜索块匹配运动估计的流水线结构及其 FPGA实现 16 end fss_motion; 表 4.1 运动估计模块接口 信号 输入/输出 描述 CLOCK Input 模块的全局时钟 对于所有的寄存器 计数器等同步逻辑使用同 一个时钟 ENABLE Input 模块启动信号 低电平时 模块保持当前状态 RESET Input 全局复位信号 高电平时 模块中的所有状态 寄存器 计数器 将复位 FINISHED Output 标志 告知外部控制电路 MVX MVY和 SAD信号是有效的 MVX Output 4bit有符号值 运动矢量在 X方向的值 有效值[-7 7] MVY Output 4bit有符号值 运动矢量在 Y方向的值 有效值[-7 7] SAD Output 16bit无符号值 相应运动矢量MV的 SAD值 CONTROL UNIT COMPARATOR ADDRESS GENERATOR Ref_addr Can_addr Pe0_en RESET ENABLE Reference block (16*16*8 bits ) 9-PE U N ITCandidate Area (32*32*8 bits