基于 A*算法與自適應分片的大規(guī)模最優(yōu)路徑規(guī)劃

郭耕辰 馮良炳 鄧 亮 趙永剛 劉 宇

(中國科學院深圳先進技術研究院 深圳 518055)

基于 A*算法與自適應分片的大規(guī)模最優(yōu)路徑規(guī)劃

郭耕辰 馮良炳 鄧 亮 趙永剛 劉 宇

(中國科學院深圳先進技術研究院 深圳 518055)

路徑規(guī)劃引擎是在線地圖系統(tǒng)中一個至關重要的部分，靜態(tài)路徑規(guī)劃算法是重中之重。現(xiàn)有的對 A* 算法的改進主要是通過預處理算法，對路網(wǎng)數(shù)據(jù)進行靜態(tài)分層預處理，其效率過低。文章提出了一種自適應分層的思想，同時對 A* 算法的啟發(fā)式函數(shù)進行改進，引入了方向引導函數(shù)，使得 A* 算法在日常路網(wǎng)上的可用性有了較大的提高。實際的路網(wǎng)實驗表明，提出的算法的搜索效率、效果均優(yōu)于同類算法，與標準層次 A* 算法相比，文章算法的搜索空間降低為原來的 42%，搜索時間僅為原來的13%。

路徑規(guī)劃；A* 算法；自適應分層；方向啟發(fā)式函數(shù)

1 引 言

對于一個在線地圖系統(tǒng)來說，路徑規(guī)劃引擎是其中一個重要的組成部分。路徑規(guī)劃問題，簡而言之就是以路網(wǎng)拓撲結構為基礎，在其形成的有向圖中找到一個最短路徑的問題。在現(xiàn)實環(huán)境中，往往指的是從出發(fā)點到目標點總代價最小的路徑過程。這個代價依據(jù)相應的需求來制定，如道路的物理長度、道路的類別和車速限制等。

A* 算法在進行大規(guī)模搜索的時候，耗時急速增加，因此，在應用到實際的系統(tǒng)中時，需要對其進行優(yōu)化。優(yōu)化可以在如下幾個方面進行：縮小搜索空間、雙向搜索和層次化搜索。錢紅昇等[1]提出了一種在分層基礎上對啟發(fā)式函數(shù)的改進，在前期搜索過程中，由于運算速度的要求較高，可以通過增大權值來加大啟發(fā)式函數(shù)的作用。在后期過程中，路徑搜索主要以精度為重，可以減小啟發(fā)式函數(shù)的權重以提高搜索精度，同時，設置了權值的上下限閾值，以保證不會因為前期搜索太快而損失搜索精度，后期因為搜索太細而損失了搜索速度。這種改進的 A* 算法綜合考慮了路徑搜索效率和搜索精度的雙重要求，在保證搜索精度的同時提高了搜索效率。實驗結果表明其總的搜索節(jié)點數(shù)明顯小于經(jīng)典 A* 算法，效率有了較大的提升。在實際工程基礎上，往往使用雙向搜索[2]來加快尋路的速度。雙向搜索是指從起點和終點同時運行路徑規(guī)劃算法，當發(fā)現(xiàn)有候選點滿足終止條件后，終止算法。殷[3]和Bauer 等[6]提出了路徑搜索過程中，起點和終點所在方位對縮小搜索空間的重要性，通過設置優(yōu)先區(qū)域，在優(yōu)先區(qū)域內(nèi)搜索，減少了無意義的運算。但其設計的啟發(fā)式函數(shù)時間復雜度比較高。Holzer 等[4]則提出了工程化的分層思想用于優(yōu)化路網(wǎng)圖，但無法自動適應不同路網(wǎng)的結構，無法動態(tài)的對層次進行改變。很多優(yōu)化的思想在算法之間是可以通用的，Delling 等[5]提出了很多工程化的優(yōu)化方式，穆[7]從數(shù)據(jù)結構層面上，引入了Cheap 表來改進 open 表的操作效率，用時間換取空間，但這兩者之間的平衡很難把握。

本文將在現(xiàn)有 A* 算法的改進基礎上，提出一種針對方向加強的啟發(fā)式函數(shù)，待搜索路徑偏離起點和終點向量越遠，導致代價越高，因此算法會盡量選出與出發(fā)點到目的地方向相符度高的候選點，極大地縮小了搜索空間。同時提出一種自適應的分層方式，使得算法對路網(wǎng)的動態(tài)適應成為可能，從而達到對現(xiàn)有路徑規(guī)劃方法的優(yōu)化。

2 算法描述及實現(xiàn)

2.1 A* 算法

A* 算法[8]是人工智能中的一種啟發(fā)式算法，它通過定義代價函數(shù)評估代價大小來確定最優(yōu)路徑。代價函數(shù)為：

其中，n 表示待拓展的節(jié)點；g(n)表示從起點沿著已生成的路徑到一個給定節(jié)點的移動開銷，這個值由我們根據(jù)路網(wǎng)選定的度量來決定，一般情況下，取道路的物理長度；h(n)表示從給定節(jié)點到目的節(jié)點的估計移動開銷，這個值是一個啟發(fā)式的預估。

現(xiàn)有的啟發(fā)式函數(shù)最主要是如下幾種：(1)以起點和終點在標準坐標系上的絕對軸距總和的曼哈頓距離；(2)在二維空間中兩點之間的直線段距離的歐氏距離；(3)在二維空間下取起點和終點坐標數(shù)值差的最大值的切比雪夫距離。

以上的三種啟發(fā)式函數(shù)主要應用于平面網(wǎng)格，在城市路網(wǎng)的應用方面，適用性不強，因此本文首先會對啟發(fā)式函數(shù)進行優(yōu)化。

同時，上述的 A* 算法如果直接應用在大規(guī)模路網(wǎng)上將會產(chǎn)生嚴重的計算性能瓶頸?，F(xiàn)有的效率較高的算法[1]往往是對路網(wǎng)進行分層處理，降低路網(wǎng)的復雜性。本文將通過在分層基礎上，加上自適應的劃分過程，進一步提高算法的效率。

2.2 啟發(fā)式函數(shù)

圖 1 方向?qū)驅(qū)嵗鼺ig. 1. Goal-directed example

如圖 1 所示，根據(jù)路網(wǎng)圖的特點，從起點到終點的路徑，其方向上應符合從起點指向終點的向量[6]，也就是每次在路徑選擇上，與 AB 向量夾角越小的邊，其權重就越大。記起點為終點為則該向量與坐標軸 x 軸正方向的夾角為待搜索點的坐標為與坐標軸 x 軸正方向的夾角為則向量 SB 與向量 AB 的夾角為但是，在實際計算中使用這個公式，會導致計算量過大，路徑規(guī)劃過程的大部分運算時間都被用來計算這個啟發(fā)式函數(shù)。因此，為了表示待搜索點與待搜索路徑結果的符合程度，同時還能放大這種差異，本文選用圖 2 中，以點 S 分別向 x 軸正方向和 y 軸正方向做延伸，與三角形的兩條邊相交于兩個點，形成的矩形面積(即 S 點形成的梯形與完全符合AB 方向形成的三角形的面積差)作為啟發(fā)式函數(shù)(公式(1))來引導路徑規(guī)劃過程。

圖 2 啟發(fā)式函數(shù)Fig. 2. Heuristic function

其中 k 表示放大系數(shù)，用來調(diào)校向量的大小，根據(jù)每個系統(tǒng)的實際情況進行取值，用來改變這種方向引導對整個路徑選取過程的影響系數(shù)。

圖 3 使用普通 A* 算法測試各啟發(fā)式函數(shù)的搜索空間Fig. 3. The search space for each heuristic function used common A* algorithm testing

圖 3 為常見 A* 啟發(fā)式函數(shù)，圖中(a)～(d)分別為使用曼哈頓距離、歐氏距離、切比雪夫距離和使用本文的強化方向指向距離的搜索空間的測試結果。

雙向策略[2]同時進行正向搜索和反向搜索兩套搜索，當發(fā)現(xiàn)一個點同時被正向搜索和反向搜索選為路徑點的時候，算法結束。從圖 4 可以看到，使用雙向搜索的時候，搜索空間的優(yōu)化效果更為明顯。

圖 4 使用雙向 A* 算法測試各啟發(fā)式函數(shù)的搜索空間Fig. 4. The search space for each heuristic function used bi-direction A* algorithm testing

2.3 自適應分層

對實際的大規(guī)模路網(wǎng)進行搜索時，如果直接使用上述改進的 A* 算法，時間代價太大。一般都采用對路網(wǎng)圖進行層次劃分方法，層次劃分可以通過動態(tài)和靜態(tài)兩種方式進行。Holzer 等[4]提出的代表性靜態(tài)方式通過對路網(wǎng)劃分為網(wǎng)格，對給定的路網(wǎng)圖賦予相應的網(wǎng)格結構來實現(xiàn)。本文將引入一種動態(tài)的分割方法，可以對整個地圖程序的路徑規(guī)劃引擎提供自適應的分層，以此來減少人工的參與和對各種不同地區(qū)的路網(wǎng)結構進行適配。

路網(wǎng)的分層通過構建一系列的層次圖來實現(xiàn)。一個路網(wǎng) G 的層次圖實質(zhì)上通過以下兩種方式拓展了原有的 G 圖：

(1)通過層次結構中添加的邊拓展了 G 的邊集 E；

(2)V 集中任意兩點 s、t 的最短距離與層次圖 M 中 s 到 t 的距離相等。

為了得到以上的層次圖，我們使用了一種叫做組件樹[4]的特殊數(shù)據(jù)結構來實現(xiàn)。生成層次圖M 的目的在于使每個層次的子圖要比原有的路網(wǎng)圖 G 規(guī)模小。這樣，把 A* 算法應用到這個相對小的圖上，速度會更快一些。

層次圖 M 通過以下輸入來構建：

我們把 Li＝(Ei, Ui, Di)叫做多層圖 M 的第i層。同時我們預先定義 L0＝(E, ?, ?)為第 0 層，其中 E 表示原路網(wǎng)圖 G。加上第 0 層，我們說M(G , S1, …, Sl)是一個 l+1 層的圖。

層次圖的構建是一個迭代的過程，我們總是假設已經(jīng)構建了第 Li—1層。迭代從 i＝1 開始，對于 Si—1中的每個點 u 來說，以 u 為根在圖(Si—1, Ei—1)中構建一個最小路徑樹 Tu。具體判斷一個候選邊(u, v)是否被添加到集合Ei，Ui，Di的條件為：

Li包含了一個邊(u, v)當且僅當沒有 Ti中 u到 v 路徑上的點屬于 Si。

換句話說，如果 u 到 v 路徑上的點除了兩個端點 u 和 v 之外，在 Si中再也找不到其他的點，此時邊(u, v)被添加到 Li中去。新邊(u, v)的權重為 G 中 u 到 v 的最短路徑長度。

值得注意的是，層次 Li在這個構建的過程中不是唯一的，因為最短路徑樹不是唯一的。到此為止，我們可以給出多層圖的定義：

圖 5 是一個三層圖的例子，第 0 層包含了原始的路網(wǎng)圖 G。取 S1＝{a, b, c}，S2＝{a, c}。為了更好的說明問題，我們在第 1 層和第 2 層上畫上了所有點，但實際上，他們是不存在的。第 1層和第 2 層被化成了兩個平面，上面的平面用于表示邊集 Ei，下面的平面用于表示圖 G～Si中的連接組件。Ui和 Di中的邊連接了一個層的不同平面。

圖 6 是與圖 5 對應的組件樹，只有點 s 和 t的葉子節(jié)點被保留。

圖 5 三層圖例子Fig. 5. A three levels example

圖 6 對應的組件樹Fig. 6. A corresponding component tree

由于最短路徑樹不是唯一的，路網(wǎng)的這個預處理過程就涉及到圖的分割問題，如果僅僅使用網(wǎng)格來分割這個圖，不能最大程度地反映出路網(wǎng)的自然屬性。實際上，路網(wǎng)不同部分的性質(zhì)差別很大，人口密集區(qū)域應該分割得更細，而如湖泊等地點的分割粒度要求比較粗，因為沒有人會去試圖尋找從湖泊中央到湖泊邊界的路徑，這也不是路徑規(guī)劃系統(tǒng)的應用范疇，因此，本文提出了自適應分割的概念。

自適應分割，就是在原有的路網(wǎng)網(wǎng)格分割基礎上，對內(nèi)部查詢頻繁的單位格進行進一步自適應劃分，使得查詢頻繁的區(qū)域(即人口密集區(qū)域)的劃分粒度更細致，提高查詢的效率。

首先，按照網(wǎng)格分割的思想，假定要將路網(wǎng)劃分為 n 層，最開始為第 n 層，對整個原路網(wǎng)圖G 以坐標為標準進行 Kn等分；然后第 n—1 層，對第 n 層劃分后的格子進行 Kn—1等分，并將這個過程一直迭代下去，直到第 1 層為止。這個過程被叫做路網(wǎng)的預處理過程，其耗費的時間比較長，但是往往在很長的一段時間里，在路網(wǎng)整體結構變化不大的情況下，不需要多次運行。這個過程與路網(wǎng)代價的選取是相互獨立的。

圖 7 對層次化優(yōu)化原理進行了進一步說明。如果路徑 BC 和路徑 CD 在第 i 層被分到不同的格子里面，這樣在層次結構的表示上，第 i+ 1 層里面，就會保存一個從 B 到 D 的快捷方式(shortcut)，在第 i+1 層的搜索過程中，如果一個人找從 A 到 D 的路徑，就可以得到 A→B→D的結果，然后在下一層對 BD 這個 shortcut 進行展開，其路徑查找次數(shù)就會降低。

圖 7 層次化優(yōu)化的說明Fig. 7. The hierarchical optimization

這便是分層的好處，也是本文要引入自適應分割對層次進行擴充的目的。

如果系統(tǒng)運行過程中，很多用戶去查找一個格子中的起點和終點，則說明在這個格子里，路網(wǎng)節(jié)點的密集程度比較高，也可理解為人口密集程度比較高。因此，如果對這個格子進行進一步的劃分，可以得到一個更好的層次結構，從而提高系統(tǒng)的查詢效率。而且在預處理過程后，網(wǎng)格的結構已經(jīng)基本形成，往往這個自適應的過程并不會對原有的層次結構產(chǎn)生過大的改變。同時這種新的分割與代價的選取是相關的，可以根據(jù)不同的代價，如道路的長度、道路的限速等動態(tài)而靈活改變。

自適應擴充的過程如下：

在整個系統(tǒng)中，為第 1 層(該層是分割粒度最小的一個層)每個格子維護一個計數(shù)器，設定一個閾值 T1，每發(fā)生一次格子內(nèi)的查詢，計數(shù)器 c 加 1，當達到 c＞T 的時候，對該格子進行分割。類似于細胞增殖的過程，當其需要向下一代繁衍的時候，對這個格子的所有結構，包括上下文等信息復制 K1份，新產(chǎn)生的 K1個格子與原格子不同點在于其計數(shù)器置 0，同時，格子的面積是原來的 K1分之一。原格子在第一層被標記為不可用。但這種裂變并不是無止境進行下去的。分層之所以不可以無限劃分，是因為要調(diào)和連通性和劃分粒度之間的矛盾，如果劃分過多的話，會導致附加的存儲信息過多，干擾查找的效率。因此，在系統(tǒng)的實現(xiàn)過程中，若第一層的原格子被標記為不可用之后，其計數(shù)器的值將用來表示其內(nèi)部分裂的次數(shù)，當分裂次數(shù)達到系統(tǒng)設定的閾值 T2的時候，分裂不再發(fā)生。

2.4 算法實現(xiàn)

給定路徑規(guī)劃的起點 S 和終點 D，使用本文的方法求最短路徑的步驟如下：

(1)加載路網(wǎng)數(shù)據(jù)，對路網(wǎng)數(shù)據(jù)進行初始化，本文選用以網(wǎng)格方式對路網(wǎng)進行劃分。

(2)從路網(wǎng)的類金字塔的層次圖中，從高層向底層查找，直到找到第一個使 Si和 Di不在同一個格子的層次 L，如果 L＞0，則直接調(diào)用本文的指向性 A* 算法來計算最短路徑，用 Si和 Di的坐標算出方向向量，使用啟發(fā)式公式(1)作為常規(guī) A* 算法[8]的 h(n)。如果 L＝0，說明可能需要自適應分層，找到 Si和 Di所在的格子，由 2.3 中所述的條件判斷該格子是否可以分割。如果可以分割，產(chǎn)生新格子，再調(diào)用本文的指向性 A* 算法；如果不可以分割，則說明裂變次數(shù)已經(jīng)達到上限，直接調(diào)用本文的指向性 A* 算法得到規(guī)劃結果。

(3)如果(2)中得到的路徑 P1是從層次 0 得到的，則 P＝P1直接跳轉(zhuǎn)到(5)，如果是從其他層次得到的，遍歷路徑結果，找到低層路網(wǎng)到高層路網(wǎng)最近的節(jié)點作為新的起點和終點，分別記為 S' 和 D'，調(diào)用本文的指向性 A* 算法求 S 到 S'的路徑為 P2，D 到 D' 的路徑為 P3。

(4)組合路徑 P＝P1+P2+P3，得到最終的路徑，跳轉(zhuǎn)到(5)。

(5)返回最終結果 P，即為 S 到 D 的最短路徑。

3 仿真實驗與結果分析

從圖 3 的網(wǎng)格實驗結果可以看出，使用歐氏距離作為啟發(fā)式函數(shù)和本文的方向指向函數(shù)得到的路徑結果是最正確的，因為在無障礙的情況下，兩點間線段最短。因此取本文啟發(fā)式函數(shù)與歐氏距離做啟發(fā)式函數(shù)作對比。如表 1 所示，相比之下本文啟發(fā)函數(shù)的時間僅需要 1 ms，比歐氏距離作為啟發(fā)式函數(shù)快一倍，搜索空間也僅為歐氏距離作為啟發(fā)式函數(shù)結果的 53%，效率提升非常明顯。

以上結果的放大系數(shù) K 取值為 1，實驗過程表明，K 越大，算法的貪心性也就越強，如果過強的話，在實際路網(wǎng)中會對結果的正確性造成干擾。例如，一個完全符合起點和終點向量方向的道路，其代價為 α，另一條稍微偏離一點的道路的代價為 β，αβ，K 的值如果設定過大的話，往往會導致最終選取了第一條道路。

因此 K 的選取要結合路網(wǎng)的比例尺、度量的表示單位等數(shù)據(jù)來選取。一般選取 K 為單位代價的坐標偏移值。例如，如果每個格子的代價為1，坐標的偏移也為 1，那么取 K＝1。

圖 4 是雙向路徑規(guī)劃試驗的結果。本文啟發(fā)式函數(shù)的搜索空間也僅為歐氏距離作為啟發(fā)式函數(shù)結果的 69%。

為了驗證此算法在真實路網(wǎng)上的優(yōu)化效果，采用深圳路網(wǎng)圖的一部分作為測試集。分別對經(jīng)典 Dijkstra 算法、經(jīng)典層次 A* 算法、自適應層次A* 算法和指向性自適應層次 A* 算法進行比較。

表 1 網(wǎng)格模擬結果Table 1. Grid simulation results

圖 8 路網(wǎng)實驗結果Fig. 8. The experimental results of road network

我們使用的測試環(huán)境是深圳市路網(wǎng)圖，共有 30256 個節(jié)點和 185202 條路段，運行在 Intel 2.0 GHz 主頻的 CPU 上，內(nèi)存為 2G，使用 Java語言開發(fā)，使用 SWT 構建桌面環(huán)境，以實際的行駛道路長度作為度量參數(shù)。仿真結果如圖 8 所示。同時從表 2 我們可以看到 Dijkstra 算法雖然得到了最優(yōu)的路徑長度 6957.85 m，但是其搜索時間 4187 ms 要遠大于 A* 系列算法。

表 2 路網(wǎng)實驗結果Table 2. The network experimental results

同時在 A* 算法中，本文的指向性自適應層次 A* 算法在裂變前的路網(wǎng)結構與經(jīng)典層次 A* 算法的路網(wǎng)結構是相同的，所以兩者結果相同。但查詢?nèi)舾纱魏螅?1 層的高層路網(wǎng)發(fā)生了裂變，由于此時高層對搜索時間的影響比較大，使得搜索時間由 1710 ms 降為 1582 ms，但是搜索的節(jié)點數(shù)反而增加了，由 3583 個節(jié)點增加到 3894，這是由于搜索底層節(jié)點到高層節(jié)點時，多搜索了一些節(jié)點。

在自適應層次 A* 算法上加上指向性啟發(fā)式函數(shù)后，搜索空間從 3583 降低到了 1545，降低為原來的 43%，可見，指向性啟發(fā)式函數(shù)對搜索空間的縮小作用很大，使得搜索時間也大幅降低為 281 ms。值得注意的是，帶指向性啟發(fā)式函數(shù)的算法裂變后，它的搜索節(jié)點數(shù)降低了，而非指向性的實驗結果則是增加，這是由于在計算底層節(jié)點到高層節(jié)點的過程中，由于是在同格子的一個很小的區(qū)域中進行，因此，指向性啟發(fā)式函數(shù)對搜索空間的縮小更為明顯。

綜合以上分析，搜索節(jié)點的減少得益于啟發(fā)式函數(shù)對方向的引入，同時，自適應分層技術通過對層次進行擴充來提高搜索的效率。雖然不排除損失了一部分精度，但指向性自適應層次 A* 算法算出來的結果已經(jīng)很大程度上接近于Dijkstra 算法的結果。這更加符合路徑規(guī)劃引擎對路徑規(guī)劃算法的要求。

4 結 論

本文在常規(guī) A* 網(wǎng)格分層的基礎上，提出了一種自適應的層次劃分方法，根據(jù)算法運行時的情況對層次進行動態(tài)擴充，顧及到了劃分粒度和層次連通性對效率影響之間相互的平衡。同時結合指向性的啟發(fā)式函數(shù)，極大地縮小了搜索空間，提高了搜索的效率，且算法的精度和效率也達到了一個比較好的平衡。實驗結果表明，改進后的 A* 算法的效率比原有的經(jīng)典層次 A* 算法高 8 倍以上，適用于實際的路網(wǎng)環(huán)境。

[1] 錢紅昇, 葛文鋒, 鐘鳴, 等. 基于分層的改進 A*算法在路徑規(guī)劃中的應用 [J/OL]. 計算機工程與應用, 2013.

[2] 李引珍, 顧守淮. 有向網(wǎng)絡上兩頂點間最短路徑的雙向搜索算法 [J]. 甘肅科學學報, 1998, 10(2): 11-14.

[3] 殷超. 基于改進 Dijkstra 算法的最短路徑搜索仿真 [J]. 山東理工大學學報(自然科學版), 2010, 24(6): 33-36.

[4] Holzer M, Schulz F, Wagner D. Engineering multilevel overlay graphs for shortest-path queries [J]. Journal of Experimental Algorithmics, 2008, 13: 2.5-2.26. doi: 10.1145/1412228.1412239.

[5] Delling D, Sanders P, Schultes D, et al. Engineering Route Planning Algorithms [M]. Springer Berlin Heidelberg, 2009: 117-139.

[6] Bauer R, Delling D, Sanders P, et al. Combining Hierarchical and Goal-directed Speed-up Techniques for Dijkstra’s Algorithm [M]. Springer Berlin Heidelberg, 2008: 303-318.

[7] 穆中林, 魯藝, 任波, 等. 基于改進 A′ 算法的無人機航路規(guī)劃方法研究 [J]. 彈箭與制導學報, 2007, 27(1): 297-300.

[8] Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

Large Scale Route Planning A＊ Algorithm Based on Self-Adaptive
Hierarchy Method

GUO Gengchen FENG Liangbing DENG Liang ZHAO Yonggang LIU Yu
( Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China )

The route planning engine has already become an important part for an online map system. The route planning algorithm is the key for the engine. The existing improvements for A* algorithm are mainly on the preprocessing part in which the roadmap data were layered statically. In this paper, an adaptive hierarchical method was proposed with an improved heuristic function which has goal-direction process. It greatly improves the efficiency and usability of A* algorithm in the engineering road planning system. The experiment result shows that the algorithm takes up only 42% of the search space and 13% of the search time when compared with the general A* algorithm.

route planning; A* algorithm; self-adaptive hierarchy method; directional guiding heuristic function

TG 156

A

2013-12-29

國家自然科學基金項目(61070147)，深圳市科技研發(fā)資金基礎研究計劃(JC201105190951A)。

郭耕辰，碩士，研究方向為地理信息系統(tǒng)和圖形圖像；馮良炳(通訊作者)，博士，研究方向為智能計算與智能控制、多視角三維重建、網(wǎng)絡服務組合和增強現(xiàn)實，E-mai：lb.feng@siat.ac.cn；鄧亮，碩士，研究方向為模式識別和視頻監(jiān)控等；趙永剛，碩士，研究方向為增強現(xiàn)實和圖像處理等；劉宇，碩士研究生，研究方向為圖像檢索和軟件架構。