一種三維天際線快速提取和顯示算法

付仲良 譚均銘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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