一种改进的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