遥感图像多尺度分割算法与矢量化算法的集成
第４０卷
、厂０１．４０
第６期
Ｎｏ．６
计算机工程
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ
文章编号：１０００—３４２８（２０１４）０６—０２５６—０６
文献标识码：Ａ
２０１４年６月
Ｊｕｎｅ２０１４
－图形图像处理－
中图分类号：ＴＰ７５１．１
遥感图像多尺度分割算法与矢量化算法的集成
王海，童恒建，左博新，汤文瑞
（中国地质大学（武汉）计算机学院，武汉４３００７４）
摘要：在遥感图像处理和分析软件中，图像分割，分类和矢量化是前后独立的过程：先分割，分类，再矢量化整幅图像。由于矢量化后得到的矢量文件未写入图像对象（区域、图斑）的特征信息，只能用于显示而不能用于后续操作。此外，处理复杂图像时还存在
矢量文件多边形数目与分割份类后图像区域数目不一致的问题。为此，将多尺度分割算法与矢量化算法进行一体化集成。对遥感
图像进行多尺度分割得到图像对象链表，逐个对图像对象做矢量化处理，同时把特征统计信息写入多边形属性中。集成后不仅可保证矢量多边形数目与图像对象数目完全一致，而且由于特征统计信息已作为多边形区域的属性保存在多边形中，后续的多尺度分割、区域合并、空间关系操作等均可基于矢量多边形进行。
关键词：遥感图像；基于对象的图像分析；多尺度分割；矢量化；算法集成；对象矢量化
ＩｎｔｅｇｒａｔｉｏｎｏｆＭｕｌｔｉｓｃａｌｅＳｅｇｍｅｎｔａｔｉｏｎＡｌｇｏｒｉｔｈｍａｎｄＶｅｃｔｏｒｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒＲｅｍｏｔｅＳｅｎｓｉｎｇＩｍａｇｅ
ＷＡＮＧ
Ｈａｉ，ＴＯＮＧ
Ｈｅｎｇ－ｊｉａｎ，ＺＵＯ
Ｂｏ－ｘｉｎ，ＴＡＮＧＷｂｎ－ｒｕｉ
ｖｅｃｔｏｒｉｚａｔｉｏｎ
ｏｒ
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＧｅｏｓｃｉｅｎｃｅｓ（Ｗｕｈａｎ），Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ）
［Ａｂｓｔｒａｃｔ］Ｉｎｒｅｍｏｔｅｓｅｎｓｉｎｇｉｍａｇｅｐｒｏｃｅｓｓｉｎｇａｎｄａｎａｌｙｓｉｓｓｏｆｔｗａｒｅ，ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ／ｃｌａｓｓｉｆｉｃａｔｉｏｎａｎｄ
ｓｅｐａｒａｔｅ
ａｒｅｔｗｏ
ｐｒｏｃｅｓｓｅｓ：（１）Ｓｅｇｍｅｎｔａｔｉｏｎ／ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ｃａｎ
ｏｆｔｈｅｗｈｏｌｅｉｍａｇｅ；（２）Ｖｅｃｔｏｒｉｚａｔｉｏｎｏｆｔｈｅｗｈｏｌｅｓｅｇｍｅｎｔｅｄ
ａ
ｃｌａｓｓｉｆｉｅｄｉｍａｇｅ．
Ｖｅｃｔｏｒｉｚｅｄｆｉｌｅ
ｏｎｌｙｂｅｕｓｅｄｆｏｒｄｉｓｐｌａｙｉｎｇａｎｄＣａｎｎｏｔｂｅｕｓｅｄｆｏｒ
ｎｏｔｗｒｉｔｔｅｎ
ｓｕｂｓｅｑｕｅｎｔｏｐｅｒａｔｉｏｎｂｅｃａｕｓｅｔｈｅｆｅａｔｕｒｅｉｎｆｏｒｍａｔｉｏｎｏｆｉｍａｇｅ
ａｎ
ｏｂｊｅｃｔｓ（ｒｅｇｉｏｎｓ，ｐａｒｃｅｌｓ）ｉｓｉｎｔｏｔｈｅｆｉｌｅ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅｒｅｅ】【ｉｓｔｓ
ｏｒ
ｉｎｃｏｎｓｉｓｔｅｎｔｂｅｔｗｅｅｎｔｈｅｐｏｌｙｇｏｎｎｕｍｂｅｒｉｎｖｅｃｔｏｒｆｉｌｅａｎｄ
ｉｓｃｏｍｐｌｅｘ．Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｓｅ
ｔｈｅｎｕｍｂｅｒｏｆｉｍａｇｅｏｂｊｅｃｔｓｉｎｔｈｅｓｅｇｍｅｎｔｅｄｐａｐｅｒｉｎｔｅｇｒａｔｅｓｍｕｌｔｉｓｃａｌｅｏｆｉｍａｇｅｏｂｊｅｃｔｓｂｙｔｈｅ
ｃｌａｓｓｉｆｉｅｄｉｍａｇｅｗｈｅｎｔｈｅ
ｉｍａｇｅ
ｔｗｏ
ｐｒｏｂｌｅｍｓ，ｔｈｉｓ
ｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｖｅｃｔｏｒｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｔｌｙ，ｒｅｍｏｔｅｓｅｎｓｉｎｇｉｍａｇｅｉｓｍｕｌｔｉｓｃａｌｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｓｅｃｏｎｄｌｙ，ｅａｃｈｉｍａｇｅｏｂｊｅｃｔｉｓｖｅｃｔｏｒｉｚｅｄ，ａｔｔｈｅ
ｓｅｇｍｅｎｔｅｄ
ｏｒ
ｄｉｖｉｄｅｄｉｎｔｏｔｈｅｃｏｌｌｅｃｔｉｏｎ
ｔｉｍｅｆｅａｔｕｒｅｓｔａｔｉｓｔｉｃａｌ
ｓａｎｌｅ
ｉｎｆｏｒｍａｔｉｏｎ
ｔｈｅ
ｏｆｅａｃｈ
ｉｍａｇｅｏｂｊｅｃｔｉｓｗｒｉｔｔｅｎｉｎｔｏｔｈｅｐｏｌｙｇｏｎ’Ｓａｔｔｒｉｂｕｔｅｓ．Ｂｙｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄ，ｔｈｅｐｏｌｙｇｏｎｎｕｍｂｅｒｉｎｖｅｃｔｏｒｆｉｌｅｅｑｕａｌｓ
ｃｌａｓｓｉｆｉｅｄ
ｎｕｍｂｅｒｏｆｉｍａｇｅ
ｏｂｊｅｃｔｓｉｎｔｈｅｉｍａｇｅ．Ｍｏｒｅｏｖｅｒ，ｓｕｂｓｅｑｕｅｎｔ
Ｏｉｌ
ｍｕｌｔｉｓｃａｌｅ
ｓｅｇｍｅｎｔａｔｉｏｎ，ｒｅｇｉｏｎ
ｍｅｒｇｉｎｇａｎｄｔｈｅ
ｏｐｅｒａｔｉｏｎｏｆｓｐａｔｉａｌｒｅｌａｔｉｏｎｓｈｉｐ，ｅｔｃ．ｃａｎｂｅｅｘｅｃｕｔｅｄｂａｓｅｄ
ｐｏｌｙｇｏｎｉｓ
ｔｈｅｖｅｃｔｏｒｐｏｌｙｇｏｎ，ｂｅｃａｕｓｅａｌｌｆｅａｔｕｒｅｓｔａｔｉｓｔｉｃａｌｉｎｆｏｒｍａｔｉｏｎｏｆｅａｃｈ
ｓａｖｅｄｉｎｖｅｃｔｏｒｆｉｌｅ．
［Ｋｅｙｗｏｒｄｓ］ｒｅｍｏｔｅｓｅｎｓｉｎｇｉｍａｇｅ；Ｏｂｊｅｃｔ－ｂａｓｅｄＩｍａｇｅＡｕａｌｙｓｉｓ（ＯＢＩＡ）；ｍｕｌｔｉｓｃａｌｅｏｂｊｅｃｔ
ｖｅｃｔｏｒｉｚａｔｉｏｎ
ｓｅｇｍｅｎｔａｔｉｏｎ；ｖｅｃｔｏｒｉｚａｔｉｏｎ；ａｌｇｏｒｉｔｈｍ
ｉｎｔｅｇｒａｔｉｏｎ；
ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００－３４２８．２０１４．０６．０５５
１概述
近年来，随着遥感技术和信息技术的发展，高空间分辨率遥感图像在土地覆盖、土地利用、城市规划、环境监测、目标提取等领域获得了广泛的应用。随着图像空间分辨率的提高，如ＩＫＯＮＯＳ、ＱｕｉｃｋＢｉｒｄ和ＷｏｒｌｄＶｉｅｗ．２卫星全色图像的空间分辨率分别已达到１
ｍ，０．６１
同类地物内部的空间信息更加丰富，地物的几何结构、纹理信息也更加明显，光谱差异逐渐增大，基于像元（Ｐｉｘｅｌ．
ｂａｓｅｄ）光谱统计的分类技术处理这类影像时显得粒度过小，
已经不能满足当前遥感信息分类和信息提取的要求。为了
充分利用高空间分辨率遥感影像地物的纹理、几何形状和
结构等信息，基于对象的图像分析方法（Ｏｂｊｅｃｔ．ｂａｓｅｄ
Ｉｍａｇｅ
ｍ和０．５
ｍ，
Ａｎａｌｙｓｉｓ，ＯＢＩＡ）开始兴起，突破了传统方法以像素为基本分
基金项目：国家自然科学基金资助项１；１（４１１７１３３９，４１００４０４９）；中国地质调查局基金资助项目“云南１：５万九农、阿登各、德钦县、红坡幅区域地质调查项目地质灾害遥感解译”（１２１２０１０８８０４０４）。
作者简介：王海（１９８８一），男，硕士研究生，主研方向：遥感图像分割与分类；童恒建（通迅作者），教授、博士后；左博新，副教授、博士后；汤文瑞，硕士研究生。收稿日期：２０１３—０２－２５
修回日期：２０１３－０５－２０
Ｅ－ｍａｒｌ：ｔｈｊ２６＠ｃｕｇ．ｅｄｕ．ｃｎ
第４０卷第６期王海，童恒建，左博新，等：遥感图像多尺度分割算法与矢量化算法的集成
２５７
类和处理单元的局限性，以含有更多语义信息的多个相邻、具有相同或相似的像素组成的区域为处理单元，该区域也叫基元［１］或图像对象。这类方法首先在一定尺度下通过图像分割算法提取出由光谱和纹理均质的像素组成的同质对象，再根据遥感图像分类或者目标地物提取的具体要求，检测和提取目标地物的多种特征（如光谱、形状、大小、结构、纹理、阴影、空间位置等），以达到对遥感图像进行分类或检测的最小单元，从较高层次对遥感图像进行分析，使提取结果含有更丰富的语义信息。
遥感影像分割或分类后，一般作为地理信息系统（Ｇｅｏ．
ｇｒａｐｈｉｃＩｎｆｏｒｍａｔｉｏｎ
多尺度分割算法进行影像分割时，通过抖动矩阵选择种子像元，采用自下而上的区域合并算法形成对象，而且把光谱异质性和形状异质性同时考虑，作为区域合并的准则【１２１，避免了只用影像的光谱特征造成分割对象的边界破碎的情况。２．１异质性计算
在高分辨率遥感影像中相邻的２个影像区域合并后新生成的影像区域的结构异质性，计算式：
ｆ＝Ｗ・ｈ。删＋（１一ｗ）・ｋ
（１）
其中，矗蛔。和ｈｓｐ。ｃｔｘａｌ分别为合并后新生成的影像区域的形状异质性和光谱异质性。
Ｓｙｓｔｅｍ，ＧＩＳ）的数据源，常用于地图制
图。由于影像数据不能满足ＧＩＳ中进行空间分析的要求【到；
此外，矢量数据结构具有数据表达精度高、占用内存小、工作效率高的优点，有利于空间拓扑分析及空间网络分析。因此一般要对分割或分类后的栅格数据进行矢量化。
传统的处理方法是将影像分割和矢量化作为独立的两个过程，先对遥感影像进行影像分割得到分类栅格图，再对分类栅格图进行矢量化生成矢量数据，作为数据分析的数据源。栅格矢量化作为ＧＩＳ的重要内容，目前已有多种矢量化的方法，如有向边界法【３】、基于“栅格技术”的栅格
ｋ帮ｌ蒜溉一
合并后对象的平滑度和紧致度。
，ｋｏｏ血＝
鬼岬。＝ｗｃ删・ｋ＋（１一‰。）・吃。。也
（２）
㈤
其中，ｗｃ。删为紧致度所占权重；Ｃ为波段数量；Ｗｃ为各个
波段所占权重；ｎＯｂｊｌ＋Ｏｂｊ２和Ｄ∥１＋Ｏｂｊ２分别为合并后新生成
对象（影像区域）的面积（像素总数）及对应影像光谱值的标准
差；ｎｏｂｊ。和Ｄ。Ｐ１分别为合并前相邻对象１的面积和对应影像光谱值的标准差；ｎＯｂｊ２和Ｄ垆２分别为合并前相邻对象２
的面积和对应影像光谱值的标准差；，ｚ锄。血和，ｚ。。。分别为
数据矢量化方澍４１、基于拓扑关系的矢量化方法［５】、基于游程编码的栅格数据矢量化方澍６１、散列线段聚合法［７］、计算
机图形学书籍提出的一些跟踪法惮１等。上述方法通常存在２个问题：（１）难于将分类图的各图斑属性数据写入矢量文件；（２）在拓扑关系复杂的情况下，生成的多边形数目和源分类图图斑个数不相等。
ｋ。。＝，删・－ｌＯｂｊｌ＋Ｏｂｊ２ｎＯｂｊ１＋倒２。了—一一～（ｎＯｂｎ．导＋‰：－导）（４）ｎ．了二＋‰２。产）竹Ｊ
‘切１＋锄２‘切１％ｗ２
本文采用文献［７］提出的矢量化算法一散列线段聚合
法，它相对于传统方法具有简单、高效的特点，将其与面
向对象的多尺度分割算法集成，提出多尺度分割与矢量化一体化的思想。首先对遥感影像进行多尺度分割，并将影像分割的图斑以对象链表的形式存储在内存中；再对对象链表中的对象逐一进行矢量化，在矢量化的过程中，将对象的属性，如对象多边形内的像素的光谱均值、方差、多边形的面积、周长等，保存在矢量化后的多边形中，将后续的操作如对象的合并等，转换为矢量多边形的合并，而这些矢量操作在地理信息系统软件中均已得到实现。
’ｋ２‰嗍２‘下—一一【‰１‘下兰＋‰２‘下兰，ｋ＝‰嗍：・｛ｖｖ些，．，ｖｖｊ竺＿一（‰。・半＋‰：・｛坠）
、／‰嗍：
、／‰・
、／‰ｚ
（５）
其中，ｌＤ６『１＋Ｏｈｊ２和ｂｏｂｊｌ＋∞『２分别为合并后区域的周长和该区域最小外接矩形周长；ｌｏｂｊｌ和６０６『１分别为合并前的对象１的周长和该对象最小外接矩形周长；ｌＤ牝和６０啪分别为合并前的对象２周长和该对象最小外接矩形的周长。２．２数据结构
本文方法所采用的主要数据结构如下：
ｓｔｍｃｔｓｅｇｍｅｎｔｐｉｘｅｌ
｛ｕｎｓｉｇｎｅｄｌｏｎｇｉｎｔｐｉｘｅｌ＿ｉｄ；产像素ｉｄ，可以通过此ｉｄ求出
２多尺度分割算法原理
面向对象的影像分割最终目的是为了提取影像中在形状和范围上与真实世界地物目标相近似的影像区域（影像对象）ｐ】，但是单一的尺度很难充分反映不同尺度下的地物目标与空间格局，只有在多尺度下才能充分表达和描述高空问分辨率影像中丰富的地物目标和空间语义信息【ｌ０１。分形网络演化算法（Ｆｒａｃｔａｌ
ＮｅｔＥｖｏｌｕｔｉｏｎ
像素在影像中的行列号＋／
ｓｔｒｕｃｔｓｔｒｕｃｔ
ｓｅｇｍｅｎｔＡｏｉｘｅｌ＋ｎｅｘｔ＿ｐｉｘｅｌ；ｓｅｇｍｅｎｔ
ｉｎｔｉｄ；
产下一个像素＋／）；
｛ｕｎｓｉｇｎｅｄｌｏｎｇ
ｆｌｏａｔａｒｅａ；
／＋对象ＩＤ号，作为对象的标识８／
产对象的面积，即对象所包含像素个数，对应
／＋对象的周长，用于计算对象的平滑度和／＋对象的外包矩形，ｂ＿ｂｏｘ［Ｏ］、ｂ＿ｂｏｘ［１］分
式（３）～式（５）中的ｎｏｂｊｌ，ｎｏｂｊ２，ｎＯｂｊｌ＋Ｏｂｊ２＋／
ｆｌｏａｔｐｅｒｉｍｅｔｅｒ；
Ａｐｐｒｏａｃｈ，ＦＮＥＡ）［＇Ｉ］于
紧致度，对应式（４）和式（５）中的１０ｂｉｌ，１ｏｂｊ２，ｌｏｂｊｌ＋Ｏｂｊ２＊／
ｆｌｏａｔ
２０００年首次被提出，该算法作为一种多尺度分割算法已成功应用到商业遥感软件ｅＣｏｇｎｉｔｉｏｎ中，取得了很好的分割效果。
ｂ＿ｂｏｘ［４］；
别记录左上角坐标的Ｘ，ｙｏｂ＿ｂｏｘ［２］，ｂ＿ｂｏｘ［３］分别记录外包矩形的宽和高。在异质性计算时可通过两点坐标计算对象最小外接矩形
２５８
计算机工程２０１４年６月１５Ｅｔ
的周长，对应式（４）中的ｂｏｂｊｌ，ｂｏｂｊ２，ｂｏｂｊｌ＋Ｏｂｊ２＊／
ｆｌｏａｔ
１０１０１０１００１００５０５０５０５０５０５０１５０１５０
ａｖｇ＿ｃｏｌｏｒ［ＮＵＭ＿ＢＡＮＤＳ］；／８对应光谱波段的光谱均
１０１０１０１００１００５０５０５０５０５０５０１５０１５０
值，在对象合并阶段用来计算光谱异质性・／
１０
１０
１０
１００
１００
５０
５０
５０
５０
５０
５０
１５０
１５０
ｆｌｏａｔ
ｓｔｄ＿ｃｏｌｏｒ［ＮＵＭ＿ＢＡＮＤＳ］；／乖对应光谱波段的光谱标
ｌＯＯ
１００
１００
１００
１００
２００２００２００２００２００
２００
１５０
１５０
准差，对应式（３）中的６ｃｏｂｊｌ，６ｃｏｂｊ２，６ｃｏｂｊｌ＋ｏｂｊ２＋／
ｆｌｏａｔ
ａｖｇ＿ｃｏｌｏｒｓｑｕａｒｅ［ＮＵＭ＿ＢＡＮＤＳ］；／＋对应光谱波段的
ｌＯＯ１００１００１００１００２００２００２００２００２００２００５０５０
光谱方差，用于计算对象标准差＋／
ｆｌｏａｔ
５０５０５０５０５０
５０８０８０８０
５０１８０１８０１８０
５０５０８０８０８０
５０８０８０８０
５０５０５０５０
５０５０５０５０
２００２００２００２００２００２００
５０５０５０
５０５０５０
ｃｏｌｏｒｓｕｍ［ＮＵＭ＿ＢＡＮＤＳ］；严对应光谱波段的光谱
５０５０５０
１１８０１
值之和，在计算合并后对象的方差时，用来计算均值＋／
ｉｎｔｕｓｅｄ；
ｓｔｒｕｃｔｓｔｒｕｅｔｓｔｒｕｃｔｓｔｒｕｃｔ
１１８０１
产用于标记对象在分割阶段是否被使用过・／
１
１８０
１
２００２００２００２００
ｓｅｇｍｅｎｔ＿ｐｉｘｅｌ４ｐｉｘｅｌ＿ｌｉｓｔ；
／＋对象包含的像素链表＋／
５０
５０
５０
５０
５０
５０
５０
５０
５０
２００２００２００２００
ｓｅｇｍｅｎｔ＋ｐｒｅｖｉｏｕｓ＿ｓｅｇｍｅｎｔ；产当前结点的前驱对象＋／ｓｅｇｍｅｎｔ＋ｎｅｘｔ＿ｓｅｇｍｅｎｔ；产当前结点的后继对象＋／
严当前结点的ｓｅｇｍｅｎｔ＋ｐｒｅｖｉｏｕｓ＿ｕｎｕｓｅｄ＿＿ｓｅｇｍｅｎｔ；ｓｅｇｍｅｎｔ
４ｎｅｘｔ＿ｕｎｕｓｅｄ＿ｓｅｇｍｅｎｔ；
（ａ）标识前分类图
０
０
Ｏ
３
３
５
５
５
５
５
５
６
６
前一个没有被使用的对象＋／
ｓｔｒｕｃｔ
产当前结点的下一个
００Ｏ３３５５５５５５６６
没有被使用的对象・／｝；
００Ｏ３３５５５５５５６６
２．３算法策略
一幅ＭｘＮ阵列的数字图像首先初始化为ＭｘＮ个对象（ｓｅｇｍｅｎｔ），从像素级对象开始计算，根据局部区域异质度准则计算得到某对象与相邻区域的最小异质度对象，如果最小的异质度小于所给的阈值，将相邻的对象合并为面积更大的对象，直到遍历完所有的对象，然后再从上一次的分割结果进行分割，每次分割后得到分割后图像的区域面积最小值，直到区域面积最小值大于给定的面积尺度阈值或循环次数超过设定的循环最大次数，终止合并，程序完
２０
２０
２５
２５
２５
２５
２５
２０
２０
１０
ｌＯ
６
６
２０
２０
２５
２５
２５
２５
２５
２０
２０
１０
ｌＯ
ｌＯ
１０
３
３
３
３
３
ｌＯ
１０
１０
１０
１０
ｌＯ
６
６
３
３
３
３
３
１０
１０
１０
１０
ｌＯ
１０
６
６
２０２０２０２０２０２０２０２０２０ｌＯ１０６６
２０２０２５２５２５２５２５２０２０ｌＯ１０６６
２０２０２０２０２０２０２０２０２０１０ｌＯｌＯ１０
成影像分割，此时程序输出新的Ｋ个ｓｅｇｍｅｎｔ对象，并且
以链表的形式存储在内存中。
（ｂ）标识后ＩＤ
图１分割后的区域标识过程
３矢量化算法
遥感分类图是一种栅格数据，栅格数据的每个基元都是一定大小的多边形区域，因此，栅格数据矢量化后的矢量数据只有面状信息，没有点和线【ｌ３１。对分类图的矢量化就是提取不同图斑之间的边界线，形成矢量弧段，进而生成具有拓扑关系的矢量多边形。本文用到的数据结构如下：
ＣｌａｓｓＲＰｏｌｙｇｏｎ
经过上述处理后得到Ｍ行Ⅳ列的ＭｘＮ的新数字阵列，对ＭｘＮ的新数字阵列向四周外扩一行（列），并将外扩的值赋为一１，即得到新的（？ｌ升２）×（Ⅳ＋２）的数字阵列（如图２所示），这样可以避免边界的特殊处理。在生成分割线的过程中，若２个相邻坐标点之间的Ｄ不同，则这２个坐标点之间必然存在—条分割射线，分割线有垂直（由上至下，如图３（ａ）所示）和水平（由左至右，如图３（ｂ）所示）２种情况，该射线可以延伸到射线的左右坐标点ＩＤ发生变化为止，这样就形成
／＋在生成多边形阶段用来标记是
｛ｉｎｔ否闭合＋／
ｎＬａｓｔＬｉｎｅＵｐａｄａｔｅｄ；
了分割线（如图４所示）。
生成分割线的具体算法如下：
ｖｏｉｄ
ｉｎｔｎＰｏｌｙＶａｌｕｅ；产区域像元值＋／
严用来存储弧段的端点，因为
Ｇｅ也ｄｇｅ（处理后的Ⅲ图（图２））
ｖｅｃｔｏｒ＜ｖｅｃｔｏｒ＜ｉｎｔ＞＞ａａｎＸＹ；
Ｂｅｇｉｎ
一个多边形可能是多个弧段组成，所以声明二维容器ｔ／｝；
ｗｈｉｌｅ（除第１行外，逐行扫描Ｄ图，即Ｉ＝１ＴｏＭ＋Ｉ）｛Ｗｈｉｌｅ（在ＩＤ图中的每行逐个扫描各个点，即Ｊ＝０ＴｏＮ＋１）｛Ｉｆ点与周围４个点中任意一个Ⅲ不相等且此Ⅲ不等于
一１Ｔｈｅｎ
本文首先通过扫描分类图并赋给每个区域一个唯一的标识ＩＤ（ＩＤ≥０），这样做的意义是将分类图中像元值相等却不属于同一区域的２个区域区分开，例如，图１（ａ）中像元值为５０的２个区域经过变换后转换为不同的ＩＤ，如图１（ｂ）所示。
｛如果此ＩＤ号没有声明ＲＰｏｌｙｇｏｎ对象，则先声明一个
ＲＰｏｌｙｇｏｎ对象，并将分割线存储于此对象的成员ａａｎＸＹ容器中。
第４０卷第６期王海，童恒建，左博新，等：遥感图像多尺度分割算法与矢量化算法的集成
２５９
同时将此分割线与已有的分割线进行首尾比较，如果此分割线的首端点等于已有分割点的末端点，并且２条分割线方向相同，则将两分割线合并为一条分割线并去掉中间点，只保留首尾端点。如果找不到可以合并的分割线，则独立存储于ａａｎＸＹ容器中。）））
Ｅｎｄ
靠
＼、
＼＠５Ｍ６’５））
（（８，４），（８，５））
善壶纛
Ｉ
＼（（６，５），（７，５））
Ｉ
（（７，５），（８，５））
以图４中ＩＤ为１０的区域为例，生成分割线的具体过程如图５所示。
０
１
２
３
４
５
６
７
Ｒ
９
图５分割线生成过程中的数据结构演化
—１－１
—１０
—１０
—１０
—１１
—１２
一ｌ５
一１５
一ｌ５
一１—１
具体步骤如下：
（１）当扫描至（６，５）坐标点时，发现与（５，５）、（６，４）、（６，６）坐标点的ＩＤ不相等，则将对应的３条分割线（（５，４），（５，５））、（（５，４），（６，４））、（（５，５），（６，５））依次存储于ａａｎＸＹ［Ｏ］、ａａｎＸＹ［１］
－１一ｌ－１
００
００
００
００
２２２
５２２
５２２
５２２
—１一ｌ—１
和ａａｎＸＹ［２ｌｄＯ。
００
００
００
００
（２）扫描（７，５）坐标点时，发现与（７，４）、（７，６）坐标点ＩＤ不相等，但此时生成的分割线（（６，４），（７，４））、（（６，５），（７，５））与ａａｎＸＹ［１］、ａａｎＸＹ［２］ｄ？的分割线合并为（（５，４），（７，４））、（（５，５），（７，５））。
（３）扫描（８，５）坐标点时，发现与（８，４）、（９，５）、（８，６）坐标点的Ⅲ不相等，此时生成分割线（（７，４），（８，４））、（（８，４），（８，５））、（（７，５），（８，５）），将（（７，４），（８，４））、（（７，５），（８，５））分别与（（５，４），（７，４））、（（５，５），（７，５））合并为（（５，４），（８，４））、（（５，５），（８，５））后存储于ａａｎＸＹ［１］、ａａｎＸＹ［２］中，分割线（（８，４），（８，５））则独立存
－１２１０１０１０一１
—１—１一ｌ
２０２０２０
２０２５２０
２０２５２０
２０２０２０
２２２０
２０２０２０
２０２０２０
２０２０２０
—１—１—１
一ｌ一１一ｌ一１一ｌ一１—１—１—１—１
图２ＩＤ图
口
口ｊ，主口
（ａ）垂直方向
储于ａａｎＸＹ［３］Ｏ。
获取分割线后，通过比较多条分割线的起始点和终点可以将具有相同左、右ＩＤ的线段连接成弧段。其中弧段的方向满足逆时针方向，经过处理之后一个简单多边形由一
口
（ｂ）水平方向
个封闭弧段构成，而具有“岛”的多边形由多个封闭弧段构成。生成弧段的具体算法如下：
ｖｏｉｄ
ＧｅｔＲｉｎｇ（ａａｎＸＹ）
图３分割线的２神情况
Ｂｅｇｉｎ
Ｗｈｉｌｅ（从ａａｎＸＹ［Ｉ］开始逐个搜索ａａ／ｌＸＹ中的分割线，Ｉ＝０）｛Ｗｈｉｌｅ（ａａｎＸＹ［Ｉ］００的弧段没有闭合）
｛Ｗｈｉｌｅ（从ａａｎＸＹ［Ｊ］开始逐个搜索ａａｎＸＹ中的分割线，
固
Ｊ＝Ｉ＋１）
｛Ｉｆ第Ｊ条分割线的首端点或者末端点与第１条分割线
末端点相等Ｔｈｅｎ
使第Ｊ条分割线方向与第１条方向（逆时针方向）一
致，然后将第Ｊ条分割线的末端点添加到第１条分割线中作为第１条分割线的末端点；
Ｊ讣１；）
Ｉ＿Ｉ＋１；）｝
Ｅｎｄ
以图４中ＩＤ为１０的区域为例，区域对应的分割线分别存储在ａａｎＸⅥＯ］、ａａｎＸＩ＇［１］、ａａｎＸＹ［２］、ａａｎＸＹ［３］中，生成弧段的过程如下：
（１）以ａａｎＸＹ［Ｏ］ｄＯ存储的弧段为基准分别扫描ａａｎＸＹ［１］、
图４分割线示意图
ａａｎＸＹ［２］、ａａｎＸＹ［３］，发现与ａａｎＸＹ［２］中的分割线可以连接，
计算机工程
则连接２条分割线去掉中间重复点，将结果（（５，４），（５，５），（８，５））存于ａａｎＸＴ［Ｏ］ｄＯ，并且将ａａｎＸＹ［３］ｄＯ的分割线赋予ａａｎＸＹ［２］，释放ａａｎＸｙ【３］。
（２）以ａａｎＸＹ［Ｏ］为基准扫描ａａｎＸＹ［１］、ａａｎＸＹ［２］，发现与ａａｎＸＹ［２］的分割线可以连接，但此时ａａｎＸＺ［２ｌｄＹ的分割线与ａａｎＸＴ［Ｏ］中的分割线方向相反，因此，改变ａａｎＸＹ［２】中的分割线的方向为（（８，５），（８，４）），并且与ａａｎＸＹ［ＯｌｄＯ的弧段连接为（（５，４），（５，５），（８，５），（８，４））存于ａａｎＸＴ［Ｏ］中，释放
ａａｎＸＹ［２］。
２０１４年６月１５日
交的情况；同时，在多边形的生成过程中，没有建立多边形与多边形之间的包含与被包含关系就会产生岛的问题。本文通过将多尺度分割后的区域对象链表中图像对象逐个矢量化，不会出现自相交的区域（对角区域相同），从根本上解决了多边形自相交的问题，得到矢量多边形之后，通过
比较多边形边界就很容易地建立多边形之间的包含与被包
含的拓扑关系。４．１集成原理
在执行完一次多尺度分割之后，得到一个ｓｅｇｍｅｎｔ对象
（３）以ａａｎＸＹ［Ｏ］为基准扫描发现与ａａｎＸＹ［１］分割线可以连接，但此时ａａｎＸＹ［１ｌｄＯ的分割线与ａａｎＸｙ【ＯｌｄＯ的分割线方向相反，因此，改变其方向为（（８，４），（５，４）），并且与ａａｎＸＹ［Ｏ】中的弧段连接为（（５，４），（５，５），（８，５），（８，４），（５，４））存于ａａｎＸＹ［Ｏ］中，释放ａａｎＸＹ［１】。
这样就形成了一条封闭的弧段，即多边形。形成弧段的过程如图６所示。
ａａｎＸｊｌ＇［，１］
链表，需要将分割结果进行矢量化，并且将ｓｅｇｍｅｎｔ对象的
特征属性，写入矢量文件。这样就可以在接下来的分割过程中直接对矢量数据进行操作。在矢量化过程中，如果一次性对整幅图进行直接矢量化，很难将各个对象的属性写入对应的矢量多边形中。因此，本文采取的策略是将分割后的对象区域逐个进行矢量化。具体步骤如下：
（１）获取ｓｅｇｍｅｎｔ的外接矩形坐标，计算出ｓｅｇｍｅｎｔ外包
ａａｎＸⅥＯ］
ｋ盘圈ｋ
ａａｎＸＹ［２］
ａａｎ，ＸＹ［３］
矩形的宽ｗｉｄｔｈ高ｈｅｉｇｈｔ，并根据外包矩形左上角坐标计算
出ｓｅｇｍｅｎｔ相对于图像原点的偏移量ｘ＿ｏｆｆｓｅｔ和ｙ＿ｏｆｆｓｅｔ。
（２）在内存中构建出宽度为ｗｉｄｔｈ和高度为ｈｅｉｇｈｔ的临
１
ａａｎＸⅥＯ］
一
磊靶ｍ
图６多边形的弧段生成过程中的数据结构
时影像文件，将ｓｅｇｍｅｎｔ像素链表中的像素值填充到对应像
素中（此时要将像素坐标根据ｓｅｇｍｅｎｔ的偏移量做相应的偏移）。对于不在像素链表中的像素，其值赋为无效值。
（３）对构建的临时影像做矢量化，并将组成弧段的点做偏移逆变化，矢量化完成后，如果多边形的ｎＰｏ砂Ｖａｌｕｅ值
等于无效值，则不做处理，否则写入对应的ｓｅｇｍｅｎｔ属性信
息，并且将多边形写入矢量文件。
如此反复执行上述步骤，直至ｓｅｇｍｅｎｔ链表末尾，这样整幅图就完成了矢量化。４．２实验结果对比
本文方法已被成功地开发了软件模块，通过与ＥＮＶＩ的矢量化算法比较之后，验证了多尺度分割算法与矢量化算法一体化集成之后，解决了多边形自相交及岛的问题。图８（ａ）为多尺度分割后生成的中间图像。图８（ｂ）为用ＥＮＶＩ直接对中间图像矢量化后，并用ＡｒｅＭａｐ进行填充后的矢量图，图８（ｃ）为本文方法矢量化后，并用ＡｒｅＭａｐ进行填充后的矢量图。从图８（ｃ）可以看出通过本文方法处理得到的矢量图中不存在自相交多边形，并且有效地解决了岛的问题。此外，用遥感图像进行了测试，测试中发现矢量化后的多边形的数目始终与分割后区域对象数目相等，并且可以准确地将各区域的属性信息写入对应的多边形，如图９所示。
１
—１
—１
—１
—１
—１
—１
—１
—１
—１
上述算法可以将散列的分割线有序化并形成完整的弧段，如图７所示，ＩＤ为０，１，２，５，１０，２５的为简单多边形，分别对应弧段口，ｂ，ｃ，Ｚｅ，ｇ。ＩＤ为２０的多边形是具有内岛的多边形，由弧段，和五构成。
图７多边形生成结果
４多尺度分割算法与矢量化算法的集成
在矢量化过程中遇到对角区域相同时，仅靠判断弧段左右区域属性去搜索下一弧段，就有可能出现多边形自相
巴邑７
（ａ）中间图像
Ｏ）ＥｌＷＩ方法结果（ｃ）本文方法结果
图８矢量化结果对比
第４０卷第６期王海，童恒建，左博新，等：遥感图像多尺度分割算法与矢量化算法的集成
２６１
图９多尺度分割算法和矢量化算法集成后的图像处理结果
５结束语
本文将多尺度分割算法与矢量化算法相结合，弥补了传统矢量化算法的不足。对分割后的图像区域对象逐个矢量化，使得复杂的拓扑关系简单化，确保了矢量多边形的数目与分类图图斑数目相等，而且使得区域对象的属性信息更容易写入到矢量文件中。通过本文方法得到的矢量化图形，可以直接用于影像分割或者分类。该方法不足之处在于首次分割和矢量化时耗时较多，但后续的处理可以基于矢量文件直接进行操作，不仅方便，而且速度较快。今后将研究基于矢量化后的图形（每个多边形含有图像对象的多个特征属性）的分割和分类。
参考文献
［１］
［５］沈掌泉，王人潮．基于拓扑关系原理的栅格数据转换矢量
方法的研究［Ｊ］．遥感学报，１９９９，３（１）：３８—４２．
［６】谢顺平，都金康，王腊春，等．基于游程编码的ＧＩＳ栅格数
据矢量化方法［Ｊ］．测绘学报，２００４，３３（４）：３２３—３２７．
［７】黄波，陈勇．矢量、栅格相互转换的新方法［Ｊ］．遥感技
术与应用，１９９５，１０（３）：６１－６５．
［８］孙家广．计算机图形学瞰］．北京：清华大学出版社，１９９８．
［９］蔡华杰，田金文．一种高分辩遥感影像多尺度分割新算
法［Ｊ］．武汉理工大学学报，２００９，３１（１１）：９７－１００．
［１０】谭衢霖，刘正军，沈伟．一种面向对象的遥感影像多尺度
分割方法［Ｊ］．北京交通大学学报，２００７，３１（４）：１１１－１１３．
［１１］Ｂａａｔｚ
Ｍ，Ｓｃｈｆｉｐｅ
Ａ．Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ
ｆｏｒＨｉｇｈ
Ｓｅｇｍｅｎｔａｔｉｏｎ：Ａｎ
ＯｐｔｉｍｉｚａｔｉｏｎＡｐｐｒｏａｃｈ
ＱｕａｌｉｔｙＭｕｌｔｉ－ｓｃａｌｅＩｍａｇｅ
周成虎，骆剑承．高分辨率卫星遥感影像地学计算［Ｍ］．北京：科学出版社，２００９．
Ｓｅｇｍｅｎｔａｔｉｏｎ［Ｃ］／／Ｓｔｒｏｂｌ
［Ｓ．ｎ．］，２０００：１２－２３．
Ｊ，Ｂｌａｓｃｈｋｅ
Ｔ．Ａｎｇｅｗａｎｄｔｅ
Ｇｅｏ—
ｇｒａｐｈｉｓｃｈｅＩｎｆｏｒｍａｔｉｏｎｓｖｅｒａｒｂｅｉｔｔｍｇＸＩＩ．Ｓａｌｚｂｕｒｇ，Ｇｅｒｍａｎｙ：
［２］扶卿华，倪绍祥，郭剑，等．栅格数据矢量化及相关问题
的解决方法［Ｊ］．地球信息科学，２００４，６（４）：８５－８９．
［１２】童磊．面向对象的高分辨率影像信息提取方法研究ｐ］．
长沙：中南大学，２００９．
［１３］陈仁喜，赵忠明．遥感分类栅格图的快速矢量化方法［Ｊ］．
遥感学报，２００６，１０（３）：３２６－３３０．
编辑金胡考
［３］李占才，刘春燕．点阵图形矢量化的高效方法——有向边
界法［Ｊ］．计算机应用与软件，１９９７，１４（３）：４８—５１．
［４］吴华意，龚键雅，李德仁．无边界游程编码及其矢栅直接相
互转换算法［Ｊ］．测绘学报，１９９８，２７（１）：６３—６８．
遥感图像多尺度分割算法与矢量化算法的集成
作者：作者单位：刊名：英文刊名：年，卷(期)：
王海， 童恒建， 左博新， 汤文瑞， WANG Hai， TONG Heng-jian， ZUO Bo-xin， TANG Wen-rui中国地质大学(武汉)计算机学院,武汉,430074计算机工程
Computer Engineering2014,40(6)
参考文献(13条)
1.周成虎;骆剑承 高分辨率卫星遥感影像地学计算 2009
2.扶卿华;倪绍祥;郭剑 栅格数据矢量化及相关问题的解决方法 2004(04)3.李占才;刘春燕 点阵图形矢量化的高效方法--有向边界法 1997(03)
4.吴华意;龚键雅;李德仁 无边界游程编码及其矢栅直接相互转换算法 1998(01)5.沈掌泉;王人潮 基于拓扑关系原理的栅格数据转换矢量方法的研究 1999(01)6.谢顺平;都金康;王腊春 基于游程编码的GIS栅格数据矢量化方法 2004(04)7.黄波;陈勇 矢量、栅格相互转换的新方法 1995(03)8.孙家广 计算机图形学 1998
9.蔡华杰;田金文 一种高分辩遥感影像多尺度分割新算法 2009(11)10.谭衢霖;刘正军;沈伟 一种面向对象的遥感影像多尺度分割方法 2007(04)
11.Baatz M;Sch(a)pe A Multiresolution Segmentation:An Optimization Approach for High Quality Multi-scale ImageSegmentation 2000
12.童磊 面向对象的高分辨率影像信息提取方法研究 200913.陈仁喜;赵忠明 遥感分类栅格图的快速矢量化方法 2006(03)
引用本文格式：王海.童恒建.左博新.汤文瑞.WANG Hai.TONG Heng-jian.ZUO Bo-xin.TANG Wen-rui 遥感图像多尺度分割算法与矢量化算法的集成[期刊论文]-计算机工程 2014(6)