动机
特征检测器找出两幅图像中可能重复出现的位置,却没有告诉我们第一幅图的某个点对应第二幅图的哪一点。描述子把点附近的外观概括成一个向量;比较向量后,我们得到的仍只是候选配对。相似的外观也可能来自另一个相似物体,所以配准还要检验多个配对在几何上是否一致。本节建立一个简单流程,并厘清其采样概率究竟保证了什么。
定义
定义 5.2.1
(描述子距离)
设两幅图的检测位置分别为 和 ,描述子分别为 。对实数向量,可以选择欧氏(Euclidean)距离 。描述子不是点的位置:其坐标记录的是所选的局部图像量。比较前,两边必须用兼容的方式构造及缩放。二进制描述子一般可用汉明(Hamming)距离;任意编码后使用欧氏距离不一定有意义。
定义 5.2.2
(比值检查)
固定一个源描述子,把目标距离连同其索引排序为 。若至少有两个目标描述子、,选定 ,只有在下式成立时才接纳最近的目标:
这个比值衡量的是最近候选相对于其他候选有多独特,并非配对正确的概率。若两个最近距离相等且为正,严格不等式会拒绝该配对。若两个最近距离均为零,比值没有定义,我们把情况视为模糊并拒绝;若候选不足两个,也无法计算比值。若只有第一个距离为零而 ,它会通过,但仍可能配错。
常见错误
(把比值阈值直接用于距离平方)
许多程序存储的是距离平方。若最近两个距离为 和 、,比值为 ,配对应被拒绝;若把平方比值 与同一 比较,却会接纳它。等价的平方距离条件是 ,此处为 ,并不成立。
定义 5.2.3
(互为最近邻检查)
互为最近邻检查还要求:原来的源描述子也必须是所选目标的最近源描述子之一;遇到距离相同时须先明确处理规则。
它能排除部分多对一配对,却不能证明配对正确。也可加入绝对距离上限,排除虽然相对独特、但其实并不相似的候选;上限的尺度取决于描述子及数据。重复纹理、遮挡,或真正对应点根本不在候选集合中,都可能使这些检查失效。
几何一致集合
定义 5.2.4
(前向残差与一致集合内点)
对候选配对 和变换 ,定义前向残差 ,单位是目标图像的坐标单位。指定阈值 后,若 ,便称该配对是这个模型的一致集合内点。
这一标签只表示它与某模型相符,并不表示它的真实身份已被证实。阈值应考虑测量噪声和坐标单位;改变图像分辨率却不调整阈值,检验的意义也会改变。
考虑平移 ,一对点已可提出候选 。用全部候选配对评分,保留有较多一致配对的模型,再用选中的配对重新拟合。对二维保方向相似变换,两个源点不同、目标点也不同的配对可确定一个候选;退化样本必须排除。其他模型有各自最少样本数及退化条件。拟合后应检查残差在图像中的分布,并用未参与选择模型的数据检验对齐:某个重复图案形成庞大一致集合,仍可能不是我们希望配准的物体。
概念视角几何
外观和几何回答不同问题
描述子距离比较局部外观;几何残差则检查一个整体变换能否解释点的位置。可靠流程需要两者,但若另一组错配支持另一个变换,它仍可能同时通过两种检查。
定理或命题
定理 5.2.5
(抽到全内点样本的概率)
设 是整数,且 、、、。固定 个候选配对,其中恰有 个是真正内点。每次试验从中均匀、不放回地选出 个不同配对;各次试验互相独立,而且每次都重新从全部 个配对采样。一次试验全是内点的概率为
其中 时分子视为零。进行 次后,至少一次抽到全内点的概率为 。当 ,要使这概率至少为 ,充要条件是
若 ,任何有限次数都不够;若 ,一次便足够。这是采样保证,并不保证所得变换准确,也不保证它最后被选中。
选定一致集合之后,平移模型的重新拟合有闭合形式。
命题 5.2.6
(平移的最小二乘重新拟合)
设 是非空有限的候选配对 集合,位移为 。使 最小的平移唯一,且等于平均位移 。
证明思路
证明
(计算子集与独立试验)
所有 个子集等可能,其中全由内点构成的恰有 个。一次失败的概率为 ;由各次试验之间的独立性,全部失败的概率是 。取补事件便得到结论。当 ,取对数后除以负数 ,不等号方向反转;最后向上取整,便得到所需最小整数。
证明透视
采样概率没有涵盖什么
定理中的每个假设各用一次。均匀选取 元子集,使计数比值成为概率,共有 个等可能结果。不放回采样,使有利结果恰为内点集合的 元子集。若可放回并计次序,计数便是 中的 ;这正是常见近似 的来源,而它在此一般并非精确值。独立性只用于试验之间,即乘积 ;同一次试验内的配对并不独立,也不需要独立。
上界中的关键一步是除以 :当 时它是负数,不等号因此反转。 时此对数为零, 时它无定义,所以两种情况须另行说明。被计算的事件是抽到全内点样本;退化、噪声、阈值筛选及模型选择都在证明范围以外。
重新拟合只是一次初等的配方。
证明
(用配方求平均位移)
由于 ,在 附近展开:
因为交叉项 为零。第二个和与 无关,第一项恰在 时为零。
例子
例题 5.2.7
(独特的描述子仍可能配错)
设 ,目标描述子为 、、。最近两个距离是 和 ;取 时,因 ,第一个通过。假设 实际属于另一个重复物体,而真正对应点被遮挡,检查仍会通过,因为它只比较给定候选。若用距离平方 ,等价判断是 ,不是 。
例题 5.2.8
(含一个离群配对的平移一致集合)
考虑四对候选:、、 和 。它们提出的位移依次是 。取 ,第一个候选模型得到三个内点,最后一个得到一个。对前三个位移做最小二乘平移拟合,即取平均,得到 ,三个残差都是零。若四个都使用,平均则是 ,可见一个严重错配的影响。一致性方法并没有证明前三对是真配对,只找到一个受到它们支持的模型。
例题 5.2.9
(有限采样的精确概率)
若 、、,一次成功概率为 ,不是 。三次独立试验至少成功一次的概率为 。若要求至少 ,需七次:,而 。
常见误解
反例模式
庞大的错误一致集合
假设四对正确配对共有平移 ,另有六对错配共有平移 。取 ;两个位移相距 ,所以没有平移能同时接纳两组。两组都完全符合各自的变换,但最大一致集合会选择六个错配。几何一致本身不能辨认我们想要的是哪个实体;还需要先验信息、较大范围的图像背景或独立验证。
采样置信度是另一个容易把正确公式过度解读的地方。
常见错误
(把采样界读成配准保证)
把估计的内点比例代入置信度公式,不能自动得到无条件保证:比例估计和各次均匀独立采样的假设都要有依据。增加 也不能修复不合适的变换、过大的阈值,或缺乏代表性的候选集合。重新拟合可能改变哪些配对落在阈值内;若反复重新分类,就要明确停止规则,不能自动假设每项想改善的指标都会单调变好。
小结
描述子提供局部候选,比值和互为最近邻检查可减少部分模糊性。几何一致集合检查候选是否支持共同变换,再拟合利用选出的配对。在明确假设下,采样置信度只衡量抽到全内点子集的机会,不等于正确配准的确定性。
练习
练习 5.2.10
(最近两个距离为 和 ,。判断是否接纳;再用距离平方判断,并写出正确阈值。)
基础
解答(2)
- 1
应用比值检查
,故接纳。
- 2
改写为距离平方
,同样接纳;平方距离的阈值是 。
练习 5.2.11
(三个目标距离为 。比值检查能否区分最近的两个?若距离变为 又如何?)
基础
解答(2)
- 1
检查两个零距离
比值为 ,无定义,应视为模糊并拒绝。
- 2
检查单个零距离
比值为 ,通过任何正阈值,但配对仍不一定正确。
练习 5.2.12
(五个候选平移为 。取 ,求候选 和 的分数,再分别求较大一致集合及全部五个位移的最小二乘拟合。)
核心
解答(2)
- 1
为两个候选评分
两个不同位移相距五,大于 ;分数分别为四和一。
- 2
以平均位移重新拟合
选出的四个位移平均为 ;全部五个平均为 。
依据: 最小二乘平移等于平均位移。
练习 5.2.13
(六对候选中有四对是真正内点,每次均匀选取两个不同配对,各次试验独立。求两次中至少一次全是内点的概率,并解释它为何不是最终正确配准的概率。)
核心
解答(3)
- 1
计算一次试验的概率
。
- 2
合并两次独立试验
。
- 3
说明未涵盖的部分
退化样本、噪声、模型选择和另一个错误一致集合仍可能妨碍正确配准。