Page 300 - 《软件学报》2020年第11期

宋传鸣 等:采用自适应缩放系数优化的块匹配运动估计 3615

(a) Akiyo (b) Vtc1nw

(c) Waterfall (d) Crew

Fig.4 Frame-wise PSNR comparison of Akiyo, Vtc1nw, Waterfall, and Crew sequences
图 4 Akiyo、Vtc1nw、Waterfall 和 Crew 序列的逐帧 PSNR 比较

5.2 计算复杂度分析
本节讨论上述 6 种算法的计算复杂度.设待匹配块的尺寸为 B×B 像素,搜索窗口的尺寸为 W×W 像素.
首先,从处理 1 个宏块的时间复杂度来看:
2
2
• 块匹配全搜索的计算复杂度为 O(B W );块匹配全搜索+自适应缩放系数预测算法需要在全搜索的基
2+
2
2
础上,计算 4 次空域/时域差分、2 次双线性插值和 2 次运动补偿误差,故其复杂度为 O(B W 8B ).
2
2
• 根据文献[57,58],块匹配菱形搜索的计算复杂度约为块匹配全搜索的 7%,即 O(0.07B W );本文算法在
菱形搜索的基础上,还需计算 4 次空域/时域差分、2 次双线性插值和 2 次运动补偿误差,则复杂度约为
2
2+
2
O(0.07B W 8B ).同时,由于本文算法未以边信息的形式传输缩放运动系数,解码端需在块平移运动向
量的基础上计算 4 次空域/时域差分、2 次双线性插值和 2 次运动补偿误差,从而自适应地重建该缩放
2
系数,其复杂度为 O(8B ).
• 由文献[50]的分析可知,基于缩放模型的全搜索 ZFS 需要 3 重循环,并且对于每个候选向量,均要计算 1
2
2
轮双线性插值和 1 轮预测误差,其时间复杂度为 O(2B W zr).而基于缩放模型的快速搜索 3D-ZPDS 的
2
2
计算复杂度则约为前者的 13% [50] ,即 O(0.26B W zr).
其次,表 3 统计了 6 种算法在全部视频序列上的实际运行时间,实验环境为:Intel Xeon(TM) i7-4790CPU@
3.6GHz,16GB 主存,64 位 Windows 10 专业版,集成开发环境为 Visual C++6.0.从表 3 可见,当 B=16,W=33,zr=2 时,