基于紅黑樹數據結構的海岸線無人機正射影像拼接研究

范詩玥，張峰，盧文虎，王晶，王豐，劉慶群（國家海洋信息中心，天津　300171）

?

基于紅黑樹數據結構的海岸線無人機正射影像拼接研究

范詩玥，張峰，盧文虎，王晶，王豐，劉慶群
（國家海洋信息中心，天津300171）

摘要：隨著無人機技術的快速發展，以測量為目的的無人機攝影測量技術已廣泛應用到各行各業。相比于常用測量技術，無人機攝影測量技術需要處理抖動平臺下的序列攝影圖像，技術難度更大。利用紅黑樹數據結構實現無人機攝影圖像的大尺度特征點匹配連接，基于相機標定和捆綁調整兩個無人機攝影測量的關鍵技術環節，實現無人機海岸線遙感影像的快速拼接。

關鍵詞：無人機攝影測量；大視角圖像匹配；紅黑樹數據結構；影像正射拼接

經過近60年發展，攝影測量理論及技術已日趨成熟，并廣泛應用于城市建模、國家三四等水準測量等行業（王之卓等，1979；李德仁等，1992；Edward et al，2001；張劍清等，2003）。攝影測量主要是把專業測量相機安裝在穩定有人機平臺上，在飛行前進行嚴格航跡規劃及精確地控制相機曝光間隔，利用高質量飛行影像解算相機外方位元素和地面三維點，并在此基礎上通過密集匹配、鑲嵌線提取等操作實現DEM（數字高程模型）、DSM（數字表面模型）及DLG（數字線化模型）等數字化產品生產。然而，這種常規攝影測量技術并不適用于所有場景，比如地震災區、偏遠海岸線等人無法到達的復雜、敏感環境。隨著飛控、導航等技術發展，無人機技術近十年得到飛速發展（唐強等，2004；聶博文等，2007），民用無人機技術現已應用到地質勘查、遙感等領域（孫杰等，2003；李宗南等，2014）。由于無人機載荷有限以及無人機飛行失敗風險性系數偏大，搭載在無人機平臺上的相機較有人機在飛行中易受到風、氣流影響，所拍攝相片在尺度、亮度、角度上存在較大變化，故給無人機影像特征提取匹配增加難度。以上這些因素都將嚴重影響到測量定位及數字化產品的精度。

具有空間信息的拼接技術已廣泛應用于航天、航空及無人機領域，具有代表性的工作如下。為解決衛星拼接像元失配的問題，常琳等（2014）提出了一種實現TDI CCD相機像元快速拼接配準的匹配算法。張過等（2012）以基于多CCD影像重成像算法作為內視場拼接的技術手段，實現航空飛機雷達地形測繪DEM的影像拼接。劉春等（2012）以稀少控制信息的無人機影像嚴格拼接為目的，引入光束法自由網平差技術實現無人機影像拼接。

無人機影像特征提取匹配和同名點轉點算法是實現遙感影像拼接的基礎，在國內外有大量研究人員進行相關研究，基本思路大致相同，即直接通過中間影像上的特征點坐標進行直接比較和串點（Barazzetti，2010）。此類方法在處理小分辨率影像時，效率可以接受，但是對于大尺度無人機遙感影像時，候選特征點過多造成了效率極其低下。所以，本文利用紅黑樹數據結構實現無人機攝影圖像的大尺度特征點匹配連接，同時根據無人機相機標定和捆綁調整等關鍵技術環節，將無人機攝影技術應用到海岸線數字化生產中，制作正射拼接影像產品。

1　無人機相機標定

1.1畸變糾正幾何模型

理想透視模型的物理原型為針孔成像模型，物和像會滿足直線投影關系。但是無人機相機并不像常規航測用途的專業相機，相機光學系統存在加工和裝配的誤差，像點和對應地面點不滿足嚴格的共線條件，因此在相機圖像平面上實際所成的像與理想成像之間存在畸變，相機成像理想點和實際點存在差異。利用圖像來進行測量，從而反算出相機的內外參數及其三維點坐標時，第一步應是相機標定，去除相機的畸變因素。

相機幾何畸變包括徑向畸變和切向畸變（張劍清等，2003），相比于切向畸變，徑向畸變更大。像點（xr和yr）兩個方向的徑向畸變糾正模型和可以用下面的公式標定。

其中，k1、k2....為徑向畸變系數，通常情況下，二階模型可以滿足實際的精度，所以本文選用二階模型來刻畫徑向畸變函數，即公式（2）。

切向畸變糾正模型可以用公式（3）表示。

其中，p1、p2為切向畸變系數，實際使用中，刪除高階項o［（xryr）4］。

綜合上述徑向畸變模型（公式（2））和切向畸變模型（公式（3）），得到最后完整的相機畸變幾何糾正模型，如公式（4）。

其中像點（ui和vi）是經過畸變幾何糾正的坐標，從而消除了儀器制造工藝誤差帶來的非共線的實驗條件。

1.2相機標定方法

本文利用像點作為真值，優化徑向畸變參數（k1k2）和切向畸變參數（p1p2）。假設從圖像上提取出一系列特征點（ui和vi），將上面4個參數當作待求參數，利用最小二乘非線性迭代優化中求出準確的值。非線性優化中，需要對上面4個參數分別求導，導數如公式（5）和（6）。

公式（5）和公式（6）組成偏導數矩陣，如：

給定畸變參數初值后和已知偏導數矩陣J，可以通過公式（8）計算得到畸變參數改正值。

其中，e為像點改正數。

當標定得到準確的徑向和切向畸變參數后，通過公式（4）可以將原始無人機圖像糾正為無畸變的無人機圖像。

實際實現過程中，首先需要從圖像中獲取穩定高精度匹配特征點，這些特征點將作為優化問題的觀測真值。然后根據公式（7）計算優化問題的一階導數，通過公式（8）進行多次迭代。每次迭代優化后的變量增值將加入到初值中，作為下一次迭代初值，直至問題收斂。當問題收斂后，從變量中提取出相機畸變參數。

2　無人機大視角圖像特征提取匹配

2.1立體像對同名點提取匹配

特征點提取在航空測量中至關重要，只有匹配后的同名點才能唯一確定三維點坐標，才能用于相機定姿和定位。本小節主要介紹如何從立體像對中獲取高精度匹配的同名點。由于無人機拍攝的隨意性，即兩兩圖像間在尺度、亮度、幾何變換中存在很大差異，故需要研制一種對尺度、亮度、旋轉不變的特征點提取匹配算法。尺度不變特征提取算法（SIFT）是Lowe（1999）在1999年發表、2004年完善總結的一種計算機視覺算法，用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉不變量。如圖1所示，分別對左、右影像進行SIFT特征提取，最后利用尺度不變特征變換算法進行匹配。

圖1　SIFT算法框架圖

不同于其他特征點提取匹配算法，SIFT算法因考慮到高斯尺度空間和高斯差分尺度空間，對尺度和噪聲有很強抗敏感性。高斯尺度空間是將原始無人機圖像通過不同高斯卷積核產生一階圖像，選取一階圖像中某一張進行圖像降采樣得到第二階圖像的第一張，然后利用高斯卷積核對此圖像進行卷積運算得到二階圖像，以此得到連續的尺度空間。高斯差分金字塔通過高斯金字塔中相鄰尺度空間函數相減即可，它最大的優點是計算簡單，主要作用是減少噪聲干擾。

SIFT算法流程分三大步：第一步是SIFT特征點的檢測；第二步是SIFT特征描述符的生成；第三步是SIFT特征向量的匹配。其中第一步最為關鍵，其原理為尋找尺度空間極值點，每一個采樣點都要和它同尺度的8個相鄰點和上下相鄰尺度對應的18個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點，得到某個尺度上的極值并保存它的尺度和位置信息。得到區域極值后，還需進一步精確定位特征點。首先可以根據具體情況將閾值設定為一個數值，尺度空間中灰度值若小于該值則拋棄。再通過擬和三維二次函數以精確確定關鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關鍵點和不穩定的邊緣響應點（因為高斯差分算子會產生較強的邊緣響應），以增強匹配穩定性、提高抗噪聲能力。故SIFT提取特征點并不是幾何特性的極值點，而是灰度空間的極值。

SIFT特征提取算法可以提供含有方向和梯度的128維描述符信息，所以實現兩張影像特征點匹配可以根據128維描述符在空間中的最短歐式距離來判斷。為了避免噪聲的干擾，對于一張影像中待匹配的興趣點，假如在另一張影像中的所有像點中，歐式距離的最短距離和次短距離小于給定的閾值，就認為這對特征點匹配。

2.2紅黑樹多圖像連接點生成

在攝影測量航線規劃中，對航向和旁向攝影重疊度均有嚴格要求，所以一個地面點會在多張影像上成像，所有這些像點組成的集合被定為連接點。相比于只有兩次觀測的立體像對同名點，三次及更多的連接點可以為捆綁調整優化特征點提供更豐富的多余信息，從而提高定位定向的精度。另外，連接點還可以實現兩兩像對的連接，實現整體模型的尺度歸一化。因此，連接點生成在攝影測量中非常重要，為捆綁調整提供必要的輸入信息量。

圖2　連接點示例圖

如圖2所示，總共拍攝了5張序列影像，圖像的編號分別為1、2、3、4、5。有兩組連接點，分別為A（被第1、2、3張影像觀測到，總觀測次數為3）和B（被第2、3、4、5張影像觀測，總觀測次數為4）。由于使用特征點提取匹配只能得到兩張影像的同名像點對，無法直接轉點。例如使用特征提取匹配算法SIFT分別匹配第一、二張影像得到，第二、三張影像得到，然后需要判斷，是否為同名像點。假如這兩對特征點指示相同的地面點，需要將其合并得到A。將所有特征提取匹配算法得到的單對同名像點連接得到連接點轉點。由于沒有任何信息，實現和連接只能通過兩對公有的圖像信息，即第二張影像的圖像坐標是否相同；倘若相同，認為其為相同的同名像點，從而實現轉點。但使用SIFT算法可以從一對相鄰圖像對中得到上千甚至上萬個同名像點對，因此在海量數據點對中去直接比較圖像坐標來實現轉點的效率將極為低下。紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。本文利用紅黑樹數據結構，設計了一種適用于建立特征點空間關系的數據結構，大大提高了連接點轉點的效率。

對于特征點數據，可以利用紅黑樹數據結構加速連接點轉點過程。相比于其它二叉樹，除了擁有鍵值和鍵值對應數據外，還包含顏色屬性。圖3為一棵包含6個節點的紅黑樹，每個節點左邊表示鍵值，右邊表示鍵值對應的內容（i表示第i個連接點），鍵值顏色為紅色或者黑色。每個連接點的鍵值索引可以設為如下數據結構形式：

struct RB_Key

｛

int imgNo；

float u；

float v；

｝；

其中，imgNo為圖像序號，u、v為圖像坐標。在進行連接點轉點的過程中，只需要比較鍵值就可以快速進行特征點轉點。

為了更清晰了解整個搜索過程，下面通過圖2中的第一個特征點A來說明。A特征點被3張影像共同觀測到，分別為圖像1、2和3。利用2.1節提出的方法分別進行兩次提取和匹配，得到兩個特征點分別為和（每個括號表示一個像點，每像點包括圖像序號和圖像坐標）。在判斷是否與屬于同一個特征點時，將第二個像點作為鍵值，將第一個像點作為鍵值，只需要在圖3中搜索鍵值。當找到相同鍵值時，連接兩個像點，得到3次觀測的特征連接點，

即

圖3　紅黑樹數據結構示例圖

3　捆綁調整

捆綁調整主要作用是利用第2節提供的匹配特征點作為觀測，并利用像點和三維點的相機成像模型估計出拍攝狀態下的相機位姿和三維點。首先介紹應用到捆綁調整模型的相機成像坐標系統轉換關系，最后介紹捆綁調整的數學原理。

3.1坐標系變換關系

相片坐標系、像平面坐標系、攝影坐標系、大地坐標系是攝影測量最重要坐標系，四者間的相互轉換關系如下。

（1）像平面坐標（x，y）與相片坐標（像素坐標）（u，v）

其中，（u0，v0）為相片內方位元素，r′為傾斜因子，dx和dy為CCD每個象元的實際尺度。

（2）攝影坐標（Xc，Yc，Zc）與像平面坐標（x，y）

（3）攝影坐標（Xc，Yc，Zc）與大地坐標（XW，YW，ZW）

其中，R為旋轉量，t為平移量。

（4）合并得到相片坐標（u，v）與大地坐標（XW，YW，ZW）

其中，fu=，fv=，r = r′f。K為相機內參數矩陣，P= K［ R t］相機投影矩陣，M為大地坐標。

最后得到圖像坐標（u，v，1）和大地坐標（XW，YW，ZW）相互關系。圖像坐標和三維大地坐標組成的小孔成像模型將作為捆綁調整的平差基本單元。

3.2捆綁調整的非線性優化

捆綁調整的數學本質為非線性最小二乘優化問題，即給定觀測值來估計最優的優化參數。如式（12）中，觀測值Z為第2節提取匹配到的連接點，優化參數X包括相機的外方位元素和連接點的三維坐標。攝影測量中，每個相機的外方位元素包括6個變量，分別為3個線元素和3個角元素；每個特征點包括3個變量。假設n張圖像，觀測到m個地面點，同時投影到所有圖像形成k個投影點。此時，觀測量Z個數為k×2 j，優化參數個數為n×6 + m×3。則捆綁調整算法的非線性最小二乘問題，就是要找到一個狀態向量X，使得最小化。

其中，假設所有特征點所對應的投影像點坐標的不確定度是相同的，并且是互相獨立的。因此在光束法平差算法中，將用Σ-1Z= I作為權重。

4　海岸線正射影像拼接

4.1整體實驗方案設計

整體實驗方案包括相機畸變校正、紅黑樹特征匹配、相機初始化、捆綁調整和正射拼接5個主要步驟（圖4），詳細過程如下：

圖4　無人機測量實驗方案設計

（1）相機畸變校正：由于無人機海岸線測量使用的是普通相機，鏡頭存在徑向畸變和切向畸變，直接使用原始圖像的信息，無法準確描述像點與其對應地面點的線性關系，因此需要利用徑向畸變參數和切向畸變參數糾正所有拍攝的圖像。

（2）紅黑樹特征匹配：原始圖像信息無法直接應用于后續的信息處理，需要利用尺度不變特征變換算法得到大量高精度的穩定的特征點，然后利用RANSAC算法（Fischler et al，1981）去除用SIFT算法所得特征點中的錯點；對連續多對圖像兩兩進行特征提取，然后利用紅黑樹結構，快速對多張具有重疊圖像的特征點進行連接，生成具有豐富信息的連接點信息。

（3）相機初始化。下一步的捆綁調整計算屬于非線性問題中的最小二乘問題，需要為非線性優化問題提供較準確的初始值。

（4）捆綁調整。整合標定后的相機內參數、連接點數據和相機初始值，利用Levenberg-Marquardt算法（伏燕軍等，2007）實現捆綁調整。捆綁調整可以得到兩類優化數據結構，其一是參與優化的連接點對應的三維特征點的空間坐標，其二是安裝在無人機上的相機6個位置姿態信息。

（5）正射拼接：利用捆綁調整后得到的三維特征點空間坐標和相機6個姿態參數進行拼接，得到正射拼接影像。正射拼接的目的是實現相機從透視成像向平行方式成像。根據捆綁調整得到的稀疏三維點，通過擬合加密得到地形場景。然后，實現每個點在相片上的單張微分糾正。糾正后的影像將帶有具體的地理坐標信息，根據坐標的統一性，可直接實現影像拼接。

4.2海岸線無人機影像正射拼接

海岸線數字化產品中，正射拼接影像有著重要的作用與意義。本小節將4.1方案得到的相機外方位元素和三維點，利用間接法實現單張相片微分糾正。微分糾正后的每張相片都歸一化到大地坐標系統，因此，直接通過坐標平移就可以實現整個海岸線測區的單張糾正后影像的拼接，最后得到一張完整覆蓋該測區的正射拼接影像。

實驗中利用無人機拍攝的6張海岸線影像（圖5）進行基于紅黑樹數據結構特征匹配，匹配結果如圖6和圖7所示。圖6是利用前兩張圖像提取得到10 342個匹配特征點（紅色點表示），其中兩張圖像同名像點用綠色直線連接（圖7）。最后，根據各影像匹配生成的同名像點及計算得到的相機參數進行反算，拼接成正射影像結果如圖8所示。

圖5　原始影像

圖6　同名點匹配結果

圖7　同名點連接結果

倘若需要對拼接結果進行定量分析，需要通過大量控制點作為檢查點進行衡量。因為本文數據缺乏控制點，所以只能通過目視方式進行定性分析。實驗表明，不同影像邊緣上的道路線拼接后無縫隙，無明顯像素偏移，證明了該方法的可行性。

圖8　無人機海岸線影像拼接結果

5　總結

利用紅黑樹數據結構優化了無人機影像大視角的特征點匹配，實現了快速、精確的同名像點提取，通過捆綁調整得到的三維地形及相機優化參數反算，完成正射影像拼接生產，實驗結果顯示，該拼接方法對拼接后影像中海岸線的連續性無任何影響，效果良好。本方法為海岸線數字化及海岸線變遷分析工作提供了一種技術支撐手段。

參考文獻

Barazzetti L，Remondino F，Scaioni M，2010. Extraction of accurate tie points for automated pose estimation of close-range blocks. In：ISPRS Technical Commission III Symposium on Photogrammetric Computer Vision and Image Analysis.

Edward M M，James S B，Chris J M，2001. Introduction to modern photogrammetry. Wiley press.

Fischler M，Bolles R，1981. Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM，24（6）: 381-39.

Lowe D G，1999. Object recognition from local scale-invariant features. In：IEEE international conference on computer vision（ICCV），2: 1150-1157.

常琳，金光，楊秀彬，2014.航天TDI CCD相機成像拼接快速配準算法設計與分析.光學學報，34（5）：48-56.

伏燕軍，楊坤濤，鄒文棟，等，2007.基于Levenberg-Marquardt算法的圖像拼接.激光雜志，28（5）：46-48.

李德仁，鄭肇葆，1992.攝影測量學.北京：測繪出版社.

李宗南，陳仲新，王利民，等，2014.基于小型無人機遙感的玉米倒伏面積提取.農業工程學報，30（19）：207-213.

劉春，李巍岳，雷偉剛，等，2012.基于光束法自由網平差的無人機影像嚴格拼接.同濟大學學報：自然科學版，40（5）：757-762.

聶博文，馬宏緒，王劍，等，2007.微小型四旋翼飛行器的研究現狀與關鍵技術.電光與控制，14（6）：113-117.

孫杰，林宗堅，2003.無人機低空遙感監測系統.遙感信息（1）：49-50.

唐強，朱志強，王建元，2004.國外無人機自主飛行控制研究.系統工程與電子技術，26（3）：418-422.

王之卓，1979.攝影測量原理.測繪通報，4：016.

張過，劉斌，江萬壽，2012.虛擬CCD線陣星載光學傳感器內視場拼接.中國圖象圖形學報，2012，17（6）.

張劍清，潘勵，王樹根，2003.攝影測量學.武漢：武漢大學出版社.

（本文編輯：袁澤軼）

Study on the coastline orthophoto mosaic using UAV images based on red-black data structure

FAN Shi-yue，ZHANG Feng，LU Wen-hu，WANG Jing，WANG Feng，LIU Qing-qun
（National Marine Data and Information Service，Tianjin 300171，China）

Abstract：With the rapid development of UAV technology，photogrammetric technology involving high resolution camera is widespreadly applied to lots of fields. Compared with traditional survey methods，it is more difficult to handle with aerial images，captured by cameras on unstable aerial platform. In this paper，red-black data structure is used in large scale tie point matching and connecting. Meanwhile the camera calibration and bundle adjustment technologies are used to generate coastline mosaic using UVA images.

Keywords：UAV photogrammetry；image matching for large viewport；red-black data structure；image mosaic

中圖分類號：P231.5

文獻標識碼：A

文章編號：1001-6932（2016）02-0132-08

Doi：10.11840/j.issn.1001-6392.2016.02.002

收稿日期：2015-06-25；

修訂日期：2015-08-12

作者簡介：范詩玥（1989-），女，碩士，研究實習員，主要從事海島遙感影像處理及管理研究，電子郵箱：julia317fan@126.com。

通訊作者：張峰（1978-），男，博士，副研究員，電子郵箱：olileo@163.com。