郝竹明 黃 惠

（中國科學院深圳先進技術研究院 深圳 518055）

基于自適應幾何分析的高效交互式導航

郝竹明 黃 惠

（中國科學院深圳先進技術研究院 深圳 518055）

三維場景的虛擬導航需要同時保證相機視角的光滑性和智能性，在算法設計上極具挑戰(zhàn)。文章研發(fā)了一套實時自動生成光滑連續(xù)且高效的相機路徑導航系統(tǒng)。首先通過線下模型幾何分析和語義分析，包含分析場景中建筑物模型、道路模型以及非建筑的重要模型等，求得模型重要性值；其次是自適應地獲取路線采樣點以及高效存儲采樣點的視角圖片；最后是利用動態(tài)規(guī)劃的方式求出每個采樣點的最佳視角并光滑地連接這些采樣點形成相機運行軌跡。4個不同三維場景的實驗結果表明了所提算法的高效性和智能性，同時文章所進行的用戶調查也充分反映了所提方法具有的明顯優(yōu)勢。

導航；幾何分析；重要性值；自適應

1 引 言

三維虛擬場景漫游和相機控制在最近十年內得到廣泛的研究［1-4］。各種各樣的導航平臺相繼產生，如谷歌地球，smart3D 瀏覽工具等。這些平臺提供了通過衛(wèi)星、航拍、手工等方式生成的大量三維模型，同時集成了簡單的虛擬漫游方式。這些漫游方式大多數是基于勻速、固定俯仰角的方式，且每天都還在產出大量的三維場景模型，這使得研究三維場景的虛擬導航成為可能，也極其緊迫。

通常一個虛擬的三維場景包含了以下幾個部分：三維建筑物模型、雕塑等非建筑物模型、道路模型以及高速路地形模型。如果對這些模型不做任何分析，而是簡單地讓相機沿路勻速運行，將會導致虛擬漫游既耗時又低效。Grabler 等［5］在研究地圖導航的工作中就提出了一套很有用的三維場景中模型的分析方法，包括分析了建筑物和路型等信息。在 Polonsky 等［6］的工作中，對場景分析所用的描述子包含了諸如建筑物表面可見性、目標顯著性、曲率、外表輪廓和拓撲復雜度等。

現存許多方法是關于視點選擇的，其中基于信息論理論的有 Vazquez 等［7］提出的作為度量具體視角下的信息量的視點熵概念。這種方法主要是利用了球體方向下建筑物投影面積比例：當投影面積平均分布時，熵最大。除了考慮視點下的幾何特征外，部分研究［8，9］還考慮了語義特征，如建筑物風格、結構類型或建筑位置，從而更好地改進了計算最佳視點的方式。

本文關于建筑物分析和視點選擇有借鑒前人研究的思路，但又有所不同：文中考慮到了一些具體描述子，比如獨特性，而不是單獨的單棟建筑的特性分析；重要性值的加權權重通過學習獲得，不是簡單經驗觀察。

相機控制一直是一個很具挑戰(zhàn)性的問題：需要解決視點計算、路徑規(guī)劃以及用戶交互等任務。Christie 等［10］曾對有關虛擬世界的導航方法和動機進行調查研究。Drucker 等［11］是第一次提出關于虛擬三維博物館場景自動漫游方法的人，他們使用了路徑規(guī)劃和圖的搜索方法。其他一些方法［12］，如基于運動規(guī)劃也被大量研究。此外，還有很多基于幾何角度的相機研究方法，如碰撞避免［13，14］、目標可見性［15］、光滑性［16］等。但以上這些方法大都是僅關注了相機軌跡的生成，而忽略了相機運行速度的計算，而速度本身也是導航中一個很重要的問題。因此，本文考慮了關于速度的一個解決方案。

在許多三維場景漫游的應用中，如游戲尋路等，需要大量用戶交互，但同時又需要自動導航的部分，這樣一個交互的需求給相機控制提出了極大的挑戰(zhàn)。怎樣在用戶新設定的相機姿態(tài)下繼續(xù)自動導航，目前幾乎很少研究涉及這個問題的解決。

綜上所述，本文提出了一種基于幾何分析的理想的高效交互式三維導航方法，希望能夠做到實時自動生成光滑連續(xù)且高效的相機導航路徑。為此，需要做到以下幾點：一是如第 2 節(jié)所述的一種三維場景幾何特征的分析方法，能夠有效地分析出哪些場景模型是關鍵的，哪些相對沒那么關鍵；二是怎樣高效利用這些分析結果進行實時運算，得出當前采樣點的最佳視點，即第 3 節(jié)提出的一種基于全景圖的采樣存儲和分析方式；最后一點即第4節(jié)所描述的利用得到的最佳視點進行動態(tài)規(guī)劃的最優(yōu)求解得出光滑連續(xù)的相機路徑。

文章最后在四種三維虛擬場景上證明了所提解決方法的有效性。同樣也把該方案應用到了谷歌地球、智能三維瀏覽工具來生成真實衛(wèi)星或航拍的三維場景下的導航。

2 場景幾何特征分析

本研究開發(fā)了一個自動化的系統(tǒng)來評估場景的幾何特征重要性。所提導航系統(tǒng)的輸入包含了城市場景中的三維幾何模型（模型的經緯度坐標）、道路的幾何模型和路型信息（如圖1 所示）。其中，路型信息包括普通街道、主干道、干線、匝道或者高速路。另外，交通圖將道路分成四個交通層次；地形平面圖將場景分成水路、公園和地面。對于關鍵的地標建筑或者標識性非建筑模型（雕塑、橋梁等）需要建立一定規(guī)模的數據庫，這些數據可根據模型經緯度以及名字從網絡獲取。

分別對以上信息進行分析，最后將分析結果渲染成 RGB 圖。其中，暖色調代表重要的信息；冷色調代表不重要信息。

2.1 建筑物特征分析

本文基于 Appleyard［17］提出的一個調查結果來決定分析建筑的哪些特征，這個調查主要是咨詢了調查者記住了沿路的哪些建筑。

2.1.1 幾何特征

在某一塊區(qū)域內，如果建筑物有一些區(qū)分性很強的特征（如顏色、形狀等），被調查者將會很容易記住。本文主要分析了四種最顯著的幾何特征：高度、不規(guī)則性、二面角、獨特性。以下將分別介紹這四種特性以及如何將其關聯。

（1）高度

一些比較高的建筑從遠處看會更加顯眼，像摩天大廈這樣的建筑往往都是一個城市的地標。

因此使用了建筑物高度作為一個幾何特征。越高的建筑得到的分值越大。我們在給定的鄰域內（本文統(tǒng)一采用 150 m 作為鄰域半徑），通過歸一化的方式求得該項的值。

其中，Ω 是給定鄰域內建筑物集合；h（b）指建筑物b 的高度；Sh（b）指建筑物 b 在高度一項的得分。

（2）不規(guī)則性

許多建筑物都有一個簡單的、規(guī)則的矩形形狀。一棟建筑物的形狀和規(guī)則的標準形狀相離越遠，這個建筑物就越顯著。使用了這樣一個幾何特性做為度量之一，度量了建筑物的包圍盒體積和真實建筑物的體積［18］的比例，公式如下：

其中，V（b）指建筑物 b 的體積；BB（b）指建筑物的包圍盒；Sr（b）指建筑物 b 在不規(guī)則性一項的得分。

（3）二面角

二面角一直是一個很好的表征建筑物結構復雜度的特征。如圖2 所示，同樣是接近標準包圍盒的建筑物結構，高度雖然也相似，但是由于左圖的二面角和更大，該建筑顯然更容易被用戶所記住。

這一項度量了根據二面角所在邊的邊長作為權重的加權二面角和。

圖1 系統(tǒng)的輸入數據Fig. 1 The input data of the system

圖2 二面角圖示Fig. 2 The diagrams of dihedral angle

其中，len（i）指第 i 個二面角所對應的邊長；dihedral（i）指第 i 個二面角的角度；Sa（b）指建筑物 b 在二面角屬性一項的得分。

（4）獨特性

如果一個建筑物和周邊的相鄰建筑物有很大的區(qū)別，將會很顯而易見地成為漫游中的一個標志性建筑。為了計算這樣一個特征，使用如下一個打分項：

其中，x 是指前面三項的值；med（x）是指中值。中值所采用的鄰域和以上幾項類似。

最終建筑物幾何特征得分通過線性加權求和得到：

為了得到這些權重，隨機抽取了場景中一些地標建筑，并在網上（主要來源主流網站，如雅虎、大眾點評等）取得這些建筑的介紹以及一些評分，最終通過上述權重加權來擬合這些評分，從而得到理想的權重值。

2.1.2 位置結構特征

一些認知心理學的研究表明，游覽者更加容易關注到道路交叉口的建筑物或者城鎮(zhèn)廣場周邊的建筑［19］。這樣的空間位置使得這些建筑在導航中起到非常關鍵的作用，因此本文將其作為一項重要度量。

（1）交叉路口的結構

越是重要交叉路口的建筑越比其他建筑顯著。因此，需給所有道路的每一個交叉路口打一個分：打分機制更傾向于給分支越多的交叉路口越高的得分；最終使用一個高斯加權因子，基于路口到建筑的距離來給建筑物一個得分；對于每一棟建筑累加周邊所有交叉路口對其的得分。

道路通常被分為一些離散的類型集合。在本文中，總共分為五類，主要是普通街道、主要街道、干道、匝道和高速路。這些分類可以根據經緯度從谷歌地球的 API 獲取到。根據經驗估計，給予對應項的權重分布分別為 0.25， 0.5， 0.75， 0.8，1.0。這樣也就給了交叉路口一個得分評估。

（2） 廣場結構

為了標識建筑物是坐落在廣場周邊，首先從地形圖上提取出廣場和計算出廣場的重要性值。這樣一個重要性值使用一種類似于交叉路口處理的方式轉化成建筑物的得分。

作為一個廣場區(qū)域，正常從地圖上截取是沒有一個很明顯或精確的邊界。所以我們根據建筑物密度谷值為中心，采用均值移動算法，不斷調整密度最低點，即廣場中心點。從而給在這個廣場周邊的建筑一個得分，見圖3 所示的移動過程。

圖3 廣場中心點移動示意圖Fig. 3 Illustration of square center movement

2.2 非建筑物模型數據驅動分析

場景中一些非建筑物模型，包括了雕塑、重要路標、橋梁等模型，主要采用數據驅動的處理方式，即提前將重要小件離線標定出來，加入數據庫。以這些小件的坐標和名稱在網絡上搜索其相關屬性，然后將這些屬性按特定結構存儲起來。所保存的屬性主要包含主流旅行網站給予這個模型的打分，以及這個模型坐落的區(qū)域、地址、所屬類型、用戶所傾向的得分。而大多數非建筑物模型是沒有網絡數據的，此時一律打分為1 分。

圖4 所示為非建筑物模型存儲結構和數據源。得到這樣一份存儲結構后，根據其所屬區(qū)域的建筑物得分，來給出新的關于坐落區(qū)域的打分。

其中，Ω指所有非建筑物模型集合；bldaffect（m）指建筑物對非建筑物模型的影響得分，建筑物的影響權重，是用建筑物的得分高斯加權作為模型的影響得分。

圖4非建筑物模型存儲結構和數據源Fig.4Storage structure and data source for non-building models

3 視點的重要性值計算和存儲

計算出每個單獨模型的重要性得分（圖5），作為建筑物加權得分。然后把場景紋理模型根據重要程度渲染成對應的顏色模型。其中，暖色調代表重要的模型，冷色調則代表不重要的模型，如圖6 所示，也即得到了如下的一個模型變換。

圖5 建筑物幾何特征評估得分Fig. 5 The building geometrical characteristics assessment score

圖6 紋理模型到顏色模型的映射Fig. 6 Mapping between texture model and the color models

下面的工作將分為：給定起始點和終點之后，進行自適應采樣路徑點；對于每個路徑點，計算各個高度的場景重要性值；離線保存這些場景，以保證能夠實時響應用戶的交互。

3.1 自適應采樣

由于大多數三維場景組成包含了范圍較小的城市區(qū)域以及范圍較大的高速路區(qū)域。如果完全均勻對這些點采樣，過于稠密將會影響計算效率，而過于稀疏將會影響城市區(qū)域的計算精確度，所以需要一個自適應的采樣方式。同時在每個采樣點，由于要覆蓋相機的 6 個自由度，高度上采用了非線性采樣，而由于角度范圍是固定的，且視場角有一個固定覆蓋值，所以朝向和俯仰角采用了均勻采樣。相機翻滾角這個自由度則默認不變。

3.1.1 路徑點的自適應采樣

如圖7 所示，紅色點即為自適應的采樣點，此處自適應采樣主要考慮某個點附近建筑物的密集程度以及路型的復雜度這兩個特征。

圖7 路徑點的自適應采樣Fig. 7 Adaptively sampling path points

初始階段先均勻密集采樣整個路線，對第一次的均勻采樣點，可以輕易計算出給定范圍內建筑物的密集度，同時根據第 2 節(jié)對于不同路型會有不同的得分，從而得出每個均勻采樣點的價值：

其中，d（wp）指的是采樣的建筑物密度值；r（wp）指的是路型的加權值；wd和 wr分別為對應權重，文中對應采用 0.7 和 0.3 這兩個系數。

其中，Ω 指該采樣點 150 m 范圍內的建筑物集合；b 為單個建筑物的位置坐標；p 為采樣點的位置坐標。

在計算出每個均勻采樣點的價值后，開始自適應地調整新的采樣間隔，保證價值越大的點所在的區(qū)域采樣越密集。先累計求出所有采樣點的價值總和（設為 V）。將 V 值等分：假設要采樣1000 個點，那么從起始點開始累加均勻采樣點的價值，累加到 V/1000 的時候，保留該點；如果超過 V/1000，最后一段根據 V 值的差值按比例截取，獲得一個新的點。所以算法所提的自適應采樣的本質是根據重要性值的均勻采樣。

3.1.2 非線性的高度采樣

由于在三維場景中還有高度這個維度，而高度的范圍是無限的，但是根據現有研究表明，高于 1000 m 的高度在虛擬漫游中已經沒有太大意義。因此高度取值范圍為 10～1000 m。

圖8 所示為在高度方向采用了非線性的采樣方式，具體計算如下：

其中，a 滿足 ，即可求得 a=2.84。求得a 之后可以很方便地求出對應的 5 個采樣高度。

圖8 非線性高度采樣Fig.8 Nonlinear sampled elevation

3.1.3 朝向和俯仰角的均勻采樣

相機除了 x、y、z 三個位置坐標的自由度外，還有圍繞這三條軸旋轉所產生的三個自由度。在本解決方案中側滾角保持不變，因為如果側滾角產生變化，會導致相機過于靈活，從而使用戶產生眩暈感；偏航角的范圍是－180°～180°，而俯仰角的范圍是－90°～90°。相機的視場角在水平和豎直方向設定有一個固定比例，本文采用的是 60∶36。由于在水平方向的視場角是 60°，故在水平方向分成 6 等分；同理，豎直方向分成 5 等分，結果如圖9 所示。

圖9 相機俯仰角角度的采樣Fig. 9 Pitching angle sample for camera

觀察到在海拔最高和最低的位置，仰視和俯視是沒有任何意義的；同樣在次高和次低的位置，完全的仰視（即仰視角度很大）和完全的俯視（即俯視角度很大）也是沒有意義的，所以此處需要根據采樣高度去掉一些方向。

3.2 全景圖存儲

整個自動的采樣過程如上兩節(jié)所述，由于需要滿足后續(xù)更靈活的用戶交互需求，需要動態(tài)獲得某些視角的重要性值，此時為了響應用戶的交互操作，需要提前采樣出更多的視角。如果對于插值采樣的視角也完全按照之前上一小節(jié)的精細處理方案，將導致存儲量過于龐大，線下運算過于耗時。

本文采用全景盒的方式來存儲視場圖片，以視場角為 90°定點采樣六張圖，分別為朝前、朝后、朝左、朝右、朝上和朝下。從而利用這六張圖片來構成全景圖，保證后續(xù)動態(tài)獲得重要性值，而不需要再次花費大量時間來渲染出新視角下的圖片求解。這樣就可以達到用戶要求的實時性需求，因為本算法線下預處理最耗時的部分就是視角采樣渲染，幾乎占據了 90% 的時間消耗。圖10 所示為本文保存的全景立方盒圖片。

圖10 全景立方盒圖Fig. 10 Panoramic cube image

3.3 重要性值計算

對于 3.1 中采樣得到的圖片，將通過累加其像素值來求得該視角下的重要性值。至此，整條路線上每個采樣點都有一系列的重要性值。在累加的過程中考慮到圖像的一些顯著性特性，比如中心位置、圖像分布均勻性等，添加了一些額外的權重。而對于存儲的全景圖，需要二次截取其對于視場角 60°的位置，來累計像素求和。

4 相機軌跡優(yōu)化求解

至此已經可以得到一系列采樣點，同時得到了采樣點對應的一系列視角下的重要性值。此時只需要以這些視角作為求解的離散值，然后在采樣點間線性插值，即可得到最終的連續(xù)相機軌跡。

4.1 動態(tài)規(guī)劃的軌跡優(yōu)化方程

由上一小節(jié)，得到如下一個矩陣 M：

該矩陣的行代表了某個采樣點的（3+4+5+4 +3）×6 個采樣視角，6 指在朝向上的 6 個均勻采樣的方向；括號中數值代表不同高度在俯仰角上的采樣數量，見圖9；而列代表了各個采樣點。

首先需要保證整個軌跡在每個采樣點上都盡量經過重要性值最高的視角，其次要保證整個相機的視角變化是連續(xù)的。要保證視角變化光滑亦即保證如果從第 i 個點的第 j 個視角跳到第 i+1個點的第 k 個視角，如果 k 離 j 越遠會得到越大的懲罰。

為保證相機從一個舒適的角度開始運動，動態(tài)規(guī)劃的起始狀態(tài)設置為 10 m 高度朝正前方的姿態(tài)。也就是 。

動態(tài)規(guī)劃的狀態(tài)轉換方程為：

其中，a 是指高度和朝向不變，俯仰角變化時采樣的間隔數；b 是指角度不變，高度變化時的采樣間隔數；p1和 p2是對朝向和俯仰角變化的懲罰因子；p3是對高度變化的懲罰因子。結果分析發(fā)現，懲罰因子的變化會極大地影響整個相機的軌跡自由度，見圖11。利用上式可以求解出一系列對應采樣點的相機參數以及對應參數下的重要性值。為了保證較好的漫游體驗，對這些參數再次做拉普拉斯光滑，進一步保證了相機軌跡的光滑性。

4.2 動態(tài)速度的線性求解

當求出最優(yōu)化的軌跡之后，也即可以得到每個采樣點上所取的視角興趣值。高效導航的目標是保證相機能夠在興趣值高的地方運動更長時間，在興趣值低的地方運行很少的時間。

設定需要求解的 ti即相機從采樣點 pi運行到采樣點的時間。求解如下的優(yōu)化方程：

其中，T 是用戶指定的漫游導航的總時長；Vi指對應采樣點的重要性值；Si是指 pi到的路線長度。

圖11 懲罰因子的變化導致的完全不同的相機軌跡Fig. 11 Different camera trajectory caused by the change of penalty factors

5 結 果

5.1 分析和對比

為了評估本文所提工作的有效性，做了三組對比，分別比較了幾何得分、視角效果、運行時間在虛擬導航中最影響用戶體驗的方面。

圖12 比較了本文的幾何分析得分結果和基于信息熵［7］的重要性得分結果。其中，左右兩張圖為以兩個相似的視角截取的導航場景：右圖的建筑物地標性更強；左圖只是三維場景中一個小城鎮(zhèn)的普通建筑群，且這些建筑沒有任何區(qū)分性。因而本方案在左圖的得分明顯低于右圖。但是信息熵的方法給了兩個視角基本差不多的得分。主要是因為信息熵的方法只考慮了相對投影面積，而本文的方法還考慮了一些額外的屬性，比如獨特性。

圖12 視角重要性值打分對比（V 是本文重要性值得分，E是信息熵得分）Fig. 12 Importance value comparison（V is our score， E is entropy based score）

在視角效果這一塊，主要是和谷歌地球［20］內嵌的導航系統(tǒng)進行了對比。很容易發(fā)現由于谷歌的內嵌導航需要用戶提前設定好相機自由度，然后整個過程都固定不變，這就使得不太可能設定出一個對全程都很好的視角，見圖13。下圖右側是本文的結果，首先在高速路部分本方案有一個很好的鳥瞰視角，幫助用戶把握整體信息；同時在城區(qū)，能夠以地面行車的模式運行，用戶可以看到更多細節(jié)。而谷歌由于是固定視角，兩者都不能很好地兼顧。

圖13 本文系統(tǒng)和谷歌導航的對比Fig. 13 Comparion with google default navigation

最后和勻速導航對比了在時間分布上的差異?，F在大多數導航平臺都是基于勻速的簡單導航方式，如谷歌地球［20］、smart3D 的瀏覽平臺［21］、上海龍引擎公司的瀏覽平臺［22］，而本文的目標之一是希望在重要位置導航時間更長，不重要位置時間短一些。這樣保證了導航了高效性，用戶不至于失去興趣，又能獲得關鍵信息，見圖14。

本文在大量的三維虛擬場景和谷歌等真實掃描數據平臺上執(zhí)行了如前所述的算法。在試驗中發(fā)現離線最耗時的部分主要是視點采樣，即渲染某個采樣視角下的圖片最耗時。

圖14 時間分布Fig. 14 Time variation

圖15 導航效果截圖Fig. 15 Navigation effect screenshots

圖15 展示了導航中一些代表性的截圖。包含了虛擬平臺和谷歌地球的平臺，截取了其高速路段和城區(qū)部分的一些導航圖。對應截圖四個場景的數據見表1。由表中數據可以發(fā)現，大量的時間消耗都是發(fā)生在采集視角圖片的過程。如果完全高密度均勻采樣，時間代價還會提高一個級數。

因而本文工作的主要貢獻點：（1）提出了一套合理完善的三維場景的模型分析方案，兼顧考慮了包括建筑物、非建筑物以及道路模型；（2）使用了自適應的獲取采樣點方法，同時提出了使用全景圖存儲渲染結果的方案；（3）解決了如何基于分析結果，實現最佳視點下光滑連續(xù)導航的動態(tài)規(guī)劃求解方案。

5.2 用戶調查

為了評估算法的有效性，我們做了用戶調研，并和一些當前可選方案做了對比，分別是：（1）勻速導航［22］；（2）非連續(xù)的重點位置導航：在關鍵位置勻速，其他部分直接跳過；（3）Chen 等［23］提出的導航方式；（4）谷歌內置導航方式［20］。

為了生成非連續(xù)的重點位置導航，手動選擇了沿路最關鍵的路段。在選出來的每一段，以勻速、固定俯仰角運行，跳過沒有選出來的不重要路段，保證有足夠時間運行在關鍵部分。

有 58 位參與者參加了本次調研。這些參與者事先并不清楚本次調查實驗的目的，也不知道我們的工作；所有參與者視力正常或者糾正后是正常的；用戶事先都同意本次調查且本次調查遵循赫爾辛基聲明。在調查過程中，每一位參與者被展示了8 對視頻；每一對包含了本工作的結果和上述的一種方案的結果；8 對的出現順序以及左右位置都是隨機的；整個實驗時長大概在 30分鐘，參與者可以重復觀看視頻，然后需要回答如下問題：

問 1：哪一個視頻更好地概括了整個線路？

問 2：哪一個視頻看起來更舒服？

問 3：哪一個視頻提供了最多的信息？

對每一種情況，樣本數量是 116（58 位參與者，2 次重復），調查結果見圖16。結果顯示，本文設計系統(tǒng)具有明顯的優(yōu)勢。

6 總結與展望

在本工作中我們解決了關于交互式高效導航的問題，保證了軌跡既能兼顧整個場景的重要性值，又能光滑連續(xù)。分別分析了場景的建筑、路型和一些關鍵的非建筑物的模型，提出一套完整的分析方案。對于場景的路徑采樣，本文提出了智能化自適應的采樣方案，包括采樣相機的坐標和朝向共 6 個自由度。最后使用了動態(tài)規(guī)劃的方案求解出了光滑連續(xù)的相機路徑。

表1 測試場景數據分析Table 1 Statistics for test scene

圖16 對應三個問題的用戶調研結果Fig. 16 User study for three questions

當前的解決方案也有一些限制，首先是在高度變化上不能太大，因為該方案不允許高密度、無限制的在海拔這個維度采樣。一個可能的解決方法是由用戶指定高度需求，然后在該范圍內高密度采樣。其次是該方法主要是針對距離不是很長的導航，因為要離線采樣存儲，這就使得不太容易處理太長的路徑，否則會需要存儲非常大量的數據。而在一個更長的路線上導航會是一個很有趣的問題。

［1］ Mühler K，Neugebauer M，Tietjen C，et al. Viewpoint selection for intervention planning ［C］ // Proceedings of IEEE/ Eurographics Symposium on Visualization， 2007： 267-274.

［2］ Ji GF，Shen HW.Dynamic view selection for time-varying volumes ［J］. IEEE Transactions on Visualization and Computer Graphics， 2006， 12（5）：1109-1116.

［3］ Klomann M，Milde JT.Semi autonomous camera control in dynamic virtual environments［M］ // Virtual and Mixed Reality-Systems and Applications. Springer Berlin Heidelberg， 2011：362-369.

［4］ Serin E，Adali S，Balcisoy S. Entropy assisted automated terrain navigation using traveling salesman problem ［C］ // Proceedings of the 10th International Conference on Virtual Reality Continuum and Its Applications in Industry， 2011：41-48.

［5］ Grabler F，Agrawala M， Sumner RW， et al. Automatic generation of tourist maps ［J］.ACM Transactions on Graphics， 2008， 27（3）： 100.

［6］ Polonsky O，Patané G，Biasotti S， et al. What's in an image？ ［J］. The Visual Computer， 2005， 21（8-10）：840-847.

［7］ Vázquez P， Feixas M， Sbert M， et al. Viewpoint selection using viewpoint entropy ［C］ // Proceedings of Conference on Vision Modeling and Visualization，2001：273-280.

［8］ Sokolov D，Plemenos D. Virtual world explorations by using topological and semantic knowledge ［J］. The Visual Computer，2008， 24（3）： 173-185.

［9］ Yiakoumettis C，Doulamis N，Miaoulis G，et al. Active learning of user's perferences estimation towards a personalized 3D navigation of georeferencend scenes ［J］. GeoInformatica， 2014，18（1）： 27-62.

［10］ Christie M，Olivier P， Normand JM. Camera control in computer graphics ［J］. Computer Graphics Forum， 2008， 27（8）： 2197-2218.

［11］ Drucker SM，Zeltzer D.Intelligent camera control in a virtual environment ［C］// Graphics Interface.Canadian Information Processing Society， 1994：190-190.

［12］ Nieuwenhuisen D，Overmars MH.Motion planning for camera movements ［C］ // Proceedings of IEEE International Conference on Robotics and Automation， 2004： 3870-3876.

［13］ Li TY，Lien JM， Chiu SY，et al. Automatically generating virtual guided tours ［C］ // Proceedings of Computer Animation， 1999： 99-106.

［14］ Salomon B，Graber M，Lin MC，et al.Interactive navigation in complex environment using path planning ［C］ // Proceedings of the 2003 Symposium on Interactive 3D Graphics， 2003： 41-50.

［15］ Oskam T，Sumner RW，Thuerey N，et al.Visibility transition planning for dynamic camera control［C］ // Proceedings of the 2009 ACM SIGGRAPH/ Eurographics Symposium on Computer Animation，2009： 55-65.

［16］ Hsu WH，Zhang YB，Ma KL. A multi-criteria approach to camera motion design for volume data animation ［J］. IEEE Transactions on Visualization and Computer Graphics，2013，19（12）： 2792-2801.

［17］ Appleyard D.Why buildings are known： a predictive tool for architects and planners ［J］.Environment and Behaviour， 1969， 1（2）： 131-156.

［18］ Mirtich B. Fast and accurate computation of polyhedral mass properties ［J］. Journal of Graphics Tools，1996，1（2）：31-50.

［19］ Michon P，Denis M. When and why are visual landmarks used in giving directions？ ［M］ // Spatial information theory. Springer Berlin Heidelberg，2001： 292-305.

［20］ Google.Google 地球. ［2015-06-17］. http：//www. google.cn/intl/zh-CN/earth/.

［21］ Acute3D.Smart3D 瀏覽平臺. ［2015-06-17］. http：//www.acute3d.com/.

［22］ 上海龍引擎網絡有限公司. 龍引擎三維虛擬現實平臺. ［2015-06-17］. http：//www.dragonengine.cn/ .

［23］ Chen B，Neubert B，Ofek E，et al. Integrated videos and maps for driving directions ［C］ // Proceedings of the 22nd annual ACM Symposium on User Interface Science and Technology，2009：223-232.

Efficient Interactive Navigation Based on Adaptive Geometry Analysis

HAO Zhuming HUANG Hui

（ Shenzhen Institutes of Advanced Technology， Chinese Academy of Sciences， Shenzhen 518055， China ）

Virtual navigation in 3D scenes requires both smooth and intelligent camera control， which is a very challenging task. In this paper， a real time navigation system that could automatically generate an effective and smooth camera flyby trajectory was presented. Firstly， offline geometric and semantic features of models were analyzed in the given 3D scene， including buildings， roads and other visible parts， to evaluate the importance of models. Secondly， the path from origin to destination was sampled adaptively， and visual images from different views on each sampled point were stored effectively. Finally， the best view on each sampled point was extracted and connected smoothly to get the camera flyby trajectory. The experiments done in four different 3D scenes clearly demonstrate the efficiency and intelligence of the proposed algorithm， and the user investigation also verifies its superiority over the existing methods.

navigation； geometry analysis； importance value； adaptively

TP 391

A

2015-06-13

2015-09-11

國家自然科學基金項目（61379091）；科技部863 項目（2015AA016401）；廣東省科技廳項目（2014B050502009）；深圳市科技創(chuàng)新委項目（CXB201104220029A，JCYJ20140901003938994，CXZZ20130322162845315）

郝竹明，碩士研究生，研究方向為計算機圖形學；黃惠（通訊作者），研究員，博士研究生導師，研究方向為計算機圖形學，E-mail：hhzhiyan@gmail.com。