武汉科技大学本科毕业设计
若??R,Q??max??Q,SiQ?，则合并R与Q。 3.2
i?1,2,...,q 合并规则（2）非常简单，但它确立了该区域合并进程的基础。（2）一个重要的优点是它避免了合并控制中相似性阈值的预置。虽然最值运算操作对异常值敏感 ，但我们经验发现算法工作良好。 这主要是因为，直方图是对本地区全局描述，它具有很强的噪音和很小的变化。
但是，标记区域仅覆盖一部分的目标和背景，那些目标和背景中的非标记区域也应
当被自动识别并正确标记。总的来说，标记区域包含了相应的主要特征，因此，未标记的目标区域与目标标记区域，以及未标记的背景区域与背景标记区域有着更高的自相似度。所以通常情况下，非标记的目标区域不会与背景区域相合并。类似地，未标记的背景区域同样不会与目标区域相合并。
3.5 区域合并算法
基于最大相似度的区域合并算法(Maximal Similarity based Region Merging，简称MSRM)，分为两个迭代地执行的阶段，直到没有新的区域合并发生。合并策略是尽可能合并背景区域，而保持前景区域不被合并。一旦合并完所有的背景区域，等价于提取了目标。
对每一个区域B?MB，确定其邻域集合SB=?Ai?i=1,2,...,r。对每一个Ai，如果Ai?MB，
i求其相应的邻域集合SAi=?AAj?j=1,2,...,k，显然B?SAi。然后计算Ai和SAi中的每一个区域
的相似度。如果B和Ai，满足下式：
??Ai,B??max??Ai,SAj?
ij=1,2,...,k那么B和Ai，合并成一个区域，新的区域将和B有相同的标记，即：
B=B?Ai
否则，B和Ai将不台并。
以上的过程迭代进行。在每一次迭代中，集合MB和N将被更新．其中，MB膨胀、
N收缩。当所有背景标记MB找不到新的合并对象时，迭代结束。经过第一阶段，部分
属于背景的区域互相合并。但是，仍有一些背景区域因为彼此间具有更大的相似度．因此它们不能和背景标记区域合并。第一阶段的合并结果如图3.3（a）所示。可以看出，
11
武汉科技大学本科毕业设计
经过第一阶段后，大多数属于背景的区域己被合并，但仍有一些未标记的背景区域未和背景标记区域合并。
为了完成目标提取，第二阶段将以第一阶段剩下的未标记区域N为处理对象，其中包含部分目标特征，同时也包含部分背景特征。未标记区域在最大相似度规则的指导下互相融合，即目标部分互相融合，背景部分互相融合。
经过第一阶段台并之后，对每一个未标记区域(属于目标或背景) P?N，构成它的邻域集合SP=?Hi?i=1,2,...,p，-接着，对每一个Hi，如果其满足Hi?MB和Hi?MO，构成
i它的邻域集台SHi=?AHj?j=1,2,...,ki。那么P?SHi。计算Hi和SHj中每一个区域的相似度
??Hi,SHj?。如果P和Hi，满足下式：
i??Hi,P??max??Hi,SHj?
ij=1,2,...,k那么将P与H，合并成一个区域
P=P?Hi
否则，它们不能合并。
以上过程迭代至未标记区域N中不再发生合并为止。图3.3（b）表明，经过第二阶段的合并之后，一些未标记目标区域和未标记背景区域分别互相融合。接着，重复地执行第一阶段和第二阶段，直到没有新的合并发生。最后，每个区域被标记成两类：目标或背景，图3.3（d）显示了最终提取的目标。在绝大部分实验中，算法将在2-3个回合结束。
图3.3 区域合并过程（a）第一回合第一阶段(b)第一回合第二阶段(c)第二回合第一阶段(d)第二回合第二阶段 MSRM算法
输入：初始均值漂移分割结果。 输出：最后的分割图。 当处于最后循环的区域合并中，
12
武汉科技大学本科毕业设计
第1阶段。将未标记区域N与背景标记区域MB合并。
输入：初始分割结果或第二个阶段的合并结果。
（1-1）对于每个区域B?MB，构成其邻域集合SB=?Ai?i=1,2,...,r。
i（1-2）对于每个Ai且Ai?MB，构成其邻域集合SAi=?AAj?j=1,2,...,k。
ii（1-3）计算??Ai,SA如果??Ai,B??max?Ai,SA，那么B=B?Ai。否则B和Ai不j?，jj=1,2,...,k??合并。
（1-4）更新MB和N。
（1-5）如果MB的地区无法找到新的合并对象，第一阶段合并结束。否则，返回到（1-1）。 第2阶段。自适应地合并未标记区域N。
输入：第一阶段合并的结果。
（2-1）对于每个区域P?N，构成其邻域集SP=?Hi?i=1,2,...,p。
i（2-2）对于每个Hi，Hi?MB且Hi?MO，构成其邻域集合SHi=?AHj?j=1,2,...,k，显然P?SHi。
Hii（2-3）计算??Hi,SH，那么P=P?Hi，否则，P与Hij?。如果??Hi,P??max?Hi,Sjj=1,2,...,k??不再合并。
（2-4）更新N。
（2-5）如果在区域N无法找到新的区域合并，第二阶段停止。否则返回到（2-1）。 结束
3.6 收敛性分析
该MSRM算法是一个迭代的方法。它逐步将未标记背景区域N分配到MB，然后把所有剩下的区域分配到MO。可以很容易地看出该方法收敛。我们有以下定理。
定理1 2.4节中的MSRM算法收敛，即所有的N区域经过若干迭代会被标记为
目标或着背景。证明如下：
如果在第一个阶段，一个未标记区域P?N在其邻域中有最大相似度区域B(B?MB)，那么P与B合并，即B=P?B。如果和P有最大相似度的区域B在目标标记区域中，那么P将保留。如果P和另一个未标记区域P’( P’∈N)有最大相似度，那么P与P’将在第二阶段合并．即P= P’? P。。根据以上分析，在迭代的下一个回合，P将与MB或其与另一个未标记区域P’合并，或仍保持不变。如果在某次选代后．任一个未标记区域P在MB或N中找不到相应的合并对象，算法将停止。
13
武汉科技大学本科毕业设计
从上面过程可以看出，随着合并的进行，来标记区域中的一部分与目标标记区域合并，一部分将与背景标记区域台并，因此未标记区域N的个数将会逐渐减少。一旦N停止减少，整个算法将停止，N中所有剩下的区域将被标记为MO。因此，N中所有的区域全部被标记，算法收敛。 3.7
本章小结
本章首先提出对彩色图像进行分割的算法，将以Mean Shift算法的分割结果作为基
础，提出一种新的交互式区域台并算法，来提取自然图像中的目标。接着对MSRM算法的背景知识做了介绍，即区域的表示和相似度的度量，以及标记的划分等。然后详细描述基于最大相似度的区域合并算法，MSRM分为两个迭代地执行的阶段，直到没有新的区域合并发生。合并策略是尽可能合并背景区域，而保持前景区域不被合并。一旦合并完所有的背景区域，等价于提取了目标。最后本章指出了算法的收敛性，并进行了证明。
14
武汉科技大学本科毕业设计
4 系统设计及实验结果
4.1 引言
MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。本文采用MATLA7.10完成系统设计。
4.2 图像分割系统
为了验证本文的算法，本文设计了一个自适应图像分割系统，该系统由3个模块组成，预处理模块、标记模块、和区域合并模块。该系统的总体框架如图所示，
图像分割系统 预处理模块 标记模块 区域合并模块 图4.1 图像分割系统框架
预处理模块的功能是：将原始的图片进行初始分割，这里采用的Mean Shift算法，初始分割后保存的文件名为‘imagename_IniSeg.png’。由于本文着重于区域合并算法，这里采用EDISON System[23]，它基于边缘信息对Mean Shift方法进行了扩展，区域性更好，可以识别微弱边缘。
标记模块的功能是：根据用户鼠标动作所完成的输入，在初始分割后的图像上做好相关的标记。其中目标标记为绿色，背景标记为红色。
区域合并模块是本文的核心部分，其功能是：根据目标和背景的标记结果和初始分割得到的小区域，按最大相似度规则进行合并，最后提取目标的轮廓。 4.3
实验结果与分析
通过一些有代表性的例子测试提出的算法，然后进行鲁棒性分析以及介绍可能失败
的情况，最后分析了提出算法的局限性。
4.3.1 实验结果
MSRM算法本质上是一个自适应区域合并方法。当用户输入交互式信息之后，算法
15