一种振镜扫描汉字激光打标优化算法

高世一，许 超，杨永强，陈和兴

（1.广州有色金属研究院，广州510650；2.华南理工大学机械与汽车工程学院，广州510006；3.大族粤铭激光科技有限公司，睢宁221200）

一种振镜扫描汉字激光打标优化算法

高世一1，许 超2，3，杨永强2，陈和兴1

（1.广州有色金属研究院，广州510650；2.华南理工大学机械与汽车工程学院，广州510006；3.大族粤铭激光科技有限公司，睢宁221200）

为了提高汉字激光打标效率，结合笔画跟踪算法和贪心算法，给出了一种振镜式汉字激光打标优化算法。该算法首先提取出汉字的连续笔画，然后运用贪心算法获得汉字笔画最优输出路径，最后按最优路径实现激光打标。结果表明，该算法减少了激光大跳跃次数，提高了汉字激光打标效率。

激光技术；算法优化；振镜扫描；激光打标

引 言

激光打标是继激光焊接、激光切割、激光雕刻之后新发展起来的又一项先进激光制造技术。它利用高能量密度激光束对材料局部加热，使之融化并发生物理化学变化，在物体表面留下永久性标记。激光打标相比于传统打标技术具有很多优势［1-2］：（1）激光通过光学系统可形成微细光束，在物体表面形成最小直径约0.1mm光斑，非常适合高精度打标；（2）能获得高质量、永久性标记，不会因为触摸或者放置时间长久产生模糊、消退现象；（3）相对传统的喷墨喷码技术，不需要油墨等耗材，节约成本、绿色环保。

激光打标自诞生之日到现今，经历了不同发展阶段［3］，目前最为先进的激光打标方式是采用振镜扫描的激光打标。采用振镜扫描激光打标，具有打标速度快、稳定性好、定位精度高等特点，非常适用于流水生产线高速打标［4］。

对于标点符号、数字及英文字母等字符，由于字形简单、笔画数目少，打标较易实现。但对于汉字，特别是笔画数目多、字形复杂的汉字，需要深入研究打标算法及其效率。为了提高汉字打标效率，参考文献［5］中提出了笔画跟踪算法。作者在笔画跟踪算法基础上，进一步采用贪心算法对打标的各笔画首末端点重新排序优化，提高了激光打标效率。

1 激光振镜扫描原理

激光振镜扫描原理如图1所示，激光器发出的光束被x轴振镜和y轴振镜反射后，透过平面场镜在工件表面某点聚焦，在激光作用下该点发生热化学反应形成一个永久标记。通过控制x轴和y轴振镜偏转角度来控制激光束在平面的扫描路径，振镜偏转角度与激光束在工件平面焦点位置的数学模型见参考文献［6］。

Fig.1 Schematic diagram of 2-D laser galvanometer scanning

2 激光振镜扫描汉字分析

2.1 汉字存储方式

汉字通常以点阵图的方式存储在计算机中［7］。如HZK16字库中的汉字按16×16点阵存储，具有二值图像特征，构成汉字的点用“1”标识，其余的点用“0”标识。以汉字“华”为例，存储方式见图2。振镜扫描时要保证在汉字点阵图中1的位置开启激光，而在0的位置关闭激光。

Fig.2 Chinese character storage and laser scanning point

2.2 汉字激光振镜扫描

激光振镜扫描汉字包括连续扫描和跳跃扫描两种方式，连续扫描是指激光扫描同一笔画上的连续点，跳跃扫描是指激光在不同笔画首末端点之间跳跃。激光在构成汉字的每个点上停留时间设定为1.8ms。

为了获得连续扫描和跳跃扫描的振镜偏转定位时间，采用德国PRO公司制造的帧率为7000帧／s的高速摄像机拍摄激光打标时光斑位置并记录时间，图3为其中的4帧图像。

Fig.3 Laser spot and time record gotten by high speed camera

从拍摄到的多帧激光光斑图像可计算出连续扫描时笔画上各点平均用时，减去激光停留时间1.8ms后，即可得到连续扫描笔画各点振镜偏转定位时间，结果见表1。同理，拍摄到的多帧激光光斑图像记录了激光跳跃时前后时间，其时间差就是激光跳跃时振镜偏转定位时间。考虑到在不同笔画间跳跃时跳跃的间隔点不同，把跳跃间隔点分为两类：大距离跳跃（大于5个间隔点）和小距离跳跃（不大于5个间隔点），结果见表2。从表1及表2可知，连续扫描振镜偏转定位时间可不计，而跳跃扫描镜偏转定位时间不可忽略。

Table 1 Continuous galvanometer scan time of each point under 1.8ms stay time／s

Table 2 Jump scan time of each point under 1.8ms stay time／s

3 激光振镜扫描汉字算法优化

3.1 算法分析

汉字点阵扫描因激光跳跃频繁降低了汉字打标效率，参考文献［5］中提出了笔画跟踪算法，按笔画搜索顺序输出汉字各笔画。该算法没有对笔画输出顺序进一步分析，在一个笔画的末端到另一个笔画的首端经常遇到激光大距离跳跃问题。为减少笔画输出的激光大距离跳跃问题，作者在提取汉字笔画后，采用贪心算法对笔画端点路径进行优化。贪心算法在对问题求解时，总是做出在当前看来是最好的选择［8-9］，非常适用于激光振镜扫描汉字优化，可获得近似全局最优解且算法执行效率高。

汉字笔画跟踪有3种不同的搜索策略，这里采用按行搜索和横向优先的组合搜索方法［10］。笔画跟踪某个汉字后将产生n个笔画，每个笔画的首末端点分别为D11，D12，D21，D22，D31，D32，D41，D42等，其中物理量D的第1个下标表示笔画数，第2个下标表示该笔画上的端点标记。应用贪心算法，在获得汉字的各个笔画数组后，对汉字全部笔画的所有首末端点进行排序，找到一个遍历所有端点并且每一步距离最短的排序策略。所求问题可描述为求出一个端点排列，激光扫描一个完整汉字前提下激光跳跃距离f最短，见下式：

式中，S为Dim和Djn之间的距离。

为获得最小值f需要对问题分解，具体到本算法，就是在激光扫描完某一笔画后，需要遍历未扫描所有笔画首末端点，计算该笔画激光扫描结束端点距离所有未扫描笔画首末端点的距离S1，S2，S3…，取其最小距离端点作为下一个扫描笔画的起点，如下式所示：

如果计算出的最小距离端点为笔画的末端，则在打标时需要逆向输出此笔画。

3.2 算法流程

算法流程见下。

（1）打开HZK16字库文件提取字模，用点阵二值图像函数f（i，j）（其中i＝1，2，3…16；j＝1，2，3…16）来描述待提取笔画汉字特征。

（2）按行搜索f（i，j）＝1的点，记录该点在点阵中的位置（i，j），标记为首端点，之后置f（i，j）＝0。

Fig.4 Optimization algorithm flow chart

（3）在点（i，j）的八领域按照横向优先规则搜索与该点相邻的连续点（i′，j′），如果搜索到f（i′，j′）＝1，则存储该点在点阵中的位置（i′，j′），之后置f（i′，j′）＝0（其中i′＝1，2，3…16；j′＝1，2，3…16）。如果没搜索到f（i′，j′）＝1的点，则标记点（i′，j′）为末端点，返回到点（i，j）位置，继续步骤（2）。

（4）判断点阵中是否还有f（i，j）＝1，如有则重复步骤（3），如没有则笔画提取完成。

（5）以D12为起点，按（2）式计算距离最短端点序列Dij。

（6）判断序列点Dij是否包含了笔画末端点，如包含则对其对应的笔画数组反向排序更新。

（7）输出D11，Dij序列点对应的笔画。算法流程图如图4所示。

3.3 结果分析

汉字打标总时间为激光打标时间（激光在汉字每点停留时间总和）、激光大距离跳跃、激光小距离跳跃之和。本算法是按笔画连续打标，因此跳跃点数等于笔画数。对上下结构、左右结构及独立结构3种字型汉字采用本算法和点阵扫描激光打标比较，试验结果见表3。将表3中的数据按以下两式分别计算跳跃速度提高和总速度提高均值，可知跳跃速度平均提高60.4%，汉字打标总速度平均提高29.6%。

式中，t1为大距离跳跃时间，t2为小距离跳跃时间，T1为点阵打标总时间，T2为本算法打标总时间。

Table 3 Algorithm comparison

4 结 论

振镜扫描激光汉字打标是是激光制造的一项关键技术，在食品、医药和包装等行业具有广泛应用前景。给出了一种振镜扫描激光汉字打标优化算法，汉字打标效率得到提升，有望在振镜扫描激光汉字打码系统中获得应用。

［1］ LIU W P.Development of laser marking machine based on ARM and FPGA［D］.Nanjing：Nanjing Forestry University，2011：10-11（in Chinese）.

［2］ ZHANG N X.Study on CO2laser marker［D］.Changchun：Changchun University of Science and Technology，2012：8-12（in Chinese）.

［3］ ZHANG Y.High speed and high precision galvanometer laser marking system solutions based on DSP［D］.Wuhan：Huazhong University of Science＆Technology，2007：8-10（in Chinese）.

［4］ SUN L Y，HAN X Ch.The research of NC controller of laserpointer［J］.Machine Design and Manufacturing Engeering，1998，27（6）：44-45（in Chinese）.

［5］ LIU Y Zh.The laser marking system on lattice character optimum processing［D］.Changchun：Changchun Institute of Optics，Fine Mechanics and Physics of Chinese Academy of Sciences，2004：44-48（in Chinese）.

［6］ ZHAO Y F，CHEN X H，ZHENGY，etal.Achievement for scanning project upon the mirror laser online-marking system［J］.Applied Laser，2004，24（1）：41-42（in Chinese）.

［7］ FENG L Y，WANG X，ZHOU JT，et al.Polynomial fitting correction of galvanometer geometric distortion error in laser marking［J］.Laser Technology，2013，37（5）：601-604（in Chinese）.

［8］ BIX J，HAN Zh N.The development of Chinese font and its storage technology［J］.Computer Techniques of Automation and Applications，2007，26（12）：95-96（in Chinese）.

［9］ KUANG Y，WU Y F，WU B，et al.Extraction and optimization of marking path laser marking systems［J］.Laser Technology，2012，36（1）：131-133（in Chinese）.

［10］ TEMLYAKOV V N，ZHELTOV P.On performance of greedy algorithms［J］.Journal of Approximation Theory，2011，163（9）：1134-1145.

Optimization algorithm of galvanometer scanning laser marking for Chinese characters

GAO Shiyi1，XU Chao2，3，YANG Yongqiang2，CHEN Hexing1
（1.Guangzhou Research Institute of Non-ferrous Metals，Guangzhou 510650，China；2.College of Mechanical and Automotive Engineering，South China University of Technology，Guangzhou 510006，China；3.Han’s Yueming Laser Technology Co.Ltd.，Suining 221200，China）

In order to improve the laser marking efficiency，based on the stroke tracking algorithm and the greedy algorithm，an optimum algorithm of galvanometer scanning laser marking for Chinese characters was put forward.Firstly，the continuous strokes of Chinese characters were extracted.Then，the optimal output path of Chinese character strokes was obtained by means of greedy algorithm.Finally laser marking was realized according to the optimal output path.Experimental results show that this algorithm makes the laser jump times decrease and improves the efficiency of Chinese characters laser marking significantly.

laser technique；algorithm optimization；galvanometer scanning；laser marking

TN249

A

10.7510／jgjs.issn.1001-3806.2014.06.014

1001-3806（2014）06-0790-04

广东省重点实验室建设基金资助项目（2012A061400011）

高世一（1973-），男，博士，高级工程师，主要研究领域为自动化焊接及检测。

E-mail：meshiyigao＠163.com

2014-01-06；

2014-03-11