基于SUSAN算法的图像配准

2006年10月

文章编号:1001-9081(2006)10-2380-03

计算机应用

ComputerApplications

Vol.26No.10

Oct.2006

基于SUSAN算法的图像配准

文杨天,李　征,吴仲光

(四川大学计算机学院,四川成都6100)

(yangtianwen008@gmail.com)

摘　要:通过检测物体的特征点来完成两幅图像的配准。根据USAN区域的描述,采用简化了的SUSAN算法检测刚体的特征点,然后通过找到的特征点和刚体形状不变的特性采用特征点之间的几何关系来配准。实验的结果表明,在无旋转条件下的刚体图像配准中,该算法在特征点提取和图像配准过程中速度比较快。

关键词:角点检测;特征点提取;SUSAN算法;图像配准中图分类号:TP391.41　　文献标识码:A

ImageregistrationbasedonSUSANalgorithm

WENYang2tian,LIZheng,WUZhong2guang

(SchoolofComputerScience,SichuanUniversity,ChengduSichuan6100,China)

Abstract:Tosolveimageregistration,modifiedSUSANalgorithmwasusedtodetectthecornerpoints.Onthegroundoftheunchangeablequalityofrigidbodyandthegeometryrelationbetweenthefeaturepoints,theimageregistrationwasaccomplished.Theexperimentprovesthatitisathighspeedinthecourseoffeatureextractionandimageregistration.

Keywords:cornerdetection;featureextraction;SUSANalgorithm;imageregistration

0　引言

图像配准是图像分析和处理的基本问题,是三维重建等

方面的关键技术之一。图像配准可以认为是在不同时间或相同时间、从不同视角或相同视角对同一场景拍摄的两幅或者多幅图像进行的空间域上的匹配过程。简单地说,图像配准就是建立两幅图像之间的对应关系,确定相应的几何变换参数,对两幅图像中的同一目标进行匹配。近几年,在许多领域中,都对图像配准进行了大量的研究,比较有代表的是:模式识别、自动导航、遥感领域、医学诊断、计算机视角等,虽然每个领域都是根据自己的实际应用背景来制定的配准方法,但是不同领域的配准技术之间在理论方法上有很大的相似性。通过近几年的研究,图像配准的方法通常可以划分为两大类:基于区域的方法和基于特征的方法[1]。

基于区域的方法将一幅图像上的小窗口内像素与另一幅图像上同样尺寸窗口做统计比较。通常选用相关系数作为测度,然后将满足条件的窗口中心作为控制点用于求解两幅图像间的变换参数。

基于图像特征的方法是根据两幅图像的相同特征的几何关系计算配准参数,因此这种方法首先要提取图像中的特征,如角点、线等。角点的定义是:图像中图像中周围亮度变化剧烈的点。在图像识别中,角点是图像的重要局部特征,它集中了图像上很多重要的形状信息。由于角点具有旋转不变性,几乎不受光照条件的影响,角点只占全部像素点的很少一部分,在没有丢失图像数据信息的条件下,角点是最小化要处理的数据。一幅图像中包含了大量的像素点,但是角点包含了被识别图像的重要的几何参数信息,它的检测结果直接关系到后续图像配准的精度。

在图像处理中,目前对角点还没有一个统一的定义,根据

作者采取的方法不同,对角点的定义也有不同的表示。比如:图像边界上曲率最大的点、图像中梯度值和梯度变化率都很高的点、图像中具有最大偏转角和偏差的点等。根据学者们的研究结果,大致可以将角点检测算法分为三类:

基于模板的角点检测。最有代表性的是Bretschi建议的一套模板[2]。

基于边缘的角点检测。它又可以细分为:1)基于边界链码的角点检测,其中Freeman编码最具有代表性;2)基于边界曲率的角点检测,其中有名的算法是采用目标边缘梯度方向的曲率变化率来检测角点[3];3)采用最小二乘法用三次多项式曲面拟合数字图像[4],利用高斯滤波与表面曲率来检测角点[5],利用拟合边界方法来检测角点[6];4)基于小波变换的角点检测。

基于灰度变化的角点检测。最著名的是Harris算法(又称Plessey算法)[7]和SUSAN算法。

本文通过直接对灰度图像的角点检测,在不考虑图像旋转的情况下对图像进行配准。这个算法比采用基于一阶方向导数的Harris算子检测角点的速度快,图像匹配过程中,直接对角点的几何关系进行比较,匹配的速度明显加快。

1　原理描述

SUSAN算法是由牛津大学的S.M.Smith,J.M.Brady

[8]

首先提出的,它主要用来计算图像中的角点特征的。SUSAN算法的特点是:对角点的检测比对边缘检测的效果好,适用于基于角点检测的图像配准;无须梯度的计算,提高了算法的效率;SUSAN检测方法对局部噪声不敏感、抗噪能力强。

如图1所示,圆形区域内的每一个像素点的灰度值与中心像素点的灰度值比较,灰度值与中心像素点相近的点组成的区域称为USAN区域(UnivalueSegmentAssimilating

　　收稿日期:2006-04-21;修订日期:2006-06-26　　作者简介:文杨天(1982-),男,四川成都人,硕士研究生,主要研究方向:数字图像处理、嵌入式系统;　李征(1975-),男,四川成都人,讲师,硕士研究生,主要研究方向:数字图像处理;　吴仲光(1955-),男,四川成都人,副教授,主要研究方向:嵌入式系统.

第10期文杨天等:基于SUSAN算法的图像配准2381　　　　

Nucleus)。

a:表示a点区域处于背景中,整个区域都在USAN区域

中。

b:表示b点区域有超过半数的点都在USAN区域中,b

点是边缘。

c:表示c点区域有等于半数的点都在USAN区域中,c点是边缘。

d:表示d点区域有小于半数的点都在USAN区域中,d点是拐点。

编码序号tmp[0]、tmp[x]和tmp[y]对应的点,在8邻域范围中对应的几何角度满足45°～135°。其中sign(x)是符号函数定义为:

1　　x≥0

sign(x)=-1　x<0

图2　点的八邻域图

图1　USAN区域图解

SUSAN算法的数学描述:

SUSAN模板在图像上滑动,在每一个位置比较模板内各图像像素的亮度与模板核的亮度:

→→

1　if|f(　r)-f(　r0)|≤t→→

(1)C(　r,　r0)=→→

2　if|f(　r)-f(　r0)|>t

→→式中,　是模板内除核之外的任意一点的位置r,　r0是图像

→→→

中的核的位置,f(　r)为　的亮度r,f(　r0)为核的亮度,t为亮度

→→

的阈值,用阈值来控制生成角点的数量,C(　r,　r0)为亮度比较的结果。

为了抑制图像局部细节轻微变化所造成的干扰,可以将tmp[0]的值用8邻域中局部平均值avg(i,j)代替。局部平均值的定义为:

1avg(i,j)=∑f(k,l)

NΩ(i,j,M)通常采用更加稳定的(2)式代替(1)式:

→→(r)-f　(r|f　0)|6

→→-(2)tC(　r,　r0)=e

计算以n为中心像素点的模板内USAN区域大小为:→→→

(3)n(　r0)=∑C(　r,　r0)

→r　→

然后n(　r0)与一个给定的阈值G进行比较:

→→→(),if|n(G-n　r　r0)|→R(r　0)为反应函数,经过局部非极大值抑制NMS(Non2maxi2mumSuppression)之后确立为角点。

为了检测角点,沿着图像上的待检测的像素点按照顺序遍历图像上的每一个点,当循环遍历到一个像素点时,以这个像素点为中心沿着R为半径的圆弧进行扫描,找出圆弧上灰度变化强烈的点。具体实现的方法[9]如下:

1)当循环遍历到图像上的一个点时,同时取出这个点周围半径为R的圆弧上的点的灰度值。也即中心点周围的R邻域(实验结果表明半径为1的模板效果好于半径为2的模板)。

如图2所示,f(i,j)表示点(i,j)的灰度值,将这9个点顺时针编码,将它们的灰度值存储在tmp[0]→tmp[8]中。

2)从tmp[1]开始,计算sign(tmp[1]-tmp[0])…sign(tmp[8]-tmp[0])的值,当sign(x)的值变化的时候,记录下变化的位置。当有符号变化的时候,就可以得到两个圆弧曲线与角点边缘的交点,记下取得符号变化的两个点的编码序号tmp[x]和tmp[y]。可以通过上述对USAN的三种形态的表述,得出结论:要想找到的点是角点必须是使得

()

其中Ω(i,j,M)表示以(i,j)为中心M为半径的圆,N表示圆形区域中像素点的个数。

3)通过前两步找出的点包含了角点,同时也包含了离角点很近的点(干扰点)。下面谈论如何去出这些干扰点。

[10]

在MIC算法中,提出了角点的自身特性,那就是通过角点的任意方向的直线在角点处的灰度变化都很大。根据MIC算法,直接定义一个角点反应函数CRF:

22

CRF=min((f(ia,ja)-f(i,j))+(f(ib,jb)-f(i,j)))其中(ia,ja)和(ib,jb)表示与中心点成为直线的两个点,也就是通过中心点的四条直线,分别是水平H,竖直V,左对角L,右对角R这四条线。可以将这四条线代入角点反应函数中的到:

22

H=[f(i,j)-f(i,j-1)]+[f(i,j)-f(i,j+1)]

22

V=[f(i,j)-f(i-1,j)]+[f(i,j)-f(i+1,j)]

2

L=[f(i,j)-f(i-1,j-1)]+

2

[f(i,j)-f(i+1,j+1)]

2

R=[f(i,j)-f(i-1,j+1)]+

2

[f(i,j)-f(i+1,j-1)]CRF(i,j)=min(H,V,L,R)

通过对USAN区域的理解,当(ia,ja)和(ib,jb)都落在USAN区域中时,角点反应函数CRF的值会很大。所以只要选取适当大的阈值就可以通过角点反应函数CRF来消除干扰点找到合适的角点。

本文定义配准的参考图像为基准图像,而被配准的图像为后续图像。由于本文图像中的物体都是刚体,忽略了图像旋转,所以采用物体中的几何特性就可以完成配准。采用的方法描述如下:

1)在基准图像和后续图像中,把找到的角点按照先y方向后x方向的顺序编号,使图像上的点成为有序的角点队列。

2)假设基准图像和后续图像中的第n个角点是正确的配对点,首先计算它们之间的位移关系:

firstp.x-secondp.x=Δx

(5)

firstp.y-secondp.y=Δy

在(5)式中firstp.x表示基准图像中角点的x坐标,secondp.x是后继图像中角点的x坐标,Δx是图像在x方向上的位移。

3)将位移量Δx和Δy都恢复到后续图像上,也即是:

2382　　　　

secondp.x+Δx=newp.x

secondp.y+Δy=newp.y

计算机应用

(6)

2006年

照片,首先采用了本文的方法对图像的角点进行检测,图3找到的角点有24个,图4找到的角点有23个,都用的“X”表示。角点找到以后,按照本文的算法进行图像匹配,从匹配结果图5、图6可以看出,没有匹配成功的点就消失了,证明算

Δx=-57

法的正确性。图像的位移是。

Δy=-29

式中,newp.x表示后续图像在按照位移量恢复之后的点的坐标。然后取出基准图像的第n+1个角点,它的坐标是firstp.xn+1,first.yn+1,在后续图像中按照排序的顺序,依次检测,找到后续图像中与第n+1个角点相匹配的点,判断的标准入(7)式,t表示阈值:

firstp.xn+1-newp.x≤t

(7)

first.yn+1-newp.y≤t

4)从基准图像中取出第n+2个角点的坐标firstp.xn+2,

first.yn+2,按照上面的步骤3)的做法在后续图像中找出与第n+2个角点匹配的点。接下来取出第n+3…end一直到基准

3　结语

本文应用SUSAN算法,对刚体图片进行角点检测,然后根据刚体的几何不变性对图像直接进行配准。由于采用SUSAN算法找出角点,角点的数量不大,对于后续的图像配准的实现带来相当大的速度优势。在图像配准中,仅仅对找到的少量角点进行比较,采用两重循环的简单排序办法,其算法的时间复杂度为O(n2),由于角点数量不大,对于时间复杂度为O(n2)还是很快的。由于SUSAN算法和其他角点检测算法相比较具有精确度高,抗噪声能力强和速度快的特点,因此适合于很多图像的角点检测。当然本文的算法也有待改进,由于以快速检测为目标而忽略了检测角点的精确度,配准算法适用的范围比较窄,这些都是以后有待改进和提高的地方。参考文献:

[1]　LIH,etal.Acontour2basedapproachtomultisensorimagereg2

isteation[J].IEEETransactiononImageProcessing,March,1995,4(3):320-334.

[2]　JURGENB.AutomatedInspectionSystemsforIndustry[M].UK:

IFS.

[3]　ROSENFELDAK.KGray_levelcornerdetection[J].DatternRec2

ognitionletters,1982,3(1):95-102.

[4]　ZUNIGAOA,HARALICKR.Cornerdetectionusingthefacetmod2

el[A].InProceedingsofCVPRπ83[C].Arlington,VA,USA,June1983.30-37.

[5]　SMITHSM,BRADYJM.SUSAN2anewapproachtolowlevelimage

processing[J].JournalofComputerVision,1997,23(1):45-78.[6]　MEDIONIG,YASUMOTOY.cornerdetectionandcurverepresen2

tationusingcubicB2Spline[J].ComputerVision,Graphics,ImageProcess.,1987,39(3):267-278.

[7]　HARRISC,STEVENM.Acombinedcornerandedgedetector[A].

In:Proc4thAlveyVisionConf[C].Manchester,UK,1988.147-151.

[8]　SmithSM,BRADYM.SUSAN2anewapproachtolow.levelimage

processing[J].InternationalJournalofComputer.1997,23(1):45-78.

[9]　周鹏,谭勇,徐守时.基于角点检测图像配准的一种新算法[J].

图像的最后一个角点,完成上面的步骤3)。

5)判断如果基准图像和后续图像的第n个角点之间的

位移量Δx,Δy恢复到和后续图像上之后,基准图像第n个角点之后的所有角点(n+1,n+2,n+3…end)之中,有半数以上的角点都在后续图像上找到对应的点,那么第n个角点算匹配成功。

如果匹配成功,记录下点对的位置。如果匹配不成功,删除这个点。开始重复执行操作第二步,比基准图像的第n+2角点是否有点能够匹配后续图像的第n+2个角点。直到完成基准图像之中所有点的匹配。

2　实验结果及其分析中国科学技术大学学报,2002,32(4):455-461.

根据本文的方法,在Windows环境下,使用VC++6.0编写程序来实现。图3、图4是两幅不同视角的同一物体的

(上接第2379页)

[10]TRAJKOVICM,HEDLEYM.

Computing[J].1998,16:75-87.

FastcornerdetectionImageand

5　结语

本文针对轮廓跟踪算法,提出了改进的轮廓跟踪算法和轮廓表存储结构,并应用于字符的识别技术中。在存储字符的轮廓线时运用了轮廓表,从而生成字符的轮廓编码,不仅能压缩轮廓特征数据以提高字符匹配速度,而且可以避免字符笔画长短与标准字符笔画长短不一致所引起的误差。参考文献:

[1]　杜彦蕊,李珍,宋卫宏.基于特征编码的手写字符识别技术[J].

计算机工程,2004,30(5):156-158.

[2]　赵丹青,孙德宝.字符识别在车牌识别中的应用[J].中南民族大

学学报(自然科学版),2002,21(3):33-35.

[3]　张远鹏,董海,周文灵.计算机图像处理技术基础[M].北京:北

京大学出版社,1999.

[4]　朱学芳.多媒体信息处理与检索技术[M].北京:电子工业出版

社,2002.