一種有效的角點檢測與匹配算法

摘 要:角點的檢測和匹配是三維重建工作的基礎部分，也是關系到三維圖像重建準確性的重要部分。提出了一種角點檢測算法，集多種經典算法之長處，用雙重不同的判定條件，提高了的角點檢測的速度，增加了檢測出的角點數，并且改善了角點的精確度。在此基礎上進一步提出使用簡單的模板匹配方法進行角點匹配。實驗表明，該算法簡單且精確度高，優于其他現有的算法，而且能夠得到足夠多的匹配對進行下一步的三維重建工作。

關鍵詞:角點檢測;角點匹配;三維重建;角點精確度

中圖分類號:TP311文獻標識碼:A

文章編號:1004-373X(2010)04-045-04

An Efficient Algorithm of Corner Detecting and Matching

ZHOU Shuhuang，YUAN Jie

(Nanjing University，Nanjing，210093，China)

Abstract:In three-dimensional reconstruction，the task of corner-detecting and matching，not only is a basic part，but also has respect to veracity of the reconstruction.The algorithm introduced in this paper，with the merits of some classical algorithms，using two different conditions to make judgment，which can effectively improve the velocity of detecting，the quantity of corners，and the precision of corner-detecting.On this basis，a simple method，using the template matching，is used to match the corners.Experiments show that this algorithm is proved to be better than some other existing ways.It is simpler and more accurate，the number of matched pairs of corners which is large enough can be obtained for the next step of three-dimensional reconstruction.

Keywords:corner-detecting;corner-matching;three-dimensional reconstruction;preision of corner

0 引 言

在三維圖像重建的工作中，角點的檢測和匹配是很重要的前期準備。在角點檢測和匹配的領域，前人做了很多工作，如Harris算法[1]、SUSAN算法[2-4]、sift算法[5]等。Harris算子是由C.Harris和M.J.Stephens于1988年提出的一種基于信號的點特征提取算子，此算子受信號處理中自相關函數的啟發，給出與自相關函數相聯系的矩陣M。M陣的特征值是自相關函數的一階曲率，如果兩個特征值曲率值都高，那么就認為該點是角點。該算法雖然速度較快，但是檢測出來的角點較少，會影響下一步的匹配。SUSAN算法是1997年英國牛津大學的Smith等人提出的一種處理灰度圖像的方法。該算法將位于圓形窗口模板中心等待檢測的像素點視為核心點。核心點區域可以劃分為亮度值等于或相似于核心點亮度的區域，即核值相似區(USAN)和亮度值不相似于核心點亮度的區域。該算法比較直觀，但是會出現的誤檢測。SIFT算法的主要思想是利用多尺度變換在尺度空間中找極值點，提取角點位置和方向，使其對圖像縮放、旋轉、光線變化甚至仿射變換保持不變，算法比較復雜，速度也不高。近年來有不少針對這幾種經典算法做出改進的算法出現，比如:多尺度的Harris角點檢測[6]，有一定的抗噪能力，但是和SIFT算法一樣，在多尺度空間條件下算法比較復雜;RSUSAN角點檢測算法[7]重新定義SUSAN算法中小核值相似區，抗噪能力好，但是對于SUSAN算法的誤檢測情況沒有多大的改善。

近期研究的角點匹配算法基本可以分為兩大類:

(1)基于窗口的匹配。窗口是由待匹配點附近的象素灰度值組成的二維矩陣。其中最常用的是用交叉相關性來匹配[8]，不使用固定大小的窗口，而是用連接窗，在全局范圍內進行匹配，該方法對于處理重復紋理具有較好的效果。

(2)基于特征的匹配。在匹配前先要抽取邊或區域等特征。這些特征是圖像內容更抽象的描述，在不同的光照下具有更多的不變性。但是特征匹配往往有很高的計算代價，如Daniel等[9]提出一種在正交和影射變換下判斷兩組點集是否是由同一組二維或三維點集映射而成的方法。遺憾的是，三維情形下這種算法的時間復雜度接近n的7次方，n是角點數，且文中并未給出一個應用的例子。

這里提出的角點檢測算法吸取Harris算法和SUSAN算法的優點，并對兩者的不足之處做出改進。利用Harris算法速度較快的特點，對全圖先粗檢測一遍，并不要求有多高的精確度，要求盡可能多的真角點被找到，而去除偽角點的工作由接下來的SUSAN算法實現。由于此時只要驗證之前的角點真偽，計算量大大減少，也就繞過了SUSAN算法耗時長的問題。另外，兩種不同的決策方式對于精確度也有很大的幫助。在角點檢測過程中沒有提取描述特征，故本文的匹配算法是基于窗口匹配的。但與利用交叉相關性，找支持點的方法相比，該算法直接采用模板匹配，方法簡單很多，沒有復雜的計算過程，但是仍然能夠達到很好的效果;而相較于比較簡單的直方圖比較，由于是對每個像素點的一一比較而不是將灰度級化那樣粗略地描述灰度特征，準確度更高。

1 圖像角點的提取

在實驗中發現，僅用Harris算法比較快，但是檢測出來的角點過少，會影響下一步的匹配。而僅用SUSAN算法不僅慢，而且檢測出來的偽角點較多，也會影響匹配效果。因此，考慮將兩者相結合，以提高檢測的效率和準確度。檢測過程中，先使用差分算子與圖像卷積(見式(1))，計算圖像在x和y方向的梯度Ix，Iy。

Ix=Ix=I[-1，0，1];

Iy=Iy=I[-1，0，1]T(1)

為了提高抗噪能力，對圖像進行了高斯平滑(見式(2))，進而計算出興趣值(見式(3))。

G=exp[-(x2+y2)/2σ2]; A=I2xG;

B=I2yG; C=IxIyG;

M=AC

CB(2)

H=|M|-k#8226;tr2(M)(3)

式中:σ取值為0.8;k取值為0.04;tr2(M)為矩陣M的跡。矩陣H為每一點的元素值對應于原圖相應點的興趣值。角點響應準則為:H在角的區域是正值，在邊的區域是負值，在內部是很小的值。計算圖像窗口中心點的H值，如果大于某個給定的門限值，就認為這個點是角點。實驗中發現，給定一定的門限，檢測出來的角點雖然有準確度，但是數量較少，而放大門限，則會增添偽角點，使準確度降低很快。該算法在Harris算法后再用USAN準則約束，去偽存真。實驗中采用較小的門限，盡可能多地將真角點檢測出來，在SUSAN部分把偽角點剔除。

在SUSAN部分，采用37點模板，即在7×7的窗口內選取一個八邊形來近似USAN準則中的圓形，如圖1所示，其用于灰度比較。灰度比較時，并不像經典SUSAN算法中所描述的將核心點與其他點做比較，取一個固定的閾值，而是在核心點十字區域的點與之比較的結果使用的閾值相較于其他部分與核心點灰度的差值的閾值要稍小一點。在實驗得出，前者的閾值h1為10，而后者的閾值h2為30時效果較好。由于偽角點的情況包括角點在圖形內部、邊緣以及角點是噪聲的情況，故對于R不僅要設有上限去除在內部的偽角點還應該設有下限剔除噪聲引起的誤檢測。初始響應函數為:

R=1，if|n(0)|t2

0，else(4)

式中:n(0)=∑c(;0)，c(，0)是灰度比較結果。而n(0)的上下限是在實驗中得出的能有效過濾偽角點的閾值，其中上限取49/3，下限取49/5。

圖1 37模板

該部分流程圖如圖2所示。

圖2 角點檢測流程圖

在實驗中，興趣值矩陣H中每個元素的閾值在500~5 000中選取，步進值為500，選取能得到最多角點的值作為閾值。實驗表明，過小或過大的閾值對檢測結果影響不大，而且過小的步進對于結果也變化不大。這樣的選擇對于結果以及計算量都比較適中。

2 角點匹配

由于上一步角點檢測結果偽角點極少，故在匹配時，對于相對位移較小(如勻速運動的相鄰幀)的圖片，只要采用基于灰度的塊匹配就可以達到很好的效果。位移大小的判定和搜索窗口的大小相關，但正由于是小位移圖像，模板匹配才能達到很好的效果，因為位移小，物體同一部分的光照變化，位置變化以及局部灰度變化都可視作極小。由于通常情況下待檢測物體都應該出現在圖片中央，所以在角點匹配之前，進行的預處理，將兩圖邊緣部分視為無角點區域，即使存在真角點也視為偽角點，用的是先驗知識，可以大大減少運算量。在一個鄰域中(實驗中在15×15的鄰域中進行搜索)，一幅圖像的角點在另一幅中可能沒有對應角點，則視該角點不屬于任一匹配對，但也可能找到多個可能匹配的角點，反之亦然，這樣就形成了一個多對多的映射。實驗中，以一幅圖像(設為pic1)的角點為中心，在另一幅圖像(設為pic2)中選取15×15的鄰域(鄰域的選取和兩圖相對位移的大小有關)，視該區域內的角點為可能匹配的角點，其他角點都不是能匹配的角點，采用絕對平均誤差準則:

MAD=1mn∑mi∑njA(i，j)-B(i，j)(5)

以此選取灰度最為接近的角點作為匹配對。雖然均方誤差(MSE)在這些場合用的比較多，但是在實驗中發現，與MAD相比，使用MSE并不能有效提高匹配的準確率，反而增加運算量，故選擇MAD的方法。設pic1的某角點P在pic2中的對應的角點有(P1，P2，…，Pi)，逐一計算不同角點對的MAD，選取最小的MAD對應的角點為匹配角點，這樣可能匹配出來的角點對還會是一個多對多的結果，與匹配之前相比只是角點對減少了。于是，再反向匹配一次，即由pic2向pic1匹配，得到的匹配對與上一次所得的匹配對取同或作為最后的結果。該部分流程圖如圖3所示。

通常，對于MAD結果應取一定的閾值來選定。實驗中發現，選取最小的MAD值就可以達到目的，不需要去找到合適的閾值，故該算法采用了這樣的判斷條件。

3 實驗結果

實驗表明，該算法匹配精度高，匹配對的數量也有一定的保證，足以支持下一步的重建工作。從標準圖像庫取出一幅圖像如圖4所示。

圖3 角點匹配流程圖

圖4 魔方原圖像

檢測結果如下:圖5(a)中的白色框標示了用本文所介紹的方法檢測出的角點;圖5(b)為用Harris算法所做檢測;圖5(c)為用SUSAN算法所做檢測。

圖5 檢測結果

由圖5可以清楚看出，用本文所述方法檢測出的角點數介于Harris算法和SUSAN算法檢測出的數量之間，與Harris算法相比，角點數顯著增多，而相比于SUSAN算法，本文的算法沒有出現偽角點，精確度大大提高。在運算時間上的比較，此圖用SUSAN算法要耗時38.328 s，本文所提出的算法則只需要7.547 s，并且是在自適應閾值的情況下。與SUSAN算法相比，效率上的優勢十分明顯。

從標準圖像庫取出幾幅相對位移較小的圖片進行匹配。結果如圖6，圖7所示。

圖6 匹配結果(一)

圖7 匹配結果(二)

與實際匹配對相比，在大多數情況下，本文的算法能達到很高的準確率，統計表明，匹配率最高可達到100%，最低也能達到86.7%，平均精度能達到97.27%。錯誤的匹配對都出現在灰度變化較小的紋理且角點密集處， 而非幾何角點， 由于所得點數足夠在計算三維坐標時列出超定方程，故少量的錯誤匹配可以濾除。

4 結 語

本文的角點檢測算法取兩種經典算法之長，避其之短，充分利用了圖片的灰度信息，算法思想簡單清晰，效果增益明顯。建立在這樣的檢測效果上，角點匹配的方法只要利用了圖片的灰度信息和位置信息，不用過多的互相關信息或者角點的梯度、方向等信息，就能達到很好的準確性和有效性，與已有的方法相比要簡單許多。二者相結合，足以為三維重建工作，做好充分的準備。但是，新的算法針對的是位移較小的兩幅圖片，即默認物體或者是相機勻速低速運動，對于位移較大圖片則會出現錯誤。要在這一方面進行改進，可以采用塊匹配的方法[10]，做運動檢測、運動估計等方面的工作。

參考文獻

[1]尹丹，滿家巨，王梓豪.一種改進的點特征圖像匹配算法[J].計算機與現代化，2008(3):70-72，76.

[2]Smith S M，Brady J M.SUSAN-A New Approach to Low Level Image Processing[J].Int.Journal of Computer Vision，1997，23(1):45-78.

[3]Ewaryst Rafajlowicz.SUSAN Edge Detector Reinterpreted，Simplified and Modified[J].Multidimensional Systems，2007:69 - 74.

[4]Zhou Dongxiang，Liu Yunhui，Cai Xuanping.An Efficient and Robust Corner Detection Algorithm[A].Intelligent Control and Automation[C].2004，5:4 020-4 024.

[5]Lowe D G.Distinctive Image Features from Scale Invariant Key Points[J] International Journal of Computer Vision，2004，60 (2):91-110.

[6]張小洪，李博，楊丹.一種新的Harris多尺度角點檢測[J].電子與信息學報，2007，29(7):1 735-1 738.

[7]楊莉，張宏，李玉山.一種快速自適應的RSUSAN角點檢測算法[J].計算機科學，2004，31(5):198-200.

[8]張遷，劉政凱，龐彥偉，等.基于SUSAN算法的航空影像的自動配準[J].測繪學報，2003，32(3):245-250.

[9]Daniel P Huttenlocher，Jon M Kleinberg.Comparing Point Sets Under Projection [A].Proceedings of the 5th Annual ACM -SIAM Symposium on Discrete Algorithms[C].Arlington，Virginia，1994:1- 7.

[10]Aroh Barjatya.Block Matching Algorithms for Motion Estimation[Z].DIP 6620，2004.