基于NSCT的图像拼接算法

章建军，曹 杰

（南京航空航天大学 江苏 南京 210016）

随着计算机和图像处理技术的发展，图像拼接技术也随之诞生，并且在现实生活中发挥着越来越大的作用，应用前景也越来越广泛[1]。由于图像采集设备捕获单幅图像的视野一般是有限的，在一些应用场合就需要把多幅有重叠区域的图像拼接成一幅完整的图像，以扩大视野范围或者获得超分辨率的拼接图像。图像拼接的关键技术之一是图像配准，即寻找将两幅图像间相重叠的部分对齐所需的变换，是对不同时间、不同视场或不同成像模式的两幅或多幅图像进行空间变换处理，使得各个图像在几何上能够匹配对应起来。另一个关键技术是图像融合，目的是使拼接后的图像要尽可能接近原始图像,失真尽可能小,没有明显的拼接痕迹、没有明显的曝光差异。

图像配准技术可以分为基于特征和基于区域两种方法[2]。文献[3]提出的SIFT(scale invariance feature transform)算法属于基于特征的配准，算法匹配精度较高，但计算量较大，实时性较差。对于图像融合算法，文献[4]提出了基于小波的图像拼接方法，但是对于二维图像，小波仅能以“点”奇异来逼近“线”奇异，变换后图像的信息缺失较大，拼接后的图像过渡不自然。针对以上缺点，对于图像配准，本文采用改进的角点检测算法及流形上的优化算法进行快速匹配；对于图像融合，文中采用非下采样轮廓波变换(NSCT)方法。实验证明，本文算法，不仅拼接速度较快，而且拼接后的图像更加自然，过渡更平滑。环境的绘图，待绘成地图后再进行路径规划、自主移动并完成任务。有鉴于此种模式需要额外的绘图工作准备，近年来也有学者提出一类探索算法, 该类算法部分采用路径规划思想，以实现自主绘制地图为目标，寻找最有利于绘图的机器人移动路径。因此后文将分别介绍路径规划算法及探索算法。

1 角点特征检测

角点检测是计算机视觉和数字图像处理中一种常用技术。角点所在的邻域通常也是图像中稳定的并且信息丰富的区域，这些区域可能具有某些特性，如旋转不变性、尺度不变性、仿射不变性和光照亮度不变性。因此，在计算机视觉和数字图像处理领域中，研究角点有重要意义。角点检测有多种方法，基于图像灰度的方法通过计算点的曲率及梯度来检测角点，是目前研究的重点。

由于Harris角点检测算子具有对亮度和对比度的变化不敏感，具有旋转不变性等性质而获得广泛应用。图像Harris角点检测算法实现步骤归纳如下：

1) 计算图像I在x和y两个方向的梯度：

其中，⊗表示卷积运算。

2)计算图像两个方向梯度的乘积：

其中ω为加权函数，可以取常数，但一般取高斯加权函数。令

其中，det表示取方阵的行列式，trace表示取方阵的迹，α为经验常数，取值范围0.04-0.06。

4)计算每个像素的Harris响应值R，并对小于某一阈值的R置为0：

5)在3×3或者5×5的邻域内进行非极大值抑制，局部极大值点即为图像中的角点。

改进的Harris角点检测算法，即Harris-Laplace角点检测通过如下两步检测具有尺度不变性的Harris角点：

1)在多尺度下，使用Harris角点检测算法进行角点检测。

2)自动搜索角点的特征尺度。

2 图像变换参数的求解

2.1 李群与李代数的基本概念

李群是一个拓扑群，同时也是一个解析流形，其同时具有群结构和拓扑结构，而且群结构和拓扑结构是相容的。在单位元附近，李群可以线性化。对于n维李群G，单位元附近的切空间TeG是n维向量空间。对任意a∈G，利用李群的左平移，可以把切向量Xe∈G平移为a点处的切向量dLa(Xe)，利用左平移可以得到群G上的切向量场。李群G上的全体左不变向量场构成一个同构于单位元处切空间TeG的向量空间，在李括号[X,Y]=XY-YX下成为李代数，记作g。

设g为李群G的李代数，对任意Xe∈G，存在积分曲线expX，满足expX(t1+t2)=expX(t1)expX(t2)∀t1, t2∈R

称expX(t)，为G的单参数子群。称映射exp:g→G，exp(X)=expX(1)为指数映射。

全体n×n可逆矩阵的集合关于矩阵乘法构成矩阵李群,即GL(n,R)。行列式为1的n阶实矩阵构成的李群称为特殊线性群，即SL(n,R)，相应李代数为SL(n,R)。本文涉及的是SL(3,R)，对应的李代数为SL(3,R)，其基向量为：

2.2 基于李群指数映射的参数优化算法

设图像上点P的齐次坐标为[x,y,1]T，SL(3,R)在欧氏空间的嵌入映射为π:t→π(t)，对于任意t∈SL(3,R)，定义从SL(3,R)到P点的作用为w:SL(3,R)×P→P，则射影变换可表示为

任取一幅图像中指定的子图像作为初始模板，其灰度值为I(P)，模板图像经过射影变形后在另一幅图像中的灰度值为I(w(t))(P)。构造目标函数如下：

为了提高算法的快速性和鲁棒性，本文采用流形上的优化算法求解上述最优化问题而获取射影变换参数。

t迭代公式为：

其中λi为可调步长。

基于李群指数映射的参数求解可以归纳如下：

(2)作意取一幅图像通过一定算法确定模板图像I(P)，计算变换参数初始值t。

(3)迭代求解变换参数

1)根据前次迭代所得的参数V，在另一幅图像中获取准目标图像I。t(P)并计算目标图像和模板图像的差值图像I。t(P)-I(P)。

3)计算参数增量V,并选择合适的λ，更新参数：t。exp(λv)→t。

4)若‖V‖大于预先指定的正数或迭代次数小于预定值，返回步骤1)。

3 非下采样轮廓波变换

3.1 NSCT变换

Contourlet[5-6]作为一种多尺度和多方向的图像表示方法，已经在自然图像去噪[7]、图像融合[8]等领域[9]获得了广泛的研究，展示了这一多尺度几何分析方法的强大潜力。Contourlet最初的提出是为了寻找图像中分段光滑的轮廓信号的稀疏表示，M. N. Do和Martin Vetterli认为Contourlet是一种“真正”的二维图像表示方法。然而由于Contourlet在实现过程中，对滤波后的图像进行了隔行隔列的重采样，使低频子带和高频子带产生频谱混叠。频谱混叠造成同一方向的信号会在几个不同的方向子带同时出现，从而在一定程度上削弱了其方向选择性。

为了消除Contourlet变换的频谱混叠现象，增强其方向选择性和平移不变性。基于Contourlet变换和非下采样思想，A.L. Cunha、J. P. Zhou和M. N. Do等于2006年利用非下采样塔式分解和非下采样滤波器组，构造出了非下采样Contourlet变换（NSCT）[10]。由于没有下采样操作，NSCT具有平移不变性。

NSCT变换包括两个步骤：第一步采用拉普拉斯金字塔（Laplacian pyramid，LP)来实现多尺度分解，第二步通过方向滤波器组(Directional filter bank，DFB)来实现方向分解。

3.2 非下采样LP分解

在Contourlet变换的LP分解中，首先对上一尺度低频图像用低通滤波器进行低通滤波，然后进行下采样，得到低频图像；再对该低频图像进行上采样，然后用高通滤波器对上采样后的图像进行高通滤波，并将高通滤波后的图像与上一尺度的低频图像进行差分，得到塔式分解后的高频部分。

非采样的LP分解不同于Contourlet变换中的LP分解，在NSCT中，采用atrous算法的思想，对低通滤波器和高通滤波器分别进行上采样，然后对上一尺度低频图像采用上采样后的低通滤波器进行低通滤波，得到低频图像；对上一尺度低频图像用上采样后的高通滤波器进行高通滤波，得到LP分解后的高频图像。图像经N级非采样塔式滤波后，可得到N+1个与源图像具有相同尺寸大小的子带图像。

3.3 非下采样DFB分解

1992 年，Bamberger和Smith构造了扇形方向滤波器组。非采样滤波器组去除了该方向滤波器组中的下采样和上采样环节，对应地对方向滤波器组中的滤波器做插值处理，得到同样具有平移不变特性的非采样方向滤波器组。如果对某尺度下的子带图像进行k级方向分解，可得到2k个与原始输入图像大小相同的方向子带图像。因此图像经N级NSCT分解后可得到个和原始输入图像大小相同的方向子带图像，其中ki为尺度i下的方向分解级数。

4 基于NSCT的图像拼接算法

如何选取模板图像非常关键，首先选取的模板图像在另一幅图像中应存在，其次模板图像的信息量应比较丰富。本文的选择方法分为两步：第一步，使用角点检测算法或其改进算法检测两幅图像的特征点，并进行匹配；第二步，在匹配的角点中，计算以角点为中心一定大小的子图像的空间频率，选择空间频率最大的子图像作为模板图像。空间频率定义为：

其中，M及N表示图像的大小，I(x，y)表示(x，y)处的像素值。空间频率可以作为图像清晰程度的测度，空间频率越大则图像越清晰，信息越丰富。

另一个关键问题是怎样对拼接处图像进行融合。由于NSCT变换具有非常好的方向特性，能够更好地显示图像的几何特征，所以能为图像拼接提供更多的信息。NSCT变换在分解和重构的过程中取消了下采样环节，能够得到与源图像尺寸大小相同的各级子带图像，并且具有平移不变性，因此有效地解决了拼接过程中的平移问题。

基于以上讨论，文中提出一种基于NSCT的图像拼接算法，算法步骤为：

1)利用角点检测算法或其改进算法求取特征点并进行匹配，使用上文提到的方法选取模板子图像。

2)使用基于流形上的优化算法求解射影变换参数。

3)对待拼接的两幅图像进行NSCT变换，得到不同尺度不同方向上的变换系数。对得到的变换系数构成的子图像进行拼接，对拼接缝附近的图像采用加权平均的融合方法平滑，得到多个分量的拼接结果。其中融合方法为：

其中，SF(I)表示图像I的空间频率，I(x,y)表示(x,y)处的像素值。

4)最后利用重构算法将拼接的各频带子图像进行逆NSCT变换得到拼接图像。

5 实验结果及分析

根据以上所述的图像拼接算法，文中选取了具有重叠区域的两幅图像进行了拼接实验。待拼接的两幅图像如图1所示，大小分别为940×427和947×434，拼接后的图像如图2所示。黑色区域部分是由于变换参数旋转，在拼接后用零填充而造成的。可以看到拼接图像后的视觉效果很好，过渡平滑自然，没有明显的接缝。

6 结束语

一方面，使用流形上的优化算法可以快速地求出变换参数，而且具有较好的鲁棒性。另一方面，由于NSCT相比于小波变换，在每个尺度提供不同数目、灵活的方向，具有更好的方向特性，从而可以更好地表示图像的几何特征，所以能为图像拼接提供更多的信息，它是真正的二维变换并且能够捕捉内在的几何结构。NSCT利用NSPFB和NSDFB对图像进行多尺度、多方向分解，只具有上采样过程，具有平移不变性，得到的拼接图像更加自然，过渡更加平滑。

图1 待拼接的两幅图像Fig. 1 Two original images

图2 拼接后的图像Fig. 2 The finial image

[1] 漆驰,郑国勤,孙家广. 一个基于全景图的虚拟环境漫游系统[J].计算机工程与应用, 2001,15(37):138-141 QI Chi, ZHENG Guo-qi, SUN Jia-guang. An image-based virtual environment navigation system [J]. Computer Engineering and Application, 2001, 15(37):138-141.

[2] 蔡丽欢,廖英豪,郭东辉. 图像拼接方法及其关键技术研究[J]. 计算机技术与发展, 2008,18(3):1-4 CAI Li-huan, LIAO Ying-hao, GUO Dong-hui. Study on image stitching methods and its key technologies [J].Computer Technology and Development, 2008, 18(3):1-4

[3] Lowe D G. Distinctive image features from scale-invariant key points [J]. International Journal of Computer Vision, 2004,60(2):91-110.

[4] 王宇,王涌天,刘越. 基于SIFT和小波变换的图像拼接算法[J]. 北京理工大学学报,2009, 29(5):423-426.WANG Yu, WANG Yong-tian, LIU Yue. Image stitch algorithm based on SIFT and wavelet transform [J]. Transaction of Beijing Institute of Technology, 2009, 29(5):423-426.

[5] Do. M. N, Vetterli.M . Contourlet: A directional multiresolution image representation [C]//Proc of IEEE International Conference on Image Processing, Rochester, NY, 2002: 357-360

[6] Do. M. N, Vetterli.M. The contourlet transform: an efficient directional multiresolution image representation [J].IEEE Trans on Image Processing,2005,14(12):2091-2106.

[7] 梁栋,沈敏,高维清,等. 一种基于Contourlet递归Cycle Spinning的图像去噪方法[J].电子学报,2005,33(11):2044-2046.LIANG Dong,SHEN Min,GAO Qing-wei, et al.A method for image de-noising based on the contourlet transform using recursive cycle spinning [J].Acta Electronica Sinica,2005,33(1):2044-2046.

[8] 刘胜鹏,方勇. 基于Contourlet变换和PCNN的融合算法及其在可见光与红外线图像融合中的应用[J].红外与毫米波学报,2007, 26(3):364-369.LIU Sheng-peng, FANG Yong. Infrared image fusion algorithm based on contourlet transform and improved pulse coupled neural network [J]. Journal of Infrared and Millimeter Waves, 2007,26(3):364-369.

[9] 焦李成,侯彪,王爽,等，图像多尺度几何分析理论与应用-后小波分析理论与应用[M].西安:西安电子科技大学出版社,2008.

[10] Cunha A L, ZHOU Jian-ping ,Minh. Do N. The nonsubsampled contourlet transform: theory, design, and applications [J]. IEEE Trans on Image Processing, 2006, 15(10):3089-3101.