基于改进Fleury算法的激光扫描投影路径规划方法

侯茂盛，孙明利，杨 帆，李丽娟，朱运东，范成博

(长春理工大学 光电工程学院 光电测控与光信息传输技术教育部重点实验室,吉林 长春 130022)

引言

激光扫描投影技术是依据零部件的三维CAD数模驱动二维振镜扫描系统使激光器出射的光线被快速转折，从而在三维空间中任意位置的投影区域内绘制出由激光线快速循环扫描形成的零部件外形轮廓线框，技术人员可以通过清晰、明亮的零部件轮廓线框得到更加直观和实用的信息，实现更精确、高效的零部件安装定位装配[1-2]。该技术现在已被广泛应用于汽车零部件的安装定位和检测、航空航天领域飞行器零部件的精密制造、管线铺设、复合材料铺叠制造等重点工程[3-6]，可以加速实现我国先进装备生产制造的数字化、智能化，节省人力物力，是建设智能化工厂、数字化车间的必备技术和设备[7]。

由于激光扫描投影系统利用了人眼的视觉暂留效应[8]，所以在其应用过程中，如果待投影图形较为复杂，扫描整幅图形的频率远小于20 Hz，投影出图像发生闪烁，这种不稳定的现象被称为“频闪”[9-10]。扫描投影图形的频闪不利于实际装配现场的辅助定位装配。为解决上述问题，研究并提出了一种改进Fleury算法的激光扫描投影路径优化方法，减少扫描图像所需时间，改善所研发激光扫描投影仪器的频闪问题，保证扫描图像质量，在定位、装配等实际应用中获得更理想的效果。

首先介绍了路径优化问题的图论基础，分析了基于图论理论解决激光扫描投影系统路径优化的可行性，利用Fleury算法实现激光扫描投影系统欧拉路径优化，并针对Fleury算法无法优化非欧拉路径的局限性加以改进，提出改进的Fleury算法并对激光扫描投影系统的扫描路径优化进行仿真分析，再应用于研发的激光扫描投影系统中进行验证实验。

1 扫描路径优化问题的图论基础

1736年，瑞典数学家欧拉(Leonhand Euler)解决了哥尼斯堡七桥问题，由此开创了图论学科的研究[11]。

图论是离散数学的一个分支。它以图为研究对象，由若干给定的点及连接两点的线所构成，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的这种关系[12]。

在激光扫描投影系统中，要利用例如图1(a)所示的零部件的CAD数模，在待投影平面扫描出清晰的激光轮廓线框，这种由投影控制点和轮廓线组成的扫描线框可以抽象为图论里的顶点和边，这就将激光扫描投影技术与图论相结合，如图1(b)所示，得到了一个研究激光扫描投影系统路径优化问题的新思路。

图1 激光扫描投影图形的原理Fig.1 Principle of laser scanning projection graph

1.1 图的概念

图是由顶点集合及顶点间的关系集合组成的一种数据结构[13]。如图2所示，设图G=(V,E)，与顶点v相关联的边e的个数称为顶点v的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图2中，v1,v2,v3,v4的度都为3，都是奇点。

图2 图的概念Fig.2 Definition of graph

假设图G=(V,E)，有n个顶点，即V={V0,V1,V2,V3,…,Vn-1}，E可以用如下的形式的矩阵D描述，对于矩阵D中的每一个元素di，满足：

(1)

从定义中可以看出矩阵D中的元素dij表示了顶点Vi和顶点Vj之间边的关系，dij的值表示了该边的权值。

由此图2中的矩形可表示为邻接矩阵：

(2)

1.2 Euler图在激光扫描投影路径优化中的应用

欧拉解决哥尼斯堡问题的实质就是在图G中寻找经过每一条边一次且仅一次的闭迹。经过图G的每条边至少一次的闭迹称为图G的环游；经过每条边仅一次的环游称为图G的Euler环游。包含Euler环游的图称为Euler图[14]。

在激光扫描投影系统的应用中，为了绘制一个完整的激光扫描投影图像，扫描时需要用空白跳转线来连接可见轮廓线。二维振镜连续扫描的同时开闭激光器实现轮廓线和跳转线的绘制。在上述过程中，绘制可见轮廓线和不可见的跳转线都需要耗费时间。若待扫描的图像不需要添加跳转线，轮廓线也不重复绘制，就可以优化扫描路径，减少不必要的时间浪费，有效改善频闪问题。

2 基于改进FLeury算法的扫描投影路径规划

2.1 Fleury算法的实现

当待扫描的图形可以抽象为欧拉回路时，应用Fleury算法依次描绘每一条轮廓线从而得到欧拉扫描路径。Fleury算法的基本步骤[15]如下：

1) ∀v0∈V(E)，令W0=v0；

2) 若Wi=v0e1v1e2…eivi已选定，则从E-{e1,e2,…,ei}中选取一条边ei+1，使得：a)ei+1与ei相邻；b)除非已经无选择余地，否则ei+1不要选Gi=G-{e1,…,ei}的桥。

3) 直到上一步不能继续循环为止。

激光扫描投影系统扫描路径优化方法的主要逻辑与Fleury算法的步骤相对应：a) 判断待扫描图形是否为欧拉图，如果不是，则跳出程序；b) 确定欧拉回路的投影起点和起始轮廓线；c) 寻找接下来需要扫描的轮廓线和接下来需要扫描的投影控制点，直到完成图形扫描；d) 输出扫描路径及其所对应的权值，完成激光扫描投影路径的优化。

流程图如图3所示。

图3 激光扫描投影路径优化流程图Fig.3 Flow chart of laser scanning projectionpath optimization

在选择下一条投影轮廓线时，要判断这条轮廓线的终点dvex是否符合Fleury原理的判定，如图4所示。若符合则可以在程序中更新扫描路径矩阵，便于进行下一次循环过程。若找不到下一个投影控制点，也就是程序中dvex=0时，则跳出循环，在之前的步骤中重新搜索可以实现的扫描路径。

图4 选择下一条轮廓线Fig.4 Selecting the next contour line

图5 选择下一个投影控制点Fig.5 Selecting the next projection control point

在选择下一个扫描轮廓线的端点时，要进行多次判断，如图5所示。

1) 判断下一个扫描投影点是否唯一。如果在当前轨迹下只有一点可以选择，直接选取该点为下一扫描点。

2) 倘若下一点有多个选择，需要判断这个投影控制点是否在之前的轨迹中已经扫描过。如果没有扫描，可以把这个点当做下一个控制点的备选之一；如果这些邻接的点全部扫描过，就要进行下一步的判断。

3) 如步骤2)中所述，当可以选择的所有的投影控制点已全部扫描过，判断所有备选点和当前投影点的连线在之前的路径中是否已经存在。倘若所有的路径都已扫描过，那么当前控制点的选择发生错误，跳出函数，重新寻找路径。如果已扫描过的的路径中没有找到这条路径，那么这条轮廓线可以作为备选以进行下一步的判断。

4) 根据Fleury算法的基本原理，如果有其他的路径可以选择，就不能选择桥作为下一条轮廓线。所以此处应对这些线段是否为桥进行判断。倘若为桥，则循环到下一条可以选择的线段；若不是桥，则该线段所对应的终点即作为输出。

2.2 Fleury算法改进

由于Fleury算法只能解决欧拉图的路径优化问题[16]，当判断输入的投影图形为非欧拉图时，程序将直接结束。但是在实际应用中，待投影的图形一般为非欧拉图，所以本文提出一种改进的Fleury算法，将非欧拉投影图形转化为欧拉图。

在判断原投影图为非欧拉图的情况下，需要对原图进行改造，使其变成欧拉图。流程图如图6所示，在原投影图中，奇点个数大于等于2，所以只需将奇点转变成偶点就可以完成欧拉图的构造。因此对这些奇点进行配对处理，配对的原则：选择未相连的两个奇点进行连线，使其均变为偶点。当奇点个数确认为0，即可跳出循环，得到新的邻接矩阵，也就得到了改造过的欧拉图。这样就可以应用上述Fleury算法对激光扫描投影路径进行优化。

图6 Fleury算法的改进Fig.6 Improvement of Fleury algorithm

3 路径优化算法仿真实例

在激光扫描投影系统的实际应用中，当待投影图形为多行多列矩阵时，因其可选择路径较多且均为非欧拉路径，更易发生频闪。所以本章以如图7所示的3×3“棋盘式”投影图形为模型进行MATLAB环境下的路径优化仿真分析，验证改进的Fleury算法是否可以达到预期效果。

图7 投影图像仿真模型Fig.7 Simulation model of projected image

整体仿真过程有如下4个阶段。

3.1 待投影图形邻接矩阵的判断及优化

该投影图共有16个投影控制点，该图对应的邻接矩阵尺寸为16×16，通过图的逻辑将两点之间的通断用0或1进行表示，从而得出该图对应的邻接矩阵(如图8)。通过邻接矩阵进行判断，得出该投影图为非欧拉图。添加空白跳转线段将奇点优化为偶点，从而得出新的邻接矩阵(如图9)，将原来的非欧拉图转化为现在的带有空白线的欧拉图。

图8 非欧拉图的邻接矩阵Fig.8 Adjacency matrix of non-Euler graph

图9 根据更改后的邻接矩阵得到欧拉图Fig.9 Eulerian graph based on modified adjacency matrix

3.2 确定起始路径

默认投影起始点为v1，在邻接矩阵中的第一行进行搜索，找到与投影起始点v1相接的点的位置：

t1=find(b(vet,:)==1)

(2)

式中：vet是起点v1；b为优化后的邻接矩阵，则t1=[v2,v8]。

那么起始扫描路径也就是从v1-v2和v1-v8这两条轮廓线中选择。先将v1-v2赋值在路径矩阵的第一列中作为起始路径，再进入后续处理流程。如果发现v1-v2这条起始路径并不能得到期望的整体路径，则将v1-v8重新赋值在路径矩阵中，重新进行路径规划。

3.3 依次确定后续路径

继续在邻接矩阵中寻找与当前投影控制点相衔接的点，并通过可选择投影点的个数，进行不同的逻辑运算。

1) 如果只有一个可选择的投影控制点，可直接将这一点作为路径中的下一个控制点。例如，扫描至点v13时，不论刚刚扫描过v12-v13还是v14-v13，都仅剩一点可以选择。

2) 如果可选择的点在之前的扫描路径中没有出现过，通常情况下都可以作为备选点。例如，当扫描至v2时，v3、v7、v8都是未扫描过的投影点，可以使用一个循环去判断哪个投影点更为合适，即选为下一个投影控制点。

3) 如果可选择的点都已存在于扫描路径中，就需要判断当前投影点与可选择的投影点所连接成的扫描路径是否在之前的路径中已经存在。若都已存在，则需要跳出循环，重新进行上一级循环。

综上所述，选择扫描路径的优先顺序是：先选唯一的，再选相关性低的，若都没有只能选择重复经历的投影控制点。

3.4 输出路径与权值

由上述过程逐步建立的路径矩阵即为输出的扫描路径，在本模型中，得到的扫描路径矩阵和权值，如图10所示。

图10 输出的路径与权值Fig.10 Output path and weight

4 实验结果

图11为自主研发激光扫描投影系统试验装置。右上为与计算机相连接的数据采集卡。

图11 自主研发的激光扫描投影系统Fig.11 Laser scanning and projection systemindependently developed

实验使用搭建的激光扫描投影系统在投影面上投影出一个5×5矩阵。投影时，将待投影图像的数模写入计算机，经计算机自主处理后将待投影图像信息写入数据采集卡，经过开闭激光器、二维扫描振镜不断偏转等过程，将该图形投影至投影平面。计算机软件界面显示绘制该图形的频率为15.2 Hz，图像频闪问题较为严重，导致无法拍摄出完整的投影图形，如图12所示。

图13 改进Fleury算法优化扫描路径后的复杂图形投影Fig.13 Complex graph projection after path optimizationwith improved Fleury algorithm

将改进Fleury算法程序写入计算机。当待投影图形的数模文件写入计算机后，使用该算法对扫描路径进行规划，输出优化后的路径，写入数据采集装置，继续投影。计算机软件界面显示绘制该图形的频率为25.6 Hz，图像频闪问题得到明显改善，如图13所示。

5 结论

依据激光扫描投影系统的成像原理，将图论理论与激光扫描投影图形相联系，并将求解欧拉回路的Fleury算法应用于激光扫描投影路径规划，且针对该算法无法优化非欧拉路径的局限性，提出了改进的Fleury算法。利用MATLAB仿真软件对上述算法的扫描路径规划效果进行仿真分析，优化得到最佳的欧拉路径。将多行多列矩阵输入扫描投影系统，实验对比发现，未经优化的投影图形频闪问题较为严重，辅助定位装配的效果也受到影响。经改进Fleury算法规划后的激光扫描投影路径投影出的图像，扫描频率更高，频闪问题得到有效改善，能够达到实际工程应用中对零部件的精准定位要求。