最小亮度变化角点自适应检测算法研究

来源：意榕旅游网

2003年8月第30卷　第4期

西安电子科技大学学报(自然科学版)

JOURNAL　OF　XIDIAN　UNIVERSITY

Aug.2003

Vol.30　No.4

最小亮度变化角点自适应检测算法研究

杨　莉,初秀琴,李玉山

(西安电子科技大学CAD所,陕西西安　710071)

摘要:对最小亮度变化角点检测进行了深入探讨,对其存在的不足提出两点改进:⑴用模糊度概念进行自适应窗口插值,大大减少了以往最小亮度变化角点检测普遍采用固定窗口插值所造成的漏检和虚报概率;⑵利用斜线上边缘点的方向连续性,有效地滤除了由于图像量化误差而造成的伪角点.实验证明,改进的算法明显地提高了角点检测概率和准确度.关键词:角点检测;角点响应函数;线性插值

中图分类号:TP391　　文献标识码:A　　文章编号:100122400(2003)0420530204

StudyoftheadaptivedetectionalgorithmtotheMICcorner

YANGLi,CHUXiu2qin,LIYu2shan

(ResearchInst.ofElectronicCAD,XidianUniv.,Xi′an　710071,China)

Abstract:　OnthebasisofstudyingMICcornerdetection,twoimprovedmethodsaresuggested.First,theconceptoffuzzinessisusedtoputforwardanewadaptivewindowinterpolationalgorithmtoMICcornerdetection.Thisalgorithmissuperiortothewidelyadoptedalgorithmwithfixedwindowinterpolationalgorithmwhichwillcausethemissingoftherightcornerorfalsecorneralarming.Second,makinguseofthecharacteristicthattheedgepixelsintheobliquelinehavecontinuityindirection,somekindoffalsecornerscausedbythequantificaitonerrorareremovedeasily.Experimentalresultsshowthattheprobabilityandaccuracyofcornerdetectionareimprovedgreatly.KeyWords:　cornerdetection;CRF;linearinterpolation

角点定义为二维图像亮度变化剧烈的点或图像边缘曲线上具有曲率极大值的点.由于其信息含量很高,可以对视觉处理提供足够的约束;相对于图像像素点总数少,极大地提高了计算速度,使得实时处理成为可

能;可以在图像之间进行可靠的匹配等优点,使得角点检测在光流计算、目标跟踪、三维场景重构、运动估计等机器视觉方面起着十分重要的作用.

关于角点检测的方法很多[1],早期途径为先分割图像,抽取边界形成链码,将方向改变迅速的点标志为角点.该类方法过多地依赖于图像分割及边界抽取的效果,而且图像分割复杂,计算量大,不适于实时处理.目前大部分的角点检测方法分为两类:⑴基于曲率[2～4];⑵直接基于图像亮度对比,即将与邻点亮度对比足够大的点定义为角点,这一类有SUSAN[5]算法和MIC[1]算法.

最小亮度变化(MIC)是Trajkovic等人在角点响应函数(CRF)的基础上提出的一种新的角点检测算法.新的角点检测算法对每个像素基于其邻域的图像灰度计算CRF值,具有大于某一阈值且为局部最大CRF值的像素点认为是角点.这种新的角点检测算法精度高、稳定性好,对噪声具有鲁棒性且计算迅速.经分析发现,这种算法相比较而言确实具有很多优点,但仍存在不足,如由于图像的量化结果,插值不能达到很好的效果,致使有些边缘点和角点区分不出来;由于噪声影响,有些图像边缘模糊,如果不使用足够大的模板进行CRF计算,就会遗漏很多角点,但对于对比度明显的边缘,使用大的模板又会造成角点定位不够准确;以及阈值的自适应等问题.笔者基于文献[1],对原有的算法进行改进,提出了模糊度的概念,对每一个像素在计算它的CRF值之前测定其

收稿日期:2002208210

基金项目:国家自然科学基金资助项目(60172004);北京大学视觉与听觉信息处理国家重点实验室资助项目(2001203)作者简介:杨　莉(19762),女,西安电子科技大学博士研究生.

第4期　　　　　　　　　　　　杨　莉等:最小亮度变化角点自适应检测算法研究531

模糊度,若达到模糊的标准,则只使用大窗口插值,若足够清楚,则再次使用小窗口插值,精确其位置.对量化误差形成的插值不够精确而造成的一些伪角点,还提出了一种简单的算法对之进行区分.仿真证明,改进的算法相比较原算法而言,在没有明显增加计算量的基础上,提高了角点检测概率和准确度.

1　快速角点检测

用3个典型的USAN[5]形状来说明CRF是如何区分角点、边缘点和非边界点,如图1所示.

图1　USAN的典型形状

假设通过核心点的一条任意直线,它与圆窗口边界交于相反的两点P和P′,定义如下的CRF:RN=min((fP-fN)2+(fP′-fN)2),这里,N为核心点,fP为P点处的灰度值.考虑上述3种情况,对于图1ϖ,核心

点在USAN区域内,至少有一条直线L,它的P和P′都属于USAN区,因此,CRF值很小;对于图1ω,只有一条直线,它的P和P′都属于USAN区,它的CRF值也很小;对于图1ξ,核心为角点的情况,任何通过核心的直线,它的P和P′都至少有一点不属于USAN区,因此它的CRF值很大.所以用CRF来检测角点的基本原理就是在规定的圆形窗口内寻找最小的灰度变化,即CRF值,若此CRF值仍然大于某一规定的阈值,则认为此点为角点,否则认为不是角点.

实际计算中一般采用将圆形窗口离散化来计算CRF值,但这种方法具有很大的量化误差,比如直径为3的圆窗口只能检测4个方向,直径为5的圆窗口检测6个方向,而直径为7的圆窗口,也只能检测8个方向,因此文献[1]提出用插值的方法来计算CRF值,推导了直径为3的圆形窗口的插值情况,但由于实际获得的图像边缘的渐变性,单纯

的小窗口插值会造成许多漏检现象,笔者在文献[1]的基础上以直径7为例推导大窗口插值情况.

如图2所示,首先将7×7圆形窗口离散化,即取A～H,A′～H′16个离散点,在圆周上每两点之间进行线性插值,即lM为ABA′B′之间过核心O点的任意一条直线,与圆周的交点设为M和M′,依次类推.计算时,可以首先从AA′～HH′8个方向寻找最小灰度变化,若最小灰度变化小于给定的阈值,则认为不是角点,放弃;否则,标记为候选角点.因为需要寻找的几何角点一般只占所有像素数的1%,所以这种预对候选角点进行进一步的筛选.

对lM即ABA′B′之间的插值进行详细推导:

A点的响应函数B点的响应函数

图2　7×7圆窗口线性插值示意图

处理算法可以大大减少计算量.对候选角点顺序进行lM～lU的插值计算,得到的CRF值与阈值进行比较,

　　rA=(fA-fO)2+(fA′-fO)2　,　　rB=(fB-fO)2+(fB′-fO)2　,

　　fM=(1-x)fA+xfB,　fM′=(1-x)fA′+xfB′　.

(1)(2)(3)(4)

AB间插值的响应函数　　rM=(fM-fO)2+(fM′-fO)2　,

其中

532　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第30卷

rM=Ax+2Bx+C　,

(5)

)(fA′-fO),A=rB-rA-2B.对二次曲线求最小值可得:其中C=rA,B=(fB-fA)(fA-fO)+(fB′-fA′

若B<0,而且A+B>0,在0RM=min(rA,rB).以此类推,可得CRF为min(RM,RN,RP,RQ,RR,RS,RT,RU).

2　用模糊度进行自适应窗口插值

由于图像的量化结果,插值不能达到很好的效果,有些边缘点和角点区分不出来;由于噪声影响,有些图

像边缘模糊,如果不使用足够大的模板进行CRF计算,就会遗漏很多角点,但对于比较清楚的边缘使用大的模板又会造成角点定位不够准确等问题.因此在研究文献[1]算法的基础上,针对这些问题,对原有的算法进行改进,提出模糊度的概念,即对每一个像素在计算它的CRF值之前首先测定其模糊度,若达到模糊的标准,则只使用大窗口插值,若足够清楚,则进一步使用小窗口插值,精确其位置.具体算法如下:

⑴因为低分辨率对几何角点的影响不是很大[1],所以为了提高计算效率以及减少不必要的纹理角点,首先对低分辨率图像进行候选角点的选取.方法为,对每4个像素点取平均值形成一点,将N×N分辨率的图像降低为N/2×N/2分辨率图像.对此低分辨率图像首先用7×7圆形窗口离散化成8个方向计算其CRF值来获得候选角点,然后利用上述插值方法在这8个方向之间进行线性插值,获得比较精确的CRF值,进一步减少候选角点,这里阈值取参考值500.

⑵对候选角点恢复其全分辨率位置,即将一个低分辨率的候选角点恢复成4个全分辨率的候选角点,再对全分辨率角点进行7×7线性插值,滤除一些伪角点,进一步定位角点位置.由于只使用了大窗口进行CRF计算,获得的候选角点比较多,精确定位角点位置比较麻烦,因此对于一些边缘清楚,可以比较精确定位其位置的候选角点,采用3×3小窗口进行线性插值,将使用大窗口得到的真正角点附近的伪角点滤除.对每一个候选角点测定其模糊度,若达不到模糊的标准,认为足够清楚,使用小窗口插值,精确其位置.

⑶对候选角点来说,如果处在一个对比度比较明显(即较清楚)的边界上,则一般它与其邻域的灰度差值或者比较大(不属于同一区域),或者很小(属于同一区域);而模糊的边界,候选角点与邻域的灰度差值一般介于两个阈值之间.基于这种实验经验,用37圆模板邻域提出模糊度的概念,37圆模板邻域如图3所示.

候选角点为中心点,其邻域36个点分别与中心点相减,并取绝对值,若绝对值在阈值t1和阈值t2之间的个数超过邻域点数的一半,即18,则认为模

图3　37圆模板邻域示意图

糊,否则,认为足够清楚,进一步进行3×3线性插值,阈值减小为200.这种方

法避免了大窗口在对比度明显的区域中进行角点检测而造成的候选角点过多,角点定位不准确;又避免了用小窗口在模糊区域进行角点检测造成的角点遗漏现象,且在进行大小窗口选择时,使用了计算模糊度的方法,不需要人工判定,可以自适应进行,大大提高了准确性.

⑷5×5或7×7最大值压缩获得最终角点结果.文献[1]中先将7×7圆形窗口离散化,只从8个方向得到候选角点,后采用3×3线性插值,用最大值压缩的步骤来获得最终的角点结果.图4对比显示了文献[1]和笔者利用模糊度对之改进进行角点检测的结果.用模糊度进行自适应窗口插值,由于先采用7×7线性插值,在此基础上再进行3×3线性插值,虽然进行两次插值,但7×7插值已经大大减少了候选角点的数量,并没有明显地增加计算量.改进的算法提高了角点检测的概率和准确度,减少了虚报概率,具有一定的参考价值.

⑸图像的量化造成插值不够准确,这种情况使得一些斜线上的边缘点被检测为角点.文中的算法可以滤除这些伪角点.经研究发现,这种位于斜线上被认为是角点的边缘点,如(i,j)一般具有阶梯特性,即如果此斜线偏水平方向,则若同一行此点左边两个像素(i,j-1),(i,j-2)和它具有灰度相似性,则它的右上两个像素点(i-1,j+1),(i-1,j+2)或右下两个像素点(i+1,j+1),(i+1,j+2)也和它具有灰度相似性,同理,偏水平方向的斜线若同一行此点右边两个像素和它具有灰度相似性,则它的左上或左下两个像素点也和它具有灰度相似性,垂直亦然.即边缘点具有方向上的连续性,而角点不具有.以此简单算法可以滤除这种伪

第4期　　　　　　　　　　　　杨　莉等:最小亮度变化角点自适应检测算法研究533

图4　角点检测对比结果

角点,以标准测试图像为例验证上述结果见图5.

图5　7×7圆形窗口离散化,3×3线性插值,阈值400,最大值压缩

3　结　　论

在深入探讨MIC算法的基础上,提出了用模糊度概念进行自适应窗口插值的新算法,该算法大大减少了以往采用固定窗口插值所造成的漏检和虚报概率.对于量化误差造成的一些伪角点,提出一种简单的算法对之进行滤除.实验证明,改进的算法相比较原算法而言,提高了角点检测的概率和准确性.在进行算法时,采用了不同的固定阈值,以后的研究可以采用自适应阈值法,或提高线性插值的效率,使得检测出的角点更准确.参考文献:

[1]MiroslavT,MarkH.FastCornerDetection[J].ImageandVisionComputing,1998,16(1):75287.

[2]MokhtarianF,SuomelaR.CurvatureScaleSpaceforRobustImageCornerDetection[A].ProceedingsofFourteenthInternational

ConferenceonPatternRecognition[C].Brisbane:IEEEComputerSociety,1998.181921821.

[3]OrriteC,LopezJE,AlcoleaA.CurveSegmentationbyContinuousSmoothingatMultipleScales[A].ProceedingsofInternational

ConferenceonImageProcessing[C].Lausanne:theIEEESignalProcessingSociety,1996.5792582.

[4]KwanghoonS,KimJH,AlexanderWE.AMeanFieldAnealingApproachtoRobustCornerDetection[J].IEEETransonSystems,

ManandCybernetics,PartB,1998,28(1):82290.

[5]SmithSM,BradyJM.SUSAN—aNewApproachtoLowLevelImageProcessing[J].IntJournalofComputerVision,1997,23(1):

45278.

(编辑:齐淑娟)　　

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

最小亮度变化角点自适应检测算法研究