一種改進的K—均值聚類分形編碼方法

郭慧+賀杰+陳曉虹

摘 要：為了解決分形圖像編碼耗時過長的問題，該論文主要研究了基于K-均值聚類的快速分形編碼算法。首先引入方差法將子塊分為簡單塊和復雜塊，隨后采用K-均值聚類算法對復雜子塊及父塊進行分類，并在搜索匹配父塊的過程中運用近鄰搜索法，使得相應子塊僅在近鄰范圍內與同類的父塊進行匹配運算。該方法對匹配塊的搜索過程進行了優化，大幅度減少了編碼時間。測試結果表明，與基本分形編碼算法相比可提速多倍，并且其重構圖像效果較好。

關鍵詞：分形圖像編碼；K-均值聚類；近鄰搜索；方差法

中圖分類號：TP391 文獻標識碼：A

Abstract：In order to solve 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 algorithm 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 the 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 clustering；nearest neighbor search；variance method

1 引言（Introduction）

分形圖像編碼算法具有壓縮比高、快速解碼和分辨率無關等優點，但其編碼速度慢，使得分形圖像編碼難以實時化。如何提高分形編碼速度成為分形圖像壓縮的主要研究方向之一。目前對分形編碼算法進行改進主要分為兩類：子塊分類和鄰域搜索。

子塊分類法是在搜素匹配塊之前，先按照某種特征將子塊和父塊分類，從而在匹配時用類內搜索代替全局搜索，以此來提高編碼速度。國內外學者近年來就如何設計準確的分類方法做了很多嘗試。文獻[1]提出采用邊緣分類算法將父塊分為邊緣類和非邊緣類，并將各類父塊按平均偏差排序。文獻[2]針對在K-均值聚類算法中初始聚類中心難以選取的問題，提出了一種均值-標準差的初始聚類中心選取方法，并將其應用到分形圖像編碼中，對子塊和父塊進行聚類。文獻[3]利用像素值空間和1D-DCT矢量實現模糊聚類，在解碼質量同等的情況下將編碼速度提高了40倍。

由于大量的實驗數據表明，與子塊匹配的父塊大多數都在子塊的附近，鄰域搜索成為近年來研究最為集中的優化方法。文獻[4]利用邊緣形狀相似的塊集中于某些特定區域這一現象來實現鄰域搜索。文獻[5]-文獻[7]則取得了持續進展，先后使用三均值特征、四位數特征、轉動慣量特征來實現鄰域搜索方法。文獻[8]-文獻[9]則分別提出了基于相似比、基于相對誤差的鄰域搜索方法。文獻[10]利用互惠最近鄰聚類算法實現彩色圖像的自動分割。

在以上兩類改進方法中，利用K-均值聚類算法對子塊和父塊進行分類處理，從而在更小范圍內進行匹配搜索。這類方法引起了人們的重視，然而現有的K-均值聚類分形編碼方法在選取聚類中心時普遍采用了隨機選取初始聚類中心的策略，嚴重影響了分形圖像編碼的工作效率，而且降低了系統的穩定性。文獻[2]結合數據分布的特點，采用基于均值-標準差的初始聚類中心選取方案，能有效減少K-均值聚類算法的迭代次數，加速聚類收斂速度，并將該方法應用于分形圖像壓縮編碼，有效地縮短了編碼時間。本文在文獻[2]的基礎上對分形編碼算法進行了改進。首先引入基于方差的分類方法將子塊分為簡單塊和復雜塊，并只對復雜塊進行編碼，隨后采用文獻[2提出的基于均值-標準差方法來選取初始聚類中心，對子塊和父塊進行聚類，并在搜索匹配父塊的過程中運用了近鄰搜索法，使得相應子塊僅在近鄰范圍內與同類的父塊進行匹配運算。實驗結果表明：本文算法能在保證重構圖像質量的前提下，速度是基本分形編碼算法的500多倍；與文獻[2]提出的算法相比，本文算法能在保證重構圖像質量的前提下提速190倍。

2 基本分形圖像編碼（The basic fractal image

coding）

在基本分形圖像編碼中，圖像被分割為互不重疊、大小為B×B的子塊（簡稱R塊）集合，然后以步長為、尺寸為2B×2B的窗口從上到下、從左到右滑動生成父塊（簡稱D塊）集合。隨后將所得D塊進行4鄰域像素平均操作，生成新的D塊集合，以此作為匹配運算的碼本Ω，最后對Ω進行八種等距變換，以實現對碼本的擴充。對于任意R塊，尋找能夠滿足式（1）的最佳匹配塊Dm：endprint