基于遗传算法的图形图像自动聚类

摘要

现今社会，网络技术的飞速发展，极大地促进了网络资源的共享，同时也导致人们需要面对的信息海量增长。因此，如何从这些信息中准确快速地找到有效信息，成为人们不得不面对的一个问题。聚类作为数据挖掘的一种重要工具，能够给出数据的分类划分，具有广泛的应用，已成为目前研究的热点。在聚类问题的分析研究过程中，往往把聚类看作成一个优化问题，并且可以用不同的优化方法来解决聚类问题。
　　形状是事物图像的基本特征之一。在计算机视觉和图像理解与解译中，把目标物体的形状作为识别特征进行识别是一种重要的方法。实际上，从图像库中对相同物体进行识别，就是一种自动聚类问题。本文将遗传算法用于图像的聚类，对所给的形状特征明显的图形图像集用遗传算法进行处理，划分出一个个不同的类，并且类别的个数由算法给出。具体的工作包含以下内容：
　　（1）Shape Context是一种用常用的形状描述方法，它利用轮廓点与其余轮廓点间相对位置信息，计算轮廓点的近邻点位置分布直方图，描述形状。用Shape Context方法表述图像的轮廓特征，再经过Programming Dynamic方法、Procrustes Analysis方法、Edit距离，计算得到图像间的相似度矩阵。本章所介绍的图像相似度计算的方法，将用于第三章和第四章中的聚类算法。
　　（2）使用遗传算法对图像进行聚类，并在交叉变异操作之后加入k近邻局部搜索算法，使得种群进化的方向向着“类内相似度小”的方向调整。以一定的概率对染色体进行变异，随机选择并改变染色体的某一基因位；以概率对染色体进行交叉，随机选择交叉位置，互换该位置之后的所有基因位，产生两条新的染色体；然后进行局部搜索，在局部范围内搜寻更优的解；采用轮盘赌的方式进行选择，产生下一代种群。通过实验对比，结果表明该算法在ARI和MS评价指标上具有优势，说明了该算法的良好性能。
　　（3）NSGA-II为经典多目标聚类算之一，算法计算开销小，收敛速度快并且有精英保留策略，将其与 Shape Context、Programming Dynamic、Procrustes Analysis及 Edit距离等结合，对图形图像进行自动聚类。NSGA-II的染色体变异和交叉同遗传算法相似，在交叉变异之后，对经过非支配排序的染色体进行选择，产生下一代种群。对测试图像集进行测试，表明多目标在图形图像自动聚类中，较第三章的算法性能有所提高。
　　本课题得到国家自然科学基金(No.60803098)、国家教育部博士点基金(No.20070701022)、省自然科学基金(2010JM8030)、中央高校基本科研基金(No.K50511020014)的资助。