一種改進(jìn)的K—均值聚類分形編碼方法

郭慧+賀杰+陳曉虹

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：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）

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

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

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

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

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

coding）

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