面向Hilbert八叉树的邻近格元计算算法

为提高线性八叉树邻近格元计算效率,利用Hilbert码标记格元,提出一种邻近格元Hilbert码快速计算方法。以Hilbert基元曲线为基础,引入状态向量的概念以记录Hilbert曲线对同属于一个父格元的所有子格元的填充顺序,从而建立状态向量的层级演进与退化函数,得到状态向量在m阶与m+1阶曲线中的层级映射关系,最终利用状态向量及其层级演进与退化函数实现邻近格元Hilbert码的计算。结果表明,所提算法计算结果正确;状态向量计算速度随层级提高而降低,在第20层级上1 ms内可完成4 201个格元的计算,对后续邻近格元计算影响较小;在指定层级上同等数量的邻近格元计算中,该算法的速度明显优于现有Morton码转换算法,在第15层级上百万级规模的邻近格元计算中,该算法的速度约为现有Morton码转换算法的2.1~2.4倍;在不同层级的百万级规模邻近格元计算中,该算法计算速度相比现有Morton码转换算法的提升倍数随层级提高而增大,在第20层级上该算法的效率提升达到2.6倍。     

自适应阈值的基础矩阵估计算法

针对RANSAC算法在估计基础矩阵过程中需要人为设定阈值的问题,该文提出一种自适应阈值的基础矩阵估计算法。该算法首先引入ORSA算法,计算内点集以及基础矩阵,随后将得到的内点集与基础矩阵作为最小中值算法的初始值做进一步加权优化,在保证基础矩阵估计精度的前提下得到更好的内点集。其中,利用ORSA算法估计时通过计算误匹配警报数(NFA)值评判估计精度,舍去了RANSAC算法中人为设定阈值的步骤;利用最小中值算法加权优化的过程中采用最小化误差中值的方式,避免人为设定阈值。实验结果显示,该算法在保证基础矩阵估计精度的同时,能够获得最佳的内点集,且具有一定的抗噪声能力。     

三维Hilbert曲线层级演进模型与编码计算

格网单元的编码计算是全球离散网格系统的核心,支撑着网格快速索引及应用分析的高效计算。Hilbert曲线具有聚簇性高、连续性强的特点,是研究设计全球离散网格编码的重要工具。利用Hilbert曲线进行格元编码实现了坐标等效降维表达,但是对Hilbert曲线不同层级之间的变换关系、一维Hilbert码如何刻画格元多维空间结构与关系等网格编码基础理论问题的研究尚不完备。本文以八叉树立体网格中三维Hilbert曲线层级演进关系为突破口,使用状态矩阵与演进矩阵构建层级演进模型,进而分别设计笛卡儿坐标至Hilbert码计算以及邻近格元Hilbert码计算方法。与现有算法对比,本文算法以层级演进模型为理论基础,避免了烦琐迭代步骤以及转换步骤,算法流程简明直接。试验结果表明,本文笛卡儿坐标至Hilbert码计算效率较迭代算法提高为7%~23%,邻近格元Hilbert码计算效率较转换算法提高4.0~4.5倍。