湖南大學(xué)畢業(yè)設(shè)計(jì)(論文)第頁第一章緒論1.1圖像修復(fù)的背景及目的Bertalmio在2000年首次提出圖像修補(bǔ)（imageinpainting），指利用損壞圖像已知信息，按照一定規(guī)則對損壞區(qū)域進(jìn)行修補(bǔ)。它是對圖像上信息缺損區(qū)域進(jìn)行信息填充的過程，其目的是恢復(fù)有信息缺損的圖像，并使觀察者無法察覺圖像曾經(jīng)缺損或已被修復(fù)。但他缺少足夠信息保證唯一正確的修復(fù)結(jié)果，因此是一個病態(tài)問題，解得合理性取決于人類視覺系統(tǒng)的接受程度。該項(xiàng)技術(shù)在文物保護(hù)、影視特效制作、老照片的修復(fù)、圖像中文本的去除、劃痕的修復(fù)、障礙物的去除以及隱藏視頻錯誤等方面，有著很高的應(yīng)用價值。該領(lǐng)域的研究，國外正在蓬勃發(fā)展，國內(nèi)尚處于起步階段。目前圖像修復(fù)技術(shù)主要是兩大類：第一類主要修復(fù)缺損比較小的數(shù)字圖像。即，利用缺損區(qū)域的周邊信息，估計(jì)等照度線的方向，并采用傳播機(jī)制，推測出缺損區(qū)域的信息，達(dá)到修補(bǔ)原圖的效果；第二類是用于填充丟失了大量信息的圖像補(bǔ)全技術(shù)。目前，填充圖像的技術(shù)又可以分為以下兩種方法：一種是用圖像分解來修復(fù)原圖，其主要思想是將圖像分為紋理部分和結(jié)構(gòu)部分兩部分。其中，結(jié)構(gòu)部分我們可以用inpainting的技術(shù)，而紋理部分我們則可以用填充的方法。第二種方法我們可以用塊的紋理合成技術(shù)，其主要思想是：首先選取缺損區(qū)域的邊界上的任意一個像素點(diǎn)，然后根據(jù)該像素點(diǎn)周圍圖像的紋理特征，確定合適紋理塊的大小，然后在缺損區(qū)域的周圍找到一個能與之匹配的紋理塊來替代該紋理塊。最近幾年，利用紋理合成的圖像合成技術(shù)來修復(fù)缺損大量信息的圖像已經(jīng)成為一個熱點(diǎn)，也取得了相當(dāng)大的成果。但是，圖像修復(fù)技術(shù)是一種對視覺感知過程的學(xué)習(xí)和理解。它是一個不確定問題，沒有唯一解的存在，解的合理性取決于視覺系統(tǒng)的接受程度。換言之，為了達(dá)到較好的視覺效果，我們必須讓修復(fù)效果更加符合視覺感知的特性，使得圖像看起來渾然一體，沒有修改過的痕跡。

按照適用范圍的不同，圖像修復(fù)算法可以范圍三類：平緩區(qū)域的修復(fù)算法、結(jié)構(gòu)性區(qū)域的修復(fù)算法、紋理區(qū)域的修復(fù)算法?；诮Y(jié)構(gòu)的修復(fù)算法適應(yīng)于較小范圍的損壞，但當(dāng)缺損區(qū)域比較大時，由于算法局限性會使得圖像變得模糊。并且它不能修復(fù)紋理圖像?；诮Y(jié)構(gòu)的修復(fù)算法通過一個點(diǎn)向周圍擴(kuò)散相應(yīng)的信息，它是基于點(diǎn)來恢復(fù)圖像；而基于紋理的修復(fù)方法是通過一個塊來尋找全圖中與之相似的另一個塊來修補(bǔ)缺損，它是基于塊的分析方法。這兩種方法在信息的運(yùn)用方面有所不同，基于結(jié)構(gòu)的方法只能利用缺損區(qū)域周邊的相關(guān)信息來恢復(fù)原圖，它有很多信息沒有運(yùn)用到，具有一定的局限性，而基于紋理的方法則是通過檢索全圖所有的信息來恢復(fù)原圖，能充分利用所有的信息。還從物理意義上講，矩陣的秩度量的就是矩陣的行列之間的相關(guān)性。如果矩陣的各行或列是線性無關(guān)的，矩陣就是滿秩的，也就是秩等于行數(shù)。既然秩可以度量相關(guān)性，而矩陣的相關(guān)性實(shí)際上有帶有了矩陣的結(jié)構(gòu)信息。如果矩陣之間各行的相關(guān)性很強(qiáng)，那么就表示這個矩陣實(shí)際可以投影到更低維的線性子空間，也就是用幾個向量就可以完全表達(dá)了，它就是低秩的。所以我們總結(jié)的一點(diǎn)就是：如果矩陣表達(dá)的是結(jié)構(gòu)性信息，例如圖像、用戶-推薦表等等，那么這個矩陣各行之間存在這一定的相關(guān)性，那這個矩陣一般就是低秩的。1.2低秩矩陣恢復(fù)國內(nèi)外研究現(xiàn)狀

圖像復(fù)原是數(shù)字圖像處理領(lǐng)域中的一個重要分支，科研工作者已對它研究了很長一段時間，國內(nèi)外都已經(jīng)有了很多成熟的算法,現(xiàn)有的圖像復(fù)原可分為兩大類：圖像非盲復(fù)原和圖像盲復(fù)原。圖像非盲復(fù)原算法，指的是已知噪聲的類型和大小參數(shù)，它的恢復(fù)方法一般比較簡單，比如均值濾波，去卷積的方法等。其中，去卷積算法主要包括功率譜均衡、維納濾波和幾何平均值濾波等，這些算法應(yīng)用范圍較小，需事先知道噪聲的類型，才能選取合適的恢復(fù)算法，這要求獲得大量的樣本并建立相應(yīng)的模型，并且這些算法只適合于噪聲信號不相干系統(tǒng)和線性空間不變系統(tǒng)。線性代數(shù)算法主要是通過已知的降質(zhì)因子和噪聲特性，運(yùn)用線性代數(shù)的方法求解圖像復(fù)原問題，它也有很多弊端，比如如果退化函數(shù)有接近零的特征值時，圖像復(fù)原就會對噪聲特別敏感，并且該方法的處理對象是圖像的整體，計(jì)算量比較大，在復(fù)原圖像的紋理和邊界時效果不理想。國外的學(xué)者們針對這些問題提出了很多改進(jìn)的算法，比如全局最小二乘法、約束總體最小二乘法和正則化約束總體最小二乘法。近年來，發(fā)展迅速的小波理論在圖像復(fù)原問題中也得到了廣泛的應(yīng)用。Belge等人提出了一種基于小波域邊緣保持正則化方法，給出了小波域圖像復(fù)原的一般框架。第二章低秩分解理論基礎(chǔ)2.1低秩矩陣數(shù)學(xué)理論2.1.1矩陣奇異值分解假設(shè)M是一個m×n階矩陣，其中的元素全部屬于域K，也就是實(shí)數(shù)域或復(fù)數(shù)域。如此則存在一個分解使得M=UΣV*，其中U是m×m階酉矩陣；Σ是半正定m×n階對角矩陣；而V*，即V的共軛轉(zhuǎn)置，是n×n階酉矩陣。這樣的分解就稱作M的奇異值分解。Σ對角線上的元素Σi,i即為M的奇異值。2.1.2范數(shù)矩陣范數(shù)的概念設(shè)A∈Cm×n，定義一個實(shí)值函數(shù)||A||，若滿足：(1)非負(fù)性：||A||≥0，且||A||=0當(dāng)且僅當(dāng)A=0；(2)齊次性：||aA||=|a|||A||，a∈C；(3)三角不等式：||A+B||≤||A||+||B||，A,B∈Cm×n;(4)相容性：||AB||≤||A||||B||，則稱||A||為A的矩陣范數(shù)。在許多優(yōu)化問題中，我們經(jīng)常用L1范數(shù)來代替L0范數(shù)，一是因?yàn)長0范數(shù)很難優(yōu)化求解（NP難問題），二是L1范數(shù)是L0范數(shù)的最優(yōu)凸近似，而且它比L0范數(shù)要容易優(yōu)化求解。L0范數(shù)是指向量中非0的元素的個數(shù)。如果我們用L0范數(shù)來規(guī)則化一個參數(shù)矩陣W的話，就是希望W的大部分元素都是0。

L1范數(shù)是指向量中各個元素絕對值之和，也叫“稀疏規(guī)則算子”（Lassoregularization）。

L2范數(shù)是指向量各元素的平方和然后求平方根。我們讓L2范數(shù)的規(guī)則項(xiàng)||W||2最小，可以使得W的每個元素都很小，都接近于0，但與L1范數(shù)不同，它不會讓它等于0，而是接近于0。2.1.3凸優(yōu)化問題”凸優(yōu)化“是指一種比較特殊的優(yōu)化，是指目標(biāo)函數(shù)為凸函數(shù)且由約束條件得到的定義域?yàn)橥辜膬?yōu)化問題。為目標(biāo)函數(shù)，為限制條件。如果此處，目標(biāo)函數(shù)和限制條件為凸函數(shù)，即滿足下式時：，此優(yōu)化問題即為一個凸優(yōu)化問題。之所以要研究凸優(yōu)化問題是因?yàn)槠溆幸惶追浅Ｍ陚涞那蠼馑惴?，如果將某個優(yōu)化問題確認(rèn)或者轉(zhuǎn)化為凸優(yōu)化問題，那么能夠快速給出最優(yōu)解。2.1.4稀疏矩陣如果在矩陣中，多數(shù)的元素為0，稱此矩陣為稀疏矩陣(sparsematrix)。矩陣中非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，并且非零元素的分布沒有規(guī)律，稀疏矩陣的計(jì)算速度更快,因?yàn)镸ATLAB只對非零元素進(jìn)行操作,這是稀疏矩陣的一個突出的優(yōu)點(diǎn)。圖像在傳輸過程中，經(jīng)常被各種各樣的噪聲污染，但是相對于圖像本身巨大的數(shù)據(jù)量而言，噪聲的數(shù)據(jù)量是很少的，所以我們可以把噪聲看成是稀疏的。2.2低秩矩陣恢復(fù)概述世界中的絕大多數(shù)信號都是冗余的，浪費(fèi)了大量的時間和空間資源，因此基于稀疏矩陣的低秩恢復(fù)研究具有重要意義。其模型簡單容易構(gòu)造，實(shí)現(xiàn)算法也多樣，易于收斂，已成為近期研究的熱點(diǎn)。其基本思想是為了使得最后求出的解其秩最低，并利用矩陣的奇異值來實(shí)現(xiàn)，因?yàn)榫仃嚨姆橇闫娈愔祩€數(shù)即為矩陣的秩。其數(shù)學(xué)模型可以描述為D=A+E式中，D為觀測矩陣，A為低秩矩陣，通常被稀疏噪聲矩陣E所污染，一般都假設(shè)E滿足高斯分布。該問題可以用常見的PCA算法實(shí)現(xiàn)，可以得到如下函數(shù):此時我們可以對D進(jìn)行奇異值分解，然后其在r維子空間的投影即為所求解。但是這種方法有較多局限性，于是MaYi等人提出RPCA的算法，上述問題就變成其中，要求出E的0范數(shù)，這是一個NP難問題，沒有唯一的解，于是我們將其凸優(yōu)化，得到其中只需求出X的核范數(shù)，即所有奇異值的和，λ是權(quán)重因子，通常為然后，我們就能用加速近端梯度法（APG）或拉格朗日乘子法（ALM）對上式進(jìn)行求解。2.3低秩矩陣恢復(fù)應(yīng)用2.3.1矩陣填充(MatrixCompletion)：矩陣填充一個主流的應(yīng)用是在推薦系統(tǒng)里面。我們知道，推薦系統(tǒng)有一種方法是通過分析用戶的歷史記錄來給用戶推薦的。例如我們在看一部電影的時候，如果喜歡看，就會給它打個分，例如3顆星。然后系統(tǒng)，例如Netflix等知名網(wǎng)站就會分析這些數(shù)據(jù)，看看到底每部影片的題材到底是怎樣的？針對每個人，喜歡怎樣的電影，然后會給對應(yīng)的用戶推薦相似題材的電影。但有一個問題是：我們的網(wǎng)站上面有非常多的用戶，也有非常多的影片，不是所有的用戶都看過說有的電影，不是所有看過某電影的用戶都會給它評分。假設(shè)我們用一個“用戶-影片”的矩陣來描述這些記錄，例如下圖，可以看到，會有很多空白的地方。如果這些空白的地方存在，我們是很難對這個矩陣進(jìn)行分析的，所以在分析之前，一般需要先對其進(jìn)行補(bǔ)全。也叫矩陣填充。

這叫低秩矩陣重構(gòu)問題，它可以用如下的模型表述：已知數(shù)據(jù)是一個給定的矩陣A，大小為m*n，因?yàn)槟撤N原因丟失了其中一些元素，我們能否根據(jù)其他行和列的元素，將這些元素恢復(fù)？當(dāng)然，如果沒有其他的參考條件，想要確定這些數(shù)據(jù)很困難。但如果我們已知A的秩rank(A)<<m且rank(A)<<n，那么我們可以通過矩陣各行(列)之間的線性相關(guān)將丟失的元素求出。這種假定我們要恢復(fù)的矩陣是低秩的實(shí)際上是十分合理的，比如一個用戶對某電影評分是其他用戶對這部電影評分的線性組合。所以，通過低秩重構(gòu)就可以預(yù)測用戶對其未評價過的視頻的喜好程度。從而對矩陣進(jìn)行填充。2.3.2魯棒PCA：主成分分析，可以有效的找出數(shù)據(jù)中占主導(dǎo)地位的元素和結(jié)構(gòu)，去除多余的噪聲，使得原來復(fù)雜的數(shù)據(jù)變得簡單明了，并降低它的維度。我們知道，最簡單的主成分分析方法就是PCA了。主成分分析的目標(biāo)可以看成是用一組新的基來描述原來的數(shù)據(jù)。希望在這組新的基下，原來數(shù)據(jù)能夠被它簡單明了的描述出來，并且是低維的。這個維度即最重要的“主元"。PCA的目標(biāo)就是找到這樣的“主元”，最大程度的去除多余的噪音和不必要的數(shù)據(jù)。

魯棒主成分分析（RobustPCA）考慮的是這樣一個問題：一般我們的數(shù)據(jù)矩陣X會包含結(jié)構(gòu)信息，也包含噪聲。那么我們可以將這個矩陣分解為兩個矩陣相加，一個是低秩的（由于內(nèi)部有一定的結(jié)構(gòu)信息，造成各行或列間是線性相關(guān)的），另一個是稀疏的（由于含有噪聲，而噪聲是稀疏的），則魯棒主成分分析可以寫成以下的優(yōu)化問題：

與經(jīng)典PCA問題一樣，魯棒PCA本質(zhì)上也是尋找數(shù)據(jù)在低維空間上的最佳投影問題。對于低秩數(shù)據(jù)觀測矩陣X，假如X受到隨機(jī)（稀疏）噪聲的影響，則X的低秩性就會破壞，使X變成滿秩的。所以我們就需要將X分解成包含其真實(shí)結(jié)構(gòu)的低秩矩陣和稀疏噪聲矩陣之和。找到了低秩矩陣，實(shí)際上就找到了數(shù)據(jù)的本質(zhì)低維空間。因?yàn)镻CA假設(shè)我們的數(shù)據(jù)的噪聲是高斯的，對于大的噪聲或者嚴(yán)重的離群點(diǎn)，PCA會被它影響，導(dǎo)致無法正常工作。而RobustPCA則不存在這個假設(shè)。它只是假設(shè)它的噪聲是稀疏的，而不管噪聲的強(qiáng)弱如何。

由于rank和L0范數(shù)在優(yōu)化上存在非凸和非光滑特性，所以我們一般將它轉(zhuǎn)換成求解以下一個松弛的凸優(yōu)化問題：假設(shè)一個人在不同情形下的許多張不同照片，如果將這個人的圖像拆分成一個行向量，并用這些行向量組成一個矩陣，由于圖像之間的自相似性，這個矩陣應(yīng)該是低秩的。但是，在實(shí)際中，每幅圖像都會有一定的噪聲污染，我們可以吧這些噪聲的作用看成是一個噪聲矩陣加在原來的低秩矩陣上。我們把這些圖像拆成一個個小塊，在把這些塊變成一維的行向量，然后擺成一個矩陣，則我們可以對這個矩陣進(jìn)行低秩分解，得到干凈的人臉圖像和噪聲的矩陣。

2.3.3背景建模：

背景建模的一個簡單應(yīng)用是從同一場景中拍攝的視頻中分離背景和前景。我們將拍攝的許多圖像的每一幀圖像變成一個列向量，則許多圖像就可以組成了一個很大的觀測矩陣。由于背景是基本相同的，因此他們的相關(guān)性很大，所以僅由背景像素組成的矩陣應(yīng)當(dāng)是低秩的；同時由于前景比較少，占據(jù)像素比較低，故前景組成的矩陣應(yīng)當(dāng)是稀疏的。這兩種矩陣的和就是我們的觀測矩陣視。因此，視頻背景建模實(shí)現(xiàn)的過程可以看成是低秩矩陣恢復(fù)的過程。

2.3.4變換不變低秩紋理（TILT）：

以上章節(jié)所介紹的針對圖像的低秩逼近算法，僅僅考慮圖像樣本之間像素的相似性，卻沒有考慮到圖像作為二維的像素集合，其本身所具有的規(guī)律性。事實(shí)上，對于未加旋轉(zhuǎn)的圖像，由于圖像的對稱性與自相似性，我們可以將其看做是一個帶噪聲的低秩矩陣。當(dāng)圖像由端正發(fā)生旋轉(zhuǎn)時，圖像的對稱性和規(guī)律性就會被破壞，也就是說各行像素間的線性相關(guān)性被破壞，因此矩陣的秩就會增加。低秩紋理映射算法(TransformInvariantLow-rankTextures，TILT)是一種用低秩性與噪聲的稀疏性進(jìn)行低秩紋理恢復(fù)的算法。它的思想是通過幾何變換τ把D所代表的圖像區(qū)域校正成正則的區(qū)域，如具有橫平豎直、對稱等特性，這些特性可以通過低秩性來進(jìn)行刻畫。

第三章低秩矩陣分解求解算法3.1概述現(xiàn)如今已涌現(xiàn)出許多針對低秩分解的算法實(shí)現(xiàn)。迭代閾值算法（iterativethresholding，IT）：將最優(yōu)化問題正則化，就可以得到優(yōu)化問題，使用迭代閾值算法交替更新矩陣A，E和Y。IT算法的迭代形式簡單且收斂，但他的收斂速度十分慢，且步長很難選取。加速近端梯度算法（acceleratedproximalgradient，APG）：將優(yōu)化問題的約束凸松弛到目標(biāo)函數(shù)中，給定與D同型的兩個矩陣Ya和Ye，作其拉格朗日函數(shù)的部分二次逼近，盡管APG與IT算法類似，但他降低了很多迭代次數(shù)。對偶方法（DUL）：用譜范數(shù)來代替核范數(shù)的對偶范數(shù)，則我們可以用對偶問題來解決，且這個優(yōu)化問題是非光滑的，非線性，相對APG算法，它具有更好的可擴(kuò)展性，無需對矩陣每次都進(jìn)行完全的奇異值分解。增廣拉格朗日乘子法（augmentedlagrangemultipliers，ALM）：先構(gòu)造增廣拉格朗日函數(shù)，然后使用交替更新的辦法更新A和E，直到滿足終止條件。其恢復(fù)時間較快，且精度也較高。交替方向方法（alternatingdirectionmethods，ADM，IALM）：它是對ALM的改善，用不精確的拉格朗日函數(shù)來處理，無需求出拉格朗日函數(shù)的精確解，還是迭代更新A和E。本文著重介紹APG算法和IALM算法。3.2加速近端梯度法APG建立模型后，有如下優(yōu)化問題Mins.t.X+Y=D將其凸優(yōu)化，得到如下目標(biāo)函數(shù)，其拉格朗日函數(shù)形式為：L（X，Y，u）=u（）+0.5然后，我們可以用加速近端梯度法求解，將其替代為兩個函數(shù)，記第一部分為g（X,Y,u），是一個不可微的函數(shù)，第二部分為f(X,Y),具有李普希茲連續(xù)梯度，且是光滑的。下面就對目標(biāo)函數(shù)進(jìn)行二次逼近，給出與D同樣大小的兩個矩陣Zx和Zy，初始化他們都為零矩陣，根據(jù)使得目標(biāo)函數(shù)最小的原則，則我們可以得到其迭代公式為：Zx（k+1）=X（k）+（t（k）-1）*（X（k）-X（k+1））/t（k+1）Zy（k+1）=Y（k）+（t（k）-1）*（Y（k）-Y（k+1））/t（k+1）其中，t（k）為其更新時的步長，也是一個不斷隨迭代次數(shù)變化的量。然后我們可以確定Yx和Yy更新時的步長t（k+1）=（1+）/2參數(shù)u的迭代公式為：u（k+1）=maxη（u（k），a）式中a為一個正數(shù)，0<η<1.有如下算法流程：輸入觀測矩陣D，初始化各項(xiàng)參數(shù)為零WhilenotconvergeddoZx（k+1）=X（k）+（t（k）-1）*（X（k）-X（k+1））/t（k+1）Zy（k+1）=Y（k）+（t（k）-1）*（Y（k）-Y（k+1））/t（k+1）Gx(k)=Zx(k)+(D-Zx(k)-Zy(k))/2,(u,s,v)=svd(Gx(k))Gy(k)=Zy(k)+(D-Zy(k)-Zy(k))/2,X(k+1)=us(k)[s]v(t)(x,y)=Y(k+1)=s(a/u)[Gy(k)]Z(k+1)=Z(k)+u(k)*(D-x(k+1)-y(k+1)t（k+1）=（1+）/2更新u（k）結(jié)束，輸出矩陣，即最優(yōu)解（X,Y）3.3部分加速近端梯度法從上式可以看出，APG算法一定程度上降低了迭代次數(shù)，優(yōu)化了問題的解，縮短了時間，但是它每次迭代都需對矩陣進(jìn)行一次完全的奇異值分解，而這將浪費(fèi)大量時間。基于此，提出部分APG算法部分APG算法主要是對APG算法的速度提升，在上式中，每一次迭代都要計(jì)算一次完全的奇異值分解,并且這個過程是不必要的，我們的目的只是尋求一個大于閾值的奇異值分解而已。APG算法就在奇異值分解上浪費(fèi)了時間，用了Larsen等人的PROPACK包，需要在每一步預(yù)測需要多少個奇異值及奇異向量，再計(jì)算奇異值分解中前k個奇異值及相應(yīng)的奇異向量。這樣有可能造成計(jì)算的浪費(fèi)或者不準(zhǔn)確。在仔細(xì)研究PROPACK中的LanczosSVD后，直接計(jì)算大于某一閾值的部分奇異值分解算法，就能省去很多不必要的計(jì)算。對于上述求解大于閾值t的奇異值，每次都需要估計(jì)出一個大于閾值t的奇異值的個數(shù)k，然后通過傳統(tǒng)的方法求解出前k個奇異值看是否找到了所有大于t的奇異值。在這個過程中，如果k估計(jì)得過小，那么可能會造成計(jì)算的不精確，如果這個k估計(jì)得過大，那么我們浪費(fèi)了一些時間。3.4精確增廣拉格朗日乘子法ALMAPG算法雖然在速度和時間上有所提升，但是它并不能很好的滿足我們的要求，當(dāng)矩陣維數(shù)較大時，APG算法的速度會下降較多，精度也會有所降低，不能完全應(yīng)用在現(xiàn)實(shí)中。于是有文獻(xiàn)提出了增廣拉格朗日乘子法。即將前面提出的優(yōu)化問題凸松弛到一個拉格朗日函數(shù)，消除其約束條件，應(yīng)用次微分和閾值迭代的方法求解最優(yōu)解。并且其有兩種迭代的方法，精確的增廣拉格朗日乘子法(ELAM)和非精確的拉格朗日乘子法（IALM）。對于前面有約束的優(yōu)化問題，其拉格朗日函數(shù)形式為：L(x,y,u)=f(x)+<y,h(x)>+u/2其中，u是一個正數(shù)。增廣的拉格朗日函數(shù)相對于普通的拉格朗日函數(shù)，不同的是多出一個懲罰項(xiàng)，其作為一個新的約束正則項(xiàng)。增廣拉格朗日乘子法一直迭代拉格朗日函數(shù)，得到新的Xk，然后結(jié)合乘子Yk，繼續(xù)更新獲得下一個Xk，最終獲得的Xk就會收斂到最優(yōu)解。精確的增廣拉格朗日乘子法（EALM）是交替的迭代矩陣A和E直到滿足終止條件為止。若Y=Y（k+1），則X（k+1）=argminL（X，Y（k+1），Z（k），u（k））=D（u）*（D-Y（k+1）+1/u（k）*Z（k））再由得到的Y（k+1）來更新X（k+1）:Y(k+1)=argminL(X(k+1),Y,Z(k),u(k))=S(D-X(k+1)+1/u（k）*Z（k）)而矩陣Z的更新則為：Z（k+1）=Z(k)+u(k)*(D–X(k+1)-Y(k+1))參數(shù)u的更新公式為u（k+1）=a*u(k),若u(k)*其中a為大于1的常數(shù)，e為大于零的正數(shù)。如上的迭代解決凸優(yōu)化問題的時間和精度得到了很大的提升。3.5非精確增廣拉格朗日乘子法IALM非精確的增廣拉格朗日乘子法是利用增廣拉格朗日乘子法來方便的求解低秩矩陣恢復(fù)問題。我們可以先構(gòu)造上述優(yōu)化問題的拉格朗日函數(shù)如下：然后我們用奇異值收縮算子與軟閾值算子近似替代核范數(shù)與范數(shù)的最小值問題。于是我們就可以用交替迭代的方式來求解上述問題。我們先給定E和Y來求出使得目標(biāo)函數(shù)最小的A：然后換過來根據(jù)已有的A和Y求出使得目標(biāo)函數(shù)最小的E：在根據(jù)現(xiàn)有的A和Y反過來求E，則幾次迭代后我們能得出此優(yōu)化問題的最優(yōu)解。事實(shí)證明，對于不太復(fù)雜的圖像，我們只需各自更新一次A和E，則問題往往就能得到較好的近似解。其流程圖如下：IALM的算法在數(shù)據(jù)實(shí)驗(yàn)以及實(shí)際低秩圖像去噪方面都達(dá)到了理想的效果，IALM算法比APG算法恢復(fù)時間快5倍以上，并且達(dá)到較高的精度,在理論和實(shí)際應(yīng)用上都有了更進(jìn)一步的提高。但是其在低秩圖像受到高斯噪聲污染的時候效果就不理想了，這就限制了該方法在實(shí)際中的應(yīng)用，具有一定的局限性。實(shí)驗(yàn)證明，非精確的拉格朗日乘子法在速度和精度方面在所有算法里面是最優(yōu)的，它的運(yùn)行時間比APG算法快5倍以上，但是如果污染噪聲是高斯噪聲，則它的恢復(fù)效果就不盡人意了，這使得它在現(xiàn)實(shí)生活中的應(yīng)用有一定的局限性。第四章低秩圖像去噪及復(fù)原實(shí)驗(yàn)4.1圖像噪聲模型圖像去噪指的是從一張有噪聲或缺陷的圖像中去除噪聲或缺陷，恢復(fù)原來圖像的過程。由于受各種原因的影響，圖像在記錄，傳輸和形成的過程中，圖像的質(zhì)量會有所改變，比較產(chǎn)生高斯噪聲或變得不清晰，因此噪聲圖像的恢復(fù)問題具有很強(qiáng)的重要性和實(shí)用性。我們這里設(shè)立一種圖像噪聲模型，主要指的是一種加性噪聲，即在一張圖片中加入一種噪聲，我們假定原來的理想圖像為，加入一個噪聲，污染后的圖像為：，本文所研究的就是在不知道為何種噪聲的情況下能夠快速有效的從中消除噪聲，盡可能地恢復(fù)出原來的圖像。本章主要研究三種比較常見噪聲的修復(fù)問題，分別是椒鹽噪聲，高斯噪聲及人為的劃痕。所謂高斯噪聲，它的概率密度函數(shù)一般服從正態(tài)分布；椒鹽噪聲，被該噪聲污染后，圖像像素點(diǎn)會變?yōu)?個極值灰度從0到255，而圖像中的每個像素點(diǎn)以一定的概率受到該噪聲的影響，因此它表現(xiàn)為圖象某些點(diǎn)特別暗或特別亮，而其他象素點(diǎn)不受到影響，類似我們的胡椒粉和晶體鹽的亮度的感覺，所以叫椒鹽噪聲。高斯噪聲和椒鹽噪聲的模型如下：（1）高斯噪聲模型：，這里均值一般取為0，標(biāo)準(zhǔn)差為。（2）椒鹽噪聲模型：，這里，一般取，，即像素點(diǎn)以概率受到噪聲影響變?yōu)?以概率受到噪聲影響而變?yōu)椤?.2椒鹽噪聲的去除椒鹽噪聲是由傳輸信道，圖像傳感器，解碼處理等產(chǎn)生的黑白相間的噪聲。椒鹽噪聲往往由切割圖像引起。椒鹽噪聲其實(shí)是指兩種噪聲，一種是椒噪聲（peppernoise），一種是鹽噪聲（saltnoise）。鹽=白色，椒=黑色。前者是灰度比較高噪聲，后者是灰度比較低的噪聲。一般兩種噪聲同時出現(xiàn)時，圖像上就呈現(xiàn)出黑白相間的雜點(diǎn)。

現(xiàn)在我們分別用上述四種方法來處理椒鹽噪聲，分別是加速近端梯度法，改進(jìn)后的部分APG算法，精確的增廣拉格朗日乘子法，以及不精確的增廣拉格朗日乘子法。實(shí)驗(yàn)圖像是一副低秩的棋盤格圖像，我們?nèi)藶榈募尤虢符}噪聲后，在觀察上述四種方法的處理效果及恢復(fù)時間。實(shí)驗(yàn)結(jié)果如下所示：被污染后的圖像APG算法部分APG算法精確的增廣拉格朗日乘子法ALM非精確的拉格朗日乘子法IALM第一張圖是通過MATLAB的添加噪聲的函數(shù)imnoise人為的加入?yún)?shù)為0.02的椒鹽噪聲后的圖像。從四種處理方法的結(jié)果來看，恢復(fù)出來的原矩陣效果都很不錯，都比較清晰，其中部分APG和非精確的拉格朗日乘子法IALM的原圖較小，大小為435*435的矩陣，它的秩也比較低，大概為一百二十左右，其恢復(fù)時間較快，都只有幾秒不到的時間，迭代次數(shù)也較少，其中非精確的拉格朗日乘子法IALM算法表現(xiàn)尤為突出，三十次左右迭代后就快速給出了精確解，而部分APG迭代了大概一百四十次左右才給出了正確解。而加速近端梯度法APG和精確的增廣拉格朗日乘子法ALM算法所使用的原圖較大一點(diǎn)，大小為780*780的矩陣，秩大概為二百一十左右。其恢復(fù)結(jié)果也很不錯，不過消耗了較多的時間，算法運(yùn)行的速度較慢，迭代次數(shù)也較多，加速近端梯度法APG迭代了大概一百二十次次左右，精確的增廣拉格朗日乘子法ALM更是迭代了有二百九十次多次。4.3圖像劃痕修復(fù)我們還是使用上面那張棋盤格圖像，我們?nèi)藶榈募尤雱澓郏缓笤谟^察四種算法的處理結(jié)果加速近端梯度法APG部分APG算法精確的增廣拉格朗日乘子法ALM非精確的拉格朗日乘子法IALM從上述圖片來看，恢復(fù)結(jié)果都得到了比較清晰的棋盤格圖像，而且原圖也沒有變形，劃痕圖像也比較完美的提取了出來。四種方法中非精確的拉格朗日乘子法IALM所用時間是最短的，迭代次數(shù)也很少，大約在三十次迭代后就給出了近似解，求出來的秩也比較低，大概在十三左右，且每次迭代的跳度都較大，這樣就能快速逼近最優(yōu)解。精確的增廣拉格朗日乘子法ALM相比較之下就顯得有些不足，首先它耗費(fèi)了大量時間，算法迭代的速度十分慢，迭代了差不多近三百多次才給出近似解，求解出來的秩也比較大，大概在二十四左右，且到了算法迭代的后半部分，其運(yùn)行的速度已經(jīng)很緩慢了，幾乎要十多秒才能迭代一次。加速近端梯度法的處理效果也很清晰，基本恢復(fù)了原圖，迭代次數(shù)大概在一百次左右，最后求解出來的秩也比較低，只有九左右，算法運(yùn)行的速度也比較快，很快就給出了最優(yōu)解。部分APG算法的處理效果與加速近端梯度法沒有太大區(qū)別，但算法運(yùn)行的速度方面要遜色，它迭代了大概一百四十次左右，最后求解出來的秩也比較大一點(diǎn)，大概在十二左右。4.4高斯噪聲的去除高斯噪聲，指它的概率密度函數(shù)服從正態(tài)分布。高斯分布，也稱正態(tài)分布，又稱常態(tài)分布，記為N（μ，σ^2），其中σ^2，μ為分布的參數(shù)，分別為高斯分布的方差和期望。當(dāng)有確定值時，p(x)也就確定了，特別當(dāng)μ=0，σ^2=1時，X的分布為標(biāo)準(zhǔn)正態(tài)分布。高斯噪聲的形式為：，這里均值一般取為0，標(biāo)準(zhǔn)差為。我們還是用MATLAB自帶的加噪聲函數(shù)imnoise給大小為291*291的棋盤格圖像加入?yún)?shù)為0.02的高斯噪聲，污染后的圖像如下：然后我們還是用上述四種方法，分別是加速近端梯度法，改進(jìn)后的部分APG算法，精確的增廣拉格朗日乘子法，以及不精確的增廣拉格朗日乘子法來處理。處理結(jié)果如下：加速近端梯度法部分APG算法精確的增廣拉格朗日乘子法不精確的增廣拉格朗日乘子法從上面的處理結(jié)果可以看出，這四種算法對高斯噪聲的處理效果并不如上面的椒鹽噪聲和劃痕理想，它沒有恢復(fù)出十分清晰的圖像，在恢復(fù)出來的矩陣圖像上依舊殘留著一些高斯噪聲，導(dǎo)致圖像看上去有一些模糊。在所有算法中，處理結(jié)果較好的是加速近端梯度法，迭代了一百二十次左右，恢復(fù)出來的矩陣秩大小在一百左右，運(yùn)行的時間也比較快速。部分的加速近端梯度法與之相比并沒有太大區(qū)別，迭代次數(shù)在一百四十次左右，矩陣的秩也在一百左右。不精確的增廣拉格朗日乘子法雖然在三十次左右就給出了最優(yōu)解，時間比較快速，但它的恢復(fù)效果并不好，秩在165左右，恢復(fù)出來的圖像也比較模糊。精確的增廣拉格朗日乘子法對高斯噪聲的處理效果很差，迭代次數(shù)非常大，迭代了八百多次，最后給出的最優(yōu)解秩也到了兩百多，幾乎沒有什么處理效果。第五章總結(jié)與展望圖像在傳輸過程中難免會遇到很多原因?qū)е聢D像遭到損壞，使得圖像變形或者變得模糊，造成了資源的浪費(fèi)，而圖像復(fù)原的目的就是把退化了的圖像復(fù)原成清晰的高質(zhì)量的圖像。隨著科技的進(jìn)步，圖像在人們的日常生活中扮演著越來越重要的角色，從醫(yī)療成像到航天制造，到娛樂設(shè)施等等，圖像復(fù)原作為圖像處理中的一個重要的分支，受到了很多學(xué)者的關(guān)注和重視。本文主要討論幾種改進(jìn)的基于低秩的圖像去噪方法，可快速有效的從被稀疏噪聲污染的圖像中精確的恢復(fù)原圖像。該模型在原模型的基礎(chǔ)上加上核范數(shù)部分，使相關(guān)性原本較強(qiáng)的圖像恢復(fù)結(jié)果更加精確，并且可以去除椒鹽噪聲、劃痕、高斯噪