[CS131] Lecture 9 Image Resizing and Segmentation
根据 Stanford CS131 课程写的笔记(大部分为 note 翻译),英语水平一般,如有错误请评论指正
Lecture 9 Image Resizing and Segmentation
Introduction
为了适应不同尺寸和形状的播放器,图片或影片需要调整大小,本章介绍如何在调整大小的同时保存重要内容并减少瑕疵。
Problem Statement
输入大小为的原图,输出大小为,能很好代表原图的新图像。我们希望:
- 新图要能符合设备几何限制
- 新图要展现重要内容和结构
- 新图要减少瑕疵
Importance Measures
-
用函数来确定图像中的重要部分,再用一些操作来改变图像。如下图
除了函数方法,还有注意力模型之类更精巧的方法。
Seam Carving
Basic Idea
人类视觉对边缘更加敏感。因此一个简单而有效的方法是使用基于梯度的能量方程,将光滑区域的内容移除并保存信息量更大边缘。能量公式定义为
不重要的内容即为能量公式值较小的像素。
Pixel Removal
下图从左至右用了三种不同的像素移除方案:
- 移除所有低能量像素
- 移除每行最低能量像素
- 移除每列最低能量像素
可以看出第一、二种方法破坏了原图,而第三种方法较前两种好,但仍有大量瑕疵。
A Seam
-
缝被定义为从头到尾(或从左到右)连接像素的通道。对于从头到尾的像素,我们需要从每列钟选取一个像素,数学定义为:
-
最好的缝是基于像素梯度,能够最小化能量函数的缝。
-
可以用递归关系找到最佳缝。如果定义为经过像素的缝的最小能量代价,那么其递归关系为:
该递归关系可以通过的动态程序解决,再原始算法钟。下面为一个图像的能量函数值递归关系为
-
为了找到最佳缝,我们引入回溯法。从底层能量函数值最低的像素开始,往上发展。
Seam Carving Algorithms
算法耗费,每个循环更新耗费。如果要垂直调整大小,可以旋转图片用同一算法。
图像的平均能量会随着缝剪裁算法移除低能量像素而提高。当调整大小时,我们需要移除横向和纵向的缝。如何动态同时删除横竖的缝?参考 SIGGRAPH 论文,利用再循环方程
同时剪裁横竖缝,得到更多信息。
Advanced Seam Carving
Image Expansion
用相似的方法,我们可以提高图片大小。最原始的方法时迭代地找到能量最低的缝,并复制它们来拓展图片。但是,这种方法会形成下图:
注意图像右侧看起来很不自然,这是由于每次算法找到的都是同一条缝,导致同一条缝被复制多次。更有效的方法是一次性找到能量最低的条缝,并复制它们,如下图:
这样形成的图片更加自然。注意这种方法只能以 2x 来放大图像(没有足够多的缝进行放大)。
Multi-Size Image Representation
实际中,许多图片会储存在它们缝的表示的旁边,使得图片更容易调整大小。这些缝表现和图片规模大小一致,但是它们不储存像素强度,而是由多条能量从低到高、路径排序的缝组成。注意为了一次性计算多条缝,图像的能量在模拟每条缝的移除后必须重新计算。下图是缝表示的一个例子:
有了右图的表示,可以轻松的移除条缝,只要移除右图对应标签为到的像素。
Object Removal
通过让用户指定图中物体能量的高低,我们可以保护或移除特定的物体。如下图,红色为保护,绿色为移除物体。
Limitations
当图片大小放生巨大变化时,效率的上下限。
-
图中物体的重要特征可能是低能量的,导致缝误移除。如下图
我们可以看到一些光滑平整的区域虽然梯度小能量低,但对图像十分重要,却会被算法误移除。为了解决这个问题,我们需要通过考虑更多的因素来改变能量。例如:用面部探测或者用户约束,如下图。
Forward Energy
如上文提及,缝剪裁会导致图片平均能量上升,产生锯齿状边缘。改进的方法是,不考虑移除最低能量的缝,而是移除插入最小能量到图像的缝。移除一个像素会有三种新的边缘情况,这些新边缘花费为
这种方式称为”forward energy”,之前的方法称为”backward energy”。forward energy 通过最小化添加的能量,保留了光滑的边缘。
Seam-Carving in Videos
比起图像,视频剪裁难度更大,有以下几个问题。
第一,时间问题。一个 30fps 的视频,一分钟有 1800 帧,利用缝剪裁每帧处理至少需要 30 小时。
第二,视频连接问题。视频的帧与帧之间是逻辑连续的,而人眼对移动又特别敏感,使得逐帧剪裁的视频产生失真现象。稍改进后的方法是,将视频当作一个 3D 空间,每个垂直面作为视频的一个图像。从而可以找到整个视频上能量最低的 2D 缝。剩余操作与 2D 剪裁相同。
Segmentation
我们有多种原因想让计算机可以切割图像。我们可能需要将图像切割成和现实世界中一样,多个相邻的物体组成。
我们可能想将图像基于附近的像素是相似的切割成多组。我们将这些组称为超像素 (superpixels)。超像素允许我们将一些独立像素视作一体,因此使得一些计算更快。如下图。
各种形式的图像分割帮助我们将一组像素视作一个特征,并从中得到图片信息。切割还能帮助图像效果,像背景移除。
为了解决如何切割图像问题,我们将切割当作聚类。聚类让我们将相似的数据点聚集并用一个值表示它们。我们需要解决两个问题:
- 如何确定两个像素、批 (patch)、图像是否相似?
- 如何从成对的相似处中计算整体的分类?
通常有两大类聚类算法:自上而下、自下而上。自上而下将像素和 patch 分类到一起,因为它们依赖于同一视觉实体。自下而上算法将像素分类到一起,因为它们局部相邻。
我们还可以用人类识别物体的特定视觉规律来作为聚类算法。例如:相似物体、对称、共同命运、接近度等等。共同命运指一组物体似乎会被一起移除,所以他们有共同的命运,如下图。
接近度指将物体和它们接近的物体分在一组。如下图中的三个人。