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

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；