APP下载

序列图像的快速配准算法研究

2017-06-28张艳珠

沈阳理工大学学报 2017年3期
关键词:哈希重合灰度

张艳珠,王 涛

(沈阳理工大学 自动化与电气工程学院,沈阳 110159)

序列图像的快速配准算法研究

张艳珠,王 涛

(沈阳理工大学 自动化与电气工程学院,沈阳 110159)

基于特征的图像配准算法至今已取得了很多研究成果,然而在现有的计算机性能条件下依然不能实现实时性的结果。针对基于快速鲁棒特征(Speed Up Robust Features,SURF)的序列图像拼接算法中图像配准时间长、计算繁琐等问题,提出一种结合感知哈希算法的SURF图像配准方法。设计了一种快速的搜索算法,对待拼接的相邻序列图像进行重合区域检测,确定有效的拼接区域,对有效拼接区域提取SURF特征点及描述子实现特征的配准。实验结果表明,该方法能够显著提高匹配速度和效率,提取稳定准确的特征点,减少误匹配,与现有算法相比有更好的实时性。

图像配准;感知哈希;SURF

图像拼接技术是将有重合区域的小视域图像(可以是来自不同时间和角度,甚至不同的设备)进行无缝化的拼接,来得到满足分辨率要求的大视域图像的一种技术[1]。这一技术使得人们用普通的照相机就可以获得宽视野的全景图,而不必使用广角镜头等昂贵设备,且可以有效地解决镜头边缘失真的问题。现在,这一技术已经广泛应用在遥感地图测绘、全景图像拼接、医疗图像分析领域等。

图像配准是图像拼接过程的关键技术,配准算法的优劣直接影响最后结果的质量,同时配准过程的效率也决定了整个拼接过程的实时性。关于配准算法已有很多非常成熟的研究成果,如Richard Szeliski[2]提出的基于投影变换模型的配准算法,提出了一种2D空间的八参数投影模型来实现配准;Kuglin等[3]提出的相位相关法,借助傅立叶变换思想,将图像信息变换到频域范围内计算平移矢量;Xiaowei Han等[4]提出的灰度相关的匹配算法,先将两幅图像转化成二值化的图像粗略计算出匹配位置,然后采用序贯相似性方法完成精确匹配。基于特征的图像配准算法是以图像的特征点为基础进行匹配的一种算法,该类算法具有比较高的鲁棒性。其中,里程碑式的方法为Lowe提出的尺度不变特征变换(Scale Invariant Feature Transform,SIFT)算法[5]和Bay等人提出的快速鲁棒特征(Speeded Up Robust Features,SURF)算法[6]。SIFT特征检测算法通过形成关键点的局部特征描述子作为两幅拼接图像的相似特征判别依据,具有良好的尺度、光照及空间旋转不变性,被认为是最流行且有效的特征提取方法;受到SIFT算法的启发,SURF算法对SIFT算法进行了计算速度方面的改进,应用了简化近似的思想,巧妙地运用了积分图像和DoH(Determinant of Hessian)近似,其优点是速度快于SIFT,有实验表明[7],SURF中采用的DoH近似算法比SIFT中的DoG算法快3倍,综合性能优于SIFT算法。但是,在实际的工程应用中,如果没有专用的图形计算加速设备,在现有计算机性能条件下难以满足实时性的要求,例如某些规定在几秒甚至几毫秒时间内完成特征检测、特征匹配、目标识别等一系列操作的场合,现有算法则难以完成。

在研究了基于特征的图像拼接算法之后,本文提出结合感知哈希算法和SURF算法的序列图像快速拼接方法。经典的SURF算法是首先对待拼接的图像进行所有特征点的提取,然后进行随后的特征点匹配等操作,本文提出的方法是在特征检测和提取之前,首先运用感知哈希算法进行拼接区域的检测,然后在有效拼接区域内进行特征检测和提取,省去对无关区域的检测操作,这可以大大减少SURF特征提取的运算量和运算时间,同时可以减少误匹配对,提高配准的准确性和效率。

1 图像感知哈希算法

1.1 感知哈希算法原理

感知哈希[8](Perceptual Hash)和加密算法中所说的哈希函数,或散列函数不同,它是根据图像内容的特征生成该图像的一个二进制形式的“指纹”字符串(Fingerprint),如果两幅图像是相同或相似的,则它们的感知哈希值就是相同或近似的,即“指纹”相似度越高,则图像越接近。所以该算法常常用于相同或相似文件的检测,例如以图识图的搜索算法。常用的感知哈希算法有均值哈希和基于离散余弦变换(Discrete Cosine Transformation)的DCT hash算法,算法流程图如图1所示。

图1 感知哈希算法流程图

1.2 感知哈希相似度检测

哈希算法实例如图2所示,相对于图2a,图2b、图2c、图2d分别发生了尺度、旋转、亮度及对比度的变化。

采用均值哈希和DCT哈希算法进行相似度检测,算法实现步骤:

(1)将图像转化为256级灰度图像,缩小图像尺寸到8×8或32×32像素。均值哈希为8×8,DCT哈希为32×32。这样做去除了图像的高频信息,保留了图像的轮廓等低频信息。以图2a为例,结果如图3所示。

图2 哈希算法实例图

图3 图2a灰度转化与尺寸缩小

(2)将图像的颜色空间转化为64级灰度。

(3)在均值哈希算法里,计算所有像素的灰度平均值;在DCT哈希里,计算图像的DCT变换,得到32×32的DCT系数矩阵,只保留左上角8×8的系数,因为这部分保留了图像低频的主要部分,并计算系数的平均值。计算结果如图4、表1所示。

图4 图2a DCT变换图

图2a图2b图2c图2d灰度均值24243737DCT均值37283852128456587

(4)生成哈希值。均值哈希中,像素灰度值大于等于平均值置为1,否则置为0,结果如图5所示;DCT哈希类似,通过和系数均值的比较生成哈希值,结果如图6所示。

图5 均值哈希算法哈希值结果

图6 DCT哈希算法哈希值结果

得出图像的哈希值之后,可以通过图像哈希值的汉明距离(Hamming Distance)来判断两幅图像的相似程度。相似度计算公式为

相似度检测过程中,同时采用计时函数clock()对算法的运算时间进行监测,计时单位为毫秒,计时代码如下:

clock_t start_time = clock();

{//相似度检测算法}

clock_t end_time = clock();

cout<<“time is∶” <(end_time-start_time) / CLOCKS_PER_SEC* 1000 << “ms” <

实验结果数据如表2所示。

表2 相似度检测结果

从表2实验结果来看,哈希算法在图像相似性检测中有很好的性能,对各种图像变化检测的准确率能达到50%以上,尤其是在尺寸变化、亮度及对比度变化上检测结果非常准确,且运算速度非常快,用时在十几毫秒之内。DCT哈希算法和均值哈希算法相比,相似度结果更加准确,在耗时方面只是略慢于均值哈希,综合性能较好。本文在序列图像拼接前,先采用DCT哈希算法进行图像重合区域的检测,从而快速确定匹配区域,在匹配区域进行拼接操作,可以大大提高拼接效率。

2 重合区域搜索算法

图像的重合区域指相邻图像之间相同的图像范围。常用的算法有基于模板的匹配算法。即在其中一幅图上选取一块区域作为检测的模板,在另一幅图中进行检索,找到相同或者相似的区域,以确定重合区域,这种方法计算繁琐,而且容易受到光照等变化的影响,在实际运用中不具有实时性。

本文结合感知哈希算法提出一种简单有效的重合区域检测算法,算法原理如图7所示。根据实际情况,可以知道大多数序列图的重合范围在30%~50%之间,所以设计了参数λ来表示重合范围占原图百分比的最优值。设初值从图像的20%处开始(图像1从右边开始算起,图像2从左边开始算起),随着λ逐渐增大,检测区域也逐渐增大,在λ增大的过程中,逐步匹配检测区域的相似度。

图7 搜索算法原理示意图

由实际情况可知,随着λ的变化,被检测区域的相似度曲线如图8所示。

图8 检测区域相似度曲线

在λ的搜索过程中,存在一个λ值使待检测区域的相似度达到最高,此时λ所找到的区域就是两幅图像重合的区域,即检测区域哈希值的最优匹配。为了使算法能够较为准确地确定重合区域,同时又不增加算法的时间复杂度,需要对λ的搜索速度进行试验以满足要求。以图9两组图像为实验对象,图9a组为重合区域较大的情况,图像像素大小为3264×1840,图9b组为重合区域较小的情况,图像像素大小为3264×2448。对比每组图像在不同搜索步长、次数、准确率和耗时等方面的表现。图9a组实验结果如表3所示,图9b组实验结果如表4所示。

图9 搜索算法实验图

表3 图9a组实验结果数据

表4 图9b组实验结果数据

对于图9a组实验对象,由表3可知,当搜索步长为1%和3%时,算法均能达到设定的相似度阈值,且λ值结果相同均为0.47,与实际情况相符。3%的搜索步长更快达到最优值,综合性能比1%快3倍左右。而从5%的搜索步长来看,结果并没有达到设定的阈值,且λ也没有达到最优解,由此可知,5%的步长设定偏高,不能检测到最优匹配。对于图9b组实验对象,结论与图9a组类似,即在重合区域较小的情况下(重合区域在30%左右),3%的步长也能较快地找到最优匹配,综合性能最优。

因此,在重合区域确定时,可以以待拼接序列图像3%的幅度作为搜索步长,结合感知哈希算法的快速性,便可以很快地确定重合区域。

3 基于SURF的图像配准

3.1 特征点提取

SURF算法中感兴趣点的检测主要用到了海森矩阵(Hessian Matrix)近似法。其中要借助积分图像(Integral Image),将图像在高斯微分模板下的滤波变为积分图像的加减运算,这样可以大大减少运算时间。积分图由Viola等[9]提出,Simard等[10]将其用于盒子滤波(Box Filter)。

设任意一点(i,j)的像素值I(i,j)为图像左上角到点(i,j)的对角线区域灰度值总和,为

(1)

p(i′,j′)表示点(i′,j′)的灰度值。如图10所示,在求区域W的像素总灰度值时,不管W怎么变化,都能通过该区域的4个角点,即(i1,j1)、(i2,j2)、(i3,j3)、(i4,j4)的灰度值加减得到,为∑w=I(i4,j4)-I(i2,j2)-I(i3,j3)+I(i1,j1)

(2)

图10 积分图像计算窗口内灰度和

设图像I中任意一个点X=(x,y),在尺度参数是σ下的Hessian矩阵H(X,σ)为

(3)

其中,卷积的近似过程是用盒子滤波(BoxFilter)模板代替原来的高斯模板,模板区域里分为几个小区域,每个小区域里都是相同的权值,如图11所示。其中,白色部分权值填1,黑色部分填-1,灰色部分为0。

图11 高斯二阶微分模板简化

文献[6]中设定模板尺寸为9×9,σ=1.2,对图像进行滤波和特征检测,Dxx、Dxy和Dyy分别代表不同模板与图像滤波的结果,则Hessian矩阵的行列式为

Det(Happrox)=DxxDyy-(0.9Dxy)2

(4)

Dxx、Dxy和Dyy的计算采用对积分图像的加减运算。用这个行列式的值代表图像中关键点的响应值,对整幅图像进行搜索就可以形成全图的关键点响应图。然后改变滤波模板的大小,分别与图像做卷积运算,便可以形成不同尺度下的关键点响应值图像,找出响应值中的极值点,完成特征点的提取操作。

3.2 特征点描述子

m=∑dx+∑dy

(5)

(6)

主方向即:θ′=θ|max(m)。

接下来就是生成特征描述子,具体步骤为:

(1)以特征点为中心,将边长20s的矩形窗口划分成4×4的子块,每个子块有25个像元。

(2)使用尺度为2s的小波对子块进行响应值计算,分别得到沿主方向的dy和垂直主方向的dx。得到每个子块的矢量:

V子块=[∑dx,∑|dx|,∑dy,∑|dy|]

(7)

共有16个子块,则特征描述子共有16×4=64维。

这样,SURF特征描述子不仅具有尺度和旋转不变性,而且小波响应本身具有亮度不变性,归一化后也有对比度不变性。使得算法能够得到比较稳定的兴趣点。

4 实验分析与比较

实验主要对比原SURF算法和本文算法在图像配准方面的效果。实验源图像如图12所示。实验工具借助Matlab R2012b和Visual Studio 2013软件,运行条件为Windows7系统,CPU主频2.67GHz,内存2GB。

图12 实验源图像

SURF算法特征点匹配如图13所示,配准结果如图14所示。

采用感知哈希和本文设计的搜索算法对源图像重合区域进行检测,重合度检测阈值设定为0.8,λ初值为0.1,重合区域检测结果如图15所示,图中矩形区域即重合区域,重合区域特征点匹配如图16所示。

图13 SURF特征点匹配图

图14 SURF算法配准结果

图15 重合区域检测结果

图16 重合区域特征点匹配

重合区哈希值结果如图17所示,检测数据结果如表5所示。

图17 重合区域哈希值结果

搜索次数λ相似度/%耗时/ms130468125160

本文算法匹配结果如图18所示,矩形区域为标注出的重合区域。SURF算法和本文算法数据对比如表6所示。

图18 本文算法匹配结果

特征点数SURF图12a图12b131156本文算法图12a图12b5683匹配对数2919检测耗时/ms32941423

由实验结果容易看出,本文算法在保证配准质量的前提下,获得了更快的匹配速度。在特征点检测上,由于先搜索了有效的重合区域,所以省去了无关区域的特征点检测,在特征点数目的检测耗时上比原算法缩短了一半多,而特征点匹配对的数目为19对,与原算法相比保留了绝大部分匹配对,保证了图像的配准质量。

5 结束语

将图像感知哈希算法融合到图像的配准过程中,设计了有效的搜索算法,可以快速准确地确定出拼接区域,从而大大减少了特征检测的运算量和时间。实验结果表明,结合感知哈希的SURF图像配准算法具有更高的匹配效率,且匹配效果能够满足视觉要求。研究主要针对图像间存在先

后关系的序列图像,如何设计出适合更复杂情况的配准算法有待于进一步研究。

[1]杜往泽,宋执环,闫文博,等.单摄像头旋转监控下的快速图像拼接[J].中国图象图形学报,2016,21(2):245-254.

[2]R Szeliski.Video Mosaics for Virtual Environment[J].IEEE Computer Graphics and Applications,1996,16(2):22-30.

[3]C Kuglin,D Hines.The Phase Correlation Image Alignment Method[C] // IEEE International Conference on Cybernetics and Society.New York,1975:163 -165.

[4]Xiaowei Han,Lei Yan,Hongying Zhao.An approach of fast image mosaic based on binary region segmentation[C]//27th International Congress on High-Speed Photography and Photonics.SanJose,2007:627957.

[5]Lowe D G.Object recognition from local scale-invariant features[C]//Proceedings of the IEEE International Conferenceon Computer Vision.Corfu,Greece,1999:1150-1157.

[6]Herbert Bay,Andreas Ess,Tinne Tuytelaars,et al.Speeded-Up Robust Features (SURF) [J].Computer Visionand Image Understanding,2008,110(3):346-359.

[7]Juan L,Gwun O.A comparison of sift,pca-sift and surf[J].International Journal of Image Processing (IJIP),2009,3(4):143-152.

[8]李雨佳,李京兵.基于DCT和感知哈希的纹理防伪标签鉴别算法[J].计算机应用研究,2014,31(12):3734-3737.

[9]P Viola,M Jones.Rapid object detection using a boosted cascadeof simple features[C]//Computer VisionandPatternRecognition.Kauai,2001:511-518.

[10]P Simard,L Bottou,P Haffner,et al.Boxlets:a fast convolution algorithm for signal processing and neural networks[C]// Conference on Advances in Neural Information Processing Systems.Denver,1998:571-577.

(责任编辑:马金发)

Research on Fast Registration Algorithm for Sequence Image

ZHANG Yanzhu,WANG Tao

(Shenyang Ligong University,Shenyang 110159,China)

The great progress has been made in the feature-based image registration algorithm,however,it is still difficult to achieve real-time results under the existing conditions of computer performance.For the issue of high complexity for computing time in image registration algorithm based on speed up robust features(SURF) in sequence images,a method is proposed on the basis of perceptual hash algorithm by using fast SURF.Firstly,a fast search algorithm is designed,and the overlap area in two adjacent images is detected,which determines the effective region.Then,feature points and SURF descriptor are extracted in this region to complete feature points matching.Experimental results show that the proposed method can significantly improve matching speed and efficiency within stable and accurate feature points,reducing mismatch and has better real-time performance in comparison with the existing algorithms. Key words: image registration;perceptual hash;SURF

2016-06-23

张艳珠(1971—),女,副教授,博士,研究方向:目标识别,分数阶控制,智能算法。

1003-1251(2017)03-0058-07

TP391

A

猜你喜欢

哈希重合灰度
采用改进导重法的拓扑结构灰度单元过滤技术
文件哈希值处理一条龙
基于最大加权投影求解的彩色图像灰度化对比度保留算法
电力系统单回线自适应重合闸的研究
基于灰度线性建模的亚像素图像抖动量计算
基于OpenCV与均值哈希算法的人脸相似识别系统
巧用哈希数值传递文件
考虑暂态稳定优化的自适应重合闸方法
一种基于Bigram二级哈希的中文索引结构
220kV线路重合闸运行分析