改進FAST特征點支持下的實時影像地標匹配算法

楊琪莉 朱蘭艷 李海濤

摘要：針對圖像匹配技術(shù)中匹配時間與匹配精度不能同時滿足要求的問題，提出一種基于特征點匹配的方法，利用隨機森林分類器實現(xiàn)地標的匹配，將匹配問題轉(zhuǎn)化為簡單的分類問題，大大簡化了計算過程，保證影像匹配實時性；采用FAST特征點表示影像地標，利用高斯金字塔結(jié)構(gòu)以及仿射增強策略改進FAST特征點的尺度和仿射不變性，提升影像地標匹配率。將實驗結(jié)果與尺度不變特征變換（SIFT）算法和加速魯棒性（SURF）算法進行比較。實驗結(jié)果表明在尺度變化、發(fā)生遮擋以及旋轉(zhuǎn)情況下，匹配率能達到90%左右，保持與SIFT算法和SURF算法相近的匹配率，并且匹配時間相較其他兩種算法減少了一個數(shù)量級，能有效地對影像地標進行匹配，匹配時間也滿足實時影像地標匹配要求。

關(guān)鍵詞：隨機森林；地標匹配；FAST特征點；高斯金字塔結(jié)構(gòu)；仿射增強策略

中圖分類號：TP391.41 文獻標志碼：A

Abstract：Concerning the problem that matching time and accuracy requirements can not be met the simultaneously in image matching technology， a method based on feature points matching was proposed. Landmark matching was achieved successfully by using Random Forest （RF）， and matching problem was translated into simple classifying problem to reduce the complication of computation for realtime image matching.

Landmark image was represented by Features from Accelerated Segment Test （FAST） feature points， the scale and affine invariability of FAST feature points were improved by Gaussian pyramid structure and affine augmented strategy， and the matching rate was raised. Comparing with ScaleInvariant Feature Transform （SIFT） algorithm and Speed Up Robust Feature （SURF） algorithm， the experimental results show that the matching rate of the proposed algrorithm reached about 90%， keeping the matching rate approximately with SIFT and SURF in cases of scale change， occlusion or rotation， and its running time was an order of magnitude than other two algorithms. This method matches landmarks efficiently and its running time meets the realtime requirements.

Key words：Random Forest （RF）； landmark matching； Features from Accelerated Segment Test （FAST） feature point； Gaussian pyramid structure； affine augmented strategy

0 引言

影像地標匹配的主要支撐技術(shù)是圖像匹配。文獻[1]將圖像匹配主要分為基于灰度相關(guān)匹配和基于特征匹配。其中，基于特征匹配又可以細分為基于特征點匹配以及基于變換域匹配兩種類型。文獻[2]總結(jié)出了灰度相關(guān)匹配方法是利用對待匹配圖像遍歷窗口進行相似性比較的方式進行搜索匹配的方法，該方法計算量較大，圖像相似性計算對尺度變化和旋轉(zhuǎn)情況比較敏感。文獻[3]指出基于特征的匹配方法通過對兩幅圖像提取特征，按照某種數(shù)學(xué)法則或幾何約束方法對特征進行描述，通過特征匹配實現(xiàn)圖像的匹配；

該方法匹配效果好，但是計算復(fù)雜，達不到實時性要求。文獻[4]對基于特征點的圖像匹配算法進行概述，主要有尺度不變特征變換（ScaleInvariant Feature Transform， SIFT）算法以及加速魯棒性（Speed Up Robust Feature， SURF）算法，Lowe[5]提出SIFT算法，通過引入高斯拉普拉斯算子建立尺度空間、卷積運算和差分近似，保證了特征點的尺度不變性，旋轉(zhuǎn)不變性和仿射不變性，但是相應(yīng)地增加了其計算復(fù)雜度，運行時間達不到實時性要求。Bay等[6]提出SURF算法，在SIFT算法的基礎(chǔ)上進行了改進，利用Hessian矩陣和積分圖像縮短了特征點計算時間，采用Haar小波計算特征點主方向，該算法匹配速度大于SIFT算法，但仍然沒達到實時性的要求。文獻[7-8]分別對兩種算法進行影像匹配應(yīng)用研究。變化域匹配方法將圖像進行相應(yīng)的特征空間轉(zhuǎn)換， 在空間變化域進行圖像匹配，該方法能有效處理圖像的旋轉(zhuǎn)和尺度變化，但其計算復(fù)雜、計算量大，不滿足實時性要求。

Lepetit等[9-10]提出運用隨機森林算法進行寬基線匹配，根據(jù)這一思路，可將影像地標匹配轉(zhuǎn)換為分類問題進行處理。隨機森林算法通過將匹配過程分為離線訓(xùn)練以及在線匹配兩個過程，離線過程對目標圖像計算FAST（Features from Accelerated Segment Test）特征點，并訓(xùn)練得到隨機森林。文獻[11-12]對隨機森林算法學(xué)習(xí)以及利用隨機森林對目標進行檢測、跟蹤、識別等方面進行研究。由于FAST特征點的提取只與影像的灰度值有關(guān)，不具有尺度不變形和仿射不變性，對光照變化、旋轉(zhuǎn)變換與尺度變化等較為敏感，會對隨機森林的匹配性能產(chǎn)生影響。不同于SIFT、SURF穩(wěn)健的特征點提取過程，為了保證算法的實時性，本文利用高斯金字塔結(jié)構(gòu)以及仿射增強對FAST特征點進行改進，使其具有尺度不變性和仿射不變性的同時，亦能保持實時匹配性能。

根據(jù)式（5）建立高斯金字塔，將目標圖像設(shè)置為金字塔第0組的第0層圖像I00，對I00進行降采樣處理可生成圖像I10（金字塔第一組第0層圖像），以此類推可建立好高斯金字塔結(jié)構(gòu)中每一組的第0層圖像；對圖像Ii0進行高斯模糊操作生成圖像Ii1，對每一組中的第0層圖像依次進行高斯模糊可生成該組的其他層圖像。即采用組間降采樣處理，層間高斯模糊操作的方式構(gòu)建高斯金字塔尺度空間。本文算法采用高斯模版為7×7，設(shè)置金字塔組數(shù)為3，每組圖像層數(shù)為3。

建立好影像尺度空間，分別計算在金字塔每組下的每層圖像的FAST特征點集 Fscale_ij，金字塔每組的特征點為Fscale_i={ Fscale_i1，F(xiàn)scale_i2，…，F(xiàn)scale_ij}；將金字塔每組特征點集合到一起形成帶有尺度屬性的影像FAST特征點集F={Fscale_1， Fscale_2，…，F(xiàn)scale_i}；影像FAST特征點集F能表示不同尺度下的同一幅地標影像，增強FAST特征點的尺度不變性。

圖1表示目標地標圖像在不同尺度空間下的FAST特征點， 圖（a）為高斯金字塔圖像的第0層以及在該尺度下的FAST特征點集，圖像分辨率為715×438；圖（b）為高斯金字塔圖像的第1層以及在該尺度下的FAST特征點集，圖像分辨率為357×219；圖（c）為高斯金字塔圖像的第2層以及在該尺度下的FAST特征點集，圖像分辨率為178×109。由圖1可以看出，在不同的尺度空間下圖像的特征點概括了不同圖像信息，圖（a）特征點表示圖像的細節(jié)信息，圖（b）特征點表示的主要是圖像的邊緣信息等，圖（c）特征點表示的信息比較概括。

考慮到地標影像的表現(xiàn)形式，對仿射矩陣的參數(shù)進行了優(yōu)化設(shè)置。地標影像通常不會出現(xiàn)與原始圖像完全翻轉(zhuǎn)等情況，對于兩個旋轉(zhuǎn)角度進行實驗優(yōu)化，設(shè)置角度參數(shù)θ，φ的取值范圍為[-π/2，π/2]，比例縮放因子λ1、λ2取值范圍為[0.5，1.5]。由于有些地標的特殊性，有些地標影像基本上不會發(fā)生遮擋的情況（如實驗一地標），可以對平移矩陣進行抑制，有些影像在采集過程中可能會受到圍欄、樹木等的影響發(fā)生遮擋（如實驗二地標），可以設(shè)置合適的平移矩陣。通過對仿射矩陣參數(shù)的優(yōu)化設(shè)置，使得訓(xùn)練過程中的仿射圖像能較好地模擬現(xiàn)實情況中的地標表現(xiàn)形式。圖2是部分實驗一過程中的仿射圖像，其分別對應(yīng)的仿射矩陣Ai如表1所示。

1.3 關(guān)鍵點選取

選取關(guān)鍵點是隨機森林算法離線過程中重要的部分，選取對目標地標影像表達能力強的關(guān)鍵點，對隨機森林分類正確率有至關(guān)重要的作用。本文算法在FAST特征點的基礎(chǔ)上，利用高斯金字塔和仿射增強策略對其進行改進，使FAST特征點具有尺度不變性和仿射不變性。通過計算目標圖像的改進FAST特征點集，從中選取表達能力強的作為目標圖像的關(guān)鍵點集。改進FAST選取關(guān)鍵點集過程如下：

1）對目標圖像按1.1節(jié)建立尺度空間，即建立高斯金字塔結(jié)構(gòu)。

2）在每個金字塔尺度空間中每一組圖下的每一層圖像Ij提取FAST特征點Fscale_ij={fi}，圖像高斯金字塔每一層圖像上提取的特征點的集合形成該圖像的FAST特征點F={Fscale_i}。

3）按仿射增強策略，將目標地標影像根據(jù)仿射矩陣Ai進行仿射變化生成仿射影像，并按照1）、2）步對仿射影像提取FAST特征點F′={ Fscale_i′}。

4）根據(jù)仿射矩陣Ai，逐個計算特征點集合F和F（中的同一尺度下的特征點fi和fj′的相似性，若fi-A-1fj′

5）重復(fù)3）、4）步，直到滿足仿射停止條件（本算法設(shè)置仿射次數(shù)為1000）。

選取出現(xiàn)次數(shù)最多的FAST特征點產(chǎn)生關(guān)鍵點集K={K1，K2，…，KN}。

2 隨機森林匹配

利用隨機森林匹配影像地標，將傳統(tǒng)的匹配方式轉(zhuǎn)換為離線的訓(xùn)練過程和在線的匹配過程。在離線過程對地標圖像建立尺度空間并進行特征點檢測，按照仿射增強的策略選取圖像的穩(wěn)定點，生成N個點的關(guān)鍵點集K={K1，K2，…，KN}，利用該關(guān)鍵點集訓(xùn)練生成由m棵樹組成的隨機森林分類器CT={CT1，CT2，…，CTm}。在線過程，輸入圖像檢測特征點，并對每一個特征點i利用隨機森林分類器判斷其所屬類別Y（i）∈ C={-1，1，2，…，N}，-1表示沒有與N個類別中的任意一個匹配。

2.1 隨機森林訓(xùn)練

隨機樹的每個節(jié)點包含一個簡單的二元測試，通過節(jié)點測試剖分數(shù)據(jù)空間并分類。在每個葉子節(jié)點包含對所有類別的后驗概率分布。由于存在大量的數(shù)據(jù)類別、訓(xùn)練樣本和節(jié)點測試，建立單一的一棵隨機樹將無法滿足分類要求，需要建立多棵樹即森林，每棵樹產(chǎn)生不同的空間剖分。隨著隨機樹的數(shù)量和樹的深度增加，剖分變得越來越好，葉子節(jié)點的后驗概率分布越來越接近真實，但是相應(yīng)的計算復(fù)雜度和內(nèi)存的需求會越來越大。本文算法均衡了隨機森林的規(guī)模以及耗時，設(shè)定隨機樹的數(shù)目為16棵，每棵樹深度為10層。

隨機樹里的節(jié)點二元測試都是隨機生成的，節(jié)點二元測試與點m1、m2的亮度值有關(guān)，m1、m2是以特征點為中心的剖分空間（測試片元）中的兩個隨機點。若點m1亮度值小于m2亮度值，則該片元進入左子樹，否則，進入右子樹。將每個訓(xùn)練數(shù)據(jù)按照式（10）通過每棵隨機樹，并在葉子節(jié)點記錄下每個類別出現(xiàn)的概率，進行歸一化處理后生成后驗概率分布。

為保證隨機森林分類效果，在訓(xùn)練過程中分別從兩個方面保證本文算法的隨機性：在訓(xùn)練過程中的仿射增強階段，隨機選取范圍內(nèi)的仿射因子生成隨機仿射矩陣，保證訓(xùn)練樣本包含了所有的地標圖像出現(xiàn)的情況，使得關(guān)鍵點集能很好地表達地標建筑。在建立隨機森林的節(jié)點測試階段，測試位置的隨機選取，即每個節(jié)點隨機剖分數(shù)據(jù)空間，將每棵樹的隨機剖分結(jié)構(gòu)組合到一起形成的隨機森林具有很強的分類能力。

2.2 隨機森林分類

對一個新片元分類的時候，根據(jù)每棵樹的每個節(jié)點測試判斷新片元從左子樹或右子樹往下落，當落到葉子節(jié)點，葉子節(jié)點所存儲的概率分布將決定該片元所屬的類別。如圖5所示，當待分類片元按圖4（a）方法通過隨機樹時，都將落到某個葉子節(jié)點，圖5第一列列出部分葉子節(jié)點的概率分布，將通過每棵樹所得到的概率分布平均得到新片云的平均概率分布，其中最大概率類別即為片元類別。

2.3 本文算法過程

本文算法過程如下：

1）對目標地標影像按照第1章介紹提取關(guān)鍵點集，并生成關(guān)鍵點片元。

2）生成在每個節(jié)點都包含隨機二元測試的隨機森林。

3）按照2.1節(jié)方法，將步驟1）中的關(guān)鍵點片元投入步驟2）中的隨機森林，通過不斷的二元測試比較得到隨機森林葉子節(jié)點的后驗概率分布，至此隨機森林訓(xùn)練完畢。

4）對新的測試影像按1.1節(jié)建立尺度空間，計算其FAST特征點集Ftest并生成特征點片元。

5）測試影像的每個FAST特征點片元投入隨機森林，隨機森林分類器按2.2節(jié)將每個特征點進行分類。

6）通過隨機采樣一致性（RANdom SAmple Consensus，RANSAC）方法剔除誤分類點，得出匹配結(jié)果。

本文算法關(guān)鍵步驟：1）提取改進FAST穩(wěn)定點并生成穩(wěn)定點訓(xùn)練片元，2）訓(xùn)練隨機森林生成葉子節(jié)點概率分布，3）根據(jù)訓(xùn)練好的隨機森林對待分類片元進行分類。每個步驟計算簡單，計算復(fù)雜度低，保證算法的實時性。

1）提取改進FAST穩(wěn)定點，需要將原圖像進行仿射變換1000次，并對每一個仿射后圖像計算改進FAST特征點，最后對每個特征點出現(xiàn)次數(shù)進行排序，選取前400個作為穩(wěn)定點；由于對每個圖像計算改進FAST特征點只需幾十毫秒，整個穩(wěn)定點計算過程不會產(chǎn)生較大的時間開銷。

2）生成關(guān)鍵點訓(xùn)練片元，每個關(guān)鍵點就是一個類別，每個類別的訓(xùn)練片元由不同視角影像中的關(guān)鍵點片元組合而成，只需對圖像進行簡單的仿射變換，并根據(jù)仿射變換矩陣計算關(guān)鍵點位置坐標截取片元即可。

3）訓(xùn)練隨機樹，需要將每個類別的訓(xùn)練片元依次通過每一個節(jié)點，隨機樹的每個節(jié)點僅僅包含了簡單的二元比較，不涉及復(fù)雜的計算步驟，保證算法實時性。

4）隨機森林分類，利用隨機森林對待分類的片元分類時，只需要在每個樹節(jié)點進行簡單的二元比較，并對每個葉子節(jié)點的概率分布進行均值計算。

3 實驗結(jié)果與分析

為對本文算法的地標影像匹配效果進行驗證，分別從算法匹配效率以及匹配正確性兩方面將實驗結(jié)果與SIFT算法、SURF算法以及原始FAST特征點隨機森林算法進行比較，采用兩組實驗數(shù)據(jù)表明本文算法在保證匹配正確率的情況下匹配時間上的優(yōu)點。第一組數(shù)據(jù)是昆明市地標建筑碧雞坊，地標圖像為碧雞坊正面視圖圖像，分辨率為715×438，測試圖像為任意角度下的碧雞坊圖像，圖像分辨率為348×464；第二組實驗數(shù)據(jù)地標建筑是陸軍講武堂，地標圖像分辨率為355×433，測試圖像分辨率為608×810。實驗硬件環(huán)境為Intel Core i3 2.13GHz CPU，2GB RAM；軟件環(huán)境為Microsoft Visual Studio 10.0及OpenCV 2.45。

實驗一地標碧雞坊為城市中心地標建筑，采集的圖片含有行人、車輛以及周邊建筑物的干擾信息。表2列出了實驗一測試圖像計算4種特征點所需時間，F(xiàn)AST特征點計算所需時間最短，其次為本文改進FAST特征點，最后是SURF和SIFT算法。FAST特征點雖然計算速度快，但直接用其進行匹配效果不理想，本文改進FAST特征點，加強了FAST特征點的尺度和仿射不變性，仍能保持算法的實時性；在匹配時間方面，本文算法相對SIFT算法和SURF算法減少了兩個數(shù)量級，能實現(xiàn)對地標影像的實時匹配。

本文算法利用改進FAST特征點匹配并對匹配后的匹配點對運用RANSAC剔除誤匹配。當匹配點數(shù)大于20即可表示兩個地標圖像匹配成功。實驗一測試影像在尺度上相較于目標影像發(fā)生了很大的變化，F(xiàn)AST特征點不具備尺度不變性，利用FAST特征點隨機森林算法匹配未成功。在影像發(fā)生遮擋或是影像中有大量的相似的結(jié)構(gòu)時，SIFT算法和SURF算法會產(chǎn)生一定誤匹配。三種算法實驗結(jié)果如圖7所示，結(jié)果表明本文算法具有很好的匹配性能。

表3將實驗一的結(jié)果進行對比分析，分別對圖7中的兩組圖像的匹配點數(shù)、點匹配率和匹配時間進行了分析。點匹配率是對測試圖像計算得到的特征點與匹配成功的點的比值。經(jīng)過對比分析，本文算法能保持與SIFT相近的點匹配率，成功匹配地標影像，并且在匹配時間方面遠遠優(yōu)于其他兩種算法，實現(xiàn)實時匹配地標。

實驗二對地標建筑陸軍講武堂進行測試，與實驗一地標碧雞坊相比背景相對簡單。實驗二測試影像在尺度上較目標影像變化不大，只是產(chǎn)生較大的旋轉(zhuǎn)、遮擋以及雜亂背景等情況。FAST特征點隨機森林算法對圖8三個影像的點匹配數(shù)分別為：8、20和21（RANSAC后），對發(fā)生較大旋轉(zhuǎn)的情況無法進行匹配。本文算法在訓(xùn)練階段利用仿射增強策略增強FAST特征點仿射不變性，能對實驗二測試影像高效匹配，實驗結(jié)果見圖8。

對實驗二結(jié)果進行統(tǒng)計分析，從匹配效率以及匹配正確性兩方面與SIFT算法、SURF算法以及FAST隨機森林算法進行比較，對比結(jié)果如圖9所示。

圖9（a）表示四種算法的匹配時間對比分析，采用樣本量為10的倍數(shù)，分別統(tǒng)計四種算法進行匹配所需時間。對比結(jié)果表明，本文算法平均的匹配時間大約在220ms每個圖像，F(xiàn)AST隨機森林算法匹配時間大約在180ms，而SIFT算法和SURF算法分別在4000ms和8500ms左右每個圖像。通過對比本文算法在匹配速率遠遠優(yōu)于其他兩種算法，與SIFT算法和SURF算法匹配時間的1/10進行比較仍然是本文算法具有更優(yōu)匹配速率。匹配正確率對比分析，采用樣本量為10的倍數(shù)，統(tǒng)計四種算法的匹配正確率如圖9（b）。本文算法匹配率在90%左右，F(xiàn)AST特征點隨機森林算法在60%左右，SIFT算法和SURF算法匹配正確率分別維持在92%和95%左右。本文算法在匹配正確率方面稍弱于SIFT和SURF算法，但是遠遠高于FAST特征點隨機森林算法。本文算法在保證匹配正確率與SIFT算法和SURF算法相近的情況下，匹配時間滿足實時性要求。

4 結(jié)語

本文提出了利用改進FAST特征點的隨機森林算法進行影像地標的匹配，實現(xiàn)對地標的識別。對昆明市地標建筑碧雞坊和陸軍講武堂分別進行實驗，并將實驗結(jié)果與SIFT算法、SURF算法以及FAST特征點隨機森林算法進行比較。在匹配正確率方面本文算法通過改進FAST特征點將匹配正確率從60%提升到90%，保證與SIFT算法和SURF算法相近的匹配正確率。在匹配效率上較SIFT算法和SURF算法而言，提高了不止10倍，滿足實時性要求。通過實驗驗證了本文算法在保證匹配正確率的同時能有效地提高匹配效率，能快速且高效地對地標圖像進行匹配識別。由于本文只訓(xùn)練了地標建筑的正面圖像，只能對地標建筑物的正面進行匹配與識別，可以對地標建筑建立三維模型再進行匹配與識別。

參考文獻：

[1]ZITOVA B， FLUSSER J. Image registration methods： a survey [J]. Image and Vision Computing， 2003， 21（11）：977-1000.

[2]饒俊飛.基于灰度的圖像匹配方法的研究[D]. 武漢： 武漢理工大學(xué)， 2005：14-19.（RAO J F. Research of image matching method based on intensity[D]. Wuhan： Wuhan University of Technology， 2005：14-19.）

[3]惠國保， 童一飛， 李東波. 基于改進的圖像局部區(qū)域相似度學(xué)習(xí)架構(gòu)的圖像特征匹配技術(shù)研究[J].計算機學(xué)報， 2015， 38（6）：1148-1161. （HUI G B， TONG Y F， LI D B. Image features matching based on improved patch similarity learning framework[J]. Chinese Journal of Computers， 2015， 38（6）：1148-1161.）

[4]MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors[C]// Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2003：257-263.

[5]LOWE D G. Distinctive image features from scale invariant keypoints [J]. Computer Vision， 2004， 20（2）： 91-110.

[6]徐秋輝， 佘江峰， 宋曉群， 等. 利用HarrisLaplace和SIFT描述子進行低空遙感影像匹配[J].武漢大學(xué)學(xué)報（信息科學(xué)版）， 2012， 37（12）：1443-1447.（XU Q H， SHE J F， SONG X Q， et al. Matching low altitude RS image with HarrisLaplace and SIFT descriptor[J]. Geomatics and Information Science of Wuhan University， 2012， 37（12）： 1443-1447.）

[7]BAY H， TUYTELAARS T. SURF： speeded up robust features[C]// ECCV 2006： Proceedings of the 9th European Conference on Computer Vision， LNCS 3951. Berlin： Springer， 2006： 404-417.

[8]閆利， 陳林. 一種改進的SURF及其在遙感影像匹配中的應(yīng)用[J]. 武漢大學(xué)學(xué)報（信息科學(xué)版）， 2013， 38（7）： 770-773.（YAN L， CHEN L. A modified SURF descriptor and its application in remote sensing image matching[J]. Geomatics and Information Science of Wuhan University， 2013， 38（7）： 770-773.）

[9]LEPETIT V， FUA J P. Keypoint recognition using randomized trees [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006， 28（9）： 1465-1479.

[10]LEPETIT V， PILET J， FUA P. Point matching as a classification problem for fast and robust object pose estimation[C]// CVPR 2004： Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2004， 2： II244【【頁碼就這樣排II250.

[11]LEISTNER C， SAFFARI A， BISCHOF H. MIForests： multipleinstance learning with randomized trees[C]// ECCV 2010： Proceedings of the 11th European Conference on Computer Vision， LNCS 6316. Berlin： Springer， 2010：29-42.

[12]GALL J， YAO A， RAZAVI N， et al. Hough forests for object detection， tracking， and action recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（11）： 2188-2202.

[13]ROSTEN E， DRUMMOND T. Machine learning for highspeed corner detection[C]// ECCV 2006： Proceedings of the 9th European Conference on Computer Vision， LNCS 3951. Berlin： Springer， 2006： 430-443.