策略模式在图像分割中的应用

1 基本概念
1．1 图像分割定义
    借助集合概念对图像分割可给出如下的定义：令集合R代表整个图像区域，对R的分割可看作将R分成N个子区域Rl，R2，…RN的过程：
    (a)URi=R；
    (b)读所有的i和j，i≠j，有Ri∩Rj=φ；
    (c)对i=l，2，…，N，有P(Ri)=TRUE；
    (d)对i≠j，有P(Ri∪Rj)=FALSE；
    (e)对i=1，2，…，N，Ri是连通的区域。
    其中P(Ri)是对所有在集合Ri元素的逻辑谓词，φ代表空集。
    对图像的分割总是根据一些分割准则进行的。条件(a)说明分割必须是完全的；即，每个象素必须属于一个区域。条件(b)要求区域中的点必须与某个预定义的准则相联系。条件(c)说明不同区域必须是不相交的。条件(d)涉及在分割区域内必须满足的性质——例如如果所有Ri内的像素有相同的灰度级，则P(Ri)=TRUE。条件(e)说明区域Ri和Rj对于谓词P是不同的。
1．2 Strategy模式
    按照四人团的说法，Strategy模式的意图是：定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换，本模式使算法可独立于使用它们的客户而变化。将算法的选择和算法的实现相分离，让客户可以基于场景作出选择。

2 典型算法
2．1 边缘检测边界闭合法
    为将图像中不同的区域分开，需要将边缘象素连接起来组成区域的封闭边界。边缘检测算子都是并行工作的，如果边界闭合也能并行完成，则分割基本上可以并行实现。边缘象素连接的基础是它们的梯度之间有一定的相似性。用梯度算子对图象处理可得到象素两方面的信息：1)梯度的幅度；2)梯度的方向。结合边缘象素梯度在这两方面的相似性可把边缘象素如下连接起来。具体说来如果象素(s，t)在象素(x，y)的领域且它们的梯度幅度和梯度方向分别满足以下两个条件(其中T是幅度阈值，A是角度阈值)：

   
    那么就可将(s，t)的象素与在(x，y)的象素连接起来。如对所有边缘象素都进行这样的判断和连接就有希望得到闭合的边界。
2．2 动态规划轮廓搜索法
    动态规划是一个多步决策过程，它通过把一个N步过程化为N个单步过程的方法使算法的复杂性按对数律降低。根据动态规划的原理，可将全局最优化成局部最优之和。动态规划轮廓搜索法是：
    令r(n)为从起始结点s出发经过当前结点n到达目标结点g的最小代价通路的估计代价。这个估计代价可以表示成两个代价之和，即从起始结点s到当前结点n的最小代价通路的估计代价t(n)以及从当前结点n到目标结点g的通路的估计代价h(n)之和：
    r(n)=t(n)+h(n)
    这里t(n)可取为目前从结点s到结点n的最小代价通路，h(n)可借助某些启发性知识得到。常用的启发性知识包括通路的方向性(是否指向搜索的终点)，光滑性(可通过曲率计算来估计)以及代价估计。代价的计算可参照前面的方法。根据r(n)=t(n)+h(n)进行图搜索的搜索算法(称为A*算法)由以下几个步骤构成：
    1)将起始结点标记为OPEN并置t(s)=0；
    2)如果没有结点为OPEN，失败退出，否则继续；
    3)将r(n)=t(n)+h(n)算得的估计代价r(n)为最小的OPEN结点标记为CLOSE；
    4)如果n是目标结点，找到通路退出，否则继续；
    5)展开结点n，得到它的所有子结点(如果没有子结点，返回步骤2))；
    6)如果某个子结点ni还没有标记，置r(ni)=t(n)十c(n，ni)，标记它为OPEN并将指向它的指针返回到结点n；
    7)如果子结点ni以标记为OPEN或CL0SE，根据t’(ni)=min[t(ni)，t(n)+c(n，ni)]更新它的值。将其t’值减少的CLOSE子结点记为OPEN，并将原指向所有其t’值减少的子结点的指针重指向n。返回步骤2)。
2．3 改进的直方图凹面分析法
    图像的灰度直方图是图像各象素灰度值的一种统计度量。许多的阈值选取方法就是根据直方图来进行的。对含有目标和背景两类区域的图像，其直方图并不一定总是呈现双峰形式。例如当目标和背景区域的主要灰度比较接近而部分重叠时，其间的谷可能不存在。又如当图像中目标和背景面积相差较大时，直方图的一个峰会淹没在另一个峰旁边的缓坡里，直方图具体就是把直方图看作平面上的区域，计算其凸包并求取其最大的凸残差，以对应最大凸残差的灰度值作为阈值来分割图像。这里最大的凸残差是用一种称为凹性测度的指标来衡量的。与一般方法不同，这里要求凸残差的计算是沿与灰度垂直的直线进行的。
    改进的直方图凹面分析法就是先将直方图函数取对数，计算指数凸包，然后借助凹凸性分析确定阈值。
2．4 分裂，合并和聚集法
    区域生长方法将图像以象素为基本单位来进行操作，基于区域灰度差的方法主要有如下步骤：
    1)对图像进行逐行扫描，找出尚没有归属的象素；
    2)以该象素为中心检查它的邻域象素，即将邻域中的象素逐个与它比较，如果灰度差小于预先确定的阈值，将它们合并；
    3)以新合并的象素为中心，返回到步骤2)，检查新象素的邻域，直到区域不能进一步扩张；
    4)返回到步骤1)，继续扫描直到不能发现没有归属的象素，则结束整个生长过程。

3 Strategy模式的应用
    图像分割的主要控制对象为阈值，为使阈值选取算法的选择具有更大的灵活性，引入Strategy模式，把不同的阈值选取算法分别封装起来，并使它们可以相互替换，这样不但可以在不同的环境条件下灵活地采用相应的阈值选取算法，而且在将来有更好的阈值算法出现时能够方便地对系统进行改进和扩展。实现Strategy模式的类图如图l所示。

    图1中的TaskControl类包含一个ControlStrategy接口成员controlStrategy，因此Controller类的对象可以依靠其实现ControlStrategy接口的成员controlStrategy的多态性来实现不同的阈值选取算法。当有更好的阈值选取算法出现时，只需添加一个实现ControlStrategy接口的类就可以方便地更新图像分割系统。并且TaskControl类拥有设置其成员controlStrategy的功能，使得系统可以在运行时更换不同的算法，提高了系统的灵活性。

4 结论
    通过Strategy模式，可以将不同的阈值选取方法封装起来，使图像分割系统不再局限于特定场景、一个阈值选取算法，对于不同的场景，可以选取不同的算法，实用的范围更加的广泛。