用于索引视域的凸多边形树

苗 雪 郭 茜,2 王昭顺 谢永红,2

1(北京科技大学计算机与通信工程学院 北京 100083)

2(材料领域知识工程北京市重点实验室(北京科技大学) 北京 100083)

智能手机在拍摄照片和录制视频时会在图片文件中嵌入设备的地理位置和参数信息.Ay等人[1]提出使用视域(field-of-view, FOV)描述图片所反映的地理区域，视域是由拍摄地点loc、相机朝向θ、可视角度α和可视距离r决定的扇形区域，如图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)，查询范围是一个矩形区域，我们称其为面向FOV的窗口查询(简称为FOV查询).现有查询算法有2种：基于R*树[5]及其变体的查询算法[6-8]和基于网格索引的查询算法[9].R*树索引的对象是FOV的最小包围矩形，由于矩形和扇形形状差异较大，导致节点内的无效区(dead space)较大；OR树[8]是R*树的变体，它索引的对象是FOV的圆心，所以有时会出现节点间重合较大的情况；Ma等人[9]提出了三级网格索引，当FOV的可视距离差异较大时，查询会出现大量冗余的候选网格.

Fig. 2 Convex polygon tree图2 凸多边形树

本文设计了凸多边形树来提升FOV查询的性能.凸多边形树索引的对象是包围FOV的最小五边形，如图2(a)中的f1～f9.距离较近的五边形聚合在一起构成上层节点，如图2(a)中的粗实线多边形L1由f1，f2，f3聚合而成，依此类推其余的五边形可聚合成更大的五边形L2，L3，L4.与R*树类似，凸多边形树逐层向上将较近的多边形聚集在一起直到根节点，并且每个节点对应的凸多边形边数小于等于k，如图2(a)中的限定k=5.

为了找出可以包围一组多边形的大多边形，我们提出了淹没算法，它一方面控制大多边形的边数，当最小包围多边形的边数大于k时，算法将边数减少到k；另一方面它保证大多边形中无效区最少.我们构建凸多边形树的过程是逐个插入新的FOVfnew，算法保证插入fnew之后新叶子节点中引入无效区的比重小于ε无效，同时我们也考虑fnew与旧叶子重合区的比重V重合，以及新叶子增加区的比重V增加.如果fnew不适合插入任何一个叶子，则将其暂存入等待队列中.在查询时，除了对凸多边形树进行剪枝操作以减小搜索空间之外，我们还提出角度分区筛选算法找出候选结果集合.实验结果表明，虽然创建凸多边形树比创建R*树花费的时间多，但基于凸多边形树的FOV查询算法比已有查询算法的查询效率更高.

本文工作的主要贡献有3个方面：

1) 使用五边形近似FOV，提出了索引此种五边形的凸多边形树.由于树的节点为多边形，为了保证孩子节点数量稳定，提出了淹没算法来控制多边形的边数.

2) 设计了构建凸多变形树的算法，包括节点插入算法和节点分裂算法.为了优化树的结构，提出了使用等待队列的方法.

3) 制作了仿真数据集并在仿真数据集上对算法进行了性能测试.

1 相关工作

在空间数据库领域中，对于可定位影像数据的研究工作主要包括影像数据视域的建模方法和影像数据的空间查询技术.

1.1 可定位影像数据的视域建模方法

为了建立影像和地理区域之间的映射关系，我们利用影像文件中内嵌的地理坐标和光学参数来重构影像所反映的地理区域.但是，拍摄设备是由多个透镜组成的复杂光学系统，我们很难准确还原光路并推算出影像对应的地理区域.一种常见的做法是忽略拍摄设备的高度并且把拍摄过程简化为小孔成像，使用扇形视域来近似地描述影像对应的地理区域[1,10].随着无人机技术的广泛应用，也有研究者使用二维平面中的四边形来近似地描述无人机在地面上的视域[11-12].这些建模方法将视域简化为二维平面图形，使得我们可以从空间数据查询的角度来搜索图片.比如Kim等人[13]设计并开发了TVDP平台，并利用空间数据处理技术对可定位城市影像进行查询和分析；Toyama等人[14]开发了一个用于图片搜索的数据库，它通过拍摄位置的经纬坐标和时间戳索引大规模图像数据；Li等人[15]提出了一种估计照片视角方向的实用方法，它可以找出非位置感知设备拍摄的具有错误姿势的照片.

1.2 可定位影像数据的空间查询

在空间数据库中，可定位影像数据查询问题的实质是找出与用户输入的查询区域相交的视域.根据应用场景的不同，视域的形状可以抽象为扇形[8]或四边形[11].这类基本查询找出所有与查询区域相交的视域，并将它们全部作为结果返回给用户.为了提升结果的质量，Alfarrarjeh等人[16]提出根据视域对查询区域的覆盖程度以及视域的朝向对查询结果进行排序，Ay等人[17]提出了衡量连续视域与查询区域相关性的方法.

为了提高查询效率，针对不同的查询问题，研究者们提出了不同的索引技术.根据索引对地理信息的利用程度，我们将其分为两大类：1)建立索引时仅考虑拍摄设备的地理位置，如Alfarrarjeh等人[18]同时考虑设备的位置和影像的语义为图片建立了索引；2)根据设备的视域来构建索引，如Ay等人[1]使用R*树来索引扇形视域(即FOV).然而，直接使用R*树索引FOV会产生较大的节点内无效区和节点间重合区.

为了进一步提升查询效率，Lu等人[8]提出使用OR树来索引FOV.OR树是R*树的变体，它的节点中不仅存储了包围若干拍摄位置(即FOV圆心)的最小边界矩形，而且也存储了这些FOV的方向范围和可视距离范围.构建OR树的策略是尽量将拍摄位置靠近、可视距离相似和可视角度范围相似的FOV放入同一个节点中.这种构建策略的缺点是节点间的重合较大，并且树的结构取决于FOV的插入顺序.

本文在Lu等人[8]工作的基础上，提出了一种新的FOV索引，即凸多边形树，用于支持FOV查询.虽然凸多边形比矩形更适合包围扇形等不规则形状，但多边形边数不确定以及形状不规则等因素为索引的构建带来了困难和挑战.本文将在第3节详细介绍构建凸多边形树的方法.

1.3 特定场景下的影像数据空间查询

为了更好地索引视频帧在二维平面空间中的视域，Kim等人[6]提出了GeoTree.GeoTree的叶子节点中存储的是用于包围连续视域的最小倾斜矩形.GeoTree适用于索引视域方向变化不剧烈的视频.为了更准确地拟合拍摄设备的运动轨迹，Lee等人[7]提出GeoVideoIndex，它根据设备位置的变化趋势构造包围矩形，使其可以包围住更多的FOV，从而减小了索引占用的存储空间和索引的构建时间.Ma等人[9]提出一种基于可视场景、设备位置和视域方向的三级网格索引，这种网格结构适用于索引可视距离较接近的视域.针对无人机的高空拍摄场景，Lu等人[11]提出了用于索引四边形视域的TetraR树.

2 问题定义与解决方法概述

本节给出了FOV查询的正式定义并给出了FOV查询的解决方法概述.该过程主要包括2个阶段，即索引构建阶段和查询处理阶段.

2.1 问题定义

在二维欧氏空间中，FOV由4个参数决定：设备位置loc、镜头朝向θ、最大可视角度范围α和最大可视距离r.前2个参数由设备自带的GPS和方向传感器自动获取，后2个参数可由镜头本身参数推算得到.本文使用四元组(loc，αb，αe，r)描述FOV，其中αb和αe是以顺时针为序的FOV可视角度范围的起始角度和终止角度.

定义1.FOV查询.在二维欧氏空间中，用户指定矩形查询区域Q，系统从已有的FOV集合F中找出所有与Q相交的FOV.

如图1所示，用户指定了可以恰好包围住雕像的矩形查询框Q，系统判断只有照片img1，img2，img3的FOV与Q相交，所以系统会将这3张照片返回给用户.

2.2 解决方法概述

解决FOV查询的基本方法是检查每个FOV是否与查询区域Q相交，并且返回与Q有交集的FOV作为结果.这种方法需要遍历整个FOV集合，查询效率较低.为了提高查询效率，我们提出使用凸多边形树索引FOV的方法来减小搜索空间.在预处理阶段，我们为整个FOV集合构建凸多边形树.在查询处理阶段，我们使用深度优先搜索的方式遍历凸多边形树，在遍历的过程中剪掉不可能包含结果的节点.图3展示了索引构建和查询处理的主要流程.

Fig. 3 The overview of our solution图3 解决方法概述图

在索引构建阶段，我们使用逐一插入FOV的方式来构建凸多边形树.凸多边形树的结构与R*树类似，与R*树不同的是它的节点对应的区域不是包围矩形而是包围凸多边形.为了保证孩子节点数量稳定，我们提出淹没算法使包围凸多边形的边数不超过k(3.1节将详细介绍淹没算法).在插入某个FOVf时，我们根据V无效，V增加和V重合这3个评判标准找到适合插入f的叶子节点Nopt，然后将f插入到Nopt中，并自底向上更新Nopt,Nopt的父亲节点，直至根节点.如果我们没有找到适合插入f的叶子节点，则将f放入等待队列中.如果在插入的过程中出现孩子节点的数量超过Mmax的情况，则执行节点分裂操作(3.2节将详细介绍节点的插入和分裂策略).

在查询处理阶段，用户输入矩形查询范围Q(x1，y1，x2，y2)，其中(x1，y1)和(x2，y2)分别为Q的左下顶点和右上顶点坐标.我们从根节点开始自上而下遍历凸多边形树.当下降至某个节点N时，判断其是否与Q相交，如果相交，就下降到N的孩子节点.最后，将与Q有交集的所有FOV对应的照片作为结果返回给用户.

以图1为例，在索引构建阶段，我们构建一个凸多边形树索引所有的FOV.在查询处理阶段，当用户输入查询范围Q(矩形框)之后，我们用深度优先搜索的方式遍历凸多边形树，在遍历的过程中剪掉与Q不相交的节点，并将与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*多边形来包围一个多边形集合，用以构成树的节点.

定义2.k*包围多边形.给定一个多边形集合F={f1，f2，…，fn}，如果一个边数不超过k的多边形可以包围住F中所有的多边形，并且使无效区最小，则此多边形被称为集合F的k*包围多边形，用BPk(F)表示.

这里无效区是指属于BPk(F)但不属于F的区域，即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}，每个叶子节点负责m个fi，它存储包围这些fi的k*多边形以及指向这些fi的指针.每个叶子节点的上一层节点负责m个叶子节点，它存储包围这些叶子节点的k*多边形以及指向这些叶子节点的指针，依次往上直到根节点.跟R*树类似，凸多边形树中每个叶子节点(或中间节点)包含的FOV(或孩子节点)数目m在Mmin和Mmax之间且根节点至少有2个孩子节点.

图2的例子中有9个FOV的包围五边形{f1，f2，…，f9}，其中{f1，f2，f3}由叶子节点L1负责，即L1用更大的k*多边形(k=5)包围了{f1，f2，f3}.同理，{f4，f5}由叶子节点L2负责，{f6，f7}由叶子节点L3负责，{f8，f9}由叶子节点L4负责.叶子节点{L1，L2，…，L4}又进一步聚合成2个更大的k*多边形N1和N2，而中间节点{N1，N2}又进一步向上聚合成根节点root，最终形成如图2(b)所示的树形结构.

3.1 淹没算法

本节提出淹没算法来找出包围一组多边形集合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.

③ 在不会发生混淆的情况下，FOV除了指视域扇形本身之外，也指包围此扇形的凸五边形.

多边形的新增区域为新顶点与2个旧顶点组成的三角形，如图5(a)中的Δp3p34p4.此三角形为无效区，因为此三角形与F中的所有多边形都没有交集.为了尽量减小节点的无效区，我们每次选择淹没当前多边形的一条最优边，这里最优边的含义是如果淹没它那么引入的三角形最小.如图5(b)所示，我们首先淹没边p2p3，因为淹没它引入的三角形最小.在得到新的多边形之后，我们选择淹没最优边p8p9，依此类推，我们淹没p5p6，然后淹没p7p89，其中p89为淹没边p8p9时生成的新顶点.最后，算法得到k=5的k*多边形.

算法1.淹没算法.

输入：BP，k；

输出：BPk.

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

② whileBP边数大于kdo

③ 遍历L找出最优边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②的面积(行①).然后，算法每次淹没一条最优边(行②～⑨)，直到多边形边数是k为止.每次循环时，算法遍历整个L找出最优边(行③)，求出新顶点pnew(行④)并更新多边形的顶点集合BP(行⑤).此外，算法还要将被淹没的边及其三角形从L中去掉(行⑥)，并更新两条旧边(行⑦⑧).最后，算法得到k*多边形BPk(行⑩).

在使用算法1时，需要注意多边形可能存在无法被淹没的边.如图5(b)所示，假设我们想淹没边p56p789，而p1p789的延长线和p4p56的延长线无交点.遇到此种情况时，我们将对应的三角形面积设置为无穷大，让此种边不会被选中.

3.2 节点插入策略

我们采用逐个插入FOV③的方式构建凸多边形树.插入一个FOVf分为2步：1)自顶向下找出插入f的最优叶子节点Nopt，这步被称为寻找父节点；2)将f插入到Nopt中并自底向上更新Nopt,Nopt的父节点，直至根节点，这步被称为更新父节点.在寻找父节点时，根据V无效，V增加和V重合三个评判标准找出最优叶子节点.V无效用于衡量如果将f插入节点N，那么新节点Nnew会出现多少无效区，即：

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

(1)

其中，AreaNnew表示包围f和N的k*多边形的面积，AreaN∪f表示N∪f本身的面积，Areaf表示f本身的面积.如图6所示，旧节点N为实线填充的区域，f为无任何填充的区域，新节点Nnew为既包含N也包含f的多边形，而虚线填充的区域为无效区.V增加用于衡量新节点Nnew相比于原节点N增加了多少面积，即:

V增加=AreaNnew-AreaN，

(2)

其中,AreaN表示N本身的面积.V重合用于衡量f与N的重合区域的大小，即:

V重合=AreaN∩f/Areaf.

(3)

其中,AreaN∩f表示f与N重合区域的面积，如图6所示的粗五边形区域.

Fig. 6 Display of the old node N, FOV f, and new node Nnew图6 旧节点N,FOV f和新节点Nnew的展示

我们寻找最优叶子Nopt的策略是，优先筛选出满足V无效≤ε无效(条件A)的叶子LA.此种叶子Li∈LA的优点是f插入Li后引入的无效区较小.然后，我们分3种情况处理：

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

1) 如果此种叶子只有1个，即|LA|①=1，则此叶子即为最优叶子Nopt，我们将f插入Nopt.

2) 如果没有此种叶子，即|LA|=0，则说明f远离当前的所有叶子，我们创建一个仅包含f的新叶子Nopt，并将其插入到合适的上层节点中.此处上层节点是指叶子节点的上一层节点.

3) 如果此种叶子有多个，即|LA|≥2，我们根据V重合进一步从LA中筛选出V重合≥ε重合(条件B)的叶子LB.筛选此种叶子的动机是：f插入与其重合较大的叶子后，会使得新叶子与其兄弟叶子的重合较大.

根据集合LB中元素的数量，我们分3种情况讨论：

① 如果此种叶子只有1个，即|LB|=1，则此叶子即为最优叶子Nopt，我们将f插入Nopt.

② 如果没有此种叶子，即LB=∅，我们从LA中找出V增加最小的叶子作为最优叶子Nopt，原因是f插入此叶子后引入的新增面积较少，也会在一定程度上减小新叶子与其兄弟叶子之间的重合.

Fig. 7 Waiting list图7 等待队列

算法2描述了将一个FOVf插入到凸多边形树的过程.首先，算法根据条件A筛选出叶子集合LA(行①).筛选的过程是从根节点开始向下搜索，将符合条件A的孩子节点展开，直到找出所有符合条件A的叶子为止.此处可以逐层展开中间节点的依据是如果父节点不满足条件A，则其孩子节点必然不满足条件A.然后，算法根据LA中元素的数量分3种情况处理：1)行②～⑤对应情况2，其中算法找出V无效最小的节点作为合适的上层节点，也就是说将新叶子Nopt插入到此节点后引入的无效区最小(行④)；2)行⑥～⑧对应情况1，其中行⑧将f插入到Nopt之后，要逐层向上更新父节点，直到根节点为止；3)行⑨～对应情况3，算法首先根据条件B进一步筛选LA中的叶子得到集合LB(行⑩)，根据LB集合中元素的个数又细分为3种情况.行～对应情况3中①；行～对应情况3中②；行对应情况3中③，其中W表示等待队列.

算法2.节点插入算法.

输入：凸多边形树的根节点root、准备插入树中的FOVf；

输出：插入f之后的树.

①LA←满足V无效≤ε无效的叶子节点；

② if |LA|=0 then

③Nopt←仅包含f的新叶子节点；

④ 将Nopt插入到合适的上层节点中；

⑤ 向上更新父节点一直到root；

⑥ else if |LA|=1 then

⑦Nopt←LA中仅有的叶子节点；

⑧Nopt←Nopt∪{f}，向上更新父节点一直到root；

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

⑩LB←从LA中找出满足V重合≥ε重合的叶子；

节点分裂方法：在使用算法2时需要注意，当新FOV(或新孩子节点)插入到叶子节点(或中间节点)N时，N可能会溢出.我们处理溢出的方法是将N分裂为2个新节点N1和N2.分裂的方法为：首先，我们从N的孩子中选取2个关键孩子c1和c2，它们能够成为关键孩子的原因是包围它们的k*多边形面积最大.关键孩子c1和c2分别成为N1和N2的第1个孩子.然后，我们将剩余的孩子分配给N1和N2，分配规则是每次选择1个V增加最小的孩子放入N1(或N2)中.在此过程中，我们需要确保N1和N2的孩子数目达到Mmin.算法3展示了将N分裂为N1和N2的过程.

算法3.节点分裂算法.

输入：溢出节点N；

输出：分裂后的节点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，则遍历凸多边形树找出最优叶子节点Nopt并将fi插入Nopt；如果元素中包含多个FOV，则生成对应的叶子节点Li，并将其插入到合适的上层节点中.

4 查询处理

本节介绍凸多边形树上的FOV查询处理算法.从根节点开始向下搜索可能存在结果的子树，即只有当孩子节点与查询范围Q有交集时才下降到此节点继续搜索.当下降到某个叶子节点L时，检查L包含的每个FOV(扇形)是否与Q存在交集.

函数1.FOV查询函数FovQuery(N,Q).

输入：凸多边形树的节点N、查询框Q；

输出：与Q有交集的FOV.

① ifN不是叶子节点then

② forN的每个孩子节点cido

③ ifci∩Q不为空then

④FovQuery(ci,Q)；/*递归调用*/

⑤ end if

⑥ end for

⑦ else/*N是叶子节点*/

⑧ forN的每个FOVfido

⑨ iffi∩Q不为空then

函数1描述了FOV查询的具体过程，即函数FovQuery().我们采用递归的方式对凸多边形树进行深度优先遍历，在主程序中传入函数FovQuery()的参数是root和Q，其中root是凸多边形树的根节点.执行函数FovQuery()时，首先判断节点N是否为叶子节点(行①).如果不是叶子节点，则将与Q有交集的孩子节点作为参数递归地调用函数(行②～⑥).如果是叶子节点，则判断节点中的每个FOV是否与Q有交集(行⑨)，并输出有交集的FOV(行⑩).

我们提出角度分区筛选算法以便快速地找出与Q有交集的FOV(行⑨).算法根据Q的位置将空间划分为9个区域，如图8所示.如果FOV的圆心位于Q之内，则其肯定与Q有交集.如果FOV圆心位于其他分区内，则判断两式是否同时成立:

MinDist(loc,Q)

(4)

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

(5)

Fig. 8 Angle partition filtering method图8 角度分区筛选方法

式(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)同时成立，则继续判断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 角度分区筛选方法的证明

5 实 验

本节提出了生成仿真数据集的方法，并利用此数据集进行了算法性能验证实验.在实验中对比了凸多边形树、R*树和OR树的构建效率，并且对比了这3种索引对FOV查询性能的影响.此外，我们展示和分析了在真实数据集上的查询结果.

5.1 实验环境设置和仿真数据集生成

实验平台是Intel®CoreTMi5-8300H CPU(2.30 GHz)，8 GB内存，Win10专业版操作系统.实验中的所有算法均使用Java语言实现.实验中测试了节点扇出值等因素对索引构建和查询性能的影响.实验中使用了3种数据集：1)均匀分布的数据集，即FOV的圆心在空间中随机分布，FOV的数量为103，104，105，依次令S1，S2，S3表示这3个均匀分布数据集.2)仿真数据集，为了模拟真实生活中的拍照行为，我们根据常用拍照设备的光学参数生成了大量符合实际情况的FOV.在二维空间中摆放这些FOV时，我们让其圆心(即拍摄位置)聚集在某些热门区域并且零散分布在冷门区域，以此来模拟现实生活中热门景点的照片较多而冷门区域的照片较少的现象.图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个区间中随机选取α和r的值，镜头朝向θ从[0°，360°)中随机选取.我们在空间中随机生成了若干不相交的矩形作为热门区域的边界，让h%的FOV圆心落入这些热门区域中，让(1-h%)的FOV圆心落在热门区域之外，其中仿真数据集D1中h%约为99%，D2和D3中h%约为92%.

5.2 算法性能实验分析

图11展示了在均匀数据集和仿真数据集上改变节点扇出值Mmax时，基于3种索引的FOV查询效率对比.由图11可见，当节点扇出值为40时，基于凸多边形树的FOV查询效率较高；无论在真实还是在仿真数据集上，当节点扇出值变化时，在凸多边形树上进行FOV查询比在另外2种树上更节省时间.

Fig. 12 The influences of different parameters on FOV query performance图12 不同参数对FOV查询性能的影响

图12展示的是在均匀数据集和仿真数据集上，当参数ε无效,ε重合和k变化时，在凸多边形树上进行FOV查询所花费的时间.由图12可见，当ε无效设置的较小时查询效率较高，因为较小的ε无效可以有效控制无效区的面积；在较大数据集上ε重合对性能的影响较明显，因为数据集越大节点重合越严重；边数k设置得较小时查询效率较高，因为当凸多边形边数增加时，判定凸多边形是否与Q相交需要花费更多的时间.

图13展示的是在均匀数据集和仿真数据集上，改变查询范围Q的大小时，利用3种索引进行FOV查询所花费的时间.在实验中，我们将Q的宽度设置为500 m，Q的长度设置为50 m，500 m，5 000 m，从而使Q的大小呈10倍增长.由图13可见，对于不同大小的Q，凸多边形均表现出较好的查询性能.这是因为凸多边形树中节点内无效区较小且节点间的重合区较小，这样可以避免访问大量的错误节点(错误节点为不包含结果的节点).

Fig. 13 The effect of the size of Q on query performance图13 Q的大小对查询性能的影响

图14展示了当数据集大小或节点扇出值变化时，构建R*树、OR树、凸多边形树所花费的时间.如图14(a)所示，在3个数据集上构建R*树花费的时间少于构建凸多边形树和OR树所花费的时间；当数据集较小时，构建3种索引花费的时间差不多；但随着数据集增大，构建凸多边形树和OR树所花费的时间显著增加，构建OR树的时间增幅比构建凸多边形树的时间增幅要大很多.这是因为在构建R*树和凸多边形树时，节点的插入和分裂不需要复杂的计算，而构建OR树时节点插入和分裂需要大量的复杂计算并且在节点插入和分裂过程中需要动态更新节点中附加的可视距离和方向信息.如图14(b)所示，当节点扇出值变化时，凸多边形树的构建时间与R*树的构建时间相近，R*树的构建时间最少，OR树的构建时间最多.

Fig. 14 Compare of the time cost of building indexes图14 对比构建索引的时间

图15展示了当数据集大小和节点扇出值变化时，构建3种索引的内存消耗情况.如图15(a)所示，当数据集大小变化时，构建OR树消耗的内存最多，构建R*树消耗的内存最少，而构建凸多边形树消耗的内存位于两者中间.当数据集较小时，构建3种索引的内存消耗相似；当数据集增大时，构建R*树和凸多边形树所需内存的变化不明显，而构建OR树所需的内存明显增大.这是因为R*树节点中仅存储包围矩形和孩子节点指针信息，由于存储的信息较简单，所以内存消耗较小；OR树中除了存储相机位置的包围矩形之外，还存储了节点所包含的FOV的可视距离和方向信息，所以内存消耗较大；凸多边形树中仅存储了节点的包围凸多边形，并且凸多边形的边数不超过k，因此内存消耗相对较小.如图15(b)所示，当节点扇出值变化时，构建R*树的内存消耗最少，构建OR树的内存消耗最多.

Fig. 15 Memory consumption when building indexes图15 构建索引的内存消耗情况

5.3 实验结果展示与分析

实验中用到的真实数据集是使用智能手机采集的，包含100张照片.由于实验中使用的智能手机仅能将拍摄位置和光学参数嵌入到照片文件中，而不能获取拍摄角度，所以拍摄角度是使用手机中自带的指南针记录的.图16中的气球标出了部分拍摄位置.

如图16所示，用户在地图上圈定了查询范围Q1，Q2和Q3，系统要找出拍摄到这3个区域照片.如图17(a)～(d)为拍摄到区域Q1的照片，图17(e)(f)为拍到区域Q2的照片，图17(g)～(j)为拍到区域Q3的照片.图16中的被圆圈圈出的气球标出了查询结果的拍摄位置.以Q3为例，虽然照片No.15的拍摄位置离Q3较远，但它的FOV覆盖到了Q3，使其成为查询结果.虽然照片No.42的拍摄位置比No.15的拍摄位置更近，但由于拍摄时没有朝向Q3，它的FOV未能覆盖到Q3，所以它没有成为查询结果.

Fig. 16 Query regions on real datasets图16 真实数据集上的查询区域

Fig. 17 Query results on real datasets图17 真实数据集上的查询结果

6 结束语

本文提出了索引FOV(扇形)的凸多边形树，它的节点形状为k*多边形.为了构建k*多边形，我们提出了淹没算法.构建凸多边形树时，我们使用将FOV逐个插入的方法.为了选择最优叶子节点将FOV插入，我们提出了根据无效区域大小(V无效)、重合区域大小(V重合)、增加区域大小(V增加)三个因素选择叶子节点的方法，并提出了将不适合插入的FOV暂存入等待队列中的方法.同时，我们也提出了在凸多边形树上进行FOV查询的算法，并在均匀数据集和仿真数据集上对算法进行了实验和性能分析.

作者贡献声明：苗雪、郭茜提出研究问题并设计研究方案，还进一步负责起草论文，苗雪同时负责收集、处理数据并进行实验验证；王昭顺、谢永红负责最终版本的修订.