技術(shù)報告一種改進(jìn)的K-均值聚類分形編碼方法

1、計劃類別 項目編號 項目技術(shù)報告課題名稱 項目主持人 承擔(dān)單位 題目：一種改進(jìn)的K均值聚類分形編碼方法為了解決分形圖像編碼耗時過長的問題，該論文主要研究了基于K-均值聚類的快速分形編碼算法。首先引入方差法將子塊分為簡單塊和復(fù)雜塊，隨后采用K-均值聚類算法對復(fù)雜子塊及父塊進(jìn)行分類，并在搜索匹配父塊的過程中運(yùn)用近鄰搜索法，使得相應(yīng)子塊僅在近鄰范圍內(nèi)與同類的父塊進(jìn)行匹配運(yùn)算。該方法對匹配塊的搜索過程進(jìn)行了優(yōu)化，大幅度減少了編碼時間。測試結(jié)果表明，與基本分形編碼算法相比可提速多倍，并且其重構(gòu)圖像效果較好。關(guān)鍵詞：分形圖像編碼；K-均值聚類；近鄰搜索；方差法Abstract：In order to so

2、lve the problem of overly long time during fractal image coding，this paper focuses on a fast fractal coding algorithm based on K-means clustering.First of all，the variance method is employed to divide the range blocks into simple range blocks and complex range blocks；then，the K-means clustering algo

3、rithm is applied to classify the complex range blocks and domain blocks，and the nearest neighbor search approach is applied to search matching domain blocks，so as to match the corresponding range blocks with the domain blocks of the same type only within the neighboring scope.This method optimizes t

4、he searching process for matching blocks，thereby greatly shortening the encoding time.Test results show that，compared with the basic fractal coding algorithm，this method can increase the encoding speed by many times，with high-quality reconstructed images.Keywords：fractal image coding；K-means cluster

5、ing；nearest neighbor search；variance method1 引言（Introduction）分形圖像編碼算法具有壓縮比高、快速解碼和分辨率無關(guān)等優(yōu)點(diǎn)，但其編碼速度慢，使得分形圖像編碼難以實時化。如何提高分形編碼速度成為分形圖像壓縮的主要研究方向之一。目前對分形編碼算法進(jìn)行改進(jìn)主要分為兩類：子塊分類和鄰域搜索。子塊分類法是在搜素匹配塊之前，先按照某種特征將子塊和父塊分類，從而在匹配時用類內(nèi)搜索代替全局搜索，以此來提高編碼速度。國內(nèi)外學(xué)者近年來就如何設(shè)計準(zhǔn)確的分類方法做了很多嘗試。文獻(xiàn)1提出采用邊緣分類算法將父塊分為邊緣類和非邊緣類，并將各類父塊按平均偏差排序。文獻(xiàn)2

6、針對在K-均值聚類算法中初始聚類中心難以選取的問題，提出了一種均值-標(biāo)準(zhǔn)差的初始聚類中心選取方法，并將其應(yīng)用到分形圖像編碼中，對子塊和父塊進(jìn)行聚類。文獻(xiàn)3利用像素值空間和1D-DCT矢量實現(xiàn)模糊聚類，在解碼質(zhì)量同等的情況下將編碼速度提高了40倍。由于大量的實驗數(shù)據(jù)表明，與子塊匹配的父塊大多數(shù)都在子塊的附近，鄰域搜索成為近年來研究最為集中的優(yōu)化方法。文獻(xiàn)4利用邊緣形狀相似的塊集中于某些特定區(qū)域這一現(xiàn)象來實現(xiàn)鄰域搜索。文獻(xiàn)5-文獻(xiàn)7則取得了持續(xù)進(jìn)展，先后使用三均值特征、四位數(shù)特征、轉(zhuǎn)動慣量特征來實現(xiàn)鄰域搜索方法。文獻(xiàn)8-文獻(xiàn)9則分別提出了基于相似比、基于相對誤差的鄰域搜索方法。文獻(xiàn)10利用互惠最近

7、鄰聚類算法實現(xiàn)彩色圖像的自動分割。在以上兩類改進(jìn)方法中，利用K-均值聚類算法對子塊和父塊進(jìn)行分類處理，從而在更小范圍內(nèi)進(jìn)行匹配搜索。這類方法引起了人們的重視，然而現(xiàn)有的K-均值聚類分形編碼方法在選取聚類中心時普遍采用了隨機(jī)選取初始聚類中心的策略，嚴(yán)重影響了分形圖像編碼的工作效率，而且降低了系統(tǒng)的穩(wěn)定性。文獻(xiàn)2結(jié)合數(shù)據(jù)分布的特點(diǎn)，采用基于均值-標(biāo)準(zhǔn)差的初始聚類中心選取方案，能有效減少K-均值聚類算法的迭代次數(shù)，加速聚類收斂速度，并將該方法應(yīng)用于分形圖像壓縮編碼，有效地縮短了編碼時間。本文在文獻(xiàn)2的基礎(chǔ)上對分形編碼算法進(jìn)行了改進(jìn)。首先引入基于方差的分類方法將子塊分為簡單塊和復(fù)雜塊，并只對復(fù)雜塊進(jìn)行編碼，隨后采用文獻(xiàn)2提出的基于均值-標(biāo)準(zhǔn)差方法來選取初始聚類中心，對子塊和父塊進(jìn)行聚類，并在搜索匹配父塊的過程中運(yùn)用了近鄰搜索法，使得相應(yīng)子塊僅在近鄰范圍內(nèi)與同類的父塊進(jìn)行匹配運(yùn)算。實驗結(jié)果表明：本文算法能在保證重構(gòu)圖像質(zhì)量的前提下，速度是基本分形編碼算法的500多倍；與文獻(xiàn)2提出的算法相比，本文算法能在保證重構(gòu)圖像質(zhì)量的前提下提速190倍。2 基本分形圖像編碼（The basic fractal imagecoding）在基本分形圖像編碼中，圖像被分割為互不重疊、大小為BB的子塊（簡稱R塊）集合，然后以步長為、尺寸為2B2