一种基于脊线的层级分水岭的技术定义分析

引言分水岭算法是一种常用的图像分割算法。分水岭算法的思想来源于地理学的测地线理论，20世纪70年代末引入图像分割领域。分水岭算法作为一种定义简单、定位准确、速度较快的图像分割技术，受到众多学术研究者的关注等的领接合并算法。它们在一定的领域，都取得了良好的效果。然而，分水岭预处理是辅助方法，改进的是分水岭算法的输入，而且预处理不能完全消除过分割；分水岭后处理是对分水岭产生的区域进行合并，分水岭算法产生的区域数量，直接影响其处理速度。可见预处理和后处理都未涉及对分水岭算法本身的改进。在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.分水岭算法相当的处理速度，是一种快速的分水岭改进算法。同时，在预处理方法、多级迭代停止条件等方面，本文算法仍存在着优化空间。
　　参考文献：
　　.International Journal of Image Processing，2011，5（5）：521-541.
　　.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（6）：583- 598.
　　.SPIE Image and Video Communications and Processing，2000，3974：759-766.
　　[4]刁智华，赵春江，郭新宇，等.分水岭算法的改进方法研究[J].计算机工程，2010，36（17）：4-6.
　　[5]卢官明.一种计算图学形态梯度的多尺度算法[J].中国图象图形学报，2001，6A（3）：214-218.
　　[6]焦斌亮，胡永刚.基于变尺度形态学的遥感图像边缘检测算法[J].光学仪器，2005，27（4）：13-17.
　　[7]孙卫芳，段智勇，朱仲杰.结合JSEG与分水岭方法的彩色图像分割[J].计算机工程与应用，2010，46（21）： 185-187.
　　[8]沈晶，杨学志.一种新的边缘保持分水岭的图像分割算法[J].工程图学学报，2009（5）：80-88.
　　[9]吴昊，刘正熙，罗以宁，等.改进多尺度分水岭算法在医学图像分割中的应用研究[J].计算机应用，2006，26（6）：1975-1979.
　　[10]余旺盛，侯志强，宋建军.基于标记分水岭和区域合并的彩色图像分割[J].电子学报，2011，39（5）：1007-1012.
　　.电子测量与仪器学报，2011，25（6）：516-512.
　　[12]梁旭东，武妍.基于领域特征化与聚类的图像分割方法[J].计算机工程，2011，37（3）：201-203.
　　[13]徐秋平，郭敏，王亚荣.基于多尺度分析与图割的快速图像分割算法[J].计算机应用研究，2009，26（10）：3989-3991.