馬金辰，謝世朋，李海波

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

基于多個低秩紋理提取的圖像校正方法

馬金辰，謝世朋，李海波

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

低秩紋理是圖像處理領(lǐng)域中具有重要幾何意義的結(jié)構(gòu)，通過提取低秩紋理可以對畸變或受損圖像進行有效校正；但現(xiàn)有的基于低秩紋理提取的圖像校正方法只能把感興趣區(qū)域看作一個整體，從而導(dǎo)致許多復(fù)雜情況下的校正無法獲得理想結(jié)果。針對上述問題，對現(xiàn)有算法進行改進，實現(xiàn)感興趣區(qū)域的多個低秩紋理分別提取，用以解決實際應(yīng)用中的多種畸變和受損圖像的恢復(fù)問題。對選定區(qū)域進行分割，對每個子區(qū)域分別進行低秩校正，加強初始化窗口對紋理的適應(yīng)性，從而優(yōu)化校正效果。大量實驗結(jié)果表明，該方法可以有效處理同一感興趣區(qū)域中的多個低秩紋理，在凸平面、多個不兼容區(qū)域和復(fù)雜紋理等多種情況下仍然可以獲得正確的處理結(jié)果,且校正效果與原算法相比更加符合人眼視覺特性。

低秩紋理；增廣拉格朗日乘數(shù)法；圖像分割；多分辨率；分支定界

0 引 言

圖像校正技術(shù)的研究在圖像處理領(lǐng)域具有十分重要的應(yīng)用，如智能交通管理系統(tǒng)中的車牌識別、超市條形碼錄入等。近年來，基于圖像特征點和顯著區(qū)域提取的圖像校正方法受到學者的廣泛關(guān)注，然而現(xiàn)有的檢測對稱區(qū)域和模型的校正方法，幾乎都是通過提取和重組如邊緣、角點[1-2]等局部特征實現(xiàn)的。由于特征檢測和邊緣提取本身就對噪聲、遮擋和光照改變等區(qū)域圖像變化比較敏感，故這種對稱性檢測方法缺乏魯棒性和穩(wěn)定性。另外，由于拍攝角度、噪聲等因素對獲取圖像造成的畸變和干擾會嚴重影響圖像的識別、分析及判斷，且人的視覺感知系統(tǒng)具有不變性[3]，所以基于視覺不變性的紋理分析及圖像校正方法十分必要。眾所周知，現(xiàn)有的廣泛使用的不變特征描述(Scale Invariant Feature Transform，SIFT)[4]雖然在很大程度上關(guān)于旋轉(zhuǎn)和縮放具有不變性，但是當多幅圖像由不同視角獲取時，SIFT則無法建立可靠的對應(yīng)。

現(xiàn)有研究表明，通過消除空間變換(如仿射和投影)，可以從2D圖像中提取不變性信息，這些信息對應(yīng)于3D圖像表面的大量規(guī)則模式，且可以被近似模型化為“低秩”矩陣。一個具有這種低秩紋理的圖像受到特定的空間變換后的紋理矩陣，通常不再具有低秩性。文獻[5]中Candes等基于稀疏理論，提出可通過運用先進的凸優(yōu)化算法來實現(xiàn)矩陣秩的最小化，因此可以從一幅畸變圖像中同時恢復(fù)低秩紋理及其畸變量。文獻[6]中提出一種名為RASL的圖像對齊算法，該算法同樣應(yīng)用稀疏低秩恢復(fù)模型實現(xiàn)圖像的可靠對準，但該算法無法利用圖像的空間結(jié)構(gòu)，且需處理多幅圖像中的多個空間變換，從而導(dǎo)致算法的復(fù)雜度過高，能夠解決的問題有限。文獻[7]中提出的變換主成分分析方法，結(jié)合離散的隱變量，使用期望最大化算法提取主成分和空間變換。但是使用該方法進行圖像校正時需要提前預(yù)知矩陣的秩，并且只能處理小范圍的高斯噪聲，這大大限制了其在實際中的應(yīng)用范圍。

Yi Ma等提出名為TILT(Transform Invariant Low-rank Textures)的圖像校正方法[8]，該方法直接使用圖像(窗口)的原始像素值，而不需要對圖像進行任何局部特征的預(yù)提??；且對于由干擾、遮擋或雜亂背景所造成的少量誤差，具有較強的魯棒性。文獻[9]對該算法進行優(yōu)化，解決了算法的收斂性問題，并提高了算法處理速度。雖然上述TILT算法可以校正大量近似低秩的紋理(如人臉和印刷文本)，且校正結(jié)果較好，但是該算法具有一定的局限性：當選中窗口內(nèi)包含多個不兼容區(qū)域，或各子區(qū)域受到的畸變不同時，該算法就無法實現(xiàn)圖像的正確校正。

針對上述問題，對TILT算法進行改進，將感興趣區(qū)域分割為多個子區(qū)域，從而優(yōu)化算法的初始化窗口，達到在復(fù)雜情況下校正圖像的目的。通過實驗對比文中算法與原算法的處理效果，結(jié)果表明優(yōu)化后的算法可以成功處理原算法無法解決的部分復(fù)雜問題。

1 基于低秩紋理提取的圖像校正原理

假設(shè)存在一個低秩紋理A(x,y)，從特定角度所觀察到的圖像D(x,y)是原始低秩紋理函數(shù)A(x,y)經(jīng)過變換后的形式：D(x,y)=A°τ-1(x,y)=A(τ-1(x,y))。其中，τ為一個R2→R2的旋轉(zhuǎn)變換函數(shù)，為方便計算，假設(shè)τ既包含旋轉(zhuǎn)變換又包含2D仿射或投影變換。除了空間變換，現(xiàn)實觀察到的紋理圖像還可能受到噪聲或遮擋的影響，或者包含一些背景像素。將這些干擾量模型化：D=A+E。其中，E為誤差矩陣。文中僅考慮低秩紋理圖像受損部分遠小于紋理本身的情況，即E為稀疏矩陣。則從畸變或受損圖像中恢復(fù)低秩紋理A即解決以下問題：

已知一個畸變和受損的低秩紋理圖像：D=(A+E)°τ-1，恢復(fù)低秩紋理A和空間變換τ。

上述表達式可導(dǎo)出如下形式的優(yōu)化問題：

(1)

優(yōu)化的目的是求得可能的具有最低秩的紋理A，并使噪聲矩陣E盡量稀疏，且E符合由空間變換τ所決定的觀察矩陣D。此處，γ>0為權(quán)衡誤差稀疏度和紋理的秩的加權(quán)參數(shù)。

事實上，初始問題(1)中秩函數(shù)和E的零范數(shù)都很難進行優(yōu)化解決，但最近在稀疏表示和低秩矩陣恢復(fù)方面的研究突破已經(jīng)表明[10-11]，這兩個問題都可以用其凸優(yōu)化方法解決：分別用矩陣A的核范數(shù)(Nuclearnorm)‖A‖*來代替rank(A)，用矩陣E的1范數(shù)‖E‖1來代替‖E‖0。因此，式(1)可以轉(zhuǎn)化為：

(2)

將約束條件線性化[12]為如下形式：

D°τ+JΔτ=A+E

(3)

其中，J是雅可比行列式。

則式(1)中的優(yōu)化問題轉(zhuǎn)化為：

A+E

(4)

上述的線性問題為凸問題，且能夠用凸優(yōu)化的方法高效解決。在解該線性問題時，需要使用迭代的方法在各局部解得最優(yōu)值(最小值)，并最終求得全局最優(yōu)值(最小值)。

具體算法總結(jié)如下：

算法1：

whilenotconvergeddo

步驟(1)：歸一化和計算雅閣比矩陣J。

步驟(2)(內(nèi)循環(huán))：求解線性問題。

步驟(3)：更新變換：τ←τ+Δτ。

endwhile

輸出最優(yōu)解：A*,E*,Δτ*。

算法1中，計算量最大、最耗時的部分是迭代循環(huán)過程的內(nèi)部循環(huán)(步驟(2))，可以使用增廣拉格朗日乘子法(ALM)[13]對其進行解決。對于問題(4)，增廣拉格朗日方程定義為：

(5)

其中，μ>0,Y為拉格朗日乘數(shù)矩陣，且：f(A,E)=‖A‖*+λ‖E‖1,R(A,E,Δτ)=D°τ+JΔτ-A-E。

一般情況下，使變量A,E和Δτ同時最小化的計算量十分巨大。因此可采用交替方向法[14]，對A,E和Δτ逐個求最優(yōu)解：

(6)

式(6)的解可以通過使用收縮算子的方法轉(zhuǎn)化為以下形式：

(7)

2 算法的優(yōu)化處理

2.1 區(qū)域分割

上述TILT算法運用凸優(yōu)化理論，實現(xiàn)了從畸變和受損圖像中快速提取低秩紋理和畸變量。但是，當需要處理的圖像區(qū)域包含多個不同的低秩紋理時，該方法不再適用。這是由于多個受到不同畸變的低秩紋理組合而得的矩陣，不能再分解為一個低秩矩陣A和稀疏矩陣E的和。當感興趣區(qū)域為多個不兼容區(qū)域的組合時，低秩紋理恢復(fù)問題轉(zhuǎn)化為：

(8)

Dn°τn=An+En

(9)

其中，N為分割后的子區(qū)域個數(shù)；αn為加權(quán)系數(shù)，由子區(qū)域畸變強度和受損情況決定。

由式(9)可得線性凸問題：

(10)

對于式(10)，直接求解十分困難，可將其轉(zhuǎn)化為：

JnΔτn=An+En，n=1,2,…,N

(11)

問題(11)的增廣拉格朗日方程為：

Yk=Yk-1+μk-1R(Ak,Ek,Δτk)

(12)

引入交替方向法：

(13)

(14)

為了消除由縮放坐標造成的影響，假設(shè)變換前后圖像的面積及邊長比不變，即：S(τ(Ω))=S(Ω)且L(τ(e1))/L(τ(e2))=L(e1)/L(e2)。該假設(shè)對于問題(2)添加了額外的非線性約束條件，與式(3)的方法類似，這些非線性約束條件可轉(zhuǎn)化：

AsΔτn=0

(15)

優(yōu)化后的算法可總結(jié)為算法2的形式。

算法2：

輸入:輸入圖像D∈Rm×n。

(1)whilenotconvergeddo

(2)while1≤n≤Ndo

(4)Jn(Dn°τn)=max(‖Dn°τn‖2,‖Dn°τn‖),E0=0,Δτ0=0,μ0>0,ρ>1,k=0

(5)whilenotconvergeddo

(8)Yk+1=Yk+μk(Dn°τn+JnΔτk+1-Ak+1-Ek+1)

(9)μk+1=ρμk,k=k+1

(10)endwhile

(11)An=Ak,En=Ek,Δτn=Δτk,τn=τn+Δτn

(12)endwhile

(13)endwhile

(15)輸出最優(yōu)解：

(16)

實驗中，令t1=5×10-5,t2=10-7。

算法2通過區(qū)域分割，彌補了原算法無法同時處理多個不兼容區(qū)域的缺點，可以在更多復(fù)雜情況下獲得較好的校正結(jié)果。

2.2 多分辨率方法

雖然算法2在實際應(yīng)用中能取得很好的實驗效果，但當?shù)椭燃y理中存在任意形狀的尖銳特征或輪廓時，算法會收斂到一個局部最小點，而無法得到正確解。因此，為了處理大的畸變，可以引入多分辨率方法[15-16]。多分辨率方法是計算機視覺領(lǐng)域一種廣泛使用的技術(shù)，該方法從輸入圖像開始，逐漸對圖像進行下采樣，降低分辨率。可首先通過在最低分辨率的圖像上運用算法2進行低秩紋理校正，并用最低分辨率下獲得的最優(yōu)解對高一級分辨率圖像進行初始化，以此類推。

事實上，多分辨率方法不僅提高了算法可以處理的變換范圍，也極大地優(yōu)化了算法的運行時間。這是因為，在低分辨率下凸問題能夠更快速地求解，并且，由于較高分辨率下的程序得到了更好的初始化，使得迭代至收斂的次數(shù)明顯減少。

2.3 分支定界方案

(17)

可將參數(shù)空間(旋轉(zhuǎn)和偏斜)分割成多個區(qū)域，并對這些區(qū)域逐個進行貪婪搜索。首先采用不同的旋轉(zhuǎn)角度初始化并運行算法2，然后選擇使價值函數(shù)最小的初始值，用這個初始值依次沿著x軸和y軸方向搜尋偏斜參數(shù)。使價值函數(shù)最小的參數(shù)就是分支定界方案的輸出值。

對于這樣一個分支定界方案，需要考慮其是否具有較高的效率。在多分辨率優(yōu)化策略中，只需要在最低分辨率水平下使用分支定界，并找到最優(yōu)解，然后使用這個解來初始化較高分辨率的圖像。因為算法2對于較小的矩陣在低分辨率下具有很快的運行速度，所以運行不同初始值的多個過程并不會對整體速度有太大影響。實驗結(jié)果表明，當采用多分辨率策略時，分支定界方案能使迭代次數(shù)進一步減少，雖然每次迭代所需時間略微增加，但總體時間是下降的。

為分析多分辨率方法與分支定界方案對算法的影響，在處理器主頻為1.4GHz，軟件環(huán)境為Windows7的PC機上，對大小為153×68的圖像在四種情況下分別處理，實驗結(jié)果如表1所示。

表1 實驗結(jié)果對比

3 實驗結(jié)果及分析

本節(jié)進行了大量實驗，用以驗證文中算法的有效性。如圖1所示，文中算法可以處理如建筑物表面、標牌、文本和車牌等多種低秩紋理的校正，且校正效果十分理想。

除上述簡單情況外，在多種復(fù)雜條件下進行實驗，并將文中算法與原算法進行對比，實驗結(jié)果如圖2所示。其中第一行為原始圖像及輸入窗口，中間行為原TILT算法校正結(jié)果，最后一行為文中算法校正結(jié)果。

圖1 算法對多種紋理的處理效果

圖2(a)為凸平面的紋理校正，由于試圖校正的區(qū)域關(guān)于圖像垂直中軸受到不同程度的投影變換，所以把整個區(qū)域看作整體進行低秩校正的方法會導(dǎo)致區(qū)域邊緣處效果不佳。從圖中可以看出，使用區(qū)域分割后，校正效果有所改善。

圖2(b)、(c)和(d)中，感興趣區(qū)域包含兩個相鄰的低秩區(qū)域，且兩區(qū)域受到不同程度的畸變。原TILT算法以其部分區(qū)域為準對整個窗口進行空間逆變換，這使得另一區(qū)域受到了更大程度的畸變。如圖所示，文中算法在這種情況下具有非常好的效果。

圖2(e)中，輸入窗口的圖像紋理較復(fù)雜(即秩較高)，使用文中算法對窗口進行分割，使初始窗口更加適應(yīng)紋理方向，可以優(yōu)化實驗結(jié)果。

圖2(f)中的圖像受到的畸變程度過大，原算法只能實現(xiàn)一定程度的校正，效果不理想。如圖所示，文中算法的校正效果明顯提高。

圖2 文中算法與原算法在復(fù)雜情況下的對比

4 結(jié)束語

針對多低秩紋理圖像的校正問題，將圖像區(qū)域分割與低秩提取算法相結(jié)合，提出一種新的更有效的圖像校正算法。該算法通過將感興趣區(qū)域分割為多個子區(qū)域，優(yōu)化紋理提取的初始化窗口，并采用多分辨率方法和分支定界方案，提高算法的收斂域和運行速度。實驗結(jié)果表明，該算法可以解決大量多低秩紋理圖像的校正問題，且校正效果更加符合人眼視覺特性。

[1]HeX,LiJ,WeiD,etal.Cannyedgedetectiononavirtualhexagonalimagestructure[C]//Jointconferencesonpervasivecomputing.[s.l.]:IEEE,2009:167-172.

[2]BruceNDB,KornprobstP.Harriscornersintherealworld:aprincipledselectioncriterionforinterestpointsbasedonecologicalstatistics[C]//IEEEconferenceoncomputervision&patternrecognition.[s.l.]:IEEE,2009:2160-2167.

[3] 吳永興.圖像紋理旋轉(zhuǎn)不變性分析[D].天津:天津大學,2007.

[4]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91-110.

[5]CandesEJ,RechtB.Exactlow-rankmatrixcompletionviaconvexoptimization[C]//46thannualallertonconferenceoncommunication,control,andcomputing.[s.l.]:IEEE,2008:806-812.

[6]PengYigang,GaneshA,WrightJ,etal.RASL:robustalignmentbysparseandlow-rankdecompositionforlinearlycorrelatedimages[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2011,34(11):2233-2246.

[7]FreyBJ,JojicN.Transformedcomponentanalysis:jointestimationofspatialtransformationsandimagecomponents[C]//ProceedingsoftheseventhIEEEinternationalconferenceoncomputervision.[s.l.]:IEEE,1999:1190-1196.

[8]ZhangZ,GaneshA,LiangX,etal.TILT:transforminvariantlow-ranktextures[J].InternationalJournalofComputerVision,2012,99(1):1-24.

[9] 馬 杰,張小美,苑煥朝.基于并行分離增廣拉格朗日乘子法的字符矯正[J].光電子·激光,2015,26(6):1170-1178.

[10]ZhaoYQ,YangJ.Hyperspectralimagedenoisingviasparserepresentationandlowrankconstraint[J].IEEETransactionsonGeoscience&RemoteSensing,2014,53(1):296-308.

[11]CandesEJ,TaoT.Thepowerofconvexrelaxation:near-optimalmatrixcompletion[J].IEEETransactionsonInformationTheory,2009,56(5):2053-2080.

[12]BakerS,MatthewsI.Lucas-Kanade20yearson:aunifyingframework:part4[J].InternationalJournalofComputerVision,2004,56(3):221-255.

[13]MaF,NiM,TongW,etal.MatrixcompletionviaextendedlinearizedaugmentedLagrangianmethodofmultipliers[C]//Internationalconferenceoninformativeandcyberneticsforcomputationalsocialsystems.[s.l.]:IEEE,2015:45-49.

[14]LiW,ZhaoL,XuD,etal.Efficientimagecompletionmethodbasedonalternatingdirectiontheory[C]//2013IEEEinternationalconferenceonimageprocessing.[s.l.]:IEEE,2013:700-703.

[15]JoshiA,BhaskarV.Multi-resolutionapproachformedicalimageregistrationusinggeneticalgorithm[C]//Internationalconferenceoncommunicationsandsignalprocessing.[s.l.]:IEEE,2013:612-616.

[16] 李萬朋.基于低秩紋理的旋轉(zhuǎn)不變特征提取算法研究[D].秦皇島:燕山大學,2013.

[17]XieShipeng,LiChunming,LiHaibo,etal.Alevelsetmethodforcuppingartifactcorrectionincone-beamCT[J].MedicalPhysics,2015,42(8):4888-4895.

[18]TanH,ChengB,FengJ,etal.Tensorrecoveryviamulti-linearaugmentedlagrangemultipliermethod[C]//2011sixthinternationalconferenceonimageandgraphics.[s.l.]:IEEE,2011:141-146.

Image Rectification Method Based on Multiple Low-rank Textures Extraction

MA Jin-chen,XIE Shi-peng,LI Hai-bo

(School of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Low-rank textures play an important role in image processing fields.By extracting the low-rank textures accurately,the distorted or damaged image can be rectified effectively.However,the existing methods based on texture extraction always rectify the region of interest as a whole,which makes it comes to nothing in many complex cases.Aiming at the above-mentioned problems,an improved rectification algorithm is proposed based on multiple low-rank textures extraction.The new rectification algorithm is able to extract multiple low-rank textures respectively and solve a large number of problems of image renewing for distorted or damaged images in practical application.In order to optimize the experimental results,the selected regions are segmented and each sub-region is rectified respectively which can enhance the adaptability of the initialization window to the texture.Experimental results demonstrate that the proposed method is able to rectify multiple low-rank textures in the same region of interest.In complex circumstances such as convex plane,multiple incompatible regions,complex textures and so on,the ideal processing results can be obtained with it.Further more,the results are more in accord with human vision characteristics,which is a critical evaluation criteria.

low-rank textures;augmented Lagrangian multiplier method;image segmentation;multi-resolution approach;branch-and-bound scheme

2016-04-21

2016-08-11

時間：2017-02-17

國家自然科學基金資助項目(11547155)；江蘇省自然科學基金(BK20130883)；南京郵電大學引進人才基金(NY213011，NY214026)

馬金辰(1993-)，女，碩士，研究方向為圖像處理；謝世朋，副教授，研究方向為圖像處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1628.030.html

TP391.41

A

1673-629X(2017)03-0097-06

10.3969/j.issn.1673-629X.2017.03.020