应用TSP的纤维检测装置扫描路径优化

孙 晗，周 全，杨志军

(1.广东工业大学 省部共建精密电子制造技术与装备国家重点实验室，广东 广州 510006；2.佛山市华道超精科技有限公司，广东 佛山 528225)

0 引 言

近年来，纺织行业的快速发展受益于高精密检测装备行业技术的更新换代，而通过显微成像与精密运动控制获取纤维组织结构是纺织品质量检测的关键手段之一[1]。显微成像是一种无损检测纤维细度、长度、截面形状、纤维种类测定的光学影像技术，利用高倍放大镜与精密运动平台的配合控制，可以对数毫米甚至微米级别的纤维提供高分辨率图像，非常适用于纺织纤维成像研究[2]。然而，现阶段的逐点扫描式光学显微成像系统由于高度依赖成像系统的扫描频率和机械电机扫描速度，导致采集速度慢、成像质量差。为了满足纺织行业对纤维质量检测和种类分析的研究需求，大多数纤维扫描实验需要快速完成，同时纤维数据量的显著增大，对检测系统的硬件要求也提出了挑战。

国外早期的产品，比如1994年的BLISS系统，通过走停方式扫描采集15 mm×15 mm的视场需要几十分钟[3]，这种方式称为“Z型”扫描，对于局部零权重扫描点区域和复杂纤维分布处理还有一些局限性[4]。因此上述扫描问题实质上是路径规划问题，即如何以最短路径的方式全局扫描载玻片上分布不均匀的纤维，本文采用TSP的方法对纤维扫描路径规划进行转化建模，TSP[5-6]作为著名的NP-hard问题，近年来许多专家学者对该问题求解提供了许多优化算法，如最小生成树算法[7]、遗传算法[8]和模拟退火算法[9]。模拟退火算法的实验性能具有质量高、初值鲁棒性强、通用易实现的特点，然而优化过程较长；遗传算法优点在于隐含并行性和全局解空间搜索，但易出现早熟收敛和收敛性能较差的特点。

本文提出了一种适用于快速纤维采集系统的最短扫描路径规划方法，可以通过优化电机扫描平移路径，更好地减小采样时间，实现快速采集。首先介绍纤维采集设备的硬件结构，接着用一种基于机器视觉的纤维锚框坐标算法将纤维转化为坐标的图像算法，然后将纤维坐标之间的欧几里得长度通过电机运动规划算法转化为实际运动时间，从而将最短路径问题转化为最短时间问题，最后将元启发式算法、启发式算法与谷歌 OR-Tool等方法应用在纤维扫描路径优化中，在保证图像质量的前提下缩短扫描时间，从而降低纤维图像采集时间。

1 硬件系统搭建

光学显微成像系统最终获取的是样品经过光学系统的放大并传输到光电元件上形成感光成像。该系统一般是由二维扫描平台、Z轴调焦平台、光学成像采集系统3部分组成[10]。

二维扫描平台要求在X、Y方向能精确移动，且在纤维扫描过程需要满足无顿力与低速度链波特性，本文采用上银LMT系列棒状电机来实现平台X、Y方向上的移动，X、Y方向分辨率为0.1 μm，安装结构简单，无磨耗零背隙，满足光学显微平台高速轻负载的需求。Z轴调焦平台采用课题组研发的刚柔耦合滚珠丝杠平台，Z轴方向的分辨率为0.1 μm，通过柔性铰链的弹性变形来克服摩擦死区从而满足光学系统调焦过程中的高精度与平稳性要求。

光学系统元件由光源、阿贝聚光镜、600万像素CMOS彩色相机和4倍、20倍、40倍物镜组成，满足纤维采集过程中不同放大倍率的高分辨率图像需求。目前整套硬件系统装置取得了较好的效果，纤维光学显微成像系统的系统框图和实物图如图1、2所示。

图 1 纤维光学显微成像系统Fig.1 Fiber optic microscopic imaging system

图 2 纤维光学显微成像实物Fig.2 Imaging object of fiber optic microscopic

通常，高倍物镜采集的图像质量更能反映整套硬件系统装置性能，图3所示为40倍物镜下采集到的绵羊毛纤维。

图 3 40倍物镜下绵羊毛纤维Fig.3 Sheep wool fiber under 40x objective lens

从图3可以看出，绵羊毛纤维图像整体无噪声，光学照射均匀，纤维成像保真性好，说明整套硬件系统搭建较为完善。不同动物纤维及不同物镜倍数采集的图像见文章首页OSID码“开放科学数据与内容”中的“纤维成像数据.docx”。

2 纤维锚框坐标算法

锚框坐标算法的本质是从采集到的4倍物镜粗扫描的纤维图片中识别出待检测纤维，并得到其像素坐标系下中心位置坐标，从而确定整张载玻片区域扫描权重，进行40倍物镜精扫描路径规划。

本研究根据纤维的特征，设计了纤维锚框坐标算法，检测流程如图4所示。

图 4 纤维锚框坐标算法流程Fig.4 Algorithm flow of fiber anchor frame coordinate

2.1 纤维边缘检测算法

图像经过去噪后[11]，需要对纤维的轮廓进行提取，通过纤维的轮廓进行锚框分析得到目标纤维的坐标信息。本研究采用鲁棒性较好的Canny边缘检测算法对纤维骨架轮廓进行边缘提取，Canny算子相比其他边缘轮廓算法，能最大化突出图像边缘特征，并有效减少图像计算规模[12]。Canny算法选用合适的高斯滤波函数，分别按行和列对图像f(x,y)进行平滑去噪，计算图像水平、垂直和对角线方向的梯度，同时比较图像内像素点与梯度正负方向像素点的梯度强度，通过保留或抑制像素点进行高低阈值检测，从而得到纤维轮廓边缘。所选高斯函数可表示为

(1)

式中：σ为高斯曲线标准差，控制着平滑程度。绵羊毛纤维原图与Canny检测后的图像如图5所示。

(a) 4倍放大纤维 (b) Canny算法纤维 边缘轮廓图 5 绵羊毛纤维图像及Canny轮廓提取Fig.5 Sheep wool fiber image and Canny contour extraction

图5中,Canny算法在去除纤维图像噪声的同时保持维边缘轮廓清晰，说明该算法具有较好的鲁棒性。

2.2 纤维锚框坐标算法

纤维图像经过去噪、Canny边缘检测后，需要将纤维轮廓图像以锚框标定的形式转化为像素坐标系坐标[13-14]。由于粗扫描4倍物镜与精扫描40倍物镜的相机视野不同，需要将不同视野下的纤维坐标进行转换。因此，本文以锚框算法对纤维进行Blob分析[15]，计算纤维边缘坐标并转化为40倍物镜扫描坐标，见图6。

图 6 纤维锚框算法过程Fig.6 Algorithm process of fiber anchor frame

图6中，红色部分为4倍物镜视野图像下纤维Pi，经Canny算子边缘检测后的纤维骨架。通过Blob分析求得该纤维最大外接矩形框由图中蓝色虚线框表示，其矩形框中心点坐标为(xi,yi)，矩形像素宽度为Wi，像素长度为Hi，则纤维Pi进行40倍精扫描需要扫描的数量Oi可表示为

(2)

式中：CW、CH为相机横向、纵向分辨率，像素分别设置为3 072、2 048；q为粗扫描与精扫描物镜倍数比，本文取10。则第i根纤维的j个40倍精扫描Oi_j的像素中心坐标可表示为

(3)

式中：c为纤维图像坐标修正系数，代表修正40倍物镜下纤维起始扫描坐标,本文c=50。

在4倍物镜下全局扫描18 mm×18 mm纤维切片后，进行锚框算法，得到1 000个左右的40倍精扫描坐标点，如图7所示，蓝色点为需要精扫描的点坐标。

图 7 锚框算法求解全局纤维精扫描坐标Fig.7 Anchor box algorithm for global fiber fine scanning coordinates

3 最短扫描时间算法

传统的枚举法处理此类大规模点的扫描问题有n!种路径，难以在短时间内求得最优解[16-17]。而2.2节中锚框算法取得待扫描的1 000个待扫描坐标点，通过对坐标点进行最短扫描路径规划，优化XY轴电机运动轨迹，可有效减少整体扫描时间,如图8所示。

图 8 纤维扫描最短路径规划Fig.8 Shortest path plan of fiber Scanning

3.1 纤维扫描数学模型

二维平面的纤维距离分布如图9所示。其中绿色圆形部分为二维平面的纤维坐标，红色数字部分为纤维间的平面欧式距离。

图 9 纤维扫描数学模型Fig.9 Mathematical model of fiber scanning

从图9可以看出，当装置需要扫描全部纤维时，需要依次遍历所有纤维坐标，即有5！种路径，见文章首页OSID码“开放科学数据与内容”中的“5！种路径.docx”，在不同的扫描顺序下，其纤维扫描路径总长度也不同。在3-1-2-5-4的扫描顺序下，纤维扫描路径最短，则总体扫描时间最短为最优扫描路径。

因此，可以建立纤维最短扫描时间算法的数学模型：设n个扫描坐标的集合为Qn，Ci是坐标编号，取值为[1,n],对于坐标Ci，Ci∈Qn，从Ci到Cj的距离记为d(Ci,Cj)。此处的距离考虑运动对称性，所以d(Ci,Cj)=d(Cj,Ci)。TSP的最优解就是寻找这n个坐标的一组排列组合，使得式(4)的目标函数最小，即

然而，在二维扫描平台的实际路径规划中，基于欧式距离评估的传统TSP数学模型不能得到较好的应用，原因有2点。

1) 对于纤维C1与C2的斜向点位运动需要通过直线插补的方式进行运动[18]，而另一种通过X、Y双轴电机联动的形式，与直线插补的方式相比，扫描时间更短。可见后者的评估模型更加适应于实际场合的路径规划中。

2) 电机的运动往往需要通过一段S曲线来进行运动规划。在运动规划后，电机的运动距离与运动时间呈非线性关系，因此3—1—2—5—4的路径扫描顺序不一定是最短扫描时间顺序。

故本文在原有TSP数学模型上进行改进，有

d(Ci,Cj)=max(|XCi-XCj|,|YCi-YCj|)

(5)

式中：XCi为点Ci的x坐标；YCi为点Ci的y坐标。将纤维坐标点的欧式距离转化为X、Y方向最长投影作为模型评估d(Ci,Cj)。

将d(Ci,Cj)经S曲线运动规划转化为评估时间T(Ci,Cj)，有

(6)

式中：aa为加速段最大加速度；Ta为加速段时间；Vv为匀速段最大速度；Tv为匀速段时间；ad为减速段减速度；Td为减速段时间。

则纤维扫描最短时间扫描算法的最优解为使得目标函数式(7)最小：

(7)

3.2 算法验证仿真

由于扫描点规模通常在800～1 500范围内，本文选择蚁群优化与模拟退火等启发式算法、贪心算法以及最小生成树等元启发式算法与传统Z型扫描算法在路径长度和扫描时间上做对比实验，具体实验程序见OSID码“开放科学数据与内容”中的“TSP算法”文件夹。算法的性能表现往往受硬件类型所影响。本文所用的硬件配置以及编程语言环境为Win10系统、Intel i7-10700F型号CPU、NVIDIA 3080显卡、32 GiB RAM。仿真程序均由Python 3.8编程实现。同时为了验证在不同规模节点分布下的性能，分别在800、1 200和1 500个节点(即TSP-800，TSP-1 200，TSP-1 500)下执行实验，所用的测试是二维平台上随机的坐标分布，保证算法在面对随机坐标分布时的表现性能。

为了更好地对比不同算法在纤维扫描时间实验最短的验证，使用Python的random库的seed模块，确保不同算法使用的是同一组数据从而提高算法对比性。在每一个规模节点下，使用不同的seed进行50次重复实验，确保实验结果稳定性。对于蚁群算法、模拟退火算法等启发式算法，对于不同的规模点求解，需要设置不同的算法参数[19-24]，本文所选取的蚁群算法参数中，信息素因子为5，启发函数因子为2，信息挥发素因素为0.1，蚂蚁数量为720。模拟退火算法参数中，初始退火温度数值为10 000，终止退火温度数值为1，内循环次数为2 000，降温参数为0.99。在上述实验环境参数设置下，选取具有最短行程保障的最小生成树算法，求解效率高的贪心算法、最优路径求解的蚁群算法以及本文算法进行路径仿真。TSP-800实验结果扫描路径如图10所示。

使用多种算法下TSP-800的求解时间、扫描时间与路径总长度对比结果如表1所示。TSP-1200、TSP-1500的实验数据和实验结果扫描路径见本文OSID码“开放科学数据与内容”中的“实验数据.docx”。

(a) 最小生成树算法

(c) 贪心算法

(b) 蚁群算法

(d) 本文算法图 10 TSP-800下不同算法路径轨迹Fig.10 Path trajectories of different algorithms under TSP-800

表1 TSP-800下不同算法求解优化效果

表1中，使用谷歌OR-Tool的求解结果作为扫描长度基准，通过对比其他算法路径长度求得标准偏差以说明算法路径优化性能。同时由于该求解属于NP-Hard问题，求解时间是衡量算法性能优劣的指标，其中Z型扫描算法为固定扫描路径，无求解时间。从表1可以看出，TSP-800的传统Z型扫描算法的长度为140.0 m，扫描时间为12.4 min，本文算法扫描长度为45.2 m，扫描时间为7.2 min，扫描长度和时间降低了约67.7%、41.9%。TSP-1200、TSP-1500的分析同理，TSP-1200和TSP-1500的传统Z型扫描算法的扫描长度都为140.0 m，扫描时间都为12.4min，本文算法扫描长度分别为53.8 m和65.8 m，扫描时间分别为9.0 min和9.8 min，扫描长度分别降低了约61.6%和53.0%，扫描时间分别降低了约27.4%和21.0%。验证了本文扫描算法可以真正地减少纤维扫描时间与扫描长度，提高了纤维检测装置扫描效率。

4 结 论

1) 本研究搭建了XYZ三轴纤维扫描检测平台与控制系统，具有4倍、20倍与40倍3种光学放大倍数，采集到的纤维图像成像清晰，质量较好。同时基于Canny算子提出一种锚框算法，有效地将4倍粗扫描纤维图像转化为40倍精扫描坐标点，有利于对电机运动进行最短路径规划。

2) 基于机器视觉锚框算法与TSP的最短扫描时间算法实现了纤维扫描路径优化，并将该方法编程实现集成到自主研发的纤维检测装置中，通过TSP-800、TSP-1 200、TSP-1 500规模点进行电机扫描实验，结果表明对比传统Z型扫描算法本文的扫描算法降低了21.0%～41.9%的扫描时间，总扫描路径长度降低了53.0%～67.7%。

3) 本文的锚框算法与TSP数学模型仍然适用于数据规模更大的纤维扫描路径问题，还可以推广应用于其他类型检测装置规划扫描中。但是由于实际检测纤维样品种类、尺寸的复杂性，本文的研究方法还有不足之处。如果综合考虑到大规模纤维检测时不同品种纤维对路径扫描的影响，通过动态分类纤维品种与扫描权重，建立的模型将更有实际意义。