动机
假设两幅图像都含有可辨认的点,例如校准板的角。即使亮度不同,这些点的对应位置仍可提供对齐图像的线索。我们拟合一个平移、一个旋转及共同的尺度。正尺度的相似变换保留角度与距离之比,却不能表示剪切或透视变形;选择这个模型,等于对可能的几何变化作了限制。
以下假设点的对应关系已知。错配可以严重影响最小二乘拟合,少数点上的小残差亦不能保证整幅图像都对齐。我们求的是所述有限问题的全局最优解,并未解决配对问题。
定义
设 分别是互相对应的来源与目标特征点,固定权重 且 。最小化
向量均为列向量。 由满足 、 的实二阶矩阵组成,故排除反射。允许 会包括将所有点压到一点的情况。若物理模型要求变换可逆,便须要求 ,但此时最小值未必取得。
定义加权重心 、,以及中心化点 、。令
的符号取决于约定:。在精确可逆的情况下,若反过来拟合目标到来源,旋转方向亦会反转。
定理/命题
定理 3.2.1
(加权相似变换的全局拟合)
假设 ,记 。若 ,在 下唯一的最优解为
若 ,则 、 配任意旋转均为最优,且 。若改要求 ,此情况下下确界仍为 ,但没有最小解。若 ,所有正权重来源点都重合;平移可吸收任意 ,故数据不能辨认旋转或尺度。
证明与思路
证明
(先中心化,再解一维尺度问题)
固定 ,把残差写成 。由于 和 的加权和均为零,求和后交叉项消失,因此
第二项唯一的最小化平移是 。旋转保持长度,且 ,展开其余平方得到
对每个 ,柯西–施瓦茨(Cauchy–Schwarz)不等式给出括号至多为 ;当 ,等号要求 。所以全局问题化为在 上最小化 。配方得 ,即证明公式,并在 时给出唯一性。若 ,尺度唯一取零;此时变换不再依赖旋转。若 ,每个正权重点的 都为零,故任意尺度与旋转下的中心化残差均为 ,配上上述平移即可达到。证明检查了所有容许的旋转,而不只是某个初始值附近。
证明透视
三次精确消元
证明逐一消去未知量,而每一步都是精确的。先是平移:加权重心恒等式使平移项与每个中心化残差在加权平方和中正交。重心必须使用与目标函数相同的权重;若权重不等却用不加权的重心,交叉项便不会消失。其次是旋转:固定 时,目标函数对单位向量 是仿射的,柯西–施瓦茨不等式在整个圆上找到全局最大值,而非局部最大值。限制在 正是固定 符号的原因;若允许反射,会出现另一个带自身相关量的候选。最后是尺度:这是一元二次函数,其顶点 自动可行,因为 。假设 只在这里使用,用以保证这个二次函数严格凸。
这个论证也显示了它的局限:若拟合后按残差改变权重,目标函数也会改变;这次一步推导不能证明迭代重加权方法收敛。
例题
例题 3.2.2
(四分之一圈旋转、放大与平移)
等权来源点 分别对应目标点 。重心为 、。代入得 、、、。故 、, 是逆时针四分之一圈,。代回三组原始配对可验证残差为零;最小值公式同样给出 。
例题 3.2.3
(模型无法表示的拉伸)
四个等权来源点 对应目标 :水平轴放大一倍,垂直轴不变。两个重心均为 ,故 、。于是 、、,而 的每一项都为零,故 。因此 、、、,且 。
直接验证:拟合点为 与 ,四个特征点的平方误差各为 ,总和为 。拟合尺度介于两条轴的真实尺度之间,误差平均分摊。这类残差反映模型不匹配,而非噪声;柯西–施瓦茨不等式也确认 。
例题 3.2.4
(塌缩的情况没有正尺度最小解)
等权来源点 都对应目标点 。则 、。最佳非负尺度拟合以 、 将两点压到目标,旋转任意。若要求 ,残差是 ,当 趋近零却始终大于零。声称角度唯一或正尺度下已取得最小值,都是虚构了数据没有提供的结论。
反例模式
旋转不能修复反射
来源三角形 的目标为反射后的 。此时 、、,故最佳保持方向的相似变换有 ,残差为 。反射本身可完全拟合,但其行列式为 ,并不属于 。若求解器默许反射,解的就是另一个配准问题。
常见错误
实际应用中,对上述公式有两种常见误读。
常见错误
(把 当作拟合良好的保证)
非零只表示正权重的来源点不全重合,并不保证 、配对正确、拟合良好或外推稳健。大权重只表示该点对目标函数有较大影响,并不自动是概率或已证实的精度。若权重取决于目标坐标,统计解释也可能受到影响。
常见错误
(存在错配时仍信任最小二乘)
最小二乘会平方放大大错配的影响。例如只拟合一维平移时,偏移 的平均值为 ,虽然其中两个偏移为零。应检查残差与配对;若预期有离群值,可考虑另行明确定义的稳健估计法。上述公式精确解决的是加权平方误差问题,不保证免于错配。
两种错误都把计算的性质误当作图像的性质。
概念视角几何
对齐与可辨认性是不同问题
算出的变换可以唯一,却对观测配对拟合得差;相反,塌缩或重合点可产生小残差,但参数仍无法确定。应同时检查原始坐标单位中的残差与特征点的几何分布;任何一项都不足以独自证明整幅图像已正确对齐。
总结
加权中心化精确消去平移。两个相关量 决定旋转,其长度相对于来源点分散程度的比值给出最佳尺度。全局公式依赖固定配对与权重、保持方向的相似模型,以及对零尺度的明确处理;必须对照实际成像任务检查假设与残差。
练习
练习 3.2.5
(等权来源点 分别对应 。求最佳 及最小残差。)
基础
解答(3)
- 1
中心化数据
两重心分别是 、,故 、。
- 2
计算相关量
、、,故 。
- 3
读出变换
、、。两点均精确对应,残差为零。
练习 3.2.6
(等权来源点 对应 。求 与变换。若对调两个目标点的顺序,估计角度如何改变?)
基础
解答(3)
- 1
计算相关量
两重心均为零。;由于每个 都与其 垂直,;;故 。
- 2
读出变换
、、:逆时针四分之一圈。
- 3
对调目标点
对调目标点后 ,得到顺时针四分之一圈。配对顺序是数据的一部分。
练习 3.2.7
(所有正权重来源点均为 ;等权目标点为 、。求最小误差,并举出两组不同的最优参数。)
核心
解答(3)
- 1
计算目标点的分散程度
目标重心是 ,。
- 2
使用退化情形
关键一步
最小值为 ,只要把共同来源点送到 即可取得。
依据: ,故对任意 与 ,中心化残差都等于 。
- 3
举出两组最优解
及 均把 映至 。尺度和旋转都不能辨认。
练习 3.2.8
(假设中心化数据给出 、、、。求最优解与残差。真正的特征点数据能否得到负残差?)
核心
解答(3)
- 1
计算最优解
,,、,而 。
- 2
计算残差
。
- 3
残差的符号
残差是加权平方和,不可能为负。等价地,真正的点数据满足柯西–施瓦茨不等式 ,此处 ;违反此式的任意数字不能代表这类数据。