用于圖像分類在線字典學(xué)習(xí)算法

蘭 俊 花

(天津大學(xué) 理學(xué)院數(shù)學(xué)系, 天津300072)

用于圖像分類在線字典學(xué)習(xí)算法

蘭 俊 花

(天津大學(xué) 理學(xué)院數(shù)學(xué)系, 天津300072)

稀疏編碼在人臉識別上的成功促使這項技術(shù)應(yīng)用在更廣泛的計算機(jī)視覺中.圖像分類是圖像檢索的基礎(chǔ)，而圖像的識別是比人臉識別更復(fù)雜，因為首先圖像數(shù)據(jù)量更大，其次圖像中要檢索的目標(biāo)數(shù)據(jù)不易得到.為解決這兩個問題，提出了一種新的在線字典學(xué)習(xí)的算法.實驗結(jié)果表明本方法在圖像分類上比最近提出的其他字典學(xué)習(xí)的方法效果更好.

稀疏編碼；字典學(xué)習(xí)；圖像分類

近些年，稀疏編碼和字典學(xué)習(xí)被成功地應(yīng)用在很多的領(lǐng)域，包括圖像去噪[1]，圖像超分辨率，面部識別[2]，以及圖像分類和識別[3].這主要是因為屬于同一類的高維的自然信號近似地存在于一個低維的子空間，這樣一個信號可以被少量的原子近似的表示，也就是存在一個過完備的字典D={d1,d2,…,dk}∈Rm×k(m

經(jīng)典的字典學(xué)習(xí)包含兩個迭代步驟：稀疏編碼和字典更新.稀疏編碼就是對于給定的字典找到信號的線性分解，然后固定稀疏編碼對字典進(jìn)行更新，這個過程不斷迭代直到最合適的字典找到為止.然而，盡管這些方法得到的字典對原始信號有很高的精確度，在圖像去噪，圖像填充中有很好的效果，但是這些字典對于圖像的分類卻沒有很好的效果.因為這些方法的目的是最小化原始信號的重構(gòu)誤差，所得到的字典沒有圖像類別的判別信息.

為了解決分類問題，許多監(jiān)督的字典學(xué)習(xí)方法被提出來.最近Zhang等[3]在字典學(xué)習(xí)中將分類器的訓(xùn)練添加到目標(biāo)函數(shù)中，獲得了很好的分類效果.Pham等[4]首先學(xué)習(xí)一個字典，然后用稀疏編碼作為特征來訓(xùn)練一個分類器，比如，SVM. Ramirez等[5]通過加入了一個非同類表示錯誤項學(xué)習(xí)了一個結(jié)構(gòu)化的字典，然后應(yīng)用重構(gòu)誤差進(jìn)行分類，但是這樣的分類過程比較復(fù)雜.

受前面方法的啟示，我們也考慮將類的標(biāo)簽信息加在字典學(xué)習(xí)的過程中.直觀上來說，像圖像這類高維的信號，屬于同一個類中的圖像接近與一個低維的子空間，這樣，如果找到了每一個類中的具有代表性的較少的幾個采樣標(biāo)本，聯(lián)合他們成為一個整體的字典，那么一個信號在這個字典下將有稀疏的表示，同時所得到的稀疏編碼包含了這個信號屬于哪一個類這樣的語義信息.實驗證明，不同類的特征通常共享一些相同的信息，所以不同類中的字典可能共享一些相似的字典原子，這樣使得依靠重構(gòu)誤差得到的分類結(jié)果變差，為了解決這類問題，本文將不同類表示錯誤項和分類錯誤項加到目標(biāo)函數(shù)中，本方法將學(xué)習(xí)一個鑒別的字典，同時學(xué)習(xí)到的分類器可以使得分類更簡便.

1 字典學(xué)習(xí)的介紹

考慮一組輸入信號Y=[y1,y2,…,yn]∈Rm×n，傳統(tǒng)的字典學(xué)習(xí)即最小化下面的期望重構(gòu)誤差：

(1)

(2)

許多算法可以得到這個問題的近似解，比如 K-SVD, 然而K-SVD解的是一個l0范數(shù)限制問題，這個問題不是凸的，因此這個解在理論上是次最優(yōu)的.

最近，作為l0范數(shù)的一個凸松弛，l1范數(shù)被廣泛的應(yīng)用，因為l1范數(shù)比l0范數(shù)穩(wěn)定，所以對于輸入信號的一些小地擾動不是很敏感，同時l1范數(shù)求解到的非零系數(shù)集中在訓(xùn)練采樣所在的類中，這樣字典學(xué)習(xí)的問題可以表示為：

(3)

參數(shù)λ控制著重構(gòu)誤差和稀疏編碼的權(quán)重.需要注意的是式(3)中的問題對于D和X不是凸的，但對于D和X中的任意一個是穩(wěn)定時，同時這個問題是一個凸問題.

當(dāng)D固定時這個問題叫做稀疏編碼.每個信號yi期望用少量的幾個原子字典進(jìn)行稀疏表示，這個問題是一個l1正則化最小二乘問題，許多方法可以用來解決此問題，比如：內(nèi)點法，同倫法，LARS，Lee等[3]提出了feature-signsearch算法對于解決此問題有更好的效.

當(dāng)穩(wěn)定時，這個問題叫做字典學(xué)習(xí)，這是一個 l2限制的最小二乘問題，用Marial等[6]block-coordinatedescent方法來求解.

稀疏編碼作為一個特征用來學(xué)習(xí)一個分類器被廣泛的應(yīng)用.對于分類器一個簡單的形式可以定義為：

(4)

2 算法實現(xiàn)的過程

2.1 固定D和W求解稀疏編碼X

令Y=[y1,y2,…,yc]∈Rm×n是輸入信號，X=[x1,x2,…xc]為輸入信號經(jīng)過字典后的的稀疏表示

λ‖xi‖1

(5)

這是一個經(jīng)典的lasso模型，這里我們使用feature-sign search 算法來解決此問題.

2.2 固定X, 更新D和W

為了加強(qiáng)字典的鑒別作用，使得得到的稀疏編碼更簡單，同時更新D和W, 這個問題可以表示為：

(6)

(7)

我們應(yīng)用用Marial等[11]block-coordinate descent方法來求解.

2.3 初始化參數(shù)D0,W0

對于D0我們采用高斯隨機(jī)矩陣(Gaussian random matrix)，對于W0我們采用多變量回歸模型(multivariate ridge regression)

(8)

W的解為：

W=HXT(XXT+αI)-1

(9)

(10)

對于一個新的檢測信號，我們首先通過下面的等式得到它的稀疏編碼：

(11)

然后x的類可以通過：

(12)

獲得.這里的l∈Rc是類標(biāo)簽向量.

3 實 驗

本文在兩個公共數(shù)據(jù)庫上檢測這個方法(Extended YaleB database[7]，MNIST[8])，同時和一些監(jiān)督的學(xué)習(xí)方法(D-KSVD[9]，LC-KSVD[10]，LLC[11])以及一些基準(zhǔn)算法(K-SVD[1]和SRC[2]進(jìn)行比較.

3.1 Extend YaleB database上的實驗

我們?nèi)×?個不同的字典個數(shù)，即對于每一類字典原子的個數(shù)k=5，10，15，20.實驗的結(jié)果顯示在表1中.從表1中可以看出本文的新方法比其他的方法有更高的識別準(zhǔn)確度.當(dāng)每個類中有20個字典時，SRC的最好的識別率是88.8%，而我們的方法在每個類中字典個數(shù)是5時就超過了SRC方法.這意味這我們的方法得到了一個簡潔的合適的字典.當(dāng)k=15時，識別率達(dá)到95.6%，但當(dāng)k=20時，識別率下降到94.9%，這可能是因為訓(xùn)練集個數(shù)過小而產(chǎn)生的過完備效應(yīng).K-SVD算法當(dāng)k=20時識別率明顯下降，這也說明了l0范數(shù)處理問題的不穩(wěn)定性.

表1 Extend YaleB database上人臉識別

3.2 對于數(shù)字的識別

本文應(yīng)用MNIST[8]數(shù)據(jù)集作為手寫字體識別.它包含了70 000個手寫字，其中60 000個作為訓(xùn)練集，10 000作為檢測集每個數(shù)字被正則化和中心化為一個2828的圖片，我們僅僅顯示4，7，9這三個容易混淆的數(shù)字.實驗結(jié)果顯示在表2中(實驗中每類中字典原子的個數(shù)選為15)，實驗結(jié)果顯示我們的算法得到很好的結(jié)果.

表2 對數(shù)字識別

4 結(jié) 語

對于圖像的分類，本文提出了一個在線鑒別字典學(xué)習(xí)的方法.通過實驗顯示了范數(shù)在處理稀疏編碼問題中比范數(shù)更精確，同時實驗表明在線字典學(xué)習(xí)使用更少的內(nèi)存和時間，字典和分類器同時學(xué)習(xí)得到更好的分類效果.我們將來的工作包括研究核字典學(xué)習(xí)和核稀疏編碼，從而對大數(shù)據(jù)有更好的分類效果.

[1] AHARON M, ELAD M, BRUCKSTEIN A,etal. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation [J]. IEEE Trans. Signal Processing， 2006, 54(11): 4311-4322.

[2] WRIGHT J, YANG A, GANESH A,etal. Robust Face Recognition via Sparse Representation [J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2009, 31: 210-227.

[3] JIANG Z, LIN Z, DAVIS L. Label Consistent K-SVD: Learning a discriminative dictionary for recognition [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35: 2651-2664.

[4] PHAM D S, VENKATESH S. Joint learning and dictionary construction for pattern recognition[C]// IEEE Conference on Computer Vision and Pattern Recognition, 2008.

[5] RAMIREZ I, SPRECHMANN P, SAPIRO G. Classification and clustering via dictionary learning with structured incoherence and shared features[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2010.

[6] MARIAL J, BACH F, PONCE J,etal. Online learning for matrix factorization and sparse coding [J]. Journal of Machine learning Research, 2010, 11: 19-60.

[7] LECUN Y, BOTTOU L, BENGIO Y. Gradient-based learning applied to document recognition [J]. Proceedings of IEEE, 1998, 86: 2278-2324.

[8] GEORGHIADES A, BELHUMEUR P, KRIEGMAN D. From few to many:Illumination cone models for face recognition under variable lighting and pose [J]. IEEE Trans. Pattern Anal. Mach. Intelligence, 2001, 33: 643-666.

[9] ZHANG Q, LI B. Discriminative k-svd for dictionary learning in face recognition[C]// IEEE Conference on Computer Vision and Pattern Recognition, 2010.

[10] JIANG Z, LIN Z, DAVIS L. Label Consistent K-SVD: Learning a discriminative dictionary for recognition [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35: 2651-2664.

[11] WANG J, YANG J, YU K,etal. Locality-constrained linear coding for image classification[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2010， 3360-3367.

Online dictionary learning algorithm for image classification

LAN Jun-hua

(Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China)

The success application of sparse coding in face recognition makes this technology used to a variety of problems in computer vision. Image classification is the basis of image retrieval, but image recognition is more complex than face images.In order to solve these two problems, this paper proposed a new online dictionary learning algorithm. The experimental results showed that the method was better than other dictionary learning method in image classification.

sparse coding, dictionary learning, image classification

2014-08-11.

蘭俊花(1989-)，女，碩士，研究方向：圖像處理.

TP391

A

1672-0946(2015)05-0637-04