高效前缀约简的三维Hilbert空间填充曲线编解码算法

3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性。为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率。理论上证明:当编码或解码一个k阶的窗体(窗体内总共含有2k×2k×2k个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法,编解码时间复杂度从O(k)降低到了O(1)。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。

基于GM模型和Hilbert空间填充曲线的图象压缩方法

本文提出了一种新的基于灰色模型 GM(1,1)和 Hilbert空间填充曲线的灰度图象压缩方法 .我们利用 Hilbert空间填充曲线来选取模型化序列中的象素数据 ,并据此使用 GM(1,1)模型化图象象素 .由于 Hilbert曲线是一种能够最好地保持空间点的局部邻接性的扫描曲线 ,因此基于 Hilbert曲线的这种数据选取方法能改进图象的压缩比并且显著地降低编码误差 .实验结果表明 ,本文给出的方法能获得误差小于 4%且压缩比小于 10 %.

基于空间填充曲线的动态负载均衡算法

针对Web集群系统中服务器的数量不断增加、负载指标动态变化的特点,为实现均衡的分配请求,提出一种使用空间填充曲线来实现动态负载均衡的算法。利用空间填充曲线可高效得将高维数据映射到一维索引的特点,使均衡器根据实时收集的各项负载指标快速定位到最优编码的服务器。实验结果表明,该算法能有效地缩短请求响应时间,提升了集群系统的整体性能,在大规模集群系统中均衡效果更好。

基于空间填充曲线走向的线条图像生成方法研究

以线条为微观图案而线条宽度与图像灰度值相关的图像,通常采用的线条走向较为单一。为使线条走向富有变化,采用Hilbert空间填充曲线控制线条的走向,并根据图像在微观位置上的像素灰度值设置线条的宽度,用PostScript语言编程生成线条图像。生成的线条图像在宏观上符合原图像的灰度变化,而微观上具有某种程度的"置乱"的线条图案效果。

空间索引技术及其GIS应用综述

空间索引技术可提供高效的空间数据组织与管理方式,以支撑海量空间数据的挖掘与分析。针对当前空间索引存在的知识体系不明晰、选择难等问题,该文通过文献调查法和CiteSpace工具,依据空间划分及映射方法将空间索引划分为基于树结构、格网、空间填充曲线和地址编码的空间索引四大类,并综述其原理、空间结构、适用范围及在GIS领域的应用,最后对空间索引在数据组织、高效计算、可视化、可靠性等方面的研究进行展望。结论如下:基于树结构的空间索引最具普适性且可以处理多维度及多层次的数据,查询性能依赖于树结构的平衡性及数据的分布;基于格网的空间索引可以均匀划分空间以便于高效范围查询,却不适用于非结构化或动态数据集;基于空间填充曲线的空间索引可以在实现维度压缩的同时保持局部邻近性,但插入或删除数据可能导致整个曲线的重构难以频繁更新;基于地址编码的空间索引将语义地址信息转化为编码信息,便于高效检索,然而语义地址匹配仍存在较大误差和不确定性。研究结果可为空间数据组织和结构设计提供参考。

N维Hilbert曲线生成算法

H ilbert曲线描述了一种多维空间与1维空间一一映射的方法,在图像处理、多维数据索引等领域有着重要的地位。但因为高维H ilbert曲线的复杂性,对高维H ilbert的相关算法研究很少。提出了产生N维H ilbert曲线的一个新算法。该算法基于静态演化规则,自底向上地分析N维H ilbert曲线编码规律,实现N维H ilbert曲线的编码生成。与现有的算法相比,本文算法易于实现。实验结果表明,该算法具有更好的计算性能。

N维Hilbert编码的计算

针对高维Hilbert曲线的复杂性问题,给出了一种N维Hilbert码计算方法.其基本思想是面向一个称为基因的静态演化规则表,根据基因信息进行相应的坐标变换,编解码始终依照Hilbert单元的映射特征进行映射转换;在逐层编解码过程中,把不断变化的映射形态转成固定的Hilbert单元映射方式,同时采用二进制位操作进行计算,从而实现高效的N维Hilbert映射转换.

Hilbert曲线层级演进关系

网格编码代数是当前全球空间网格研究中的难点,也是推动全球空间网格从数据组织管理框架发展成为新一代空间分析模型的理论基础。Hilbert曲线是设计全球空间网格单元编码的重要工具。本文以Hilbert曲线序列码作为八叉树立体网格单元的唯一编码,由Hilbert曲线数学性质推导得到网格单元Hilbert码的层级演进关系表,进而设计了用于网格编码代数运算的若干操作算子,为构建全球空间网格分析理论与方法提供参考。

基于三维Hilbert曲线扫描的图像置乱

Hilbert曲线的空间填充性质使得它可用于图像置乱.针对二维Hilbert曲线扫描波动性相对较小以及少数几次置乱后仍达不到较好置乱效果的弱点,提出将二维图像堆积成三维矩阵,并利用三维Hilbert曲线产生的扫描矩阵进行图像置乱.数值实验结果表明,三维Hilbert曲线扫描的置乱效果比二维好,算法对于剪切、JPEG压缩、噪声、涂鸦等攻击具有较好的鲁棒性.

融合多元经验模态分解与Hilbert空间填充曲线的sEMG处理方法

基于卷积神经网络(convolutional neural network, CNN)的表面肌电信号(surface electromygraphy, sEMG)手势识别算法通常将一维sEMG转换成二维肌电图作为CNN的输入。针对sEMG瞬时样本量偏少、以及一维sEMG转换成二维肌电图时带来的局部时序特征丢失等问题,提出了将多元经验模态分解(multivariate empirical mode decomposition, MEMD)算法与Hilbert空间填充曲线相结合的方法,以提升手势识别算法的准确率。采用开源数据集NinaPro-DB1作为实验数据集;通过MEMD算法对sEMG进行分解;将分解后的本征模态函数(intrinsic mode functions, IMFs)作为Hilbert曲线的填充域(Hilb-IMFs)映射成二维肌电图;选择DenseNet作为手势识别的基本网络。实验结果表明,提出的方法相对于传统信号升维方法在手势识别准确率上约有4%的性能提升,验证了该方法的有效性。

月球圈层空间立体网格技术研究

选定月固坐标系为月球圈层空间网格的坐标基础,根据月球结构及其人造月球卫星轨道分布情况划分月球基准圈层面,采用剖分曲线l和b对月球圈层面进行层次细分,实现对圈层面层次细分。然后,结合圈层径等距细分对月球圈层体进行层次细分,实现对圈层体层次细分,建立月球圈层空间立体网格模型。采用Hilbert曲线填充算法,实现对月球圈层网格统一编码,编码效率较高,为网格数据组织奠定基础。

一种面向并行空间数据库的数据划分算法研究

面向基于对象关系型数据库而构建的并行空间数据库系统,提出了一种基于Hilbert空间填充曲线的适合于矢量空间数据的数据划分算法。在充分考虑空间信息的海量特征以及矢量数据存储记录的不定长等特点的前提下,该算法可实现并行空间数据库中海量空间数据记录在多个存储设备上的均衡划分,以避免出现数据倾斜现象,从而提高了空间数据的检索与查询效率。

Hilbert填充曲线与空间分布模式探测的点数据集空间划分方法

空间数据划分是空间索引、并行GIS数据分解以及分布式数据管理与调度等问题的核心环节之一。针对点数据集多目标空间划分问题,引入Hilbert空间填充曲线和空间分布模式探测过程,提出针对规则、随机和聚集分布模式的点数据集空间划分方法。实验结果表明,该方法能够在缺少覆盖范围信息的条件下准确判定空间分布类型,该方法能够兼顾空间聚集性、数据量均衡与空间重叠度3种约束条件。

机器人栅格地图编码与索引方法

机器人的感知、行动及空间推理决策等与所处环境息息相关,需要各种类型的环境模型来帮助机器人认知环境。当前机器人领域主要聚焦于实时感知、环境建模与路径规划的研究,少有环境模型管理的相关研究成果。文中以机器人环境模型管理作为研究切入点,着重研究机器人栅格地图的形式化描述及栅格编码与索引方法,规范栅格地图的表达形式并实现栅格地图的高效编码索引与联动更新,最后通过实例验证文中方法的可行性。

球面三角区域四叉树L空间填充曲线

球面三角四叉树中面片和结点的排列顺序直接关系到球面三角四分剖分模型组织和管理数据的效率.在Lee编码模型基础上设计了L面片和结点空间填充曲线,给出了面片寻址、结点L曲线生成、以及面片结点访问等主要算法.同时,基于位码运算提出了面片类型判别恒定算法时间优化算子,可利用硬件来实现.结点L曲线中大多数面片结点间距离分布在较低值范围内,为数据高效存取提供了保证.但是堂兄弟面片位置相邻,结点地址却不连续,少数面片结点间距离异常大,导致平均结点间距离和遍历总距离的增大.为解决该问题,采用了m簇完备结点集作为n剖分簇结点存储基本单元,每个m簇完备结点集重复存储公共结点,从而避免了面片结点距离过大,提高了节点访问效率.

非均匀Hilbert曲线的生成算法

基于分形理论,针对Hilbert曲线处理非均匀分布的不足,提出了一种非均匀Hilbert曲线的生成算法.该算法根据数据分布密度,对子区域进行空间层次分解,构造区域连接曲线,最终以递归的方式来生成非均匀Hilbert曲线.结果表明:该算法能够对非均匀空间进行有效的处理,极大的减少曲线的路径长度和遍历曲线时的复杂度,从而打破了传统Hilbert曲线的应用局限性.

一种基于实测的高维动态负载平衡方法

针对大规模科学计算中的强非规则结构负载问题,作者开发出一种基于实测的动态负载平衡方法.首先,将由规则结构化网格组成的模拟区域剖分成多块;其次,把块的高维坐标转换成一维Hilbert空间填充曲线(HSFC)索引;然后,基于实测信息采用多层均权法剖分按一维HSFC索引排列的块;最后根据剖分信息重分配块以平衡负载.它把仅适用于一维的多层均权法扩展到二维和三维,并引入更多的实测信息和块数据结构.与ISP方法相比,该方法在64个CPU上提高负载平衡效率10%,在某MPP的500个CPU上模拟强非规则结构负载问题时,获得了88%的负载平衡效率和84%的并行效率.

基于GM(1,1)模型的压缩域图像表示与检索技术

在讨论基于灰色模型GM(1,1)和Hilbert空间填充曲线的图像压缩算法的基础上，提出了一种新的彩色图像表示与检索技术。它使用GM(1,1)对图像的像素值进行模型化处理，并且在变换域中对这些模型参数进行分析与处理，据此抽取出一种新的图像特征。这种压缩域特征描述了图像的局部细节变化，这种特点正是全局检索方法（例如颜色直方图方法）所不具备的。实验结果表明，这种压缩域图像检索技术能获得较满意的检索质量与性能，其检索结果能较好地同人们的视觉感知结果保持一致。

一种新的保留语义的P2P系统索引构造方法

提出了一种新的P2P系统索引构建方法.它使用多个简单本体(ontology),对同一资源进行描述,将各个ontology描述转化为相应的本体序号(ontology ID),然后使用Hilbert空间填充曲线,实现从多维ontology ID到一维索引值的映射,得到保留了语义的索引值.根据这个索引值,在Chord等结构化P2P上发布和查找资源.该方法对资源的描述更加准确、简单,资源的发布和查询也更加灵活和高效.

一种P2P系统节点聚类及信息检索算法

提出了一种节点聚类及信息检索算法——NCSearch。NCSearch利用Hilbert曲线的局部性特征保持能力,将有相似内容的节点聚类,形成若干个簇。搜索算法能快速定位到与查询最相关的簇,然后在簇内洪泛查找,返回的结果按相关度排序。模拟测试表明,NCSearch稳定高效,相比传统算法在搜索效率方面有明显提高。