英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

基于路径追踪的快速并行分水岭算法

Michal acute;Swiercz and Marcin Iwanowski

Institute of Control and Industrial Electronics,Warsaw University of Technology ul. Koszykowa 75, 00-662 Warsaw, Poland

{swierczm，iwanowski} @ ee.pw.edu.pl

摘要： 本文提出了一种分割数字灰度图像的快速并行分水岭算法。 我们展示了一种基于“无共享”原理的原始并行化技术，并将其应用于修改后的路径追踪分水岭算法，该算法允许将绝大多数计算分解为若干独立任务，这些任务可以在不同的处理节点。 这种方法消除了线程之间任何复杂同步的需要，并且转化为算法的非常高的效率和速度。 讨论样本结果，重点在于它们的正确性和执行时间。

介绍

流域转型[9]是一种用于形态图像分割的已建立的强大工具。 它在不同的科学领域中找到了许多应用。 流域概念来自地形学领域，指的是将大陆景观划分为集水盆地，集水盆地收集与其相关的土地区域的雨水。 该概念可以用于图像分割以生成对应于感兴趣对象的图像的分区。 灰度图像被认为是地形起伏，其中点的高度与相应像素的灰度成比例。

近年来，开发了两种概念上不同的技术来计算分水岭变换：第一种技术（浸入式）提出了将地形表面浸入湖中的转换方法，其中表面的所有局部最小值都有孔。 它在例如[1,6,8]。 第二种技术（通过路径追踪，也称为基于降雨的模拟）模拟雨水在与图像相关的地形表面上的行为，因此在某种意义上与浸没方法相反。 这种方法已被描述，除其他外，在[2,3,7,10].

已经有几次成功的分水岭变换并行尝试[4,5,6]. 然而，与这项任务有关的固有困难，其中最重要的是处理流程。 由于分水岭变换的性质，其中像素分析的顺序仅取决于图像本身的特征，并且使其非常困难任意地将图像分成更小的子图像以供独立处理。 这些方法通常需要处理之间复杂的同步和通信机制。

我们的方法旨在通过首先对少量选定像素执行初步标记来完全消除这个问题，这又允许将主图像划分为关于标记任务的完全独立的像素集并且将它们完全分别地从每个其他。 我们将这个架构背后的原理称为“无共享”规则。 正如将要证明的那样，我们的并行分水岭算法大大优于参考浸没算法[1] 和路径追踪算法[11]，同时保持一个干净和非常可扩展的结构。

本文分为4个部分。 第一部分是介绍性的，第二部分介绍“降雨”分割方法的原理，并描述基于这种技术的高效并行方法。 实验结果在第3节中给出和讨论，第4节包括结论和最后的评论。

2 算法

在本节中，我们提供了我们算法的详细描述。 首先，定义一些基本符号，然后描述一种修改后的路径跟踪顺序算法。 最后，我们提出了一种基于顺序分水岭变换的高效并行技术。

2.1 基本定义和符号

在详细描述我们的方法之前，我们介绍一些在本文中使用的基本定义。 我们定义以下条款：

• • 1. 当且仅当像素q与底层连接网格上的像素p相邻时，像素q被认为是像素p的邻域。 如果q的高度是p的所有邻居中最低的，并且也低于p的高度，则q是p的最低邻居。 如果有多个像素满足这个标准，则它们都被认为是p的最低邻居。
    2. 路径是一系列像素，其中该系列中的每两个连续像素都是图像中的邻居，并且该系列中的每个像素都是唯一的。 作为路径的长度，我们将了解路径中的像素数量。
    3. 高度h的平坦区域是一组像素，使得所有像素都是相同的高度h和每两个像素可以通过路径连接，路径中的所有像素也具有高度h。
    4. 区域最小值是一个没有较低高度邻域的像素，或者是一个没有较低邻域的像素组成的区域1。 这是流域分水岭的基本术语之一，并且广泛地代表了雨水流域的集水区。
    5. 高原是一个既不是区域最小也不是区域最大值的区域，也就是说，包含至少一个具有较低邻居的像素和至少一个具有较高邻居的像素。 如果平台上的像素至少有一个较低的邻居，则它被视为一个插座。
    6. 最速下降路径是从像素p_A到像素p_B的最短可能路径，其中每个连续像素是路径中先前像素的最低邻域，并且起始像素p_A不低于像素p_B。

高原上最陡峭的下降路径需要额外的解释。 这是一种特殊情况，因为高原的内部像素没有最低邻居。 在这种情况下，我们假设位于高原最陡下降路径的部分是高原入口像素与最近出口之间的最短路径，其中测地距离被假定为距离标准。

正如我们之前提到的那样，像素可能存在几个同样有效的最陡下降路径，导致不同的区域最小值。 因此，这样一个像素可以属于这些集水盆地中的每一个，并且必须选择一个标准来确定使用哪个盆地。 在这项工作中，我们使用“第一次找到的”标准，通过它继续最陡峭的下降路径，我们选择在邻域扫描期间找到的一个可行的最低邻居。 这是一个简单而快速的方法，即使在特定情况下有偏差，也会产生令人满意的整体结果。

2.2 连续分水岭算法

我们的连续分水岭算法实现了降雨方法，以便从每个像素沿着最陡的下降路径找到下游流，并将区域标签分配给区域最小值。 称为方向码的机制用于编码下降路径，其中每个访问像素在输出标签数组中接收临时标记。 此临时标记的值表示图像中像素的位置。 因此可以将路径视为一系列指向存储在输出数组中的像素的指针。

首先，图像被一个1像素宽的监护仪像素框架包围，该框架的海拔高于任何实际像素，因此为路径跟踪提供了不可跨越的边界。 这是为了提高性能并消除每个邻域扫描中边界条件的不必要检查。 路径追踪过程是针对图像中的每个像素执行的，可以总结如下（图1 说明该算法的连续步骤）：

1.执行邻域扫描以找到起始像素的最低邻居。 起始像素的最低邻居成为下降路径中的下一个步骤，并用方向代码标记。 路径中的每个新像素依次扫描其最低邻居以添加到路径中，并且该过程继续，直到遇到区域或单像素最小值。 这种情况在图1中的像素e1和e2的例子中得到证明。从e3开始，由高度为15的像素组成。进一步处理该区域取决于其类型（区域最小值或平台）。

图1.连续分水岭的阶段

2.如果达到区域最小值（无论是单个像素还是区域），则会标记新的标识（除非在之前的处理过程中已标记）。 然后，遍历导致区域最小值的下降路径，并将该最小值的标签沿着路径传播，从而结束跟踪过程。

3.如果遇到高原，它将被扫描到找到属于它的所有像素，并找到高原的出口（图1（a）中的像素e6，b6，f4）。 现在，所有发源于高原商店的下降路径都可以独立追踪到出口的标签（图1（b）和（c））。 然后使用区域生长（草原火灾）方法标记高原本身（图1 （c）），其中贴有标签的插口充当传播的种子并将其标签分发给高原上的邻居。 随着该区域的每次迭代，标签逐渐扩大，逐渐遍布整个高原。 在标记平台之后，处理返回到进入平台的像素，并且执行标签向上传播的路径（图1(d)).

所提出的算法能够通过仅扫描图像两次（加上一次用于初始化）来执行分水变换，这大大有助于它的迅捷。 此外，有些情况下，源自不同像素的下降路径会在某个点汇合。 为了避免不必要的跟踪，我们使用一种称为早期路径终止的方法，引入[10]。 无论何时在下降路径跟踪期间遇到已标记的像素，路径都不会进一步跟踪（因为它显然已经被扫描），并且我们继续进行标签传播，就像达到最小值一样。

2.3 并行分水岭变换

我们将通过一个双线程同时处理的例子来演示我们的并行分水岭变换的概念。 这个设置的选择是为了表达清晰，但是如果线程数量更高，该方法的主要原理也是有效的。 平行分水岭变换的一般步骤如下：

1.将图像分成两个不重叠的子图像，分辨率为1像素宽（如图2（a）).

2.对属于分隔线的像素执行下降路径跟踪和标记（图2( b )).

3.将图像分成两个子图像，由原始图像边缘和分隔线定义（图2 （c）和（d））。

4.使用顺序分水岭算法在独立的CPU线程中独立处理每个子图像。

5.通过快速大容量存储器拷贝将部分结果合并到整个图像的最终标签矩阵中。

在步骤1中，我们选择一个1像素宽的线将原始图像分解成两个子图像，如图2所示。与顺序方法一样，我们使用高于最高允许像素高度的守护像素周围框架（G），并确保没有路径追踪将移出图像边界。 当子图像的大小相同时，可以获得最佳效果，因此平均而言，每个处理都需要相似的时间。 还希望以这样的方式执行这种分割，即两个最终的子图像占据两个连续的存储器块。 这取决于实现以及阵列数据存储在内存中的方式（行 - 主或者行）

图2.平行流域 - 阶段

列主要）在给定的编程环境中。 在这个阶段不需要执行内存复制，因为只有包含图像的数据结构需要读取访问权限，并且所有线程都可以自由访问而不会互相干扰。

在步骤2中，属于分隔线的所有像素（我们将它们称为分离像素）被处理和标记。 分离像素排列在一个队列中，并为每个像素找到最陡的下降路径。 跟踪来自每个分离像素的最陡下降路径，并且在达到相应的区域最小值之后，该最小值的标签在下降路径上传播。 该步骤的结果是带有标记的分离线以及属于分离像素的最陡下降路径的所有相邻像素和局部最小值（图2（b））。 步骤3涉及标记图2(b)和(c)中两个子图像中的所有剩余像素。 子图像1和2与监护人和已经标记的分离像素相接，这保证了不存在需要在两个子图像上追踪的路径。 每个子图像是一个独立的标记任务，然后作为单独的线程并行执行。 最终步骤包括将每个单独的标记线程的标签阵列合并到最终的完整标签阵列中，从而结束图像的分割。 这是通过将存储部分标签数组的内存位置复制到一个连续块中，以便它们可以通过单个寻址访问并将其视为单个数据结构来完成的。 正如我们在讨论步骤1时指出的那样，选择分隔线方向以促进此过程，以便每个合并操作只涉及一个简单的内存块副本。

表1.基于沉浸式，降雨型和推荐算法的执行时间

所提出的并行方法结合了顺序处理和并行处理。 第2步是作为单线程工作负载执行的，我们的方法的核心在此阶段不存在。 然而，与图像中的像素总数相比，分离像素的数量相对较小，因此需要依次计算的工作量不显着，并且不会影响算法的整体性能，尤其是对于较大的图像。

该算法的计算复杂度近似于所报告的值[2]，但是，由于并行构造，实时消耗要小得多。 内存要求也是类似的，需要两种阵列结构 - 一种用于存储图像数据，另一种用于存储标签，临时方向代码和其他中间处理数据。 另外，平台处理需要两个队列结构。 在最坏的情况下，队列中的一个需要存储图像中的所有像素，所以为了提高执行速度，我们选择了静态分配。 作为发展的主要目标

这种方法是时间表现，我们觉得这个选择是公平的，考虑到现代计算机可用的RAM内存的大小。

3 评估和实验结果

并行算法的性能和正确性在一组测试图像上进行评估，包括自然图像，如“狒狒”，“莉娜”或“地球”（图4）进行性能基准测试，以及像经典的Acid2测试图像这样的专业图像，以便进行详细的低级别正确性评估（如图3所示 为了清晰起见，分段阴影部分）。

图3.低级测试：原始图像（左），参考分水岭[1]（中），平行分水岭（右）

图4.测试图像：狒狒（左），莉娜（中），地球（右） 剩余内容已隐藏，支付完成后下载完整资料

资料编号：[24929]，资料为PDF文档或Word文档，PDF文档可免费转换为Word