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

（1.廣州有色金屬研究院，廣州510650；2.華南理工大學(xué)機械與汽車工程學(xué)院，廣州510006；3.大族粵銘激光科技有限公司，睢寧221200）

一種振鏡掃描漢字激光打標(biāo)優(yōu)化算法

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

（1.廣州有色金屬研究院，廣州510650；2.華南理工大學(xué)機械與汽車工程學(xué)院，廣州510006；3.大族粵銘激光科技有限公司，睢寧221200）

為了提高漢字激光打標(biāo)效率，結(jié)合筆畫跟蹤算法和貪心算法，給出了一種振鏡式漢字激光打標(biāo)優(yōu)化算法。該算法首先提取出漢字的連續(xù)筆畫，然后運用貪心算法獲得漢字筆畫最優(yōu)輸出路徑，最后按最優(yōu)路徑實現(xiàn)激光打標(biāo)。結(jié)果表明，該算法減少了激光大跳躍次數(shù)，提高了漢字激光打標(biāo)效率。

激光技術(shù)；算法優(yōu)化；振鏡掃描；激光打標(biāo)

引 言

激光打標(biāo)是繼激光焊接、激光切割、激光雕刻之后新發(fā)展起來的又一項先進(jìn)激光制造技術(shù)。它利用高能量密度激光束對材料局部加熱，使之融化并發(fā)生物理化學(xué)變化，在物體表面留下永久性標(biāo)記。激光打標(biāo)相比于傳統(tǒng)打標(biāo)技術(shù)具有很多優(yōu)勢［1-2］：（1）激光通過光學(xué)系統(tǒng)可形成微細(xì)光束，在物體表面形成最小直徑約0.1mm光斑，非常適合高精度打標(biāo)；（2）能獲得高質(zhì)量、永久性標(biāo)記，不會因為觸摸或者放置時間長久產(chǎn)生模糊、消退現(xiàn)象；（3）相對傳統(tǒng)的噴墨噴碼技術(shù)，不需要油墨等耗材，節(jié)約成本、綠色環(huán)保。

激光打標(biāo)自誕生之日到現(xiàn)今，經(jīng)歷了不同發(fā)展階段［3］，目前最為先進(jìn)的激光打標(biāo)方式是采用振鏡掃描的激光打標(biāo)。采用振鏡掃描激光打標(biāo)，具有打標(biāo)速度快、穩(wěn)定性好、定位精度高等特點，非常適用于流水生產(chǎn)線高速打標(biāo)［4］。

對于標(biāo)點符號、數(shù)字及英文字母等字符，由于字形簡單、筆畫數(shù)目少，打標(biāo)較易實現(xiàn)。但對于漢字，特別是筆畫數(shù)目多、字形復(fù)雜的漢字，需要深入研究打標(biāo)算法及其效率。為了提高漢字打標(biāo)效率，參考文獻(xiàn)［5］中提出了筆畫跟蹤算法。作者在筆畫跟蹤算法基礎(chǔ)上，進(jìn)一步采用貪心算法對打標(biāo)的各筆畫首末端點重新排序優(yōu)化，提高了激光打標(biāo)效率。

1 激光振鏡掃描原理

激光振鏡掃描原理如圖1所示，激光器發(fā)出的光束被x軸振鏡和y軸振鏡反射后，透過平面場鏡在工件表面某點聚焦，在激光作用下該點發(fā)生熱化學(xué)反應(yīng)形成一個永久標(biāo)記。通過控制x軸和y軸振鏡偏轉(zhuǎn)角度來控制激光束在平面的掃描路徑，振鏡偏轉(zhuǎn)角度與激光束在工件平面焦點位置的數(shù)學(xué)模型見參考文獻(xiàn)［6］。

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

2 激光振鏡掃描漢字分析

2.1 漢字存儲方式

漢字通常以點陣圖的方式存儲在計算機中［7］。如HZK16字庫中的漢字按16×16點陣存儲，具有二值圖像特征，構(gòu)成漢字的點用“1”標(biāo)識，其余的點用“0”標(biāo)識。以漢字“華”為例，存儲方式見圖2。振鏡掃描時要保證在漢字點陣圖中1的位置開啟激光，而在0的位置關(guān)閉激光。

Fig.2 Chinese character storage and laser scanning point

2.2 漢字激光振鏡掃描

激光振鏡掃描漢字包括連續(xù)掃描和跳躍掃描兩種方式，連續(xù)掃描是指激光掃描同一筆畫上的連續(xù)點，跳躍掃描是指激光在不同筆畫首末端點之間跳躍。激光在構(gòu)成漢字的每個點上停留時間設(shè)定為1.8ms。

為了獲得連續(xù)掃描和跳躍掃描的振鏡偏轉(zhuǎn)定位時間，采用德國PRO公司制造的幀率為7000幀／s的高速攝像機拍攝激光打標(biāo)時光斑位置并記錄時間，圖3為其中的4幀圖像。

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

從拍攝到的多幀激光光斑圖像可計算出連續(xù)掃描時筆畫上各點平均用時，減去激光停留時間1.8ms后，即可得到連續(xù)掃描筆畫各點振鏡偏轉(zhuǎn)定位時間，結(jié)果見表1。同理，拍攝到的多幀激光光斑圖像記錄了激光跳躍時前后時間，其時間差就是激光跳躍時振鏡偏轉(zhuǎn)定位時間?？紤]到在不同筆畫間跳躍時跳躍的間隔點不同，把跳躍間隔點分為兩類：大距離跳躍（大于5個間隔點）和小距離跳躍（不大于5個間隔點），結(jié)果見表2。從表1及表2可知，連續(xù)掃描振鏡偏轉(zhuǎn)定位時間可不計，而跳躍掃描鏡偏轉(zhuǎn)定位時間不可忽略。

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 激光振鏡掃描漢字算法優(yōu)化

3.1 算法分析

漢字點陣掃描因激光跳躍頻繁降低了漢字打標(biāo)效率，參考文獻(xiàn)［5］中提出了筆畫跟蹤算法，按筆畫搜索順序輸出漢字各筆畫。該算法沒有對筆畫輸出順序進(jìn)一步分析，在一個筆畫的末端到另一個筆畫的首端經(jīng)常遇到激光大距離跳躍問題。為減少筆畫輸出的激光大距離跳躍問題，作者在提取漢字筆畫后，采用貪心算法對筆畫端點路徑進(jìn)行優(yōu)化。貪心算法在對問題求解時，總是做出在當(dāng)前看來是最好的選擇［8-9］，非常適用于激光振鏡掃描漢字優(yōu)化，可獲得近似全局最優(yōu)解且算法執(zhí)行效率高。

漢字筆畫跟蹤有3種不同的搜索策略，這里采用按行搜索和橫向優(yōu)先的組合搜索方法［10］。筆畫跟蹤某個漢字后將產(chǎn)生n個筆畫，每個筆畫的首末端點分別為D11，D12，D21，D22，D31，D32，D41，D42等，其中物理量D的第1個下標(biāo)表示筆畫數(shù)，第2個下標(biāo)表示該筆畫上的端點標(biāo)記。應(yīng)用貪心算法，在獲得漢字的各個筆畫數(shù)組后，對漢字全部筆畫的所有首末端點進(jìn)行排序，找到一個遍歷所有端點并且每一步距離最短的排序策略。所求問題可描述為求出一個端點排列，激光掃描一個完整漢字前提下激光跳躍距離f最短，見下式：

式中，S為Dim和Djn之間的距離。

為獲得最小值f需要對問題分解，具體到本算法，就是在激光掃描完某一筆畫后，需要遍歷未掃描所有筆畫首末端點，計算該筆畫激光掃描結(jié)束端點距離所有未掃描筆畫首末端點的距離S1，S2，S3…，取其最小距離端點作為下一個掃描筆畫的起點，如下式所示：

如果計算出的最小距離端點為筆畫的末端，則在打標(biāo)時需要逆向輸出此筆畫。

3.2 算法流程

算法流程見下。

（1）打開HZK16字庫文件提取字模，用點陣二值圖像函數(shù)f（i，j）（其中i＝1，2，3…16；j＝1，2，3…16）來描述待提取筆畫漢字特征。

（2）按行搜索f（i，j）＝1的點，記錄該點在點陣中的位置（i，j），標(biāo)記為首端點，之后置f（i，j）＝0。

Fig.4 Optimization algorithm flow chart

（3）在點（i，j）的八領(lǐng)域按照橫向優(yōu)先規(guī)則搜索與該點相鄰的連續(xù)點（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的點，則標(biāo)記點（i′，j′）為末端點，返回到點（i，j）位置，繼續(xù)步驟（2）。

（4）判斷點陣中是否還有f（i，j）＝1，如有則重復(fù)步驟（3），如沒有則筆畫提取完成。

（5）以D12為起點，按（2）式計算距離最短端點序列Dij。

（6）判斷序列點Dij是否包含了筆畫末端點，如包含則對其對應(yīng)的筆畫數(shù)組反向排序更新。

（7）輸出D11，Dij序列點對應(yīng)的筆畫。算法流程圖如圖4所示。

3.3 結(jié)果分析

漢字打標(biāo)總時間為激光打標(biāo)時間（激光在漢字每點停留時間總和）、激光大距離跳躍、激光小距離跳躍之和。本算法是按筆畫連續(xù)打標(biāo)，因此跳躍點數(shù)等于筆畫數(shù)。對上下結(jié)構(gòu)、左右結(jié)構(gòu)及獨立結(jié)構(gòu)3種字型漢字采用本算法和點陣掃描激光打標(biāo)比較，試驗結(jié)果見表3。將表3中的數(shù)據(jù)按以下兩式分別計算跳躍速度提高和總速度提高均值，可知跳躍速度平均提高60.4%，漢字打標(biāo)總速度平均提高29.6%。

式中，t1為大距離跳躍時間，t2為小距離跳躍時間，T1為點陣打標(biāo)總時間，T2為本算法打標(biāo)總時間。

Table 3 Algorithm comparison

4 結(jié) 論

振鏡掃描激光漢字打標(biāo)是是激光制造的一項關(guān)鍵技術(shù)，在食品、醫(yī)藥和包裝等行業(yè)具有廣泛應(yīng)用前景。給出了一種振鏡掃描激光漢字打標(biāo)優(yōu)化算法，漢字打標(biāo)效率得到提升，有望在振鏡掃描激光漢字打碼系統(tǒng)中獲得應(yīng)用。

［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，F(xiàn)ine 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

廣東省重點實驗室建設(shè)基金資助項目（2012A061400011）

高世一（1973-），男，博士，高級工程師，主要研究領(lǐng)域為自動化焊接及檢測。

E-mail：meshiyigao＠163.com

2014-01-06；

2014-03-11