王競雪：顧及拓撲關係的立體影像直線特徵可靠匹配演算法
《測繪學報》
構建與學術的橋樑 拉近與權威的距離
顧及拓撲關係的立體影像直線特徵可靠匹配演算法
王競雪1,2, 朱慶1, 王偉璽3
1. 西南交通大學地球科學與環境工程學院, 四川 成都 611756;
2. 遼寧工程技術大學測繪與地理科學學院, 遼寧 阜新 123000;
3. 深圳大學智慧城市研究院, 廣東 深圳 518060
收稿日期：2017-04-06；修回日期：2017-09-19
摘要：針對單直線匹配過程中缺乏考慮鄰近直線特徵之間關係，紋理斷裂處單一直線描述符的弱可靠性，提出了一種顧及拓撲關係的立體影像直線特徵可靠匹配演算法。該演算法首先根據直線間距離、角度等基本拓撲關係對參考影像、搜索影像上提取的直線進行編組；然後將編組得到的直線組作為匹配基元，充分利用直線特徵組內的拓撲關係，依次採用核線約束、單應矩陣約束、象限約束、不規則三角形區域灰度相關約束對其進行匹配；最後將同名直線組分裂為兩對同名單直線、並對分裂後的結果進行整合、擬合、檢核等後處理，得到「一對一」的同名直線。選取典型紋理特徵的航空影像和近景影像進行參數分析及直線匹配試驗，結果表明，本文演算法能獲取可靠的直線匹配結果。
關鍵詞：直線匹配直線組匹配拓撲關係核線約束單應矩陣
Reliable Line Matching Algorithm for Stereo Images with Topological Relationship
WANG Jingxue1,2, ZHU Qing1, WANG Weixi3
Abstract: Because of the lack of relationships between matching line and adjacent lines in the process of individual line matching, and the weak reliability of the individual line descriptor facing on discontinue texture, this paper presents a reliable line matching algorithm for stereo images with topological relationship. The algorithm firstly generates grouped line pairs from lines extracted from the reference image and searching image according to the basic topological relationships such as distance and angle between the lines. Then it takes the grouped line pairs as matching primitives, and matches these grouped line pairs by using epipolar constraint, homography constraint, quadrant constraint and gray correlation constraint of irregular triangle in order. And finally, it resolves the corresponding line pairs into two pairs of corresponding individual lines, and obtains one to one matching results after the post-processing of integrating, fitting, and checking. This paper adopts digital aerial images and close-range images with typical texture features to deal with the parameter analysis and line matching, and the experiment results demonstrate that the proposed algorithm in this paper can obtain reliable line matching results.
Key words:line matchingpair-wise line matchingtopological relationsepipolar constrainthomography
直線特徵是人類視覺信息中最顯著、最直觀、最具有代表性的特徵。城區建築物輪廓邊緣、屋頂和立面都蘊含著大量的直線特徵，包含豐富的語言信息和幾何意義，能夠較好地表達建築物結構特徵，因此，將直線特徵作為匹配基元並實現其可靠匹配是基於影像精細三維建模的基礎[1-4]。目前，攝影測量和計算機視覺領域對直線匹配進行了大量的卓有成效的研究。現有的直線匹配方法可以分為單直線匹配和組直線匹配兩類。
單直線匹配方法主要利用單一直線的幾何屬性信息(如斜率、長度、位置、重疊度、距離等)或鄰域灰度信息的特徵相似性，結合一定的幾何約束對直線逐一進行匹配。文獻[5]採用分層次直線符號法，利用直線段的長度、方向、位置和強度、對比度等特徵進行直線的相似性匹配；結合核線約束，文獻[6]利用直線鄰域灰度相關實現直線匹配；結合同名三角網約束，文獻[7-8]提出移動窗口的自適應直線相關方法，有效解決位於紋理斷裂處的直線匹配問題；結合同名點約束，文獻[9]通過窗口行向量平均化計算相似性；文獻[10]利用物方平面約束，通過計算參考直線和候選直線間重疊距離和垂直距離，確定同名直線；文獻[11]將待匹配線及與其共面的同名點作為整體進行描述及匹配；在無任何約束條件下，文獻[12-13]提出了MSLD均值-標準差直線描述子(mean-standard deviation line descriptor, MSLD)，該描述子通過統計像素支撐域內每個子區域4個方向的梯度向量構建描述子矩陣，提高描述子的可區分性及穩健性。目前單直線匹配研究取得了一定的進展[14-18]，但受限於單一直線描述符，匹配過程中沒有考慮鄰近直線特徵之間關係，匹配結果模糊性一直存在。
組直線匹配多利用滿足一定條件的直線組作為匹配基元進行匹配。文獻[19]將定義的幹線對作為匹配基元，採用全局最優化思想完成異源圖像的匹配及配准；文獻[20]根據幾何特性、灰度特性為直線分配可信度，以組直線為匹配單元，利用馬氏距離計算組直線之間的特徵相似性進行匹配；文獻[21-23]提出了一種組直線匹配方法，首先參考影像上的直線組需滿足距離、角度、半鄰域灰度相似性3個條件，綜合利用核線約束、幾何屬性約束、空間直方圖、灰度相關等約束條件確定搜索影像上的同名直線組。研究結合Daisy描述符、匹配結果冗餘及成對質量檢核3個方面對匹配結果進行後處理，減少匹配結果不確定性；文獻[24]將三維空間共面的直線組作為匹配基元，根據拓撲關係確定直線組，對直線組交點構建描述符，根據標準互相關函數確定同名直線組，該方法對紋理匱乏區域均能取得較好的匹配結果，但對於拍攝傾角變化較大的立體影像還需進一步完善。在現有組直線匹配方法的基礎上，本文提出一種顧及拓撲關係的立體影像直線特徵可靠匹配演算法。該演算法將滿足一定拓撲關係的直線組作為匹配基元，充分利用直線組間幾何信息、拓撲關係等多重約束對直線組進行匹配，並通過對同名直線組分裂、匹配結果後處理獲取可靠的直線匹配結果。
1 原理
在已有LSD直線提取結果和漸進三角網約束點密集匹配結果的基礎上，本文提出的顧及拓撲關係的立體影像直線特徵可靠匹配演算法分為特徵直線組提取、直線組匹配和匹配結果後處理3個階段。第1階段，根據直線間距離、角度等拓撲關係對參考影像、搜索影像提取的直線分別進行特徵編組，提取滿足預設條件的特徵直線組；第2階段，充分利用直線組間拓撲關係，依次採用核線約束、單應矩陣約束、象限約束和三角形區域灰度相關約束對參考影像、搜索影像上提取的直線組進行匹配，得到兩張影像上的同名直線組；第3階段，將匹配得到的同名直線組分解為同名單直線，並對結果進行後處理，主要包括對結果中「一對多」「多對一」「多對多」匹配結果進行整合，剔除錯誤的「多」直線匹配結果，並對正確的「多」直線進行擬合，最終得到「一對一」的同名單直線。
1.1 拓撲關係約束的直線編組
採用LSD演算法[25]對參考影像、搜索影像分別進行直線提取，結果表示為L={l1,l2, …,lI}，R={r1,r2, …,rJ}，I、J分別為參考影像、搜索影像上提取直線的數目。對參考影像、搜索影像提取的直線分別進行編組，得到特徵直線組。對影像上任一直線段li，兩端點分別為a和b，長度為len，將其作為目標直線，直線{li+1,li+2, …,lI}為待編組的直線，具體編組過程如下：
(1) 以目標直線li為中心建立矩形窗口作為目標直線鄰域窗口。如圖 1所示，沿目標直線兩端及垂直直線方向的兩側，分別擴展d個像素長度，得到大小為(2d+1)×(len+2d)的矩形窗口為目標直線的鄰域窗口。
(2) 依次判斷待編組的直線與目標直線鄰域窗口關係，如某一待編組直線li′在目標直線鄰域窗口內或與鄰域窗口相交，且與目標直線li的夾角θ在一定的角度範圍內，則該直線li′與目標直線li構成一特徵直線組，記為PL(li,li′,CL)，CL為特徵直線組的交點坐標。
(3) 分別選擇li和li′端點中與交點CL距離較近的點作為li和li′的起點，與點CL距離較遠的點作為直線li和li′的終點。如圖 1所示，b、e分別為兩直線的起點，a、c分別為兩直線的終點。
對每張影像上提取的直線依次進行編組，分別得到參考影像和搜索影像上的特徵直線組集合，記為PL={P1L(li1,li′1,C1L),P2L(li2,li′2,C2L), …,PML(liM,li′M,CML)}，PR={P1R(rj1,rj′1,C1R),P2R(rj2,rj′2,C2R), …,PNR(rjN,rj′N,CNR)}，其中，M和N分別為參考影像和搜索影像上直線組的數目。圖 2為參考影像、搜索影像上編組得到的直線組，其中圓點為直線組中兩條直線的交點。
1.2 顧及拓撲關係的直線組匹配
以參考參考、搜索影像上編組得到的直線組作為匹配基元進行匹配，匹配過程中依次採用核線約束、單應矩陣約束、象限約束、不規則三角形區域灰度相關約束。對參考影像上任一直線組，確定搜索影像上滿足上述四種約束條件的特徵直線組為其同名直線組。
1.2.1 核線約束
如圖 3(a)所示，參考影像上任一特徵直線組PmL(lim,li′m,CmL)，計算其交點CmL在搜索影像上的核線。計算搜索影像上各特徵直線組交點{C1R,C2R, …,CNR}到核線的距離，距離小於一定閾值Td的特徵直線組為候選直線組。如圖 3(b)所示，其中交點C1R、C2R、CnR對應的直線組為候選直線組。
1.2.2 單應矩陣約束
單應矩陣表示兩個平面之間的可逆齊次變換，同一平面上的點，在兩張影像上成像的同名點坐標記為u=[xL,yL]T，v=[xR,yR]T，則u點可通過式(1)變換到v點
(1)
式中，H為單應矩陣，通過兩張影像上至少4對同名點進行求解。對於實際影像而言，一般都存在地形起伏或者景深變換，因此全局單應矩陣不適用於整張影像。本文對任一待匹配直線組分別選取其鄰域範圍內同名點計算局部單應矩陣，用於近似表示該直線組所在局部影像區域之間的對應關係，用於限定核線上的搜索範圍。如圖 3(a)所示，以參考直線組交點CmL為中心，以兩直線lim和li′m終點方向所構成扇形區域內包含的同名點計算局部單應矩陣H，圖 3中實心三角點為用於計算局部單應矩陣的同名點。為了確保用於單應矩陣計算所需同名點的數目，迭代擴大扇形半徑直到同名點數目滿足為止。
根據局部單應矩陣H和式(1)，將參考影像上參考直線組交點CmL映射到搜索影像上，得到點，如圖 3(b)所示；計算搜索影像上各候選直線組交點到點的距離，剔除距離大於閾值Th的候選直線組。
1.2.3 象限約束
根據局部單應矩陣H，將參考影像上參考直線組PmL(lim,li′m,CmL)映射到搜索影像上，得到；如圖 3(b)所示，在搜索影像上，對建立以為原點的局部坐標系，x軸和y軸分別與像素坐標系的x軸和y軸平行，記錄中直線和直線終點所在象限分別為Q1和Q2；對搜索影像上各候選直線組分別以其交點為原點建立局部坐標系，判斷每個候選直線組中兩直線終點所在象限是否為Q1和Q2，是，保留該候選直線組，否則，捨棄該候選直線組。
1.2.4 不規則三角形區域灰度相關約束
對滿上述3個約束的候選直線組，採用不規則三角形區域灰度相關約束確定最終同名直線組。
1.2.4.1 建立單直線對應關係
首先根據直線組中兩直線所在象限建立參考直線組和候選直線組中單直線對應關係。固定參考影像上參考直線組PmL(lim,li′m,CmL)中lim為起始邊，li′m為終止邊。根據直線和直線所在象限Q1和Q2確定候選直線組中與其對應的起始邊和終止邊，這裡分兩種情況：
當Q1≠Q2時，即參考直線組中兩條直線在兩個不同的象限，候選直線組PnR(rin,ri′n,CnR)中，如果rin終點所在象限為Q1，則rin為起始邊，ri′n為終止邊，反之，如果ri′n終點所在象限為Q1，則ri′n為起始邊，rin為終止邊，更新候選直線組為PnR(ri′n,rin,CnR)。
當Q1=Q2時，即參考直線組PmL(lim,li′m,CmL)中兩條直線在同一象限，根據向量叉積判斷從lim到li′m是順時針還是逆時方向旋轉，對應的，判斷候選直線組PnR(rin,ri′n,CnR)中從rin到ri′n是否與從lim到li′m的旋轉方向一致，如果不一致，更新候選直線組為PnR(ri′n,rin,CnR)，否則，候選直線組不變。
1.2.4.2 對應三角形區域提取
如圖 3(a)所示，以參考直線組交點CmL、起始邊終點a、終止邊終點c構成三角形ΔaCmLc所包含的區域作為灰度相關區域，並採用掃描線演算法確定三角形區域內所包含的像素點坐標及其灰度值，灰度值記為G={g1, …,gi, …,gNg}，Ng為區域內包含的像素點數目。
如圖 3(b)所示，分別計算參考直線組起始邊終點a、終止邊終點c在搜索影像上的核線Ha、Hc，分別計算Ha、Hc與候選直線組中起始邊和終止邊的交點，記為a′和c′。搜索影像上以候選直線組交點、a′點和c′點構成三角形所包含的區域作為灰度相關區域。
利用參考影像、搜索影像灰度相關區域的3個頂點坐標，根據式(2)計算兩灰度相關區域仿射變換參數
(2)
式中，a、a1、a2、b、b1、b2表示仿射變換的6參數；x和y表示參考影像上灰度相關區域頂點坐標，x′和y′表示搜索影像上對應的灰度相關區域對應頂點坐標。
根據仿射變換參數和參考影像上灰度相關區域ΔaCkLc內包含的像素點坐標計算搜索影像上灰度相關區域內對應像素點的坐標，並根據雙線性插值方法計算得到對應像素點的灰度值，記為F={f1, …,fi, …,fNg}。
1.2.4.3 灰度相關計算
根據相關係數式(3)計算參考影像、搜索影像灰度相關區域的灰度相關係數ρ
(3)
式中，gi和fi分別為參考影像、搜索影像灰度相關區域內對應像素的灰度值；g和f分別為對應的灰度相關區域內所有像素灰度值的平均值。選取相關係數最大且大於一定閾值Tρ的灰度相關區域對應的候選直線組為PmL(lim,li′m,CmL)的同名特徵直線組。
1.3 匹配結果後處理
根據直線組中單直線應關係將匹配得到的每對同名直線組分裂為兩對同名單直線，由於直線編組過程中同一直線可能出現在多個直線組中，參與多次匹配，會得到多次匹配結果。同時由於直線提取結果斷裂和錯誤匹配，匹配結果中存在「一對多」「多對一」「多對多」匹配情況，因此需要對匹配結果進行後處理。在確保匹配結果中對應關係唯一性的基礎上，對結果中非「一對一」的「多」直線進行檢核，剔除錯誤的「多」直線匹配結果，並對正確的「多」直線進行擬合，最終得到「一對一」的同名單直線。
首先，根據文獻[10]中匹配結果整合演算法對分裂得到的同名單直線依次實現從左到右，再從右到左的「一對多」匹配結果整合。然後，對整合後同名直線對應關係中「一對多」「多對一」「多對多」結果中的「多」直線進行擬合，如果擬合直線斜率與原有的多條直線斜率均一致且「多」直線間重疊度為0，則用擬合直線代替原有的「多」直線，否則將該組匹配結果刪除。最終得到參考影像上與搜索影像上「一對一」的同名直線。
2 試驗與分析
為了驗證本文演算法的有效性，共採用一組航空影像、兩組近景影像用於直線匹配試驗。第1組為圖 4(a)所示的DMC數字航空影像的子影像對，影像集中在人工建築物密集區域，提取的直線特徵多為建築物邊緣，影像大小分別為499× 463像素、487×450像素；第2組為圖 4(b)所示存在尺度變化的近景影像對，兩張影像之間尺度比約為1:1.5，影像大小均為600×800像素；第3組為圖 4(c)所示存在旋轉的近景影像對，兩張影像旋轉角度約為40°，影像上地物細節信息較為豐富。試驗過程中，首先對圖 4所示3組影像實現漸進三角網約束點密集匹配及LSD直線提取，然後在此基礎上進行直線匹配。匹配過程中參數閾值設置如下：Td=5，Th=20，Tρ=0.7。
2.1 直線編組參數選取
本文採用直線組作為匹配基元進行直線匹配，而直線編組結果對直線匹配結果產生直接的影響。本文編組過程中共包含直線鄰域擴展長度d和直線夾角θ角度範圍兩個參數，因此本文採用第1組航空影像數據，在d和θ取不同值的情況下進行直線編組及匹配試驗，分析編組過程中不同參數值對編組的影響，進而研究其對匹配結果的影響，通過對比分析確定編組參數用於後續匹配。
在匹配參數一致的條件下，本文對θ∈[45°, 135°]、θ∈[30°, 150°]、θ∈[15°, 165°]3個取值範圍及d分別取5、10、15、20、25值的情況下進行匹配試驗，結果分別如表 1、表 2、表 3所示。其中，第1列為d的取值；第2、3列為參考影像、搜索影像上編組得到的直線組的數目；第4列為匹配得到的同名直線組的數目；第5列為同名直線組分裂後得到同名直線的數目。但是由於匹配結果中存在「一對多」「多對一」「多對多」對應關係，因此結果中包含參考影像、搜索影像上直線數目不相同，第6、7列為匹配結果中分別包含的參考影像、搜索影像上提取直線的數目；第8列為經過對「一對多」「多對一」「多對多」結果整合、擬合、檢核後得到的最終的同名直線數；第9列為正確匹配的數目，第10列為匹配的正確率。
表 1θ∈[45°, 135°]的直線匹配結果Tab. 1Line matching results by different parameterdandθ∈[45°, 135°]
表選項
表 2θ∈[30°, 150°]的直線匹配結Tab. 2Line matching results by different parameterdandθ∈[30°, 150°]
表選項
表 3θ∈[15°, 165°]的直線匹配結果Tab. 3Line matching results by different parameterdandθ∈[15°, 165°]
表選項
圖 4(a)兩張影像上提取直線的數目分別為398條、406條。一方面，由於一條直線可能存在多個組中，因此編組得到的直線組數會多於直線提取的數目；另一方面，由於夾角和鄰域範圍的設定，會存在一些直線未被編組，因此編組得到直線組數也會少於直線提取的數目。
從表 1、表 2、表 3中可以看出隨著θ角度範圍增大、d值增大，參考影像、搜索影像上編組得到的直線組數目越多，匹配得到的同名直線組數目越多，對應分裂後同名單直線數目越多，且包含參考影像、搜索影像上直線數目越多。但是隨著結果中「一對多」「多對一」「多對多」對應關係增多，匹配後處理後得到的同名直線的數目並沒有因此而增多。這是由於本文在對「多」結果的擬合和檢核的過程中採用了「一刀切」的方法，導致部分正確的匹配結果也被刪除掉，影響最終同名直線的數目。尤其在誤匹配較多的情況下，同名直線數目會大幅度的減小，例如，當d=25時，參考影像、搜索影像上編組後得到直線組的重複率較小，直線組匹配正確率不高，錯誤匹配較多，最終同名直線數目較小。後續將針對後處理中合併和檢核過程進行針對性的研究。此外，針對圖 4(a)所示影像，匹配結果中誤匹配多發生在人字形的屋頂處，主要是由於不同視角產生的直線投影不同導致直線提取結果的不同而引起的錯誤匹配。
2.2 本文演算法匹配結果及不同方法對比分析
通過2.1節不同參數對比分析試驗，本文選取參數θ∈[30°, 150°]，d=20對圖 4所示影像進行直線匹配試驗。為了與本文演算法進行更加客觀的對比分析，在初始同名點及直線提取結果相同的條件下，本文實現了文獻[13]中基於MSLD描述子的直線匹配方法，實現過程中在原文獻描述子基礎上，增加了利用同名三角約束匹配候選直線，對其結果也採用本文的後處理演算法進行處理。文獻[13]根據最小歐氏距離與次最小歐氏距離的比值小於閾值TN確定同名直線，TN=0.8。兩種方法直線匹配結果顯示如圖 5-圖 7所示，人工目視判讀直線匹配結果是否正確，其中紅色線為正確匹配直線，藍色線為錯誤匹配直線。兩種演算法直線匹配結果統計如表 4所示，其中第1列為試驗影像，第2、3列為參考影像、搜索影像上提取直線的數目，第4列為採用的演算法，第5列為匹配得到同名直線的數目，後5列表示的含義與表 1所述含義一致。從中可以看出對於圖 4(a)航空影像和圖 4(b)存在尺度變化影像，本文演算法取得較好的結果。航空影像上特徵線多位於建築物邊緣，而不同影像上同一建築物兩側紋理信息的一致性較弱，MSLD構建描述子過程中同時考慮直線兩側信息，這對不同影像上同一建築物邊緣相似性的計算會產生影響，而本文演算法利用直線組構建相關區域，對於位於同一屋頂面上的直線組不會受紋理斷裂的影響；對於尺度變化影像，主要是因為MSLD描述子本身沒有考慮尺度變化，而本文演算法在確定三角形灰度相關區域時用到仿射變換，因此對於小尺度變化的影像具有一定的適應性；但對於圖 4(c)所示紋理豐富，細節較多的影像，MSLD的結果要好於本文演算法。這是由於MSLD描述子利用梯度特徵，其穩健性強於單純基於區域的灰度相關，尤其對於細節信息豐富的影像，MSLD能產生較好的匹配效果，產生較少的錯誤匹配。而本文單純基於區域灰度相關的匹配結果可靠性較弱，初始匹配會產生較多的錯誤匹配，後處理後刪除掉大部分錯誤匹配，但是同名直線的數目也大幅度減小。後續研究將會考慮用基於梯度的描述子代替傳統的灰度相關。
表 4不同演算法直線匹配結果Tab. 4Line matching results by different algorithms
表選項
此外，匹配過程中涉及3個參數閾值Td、Th、Tρ的設定。其中，Td和Th主要用於核線約束和單應矩陣約束匹配候選，在本文演算法匹配過程中這兩種約束較為寬泛，在一定範圍內受閾值影響較小，後續象限約束較為嚴格。相關係數閾值採用經驗化閾值，取為0.7。
3 結論
本文探索了一種顧及拓撲關係的立體影像直線特徵可靠匹配演算法。該演算法主要特點表現在以下幾個方面：①在已有單應矩陣的基礎上，提出了象限約束，使得特徵編組具有任意性，不用考慮任何對應關係，簡化了編組過程；②對位於同一面片上的直線組，能有效避免紋理斷裂對匹配產生的影響，提高匹配的可靠性，同時，三角形灰度區域建立過程中引入的仿射變換使得該方法適用於存在一定尺度變化的影像；③對「一對多」「多對一」「多對多」的匹配結果進行整合，並對整合結果中的「多」直線進行檢核，對正確的「多」直線進行擬合，剔除錯誤的「多」直線匹配結果，得到「一對一」的同名直線。此演算法一方面解決了直線提取過程中產生的斷裂，另一方面提高了匹配的正確率。
下一步研究工作：①目前演算法沒有充分利用匹配結果中的冗餘信息，同時匹配結果後處理過程中，採用「一刀切」政策，部分正確的匹配結果被刪除，使得匹配直線數目大大減少，後續將重點研究充分利用冗餘信息提高後處理的高效性及有效性；②現有研究是基礎性和探索性的，後續將現有演算法中基於灰度的描述符替換成基於梯度信息的描述符，提高描述符的穩定性和可靠性；③進一步將考慮未被編組的直線，使其加入匹配。
【引文格式】王競雪，朱慶，王偉璽。顧及拓撲關係的立體影像直線特徵可靠匹配演算法[J]. 測繪學報，2017，46(11)：1850-1858. DOI: 10.11947/j.AGCS.2017.20170162
TAG:測繪學報 |