14. 切割图像 - 智能剪刀(Intelligent Scissors)

在讲述图像合成与图像融合时，我给大家介绍了一种直接剪切粘贴(cut-and-paste)的方法，只需要简单的从原图中抠出想要的物体，并按照一定的顺序叠放在一起，就可以构成一幅看起来挺不错的融合后的图像。

我还提到即便是像Alpha融合这类方法，也依赖于准确的抠图。那么问题来了？我们如何才能从图像中抠出想要的物体呢？

对于这个问题，其实有两种思考方式：

第一种，是通过在图像中寻找物体与物体之间的接缝来完成。只要能知道准确的接缝线，就能将沿着接缝线切割图像从而抠出想要的物体。这里我们将这个过程称为Finding Seams。

第二种，是认为这是一个分割问题，这需要我们对每个像素进行分类，前景像素是一类，背景像素是一类。英文称之为Segmentation。

在接下来的几篇文章中，我会通过介绍几篇经典的论文，从而让你看到Finding Seams和Segmentation的典型算法，还会让你看到一些很精彩的应用。

今天我首先给大家介绍的是一个早在1995年就诞生的方法：Intelligent Scissors，它后来成为了PhotoShop中的标配功能：智能套索。所参考的论文主要有如下两篇：

[1]Intelligent Scissors for Image Composition, Eric N. Mortensen, 1995

[2]Interactive Segmentation with Intelligent Scissors, Eric N. Mortensen， William A. Barrett, 1998

我看到这文章时不禁感叹，虽然随着深度学习的大力发展，从图像中抠出目标已经有了很先进的方法了，但原来在甚至早在二十多年前作者作为领域先驱就已经将问题想得这么透彻并给出了这么细致的解决方案，甚至后来直接成为Photoshop的标配功能，而那个时候个人电脑在全世界范围都还是稀罕的东西，想想1995年微软也才推出Win95，那时候PhotoShop还是非常早期的版本，连Photoshop CS品牌都还不存在（PhotoShop CS第一版于2003年发布，是PhotoShop软件的第8个主要版本）。而作者在论文[2]里面提到的实验平台HP 735/99最高主频才99MHz（见下图）。今天再认真读这样的经典论文不能不让人震撼。希望我的文章也能给你带来这样的感觉。

HP 735/99

1. 什么是Intelligent Scissors（智能剪刀）?

首先让我们直观的看一看什么是智能剪刀，我想大家一看到下面的视频就会感到很眼熟。

智能剪刀Intelligent Scissors

是的，是不是跟PhotoShop中的智能套索很像？我贴一个PhotoShop中的智能套索给你看看：

PhotoShop中的智能套索

是的，智能剪刀可以让用户只需要选择一个接近目标边缘的种子点，然后不停的移动鼠标沿着物体边缘移动，然后就可以自动的得到紧贴目标边缘的Seam(缝合线）。

在此论文发表时，全自动的图像分割还是一个尚未解决的问题（即便是当下，也还未完全解决），而手动的跟踪绘制图像上目标物的边缘则非常费时费力，智能剪刀可以使用鼠标使用简单的手势动作快速准确地提取图像中的目标物体。当鼠标位置靠近物体边缘时，该算法可以计算出一条“Live-Wire（我直译之为活线）"捕捉并包裹感兴趣的物体。

2. 基本原理

现在让我们想象，如果是你来思考这个问题，你会怎么做？

恩，首先你需要一个界面，允许用户查看图像，并且用鼠标选择一个种子点，这个似乎好办。不过想想Live-Wire相关论文发表在1992年，又不是那么容易了?

然后，你的用户移动鼠标。光标的位置和种子点之间有千万条路径，你的算法需要计算出最能够紧贴目标物体边缘的那一条。像下图一样(光标沿着白线从种子点移到了画面下方的端点，而你的算法却需要计算出黄色的紧贴物体边缘的曲线）

那么黄色曲线上的点有什么特征呢？

1. 它们在物体的边缘上
2. 它们的梯度幅度比较大，不是噪声
3. 曲线比较平滑，不会剧烈波动

你需要把所有这些特征组合在一起用于描述黄色曲线上的点。你需要从图中的Free Point到Seed Point的无数条路径中寻找一条路径，它符合上述特征的点的数量最多。你要把这条路径上的点组合在一起形成一个列表，从而形成一条完整的曲线。

看起来给人一种既简单又复杂的感觉。那么作者是如何看待这个问题的呢？事实上，作者是将图像看做”图(Graph)“，并将此问题看做在图中做种子点到光标点之间的最短路径搜索的问题。下图中，种子点位于End处，光标点位于Start处。每个像素是一个节点，而节点之间的连线(Link)具有一定的代价(Cost)。Intelligent Scissors就成了一个寻路问题，要求找出路径上累积代价最小的那一条。作者采用的是非常经典的Dijkstra寻路算法。

智能剪刀把该问题看做寻路问题

3. 链路代价的计算

当建立了第2节所述的模型后，我们可以知道智能剪刀算法至少包括两大关键点：

1. 建立代价图
2. 寻路

我们来看看作者是如何做到的。

作者认为，由于最小代价路径应对应于物体边界，因此具有强边缘特征的像素（或更准确地说，相邻像素之间的链接）应具有较低的局部代价，反之亦然。因此，局部代价是从各种边缘特征创建的：

于是，可以用下式描述从一个像素点p到另外一个像素点q的局部代价l(p,q):

其中每个因子都有自己的权重，这可以根据具体的图像应用来配置，而作者咋论文里面提到他们的实验结果表明

可以适用于很多图像。

下面我仔细介绍下每个特征代价

3.1 拉普拉斯过零点代价

作者采用拉普拉斯过零点特征是为了确保像素节点位于边缘点上，尽管1986年Canny算子就已经发布，但似乎作者并未采用。

回顾我在数码相机内的图像处理-基本图像滤波中所讲的，图像的二阶导数可以由图像与拉普拉斯核卷积所得到，当其结果过零点时可以说明中心像素位于边缘上，因此应该具备”低代价“，反之亦然。所以作者定义：

其中，

表示图像I上像素点q的拉普拉斯。

然而，由于图像是离散的，拉普拉斯真正为0的像素点非常少，直接这样做就找不到很多边缘点了。所以作者认为在如果两个像素点的拉普拉斯值符号相反，那么它们之间有一个过零亚像素点。于是就会选择两个像素点中离边缘最近的点作为实际计算中的过零点。通过这样的折中，就会得到图像上的单像素边缘曲线。

3.2 梯度幅值代价

这个就比较简单了，如果Ix和Iy分别是x和y方向上的梯度，那么首先梯度幅值为：

为了表明梯度幅值大的点具有低的代价，梯度幅值小的点具有大的代价，要对G进行反相，于是代价值

可以表示为：

这里max(G)是整个图像里面梯度幅值的最大值。

3.3 梯度方向代价

添加梯度方向代价的主要目的是要使得

1. 当两个像素具有相似的梯度方向，但是该方向却和它们之间的连接的方向接近垂直时给予高代价
2. 当两个像素具有相似的梯度方向且和它们之间的连接的方向一致时，给予低代价

于是作者论文[2]中的定义为：

我从论文[2]中截取了作者的例子，可以让各位更直观的理解fD的定义：

4. 寻路

当有了局部代价l(p,q)后，就很容易利用Dijkstra寻路算法了。在我正式阐述作者的算法时，先让我们看看一般性的最小代价路径的动态规划求解法的一个简短介绍，这视频我觉得讲的太清楚了，完全不用我再多费笔墨^_^：

我们的作者将在论文中列出了算法的说明如下，论文中此算法称为"Live-Wire 2-D dynamic programming (DP) graph search algorithm”

好了，让我们看看作者列出的实际例子，这个例子中为了简单起见忽略了链路特征，只展示了仅梯度幅值时的寻路算法：

种子点被圈住，接下来不断对种子点的邻域进行扩展操作，进而改变上述算法中的活动列表L。注意在此过程中，位于中心点的对角线上的原cost值需要乘以

来表明距离的影响，大家可以仔细对照上面的公式看看。

算法持续迭代，到L中没有元素时停止：

此时以种子点为起点循着最小代价路径就得到了最小代价路径。

5. 更多细节

上述信息看起来还是比较直观易懂的，但实际上作者实现的Intelligent Scissors还有更多重要细节，远比我这里描述的要更深入，如果大家去读论文[2]时会更有体会，有少部分段落看得我很抓狂，感觉太复杂了。

1） 为了能够实时显示新计算出的路径，因此第4节提到的寻路算法要运行非常的快（想想我在一开篇提到的作者用的电脑）。因此需要寻找高效的寻路算法实现，特别是其中活动列表中的元素需要按照代价值排序。作者在论文[2]中提到“The active list is sorted with a specialized O(N) bucket sort ”，即使用了高效的桶排序。

2）实际使用中运行用户点击鼠标选择新的种子点，种子点之间由上述算法自动算出最佳路径。但这个过程对用户来说也是繁琐且容易出错的，例如用户可能在偏离边缘的地方点击鼠标。于是就有自动光标位置调整功能（Cursor Snap）, 当用户移动鼠标时，自动将光标调整到邻域里面的梯度幅值最大点，帮助用户更好的定位目标边缘。

3）为了让用户尽可能少的去选择新的种子点，还有一个很酷的功能叫做“路径冻结”(Path Cooling)。我们知道从当前光标位置到种子点只可能有一条最佳路径，但是当光标移动时有很多条最佳路径到种子点。这些路径之间有可能有重合的部分。因此当用户移动鼠标时，系统会记录重合的路径。如果一条路径片段在一段时间后（不论用户如何移动光标）都没有改变，那么此路径就会冻结。路径的端点会被设置为新的种子点。接下来的路径计算就会基于新的种子点来。

4) 在线学习: 有时候语义或视觉上的边界并非是强边缘，例如下图中的左心室图。可以看到(c)图中算法跟踪到了具有强梯度幅值的外边缘，而非原本想要抠出的内部边缘。

如果引入在线学习，算法会根据当前曲线之前的少量像素的特征来推断新的边界像素的特征，从而给不同的“新”像素赋以不同的代价，因此像(d)图一样可以得到更好的边界结果。

6. 变种

原论文如此经典，因此早年间很多学校的课程设计都会选择它作为给学生的挑战。我查找过程中发现，可能是由于原论文的特征过于复杂，因此一些教授对此作了轻微的变化。例如华盛顿大学2009年CSE455课程就以此作为课程项目：

Project 1: Image Scissorscourses.cs.washington.edu

这个项目在计算链路的代价时选择了可以用卷积来实现的方式，因此更加的直观易懂。还有一些人在此基础上作了很好的解释，参看这里：

https://medium.com/@saniyazaidi14/intelligent-scissors-for-image-composition-an-amateurs-explanation-9b75bd97b65cmedium.com

7. 总结

今天介绍的智能剪刀(Intelligent Scissors)是我们接触到的第一个寻找图像中目标与非目标之间的接缝的算法，其中使用到了多种边缘代价来提高鲁棒性，还使用到了动态规划来求解最佳路径。其中的思想即使到现在也并不落后，这些思想相信在一些领域依然有用。希望我今天的介绍能给你启发。

我们接下来还会看到更多Finding Seams相关的应用，敬请期待。

8. 参考资料

[1] Intelligent Scissors for Image Composition, Eric N. Mortensen, 1995

[2] Interactive Segmentation with Intelligent Scissors, Eric N. Mortensen， William A. Barrett, 1998

[3] CMU 2017 Fall Computational Photography Course 15-463, Lecture 8

[4] Sartorial Adventures with Image Scissors

[5] Intelligent Scissors for Image Composition: An amateur’s explanation

[6] Intellegent Scissors Interactive tool for image segmentation

[7] Minimum Cost Path Dynamic Programming

[8] HP 735/99

[9] Demo of Intelligent Scissors

[10] Demo of Magnetic Lasso Tool of PhotoShop