用于索引視域的凸多邊形樹(shù)

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

1(北京科技大學(xué)計(jì)算機(jī)與通信工程學(xué)院 北京 100083)

2(材料領(lǐng)域知識(shí)工程北京市重點(diǎn)實(shí)驗(yàn)室(北京科技大學(xué)) 北京 100083)

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

Fig. 1 An example of the FOV query圖1 FOV查詢(xún)示例

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

Fig. 2 Convex polygon tree圖2 凸多邊形樹(shù)

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

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

本文工作的主要貢獻(xiàn)有3個(gè)方面：

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

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

3) 制作了仿真數(shù)據(jù)集并在仿真數(shù)據(jù)集上對(duì)算法進(jìn)行了性能測(cè)試.

1 相關(guān)工作

在空間數(shù)據(jù)庫(kù)領(lǐng)域中，對(duì)于可定位影像數(shù)據(jù)的研究工作主要包括影像數(shù)據(jù)視域的建模方法和影像數(shù)據(jù)的空間查詢(xún)技術(shù).

1.1 可定位影像數(shù)據(jù)的視域建模方法

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

1.2 可定位影像數(shù)據(jù)的空間查詢(xún)

在空間數(shù)據(jù)庫(kù)中，可定位影像數(shù)據(jù)查詢(xún)問(wèn)題的實(shí)質(zhì)是找出與用戶(hù)輸入的查詢(xún)區(qū)域相交的視域.根據(jù)應(yīng)用場(chǎng)景的不同，視域的形狀可以抽象為扇形[8]或四邊形[11].這類(lèi)基本查詢(xún)找出所有與查詢(xún)區(qū)域相交的視域，并將它們?nèi)孔鳛榻Y(jié)果返回給用戶(hù).為了提升結(jié)果的質(zhì)量，Alfarrarjeh等人[16]提出根據(jù)視域?qū)Σ樵?xún)區(qū)域的覆蓋程度以及視域的朝向?qū)Σ樵?xún)結(jié)果進(jìn)行排序，Ay等人[17]提出了衡量連續(xù)視域與查詢(xún)區(qū)域相關(guān)性的方法.

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

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

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

1.3 特定場(chǎng)景下的影像數(shù)據(jù)空間查詢(xún)

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

2 問(wèn)題定義與解決方法概述

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

2.1 問(wèn)題定義

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

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

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

2.2 解決方法概述

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

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

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

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

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

3 凸多邊形樹(shù)

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

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

我們使用k*多邊形來(lái)包圍一個(gè)多邊形集合，用以構(gòu)成樹(shù)的節(jié)點(diǎn).

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

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

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

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

3.1 淹沒(méi)算法

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

Fig. 5 Submerging convex polygon sides when k=5圖5 k=5時(shí)凸多邊形的淹沒(méi)操作

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

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

② 三角形Δpipi,i+1pi+1簡(jiǎn)寫(xiě)為Δpipi+1，如Δp3p3,4p4簡(jiǎn)寫(xiě)為Δp3p4.

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

多邊形的新增區(qū)域?yàn)樾马旤c(diǎn)與2個(gè)舊頂點(diǎn)組成的三角形，如圖5(a)中的Δp3p34p4.此三角形為無(wú)效區(qū)，因?yàn)榇巳切闻cF中的所有多邊形都沒(méi)有交集.為了盡量減小節(jié)點(diǎn)的無(wú)效區(qū)，我們每次選擇淹沒(méi)當(dāng)前多邊形的一條最優(yōu)邊，這里最優(yōu)邊的含義是如果淹沒(méi)它那么引入的三角形最小.如圖5(b)所示，我們首先淹沒(méi)邊p2p3，因?yàn)檠蜎](méi)它引入的三角形最小.在得到新的多邊形之后，我們選擇淹沒(méi)最優(yōu)邊p8p9，依此類(lèi)推，我們淹沒(méi)p5p6，然后淹沒(méi)p7p89，其中p89為淹沒(méi)邊p8p9時(shí)生成的新頂點(diǎn).最后，算法得到k=5的k*多邊形.

算法1.淹沒(méi)算法.

輸入：BP，k；

輸出：BPk.

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

② whileBP邊數(shù)大于kdo

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

④ 求邊pi-1pi與邊pi+2pi+1的延長(zhǎng)線(xiàn)交點(diǎn)pnew；

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

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

⑨ end while

⑩BPk←BP.

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

在使用算法1時(shí)，需要注意多邊形可能存在無(wú)法被淹沒(méi)的邊.如圖5(b)所示，假設(shè)我們想淹沒(méi)邊p56p789，而p1p789的延長(zhǎng)線(xiàn)和p4p56的延長(zhǎng)線(xiàn)無(wú)交點(diǎn).遇到此種情況時(shí)，我們將對(duì)應(yīng)的三角形面積設(shè)置為無(wú)窮大，讓此種邊不會(huì)被選中.

3.2 節(jié)點(diǎn)插入策略

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

V無(wú)效=(AreaNnew-AreaN∪f(wàn))/Areaf,

(1)

其中，AreaNnew表示包圍f和N的k*多邊形的面積，AreaN∪f(wàn)表示N∪f(wàn)本身的面積，Areaf表示f本身的面積.如圖6所示，舊節(jié)點(diǎn)N為實(shí)線(xiàn)填充的區(qū)域，f為無(wú)任何填充的區(qū)域，新節(jié)點(diǎn)Nnew為既包含N也包含f的多邊形，而虛線(xiàn)填充的區(qū)域?yàn)闊o(wú)效區(qū).V增加用于衡量新節(jié)點(diǎn)Nnew相比于原節(jié)點(diǎn)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é)點(diǎn)N,FOV f和新節(jié)點(diǎn)Nnew的展示

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

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

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

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

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

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

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

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

Fig. 7 Waiting list圖7 等待隊(duì)列

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

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

輸入：凸多邊形樹(shù)的根節(jié)點(diǎn)root、準(zhǔn)備插入樹(shù)中的FOVf；

輸出：插入f之后的樹(shù).

①LA←滿(mǎn)足V無(wú)效≤ε無(wú)效的葉子節(jié)點(diǎn)；

② if |LA|=0 then

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

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

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

⑥ else if |LA|=1 then

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

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

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

⑩LB←從LA中找出滿(mǎn)足V重合≥ε重合的葉子；

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

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

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

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

①c1,c2←N的2個(gè)關(guān)鍵孩子；

②N1←N1∪{c1}；

③N2←N2∪{c2}；

④ while |N1|

/*|N1|和|N2|表示N1和N2的孩子數(shù)目*/

⑤ if |N1|

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

⑦N1←N1∪{ci}；

⑧ end if

⑨ if |N2|

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

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

算法4.等待隊(duì)列生成算法.

輸入：FOVf、等待隊(duì)列W；

輸出：更新之后的W.

① if |W|≠0 then

②LC←W中滿(mǎn)足V無(wú)效≤ε無(wú)效的元素；

③ if |LC|=0 then/*沒(méi)有找到最佳元素*/

④W←W∪{f}；

⑤ else if |LC|=1 then

/*找到1個(gè)最佳元素*/

⑥Eopt←LC中僅有的元素；

⑦Eopt←Eopt∪{f}；

⑧ else/*找到多個(gè)最佳元素*/

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

⑩Eopt←Eopt∪{f}；

當(dāng)W中的元素?cái)?shù)目達(dá)到Mmax時(shí)，我們將W中存儲(chǔ)的所有元素作為葉子重新插入到樹(shù)中.如果元素中僅有1個(gè)FOVfi，則遍歷凸多邊形樹(shù)找出最優(yōu)葉子節(jié)點(diǎn)Nopt并將fi插入Nopt；如果元素中包含多個(gè)FOV，則生成對(duì)應(yīng)的葉子節(jié)點(diǎn)Li，并將其插入到合適的上層節(jié)點(diǎn)中.

4 查詢(xún)處理

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

函數(shù)1.FOV查詢(xún)函數(shù)FovQuery(N,Q).

輸入：凸多邊形樹(shù)的節(jié)點(diǎn)N、查詢(xún)框Q；

輸出：與Q有交集的FOV.

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

② forN的每個(gè)孩子節(jié)點(diǎn)cido

③ ifci∩Q不為空then

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

⑤ end if

⑥ end for

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

⑧ forN的每個(gè)FOVfido

⑨ iffi∩Q不為空then

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

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

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過(guò)遠(yuǎn)，不可能覆蓋到Q.式(5)中，[αb,αe]是FOV的方向范圍，[αqb,αqe]是Q相對(duì)于loc的方向范圍(如圖8所示).如果式(5)不成立，則FOV的方向范圍偏離了Q相對(duì)于loc的方向，F(xiàn)OV無(wú)法覆蓋到Q.如果式(4)和式(5)同時(shí)成立，則繼續(xù)判斷FOV的半徑邊rb或re是否與Q距離loc較近的邊有交點(diǎn)，如果有交點(diǎn)，則判定此FOV與Q有交集.

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

證畢.

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

5 實(shí) 驗(yàn)

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

5.1 實(shí)驗(yàn)環(huán)境設(shè)置和仿真數(shù)據(jù)集生成

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

Fig. 10 Three simulation datasets generated by mobile phone photography圖10 通過(guò)手機(jī)拍照生成的3個(gè)仿真數(shù)據(jù)集

Fig. 11 Time cost of FOV queries圖11 FOV查詢(xún)所花費(fèi)的時(shí)間

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

5.2 算法性能實(shí)驗(yàn)分析

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

Fig. 12 The influences of different parameters on FOV query performance圖12 不同參數(shù)對(duì)FOV查詢(xún)性能的影響

圖12展示的是在均勻數(shù)據(jù)集和仿真數(shù)據(jù)集上，當(dāng)參數(shù)ε無(wú)效,ε重合和k變化時(shí)，在凸多邊形樹(shù)上進(jìn)行FOV查詢(xún)所花費(fèi)的時(shí)間.由圖12可見(jiàn)，當(dāng)ε無(wú)效設(shè)置的較小時(shí)查詢(xún)效率較高，因?yàn)檩^小的ε無(wú)效可以有效控制無(wú)效區(qū)的面積；在較大數(shù)據(jù)集上ε重合對(duì)性能的影響較明顯，因?yàn)閿?shù)據(jù)集越大節(jié)點(diǎn)重合越嚴(yán)重；邊數(shù)k設(shè)置得較小時(shí)查詢(xún)效率較高，因?yàn)楫?dāng)凸多邊形邊數(shù)增加時(shí)，判定凸多邊形是否與Q相交需要花費(fèi)更多的時(shí)間.

圖13展示的是在均勻數(shù)據(jù)集和仿真數(shù)據(jù)集上，改變查詢(xún)范圍Q的大小時(shí)，利用3種索引進(jìn)行FOV查詢(xún)所花費(fèi)的時(shí)間.在實(shí)驗(yàn)中，我們將Q的寬度設(shè)置為500 m，Q的長(zhǎng)度設(shè)置為50 m，500 m，5 000 m，從而使Q的大小呈10倍增長(zhǎng).由圖13可見(jiàn)，對(duì)于不同大小的Q，凸多邊形均表現(xiàn)出較好的查詢(xún)性能.這是因?yàn)橥苟噙呅螛?shù)中節(jié)點(diǎn)內(nèi)無(wú)效區(qū)較小且節(jié)點(diǎn)間的重合區(qū)較小，這樣可以避免訪(fǎng)問(wèn)大量的錯(cuò)誤節(jié)點(diǎn)(錯(cuò)誤節(jié)點(diǎn)為不包含結(jié)果的節(jié)點(diǎn)).

Fig. 13 The effect of the size of Q on query performance圖13 Q的大小對(duì)查詢(xún)性能的影響

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

Fig. 14 Compare of the time cost of building indexes圖14 對(duì)比構(gòu)建索引的時(shí)間

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

Fig. 15 Memory consumption when building indexes圖15 構(gòu)建索引的內(nèi)存消耗情況

5.3 實(shí)驗(yàn)結(jié)果展示與分析

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

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

Fig. 16 Query regions on real datasets圖16 真實(shí)數(shù)據(jù)集上的查詢(xún)區(qū)域

Fig. 17 Query results on real datasets圖17 真實(shí)數(shù)據(jù)集上的查詢(xún)結(jié)果

6 結(jié)束語(yǔ)

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

作者貢獻(xiàn)聲明：苗雪、郭茜提出研究問(wèn)題并設(shè)計(jì)研究方案，還進(jìn)一步負(fù)責(zé)起草論文，苗雪同時(shí)負(fù)責(zé)收集、處理數(shù)據(jù)并進(jìn)行實(shí)驗(yàn)驗(yàn)證；王昭順、謝永紅負(fù)責(zé)最終版本的修訂.