數(shù)字?jǐn)z影測量論文

1、典型點(diǎn)特征提取算法研究摘要： 立體像對的自動(dòng)匹配和目標(biāo)的自動(dòng)識別是當(dāng)代攝影測量研究的一大熱點(diǎn)，而特征提取是自動(dòng)匹配和目標(biāo)識別的前提。特征提取包含點(diǎn)特征提取、線特征提取和面特征提取，本文主要研究和實(shí)現(xiàn)了Moravec算子、 Forstner算子和Harris算子這三種基本的點(diǎn)特征提取算法。通過編程實(shí)現(xiàn)，對三種點(diǎn)特征提取算子的效果和優(yōu)缺點(diǎn)做了比較分析。關(guān)鍵詞： 點(diǎn)特征提取，Moravec算子，F(xiàn)ostner算子，Harris算子0. 前言當(dāng)代攝影測量與傳統(tǒng)攝影測量的根本區(qū)別在于數(shù)據(jù)處理的自動(dòng)化或半自動(dòng)化，如：數(shù)據(jù)的自動(dòng)獲取，影像自動(dòng)糾正，影像自動(dòng)匹配和影像自動(dòng)拼接等【1】。這些自動(dòng)化的前提是對影像

2、特征的自動(dòng)提取。影像的特征一般可以分為點(diǎn)特征、線特征、面特征三類。在同名點(diǎn)匹配、DEM（和DSM）密集點(diǎn)云生成中最重要的是點(diǎn)特征的提取和精度定位。點(diǎn)特征是指在影像上最基本的特征，是一種表征影像局部特性的位置度量，可以用來作為影像中具有一定特征的局部區(qū)域的位置標(biāo)示【2】。通俗來講點(diǎn)特征可以定義為那些灰度在多個(gè)方向都有較大變化的點(diǎn)，如圓點(diǎn)、角點(diǎn)等。提取點(diǎn)特征的算子一般被稱為興趣算子或有利算子。在各種文獻(xiàn)中，人們根據(jù)不同的出發(fā)點(diǎn)和目的提出了多種特征提取的興趣算子。而這些興趣算子根據(jù)它們性質(zhì)又大致可以分為三類【3】【4】。第一類是基于模板匹配的算子：通過計(jì)算一個(gè)固定的特征點(diǎn)模板與所有圖像子窗口的相似性

3、，以相似程度來判斷某一象元是否為特征點(diǎn)，這種方法計(jì)算量較大，比較耗費(fèi)時(shí)間。第二類是基于圖像邊緣特征的算子：通過先對圖像的邊緣輪廓進(jìn)行提取，然后通過邊界上方向變化的快慢來判斷特征點(diǎn)，這種方法的效果依賴于圖像邊緣提取的效果，計(jì)算復(fù)雜度高。第三類是基于影像灰度的算子：影像的灰度是對地物的反射信號的數(shù)字化記錄，因此類比于信號處理，通過對影像局部灰度變化的計(jì)算來找到信號有較大變化的點(diǎn)，這樣的點(diǎn)就是所尋找的特征點(diǎn)，這種基于灰度的方法計(jì)算簡單，因而使用較為普遍。角點(diǎn)在特征點(diǎn)中更為常見，在實(shí)際圖像中一般位于輪廓的拐角、直線的交點(diǎn)、直線的端點(diǎn)等位置。其類型大致可分為：L型交叉點(diǎn)、T型交叉點(diǎn)、Y型交叉點(diǎn)、X型交叉

4、點(diǎn)、箭型交叉點(diǎn)（如下圖0.1所示）。本文中主要研究和實(shí)現(xiàn)了幾種最常見的點(diǎn)特征提取算子：Moravec算子、Forstner算子和Harris算子。主要的提取目標(biāo)為角點(diǎn)，并通過標(biāo)準(zhǔn)圖像（如下圖0.2所示）來對三種點(diǎn)特征提取算子的提取效果作比較。（圖0.1 典型角點(diǎn)）1. 算法原理和實(shí)現(xiàn)1.1 Moravec算子Moravec于1977年提出利用灰度方差提取點(diǎn)特征，這就是Moravec算子，它屬于第三類基于影像灰度的算子。Moravec算子通過計(jì)算各像素四個(gè)主要方向（即：0度方向、45度方向、90度方向、145度方向（如圖1.1所示）上面灰度的差平方和，并且選取灰度差平方和中的最小值為該點(diǎn)的角點(diǎn)響

5、應(yīng)函數(shù)值或稱興趣值（IV），然后通過一定的閾值判斷，選取興趣值IV中大于閾值的點(diǎn)做為候選點(diǎn)，最后通過一定的窗口，選擇窗口中備選點(diǎn)里的極大值點(diǎn)做為該窗口中的特征點(diǎn)。（圖1.1 Moravec算子的四個(gè)方向）具體的實(shí)現(xiàn)步驟如下：（1）計(jì)算各象元的興趣值IV。在以像素（c，r）為中心的w*w的窗口中，計(jì)算該像素四個(gè)主要方向相鄰像素的灰度差平方和：其中k = INT（w/2），即計(jì)算窗口的一半大小。然后取上述四個(gè)值的最小值作為該像素的（c，r）的興趣值：（2）通過經(jīng)驗(yàn)閾值選取候選點(diǎn)。給定一個(gè)經(jīng)驗(yàn)閾值，將上一步中的到的興趣值大于該閾值的點(diǎn)作為候選點(diǎn)。此時(shí)閾值越小，結(jié)果中提取到的特征點(diǎn)越多；閾值越大，結(jié)果

6、中提取到的特征點(diǎn)越少。（3）極大值濾波，選出特征點(diǎn)。在一定大小的窗口內(nèi)（一般不同于興趣值計(jì)算的窗口大小）選取興趣值中最大的點(diǎn)作為特征點(diǎn)。1.2 Forstner算子Forstner算子也是屬于第三類利用灰度選取特征點(diǎn)的算子，作為一個(gè)可以用于精確定位的特征提取算子，F(xiàn)orstner算子的理論更偏向于誤差處理，整體計(jì)算過程比Moravec算子要復(fù)雜一些。在本文中只考慮算子在提取特征點(diǎn)（即選取最佳窗口）的過程的實(shí)現(xiàn)。Forstner算子通過計(jì)算各像素的Robert梯度和以像素為中心的一個(gè)窗口的灰度協(xié)方差矩陣，在影像中尋找盡可能小而接近于圓的誤差橢圓的點(diǎn)作為特征點(diǎn)。算法的具體實(shí)現(xiàn)步驟如下：（1）計(jì)算窗

7、口中灰度的協(xié)方差矩陣。其中：分別表示窗口中各像素點(diǎn)的Robert梯度值。（2）計(jì)算興趣值q和w。其中： DetN 表示矩陣N的行列式；trN表示矩陣N的跡。（3）確定候選點(diǎn)。根據(jù)經(jīng)驗(yàn)閾值，選取出候選點(diǎn)。這里的對q和w分別有閾值。（4）選取極值點(diǎn)。在一個(gè)適當(dāng)?shù)拇翱诶镒鰳O大值濾波，以權(quán)值w為依據(jù)選取極值點(diǎn)，則這樣的點(diǎn)就是我們提取的特征點(diǎn)。1.2 Harris算子Harris算子也屬于第三類利用灰度選取特征點(diǎn)的算子，通過計(jì)算與自相關(guān)函數(shù)相聯(lián)系的的矩陣M，M矩陣的兩個(gè)特征值是自相關(guān)函數(shù)的一階曲率，然后計(jì)算兩個(gè)曲率值，如果兩個(gè)曲率值都大，則認(rèn)為該點(diǎn)為特征點(diǎn)。Harris算子的思想是通過自相關(guān)矩陣來提取角

8、點(diǎn)。本文中，對經(jīng)典的Harris算法加入了一個(gè)閾值選擇的步驟。具體算法步驟如下：（1）一階差分，計(jì)算梯度。首先確定n*n的影像窗口，對窗口中像素點(diǎn)進(jìn)行一階差分運(yùn)算，求得梯度值。（2）高斯濾波，計(jì)算I值。計(jì)算出與自相關(guān)函數(shù)相聯(lián)系的矩陣M，M陣的特征值是自相關(guān)函數(shù)的一階曲率。按如下公式計(jì)算I值：（3）確定候選點(diǎn)。給定一定的閾值，選取候選點(diǎn)。（4）選取特征點(diǎn)。在一定大小的窗口內(nèi)（一般不同于興趣值計(jì)算的窗口大?。┻x取 I 值中最大的點(diǎn)作為特征點(diǎn)。2 效果分析2.1 Moravec算子2.1.1 提取效果對測試圖像進(jìn)行特征點(diǎn)提取，得到結(jié)果如下圖2.1所示。（圖2.1 Moravec算子提取效果）從圖中可

9、以發(fā)現(xiàn)在高對比度處的幾種基本類型的角點(diǎn)都被提取出來，但在一些低對比度的小區(qū)域中典型的角點(diǎn)沒有被提取出來。特別是在測試圖像的左方的灰度梯度區(qū)域，沒有提取出任何的角點(diǎn)。還可以發(fā)現(xiàn)Moravec對圖中某些斜向的邊緣非常敏感，在實(shí)心形體的幾條近45度和135度的邊緣上面提取出了很多特征點(diǎn)。2.1.2 效果分析Moravec算子通過計(jì)算象元的四個(gè)方向的灰度差平方和來作為判斷是否特征點(diǎn)的條件。通過上面的提取效果圖我們可以發(fā)現(xiàn)Moravec算子的如下特點(diǎn)：（1）經(jīng)驗(yàn)閾值影響大。通過算法的原理可以知道，Moravec算子提取的特征點(diǎn)是大于閾值的興趣值中的最大值點(diǎn)，閾值是會(huì)直接影響到做極大值濾波時(shí)的候選點(diǎn)數(shù)目。

10、從上面的提取效果中也可以發(fā)現(xiàn)，圖像中灰度對比度較小的區(qū)域里的非常明顯的特征點(diǎn)也沒有提取出來。這并不是因?yàn)镸orave算子本身的缺陷，而是由于閾值設(shè)定所產(chǎn)生的問題。但是在Moravec算子的機(jī)制下，要想找到一個(gè)通用的閾值選擇方法是很麻煩的，所以一般需要人工不斷的更改閾值以得到對于一幅影像較為合理的閾值。（2）噪聲敏感。在提取的結(jié)果中還有一個(gè)明顯的特點(diǎn)：對某些斜向的邊緣線敏感。通過對比可以發(fā)現(xiàn)，在圖像中一個(gè)像素大小的斜向邊緣并不能引起Moravec算子的高敏感性。所以，可以得到結(jié)論：Moravec算子并不是具有斜向邊緣敏感性的特征提取算子。通過對圖像放大，可以看到提取了很多特征點(diǎn)的傾斜邊緣實(shí)際上是

11、由鋸齒狀的結(jié)構(gòu)構(gòu)成，而這些鋸齒結(jié)構(gòu)就像一個(gè)一個(gè)獨(dú)立的噪聲點(diǎn)，使得計(jì)算出的IV值有極大值出現(xiàn)，也即是引起了Moravec的敏感性，最終提取出了很多的特征點(diǎn)。（3）不能準(zhǔn)確定位。Moravec算子在計(jì)算四個(gè)方向灰度差平方和值時(shí)是將窗口中某一方向相鄰像素的差值直接平方相加，也即等權(quán)的相加。這樣做的結(jié)果就是角點(diǎn)的定位不準(zhǔn)確（一般最大會(huì)偏移一個(gè)像素）?？梢酝ㄟ^下圖2.2來說明這種局限性。（圖2.2 假設(shè)局部灰度圖）上圖假設(shè)為某影像上的一個(gè)小區(qū)域示意，可以知道最好的角點(diǎn)提取結(jié)果是圖中藍(lán)色五角星所在的位置。采用5*5的窗口（如1.2圖中的紅色框和藍(lán)色框）來計(jì)算IV值，根據(jù)計(jì)算四方向值的原理可以知道，紅色點(diǎn)處

12、的 IV = 255*255 ，藍(lán)色點(diǎn)處的 IV = 255*255。假設(shè)閾值取值為255，那么也就是說圖中的紅色點(diǎn)和藍(lán)色點(diǎn)在Moravec算子的機(jī)制下都可以成為候選點(diǎn)，甚至于圖中的綠色點(diǎn)和黃色點(diǎn)也可以成為候選點(diǎn)。在極大值濾波的過程中，如果按照順序搜索最大的情況來選擇最大值，那么無論怎樣計(jì)算都不可能正確的選擇出藍(lán)色點(diǎn)，而紅色點(diǎn)卻很容易被選當(dāng)做特征點(diǎn)提取出來（偏移量為1個(gè)像素）。通過上述分析，可以清楚的看到Moravec算子的定位不夠精確，特征點(diǎn)會(huì)被錯(cuò)誤提取。因此，在很多論文中提到了通過增加Moravec算子計(jì)算的方向的個(gè)數(shù)來提高結(jié)果的正確率，但增加方向的度量不好確定，而且增加方向會(huì)幾何倍數(shù)的增

13、加計(jì)算量，例如：增加30度方向，那么就必然會(huì)增加60度、120度、150度、210度、240度、300度、330度這幾個(gè)方向。考慮到圖像是一種信號的記錄，而離中心點(diǎn)不同距離的信號對中心點(diǎn)的影響是不同的。那么我們可以考慮距離加權(quán)的方式來計(jì)算這四個(gè)方向的灰度差平方和，這樣在計(jì)算值時(shí)只需要乘上一個(gè)權(quán)值（權(quán)值可以定義為）就可以將不同距離的像素最中心位置的灰度影響表現(xiàn)出來。對于上圖而言，藍(lán)色點(diǎn)處的IV值就會(huì)大于其余三個(gè)點(diǎn)處的IV值，最終就可以準(zhǔn)確的定位出紅色點(diǎn)的特征點(diǎn)。2.2 Forstner算子2.2.1 提取效果對測試圖像進(jìn)行特征點(diǎn)提取，得到結(jié)果如下圖2.2所示。（圖2.3 Forstner算子提取

14、效果）從圖中可以看到，在對比度較大的區(qū)域里明顯的特征點(diǎn)都成功提取出來，但在對比度較小的圖像區(qū)域（左方的灰度梯度區(qū)域）也沒有任何的特征點(diǎn)被提取出來還可以看到提取結(jié)果中并沒有像Moravec算子一樣在傾斜邊緣上出現(xiàn)很多的提取結(jié)果。2.2.2 效果分析Forstner算子通過計(jì)算Robert梯度值組成的灰度協(xié)方差矩陣來判斷特征點(diǎn)。通過上面的結(jié)果可以看到Forstner算子有以下特點(diǎn)：（1）經(jīng)驗(yàn)閾值影響大。同Moravec算子一樣，需要通過閾值判斷來確定候選點(diǎn)，閾值的選擇合理性會(huì)影響到最后的提取特征點(diǎn)的數(shù)目。（2）一定程度的抗噪能力。Forstner算子通過對灰度的協(xié)方差矩陣的計(jì)算，選擇出那些接近于圓

15、的誤差橢圓的點(diǎn)，因此Forstner算子不像Moravec算子僅僅考慮了某幾個(gè)方向的灰度變化量，還考慮到了整體的誤差橢圓的分布。最終表現(xiàn)的結(jié)果就是對于鋸齒狀的邊緣而產(chǎn)生的偽特征點(diǎn)有一定的抗噪能力。2.3 Harris算子2.3.1 提取效果對測試圖像進(jìn)行特征點(diǎn)提取，得到結(jié)果如下圖2.3所示。（圖2.4 Harris算子提取效果）從圖中可以看到，Harris算子對圖中的特征點(diǎn)基本上全部提取出來了。而且不同于在Moravec算子和Fostner算子提取結(jié)果，Harris算子在圖像左方的灰度梯度區(qū)域也提取出了特征點(diǎn)，但其定位效果不如Forstner算子。在圖中某些傾斜的邊緣上也有一些點(diǎn)被提取出來，但

16、特征點(diǎn)的數(shù)量少于Moravec算子提取出來的結(jié)果。2.3.2 效果分析Harris算子通過自相關(guān)矩陣來提取角點(diǎn)。通過上面的效果圖可以發(fā)現(xiàn)Harris算子有以下特點(diǎn)：（1）經(jīng)驗(yàn)閾值影響大。在本文中，對Harris算子添加了一個(gè)閾值判斷步驟。因此，同前面兩個(gè)算子一樣，需要通過閾值判斷來確定候選點(diǎn)，閾值的選擇合理性會(huì)影響到最后的提取特征點(diǎn)的數(shù)目。（2）對L型角點(diǎn)定位較好。在結(jié)果圖中可以看到Harris提取的特征點(diǎn)在L型角點(diǎn)處定位準(zhǔn)確，都是在最佳的角點(diǎn)位置處；包括在傾斜的邊緣處提取出來的那些特征點(diǎn)很多也是因?yàn)長型的角點(diǎn)而被提取出來的。2.4 三種算子的分析比較三種特征提取算子都是屬于第三類通過影像灰度

17、來提取特征點(diǎn)的算子，但是由于不同的提出目的和理論，它們的理論、復(fù)雜程度和提取結(jié)果都有所差異。Moravec算子基于灰度差平方和作為特征點(diǎn)提取的測度；Forstner算子基于Robert梯度構(gòu)成的灰度協(xié)方差矩陣，引入誤差橢圓的概念作為特征點(diǎn)提取的測度；而Harris算子則是通過相關(guān)矩陣作為點(diǎn)特征的提取測度。在影像灰度的基礎(chǔ)上都根據(jù)提出者各自的領(lǐng)域和目的加入了一些相關(guān)的專業(yè)特點(diǎn)。三種算子對測試圖像提取的耗費(fèi)時(shí)間如下表：表一 三種算子特征提取情況統(tǒng)計(jì)特征提取算子耗費(fèi)時(shí)間（ms）提取點(diǎn)數(shù)（個(gè)）Morave125280Forstner9451Harris561152整體上來講，Moravec算子是三種算

18、子最簡單的，在提取結(jié)果中會(huì)對鋸齒狀噪聲非常敏感；Forstner算子整個(gè)結(jié)構(gòu)比較復(fù)雜，但是在本文中，只是考慮了其確定最佳窗口的實(shí)現(xiàn)，因而整個(gè)算法被簡化，它對噪聲有一定的抵抗，提取的特征點(diǎn)結(jié)果都是非常典型的角點(diǎn)，定位精度比Moravec算子高；Harris算子比本文中前兩個(gè)算子都要復(fù)雜一些，因?yàn)槎嗔艘粋€(gè)高斯濾波的步驟，計(jì)算時(shí)間是三個(gè)算子中最長的一個(gè)，提取結(jié)果中L型角點(diǎn)的定位精度是三種算子里面最好的，但是其它角點(diǎn)定位誤差較大，對噪聲的抵抗性也較差。但在實(shí)際的應(yīng)用中，可以發(fā)現(xiàn)Harris更加可靠，提取出來的點(diǎn)分布較為均勻，數(shù)量也比較適中；而Moravec由于對鋸齒狀的邊緣非常敏感往往會(huì)產(chǎn)生很多的無效特征點(diǎn)的提取，F(xiàn)orstner提取的特征點(diǎn)會(huì)比較少而不滿足于如DEM密集點(diǎn)生成等任務(wù)。3 結(jié)束語在本次試驗(yàn)中，對三種常見的點(diǎn)特征提取算法進(jìn)行了討論，由于某些原因本文只是按照最原始的理論對三種算子做了算法的實(shí)現(xiàn)。通過對測試圖像的提取結(jié)果分析，對三種算子各自的特點(diǎn)做了描述，并做了簡單的橫向分析比較。在試驗(yàn)中還發(fā)現(xiàn)了一些問題：（1）對于Moravec算子的灰度差平方和可以做加權(quán)改進(jìn)，這樣可以提高算子定位的準(zhǔn)確度。（2）在實(shí)現(xiàn)三種算法時(shí)，發(fā)現(xiàn)先做極大值濾波再判斷閾值和先判斷閾值再做極大值濾波兩種方法提取的效果差別很大，但具體原因未作分析。（3）對于三種