基于改进局部敏感散列算法的图像配准.docx
- 文档编号:12946391
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:20
- 大小:540.28KB
基于改进局部敏感散列算法的图像配准.docx
《基于改进局部敏感散列算法的图像配准.docx》由会员分享,可在线阅读,更多相关《基于改进局部敏感散列算法的图像配准.docx(20页珍藏版)》请在冰点文库上搜索。
基于改进局部敏感散列算法的图像配准
基于改进局部敏感散列算法的图像配准
龚卫国“,张旋,李正浩
(重庆大学光电技术及系统教育部重点实验室,重庆400044)
摘要:
为实现图像间的快速准确配准,在局部敏感散列(LSH)算法基础上,提出一种高效的高维特征向量检索算法—改进的LSH(ELSH)算法用以图像特征间的检索配对,从而实现图像间的配准。
该配准算法首先采用尺度不变特征变换(SIFI)算法提取图像的特征点并进行描述,得到图像的高维特征向量。
然后,根据随机选择的若干子向量构建哈希索引结构,以缩减构建索引数据的维数和搜索的范围,从而缩短建立索引的时间。
最后,根据数据随机取样一致性(RANSAC)剔除错误点。
实验结果表明,与BBT(BEST-Bin-First)和LSH算法相比,LSH算法不但提高了匹配点对的准确性同时也缩短了匹配时间,其特征匹配时间分别减少了49.9%和37.9%。
实验表明该算法可以快速、精确地实现图像间的配准。
ImageregistrationbasedonextendedLSH
GONGWei-guo*,zhangXuan,LIZheng-hao
(LaboratoryofOploeleclronicTechnologyandSystemsofCheEducationMinistrytoChina)
ChongqingUniversity,Chongqing400044.China)
*Corresponding。
auhor.E-mail:
wggong@cqu.edu.cn
Abstract:
Inordertorealizequicklyandaccuratelymatchingbetweentheimagefeatures.anefficienthigh-dimensionalfeaturevectorretrievalalgorithm.ExtendedLocalitySensitiveHashing(ELSH).wasproposedbasedonLSH(LocalitySensitiveHashing).Firstly.theScaleInvariantFeatureTrans-form(SIFT)algorithmwasusedtogetthespecialpointofanimageanditsfeatures.Then.accordingtothesub-vectorsselectedrandomlyfromtheSIFTfeatures.ahashindexstructurewasbuilttore-ducetheindexingdimensionandthesearchingscope.Thus.itcansignificantlyreducethetimecostofindexing.Finally.theRandomSampleConsensus(RANSAC)algorithmwasusedtoselecttherightfeaturepointpairs.ExperimentalresultsindicatethatcomparedwiththeBest-lain-First(1313F)andtheLSHalgorithm.ELSHalgorithmnotonlyensurestheaccuracyofmatchingpoints·butalsoreducesthematchingtime.ThetimecostofELSHonlytakes50.1%ofthatofthe1313E.and62.1%ofthatoftheLSH.Inconclusion.theproposedalgorithmcanquicklyandpreciselyachievetheregistrationbetweenimages.
Keywords:
ScaleInvariantFeatureTransform(SIF);featurematching;LocalitySensitiveHashing
(LSH);ExtendedLSH(ELSH)
1引言
图像配准是对同一场景在不同条件下(如不同的时间、拍摄环境、视场角、传感器等)得到的两幅或多幅图像进行对准、异加的过程[1]。
其应用非常广泛.如计算机视觉、不同传感器获得图像的融合、全景图像拼接.医学诊断和辅助治疗等。
日前.图像配准算法主要分为3大类[2]_:
基于灰度的方法、基于变换域的方法(如傅里叶变换、小波变换、Walsh变换[3]和基于特征的方法。
其中.基于特征的方因提取图像的显著特征而具有压缩信官、量,降低对像素的依赖、算法灵活、执行速度快、精度高等优点.成为近年来研究较多的方法。
基于特征的图像配准方法可归纳为3步[4]:
1)特征检测.采用人工或自动的方法提取图像的各类特征[5].如拐点[6]、边缘线或轮廓线,曲面等;2)特征描述.对所提取的特征进行封装.将封装结果数字化、符号化.形成特征矢量和符号串、关系图.从而得到代表图像特征的描述符;3)特征匹配.按一定的空间关系匹配所提取的特征.建立图像特征间的一一对应关系。
在图像配准过程中.特征匹配的任务主要是建立两幅图像中所提取特征间的一一对应关系。
日前实现特征匹配的最常用是最近邻方法NesrestNeighbor,NN)[7].即采用样本特征点的最近邻特征点距离与次近邻距离的比值来进行特征匹配。
该方法属于精确搜索方式。
然而在实际工程中.采用精确搜索力一式不仅耗时长、效率低.而目‘对于高维数据矢量还有可能导致维数灾难。
因此.在实际中通常选用更加高效的近似搜索方法。
针对近似搜索力一法的高效性.日前有很多专家学者对这一类方法进行了深入的研究。
Brown和Lowe在基于尺度不变特征变换(ScaleInvari-ableFeatureTransform,SIFT)特征点检测方法进行相片拼接技术研究中采用KD-Free方法代替简单的线性穷尽搜索方法[8]。
KD-Tree方法是一种近似最近邻搜索方法.和线性穷尽最近邻搜索方法相比.错误率有所增加.SIFT探测到的特征点及潜在的匹配点对通常是很大的.因此.用可以有效降低匹配时间的KD-Tree方法来实现特征匹配是一种很好的选择。
KD-Tree在特维数较低时可以有效地解决最近邻搜索问题.但是当维数超过15时则会失效.甚至不如线性的穷举搜索算法[9]。
Lowe在此基础上提出BBF(Best-Bin-First)算法。
该算法在KD-Tree基础上引入优先权序列.优化了回溯追踪策略.解决了20维以上数据的最近邻查找问题[18]Indyk等在哈希表搜索的思想基础上提出局部敏感散列(LocalitySensitiveHashing,LSH)算法[10]。
该算法利用一组具有一定约束条件的哈希函数来建立多个哈希表.降低了搜索的时间复杂度。
Auclair[11]等人将LSH算法应用于SIFT描述符检索.取得了良好的效果。
随着图像配准相关技术的发展.图像的快速准确配准成为人们追求的日标。
为了寻找一种较为快速的图像配准算法.本文在LSH算法的基础上.提出了一种高效的高维特征向量检索算法.改进的LSH(ExtendedLSH,ELSH)算法用以实现图像特征之间的检索配对.并以此为基础实现图像间的配准。
该配准算法首先利用SIFT算法进行特征提取.然后根据随机抽取的子向量来对提取到的高维特征向量进行特殊的“‘降维”.然后依据所选取的子向量来建立哈希索引.进行最近邻搜索.实现图像特征的正确快速配对。
文中进行了相关的实验验证.实验结果证明该算法能快速准确地实现两幅图像间的配准。
2ELSH算法
2.1LSH算法
LSH算法是建立在哈希索引基础上的另一类近似最近邻搜索算法。
它不依赖于特征维数.可以有效地解决高维特征向量的近似近邻搜索问题。
LSH算法的基本思想是利用哈希函数将彼此相近的特征点以很高的概率散列到同一个哈希桶中,而彼此远离的特征点则散列到不同哈希桶中,在搜索过程中仅搜索那些与查询向量在同-个哈希桶中的特征集合。
LSH法的关键在于哈希函数的构建。
LSH算法首先将特征向量投影到海明空间.即一个超高维的一进制串空间;然后随泪L选择海明空间中的k个元素组成哈希索引值.这些索引值就组成了一个哈希索引值;最后通过一组不同的哈希函数构造出一个哈希表。
LSH算法是用来实现高维数据检索的。
因此.对于数据点集X来说.基于LSH的索引算法可以概括为下而3个步骤:
(1)将数据点集转化为海明空间中的一进制串选取合适
r>0,
>0,随机选取k个形如
的哈希函数
(2)利用这些哈希函数,将数据点存入相应的哈希表项。
相应的检索算法则可描述如下:
(1)查询q,运用上述索引算法中的k个哈希函数,提取
1
i
k所击中的哈希表项。
(2)对这些表项顺序排序,即得到检索结果然而在实际计算过程中,不必将数据点转为二进制串,而只需计算出哈希函数值即可。
2.2 ELSH算法
LSH算法是将特征向量投影到海明空间上进行处理的。
但是,海明空间中的维度内容所包含的信息非常的有限,这使得LSH算法的局部敏感性很低,影响了算法的性能。
本文针对LSH算法的这个缺陷,提出用随机抽取子向量来对高维特征向量进行“降维”,并利用所选取的特征子向量的
范数构建哈希函数的方法,提高了近似向量被散列到同一个哈希桶中的概率,缩减了建立索引时间。
这个过程是建立在以下
高维特征向量的特殊“降维”机制基础上的。
2.2.1 高维特征向量的“降维”
如果高维空间中的向量点彼此相近,那么它们在任意的k个向量上的投影都应该相近,基于此,本文提出了如下假设。
假设:
如果2个特征向量中随机选择的相应(相同起始位置和维数)的若干子向量距离分相近(以欧氏距离作为度量),那么这2个特征量距离相近。
该假设可以表示为式(1):
)=
(1)
其中,sim(V,V)为一个二值函数,若两个D维特征向量V和
相近,则其取值为1,否则,其取值为0[12]。
和
(1≤i≤m≤D)分别为V和V的随机子向量,并且
和
(1≤i≤m≤D)在V和V中有相同的起始位置。
文献[13]中指出,如果2个子向量距离相近,那么它们在空间中所表示的点到固定参考点的距离应该近似相等,并指出在以参考点为球心的超球面上的点彼此相近。
为此,为了简化运算,本文选取空间原点作为参考点,这样向量
和
所表示的点到原点的距离实际上就是向量的
范数(分别记作
和
(1≤i≤m))。
具体表述可见式(2):
)=
(2)
根据上面的假设以及文献[13]所讲述的观点,本文提出,如果2个特征向量V和
相应的相应的m个子向量
和
的
范数
和
相等,那么V和
彼此相近。
具体描述如式(3)所示:
(3)
2.2.2ELSH算法
基于上述结论,本文在研究LSH算法的基础上,提出一种高效的ELSH算法。
该算法首先对高维特征向量进行处理,为每个特征向量随机选取k个子向量,在选取时要确保所选取的子向量拥有相同的起始位置和维数。
然后根据待搜索的特征向量所选择的若干子向量的
范数来构建哈希索引结构,再针对目标特征向量的子向量的
范数进行搜索,存储搜索得到特征向量的位置。
在实际中,首先对其中一个高维向量随机选择k个子向量,记录下每个子向量所在特征向量中的位置,然后根据这个记录对其它高维特征向量进行“降维”。
ELSH算法的具体流程描述如下:
1.选取对应的随机子向量,对高维特征向量按2.2.1小节的要求分别选取合适的子向量。
2.对待搜索的特征向量所提取的特征向量的子向量根据LSH算法来建立哈希索引。
3.对目标特征向量的每一个特征子向量,利用LSH算法思想搜索上面所建立的索引,并存储最近邻位置。
3 基于ELSH的图像配准算法
3.1 SIFT特征提取
本文采用SIFT算法对图像进行特征提取,
SIFT算法[14-18]是2004年由Lowe所提出的特征点匹配算法,它符合实际实用的3个要求:
(1)特征点及其描述符具有相当高的辨识度特色与独特性;
(2)容易获得较高的正确匹配率;
(3)特征点及其描述符对各种破坏具有不变性,如噪声、模糊,以及
角变化、尺度变化、光照等宽基线因素。
一个完整的SIFT算法可以分
为4个部分:
计算尺度空间极值、特征点位置最佳化、计算特征点方向性及特征点描述。
3.1.1计算尺度空间极值
为构造图像的尺度空间,定义卷积算子
(4)
式中I(x,y)是输入图像,*表示x和y上的卷积运算,G(x,y,
)是尺度可变的高斯函数;σ为尺度因子,其中
(5)
高斯差分算子定义如式(6)
(6)
式中
,k和s是常数因子。
图像尺度空间构造过程如下:
先对输入图像进行卷积运算获得一组卷积图像,称其为组,再对这一组中相邻的卷积图像求差获得差分图像。
然后,将上一组卷积图像中的比例为原始图像1/2的图像再缩小1/2作为初始图像,接着采用上述的方式产生下一组卷积图像与差分图像。
以此类推可以获得多组高斯图像与高斯差分图像。
采用26邻域法计算尺度空间的极值,即遍历所有尺度下的高斯差分图像,找到所有26邻域极值点,其中26邻域由像素点所在图像的8个邻近点及上下邻近尺度图像中的9个邻近点组成。
3.1.2 特征点位置最佳化
由于DOG算法会产生较强的边缘响应,在上一步骤中找到的候选特征点并非全部都是稳定的,因此还要剔除低对比度的特征点和不稳定的边缘响应点以增强特征点的稳定性。
特征点的稳定性γ可以利用一个2×2的Hessian矩阵H计算:
(7)
本工作主要是删除低对比度及不稳定的边缘响应点的候选特征点。
以式(8)为标准删除低对比度的候选特征点。
(8)
其中,x表示为候选特征点,D表示为高斯差分后的结果,T表示为转置矩阵。
依据泰勒展开式计算一个偏移量:
(9)
若偏移量
绝对值小于0.03,则将对应区域内极值点位置删除。
针对不稳定的边缘响应点的候选特征点,利用式(10)对其进行删除。
(10)
其中.在候选特征点位置上求H.并计算出它的Tr和Del,r(设r=10)为一个闽值。
若不等式不成立.则表示该区域极值可能为边缘上的候选特征点.将其删除。
其中,m(x,y)表示坐标(x,y)上的梯度幅值,
(x,y)表示坐标(x,y)上该特征点的梯度方向,而L则表示所取区域的所有像素点。
通过方向直方图的方式决定特征点的方向,越接近特征点位置的像素权值越大并分解成8个统计方向,取梯度幅值最大值的方向为特征点的主方向,确定某个方向为主方向的基准方向,对主方向进行归一化处理。
3.1.3将作为形成特征点描述的前置作业,
主要是为了消除图像旋转等一系列刚性形变对图像表征造成的影响。
首先,以特征点位置为中心,取16×16邻近区域,计算区域内所有像素位置的梯度幅值及方向,如式(11)和(12)表示:
(11)
(12)
向量进行特征匹配,并应用随机抽样一致算法(RandomSampleConsensus.RANSAC)[19]对所
得到的特征点对进行处理,剔除误匹配点对,得到正确的特征点对。
算法的具体实现流程如图2所示。
图2 基于ELSH的图像配准算法流程图
Fig.2FlowchartofimagceregistrationalgorithmhascdonELSH
3.1.4 特征点描述
当完成以上3个步骤后,就能得到图像的特征点。
接下来的工作就是要对得到的特征点进行描述,以特征点的主方向为基准,将以特征点为中心区域主方向旋转到基准方向以达到旋转不变性并如图1所示实现特征点描述过程。
3.2 基于ELSH的图像配准算法的实现
在本文提出的高维特征向量检索算法的基础上提出了基于ELSH的图像配准算法。
该算法首先用SIFT算法对待配准图像与目标图像进行特征提取,得到图像的SIFT特征描述符向量,然后采用本文提出的ELSH算法对所提取的特征
4实验及其结果分析
为了验证本文算法.本文采用牛津大学VGG实验室[20]的仿射不变特征图片测试库进行对比实验。
实验均在WindowsXP操作系统下以vis-ualstudio2005为编程实现工具.在双核2.40GiHz,2G内存的微机上实现。
具体实验步骤如下:
Step1:
用SIFT算法分别对源图像以及待配准图像进行特征提取。
Step2:
通过计算描述子之间的欧式距离.分别采用BBF.LSH以及本文提出的ELSH算法(k=16)对计算得到的欧式距离进行搜索.采用最近距离比的方法(Nearest-NeighborDistanceRatio,NNDR)[18]进行匹配.记录不同NNIDR值下的匹配数日。
Step3:
应用随机抽样一致算法计算图像对之间的基本矩阵.计算每对图像的正确匹配点数与错误匹配点数以及匹配精度.并根据所得到的数据绘制的匹配数一错误率曲线图。
以下4幅图分别为测试库中视角、旋转、光照以及模糊4组图像对的匹配数一错误率曲线图。
实验结果说明.在相同的错误率情况下.ELSH较BBF以及LSH有更多的匹配数日。
在实际图像配准过程中.NNIDR准则为一个定值。
在本文中.取闽值为0.49。
图4表示分别用BBF,LSH以及ELSH3种算法对图像测试库中的视角变化图像组中两幅图像实现配准的结果图。
(a)视角变化
(a)Viewpointchanges
(b)旋转变化
(b)Rotationchanges
(c)光照变化
(c)Illuminationchanges
(d)模糊变化
(d)Blurchanges
图3BBF.LSH.ELSH3种算法在4组图像上的实验结果对比
Fig.3ComparisonofexperimentalresultsbetweenBBF,LSHandFLSHalgorithmsonfoursetsofimages
其中图4(a),4(b),4(c)分别表示BBF,LSH,ELSH3种算法实现配准的结果。
由图4可得.ELSH的特征配对点数多于BBF以及LSH算法。
表1表示用BBF,LSH和ELSH3种算法分别对测试库中的视角、旋转、光照以及模糊4组图片所提取的特征进行特征匹配.其中NNIDR的值取的是0.49.然后应用RANSAC'算法对得到的特征点对进行处理.计算对比3种算法的实现搜索时间以及获得的特征点对数目。
(a)BBF算法
(a)BBFalgorithm
(b)LSH算法
(b)LSHalgorithm
(c)ELSH算法
(c)ELSHalgorithm
图4 三种算法在视角变化下的特征匹配效果
Fig.4Matchingresultsusingthreealgorithmsforviewpointchanges
表1 3种算法进行特征匹配的效率对比
Tab.1Experimentalresultsofthatalgorithmsforfeaturematching
从表1的实验结果可知.在视角、旋转、光照以及模糊4种情况下.相较于BB}F以及LSH算法.ELSH算法在效率上有了较为明显的提高。
在匹配数日上.ELSH比BBF最多可多出14.9%的匹配数.比LSH最多可多出4.7%的匹配数。
在匹配时间上.与BBF算法相比.EI_SH最大可减少56.5%。
与LH相比.ELSH最大可减少48.5%.
本论文引入了类似于人类视觉系统功能的结构相似性理论及平均结构相似度(MeanStruc
tureSimilarity,MSSIM、加权平均结构相似度[21](WeightedMeanStructureSimilarity,
wMSSIM)来评价配准后图像之间的相似度。
MSSIM的依据是人类视觉系统高度适合于提场景中的结构信官、.使测量结构信官、的改变与感知图像质量的变化非常接近。
囚此如果两幅图像结构相似.则认为其质量变化不大。
表2为取测试库中的视角、旋转、光照以及模糊4组图片进行相关实验.分别用BBF,LSH,
ELH3种算法实现配准.并计算配准到的两幅图像的平均结构相似度以及加权平均结构相似
度.进行相关的比较。
表2 3种算法配准后的评价结果
Tab.2Evaluationresultsofregistrationforthreealgorithms
由表2的实验结果可以看到.在视角、旋转、光照以及模糊4种情况下.用本文提出的ELSH算法进行特征间的检索配对来实现图像配准.配准后的图像.较BBF以及LSH算法有更好的MSSIM与WMSSIM.即用本文提出的检索方法在实现图像配准过程中表现了更优的性能。
5结论
在研究图像特征匹配算法的基础上.本文提出了一种高效的高维特征向量检索算法ELSH来实现图像特征之间的检索配对.从而达到实现
图像间的快速准确配准的日的。
ELSH算法是基于ILSH算法的一个扩展。
在针对高维特征向量搜索的过程中.该算法优于传统的ELSH算法以及ILSH算法。
最后.用牛津大学的仿射不变特征图片测试库进行了实验验证。
实验结果表明.在实现图像配准过程中.本文提出的ELSH算法表现了更优的性能.可以实现图像间的快速准确配准。
参考文献:
[1]ZITOVAB,FLUSSERJ.Imagerregiistrationmethods:
asurvey[J],ImageandVisionComputing,2003(21);977-1000
[2]张锐娟,张建奇,杨翠,等.基于CSIFT的彩色图像配准技术研究[J].光学学报,2008,28(11):
20972103.
zRJ.ZHANGJQ.YANG,etal..
StudyregistrationtechniqueBased0nCSIFT[J].ActaPhotonicaSinca
.2008.28(11)2097-2103.(inChinese)
[3]GEORGEL.MaRIAP.ImageregistrationusingtheWalshtransforms[C]IEEETransactionsonImageProcessing.2006.15(8):
2343-2357
[4]魏雪云.李景文.徐华平基于融合处理的遥感图像快速配准方法巨J习电波科学学报.2009,2通(6):
1055-1059
WEIXY.LIJW.XUHP.Fastregistration
methodforremot}senseimagesbasedonfusionresult[J]ChineseJournal
ofRadioScience,2009.24(6):
1055-1059
5]LIGZH.GONGWG,NEEAYC,ONGSK,Theeffectivenessofdetector
combinations[j]OpticsExpress.2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 局部 敏感 算法 图像