复制图像块后,为何还须决定边界
一幅织布照片包含许多小范围的线条排列,要逐像素重建并不容易。直接复制一个方形图像块,可以保留方块内的排列;困难却转移到边界:下一个图像块的线条可能出现在不同高度,亮度也可能不同。即使两个图像块各自合理,矩形接合仍会暴露它们的不一致。
重叠区让我们选择何处由原有图像转用新图像块。把重叠像素全部平均,可能产生两道模糊的边缘;沿选定接缝保留两侧的其中一个候选,则有不同效果。本节把接缝选择写成精确的有限模型,并分清三件事:选图像块、为已选图像块选接缝,以及评估完成图像。它们是不同问题。
先前的有限样例模型通过更新共用像素来协调冲突的图像块候选。这里改用明确的二元归属掩码,逐点在两个候选中选一个来复制。以下教学构造连角落规则也完整指定;其数学保证只关于此构造,不会自动证明某张照片的合成结果自然。
图像块位置与重叠误差
定义 1.26.1
(图像块字典、重叠宽度与步长)
由样例图像取得非空有限字典 ,每个图像块为 ,每像素含 个实数色彩通道。字典不暗中包含旋转、缩放或色彩调整;如需要这些变换,必须另行指定变换后的图像块及允许规则。选整数重叠宽度 ,令步长 。
若图像块有 行、 列,且行数与列数均为正整数,左上位置取 ,其中 、。最后图像高度为 ,宽度为 。每行由左至右,完成一行后移到下一行。若想得到较小尺寸,可以裁剪完成的矩形;以下有限分析针对裁剪前的矩形。
定义 1.26.2
(重叠条带与已覆盖集合)
除第一个位置外,以 表示局部坐标中已被覆盖的输出值。覆盖集合 是左条带、上条带,或两者并集:
首行的后续位置只有 ;首列的后续位置只有 ;内部位置两者都有。此结论依赖上述没有缺块的规则扫描次序。内部角落同属两个条带,但仍只是一组像素:
定义 1.26.3
(逐点差异与归一化重叠误差)
对候选 ,定义逐点差异与归一化重叠误差
范数把通道差的平方相加。除以 后是每像素向量的平均平方误差,没有再除以通道数。同一位置的所有候选使用相同重叠集合,因此归一化不改变排名;与其他误差合并时,这个尺度却很重要。第一个位置的 为空,直接定义 ,不要除以零。
确定性合成可在 最小的候选中选字典编号最小者。若希望增加变化,也可在满足 的候选中抽选,其中 须先指定,并记录随机种子。当 且 时,相对容差只容许精确零误差匹配。随机选择让不同运行有变化,却没有因此建立自然纹理的概率模型。
穿过左重叠区的接缝
定义 1.26.4
(可行接缝与接缝代价)
先假设只有左条带被覆盖。接缝是一列列索引 ,满足
每行恰有一个接缝位置,每下降一行最多横移一列,第一列不能绕回第 列。除非明确限制,顶端与底端均可自由选择。固定候选后,接缝代价为
本节的贴入惯例是: 时保留旧值, 时复制 。所以接缝位置本身属于旧图像。把接缝位置分给新图像块也是一种可能惯例,但会改变若干贴入像素,必须交代。
常见错误
(接缝代价既不是整个重叠误差,也不是可见的跳变)
这个代价比较的是相同坐标上两个候选的差异。它既不是整个重叠区的差异总和,也不完全等于完成图像中相邻像素的跳跃。若想优化平滑度或梯度,应另立目标。离散接缝模型的用处,正是提供一个能精确求解及检视的代理量。
定理 1.26.5
(在指定路径类别内求精确最小接缝)
对固定的 有限非负误差阵列,令 ,并对 定义
则 是从首行走到 的可行路径最小代价。完整接缝最小代价为 。在每个状态保存一个达到最小值的前驱,再从最小底部状态回溯,便得到最优接缝。平手时可选最小列索引以便重现。
证明
(动态规划递推式给出精确最优值)
首行每一列只对应一条单点前缀,所以初始化正确。假设第 行的结论成立。任何走到 的路径必从列出的某个前驱列 而来;其前缀代价至少为 ,因此总代价至少为递推式右侧。反过来,选一个达到最小值的前驱。由归纳假设,确实存在一条到达它的最优前缀;加上 仍可行,且达到右侧的值。下界可取到,故归纳得到所有状态的结论。完整路径必在某个底部列结束,取底部最小值便得全路径最优值,保存的前驱构造出达标路径。此论证使用有限状态及每步向下一行的性质,没有依赖尚未决定的未来选择。
证明透视
为何终点足以代表前缀状态
两条在同一行、同一列结束的前缀,拥有完全相同的后续选择。以较便宜的前缀替换较贵者,不会封锁日后的移动;这是递推成立的关键。如果另规定整条路径最多可斜走若干次,只有终点便会遗失必要信息:状态还须记录已斜走的次数。递推式只能证明其状态实际保留的限制下之最优性。
若顶端必在 ,把其他首行列初始化为 ;若底端必在 ,只在 上取最后最小值。禁用位置也赋予无限代价。最后值有限便证明存在可行路径;若为无限,则没有允许路径。使用扩充实数惯例:有限 满足 ,而 。此时归纳叙述为:有限状态有达标路径,无限状态则不可达;允许且有限的前缀可以延伸,没有允许有限前驱的状态则无法到达。这些是边界条件,不是随意引入网格外前驱值的理由。当 时,只有唯一接缝。
命题 1.26.6
(接缝递推式的时间代价)
共有 个状态,每个至多三个前驱。计算全部数值需要 时间;直接回溯需要存储 个前驱。若只求代价,可用两行、即 内存,但重建路径仍须保存决策,或另行指定重算方法。
证明
(统计状态与转移)
每个状态只计算一次,取至多三个已存数值的最小值,并记录一个前驱索引。第 行只依赖第 行,所以只保留两行数值就只需 内存。
上条带可用转置后的相同论证:以 表示每列的一个行索引,满足 、,在 时保留旧像素。
完整二维条带算例
例题 1.26.7
(从两个图像块候选算到实际贴入阵列)
取 、,原有左重叠区十二个位置全为零。灰度候选为
其左重叠误差与累积代价阵列分别为
例如 ,不可使用不存在的第四列前驱。底部唯一最小值三在第二列。回溯得到 ,代价为 。保留旧值的掩码与最后图像块范围为
掩码一代表旧值,零代表新值;未覆盖的第四列必须取自 。原重叠平方误差和为 ,故 ,接缝代价则为三。两个数字分别在不同像素集合上求和,不应把它们报成图像质量改善的百分比。这只是刻意缩小的算术例子,并不是织布合成效果的证据。
反例模式
逐步选最便宜像素,代价可比最优值大任意多
考虑误差阵列
先选首行最小值,再逐行选可达位置中即时误差最小者,会在第一列起步,第二行仍留在第一列。第三行无法一步到第三列,故至少须付 。若平手选最小列,第四行再付 ,总数为 。但 可行且只花一。它确是最优:零代价路径必须依次使用第一、第一、第三、第三列,违反移动限制;其余正数项均至少为一。把每个 换成任意 ,贪心代价仍至少为 ,最优值却保持一。修正方式是在每列保留最好的累积前缀,不是只保留眼前最便宜的移动。
内部角落与完整扫描构造
内部位置若只选垂直接缝,便未处理上重叠区;只选水平接缝也未处理左重叠区。我们采用一个简单且明确的合并规则:针对同一个冻结的旧图像 及候选 ,在完整左条带求垂直接缝 ,在完整上条带求水平接缝 。不要贴完一个条带后才计算另一个。把两者旧值侧的并集保留下来:
其他位置全部复制 。因 、,此规则不会索取 以外不存在的旧像素。又因每个位置只有一个二元决策,角落不会重复写入或含糊平均。
例题 1.26.8
(宽度为一的内部角落)
取 、。两条接缝都是唯一的,,所以
旧图像提供首行及首列, 提供余下 方块。重叠共有五个像素,而非六个。
常见错误
(两条条带最优接缝并不构成最优的角落切割)
并集规则完整指定了贴入,但分别的接缝定理没有证明合并边界在 L 形重叠区上最小化某个共同能量。两条独立路径可能互相影响,或令对方部分边界不再显露。若要全局优化该区域的二元掩码,须先定义掩码能量及边界条件,再为该问题证明算法。不可把这个较强结论暗中加到两个条带结果上。
现在有限拼接程序已可逐步执行:
- 固定字典、、色彩表示、选择规则,以及所用随机种子。第一块按已声明的起始规则选择;不采随机时取最小字典编号。
- 在其后每个扫描位置冻结 上的现有输出,并集像素只计一次,算各候选的 并选一块。
- 在已覆盖条带上求垂直及/或水平最小接缝。只有一条带时使用其旧值侧;两者都有时用并集规则。
- 掩码一的位置取旧值,其余位置取候选值,完成整个图像块范围后前往下一个预定位置。
按贴入次数归纳可知,所有向 索取的值都已存在:它们都在覆盖条带内;新露出的位置则全部由 填满。有限的 次访问后,矩形完整填好。这是终止与像素归属论证,并非能量下降定理。后来的图像块可以覆写先前图像块的一部分;我们没有证明每次贴入都降低某个固定全局目标,也没有搜索所有可能拼接图像。
穷举字典时,每个位置的重叠评分需 ,两条接缝合计需 ,复制需 。取得源图像块、计算特征及加速搜索是另外的工作。
常见错误
(整体重叠最匹配不等于接缝最优)
整个重叠误差最小的候选,不一定具有最便宜的最佳接缝:评分与切割的目标不同。应按下一步实际使用的量来排序,或者说明为什么这个代理量已经足够。
纹理迁移:让第二幅图像引导选择
纯合成希望取得另一幅像源纹理的样本;纹理迁移还希望目标图像引导不同纹理出现的位置。暗的目标区域可以要求暗的源材料,亮区则要求亮的材料。这不会恢复目标物体的真实材质或三维形状,只是限制选定的图像表示。
在输出矩形上指定目标对应场 ,并给每个候选一个相容的图像块对应场 。它们可以是灰度强度、预先计算的低频色彩场,或明确选定的特征。必须交代维数、单位与预处理;若各图像块独立重缩放,可能正好移除了目标想控制的亮度信息。
定义 1.26.9
(对应代价与组合转移代价)
对固定非空集合 及图像块位置 ,使用
一般可取整个图像块作 ;也可以取明确记录、具有有效目标信息的子集。两个误差须有相容尺度,或另有明确权重惯例。 只表示数值系数相同,不会自动表示感知影响相等。
选择 最小者,再完全按前面的规则求接缝及贴入。第一块的 ,在 时由对应项决定; 时全部平手,按起始规则选取。第一块没有接缝。至此得到完整的单次扫描转移程序。接缝本身仍最小化重叠差异,而非对应误差。另外, 评的是候选方案;保留旧像素可能令完成后的图像块范围不能达到该分数。因此,完成图像与目标的符合程度仍须另外测量。
例题 1.26.10
(目标可改变选中的二维图像块)
取 、,内部重叠的三个旧值全为零,候选为
把较小字典编号分给 。其平均重叠误差为 、。这个小例子只在新露出像素使用灰度对应:,该点目标值为三。因此 、,合并代价为 、。当且仅当 时 胜出; 时 胜出;相等时用编号规则。若 ,两者分数为五及 ,故选 。宽一的接缝无选择,保留首行及首列,得到 。唯一新露出位置的目标误差是一。本例指定了实际图像块、目标、评分、接缝及贴入结果,没有从一个像素推断整体结构获得保留。
有限模型留下哪些实际评估问题
接缝代价很低,仍可能在复制图像块较深处出现砖边接错行。大图像块保留较多内部结构,却只有较少独立排列机会;小图像块较自由,但未必容纳一个完整图案。增加重叠使选择更受限,也增加搜索工作。这些取舍不会给出一个通用最佳尺寸。
色彩平方误差受曝光、对齐及色彩坐标影响。亮度归一化可能修复照明差异,亦可能破坏刻意指定的目标亮度关系。模糊后的对应场可以保留大范围明暗,却丢失细轮廓。一个对应标量不会编码语义身份、可见性或几何;即使目标特征精确一致,纹理也可能不合适。
实际评估应交代样例与目标、图像块和重叠尺寸、随机种子,展示全图及接缝、长结构的局部放大,并比较相同设定下的多次运行。要隔离切割决策,可固定图像块候选,比较矩形贴入与接缝贴入;要隔离目标项,可固定字典,比较只用重叠与加入转移分数。应用已声明的特征提取器,在完成图像上测量对应误差,包括保留的像素,并说明指标没有测量什么。这些是建议的评估控制,不是本节已完成的实验。上述数值结果都没有证明自然图像的质量。
习题
快速检查
(设 、。求步长、两行三列图像块的图像尺寸,以及内部位置的重叠大小。解释为何须扣除角落。)
解答 · 答案
步长为 ,高为 ,宽为 。每个条带有十像素,分别相加却把 角落计了两次。因此并集有 像素。若直接相加两条带分数,便会额外加重角落权重,除非本来就明确想这样做。
快速检查
(对 、、各行依次为 、、 的左条带误差阵列,计算全部动态规划值及一条自由端点最优接缝。再把顶端限制在第一列、底端限制在第二列,重做计算。)
解答 · 答案
自由端点的累积阵列为 。底部第一列以一达到最小值;回溯得到 ,代价 。限制顶端后,首行是 ,第二行 ,第三行 。底端再限制于第二列,得到代价五及路径 。自由端点的一不可用于受限问题,边界限制确实改变了问题。
快速检查
(解释按整个重叠误差选图像块,为何不同于按最小接缝误差选图像块。用三行两列左条带误差(、)验证: 的每一行都是 , 的每一行都是 。)
解答 · 答案
的重叠误差和为 ,但第一列直线接缝代价零; 的误差和为六,任何完整接缝均花三。取平均只把两个总数同除以六,因此平均重叠排名仍选 ;最小接缝排名则选 。在 图像块内取全零旧重叠,左两列候选值等于各误差的平方根,便可实现这些条带阵列;第三列任意。任一排名都没有交代重叠外的图像块内容。
快速检查
(对横移加入非负惩罚 。推导递推式并解释所需状态。在主要四行算例中,证明 时, 比原本最优的 更便宜。只比较这两条路径足以证明常列路径全局最优吗?)
解答 · 答案
初始化不变,递推为 。当前终点仍决定所有允许的下一步及转移代价,所以前缀替换证明仍成立。 时,折线差异三,加三次横移,总代价十二;第二列直线为 。只比较两条路径不能证明全局最优。实际递推四行为 、、、,所以常列路径确实达到全局最小值十,但不是唯一最优。另一条最优路径为 :差异七加一次横移惩罚三,亦得十。第二行第二列的第一、第二列前驱平手,所以最小列前驱规则会回溯出后一条路径。
快速检查
(在转移算例中,把较小编号分给 。求 、、 时的选择及贴入结果。解释为何使用全部四个目标像素是另一模型。)
解答 · 答案
时只看重叠,选 ;唯一复制的内部值为零,所以结果全零。 时对应项选 ,得 。 时分数同为 ,以较小编号选 。在全部四个像素上定义对应误差,须另外提供四个目标值,且把其中三个由旧图像保留的像素纳入评分,一般会改变分数及分界。不能由题目仅提供的一个目标值杜撰其余数值。