侯茂盛，孫明利，楊 帆，李麗娟，朱運(yùn)東，范成博

(長(zhǎng)春理工大學(xué) 光電工程學(xué)院 光電測(cè)控與光信息傳輸技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,吉林 長(zhǎng)春 130022)

引言

激光掃描投影技術(shù)是依據(jù)零部件的三維CAD數(shù)模驅(qū)動(dòng)二維振鏡掃描系統(tǒng)使激光器出射的光線被快速轉(zhuǎn)折，從而在三維空間中任意位置的投影區(qū)域內(nèi)繪制出由激光線快速循環(huán)掃描形成的零部件外形輪廓線框，技術(shù)人員可以通過(guò)清晰、明亮的零部件輪廓線框得到更加直觀和實(shí)用的信息，實(shí)現(xiàn)更精確、高效的零部件安裝定位裝配[1-2]。該技術(shù)現(xiàn)在已被廣泛應(yīng)用于汽車零部件的安裝定位和檢測(cè)、航空航天領(lǐng)域飛行器零部件的精密制造、管線鋪設(shè)、復(fù)合材料鋪疊制造等重點(diǎn)工程[3-6]，可以加速實(shí)現(xiàn)我國(guó)先進(jìn)裝備生產(chǎn)制造的數(shù)字化、智能化，節(jié)省人力物力，是建設(shè)智能化工廠、數(shù)字化車間的必備技術(shù)和設(shè)備[7]。

由于激光掃描投影系統(tǒng)利用了人眼的視覺(jué)暫留效應(yīng)[8]，所以在其應(yīng)用過(guò)程中，如果待投影圖形較為復(fù)雜，掃描整幅圖形的頻率遠(yuǎn)小于20 Hz，投影出圖像發(fā)生閃爍，這種不穩(wěn)定的現(xiàn)象被稱為“頻閃”[9-10]。掃描投影圖形的頻閃不利于實(shí)際裝配現(xiàn)場(chǎng)的輔助定位裝配。為解決上述問(wèn)題，研究并提出了一種改進(jìn)Fleury算法的激光掃描投影路徑優(yōu)化方法，減少掃描圖像所需時(shí)間，改善所研發(fā)激光掃描投影儀器的頻閃問(wèn)題，保證掃描圖像質(zhì)量，在定位、裝配等實(shí)際應(yīng)用中獲得更理想的效果。

首先介紹了路徑優(yōu)化問(wèn)題的圖論基礎(chǔ)，分析了基于圖論理論解決激光掃描投影系統(tǒng)路徑優(yōu)化的可行性，利用Fleury算法實(shí)現(xiàn)激光掃描投影系統(tǒng)歐拉路徑優(yōu)化，并針對(duì)Fleury算法無(wú)法優(yōu)化非歐拉路徑的局限性加以改進(jìn)，提出改進(jìn)的Fleury算法并對(duì)激光掃描投影系統(tǒng)的掃描路徑優(yōu)化進(jìn)行仿真分析，再應(yīng)用于研發(fā)的激光掃描投影系統(tǒng)中進(jìn)行驗(yàn)證實(shí)驗(yàn)。

1 掃描路徑優(yōu)化問(wèn)題的圖論基礎(chǔ)

1736年，瑞典數(shù)學(xué)家歐拉(Leonhand Euler)解決了哥尼斯堡七橋問(wèn)題，由此開創(chuàng)了圖論學(xué)科的研究[11]。

圖論是離散數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象，由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有的這種關(guān)系[12]。

在激光掃描投影系統(tǒng)中，要利用例如圖1(a)所示的零部件的CAD數(shù)模，在待投影平面掃描出清晰的激光輪廓線框，這種由投影控制點(diǎn)和輪廓線組成的掃描線框可以抽象為圖論里的頂點(diǎn)和邊，這就將激光掃描投影技術(shù)與圖論相結(jié)合，如圖1(b)所示，得到了一個(gè)研究激光掃描投影系統(tǒng)路徑優(yōu)化問(wèn)題的新思路。

圖1 激光掃描投影圖形的原理Fig.1 Principle of laser scanning projection graph

1.1 圖的概念

圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)[13]。如圖2所示，設(shè)圖G=(V,E)，與頂點(diǎn)v相關(guān)聯(lián)的邊e的個(gè)數(shù)稱為頂點(diǎn)v的度。度為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)稱為偶點(diǎn)。圖2中，v1,v2,v3,v4的度都為3，都是奇點(diǎn)。

圖2 圖的概念Fig.2 Definition of graph

假設(shè)圖G=(V,E)，有n個(gè)頂點(diǎn)，即V={V0,V1,V2,V3,…,Vn-1}，E可以用如下的形式的矩陣D描述，對(duì)于矩陣D中的每一個(gè)元素di，滿足：

(1)

從定義中可以看出矩陣D中的元素dij表示了頂點(diǎn)Vi和頂點(diǎn)Vj之間邊的關(guān)系，dij的值表示了該邊的權(quán)值。

由此圖2中的矩形可表示為鄰接矩陣：

(2)

1.2 Euler圖在激光掃描投影路徑優(yōu)化中的應(yīng)用

歐拉解決哥尼斯堡問(wèn)題的實(shí)質(zhì)就是在圖G中尋找經(jīng)過(guò)每一條邊一次且僅一次的閉跡。經(jīng)過(guò)圖G的每條邊至少一次的閉跡稱為圖G的環(huán)游；經(jīng)過(guò)每條邊僅一次的環(huán)游稱為圖G的Euler環(huán)游。包含Euler環(huán)游的圖稱為Euler圖[14]。

在激光掃描投影系統(tǒng)的應(yīng)用中，為了繪制一個(gè)完整的激光掃描投影圖像，掃描時(shí)需要用空白跳轉(zhuǎn)線來(lái)連接可見輪廓線。二維振鏡連續(xù)掃描的同時(shí)開閉激光器實(shí)現(xiàn)輪廓線和跳轉(zhuǎn)線的繪制。在上述過(guò)程中，繪制可見輪廓線和不可見的跳轉(zhuǎn)線都需要耗費(fèi)時(shí)間。若待掃描的圖像不需要添加跳轉(zhuǎn)線，輪廓線也不重復(fù)繪制，就可以優(yōu)化掃描路徑，減少不必要的時(shí)間浪費(fèi)，有效改善頻閃問(wèn)題。

2 基于改進(jìn)FLeury算法的掃描投影路徑規(guī)劃

2.1 Fleury算法的實(shí)現(xiàn)

當(dāng)待掃描的圖形可以抽象為歐拉回路時(shí)，應(yīng)用Fleury算法依次描繪每一條輪廓線從而得到歐拉掃描路徑。Fleury算法的基本步驟[15]如下：

1) ?v0∈V(E)，令W0=v0；

2) 若Wi=v0e1v1e2…eivi已選定，則從E-{e1,e2,…,ei}中選取一條邊ei+1，使得：a)ei+1與ei相鄰；b)除非已經(jīng)無(wú)選擇余地，否則ei+1不要選Gi=G-{e1,…,ei}的橋。

3) 直到上一步不能繼續(xù)循環(huán)為止。

激光掃描投影系統(tǒng)掃描路徑優(yōu)化方法的主要邏輯與Fleury算法的步驟相對(duì)應(yīng)：a) 判斷待掃描圖形是否為歐拉圖，如果不是，則跳出程序；b) 確定歐拉回路的投影起點(diǎn)和起始輪廓線；c) 尋找接下來(lái)需要掃描的輪廓線和接下來(lái)需要掃描的投影控制點(diǎn)，直到完成圖形掃描；d) 輸出掃描路徑及其所對(duì)應(yīng)的權(quán)值，完成激光掃描投影路徑的優(yōu)化。

流程圖如圖3所示。

圖3 激光掃描投影路徑優(yōu)化流程圖Fig.3 Flow chart of laser scanning projectionpath optimization

在選擇下一條投影輪廓線時(shí)，要判斷這條輪廓線的終點(diǎn)dvex是否符合Fleury原理的判定，如圖4所示。若符合則可以在程序中更新掃描路徑矩陣，便于進(jìn)行下一次循環(huán)過(guò)程。若找不到下一個(gè)投影控制點(diǎn)，也就是程序中dvex=0時(shí)，則跳出循環(huán)，在之前的步驟中重新搜索可以實(shí)現(xiàn)的掃描路徑。

圖4 選擇下一條輪廓線Fig.4 Selecting the next contour line

圖5 選擇下一個(gè)投影控制點(diǎn)Fig.5 Selecting the next projection control point

在選擇下一個(gè)掃描輪廓線的端點(diǎn)時(shí)，要進(jìn)行多次判斷，如圖5所示。

1) 判斷下一個(gè)掃描投影點(diǎn)是否唯一。如果在當(dāng)前軌跡下只有一點(diǎn)可以選擇，直接選取該點(diǎn)為下一掃描點(diǎn)。

2) 倘若下一點(diǎn)有多個(gè)選擇，需要判斷這個(gè)投影控制點(diǎn)是否在之前的軌跡中已經(jīng)掃描過(guò)。如果沒(méi)有掃描，可以把這個(gè)點(diǎn)當(dāng)做下一個(gè)控制點(diǎn)的備選之一；如果這些鄰接的點(diǎn)全部掃描過(guò)，就要進(jìn)行下一步的判斷。

3) 如步驟2)中所述，當(dāng)可以選擇的所有的投影控制點(diǎn)已全部掃描過(guò)，判斷所有備選點(diǎn)和當(dāng)前投影點(diǎn)的連線在之前的路徑中是否已經(jīng)存在。倘若所有的路徑都已掃描過(guò)，那么當(dāng)前控制點(diǎn)的選擇發(fā)生錯(cuò)誤，跳出函數(shù)，重新尋找路徑。如果已掃描過(guò)的的路徑中沒(méi)有找到這條路徑，那么這條輪廓線可以作為備選以進(jìn)行下一步的判斷。

4) 根據(jù)Fleury算法的基本原理，如果有其他的路徑可以選擇，就不能選擇橋作為下一條輪廓線。所以此處應(yīng)對(duì)這些線段是否為橋進(jìn)行判斷。倘若為橋，則循環(huán)到下一條可以選擇的線段；若不是橋，則該線段所對(duì)應(yīng)的終點(diǎn)即作為輸出。

2.2 Fleury算法改進(jìn)

由于Fleury算法只能解決歐拉圖的路徑優(yōu)化問(wèn)題[16]，當(dāng)判斷輸入的投影圖形為非歐拉圖時(shí)，程序?qū)⒅苯咏Y(jié)束。但是在實(shí)際應(yīng)用中，待投影的圖形一般為非歐拉圖，所以本文提出一種改進(jìn)的Fleury算法，將非歐拉投影圖形轉(zhuǎn)化為歐拉圖。

在判斷原投影圖為非歐拉圖的情況下，需要對(duì)原圖進(jìn)行改造，使其變成歐拉圖。流程圖如圖6所示，在原投影圖中，奇點(diǎn)個(gè)數(shù)大于等于2，所以只需將奇點(diǎn)轉(zhuǎn)變成偶點(diǎn)就可以完成歐拉圖的構(gòu)造。因此對(duì)這些奇點(diǎn)進(jìn)行配對(duì)處理，配對(duì)的原則：選擇未相連的兩個(gè)奇點(diǎn)進(jìn)行連線，使其均變?yōu)榕键c(diǎn)。當(dāng)奇點(diǎn)個(gè)數(shù)確認(rèn)為0，即可跳出循環(huán)，得到新的鄰接矩陣，也就得到了改造過(guò)的歐拉圖。這樣就可以應(yīng)用上述Fleury算法對(duì)激光掃描投影路徑進(jìn)行優(yōu)化。

圖6 Fleury算法的改進(jìn)Fig.6 Improvement of Fleury algorithm

3 路徑優(yōu)化算法仿真實(shí)例

在激光掃描投影系統(tǒng)的實(shí)際應(yīng)用中，當(dāng)待投影圖形為多行多列矩陣時(shí)，因其可選擇路徑較多且均為非歐拉路徑，更易發(fā)生頻閃。所以本章以如圖7所示的3×3“棋盤式”投影圖形為模型進(jìn)行MATLAB環(huán)境下的路徑優(yōu)化仿真分析，驗(yàn)證改進(jìn)的Fleury算法是否可以達(dá)到預(yù)期效果。

圖7 投影圖像仿真模型Fig.7 Simulation model of projected image

整體仿真過(guò)程有如下4個(gè)階段。

3.1 待投影圖形鄰接矩陣的判斷及優(yōu)化

該投影圖共有16個(gè)投影控制點(diǎn)，該圖對(duì)應(yīng)的鄰接矩陣尺寸為16×16，通過(guò)圖的邏輯將兩點(diǎn)之間的通斷用0或1進(jìn)行表示，從而得出該圖對(duì)應(yīng)的鄰接矩陣(如圖8)。通過(guò)鄰接矩陣進(jìn)行判斷，得出該投影圖為非歐拉圖。添加空白跳轉(zhuǎn)線段將奇點(diǎn)優(yōu)化為偶點(diǎn)，從而得出新的鄰接矩陣(如圖9)，將原來(lái)的非歐拉圖轉(zhuǎn)化為現(xiàn)在的帶有空白線的歐拉圖。

圖8 非歐拉圖的鄰接矩陣Fig.8 Adjacency matrix of non-Euler graph

圖9 根據(jù)更改后的鄰接矩陣得到歐拉圖Fig.9 Eulerian graph based on modified adjacency matrix

3.2 確定起始路徑

默認(rèn)投影起始點(diǎn)為v1，在鄰接矩陣中的第一行進(jìn)行搜索，找到與投影起始點(diǎn)v1相接的點(diǎn)的位置：

t1=find(b(vet,:)==1)

(2)

式中：vet是起點(diǎn)v1；b為優(yōu)化后的鄰接矩陣，則t1=[v2,v8]。

那么起始掃描路徑也就是從v1-v2和v1-v8這兩條輪廓線中選擇。先將v1-v2賦值在路徑矩陣的第一列中作為起始路徑，再進(jìn)入后續(xù)處理流程。如果發(fā)現(xiàn)v1-v2這條起始路徑并不能得到期望的整體路徑，則將v1-v8重新賦值在路徑矩陣中，重新進(jìn)行路徑規(guī)劃。

3.3 依次確定后續(xù)路徑

繼續(xù)在鄰接矩陣中尋找與當(dāng)前投影控制點(diǎn)相銜接的點(diǎn)，并通過(guò)可選擇投影點(diǎn)的個(gè)數(shù)，進(jìn)行不同的邏輯運(yùn)算。

1) 如果只有一個(gè)可選擇的投影控制點(diǎn)，可直接將這一點(diǎn)作為路徑中的下一個(gè)控制點(diǎn)。例如，掃描至點(diǎn)v13時(shí)，不論剛剛掃描過(guò)v12-v13還是v14-v13，都僅剩一點(diǎn)可以選擇。

2) 如果可選擇的點(diǎn)在之前的掃描路徑中沒(méi)有出現(xiàn)過(guò)，通常情況下都可以作為備選點(diǎn)。例如，當(dāng)掃描至v2時(shí)，v3、v7、v8都是未掃描過(guò)的投影點(diǎn)，可以使用一個(gè)循環(huán)去判斷哪個(gè)投影點(diǎn)更為合適，即選為下一個(gè)投影控制點(diǎn)。

3) 如果可選擇的點(diǎn)都已存在于掃描路徑中，就需要判斷當(dāng)前投影點(diǎn)與可選擇的投影點(diǎn)所連接成的掃描路徑是否在之前的路徑中已經(jīng)存在。若都已存在，則需要跳出循環(huán)，重新進(jìn)行上一級(jí)循環(huán)。

綜上所述，選擇掃描路徑的優(yōu)先順序是：先選唯一的，再選相關(guān)性低的，若都沒(méi)有只能選擇重復(fù)經(jīng)歷的投影控制點(diǎn)。

3.4 輸出路徑與權(quán)值

由上述過(guò)程逐步建立的路徑矩陣即為輸出的掃描路徑，在本模型中，得到的掃描路徑矩陣和權(quán)值，如圖10所示。

圖10 輸出的路徑與權(quán)值Fig.10 Output path and weight

4 實(shí)驗(yàn)結(jié)果

圖11為自主研發(fā)激光掃描投影系統(tǒng)試驗(yàn)裝置。右上為與計(jì)算機(jī)相連接的數(shù)據(jù)采集卡。

圖11 自主研發(fā)的激光掃描投影系統(tǒng)Fig.11 Laser scanning and projection systemindependently developed

實(shí)驗(yàn)使用搭建的激光掃描投影系統(tǒng)在投影面上投影出一個(gè)5×5矩陣。投影時(shí)，將待投影圖像的數(shù)模寫入計(jì)算機(jī)，經(jīng)計(jì)算機(jī)自主處理后將待投影圖像信息寫入數(shù)據(jù)采集卡，經(jīng)過(guò)開閉激光器、二維掃描振鏡不斷偏轉(zhuǎn)等過(guò)程，將該圖形投影至投影平面。計(jì)算機(jī)軟件界面顯示繪制該圖形的頻率為15.2 Hz，圖像頻閃問(wèn)題較為嚴(yán)重，導(dǎo)致無(wú)法拍攝出完整的投影圖形，如圖12所示。

圖13 改進(jìn)Fleury算法優(yōu)化掃描路徑后的復(fù)雜圖形投影Fig.13 Complex graph projection after path optimizationwith improved Fleury algorithm

將改進(jìn)Fleury算法程序?qū)懭胗?jì)算機(jī)。當(dāng)待投影圖形的數(shù)模文件寫入計(jì)算機(jī)后，使用該算法對(duì)掃描路徑進(jìn)行規(guī)劃，輸出優(yōu)化后的路徑，寫入數(shù)據(jù)采集裝置，繼續(xù)投影。計(jì)算機(jī)軟件界面顯示繪制該圖形的頻率為25.6 Hz，圖像頻閃問(wèn)題得到明顯改善，如圖13所示。

5 結(jié)論

依據(jù)激光掃描投影系統(tǒng)的成像原理，將圖論理論與激光掃描投影圖形相聯(lián)系，并將求解歐拉回路的Fleury算法應(yīng)用于激光掃描投影路徑規(guī)劃，且針對(duì)該算法無(wú)法優(yōu)化非歐拉路徑的局限性，提出了改進(jìn)的Fleury算法。利用MATLAB仿真軟件對(duì)上述算法的掃描路徑規(guī)劃效果進(jìn)行仿真分析，優(yōu)化得到最佳的歐拉路徑。將多行多列矩陣輸入掃描投影系統(tǒng)，實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，未經(jīng)優(yōu)化的投影圖形頻閃問(wèn)題較為嚴(yán)重，輔助定位裝配的效果也受到影響。經(jīng)改進(jìn)Fleury算法規(guī)劃后的激光掃描投影路徑投影出的圖像，掃描頻率更高，頻閃問(wèn)題得到有效改善，能夠達(dá)到實(shí)際工程應(yīng)用中對(duì)零部件的精準(zhǔn)定位要求。