为了解决三维激光扫描系统中重构曲面存在的空洞问题, 提出了基于Floyd最短路径选择算法的空洞识别与修复方法。该方法对三维曲面中所有可能构成空洞的边界点进行逐个处理, 采用树搜索算法获得与处理点直接或间接相连的边界点; 将搜索到的边界点作为路径选择的节点, 将连接节点的边界边作为路径选择的边并根据节点的搜索级别设置边的长度。当新搜索到的边界点与已搜索点发生重复时, 首先, 利用Floyd算法处理距离矩阵和路由矩阵找到空洞端点; 然后, 根据重复点与空洞端点生成空洞边集, 最后, 采用波前法对空洞边集进行处理。实验结果表明: 本文所提方法能够准确识别连接有孤立边的空洞以及两个相邻空洞的特殊空洞结构, 与传统方法相比, 该方法具有更强的通用性和鲁棒性, 空洞修复数量与两个传统方法相比分别提高了541%和213%。

To solve the hole-problem of the reconstructed surface in three dimensional laser scanning system, the hole-recognition and repair method based on the Floyd shortest path selection algorithm is proposed. We process one by one all the boundary points of the three dimensional surface which might constitute a hole, and adopt the tree search algorithm to obtain the boundary points, which are directly or indirectly connected to the processed point, and use them as the routing nodes, then the boundary sides which are connected with the nodes are used as the routing sides, and we set the length of the boundary sides according to the search level of the nodes. When the newly searched boundary point overlap with the already searched points, we firstly process the distance matrix and the routing matrix to find the hole endpoint by the Floyd algorithm, and then make use of the repeated point and the hole endpoint to generate the hole boundary sides set. Finally, we deal with the hole boundary sides set using the wave front method. The experimental results show that the proposed method can accurately identify the special hole-structures, such as a hole connected with an isolated boundary side and two adjacent holes, and has better versatility and robustness compared with the traditional method. Compared with two traditional methods, the number of the repaired holes has been increased by 541% and 213%, respectively.