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

摘要：

智能手机等设备在拍摄照片和录制视频时会将拍摄位置和光学参数记录到影像文件中,可以提取并利用这些信息,在二维平面空间中还原出图片所对应的扇形视域(field-of-view,FOV).将影像文件及其对应的FOV存储在计算机中,用来支持用户对影像文件的空间查询.一种典型的空间查询是用户在地图上指定查询区域,计算机找出拍摄到这个区域的影像返回给用户,其实质是找出与查询区域存在交集的FOV.为了提升查询效率,需要设计合理的数据结构来索引FOV.然而,现有的索引结构没有充分利用FOV的形状特点.使用五边形近似描述FOV,并设计凸多边形树来索引五边形.树的节点是k*凸多边形.k*凸多边形是包围一组多边形的最佳多边形,它的边数不超过k并且无效区域最小,即它本身与其内部元素的差集最小.提出了淹没算法来找出这样的包围多边形.在构建凸多边形树时,将逐一插入FOV,为每个待插入FOV选择最优叶子节点的标准是让FOV插入后新节点的无效区较小,新节点的增加区较小,并且旧节点与FOV的重合区较大.同时,提出了基于凸多边形树的FOV查询算法.实验结果表明凸多边形树与现有索引相比可以提升查询效率.

关键词：空间查询、视域、凸多边形、树形索引、扇形

所属期刊栏目：59

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金;中央高校基本科研业务费专项;中央高校基本科研业务费专项;国家重点研发计划

在线出版日期：2022-04-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：706-719