动机
把两张人像直接交叉淡化,只改变透明度,两双眼睛仍留在各自位置。过渡到一半时,便可能看见两对淡淡的眼睛。几何渐变先问:第一张图像的哪一点应变成第二张的哪一点?把对应特征移向共同中间形状后,才在对应位置混合外观。几何与色彩插值是两个决定,时间上看似流畅也不代表两者正确。
最难的往往是对应本身。两张图像所选的嘴角,应有相同语义角色。遮挡、不同表情或新显露的表面,未必能用一对一平面变形表示。本节先假设对应特征点及共同三角形连接关系已提供,使数值构造可以逐步检查,也能准确指出哪些位置有逆映射。
这个简单模型仍有反直觉之处:起点与终点三角形均非退化、方向一致,中途却可以塌缩。只看第一帧与最后一帧不足够。我们会分清跨三角形边的连续性、三角形内的局部可逆性,以及全网格的一对一性。这些性质回答不同问题,需要不同假设。
定义
定义 1.28.1
(相容的公共剖分与插值特征点)
用有限相容三角剖分覆盖紧凸多边形区域 。相容指不同三角形内部不交,交集只能是一条完整共有边、一个共有顶点或空集,没有悬挂顶点。第一幅图像顶点 使用全局索引,第二幅对应顶点为 ;两网格用相同索引三元组定义三角形。时间 的特征点为 。中间三角形必须有非零面积,才能进行逆向采样。
定义 1.28.2
(重心坐标与三角形上的仿射映射)
对有次序的来源三角形 ,写
若 ,重心坐标唯一。点在闭三角形内,当且仅当三个坐标均非负。在一条边上,对面顶点的坐标为零。映至对应目标三角形的仿射映射为
其 Jacobian 行列式为 。零表示局部塌缩,负值表示相对指定顶点次序反向。翻折可能涉及方向反转,也可能涉及不同网格区域重叠。对任意组合网格,只检查每个三角形方向为正,本身并不是全局不重叠证明。
定义 1.28.3
(输出点的双图渐变值)
对中间三角形 的输出点 ,先求重心坐标,再查询
是指定的连续重建规则,例如双线性插值。先做几何变形,再于共同中间形状交叉淡化。使用线性光值才有物理混合解释;直接混合显示编码通常得到不同结果。
定理 / 命题
定理 1.28.4
(顶点对应唯一决定连续分片仿射映射)
在上述相容来源剖分中,假设每个三角形非退化,目标值一致地指定至全局索引顶点。则存在唯一映射,把每个 映至 ,并在每个来源三角形上仿射。它在整个剖分域连续。某三角形上的映射可逆,当且仅当其目标三角形非退化。连续性不蕴含全局单射。
定理 1.28.5
(小 Lipschitz 位移保证像域上的全局逆映射)
连续位移 对全部 满足 。若 ,则 满足
因此它是单射,在 上的逆映射 Lipschitz 常数不超过 。这是有效渐变的充分条件,并非必要条件。
对凸剖分域的连续分片仿射位移,可用所有三角形 Jacobian 的最大欧氏(Euclidean)算子范数作 。把两点间线段按三角形边界切开,逐段累加界,总长等于原线段长度,便得全局估计。凸性保证线段留在域内;非凸域不能不加修改就使用同一证明。
证明思路
证明
(分片仿射映射的存在性、连续性与局部可逆性)
在非退化的来源三角形 上取 。它是仿射映射;由 、 可知它把 分别映到 。满足这些顶点值的仿射映射只有一个:两个这样的映射之差仍是仿射映射,在 处为零,所以是一个线性映射,并且把可逆矩阵 的各列都映成零,因此恒为零。
相容剖分中的两个三角形只可能交于一整条公共边、一个公共顶点,或者不相交。在端点为 的公共边上,点可写成 ,两个三角形上的仿射映射都把它映到 ,因为两者用的是同一组按全局索引给定的目标值。所以各片在重叠处取值一致;有限个闭片各自连续、在重叠处一致,整个区域上的映射就连续。每个三角形上的线性部分是 ,它可逆当且仅当 ,也就是目标三角形非退化。以上推理没有排除两个相距很远的三角形被映到同一区域。
证明
(由小的 Lipschitz 常数得到距离界)
对 ,
由三角不等式和 得 。由反向三角不等式得 。当 时 为正,所以 必有 :映射是单射,在其像上存在逆映射。对像点 、,下界就是 ,即逆映射的 Lipschitz 界。当 接近一时保证变弱:很小的输出位移可能对应很大的来源位移。
证明透视
共有边给出连续性,距离下界给出单射性
第一个证明只用到一条边上端点数据的一致性,管不了其他三角形会被移到哪里。第二个证明比较所有点对,禁止它们的像相撞。两者是不同的逻辑机制。渲染器可以靠“后画的盖住先画的”掩盖重叠,但这种绘制约定不会把多对一的几何映射变成真正的逆映射。
每个假设只在一处起作用。按全局索引一致赋值,只用来使两条边上的公式相等; 非退化,只用来构成 ; 只用来使 为正,把距离下界变成单射性。两个证明都没有用到 的凸性;凸性只出现在为分片仿射位移估计 的线段论证里。
每个中间三角形的面积也有精确有限检查。边矩阵 的行列式 在二维是二次多项式。要证明整个区间 ,应检查端点,以及区间内可能是最小值的临界点。只看若干画面,可能漏掉两帧之间的零点。面积检查仍属局部;全局重叠和边界行为需要另行检查,或使用上述充分定理。
例题详解
例题 1.28.6
(完整计算一个中间像素)
来源顶点为 ,目标为 。在 ,中间顶点为 。输出点 的重心坐标是 ,来源查询分别为 、。若连续图像 、,强度为 和 ,半混合得到 。这些是示意强度单位,并未假定通道一定限制在一以内。
例题 1.28.7
(两端方向正确,途中仍会塌缩)
取 、,两个行列式均为一,但
它在 、 为零,中间为负, 时等于 。半周旋转配合不等比例缩放,若只把顶点沿直线插值,便可经过塌缩。补救需要另一条几何路径、额外对应或受控变形模型;改色彩混合不能恢复不存在的几何逆映射。
例题 1.28.8
(一项保守但全局有效的保证)
设 ,,欧氏算子范数为 。对全部 ,定理给出 ,所以没有碰撞。 的线性部分为 ,最小奇异值正是 ,垂直方向达到界。平移 改位置却不改点差,因此即使整幅图移得很远,纯平移仍不造成此种退化。
数字实现可先定特征点及共同连接关系,检查来源、目标与整个时间区间;每帧再把输出像素定位至有效中间三角形,计算重心坐标,查询两张原图并混合。共有边上的像素需要一致归属约定,避免遗漏或重写不一致。连续公式在边上相同,浮点三角形测试仍可能有分歧,因此光栅化规则要明确。
概念视角算法
一张移动网格查询两张原图
中间位置的重心坐标,在两张原图挑出相应位置;不是先取上一帧,再不断把它变形。直接查询原图可避免随时间累积插值模糊。当三角形缩小,逆映射涵盖较大的来源覆盖范围,仍可能需要抗混叠。避免重复采样并没有免除采样信息的限制。
连接关系本身也要检查。两端各自独立剖分,可能在四边形中选不同对角线,令部分区域没有“对应三角形”。共同组合网格是模型的一部分,不能交给两次无关剖分自动决定。图像边界特征点亦有作用;欠缺它们,原本想覆盖整帧的渐变可能留下未覆盖区域。
常见错误
反例模式
连续并不阻止重叠
在 ,连续分片仿射函数 在共有顶点零一致,却把 和 映至同一点。延伸为长方形上的 ,便得重叠平面映射。局部公式没有裂缝,一侧却反向,整体没有单值逆映射。共有边吻合,不能单独证明图像变形可用。
常见错误
(把每个特征点都当成同一个可见的材料点)
特征的可见性发生变化时,一对特征点未必标示同一个材料点。闭口与张口看到的是不同的表面,平面双射不可能凭空生成第一张图中被遮住的牙齿。淡化可以让新的外观浮现出来,但那是合成上的选择。边界移动正确,同样不能保证大三角形内部的纹理遵循合理的运动。
常见错误
(把行列式为正当作数值上安全)
可逆性只有“是”或“否”,数值敏感度则取决于奇异值。细长的三角形即使面积为正,也可能放大特征点的误差。应当查看条件数、有意义的对应点密度和来源覆盖范围,而不是只看符号。特征点增多而没有带来新信息,只是把同一个猜测切得更细,未必改善模型。
总结
分片仿射渐变由共有特征点连接关系、重心几何及外观插值组成。共有边值一致给连续性,非零三角形面积给局部逆;两者均不单独保证全局一对一。Lipschitz 位移界提供一项严格充分条件,面积二次式则找出端点检查漏掉的中间塌缩。有效几何还需配合采样、外观与遮挡的明确处理。
练习
快速检查
(在第一个例题中取 的中间点 。求它的重心坐标、两个来源查询点,以及对相同连续图像得到的合成强度。)
解答 · 答案
重心坐标为 ,因为 、。于是 、,两个强度分别为 和 ,各取一半混合得 。在两张原图中都用同一组重心权重来确定几何位置;若直接把中间图的笛卡尔(Descartes)坐标拿去查原图,就会找错特征位置。
快速检查
(相邻的来源三角形共有顶点 。若这两个顶点的目标值一致,直接证明两个仿射映射在 ()处取值相同。若其中一个三角形对 用了不同的目标,哪一步会失效?)
解答 · 答案
仿射性使两个三角形都给出 ,所以两者在整条边上的限制相同。若第二个三角形用 ,边上的取值相差 ,对 非零。这是沿边出现真正的裂缝,而不只是数值插值误差。
快速检查
(对 、,展开 并求它在 上的最小值。验证只检查 和 会漏掉塌缩。)
解答 · 答案
展开得 。导数在 处为零,此时 ;两个端点处都是 。零点是 和 ,所以端点处的符号掩盖了两个奇异时刻以及中间方向反转的区间。
快速检查
(凸区域上的连续分片仿射位移,其各三角形的 Jacobian 范数都不超过 。在 时给出距离的上下界和逆映射的 Lipschitz 界。为什么定理不要求常数平移部分很小?)
解答 · 答案
,故 ,逆映射的常数不超过 。常数位移在 中相互抵消,对每个 Jacobian 的贡献为零。这个条件限制的是相对形变,而不是整张图像平移多远。