一种基于脊线的层级分水岭新算法 摘要： 针对传统V.S.分水岭算法存在的过分割现象，提出一种基于脊线的层级分水岭算法通过对传统V.S.分水岭算法中浸没过程的适当改进，找到完整无冗余的区域脊线；再次修改浸没过程，仅对脊线进行多级迭代的分水岭再分割，即可完成区域分割实验结果显示：该算法能处理传统V.S.分水岭算法的过分割现象，且计算速度较快 关键词： 图像分割； 分水岭算法； 脊线； 多层级分割； 模拟泛洪 引言分水岭算法是一种常用的图像分割算法分水岭算法的思想来源于地理学的测地线理论，20世纪70年代末引入图像分割领域分水岭算法作为一种定义简单、定位准确、速度较快的图像分割技术，受到众多学术研究者的关注[1]目前应用得较多的2种算法为：1991年Vincent L等人[2]提出的基于模拟泛洪的快速分水岭算法（下文简称为“V.S.分水岭算法”）；2000年Smet P D等人[3]提出的一种模拟降水的分水岭分割算法传统分水岭算法存在着不足之处，如：对图像噪声敏感、易产生过分割、对低对比度图像易丢失某些重要轮廓等为此，很多学者进行了相关研究，提出了一些改进型分水岭算法，如与预处理滤波、标记、小波变换等结合的改进算法[4]。
其可分为：分水岭预处理和分水岭后处理两类算法分水岭算法的输入图像通常是图像梯度，分水岭预处理多是优化梯度图，以降低过多的局部极小点梯度图一般采用形态梯度[56]、索贝尔（Sobel）梯度算子、J图分割（JSEG）[7]等算法为了降低过分割，预处理阶段可采用中值滤波、非线性滤波、双边滤波[8]、多尺度滤波[9]、多尺度梯度[5]、形态学标记[10]等方法减少局部极小值点的个数分水岭后处理，旨在对传统分水岭算法产生的过分割区域，进行区域合并进行区域合并的算法有：基于K均值聚类算法（kmeans clustering with manifold，KCM）、模糊聚类算法（fuzzy cmeans，FCM）、期望最大（expectationmaximization，EM）、高斯混合模型（Gaussian mixture model，GMM）、图论等的簇集算法[1115]；及利用贝叶斯、马尔可夫随机场（Markov random field，MRF）[16]、积水盆深度[1718]、相邻区域边界长度[19]等的领接合并算法它们在一定的领域，都取得了良好的效果然而，分水岭预处理是辅助方法，改进的是分水岭算法的输入，而且预处理不能完全消除过分割；分水岭后处理是对分水岭产生的区域进行合并，分水岭算法产生的区域数量，直接影响其处理速度。
可见预处理和后处理都未涉及对分水岭算法本身的改进在V.S.分水岭算法中，水从起伏地貌的各个局部最低点开始向上漫溢，从不同地方漫溢上来的水会交汇于不同的局部区域边缘如在水面交汇的地方建起水坝，则这片地面就被分割成不同的区域这些不同的区域称为汇水盆地，区域边缘建起大坝的地方称为分水岭一次分水岭分割处理，可得到丰富的区域和边界；也包括部分实际并不需要的边界为此，本文针对分水岭算法本身，提出了一种新的基于脊线的层级分水岭算法，即：利用经典泛洪分水岭算法本身的优点，设计新的泛洪规则，实现多次分水岭分割过程的多级迭代算法，来完成图像的分割目的，并将一次分水岭分割形成的分水岭称为“脊线” 1基于脊线的层级分水岭算法本算法核心是一种利用分水岭算法本身的多级迭代算法，图1所示为算法流程框图待处理图像输入后，经过四个步骤，即可输出结果各步骤说明如下：（1）预处理：降低噪声，平滑图像2）生成脊线：生成可供再分割区域边界脊线为了实现基于脊线的多级分割，本文算法要求该步骤生成的脊线必需满足2个条件：（a）区域一定有封闭完整的边界脊线，不允许存在无脊线分割的相邻区域；（b）脊线宽度为1个像素，不能有冗余本文利用了一种改进的V.S.泛洪分水岭算法来生产这些脊线。
3）基于脊线的多层级再分割：将已获得的积水盆区视为透明区，根据给定的“泛洪”规则，仅对已知脊线进行另一种改进的V.S.泛洪分水岭算法来生成新的脊线，以实现多层级再分割4）判断是否达到分割目标：根据一定判据，判断分割是否达到目的是则停止分割，输出结果，当前已获得的脊线即为所得分水岭；否则利用当前脊线，再重复步骤（3），直到满足分割目标为止 下文重点描述步骤（2）和步骤（3），也即本文算法核心所在 1.1生成脊线为了在后续分水岭算法的再分割中，仅利用已知的脊线信息，本文算法要求本步骤生成的脊线必须足够完整生产脊线有多种算法，一种方法是通过边界提取算子，如罗伯特（Robert）算子，但不能确保脊线一定出现在边界处考虑V.S.分水岭算法本身的优点，经过适当的改进，即可实现：在泛洪生成区域的过程中，同步生成完整的脊线下文将此改进算法简称为分水岭“改进算法A”V.S.分水岭算法[2]可以分为两个过程：排序和浸没排序可得到待处理图像的最小像素值hmin和最大值像素值hmax浸没过程是个区域生长的循环过程，流程图如图2所示，其中，h表示循环变量 由于“改进算法A”对浸没过程中队列生长的严格判断，可获得完整非冗余的分水岭脊线。
图3所示为“改进算法A”与V.S.原算法的结果比对图，梯度图通过Sobel算子得出其中（a）为实验原图，（b）、（d）分别为V.S.分水岭算法与“改进算法A”生成区域图，（c）、（e）分别为（b）、（d）对应的局部放大图在（c）图方框指示区中存在相邻4像素皆为标记脊线的情况，即脊线宽度超过了1个像素；（c）图中还存在大量脊线断裂不连续的现象；而（e）图中脊线连续封闭且宽度恒为1个像素，有效避免了这些现象 1.2基于脊线的多层级再分割经过“改进算法A”，生成了完整的区域脊线这些脊线有以下两个特点：（1）从形态看，每一个分割后的积水盆，都是由脊线包围的封闭区域，当水充满每一个积水盆时，盆内的更精细的结构将不可见，影响形态的只有脊线元素2）图像梯度反映了图像局部的不一致性，分水岭的脊线，是局部不一致性最强的位置，积水盆内部的一致性好于脊线，脊线反映了相邻区域的差异因此，综合以上因素，为了获得更大尺度、更宽一致性的区域，有必要跟踪已有脊线，仅对脊线元素，迭代实施某种分水岭变换，以达到所需的区域分割目标为止此过程即为：基于脊线的多层级再分割过程，其中迭代变换是一种再次改进的V.S.分水岭算法，本文简称其为分水岭“改进算法B”。
改进算法B”对图2中的两个环节做了新的修改，描述如下：（1）搜索像素入队列：只搜索分水岭脊线，当脊线领域中具有“新级别”（大于前一层级标识最大值）标记的像素，将脊线加入队列，同时设置脊线标识（MASK）2）队列像素区域生长：对队列中像素进行区域生长a）对标记为MASK的像素作区域生长先确定当前像素的标记是否为分水岭，是则停止生长；否则考虑此像素的领域像素，且仅当领域像素标记为MASK或“前一级别”时，对领域作基于距离变换的区域生长像素邻域标记类型可能有：前一级别标记、当前级别标记、MASK和脊线；（b）对标记为“前一级别”的像素作区域生长仅当领域像素标记为MASK或“前一级别”时，对领域作基于距离变换的区域生长；（c）对“前一级别”邻域像素的标记处理细节可以通过一个简单的区域映射表来实现，即“前一级标记”“当前级别标记”，初始时每个表项设为无效标记，如取-1映射表的作用是保证区域生长过程中，“前一级别”区域的完整性，另一个作用是避免同时查询、新旧两张标记图这个映射表也是层级分割输出的一部分映射表的实现可以用一个数组即可 图4所示为基于脊线的多层级分割原理示例图图4（a）为分水岭算法待处理梯度图的局部。
图4（b）为“改进算法A”生成的脊线图，脊线用虚线表示（下同），生成浸没区域为①图4（c）和（d）是两级“改进算法B”的处理结果对图4（b）中脊线进行“改进算法B”的分水岭变换，将会继续浸没产生图4（c）中②区，生成如图4（c）所示新脊线对图4（c）中脊线进行“改进算法B”，将会继续浸没产生图4（d）中③区，生成如图4（d）所示新脊线之后，需要根据整张图像的情况和采用的判据，进行更多级别的再分割，达到分割目标即可结束 1.3多层级分割判据如果对基于脊线的多层级分割过程不加限制，将出现“过合并”现象在实际应用中，需要用合适的判据方法来减少“过合并”现象本文采用判据方法为：自适应调整脊线阈值法由两部分实现：（1）自适应更新脊线值：计算区域的平均灰度，将区域脊线值更新为相邻区域灰度均值差的最大值2）区域分类：区域脊线的最大值为vmax，取一阈值vthred，判断两者关系：对满足vmax>vthred区域不作处理，直接进入下一级分割；对其它区域，进行浸没计算vthred计算方法为：对经“改进算法A”获得的区域脊线图，仅考虑脊线值，非脊线像素置0，进行基于最大类间方差法[20]二值化，计算而来的分割阈值。
2实验结果与分析按照图1所示流程图，本文对Berkeley数据库彩色图像及工程实用电缆截面图像进行了基于脊线的层次分水岭分割实验显示：本文算法可以处理部分图像的过分割现象，且处理速度较快 2.1实验过程本文算法经预处理阶段后生成梯度图，不同图像可以选择不同的梯度图生成方式然后对梯度图作边界2个像素的延拓对此梯度图进行分水岭“改进算法A”生成初始脊线随后，对脊线进行分水岭“改进算法B”、自适应调整脊线阈值相结合的多层级再分割过程，即可完成最后分割不同的图像，再分割的级数不同 2.2分割结果与分析本文选取的测试实验图像有两类：Berkeley数据库的彩色图像；工程用电缆绝缘切片灰度图像此两类图像的多级分割实验为实验一和实验二，实验过程图如图5、图6所示二者都按灰度图像处理，梯度图获取方式都为Sobel梯度算子在实验一和验二中，第一张图为原始图像，其它为多级分割的各级区域脊线图，脊线用实线表示，区域透明，多级分割的级别用n表示n=1表示“改进算法A”获取的区域脊线图，n>2表示“改进算法B”获取的区域脊线图n=7表示最后分割结果图 从实验一、二中可以看出，随着分割级数的增加，区域数量逐渐减小，灰度相似的小区域逐渐向同一个大区域合并，基本完成不同灰度区域的分割。
实验一最后一级将鹰树枝分割在同一区域中，天空被树枝分割为6个区域，在图中用①～⑥标号表示实验二最后一级将电缆绝缘切片图像主要分为三个区域：绝缘层内、绝缘层、绝缘层外图7所示为更多的多级分割实验图，第一行为原始图像，第二行为对应的多级分割最后结果图第一列基本实现天空、树木山坡的分割第二列将花叶、花盆、花盆中土、背景基本分离开来了第三、四、五列实现了电缆绝缘层、层内外背景的分离，且第五列同时实现了两个绝缘层的单独分割 3结论本文针对传统V.S.分水岭分割算法中存在的过分割现象进行了分析，考虑分水岭算法本身的优点，提出了一种基于脊线的层次分水岭算法通过分水岭“改进算法A”提取了完整非冗余的区域脊线，自适应调整脊线阈值，对脊线进行分水岭“改进算法B”多层级再分割，取得了不错的实验结果从对部分彩色图和工程图的实验中看出：本文算法可以有效避免过分割现象，对不同显著区域能有有效分割在层级迭代过程，本文算法只处理脊线，计算量大大降低，达到与传统V.S.分水岭算法相当的处理速度，是一种快速的分水岭改进算法同时，在预处理方法、多级迭代停止条件等方面，本文算法仍存在着优化空间 参考文献： [1]MAHMOUDI R，AKILM，Analyses of the watershed transforms[J].International Journal of Image Processing，2011，5（5）：521-541. [2]。