0 引言

在世界多元化发展的背景下, 互联网技术在各个方面都为人们的生活带来了便利。图形图像作为人类与计算机交互最为直观、便捷的方式, 其相应的处理以及识别分析能力直接会影响到人们的感官体验, 而图像分割作为连接图像处理与图像识别、图像分析的桥梁, 也会为接下来的后续使用带来极大的性能提升; 同时, 图像本身的来源以及背景也随着成像技术的进步, 逐渐朝着多元化的方向发展, 大尺寸、高分辨率的图像本身蕴含着多维度的信息, 例如生物医学图像^[1]、地理遥感图像^[2]等, 如何在准确分割的同时保持较低的消耗时间成为时下研究的热点。

像素作为图像分割的基本单位, 是图像灰度及其基本原色素的编码, 在当今的大数据时代背景下, 大尺度、高分辨率的图像如果仍是以像素作为分割基准点, 执行起来就会非常耗时。超像素在图像分割中并没有十分明确的定义, 在不同的环境背景下可以适应性地变化, 大致可以理解为将某些具有相邻位置、相近颜色、相似亮度或者相似纹理特征的像素聚合到一起形成的一小块区域^[3]。

在超像素提出的初期, 从算法核心的立足点的角度出发可以大致可分为两个原型：一是基于图论的方法, 二是基于梯度下降的算法。比较有特点的基于图论的方法有：2000年Shi等^[4]提出的标准分割(Normalized cut, Ncut)方法、2004年Felzenswalb等^[5]提出的graph-based方法、2008年Moore等^[6]提出的超像素格方法、2010年Veksler等^[7]提出的GCa10 and GCb10算法、2011年Liu等^[8]提出的基于熵率的方法、2011年Zhang等^[9]提出的基于伪布尔优化的超像素分割算法、2012年Bergh等^[10]提出的基于种子点的算法、2013年王春瑶等^[11]提出的基于自适应结构块的超像素算法等。这些算法都是根据原始图像的边界信息或者纹理特征来进行特征标识, 利用相应的类似最小生成树等的算法原型来进行全局最优化代价函数的判定进而对图像进行分割。而在基于梯度下降的算法中比较有特点的有：1991年被Vincent等^[12]提出并一直优化至今的分水岭算法、2002年Comaniciu等^[13]提出的Meanshift算法、2008年Vedaldi等^[14]提出的快速漂移算法、2009年Levinshtein等^[15]提出的水平集膨胀算法以及2010年Achanta等^[16]提出的一直被用作比较的简单线性迭代聚类(Simple Linear Iterative Clustering, SLIC)算法等, 这些算法都是基于聚类的模型, 利用初始化的种子中心, 运用相应的优化判别方式来确定聚集的判定, 最后形成超像素的像素集合。

作为大数据时代的衍生物, Hadoop平台在处理海量数据方面有着十分有效的作用。追溯到最初, 谷歌的三大论文Bigtables^[17]、谷歌文件系统(Googel Fie System, GFS)^[18]、MapReduce^[19]带来了云计算的变革, Hadoop就是在此基础上用来对文本数据进行存储和分析。Hadoop的原型是Apache下的Java开源项目Nutch^[20]。全球的各大IT公司纷纷为了在云计算行业上占有一席之地而改革创新, 而良好的计算模式和运行框架的诞生也为包括大分辨率图像在内的海量数据集的处理带来了新的可能。因此, 如何利用好其拓展性来更有效地解决更多的实际问题将会带来更快的技术更新。

在当前的大数据环境下, 将图像处理与分布式相结合能达到更令人满意的结果。在研究初期, 学者们利用了MapReduce其中的一部分或者仅仅完成了对图像的简单处理, 例如图像的灰度处理、特征值提取等, 2011年南京邮电大学朱秀昌等^[21]仅利用了Map的过程完成了图像的灰度化处理。之后的研究中, 技术逐渐走向完整化并有了相应的实际应用：2011年美国空间技术研究院的Kocakulak等^[22]利用Hadoop平台完成了导弹发射轨迹图像的处理；2013年北京邮电大学的杨丛聿^[23]利用Map提取特征值并在Reduce中完成相似度分析, 完成图像的匹配; 同年Zhang等^[24]利用聚类的算法并部署到Hadoop平台上, 完成了大量社交图像的聚类处理；2014年Szul等^[25]利用MapReduce模型并结合Hadoop中的另一个开源库Scalding完成了图像拼接; 同年的Lakshmanan等^[26]利用特征抽取完成对于高分辨率3D雷达图像的拼接。

本文将针对Hadoop平台的特性, 为了减少初始任务分配时间的损耗, 设计了针对超像素分块的分片算法；同时在Map任务生成超像素的过程中, 加入距离和梯度的适应性限制, 生成规则的超像素块；并设计了Reduce任务中的区域合并, 充分利用了分布式平台的MapReduce的特性。最后实验中分别选取了大小两种尺寸的图像对算法的适用性进行测试, 总体的并行化效果具有实用价值。

1 基于多图像块的分片算法 1.1 Hadoop中分片的相关知识

MapReduce是Hadoop平台的核心计算模型, 集群中由一个负责调度的主节点和多个执行任务的从节点, 集群中的每一个从节点机器既可能被分配到Map任务, 也可能被分配到Reduce任务。

对于Hadoop平台来说, 预处理的数据在Hadoop分布式文件系统(Hadoop Distributed File System, HDFS)上分块(block)存储, 而对于Map的输入则是将数据块进行分片(split), 每一个分片被分配给一个Map节点, 而一个Map节点可能会有多个分片的输入, 其中这个分片的大小就是上文提到的任务, 也就是Map处理数据的最小单位。

如图 1所示, HDFS中的每一个分块对应着一个分片, 而分片是分配给Map的任务单位, 这种现象是分块与分片之间的耦合产生的, 对于块的设定, 经过学者们的研究, 可以类比GFS中的思想, 在HDFS中, 较大的block会一定程度上提高集群的效率, 根据经验, 一般会设为64 MB, 一般是由参数dfs.block.size来进行确定, 在HDFS的hdfs-site.xml中进行配置。

1.2 基于双重重叠切分的输入

考虑到Hadoop的处理流程, 在任务分块时, 需要对原始输入的图像进行切割。为了使得分割后不丢失切割线部分的信息, 采用图 2的双重重叠方式进行分块。

图 2中灰色部分为重叠区域, 图中只是分割的一部分, 并不代表整个图像, 表示如下：

1) 首先读入待处理图像, 分析相应的分辨率n*m, 假设图像的高度为h, 宽度为w。

2) 对于分割后的块, 按照串行的顺序进行编号, 从0到N-1, 假设横向的片数为WP, 纵向的片数为HP, 每一片的宽度为w_i, 高度为h_i, 重叠的权值为σ, 即横向的重叠宽度为σw_i, 纵向的重叠高度为σh_i, 假设所有的划分都完整, 即块大小都相等, 则可以得到如下关系：

$ \begin{gathered} WP = \left\{ {\left( {0,{w_0}} \right),\left( {\left( {1 - {\sigma }} \right){w_1},\left( {2 - {\sigma }} \right){w_1}} \right)} \right., \ldots , \hfill \\ \left. {\;\;\;\;\;\;\;\left( {\left( {{\text{i}} - {\sigma }} \right){w_i},\left( {{\text{i}} - {\sigma + 1}} \right){w_i}} \right)} \right\};i \geqslant 0 \hfill \\ \end{gathered} $

(1)

$ \begin{gathered} HP = \left\{ {\left( {0,{h_0}} \right),\left( {\left( {1 - {\sigma }} \right){h_1},\left( {2 - {\sigma }} \right){h_1}} \right),} \right. \ldots , \hfill \\ \left. {\;\;\;\;\;\;\;\left( {\left( {{\text{i}} - {\sigma }} \right){h_i},\left( {{\text{i}} - {\sigma + 1}} \right){h_i}} \right)} \right\};i \geqslant 0 \hfill \\ \end{gathered} $

(2)

1.3 基于动态最优的分片策略

对于分片算法的设计应当考虑两方面情况：首先, 对于作业数据量较小的情况, 在分块设置较小的前提下, 应当尽可能多地将数据划分成更多小的片段, 使得平台的负载更均衡；其次, 对于作业数据量较大的情况, 降低每一个Map节点处理时候的时间损耗, 同时也会给节点间的通信减轻负担。

本文算法根据静态平均和动态最优两个方式计算出相应的分片策略：

1) 静态平均分片。

静态平均算法在能够完整分配到Map节点的情况下满足尽量多的任务分配, 同时对于剩余的数据作均值化处理, 需要注意的是大小为s_m的块只有一个。

首先s_block仍为HDFS块的大小, S为输入数据的总数据量大小, 根据上一节的切分算法, 对于可以完成切分的部分, 大小是均匀的并设其为s_a, 令s_block的大小等于一个切分块的大小, 同时, 不完整的部分右侧的设为s_h, 下部的设为s_w, 右下角的设为s_m, 假设大小为s_h的块的个数为h, 大小为s_w的块的个数为w, 根据图形的规律作以下的约定：

$ N = h*w $

(3)

$ {N_a} = \left\lfloor {N/{n_d}} \right\rfloor + \left\lfloor {h/{n_d}} \right\rfloor + \left\lfloor {w/{n_d}} \right\rfloor $

(4)

$ {s_t} = (N\% {n_d}{\text{*}}{s_a}) + \left( {h\% {n_d}*{s_h}} \right) + \left( {w\% {n_d}{\text{*}}{s_w}} \right) + {s_m} $

(5)

$ {N_{ss}} = {N_a} + \left\lceil {{s_t}/{n_d}} \right\rceil $

(6)

$ {S_{ss}} = \left\lceil {\left( {{N_{ss}}*\overline S } \right)/{s_{{\rm{block}}}}} \right\rceil *{s_{{\rm{block}}}} $

(7)

其中：n_d表示DataNode节点的个数；N_a表示可以完整分配状态下每个节点分配的片数, 表示所有块的平均大小；s_t作为中间过程变量, 表示不能整除下剩余的数据量的大小；N_ss即为静态状态下每个Map节点可以完成总片数；S_ss为静态平均分片(Static Split)下的分片大小。

2) 动态最优分片。

动态最优的过程就是在遍历输入数据块时, 动态调整计算出分片的大小, 其他出现的名字和上述相关的参数都一致。

$ {N_c} = \mathop \sum \limits_{i = 1}^n \left\lfloor {{s_i}/{s_a} + \alpha } \right\rfloor $

(8)

$ {N_{sd}} = \left\lfloor {\beta + {N_c}/{n_d}} \right\rfloor $

(9)

$ {N_{{\text{total}}}} = \left\{ {i|n = \min \left( {\left\lceil {\left( {{s_a}*i} \right)/{s_{{\text{block}}}}} \right\rceil /i} \right),i = 1,2...,{N_{sd}}} \right\} $

(10)

$ {S_{sd}} = {N_{{\text{total}}}}*{s_{{\text{block}}}} $

(11)

上述α和β分别是动态适应的参数, 式(8)求得的N_c表示在输入的数据块中, 大小大于块大小(1-α)的块的数量, 即如果α为0.5, 则N_c表示数据块大小大于(1-0.5)*s_a的数量, 即总共的数据大约相当于等量的N_c块大小为s_a的块, N_sd对N_c分配到相应Map任务上的个数作一个动态调整, 一般状态下β会大于0.5, 即更倾向于扩大片的大小来容纳更多的HDFS块, 式(10)是动态过程的关键步骤, 此时对于每一个可能的分片容量, 根据其具有的比例动态调整最后的大小。举个例子, 假如N_ss为10, 每个Map的任务为10个, 此时s_a的大小为5 MB, s_block的大小为2 MB, 即其比例为2.5, 为了满足同一个图像分块都在同一个Map任务节点, 则当i为1时, 一个片的大小应为3个分块, 即向上取整, 此时的n值为3, 但这并不是最好的结果, 通过式(10)的动态过程, 当i为2时, 2个s_a 10 M, 相当于5个分块, 此时的n值为2.5, 这样逐步计算就能确定最终最合适的分片大小对应的分块数, 最后S_sd为动态最优分片下(Dynamic Split)的分片大小。

由于上述两种算法的基础都是s_a要大于s_block, 因此综合上述两种分片的策略, 可以得出最终在实验中使用到的分片大小为：

$ {s_{split}} = {\text{max}}\left( {{s_{{\text{block}}}},{\text{min}}\left( {{{\text{S}}_{ss}},{S_{ds}}} \right)} \right) $

(12)

对于静态平均和动态最优两种策略中的S_ss和S_ds, 如果S_ss>S_ds, 则表示在满足本节最初的设计基础的前提下, 动态情况下可以分得更精细, 减少Map节点的数据处理时间, 此时选择S_ds来作为最终的分片大小；再者, 如果S_ss≤S_ds, 则表示动态情况下为了保持参数的最优化, 使分片更大, 平均的分片已经可以完成任务, 这时就应该选取S_ss来作为最终的分片大小。

综上, 在静态平均和动态最优两种策略中选择片大小较小的来作为最终的分片大小, 同时, 考虑到如果最初的块大小s_block没有设置成与s_a等大, 对于所有的输入数据块都小于block的大小的情况, 上述算法的结果也会小于s_block, 这时为了保证通信的高效率, 用s_block表示分片的大小。

2 带有Map约束的分水岭算法 2.1 分水岭算法的相关知识

图像分割中的分水岭算法是对数学中形态学的应用。在早期的二值黑白图像的处理中, 由Digabel等将分水岭的相关理论知识应用到其中, 随后, 大量的学者开始在各个方面对其进行完善, 将平面的图像抽象成立体的地形图, 其中像素点的灰度值作为其海拔高度。比较经典的方式是1991年由Vincent等提出的浸没算法, 将分水岭算法很好地分成了两个过程：第一个过程是对图像的灰度系数进行排序, 将每一个等级内的灰度值进行归类划分；第二个过程是用抽象的等高线方式来进行水平的切割, 从每个最低点开始灌水, 直到完成分割。

分水岭算法表示在每两个相邻的最低点灌水后, 会将汇聚的地方筑起堤坝, 也就是作为后续处理的分割线, 这样做的结果就是会产生大量的过分割, 消除过分割一直是该算法不断优化的方向。

2.2 Map任务块内的超像算法

为了满足Map任务的边界限制同时得到规整的超像素块, 本文在浸水过程加入限制, 使得每个种子点的区域不会蔓延到整个图像块中, 建立一个梯度下降的比例参数σ, 设定其延伸方向的梯度下降为最大梯度值grad_max与当前种子点梯度值grad_i差值的σ倍, 再将其与距离相结合，有：

$ d(i) = {d_{\sigma (gra{d_{\max }} - gra{d_i})}} + \lambda d $

(13)

式中：d表示期望的超像素个数分配到每一个Map任务中对应的区域平均长度；d(i)表示该种子应搜索的最大距离, 可以根据所需的超像素的数目求得；λ的取值应小于0.5, 表示在过程中, 梯度的约束力大于距离的约束力。

假设预处理图像的最小灰度值为g_min, 最大灰度值为g_max。对于浸水操作, 首先从g_min开始, 将所有灰度值为g_min的点记为G_i(i=1, 2, …, n), 即总共有n个像素点的灰度值为g_min, 在以其中每一个点进行浸水的过程中, 采用八邻域的判断方式, 用N_i表示每一个i对应像素点的邻域, 设区域合并后的积水盆为CB, 则根据合并的规定：

$ C{B_T}\left( {{N_i}} \right) = \left\{ {p\left| {p \in {N_i},} \right|f\left( p \right) - f\left( {{N_i}} \right)| \leqslant T} \right\} $

(14)

假设g_min中合并后的区域内种子点的个数为N, 则所有灰度值为g_min的点的积水盆为：

$ C{B_T}\left( {{g_{{\text{min}}}}} \right) = \bigcup\limits_{i = 1}^N {C{B_T}\left( {{N_i}} \right)} $

(15)

从g_min到g_max逐步循环, 得到所有的积水盆, 最后将其边缘作为分割线即可完成最终的分割。

2.3 算法的并行化设计

在上面的算法中, 主要对输入和后续的合并处理进行了相应的改进, 主要的流程如下：

1) 读入图像, 按照重叠切割的方式进行切分, 并计算出相应的分片大小。

2) 在Map中对于每一个超像素块中的图像按照本文算法来进行分割。

3) 在Reduce中对于所有的结果进行相应的合并。

4) 输出最终的分割结果。

最终策略达到的效果具体如图 3所示。

3 基于Reduce的区域合并

由于本文是基于并行的超像素原理对图像进行分割, 故所涉及到的区域合并分为两个部分：第一部分是在每个超像素块内, 对分水岭算法的过分割的合并；第二部分是对所有超像素块边界的合并。

1) 块内区域合并。

本阶段旨在对每个Map的输出块内的区域进行合并, 算法运行在Map节点。在合并的过程中采用颜色直方图的相似度来进行判断, 基于不同的颜色空间会有不同的直方图处理方法, 由于HSV(Hue-Saturation-Value)可以很好地表示人们主观对颜色的辨识和判断, 因此本文采用HSV颜色空间进行处理。

对于合并区域图像中两个像素点p₁、p₂, 用HSV各个数值来构成相应的三元向量, 用三维的余弦值的关系来表示两个像素点的相似度, 为了方便表示, 用x₁、x₂、x₃分别表示对应的h、s、v参数, 则余弦值可以表示为：

$ \cos \left( \theta \right) = \frac{{\sum\limits_{i = 1}^3 {\left( {{x_i}*{y_i}} \right)} }}{{\sqrt {\sum\limits_{i = 1}^3 {{{\left( {{x_i}} \right)}^2}} } *\sqrt {\sum\limits_{i = 1}^3 {{{\left( {{y_i}} \right)}^2}} } }} $

(16)

2) 块间区域合并。

在上文的论述中了解到MapReduce的过程中, 所有的输入输出都是以键值对的形式进行的, 因此, 为了更有效地利用Hadoop平台的资源, 需要在Shuffle的过程对Map的输出作相应的排序和整理。

Shuffle处于MapReduce的中间过程, 对于有效的Reduce合并起着至关重要的作用。在本文中, 对于Map的输出〈K, V〉中, K是中间过程的地址, 如果V仅代表着一个具体的超像素块, 因为在Map的输入分块中存在着很多的重叠部分, 那么在合并的过程中就会涉及到很多节点之间的通信, 如何将邻近的超像素块映射到相同的节点上是算法设计的主要目的。

本文从滤波的过程中得到启发, 可以选取如图 4两种方式进行合并。

对于k-近邻的合并方式, 需要用到横向和纵向两个方向, 假设N=m*n, 其中m表示行数, n表示列数, 将横纵两个方向交叉进行, 假设以一个块的任务量为基准, 则循环初始的任务被分为N/k个, 每一个的任务量为k, 迭代到第二次处理需要的任务量约为2k, 以后每一次迭代任务量逐渐增加, 最后的总任务量可以表示为：

$ T\left( k \right) = N{\text{*}}\left( {\frac{1}{k}{\text{*}}k + \frac{1}{{{k^2}}}{\text{*}}\left( {2k} \right) + \ldots + \frac{1}{N}{\text{*}}\left( {mk} \right)} \right) $

(17)

为了方便运算, 令q=1/k, 则可将公式化简并求导为得：

$ \begin{gathered} T'\left( q \right) = 2*\left( {N - 1} \right)/\left[ {{{\left( {1 - q} \right)}^3}} \right] + \hfill \\ \;\;\;\;\;\;\;\;\;\;\frac{{ - {\text{ln}}N*\left( { - {\text{ln}}q + \left( {1 - q} \right)/q} \right)}}{{{{\left( {1 - q} \right)}^2}{{\left( {{\text{ln}}q} \right)}^2}}} = \hfill \\ \;\;\;\;\;\;\;\;\;\;\frac{1}{{\left( {1 - {\text{q}}} \right){q^2}}}*\left[ {\frac{{2*\left( {N - 1} \right)}}{{\left( {1 - q} \right)}} + } \right. \hfill \\ \left. {\;\;\;\;\;\;\;\;\;\;\frac{{ - {\text{ln}}N*\left( { - {\text{ln}}q + \left( {1 - q} \right)/q} \right)}}{{{{\left( {\ln q} \right)}^2}}}} \right] \hfill \\ \end{gathered} $

(18)

对于该导数, 中括号前面的数值大于等于0, 因此只需要对后面的进行分析即可。当1 < q < N时, r(q) < 0, T(q)单调递减；反之, 当0 < q < 1时, r(q) > 0, T(q)单调递增, 而q=1/k, 因此为了减少总体的任务量, 应当适当地增加k的大小, 即在k-近邻中, 应当尽可能地将一整行的数据排序整理, 作为value_list的值。

本文Shuffle中的k-近邻排序在理想状态下, 可以更好地完成由串行到并行的优化, 但是随着k的增加, 有可能会带来JobTracker的调度负重, 因此本文在此基础上进一步优化, 采取了k-邻域的排序基准。k-邻域的模板是方形的, 如图 4所示, 因此, k的值应该为整数的平方, 对于第一次迭代需要处理的任务数量为$2*(\sqrt k - 1)*\sqrt k $, 每一层迭代都会在上一层的基础上增加$\sqrt k $倍, 则总的任务量可以表示为：

$ \begin{gathered} T\left( k \right) = N{\text{*}}\left( {1/k} \right)*\left( {2*\left( {k{\text{ - }}\sqrt k } \right)} \right) + \left( {1/{k^2}} \right)* \\ \left( {{\text{2*}}\left( {k{\text{ - }}\sqrt k } \right){\text{*}}\sqrt k } \right) + \ldots + \\ \left( {1/N} \right)*\left( {2*} \right)\left( {k{\text{ - }}\sqrt k } \right)*{\sqrt k ^{m - 1}} \\ \end{gathered} $

(19)

为了方便分析, 令$p = \sqrt k $, 则化简后：

$ \begin{gathered} T(p) = 2N*\left[ {\left( {1 + \left( {1/p} \right) + \cdots + \left( {1/{p^{m - 1}}} \right)} \right) - } \right. \hfill \\ \;\;\;\;\;\;\;\;\;\left. {\left( {\left( {1/{p^2}} \right) + \cdots + \left( {1/{p^m}} \right)} \right)} \right] = \hfill \\ \;\;\;\;\;\;\;\;\;2N*\left( {1 - \left( {1/{p^m}} \right)} \right) = 2N*\left( {1 - \left( {1/\sqrt N } \right)} \right) \hfill \\ \end{gathered} $

(20)

可见在k-邻域的处理下, 总的任务数为只和块总量N有关的定值, 因此, 在k值选取时, 只需要考虑非理想状态下主从节点的通信问题, 由于本文的实验环境中, 从节点最多时为4个, 因此, Map节点和Reduce节点几乎会有相同量的处理任务, 结合上一节中分片算法的分析, 因此k的选取应使得其邻域的总大小与分片的大小相仿。

根据上述的各部分的算法描述, 具体的细节流程如图 5所示。

4 实验结果与分析 4.1 实验环境

本文所有基于Hadoop平台的实验都在4台VMware平台下的虚拟机搭建成的Hadoop集群环境中完成。1个作为主节点, 内存为2 GB, 其余3个作为从节点, 内存为1 GB, 硬盘大小为20 GB, 处理器都为双核, 虚拟机操作系统为Ubuntu12.04, 32位, Hadoop版本为Hadoop1.2.1。其他相关实验工具为：Eclipse, JDK1.8。

4.2 超像素块对比实验

为了验证本文基于Hadoop平台的超像素算法的有效性, 此节将Map节点的中间过程即超像素块与其他相应算法进行对比, 实验中, 对比实验的代码均来自相应的开源代码, 采用的图片是伯克利大学的图片库BSD300, 式(13)中的σ取0.3, λ取0.4。将本文算法与Ncut和SLIC进行对比, 结果如图 6所示。

从直观的角度观察可以发现, SLIC算法生成的超像素的面积不匀称、分布不规律, 这是由于SLIC算法采用线性的迭代搜索, 其聚类中心与位置相关, 因此聚类到的区域也会很不规律。而本文的Map节点中采用的是优化过的分水岭算法, 虽然还是会有一些过分割现象, 但是由于在整体的划分中, Map节点的任务是在一个超像素块内进行的深层次划分, 因此其整体的结构式比较有规则。同时, 从肉眼的角度观察分割的准确度, 由于SLIC追求的是时间上的效率, 为了达到线性的时间复杂度, 因此很多区域只是一个大概的轮廓, 比如左下角的木板以及左侧山峰的顶端等都有划分不精细的问题; 而本文采用的方法会与所有颜色层的像素点进行比对, 因此可以得到很准确的超像素轮廓, 但是由于小图像的超像素形成都在1 s左右, 而Hadoop的启动相对耗时, 在初期超像素形成的阶段并不占优势。对于Ncut算法, 其图像的合成代码是原作者编写^[26], 因此还保持灰度的状态, 但是并不会影响比较, 从图 6中可以看到, 虽然超像素的形状不是很规则, 但是其边缘的保持度很好, 与本文算法的准确度从肉眼上很难区分出来, 但是其在时间上就有很多的不足, 对于图例中321×481的图像, 产生100个超像素的过程中就已经花费了181.97 s。下面将进行详细的对比。

对于分割的质量, 本文从test数据集中全部100个图像的平均结果出发, 利用边缘查全率(Boundary Recall ratio, BR)和欠分割错误率(Under segmentation Error, UE)两个指标对三个算法进行严格的数值评定, 对比的结果如图 7~8所示。

在本文中, 分了方便比较, 初始化切分都分为16个区域, 因此选择对比生成的超像素数目都是16的整数倍, 重叠区域σ设为0.1, 不采用块间区域合并, 相邻的部分随机选择一个方向的分割作为准则来进行比较。从图 7可以看出, 在边缘查全率上本文算法与Ncut都有很明显的优势, 三种算法都是随着超像素数目的增加而越加精确, 但是在超像素数目较少的情况下, 由于本文中分布式的设计, 不同区域内也会有很精细的划分, 因此在低数目的超像素实验中, 本文算法也取得了相对理想的结果。在图 8中, 对比了三者的欠分割错误率, SLIC算法由于采取的是聚类的策略, 十分依赖聚类中心的数目, 因此在超像素数目比较少的情况下, 本文算法具有更好的效果, 在超高像素数目足够多的情况下, 三者都能达到比较优的分割结果。

4.3 最终分割效果对比实验

本文的整体分割主要流程是对切分好的图像块进行Map任务节点的超像素生成, 针对生成的超像素块在Reduce任务节点采取区域合并。下面是实验流程中的中间结果。

从图 9中可以很明确了解本文的分割流程, 图(b)是本文的重叠切割的效果, 选择的重叠参数σ为0.1, 可以从其中的分割中分辨出重叠的部分, 图(c)、(e)是每个Map节点中对于图像的处理, 图(d)、(f)是其中方框部分的放大效果图, 可以看到本文的超像素的边界保持的准确度很高, 图(g)是整体的超像素形成后的效果图, 图(h)为最终的分割结果, 将超像素内部以及块之间进行区域合并, 图像中的人物主图案轮廓十分清晰, 同时, 背景的花朵以及植物都很完整地分割出来。为了更准确了解分割的质量, 本文将会从大小两种尺度的图像对算法进行效果对比。

1) 小尺度图像对比实验。

本阶段利用伯克利的图像库中的图像进行实验, 图像大小均为321×481。对比其他两种算法:第一种算法是基于纹理特征的分割, 由Yu Hen Hu博士在ECE738(Electrical and Computer Engineering)上进行讲解^[27], 本文简称为ECE; 第二种是基于Mean-shift聚类的算法^[13], 经过很多的优化, 是目前分割效果较好的算法, 已经应用于软件Edison中。

三种算法的分割效果如图 10所示。单从本文算法的分割结果可以看到, 对焦焦点对本文的算法有一定影响, 比如最后一幅图片的蘑菇, 右边的树叶和左边树叶, 由于对焦的不同产生了不一样的成像结果, 而算法分割时候合并的阈值在过程中没有变化, 因此产生了不一样的分割结果, 拥有更好的容错性是以后的改进方向。与其他分割的结果相比, 本文的边缘贴合度更高, 在准确的同时又减少了原本算法的过分割；从细节部分观察, 本文的局部特征保存得也很完整, 可以从第二幅图像中, 楼房的门窗分割效果十分整齐。本文算法的缺点是线条过于生硬, 不够圆润。

对于分割的准确性, 可以用F值来进行测试, 如式(21)所示:

$ F = 2/\left( {1/p + 1/r} \right) = 2pr/\left( {p + r} \right) $

(21)

其中：p表示精确率(precision), r表示召回率(recall)。p为分割正确的数量除以所有分割出来的数量, r表示分割正确的数量除以应正确分割的总数量, 可以看到, 上述的F作为p、r的调和平均数, 将二者的关系进行综合, F为0到1的数值, 越接近1表示p、r两者的指标都优秀, 保证了分割的质量的判定。

表 1是进行了50次实验各个分割的平均时间和准确性的对比情况。

2) 大尺度图像对比实验。

超像素算法中最简单的SLIC算法, 在相同的1 GB内存实验环境中, 对于分辨率为3 000×3 000, 0.8 m可见度的卫星图像已经显示内存不足不能正常运行, 对于2 000*2 000尺寸的图像其运行速度已经不乐观, 而在本文的环境下就可以很快速地运行, 并且有很好的效果。下面的图像是美国QuickBird卫星于2009年4月24日拍摄的位于曼哈顿南边的华尔街, 0.6 m可见度, 分辨率3 000×3 000。

图 11所示是(a)是原图, (b)是方框部分放大的图, 可以很清晰分辨出各个景物, 图 12是本文的分割效果图, 整体部分只显示分割的线条。

从图 12中可以看到, 大部分的建筑物和道路边界十分清晰, 但是由于光照的原因, 海水的部分产生了些许的过分割, 这也是下一步的研究目标。为了更好地用数据来说明本文算法的效果, 本文以Edison软件的分割来作为对比对象, Edison软件是一个相对成熟的图像分割软件, 实验过程中使用其默认的参数和优化后的Mean-Shift算法, 表 2是本文算法和利用Edison软件分割的时间对比表, 采用不同分辨率图像多幅, 取平均值, 单位默认为秒(s)。

在表 2中, 本文的总体时间除分割、合成外还包括平台的启动时间以及节点的通信时间, 在相对较低的分辨率下, 其分割外的损耗会占有很大比重, 整体的时间上比Edison要费时, 但是在3 000×3 000的分辨率之后, 本文算法的时间优势逐渐体现出来, 在3 000×4 000之后Edison虽然预处理时间较短, 但是仍然无法短时间完成分割, 但是仍然无法完成分割；此外在运行的过程中, 超过2 000×3 000的实验, Edison软件的内存使用率很高, 经常使整个系统达到90%, 而本文算法则只占用很少的内存, 因此证明了本文算法思路的可行性, 同时对于大尺寸图像分割的准确度还应继续完善。

5 结语

本文采用超像素代替原始的像素作为分割的处理基元, 解决了原始像素作为分割基元时的效率低下问题, 将Hadoop分布式的特点与超像素的分块相结合, 完成了初始任务的分片、任务节点的超像素分割以及超像素的区域合并三个方面的优化。

在实验中所有小尺寸的图像数据来源于伯克利大学的图像库, 大尺寸的图像来源于互联网中QuickBird的卫星云图, 过程中对于各个优化部分都分类进行了相应的对比实验, 最终的实验表明, 本文算法的图像分割效果在不同尺寸下都令人满意, 而在分割效率上, 本文算法具有明显的优势。

由于缺少现有其他并行化图像分割算法的开源实验, 因此在大尺寸图像的精度对比中, 缺少统一的指标, 在今后的后续研究中, 可以在这个方向继续研究, 找到更多的对比指标, 同时可以在Map节点的分割算法中, 对阈值进行适应性调整, 提高分割的精度。