ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (3): 706-719.doi: 10.7544/issn1000-1239.20200689

• 软件技术 • 上一篇    



  1. 1(北京科技大学计算机与通信工程学院  北京  100083);2(材料领域知识工程北京市重点实验室(北京科技大学)  北京  100083)  (
  • 出版日期: 2022-03-07
  • 基金资助: 

Convex Polygon Tree for Indexing Field-of-Views

Miao Xue1, Guo Xi1,2, Wang Zhaoshun1, Xie Yonghong1,2   

  1. 1(School of Computer & Communication Engineering, University of Science and Technology Beijing, Beijing 100083);2(Beijing Key Laboratory of Knowledge Engineering for Materials Science(University of Science and Technology Beijing), Beijing 100083)
  • Online: 2022-03-07
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61602031), the Fundamental Research Funds for the Central Universities (FRF-BD-19-012A, FRF-IDRY-19-023), and the National Key Research and Development Program of China (2017YFB0202303).

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

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

Abstract: Smart device, such as smart phones, can record their geographical positions and optical parameters into image files when capturing photos and videos. We can extract and use the information to restore the sector-shaped geographical area, which is known as the field-of-view (FOV). We store the images together with their FOVs in order to support the spatial queries on images. Typically, a user circles a region on the map as a query, and the computer returns the images which capture the region. In fact, the query is to find the FOVs that intersect with the query region. To make FOV queries fast, an index should be built. However, the existing indexes exploit the sector-shaped feature inadequately. We design a convex polygon tree to index pentagons which are the approximations of sectors. Each tree node is a k\+*-convex polygon, which encloses a set of polygons. The number of sides of the polygon must be no more than k, and the difference between the polygon and its elements should be minimized. We propose a submerging algorithm to compute such k\+*-convex polygons. To build a convex polygon tree, we insert FOVs iteratively. Each time we select a best leaf node for insertion. The selection criteria are to make the dead space and the increasing space as small as possible, and to make the overlap area between the old node and the FOV as large as possible. We also propose an FOV query algorithm based on the proposed convex polygon tree. The experimental results show that the convex polygon tree performs better than the existing indexes.

Key words: spatial query, field-of-view (FOV), convex polygon, tree structure, sector-shaped