智能目標識別分類技術(shù)

一、K-均值算法因為K-SVD算法是由K-均值擴展而來，有必要先簡單介紹K-均值算法。K-均值算法要解決的問題是：求解一個包括K個代碼的碼本，使得在此碼本上，根據(jù)最近鄰分配法則，對包括N個信號的信號集合Y={yh,N□K進行分類，得ii=1到最佳分類問題。此時，Y中各向量被歸類于與之距離最小的代碼所代表的類中，C={c，c，…,c}為碼本，C中的列c為碼本中的大媽。當碼本C給定時，每個TOC\o"1-5"\h\z1 2 K i信號用最近（12-范數(shù)意義下）的一個代碼表示。也就是說，y沁Cx，其中x=ei ij是自然基中的一個向量（除第j個值為1外，其他值都為0）。滿足\o"CurrentDocument"vk豐j‘||y.-Ce.||2勻|y.-CekII2 ⑹i J2 i k2這相當于稀疏編碼的一個特例：只用一個原子表示信號y，同時強制系數(shù)等i于1。這種表示方法中，yi的方差為e2=||y-Cx||2，則Y的量化誤差由下式確定1 i i i2E2=fe2=||Y-CX||2 ⑺i Fi=1K-均值算法的目標函數(shù)如下式Vi,x=eikmin{YVi,x=eikC‘X FK-均值算法的實現(xiàn)是一個迭代過程，包括兩步：（1）求X,本質(zhì)上就是稀疏編碼；（2）更新碼本。?①???碼；（2）更新碼本。?①??????O圖4K均值算法步驟示意圖

從上圖中，我們可以看到，A，B，C，D，E是五個在圖中點。而灰色的點

是我們的種子點，也就是我們用來找點群的點。有兩個種子點，所以K=2。然后，K-Means的算法如下：1。 隨機在圖中取K（這里K=2）個種子點。2。 然后對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（上圖中，我們可以看到A，B屬于上面的種子點，，C，D，E屬于下面中部的種子點）3。 接下來，我們要移動種子點到屬于他的“點群”的中心。（見圖上的第三步）4。 然后重復第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A，B，C,下面的種子點聚合了D，E）。二、K-SVD算法K-SVD算法和K-均值聚類算法有著很深的聯(lián)系，當K-SVD算法中要求的每個信號只用一個原子來近似時，K-SVD算法就退化為K均值聚類算法。同樣，稀疏表示也可看作廣義的矢量量化（VQ），其中的每個信號用多個代碼的線性組合表示。令De□nxK,ye□n,xe□k分別代表字典、訓練信號、訓練信號的稀疏表示系數(shù)

向量，Y={yh為N個訓練信號的集合，X={x}n為Y的解向量的集合。從線TOC\o"1-5"\h\zii=1 ii=1性組合角度看，K-SVD訓練算法的目標方程可表示為min{Y-DX||2} s.t ViJ|x||<T (9)D,X F i0 0其中，T為稀疏表示系數(shù)中非零分量的數(shù)目的上限，即系數(shù)向量中最大差異0度。從誤差逼近角度來看，K-SVD訓練算法的目標方程還可以表示為min{|x||}, s.t ||Y-DX\|2<￡ (10)D,X i0 F本質(zhì)上，式(9)和式(10)是相同的，只是考慮問題的角度不同，K-SVD作者在論文中的目標函數(shù)式子采用(9)。式(9)求解是一個迭代過程。首先，假設(shè)字典D是固定的，用MP、OMP、或BP等算法可以得到字典D上Y的稀疏表示的系數(shù)矩陣X；然后根據(jù)系數(shù)矩陣X，找到更好的字典D。字典的更新是逐列進行的。首先假設(shè)系數(shù)矩陣X和字典D都是固定的，將要更新字典的第k列d，令系數(shù)矩陣X中d相應(yīng)的k行為xk(不同于X的第k列xkkTk的轉(zhuǎn)置)，則目標函數(shù)式(6。21)中的懲罰項可以重寫為IY-DXII2FIY-DXII2FXj—dxkjT丿j*k 丿kT2=IIe—dxk11kkTFF(11)上式中，乘積DX被分解成K個秩為1的矩陣和。按照假設(shè)其中K-1項是固定的。所剩的一個，也就是要處理的第k個。矩陣E代表的是去掉原子d的成分在所kk有N個樣本中造成的誤差。如果此時就用奇異值分解(SVD)更新d和xk，SVD能找到距離E最近的秩為kTk1的矩陣，這能有效地減少式(10)代表的誤差。但是，如此得到的xk將是滿向量T(相對于稀疏向量而言，滿向量表示向量大多數(shù)元素都是非零元的向量)，所以更新的d也不能被強制的滿足稀疏條件。換句話說，因為xk中的0的影響，用SVDkT得到的xk更新向量中的非零值的位置和數(shù)量會和原xk中非零位置和數(shù)量不同，TT出現(xiàn)“發(fā)散”。為解決此問題，直觀的可以看出，去掉xk中所有的0僅保留非零值，再用SVD更新d和xk時，就不會出現(xiàn)“發(fā)散”現(xiàn)象了。kT定義集合? ｛II<i<N,xk(i)H0｝為用到d所有信號集合｛y｝的索引所構(gòu)TOC\o"1-5"\h\zk T k i成的集合，即xk(i)z0的點的索引值。定義。為Nx|o|矩陣，他在(o(i),i)處T k k k的值都為1,其他點為0。定義xk二xkG、Yk二YkQ、Ek二EkQ，則三者分別RTkRTkRTk為xk、Y、E中去掉零輸入后的收縮結(jié)果，Yk為當前用到原子d的樣本集合，EkT k R k T為去掉不受原子d影響的樣本后，如果不考慮d在其受影響的樣本中成分時，k k帶來的誤差。xk的長度為|w，Yk、Ek是nx|wI矩陣。R 1k RR 1k1此時，最小化式(11)得到的解xk和原xk就會有相同的支撐，不會出現(xiàn)“發(fā)TT散”。相當于式(11)經(jīng)過一次轉(zhuǎn)化，轉(zhuǎn)化為IIeQ-dxkQ2=||Ek-dxklI2 (12)kkkTkl\RkR“f對Ek做SVD分解，則Ek二UAVt，令d為U的第一列，則d為d的更新結(jié)果。R R k k k同時，用V的第一列和A(l,l)的乘積更新xk。在逐列更新完成后用字典D做稀R疏分解，并判斷是否達到停止條件(停止條件可以是既定的迭代次數(shù)或者重構(gòu)信號和原信號之間的誤差率)，以決定迭代是否繼續(xù)。K-SVD算法非常靈活，可以和常見的稀疏分解的最優(yōu)原子搜索算法(如匹配追蹤(MP)、正交匹配追蹤(OMP)、基追蹤(BP)、FOCUSS等)結(jié)合使用。文中所選的是正交匹配追蹤算法。三、 K-SVD算法仿真實驗結(jié)果在以上知識的指導下，我們給出了在高斯白噪聲下使用KSVD方法進行去噪的仿真結(jié)果。實驗設(shè)置：實驗用圖為標準測試圖Barbara、House、Lena和Peppers。所加高斯白噪聲分別方差分別為15、25和35。而去噪過程中所采用的字典分別為固定的DCT字典和文檔中所闡述的使用噪聲塊學習出的字典。實驗用圖如下：圖5實驗用原圖和加標準差為15、5、5的噪聲圖像，從左至右分別為Barbara、ouse、Lena和Peppers分別采用了兩種字典學習方式一一固定的DCT字典和由噪聲圖像學習的字典,去噪結(jié)果圖由下圖所示：

圖6固定DCT字典的K-SVD算法去噪結(jié)果圖，從上到下噪聲標準差為15、25、35■圖■圖7基于噪聲圖像塊學習的字典的KSVD去噪結(jié)果■盤■盤EUS9KH闈DM陽■羽■■.電懸範龍團應(yīng)曲Hi切用■加心￡然:1i視』輯猷■胡自召去il閒詈tie亠rH,\i1浴肯IIK'K占暫耳■U.：x［滅耆砌殘IW嚴辯輕H:T痢CLfXSMTOfflQCK^K落■職￥鼻鼻2比左懸諛FS3FKWm.'Jli^Yi'M工宣?KiXZVJ皿曲先妗JillIIf髓?鳴斟薄用那的帀楸閾1、刪惱WZKWfflASJ—XI|怫?詢轡帰妙J城沏訓':l3IIIIIIWS?7/Wfllll?!WZ曲辭MNM-57J1?丄公左葉眾站慰骰■菩I-(a)(b)圖8K-SVD算法所用字典結(jié)果(a)DCT字典(b)自適應(yīng)學習的字典表1定量分析不同噪聲標準差下應(yīng)用不同字典的去噪結(jié)果o=15o=25o=35噪聲圖DCTAdaptive噪聲圖DCTAdaptive噪聲圖DCTAdaptiveBarbara24.6131.6532.3820.1628.6929.6317.2426.7127.81House24.5933.4534.2720.1630.9932.0717.2829.2930.31Lena24.5833.3533.6720.1530.9231.3417.2229.1729.65Peppers24.6131.6732.1420.1828.9129.6317.2627.1828.09由圖6、圖7和表1所示，我們可以看到K-SVD算法在去噪性能確實有很明顯的效果。屬于目前流行的幾種去噪算法之一。細節(jié)上看，固定的DCT字典不能很好的適應(yīng)各類圖像，而去噪的結(jié)果也沒有自適應(yīng)學習的字典效果好。宏觀上看，K-SVD算法在低標準差