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

基于有效计算最短路径的改进分水岭算法

Viacute;ctor Osma-Ruizlowast;, Juan I. Godino-Llorente, Nicolaacute;s Saacute;enz-Lechoacute;n, Pedro Goacute;mez-Vilda

Dpt. of Ingenieriacute;a de Circuitos y Sistemas, Universidad Politeacute;cnica de Madrid, Ctra. Valencia, Km. 7, 28031, Madrid, SpainReceived 5 July 2005; received in revised form 10 March 2006; accepted 27 June 2006

摘要

本文介绍了利用像素箭头对灰度数字图像进行降雨模拟计算分水岭变换的新算法。这种方法的效率是基于限制必要的相邻运算来将计算转换到外层, 以及在整个图像上执行的扫描总数。实验表明, 所提出的算法能够显著降低已知速度最快的算法的运行时间, 不涉及任何效率损失。

关键字: 分水岭;图像分割;箭头

1. 导言

分水岭变换是数字图像分割领域中最有价值的工具之一[1]。这一技术的主要优点之一在于, 结果是一组划分良好的区域, 所以如果我们认为这些区域代表搜索的对象, 我们将得到一个由一组连接的像素定义的精确的边缘检测。对于其他分割技术来说, 这是一个很大的改进, 它通过不连通的线来解决边缘检测问题, 这使得乍一看可以分辨出物体, 但在处理自动系统时却相当复杂。

流域的概念来自于地形领域, 指的是在几个盆地或集水区的景观划分。一个很好的例子是将美国划分为两个主要区域的大陆鸿沟: 一个与大西洋有关, 另一个与太平洋有关。所以, 在雨天, 所有的雨滴下降的一面的鸿沟流到一大洋, 而雨落在另一侧的分裂将流入其他海洋。很明显, 只要沿途没有陷入局部最低水位，水将到达海洋。这两个地区通常被命名为集水盆地, 每一个区域都有一个相关的最小值 (海洋)。分隔两个盆地的边界线称为分水岭线, 对应于例子中的大陆鸿沟。从这个角度来看, 我们可以将图像视为一个地形面, 其中每个像素都是位于某一高度的点, 作为其灰度级 [1–3]的函数。白色 (灰色等级255) 被采取意味最大高度和黑颜色 (灰色等级0) 极小值。其余灰度级与这些极值之间的图像相关的高度相匹配。

考虑到这一定义, 在过去几年中, 开发了两种概念上截然不同的方法来计算分水岭变换:

• 第一种方法通过淹没地形表面来提出转换。这种技术基本上是将表面逐渐浸入水容器中。以前，每个表面最小值都有一个孔。水将开始流经这些洞，首先通过海拔较低的海域，然后逐渐达到海拔较高的海域。渐渐的所有与极小值相关的集水盆地都被淹没。来自两个或两个以上不同盆地的洪水可能会汇聚在一起。在这一点上，假设建筑堤防以防止它们汇聚。一旦整个表面被浸没, 只有堤坝在水位以上, 组成分水岭线。流域或集水盆地是所有被线包围的区域。有几个实现此技术的算法 [4，5], 后来改进了[6–10] , 甚至在硬件中实现 [11]。.
• 第二种方法模拟与图像关联的曲面上的雨水。落在一个点上的水滴会沿着最陡下降的路径流动, 直到达到最小值。这个点被标记为属于与这个最小值相关的接收盆地。这个过程对表面上的所有点重复进行，因此最终每个点都将被分配到最小值，并且表面将被划分为其集水盆地。在这种方法中, 没有一点将明确属于分水岭线, 因为每一个点被标记为属于某一盆地。因此, 这些线将由分离不同盆地的像素边缘形成。此方法已在参考文献中实施[1], 并在引用中进行了改进[12–14]。还有其他研究侧重于硬件适应 [15]和并行处理 [16，17].

在此简要说明中, 我们没有区分基于地形距离的方法[18，19] 和基于本地条件 (此处定义为降雨模拟)的方法, 因为它们概念上相当相似 [17]。然而，重要的是要提到，基于地形距离的大多数方法也会产生分水线，就像那些基于浸水的方法一样。

淹没标准之后的大多数过程都面临着一个共同的问题，即大的图像区域可能构成分水岭线的一部分，而希望这些线的宽度不会超过数字图像中的最小分辨率（通常是一个像素）。在图1中的图像中可以清楚地观察到此事实 。集水盆地以浅灰色表示, 而暗灰色点则构成分水岭线。每个单元格中的数字表示相应像素的灰度级别。此外，标记为属于分水岭线的点倾向于减缓通常在分水岭变换计算之后的合并过程 [20–25]。

图1 利用Vincent和 Soille 算法获得的分水岭线和集水盆地 [6]。深灰色代表分水岭线。浅灰色代表流域盆地。数字表示像素的灰色级别。

基于降雨流模拟的技术不存在上述问题, 因为它们将所有点标记为属于一个盆地。在图 2中, 对分割图像的四个集水盆地中的每个流域使用了不同的灰色级别。粗线代表边界线, 即相当于前分水岭线, 此时呈现理想宽度。提出了一种基于该判据计算分水岭变换的新算法, 但效率更高, 运行时间比当前方法低。