海量的自然场景图像需要被快速检索、分析,这要求能够快速准确的对这些图像进行自动图像分割。由于自然场景图像具有光照不确定、背景复杂等特点,使得自然场景图像的分割成为图像分割领域的难点和热点。论文以自然场景图像为研究对象,对基于图论和聚类的分割方法进行了深入的研究,并利用分割好的区域进行分类、检索等实验,取得了如下成果:(1)针对现有的基于图论的分割方法执行速度慢,对突变边缘敏感及分割纹理图像效果不好的问题,本文提出了一种新的基于图论的颜色-纹理区域分割方法。该方法采用分块的颜色和纹理特征,同时将邻域相关性引入到块间权重中,最后利用最小生成树缩减的方法进行图像分割。主客观的实验表明新算法对于复杂的自然图像分割更准确,同时分割速度较N-Cut方法大幅提高。(2)为了解决现有聚类分割算法需要预先指定分类数、初始分类中心等问题,本文提出了一种自适应AP聚类图像分割算法。该方法根据图像的整体特征自动计算偏向参数,避免了传统聚类分割算法需预先指定初始值问题,对复杂的自然图像分割时,分割精度较基于K均值聚类和模糊C均值聚类的分割算法有了较大提高。(3)为了验证本文提出的自适应AP聚类算法在基于区域图像检索系统中的实际应用效果,提高基于区域图像检索的区域匹配准确率,论文提出了一种加权的区域匹配方法。实验结果表明,由于区域匹配过程增加了重要区域的权重,减少了次要区域权重,显著改善了基于区域图像检索系统的检索准确率。(4)聚类分割算法对于空间离散的区域分割效果好,基于图论分割方法对于连续平滑的区域更有优势。论文利用两类方法的优点,提出一种新的结合图论与聚类的自然场景图像分割算法。图像分割实验表明,该方法有效的利用了两类方法的优点,弥补了各自的缺点,提高了自然图像分割的鲁棒性。