动机
一小张石面照片包含局部纹理信息:相邻强度模式、重复边缘和特定色彩组合。若想把它延伸,直接重复整张照片会暴露长方形周期。另一做法是重新安排较小图像块,同时要求重叠部分相容。这是很具体的数据驱动合成:局部候选来自量得的样例,而非石头的解析方程。
“数据驱动”并不取消模型选择。我们仍要定图像块大小、色彩表示、相似度、输出约束及搜索程序。重叠吻合的图像块,可能在应延续水平结构的位置放一条垂直裂纹。反过来,要求每块完全等于来源样例,也可能因邻块互相冲突而不可能。有用的模型应显示取舍,而不是用一幅漂亮结果遮盖它们。
以下刻意建立有限模型,使算法有精确终止证明,也可以手算完整执行。它不是完整现代纹理合成器,更不是所有图像类别的统计模型。其教学价值在于分清最近邻选择、重叠提议的协调,以及目标值下降与图像可信之间的距离。
定义
定义 1.27.1
(含观测值的有限样例能量)
为清楚起见,用固定有限网格的灰度输出 ,每值属有限非空字母表 。位置 的提取器 选出 个像素。有限字典 来自指定样例图像块,字典值未必穷尽输出字母表。彩色版本以向量代标量,且须明定色彩距离。
标签 指定该位置选哪个字典图像块。已观测位置集合为 ,值为 ,取 ;另可把集合 内像素硬性固定为字母表中的指定值。定义
这是优化目标,不自动是概率或校准感知评分。它要求输出图像块接近字典成员,并让已观测像素抵抗变化。硬性固定与有限惩罚不同:即使改动固定像素能减少图像块误差,也不允许改。
定义 1.27.2
(消去标签后的能量)
消去标签,得到
对当前图像,每个图像块各选最近邻;重叠像素再把这些决定耦合。独立复制的候选不一定相容,整体目标也没有因此变成凸函数。
定义 1.27.3
(系数与提议总和)
固定标签后, 是像素 出现于各图像块的次数,若 再加 ; 是所有字典图像块在该位置的提议值总和,若有观测再加 。这些系数逐项计算目标中的每次出现。假设单一提取器内没有重复同一像素,不同图像块共享像素则正是模型核心。
定理 / 命题
定理 1.27.4
(精确坐标更新是最近图像块与最近平均值决策)
固定 ,最小化一个标签等于搜索 的最近字典图像块。固定标签和其他像素后,非固定像素若 ,应选最接近 的字母表值;若 ,其值不影响目标。结论针对此平方误差模型,遇平手不宣称唯一。
定理 1.27.5
(有限模型的严格坐标下降必会停止)
按固定次序反复访问每个标签及非固定像素。只有精确最小化能严格降低目标时才更新;平手保留当前值。则状态只会改变有限次。一整轮没有变化时,当前状态是逐坐标极小值,但未必是全局极小值,终止也不证明知觉质量。
此终止论证必须使用有限字母表。若强度连续,目标下降且有下界,可以让能量值收敛,却未必有限步停止。近似最近邻搜索也不自动保留精确逐坐标最小性。仍可在验证下降后接受提议,但停止时能宣称的性质需要相应减弱。
证明思路
证明
(标签与像素的精确更新)
一个标签只出现在 ,所以更新就是有限最近邻搜索。把涉及像素 的项收集起来,忽略与它无关的常数; 时为
因此最佳允许值最接近加权提议平均。这是协调多个提议,不是说平均值本身属某个字典图像块。硬性固定像素无论系数如何,都排除在更新之外。
证明
(严格改变只有有限多次)
可行图像与标签状态至多 个。每次改动严格下降,故不能重访状态,总改动次数至多为状态数减一。这个界可以极大,只是正确性论证,不是高效最坏情况保证。一整轮不变时,每个坐标都在同一固定状态下受检查,因此没有单坐标严格改善。
证明透视
平手保留现值为何重要?
不同状态可以有相同能量。若求解器不断在同样好的标签间切换,有限状态本身不能排除循环。平手不动,才使真正改动都有严格进度量。浮点程序还要交代比较规则;容差会改变“无改善”的意思,不能默认等同精确逐坐标最小。
固定标签后,不同输出像素的目标可分离,因此同时按最近平均规则更新全图,也精确最小化图像这一组坐标。但联合问题仍非凸,因标签一变,提议亦变。初始图、硬约束与字典可导致不同终点。随机初始化能探索替代结果;随机种子能记录执行,却不能保证选到最佳结果。
例题详解
例题 1.27.6
(完整追踪一次有限合成)
三个输出像素,字母表 ,图像块 、,字典 、。固定 、,没有观测惩罚。由 、标签 开始,能量 。第一块到两样例的平方距离均为四,保留标签一;第二块改选标签二,能量降至四。中间像素收到零与二的提议,平均一,所以改成一,能量降至二。下一轮第一块到首样例成本一、另一样例五;第二块相反,所以标签保持 。像素平均仍是一,整轮不变,终点为 、能量二。
例题 1.27.7
(观测数据怎样改变提议平均)
两个图像块在某自由像素提议零、二;观测 ,惩罚 。故 、,无限制平均是 。在字母表 ,一与二平手,能量均为四,而零的能量十二。若当前值是一,严格更新规则保留它。更大观测惩罚可偏向二,却仍不等于把像素硬性固定。
例题 1.27.8
(逐坐标极小值可以错过最佳状态)
只有一个输出像素 ,字典是单像素零及二,观测 、。状态 能量 ;只改标签变 ,只改像素变四,所以是逐坐标极小值。但同时改成 ,能量为零。即使精确更新且完全没有数值误差,有限算法仍可能在次佳状态停止。
第一例也显示重叠合成实际做了什么:最终两个输出图像块是 、,均不等于字典成员。共享像素协调导致折衷。若更重视完整保存来源纹理元素,可以改为在复制区域间选边界;但那是另一个带自身约束的优化问题,并不是本目标隐含的功能。
概念视角结构
样例是有限词汇,重叠则是组合约束
字典列出模型能提议哪些局部模式;重叠项决定邻近提议能否一致共享像素。有效局部图像块词汇不等于墙壁、人脸或物体的全局描述。增大图像块加入长距离信息,也增加搜索成本与直接复制风险。图像块尺度决定哪些结构受直接约束,哪些只期待由局部相容涌现,或根本不出现。
穷举标签一轮,在 位置各比较 个 维候选,约需 次标量运算。收集提议和约需 ,直接搜索字母表约需 。这些是每轮成本,并不保证轮数是小常数。内存还要存字典与标签场。状态有限不是实际枚举全部状态的好理由。
常见错误
反例模式
零局部误差不保证想要的场景
若字典只有常数零与常数一图像块,没有数据项禁止时,全零输出的图像块能量为零。即使目标是砖墙,该数值也没说明砖块几何,因字典与约束根本未编码它。要修正结论,须先论证目标代表所需结构,再做适当评估;只最小化方便计算的数,不能建立真实感。
常见错误
(把合成补全当作实测数据)
没有统计模型,不应把最近邻距离当概率。从样例复制的图像块,也不等于破损照片缺失部分的观测真相。样例恢复是在假设下提供合理填补,同一已知像素可容许多种完成。清晰结果仍可能加入无根据细节;用途需要时,应记录样例来源并分清量得与合成区域。
常见错误
(原始图像块距离不具平移不变性)
图像块距离还取决于尺度及对齐。一像素平移,可以让同一重复边缘在原始欧氏(Euclidean)坐标中相距很远。旋转、照明归一化或特征距离会改搜索,但每项不变性亦会丢掉某些区别。新增弹性应回应实际模型需要,不应只为降低残差而把不同模式视作相同。
总结
样例目标把最近局部提议、重叠及观测约束结合。标签更新选字典邻居,图像更新协调像素提议。有限字母表及严格平手规则保证有限步到达逐坐标极小值,没有全局最佳或知觉真实感保证。完整小例使执行可核查,也显示相邻图像块不相容时的折衷。
练习
快速检查
(在完整合成例中枚举四组标签,对自由 最小化,验证联合最佳能量,并指出其他标签为何较差。)
解答 · 答案
标签 的能量 ,在零得四; 为 ,在二得四; 为 ,在一得二; 为 ,在一得十。因此这个例子的终点碰巧是全局最佳,但不能推广,另例已展示反例。
快速检查
(两个图像块提议一与三,观测提议零,。在字母表 求全部最小像素值及能量。)
解答 · 答案
、,平均一,是唯一字母表最小值。能量 。配方为 ,同时验证最小值与唯一性。
快速检查
(一像素字母表 、字典零与二、、。精确判定何时 是严格更新规则下的逐坐标极小值,并与全局最佳比较。)
解答 · 答案
当前能量 ,只改标签必加四;只改像素得四,因此恰在 有严格改善。 时是逐坐标极小值,等于一时平手保留。联合状态 总有零能量。因此 对所有正 能量为正,而当它确是逐坐标极小值,即 ,便是全局次佳。
快速检查
(五个自由像素各有四值,三个图像块标签各有两选择。给严格状态改动次数上界,并解释等能量改标签与近似最近邻停止为何需要不同保证。)
解答 · 答案
状态数 ,故严格改动至多 8191 次。这个宽松界算改动,不算坐标测试。等能量改动可以重访状态而循环;近似搜索可能漏掉更佳标签,所以无改动一轮只能证明已测提议没有改善,除非另验精确最近邻最优性。