一种新的基于网格编码和区域合并的SAR图像快速分割算法

张泽均水鹏朗

(西安电子科技大学雷达信号处理国家重点实验室 西安 710071)

1 引言

近几十年来，合成孔径雷达(SAR)成像系统得到广泛应用[1]。它以全天候、全天时主动成像的优点弥补了经典被动光学成像系统的不足。SAR图像分割技术是SAR图像应用和自动解译的关键技术[2]。由于SAR图像相干斑的存在，增大了SAR图像分割难度[2]。国内外众多学者提出了各种SAR图像分割算法[36]-，主要分为基于区域合并[4,6]和全局模型优化[5]两类。

基于区域合并的 SAR 图像分割算法[4,6]首先对SAR图像进行过分割；然后，构造相邻区域之间的相似性度量；最后，迭代地合并最相似的两个相邻区域，直到最相似的两个相邻区域之间的相似度不满足预设的条件为止。

基于全局模型优化的 SAR图像分割算法的重点是模型的建立及其优化求解[5]。从编码理论的角度出发，一种经典的基于模型的SAR图像分割方法是利用最短描述长度(MDL)准则建立 SAR图像的分割模型，递归地实现模型的优化求解[5]。

MDL准则是 Rissanen[7]在 1978年提出，用于估计描述数据的参数模型的参数个数。从图像编码的角度出发，Leclerc[8]首次将MDL准则应用到图像分割中。文献[9]在 MDL准则下讨论传统蛇模型中的正则化项，提出了将蛇方法、区域生长、区域合并和贝叶斯方法统一于一体的区域竞争算法。Figueiredo等人[10]用B样条曲线来表示区域的边界，利用 MDL准则估计曲线控制点的数目与位置，将医学图像分割成目标和背景两个区域。文献[5]利用多边形网格表示区域的边界，提出一种基于 MDL准则的SAR图像分割模型，通过迭代地变形多边形网格的形状、节点的位置和节点个数来实现SAR图像分割。该方法的最大优点是不需要经验地调整模型的参数。但是，它在实现模型优化的时候存在以下主要的不足：(1)每次迭代都需要全局地更新多边形网格的编码长度；(2)分割结果对初始分割敏感度高；(3)算法的时间复杂度高。

本文利用八邻域网格来表示区域的边界，建立一种新的基于MDL准则的SAR图像分割模型，迭代过程中只需要局部地更新网格的编码长度，提高了模型的计算效率。利用多方向比例边缘检测算子提取SAR图像的比例边缘强度映射(RESM)，提出一种新的抑制RESM均质区域内极小值的阈值处理方法，对阈值处理后的RESM进行分水岭变换获得SAR图像的初始过分割结果。递归合并使图像的编码长度减少最快的两个相邻区域，直到图像的编码长度不再减少为止。利用区域邻接图(RAG)和最近邻图(NNG)技术来加速递归区域合并过程。将光学图像分割中度量边缘定位精度的精确度(P)和召回率(R)指标借用来评价SAR图像分割算法的边缘定位精度。

2 基于网格编码的SAR图像分割模型

2.1 基于MDL准则的SAR图像分割模型

假设多视强度SAR图像I中的相干斑是完全发展的[2]，那么，区域Ri内的每个像素服从均值为iθ的Gamma分布：

根据式(1)与不同区域之间和区域内像素之间的统计独立性，SAR图像I的香农编码长度为

其中，N为原始图像的像素个数。Gamma模型的编码长度 ()L θ近似为[5]

2.2 区域边界的网格编码

区域边界的表示及其编码方式对 SAR图像的分割结果和效率均有影响[5]。本文使用八邻域网格表示区域的边界。

(2)分割结果中，每条公共边的起点在整个图像网格平面上的位置是随机的，因此，需要lnN位来编码每条公共边界的起始坐标。

将式(4)右边的第3项、式(5)和式(7)代入式(2)，得到本文提出的基于八邻域网格编码的 SAR图像分割模型：

模型式(7)的优化求解是一个关键问题，一般没有简单有效的方法求解之。文献[5]和文献[10]分别基于区域边界的多边形网格和B样条曲线表示提出了求解次优解的方法。但它们的时间复杂度高。本文结合多方向比例边缘检测和区域合并技术来求解分割模型式(7)的次优解。

3 基于区域合并技术的模型优化算法

本文的模型优化方法主要包括两个模块：第 1个模块利用多方向比例边缘检测算子获得 SAR图像的比例边缘强度映射(RESM)，提出一种新的抑制RESM均质区域内的极小值点的阈值处理方法，对处理后的RESM进行分水岭变换，得到SAR图像的初始过分割结果；第2个模块使用区域合并技术迭代地合并使图像的编码长度式(7)减少最快的两个相邻区域，利用区域邻接图(RAG)和最近邻图(NNG)加速区域合并过程，得到最终分割结果。

3.1 SAR图像的初始分割

在基于区域合并的图像分割中，初始分割结果的质量对区域合并的效率与性能起着关键性的作用，要求它同时满足如下两个条件：

条件1：区域个数尽量少；

条件2：不存在欠分割。

条件1保证区域合并的高效性；条件2保证初始分割结果中不能丢失真实的边缘。本文利用多方向比例边缘检测器[11]提取原始SAR图像的RESM，提出一种抑制RESM均质区域内极小值的阈值处理方法，然后，对阈值处理后的RESM进行分水岭变换得到SAR图像的初始过分割结果。

图 1显示了多方向比例边缘检测器的配置结构，它的参数配置和分别表示：检测器的长度，宽度，两个矩形之间的宽度和检测器的方向。对于某一特定方向fθ，首先计算中心像素点(x,y)两边矩形区域内像素点的均值︿1(,R x和，然后计算点在方向上的比例边缘强度映射：

图1 边缘检测滤波器配置

缘检测器的方向数。构造图像的RESM：

图2显示了3视SAR图像阈值处理后的RESM及其分水岭变换结果。为了比较本文方法的优势，在图2分别给出了文献[4]和文献[6]中的初始分割结果。很明显，本文方法获得的初始分割结果满足以上两个条件，而文献[4]和文献[6]的初始分割结果只满足第2个条件。

图2 初始分割方法比较

3.2 基于区域合并技术的模型优化算法

用RAG表示图像的区域[12]。RAG被定义为一个无向连接图，，其中，是图G的节点集合，每个结点表示分割结果中的一个区域。是边集合，如果一条边，则区域i和j相邻。在边集合E中，每条边被赋予一个权值

图3给出用RAG表示图像分割的例子，图3(a)表示一个6个区域的分割结果，图3(b)是它的RAG表示，边上的数值表示它的权值。

利用 RAG的最近邻图(NNG)特性加速区域合并过程，RAG的NNG定义为一个有向图，其中，如果，那么存在从节点i指向节点j的有向边，其权值为。当而且时，那么区域i和j之间构成一个环，图3(c)表示图3(b)的NNG。搜索RAG中的最小权值时，只需要在NNG的环上搜索即可。表1中描述了基于RAG和NNG的区域合并过程。

表1 基于RAG的区域合并算法

4 实验结果与性能评价

为了验证本文算法的有效性，分别对合成和真实SAR图像进行试验，同时与3种方法进行比较，分别是：SRG-HM[4], MDL-PGP[5]和 CHUMSIS[6]。分析了本文算法的计算复杂度。借用光学图像分割中用于度量边缘定位精度的精确度-召回率(Precision-Recall, P-R)指标[13]来度量 SAR 图像分割算法的边缘定位精度。

4.1 实验结果

在分片常数卡通图 4(a)的基础上，利用乘性噪声模型分别产生服从Gamma分布的1视和4视合成强度格式 SAR 图像(分别对应图 5(a)中从上至下)。图5(b)-5(e)分别给出了4种算法的分割结果。为了视觉效果，所有图像均用幅度格式显示。

图3 图像区域的RAG表示

图4 合成的光学图像

从图5的合成SAR图像的分割结果可以看出，在1视图像分割中，前面3种方法中均有漏检的弱边缘(如图中白色箭头所指)，而且边缘定位精度低。对于4视的合成SAR图像，CHUMSIS方法也存在漏检的边缘。MDL-PGP方法与本文方法在视觉上获得相似的结果，均优于前面两种方法。

图6给出了真实SAR图像的分割结果，图6(a1),6(a2)和6(a3)的视数分别为1视、3视和4视。视觉上，SRG-HM方法和MDL-PGP方法均存在明显的过分割现象，而且 SRG-HM 方法的边缘定位精度低。CHUMSIS方法存在明显的欠分割现象。本文方法降低了过分割和欠分割程度，而且提高了边缘定位精度。

4.2 效率分析

在表1中描述的区域合并算法中，假设初始分割所需要的时间为tin，在搜索最小权值的边时，每次权值比较的时间为tcm，更新RAG的时间为tup,RAG的平均连接度为d，最终分割结果中区域的个数为K,RAG中初始节点个数为，每次迭代区域个数减少1，算法总的运行时间ttl为

实际中，K远小于初始分割中的区域个数|V0|。因此，式(11)近似为

式(14)中右边的第3项是更新RAG和NNG所需要的时间。

表2给出了4种算法的运行时间，计算机平台为：Pentium (R) Dual-Core, 2.93 GHz CPU, 2 GB内存，MATLAB 2010b。可以看出，本文方法要比其它3种方法的高效得多。

4.3 性能评价

引入自然图像分割中度量边缘定位精度的精确度-召回率(Precision-Recall, P-R)指标[13]来度量SAR图像分割算法的边缘定位精度。在图4(a)的基础上分别独立产生30幅1视、3视和4视合成SAR图像集合。图4(b)为真实边缘。

图5 合成SAR图像分割结果，从上到下分别为1视和4视，图像尺寸为512×479

图6 真实SAR图像分割结果，3幅图像的尺寸均为401×401

表2 4种算法的运行时间比较

表3给出了4种分割算法分别取最优参数设置时，每视数的30幅图像的平均指标值。从表中可以看出，本文方法的 3个边缘定位指标均明显优于SRG-HM方法和 CHUMSIS方法；与 MDL-PGP方法相比，除了单视图像的命中率略低，本文方法的其它指标均优于它。

表3 4种方法边缘定位指标比较

5 结束语

本文建立了一种新的基于 MDL准则和八邻域网格编码的SAR图像分割模型。结合多方向比例边缘检测器和区域合并技术实现模型的快速求解。利用多方向比例边缘检测器提取SAR图像的RESM，提出一种新的阈值化处理方法来抑制RESM均质区域内部极小值，对阈值处理后的RESM进行分水岭变换，获得原始图像的初始分割结果。利用区域邻接图(RAG)和最近邻图(NNG)技术实现快速区域合并，将区域合并的时间复杂度降低了近d(d为RAG的节点的平均连接度)倍。引入精确度(P)和召回率(R)来评价分割算法的边缘定位性能。与3种常用方法相比，本文方法边缘定位精度高，算法时间复杂度低，而且降低了欠分割与过分割程度。

[1] 邓云凯, 赵凤军, 王宇. 星载SAR技术的发展趋势及应用浅析[J]. 雷达学报, 2012, 1(1): 1-10.Deng Yun-kai, Zhao Feng-jun, and Wang Yu. Brief analysis on the development and application of spaceborne SAR[J].Journal of Radars, 2012, 1(1): 1-10.

[2] Gonzalez A A, Valero S, Chanussot J, et al.. Processing multidimensional SAR and hyperspectral images with binary partition tree[J]. Proceedings of the IEEE, 2013, 101(3):723-747.

[3] 颜学颖, 焦李成, 王凌霞, 等. 一种提高SAR图像分割性能的新方法[J]. 电子与信息学报, 2011, 33(7): 1700-1705.Yan Xue-ying, Jiao Li-cheng, Wang Ling-xia, et al.. New method for improving the performance of SAR image segmentation[J]. Journal of Electronics ＆amp; Information Technology, 2011, 33(7): 1700-1705.

[4] Carvalho E A, Ushizima D M, Medeiros F N S, et al.. SAR imagery segmentation by statistical region growing and hierarchical merging[J]. Digital Signal Processing, 2009,20(5): 1365-1378.

[5] Galland F, Bertaux N, and Refregier P. Minimum description length synthetic aperture radar image segmentation[J]. IEEE Transactions on Image Processing, 2003, 12(9): 995-1006.

[6] Yu Hang, Zhang Xiang-rong, Wang Shuang, et al.. Contextbased hierarchical unequal merging for SAR image segmentation[J]. IEEE Transactions on Geoscience and Remote Sensing, 2013, 51(2): 995-1009.

[7] Rissanen J. Modeling by shortest data description[J].Automatica, 1978, 14(1): 465-471.

[8] Leclerc Y C. Constructing simple stable descriptions for image partitioning[J]. Computer Vision, 1989, 8(1): 73-102.

[9] Zhu S C and Yuille A. Region competition: unifying snakes,region growing, and Bayes/MDL for multiband image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(9): 884-900.

[10] Figueiredo M A T, Leitao J M N, and Jain A K.Unsupervised contour representation and estimation using B-splines and a minimum description length criterion[J].IEEE Transactions on Image Processing, 2000, 9(6):1075-1087.

[11] Schou J, Skriver H, Nielsen A A, et al.. CFAR edge detector for polarimetric SAR images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2003, 41(1): 20-32.

[12] Peng B, Zhang L, and Zhang D. Automatic image segmentation by dynamic region merging[J]. IEEE Transactions on Image Processing, 2011, 20(12): 3592-3605.

[13] Arbelaez P, Maire M, Fowlkes C, et al.. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5):898-916.