Video Segmentation: Propagation, Validation and Aggregation of a Preceding Graph1作者Siying Liu & Sim Heng Ong新加坡国立大学电气与计算机工程系4工程驱动3 ，新 加坡117576 elelsnus.edu.sg eleongshnus.edu.sg Guo Dong & Chye Hwang Yan国防科技实验室，科学园道 20，新加坡118230 gdongdso.org.sg ychyehwadso.org.sg2目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论3文章摘要In this work, video segmentation is viewed as an efficient intra- frame grouping temporally reinforced by a strong inter-frame coherence. Traditional approaches simply regard pixel motions as another prior in the MRFMAP framework. Since pixel pre- grouping is inefficiently performed on every frame, the strong Correlation Between inter-frame groupings is largely underutilized. We exploit the inter-frame correlation to propagate trustworthy groupings from the previous frame. A preceding graph is constructed and labeled for the previous frame. It is temporally propagated to the current frame and validated by similarity measures. All unlabeled subgraphs are spatially aggregated for the final grouping. Experimental results show that the proposed approach is highly efficient for spatio- temporal segmentation. It makes good use of temporal correlation and produces satisfactory grouping results.4文章摘要视频分割是一种帧内图像的聚类方法，这种方法可以利 用时域上的帧间一致性信息来改善分割效果。 传统的视频分割方法只是简单地将像素点的运动看成 MRF-MAP工作框架下的一个先验信息。对每帧图像来说 ，像素聚类不能高效的完成，帧间的相关性信息没能充 分的利用起来。 在本文中，我们利用了帧间的时空局部一致性信息，从 前一帧分割图像中来传播可信度大的聚类结果。对前一 帧已经标定的图，我们把它传播到当前帧，并且通过相 似性措施来验证这个分割结果，所有没有标定的子图都 会在空间上做一次最后的聚合从而来得到我们最终的分 割结果。 实验结果表明我们的方法对时空分割是非常高效的，它 充分利用时间上的相关性信息，产生了令人满意的聚类 结果。5目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论6引言 Video segmentation在基于内容的视频检索和视频摘要上，意指语义实体 的分解（a decomposition of semantic entities）；在视频编解码上指运动物块的分割； 在场景解释上指一种基于时空信息的聚类方法； 在本文中指一种帧内的高效分割方法，这种方法可以 利用帧间的相关性来加强，它其实是一种基于时间相 关性和空间一致性的像素标定算法；7引言极大后验分割方法（MAP）8引言基于MRF-MAP分割方法 随机场：位置（ ）,相空间（ ）；怎么样利用位置集中每 两点之间的相关性将相空间的值赋给每个位置的问题； 马尔科夫性质：指的是一个随机变量序列按时间先后关系依次 排开的时候，第N+1时刻的分布特性，与N时刻以前的随机变量 的取值无关。 与 都用MRF来建模； 称为特征场或者灰度场，常以标号场为条件，用分布 函数描述观测数据或特征向量的分布。 称为标号场，常又被称为隐随机场，用先验分布描述标 号场的局部相关性。9引言基于MRF-MAP分割方法 数据项 对应特征场，表征观测数据或者特征向量的分布。 平滑项 对应标号场，表征不同像素点之间的关系。是图像 一种局部相关性的描述。 参数 来平衡二项之间的关系。 该方法的优雅之处就是把图像分割问题装化为了对最小化能量 函数的研究。10引言MRF-MAP VS Graph cut 最小化MRF-MAP的能量函数等价于 在图G中找最小权值和的割。 Graph cut Graph G=(S,E),S是像素点集，E是边集。 W是针对G中的每条边相连的2个像素的相关属性设置的权值。 上式的解法：the ratio cut，Normalized cut and min-max cut。11引言Graph cut的解法Graph cut的多值分割（ICM）12引言Graph cut的解法Min-max cut13引言Graph cut解法的相关比较 解法的分类 以Normailized cut为代表的谱图割方法，时间复杂度高（ ），限制了它们在尺度比较大的图片上的应用。以min-max为解法的图割方法，可以很好的解决空域上的图 片的分割，但是必须预先指定一些像素作为样本。14引言基于MRF-MAP的时空聚类方法 和 分别代表前一帧的标号集和像素集， 代表时间。 该方法的缺点： 容易引起过分割，时间相干性未能在video-based应用上得到充分利用 。 这种方法寻找一个最优解来分割不同大小的物体，很难找到一个模型 来解决空间尺度上的变化。而且该方法容易产生亚最优的分割结果。15目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论16系统结构流程图17目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论18问题形式化及解决传播 问题：A表示仿射变换矩阵。 在图像 和 采用SIFT算法找到 对尺度不变特征作 为样本训练得到A。 训练过程中为了增强算法的鲁棒性，可以通过RANSAC（ 随机采样一致算法）来选取比较好的样本，并且减少传播 变换带来的错误。19问题形式化及解决验证 问题：检测出了独立运动和仿射变换带来的错误。 经过验证环节，图 被分成2部分，一部分保留了前 一帧传播过来的正确结果，另一部分待定。20问题形式化及解决聚合 问题： 一种思路：以 为种子，分别建模，然后用min-max方法来cut。 两个挑战： Independent motions 和newly appear objects21问题形式化及解决聚合 本文的方法： 采取先将 进行颜色聚类，将它转化成许多的subgraphs， 然后和 的子图一起进行聚合聚合的准则：Edge，color and shape22问题形式化及解决聚合 聚合准则：EdgeThe edge weight：惩罚准则函数：23问题形式化及解决聚合 聚合准则：color惩罚准则函数：24问题形式化及解决聚合 聚合准则：shape 惩罚准则函数：Total cost function： 聚合候选选取：25聚合算法：26时空分割算法27目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论28实验结果实验数据 两段视频Table tennisCoast Guard29实验结果Over Segmentation Evaluation：30实验结果31实验结果Independent motion & newly appearear objects32实验结果33目录文章摘要 引言 基于MRF的极大后验分割方法 MRF-MAP VS Graph cut 基于MRF-MAP的时空聚类方法 系统结构流程图 问题形式化及解决 传播 验证 聚合 实验结果 总结和讨论34总结和讨论本文的方法充分挖掘了帧间的相关性来分 割，传播了前一帧的分割结果，通过颜色 相似性来验证，保留了正确的传播结果， 最后在空间上以最小化能量函数的方式来 聚合未标定的数据来得到最终的结果。 传播了分割结果，减少了每帧重新分割的 计算负担。 验证和聚合步骤可以解决独立运动和新进 入物体引起的分割问题。35总结和讨论Future work在验证阶段，仅用颜色相似性来验证是不够的，可以 融入多种其他特征信息来验证。 Question36