以路径选择缩放图像
均匀缩小图像会压缩所有内容,包括可能希望保留的特征。内容感知方法可以移除一条相连的像素路径,称为接缝,同时尽量避开视觉上重要的区域。方法依赖分配给各像素的能量:总能量低只是一个数学目标,并不保证被移除的内容对观看者不重要。
定义 10.1.1
(垂直接缝及其能量)
设图像有 行、 列。这里先为每个像素固定一个有限实数 ,其中 、。一条垂直接缝在每一行选一列 ,且相邻两行满足 。其能量为 。选出接缝后,在每一行分别删除所选像素并合拢该行的空位,得到的矩形图像有 行、 列。
能量可以使用局部图像差分、用户提供的保护蒙版,或二者结合。不同选择会得到不同的接缝。本节假设整张能量表已经固定,不假设像素能量能够完美表达对象的含义,也不假设缩放之后能量仍然有效。
动态规划与证明
定义 10.1.2
(累积接缝成本)
终止于像素 的接缝前缀,是一组列 ,满足 。令 为 在所有这类前缀上的最小值。到第一行的前缀只有一个像素,故 。
定理 10.1.3
(接缝递推式)
对 ,
垂直接缝的最小能量是 ;从使它最小的最底行列出发,沿最小前驱回溯,就得到达到此值的接缝。
证明
(按行归纳)
令 。在图像边缘,这个集合只包含实际存在的列;不会悄悄地把图像之外的像素当作零成本。
终止于 的有效前缀,其前一个像素是某个 对应的 ,去掉最后一个像素就得到终止于 的有效前缀。反过来,任何终止于 ()的有效前缀都可以延伸到 。
上界:在终止于最小化 的最小成本前缀后面加上 ,得到成本为 的前缀,所以 不超过这个值。下界:对任何终止于 的前缀,去掉最后一个像素后得到某个 的前缀,其成本至少为 ,因此原前缀的成本至少为 。于是等式成立。完整接缝就是长度为 的前缀,所以最小接缝能量是 。从取最小值的最底行列开始,每一步都取最小前驱,得到的接缝能量恰为 。
即使能量为负,这个证明依然成立,因为每条完整接缝恰有 个像素,而逐行的有向图没有环。
证明透视
为什么递推式只需要最后一个像素
证明用到三个事实。前缀的成本是一个和,因此去掉最后一个像素恰好减去 ,不牵涉其他项,上下两个界都由此而来。相邻条件只联系相邻两行,所以延伸前缀的方式只取决于它的最后一个像素,与如何到达无关;这就是最优子结构这一步:到达 的最佳方式包含到达其前驱的最佳方式。最后,能量是固定的数值,不随所选接缝而变。如果目标的成本依赖前缀中不止最后一个像素的部分,或者能量会随接缝改变,论证就会失效。负值没有影响,因为每个候选恰好有 项。
要读出接缝,为每一项保存一个取到最小值的前驱;从最底行取最小值的列出发,沿指针向上,再把列号的顺序反转。若候选值并列,任取一个最小值对所述目标都是最优的;若实现需要确定的输出,必须明确规定并列时的取舍规则。单行也是有效的特例:选该行中能量最小的像素,不需要前驱步骤。
概念视角算法
接缝是分层图上的最短路径
为每个像素建立一个节点,只要 ,就从 向 连一条边,并让每个节点带有权重 。再加入连向第一行的源点和从第 行连出的汇点,有效接缝恰好就是从源点到汇点的路径,接缝能量是路径上权重之和。这个图没有环,所以即使有些权重为负,也可以按行的顺序计算最短路径,而 就是到节点 的最短路径长度。
一个诱人的捷径是不理会这个图,逐行独立地选取最便宜的像素。相邻条件恰好禁止这样做。
反例模式
逐行选最便宜的像素不是接缝
取 、,第 1 行能量为 ,第 2 行为 。最便宜的像素在第 列和第 列,总和为 ,但 ,所以这不是接缝。有效接缝为 ,能量依次为 ,因此最小值是 。即使改用“从最便宜的顶部像素出发,每步走向较便宜的邻点”这一修正规则,仍可能失败:第 1 行为 、第 2 行为 时,它选第 1 列,再走向成本为 的邻点,能量为 ;而 ,从第 2 列或第 3 列出发即可达到。局部选择不能代替递推式。
表格例题
例题 10.1.4
(四行表格上的累积成本)
对下面这张固定的能量表,逐行计算累积成本:
| 行 | 第 1–4 列的像素能量 | 第 1–4 列的累积成本 |
|---|---|---|
| 1 | 4, 2, 4, 7 | 4, 2, 4, 7 |
| 2 | 6, 1, 5, 4 | 8, 3, 7, 8 |
| 3 | 2, 4, 1, 6 | 5, 7, 4, 13 |
| 4 | 4, 3, 2, 3 | 9, 7, 6, 7 |
例如第 3 行第 1 列只用到第 2 行的第 1、2 列,所以成本是 。最底行的最小成本是第 3 列的 。回溯得到自上而下的列号 ,能量为 。这张表说明,在这些固定能量下,该接缝在所有有效垂直接缝中最优;一般而言,逐行独立地选能量最小的像素并不能保证满足相邻条件。
例题 10.1.5
(两条最优接缝并列)
取 、,第 1 行能量为 ,第 2 行为 。第一行的成本为 。第 2 行第 1 列只有第 1、2 列可作前驱,所以 ;;。最小值 出现在第 1 列和第 3 列,得到两条最优接缝,列号 与 ,能量都是 。两者对目标都是最优的,所以程序必须按明确的规则取舍,例如取列号最小者。两个边缘列都不会去查第 列或第 列。
例题 10.1.6
(移除接缝后再重复)
从上面的四行表格中移除接缝 。保持其余能量不变,新的各行为 、、、,共 列。在这张固定表上重复该算法,累积成本为 、、、,所以下一条接缝的能量是 。实际应用中,新图像的能量会重新计算,因为被接缝隔开的像素现在已经相邻;上表只是这一步在能量不变时的版本。
效率与目标未涵盖的因素
命题 10.1.7
(接缝算法的时间与空间)
计算所有成本 需要 时间。若只需要最小值,两行成本只需 空间;若按上述直接方法重构接缝,每格保留一个前驱,则额外需要 空间。输出接缝本身需要 空间。
证明
(数格子与保留的行)
共有 个格子,每格最多检查三个前驱,所以需要 时间。第 行只用到第 行,所以不保存前驱时只需保留两行成本。每格一个前驱共 个值,而最后得到的接缝每行一列。
边界与并列时的取舍必须前后一致地记录。
常见错误
(把不存在的邻点当作免费)
取第 1 行能量 、第 2 行 。像素 只在第 1、2 列有前驱,所以 。如果给不存在的第 列赋成本 ,公式会得到 ,比任何经过 的接缝能量都小,因为它们都要经过第 1 行,而那里的能量至少为 。只有实际存在的列才能进入最小值。
若要移除多条接缝,可以每次移除一条,更新图像和能量表,再重复。初始宽度为 时,在每一步宽度至少为二的条件下最多移除 条:移除 条之后宽度为 。每次迭代只解决当前这张固定表的问题;这本身并不能证明所得序列对另行定义的多次移除目标是全局最优的。重新计算局部能量也可能使每次移除后的目标发生变化。只累计原像素能量的目标,没有明确计入移除接缝后新相邻像素之间产生的不连续。更复杂的目标可以加入这些成本,但其递推式及假设必须另行推导。
低梯度或低指定能量的路径仍可能穿过人脸、文字或有意义的直线边缘。蒙版、感知准则和人工检查可以减少部分失败,但都不能证明语义一定被保留。交换行与列的角色即可处理水平接缝;这是另一种路径方向,而不是原封不动地使用同一条垂直接缝。
练习
快速检查
(若 且能量行为 ,给出一条最小接缝及其能量。递推式如何避免去要求不存在的前驱?)
递推式用于哪些 值?
解答 · 答案
最小接缝是第 列,能量为 。只有一行时只用到 ,而递推式只对 使用,所以不会要求任何前驱。对 ,最小值只在实际存在的列上取。
快速检查
(给出一个至少三列的两行能量表,使逐行独立地选最便宜的像素违反相邻条件。)
把两个最便宜的像素放在相隔两列的位置。
解答 · 答案
取第 1 行为 、第 2 行为 。最便宜的像素在第 列和第 列,总和为 ,并不是接缝。递推式给出 、、,所以每条有效接缝的能量至少为 。
快速检查
(为什么重新计算能量并重复单接缝算法,本身不能证明对多接缝目标全局最优?)
比较每次迭代所优化的对象与多接缝目标所累计的对象。
解答 · 答案
每次迭代只对当前这张固定表最优。移除接缝会改变图像,所以下一张表的能量和相邻关系都与原来不同,而逐次单接缝最优值之和,并没有被证明是任何定义在整个序列上的目标的最优值。全局结论需要另行定义目标并另行证明。
快速检查
(对各行为 、、 的能量表,计算累积成本并求一条最小垂直接缝。)
先填第 1 行,再利用上一行中实际存在的列逐格计算。
解答 · 答案
第 1 行成本为 。第 2 行:,,。第 3 行:,,。最小值是第 1 列的 ;回溯得列号 ,能量为 。