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

高世一，許 超，楊永強(qiáng)，陳和興

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

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

高世一1，許 超2，3，楊永強(qiáng)2，陳和興1

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

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

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

引 言

激光打標(biāo)是繼激光焊接、激光切割、激光雕刻之后新發(fā)展起來(lái)的又一項(xiàng)先進(jìn)激光制造技術(shù)。它利用高能量密度激光束對(duì)材料局部加熱，使之融化并發(fā)生物理化學(xué)變化，在物體表面留下永久性標(biāo)記。激光打標(biāo)相比于傳統(tǒng)打標(biāo)技術(shù)具有很多優(yōu)勢(shì)［1-2］：（1）激光通過(guò)光學(xué)系統(tǒng)可形成微細(xì)光束，在物體表面形成最小直徑約0.1mm光斑，非常適合高精度打標(biāo)；（2）能獲得高質(zhì)量、永久性標(biāo)記，不會(huì)因?yàn)橛|摸或者放置時(shí)間長(zhǎng)久產(chǎn)生模糊、消退現(xiàn)象；（3）相對(duì)傳統(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)定性好、定位精度高等特點(diǎn)，非常適用于流水生產(chǎn)線高速打標(biāo)［4］。

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

1 激光振鏡掃描原理

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

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

2 激光振鏡掃描漢字分析

2.1 漢字存儲(chǔ)方式

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

Fig.2 Chinese character storage and laser scanning point

2.2 漢字激光振鏡掃描

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

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

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

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

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 算法分析

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

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

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

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

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

3.2 算法流程

算法流程見下。

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

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

Fig.4 Optimization algorithm flow chart

（3）在點(diǎn)（i，j）的八領(lǐng)域按照橫向優(yōu)先規(guī)則搜索與該點(diǎn)相鄰的連續(xù)點(diǎn)（i′，j′），如果搜索到f（i′，j′）＝1，則存儲(chǔ)該點(diǎn)在點(diǎn)陣中的位置（i′，j′），之后置f（i′，j′）＝0（其中i′＝1，2，3…16；j′＝1，2，3…16）。如果沒搜索到f（i′，j′）＝1的點(diǎn)，則標(biāo)記點(diǎn)（i′，j′）為末端點(diǎn)，返回到點(diǎn)（i，j）位置，繼續(xù)步驟（2）。

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

（5）以D12為起點(diǎn)，按（2）式計(jì)算距離最短端點(diǎn)序列Dij。

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

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

3.3 結(jié)果分析

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

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

Table 3 Algorithm comparison

4 結(jié) 論

振鏡掃描激光漢字打標(biāo)是是激光制造的一項(xiàng)關(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

廣東省重點(diǎn)實(shí)驗(yàn)室建設(shè)基金資助項(xiàng)目（2012A061400011）

高世一（1973-），男，博士，高級(jí)工程師，主要研究領(lǐng)域?yàn)樽詣?dòng)化焊接及檢測(cè)。

E-mail：meshiyigao＠163.com

2014-01-06；

2014-03-11