基于粒子群的彩色印刷品圖像分層搜索定位算法

李 強,耿云逸,吳福培,2,李昇平,2,陽 春,陳 練

(1.汕頭大學工學院機電系,廣東 汕頭 515063;2.汕頭輕工裝備研究院,廣東 汕頭 515063)

0 引言

隨著機器視覺技術在印刷品檢測中的推廣應用,印刷的速度和要求越來越高,需要對常見的印刷品表面缺陷,如飛墨、劃痕、刀絲、漏印等進行精確快速檢測.檢測過程包括圖像獲取、圖像處理、目標定位、檢測與識別,而作為中間環節的目標定位在很大程度上制約著缺陷檢測的速度,定位質量的高低也直接影響后續誤判的概率.另一方面,印刷圖像向寬幅面、多色彩的方向發展,圖像本身數據量的增加也對檢測的速度提出了挑戰.為了適應生產的需要,提高產品質量,目標定位作為檢測的一個前提顯得越來越重要.

受復雜生產環境、振動、噪聲、張力變化、傳輸信號中斷等因素的影響,給圖像精確定位帶來了難點,算法本身的不理想也增加了搜索的負擔.為了提高定位的時間,實現模板的快速匹配,文獻[5]對模板圖像進行抽樣提取匹配點,采用遺傳算法的非遍歷機制,迅速收斂到全局最優解,減少匹配過程的計算量.文獻[7]借助模擬退火算法的思想,提出了一種尺度參數可變的散亂點匹配,通過曲線約束進行控制點篩選達到更廣泛的收斂區間和更高的定位精度.這些方法在提高搜索效率上有一定積極作用,但是面對印刷品高速、高精檢測的要求時,多數算法的速度會遇到瓶頸,匹配速度和精度不可均衡,很難滿足生產的要求.針對這一問題,本文首先采用圖像金字塔(圖1),對圖像進行分層預處理,從計算效率和存儲來看,可以快速生成.其次,由于分層后可以確定每層圖像的像素點的個數,因此建立了各層基于特征點的目標函數.最后采用粒子群搜索算法進行分層迭代搜尋,由粗到細求解各層最優匹配參數,相比直接對整幅圖像進行搜索,該方法計算簡單、收斂快,精度高.

圖1 圖像金字塔

1 圖像分層預處理

1.1 圖像分層預處理

圖像金字塔化一般包括兩個步驟:首先,對圖像用低通濾波器進行平滑;其次,對平滑后的圖像在橫縱兩個方向按固定比例(常為0.5)進行抽樣.對任意一幅圖像,通過一個kXk的卷積模板加權平均為新的像素構成的第二級圖像,再在第二級圖像的基礎上構成第三級圖像,持續下去構成一系列的序列.像素大小為mXn的參考模板序列和像素大小為MXN的待測圖像序列分別表示為:

其中,w=1,2,…,p,p是圖像金字塔的層數,具體的分層層數的選擇,根據模板圖像和待匹配的圖像的大小以及k的大小而定.圖2表示的是圖像經過提取邊緣輪后,由高斯低通濾波器進行平滑,生成四層金字塔:

圖2"鐵觀音"分層

圖2 所示為目標圖像"鐵觀音"的邊緣在不同層數下的邊緣檢測.由于金字塔的層數實際對應頻率域的尺度選擇,而多尺度表達隨著尺度參數的增加冗余信息也變得更多.在第二層,邊緣陰影比較清晰的突顯出來;而第三層,由于經過兩次平滑而導致邊緣形狀扭曲變形;而第四層是由第三層平滑得到,如果采用第四層圖像對該圖像結構進行定位和檢測,將會導致更嚴重的偏差,由此可認為該層不適合定位和檢測,是多余的信息.因此,選擇合適的層數或尺度因子對目標圖像的定位與檢測至關重要.

1.2 搜索空間

圖3中,T是參考模板,點個數為mXn,si,j是待測圖像,大小為MXN;坐標(i,j)表示模板覆蓋被搜索圖的左上角坐標;p表示圖像分層層數.則由分層預處理可知:第w層的搜索范圍:

圖3 分層圖

2 印刷品圖像的匹配模型

2.1 點匹配模型

目標定位過程中需要考慮的參數有:平移

參數,旋轉參數,尺度因子等;用圖像的仿射變換來解決圖像間的幾何位置差別.若原圖像素中某一點坐標為(x1,y1),經過仿射變換后的坐標為(x2,y2),則:

可用向量和矩陣表示為P2=T+sRP1.上式中P2,P1為坐標,T是平移向量,tx、ty為歐式空間x方向平移分量、y方向平移分量,s是尺度或比例因子,θ是旋轉因子,R為旋轉矩陣.為了確定變化后的圖像與標準圖像間差異的最小位置,相似性度量采用距離函數的形式:

式中,f(x1,y1)是參考圖像在(x1,y1)的像素點,f(x2,y2)是待匹配圖像在(x2,y2)的像素點.本文將模板和待測圖像進行分層后,可知在第w層上像素點個數分別為:.從而建立像素點的分層匹配模型為:

2.2 粒子群算法(PSO)

粒子群算法是介于遺傳算法和進化規劃之間的一種群體智能算法,由于其隨機搜索的本質,不容易陷入局部最優解,基于適合度概念的進化特征又保證了算法的快速性.在粒子群算法中,每個個體稱為一個"粒子",每個粒子都具有位置矢量和速度矢量,而位置矢量代表問題的一個可能的解.PSO中涉及的主要概念如下.

zi=(zi1,zi2,…,ziD),即群體由m個粒子構成,zi為第i個粒子(i=1,2,…,m)的D維位置矢量,根據事先設定的適應值函數計算zi當前的適應值.vi=(vi1,vi2,…,viD)為粒子的飛行速度,即粒子移動的距離.pi=(pi1,pi2,…,pid,…,piD)為單個粒子搜索到的最優位置.pg=(pg1,pg2,…,pgd,…,pgD)為整個粒子群迄今為止搜索到的最優位置.如圖4為粒子調整位置的示意圖.

圖4中隨機分配3個粒子,求解三個匹配參數,粒子維數為3.以粒子1為例,首先隨機分配起始搜尋位置和粒子速度v1,計算適應值:z11.粒子2、粒子3進行相同的操作,將三個個體極值中的適應度最優個體的位置和適應值記錄到全局極值中.然后,更新速度和位置,v2是按公式(6)更新后的速度,是按公式(7)調整后的下一個搜索點.其中,vpi記錄搜索到最佳位置處單個粒子的速度,vpg記錄搜索到最佳位置處整個粒子的速度.在迭代過程中,粒子反復跟蹤個體和群體的最佳適應值不斷調整自己的位置,從而得到最優解.粒子根據以下式子更新速度和位置:

圖4 粒子群迭代過

其中,i=1,2,…,m;d=1,2,…,D;k是迭代次數,γ是慣性權重因子;r1,r2是[0,1]

之間的隨機數,用來保持群體的多樣性;c1,c2是學習因子.

2.3 基于粒子群的分層搜索

在高速印刷中,在印刷張力的作用下紙張保持相對穩定連續的運動,此時尺度或比例的變化極小,可假設為常量,因此s取1.公式(5)簡化為:該問題可以描述為:以適應度評價函數D=D(T,R,w)為判決基準下,在搜索空間為公式(2)各層上(第w層)找到最佳匹配點的位置時求解匹配參數的值.因此,算法描述如下:

其中,w=1,2,…,p表示金字塔的第w層,ε為設置的門限值.當第w層搜索結束,以取得全局最優解的粒子位置作為下一層的初始搜索位置,縮小了隨機分配搜尋的范圍.其次,由于每個粒子具有向全局最優解接近的趨向,可以很好的避免搜索中的局部最優解,尤其是受到噪聲、振動干擾的突變像素所在位置粒子.

圖5 算法流程圖

3 實驗結果及分析

實驗平臺為Pentium(R)D CPU 2.20GH和2GB內存,在機器視覺處理軟件Halcon下完成.課題在卷筒紙印刷中要求表面缺陷的最小檢測精度為0.2 mm,檢測速度不低于200 m/min,印刷紙的最大幅寬為1020 mm,相當于每秒檢測5張1020X720 mm的單張紙.首先,確定初始化粒子個數m=30,隨機分布到待測圖像上,圖像長寬為361X 160 mm,像素個數為1024X454,匹配模板像素大小為74X84,采用3X3卷積模板對圖像分層.其次,結合最小精度和像素分辨率選定恰當的閾值作為算法迭代的終止條件.最后,由定位參數對待測圖像進行仿射變換實現位置校正.實驗流程如圖6所示.

為了獲取標準圖像,程序連續采集25張印刷品樣品圖像,通過在線學習訓練得到如圖7(a)所示的效果圖.如圖7(b)所示待測圖像總共有300張,分別被處理成不同的旋轉角度:1°,2°,4°,6°.

圖6 實驗流程圖

圖7 實驗圖像

在圖7(b)中,待測圖像存在旋轉偏移,偏移角度為2°,并且有飛墨.在選擇ROI區域后,首先提取區域邊緣特征建立形狀模板,然后模板進行分層,本實驗層數為3層,見圖7(c).采用圖6中的粒子初始參數,對待測圖像分層搜索,如圖7(d)右側與下側邊緣,實驗結果顯示圖像像素的位置整體被校正.

3.1 校正偏差和分層后時間的對比

實驗統計了如表1所示的不同偏移角度下的平均時間和角度對比.同時,測試了如表2所示的不同分層層數下的時間.

表1 不同角度下的偏差和平均時間

表1表示分層數為3層時的角度偏差對比,角度偏移相當于同時存在水平偏移和垂直偏移.算法搜索的角度與實際值存在一定誤差,主要原因有二:一是由于粒子群算法本身在迭代過程的計算誤差不斷累積產生的;其次是對模板進行邊緣匹配時,邊界點或噪聲點對待測圖像的干擾產生的偽邊緣造成邊緣檢測誤差.試驗中對連續圖像進行了多次測試,統計結果顯示平均校正偏差不超過0.1°,即水平誤差達到0.999個像素,垂直誤差達到0.017個像素,校正精度很高.

表2 不同分層下的平均時間

表2表示單層數搜索與多層搜索的時間對比,對單層圖像采用粒子群平均時間超過1s,在相同的參數下對分層后的圖像采用粒子群搜索時間大幅降低.當分層層數為3層,最大角度偏移為6°時,印刷品的校正時間僅僅占檢測時間的27.66%.這是因為,分層前單層圖像和模板匹配時的計算量為(1024-74)X(454-83)=352450,圖像分3層后,最大分辨率圖層下的搜索量降為352450÷9=39161,全部圖層的數據量與分層前數據量相比降低了3倍.對于高精度凹印機,印刷品在印刷位置上是相對平穩的,在印刷張力的作用下圖像偏移的角度要低于2°,實際中匹配的時間要低于測試的時間.

3.2 與其他算法時間對比

按本文算法在搜索時間上,對文獻所提出的幾種算法進行了對比,在相同的硬件條件下,采用相同尺寸的圖片和模板,分層層數為3層,對300張待測印刷品的平均匹配時間進行了統計,如表3:

表3 幾種算法的性能比較

從表3可知,在搜索時間上,文獻[13]和文獻[14]分別采用禁忌搜索和粒子群算法,相對來說提高了速度,文獻[5]對單層模板進行抽樣,采用遺傳算法進行非遍歷機制,相比來說收斂時間更快.本文算法平均時間最低,達到11.7 ms,可知對圖像和模板進行多層抽樣,結合粒子群搜索的特性更能提高算法的實時性.

在粒子群搜索中,粒子在圖像中搜索最佳位置的過程是跟隨當前單個粒子找到的最好位置和群體中的最好位置,是一種單項的信息共享機制.相比遺傳算法的種群向比較均勻的最優區域移動,粒子群的所有粒子加速向自身最好位置靠近的特性使得收斂速度較快;由于金字塔多分辨率表達的每一層分辨率都要減少固定比率,低分辨率下維數小、數據量小.所以在最高層搜索目標時,可快速定位目標圖像的位置,下一層圖像以上一層圖像的最佳點開始搜索定位目標圖像,可避免對整層進行匹配計算量大的問題.因此,該方法可以明顯的降低匹配時間,應用于印刷品全畫面在線檢測系統,實時性和精度都較高.

4 結論

本文建立了印刷品圖像的分層匹配模型,描述了基于粒子群的搜索策略.在此基礎上,提出了一種基于粒子群算法的分層搜索定位方法,解決了工程實踐中因圖像寬幅面、數據量大而帶來的定位時間消耗過大的問題.實驗結果表明,該方法可以很好的對印刷品進行位置校正,校正偏差平均不超過0.1°,對最大偏移角度為6°的圖像搜索時間高達12.6 ms,僅占檢測時間的27.66%,可以實現對印刷品的準確、快速定位.

[1]Glukman J.Scale Variant Image Pyramids[J]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2006,1(10):1069-1075.

[2]Klein S,Staring M,Pluim J P W.Evaluation of optimization methods for nonrigid medical image registration using mutual information and B-splines[J]. IEEE Transactions on Image Processing,2007,16(12):2879-2890.

[3]Wei X L,Zhang H,Ma Y J,et al.An optimization algorithm of image mosaic based on maximum mutual information[J].Journal of Optoelectronics Laser,2009,20(10):1399-1402.

[4]劉建偉,梁晉,梁新合,等.大尺寸工業視覺測量系統[J].光學精密工程,2010,18(1):127-133.

[5]姜凱,陳海霞,劉立峰,等.基于模板抽樣的快速圖像匹配算法[J].光學精密工程,2004,12(3):312-315.

[6]梁鵬,何俊詩,黎紹發.基于多尺度LBP金字塔特征的分類算法[J].計算機工程,2011,37(8):167-168.

[7]魏陽杰,吳成東,董再勵.基于亞像素圖像塊匹配方法的壓電陶瓷驅動特性測量[J].機械工程學報,2010,46(17):152-158.

[8]林洪彬,劉彬,張玉存.逆向工程中點散亂云變尺度配準算法研究[J].機械工程學報,2011,47(14):2-6.

[9]葛寶臻,馬云峰,魏耀林.求解粒子群粒度分布的改進Projection算法[J].光學精密工程,2012,20(1):198-203.

[10]吳福培,張憲民.印刷電路板無鉛焊點假焊的檢測[J].光學精密工程,2011,19(3):698-702.

[11]李博,楊丹,鄧林.移動機器人閉環檢測的視覺字典樹金字塔TF-IDF得分匹配方法[J].自動化學報,2011,37(6):666-673.

[12]王君本,盧選民,賀兆.一種基于魯棒特征的匹配算法[J].計算機工程與科學,2011,33(2):112-117.

[13]程紅,陳文劍.禁忌搜索算法在圖像匹配中的應用研究[J].地理與地理信息科學,2011,27(6):33~35.

[14]王維真,熊義軍,魏開平,等.基于粒子群算法的灰度相關圖像匹配技術[J].計算機工程與應用,2010,46(12):169-171.