一种基于MBR的不确定区域间方向关系建模方法

现实世界中的区域多具有不确定边界,现有基于确定区域的建模方法无法直接处理此类不确定区域间的方向关系.用宽边界表示区域的不确定边界,以区域的最小边界矩形(minimum bounding rectangle,简称MBR)为模型,提出一种基于MBR的不确定区域间方向关系建模方法.利用基于MBR的主方向关系和矩形代数表示不确定区域间方向关系;定义不确定区域间方向关系的相容性复合;并给出一种相容性复合计算方法.

基于MBR的GPS轨迹数据压缩算法

移动对象产生的大量GPS轨迹数据,蕴含了丰富的时间和空间信息。为了减少GPS轨迹数据的存储空间,提高数据分析的效率,针对常用GPS轨迹数据压缩方法不适用于移动设备的问题,本文提出了一种基于MBR的GPS轨迹数据压缩算法,通过Geolife作为样本数据集对该算法进行了测试。实验结果表明该算法对全局GPS轨迹数据和局部GPS轨迹数据均有较高的压缩率和压缩精度,为移动设备的GPS轨迹数据提供了一种有效的压缩方法。

Spark框架下矢量多边形求交算法研究

提出一种分布式内存计算框架Spark下的矢量多边形求交算法,解决了大数据环境下并行矢量多边形求交计算过程中网络数据传输成本高、冗余计算量大的问题。该算法根据空间填充曲线构建空间网格分区,并利用多边形最小外包矩形(MBR)进行网格填充,以传输MBR代替传统算法中直接传输多边形几何体的过程,减少了算法的网络数据传输量。针对复杂多边形跨越多个网格分区的场景,提出一种跨区数据交点定位策略,从而消除跨区多边形的冗余计算。实验结果表明,本文方法能够显著提高并行矢量多边形求交算法的计算效率。

求解简单多边形间最小距离的一个线性时间算法

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。

基于主成分分析的珠宝自动定位及检测方法

针对不规则物体形状特征难以估计的问题,以实现对珠宝的自动测量技术为前提,通过引入主成分分析的概念,提出一种新的对不规则珠宝图像的自动检测方法。该算法首先利用主分量分析提取出目标珠宝图像的主轴,然后根据优化后的主轴方向计算珠宝外接矩形的四个顶点,最后定位出最优外接矩形的位姿从而完成对不规则珠宝轮廓的检测。将所提算法用于真实珠宝图像,结果表明,算法能够准确定位检测出图像中的目标。与利用重心原理结合最小二乘法的方法和以投影为基础计算能量最大值的算法相比,实验图像的主观效果和客观的误差分析都表明了该算法在准确性和鲁棒性的优势。

一种面向不确定数据流的聚类算法

作为大数据的重要组成,产生于传感器、移动电话设备、社交网络等的不确定流数据因其具有流速可变、规模宏大、单遍扫描及不确定性等特点,传统聚类算法不能满足用户高效实时的查询要求.首先利用MBR(minimum bounding rectangle)描述不确定元组的分布特性,并提出一种基于期望距离的不确定数据流聚类算法,计算期望距离范围的上下界剪枝距离较远的簇以减少计算量;其次针对簇内元组的分布特征提出了簇MBR的概念,提出一种基于空间位置关系的聚类算法,根据不确定元组MBR和簇MBR的空间位置关系排除距离不确定元组较远的簇,从而提高聚类算法效率;最后在合成数据集和真实数据集进行实验,结果验证了所提出算法的有效性和高效性.

基于节点分裂优化的R-树索引结构

针对R-树索引空间查询效率低下的问题,提出一种基于节点分裂优化的R-树索引结构:SR-树索引。SR-树索引在节点分裂过程中,通过增加叶子节点的空间数据聚集性来减少叶子节点最小外接矩形的覆盖面积。为了有效降低磁盘读写消耗,SR-树节点在写入索引时,首先将索引树在内存中建好,然后在文件中写入树信息,最后通过递归的方式写入节点。实验结果表明,与R-树索引相比,SR-树索引可以在减少最小外接矩形重叠面积的同时,有效降低查询响应时间,从而达到提高查询效率的目的。

案例索引BCS-Tree及其构建方法研究

为克服现有案例索引方法存在的不足,提出了一种新的索引结构BCS-Tree.首先,对松弛聚类(graph-based relaxed clustering,GRC)算法进行了自适应改进,以克服现有基于聚类方法受初值影响大、只能适应凸形聚类等缺点;其次,将KICA与最小外接矩阵(minimum bounding rectangle,MBR)结合,增强了MBR方法对非线性和非正态分布数据的处理能力;然后,在给出双基点选择方法的基础上,提出了基于改进GRC和双基点聚类分割的BCS-Tree构建方法;最后,基于对查询点和案例数据之间可能分布关系的全面分析,设计了BCS-Tree的查询算法,并结合理论推导和实例验证,对BCS-Tree及其查询算法进行了分析.结果证明,所提的索引构建方法具有较强的参数鲁棒性和适用性,且BCS-Tree及其查询算法具有良好的检索效能.

支持位置追溯的射频识别移动对象索引机制

随着射频通信技术的不断成熟及硬件制造成本的不断降低,射频识别(RFID)技术已开始应用于物品实时监控、跟踪与追溯领域。在供应链应用中,RFID对象数量繁多而且位置经常发生变化,如何从海量数据中查询标签对象的位置及其变化历史已成为供应链追溯亟须解决的问题。针对RFID移动对象特征及追溯查询需求,提出了一种有效的时空索引机制CR-L,并详细讨论了CR-L的结构及维护算法,包括插入、删除、二分裂及惰性分裂算法等。针对对象查询,CR-L利用读写器、时间及对象等三维信息设计了新的最小外界矩形(MBR)值计算原则,将相同读写器在相近时间内探测到的轨迹尽可能聚集于相同或相邻节点。对于轨迹查询,采用单链表将相同对象的轨迹链接起来。实验结果表明,所提索引机制具有较好的查询效率和较低的空间占用率。

PCB自动布线算法介绍

讨论了PCB自动设计中版面图形数据组织和障碍数的建立,比较了链表、二叉树、四维二叉树3种结构的特点。介绍了PCB自动设计 中分解算法、图形相交算法及其在图形数据处理中的应用。

一种新的合成孔径雷达图像船只几何特征提取方法

海上船只监测在海洋交通、渔业管理等领域发挥着重要的作用。高分辨率合成孔径雷达卫星的发射,使船只类型识别成为可能,进一步提高了海洋监测的能力。几何特征是一种重要的船只类型识别特征,本文提出了一种新的合成孔径雷达图像船只几何特征提取方法。与传统方法不同,本文利用最大稳定极值区域算法,取代常用的恒虚警率算法,来检测定位船只。这种方法能够在同等检测率的情况下,有效的降低虚警率,并且具有更快的速度。在几何特征提取过程中,本文提出了改进的最小外接矩形提取方法,这种方法能够有效的抑制旁瓣对船只几何特征提取的影响。实验证明,本文提出的方法能够更快速、准确的提取船只的几何特征。

基于直角多边形近似的R树插入算法

空间查询效率是衡量空间数据库性能的关键,而空间连接查询是最耗时、最重要的空间查询。直角多边形近似是空间数据库中一种新的空间对象近似方法,和MBR近似方法相比,它改进了空间对象的近似精度。文中主要探讨了节点是直角多边形近似的R树插入算法。

MSCR树:一种移动终端电子地图索引结构

现有空间数据索引结构并未同时考虑移动终端电子地图的多比例尺特性及嵌入式设备性能的限制,造成对大区域进行空间查询操作时装载开销过大。深入分析了多种空间索引结构的特点,提出一种新的空间索引结构——MSCR树索引结构,该结构将多级地图中的空间元素线性化,同时以压缩的方式存储空间元素外包矩形数据以提高数据读写效率。实验表明,MSCR树算法有效地提高了查询性能与空间利用率。

基于R树的方向关系表示及方向关系检索

在空间数据库和地理信息系统中,方向关系描述空间数据对象之间的空间顺序关系,构成了重要的用户查询类。然而对方向关系的形成及有效处理所做的工作较少。本文在综合相关知识的基础上,主要讲述二维物体方向关系的定义、基于MBRs表示空间物体间的方向关系以及基于R树对方向关系进行检索三个问题。