一種振鏡掃描漢字激光打標優化算法

高世一，許 超，楊永強，陳和興

（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