9.3.1流域变换算法建模
流域变换可以归属为基于区域的分割方法，这种方法的思想来源于地理学，即将图像看做是地形学上被水覆盖的自然地貌，图像中的每一像素的灰度值表示该点的海拔高度，其每一个局部极小值（Local Minima）及其影响区域称为集水盆（Catchment Basins），而集水盆的边界则是分水岭。通常描述流域变换有如下两种方法：第一种是“降雨法”，即当一滴雨水分别从地形表面的不同位置开始下滑，其最终将流向不同的局部海拔高度最低的区域（又称为极小区），那些汇聚到同一个极小区的雨滴轨迹就形成一个连通区域，称为集水盆，对于地形上凸起的平坦高地，雨滴在其上的运动，通常认为是顺着距离高地的下降边沿最近的路径流动。第二种方法是模拟“泉涌浸没”的过程，即首先在各极小区的表面打一个小孔，同时让水从小孔中涌出，并慢慢淹没极小区周围的区域，那么各极小区波及的范围，即是相应的集水盆。这实质上是两种不同的泛洪方法，不论是降雨法，还是爬山法，不同区域的水流相遇时的界限，即是期望得到的分水岭。将其应用到图像分割中，流域变换就是指将源图像转换为一个标记图像，其中所有属于同一集水盆的点均被赋予同一个标记，同时用一个特殊的标记来标识分水岭上的点。
1.连续域流域变换定义
连续域中严格的流域变换定义一般是基于距离函数的图像积分，但不同的距离函数可以得到不同的定义，这里仅讨论其中的一种。
定义9.1连续域流域变换定义
设fF(D)在定义域内存在极小区集合，I为顺序索引标记集合。某一极小点mi所代表的极小区最终形成的集水盆B(mi)定义为对于所有的pD，p到以极小点mi代表的极小区的距离比到其他任何以mj代表的极小区的距离更短：变换形成的分水岭是不属于任何集水盆的点的集合：设w0为一特殊标记，且，其代表分水岭点，那么灰度图像f的流域变换实质上是一个映射，使得若，则；否则，即图像f的流域变换就是将标记w0赋予D中各点，使得不同的集水盆打有不同的标记并且特殊标记，w0赋予图像f中分水岭上的点。
2.离散域流域变换定义
在图像处理中，我们更感兴趣的是数字图像，这时，数字灰度图像。但在数字图像中，距离函数的变化，高地（具有恒定灰值的区域）的形成及其在图像中可能大面积延伸所引发的问题，将使得连续域流域变换的定义不能直接扩展到离散域中来，而且这种非局部性的影响也是流域变换并行化的主要障碍。
递归过程的定义就是使灰度级从hmin增长到hmax，同时与f的极小区相关的集水盆也顺序地扩大。若用Xh表示在h级计算所得的集水盆集合，则一个在h+1级属于阈值集Th+1的连通域，要么是一个新极小区，要么是Xh中一个集水盆的扩展（其中，）。对于后者应计算Xh在Th+1范围内的测地影响区IZ，并更新为Xh+1，这里用Mh表示在h级所有极小区的集合。
9.3.2流域变换算法存在的问题
研究与实践表明，流域变换的思想已成功应用于图像处理和分析领域，并且随着理论研究的深入，人们又提出了许多新的行之有效的实现算法。但是这种算法还是存在着一些问题需要进一步的研究：
①分水岭位置的准确性问题。通常认为流域变换中的数字距离是连续域情况的一个近似结果，它应当尽量地逼近欧几里得距离，这也是产生误差的原因之一。由此可见，研究适合于流域变换的距离公式有利于提高算法的精度。
②算法并行化的问题。效率低一直是困扰流域算法发展的问题，以至于1998年后，国内在这方面的研究遭到冷遇。但随着并行化手段的发展，流域算法的并行化又成为近几年国际上研究的热点。
③过度分割（Oversegmentation）问题。由于原始信号中的噪声或一些小的灰值起伏波动，在梯度图像中可能存在许多假的极小值，造成分割过度。即使对梯度图像作过平滑，存在的极小点也往往会多于原始图像中的物体数目。本书即采用小波变换的方法较好地解决了流域算法的过度分割问题。
9.3.3采用小波变换解决流域算法的过度分割问题
前面我们讲过流域算法存在过度分割的问题，已有一些文献报道了解决过度分割的算法，他们一般均是基于区域合并的算法。本书则采用小波多分辨率分析的方法较好地解决了Watershed算法的过度分割问题，并有效地提高了计算速度。关于小波多分辨率分析的知识我们在上面的章节中已经作了详细的说明，在这一章我们就不再赘述。
1.Vincent-Soille算法
Vincent-Soille算法是Vincent和Soille在1991年提出的基于浸没模拟的Watershed算法。该算法分为如下两步：
（1）按灰度递增的次序给像素排序，以便于在某一灰度级直接访问相关像素；
（2）浸没过程：从极小区开始，一级一级地处理。用该算法模拟泉涌时，使用一个FIFO队列，按照宽度优先的方式递归地分配给每一极小区及其相关的集水盆不同的标记。例如递归到灰度级h，首先将所有灰度值为h的像素赋予标记MASK，且其中那些已标记邻域像素的像素被插入队列；然后从队列中的这些像素开始，在MASK的范围内计算各集水盆的测地影响区IZ，如果某像素只与一个集水盆i的像素连通，则打上该集水盆的标记i；如果一个像素同时与两个集水盆相邻，则标记为分水岭像素w0 ；最后那些标记为MASK的像素，则属于新出现的极小区，被赋予一个新的标记。该算法的复杂度与输入图像的像素个数呈线性关系。
2.基于小波变换的Watershed算法
小波变换的具体计算方法在前面章节已有详细的说明，这里就不再重复。该算法首先将原始图像进行一次小波变换，把原图像变换到小波域。求出变换后小波概貌图的形态学梯度图，梯度图中的高亮区域对应于原图像中的边界位置。图像的形态学梯度定义为：GRAD（f）=（f？g）-（f⊙g），其中g为以原点为中心的扁平结构元素，？和⊙分别为数学形态学中的膨胀和腐蚀操作。然后在梯度图中按一定的阈值T标记出极小区域。对标记后的梯度图采用Vincent-Soille算法分割，得到分割结果，如果分割结果中过度分割情况还比较严重，不符合分割要求则程序重新跳到第一步开始执行：对上次小波变换的概貌图再进行一次小波变换，对变换后的概貌图进行同样的处理直到结果符合要求。
3.算法讨论及实验结果
基于小波变换的Watershed算法在进行Watershed 变换前首先对原图像进行了一次小波变换，将原图像变换到小波域上，而后面的处理均是在小波变换后的概貌图上进行的。小波变换后的概貌图实际上是原图像被小波滤波器对（Filter Bank）中的低通滤波器滤波后的结果。由于小波变换的多分辨率特性，概貌图即是原图像在较大尺度上的图像。这种分解可以一层一层地进行下去，直到满足我们的要求。小波滤波器对图像噪声和小集水盆有很好的过滤作用，而噪声和小集水盆是造成图像过度分割的根本原因。小波的多分辨率分析为我们提供了不同尺度的图像信息，就像人眼从不同的距离来看一个物体，因此我们从大尺度上去分割图像能有效地抑制过度分割。虽然我们可以通过提高标记阈值T的方法来克服过度分割问题，但提高T值将造成相邻不同目标的极小区域合并，这样将使相邻不同目标被错误地分割到一起。而小波多分辨率分析只是将相邻且尺度较小的区域通过滤波进行了合并，这是多分辨率分析的优点之一。
根据Nyquist采样定理经过一级小波分解后进行下采样（Downsample）概貌图中的像素数目只占原图的1/4，经过二级小波分解后概貌图中的像素数目占原图的1/16，以此类推，计算量以1/4n（n为分解层数）递减，因此本算法还能显着地提高Watershed算法的计算速度。
①为验证基于小波变换的Watershed算法对克服图像过度分割的有效性，本书对标准图像分别采用一般的Watershed算法和我们提出的基于小波变换的Watershed算法在相同的标记阈值T（T=10）的情况下进行分割。小波变换采用的是Haar小波，它的低通滤波器参数为：L=（1/2，1/2）。对比两幅图，可以看出一般的Watershed算法的分割结果中存在着严重的过度分割现象，许多分割区域是由于噪声或小集水盆的影响而形成的，和原图像对比也不符合人眼的直观感觉。而采用本书提出的算法得到的分割结果有效地克服了图像的过度分割现象，并保存了原图像中存在的边界。根据前面的分析在这种情况下本书的算法计算速度比一般的Watershed算法快近四倍。如果还存在较严重的过度分割现象，则可进行进一步的小波分解，从更大的尺度上去观察图像，并进一步地提高计算速度，这正是小波多分辨率分析的优点。图像的过度分割现象已进一步得到了解决，这相当于我们从更大的尺度上去观察图像，但相应的图像分辨率会进一步下降。因此过度分割和图像分辨率是互相矛盾的，我们在应用时要权衡两方面的利弊，从而决定小波分解的层数。
②为了研究基于小波的流域算法的抗噪声性能，我们在标准图像中添加了标准化方差为0.001、均值为0的高斯白噪声。我们可以看出得到的分割区域是完全杂乱无章的。这说明普通的流域算法是一种对噪声相当敏感的分割算法，也是它为什么存在过度分割的一个重要原因。可以看出采用一级小波分解再进行流域算法受噪声的影响远远小于普通的流域算法，而采用二级小波分解后进行流域算法其结果基本未受影响，在这种情况下采用二级小波分解是一个比较好的选择。可以认为小波变换对提高流域分割算法的抗噪声性能具有相当大作用。
③我们对一幅真实的核磁图像（MRI）的T1加权图进行了处理，采用普通的流域算法得到的结果是一些杂乱的区域，而采用小波分解后再进行流域算法能得到一些完整的区域，分割效果得到了显着的提高。即使采用了小波的方法，其结果也存在大量的分割区域，这正说明了人类大脑结构的复杂性，以及分析医学图像的困难性（因为医学图像中含有大量的不同种类噪声信号）。如何进一步提高算法性能并将其应用到临床是我们下一步需要深入研究的问题。
我们分别对三种情况的计算时间进行了近似的实际测定。从表中可看出采用小波分解后，计算速度得到了明显的提高。按我们前面的分析，在不考虑小波分解所需时间的情况下，计算速度的提高应是4的倍数，而这里约为2的倍数，这主要是因为考虑了小波分解所需的时间。
9.3.4基于小波变换的流域算法小结
我们提出的基于小波变换的流域算法，解决了流域算法的过度分割问题，并有效地提高了流域算法的抗噪声能力，而且提高了计算的速度。但这种算法性能的提高是以分辨率的降低为代价的，在应用时应注意。小波的方法特别适合于边界模糊的图像分割，这是由于小波的多分辨率特性所决定的，在大尺度上边界的模糊将得到减弱，从而解决如图像的过度分割等问题。我们认为模糊图像的数学模型如下式：
定义9.3模糊图像的数学模型
其中为实际含有噪声的图像，为原图像，为噪声成分（这里是加性噪声的情况），F为我们定义的模糊算子，它作用在图像上会对图像产生模糊化的作用。
9.4医学图像的分割评价
图像分割的另一个重要问题是对分割算法的定性和定量评价。这对于医学图像的分割尤为重要，因为分割的准确度直接关系到临床应用的效果。
图像分割评价通过对图像分割算法性能的研究达到优化分割的目的。通过评价可以掌握各个算法在不同分割任务中的表现，以通过选择算法参数来适应不同类型图像的需要。另外，通过比较多个算法分割特定图像的性能，有助于在具体分割任务中选取合适的算法。分割评价不仅可以提高现有算法的性能，对研究新的分割技术也有指导意义。
人们在分割算法的评价方面提出了若干方法，这些方法有两个关键点：一是分析分割算法的机制或试验算法的途径，二是用来评判算法性能的准则。现有的评价方法可以归纳为两类：直接分析法和间接实验法。分析法直接研究分割算法本身的原理特性，通过分析推理得到算法性能。在本书中我们基本上对每一个算法均首先采用了这一方法。实验法则根据分割图像的质量间接地评判算法的性能。具体做法是，用待评价的算法去分割图像，然后借助一定的质量测度来判断分割结果的优劣。实验法又进一步分为两种：一种称为优度实验法，它采用一些优度参数描述已分割图的特征，然后根据优度值来判定分割算法的性能；另一种称为差异实验法，它先确定理想的或期望的参考图，然后通过比较已分割图与参考图，根据他们的差异来判定算法的性能。评价医学图像分割算法的一般做法是采用差异实验法，即将计算机的分割结果与正确分割结果相比较。正确分割结果（Ground Truth）数据包括实际数据和仿真数据两种来源。本书在进行研究时同时采用了两种数据来源。但主要采用了仿真数据（包括我们在进行PET激活区的提取时，广义地讲PET激活区的提取也是一种特殊形式的图像分割），仿真数据可以提供精确、客观的数据集，缺点是它们不是实际的数据。但对于医学图像，来自真实病人的数据集是机密的，非常不容易获得，本书所用的数据（特别是PET数据），就是费了很大的努力才获得的。