非負(fù)矩陣分解方法及其在選票圖像識別中的應(yīng)用.pdf

1、圖像識別是隨著計算機技術(shù)發(fā)展而興起的。它利用計算機對圖像進行處理，以識別各種不同模式的目標(biāo)和對象，是圖像融合、立體視覺、運動分析等實用技術(shù)的基礎(chǔ)。
　　 近年來，隨著圖像識別技術(shù)在自然資源分析、生理病變、天氣預(yù)報、導(dǎo)航、地圖與地形配準(zhǔn)、環(huán)境監(jiān)測等領(lǐng)域的廣泛應(yīng)用，各種理論和方法也被大量應(yīng)用到圖像識別中，非負(fù)矩陣分解(Non-negativeMatrixFactorization，NMF)理論就是其中之一，是當(dāng)今的研究熱點。NMF是

2、從“對整體的感知由對組成整體的部分感知構(gòu)成”觀點出發(fā)而構(gòu)建的。它將一個非負(fù)矩陣分解為兩個非負(fù)矩陣的乘積，原矩陣中的一列可以解釋為基矩陣巾所有列向量的加權(quán)和，而權(quán)重系數(shù)為權(quán)重矩陣中對應(yīng)列向量中的元素。這樣基于向量組合的分解具有可解釋性和明確的物理意義，而且占用存儲空間更少，是一個處理非負(fù)數(shù)據(jù)的強大工具。從模式識別角度來看，NMF實質(zhì)上是一種子空間分析方法，其本質(zhì)是一種特征提取和選擇的方法。NMF的主要思想是在樣本空間中尋找合適的子空間（特

3、征子空間），通過將高維樣本投影到低維子空間上，從而在子空間上獲得樣本的本質(zhì)特征，利用這些特征實現(xiàn)分類。作為一項數(shù)據(jù)處理技術(shù)，NMF揭示了描述數(shù)據(jù)的本質(zhì)，已經(jīng)被廣泛應(yīng)用到人臉檢測與識別、圖像融合、圖像檢索、圖像分類、圖像復(fù)原、圖像壓縮、灰度圖像的數(shù)字水印、文本分析與聚類、語音識別、生物醫(yī)學(xué)工程、網(wǎng)絡(luò)安全的入侵檢測等諸多方面的研究中。
　　 本文在非負(fù)矩陣分解理論方面進行深入研究。首先，基于Frobenius范數(shù)和Kullback-

4、Leibler散度的兩個目標(biāo)函數(shù)，利用Taylor展開式、穩(wěn)定點求解和Newton求根公式，提出了一種非負(fù)矩陣分解的理論分析方法;然后，利用該方法，嚴(yán)格導(dǎo)出了三種非負(fù)矩陣分解方法，解決了相關(guān)問題。最后，將結(jié)構(gòu)模式識別方法和本文的非負(fù)矩陣分解方法應(yīng)用到選票圖像中的特殊手寫符號識別，詳細(xì)給出了選票圖像識別方法。本文的主要貢獻有以下幾個方而:
　　 1.提出了非負(fù)矩陣分解新方法
　　 根據(jù)Frobenius范數(shù)‖X-WH‖2F

5、和Kullback-Leibler散度D(X‖WH)，提出了一種新的非負(fù)矩陣分解(NovelNon-negativeMatrixFactorization，NNMF)方法。從理論上嚴(yán)格推導(dǎo)了非負(fù)矩陣分解中基矩陣和權(quán)重矩陣的迭代公式，算法推導(dǎo)方法是新穎的。證明了算法的收斂性。給出了算法步驟。與標(biāo)準(zhǔn)NMF方法比較，本文的方法更容易找到輔助函數(shù)，從而更容易確定迭代公式。當(dāng)使用Frobenius范數(shù)作為目標(biāo)函數(shù)時，可以得到與標(biāo)準(zhǔn)NMF完全相同的

6、迭代公式。當(dāng)使用Kullback-Leibler散度作為口標(biāo)函數(shù)時，獲得了一組新的迭代公式;在人臉識別實驗中，當(dāng)收斂精度不是很高時，基矩陣的列基取不同值的大部分情況下，相對于相應(yīng)的標(biāo)準(zhǔn)NMF算法，該算法具有較高的識別率。
　　 2.提出了近似正交非負(fù)矩陣分解方法
　　 將Frobenius范數(shù)和近似正交約束作為目標(biāo)函數(shù)，提出了近似正交非負(fù)矩陣分解（ApproximateOrthogonalNon-negativeMatr

7、ixFactorization，AONMF）方法。利用Taylor展開式和穩(wěn)定點求解方法，嚴(yán)格導(dǎo)出了非負(fù)矩陣分解的基矩陣和權(quán)重矩陣的迭代更新算法，并證明了算法的收斂性、闡述了基矩陣近似正交的理由。人臉識別結(jié)果表明:只要基矩陣的秩選擇恰當(dāng)，識別率是較高的。
　　 3.提出了收斂投影非負(fù)矩陣分解方法
　　 為了解決投影非負(fù)矩陣分解(ProjectiveNon-negativeMatrixFactorization，P-NMF

8、)算法的收斂性問題，提出了收斂投影非負(fù)矩陣分解(ConvergentProjectiveNon-negativeMatrixFactorization，CP-NMF)方法。分別利用Frobenius范數(shù)和Kullback-Leibler散度作為目標(biāo)函數(shù)，利用Taylor展開式和Newton迭代求根公式，嚴(yán)格導(dǎo)出了投影非負(fù)矩陣分解的基矩陣迭代算法，并證明了算法的收斂性。實驗結(jié)果表明:該算法具有較快的收斂速度，而基矩陣的初值會影響收斂速度;

9、相對于標(biāo)準(zhǔn)NMF，該方法的基矩陣具有更好的正交性和稀疏性，但數(shù)據(jù)重建結(jié)果說明基矩陣仍然是近似正交的;人臉識別結(jié)果表明該方法具有較高的識別率。
　　 4.提出了線性投影非負(fù)矩陣分解方法
　　 針對基于線性投影結(jié)構(gòu)的非負(fù)矩陣分解(LinearProjection-BasedNon-negativeMatrixFactorization，LPBNMF)迭代方法比較復(fù)雜的問題，提出了線性投影非負(fù)矩陣分解(LinearProjec

10、tiveNon-negativeMatrixFactorization，LP-NMF)方法。從投影和線性變換角度出發(fā)，將Frobenius范數(shù)作為目標(biāo)函數(shù)，利用Taylor展開式和穩(wěn)定點求解方法，嚴(yán)格導(dǎo)出了基矩陣和線性變換矩陣的迭代算法，并證明了算法的收斂性。實驗結(jié)果表明:該算法是收斂的;相對于一些非負(fù)矩陣分解方法，該方法的基矩陣具有更好的正交性和稀疏性;人臉識別結(jié)果說明該方法具有較高的識別率。
　　 5.提出了選票圖像識別方法

11、
　　 選票圖像中的特殊手寫符號通常是:勾“√”、罔“○”、叉“×”、杠“＼、—、/（三種寫法）”。為了解決基于光學(xué)字符識別(OpticalCharacterRecognition，OCR)技術(shù)的選舉投票系統(tǒng)巾手寫符號圖像的快速定位與識別問題，提出了選票圖像識別方法。該方法在充分考慮選舉信息的基礎(chǔ)上，實現(xiàn)了選票的可視化設(shè)計。該選票設(shè)計記錄了選舉信息巾相關(guān)對象的位置數(shù)據(jù)。利用這些數(shù)據(jù)，將選票圖像預(yù)處理后，找到一個確定的參考點，再提

12、取選票設(shè)計中的位置數(shù)據(jù)，將它轉(zhuǎn)化為相對于這個參考點的圖像位置，利用該位置搜索表格線，從而確定要識別圖像的準(zhǔn)確位置;基于該位置，可截取手寫符號圖像，對該圖像進行一系列處理后，提取其結(jié)構(gòu)特征，采用結(jié)構(gòu)模式識別方法識別。如果結(jié)構(gòu)特征無法判別，就采用本文的NMF方法進行新的特征提取后再識別。實驗結(jié)果表明，這種方法的定位速度快、識別率高。結(jié)合選票設(shè)計的識別方法使得識別軟件定位速度更快、選票版面可以更復(fù)雜，采用結(jié)構(gòu)模式識別和NMF相結(jié)合的方法識別準(zhǔn)