用于索引視域的凸多邊形樹

苗 雪 郭 茜,2 王昭順 謝永紅,2

1(北京科技大學計算機與通信工程學院 北京 100083)

2(材料領域知識工程北京市重點實驗室(北京科技大學) 北京 100083)

智能手機在拍攝照片和錄制視頻時會在圖片文件中嵌入設備的地理位置和參數信息.Ay等人[1]提出使用視域(field-of-view, FOV)描述圖片所反映的地理區(qū)域，視域是由拍攝地點loc、相機朝向θ、可視角度α和可視距離r決定的扇形區(qū)域，如圖1所示.除了根據內容和關鍵字來搜索圖片[2-4]外，人們也可以根據視域來搜索圖片.圖1中的5個扇形f1，f2，…，f5分別代表5張照片img1，img2，…，img5的視域，假設用戶指定了查詢范圍Q(即圖1中矩形框)，系統返回的結果為照片img1，img2，img3，因為它們的視域f1，f2，f3均與Q有交集.

Fig. 1 An example of the FOV query圖1 FOV查詢示例

圖1示例中的查詢對象為視域扇形(FOV)，查詢范圍是一個矩形區(qū)域，我們稱其為面向FOV的窗口查詢(簡稱為FOV查詢).現有查詢算法有2種：基于R*樹[5]及其變體的查詢算法[6-8]和基于網格索引的查詢算法[9].R*樹索引的對象是FOV的最小包圍矩形，由于矩形和扇形形狀差異較大，導致節(jié)點內的無效區(qū)(dead space)較大；OR樹[8]是R*樹的變體，它索引的對象是FOV的圓心，所以有時會出現節(jié)點間重合較大的情況；Ma等人[9]提出了三級網格索引，當FOV的可視距離差異較大時，查詢會出現大量冗余的候選網格.

Fig. 2 Convex polygon tree圖2 凸多邊形樹

本文設計了凸多邊形樹來提升FOV查詢的性能.凸多邊形樹索引的對象是包圍FOV的最小五邊形，如圖2(a)中的f1～f9.距離較近的五邊形聚合在一起構成上層節(jié)點，如圖2(a)中的粗實線多邊形L1由f1，f2，f3聚合而成，依此類推其余的五邊形可聚合成更大的五邊形L2，L3，L4.與R*樹類似，凸多邊形樹逐層向上將較近的多邊形聚集在一起直到根節(jié)點，并且每個節(jié)點對應的凸多邊形邊數小于等于k，如圖2(a)中的限定k=5.

為了找出可以包圍一組多邊形的大多邊形，我們提出了淹沒算法，它一方面控制大多邊形的邊數，當最小包圍多邊形的邊數大于k時，算法將邊數減少到k；另一方面它保證大多邊形中無效區(qū)最少.我們構建凸多邊形樹的過程是逐個插入新的FOVfnew，算法保證插入fnew之后新葉子節(jié)點中引入無效區(qū)的比重小于ε無效，同時我們也考慮fnew與舊葉子重合區(qū)的比重V重合，以及新葉子增加區(qū)的比重V增加.如果fnew不適合插入任何一個葉子，則將其暫存入等待隊列中.在查詢時，除了對凸多邊形樹進行剪枝操作以減小搜索空間之外，我們還提出角度分區(qū)篩選算法找出候選結果集合.實驗結果表明，雖然創(chuàng)建凸多邊形樹比創(chuàng)建R*樹花費的時間多，但基于凸多邊形樹的FOV查詢算法比已有查詢算法的查詢效率更高.

本文工作的主要貢獻有3個方面：

1) 使用五邊形近似FOV，提出了索引此種五邊形的凸多邊形樹.由于樹的節(jié)點為多邊形，為了保證孩子節(jié)點數量穩(wěn)定，提出了淹沒算法來控制多邊形的邊數.

2) 設計了構建凸多變形樹的算法，包括節(jié)點插入算法和節(jié)點分裂算法.為了優(yōu)化樹的結構，提出了使用等待隊列的方法.

3) 制作了仿真數據集并在仿真數據集上對算法進行了性能測試.

1 相關工作

在空間數據庫領域中，對于可定位影像數據的研究工作主要包括影像數據視域的建模方法和影像數據的空間查詢技術.

1.1 可定位影像數據的視域建模方法

為了建立影像和地理區(qū)域之間的映射關系，我們利用影像文件中內嵌的地理坐標和光學參數來重構影像所反映的地理區(qū)域.但是，拍攝設備是由多個透鏡組成的復雜光學系統，我們很難準確還原光路并推算出影像對應的地理區(qū)域.一種常見的做法是忽略拍攝設備的高度并且把拍攝過程簡化為小孔成像，使用扇形視域來近似地描述影像對應的地理區(qū)域[1,10].隨著無人機技術的廣泛應用，也有研究者使用二維平面中的四邊形來近似地描述無人機在地面上的視域[11-12].這些建模方法將視域簡化為二維平面圖形，使得我們可以從空間數據查詢的角度來搜索圖片.比如Kim等人[13]設計并開發(fā)了TVDP平臺，并利用空間數據處理技術對可定位城市影像進行查詢和分析；Toyama等人[14]開發(fā)了一個用于圖片搜索的數據庫，它通過拍攝位置的經緯坐標和時間戳索引大規(guī)模圖像數據；Li等人[15]提出了一種估計照片視角方向的實用方法，它可以找出非位置感知設備拍攝的具有錯誤姿勢的照片.

1.2 可定位影像數據的空間查詢

在空間數據庫中，可定位影像數據查詢問題的實質是找出與用戶輸入的查詢區(qū)域相交的視域.根據應用場景的不同，視域的形狀可以抽象為扇形[8]或四邊形[11].這類基本查詢找出所有與查詢區(qū)域相交的視域，并將它們全部作為結果返回給用戶.為了提升結果的質量，Alfarrarjeh等人[16]提出根據視域對查詢區(qū)域的覆蓋程度以及視域的朝向對查詢結果進行排序，Ay等人[17]提出了衡量連續(xù)視域與查詢區(qū)域相關性的方法.

為了提高查詢效率，針對不同的查詢問題，研究者們提出了不同的索引技術.根據索引對地理信息的利用程度，我們將其分為兩大類：1)建立索引時僅考慮拍攝設備的地理位置，如Alfarrarjeh等人[18]同時考慮設備的位置和影像的語義為圖片建立了索引；2)根據設備的視域來構建索引，如Ay等人[1]使用R*樹來索引扇形視域(即FOV).然而，直接使用R*樹索引FOV會產生較大的節(jié)點內無效區(qū)和節(jié)點間重合區(qū).

為了進一步提升查詢效率，Lu等人[8]提出使用OR樹來索引FOV.OR樹是R*樹的變體，它的節(jié)點中不僅存儲了包圍若干拍攝位置(即FOV圓心)的最小邊界矩形，而且也存儲了這些FOV的方向范圍和可視距離范圍.構建OR樹的策略是盡量將拍攝位置靠近、可視距離相似和可視角度范圍相似的FOV放入同一個節(jié)點中.這種構建策略的缺點是節(jié)點間的重合較大，并且樹的結構取決于FOV的插入順序.

本文在Lu等人[8]工作的基礎上，提出了一種新的FOV索引，即凸多邊形樹，用于支持FOV查詢.雖然凸多邊形比矩形更適合包圍扇形等不規(guī)則形狀，但多邊形邊數不確定以及形狀不規(guī)則等因素為索引的構建帶來了困難和挑戰(zhàn).本文將在第3節(jié)詳細介紹構建凸多邊形樹的方法.

1.3 特定場景下的影像數據空間查詢

為了更好地索引視頻幀在二維平面空間中的視域，Kim等人[6]提出了GeoTree.GeoTree的葉子節(jié)點中存儲的是用于包圍連續(xù)視域的最小傾斜矩形.GeoTree適用于索引視域方向變化不劇烈的視頻.為了更準確地擬合拍攝設備的運動軌跡，Lee等人[7]提出GeoVideoIndex，它根據設備位置的變化趨勢構造包圍矩形，使其可以包圍住更多的FOV，從而減小了索引占用的存儲空間和索引的構建時間.Ma等人[9]提出一種基于可視場景、設備位置和視域方向的三級網格索引，這種網格結構適用于索引可視距離較接近的視域.針對無人機的高空拍攝場景，Lu等人[11]提出了用于索引四邊形視域的TetraR樹.

2 問題定義與解決方法概述

本節(jié)給出了FOV查詢的正式定義并給出了FOV查詢的解決方法概述.該過程主要包括2個階段，即索引構建階段和查詢處理階段.

2.1 問題定義

在二維歐氏空間中，FOV由4個參數決定：設備位置loc、鏡頭朝向θ、最大可視角度范圍α和最大可視距離r.前2個參數由設備自帶的GPS和方向傳感器自動獲取，后2個參數可由鏡頭本身參數推算得到.本文使用四元組(loc，αb，αe，r)描述FOV，其中αb和αe是以順時針為序的FOV可視角度范圍的起始角度和終止角度.

定義1.FOV查詢.在二維歐氏空間中，用戶指定矩形查詢區(qū)域Q，系統從已有的FOV集合F中找出所有與Q相交的FOV.

如圖1所示，用戶指定了可以恰好包圍住雕像的矩形查詢框Q，系統判斷只有照片img1，img2，img3的FOV與Q相交，所以系統會將這3張照片返回給用戶.

2.2 解決方法概述

解決FOV查詢的基本方法是檢查每個FOV是否與查詢區(qū)域Q相交，并且返回與Q有交集的FOV作為結果.這種方法需要遍歷整個FOV集合，查詢效率較低.為了提高查詢效率，我們提出使用凸多邊形樹索引FOV的方法來減小搜索空間.在預處理階段，我們?yōu)檎麄€FOV集合構建凸多邊形樹.在查詢處理階段，我們使用深度優(yōu)先搜索的方式遍歷凸多邊形樹，在遍歷的過程中剪掉不可能包含結果的節(jié)點.圖3展示了索引構建和查詢處理的主要流程.

Fig. 3 The overview of our solution圖3 解決方法概述圖

在索引構建階段，我們使用逐一插入FOV的方式來構建凸多邊形樹.凸多邊形樹的結構與R*樹類似，與R*樹不同的是它的節(jié)點對應的區(qū)域不是包圍矩形而是包圍凸多邊形.為了保證孩子節(jié)點數量穩(wěn)定，我們提出淹沒算法使包圍凸多邊形的邊數不超過k(3.1節(jié)將詳細介紹淹沒算法).在插入某個FOVf時，我們根據V無效，V增加和V重合這3個評判標準找到適合插入f的葉子節(jié)點Nopt，然后將f插入到Nopt中，并自底向上更新Nopt,Nopt的父親節(jié)點，直至根節(jié)點.如果我們沒有找到適合插入f的葉子節(jié)點，則將f放入等待隊列中.如果在插入的過程中出現孩子節(jié)點的數量超過Mmax的情況，則執(zhí)行節(jié)點分裂操作(3.2節(jié)將詳細介紹節(jié)點的插入和分裂策略).

在查詢處理階段，用戶輸入矩形查詢范圍Q(x1，y1，x2，y2)，其中(x1，y1)和(x2，y2)分別為Q的左下頂點和右上頂點坐標.我們從根節(jié)點開始自上而下遍歷凸多邊形樹.當下降至某個節(jié)點N時，判斷其是否與Q相交，如果相交，就下降到N的孩子節(jié)點.最后，將與Q有交集的所有FOV對應的照片作為結果返回給用戶.

以圖1為例，在索引構建階段，我們構建一個凸多邊形樹索引所有的FOV.在查詢處理階段，當用戶輸入查詢范圍Q(矩形框)之后，我們用深度優(yōu)先搜索的方式遍歷凸多邊形樹，在遍歷的過程中剪掉與Q不相交的節(jié)點，并將與Q相交的FOV存入到結果集中.最后，我們將結果集中FOV對應的照片展示給用戶，即img1，img2，img3.當用戶輸入其他查詢范圍時，我們可以重復利用凸多邊形樹進行搜索.

3 凸多邊形樹

為了方便計算，我們將FOV簡化為包圍五邊形，如圖4(a)所示，取弧的邊緣點p1和p4，以及弧的中點pmid，做此3個點的切線，切線的交點p2，p3與p1，p4，p0組合在一起構成FOV的包圍五邊形，如圖4(b)所示.

Fig. 4 Five-side bounding polygon of an FOV圖4 FOV的包圍五邊形

我們使用k*多邊形來包圍一個多邊形集合，用以構成樹的節(jié)點.

定義2.k*包圍多邊形.給定一個多邊形集合F={f1，f2，…，fn}，如果一個邊數不超過k的多邊形可以包圍住F中所有的多邊形，并且使無效區(qū)最小，則此多邊形被稱為集合F的k*包圍多邊形，用BPk(F)表示.

這里無效區(qū)是指屬于BPk(F)但不屬于F的區(qū)域，即BPk(F)-F.如圖2(a)所示，多邊形集合{f1，f2，f3}的5*包圍多邊形為L1，即BP5({f1，f2，f3})=L1.同理，多邊形集合{L1，L4}的5*包圍多邊形為N1，即BP5({L1，L4})=N1.

凸多邊形樹的索引對象是FOV的包圍五邊形集合F={f1，f2，…，fn}，每個葉子節(jié)點負責m個fi，它存儲包圍這些fi的k*多邊形以及指向這些fi的指針.每個葉子節(jié)點的上一層節(jié)點負責m個葉子節(jié)點，它存儲包圍這些葉子節(jié)點的k*多邊形以及指向這些葉子節(jié)點的指針，依次往上直到根節(jié)點.跟R*樹類似，凸多邊形樹中每個葉子節(jié)點(或中間節(jié)點)包含的FOV(或孩子節(jié)點)數目m在Mmin和Mmax之間且根節(jié)點至少有2個孩子節(jié)點.

圖2的例子中有9個FOV的包圍五邊形{f1，f2，…，f9}，其中{f1，f2，f3}由葉子節(jié)點L1負責，即L1用更大的k*多邊形(k=5)包圍了{f1，f2，f3}.同理，{f4，f5}由葉子節(jié)點L2負責，{f6，f7}由葉子節(jié)點L3負責，{f8，f9}由葉子節(jié)點L4負責.葉子節(jié)點{L1，L2，…，L4}又進一步聚合成2個更大的k*多邊形N1和N2，而中間節(jié)點{N1，N2}又進一步向上聚合成根節(jié)點root，最終形成如圖2(b)所示的樹形結構.

3.1 淹沒算法

本節(jié)提出淹沒算法來找出包圍一組多邊形集合F={f1，f2，…，fm}的k*多邊形.淹沒算法的起點是包圍F的最小凸多邊形BP(F)，如圖5(a)中的多邊形為包圍某多邊形集合F的最小多邊形BP(F)，為了讓圖更簡潔，我們沒有畫出集合F中的多邊形.如果BP(F)的邊數≤k，則BP(F)為F的k*多邊形，算法直接將此多邊形作為結果返回;如果BP(F)的邊數>k，則算法每次淹沒一條BP(F)的邊，直到邊數減少到k為止.

Fig. 5 Submerging convex polygon sides when k=5圖5 k=5時凸多邊形的淹沒操作

淹沒操作選擇2個相鄰頂點pi和pi+1，將邊pi-1pi延長并且將邊pi+2pi+1延長，用這2條延長線的交點取代pi和pi+1將淹沒掉邊pipi+1.如圖5(a)，如果想淹沒邊p3p4，則延長p2p3和p5p4，用延長線的交點p34作為多邊形的新頂點，這個操作將淹沒掉邊p3p4.通過淹沒操作得到的新多邊形仍然是凸多邊形.

① 包圍集合F的最小凸多邊形BP(F)簡寫為BP，k*多邊形BPk(F)簡寫為BPk.

② 三角形Δpipi,i+1pi+1簡寫為Δpipi+1，如Δp3p3,4p4簡寫為Δp3p4.

③ 在不會發(fā)生混淆的情況下，FOV除了指視域扇形本身之外，也指包圍此扇形的凸五邊形.

多邊形的新增區(qū)域為新頂點與2個舊頂點組成的三角形，如圖5(a)中的Δp3p34p4.此三角形為無效區(qū)，因為此三角形與F中的所有多邊形都沒有交集.為了盡量減小節(jié)點的無效區(qū)，我們每次選擇淹沒當前多邊形的一條最優(yōu)邊，這里最優(yōu)邊的含義是如果淹沒它那么引入的三角形最小.如圖5(b)所示，我們首先淹沒邊p2p3，因為淹沒它引入的三角形最小.在得到新的多邊形之后，我們選擇淹沒最優(yōu)邊p8p9，依此類推，我們淹沒p5p6，然后淹沒p7p89，其中p89為淹沒邊p8p9時生成的新頂點.最后，算法得到k=5的k*多邊形.

算法1.淹沒算法.

輸入：BP，k；

輸出：BPk.

①L←{p1p2,Δp1p2,…,pnp1,Δpnp1}；

② whileBP邊數大于kdo

③ 遍歷L找出最優(yōu)邊pipi+1；

④ 求邊pi-1pi與邊pi+2pi+1的延長線交點pnew；

⑤BP←BP-{pi,pi+1}∪{pnew}；

⑥L←L-pipi+1,Δpipi+1；

⑨ end while

⑩BPk←BP.

淹沒算法如算法1所示.算法的輸入是凸多邊形BP①和k，輸出是k*多邊形BPk.首先，我們使用鏈表L存儲凸多邊形每條邊pipi+1及其對應三角形Δpipi+1②的面積(行①).然后，算法每次淹沒一條最優(yōu)邊(行②～⑨)，直到多邊形邊數是k為止.每次循環(huán)時，算法遍歷整個L找出最優(yōu)邊(行③)，求出新頂點pnew(行④)并更新多邊形的頂點集合BP(行⑤).此外，算法還要將被淹沒的邊及其三角形從L中去掉(行⑥)，并更新兩條舊邊(行⑦⑧).最后，算法得到k*多邊形BPk(行⑩).

在使用算法1時，需要注意多邊形可能存在無法被淹沒的邊.如圖5(b)所示，假設我們想淹沒邊p56p789，而p1p789的延長線和p4p56的延長線無交點.遇到此種情況時，我們將對應的三角形面積設置為無窮大，讓此種邊不會被選中.

3.2 節(jié)點插入策略

我們采用逐個插入FOV③的方式構建凸多邊形樹.插入一個FOVf分為2步：1)自頂向下找出插入f的最優(yōu)葉子節(jié)點Nopt，這步被稱為尋找父節(jié)點；2)將f插入到Nopt中并自底向上更新Nopt,Nopt的父節(jié)點，直至根節(jié)點，這步被稱為更新父節(jié)點.在尋找父節(jié)點時，根據V無效，V增加和V重合三個評判標準找出最優(yōu)葉子節(jié)點.V無效用于衡量如果將f插入節(jié)點N，那么新節(jié)點Nnew會出現多少無效區(qū)，即：

V無效=(AreaNnew-AreaN∪f)/Areaf,

(1)

其中，AreaNnew表示包圍f和N的k*多邊形的面積，AreaN∪f表示N∪f本身的面積，Areaf表示f本身的面積.如圖6所示，舊節(jié)點N為實線填充的區(qū)域，f為無任何填充的區(qū)域，新節(jié)點Nnew為既包含N也包含f的多邊形，而虛線填充的區(qū)域為無效區(qū).V增加用于衡量新節(jié)點Nnew相比于原節(jié)點N增加了多少面積，即:

V增加=AreaNnew-AreaN，

(2)

其中,AreaN表示N本身的面積.V重合用于衡量f與N的重合區(qū)域的大小，即:

V重合=AreaN∩f/Areaf.

(3)

其中,AreaN∩f表示f與N重合區(qū)域的面積，如圖6所示的粗五邊形區(qū)域.

Fig. 6 Display of the old node N, FOV f, and new node Nnew圖6 舊節(jié)點N,FOV f和新節(jié)點Nnew的展示

我們尋找最優(yōu)葉子Nopt的策略是，優(yōu)先篩選出滿足V無效≤ε無效(條件A)的葉子LA.此種葉子Li∈LA的優(yōu)點是f插入Li后引入的無效區(qū)較小.然后，我們分3種情況處理：

① |·|表示集合中元素的數量，如|LA|表示集合LA中元素的數量.

1) 如果此種葉子只有1個，即|LA|①=1，則此葉子即為最優(yōu)葉子Nopt，我們將f插入Nopt.

2) 如果沒有此種葉子，即|LA|=0，則說明f遠離當前的所有葉子，我們創(chuàng)建一個僅包含f的新葉子Nopt，并將其插入到合適的上層節(jié)點中.此處上層節(jié)點是指葉子節(jié)點的上一層節(jié)點.

3) 如果此種葉子有多個，即|LA|≥2，我們根據V重合進一步從LA中篩選出V重合≥ε重合(條件B)的葉子LB.篩選此種葉子的動機是：f插入與其重合較大的葉子后，會使得新葉子與其兄弟葉子的重合較大.

根據集合LB中元素的數量，我們分3種情況討論：

① 如果此種葉子只有1個，即|LB|=1，則此葉子即為最優(yōu)葉子Nopt，我們將f插入Nopt.

② 如果沒有此種葉子，即LB=?，我們從LA中找出V增加最小的葉子作為最優(yōu)葉子Nopt，原因是f插入此葉子后引入的新增面積較少，也會在一定程度上減小新葉子與其兄弟葉子之間的重合.

Fig. 7 Waiting list圖7 等待隊列

算法2描述了將一個FOVf插入到凸多邊形樹的過程.首先，算法根據條件A篩選出葉子集合LA(行①).篩選的過程是從根節(jié)點開始向下搜索，將符合條件A的孩子節(jié)點展開，直到找出所有符合條件A的葉子為止.此處可以逐層展開中間節(jié)點的依據是如果父節(jié)點不滿足條件A，則其孩子節(jié)點必然不滿足條件A.然后，算法根據LA中元素的數量分3種情況處理：1)行②～⑤對應情況2，其中算法找出V無效最小的節(jié)點作為合適的上層節(jié)點，也就是說將新葉子Nopt插入到此節(jié)點后引入的無效區(qū)最小(行④)；2)行⑥～⑧對應情況1，其中行⑧將f插入到Nopt之后，要逐層向上更新父節(jié)點，直到根節(jié)點為止；3)行⑨～對應情況3，算法首先根據條件B進一步篩選LA中的葉子得到集合LB(行⑩)，根據LB集合中元素的個數又細分為3種情況.行～對應情況3中①；行～對應情況3中②；行對應情況3中③，其中W表示等待隊列.

算法2.節(jié)點插入算法.

輸入：凸多邊形樹的根節(jié)點root、準備插入樹中的FOVf；

輸出：插入f之后的樹.

①LA←滿足V無效≤ε無效的葉子節(jié)點；

② if |LA|=0 then

③Nopt←僅包含f的新葉子節(jié)點；

④ 將Nopt插入到合適的上層節(jié)點中；

⑤ 向上更新父節(jié)點一直到root；

⑥ else if |LA|=1 then

⑦Nopt←LA中僅有的葉子節(jié)點；

⑧Nopt←Nopt∪{f}，向上更新父節(jié)點一直到root；

⑨ else/*即|LA|≥2*/

⑩LB←從LA中找出滿足V重合≥ε重合的葉子；

節(jié)點分裂方法：在使用算法2時需要注意，當新FOV(或新孩子節(jié)點)插入到葉子節(jié)點(或中間節(jié)點)N時，N可能會溢出.我們處理溢出的方法是將N分裂為2個新節(jié)點N1和N2.分裂的方法為：首先，我們從N的孩子中選取2個關鍵孩子c1和c2，它們能夠成為關鍵孩子的原因是包圍它們的k*多邊形面積最大.關鍵孩子c1和c2分別成為N1和N2的第1個孩子.然后，我們將剩余的孩子分配給N1和N2，分配規(guī)則是每次選擇1個V增加最小的孩子放入N1(或N2)中.在此過程中，我們需要確保N1和N2的孩子數目達到Mmin.算法3展示了將N分裂為N1和N2的過程.

算法3.節(jié)點分裂算法.

輸入：溢出節(jié)點N；

輸出：分裂后的節(jié)點N1和N2.

①c1,c2←N的2個關鍵孩子；

②N1←N1∪{c1}；

③N2←N2∪{c2}；

④ while |N1|

/*|N1|和|N2|表示N1和N2的孩子數目*/

⑤ if |N1|

⑥ci←N-N1-N2中讓N1的V增加最小的孩子；

⑦N1←N1∪{ci}；

⑧ end if

⑨ if |N2|

⑩cj←N-N1-N2中讓N2的V增加最小的孩子；

等待隊列的生成：如果f目前不適插入到任何一個葉子中，算法2將其放入等待隊列W中(行).等待隊列W中的元素為FOV的集合，等到時機成熟時，它們會作為葉子插入到凸多邊形樹中.當我們要將f放入W時，如果W非空，則遍歷W找出最佳元素Eopt并將f并入Eopt中，即Eopt←Eopt∪{f}；如果W為空或沒有找到最佳元素，則直接將{f}放入W中.衡量最佳元素的標準是在f并入到此元素后，使得V無效≤ε無效.如果符合條件的元素超過1個，則從中選取V增加最小的元素并將f并入該元素.算法4展示了生成等待隊列W的過程.

算法4.等待隊列生成算法.

輸入：FOVf、等待隊列W；

輸出：更新之后的W.

① if |W|≠0 then

②LC←W中滿足V無效≤ε無效的元素；

③ if |LC|=0 then/*沒有找到最佳元素*/

④W←W∪{f}；

⑤ else if |LC|=1 then

/*找到1個最佳元素*/

⑥Eopt←LC中僅有的元素；

⑦Eopt←Eopt∪{f}；

⑧ else/*找到多個最佳元素*/

⑨Eopt←LC中V增加最小的元素；

⑩Eopt←Eopt∪{f}；

當W中的元素數目達到Mmax時，我們將W中存儲的所有元素作為葉子重新插入到樹中.如果元素中僅有1個FOVfi，則遍歷凸多邊形樹找出最優(yōu)葉子節(jié)點Nopt并將fi插入Nopt；如果元素中包含多個FOV，則生成對應的葉子節(jié)點Li，并將其插入到合適的上層節(jié)點中.

4 查詢處理

本節(jié)介紹凸多邊形樹上的FOV查詢處理算法.從根節(jié)點開始向下搜索可能存在結果的子樹，即只有當孩子節(jié)點與查詢范圍Q有交集時才下降到此節(jié)點繼續(xù)搜索.當下降到某個葉子節(jié)點L時，檢查L包含的每個FOV(扇形)是否與Q存在交集.

函數1.FOV查詢函數FovQuery(N,Q).

輸入：凸多邊形樹的節(jié)點N、查詢框Q；

輸出：與Q有交集的FOV.

① ifN不是葉子節(jié)點then

② forN的每個孩子節(jié)點cido

③ ifci∩Q不為空then

④FovQuery(ci,Q)；/*遞歸調用*/

⑤ end if

⑥ end for

⑦ else/*N是葉子節(jié)點*/

⑧ forN的每個FOVfido

⑨ iffi∩Q不為空then

函數1描述了FOV查詢的具體過程，即函數FovQuery().我們采用遞歸的方式對凸多邊形樹進行深度優(yōu)先遍歷，在主程序中傳入函數FovQuery()的參數是root和Q，其中root是凸多邊形樹的根節(jié)點.執(zhí)行函數FovQuery()時，首先判斷節(jié)點N是否為葉子節(jié)點(行①).如果不是葉子節(jié)點，則將與Q有交集的孩子節(jié)點作為參數遞歸地調用函數(行②～⑥).如果是葉子節(jié)點，則判斷節(jié)點中的每個FOV是否與Q有交集(行⑨)，并輸出有交集的FOV(行⑩).

我們提出角度分區(qū)篩選算法以便快速地找出與Q有交集的FOV(行⑨).算法根據Q的位置將空間劃分為9個區(qū)域，如圖8所示.如果FOV的圓心位于Q之內，則其肯定與Q有交集.如果FOV圓心位于其他分區(qū)內，則判斷兩式是否同時成立:

MinDist(loc,Q)

(4)

[αb,αe]∩[αqb,αqe]≠?.

(5)

Fig. 8 Angle partition filtering method圖8 角度分區(qū)篩選方法

式(4)中MinDist(loc,Q)是圓心loc到Q的最小距離，r是FOV的半徑.如果式(4)不成立，則FOV離Q過遠，不可能覆蓋到Q.式(5)中，[αb,αe]是FOV的方向范圍，[αqb,αqe]是Q相對于loc的方向范圍(如圖8所示).如果式(5)不成立，則FOV的方向范圍偏離了Q相對于loc的方向，FOV無法覆蓋到Q.如果式(4)和式(5)同時成立，則繼續(xù)判斷FOV的半徑邊rb或re是否與Q距離loc較近的邊有交點，如果有交點，則判定此FOV與Q有交集.

證明.1)若MinDist(loc,Q)≥r，無論[αb,αe]∩[αqb,αqe]是否為?，FOV一定不會與Q相交，如圖9中f1所示；2)若[αb,αe]∩[αqb,αqe]=?，無論MinDist(loc,Q)是否小于r，FOV一定不會與Q相交，如圖9中f2所示；3)若MinDist(loc,Q)

證畢.

Fig. 9 Proof of the angle partition filtering method圖9 角度分區(qū)篩選方法的證明

5 實 驗

本節(jié)提出了生成仿真數據集的方法，并利用此數據集進行了算法性能驗證實驗.在實驗中對比了凸多邊形樹、R*樹和OR樹的構建效率，并且對比了這3種索引對FOV查詢性能的影響.此外，我們展示和分析了在真實數據集上的查詢結果.

5.1 實驗環(huán)境設置和仿真數據集生成

實驗平臺是Intel?CoreTMi5-8300H CPU(2.30 GHz)，8 GB內存，Win10專業(yè)版操作系統.實驗中的所有算法均使用Java語言實現.實驗中測試了節(jié)點扇出值等因素對索引構建和查詢性能的影響.實驗中使用了3種數據集：1)均勻分布的數據集，即FOV的圓心在空間中隨機分布，FOV的數量為103，104，105，依次令S1，S2，S3表示這3個均勻分布數據集.2)仿真數據集，為了模擬真實生活中的拍照行為，我們根據常用拍照設備的光學參數生成了大量符合實際情況的FOV.在二維空間中擺放這些FOV時，我們讓其圓心(即拍攝位置)聚集在某些熱門區(qū)域并且零散分布在冷門區(qū)域，以此來模擬現實生活中熱門景點的照片較多而冷門區(qū)域的照片較少的現象.圖10展示了實驗中使用的3個仿真數據集D1,D2,D3，每個仿真數據集中FOV數量都是104.3)真實數據集，我們使用iPhone 6s Plus實地拍攝了100張照片用于展示查詢效果.均勻分布數據集和仿真數據集用于測試索引構建和FOV查詢的性能.由于互聯網上沒有大量的帶地理信息的標準影像數據集，所以我們手工拍攝的少量照片僅用于分析和驗證FOV查詢的結果.

Fig. 10 Three simulation datasets generated by mobile phone photography圖10 通過手機拍照生成的3個仿真數據集

Fig. 11 Time cost of FOV queries圖11 FOV查詢所花費的時間

在制作仿真數據集時，我們調查了目前國內主流智能手機的光學參數，使用Ay等人[1]提出的方法計算出智能手機鏡頭的最大可視角度α范圍為[20°，80°]，最大可視距離r為[200，400](單位：m).在生成仿真FOV時，我們從這2個區(qū)間中隨機選取α和r的值，鏡頭朝向θ從[0°，360°)中隨機選取.我們在空間中隨機生成了若干不相交的矩形作為熱門區(qū)域的邊界，讓h%的FOV圓心落入這些熱門區(qū)域中，讓(1-h%)的FOV圓心落在熱門區(qū)域之外，其中仿真數據集D1中h%約為99%，D2和D3中h%約為92%.

5.2 算法性能實驗分析

圖11展示了在均勻數據集和仿真數據集上改變節(jié)點扇出值Mmax時，基于3種索引的FOV查詢效率對比.由圖11可見，當節(jié)點扇出值為40時，基于凸多邊形樹的FOV查詢效率較高；無論在真實還是在仿真數據集上，當節(jié)點扇出值變化時，在凸多邊形樹上進行FOV查詢比在另外2種樹上更節(jié)省時間.

Fig. 12 The influences of different parameters on FOV query performance圖12 不同參數對FOV查詢性能的影響

圖12展示的是在均勻數據集和仿真數據集上，當參數ε無效,ε重合和k變化時，在凸多邊形樹上進行FOV查詢所花費的時間.由圖12可見，當ε無效設置的較小時查詢效率較高，因為較小的ε無效可以有效控制無效區(qū)的面積；在較大數據集上ε重合對性能的影響較明顯，因為數據集越大節(jié)點重合越嚴重；邊數k設置得較小時查詢效率較高，因為當凸多邊形邊數增加時，判定凸多邊形是否與Q相交需要花費更多的時間.

圖13展示的是在均勻數據集和仿真數據集上，改變查詢范圍Q的大小時，利用3種索引進行FOV查詢所花費的時間.在實驗中，我們將Q的寬度設置為500 m，Q的長度設置為50 m，500 m，5 000 m，從而使Q的大小呈10倍增長.由圖13可見，對于不同大小的Q，凸多邊形均表現出較好的查詢性能.這是因為凸多邊形樹中節(jié)點內無效區(qū)較小且節(jié)點間的重合區(qū)較小，這樣可以避免訪問大量的錯誤節(jié)點(錯誤節(jié)點為不包含結果的節(jié)點).

Fig. 13 The effect of the size of Q on query performance圖13 Q的大小對查詢性能的影響

圖14展示了當數據集大小或節(jié)點扇出值變化時，構建R*樹、OR樹、凸多邊形樹所花費的時間.如圖14(a)所示，在3個數據集上構建R*樹花費的時間少于構建凸多邊形樹和OR樹所花費的時間；當數據集較小時，構建3種索引花費的時間差不多；但隨著數據集增大，構建凸多邊形樹和OR樹所花費的時間顯著增加，構建OR樹的時間增幅比構建凸多邊形樹的時間增幅要大很多.這是因為在構建R*樹和凸多邊形樹時，節(jié)點的插入和分裂不需要復雜的計算，而構建OR樹時節(jié)點插入和分裂需要大量的復雜計算并且在節(jié)點插入和分裂過程中需要動態(tài)更新節(jié)點中附加的可視距離和方向信息.如圖14(b)所示，當節(jié)點扇出值變化時，凸多邊形樹的構建時間與R*樹的構建時間相近，R*樹的構建時間最少，OR樹的構建時間最多.

Fig. 14 Compare of the time cost of building indexes圖14 對比構建索引的時間

圖15展示了當數據集大小和節(jié)點扇出值變化時，構建3種索引的內存消耗情況.如圖15(a)所示，當數據集大小變化時，構建OR樹消耗的內存最多，構建R*樹消耗的內存最少，而構建凸多邊形樹消耗的內存位于兩者中間.當數據集較小時，構建3種索引的內存消耗相似；當數據集增大時，構建R*樹和凸多邊形樹所需內存的變化不明顯，而構建OR樹所需的內存明顯增大.這是因為R*樹節(jié)點中僅存儲包圍矩形和孩子節(jié)點指針信息，由于存儲的信息較簡單，所以內存消耗較??；OR樹中除了存儲相機位置的包圍矩形之外，還存儲了節(jié)點所包含的FOV的可視距離和方向信息，所以內存消耗較大；凸多邊形樹中僅存儲了節(jié)點的包圍凸多邊形，并且凸多邊形的邊數不超過k，因此內存消耗相對較小.如圖15(b)所示，當節(jié)點扇出值變化時，構建R*樹的內存消耗最少，構建OR樹的內存消耗最多.

Fig. 15 Memory consumption when building indexes圖15 構建索引的內存消耗情況

5.3 實驗結果展示與分析

實驗中用到的真實數據集是使用智能手機采集的，包含100張照片.由于實驗中使用的智能手機僅能將拍攝位置和光學參數嵌入到照片文件中，而不能獲取拍攝角度，所以拍攝角度是使用手機中自帶的指南針記錄的.圖16中的氣球標出了部分拍攝位置.

如圖16所示，用戶在地圖上圈定了查詢范圍Q1，Q2和Q3，系統要找出拍攝到這3個區(qū)域照片.如圖17(a)～(d)為拍攝到區(qū)域Q1的照片，圖17(e)(f)為拍到區(qū)域Q2的照片，圖17(g)～(j)為拍到區(qū)域Q3的照片.圖16中的被圓圈圈出的氣球標出了查詢結果的拍攝位置.以Q3為例，雖然照片No.15的拍攝位置離Q3較遠，但它的FOV覆蓋到了Q3，使其成為查詢結果.雖然照片No.42的拍攝位置比No.15的拍攝位置更近，但由于拍攝時沒有朝向Q3，它的FOV未能覆蓋到Q3，所以它沒有成為查詢結果.

Fig. 16 Query regions on real datasets圖16 真實數據集上的查詢區(qū)域

Fig. 17 Query results on real datasets圖17 真實數據集上的查詢結果

6 結束語

本文提出了索引FOV(扇形)的凸多邊形樹，它的節(jié)點形狀為k*多邊形.為了構建k*多邊形，我們提出了淹沒算法.構建凸多邊形樹時，我們使用將FOV逐個插入的方法.為了選擇最優(yōu)葉子節(jié)點將FOV插入，我們提出了根據無效區(qū)域大小(V無效)、重合區(qū)域大小(V重合)、增加區(qū)域大小(V增加)三個因素選擇葉子節(jié)點的方法，并提出了將不適合插入的FOV暫存入等待隊列中的方法.同時，我們也提出了在凸多邊形樹上進行FOV查詢的算法，并在均勻數據集和仿真數據集上對算法進行了實驗和性能分析.

作者貢獻聲明：苗雪、郭茜提出研究問題并設計研究方案，還進一步負責起草論文，苗雪同時負責收集、處理數據并進行實驗驗證；王昭順、謝永紅負責最終版本的修訂.