Parallelization of Morphological Operators Based on Graphs
Parallelization of Morphological Operators Based on Graphs
复制标题
基于图的形态算子的并行化
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Imane Youkana
中科院分区：
文献类型：
--
作者：
Imane Youkana
数学形态学是一个非常强大的框架，它提供了一套滤波和分割工具，在图像分析的应用中非常有用。数学形态学的第一个应用领域是Matheron和Serra在1964年提出的二值图像[54]。数学形态学的理论是基于底层图像空间是一个完整的网格[28]，允许考虑用数学形态学算子处理非常广泛的数据类别。另一方面，考虑到携带结构信息的数字对象，数学形态学已经在图、单纯复形和超图上发展。本论文报告
重点是图空间上的数学形态学的框架[14]。这个框架考虑了输入和输出都是图（顶点集和边集）的算子。基本算子从一种集合到另一种集合。它们可以被组合以获得作用于给定图的边子集、顶点子集和子图的算子。
主要目标是提供有效的计算和实现这些形态算子的图形。为此，我们研究了基于图的数学形态学算子。这些运算符依赖于指定基本膨胀/侵蚀的迭代次数的大小参数。因此，这些迭代运算符的相关运行时间随着大小参数的增加而增加，算法运行时间为O（λ.n），其中n是底层图的大小，λ是大小参数。在我们的工作中，我们专注于距离图，使我们能够恢复（通过阈值）所有考虑的膨胀和侵蚀，因此[14]中提出的所有算子。在第一部分中，我们提出了三个新的距离图，称为边-边，边-顶点和顶点-边距离图。此外，基于新的路径概念，它考虑了沿路径的边和沿着顶点的数目，我们提出了我们的顶点-顶点距离图。我们证明了这些距离映射导致了[14]中提出的所有算子的原始特征。在此基础上，提出了一种求解无权图中距离映射的线性-时间序列算法，从而得到了图的膨胀/腐蚀算子。事实上，图上的任何膨胀、腐蚀、打开和关闭都可以通过对这些距离图进行阈值处理来获得。因此，这些运算符可以相对于图的大小在线性时间内计算，具有单次迭代并且不依赖于该大小参数。
在第二部分中，我们研究了多核架构上的并行化策略，从而有效地计算我们提出的距离图，从而计算图上的形态算子。该策略包括迭代地建立距离图的连续水平集，并行地遍历每个水平集。事实上，为了说明我们的并行策略的时间复杂度，我们对所考虑的图和集合做了假设。在这些假设下，我们的并行算法运行在O（n/p + K log 2 p），其中n，p和K是图的大小，可用处理器的数量，以及不同的水平集的距离图，分别。在第三部分中，提供了用于实验评估的2D图像和3维网格数据集的描述。然后，我们在这些实验数据集上评估了所提出的假设的规律性。并且，我们进行了分析，通过应用所提出的顺序和并行算法的目标架构上的实现所获得的结果。该评估显示，与以前的实现相比，处理时间有了显著的改善。
Mathematical morphology is one of the most powerful frameworks which provides a set of filtering and segmenting tools that are very useful in applications to image analysis. The first field of applications of mathematical morphology was binary image by Matheron and Serra in 1964 [54]. The theory of mathematical morphology is based on that the underlying image space is a complete lattice [28] allowing to consider the processing of a very broad class of data with mathematical morphology operators. On the other hand, considering digital objects carrying structural information, mathematical morphology has been developed on graphs, simplicial complexes, and on hypergraphs. This thesis report
is focused on the framework of mathematical morphology on graphs spaces presented in [14]. This framework considers operators whose input and output are both graphs (sets of vertices as well as sets of edges). The basic operators go from one kind of sets to another one. They can be combined in order to obtain operators acting on the subset of edges, on the subset of vertices, and on the subgraphs of a given graph.
The main objective is to provide efficient computation and implementation of these morphological operators on graphs. To this end, we study the (unweighted) graph-based mathematical morphology operators. These operators depend on a size parameter that specifies the number of iterations of elementary dilations/erosions. Thus, the associated running times of these iterated operators increase with the size parameter, the algorithm running in O(λ.n) time, where n is the size of the underlying graph and λ is the size parameter. In our work, we are focused in distance maps that allow us to recover (by thresholding) all considered dilations and erosions, hence all the operators proposed in [14]. In the first part, we propose three new distance maps on graphs called edge-edge, edge-vertex, and vertex-edge distance maps. Furthermore, based on new notion of path which considers both the numbers of edges and of vertices along the path, we present our vertex-vertex distance map. We show that these distance maps lead to original characterization of all operators presented in [14]. Then, a linear-time sequential algorithms for distance maps in unweighted graphs, hence the operators of dilations/erosions on graphs is proposed. In fact, any dilation, erosion, opening and closing on graphs can be obtained with a single iteration by thresholding these distance maps. Therefore, these operators can be computed in linear time with respect to the size of the graph, with a single iteration and without any dependence to this size parameter.
In the second part, we investigate a parallelization strategy on multi-core architec-ture leading to efficiently compute our proposed distance maps, hence the morphological operators on graphs. The proposed strategy consists of building iteratively the succes-sive level-sets of the distance maps, each level set being traversed in parallel. Indeed, to state the time complexity of our parallel strategy we make assumptions about the graph and the sets under consideration. Under these assumptions, our parallel algorithms run in O(n/p + K log 2 p) where n, p, and K are the size of the graph, the number of available processors, and the number of distinct level-sets of the distance map, respectively. In the third part, a description of the 2D image and 3-dimensional meshes datasets used for experimental evaluations is provided. Then, we assess the regularity of the proposed assumptions on these experimental datasets. And, we perform an analysis of the results obtained by applying the implementations of the proposed sequential and parallel algorithms on the target architectures. This evaluation shows a significant improvement of the processing time over the previously available implementations.