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

0 引言
图像分割是一种重要的图像技术，它不仅得到人们广泛重视和研究，也在实际中得到大量的应用。图像分割在不同领域中有时也用其他名称，如目标轮廓技术阈值化技术，图像区分或求差技术，目标检测技术，目标识别技术，目标跟踪技术等，这些技术本身或核心实际上也是图像分割技术。图像分割的算法有很多，但是，在目前还没有一个算法是适合于所有的图像分割。针对不同的领域、不同的条件，应该选用不同的分割算法。

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)，继续扫描直到不能发现没有归属的象素，则结束整个生长过程。