基于动态分配的分水岭图像分割并行方法

摘要

本发明涉及一种基于动态分配的分水岭图像分割并行方法，将图像平均分成k个基础子图，并将基础子图动态分配给k个线程同时处理，并让先处理完基础子图的线程分担任务较重的线程的任务；然后对基础子图进行分水岭分割，通过排序和浸没对像素点进行处理；再通过改进灰度准则对过分割的基础子图进行后处理；最后采用层叠拼接的方法对基础子图进行并行拼接。本发明的方法通过将基础子图动态分配给多个线程同时进行处理，提高了算法的效率，采用改进灰度准则，具有一定的噪声抑制作用，增强了算法的鲁棒性，最后采用层叠拼接基础子图，进一步的提高了算法效率。

说明书

技术领域

本发明涉及图像处理领域，尤其涉及基于动态分配的分水岭图像分割并行算法。

背景技术

在遥感信息计算体系中，作为高空间分辨率遥感影像信息提取与目标识别的前提和基础，图像分割方法是实现从数据到信息的对象化提取的过渡环节和关键步骤，具有十分重要的地位。图像分割就是把图像分解为一些特定的性质相似的部分(区域对象)，并用这些部分对图像进行分析和描述。图像分割的结果是图像特征提取和识别等图像理解的基础，所以对图像分割的研究也一直都是数字图像处理技术研究中的热点和焦点，至今已经提出了大量的各种类型的算法。在这些不断涌现的算法中，分水岭算法以其分割精细、便于软硬件实现的优点在近年来得到了广泛应用。从本质上讲，它是一种基于区域生长的分割方法，但它得到的是连续、闭合、但有像素宽的目标边界。分水岭分割算法有两种变换方式：沉浸分水岭变换和降水分水岭变换。兙俥

分水岭算法是一种基于拓扑理论的数学形态学得分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一个像素灰度值表示该点得海拔高度，每一个局部极小的值及其影响区域称为集盆，而集水盆的边界则形成分水岭。它可以将图像分割为互不重叠区域，得到一个像素宽度且连续的边界，其应用对象是灰度梯度图像。Vincent和Soille提出的浸没模拟分水岭算法是根据自然界中水浸没的规律，即地形处于低洼的地段先被浸没。分水岭算法主要包含了两个步骤。第一步：将图像进行处理，在将处理的图像像素灰度值的大小按照升序排列出来；第二步：对排序处的顺序进行扫描，构造出“集水盆地”，然后在不同标记的“集水盆地”的边缘构造出“防水提坝”，来对图像区域的初始化划分处理。兙

为了提高遥感图像分割处理效率，学者开始把并行计算技术引入遥感图像分割处理中，进行了诸多研究，如区域生长法图像分割的数据并行方法研究、针对流域变换算法、多区域并行增长算法、通过网格划分来实现相似度矩阵的并行计算等方法。

但目前的技术方案还存在以下不足：

1、只对原始串行算法进行了表层的静态并行化

分水岭算法比较复杂，且存在过分割问题，这需要进行分割后处理。分水岭运算过程中涉及到非常多的递归运算，且高分遥感影像数据量庞大，因此在图像分割过程中计算量很大，耗时长，所需计算资源较多，且效率不离，故在分割算法计算过程中主要对其进行并行化改造。如何进行算法的并行化改造是需要技巧的，需要进行合理的算法设计。然而现有算法仅仅进行了最简单的静态并行化改造，对算法的速度提升有限，没有充分利用计算资源，造成资源的闲置、浪费。因此，需要根据算法运行中，各个计算资源的状态，设计动态并行算法，进一步提高算法并行效率。

2、在对过分割小区域合并时没有考虑算法对脉冲噪声的抗干扰能力

现有算法在进行过分割小区域合并时，基本采用对两个区域之间像素灰度值的直接比较，用阈值进行判别。这种方式对无噪图像以及高斯分布噪声污染图像的处理有较好效果，但是对于脉冲噪声污染的图像，则会受到严重的干扰，鲁棒性较差。主要原因是脉冲噪声对像素灰度值有较大幅度的改变，使得判别值会大幅偏离。需要改进过分割小区域合并判别算法，使之具有一定的抗脉冲噪声干扰能力。

3、对算法并行化后产生的额外的缝合步骤没有进行并行化

分割并行化和其他基于像素的图像处理并行化不同，存在典型的＂缝合线＂问题。这是并行化后产生的额外步骤。然而现有算法只将次步骤串行处理。随着图像分辨率的提高、并行分块的数量增大，必然导致最后需要缝合子图的数量增大，计算量也相应提高，成为整个算法效率提升的瓶颈。为此需要设计合适的处理方法，将缝合拼接部分也并行化，深层地提高算法效率。

发明内容

针对现有技术之不足，本发明提出一种基于动态分配的分水岭图像分割并行方法，所述方法包括以下步骤：

步骤1：静态分块及分配，将图像进行初始的静态平均分块，然后平均分配给线程池的并行线程；

步骤11：根据线程数量k，将图像沿长边方向平均分成k个子图，按顺序标记为p₀,p₁,p₂,...,p_k-1，构成子图集合{p_n|0≤n≤k-1}，p_n称为基础子图；

步骤12：将k个基础子图分配给k个线程同时进行处理；

步骤13：在将基础子图分配给线程时，同步产生基础子图序映射表；

步骤2：动态分配

步骤21：当一个线程处理完分配的基础子图后，等待并查找是否有还未处理完基础子图的其他线程，如果有，则向其他线程发送分担任务请求并接受其他线程分离的任务，同时更新基础子图序映射表；

步骤22：如果一个线程还有未处理完的基础子图，同时接收到其他线程发送的分担任务请求，并且未处理完基础子图的线程的工作量大于阈值时，则向该线程分离未处理完的剩余图像；

步骤3：子图分水岭分割，对分配到每个线程的基础子图进行分水岭分割；

步骤31：排序，扫描整幅图像得到各个灰度级的概率密度分布情况，根据灰度数据分布的积累概率和像素点的灰度级来确定各个像素点在整个排序中的相对位置，将所有的像素点由低到高进行排序，将排序位置放入排序数组当中；

步骤32：浸没，像素点按照灰度级由低到高的顺序依次进行浸没处理，对相同灰度级的像素点集合做同一灰度级处理，然后扫描当前灰度级的像素点，检验是否还有未经标记的像素点，若发现有未标记的像素点，则将当前的标记值加1，直到所有的灰度层都处理完成；

步骤4：基础子图过分割后处理

步骤41：找到对图像进行过分割后的小区域的邻域区域，按照邻域区域大小，由小到大依次比较灰度均值，若差值在预设范围内，则进行区域合并；

步骤42：如果找到可以合并的邻域区域，合并后更新新区域的邻域，如果没有找到，继续下一个区域的处理；

步骤5：基础子图边界缝合

步骤51：按照基础子图序映射表的顺序，将所有基础子图进行第一轮并行任务分配，每个线程分配偶数个基础子图，若基础子图数为奇数，则留下最后一个等待一下轮合并；

步骤52：每个线程将各自分配的基础子图拼接完成后生成第一轮拼合子图，在此基础上进行第二轮并行任务分配，以此循环直到所有基础子图拼接完成。

本发明的有益效果在于：

1、本发明的技术方案将图像平均分块后分给不同的线程同时进行处理，并且，在部分线程完成其分配的子图处理后，帮助其他任务较重的线程分担任务，提高了算法的效率和计算机资源利用率，避免了资源的闲置和浪费。

2、在对过分割后的子图进行后处理时，采用改进灰度准则，提高了脉冲噪声的抗干扰能力，增强了算法的鲁棒性。

3、在对基础子图进行拼接的过程中，本发明方法也采用了并行的处理方式，采用层叠拼接的方式，进一步提高了算法的效率，缩短了图像处理的时间。

附图说明

图1是本发明的方法流程图；

图2是静态分块示意图；

图3是本发明方法中动态分配的流程图；

图4是层叠拼接示意图；和

图5是基础子图层叠拼接示意图。

具体实施方式

下面结合附图进行详细说明。

本发明的长边方向是指长方形图像较长的一边。

本发明提出的基于动态分配的分水岭图像分割并行方法，如图1所示，本发明方法包括以下步骤：

步骤1：静态分块及分配，将图像进行初始的静态平均分块，然后平均分配给线程池的并行线程。

图2为静态分块示意图。步骤11：根据线程数量k，将图像沿长边方向平均分成k个子图，按顺序标记为p₀,p₁,p₂,...,p_k-1，构成子图集合{p_n|0≤n≤k-1}，p_n称为基础子图。其中，k一般是机器CPU核数的整数倍，最简单等于核数。

步骤12：将k个基础子图分配给k个线程同时进行处理。分配时不设主线程，所有线程地位相同。现有算法中，会专门设置一个主线程，即，节点，作为最后接收子图进行拼接处理的线程，这种方式使得在最后阶段，负载不均衡，主线程成为算法瓶颈，而其他线程资源限制。因此在本发明的方法中，最后拼接时采用两两组合，层层递进的方式，而不是采用将每个基础子图发送给主线程统一处理的方式，这样可以进一步提高算法的效率，节约处理时间。

步骤13：在将基础子图分配给线程时，同步产生图序映射表。图序映射表是为了保证经过后续分配后，所有子图能够正确拼接。

步骤2：动态分配

图3是本发明动态分配流程图，尽管在步骤1中对图像进行了平均划分和线程分配，但是由于分水岭算法对每个像素点的处理并不相同，因此每个基础子图的运算时间也不相同。目前的分水岭并行分割算法均没有考虑到这一点，这样就会导致部分任务较轻的线程结束自身静态分配的任务后处于闲置状态，浪费了计算资源，也降低了运行效率。而任务较重的线程则会成为整个算法的瓶颈，算法的最终耗时依赖于最后一个运行结束的线程。为了进一步提高算法的效率，本发明采用动态分配的方法，充分利用每条线程的计算能力，尽可能做到每条线程上的负载动态均衡。

动态分配的基本思路是：当某一个线程完成分配给它的任务后，则可以向其他未完成任务的线程请求分配任务并接受另一个没有完成任务的线程分配的额外任务。

步骤21：当一个线程处理完分配的基础子图后，等待并查找是否有还未处理完基础子图的其他线程，如果有，则向其他线程发送分担任务请求并接受其他线程分离的任务，同时更新基础子图序映射表。

步骤22：如果一个线程还有未处理完的基础子图，同时接收到其他线程发送的分担任务请求，并且未处理完基础子图的线程的工作量大于阈值时，则向其他线程分离未处理完的剩余图像。具体的，将未完成的图像一分为二，一半分出去给其他线程处理，一半留下自身线程处理。

步骤3：基础子图分水岭分割，本步骤是对每个线程所分配到的基础子图做分水岭分割。

步骤31：排序，扫描整幅图像得到各个灰度级的概率密度分布情况，根据灰度数据分布的积累概率和像素点的灰度级来确定各个像素点在整个排序中的相对位置，将所有的像素点由低到高进行排序，将排序位置放入排序数组当中。

步骤32：浸没，像素点按照灰度级由低到高的顺序依次进行浸没处理，对相同灰度级的像素点集合做同一灰度级处理，然后扫描当前灰度级的像素点，检验是否还有未经标记的像素点，若发现有未标记的像素点，则将当前的标记值加1，直到所有的灰度层都处理完成。未标记的像素点就意味着一个新的极小区域。

步骤4：基础子图过分割后处理

过分割问题就是指分水岭分割后的图像中存在大量的不必要的小区域，需要通过合并小区域来改善。本步骤仍然属于基础子图处理，在每个线程中独立处理，采用改进的灰度准则。目前的灰度准则虽然正常情况下可以将灰度大的区域保留，符合人眼的感知效果，但是它易将受噪声污染的小区域保留，或者将模糊的灰度区域去掉。因此本方法中提出的改进灰度准则，对噪声具有一定的鲁棒性。

改进灰度准则的基本思路是：通过对小于阈值的小区域的邻域区域之间灰度均值的比较，来判断是否进行合并。该灰度均值为邻域区域的灰度均值。

通过灰度均值比较有两个优点，一是灰度均值可以在分水岭风格确定区域时就计算，而不必等到分割后再次遍历区域中的每个点。二是通过灰度均值有一定的抑制噪声的作用，增加算法鲁棒性。

步骤41：找到对基础子图进行过分割后的小区域的邻域区域，按照邻域区域大小，有小到大依次比较灰度均值，若差值在预设范围内，则进行区域合并。例如，有邻域区域1、邻域区域2、邻域区域3和邻域区域4，将邻域区域1和邻域区域2进行灰度均值比较，邻域区域2和邻域区域3进行灰度均值比较，邻域区域3和邻域区域4进行灰度均值比较，若相邻区域的灰度均值差值在预设范围内，则进行合并。

步骤42：如果找到可以合并的邻域区域，合并后更新新区域的邻域区域，如果没有找到，继续下一个小区域的处理；

步骤5：基础子图边界缝合

目前的算法大部分只是对并行实现简单的应用，所以在最后拼接阶段基本采用单线程/进程串行处理的方式，没有充分利用并行优势。本发明方法将串行拼接改为层叠拼接，将待拼接的基础子图进行并行分配，提高了算法效率。

图4为层叠拼接示意图，图5为基础子图层叠拼接示意图，如图4和图5所示，基础子图层叠拼接包括以下步骤：

步骤51：按照基础子图序映射表的顺序，将所有基础子图进行第一轮并行任务分配，每个线程分配偶数个基础子图，若基础子图数为奇数，则留下最后一个等待一下轮合并。

步骤52：每个线程将各自分配的基础子图拼接完成后生成第一轮拼合子图，在此基础上进行第二轮并行任务分配，以此循环直到所有基础子图拼接完成。

本发明的技术方案适用于遥感领域，同时也适用于其它领域，由于遥感领域图像精度高，像素极多，采用本发明速度提升尤其明显。

需要注意的是，上述具体实施例是示例性的，本领域技术人员可以在本发明公开内容的启发下想出各种解决方案，而这些解决方案也都属于本发明的公开范围并落入本发明的保护范围之内。本领域技术人员应该明白，本发明说明书及其附图均为说明性而并非构成对权利要求的限制。本发明的保护范围由权利要求及其等同物限定。