基于稀疏編碼和嶺回歸的文本圖像復(fù)原算法

王之毅，畢篤彥，熊 磊，凡遵林，張曉瑜

(1.空軍工程大學(xué) 航空航天工程學(xué)院，西安 710038； 2.新疆軍區(qū) 自動(dòng)化站，烏魯木齊 830042)(*通信作者電子郵箱1970696669@qq.com)

基于稀疏編碼和嶺回歸的文本圖像復(fù)原算法

王之毅1*，畢篤彥1，熊 磊1，凡遵林1，張曉瑜2

(1.空軍工程大學(xué) 航空航天工程學(xué)院，西安 710038； 2.新疆軍區(qū) 自動(dòng)化站，烏魯木齊 830042)(*通信作者電子郵箱1970696669@qq.com)

為解決現(xiàn)有稀疏編碼方法在文本圖像復(fù)原中存在的編碼碼元表述空間有限和計(jì)算時(shí)間長(zhǎng)的問題，提出了一種基于嶺回歸的稀疏編碼文本圖像復(fù)原方法。首先，該方法在訓(xùn)練階段使用樣本圖像塊訓(xùn)練出用于稀疏表達(dá)的字典，并根據(jù)樣本圖像塊和編碼碼元之間的歐氏距離對(duì)樣本圖像塊進(jìn)行聚類；其次，在局部流形空間構(gòu)建低質(zhì)量文本圖像塊和清晰文本圖像塊之間的嶺回歸，實(shí)現(xiàn)對(duì)編碼碼元表述空間的局部多線性擴(kuò)展和快速計(jì)算；最后，在測(cè)試階段搜索和低質(zhì)量文本圖像最相近的編碼碼元，計(jì)算出近似的清晰文本圖像塊，從而避免計(jì)算耗時(shí)的低質(zhì)量文本圖像塊的稀疏編碼。實(shí)驗(yàn)結(jié)果表明，所提算法在恢復(fù)的圖像質(zhì)量上相比現(xiàn)有的基于稀疏編碼的算法在峰值信噪比上高0.3～1.1 dB，耗時(shí)降低了1～2個(gè)數(shù)量級(jí)，為提高文本圖像復(fù)原質(zhì)量和提升算法運(yùn)算速度提供了一種解決方案。

文本圖像復(fù)原；稀疏編碼；流形空間；嶺回歸；聚類

0 引言

隨著科學(xué)技術(shù)的進(jìn)步，獲得圖像和視頻的設(shè)備在日常生活中隨處可見，處理圖像和視頻的計(jì)算機(jī)和移動(dòng)終端無論是在處理速度還是內(nèi)存容量上都有了很大的提升，這就催生了光學(xué)字符識(shí)別(Optical Character Recognition,OCR)、自然場(chǎng)景文本識(shí)別、基于文本內(nèi)容的圖像檢索等一批應(yīng)用。在自然場(chǎng)景下獲取的含有文本的圖像或者視頻往往因?yàn)楣庹铡⑦\(yùn)動(dòng)、視角、獲取圖像或者視頻的設(shè)備性能等因素的影響導(dǎo)致圖像變形、含有噪聲、運(yùn)動(dòng)模糊、分辨率較低，通過掃描舊文件獲得的圖像會(huì)有老化、侵蝕、污點(diǎn)等退化現(xiàn)象，有必要對(duì)含有文本的圖像進(jìn)行去除噪聲、消除模糊、超分辨率、消除變形等圖像復(fù)原處理。

近年來，文獻(xiàn)[1-4]試圖從不同的角度解決圖像復(fù)原的難題，取得了一定的效果。Chiang等[1]統(tǒng)計(jì)整理了文本圖像的邊緣信息，融合到該圖像中；該算法對(duì)邊緣清晰的圖像效果明顯。Bertalmio等[2]使用基于高階偏微分方程的數(shù)字圖像復(fù)原算法對(duì)圖像受損區(qū)域依據(jù)邊緣的特點(diǎn)各向異性地向區(qū)域內(nèi)修復(fù)，取得了較好的復(fù)原效果，但是對(duì)含有噪聲、模糊的圖像效果不理想。Thouin等[3]針對(duì)單幅文本圖像使用非線性最大化雙峰優(yōu)化技術(shù)，對(duì)舊文件中由于老化，油污等產(chǎn)生的退化現(xiàn)象能夠獲得較清晰的圖像。Donaldson等[4]也使用了該技術(shù)對(duì)文本圖像的分辨率進(jìn)行增強(qiáng)。

文獻(xiàn)[5-11]是使用稀疏編碼的方法對(duì)自然圖像進(jìn)行復(fù)原，該方法基于壓縮感知理論。文獻(xiàn)[12]提出的壓縮感知理論認(rèn)為由高分辨率圖像經(jīng)過下采樣得到的低分辨率圖像在一定條件下可以以高概率復(fù)原。Sen等[13]利用壓縮感知理論對(duì)低分辨率圖像進(jìn)行超分辨率復(fù)原，但自然圖像紋理細(xì)節(jié)復(fù)雜，很難獲得最優(yōu)的高分辨率圖像。文獻(xiàn)[14-15]將成對(duì)的低分辨率圖像和高分辨率圖像以一定的重疊分割成對(duì)應(yīng)的圖像塊，用圖像塊稀疏表示圖像，對(duì)高分辨率輸出圖像進(jìn)行重構(gòu)，取得了較好的圖像質(zhì)量，但是算法計(jì)算復(fù)雜度大。Yang等[16-17]僅利用高分辨率圖像塊訓(xùn)練字典，降低了該類算法的時(shí)間復(fù)雜度。

Zeyde等[18]使用最優(yōu)化方法通過低質(zhì)量圖像塊訓(xùn)練出一個(gè)稀疏字典，然后通過使低質(zhì)量圖像塊在低質(zhì)量圖像塊字典上的稀疏編碼和對(duì)應(yīng)的清晰圖像塊在高分辨率字典上的分解有相同的系數(shù)來構(gòu)建高分辨率字典。對(duì)輸入的低質(zhì)量圖像塊，計(jì)算在低質(zhì)量圖像塊字典上的稀疏編碼，使用該稀疏編碼在在清晰圖像塊字典上構(gòu)建出近似的清晰圖像塊。該方法利用稀疏編碼計(jì)算獲得的少量碼元對(duì)整個(gè)圖像塊空間進(jìn)行描述，有效降低了表征空間維數(shù)，具有較低的搜索計(jì)算復(fù)雜度；但同時(shí)存在圖像細(xì)節(jié)損失多，對(duì)測(cè)試樣本重構(gòu)計(jì)算時(shí)間長(zhǎng)的缺點(diǎn)。

針對(duì)上述問題，本文提出一種碼元嶺回歸方法，利用稀疏編碼獲得的碼元，在每個(gè)碼元局部流形空間使用樣本圖像塊構(gòu)建嶺回歸，從而將整個(gè)空間劃分為各個(gè)碼元的嶺回歸模型，有效地提高了復(fù)原細(xì)節(jié)，并顯著降低了測(cè)試階段的時(shí)間復(fù)雜度。

1 碼元嶺回歸算法

1.1 稀疏編碼部分

這一步的目的是獲得低質(zhì)量文本圖像稀疏編碼和字典Db。將每一幅樣本圖像都重疊分割成圖像塊，使用最優(yōu)化方法對(duì)低質(zhì)量文本圖像塊訓(xùn)練出一個(gè)稀疏字典Db。然后通過使低質(zhì)量文本圖像塊在該字典上的稀疏表示和對(duì)應(yīng)的清晰圖像塊在相應(yīng)的字典上的分解有相同的稀疏編碼來構(gòu)建清晰圖像塊字典Do。訓(xùn)練低質(zhì)量圖像塊字典Db的過程可以用式(1)表示：

s.t.‖αk‖0≤L; ?k

(1)

構(gòu)建好了低質(zhì)量文本圖像塊字典后，就需要以此為基礎(chǔ)構(gòu)建清晰文本圖像塊字典，目標(biāo)是對(duì)于清晰文本圖像塊可以通過式(2)得到近似值：

(2)

這樣的清晰文本圖像塊字典需要用以下的優(yōu)化過程求解來減少恢復(fù)出的圖像塊與原始清晰圖像塊之間的誤差：

(3)

Do=PoA+=PoAT(AAT)-1

(4)

1.2 局部碼元回歸

在訓(xùn)練字典的過程中也將帶噪聲、模糊的圖像塊按照跟字典Db中碼元的歐氏距離進(jìn)行聚類。由此，字典Db中每個(gè)碼元都對(duì)應(yīng)一個(gè)帶噪聲、模糊的圖像塊簇。利用帶噪聲、模糊的圖像塊簇和與之對(duì)應(yīng)的清晰圖像簇之間的關(guān)系，通過嶺回歸算法訓(xùn)練出回歸。這個(gè)過程可以用式(5)表示:

(5)

這個(gè)最優(yōu)化過程可以得到一個(gè)閉合形式的解：

(6)

(7)

完整形式可表示為：

(8)

(9)

1.3 重疊處理

為了消除經(jīng)過運(yùn)算得到的近似清晰文本圖像塊邊緣的差異，在訓(xùn)練階段低質(zhì)量的文本圖像塊和清晰文本都有重疊,由下式可以得到近似清晰文本圖像：

(10)

1.4 算法步驟

本文算法的步驟可以總結(jié)為：

訓(xùn)練階段(可以離線完成):

步驟5 對(duì)每一個(gè)低質(zhì)量文本圖像塊簇和對(duì)應(yīng)的清晰文本圖像塊簇，利用嶺回歸算法，訓(xùn)練出一個(gè)回歸。

測(cè)試階段:

2 本文算法實(shí)驗(yàn)結(jié)果與分析

正文內(nèi)容該算法的實(shí)驗(yàn)環(huán)境為Inter Core 2 Duo CPU E7200 2.53 GHz，內(nèi)存4 GB，WIN7 SP1 64位操作系統(tǒng)，仿真軟件為Matlab R2016a。

在字典訓(xùn)練階段選擇100對(duì)樣本圖像，低質(zhì)量文本圖像由清晰文本圖像經(jīng)過動(dòng)感模糊、加噪聲、斷筆處理。圖像塊的大小選取為8×8，從切割好的圖像塊中隨機(jī)抽取n(n=5 000 000)塊圖像作為訓(xùn)練塊，K-SVD的迭代次數(shù)設(shè)置為60，編碼的稀疏度設(shè)置為3，字典碼元數(shù)本文中采用1 024，迭代共軛梯度算法的迭代次數(shù)設(shè)置為50。訓(xùn)練低質(zhì)量文本圖像塊字典時(shí)正則項(xiàng)的平衡因子設(shè)置為0.1，更新迭代次數(shù)設(shè)置為10。

在訓(xùn)練回歸階段，利用已經(jīng)訓(xùn)練好的字典碼元作為中心，依據(jù)歐氏距離對(duì)低質(zhì)量文本圖像塊進(jìn)行聚類，每一簇的個(gè)數(shù)是2 048個(gè)，使用每一簇中的低質(zhì)量文本圖像塊和與之對(duì)應(yīng)的清晰文本圖像塊的關(guān)系訓(xùn)練回歸。

在圖像復(fù)原質(zhì)量上除了主觀評(píng)價(jià)外，還采取了峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)。峰值信噪比和均方誤差(Mean Squared Error, MSE)的關(guān)系如式(11)所示：

PSNR=10 lg(2552/MSE);

(11)

在時(shí)間復(fù)雜度上，采用了算法在測(cè)試階段的運(yùn)行時(shí)間。

在本文的實(shí)驗(yàn)中，測(cè)試圖像選取10幅不同字體不同字號(hào)的低質(zhì)量文本圖像進(jìn)行復(fù)原，字典采用相同的碼元數(shù)量，均為1 024個(gè)。將本文實(shí)驗(yàn)結(jié)果跟文獻(xiàn)[5]、文獻(xiàn)[14]和文獻(xiàn)[18]方法在復(fù)原的圖像質(zhì)量和時(shí)間復(fù)雜度上作了比較，實(shí)驗(yàn)結(jié)果如表1和圖1所示。其中圖1是從10幅圖中選擇了1幅對(duì)復(fù)原結(jié)果進(jìn)行了比較。

表1 各種方法對(duì)10幅低質(zhì)量文本圖像復(fù)原結(jié)果的PSNR和測(cè)試階段耗時(shí)對(duì)比(1 024碼元)

圖1 幾種算法復(fù)原圖對(duì)比(1 024碼元)

從復(fù)原的文本圖像來看，文獻(xiàn)[5]、文獻(xiàn)[14]、文獻(xiàn)[18]的復(fù)原圖有偽影，文獻(xiàn)[5]復(fù)原圖還有明顯的振鈴現(xiàn)象。這幾種算法對(duì)噪聲的消除作用不強(qiáng)，字體與背景的對(duì)比不明顯。本文算法能夠有效消除噪聲、偽影，得到比較清楚的圖像；對(duì)于降質(zhì)圖中出現(xiàn)的斷筆現(xiàn)象能夠較好恢復(fù)，能從主觀上較好地識(shí)別出字符的內(nèi)容，存在的問題是恢復(fù)圖像字符的邊緣不夠清晰。從實(shí)驗(yàn)數(shù)據(jù)來看，本文算法在恢復(fù)文本圖像的質(zhì)量上更接近原圖(比其他算法高0.3～1.1 dB)，在測(cè)試階段消耗的時(shí)間更短。

以上實(shí)驗(yàn)是將所有算法中訓(xùn)練的字典碼元數(shù)目設(shè)定為1 024，本文算法中用于訓(xùn)練碼元回歸的圖像塊每一簇的個(gè)數(shù)為2 048，改變參數(shù)，會(huì)對(duì)恢復(fù)的文本圖像的質(zhì)量和算法的運(yùn)行時(shí)間產(chǎn)生影響。圖2、圖3分別顯示了字典碼元數(shù)目與恢復(fù)的文本圖像質(zhì)量、測(cè)試階段的運(yùn)行時(shí)間的關(guān)系。從圖2可以看出本文算法復(fù)原圖的質(zhì)量隨著字典碼元數(shù)目的增加逐漸提高，增長(zhǎng)速度則逐漸減緩，同時(shí)比文中介紹的其他幾種算法有明顯優(yōu)勢(shì)。從圖3可以看出本文算法在測(cè)試階段的運(yùn)行時(shí)間比其他幾種算法低一個(gè)或者兩個(gè)數(shù)量級(jí)，并且隨著字典碼元數(shù)目的增加測(cè)試階段的運(yùn)行時(shí)間增加緩慢，而文中介紹的其他幾種算法的運(yùn)行時(shí)間則隨著字典碼元數(shù)目的增加變化較快，主要原因是本文算法計(jì)算嶺回歸是一種線性運(yùn)算，求解線性轉(zhuǎn)換的時(shí)間要遠(yuǎn)低于求解稀疏編碼所需要的時(shí)間。

3 結(jié)語

本文針對(duì)運(yùn)動(dòng)模糊，含有噪聲且有斷筆的低質(zhì)量文本圖像提出了一種基于碼元嶺回歸的文本圖像復(fù)原算法，通過實(shí)驗(yàn)，本文算法對(duì)由于模糊，噪聲斷筆等原因退化的低質(zhì)量文本圖像能夠有效復(fù)原，在時(shí)間復(fù)雜度上有了很大提升。該算法所采取的訓(xùn)練文本圖像塊以字典碼元為中心進(jìn)行聚類，更準(zhǔn)確地描述了文本圖像塊之間的關(guān)系，通過對(duì)聚類的文本圖像塊訓(xùn)練回歸，提升了算法的運(yùn)算速度。

圖2 字典碼元數(shù)目對(duì)峰值信噪比的影響

圖3 字典碼元數(shù)目對(duì)運(yùn)行時(shí)間的影響

References)

[1] CHIANG M C, BOULT T E. Imaging-consistent super-resolution [EB/OL]. [2016- 11- 08]. http://innovation.uccs.edu/～tboult/PAPERS/IUW97-Imaging-Consistent-Super-Resolution-Chiang-Boult.pdf.

[2] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting [C]// Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2000: 417-424.

[3] THOUIN P D, CHANG C I. A method for restoration of low-resolution document images [J]. International Journal on Document Analysis and Recognition, 2000, 2(4): 200-210.

[4] DONALDSON K, MYERS G K. Bayesian super-resolution of text in video with a text-specific bimodal prior [J]. International Journal of Document Analysis and Recognition, 2005, 7(2): 159-167.

[5] ZORAN D, WEISS Y. From learning models of natural image patches to whole image restoration [C] // Proceedings of the 2011 International Conference on Computer Vision. Washington, DC: IEEE Computer Society, 2011: 479-486.

[6] CHANTAS G, GALATSANOS N P, MOLINA R, et al. Variational Bayesian image restoration with a product of spatially weighted total variation image priors [J]. IEEE Transactions on Image Processing, 2010, 19(2): 351-362.

[7] 王璐,胡晰遠(yuǎn),彭思龍.基于分塊的空間變化抖動(dòng)模糊圖像的全局模糊去除[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2012,24(6):766-774.(WANG L, HU X Y, PENG S L. Partition-based global deblurring of space-variant shake-blurred image [J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(6): 766-774. )

[8] AHARON M, ELAD M, BRUCKSTEIN A. K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation [J]. IEEE Transactions on Signal Processing, 2006, 54(11): 4311-4322.

[9] 陳柘,陳海.基于稀疏表達(dá)的圖像去噪方法研究 [J].電子設(shè)計(jì)工程,2014,22(2):168-170.(CHEN Z,CHEN H. Research on image denoising based on sparse representation [J]. Eletronic Design Engineering, 2014, 22(2): 168-170.)

[10] 姜鵬飛.基于稀疏表示與字典學(xué)習(xí)的圖像去噪算法研究[D].西安:西安電子科技大學(xué),2011:35-48.(JIANG P F. Image denoising based on sparse representation and dictionary learning [D]. Xi’an: Xidian University, 2011: 35-48.)

[11] 浦劍,張軍平.基于詞典學(xué)習(xí)和稀疏表示的超分辨率方法[J].模式識(shí)別與人工智能,2010,23(3):335-340.(PU J, ZHANG J P. Super-resolution through dictionary learning and sparse representation [J]. Pattern Recognition and Artificial Intelligence, 2010, 23(3): 335-340.)

[12] DONOHO D L. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[13] SEN P, DARABI S. Compressive image super-resolution [C]// Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers. Piscataway, NJ: IEEE, 2009: 1235-1242.

[14] YANG J, WRIGHT J, HUANG T S, et al. Image super-resolution via sparse representation [J]. IEEE Transactions on Image Processing, 2010, 19(11): 2861-2873.

[15] LU J, ZHANG Q, XU Z, et al. Image super-resolution by dictionary concatenation and sparse representation with approximate L0 norm minimization [J]. Computers & Electrical Engineering, 2012, 38(5): 1336-1345.

[16] YANG S, SUN F, WANG M, et al. Novel super resolution restoration of remote sensing images based on compressive sensing and example patches-aided dictionary learning [C]// Proceedings of the 2011 International Workshop on Multi-Platform/Multi-Sensor Remote Sensing and Mapping. Piscataway, NJ: IEEE, 2011: 1-6.

[17] YANG S, WANG M, SUN Y, et al. Compressive sampling based single-image super-resolution reconstruction by dual-sparsity and non-local similarity regularizer [J]. Pattern Recognition Letters, 2012, 33(9): 1049-1059.

[18] ZEYDE R, ELAD M, PROTTER M. On single image scale-up using sparse-representations [C]// Internet Conference on Curves and Surfaces, LNCS 6920. Berlin: Springer, 2010: 711-730.

Textimagerestorationalgorithmbasedonsparsecodingandridgeregression

WANG Zhiyi1*, BI Duyan1, XIONG Lei1, FAN Zunlin1, ZHANG Xiaoyu2

(1.CollegeofAeronauticsandAstronauticsEngineering,AirForceEngineeringUniversity,Xi’anShaanxi710038,China;2.CommandAutomationStation,XinjiangMilitaryArea,UrumqiXinjiang830042,China)

To solve the problem that sparse coding in text image restoration has the shortcomings of limited expression of dictionary atoms and high computation complexity, a novel text image restoration algorithm was proposed based on sparse coding and ridge regression. Firstly, patches were used to train the dictionary for sparse representation at training stage and the sampled image were clustered based on the Euclidean distances between the sampled image patches and the dictionary atoms. Then, the ridge regressors between low-quality text image patches and clear text image patches were constructed in local manifold space to achieve the local multi-linear expansion of dictionary atoms and fast calculation. At last, the clear text image patches were directly calculated at testing stage by searching for the most similar dictionary atoms with low-quality text image patches without calculating the sparse coding of low-quality text image patches. The experimental results show that compared with the existing sparse coding algorithm, the proposed algorithm has improved Peak Signal-to-Noise Ratio (PSNR) by 0.3 to 1.1 dB and reduced computing time at one or two orders of magnitude. Therefore, this method provides a good and fast solution for text image restoration.

text image restoration; sparse coding; manifold space; ridge regression; clustering

2017- 03- 09;

2017- 03- 21。

國家自然科學(xué)基金資助項(xiàng)目(61372167, 61379104)。

王之毅(1982—)，男，河南鄲城人，助理工程師，碩士研究生，主要研究方向：圖像處理； 畢篤彥(1962—)，男，陜西扶風(fēng)人，教授，博士，主要研究方向：圖像處理、模式識(shí)別； 熊磊(1976—)，男，江西南昌人，副教授，博士，主要研究方向：圖像處理、計(jì)算機(jī)視覺； 凡遵林(1991—)，男，湖南郴州人，博士研究生，主要研究方向：圖像處理、模式識(shí)別； 張曉瑜(1983—)，男，河南鎮(zhèn)平人，助理工程師，碩士，主要研究方向：機(jī)器學(xué)習(xí)、人工智能。

時(shí)間 2017- 08- 09 10:36:06 。 網(wǎng)絡(luò)出版地址 http://kns.cnki.net/kcms/detail/51.1307.TP.20170809.1036.002.html。

1001- 9081(2017)09- 2648- 04

10.11772/j.issn.1001- 9081.2017.09.2648

TN911.73

A

This work is partially supported by the National Natural Science Foundation of China (61372167,61379104).

WANGZhiyi, born in 1982, M.S.candidate, assistant engineer. His research interests include image processing.

BIDuyan, born in 1962, Ph.D., professor. His research interests include image processing, pattern recognition.

XIONGLei, born in 1976, Ph.D., associate professor. His research interests include image processing, computer vision.

FANZunlin, born in 1991, Ph.D. candidate. His research interests include image processing, pattern recognition.

ZHANGXiaoyu, born in 1983, M. S., assistant engineer. His research interests include machine learning, artificial intelligence.