一种新的SAR图像目标检测像素聚类算法

宋文青 徐 玮 相 飞

(西安电子工程研究所 西安 710100)

0 引言

随着SAR系统的不断发展，其在军事和民用领域的应用越来越广泛[1-5]。SAR图像自动目标识别就是SAR图像的重要应用之一[5]。在SAR图像自动目标识别中，目标检测处理是其首要环节，目的是从SAR图像中快速获取观测场景中的疑似目标区域[6-8]。目前，最为常用且最为稳健的目标检测方法为像素级别的恒虚警率(Constant False Alarm Rate, CFAR)检测算法[6]。SAR图像经CFAR目标检测后，输出一幅二值图像，其中0表示对应像素为杂波背景，1表示对应像素为疑似目标点。在高分辨SAR图像中，目标通常由空间上多个像素点组成，因此需要进一步对二值图像中的目标像素点进行空间聚类进而才能输出目标层的检测结果[7]。

传统的目标像素聚类方法[6-8]，通常假设观测场景的局部区域内仅存在一个潜在目标，从而可以简单地将任意两个不超过预设距离的像素点(区域)进行聚类以生成目标聚类结果，其中距离范围通常设为目标在图像上的最大投影长度。然而，对于多目标场景，局部区域内仅有一个潜在目标的假设条件不再满足，如果采用相同的聚类策略就会出现相邻目标的像素聚类成一个目标的情况，进而不能准确输出目标层的检测结果。目标像素聚类可以看作是一种空间离散点聚类问题。目前，常用的聚类方法有K-means算法、层次聚类算法和基于密度的DBSCAN算法等[9-11]。K-means算法需要目标个数先验信息，而对于未知的观测场景该信息通常很难获得[9]。层次聚类算法采用自上而下或者自下而上的顺序通过不断分裂或合并聚类集合从而获得最终的聚类结果[10]。算法复杂度高，不适合大数据集样本的聚类。DBSCAN算法是一种基于密度的聚类算法[11]，其通过搜索样本集中相互密度相连的最大样本集合以实现样本的聚类。算法的聚类结果受密度参数MinPts和密度半径参数Eps影响较大。

在SAR图像目标检测应用中，感兴趣的目标通常为地面车辆目标和海洋舰船目标等。这些目标体上一般存在点散射和分布散射两种结构，在图像中分别表现为孤立散射强点和高密度集中的散射点群。进一步，目标中的分布式结构散射点，经SAR图像目标检测后，部分散射点可能会被漏检，同样呈稀疏分布状态。基于此现象，本论文拟采用一种基于DBSCAN聚类和区域合并相结合的目标像素聚类算法。DBSCAN聚类使图像中紧密分布的目标散射点首先聚成一类，区域合并进一步使这些初步生成的小区域合并成目标层聚类结果。DBSCAN初步聚类后，参与区域合并过程的区域个数大大减少，进而能够大大降低算法的计算复杂度，使其适用于SAR图像目标检测应用。不同于传统的目标像素聚类方法，该区域合并方法以区域间的距离作为区域合并顺序的判断准则，因此可以一定程度上解决多目标环境下的目标像素聚类问题。为了进一步提升算法的计算效率，本文在区域合并过程中采用一种基于区域邻接图(Region Adjacency Graph, RAG)和最近邻接图(Nearest Neighbor Graph, NNG)快速合并方法[10]。该方法利用RAG图表征区域间的连接关系，同时在NNG图中搜索待合并的最小权值边所连接的两个区域。相对于RAG图，NNG图中边的数量大大减少，进而能够降低算法的计算复杂度。

论文内容安排如下：第1节中介绍了DBSCAN算法的聚类原理；第2节介绍了基于RAG和NNG的快速区域合并算法；第3节详细介绍了本文基于DBSCAN和区域合并的聚类算法的具体处理流程；第4节中基于实测数据对本文算法进行实验验证和结果分析。

1 DBSCAN聚类算法

假设待聚类样本集为D，p为其中的一个样本，定义点p的Eps邻域为NEps(p)={q∈D|dist(p,q)

1)直接密度可达：给定样本集D中的两个样本p和q，如果q∈NEps(p)，且NEps(p)≥MinPts，则称q是从核心样本p直接密度可达的。

2)密度可达：给定样本集D中的n个样本p=p1、p2、…、q=pn，如果pi是从pi-1直接密度可达的，则称q是从样本p密度可达的。

3)密度相连：给定样本集D中三个样本p、q和o，如果p和q都是从核心样本o密度可达的，则称p和q是密度相连的。

可以看出，密度可达是直接密度可达关系的级联传递，且两者是非对称的。而密度相连是具有对称关系的。DBSCAN聚类算法就是通过寻找样本集合中的相互密度相连的最大样本集合实现聚类，算法的处理流程如表1所示。

表1 DBSCAN聚类算法处理流程

2 基于RAG和NNG的快速区域合并算法

区域合并算法将样本集中的每个样本看成图中的一个节点，样本间的连接关系看成图中的边，边的权值为两个样本的距离度量。算法通过迭代合并图中具有最小权值的边所连接的两个样本实现样本集聚类，且当最小权值超过预设阈值时合并结束。为了提高算法的计算效率，文献[10]中给出了一种基于区域邻接图RAG和最近邻接图NNG合并的快速区域合并方法。

对于集合中样本间的连接关系，可以采用无向图RAG有效表示，G=(V,E)。其中V为样本集合，E=(V,V)为样本间的关系，每条边的权值为样本间的距离度量。在RAG图中，每个节点通常具有多个节点与其连接。然而，在算法合并过程中，仅利用到每个节点的最小权值边及其所对应的节点。因此，对于每个节点，仅需要记录与其具有最小权值连接的边，从而大大减少图中最小权值边的搜索范围，以实现降低算法计算复杂度的目的。此时，集合中样本连接关系可采用最近邻图NNG有效表示，Gm=(Vm,Em)。NNG中的顶点集合与RAG相同，而连接两个节点的边(vi,vj)是一个有向边，表示在RAG中所有与vi具有边连接的节集合中vj与其具有最短距离。在NNG中，从某个节点出发最后回到该节点所连接的节点路径称之为一个闭环(Cycle)，闭环具有以下四个特点[10]：

1)每个最近邻图中至少存在一个闭环；

2)每个闭环中有且仅有两个顶点；

3)最近邻图中具有最小权值的两个顶点必是一个闭环；

4)每个节点最多仅存在一个闭环中。

从NNG中闭环的特点可以看出，在搜索最小权值边时，仅需要对NNG中的闭环集合进行操作，因此能够进一步地降低算法的计算复杂度。基于RAG和NNG的快速区域合并算法处理流程如表2所示。

表2 基于RAG和NNG的快速区域合并算法处理流程

3 本文目标像素聚类算法

前文中指出，根据SAR图像中目标检测像素在空间的分布情况，本文采用DBSCAN聚类和区域合并聚类相结合的目标像素聚类方法。算法首先采用DBSCAN聚类方法在目标局部结构层对像素进行初步聚类。然后再对这些初步聚类的区域进行区域合并进而生成目标层的聚类结果。

在DBSCAN聚类中，邻域半径Eps和最小密度MinPts是影响聚类结果的关键因素。由于该聚类过程主要目的是生成目标局部结构层的初始聚类结果，以降低参与后续区域合并的区域个数。因此参数Eps和MinPts的设定仅需要保证不同目标的任意两个像素p和q是相互非密度相连的，即Eps设定应小于相邻目标的最小间隔。同时，为了防止相邻目标之间的虚警像素成为核心样本，使不同目标的像素产生密度相连关系，参数MinPts不能设置太小，本文中设为邻域总像素个数的60%。

经DBSCAN初步聚类后，每个聚类可以看作为一个区域，作为后续的区域合并的输入。在原始DBSCAN算法中，聚类后将未聚类到任意一个核心样本内的像素归为噪声像素。而对于本文应用，这些稀疏分布的像素点可能同样为目标像素点。因此，这些像素点同样作为单像素区域参与到后续的区域合并过程中。

在区域合并算法中，节点间的距离度量是影响算法聚类结果的关键因素。本文采用一种最远距离约束最近距离的距离度量方法。对于两个像素聚类集合R1和R2，其最近距离定义为

(1)

最远距离定义为

(2)

则最远距离约束的最近距离的定义为

(3)

其中，S为目标在图像中的最大尺寸。采用公式(3)的距离度量方法其目的是，在区域合并过程中，一方面需要考虑区域间的最近距离，根据该距离权值确定区域合并的顺序；另一方面还需考虑区域间的最远距离，两个区域合并后的区域尺寸大小应限定在目标尺寸范围内。

由前文可以看出，当两个像素p和q间的距离dist(p,q)大于S时，两者所在区域不会合并到一个区域内，因此我们在计算当前像素与其他像素的距离时仅需计算其2×S+1邻域内像素的距离，并将与其他像素的距离置为无穷大。这样以来，在构建RAG图时，仅对当前区域与其内部所有像素的2×S+1邻域内的像素所在区域建立连接关系。两个区域间的最近距离、最远距离和最远距离约束的最近距离可分别由式(1)、式(2)和式(3)计算得出。

(4)

综上所述，本文目标检测像素聚类处理流程如表3所示。

表3 本文目标检测像素聚类处理

4 实验结果与分析

本节中，采用实测SAR图像的二值检测图对本文聚类算法进行对比分析，其中对比方法采用传统的聚类方法[7]。实验中采用的SAR图像数据，其距离和方位分辨率为0.1m。原始SAR图像，其二值检测结果如图1所示。

图1(a)为观测场景原始SAR图像，场景中存在一个多目标区域，其分布在场景的右侧(图中虚线框区域)。图1(b)观测场景像素级的二值检测结果示意图，0表示背景像素，1表示疑似目标像素。

实验中，考虑到相邻目标间距(约0.5m=0.1m×5)和目标尺寸大小(约6m=0.1m×60)，本文方法输入参数邻域半径Eps、最小密度MinPts和目标最大尺寸分别设为5、15(⎣5×5×60%」=15)和60；传统方法目标最大尺寸参数设为60。图2中给出了传统方法和本文方法的实验结果目标像素聚类结果。图2(a)和图2(b)为整幅图像的聚类结果，图2(c)和图2(d)分别为图2(a)和图2(b)中多目标区域的聚类结果。图2中，每一个方框代表一个聚类区域。

从场景原始SAR图像可以看出，在多目标区域，相邻目标的间距要小于目标的尺寸。传统聚类方法，仅通过判断像素(区域)之间距离来决定该目标是否聚类到该区域，而对像素(区域)聚类的顺序没有要求，因此很容易将相邻目标的像素聚成一个目标，形成虚警目标的现象。而本文算法采用区域合并的策略进行像素聚类，并根据像素与像素、区域与区域之间的距离来判断合并顺序，进而能够有效地解决该多目标场景目标像素聚类问题。从图2实验结果也可以看出，传统方法聚类结果中出现了多处相邻目标被聚类成一个目标的情况，而本文方法输出的每个聚类区域仅包含一个目标。

图1 实测SAR图像及其二值检测图

图2 传统方法和本文方法目标聚类结果对比

5 结束语

针对SAR图像目标检测中的多目标区域目标像素聚类问题，文中提出一种基于最远距离约束的最近距离区域合并算法。算法首先采用DBSCAN方法对目标像素进行聚类，生成目标局部结构层的初步聚类结果；然后利用区域合并算法对这些初步聚类区域进行合并，进而给出目标层的目标像素聚类结果。同时，采用RAG和NNG表征聚类区域间的连接关系，对区域合并过程进行加速处理。实验结果表明，相较于传统聚类算法，本文算法能够将同一目标的像素聚成一个区域，将目标与其相邻目标有效地隔离开来。