Image Segmentation with A Bounding Box Prior 作者：Victor Lempitsky, Pushmeet Kohli, Carsten Rother, Toby Sharp 出处：ICCV 2009 讲解人：马志国 2018年11月29日

第一作者 Name: Victor Lempitsky Education: Researches: Publications: Postdoc: Microsoft Research Cambridge Ph.D and undergraduate: Moscow State University Researches: Computer vision and pattern recognition Publications: Conference: ICCV’09, CVPR’09, ECCV’08, CVPR’ 08, ICCV’ 07, CVPR’07(3), BMVC’ 06, ECCV’ 06. Journal: PAMI’ 2009 2018年11月29日

第二作者 Name: Pushmeet Kohli Education: Researches: Publications: Postdoctoral Researcher: Microsoft Research Cambridge, 2007 PhD: Computer Vision, Oxford Brookes University, 2007 Undergraduate: National Institute of Technology, Warangal, 2004 Researches: Computer Vision Discrete Optimization Algorithms for MAP Inference Crowd-sourcing for Machine Learning Publications: Conference: ECCV’08, ICML’08, CVPR’08(3), CVPR’07, ECCV’06, ICCV’05, Journal: IJCV’09, SIGGRAPH’08, PAMI’08, IJCV’08, CVIU’08, PAMI’07 2018年11月29日

第三作者 Name: Carsten Rother Education: Researches: Publications: Permanent researcher: Microsoft Research Cambridge, 2004 -- PhD: Royal Institute of Technology Stockholm/Sweden, 2004 Diploma degree: University of Karlsruhe/Germany, 1999 Researches: Markov Random Field Models for Computer Vision Discrete Optimization Vision for Graphics (interactive segmentation and matting) Publications: Conference: CVPR(13), ICCV(8), ECCV(7), BMVC(3), … Journal: IJCV(3), PAMI(2), … 2018年11月29日

第四作者 Name: Toby Sharp Education: Researches: Publications: Diploma degree: University of York in pure mathematics Researches: Lead developer for the Computer Vision group Professional member of the BCS and IEEE Led the design and development of MoviePlus Publications: Conference: ICCV’09, CVPR’08(2), ECCV’08(2) Journal: ACM Transactions on Graphics 2018年11月29日

文章的相关信息 相关文献 Y. Boykov and M.-P. Jolly, “Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images” In ICCV, 2001 S. Nowozin and C. Lampert. Global connectivity potentials for random field models. In CVPR, 2008. 2018年11月29日

文章摘要（英） User-provided object bounding box is a simple and popular interaction paradigm considered by many existing interactive image segmentation frameworks. However, these frameworks tend to exploit the provided bounding box merely to exclude its exterior from consideration and sometimes to initialize the energy minimization. In this paper, we discuss how the bounding box can be further used to impose a powerful topological prior, which prevents the solution from excessive shrinking and ensures that the user-provided box bounds the segmentation in a sufficiently tight way. The prior is expressed using hard constraints incorporated into the global energy minimization framework leading to an NP-hard integer program. We then investigate the possible optimization strategies including linear relaxation as well as a new graph cut algorithm called pinpointing. The latter can be used either as a rounding method for the fractional LP solution, which is provably better than thresholding-based rounding, or as a fast standalone heuristic. We evaluate the proposed algorithms on a publicly available dataset, and demonstrate the practical benefits of the new prior both qualitatively and quantitatively. 2018年11月29日

文章摘要（中） 用户提供的矩形边框，在现有的交互式图像分割框架中，被认为是一种简单和流行的交互方式。但这些框架仅利用提供的边框将边框外的部分排除在外，以此作为能量最小化的初始化。本文中，我们讨论如何进一步利用边框提供的拓扑先验，确保分割结果与边框保持足够的紧致性。 拓扑先验被表示为全局能量最小化框架中的严格约束，推导为整数规划问题。通过线性松驰和pinpointing的图割算法，可以近似求解上述的整数规划问题。 公共的数据集上的定性及定量的实验展示了新的先验的有效性。 2018年11月29日

提纲 背景知识介绍：线性规划和图割 问题的提出 问题的形式化表述 问题的求解 实验结果 问题与讨论 紧致性定义 最小化能量函数 连续松驰线性规划 Pinpointing算法 实验结果 问题与讨论 2018年11月29日

交互式分割简介 交互式分割的目标 更精确分割 更少用户交互 交互方式 矩形框 笔画 … 2018年11月29日

线性规划的标准形式 目标函数 约束 矩阵形式 2018年11月29日

线性规划的求解 求解算法 算法已经很成熟 单纯形法(可行域边界) 椭球法 内点法（可行域内部） … 蓝色框为可行域，实线表示约束函数，虚线为目标函数在不同位置取值 求解算法 单纯形法(可行域边界) 椭球法 内点法（可行域内部） … 算法已经很成熟 2018年11月29日

图像分割中的能量最小化方法 图像分割 指定每个像素为背景（标号为0）或前景（标号为1） Cp为图像B中像素p的特征（本文中取RGB值） 最优分割等价于最小化能量函数E(x) 2018年11月29日

使用Graph cut最小化能量函数 Boykov(2001)等人提出的方法可以快速最小化形如 的能量函数 复杂度为多项式级，较之原始的指数级下降很多。 Google scholar中该文章被引用1484次，另外两篇后续的文章分别被引用846和801次。 2018年11月29日

本文问题的提出 未利用边框的紧致性约束，分割结果的某些部分离图像的边框过远（颜色与主体不一致的部分） 2018年11月29日

以前的方法 现有的交互式分割方法大多忽略边框的拓扑先验，只对边框的内部进行处理 主动边界亦称为Snake,可以利用拓扑先验，但容易收缩过于严重或陷入局部最小 2018年11月29日

本文方法 将拓扑先验形式化为紧致性，从而将分割问题转化为整数规划的问题 目标函数中整合了颜色分布和边缘信息，约束项中实现紧致性 通过放松对解的整数性要求，最后对实数解进行取整，可得到上述整数规划问题的近似解 提出pinpointing作为替代简单的阈值化取整方法 2018年11月29日

紧致性定义 边框B中虚线与边框之间的部分称为margin，四种margin分别为right, left, top, bottom Margin包围的部分称为中间盒(middle box) M. 两种交叉路径 短交叉路径：位于中间盒M中，且端点在M上的曲线(图中 蓝虚线) 长交叉路径：曲线位于边框B中，如曲线的端点在边框B的左右的两侧，曲线只能经过top, bottom margin的中间; 类似地，当端点在上下两侧，曲线只能经过right, left margin的中间。（图中红虚线） 三种形状 强紧致形状：与所有短交叉路径相交（图b） 弱紧致形状：与所有的长交叉路径相交（图d） 非紧致形状：不符合弱紧致的其他形状（图c） 2018年11月29日

紧致性约束下的能量最小化 紧致性约束：交叉路径上的点，至少有一个四邻域点为前景像素 新约束下的能量函数如下 精确求解上述整数规划问题的复杂度为指数级，需要进行近似求解 2018年11月29日

优化方法介绍 放松对xp的整数性约束，优化函数变为标准线性规划 问题：约束（c）的数目为指数级，无法直接求解，可使用迭代的方法求解。 2018年11月29日

线性规划的迭代求解 每次只考虑交叉路径的子集 开始时路径子集 为空 从剩下的路径中选取误差最多为 的路径加入到 中 开始时路径子集 为空 从剩下的路径中选取误差最多为 的路径加入到 中 当所有的路径都在误差为 的范围内，则迭代结束 2018年11月29日

Pinpointing算法 上述线性规划的解为实数，需要阈值化得到最终的分割结果。保证取整结果满足路径约束的前提下，阈值应该尽可能大。 问题：如何确定阈值？ 求解如下的整数规划问题得到分割结果 2018年11月29日

Pinpoint算法详解 先决条件：实值的优先图，可使用前面的线性规划的解 两个阶段 扩展：目标是满足所有的路径约束 收缩：去除多余的像素 2018年11月29日

实验 平滑项和数据项的定义 数据项中使用了高斯混合对前背景进行建模 50张自然图像 2018年11月29日

实验一 六种方法的相对性能 一元项阈值化 图割 线性规划阈值化 线性规划加Pinpoint 一元项加Pinpoint 2018年11月29日

实验结果 上方为较容易的图例，下方为较难的图例 2018年11月29日

定量的实验结果 Error-22：Graph Cut的分割结果不满足紧致性的22张图像上的错误率 2018年11月29日

实验二：迭代过程 对比GrabCut方法，利用当前的分割结果，更新前景与背景模型进行迭代。 左（上）为GrabCut结果，右（下）为本文方法 2018年11月29日

实验二：定量结果 2018年11月29日

实验：关键参数敏感度实验 错误率（纵坐标）与紧致度（横坐标）的关系，增加紧致性先验以后，分割的错误率下降。 2018年11月29日

问题与讨论 本文的紧致性约束本质上是一种非局部的约束。如何在Graph Cut分割的框架中增加诸如形状，物体位置关系等非局部的先验信息呢？ 如何利用待分割物体不稳定（有噪音或错误）的位置，形状，颜色等信息，更好地分割物体呢？ 2018年11月29日