龙源期刊网 http://www.qikan.com.cn
基于Hadoop的超像素分割算法
作者：王春波 董红斌 印桂生 刘文杰 来源：《计算机应用》2016年第11期
摘 要：针对高分辨率图像像素分割时间复杂度高的问题， 提出了超像素分割算法。采用超像素代替原始的像素作为分割的处理基元， 将Hadoop分布式的特点与超像素的分块相结合。在分片过程中提出了基于多任务的静态与动态结合的适应性算法， 使得Hadoop分布式文件系统（HDFS）的分块与任务分发的基元解耦；在每一个Map节点任务中， 基于超像素分块的边界性对超像素的形成在距离和梯度上进行约束， 提出了基于分水岭的并行化分割算法。在Shuffle过程的超像素块间合并中提出了两种合并策略， 并进行了比较。在Reduce节点任务中优化了超像素块内合并， 完成最终的分割。实验结果表明.所提算法在边缘查全率（BR）和欠分割错误率（UR）等分割质量指标上优于简单线性迭代聚类（SLIC）算法和标准分割（Ncut）算法， 在高分辨率图像的分割时间上有显著降低。 关键词：Hadoop； 图像分割； 超像素； 并行算法； MapReduce 中图分类号：TP391.41 文献标志码：A
文章编号：1001-9081（2016）11-2985-08 0 引言
在世界多元化发展的背景下， 互联网技术在各个方面都为人们的生活带来了便利。图形图像作为人类与计算机交互最为直观、便捷的方式， 其相应的处理以及识别分析能力直接会影响到人们的感官体验， 而图像分割作为连接图像处理与图像识别、图像分析的桥梁， 也会为接下来的后续使用带来极大的性能提升； 同时， 图像本身的来源以及背景也随着成像技术的进步， 逐渐朝着多元化的方向发展， 大尺寸、高分辨率的图像本身蕴含着多维度的信息， 例如生物医学图像[1]、地理遥感图像[2]等， 如何在准确分割的同时保持较低的消耗时间成为时下研究的热点。
像素作为图像分割的基本单位， 是图像灰度及其基本原色素的编码， 在当今的大数据时代背景下， 大尺度、高分辨率的图像如果仍是以像素作为分割基准点， 执行起来就会非常耗时。超像素在图像分割中并没有十分明确的定义， 在不同的环境背景下可以适应性地变化， 大致可以理解为将某些具有相邻位置、相近颜色、相似亮度或者相似纹理特征的像素聚合到一起形成的一小块区域[3]。
在超像素提出的初期， 从算法核心的立足点的角度出发可以大致可分为两个原型：一是基于图论的方法， 二是基于梯度下降的算法。比较有特点的基于图论的方法有：2000年Shi
龙源期刊网 http://www.qikan.com.cn
等[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其中的一部分或者仅仅完成了对图像的简单处理， 例如图像的灰度处理、特征值提取等，2009年Conner等人提出了基于Hadoop的图像特征值提取的Blob算法， 步骤十分简单， 利用循环迭代逐步测试所有的像素点， 对所有的像素点进行排列；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 基于多图像块的分片算法
龙源期刊网 http://www.qikan.com.cn
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会一定程度上提高集群的效率， 根据经验， 一般会设为64MB， 一般是由参数dfs.block.size来进行确定， 在HDFS的hdfs-site.xml中进行配置。
1.2 基于双重重叠切分的输入
考虑到Hadoop的处理流程， 在任务分块时， 需要对原始输入的图像进行切割。 为了使得分割后不丢失切割线部分的信息， 采用图2的双重重叠方式进行分块。
图2中灰色部分为重叠区域， 图中只是分割的一部分， 并不代表整个图像， 表示如下： 1）首先读入待处理图像， 分析相应的分辨率n*m， 假设图像的高度为h， 宽度为w。 2）对于分割后的块， 按照串行的顺序进行编号， 从0到N-1， 假设横向的片数为WP， 纵向的片数为HP， 每一片的宽度为wi， 高度为hi， 重叠的权值为σ， 即横向的重叠宽度为σwi， 纵向的重叠高度为σhi， 假设所有的划分都完整， 即块大小都相等， 则可以得到如下关系：
1.3 基于动态最优的分片策略
对于分片算法的设计应当考虑两方面情况：首先， 对于作业数据量较小的情况， 在分块设置较小的前提下， 应当尽可能多地将数据划分成更多小的片段， 使得平台的负载更均衡；其次， 对于作业数据量较大的情况， 降低每一个Map节点处理时候的时间损耗， 同时也会给节点间的通信减轻负担。
本文算法根据静态平均和动态最优两个方式计算出相应的分片策略： 2.3 算法的并行化设计