一种用于超分辨率重建的自适应块匹配算法

唐玲, 陈明举

(四川理工学院自动化与电子信息学院, 四川自贡643000)



一种用于超分辨率重建的自适应块匹配算法

唐玲, 陈明举

(四川理工学院自动化与电子信息学院, 四川自贡643000)

提出了一种基于自适应块匹配的超分辨重建算法。首先根据相邻运动块之间的相关性来预测搜索块，然后利用图像的运动特性自适应地选择合适的搜索模式，最后采用最大后验概率估计算法对配准后的图像进行超分辨率重建。该算法可以有效减少搜索匹配点的个数，极大提高搜索速度，并且能够获得与全搜索算法同样高的配准精度，具有较大的峰值信噪比。实验结果表明，所设计算法能获得较好的视觉效果与重建效果，具有一定的实用价值。

超分辨率重建;自适应块匹配;最大后验概率;峰值信噪比

引言

超分辨率重建是指将多幅具有互补信息的低分辨率图像(或视频序列)进行处理，融合估计出一幅或多幅高分辨图像的技术。重建算法通常包括图像配准(或运动估计)、插值、消除模糊和噪声几个组成部分，也有一些空域算法将插值与去除模糊和噪声合二为一，例如迭代反向投影(IBP)，最大后验概率估计(MAP)等。在图像重建过程中，图像配准是超分辨率算法实现的第一步也是极其重要的一步，在图像配准中对像素块运动位置估计的准确性将直接影响重建图像的质量。众多的图像配准方法主要在图像像素空间或图像的频率空间进行，其中基于像素块的匹配算法是常见的一种高效方法。

在块匹配算法中，全搜索(FS)算法是对图像整个像素空间进行搜索，从而找出最符合匹配规则的点，通常图像所含的信息量大、计算复杂度太高、耗时较大，因此，不适宜于实时系统。为此，学者提出了很多优秀的运算简单且耗时少的快速图像匹配算法，例如三步搜索法(TSS)[1]、四步法(FSS)[2]、菱形搜索法(DS)[3]、六边形搜索法(HEXBS)[4]等，这些算法都只是有效地利用运动矢量统计分布特性来固定地选择合适的搜索方式。后来学者们提出来的自适应配准算法，如参数自适应图像配准[5]、基于角点特征的自动配准[6]、自适应最优块匹配[7]等，在不同程度上提高了配准准确度，但是速度较慢且计算的复杂度较大。本文在对配准算法研究的基础上，针对其不足提出一种空域自适应图像块匹配算法，可以灵活地根据图像块的大小选择合适的搜索模式，从而在降低复杂度的同时进一步提高了搜索速度，获得较高的配准精度，最后利用最大后验概率估计算法对已配准图像进行重建，取得了较好的重建效果。

1 自适应搜索算法

该算法首先根据相邻运动块之间的相关性预测搜索块，再利用图像的运动特性选择合适的搜索方式，针对运动块较小的运动矢量选择运算速度较快的算法搜索，大运动块的运动矢量的搜索选择精度较高的算法，从而以实现根据不同运动块选择不同搜索模式的自适应。

1.1 匹配准则

在搜索过程中，对于评价搜索块的相似性，选择求和绝对误差(SAD)以及求和绝对方差(SSE)作为判别准则，其定义如下：

(1)

(2)

式中，(x,y)为位移矢量，fk和fk-1分别为当前帧的图像块和前一帧的预测块，m×n为宏块大小，为了方便算法的实现，一般取m,n的值相等，通常，宏块大小取值为16×16像素。在搜索相似块时，匹配准则选用求和绝对误差SAD。当SAD达到最小时的位移矢量(x,y)就是当前块的运动矢量(MV)，即求解：

(3)

1.2 目标MV的预测

为了获取当前块准确的MV预测，我们首先要得到相邻运动块之间的相关性。通常相关性最强的参考相邻块，应该是当前块左侧、正上、左上和右上方向上的，其他方向上的块与当前块的相关性较小，如图1所示。通过对大量图像序列的统计结果进行分析表明，当前块与其左侧、正上相邻块的运动相关性最大，与左上、右上相邻块的相关性较小，因此本文只选择上邻块作为预测块，忽略其他方向相邻块，以减少运算量。

图1 当前块的相邻块位置

1.3 搜索模式的选取

DS算法是一种高效的快速块匹配算法，主要有两种模式[8]：基于菱形的大九点搜索模式(LDSP)以及小五点搜索模式(SDSP)，如图2所示。当搜索距离中心小于两个像素的小的运动矢量时，LDSP会导致过度搜索，而对于一些大的、复杂的运动图像块，LDSP搜索范围显得太小，从而搜索不足。针对LDSP这一问题，本文根据当前块运动等级来选择搜索模块的自适应算法。对图像块进行运动估计，计算当前块与参考块同一位置之间的SAD[9]，若其SAD值小于设定的误差阈值则认为当前块的运动向量为0，并停止搜索，从而减少搜索的计算量；如果当前块的宏块是第一行(列)，则认为当前块的运动等级低，为小运动，直接采用SDSP进行搜索，这样搜索不会有较大的起伏；否则认为当前块的运动等级高，为大运动，此时先采用LDSP进行初步搜索，后采用SDSP进行精确定位。

图2 搜索模式

在初步搜索阶段，预测的MV的长度可以根据其水平、垂直坐标来确定：

(4)

式中，Γ是MV的大小，round为取整，MV(x)和MV(y)分别是当前MV的水平坐标和垂直坐标。为简化起见，可以使用式(5)决定MV的长度：

(5)

把LDSP模型的中心对准搜索窗的中心点，根据预测MV的长度检测搜索点以及预测点，从而找到使SAD值达到最小的点，并把该最小点作为SDSP模型的中心点。完成初步搜索后，可以粗略估计运动对象的运动趋势，然后通过SDSP模型检测它的搜索点，如果最小SAD值在小菱形中心时，那么中心点即为运动矢量，此时停止搜索；反之重复此步骤，直到最小匹配点为SDSP的中心点，从而完成MV的精确定位。具体流程如图3所示。

图3 自适应块匹配搜索算法流程图

2 基于最大后验概率的超分辨重建算法

基于Bayesian理论的最大后验概率估计(MAP)算法[10]以其受抗噪声干扰能力强、解唯一等优点得到了广泛的应用。基于MAP的图像重建的基本思想是在已知低分辨率图像的前提下，使重构后的高分辨率图像的后验概率达到最大。

假设有N幅观测低分辨率图像序列为{yk,k=1,2,…,N}，理想高分辨率图像为x，它们之间的关系可以表示为yk=DkHkFkx+nk，其中，Dk、Hk和Fk分别为下采样矩阵、模糊矩阵和仿射变换矩阵，nk为高斯白噪声。在不失一般性条件下，假设所有低分辨率图像序列都具有相同的D和H，那么MAP算法的求解代价函数为：

(6)

式中，λ是正则化参数，J(x)是正则化泛函，距离范数为p，当p=1时，并将上式对x求变分得到迭代的求解式为：

(7)

式中，J(x)进行变分后为L(x)x，迭代步长为β。求解时，D、H默认为已知量。在图像超分辨率重构中，H对光学系统的点扩散方程进行估计而得到。在非联合求解算法中，Fk可以通过图像配准算法计算得到，本文将采用前面提出的自适应块匹配算法得到的配准参数用于超分辨率重建。

3 实验及结果分析

实验1：采用大小为16×16像素的宏块，搜索范围为±8像素，匹配准则采用SAD准则。为验证本文提出的自适应块匹配搜索算法的有效性，将提出的配准算法与FS、DS两个序列的搜索结果进行比较，采用平均峰值信噪比(PSNR)、平均搜索点数(块匹配次数)以及相对于FS搜索的速度倍数作为评价标准(表1)。从表1可以看出，本文算法相比其他两种算法不仅有效减少了匹配点的搜索个数、大幅度提高搜索速度，从而减少搜索的时间，并且重构后的图像与其他两种算法一样可以获得较高的PSNR。

表1 视频测试序列在不同算法中的性能比较

图4 是采用Tennis序列分析不同算法的PSNR性能曲线。从图4可以看出本文算法能够获得的峰值信噪比与全搜索算法FS基本相同，配准精度较高。

图4 不同算法的PSNR比较

实验2：对一幅512×512像素的高分辨率图像按表2进行平移和降采样，从而产生4幅64×64的低分辨率图像(q=8)，将这些图像通过上述自适应块匹配搜索方法配准后采用最大后验概率估计(MAP)算法进行重建。自适应块匹配搜索计算得到的位移量见表2，其中第一幅图像y1是参考帧。由表2可见，采用自适应块匹配算法得到的各低分辨率图像帧之间的位移量与实际位移量非常接近，误差范围在0.05左右。重建图像结果如图5所示。

表2 低分辨率图像帧间的位移量

图5 图像序列超分辨率重建结果

图5(a)为原始高分辨率图像，图5(b)是将参考帧经过双线性插值重建后的结果，可以看出双线性插值的图像整体比较模糊，损失了图像的细节，图5(c)是采用DS算法配准后采用MAP重建的高分辨率图像，图5(d)是采用本文的自适应搜索算法配准的重建结果，通过比较发现，本文方法实现的超分辨率重建效果无论在清晰度还是在细节保持方面较双线性插值算法都有所改善，重构后图像的视觉效果与采用快速DS配准相接近。但是根据实验1的结论，本文所提出的算法能极大提高搜索速度，因此更能达到实时性要求，具有更好的应用价值。

4 结束语

本文在研究基于块匹配的图像配准基础上，针对传统算法的不足，提出了一种自适应块匹配算法用于超分辨率重建，该算法采用自适应方式选择搜索模式，能够明显降低平均搜索点数、提高配准速度，且从配准图像的峰值信噪比值可以看出提出算法同其他快速块匹配算法相比都具有较高的配准精度。并且使用本文的配准方法进行最大后验概率估计重建得到的超分辨图像具有较好的视觉效果，有一定的实用价值。

[1] Koga T,Linuma K,Hirano A,et al.Motion compensated interframe coding for video conference[C]//In Proc.Nat.Telecommunication Conf.,New Orleans,LA,November 29-December 3,1981:531-535.

[2] Po L M,Ma M C.A novel four-step search algorithm for fast block motion estimation[J].IEEE Trans on Circuits and Systems for Video Tech,1996,6(3):313-317.

[3] Zhu S,Ma K K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans on Image Processing,2000,9(2):287-290.

[4] Zhu C,Lin X,Chau L P.Hexagon-based search pattern for fast block motion estimation[J].IEEE Trans On Circuits System Video Technology,2002,12(5):349-355.

[5] 韩磊,黄陈蓉,须梦溪,等.参数自适应的图像亚像素级配准方法[J].计算机应用,2013,33(2):487-490.

[6] 赵前鑫,杨英宝.一种基于角点特征的遥感影像自动配准方法[J].测绘科学,2013,38(3):160-162,133.

[7] 蔡成涛,梁小龙,谭吉来,等.自适应最优块匹配视频稳像算法[J].系统工程与电子技术,2013,35(6):1324-1329.

[8] 张培珍,江华俊,沈玉利.自适应块匹配搜索算法研究[J].计算机应用,2006,26(4):797-798,802.

[9] 孙琰玥,何小海,宋海英,等.一种用于视频超分辨率重建的块匹配图像配准方法[J].自动化学报,2011,37(1):37-43.

[10] Schultz R,Stevenson R.Extraction of high-resolution frames from video sequences[J].IEEE Trans Image Processing,1996,5(6):996-101.

An Adaptive Block Matching Algorithm for Super-resolution Reconstruction

TANGLing,CHENMingju

(School of Automation and Electronic Information, Sichuan University of Science & Engineering, Zigong 643000, China)

This paper presents an adaptive block matching algorithm of super-resolution reconstruction. Firstly, the search block is predicted according to the correlation between adjacent blocks, and then the appropriate search mode is adaptively selected by using the motion characteristics of the image, finally, the image after rectification is super-resolution reconstructed by the maximum posterior probability estimation algorithm. The algorithm greatly improves the search rate，at the same time effectively reduces the search number of matching points, and can obtain the same registration accuracy compared with the full search algorithm, maintains a high peak signal to noise ratio(PSNR). Experimental results show that the algorithm has better visual effect and reconstruction effect, which confirms a practical value of the algorithm.

super-resolution reconstruction; adaptive block matching; maximum posterior probability; PSNR

2015-03-11

四川省教育厅科研项目(13ZB0138);人工智能四川省重点实验室开放基金项目(2013RYY02)

唐 玲(1981-),女,重庆铜梁人,讲师,硕士,主要从事信号与信息处理方面的研究，(E-mail)fashion-kitty@163.com

1673-1549(2015)03-0033-04

10.11863/j.suse.2015.03.07

TN919.8

A