2010-10-21wangzhiming@ 54§8.5.2概率松驰法离散松驰法：不会产生二义性的标记，但只适用于简单的场景，不能处理不完全或不精确的图像分割； 概率松驰法：可克服场景中存在漏掉物体或是有额处区域的分割问题，但会导致图像不明确的解释。
2010-10-21wangzhiming@ 55§8.5.2概率松驰法(续) 相容的不见得是最好的，甚至不见得是正确的。
2010-10-21wangzhiming@ 56§8.5.2概率松驰法(续)每个物体有一组一元性质，标注是依据物体性质和在可能的物体标记与其他性质相互作用的物体标记之间的相容性度量；设物体R i 的标记为θi ，θi ∈Ω，Ω={ω1, ω2,….., ωR }；物体R i 的标记θi 的置信度是由与它直接作用的物体的标记结构决定；r(θi= ωk , θj= ωl )表示两个物体R i 与R j 之间的相容度。
松驰算法是一个迭代过程，目标是在整幅图像中得到局部最优的相容性。
2010-10-21wangzhiming@ 57§8.5.2概率松驰法(续)2010-10-21wangzhiming@ 58§8.5.2概率松驰法(续) 在迭代处理的第s 步对物体R i 标注θi 的支持q 可从其与物体R j 的二元关系中计算得到： 物体R i 拥有相同标记θi 的支持Q 可从第s 步迭代处理中的所有N 个直接相互作用的物体R j 以及它们的标记得到：(c 为归一化系数）∑======R l l j sl j k i k i sj P r q 1)(),()(ωθωθωθωθ∑∑∑==========N j R l l j sl j k i ij Nj k i sjij k i s P r c q c Q 111)(),()()(ωθωθωθωθωθ11=∑=N j ij c§2010-10-21wangzhiming@ 60§8.5.2概率松驰法(续) 线性松驰方案：初始非上下文概率：最优化问题，最大化标记的全局置信度：k i Q P k i k i ,)()(对所有ωθωθ===)|()(0i k i k i X P P ωθωθ===∑∑∑∑=========R k N i N j R l l j l j k i ij k i P r c P F 1111)(),()(ωθωθωθωθ0)(,1)(1>===∑=k i R k k i P P ωθωθ2010-10-21wangzhiming@ 61§8.5.2概率松驰法(续) 算法8.10：概率松驰法1. 定义图像中所有物体R i 的解释(即标记)的条件概率；2. 重复步骤3和4，一直到得到图像的最佳解释(目标函数F 取最大值)；3. 计算目标函数F 的值，以度量场景标注的效果好坏；4. 更新物体解释(标记)的概率值，使得目标函数F 的值增加。
2010-10-21wangzhiming@ 62§8.5.3搜索解释树树的层数与场景中的物体的数目一致，节点分配了所有可能的标记，使用基于回溯的深度优先的搜索策略；从第一物体(树根)分配标记开始，依此为每个物体分配相容的标记；如果不能分配相容的标记，则回溯到改变较高层次的一个最近的节点的标记； 一般采用基于深度优先的搜索策略；效率较低；需要合适的剪枝算法。
2010-10-21wangzhiming@ 63§8.6语义图像分割和理解语义方法表示了图像分割中的高级领域，包括图像区域解释，以图像理解为结果；语义区域增长：语义包含更多的有价值的信息； 图像区域以及其相互关系的表示：区域邻接图：节点表示区域，区域相邻关系由连接节点的弧表示； 对偶图：每个节点与不同区域边界线的交点相关，每条弧与一个边界线相关。
2010-10-21wangzhiming@ 64§8.6语义图像分割和理解(续)2010-10-21wangzhiming@ 65算法8.11:为归并两个区域更新区域邻接图其对偶1. 区域邻接图 (a)添加目前不存在的连接区域R i 和所有与R j 邻接的区域的弧；(b)在图中去掉节点R j 以及它的所有弧；2. 对偶图(a)去掉图中所有对应于区域R i 和R j 之间的边界的弧； (b)对所有与这些弧相关联的节点：如果与节点相关联的弧数是2，去掉此节点并合并这两条弧； 如果与节点相关联的弧数大于2，用新的区域标记R i 来更新与区域R j 的部分边界相关的弧的标记。
2010-10-21wangzhiming@ 66§8.6.1语义区域增长需要合并具有相同解释的相邻区域为一个单独的区域； 区域的解释可能是不可靠的，需要使用关于相邻区域关系的先验知识，并在区域归并中考虑上下文信息，最终在一定约束下得到最优的图像分割和解释。
2010-10-21wangzhiming@ 67算法8.12：语义区域归并1. 以含有很多小区域的图像初始化图像分割；2. 合并所有在公共边界上具有至少一条弱边缘的邻接区域；3. 对预先设置的常数c 1和c 2及阈值T 1，如果S ij <T 1，则合并相邻区域R i 和R j ，其中：4. 对所有区域R i 和R j ，计算以相互边界B ij 将它们分成两个有相同解释(θi =θj )区域的条件概率P ，如果P 大于某个阈值T 2，则合并R i 和R j 。
如果任何两个区域都不能归并，跳至步骤5；5. 对任何区域Ri，计算初始条件概率：6. 重复本步骤直到所有区域的标记是最终的：找到对其解释具有最高置信度C i 的非最终的区域，使用该解释标记区域，并标记是最终的，对每个非最终区域R i 及它的每个可能解释ωk ，更新其解释。
2010-10-21wangzhiming@ 68§8.6.1语义区域增长(续) 语义区域增长的局限性：归并结果与处理顺序有关，可能不是最优；没有可以找到最优归并的机制；语义区域增长从过分割结果开始，但这些结果可能不是最优的；通常的语义区域增长只是解释的层次上归并区域，并不估计归并得到的新区域的性质； 对于复杂图像得到不可靠的结果。
2010-10-21wangzhiming@ 69§8.6.2遗传图像解释 遗传图像解释：允许不断地寻找更好的归并和分裂；将语义和更高层知识结合到主分割过程中，而不是作为主分割步骤完成后的后处理；语义包含在目标评价函数中；在语义函数评价中，任何归并的区域都被认为是邻接的(contiguous )区域，测量它的所有属性； 遗传算法往往会达到(或接近)全局最优的图像分割和解释。
2010-10-21wangzhiming@ 70§8.6.2遗传图像解释(续) 遗传图像解释算法：基于假设和验证的准则；目标函数通过遗传算法来优化；遗传算法用串码描述待处理种群的任何一个成员； 在单个处理步骤中测试整个种群，优胜劣汰。
2010-10-21wangzhiming@ 71§8.6.2遗传图像解释(续)最优化准则：根据区域R i的性质X i，得到的该区域的解释是θi的置信度：根据与区域R i相邻且有解释θj的邻域R j，得到的该区域的解释是θi的置信度：在整幅图像上评价解释的置信度：(N R为邻接区域数目)或2010-10-21wangzhiming@ 72算法8.13：遗传图像分割和解释 1. 初始化分割，定义每个区域与它的标记在码串中位置的对应。
码串由遗传算法产生；2. 建立初始区域邻接图；3. 随机选择码串的初始种群，必要时使用先验知识；4. 遗传最优化。
为当前种群的每个码串，压缩得到区域邻接图(算法8.11)，利用邻接图，为种群的每个码串计算最优分割函数值；5. 如果在连续的几个步骤之后，最优化准则的最大值没有显著的增加，那么跳至步骤7；6. 让遗传算法产生分割和解释假设的新的种群，跳至步骤4；7. 具有最大置信度的码串(最好的分割假设)表示最终的图像分割和解释结果。
§8.6.2遗传图像解释(续)2010-10-21wangzhiming@ 73§8.6.2遗传图像解释(续) 例：分割草坪和球符号：B –ball ，L –lawn ； 高层知识:图像中有一个圆形的球在绿色的草坪上。
2010-10-21wangzhiming@ 74§8.6.2遗传图像解释(续)一元条件：根据球的紧致性，可得到一个区域是球的置信度：根据草坪是绿色的知识，可得到一个区域是草坪的置信度： 完美情况下，各自置信度为1。
二元条件：假设一个区域在另一个区域内部的置信度可由相容性函数来计算：2010-10-21wangzhiming@ 75§8.6.2遗传图像解释(续) 假设初始的猜测种群为：2010-10-21wangzhiming@ 76第2、3位置随机杂交，得到种群如下：2010-10-21wangzhiming@ 77§8.6.2遗传图像解释(续) 优秀的第2、3个被保留，其他两个死亡，再次杂交： 再次杂交：2010-10-21wangzhiming@ 78§8.6.2遗传图像解释(续)最终结果：2010-10-21wangzhiming@ 79小结1.图像理解控制策略：并行与串行，分层与非分层，自底向上与基于模型，混合控制；2.活动轮廓模型：内力(曲线的形状)，外力(图像中力，外部约束力)，能量最小化；3.点分布模型：具有一定形状但非刚体，配准、计算均值与协方差矩阵的特征向量和特征值；4.图像理解中的模式识别方法：分类，上下文图像分类，递归的上下文图像分类；5.场景标注和约束传播：离散松驰法，概率松驰法，搜索解释树；6.语义图像分割与理解：语义区域增长，遗传图像解释。
2010-10-21wangzhiming@ 80本章要求理解不同的图像理解控制策略之间的区别；理解活动轮廓模型的能量最小化搜索过程中各种力分别对应哪些因素；点分布模型适用的描述对象及描述方法；贝叶斯分类及上下文信息的利用； 理解语义增长及遗传算法的基本概念。
2010-10-21wangzhiming@ 81课后思考题1. 活动轮廓模型的内力和外力分别受哪些因素影响？2. 描述点分布模型的最大特征维数受限于哪些因素？3. 以图像二值化为例，给出是否利用上文信息的方案。
