基于稀疏表示的Data Matrix碼圖像修復算法

陳慶然，許義寶，李新華

(安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥 230601)

0 引 言

隨著信息技術與自動識別技術的快速發展，二維碼得到了廣泛應用。由于Data Matrix碼具有尺寸小、密度高以及信息量大等特點[1]，因此作為常用的二維碼，以下簡稱DM碼。然而，DM碼圖像在獲取過程中不可避免地會受到很多因素的影響，導致圖像質量下降。條碼圖像修復旨在消除這些因素的影響，恢復和重構出一幅可以準確識別并解碼的圖像。

當前的圖像修復算法主要有基于偏微分方程(PDE)圖像修復[2]、基于紋理合成圖像修復[3]和基于稀疏表示的圖像修復[4]三大類?；谄⒎址匠痰男迯退惴ㄊ菍D像中的已知信息按照某種規則擴散到未知區域，對小區域受損的圖像修復效果較好?；诩y理合成圖像修復算法[5]是通過將圖像中已知的信息大面積復制到缺損區域來進行恢復，該算法沒有得到推廣主要是因為常常會出現誤匹配現象且計算效率低。而基于稀疏表示的圖像修復算法是利用字典訓練與已知圖像內的有效信息進行稀疏編碼[6-7]，從而達到圖像的修復。

對于一些具體的修復算法，例如Elad等[8]以壓縮感知為基礎，利用形態分量分析(MAC)算法將圖像分解為卡通層與紋理層兩部分分別進行修復，提高了算法的計算復雜度。李民等[9]利用樣本圖像的先驗知識，將待修復圖像本身的信息統一于字典訓練，增強了算法的自適應性，但是忽略了樣本間的自相關性。文獻[10-11]是基于DCT字典進行圖像修復，DCT字典算法對邊界信息修復效果一般。Zhang L等[12]提出利用PCA學習將圖像分塊訓練，算法的魯棒性較低。Xu等[13]提出了基于結構稀疏的修復算法，充分考慮了圖像的幾何結構與紋理信息，但是由于基于塊稀疏特性的修復將圖像的每一個塊獨立編碼，重構時不能獲得準確的稀疏系數。

為了克服以上算法的不足，文中提出一種基于組稀疏表示的圖像修復算法。該算法將圖像塊聚類作為基本單位，采用一次SVD分解與優化編碼算法，在提高字典學習過程中計算效率的同時，考慮了圖像的局部稀疏性與自相關性進行稀疏編碼，并通過實驗對其進行了驗證。

1 總體框架

1.1 目標函數

從數學角度分析，圖像的降質模型表示為：

y=Hx+n

(1)

其中，x為原始圖像；y為待修復圖像；n為加性噪聲；H為降質矩陣。

圖像恢復問題是根據H的不同而發生變化，如果H是掩碼矩陣，問題為圖像修復，如果H是隨機投影矩陣，問題為壓縮感知恢復，如果H是模糊算子矩陣，問題則為去模糊。文中研究的是一種塊聚類稀疏表示的圖像修復問題，此時，H中的元素大多為0，因而難以求出H的逆矩陣。也就是說圖像修復是典型的不可逆問題，正則化則是找出這種問題解的方法之一。具體來說，首先將圖像y分塊再將具有相似結構的塊進行聚類稱為組，每一個塊聚類xGk在字典DGk下的編碼過程就是尋找相應的稀疏向量αGk，即可獲得重構圖像，表示為x≈DGkαGk。于是，在正則化框架下基于組稀疏表示圖像修復的目標函數為：

(2)

得到αGk以后就可以獲得原始圖像x?？梢钥闯觯謴统鲈紙D像的前提是獲得字典原子與對應的稀疏系數。

1.2 快速自適應字典學習

字典DGk的定義需要滿足，能夠很準確地表示每一組xGk的同時希望xGk在字典DGk的表示下系數αG越稀疏越好。

普通的學習字典DGk可以通過下式學習得到：

(3)

其中，p為0或1。

但是這種方法學習到的字典計算復雜度高、效率較低。于是文中提出將塊聚類的估計qGk進行一次奇異值分解(singular value decomposition,SVD)后，快速得到自適應學習字典。

(4)

其中，γrGk=[γrGk?1,γrGk?2,…,γrGk?m]。

1.3 分離迭代算法

分離迭代正則化[14]作為一種新的迭代正則化方法，廣泛應用于圖像去模糊[15]、圖像分割[16]與壓縮感知[17]等問題，它是解決L1范數優化問題的最有效算法之一。利用分離迭代框架求解目標函數，首先引入一個變量q，將式(2)轉化為與其等價的等式：

(5)

其中，通過正則化參數λ平衡稀疏表示系數αG的稀疏性與精度。

調用分離迭代算法得到：

(6)

其中，將最上面的式子取梯度后令結果為0，可以求得組估計q=(HTH+sI)-1w，其中w=HTy+s(DGαG+b)，I代表與之匹配的單位矩陣。

2 優化梯度算法

基于塊聚類的稀疏表示L0最小化圖像修復模型如式(2)，由于L0范數最小化以直接求解，因此通常的做法是求解其最優的近似解，即轉化為L1范數最小化。在一定條件下可以將L0范數優化問題與L1最小化問題的解等價，式(2)等價為：

(7)

根據式(6)，在q已知的情況下求αG，即：

(8)

對式(8)做一些變形，令z=DGαG，可得：

(9)

ε}=1

(10)

根據此定理，可得式(9)在迭代后滿足：

(11)

另Γ=kλ/s，此時式(9)可以變形為：

(12)

顯然，求出式(12)的最優解即為修復過程中需要不斷更新的稀疏系數。下面關于范數最小值的求解進行討論。與其他存在的算法求解方式不同，將它轉化為一般的一元函數的方程求解極小值，令

(13)

從范數的角度分析，可以展開等價于：

為使y(αGk)獲得的解最優，首先對y(αGk)中的αGk進行一階求導，然后令其導數等于0時解出αGk的值。下面對y(αGk)′=αGk-γGrk+Γ?|αGk|求導可得y(αGk)'=αGk-γGrk+Γ?|αGk|，y(αGk)′與y(αGk)′已知。令y(αGk)'等于0滿足最小化條件，可得αGk-γGrk+Γ?|αGk|=0。其中H表示取次梯度，進一步展開可得：

(14)

進行計算后αGk=max(|γGk|-Γ,0)°sign(γGk)，其中H代表絕對值算子，H代表向量對應元素的點乘運算，sign表示取符號函數。

至此，字典與稀疏系數都得到了求解。實際上，得到了最高效的字典原子與最稀疏的稀疏系數，從而使得整個修復算法更具魯棒性。下面給出塊聚類稀疏表示的圖像修復整體算法步驟：

(1)輸入待修復的灰度圖像y(若輸入圖像為彩色圖像，則提取出彩色圖像的亮度信息作為輸入)和掩碼矩陣H；

(2)初始化q0=y,λ,k=240,s；

(3)根據q=(HTH+sI)-1w計算q；

(4)令Γ=kλ/s,用于計算稀疏系數；

(6)根據式(14)計算x=DGαG，可以得出修復后的圖像x=DGαG。

3 實驗結果與分析

通過仿真實驗來驗證該算法的可行性，利用文獻[18-19]的算法與文中算法進行對比，實現對不同受損的樣本DM碼圖像進行修復。圖像大小為256×256像素，以重疊4像素的間隔取出圖像大小為7×7的塊，構建每組的搜索窗口的大小為L×L即40×40。采用修復后圖像的峰值信噪比(PSNR)與結構相似性(SSIM)作為初步衡量圖像修復效果，SSIM的值越大(最大為1)且PSNR越大，說明修復效果越好。最后對修復之后的DM圖像進行解碼測試，可以正確解碼的條碼圖像滿足真正修復的效果。

實驗分為兩組：第一組對于劃痕的DM碼圖像進行修復，分別給出文中算法與文獻[18-19]算法的DM碼的修復效果圖，如圖1和圖2所示。

圖1 樣本1原始圖與掩碼1破壞圖

圖2 被掩碼1破壞的圖像修復結果

圖3為文中算法修復的識別結果，可以準確解碼為CNA10C22GX74218LS8F0A00。

圖3 文中算法修復的識別結果

第二組對于被遮擋的DM碼圖像進行修復，表1分別給出了三種算法修復的實驗數據。

表1 掩碼2破壞的三種算法修復的實驗數據

文獻[19]中算法的修復結果圖針對性不強，修復結果產生局部模糊，有時不能徹底去除掩碼,使得圖像質量較差，修復的圖像不能夠正確解碼，如圖4所示。

由上述實驗數據對比可知，對于不同掩碼破壞的圖像，文中算法修復的結果的PSNR與SSIM的值相比其他兩種算法都有提高，并且在保證高的PSNR的同時滿足了識別功能，可見該算法的穩定性與有效性。

圖4 文獻[19]算法修復的識別結果

4 結束語

提出了一種基于塊聚類稀疏表示的DM碼圖像修復算法，將圖像塊之間的稀疏性與自相關性有效結合在一起，在實際應用中，塊聚類稀疏表示算法是解決稀疏與冗余表示的很好的選擇。在改進稀疏編碼算法方面，L1范數被采用作為解決L0范數優化問題，并且巧妙地運用一次SVD分解來設計快速學習字典，降低了學習字典的計算復雜性。另外，采用分離迭代與優化梯度算法求解組稀疏表示的正則化問題，提高了整體算法的計算效率。對比實驗中可以看出該算法相比其他算法的優勢所在，算法的移植性較好且修復后圖像大大提高了識別率，為工業應用提供了新的思路。未來的研究可以將算法提升到三維視頻的修復。

[1] 劉寧鐘,楊靜宇.三維條碼的編碼理論和設計[J].計算機學報,2007,30(4):686-692.

[2] BERTALMIO M,SAPIRO G,CASELLES V,et al.Image inpainting[C]//Proceedings of the 27th annual conference on computer graphics and interactive technique.[s.l.]:[s.n.],2000:417-424.

[3] EFROS A A,LEUNG T K.Texture synthesis by non-parametric sampling[C]//Proceedings of the seventh IEEE international conference on computer vision.[s.l.]:IEEE,1999:1033-1038.

[4] ELAD M,FIGUEIREDO M A T,YI M.On the role of sparse and redundant representations in image processing[J].Proceeding of the IEEE,2010,98(6):972-982．

[5] CRIMINISI A, PEREZ P, TOYAMA K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Transactions on Image Processing,2004,13(9):1200-1212.

[6] 黃江林.基于稀疏表示的圖像修復算法研究[D].合肥:安徽大學,2013.

[7] 張 健.基于稀疏表示模型的圖像復原技術研究[D].哈爾濱:哈爾濱工業大學,2014.

[8] ELAD M,STARCK J L,QUERRE P,et al.Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)[J].Applied and Computational

Harmonic Analysis,2005,19(3):340-358.

[9] 李 民,程 建,李小文,等.非局部學習字典的圖像修復[J].電子與信息學報,2011,33(11):2672-2678.

[10] GULERYUZ O G.Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising:Part I-theory[J].IEEE Transactions on Image Processing,2006,15(3):539-554.

[11] GULERYUZ O G.Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising:Part II-adaptive algorithms[J].IEEE Transactions on Image Processing,2006,15(3):555-571.

[12] ZHANG L,DONG W,ZHANG D,et al.Two-stage image denoising by principle component analysis with local pixel grouping[J].Pattern Recognition,2010,43(4):1531-1549.

[13] XU Z,SUN J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing,2010,19(5):1153-1165.

[14] OSHER S,BURGER M,GOLDFARB D,et al.An iterative regularization method for total variation-based image restoration[J].SIAM Journal on Multiscale Modeling & Simulation,2005,4(2):460-489.

[15] CAI J F,OSHER S,SHEN Z.Split bregman methods and frame based image restoration[J].SIAM Journal on Multiscale Modeling & Simulation,2009,8(2):337-369.

[16] GOLDSTEIN T,BRESSON X,OSHER S.Geometric applications of the split Bregman method:segmentation and surface reconstruction[J].Journal of Scientific Computing,2010,45(1-3):272-293.

[17] GOLDSTEIN T, OSHER S. The split Bregman method for L1 regularized problems[J].SIAM Journal on Imaging Sciences,2009,2(2):323-343.

[18] ZHANG J,ZHAO D,GAO W.Group-based sparse representation for image restoration[J].IEEE Transaction on Image Processing,2014,23(8):3336-3351.

[19] ZHANG Jian,ZHAO Debin,XIONG Ruiqin,et al.Image restoration using joint statistical modeling in a space-transform domain[J].IEEE Transactions on Circuits and Systems for Video Technology,2014,24(6):915-928.