鐘 成，李 卉，黃先鋒

（1.中國(guó)地質(zhì)大學(xué) 教育部長(zhǎng)江三峽庫(kù)區(qū)地質(zhì)災(zāi)害研究中心，湖北 武漢 430074；2.中國(guó)地質(zhì)大學(xué) 行星科學(xué)研究所，湖北 武漢 430074；

3.武漢大學(xué) 測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079）

傳統(tǒng)正射糾正未考慮建筑物、樹木等地面目標(biāo)的投影變形，在城市大比例尺正射影像上，建筑物傾斜遮擋的情況非常嚴(yán)重，影響了影像信息的有效解譯和利用.20世紀(jì)90年代以來，隨著世界范圍內(nèi)城市三維仿真項(xiàng)目的興起和城市大比例尺地圖的應(yīng)用需求日益強(qiáng)烈，利用城市三維模型制作“真正射影像”的研究和生產(chǎn)逐漸展開.

真正射影像制作的核心問題是高效穩(wěn)健的遮蔽檢測(cè)過程.根據(jù)攝影測(cè)量的基本原理，非正射投影造成的高層建筑傾斜會(huì)導(dǎo)致對(duì)低矮目標(biāo)的遮蔽，若直接利用數(shù)字微分糾正方法為DSM（數(shù)字表面模型）格網(wǎng)尋找對(duì)應(yīng)影像信息，低矮目標(biāo)將獲得高層建筑的影像信息，其結(jié)果是造成高層建筑在正射影像上多次出現(xiàn)，學(xué)術(shù)界稱之為“鬼影”現(xiàn)象.這樣的正射影像無法談及幾何精度或光譜精度等問題.解決該問題的思路是，首先檢測(cè)出高層建筑對(duì)低矮目標(biāo)的遮蔽情況，在正射糾正過程中這些遮蔽地區(qū)不分配影像信息，最后利用影像序列的重疊信息或利用仿真方法修復(fù)遮蔽地區(qū).

已有遮蔽檢測(cè)方法大多基于計(jì)算機(jī)圖形學(xué)的ZBuffer消隱技術(shù)，比較目標(biāo)距光源點(diǎn)的距離判斷其遮蔽情況［1－4］.這類方法在處理大量復(fù)雜的矢量建筑物模型時(shí)效率很低［5］；而在處理柵格數(shù)據(jù)時(shí)，因難以捕獲相機(jī)畸變和投影成像造成的柵格變形，將導(dǎo)致錯(cuò)誤的判斷競(jìng)爭(zhēng)關(guān)系，造成大量偽遮蔽和偽可見噪聲［6－7］.此外，該方法無法處理被高窄墻體遮蔽目標(biāo)的偽可見問題，即所謂“M-Portion”問題［3，8－9］，改進(jìn)的方法需要將墻面納入遮蔽檢測(cè)計(jì)算過程，大大增加了計(jì)算工作量和復(fù)雜度.產(chǎn)生這些問題的根本原因在于復(fù)雜多樣的現(xiàn)實(shí)世界難以用簡(jiǎn)單的三維體塊模型表示，基于圖形學(xué)的Z-Buffer技術(shù)也未顧及攝影測(cè)量的特殊情況［10］.

1 快速遮蔽檢測(cè)方法

從計(jì)算效率的角度出發(fā)，優(yōu)先考慮采用柵格DSM參與計(jì)算；從計(jì)算穩(wěn)健性的角度出發(fā)，需克服各類偽可見和偽遮蔽噪聲.為此可采用徑向投影高度角的變化情況進(jìn)行遮蔽區(qū)域分析，其原理是，同一方位射線上逐漸遠(yuǎn)離天底點(diǎn)時(shí)目標(biāo)的投影高度角逐漸增大；在進(jìn)入被遮蔽地區(qū)時(shí)投影高度角突然變小，直到離開被遮蔽地區(qū)時(shí)又回到之前的數(shù)值.據(jù)此，可以容易發(fā)現(xiàn)被遮蔽地區(qū).該方法對(duì)遮蔽地區(qū)和遮蔽源的掃描都是連續(xù)的，對(duì)遮蔽地區(qū)的判斷僅需高層建筑的邊緣柵格，可避免因柵格變形造成的錯(cuò)誤競(jìng)爭(zhēng)，也可避免因缺乏墻面信息造成的“M-Portion”問題［11］.

為全面檢測(cè)遮蔽情況，從天底點(diǎn)到DSM邊緣所有柵格的射線都需要分析太陽(yáng)高度角的變化情況.此時(shí)，鄰近天底點(diǎn)的柵格將被多次訪問，導(dǎo)致效率低下.可行的方法包括徑向掃描和螺旋掃描兩種方法（圖1），前者首先以不同半徑將DSM劃分為多個(gè)圓環(huán)，在每個(gè)圓環(huán)內(nèi)根據(jù)完整掃描的要求制定合適的掃描和方向間隔；后者從天底點(diǎn)出發(fā)以螺旋方式掃描DSM柵格，最終完成對(duì)DSM的完整掃描.本文力圖通過分析兩種方法的計(jì)算步驟和算法復(fù)雜度，推導(dǎo)最優(yōu)的配置方案，最終提出具有最高效率的遮蔽檢測(cè)方法.

兩種方法基本原理一致，區(qū)別在于對(duì)DSM掃描的方式，以及由此導(dǎo)致的不同的掃描面積、方位射線數(shù)和進(jìn)行可見性判斷的面積.因此，通過分析計(jì)算過程的復(fù)雜度，找到最優(yōu)的分配方法，可找到復(fù)雜度最低的遮蔽檢測(cè)方法.首先，基于算法原理利用嚴(yán)密的幾何關(guān)系可以推出兩種方法不同的掃描面積、射線數(shù)據(jù)和可見性判斷面積；然后，利用計(jì)算數(shù)學(xué)理論推導(dǎo)出各個(gè)步驟包含的計(jì)算復(fù)雜度；最后利用微積分的極值理論求出具有最小復(fù)雜度的方法.

1.1 算法過程

首先，對(duì)于給定DSM 柵格（x，y，z），投影中心坐標(biāo)為（Xc，Yc，Zc），計(jì)算并記錄每個(gè)DSM 柵格的投影高度角a.

圖1 徑向掃描和螺旋掃描方法Fig.1 Illustration of radial sweep and spiral sweep method

然后掃描DSM，分析沿掃描射線的投影高度角變化情況.對(duì)于徑向掃描，計(jì)算當(dāng)前范圍內(nèi)由邊緣柵格決定的方位射線，沿著射線方向逐個(gè)比較a變化，同時(shí)記錄柵格的可見性，若發(fā)現(xiàn)a突然變小，則記錄當(dāng)前的amax值，投影高度角未超出amax的柵格都被認(rèn)為是被遮蔽的地區(qū)，其可見性值設(shè)為零.

對(duì)于螺旋掃描方式，需要計(jì)算每個(gè)柵格與天底點(diǎn)確定的方位射線，然后比較其與射線上相鄰且靠近天底點(diǎn)的柵格的a變化，同樣記錄當(dāng)前的amax值，投影高度角未超出amax的柵格被認(rèn)為是被遮蔽的地區(qū)，其可見性值設(shè)為零.

由上述分析可知，兩種方法效率的影響因子包括不同的掃描面積、方位射線數(shù)和可見性判斷面積，需要研究這些因子的優(yōu)化方法，以提高算法效率.

1.2 計(jì)算復(fù)雜度分析

假定DSM為圓形且未進(jìn)行分割，設(shè)定柵格尺寸為1，徑向掃描的每條掃描射線的面積為

式中：r為DSM半徑；d為DSM柵格的直徑.而掃描射線的數(shù)量可以由下式獲得：

可計(jì)算得到徑向掃描的掃描面積為

從式（4）可以看到，徑向掃描面積兩倍于DSM實(shí)際面積，存在較大程度的重復(fù)掃描.考慮到若一個(gè)柵格的可見性已經(jīng)判定，那么在重復(fù)掃描的過程中，不需要再重復(fù)判斷，因此需要進(jìn)行可見性判定的面積為πr2.

若DSM進(jìn)行了n次分割，根據(jù)圖1，其掃描面積、射線數(shù)量和可見性判斷面積計(jì)算公式演變?yōu)?/p>

式中：Sr為徑向掃描面積；Lr為徑向掃描射線數(shù)；Vr為徑向掃描需要進(jìn)行可見性判斷的面積.

對(duì)于螺旋掃描，容易判斷其掃描面積和可見性面積等于DSM的面積.考慮到每個(gè)柵格都需要計(jì)算方位射線，可以得到

式中：Ss為螺旋掃描面積；Ls為螺旋掃描射線數(shù)；Vs為螺旋掃描需要進(jìn)行可見性判斷的面積.

通過計(jì)算數(shù)學(xué)分析，可知計(jì)算每一條射線參數(shù)需要5個(gè)基本操作（加減乘除），確定柵格的可見性需要4步操作.在徑向掃描中需要3步操作來掃描一個(gè)柵格，而螺旋掃描中僅需要1步可實(shí)現(xiàn)柵格定位.考慮到這些基本操作的復(fù)雜度是常量，兩種方法的計(jì)算復(fù)雜度可以估計(jì)為

式中：Cr代表徑向掃描方法的復(fù)雜度；Cs代表螺旋掃描方法的復(fù)雜度.

式（7）表明徑向掃描方法的復(fù)雜度主要依賴于DSM劃分方式，而螺旋掃描的復(fù)雜度依賴于DSM的大小.在給定DSM的情況下，螺旋掃描的復(fù)雜度是一個(gè)常量，而徑向掃描的復(fù)雜度是可以通過修改DSM劃分方法而改善的.

1.3 求解最小復(fù)雜度

兩種方法計(jì)算復(fù)雜度的差異可以通過下式計(jì)算：

若采用等差數(shù)列方法劃分DSM，即ri－ri－1＝m（m＞0）可得

在給定DSM的情況下，r為常量，此時(shí)求最小復(fù)雜度演變?yōu)榍蠼鈫巫兞亢瘮?shù)的最小值問題.考慮到n和ΔC在［1，r］是連續(xù)的，且ΔC是可微的，對(duì)ΔC求極值可得到

則可獲得最小ΔC的分割數(shù)為

帶入式（9），計(jì)算得到最小的ΔC為

當(dāng)r大于10時(shí)，ΔC的值小于0，也就是說通過選擇最佳分割數(shù)，徑向掃描的復(fù)雜度此時(shí)小于螺旋掃描.這證明螺旋掃描效率高于徑向掃描的一般性結(jié)論不成立.

若采用等比數(shù)列方法分割 DSM，即ri／ri－1＝m（m＞0），式（8）演變?yōu)?/p>

由于求解冪指數(shù)的極值比較復(fù)雜，反而會(huì)影響計(jì)算復(fù)雜度，本文不再討論.同樣的，也可以采取其他方法劃分DSM，進(jìn)而比較算法復(fù)雜度.

上述推導(dǎo)已經(jīng)證明通過求解最優(yōu)分割數(shù)，徑向掃描方法的復(fù)雜度可以得到大幅度改善并獲得比螺旋掃描更高的計(jì)算效率.因此，基于最優(yōu)分割數(shù)的徑向掃描方法可認(rèn)為是一種高效穩(wěn)健的遮蔽檢測(cè)方法.

2 實(shí)驗(yàn)與討論

考慮到LiDAR（激光掃描數(shù)據(jù)）可以快速有效地獲取地表三維模型，已經(jīng)日益成為城市三維建模的重要數(shù)據(jù)源，實(shí)驗(yàn)采用LiDAR點(diǎn)云構(gòu)建高分辨率DSM；作為基礎(chǔ)實(shí)驗(yàn)數(shù)據(jù)，引入Z-Buffer方法對(duì)比算法的穩(wěn)健性和效率.

實(shí)驗(yàn)數(shù)據(jù)如圖2所示，包含加拿大多倫多地區(qū)的LiDAR點(diǎn)云數(shù)據(jù)（圖2a）和航空影像數(shù)據(jù)（圖2b）.航空影像的分辨率為0.5m，LiDAR點(diǎn)云的分辨率為1.0m.航空影像記錄了城市目標(biāo)的灰度和紋理信息，LiDAR數(shù)據(jù)記錄城市目標(biāo)的三維坐標(biāo).在圖2b中左下部分有重大偏移和遮蔽的地區(qū)，從圖2c展示的局部點(diǎn)云可知，這些地區(qū)點(diǎn)云中不存在變形和遮蔽.因此，利用LiDAR構(gòu)建的DSM實(shí)施航空影像的真正射糾正是可行的.

圖2 實(shí)驗(yàn)數(shù)據(jù)Fig.2 Experimental data

圖3展示了利用典型方法實(shí)施遮蔽檢測(cè)的實(shí)驗(yàn)結(jié)果.圖3a展示了Z-buffer方法產(chǎn)生的可見性矩陣，圖3b展示其局部放大圖，圖3c展示了對(duì)其進(jìn)行Z-buffer遮蔽檢測(cè)的結(jié)果，圖3d展示了徑向掃描方法產(chǎn)生的可見性矩陣.從圖3a～3c中，可以發(fā)現(xiàn)大量的離散噪聲，以及由噪聲組成的黑色曲線.這些是因?yàn)閆-buffer方法無法適應(yīng)DSM起伏和分辨率差異引起的.如果采用濾波方法消除噪聲，將降低影像的細(xì)節(jié)層次.而在圖3d～3f中則沒有這些離散噪聲和曲線，表明基于徑向投影高度角變化的檢測(cè)方法可以有效地適應(yīng)城市地區(qū)復(fù)雜的DSM起伏和分辨率差異.圖3也表明，由于LiDAR數(shù)據(jù)分辨率低于遙感影像，由其構(gòu)建的DSM生產(chǎn)的真正射影像中缺乏精確的斷裂線，建筑物輪廓出現(xiàn)鋸齒.

圖3 遮蔽檢測(cè)實(shí)驗(yàn)Fig.3 Detecting occlusions with typical methods

高窄的結(jié)構(gòu)容易產(chǎn)生M－portion問題，在數(shù)據(jù)源中較難發(fā)現(xiàn)此類結(jié)構(gòu)，為了驗(yàn)證算法對(duì)于 M－portion問題的處理能力，圖4展示了兩種方法對(duì)于高窄結(jié)構(gòu)的檢測(cè)結(jié)果.圖4a展示了實(shí)驗(yàn)中人為添加了模擬的高窄結(jié)構(gòu).圖4b是利用Z-buffer方法檢測(cè)的結(jié)果.可見建筑頂面的遮蔽范圍被檢測(cè)出來，而部分被墻面遮蔽地區(qū)未被檢測(cè)到.這是因?yàn)榭紤]到效率問題，一般未將墻面納入DSM參與計(jì)算和分析，若墻面遮蔽地區(qū)大于建筑本身面積，則會(huì)導(dǎo)致偽可見的情況，即所謂“M-portion”問題.高且窄的建筑物最容易導(dǎo)致這類問題的出現(xiàn).圖4c是利用徑向掃描方法檢測(cè)的結(jié)果，可見建筑物頂面和墻面遮蔽的地區(qū)都被檢測(cè)出來了.根據(jù)該方法的原理，僅需掃描建筑物邊緣的柵格即可完成對(duì)頂面和墻面遮蔽的檢測(cè)，無需額外改進(jìn)和其他步驟.而絕大部分基于Z－buffer原理的方法及改進(jìn)算法往往很難高效地發(fā)現(xiàn)并解決M－portion問題.從這一點(diǎn)來說，該方法極大地提高了遮蔽檢測(cè)的穩(wěn)健性.

圖4 對(duì)高窄結(jié)構(gòu)的檢測(cè)Fig.4 Detecting occlusions with simulated DSM

本文對(duì)典型方法的計(jì)算效率做了對(duì)比實(shí)驗(yàn)，包括Z-Buffer方法，徑向掃描方法、螺旋掃描方法和最優(yōu)分割數(shù)徑向掃描方法.實(shí)驗(yàn)設(shè)備是具有雙核2.8G CPU和3.0GDDR內(nèi)存的微機(jī).圖5展示了效率實(shí)驗(yàn)的結(jié)果.

圖5 效率實(shí)驗(yàn)Fig.5 Performance of typical methods

從圖5可見，隨著給定DSM尺寸增大，各類方法消耗的時(shí)間增加.其中，對(duì)于任何尺寸，Z-Buffer總是消耗最長(zhǎng)時(shí)間，徑向掃描方法次之，螺旋掃描方法又次之，最優(yōu)分割徑向掃描方法消耗的時(shí)間最短.這說明最優(yōu)分割徑向掃描方法在這些方法中具有最高效率.考慮到其他基于Z-Buffer原理的方法或改進(jìn)算法往往比基于柵格數(shù)據(jù)的Z-Buffer消耗更長(zhǎng)的時(shí)間［11］，可認(rèn)為最優(yōu)分割徑向掃描方法是具有最高效率的遮蔽檢測(cè)方法.此外，值得注意的是，最優(yōu)分割徑向掃描方法的效率曲線表現(xiàn)為線性函數(shù)，而ZBuffer方法的效率曲線表現(xiàn)為高次函數(shù).隨著給定DSM尺寸逐漸增大，兩種方法消耗的時(shí)間差距會(huì)越來越大.

3 結(jié)語(yǔ)

近十幾年來，國(guó)內(nèi)外學(xué)者努力嘗試尋找一種高效、穩(wěn)健、精確的遮蔽檢測(cè)方法.已有的基于ZBuffer技術(shù)的遮蔽檢測(cè)方法并不適應(yīng)攝影測(cè)量的特殊要求，已經(jīng)被證明存在諸多難以克服的問題，而一些改進(jìn)算法往往過于復(fù)雜，計(jì)算不穩(wěn)定且效率低下.實(shí)驗(yàn)表明，基于徑向投影高度角變化的方法可以有效解決因地形起伏、分辨率差異和高窄墻體引起的各類偽可見和偽遮擋問題，實(shí)現(xiàn)穩(wěn)健、精確的遮蔽檢測(cè).對(duì)比實(shí)驗(yàn)表明，同樣數(shù)據(jù)量下該方法消耗時(shí)間最少，且數(shù)據(jù)量增大時(shí)的時(shí)間增量也最少.本文的理論推導(dǎo)和實(shí)驗(yàn)表明，最優(yōu)分割的徑向掃描方法可以實(shí)現(xiàn)穩(wěn)健、精確、快速、高效的遮蔽檢測(cè)，有利于大規(guī)模高質(zhì)量真正射影像制作.

［1］ Amhar F，Jansa J，Ries C.The generation of true orthophoto using a3D building model in conjunction with a conventional DTM ［J］.International Journal of Photogrammetry and Remote Sensing，1998，32（4）：16.

［2］ Skarlatos D.Orthophoto production in urban areas［J］.Photogrammetric Record，1999，16（94）：643.

［3］ Rau J Y，Chen N，Chen L.True orthophoto generation of built-up areas using multi-view photos［J］.Photogrammetric Engineering and Remote Sensing，2002，68（6）：581.

［4］ Bang K，Habib A F，Kim K，et al.Comprehensive analysis of alternative methodologies for true ortho-photo generation from high resolution satellite and aerial imagery［C］／／The 5th International Symposium on Mobile Mapping Technology MMT’07.Padua：International Society for Photogrammetry and Remote Sensing，2007：1-5.

［5］ 鐘成，黃先鋒，李德仁，等.真正射影像生成的多邊形反演成像遮蔽檢測(cè)算法［J］.測(cè)繪學(xué)報(bào)，2010，39（1）：59.

ZHONG Cheng，HUANG Xianfeng，LI Deren，et al.Polygon based inversion imaging for occlusion detection in true orthophoto generation［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：59.

［6］ Braun J.Aspects on true orthophoto production［C］／／Proceedings of 49th Photogrammetric Week.Heidelberg：［s.n.］，2003：205-214.

［7］ Sheng Y W.Minimising algorithm-induced artefaccts in orthophoto generation：a direct method implemented in the vector domain［J］.The Photogrammetric Record，2007，22（118）：151.

［8］ Rau J Y，Chen N Y，Chen L C.Hidden compensation and shadow enhancement for true orthophoto generation［C／CD］∥Proceedings the of 21st Asian Conference on Remote Sensing.Taipei：［s.n.］，2000.

［9］ Sheng Y W，Gong P，Biging G.True orthoimage production for forested areas from large scale arial photograph［J］.Photogrammetric Engineering and Remote Sensing，2003，69（3）：259.

［10］ Zhong C，Li H，Li Z，et al.A vector-based backward projection method for robust detection of occlusions when generating true ortho photos［J］.GIScience and Remote Sensing，2010，47（3）：412.

［11］ Habib A F，Kim E，Kim C.New methodologies for true orthophoto generation［J］.Photogrammetric Engineering and Remote Sensing，2007，73（1）：699.