基于四叉树与图割的遥感图像分割方法
第３６卷第８期计算机工程２０１０年４月ＶｏＬ３６Ｎｏ．８ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇＡｐｒｉｌ２０１０
?图形图像处理?文章编号ｔｌＩｌ（ＩＩ卜—３４２８（２０１０Ｊ０８＿．０２２４＿一０３文献标识码－Ａ中圈分类号ｔＴＰ３９１．４１基于四叉树与图割的遥感图像分割方法
周四龙似．粱栋Ｌ２，王慧２，孔额２
（１．安徽大学计算智能与信号处理教育部重点实验室，合肥２３００３９；
２．安徽大学电子科学与技术学院，合肥２３００３９）
摘要：针对图割算法实时性差的问题，提出一种基于四叉树与图割的遥感图像分割方法。用四叉树分割方法将遥感图像分割成多个区域，根据区域的邻接性合并相似小区域，结合区域问的灰度和位置信息，利用ＮｏｒｍａｌｉｚｅｄＣｕｔ方法在区域间进行划分，完成图像的分割。实验结果证明该方法能有效消除四叉树方法的过分割现象。
关健诃：图像分割；四叉树；区域合并；图割
ＲｅｍｏｔｅＳｅｎｓｉｎｇＩｍａｇｅＳｅｇｍｅｎｔａｔｉｏｎＡｐｐｒｏａｃｈ
ＢａｓｅｄｏｎＱｕａｒｔｅｒ－ｔｒｅｅａｎｄＧｒａｐｈＣｕｔ
ＺＨＯＵＳｉ．１０ｎｇ圯，ＬＩＡＮＧＤｏｎｇＬ２，ＷＡＮＧＨｕｉｚ，ＫＯＮＧＪｉｅ２
（１．ＥｄｕｃａｔｉｏｎＭｉｎｉｓｔｒｙＫｅｙＬａｂｏｒａｔｏｒｙｏｆＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｉｎｇ＆ＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ，ＡｎｌｍｉＵｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ２３００３９；
２．ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ２３００３９）
［Ａｂｓｔｒａｃｔ］Ａｉｍｉｎｇａｔｔｈｅｐｒｏｂｌｅｍｏｆｐｏｏｒｒｅａｌ—ｔｉｍｅａｂｉｌｉｔｙｏｆｇｒａｐｈｃｕｔ，ｔｈｉｓｐａｐｅｒｓｕｇｇｅｓｔｓａｒｅｍｏｔｅｓｅｎｓｉｎｇｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎａｐｐｒｏａｃｈｂａｓｅｄｏｎｑｕａｒｔｅｒ－ｔｒｅｅａｎｄｇｒａｐｈｃｕｔ．Ｔｈｅａｐｐｒｏａｃｈｕｓｅｓｑｕａｒｔｅｒ－ｔｒｅｅｔｏｓｅｇｍｅｎｔｔｈｅｒｅｍｏｔｅｓｅｎｓｉｎｇｉｍａｇｅｉｎｔｏａｌａｒｇｅｎｕｍｂｅｒｏｆｓｍａｌｌｐａｒｔｉｔｉｏｎｓ，ｗｉｔｈｔｈｅａｄｊａｃｅｎｃｙｏｆｅａｃｈｐａｒｔｉｔｉｏｎ，ｓｍａｌｌｅｒａｎｄｓｉｍｉｌａｒｐａｒｔｉｔｉｏｎｓａｒｅｍｅｒｇｅｄｉｎｔｏｓｏｍｅａｒｅａｓ．Ｂｙｉｎｔｅｇｒａｔｉｎｇｇｒａｙｆｅａｔｏｒｅａｎｄｓｐａｔｉａｌｌｏｃａｔｉｏｎｏｆｅａｃｈｐａｒｔｉｔｉｏｎ，ｎｏｒｍａｌｉｚｅｄｃｕｔｔｉｎｇａｐｐｒｏａｃｈｉｓｕｓｅｄｔｏｓｅｇｍｅｎｔｔｈｅｉｍａｇｅａｍｏｎｇｐａｒｔｉｔｉｏｎｆｒｏｍｇｌｏｂａｌｖｉｅｗ，ｂｙｗｈｉｃｈｔｈｅｆｉｎａｌｓｅｇｍｅｎｔｅｄｉｍａｇｅＣａｌｌｂｅｇｅｎｅｒａｔｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｏｖｅｒ－ｓｅｇｍｅｎｔａｔｉｏｎＣａｎｂｅｅｌｉｍｉｎａｔｅｄｅｆｆｅｃｔｉｖｅｌｙ．
［Ｋｅｙｗｏｒｄｓ］ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ；ｑｕａｒｔｅｒ－ｔｒｅｅ；ｒｅｇｉｏｎｍｅ唱ｅｒ；ｇｒａｐｈｃｕｔ
１概述
图像分割是从图像中分割出感兴趣的区域。随着卫星遥感技术的广泛应用，大量的遥感图像随之而生，从这些图像中分割出有用的区域极具意义。图像一旦被分割就可以进行进一步处理，如分类、识别，因此，图像分割是计算机视觉中一个极其重要而又具有挑战性的领域。
近年来基于图论的分割方法引起了人们的极大兴趣，其中最常见的方法有ＭｉｎｉｍｕｍＣｕｔ…，Ｍｉｎ．ｍａｘＣｕｔｌ２Ｊ，ＡｖｅｒａｇｅＣｕｔ口Ｊ，ＲａｔｉｏＣｕｔｌ４ｌ及ＮｏｒｍａｌｉｚｅｄＣｕｔｐＪ。这些方法都将图像的像素点作为节点构造无向赋权图，然后按照某一准则对图的顶点进行划分，进而完成对图像的分割，其中，ＮｏｒｍａｌｉｚｅｄＣｕｔ方法是一种较规范的形式，可以将求解准则转化为求解矩阵的特征矢量问题１６Ｊ。文献【７】提出了一种基于图割改进的图像分割方法。
文献【５］提出的ＮｏｒｍａｌｉｚｅｄＣｕｔ方法用于解决图像分割与聚类。该方法将图像的像素点作为节点建立无向赋权图，边上的权值代表像素点之间的关系，然后寻找一种正规化的最小割，对图中的节点进行划分，从而完成对图像的划分。由于此方法属于ＮＰ—ｈａｒｄ问题，图的节点越多，问题的求解越费时，因此对较大图像进行分割的速度异常缓慢。
文献【８】提出的四叉树分割是一种基于均匀性检测的图像分割方法。它将图像表示成一棵四叉树，树根就是原图像，除叶节点外，树中每个节点均有４个子节点，分别对应于原图像或图像块４个象限的子块。其基本思想是把一幅图像等分成４个区域，如果检查到某个子区域符合一致性标准，则—－２２４．一该子区域不再往下分割；否则，把这个区域再分割成４个子区域，这样递归地分割，直至每个子区域都符合一致性标准为止。它具有分块灵活性高、计算速度快等优点，但对噪声敏感，存在过分割等缺点。
本文综合四叉树与ＮｏｒｍａｌｉｚｅｄＣｕｔ分割算法的优点，提出一种基于四叉树与ＮｏｒｍａｌｉｚｅｄＣｕｔ的遥感图像分割方法，用四叉树分割方法产生初始分割，根据区域间的邻接性合并相似小区域，将各小区域看成图的顶点，利用ＮｏｒｍａｌｉｚｅｄＣｕｔ方法在前景的各个区域间进行分割，进而完成最终的分割。２四叉树分割方法
令Ｒ表示一幅图像，分割是将Ｒ划分成ｎ个子区域Ｒｌ，Ｒ２，…，尺。的过程，满足下列条件：
＾
（１）ＵＲ＝Ｒ。
ｉ＝１
（２）Ｒ是一个连通域，ｉ＝１，２，…，ｎ。
（３）ＲｎＲｊ＝中，对所有的ｉ和Ｊ，ｆ身。
（４）Ｐ（Ｒ）＝ＴＲＵＥ，对于ｆ－１，２，…，ｎ。
基金项目：国家自然科学基金资助项目（６０７７２１２１）；安徽省自然科学基金资助项目（０７０４１２０６５）；安徽省高等学校自然科学研究基金资助项目（２００５ＫＪ００５ＺＤ）；安徽大学。２ｌｌ”工程学术创新团队基金资助项目
作者筒介：周四龙（１９８５－－）。男，硕士研究生。主研方向：图像处理；梁栋，教授、博士生导师；王慧、孔颉，硕士研究生
收稿日期：２００９４１９—２７
Ｅ－ｍａｉｌ：６３４８２８９３５＠ｑｑ．ｃｏｍ
万方数据