付仲良 譚均銘

1 武漢大學遙感信息工程學院，湖北武漢，430079

天際線是城市整體景觀的體現(xiàn)，反映了城市的文化內(nèi)涵和經(jīng)濟發(fā)展水平。當前多采用圖像處理的方法在數(shù)碼照片中提取天際線，但二維圖像無法表達三維真實世界中的復雜實體對象之間的關(guān)系，也無法動態(tài)獲取不同觀察角度下的天際線。因此，需要一種能夠全方位顯示天際線與真實地表環(huán)境的空間關(guān)系，且能在加載了大數(shù)據(jù)量城市模型的三維場景中快速提取和顯示天際線的算法。

目前，國內(nèi)外建筑規(guī)劃領(lǐng)域?qū)μ祀H線的研究主要集中在天際線的評價指標上［1］，而天際線作為特征線提取主要應(yīng)用在小型飛行器導航避障、地理圖像標注等方面［2?6］，多采用基于區(qū)域的分割分類和邊緣檢測等圖像處理方法。Fang等［7］采用基于亮度梯度的區(qū)域增長算法對相機拍攝的城市全景照片的每列像素由上到下檢測亮度值，將其與閾值進行比較，從而提取天際線像素點。Saurer等［8］采用支持向量機（support vector machine，SVM）算法對顏色、紋理等特征訓練分類器，分割天空和地形。邊緣檢測方面，Yang等［9］采用Canny濾波邊緣檢測算法提取畫面的拓撲信息，并以山峰最高點和兩側(cè)低點為種子點延伸構(gòu)建天際線。劉松濤等［10］采用形態(tài)學濾波和Hough變換等方法來識別海天相接線。在軟件方面，呂亞霓［11］使用ArcGIS平臺的天際線工具導入三維模型，計算選定視野面上的虛擬阻擋點，并將其連接成線，投影在圓柱上展開成二維平面以展示天際線輪廓?；趫D像處理的方法存在云霧等干擾天際線提取的問題，軟件獲得的只是二維平面上的天際線輪廓，不適用于在真三維場景中實時提取天際線，無法獲取最真實城市天際線的視角感官。而在三維天際線的提取方面，雖有一些系統(tǒng)的功能實現(xiàn)，如超圖Super Map 3D，但并沒有文獻對其中的方法進行描述和研究。

針對這些問題，本文從天際線的定義入手，采用視線跟蹤算法，在三維場景中從視點引出若干束視線，將其與場景中的建筑物模型相交的第一個點作為天際線點，按順序連接成線。由于場景中數(shù)據(jù)量制約了相交檢測的速度，采取基于Open MP的中央處理器（central processing unit，CPU）并行策略來加速算法。在動態(tài)場景瀏覽過程中，利用顯卡圖形處理器（graphics processing unit，GPU）渲染管線中的模板測試動態(tài)渲染建筑物與天相接的輪廓線。針對三維場景數(shù)據(jù)量大、場景實時變換的特性，該算法能充分利用CPU的計算能力提高三維天際線提取的速度，并利用GPU渲染管線，實現(xiàn)天際線流暢渲染。

1 基于OpenMP并行視線跟蹤求交算法提取天際線

視線跟蹤求交算法通過追蹤視點到視線空間內(nèi)任意一點所經(jīng)過的路徑，檢測其與場景中物體的交點。根據(jù)天際線的定義，即物體與天相接的輪廓線，利用視線跟蹤求交算法提取天際線的主要思想如下：

首先獲取當前視角下相機的透視投影矩陣，解算出視錐體遠近裁剪面大小，并得到遠裁剪面4個角點的投影坐標，通過投影變換的逆變換得到4個角點的世界坐標。然后，以視點到遠裁剪平面左上角點為起始方向，視點到遠裁剪平面右上角點為水平掃描終止方向，計算水平掃描角，以視點到遠裁剪面左下角點為垂直掃描終止方向，計算垂直掃角。最后，在水平方向（X軸）從左至右，垂直方向（Y軸）從上到下的每一個角度采樣位置跟蹤視線，與場景相交取到的第一個交點即為天際線點，連接成線。

視線跟蹤求交算法本身蘊含一定的并行性，其中包含雙重嵌套循環(huán)，即在X方向掃描循環(huán)過程中進行Y方向掃描循環(huán)。Open MP是應(yīng)用在共享內(nèi)存處理器上的并行編程標準，使用fork?join并行機制，主線程遇到定義的并行區(qū)域時會創(chuàng)建一組工作線程，在此區(qū)域內(nèi)，多個工作線程可以執(zhí)行相同的代碼塊或使用工作共享結(jié)構(gòu)體分擔不同的任務(wù)，并行區(qū)結(jié)束，多線程組同步，工作線程終止，主線程繼續(xù)執(zhí)行。因此，OpenMP非常適合用來執(zhí)行循環(huán)語句。

并行視線跟蹤求交算法具體實現(xiàn)步驟如下：

1）初始化視線空間X軸方向（方位角）和Y軸方向（俯仰角）的步長as和es以控制迭代次數(shù)，并聲明一個數(shù)組vs用于存儲天際線點。

2）根據(jù)投影相機空間參數(shù)解算俯仰角ea和視點到遠裁剪面距離（視距）r，遠裁剪面左上、右上、左下、右下4個角點A、B、C、D的世界坐標。

3）設(shè)置線程數(shù)，開啟多線程并行計算，由as和直線方程在水平方位依次計算遠裁剪面上邊的點坐標po和平行的下邊點坐標pd。并根據(jù)視點e和po、pd三點共圓的約束，以r為半徑解算圓方程。并以es為步長在ea上插值得到弧形掃描線上的點坐標集合vp。

4）對于方位步長上每次掃描得到的vp，遍歷數(shù)組，并引視點到數(shù)組中點為視線，與場景中的物體進行相交檢測，將相交取得的第一個交點作為天際線點存儲到vs中，結(jié)束遍歷，跳出循環(huán)。

5）若計數(shù)未超過as，則跳轉(zhuǎn)到步驟3）；若計數(shù)超過as，則結(jié)束并行，并由主線程將vs中的點按順序連接成天際線。

雙重循環(huán)中存在數(shù)據(jù)依賴，即第二層循環(huán)的輸入?yún)?shù)vp由第一層循環(huán)結(jié)果得到。因此，為了保證兩個循環(huán)由同一線程處理，在最外層循環(huán)采用OpenMP制導語句#pragma omp parallel for可以使整個區(qū)域代碼由同一線程執(zhí)行。

在線程的調(diào)度優(yōu)化上，使用schedule方法將總循環(huán)次數(shù)平均分配給每個線程。如分配每個線程處理3個循環(huán)，線程0執(zhí)行i=0、1、2，線程1執(zhí)行i=3、4、5，依此類推。使用該方法需要注意vs數(shù)組中點的順序問題，可以通過每個線程ID標識每個線程計算得到的vs[ID]數(shù)組，在并行塊中設(shè)置barrier路障，等待所有線程都到達，將數(shù)組按順序合并后才能通過進入下一次多線程的并行計算。并行視線跟蹤求交算法提取天際線的程序結(jié)構(gòu)流程圖見圖1。

圖1 利用并行視線跟蹤求交算法提取天際線的流程Fig.1 Flow Chart of Skyline Extraction with Parallel Line?of?Sight Tracking Intersection Algorithm

2 基于GPU渲染管線模板測試實時渲染天際線

在三維場景動態(tài)瀏覽過程中，視點和視線空間隨每一幀的變化而變化，若采用視線跟蹤求交算法實時提取天際線，CPU計算量激增，超出了多核CPU并行處理的能力，因此需要考慮利用GPU渲染管線。為了充分利用渲染管線的高效處理能力，考慮在光柵化階段利用GPU對三維天際線進行實時渲染。具體為光柵化階段中的融合階段，這一階段主要負責將像素著色階段生成的片段顏色與當前存儲在顏色緩存中的顏色合并，以及解決可見性問題，通過深度緩存測試渲染離視點更近的圖元，并對該位置上的z值和顏色進行更新。而在寫入深度緩存前，還可通過模板緩存記錄渲染圖元位置的離屏緩存，用以控制渲染到顏色緩存和z?深度緩存。這種技巧也叫模板測試，可用于三維渲染中物體輪廓線的顯示，它完全利用GPU計算，顯示效率高，可用于實時渲染三維天際線。具體步驟如下：

1）首先清除模板緩沖區(qū)。在第一次繪制時，啟用模板測試，正常繪制物體，設(shè)置模板測試總能通過，并規(guī)定模板測試未通過時，保留模板值。模板測試通過，但深度測試未通過時，保留模板值。模板測試和深度測試都通過時，用參考值1替換模板值。這樣就使需要繪制的圖元區(qū)域，即地面物體的模板值為1，而其他部分，即天空背景模板值為0。

2）設(shè)置正面剔除，以線框形式繪制地物圖元的背面多邊形，并賦予線的寬度和顏色等材質(zhì)屬性，使其略寬于原始物體。

3）繪制步驟2）中放大的物體時，設(shè)置模板值不為1時通過模板測試。并規(guī)定模板測試未通過時，保留模板值。模板測試通過，但深度測試未通過時，保留模板值。模板測試和深度測試都通過時，用參考值1替換模板值。這樣就使模板緩沖區(qū)不為1的地方，即天空背景通過模板測試。

兩次繪制場景，將第二次以線框形式繪制的三維物體疊加到第一次繪制的原始物體上，通過模板測試剔除模板區(qū)域內(nèi)的線框，保留模板區(qū)域0值和1值相交區(qū)域的線框，即天空背景和地物相接的線段，達到天際線渲染的效果。

3 實驗與分析

本文的三維城市模型數(shù)據(jù)來源于四川省崇州市城區(qū)傾斜攝影模型數(shù)據(jù)。數(shù)據(jù)量為22.7 GB，以瓦片形式組織。算法運行平臺配置為Core i5 2.4 GHz、8 GB內(nèi)存、256 GB硬盤；算法運行環(huán)境為Win?dows10 64位操作系統(tǒng)，Visual Studio2010編譯環(huán)境，Open Scene Graph三維渲染引擎。

1）實驗1：并行視線跟蹤求交算法。設(shè)置線程數(shù)為2，不同循環(huán)次數(shù)（即水平方向步長×垂直方向步長）下串行算法與并行算法的耗時比較見表1?？梢钥闯?，基于Open MP的視線跟蹤求交算法能明顯提高算法的執(zhí)行效率，但是由于該算法是簡單的循環(huán)掃描，循環(huán)次數(shù)的增大對加速比的影響不大。

表1 不同循環(huán)次數(shù)下算法運行的時間Tab.1 Time Consumption of Algorithms with Different Number of Cycles

在此基礎(chǔ)上，考慮通過提高線程數(shù)來加快算法運行的速度。不同線程數(shù)下算法運行速度見圖2?；诓⑿杏嬎愕乃惴S著開辟線程數(shù)增加，速度有一定的提高。但是隨著線程數(shù)增多，加速效果也越來越不明顯，主要是因為線程之間通信的開銷。

圖2 不同線程數(shù)下算法運行速度Fig.2 Excution Time in Different Number of Processors

通過視線追蹤求交算法提取到的三維天際線效果如圖3所示。

圖3 利用視線跟蹤求交算法提取的三維天際線Fig.3 3D Skyline Extracted by Line?of?Sight Tracking Intersection Algorithm

2）實驗2：基于GPU渲染管線模板測試的三維天際線實時渲染。城市模型三維場景中數(shù)據(jù)量大，若每一幀都通過視線跟蹤求交計算天際線，會嚴重影響系統(tǒng)性能。本文嘗試在渲染的最后階段，利用顯卡GPU渲染管線模板測試分離地物和天空，描繪鄰接的邊界線。由于模板測試屬于硬件層的渲染，通過光柵化技術(shù)在屏幕上對模型片元著色，節(jié)省了大量系統(tǒng)計算和內(nèi)存空間。

在場景數(shù)據(jù)量不同的條件下，基于模板測試與基于Open MP并行算法的時間耗時見圖4。隨著三維場景中數(shù)據(jù)量增大，片元數(shù)增多，占用的內(nèi)存和CPU增大，導致基于OpenMP的并行算法耗時增加，不適用于在動態(tài)場景變化中實時生成天際線?；贕PU模板測試的算法利用了屏幕的緩存技術(shù)，在硬件層面對天際線進行顯示，耗時隨場景數(shù)據(jù)量增大的變化較小，能在毫秒級別對天際線進行渲染。但是這種算法丟失了天際線的幾何屬性，只能作為渲染顯示，無法提取天際線幾何信息。因此，需要結(jié)合射線求交算法實現(xiàn)天際線的快速提取和顯示。通過街景漫游功能，動態(tài)變換場景，實時生成并流暢顯示天際線，幀數(shù)在54幀/s左右。三維天際線街景動態(tài)瀏覽見圖5。

圖4 兩種算法耗時對比Fig.4 Time Consumption Comparison of the Two Algorithms

圖5 三維天際線街景動態(tài)瀏覽Fig.5 Dynamic Browsing of 3D Skyline Street View

4 結(jié)束語

源于城市規(guī)劃對天際線設(shè)計和控制的需求，針對當前天際線提取算法多為二維圖像處理的方法，且在大數(shù)據(jù)量城市模型三維場景下計算效率低的問題，本文提出一種采用Open MP并行加速的視線跟蹤求交算法，在真三維場景中提取天際線，并在視角動態(tài)變化時，通過GPU渲染管線的模板測試顯示天際線。實驗證明，此算法能快速提取三維天際線的幾何結(jié)構(gòu)，并具有良好的顯示效果。針對提取出的三維天際線點，需要進一步研究相關(guān)擬合簡化算法，以平滑天際線，達到更好的顯示效果。