(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111643852.9 (22)申请日 2021.12.2 9 (71)申请人 武汉中海庭数据技 术有限公司 地址 430000 湖北省武汉市东湖新 技术开 发区软件园东路1号软件园4.1期B6栋 1层、 9层、 10层01室(自贸区武汉片区) (72)发明人 牛科科　 (74)专利代理 机构 武汉蓝宝石专利代理事务所 (特殊普通 合伙) 42242 代理人 范三霞 (51)Int.Cl. G06T 1/20(2006.01) G06K 9/62(2022.01) G06V 10/762(2022.01) (54)发明名称 一种基于图结构的点云聚类GPU优化方法及 装置 (57)摘要 本发明涉及一种基于图结构的点云聚类GPU 优化方法及装置， 其方法包括： 获取点云数据， 基 于GPU构建基于空间网格的点云mask 图， 以及空 间网格对应点云数据的搜索范围结构图， 以得到 点云结构图； 搜索当前点的邻域点， 确定当前点 的邻域节 点表； 基于所述点云图结构和所述邻域 节点表进行点云搜索聚类， 将聚类后的点云由 GPU下载至CP U。 采用GP U加速优化方案， 在具体的 优化细节上进行优化达到加速优化的目的； 除了 运用GPU加速技术以外， 同时引入了图结构等数 据结构， 利用图论等领域的方法优化技术细 节以 期待达到良好的效果。 权利要求书2页 说明书5页 附图2页 CN 114240729 A 2022.03.25 CN 114240729 A 1.一种基于图结构的点云聚类GPU优化方法， 其特 征在于， 包括： 获取点云数据， 基于GPU构建基于空间网格的点云mask图， 以及空间网格对应点云数据 的搜索范围结构图， 以得到点云结构图； 搜索当前点的邻域 点， 确定当前点的邻域节点表； 基于所述点云图结构和所述邻域节点表进行点云搜索聚类， 将聚类后的点云由GPU下 载至CPU。 2.根据权利要求1所述的基于图结构的点云聚类GPU优化方法， 其特征在于， 获取点云 数据， 基于GPU将所述点云数据投射到空间网格中的一维坐标并存储， 以构点云图结构， 具 体包括： 构建点云数据投射到空间 网格中的一维坐标并存 储； 构建基于空间 网格的点云 mask图， 以表示所述空间 网格中是否存在点云数据； 构建所述空间 网格对应点云数据的搜索范围结构图； 基于所述 一维坐标、 所述搜索范围结构图构建点云数据一维存 储的连续索引表。 3.根据权利要求1所述的基于图结构的点云聚类GPU优化方法， 其特征在于， 搜索当前 点的邻域 点， 具体包括： 基于当前点的参数确定当前点所在的当前空间网格， 根据当前空间网格查找邻域空间 网格； 遍历邻域空间网格的连续索引表， 以计算邻域空间网格中各点与当前点的距离， 以判 断是否属于当前点的邻域 点。 4.根据权利要求3所述的基于图结构的点云聚类GPU优化方法， 其特 征在于， 还 包括： 构建二维节点表， 所述二维节点表中每个节点的第 一维用于存储当前节点的邻域点个 数， 第二维用于存 储对应边结构中的起始位置索引； 构建边结构表， 所述 边结构表用于存放每 个节点邻域的点索引。 5.根据权利要求1所述的基于图结构的点云聚类GPU优化方法， 其特征在于， 所述点云 搜索聚类采用的方法为广 度优先搜索方法。 6.根据权利要求4所述的基于图结构的点云聚类GPU优化方法， 其特征在于， 构建二维 节点表， 具体包括： 基于CUDA  shuffle指令访问线程间寄存器数据， 以构建二维节点表， 并根据所述二维 节点表构建变结构表。 7.一种基于图结构的点云聚类GPU优化装置， 其特 征在于， 包括： 结构图构建模块， 获取点云数据， 基于GPU构建基于空间网格的点云mask图， 以及空间 网格对应点云数据的搜索范围结构图， 以得到点云结构图； 邻域搜索模块， 搜索当前点的邻域 点， 确定当前点的邻域节点表； 聚类模块， 基于所述点云图结构和所述邻域节点表进行点云搜索聚类， 将聚类后的点 云由GPU下 载至CPU。 8.根据权利要求7所述的基于图结构的点云聚类GPU优化装置， 其特征在于， 所述结构 图构建模块具体用于构建点云数据投射到空间 网格中的一维坐标并存 储； 构建基于空间 网格的点云 mask图， 以表示所述空间 网格中是否存在点云数据； 构建所述空间 网格对应点云数据的搜索范围结构图；权　利　要　求　书 1/2 页 2 CN 114240729 A 2基于所述 一维坐标、 所述搜索范围结构图构建点云数据一维存 储的连续索引表。 9.一种电子设备， 其特 征在于， 包括： 存储器， 用于存 储计算机软件程序； 处理器， 用于读取并执行所述计算机软件程序， 进而实现权利要求1 ‑6任一项所述的基 于图结构的点云聚类GPU优化方法方法。 10.一种非暂态计算机可读存储介质， 其特征在于， 所述存储介质中存储有用于实现权 利要求1‑6任一项所述的基于图结构的点云聚类GPU优化方法的计算机软件程序。权　利　要　求　书 2/2 页 3 CN 114240729 A 3