一个求解多边形最小面积外接矩形的算法

多边形最小面积外接矩形是地理信息系统和图形学领域一个极其有用的工具,但是其精确求解过程比较困难。首先证明了一个多边形的最小面积外接矩形必定过该多边形凸包的一条边,然后基于该思想提出了一个计算多边形最小面积外接矩形的算法,并对算法的效率进行了分析。最后给出了算法的实验算例,进一步说明了算法的可行性与可靠性。

一种基于面积平衡约束的图斑化简算法

保持综合前后各地类土地面积平衡是土地利用数据综合的基本原则。地类图斑是面积统计的最小单元,用常规的线化简算法不但难以保证图斑的地理特性,而且会给面积统计带来不确定性。该文提出一种能够使图斑化简前后面积保持绝对平衡的化简算法,该算法给出了求取图斑群和岛图斑的地理特征点、几何特征点的相关方法,对被特征点分割的综合子弧段运用直线面积平衡和参数曲线面积平衡两种求取平衡线的方式进行化简,基本原理是综合前后弧段切割它们自身的包络矩形面积比相等,且综合后的弧段须落入综合前子弧段的误差缓冲区内。实验表明,该算法不但能保持图斑的形态特征,而且能保持图斑化简前后面积绝对相等。

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

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

一种基于激光三维成像雷达距离像的目标检测方法

为了提高激光三维成像雷达地面目标的检测效率,提出一种基于激光三维成像雷达距离像的目标检测方法。该方法首先采用基于邻域像素内检测距离反常算法对距离像进行噪声抑制预处理,然后采用基于形态学的地面估计和高程分割算法实现了距离像的地物分割,最后根据感兴趣目标的尺寸特征,采用最小外接矩形估计算法实现了感兴趣目标的快速检测。本文提出的方法充分利用了距离像的高程信息和目标已知的先验知识,不受二维图像中光照灰度变化对目标检测效果的影响以及处理三维海量点云数据对计算速率的影响。实验结果证明,本文提出的方法适用于复杂多变的战场环境下对地面目标进行快速检测,且满足了实时性要求。

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

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

基于凸包及最小面积外接矩形的QR码定位

如何提高二维码图像定位的精度和效率,其关键在于位姿算法。提出了一种快速提取QR条形码位置和角度信息的方法,该算法首先对QR码图像进行预处理,包括灰度化、二值化和二维旋转变换,接着获取初始化后图像边缘的一系列点,并称之为一组点集,计算该点集的凸包及其最小面积外接矩形,从而检测出位置信息和角度信息。实验结果表明,这种方法可以快速确定条码的位置和所在区域,比传统的Hough变换法更加精确快捷,减少占用的系统资源。

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

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

噪声条件下的运动模糊参数同步辨识的新算法

在噪声污染的情况下,匀速直线运动模糊图像频谱中的暗黑色条纹变得模糊甚至消失,根据暗黑色条纹的特征来估计运动模糊参数的方法将失效。由此,提出了一种噪声条件下的运动模糊参数同步辨识的新算法,该算法以运动模糊图像频谱作为研究对象,首先利用区域生长算法提取频谱中白色长条区域的轮廓,再计算其最小面积外接矩形,根据最小外接矩形的长度、宽度及倾斜度等参数同步估计运动模糊参数:模糊方向与模糊尺度。实验结果表明,对不同信噪比、不同模糊方向和模糊尺度的运动模糊图像,该算法可以较精确地估计出模糊参数,且具有很好的抗噪声鲁棒性。

基于视觉对比显著性分析的红外目标算法研究

从图像中自动检测出目标是红外图像应用的一个重要环节,借鉴计算机视觉中对比显著性分析的相关策略和思路,通过模糊C均值聚类和联通分析对图像进行初始分割得到初始分割对象,计算每个初始分割对象在视觉上的突出程度,通过对初始分割对象突出程度的定量化计算实现目标与背景的分离,在此基础上采用基于对象的分析方法,统计目标相关参数,构建目标过滤规则,实现目标的过滤和最终提取。实验结果表明该算法可有效从红外影像中提取目标。

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

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

基于GCP的大规模无人机影像检索方法

鉴于利用无人机影像数据进行高精度测绘及地表三维信息提取时,从具有定位定向信息、数据规模大、影像分布密集等特点的数据集中检索包含地面控制点(ground control point,GCP)的目标影像存在检索速度较慢的问题,提出了基于GCP的影像检索方法。首先,对无人机影像点集构建最小外包矩形与基准坐标系;其次,利用GCP数据构建合适大小的索引矩形(ground control point rectangle,GCP-Rec);最后,依据GCP-Rec对影像数据批量建立索引,最终生成树形索引。效率对比实验表明,该方法能快速完成大规模无人机影像的空间索引构建,提升影像检索效率,且其检索性能优于传统的R树与四叉树等空间索引。影响因素对照实验表明,影像检索效率与GCP数量成反比关系,设定GCP-Rec边长为2.0~2.4倍航带间距时检索精度最优。

多边形分割算法在农村土地确权中的应用

针对农村土地确权工作中遇到的按比例划分地块的现实需求,提出了一种按照面积比例分割简单多边形的算法。该算法通过求取多边形最小外接矩形(MABR)判定多边形总体走势,据此生成初始分割直线,再根据目标子多边形面积与目标面积的差值调整分割线的位置,最终将多边形分割为两个边界合理的子多边形。利用该算法对实测农田地块进行一分为二的面积等分实验,实验结果表明:该算法适用于常见形状的农田地块,分割结果合理,效率高、误差小。

基于分区域自适应阈值Zernike矩的骨签轮廓尺寸测量方法

汉长安城遗址出土骨签数量庞大,基于数字图像技术的骨签尺寸自动测量方法能够提高工作效率。针对骨签纹理繁多、边缘对比度低导致测量精度不高的问题,提出一种基于分区域自适应阈值Zernike矩的骨签图像尺寸测量方法。首先,利用Canny算子进行像素级定位;然后,对称设定边缘有效分区域,以欧氏距离为比例系数计算各个分区域像素点与中心点的加权灰度值,作为各区域Zernike矩提取边缘的判定阈值,提取骨签亚像素级边缘;其次,引入边缘轮廓判别条件剔除无效纹理,获取骨签图像精确轮廓;最后,使用最小外接矩算法计算骨签不规则轮廓,结合相机标定完成骨签尺寸测量。实验结果表明,与其他方法相比,该方法测量的骨签长宽的均方根误差分别降低1.3 mm和1.2 mm,平均相对误差分别降低3%和6.3%,平均绝对误差分别降低1.23 mm和1.08 mm,能够有效提高复杂边缘轮廓的骨签尺寸测量精度。