朱 慶，尚琪森，胡 翰，于昊加，鐘若飛，丁雨淋,5

（1.西南交通大學(xué)地球科學(xué)與環(huán)境工程學(xué)院，四川成都611756；2.國土資源部城市土地資源監(jiān)測與仿真重點實驗室，廣東深圳518034；3.首都師范大學(xué)北京市成像技術(shù)高精尖創(chuàng)新中心，北京100048；4.香港理工大學(xué)建設(shè)及環(huán)境學(xué)院，香港999077；5.香港中文大學(xué)太空與地球信息科學(xué)研究所，香港999077）

近年來傾斜攝影測量已經(jīng)成為城市三維建模的主要途徑[1-2].不同于如地面等手段重建的三維模型，傾斜攝影測量三維模型會受到攝影測量精度不足、構(gòu)網(wǎng)時對密集匹配點云抽稀簡化等因素的影響，噪聲明顯且難以保留如建筑物拐角棱線、道路邊界等的完整尖銳特征，需要通過修復(fù)才能滿足真實感展示和分析等深度應(yīng)用需求.特征線是模型修復(fù)的基礎(chǔ)[3]，但這些區(qū)域模型規(guī)則性缺失、特征不明顯，人工交互式選取特征點的特征線提取方式效率低、效果差，亟須一種自動化、智能化的快速特征線提取方法.

現(xiàn)有三維模型的特征線提取方法主要分為基于面和基于邊兩種類型：

1）基于面的方法要么通過多個種子點各自生長出曲率一致的面，將它們的交線作為特征線[4]；要么計算局部曲率，提取特征點或特征邊，將它們連接起來得到完整特征線[5].基于面的方法依賴曲率等對噪聲敏感的微分不變量[6]，所以通常針對點、面密度均勻的平滑模型，難以顧及粗糙的復(fù)雜模型中細(xì)碎三角形產(chǎn)生的噪聲；同時計算量大，不適合特征線的快速提取，提取結(jié)果也沒有基于現(xiàn)有三角形邊，難以利用.

2）基于邊的方法通過計算模型三角形邊的二面角等手段來估計微分量從而提取特征邊，設(shè)定閾值將滿足條件的特征邊連接成閉合環(huán)提取到特征線[7].或利用正規(guī)張量框架[8]、局部鄰域的矩[9]等來提取特征線.基于邊的特征線提取方法計算簡單、速度快，但目標(biāo)性差、正確率低，需要后續(xù)處理對結(jié)果進行過濾[10].

針對現(xiàn)有方法面對數(shù)據(jù)密集、噪聲明顯的傾斜攝影測量復(fù)雜模型特征線提取存在的嚴(yán)重缺陷，本文提出了一種快速準(zhǔn)確的基于多目標(biāo)加權(quán)最短路徑的半自動智能化方法.

1 特征線提取方法描述

本文方法流程如圖1所示.首先對傾斜攝影測量三維模型進行預(yù)處理重建拓?fù)?；然后選取兩個特征點作為目標(biāo)特征線的起終點，生成包圍盒，忽略盒外無關(guān)模型，并使用有向圖結(jié)構(gòu)組織模型數(shù)據(jù)；之后考慮距離、方向和變化趨勢等多種因素對有向圖邊進行加權(quán)；最后利用Dijkstra算法獲取起終點間的加權(quán)最短路徑，提取到目標(biāo)特征線，并對棱線特征進一步進行修復(fù)，確保質(zhì)量.

圖1 基于多目標(biāo)加權(quán)最短路徑的傾斜攝影測量三維模型特征線提取算法流程Fig.1 Flow of feature line extraction from3D model of oblique photogrammetry based on multi-objective weighted shortest path

1.1 數(shù)據(jù)的預(yù)處理

由傾斜攝影測量獲取的三角網(wǎng)模型雖然含有或者隱含正確拓?fù)潢P(guān)系，但在如OSGB等格式的三維模型數(shù)據(jù)中頂點與紋理坐標(biāo)是一一對應(yīng)關(guān)系，這些格式的數(shù)據(jù)會將對應(yīng)多個紋理坐標(biāo)的一個頂點拆分為多個頂點，具體為共用同一頂點的三角面片可能有紋理圖片上不連續(xù)的貼圖，這樣同一空間位置就會出現(xiàn)多個頂點，它們空間坐標(biāo)相同、紋理坐標(biāo)不同.這種數(shù)據(jù)組織形式雖然有利于三維模型的繪制[11]，但模型卻丟失了完整、連續(xù)的拓?fù)浣Y(jié)構(gòu)，出現(xiàn)三角網(wǎng)局部的“斷裂”，難以獲取頂點和面片的鄰域信息[12]，增大了模型幾何處理[13]的難度.

為了解決該問題，本文采用如圖1所示的模型計算與更新方法：首先通過預(yù)處理對模型進行拓?fù)渲亟╗12,14]，預(yù)處理結(jié)果就是待計算數(shù)據(jù)，之后所有幾何處理都針對待計算數(shù)據(jù)，計算結(jié)果用以更新顯示數(shù)據(jù)和文件.

其中重建拓?fù)涞念A(yù)處理主要有以下步驟：

步驟1 維護一個用于存儲處理結(jié)果的空三維模型對象T和一個以頂點坐標(biāo)為關(guān)鍵碼、頂點在T列表中的索引為值的哈希表M.

步驟2 遍歷原始模型中的三角面片.

步驟3 遍歷每個面片中的頂點.對于每個頂點，首先根據(jù)M判斷該頂點位置是否已經(jīng)存在其它頂點，如果不存在，就添加該頂點相關(guān)信息和其所在三角面片相關(guān)信息到T中，并將頂點坐標(biāo)信息和其在模型T列表中的索引插入到M；如果存在，就通過M找到該位置頂點的索引，并按照查找到的索引添加該頂點所在三角面片的相關(guān)信息到T中.

步驟4 對三角面片的遍歷結(jié)束后，模型T就是完成拓?fù)渲亟ǖ念A(yù)處理結(jié)果.

1.2 數(shù)據(jù)的組織

原始數(shù)據(jù)經(jīng)過預(yù)處理后雖然有了完整、連續(xù)的拓?fù)浣Y(jié)構(gòu)，但仍以頂點和三角面片的形式進行組織，該組織方式難以對邊進行加權(quán)，獲取鄰接頂點、面片和最短路徑也要付出很大代價[12]，同時邊的方向也是加權(quán)目標(biāo)之一，所以本文以有向圖結(jié)構(gòu)對三角網(wǎng)模型進行組織.

如圖2所示，為了獲取指定特征線，首先在模型現(xiàn)有頂點中選取兩個特征點作為目標(biāo)特征線的起終點，為了提高計算效率，再根據(jù)兩個特征點的坐標(biāo)極值生成包圍盒，忽略模型中包圍盒外無關(guān)三角網(wǎng).然后遍歷模型中的三角面片，將三角形每條邊的順、逆時針兩個方向分別錄入有向圖，方便后續(xù)加權(quán)和最短路徑求解[15].

圖2 數(shù)據(jù)的組織Fig.2 Data organization

1.3 多目標(biāo)加權(quán)

將模型以有向圖形式進行組織后，就要考慮多種影響特定特征線提取的因素對有向圖邊進行加權(quán).王欽瑞等[5,16-17]從曲率相似性、頂點間距、邊的方向、三角面片法矢夾角方面對特征線進行提取，驗證了其可行性和有效性，本文為了提取到理想特征線，從圖3所示的三角形邊長、邊的方向和鄰接三角形平面變化趨勢3個方面對有向圖邊進行加權(quán).△ABC和△BCD有公共邊BC，點A1和D1分別為點A和D在公共邊BC上的垂足，則與的夾角β就叫做共邊三角形二面角，該角可表示共邊三角形所在平面間的關(guān)系.二面角范圍為 0°～180°，180°時表示兩三角形共面.

圖3 加權(quán)目標(biāo)Fig.3 Weighted objects

本文特征線提取方法基于最短路徑，將有向圖邊初始權(quán)重設(shè)置為模型對應(yīng)邊長，可一定程度上控制尋徑結(jié)果與理想特征線間偏差從而提取到目標(biāo)特征線.所以首先計算有向圖兩節(jié)點在模型中對應(yīng)頂點的空間距離，對邊進行距離加權(quán).

目標(biāo)特征線起終點通過交互式選點確定，根據(jù)方向給邊設(shè)置一定的通過代價就可避免尋徑方向與目標(biāo)方向相反.圖4所示為方向加權(quán)方式，圖中∶黑色實線為當(dāng)前圖邊，紅色實線為交互式選取的起點、終點構(gòu)成的向量，紅色虛線由紅色實線平移而來；α為有向圖邊在模型中對應(yīng)邊的方向向量與起終點向量之間的夾角，取值范圍為0°～180°.計算模型中每條有向圖邊對應(yīng)的方向向量與起終點構(gòu)成向量的夾角：若為銳角，說明該方向與尋徑方向一致，不作處理；若為鈍角，則說明該方向與尋徑方向相反，就將該邊權(quán)重加上一個遠(yuǎn)大于模型三角形邊長的值.

圖4 方向加權(quán)Fig.4 Weighting by direction

特征通常是指曲面上具有至少一個較大主曲率的區(qū)域[6]，傾斜攝影測量三維模型的編輯和修復(fù)所需特征線不是傳統(tǒng)沿主曲率方向極值點連線所構(gòu)成的特征線[18]，而是基于現(xiàn)有三角形邊的特征線，所以要對每條邊進行特征識別.特征線處總伴隨著模型的突變，計算模型中有向圖邊對應(yīng)的共邊三角形二面角大小就能快速識別該邊特征.通過設(shè)定二面角閾值[7]可判斷邊的特征是否明顯：若二面角小于閾值，說明模型在該邊變化明顯，可作為特征線的一部分，不作處理；若二面角大于閾值，就可認(rèn)為兩三角形共面，模型在該邊沒有發(fā)生突變，特征不明顯，就將該邊權(quán)重加上一個遠(yuǎn)大于模型三角形邊長的值，從而在尋徑過程中避開此邊.

綜合上述3個因素，本文通過式（1）對有向圖邊加權(quán).

式中：dcost為加權(quán)距離即為通過代價；d為有向圖邊對應(yīng)的三角形邊長；β為模型中對應(yīng)邊的二面角，取值范圍為0°～180°；γ為二面角閾值；k為遠(yuǎn)大于三角形邊長的常數(shù).

1.4 特征線提取

考慮多種因素對有向圖進行權(quán)重設(shè)置，將不符合特征識別條件的邊權(quán)重設(shè)置為遠(yuǎn)大于邊長的值從而控制邊的通過性[19]，就能通過獲取兩特征點之間的最短路徑來提取理想的目標(biāo)特征線[20-21].

最短路徑算法可分為標(biāo)號設(shè)定（label setting，LS）算法和標(biāo)號改正（label correcting，LC）算法.LS算法不能處理權(quán)重為負(fù)值的網(wǎng)絡(luò)，但權(quán)重為正時效率高[21].本文以加權(quán)有向圖的方式組織數(shù)據(jù)，且權(quán)重均為正值，綜合空間復(fù)雜度、時間復(fù)雜度、易實現(xiàn)性等因素，采用LS算法中最具代表性的Dijkstra算法獲取最短路徑[20-21].

1.5 棱線修復(fù)

在提取到特征線后，為了解決模型直線型棱線處結(jié)構(gòu)粗糙、噪聲較大、特征不明顯的問題，擬合提取結(jié)果所經(jīng)頂點到起終點所在直線實現(xiàn)對棱線尖銳特征的修復(fù).

具體擬合方法如圖5所示，利用式（2）把特征線上的頂點O投影到由起、終點S、E構(gòu)成的向量上，得到投影向量，再通過已知的S點坐標(biāo)計算出投影點P的坐標(biāo).將O點坐標(biāo)修改為P點坐標(biāo)，完成O點向所在直線的擬合.

圖5 特征線的拉直Fig.5 Straightening of feature line

2 試驗與分析

本文選用無人機傾斜攝影測量獲取的實景三維模型進行試驗，首先通過實際提取和修復(fù)結(jié)果，驗證了本文特征線提取和修復(fù)方法的可行性與有效性.之后與單一目標(biāo)加權(quán)方法進行對比，說明各個加權(quán)目標(biāo)的有效性，驗證了綜合考慮時效果最優(yōu).最后與現(xiàn)有方法進行對比，突顯了本文方法的優(yōu)越性.

2.1 特征線提取與修復(fù)結(jié)果

地物模型特征線處總伴隨著由諸如河面與河岸高差、道路與道邊差異等因素造成的突變.所以在面對不同地物特征線的提取時，設(shè)置合適的二面角閾值就能利用本文方法提取到較為理想的結(jié)果.

不同場景和地物的特征提取需求不同，二面角閾值大小可交互式的通過提取效果來確定，本文將二面角閾值設(shè)置為160°進行實驗，不同地物利用本文方法提取到的特征線結(jié)果如圖6所示.紅色點為提取結(jié)果所經(jīng)模型頂點，均具有明顯特征，提取結(jié)果較為理想.同時也體現(xiàn)出本文方法不僅適用于直線特征的提取，對曲線甚至不規(guī)則特征也有很好的提取效果.

驗證了本文提取方法的有效性后，利用1.5節(jié)中修復(fù)方法，對建筑物棱線進行修復(fù).修復(fù)前后模型如圖7所示，紅色線框內(nèi)為目標(biāo)棱線所在區(qū)域，相比修復(fù)前模型，修復(fù)后模型的棱線區(qū)域結(jié)構(gòu)清晰、特征明顯.

圖6 特征線提取結(jié)果Fig.6 Feature line extraction results

圖7 建筑物棱線修復(fù)效果Fig.7 Remediation of the edge line

2.2 單一目標(biāo)與多目標(biāo)提取方法對比

不同加權(quán)目標(biāo)的特征線提取結(jié)果如圖8所示.其中模型變化趨勢用有向圖邊在模型中對應(yīng)的二面角大小衡量.

由圖 8（b）、（c）可知：只考慮距離時，提取結(jié)果是起終點間路程最短的路徑；只考慮方向時，提取結(jié)果是保證正確尋徑方向下步數(shù)最少的路徑.兩種方法均無法保證提取結(jié)果具有明顯特征，提取效果很差.

由圖8（d）可知：僅考慮模型變化趨勢時，提取效果與本文方法最為接近.該方法在保證提取結(jié)果有明顯特征的前提下找到了步數(shù)最少的路徑，但只考慮了局部特征，沒有顧及尋徑結(jié)果與目標(biāo)特征線間的整體偏差，所以提取效果與本文方法有一定差距.

對比圖 8（a）～（d）可知：距離、方向和模型變化趨勢對特征線提取結(jié)果均有影響，綜合考慮3種因素時提取效果最好.

圖8 不同加權(quán)目標(biāo)的提取結(jié)果Fig.8 Extraction results of different weighted objectives

2.3 與交互式等特征提取方法對比

利用不同方法得到的特征線提取結(jié)果如圖9所示，圖中虛線框為目標(biāo)特征所在區(qū)域.圖9（c）為利用文獻[10,22,23]中綜合面曲率和邊銳利程度方法的特征線提取結(jié)果，圖9（d）～（f）分別是將邊銳利度[10]閾值設(shè)置為10000、20000 和 50000 對圖 9（c）中特征線進行過濾得到的結(jié)果.

對比圖 9（a）、（b）可看出：本文方法與交互式選點方法提取效果相當(dāng)，但僅需選取兩點，大大提升了效率；同時量化特征，避免人工選點主觀性和隨機性強的問題.

圖9（c）～（f）顯示傳統(tǒng)方法對噪聲敏感、目標(biāo)性差，提取結(jié)果難以利用.對比圖 9（a）和圖 9（c）～（f）可明顯看出本文方法面對復(fù)雜傾斜攝影測量三維模型時的優(yōu)勢：目標(biāo)性強，能提取到指定特征線；抗噪聲能力強，能夠正確提取粗糙復(fù)雜模型的特征線.現(xiàn)有方法提取結(jié)果即使經(jīng)過一系列過濾，效果仍和本文方法有較大差距.

圖9 特征線提取效果對比Fig.9 Comparison of extracted feature lines

3 結(jié)束語

本文提出的特征線提取方法對傾斜攝影測量三維模型提取效率高、效果好、目標(biāo)準(zhǔn).同時，該方法還具有較強的適應(yīng)性和可拓展性特點，不僅能提取不同類型特征線，還能通過引入新的加權(quán)目標(biāo)來滿足特定情況下的特征線提取需求.

進一步的研究將在幾何特征提取基礎(chǔ)上，綜合考慮影像紋理特征，提高各種復(fù)雜特征提取的自動化與智能化水平和能力.