点特征提取算法探讨
第30卷 第1期
2007年3月
东 华 理 工 学 院 学 报
JOURNAL OF EAST CHINA
INSTITUTE OF TECHNOLOGYVol130 No11
Mar.2007
点特征提取算法探讨
官云兰, 张红军, 刘向美
3.东华理工学院人事处,江西抚州 344000)
1,231
(1.东华理工学院地测学院,江西抚州 344000;2.同济大学测量与国土信息工程系,上海 200092;
摘 要:影像特征提取是影像匹配和三维信息提取的基础,是影像分析与单像处理技术领域中最重要的任务之一。有效的特征提取算法是影像分析与处理的关键。从点特征定义出发,叙述了两种常用的点特征提取算子)))Moravec算子和Forstner算子的原理,利用Moravec算子和Forstner算子可以实现影像点特征的提取,并从提取点特征的准确度、提取速度对两种算子进行比较,最后得出了有益的结论。
关键词:特征提取;点特征;Moravec算子;Forstner算子
中图分类号:P235 文献标识码:A 文章编号:1000-2251(2007)01-042-04
影像是以灰度等级的形式表示的,其特征是由
地面景物的物理与几何特性明显变化而形成,表现为影像局部灰度的急剧变化(陈鹰,2003)。影像特征可分为点状特征、线状特征和面状特征。影像特征提取是影像匹配和三维信息提取的基础,是影像分析与单像处理技术领域中最重要的任务之一。
点特征是影像最基本的特征,它是指那些灰度信号在二维方向上都有明显变化的点,如角点、圆点等。点特征可以应用于诸如图像的配准与匹配,目标描述与识别,光束计算,运动目标跟踪、识别和立体像对3D建模等众多领域。使用点特征进行处理,可以减少参与计算的数据量,同时又不损害图像的重要灰度信息,在匹配运算中能够较大的提高匹配速度,因而受到人们的关注。提取点特征的算子称为兴趣算子或有利算子(interestoperator),即利用某种算法从影像中提取人们感兴趣的,即有利于某种目的的点(陈鹰,2003)。在影像分析和计算机的视觉领域,根据不同应用目的选择有效的点特征提取算子是非常重要的。
几何特征的提取方法。前一种方法可归纳为:首先设计一系列点模板,然后计算模板与所有图像子窗口的相似性,以相似性判断位于子窗口中心的像元是否为特征点。由于该算法计算耗时大,而且模板定义复杂,在实践中较少使用。后一种方法基于几何特征的提取算法,依赖点不同几何特性进行提取,计算简便,因而得到广泛使用。
基于几何特征的点提取,又分为两种方法。第一种方法也是最早提出的基于几何形状的方法之一。这种方法可以描述如下:对于一幅数字图像,首先对其进行图像分割,提取边界构成链码,然后找出边界上转折较大的点作为角点。这种方法在算法和处理步骤上过于复杂,且在分割时所产生的误差将导致提取点的结果偏差很大。此类算法计算步骤多,耗时较大,在实时匹配中较少使用。第二基于几何特征的点提取方法,直接依据图像的灰度信息进行提取。
在摄影测量中,有一些较为著名的点特征提取算子,如:Moravec算子、Forstner算子与Hannah算子等。本文针对Moravec算子和Forstner算子,从提取点的定位准确性及速度两个方面对两种算子进行比较,为不同应用目的选择有效的点特征提取算子提供依据。2.2 Moravec算子
Moravec算子是Moravec于(1977)年提出的,是一种利用灰度方差提取点特征的算子,主要是在四,1 点特征提取算子
2.1 点特征提取算子分类
目前已有的点特征提取算子的方法,大致可以
归为两大类:一类是基于模板的方法;另一类是基于
收稿日期:2006-10-26
作者简介:官云兰(1975)),女,副教授,主要从事摄影测量、GIS的教学与
研究。
第1期官云兰等:点特征提取算法探讨43
征点。步骤为:
(1)计算各像元的兴趣值IV(Interestvalue)。在以像素(c,r)为中心的w@w的影像窗口中(如5@5的窗口),计算图1所示四个方向相邻像素灰度差的平方和
:
图2 Moravec算子流程图Fig.2 FlowchartofMoravec
2.3 Forstner算法
Forstner算子(图2)是一种摄影测量常用的点特征定位算子。该算子通过计算各像素的Robert.s梯度和像素(c,r)为中心的一个窗口(如5@5)的灰
度协方差矩阵,在影像中寻找具有尽可能小的接近
图1 Moravec算子的四个方向Fig.1 Fourdirectionofmoravecoperators
n-1
圆的误差椭圆的点作为特征点(张祖勋等,1997)。其步骤为:
v1=v2=v3=v4=
i=-k
EEEE
(gc+i,r-gc+i+1,r)
2
n-1
i=-kn-1
(gc+i,r+1-gc+i+1,r+i+1)(gc,r+1-gc,r+i+1)
2
2
(1)
i=-kn-1
(gc+i,r-1-gc+i+1,r-i-1)
2
i=-k
其中k=INT(w/2)。取其中最小者作为该像素(c,r)
的兴趣值;
IVc,r=min{V1,V2,V3,V4}
(2)
(2)给定一个经验阈值,将兴趣值大于该值的点(即兴趣值计算窗口的中心点)作为候选点。阈值的选择应以候选点中包括所需要的特征点,而又不含过多的非特征点为原则。
(3)选择候选点中的极值点作为特征点。在一定窗口内(可以不同于兴趣值计算窗口,如5@5,7@7或9@9像元),将候选点中兴趣值不是最大者全部去掉,仅留下最大者,该像素即为一个特征点。这一步骤可称为/抑制局部非最大0。
图2为Moravec算子实现流程图。
(1)计算各像素的Robert.s梯度:
图3 Forstner算子Fig.3 Forstneroperator
gu==gi+1,j+1-gi,j
5ggv==gi,j+1-gi+1,,j
方差矩阵:
Q=N其中:
-1
(3)
特征点。
图4为Forstner算子实现流程图。
(2)计算l@l(如5@5或更大)窗口中灰度的协
=
EgEgg
uvr+k-1
2
u
EggEg
u
2v
v
(4)
EgE
c+k-1
2
u
=
i=c-kc+k-1
2
EE
j=r-kr+k-1
EE
(gi+1,j+1-gi,j)(gi,j+1-gi+1,j)
2
gv=
u
v
2
Egg
i=c-kj=r-k
c+k-1r+k-1
=
i=c-k
E
j=r-k
E
(gi+1,j+1-gi,j)(gi,j+1-
gi+1,j)
K=INT(l/2)
(3)计算兴趣值q与w。q=(trN)w=
(5)
图4 Forstner算子流程图Fig.4 FlowchartofForstner
1DetN
=(6)trQtrN
其中DetN代表矩阵N的行列式,trN为矩阵N的迹。
可以证明,q是像素(c,r)对应的误差椭圆的圆度;
(a-b)
q=1-(a+b)
2
2
2
3 两种算子的比较
下面就定位准确性、提取速度对两种算子进行实验分析。
3.1 定位准确性试验
定位准确性是判断提取出的点位置是否接近正确的点位置。以一幅常用的试验影像,分别用这两种提取算子进行提取点的实验,图5为Moravec算子提取点特征准确性试验图,图6为Forstner算子提取点特征准确性试验图。
从以上试验可以看出,使用Forstner算子对特征点的提取,定位性较Moravec算子准确。3.2 提取速度试验
实时运算中时间的节约是至关重要的。下面采用某一区域的航空影像,以256@254,400@397,500@496和700@695的不同分辨率图像进行实验分析,计算两种算法的提取速度。每一种大小的影像提取时间如表1所示。
(7)
其中a与b为椭圆的长、短半轴。如果a,b中任一为
零,则q=0,表明该点可能位于边缘上;如果a=b,则q=1,表明为一圆,w为该像元的权。
(4)确定待选点。如果兴趣值大于给定的阈值,则该像元为待选点。阈值为经验值,可参考下列值:
Iq=0.5~0.7
Tw=
fw½(f=0.5~1.5)
cwc(c=5)
(8)
其中w为权平均值;wc为权的中值。当q>Tq且w>Tw时,该像元为待选点。
(5)选取极值点。以权值w为依据,选择极值点,即在一个适当窗口中选则w
最大的待选点,而去掉其余的点。
由于Forstner算子较复杂,可首先用一简单的差分算子提取初选点,然后采用Forstner算子在3@3窗口计算兴趣值,并选择备选点最后提取的极值为
表1 计算时间比较
Tab.1 Comparisonofcomputationtmie
影像分辨率
Moravec算法计算时间/msMoravec特征点个数Forstner算子计算时间/msForstner特征点个数
256@254400@397500@496700@[**************]8
[1**********]681
[1**********]971
[**************]
4 结束语
分析摄影测量中常用的两种点特征提取算法$Moravec算子和Forstner算子的原理,并就提取的准
确度、提取时间进行了比较。通过实验证明,Moravec算法速度较快,但准确性不够;相反Forstner算法准确较高,但提取速度比前者低。这对于不同应用目
的的特征点提取方法选取有一定的借鉴意义。
图7,图8为提取特征点的结果图。
贾永红.2003.数字图像处理[M].武汉:武汉大学出版社.
参考文献
陈鹰.2003.遥感影像的数字摄影测量[M].上海:同济大学出版社.何斌,马天予等.2001.VisualC++数字图像处理[M].北京:人民邮
电出版社.
吕言.1989.用于提取数字图像点特征之有利算子研究[J].测绘学
报,18(3):175-182.
张祖勋,张剑清.1997.数字摄影测量学[M].武汉:武汉大学出版
社.
DiscussiononInterestOperatorsforExtractingPoint-likedFeatures
GUANYun-lan, ZHANGHong-jun, LIUXiang-mei
1,2
3
1
(1.FacultyofGeoscienceandSurveyEngineering,EastChinaInstituteofTechnology,Fuzhou,JX344000,China;2.DepartmentofSurveyingandGeoinformatics,TongjiUniversity,Shangha,i200092,China;3.PersonalDepar-tmen,tEastChinaInstituteofTechnology,Fuzhou,JX344000,China)
Abstract:Featuresextractionisafoundationofimagematchingand3Dinformationacquiremen,taswellasoneofthemostimportanttasksinimageanalysisandsingleimagetreatmentfield.FeaturesextractionisrealizedbyDrawoperatorsandcanbedividedintosomefeaturesanddrawnoperatorsandlinefeaturesandFeaturesextractionopera-tors.Basedonthedefinitionofpoin-tlikefeatures,twocommoninterestoperators:MoravecoperatorandForstneroperatorarecomparedinthispaper.Precision,speedandquantityoftwooperatorsareanalyzedandsomemeaning-fulconclusionsaredrawn.KeyWords:poin-tLikedfeatures;featureextraction;moravecoperator;forstneroperator