一種改進KNN的無人機圖像快速拼接方法

羅 凱，徐俊武，楊 敏

武漢工程大學計算機科學與工程學院，湖北 武漢430205

隨著時間推移，無人機技術(shù)和遙感技術(shù)發(fā)展迅速，利用無人機航拍遙感圖像對病蟲害治理已成為人們熟用的手段。由于無人機具有較強的靈活性、拍攝清晰等特點，可馬上為災情調(diào)查和病害防控提供資料。但同時無人機航拍存在視角小、易受天氣和地貌等因素的影響的問題，導致拍攝無法看清其全貌，單張圖像往往無法展示全部的目標區(qū)域，或者目標區(qū)域較為模糊，通常是拍攝多幅圖像進行圖像拼接。圖像拼接是將兩幅或者多幅圖像拼成一幅清晰度較高的全景圖像。其中圖像拼接最重要的步驟就是圖像配準。

Harris于1988年提出了Harris角點檢測算法［1］，采用角點響應函數(shù)R并提取R的局部最大值來提取特征點。潘梅等［2］改進了Harris算法，利用無人機技術(shù)實現(xiàn)了圖像拼接，拼接質(zhì)量得到提升。2004年Lowe提出的尺度不變特征變換算法［3］（scale-invariant feature transform，SIFT）對圖像縮放、旋轉(zhuǎn)有強適應性。后來Bay在SIFT算法的基礎(chǔ)上，提出了加速健壯特征算法［4］（speeded-up robust features，SURF），加入Hessian矩陣快速選取候選點，并對其進行非極大抑制。

針對KNN算法特征匹配耗時慢等問題提出一種基于圖像像素點經(jīng)緯度改進KNN的無人機航拍圖像特征點配準算法。首先利用SIFT算法提取圖像的特征點然后對其進行描述，然后提取出無人機機載系統(tǒng)里拍攝的數(shù)據(jù)信息計算出圖像像素點的經(jīng)緯度，然后計算出兩張圖像重合部分，由于兩張圖像重合部分特征點經(jīng)緯度大致相似，因此利用這一特點加快KNN算法匹配特征點的時間，然后使用隨機抽樣一致算法（random sample consensus，RANSAC）算法［12］篩選出錯誤匹配點，最后圖像融合利用最佳縫合線算法。實驗結(jié)果表明，本文所提出的算法是一種能夠快速匹配到正確特征點、效率高并且能夠得到一副清晰全景圖的航拍圖像拼接方法。

1 圖像配準方法

1.1 改進KNN算法

KNN匹配算法通過兩點向量之間的距離來判斷這兩個向量是否相似，一般選取K個與特征點相似的點，K通常取2，如果選取的點相似度低，那么其中最相似的點為最近鄰匹配點。在進行配準時，將配準圖像中提取出來的特征向量與待配準圖像中提取的特征向量求距離，找到兩個向量間最近的距離，將兩個匹配向量距離的比值與閾值進行比較，判斷是否正確。由于無人機拍攝角度小，低高度飛行，相鄰拍攝圖像間存在大面積的重疊區(qū)域，并且正確的特征匹配對都在該重疊區(qū)域內(nèi)，所以對全圖進行特征提取，計算量非常大，效率也因此降低。

為了加快KNN算法的匹配時間，本課題組從無人機機載系統(tǒng)里提取出無人機拍攝時的經(jīng)緯度坐標、高度和飛行速度等信息，通過這些信息計算出相鄰圖像的重疊區(qū)域和圖像像素點的經(jīng)緯度數(shù)據(jù)，那么就可以通過計算出來的重疊區(qū)域，對該區(qū)域進行特征提取，在特征匹配時，只對該區(qū)域進行匹配點對的判斷，由于相鄰圖像間重疊區(qū)域里的特征點經(jīng)緯度數(shù)據(jù)是大致相同的，可以很快地定位到待配準圖像匹配點所在的位置，那么在該匹配點鄰域內(nèi)的其他特征點就可以快速匹配成功，從而不僅使得匹配成功的概率大幅提升，匹配的時間也將縮短。

1.1.1 重疊區(qū)域計算 在本次實驗中無人機飛行時間為20 m/s，利用飛行航向偏角和成像中心點經(jīng)緯度數(shù)據(jù)建立相鄰圖像的位置關(guān)系，以此估計重疊區(qū)域大小，確定特征提取區(qū)域，計算具體步驟如下：

步驟1：設(shè)兩張相鄰照片為P和Q，圖像P中心點經(jīng)度為x1，緯度為y1；圖像Q中心點經(jīng)度為x2，緯度為y2，那么兩點之間距離l為：

其中地球半徑R=6 371.01 km，π取3.141 59。

2）注漿壓力變化。注漿過程中，壓力要在控制范圍內(nèi)，防止出現(xiàn)過大或過小現(xiàn)象，若壓力過低，要檢查是否漏漿或查找漿液是否通過地下某管道流走；壓力過大，應檢查是否管路或混合器被堵塞，施工時需要控制注漿壓力小于規(guī)定的注漿壓力值。

步驟2：根據(jù)每張圖像經(jīng)緯度數(shù)據(jù)，通過代碼模擬出無人機飛行軌跡。

步驟3：圖像拍攝間隔為3 s，兩張圖像間轉(zhuǎn)向角度不會太大，從飛行軌跡可以發(fā)現(xiàn)，拍攝圖片按照設(shè)定好的運行軌跡飛行，從兩張圖像的航向偏角可知圖像走勢在既定航線上平移，將圖像放到同一坐標系中，以P作為參考，圖像P中心點向下平移了l的距離到了Q的位置，重疊區(qū)域如圖1所示的區(qū)域S：

圖1 重疊區(qū)域Fig.1 Overlapping area

至此重疊區(qū)域為P縮小寬度l的下半部分區(qū)域以及Q縮小寬度l的上半部分區(qū)域，重疊區(qū)域計算出來后，實驗就只需要在該區(qū)域里進行特征提取。

1.1.2 計算像素點經(jīng)緯度 每張圖片的圖像坐標與其對應的地面坐標的相對位置關(guān)系是不變的。已知每張圖片的尺寸，機載系統(tǒng)數(shù)據(jù)里包含攝影中心的坐標、攝像頭拍攝角度和拍攝高度，從而計算出圖像像素點經(jīng)緯度坐標。利用經(jīng)緯度數(shù)據(jù)找到特征點所在區(qū)域，使用KNN算法快速匹配，完成圖片的拼接。計算圖像各點到圖像中心的距離，公式如下：

其中H為圖像拍攝高度，θ為拍攝角度，A為拍攝照片實際長度，M為圖像像素長度，N為圖像像素寬度，k為長度與圖像像素的比例，以此計算出拍攝照片實際寬度，運用勾股定理，根據(jù)k計算出每個像素點到中心像素點的橫向距離x和豎向距離y。

保持緯度大小不變，兩條距離為1 m的經(jīng)線之間經(jīng)度的間隔為0.000 05°，同理，保持經(jīng)度大小不變，兩條距離為1.1 m的緯線之間緯度的間隔為0.000 05°，這樣我們能通過每個像素點到中心像素點的距離計算出每個像素點的經(jīng)緯度。

那么基于經(jīng)緯度數(shù)據(jù)改進的KNN算法主要過程為：計算兩張圖片重疊區(qū)域，在重疊區(qū)域進行特征配準，選取特征點a，利用其經(jīng)緯度數(shù)據(jù)找到待配準圖像中相同經(jīng)緯度數(shù)據(jù)的特征點b，因為計算出來的經(jīng)緯度數(shù)據(jù)存在誤差，所以需要利用算法對像素點鄰域內(nèi)的所有特征點進行匹配，找到特征點a在待配準圖像中特征點b鄰域內(nèi)的最近鄰點m和次近鄰點n，如果兩點距離dam和dan的比值小于閾值τ，那么a和m特征點匹配成功。因此根據(jù)該改進的算法，可以很快的將重疊區(qū)域內(nèi)的特征點匹配成功，極大地提高了效率。

1.2 圖像拼接

本文選取SIFT算法進行特征點粗提取，使用經(jīng)緯度數(shù)據(jù)加快KNN算法對特征點的粗匹配，通過歐式距離度量特征點是否匹配成功。再使用RANSAC算法監(jiān)測錯誤匹配點，該算法在最小二乘法的基礎(chǔ)上對一個樣本集合計算出能夠擬合樣本分布的模型，主要過程為隨機抽取匹配成功的特征點集合里n個匹配點對，計算出這n個點對的初始變換矩陣M，然后將M驗證集合里的其他點對，如果大部分匹配點對滿足該矩陣模型，那么該模型是正確的，然后將滿足該模型的點記為內(nèi)點，不滿足的記為外點。重復此操作就可以找到正確模型，篩選出最終準確的匹配點對。

由于每張圖像拍攝時受外部因素影響，導致拼接出來的圖片存在鬼影和縫隙，因此需要選取合適的融合算法進行拼接，以消除鬼影和拼接縫，最佳縫合線融合方法能使圖像達到無縫或者逼近無縫合成，使圖像合成的效果最佳。縫合線檢測的公式如下［13-15］：

其中，Ecolor(x,y)代表圖像重疊區(qū)域像素點的顏色強度差值，Egeometry(x,y)代表圖像重疊區(qū)域像素點的結(jié)構(gòu)差值。其中Egeometry(x,y)采用改進的梯度算子：

基于經(jīng)緯度的圖像拼接流程步驟如下：

步驟1：計算重疊區(qū)域，使用SIFT算法對該區(qū)域進行特征提??；

步驟2：計算像素點經(jīng)緯度數(shù)據(jù)，減小相鄰圖片特征點匹配區(qū)域，利用經(jīng)緯度數(shù)據(jù)加快KNN算法匹配時間，搜索出正確的匹配點對；

步驟3：使用RANSAC算法對匹配的特征點對進一步提純，篩選出錯誤匹配點，得到精匹配點；

步驟4：使用最佳縫合線算法對配準后的圖像進行融合，可以很好的消除圖像之間的拼接縫，拼接完成后的全景圖會顯得更加自然。

2 實驗與分析

選取某處松樹林的航拍圖像作為數(shù)據(jù)源，圖像由大疆無人機的拍攝所得，型號為DJIFC6310，測試平臺為CPU型號為AMD Ryzen 5＠3.40 GHz，內(nèi)存為16 GB，軟件開發(fā)環(huán)境為VS Code1.47+OpenCV3.4.2，圖片分辨率為4 864×3 648，航拍高度H為113 m左右。

2.1 航跡數(shù)據(jù)

無人機機載系統(tǒng)里包含了每張圖像相對應的Exif信息，比如拍攝時間，經(jīng)緯度信息和無人機飛行角度等多種信息，如表1所示。

2.2 特征配準對比實驗

為了驗證改進的KNN匹配算法效果，使用傳統(tǒng)SIFT算法與改進的SIFT提取算法和KNN匹配算法分別做實驗對照，本次實驗使用匹配準確率來評價算法是否適合無人機航拍圖像拼接，匹配準確率通常采用均方誤差（RMSE）來評價，公式如下：

表1 無人機POS信息Tab.1 UAV POSinformation

其中R代表均方誤差值，(xi,yi)為匹配圖像第i個匹配點的坐標，(x'i,y'i)為待匹配圖像對應匹配點的坐標，N表示正確匹配對的數(shù)量。當RMSE值越小，準確度越高，反之準確度越低。通過對無人機拍攝的10組航拍圖像進行實驗，分別記錄圖像特征點匹配的正確率。

如圖2匹配結(jié)果所示，傳統(tǒng)算法全圖提取的特征點很多，存在許多錯誤的匹配點，通過本文的改進算法對重疊區(qū)域進行特征配準實驗，特征點匹配對明顯變少，特征點分布基本集中在重疊區(qū)域里，匹配特征點大幅減少，這間接降低了誤匹配現(xiàn)象發(fā)生的概率。

圖3中實線代表SIFT算法RMSE值，虛線代表本文算法，可以對比看出，改進的算法配準精度比傳統(tǒng)算法高，結(jié)合圖3中的配準結(jié)果，本文改進算法配準精度得到了明顯提升，配準效率也提高了很多。

圖3 RMSE對比Fig.3 RMSE comparison

2.3 圖像融合實驗

為了進一步驗證改進后的算法相較于傳統(tǒng)SIFT算法在無人機林區(qū)航拍圖像拼接上的優(yōu)勢，本次實驗選取無人機飛行軌跡中的多幅圖像進行拼接實驗，實驗圖像如圖4所示，通過圖4的6張圖像進行地理坐標計算，通過飛行軌跡計算圖像間重疊區(qū)域，使用改進算法對重疊區(qū)域進行特征配準，再使用最佳縫合線算法對配準后的圖像進行融合，拼接結(jié)果如圖5所示。從圖5中可以看出：本文改進的配準算法結(jié)合最佳縫合線算法在很大程度上消除了圖像拼接誤差，融合效果好，沒有明顯的鬼影和拼接縫，進一步證明了本文算法的可行性。

圖4 實驗圖像Fig.4 Experimental images

圖5 圖像融合結(jié)果Fig.5 Image fusion result

3 結(jié) 論

松材線蟲病治理的關(guān)鍵在于病蟲的監(jiān)測，目前許多松林區(qū)依然依靠人工檢查的方式，效率不高，因此利用無人機技術(shù)以及圖像拼接技術(shù)已成為防治松材線蟲病的重要手段。針對航拍圖像易受旋轉(zhuǎn)、尺度變化的影響，本文使用傳統(tǒng)的SIFT算法提取特征點，結(jié)合無人機POS系統(tǒng)存儲的地理數(shù)據(jù)改進KNN算法，特征點匹配效率變高，然后利用RANSAC算法對特征匹配點進一步提純，實現(xiàn)了局部松樹林區(qū)域圖像拼接技術(shù)，更加方便了樹林管理員采集得了松材線蟲病的松樹數(shù)量和具體地理位置，能夠更加快速治理好這一傳染病。