聲明

之前雖然聽過壓縮感知和稀疏表示，實際上昨天才正式著手開始了解，純屬新手，如有錯誤，敬請指出，共同進步。

主要學習資料是 Coursera 上 Duke 大學的公開課——Image and video processing, by Pro.Guillermo Sapiro?第 9 課。

由于對圖像處理的了解也來自與該課程，沒正經兒看過幾本圖像方面的書籍，有些術語只能用視頻中的英文來表達，見諒哈！

---

?

1. Uniqueness

假設我們已知字典矩陣 D 和稀疏向量 a， 計算出一個信號 x，即 Da = x, x?存在一個關于 D 的稀疏表示。反過來現在已知前面的 D 和 x，根據 L0 的優化問題，可以歸納為：

?的解是唯一的嗎？

顯然不一定。比如， D 中某些 atoms 恰好相等，或者 column1 = column2 + column3, 以前由 column2 和 column3 現在只用 column1 表示即可。當然也有正面的例子，比如 DCT 變換, 基向量完全正交，解是唯一的。這與 D 中 atoms 的不相關性和數目?K 有關。

?

2. Sparse Coding

和上面一樣，現有字典 D 和帶有噪聲的信號 y，進行稀疏編碼的問題可以表示的 L0 優化問題：

這是一個組合優化問題。假設 alpha 的非零項數目為 L (sparse Level)， 先令 L = 1, 每一個列向量嘗試一遍，看看是否又滿足條件的，共有 K 種組合。如果沒有，再令 L = 2, 再次嘗試，共有 K(K-1)/2 中組合。還沒有滿足條件的，則令 L = 3......組合的數目呈指數增長，這是一個 NP-hard 的問題。 實際應用中的 K = 1000, L = 10, 要窮盡所有的排列組合大概需要計算幾百萬年，因此要采用近似算法, 目前主要有 relaxation methods 和 greedy methods。

Relaxation Methods - the Basis Pursuit (BP)
我們知道， L0 norm 可以數出向量中非零 entries 的數目，具有很好的現實意義，但是由于它數學特性（求導等）極差，非常不適合作為一個優化模型中目標函數。在線性分類器中，你可以把誤分點的數目作為目標函數，但是沒法優化，所以，我們看到的線性分類器的的目標函數一般是 L1 norm（感知器算法）， L2 norm（LMS 算法和最小二乘法）以及最大熵（Logistic Regresson）等，也能達到比較好的效果。在上一篇博客中，可以看到 L1 是菱形， L2 是球體，L1 具有更好的稀疏性(解更靠近坐標軸)，所以我們采用松弛方法將 L0 norm 轉換為 L1 norm：

雖然我們把 count number 變成了 count the magnitude， 但是在某些條件下，上式的解與松弛之前的解等價。上述方法也叫 BP，新定義的問題是一個凸優化問題，解決的方法很多，有 Interior Point methods, Sequential shrinkage for union of ortho-bases, Iterative shrinkage 等。

?

Greedy Methods - Matching Pursuit (MP)
第一步，找到最接近(平行) y 的 atom， 等效與在 alpha 向量上僅取一個非零項，求出最接近的 atom， 保留下來
第二步，計算誤差是否滿足要求，如果滿足，算法停止，否則，計算出殘差信號，和第一步類似，找到最接近殘差向量的 atom， 保留下來
第三步，調整已選向量的系數，使得 Da 最接近 y，重復第二步 (OMP, Orthogonal Matching Pursuit)

總結一下解決這個問題的算法有：

?

3. Dictionary Learning - K-SVD

字典學習的一個假設是——字典對于一張 good-behaved 的圖像具有稀疏表示。因此，選擇字典的原則就有能夠稀疏地表達信號。有兩種方法來設計字典，一種是從已知的變換基中選擇，或者可以稱為 beyond wavelet 變換，比如 DCT 實際上就是一個稀疏表示（高頻部分系數趨向于 0），這種方法很通用，但是不能夠 adapted to the signal。第二種方法是字典學習，即通過已有的大量圖片數據進行訓練和學習。

比如，現在有 P 個信號（張圖片）要進行稀疏表示，如何學習一個字典？

上式字典矩陣 D 和 alpha 組成的稀疏表示 A 矩陣都是可變量，目前有幾種算法解決這個問題，下面介紹 K-SVD 算法（K-Means的一種變種），idea 非常簡單。假設現在有原始信號矩陣 X^T, 該矩陣的每一行表示一個信號或者一張圖片， D 矩陣是字典矩陣，右下方是 sparse coding 矩陣，紅色的點表示非零項：

算法步驟如下：

?

Step 1: Initialize。在 X^T 矩陣中隨機挑選一些行向量(一些原圖），填滿矩陣 D。（ K-means 隨機選點初始化)?

Step 2:?Sparse Coding. 用上一小節的方法（松弛或者貪婪法）進行稀疏編碼，Row-by-Row 計算出稀疏矩陣。

Step 3:?Dictionary Update. 字典以列向量為基，自然要 Column-by-Column 地更新字典。比如現在更新某一列, 下方對應的紅點，根據紅點找到對應的信號（圖像），然后除掉其他不相關的圖像，得到示意圖如下：

上圖中字典的 atom 對四張圖片都有貢獻，我們調整 atom 的目的是使得這個貢獻更大，從而使稀疏性表示效果更好。當然，一個 atom 只能表示一條直線，三張圖片的信號極有可能不在這條直線上，我們要做的是將中間的誤差降到最小，這其實就是一個最小二乘（MSE）的問題。具體做法是將最右下角的矩陣進行 SVD 分解(SVD 相關知識可參考之前我寫的博客)，找出主成分，然后回到 Step2, 迭代。

聲明

之前雖然聽過壓縮感知和稀疏表示，實際上前兩天才正式著手開始了解，純屬新手，如有錯誤，敬請指出，共同進步。

主要學習資料是 Coursera 上 Duke 大學的公開課——Image and video processing, by Pro.Guillermo Sapiro?第 9 課。

由于對圖像處理的了解也來自與該課程，沒正經兒看過幾本圖像方面的書籍，有些術語只能用視頻中的英文來表達，見諒哈！

---

?

1. From Local to Global Treatment

圖片尺寸有大有小，在 DCT 變換中，我們一般取 8×8 的方塊作為一組 64 維的變換信號，在稀疏表示中，我們同樣也不能把整張圖片作為 X^T 矩陣，而是在大圖片中取一定尺寸的 patch (假設是 8×8 的方塊)作為一個 signal。對于圖片中的所有的 patch (假設 ij 是 patch 的左上角坐標)組成的信號，已知字典 D 和噪聲圖片 y ，估計公式如下：

y: 帶有噪音的圖片—— the whole image
x: 要恢復的 clear image
Rij x: 以 i，j 為左上角坐標的 patch， Rij 是從 x 中提取 patch 的 0-1 矩陣
D： 字典 for all the overlapping patches

字典 D 從哪里學習？第一種選擇是基于圖片的數據庫，第二種是直接使用要降噪的圖片進行訓練。還有一種可能性是：首先基于圖片的數據庫得到字典 D (off-line)，接著來了一張要降噪的圖片，我們的做法是新建一個以 D 為初始化的字典，在要處理的圖片上再進行迭代(on-line)，得到新字典，這個新字典更適合降噪，代價是多一些計算。

?

2. K-SVD Image Denoising

在上一小節中，我們提出的可能性是 D 也需要根據要降噪的圖片進行再適應，所以，圖片降噪的公式多了一參數：

有三個變量，處理方法是先固定其中兩個，優化一個，然后迭代。從整體上來說，先用 K-SVD 算法得到字典矩陣 D 和系數編碼 alpha，保持它們不動，再優化 x：

x 的最優解實際上就是所有包含 x 像素點的 patch 的平均值，比如 patch 的大小是 8×8， 那么包含圖片中某一個像素點的 patch 就有 64 個，這個像素點最優解就是取這 64 個patch 對應位置的平均值。當然，你也可以用權重來調節不同位置的 patch 對 pixel 的影響，比如 pixel 在中間的 patch，權重大，pixel 在 patch 邊邊角角的地方，權重小。

?

3. Compressed Sensing

前面我們探討了 sparse represent 的等式，這里主要講 compressed sensing 的概念，即在稀疏表示的等號兩邊同時乘以矩陣 Q：

就變成了：

用公式可以表達為：

可以看到，變換后的信號被大大壓縮了。在一直 x波浪 和 D波浪 的情況下求 alpha 這個問題和前面 sparse coding 非常類似。一個關鍵問題是：在什么條件下由已知信號 x波浪 的情況下恢復稀疏表示 alpha？顯然，這個問題與矩陣 Q，字典 D 和 alpha 的 sparse level 有關，背后涉及很多數學理論。

?

4. Structured Sparse Models and GMM

待續...

?

5. Sparse Modeling and Classification-Activity Recognition

?待續...

?

?

?

from：http://www.cnblogs.com/daniel-D/

總結

以上是生活随笔為你收集整理的稀疏表示介绍(中)、(下)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。