Lazy Snapping的基础：Graph Cut
Lazy Snapping的基础：Graph Cut
Graph Cut技术是图论中的一个概念，也是Lazy snapping这款软件的核心技术。在软件的第一步和第二步操作中，对前景的轮廓计算和对细节部分进行修补的操作，都是基于该技术进行的。
首先，当一张图被导入到Lazy snapping中时，软件会自动采用一种被称为“水线（watershed）”的算法对该图进行处理。
所谓水线，通俗地说，就是把一张图像的梯度图想像成为一片凹凸不平的山地，其中，颜色变化小的区域就是山脊，而颜色变化剧烈的区域就是山洼。我们知道，每一个山洼周围必然都是一圈山脊，如果在每一个山洼的最低点打一个洞，然后通过这个洞向山洼里注水，则经过一段时间之后，相邻山洼里的水必然会越过山脊连接到一起。两个山洼之间的水连接在一起的这条线，就是水线。通过这些水线，软件就可以把图片分为大小不等的若干“碎片”。我们可以注意到，每一个区域中的颜色基本上都是相同的。
为什么要先对图片进行“水线”处理呢？因为我们知道，在计算机中，每一幅图都是由无数个像素点构成的，当软件需要分辨出图像的前景和背景时，就需要对图像中的所有像素点进行分析，这样一来工作量会成立方级数增加，大大减缓处理的速度。而采用了“水线”处理之后，图像中需要分析的就是那些被分割出的区域了，其数量比像素点要少数十倍，从而大大加快了软件的处理速度。
接下来，就该是用户需要做的工作了——通过划线，告诉计算机哪些是我们想要的前景，而哪些是我们不想要的背景。如果从像素点的角度来看，一旦我们在图像上画了一条线，则这条线经过的像素点被我们称为“种子点”，这些“种子点”所涉及到的区域，则被称为“种子区域”。接下来，我们就需要借助这些“种子区域”将图片分为“前景区域”和“背景区域”两大块。利用Graph Cut优化算法，图片上所有区域会被赋予惟一的属性，不属于“前景区域”就一定会属于“背景区域”。
在经过“水线”处理后的图片中，我们把相邻的区域连接在一起。而接下来Graph Cut优化算法要做的，就是尝试将每个非“种子区域”分别与“前景区域”（或“背景区域”）之间的通路“打断”。如果全部通路都可以被打断，则软件猜测该区域不属于“前景区域”，反之则可能属于。这样，经过一番运算后，软件就可以将图形分为“前景区域”和“背景区域”两大部分了，也就将我们所需要的前景的大致轮廓勾勒了出来。
Graph Cut 优化的准则，考虑了每一个区域的颜色与种子区域之间的颜色相似性，颜色越像“前景区域”就越可能被分在前景。同时它也考虑了相邻区域的颜色差别，颜色差别越大这两个区域越可能被分开。这个优化问题可以用图论中极大流（极小割）的方法很快解决。
对于一张结构较为简单的图形来说，如果其前景和背景的对比非常明显，且前景的形状较为简单，则经过前面的处理后，前景图形就已经被“抠”出来了。不过，如果图片的内容较为复杂，且前景和背景之间的对比度不是很明显的话，则需要对图片进行进一步的微调。
所谓进一步处理，其实就是将前景与背景之间的“边界”清晰地确定下来。由于在此之前我们已经确定了前景的大致轮廓，因此在这里我们只对前景和背景相交处的边界附近进行处理，也就是已经确定好的“前景区域”和“背景区域”之间的那一块地带。
要说明的是，在前一步操作中，软件通过“水线”算法将图像分为一块块区域以加快处理的速度。而现在，由于要对图像的边缘部分进行调整，软件处理的对象又变成了像素而不再是区域，以满足处理精度方面的要求。
网友评论