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

馬金辰，謝世朋，李海波

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

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

馬金辰，謝世朋，李海波

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

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

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

0 引 言

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

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

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

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

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

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

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

上述表達式可導出如下形式的優化問題：

(1)

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

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

(2)

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

D°τ+JΔτ=A+E

(3)

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

則式(1)中的優化問題轉化為：

A+E

(4)

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

具體算法總結如下：

算法1：

whilenotconvergeddo

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

步驟(2)(內循環)：求解線性問題。

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

endwhile

輸出最優解：A*,E*,Δτ*。

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

(5)

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

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

(6)

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

(7)

2 算法的優化處理

2.1 區域分割

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

(8)

Dn°τn=An+En

(9)

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

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

(10)

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

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

(11)

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

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

(12)

引入交替方向法：

(13)

(14)

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

AsΔτn=0

(15)

優化后的算法可總結為算法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)輸出最優解：

(16)

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

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

2.2 多分辨率方法

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

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

2.3 分支定界方案

(17)

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

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

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

表1 實驗結果對比

3 實驗結果及分析

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

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

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

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

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

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

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

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

4 結束語

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

[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] 吳永興.圖像紋理旋轉不變性分析[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] 李萬朋.基于低秩紋理的旋轉不變特征提取算法研究[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