基于遺傳算法的二維QR碼圖像識別

1、第26卷第4期2005年12月大連鐵道學院學報JOURNAL OF DAL I A N RA I L WAY I N STI T UTE Vol .26No .4Dec .2005文章編號:100021670(20050420047205基于遺傳算法的二維QR 碼圖像識別谷曉琳,黃明,戚海英(大連交通大學電氣信息學院,遼寧大連1160283摘要:基元識別是二維碼圖像識別中的一個關鍵問題,提出了基于遺傳算法的QR 碼識別方法.首先建立QR 碼待識別模式模型,據此進行遺傳算法,通過實例進行圖像識別.該方法抓住了QR 碼基元的重要特征,利用改進遺傳算法,可以提高QR 碼圖像的識別效率.關鍵詞:遺傳算

2、法;二維碼;QR 碼;圖像識別中圖分類號:TP391.41文獻標識碼:A22D i m en si ona l Bar Code Recogn iti on Ba sed on Geneti c A lgor ithm sG U Xiao 2lin,HUANG M ing,Q I Hai 2yin(School of Electric &I nf or mati on,Dalian J iaot ong University,Dalian 116028,China Abstract:Funda mental recogniti on is a main p r oble m in th

3、e 22D i m ensi onal bar codes .A QR Code identify p r oble m based on genetic algorithm s is p r oposed by the p r ocess of the esfablishment of QR Code pattern recogniti on model,operati on of G A and i m age recogniti on .This method gras p s the i m portant characteristic of the QR Code,and i m p

4、 r ove the efficiency of QR Code recogniti on greatly .Key words:genetic algorithm s;22di m ensi onal bar codes;QR code;i m age identifyQR 碼(Quick Res ponse Code 是由日本Dens o 公司于1994年9月研制的一種矩陣二維碼符號,它除具有一維條碼及其它二維條碼所具有的信息容量大、可靠性高、可表示漢字及圖像多種文字信息、保密防偽性強等優(yōu)點外還具有超高速響應、全方位識讀、可離線應用的便攜式數據庫、能夠有效地表示數字字母、漢字、圖像等特點1

5、,2.QR Code 碼的尺寸小于相同密度的P DF417條碼,專有的漢字模式更加圖1QR 碼的例子圖2QR 碼的構造適合我國應用.圖1就是一個QR Code 碼的例子.目前,QR 碼的識別多是使用掃描器,其應用就被很大程度地限制于硬件.現在數碼拍攝設備正在逐漸普及,數碼相機、攝像頭隨處可見,如果使用這樣的通用設備拍攝包含QR 碼的圖像,再通過軟件對圖像進行識別,就能夠讓QR 碼的特點得到更多的發(fā)揮和應用.問題就在軟件如何進行QR 碼的識別.這就歸結于圖像分析中的基元識別.圖像分析和處理是計算機視覺中的一個熱點研究領域,受到日益廣泛的關注,而圖像基元的識別和提取是圖像分析的重要任務.通常將簡單

6、的模式圖形如三角形、矩形、圓等稱為基元.從圖象中識別和提3收稿日期:2005204220作者簡介:谷曉琳(1978-,女,助教,碩士148大連鐵道學院學報第26卷因此,本文提出了基于遺傳算法的QR碼圖像識別,目的在于提高軟件識別QR碼的識別率,拓寬QR碼的使用范圍,降低QR碼的使用門檻.1QR碼識別的問題1.1QR碼的構造特征一個QR碼稱為一個符號,QR碼中每一個顏色點稱為模塊.從版本1到版本40,符號的規(guī)格分別是21×21個模塊到177×177個模塊,其間每一規(guī)格在每條邊增加4個模塊.以版本1為例,符號的構造如圖2所示,圖中黑白顏色的模塊是QR碼的位置檢測部分,其余模塊是

7、數據和校驗部分.符號中左上、右上和左下角的8×8個模塊是固定的,不隨版本變化.1.2QR碼圖像的約束分析拍攝下來的QR碼圖像總結起來有以下幾個特征:(1由于拍攝設備的不同,拍攝的圖像通常情況下是寬度大于等于高度的矩形.(2拍攝的時候有人主觀的參與,保證了圖像的主體是QR碼,并且會完全容納QR碼.(3QR碼在圖像中的位置不固定.(4拍攝的角度和距離不同,圖像中的QR碼會有旋轉、放大和拉伸.1.3識別QR碼的主要問題QR碼的識別首先要確定符號在圖像中的位置,就是圖像中固定部分的識別問題,然后再進行數據的讀取.只要識別出檢測部分,讀取就不是難事.所以將符號中的檢測部分整體作為一個待識別模式

8、,對其進行識別就是要解決的主要問題.2模式識別問題的模型建立定義QR碼版本為v,用于檢測識別的模塊數為N,則:N=6433+1+(21+43(v-1-1632(v1,40,整數(1將QR碼符號的位置檢測模塊的集合視為一個待識別模式,一個模塊視為一個點,則待識別模式的點序列P的描述為:P=p(x1,y1,p(x2,y2,p(x N,y N(2其中,(xi,y i為相對于模式原點也就是QR碼符號的重心(x0,y0的坐標,p(為相應的灰度值,將模式放大M倍,旋轉并將模式原點移至(xc,y c,則點序列P變?yōu)镼:Q=p(x31,y31,p(x32,y32,p(x3N,y3N(3 其中x3jy3j =M

9、co s-sinsincosx jy j+x cy c,(j=1,2,N(4從圖像中取得點序列Q中相應的灰度值,與點序列P的相應點灰度值比較,滿足p(x3j,y3j=p(x j, y j(j=1,2,N的點個數計為n b,設圖像中點序列與待識別模式的匹配率為R,則:R=n bN,R0,1(5R越大識別程度越高,由此QR碼識別問題轉化為四維空間(x c,y c,M,內求匹配率R的最大值問題.這個問題適合使用遺傳算法求解.第4期谷曉琳等:基于遺傳算法的二維QR碼圖像識別493遺傳算法用于識別3.1算法思想遺傳算法在理論上能從概率的意義上以隨機的方式尋求到問題的最優(yōu)解;但實踐表明,遺傳算法也會出現一

10、些不盡人意的問題,如早熟收斂、局部尋優(yōu)能力差等.本文使用基于機器學習的改進遺傳算法,首先將原點坐標、放大倍數和旋轉角度作為一個染色體的組成部分,隨機得到多個人色體作為初始種群,并判斷其適應值得到部分較優(yōu)解并保存,從較優(yōu)解中抽取部分個體作為下一代初始種群的一部分,其余個體隨機產生,這樣既保證了初始種群的多樣化,同時也使初始種群保持了較高的平均適值,使得優(yōu)化迭代次數大大減小.引入了靜態(tài)繁殖理論,在進行交叉和變異操作后,將新生成的子代染色體適值和父代進行比較,如果子代染色體適值高于父代,則利用子代染色體替代父代染色體,否則保留父代染色體,保留父代中的優(yōu)異個體,防止進化操作對優(yōu)異個體性狀的破壞,從而有

11、效地防止了較優(yōu)解的丟失.當得到最優(yōu)解或者達到設定的進化代數時迭代結束.3.2算法的描述對于上述四維空間(xc,y c,M,求匹配率R的最大值問題,定義遺傳算法的個體I k(k=1,2,3,的基因型Gk為5:G k=(x ck,y ck,M k,k(6其中,xck 、yck、Mk和k分別為xc,y c,M和意義相同的表現型.G k可視為四維空間中的一點對應于表現型Hk5為:H k=h k1(x3k1,y3k1,h k2(x3k2,y3k2,h kN(x3kN,y3kN(7其中,x3k jy3k j =M kco sk-sinksinkco skx k jy k j+x cky ck,(j=1,2

12、,N(8根據圖像的物理約束特征,確定表現型的取值范圍及相互間映射關系如下:定義圖像的寬度為w,高度為h,由約束1知:wh,定義圖像中QR碼符號邊長為u,由約束2知:uh,因為圖像的主題是QR碼,取u34h,所以x c38h,w-38h,y c38h,58h.因為表現型x ck和yck為二進制編碼,為了克服二進制編碼存在較大Hamm ing距離和連續(xù)函數離散化時有精度映射誤差等問題,擴大xck 和yck的取值范圍:xck0,127,yck0,63.則x方向的偏移步長ex =w-34h128,y方向的偏移步長e y=h256.所以基因中的表現型同圖像中的實際值之間的關系如下:xc =38h+e x

13、(1+x ck,y c=38h+e y(1+y ck.定義圖像中QR碼符號面積為s,s916h2,h2,設定面積變化的最小值為116h2,則可以確定放大倍數M的表現型Mk 的取值范圍為:Mk0,7,則M=916+116h2M k.由于拍攝時主觀因素的參與,所以假設旋轉角度以45度為單位,所以:=45k,k0,7到此可以確定染色體Gk編碼的總長度為19位,具體如下: 50大連鐵道學院學報第26卷個體的適應度用匹配率作為評價依據.由于前面定義的QR碼符號中的點在圖像中有多個像素,圖像在拍攝過程中有略微的拉伸,旋轉角度上也不能絕對地在45k的角度上,所以不能以點所包含的像素100%匹配來評價.解決這

14、個問題的辦法是設定點中75%的像素匹配就認為該點匹配,即f(x3k j, y3k j=1,否則f(x3k j,y3k j=0.因此,個體I k的適應度可按下式計算:f(I k=Nj=1f(x3k j,y3k jN通過三個基本操作:選擇、交叉和變異來完成對染色體位串的修改,以得到最優(yōu)解.而標準遺傳算法要花費大量的時間才能收斂到最優(yōu)解,因此,有必要對其進行修改.(1交叉操作,本文采用所求解的特定問題的知識來改進,具體操作:當進行交叉操作的兩個候選解的適值低于最優(yōu)解庫中的平均值(,實施標準的單點交叉;當兩個候選解其中任一適值大于時,交叉參數從兩候選解的位置(xck 、yck、放大倍數(M k及旋轉角

15、度(k的平均值中選擇,再對該對候選解的適值函數加權.(2變異操作,對于最優(yōu)解庫中小部分可能解保持不變,以保證不丟失最佳可能解;剩下一小部分通過其解的參數上(位置、放大倍數、旋轉角度加上一小的常數實現輕微變化,該操作對應于以靠近最優(yōu)解附近的局部極值.最后的可能解的變異按如下步驟實現:小的隨機擾動值加到位置參數,大范圍的隨機擾動加到旋轉角度、放大倍數和模型已證實的參數上,變異后的可能解代替以前可能解跳出局部最優(yōu)解.一旦可能解已收斂到接近最優(yōu)解,則逐步減少變異操作概率.給出以下兩個條件作為收斂準則:(1進化代數達到一個給定的上界T;(2連續(xù)10代沒有新的最小點出現,則隨機選擇新的個體加入進化,如連續(xù)

16、兩次未出現新最小點,則進化結束.步驟1:隨機搜索獲得初始種群;步驟2:計算適應值,并判斷算法收斂準則是否滿足.如“滿足”則轉步驟5;步驟3:若算法收斂準則不滿足,進行遺傳操作.應用靜態(tài)繁殖理論,判斷子代染色體的適值是否高于父代,如果“是”,則用子代替代父代,否則保留父代;步驟4:判斷是否最優(yōu)解,是,得到最優(yōu)解,轉步驟5;否則,轉步驟3;步驟5:輸出結果.4實驗結果及分析為了驗證本算法的有效性,識別設置的參數有:種群大小為20,選擇操作淘汰比例為40%,變異率為1%,終止世代數120.針對旋轉的QR Code圖片(圖3進行識別,在70代后收斂到最優(yōu)解,而使用隨機搜索很難得到最優(yōu)解,參見圖4.從實

17、算結果可知,在圖像中進行QR碼基元提取的遺傳算法,在噪音干擾下,仍保持良好的自適應性.在同時識別和提取多個基元時,該問題演變?yōu)槎嗄B(tài)函數優(yōu)化問題,需要引用分享機制,對適應度函數做適當的改進.第4期谷曉琳等:基于遺傳算法的二維QR碼圖像識別51圖3旋轉的QR Code圖4QR碼識別的實算結果5結語實例數據分析可知,對于旋轉、放大等QR碼,應用改進的遺傳算法來識別,且能在較短時間內快速識別,即得到最優(yōu)解,效率得到明顯的改進.總體上說,本課題目前還是一個全新的概念,將其完全實現并付諸于商業(yè)化,還需要更進一步的研究、開發(fā).參考文獻:1P AVL I D I S T,S WARTZ J,WANG Y P.Funda mentals of bar code inf or mati on theoryJ.IEEE Comp u te r,1990,23(4:74286.2P AVL I D I S T,S WARTZ J,WANG Y P.I nfor mati on encoding with t w o2di m ensi onal bar codesJ.IEEE Comp u te r,1992,27(6:1