相对姿态估计的不稳定性及RANSAC的作用

89350相对姿态估计的不稳定性及RANSAC的作用0布朗大学工程学院范鸿毅0hongyi fan@brown.edu0德克萨斯大学奥斯汀分校数学系乔∙基利尔0jkileel@math.utexas.edu0布朗大学工程学院Benjamin Kimia0benjamin kimia@brown.edu0摘要0使用5点或7点随机采样一致性（RANSAC）算法进行相对姿态估计，即使没有异常值存在并且有足够的内点支持假设，也可能失败。这些情况是由于5点和7点最小问题的数值不稳定性引起的。本文通过在Riemann流形上基于多视图几何的最小问题条件进行分析的新框架，对这些不稳定性进行了表征。使用合成和真实世界数据的实验证明，RANSAC不仅用于过滤异常值，而且还选择了良好条件的图像数据，足够远离我们理论预测的不适定位置。这些发现表明，在未来的工作中，可以通过仅测试良好条件的图像数据来加速和增加RANSAC的成功率。01. 引言0过去的二十年中，多视图几何应用呈爆炸式增长，例如用于视频游戏[1]、电影[19]、考古学[28]、建筑学[22]和城市建模（例如Google街景）的三维物体模型重建；增强现实和电影摄影中的匹配移动，用于混合虚拟内容和真实视频[11]；与场景相关的照片集合的组织，称为运动结构[27]（例如在照片旅游中的先驱[2]）；机器人操作[16]；以及来自汽车制造和自动驾驶中的相机的气象学。多视图系统的一个关键组成部分是两个相机的相对姿态估计[15,35]。在应用中占主导地位的是RANSAC[29]。它从两个视图中随机选择的少数对应关系中形成假设，例如在校准相机姿态估计中选择5个。0(a)0(b)0图1.典型的相对姿态估计即使有大量的对应关系（图中显示了100个对应关系），所有对应关系都是内点，也可能发生灾难性的失败。（a）真实的极线几何。（b）来自7点算法和LO-RANSAC[8]的错误估计的极线几何。这种失败的主要原因是数值不稳定性，正如本文所示。0在未校准的相机姿态估计中，RANSAC算法在[31,33]中使用7个假设的对应关系，并使用剩余的假设对应关系验证这些假设。使用RANSAC的主要原因是其对异常值的鲁棒性，参见[3, 5,24]。多个相机的姿态可以通过局部增量[30]或全局平均[18]的方式恢复。这种方法在许多应用中非常成功。然而，在某些情况下，基于RANSAC的方法会失败，例如在两个相机之间产生相对姿态时。例如，当候选对应关系的数量减少到50到100个时，例如在均匀和低纹理表面的图像中，姿态估计过程会失败。同样，当场景中存在重复纹理时，会有大量的异常值候选对应关系，也会导致过程失败。奇怪的是，即使只有少数对应关系可用，估计也会失败：毕竟，RANSAC可以从50个中选择5个，即大约有210万种组合，所以有很多种选择。89360如果异常值比例较低，则可用的真实对应点数量较多。在没有异常值的实验中，无论是使用合成数据（见第5节）还是真实数据（见图1），该过程仍然经常失败！这是个谜，除非RANSAC的作用超出了剔除异常值。事实上，我们将论证RANSAC的主要作用是稳定估计过程，而不否认其在处理异常值方面的作用。我们将展示从最小问题估计位姿的过程通常对噪声不稳定，其不稳定性程度取决于选择的5个点或7个点。RANSAC的作用是将未选择的对应点整合到估计过程的稳定性中：如果大量未选择的候选对应点一致，则假设既没有异常值，而且更重要的是，它是对典型图像噪声稳定的估计。本文研究了多视图几何中最小问题的数值稳定性问题。我们建立了一个框架，将良好条件的最小点配置与正向投影映射的逆雅可比矩阵的条件数联系起来。利用这个框架，我们计算了5点和7点最小问题的条件数公式。此外，我们研究了病态问题，即条件数无穷大的情况。我们得到了世界场景病态的特征描述，以及使最小图像点对应配置病态的要求。关于两视图几何退化的许多分析已经出现，例如[14, 17, 20,23]。然而，这些文献研究了3D重建问题存在多个解的情况。相比之下，我们关注的是是否存在无界不稳定解。这种分析与以往文献不同，它专注于最小问题，其中通常存在多个真实解。因此，我们的理论适用于实践中使用的多视图几何：在RANSAC期间解决的最小问题。除了这个理论分析，我们提出了一种衡量给定最小图像点对应集稳定性的方法，即通过测量一个图像上的一个点到另一个点对应计算的“退化曲线”的距离。这个距离提供了评估最小假设稳定性的手段。我们提出的评估给定假设稳定性的方法为增加RANSAC的速度和鲁棒性提供了一种途径：只测试来自足够良好条件的图像数据的假设。本文的其余部分安排如下。第2节0本节回顾了估计相对位姿的两个经典问题，即校准相机的5点问题和非校准相机的7点问题。第3节介绍了一种用于分析任意最小问题条件的新理论框架。第4节介绍了相对位姿分析的具体结果。0介绍了估计、描述病态世界场景和图像数据的设置，并提出了一种测试良好条件图像数据的潜在方法。最后，第5节展示了合成和真实数据的实验结果，作为我们理论及其与RANSAC的联系的概念验证。02. 相对位姿估计的最小问题0本节回顾了5点和7点最小问题的相关设置。下一节的一般框架将再次使用这些加粗的术语。0本文介绍了基本矩阵和5点问题：W表示世界场景空间，由两个校准针孔相机之间的相对位姿和五个世界点组成。0W = SO(3) × S2 × (R3) × 5 = {(R, ˆT, Γ1, . . . , Γ5)}. (1)0Here SO(3) = {R ∈ R3×3: RR� = R�R = I} is the group ofrotation matrices, S2 = {ˆT ∈ R3: ∥ˆT∥2 = 1} is the unitsphere (representing the direction of the translation inthe relative pose) and Γi (for i ∈ {1, .., 5}) are the 3Dpoints. Meanwhile, let X denote the image data space,consisting of five image point correspondences:0X = {R2×R2}×5 = {(γ1, ¯γ1), ..., (γ5, ¯γ5)}, (2)0where γi ∈ R2 and ¯γi ∈ R2 represent correspondingpoints on the two image planes. Next, let Φ denote theforward map, projecting the given world points via thecalibrated cameras [I 0] ∈ R3×4 and [RˆT] ∈ R3×4, i.e.,0Φ ∈ R, ˆT, Γ1, ..., Γ5 = ((γ1, ¯γ1), ..., (γ5, ¯γ5)), (3)0where γi = π(Γi) and γi = π(RΓi + ˆT) where π is projectionof the 3D points onto 2D images. The relation betweencorresponding points on the two images is captured viaessential matrix E as ¯γTEγ = 0, where E ∈ R3×3. Thus, wedefine the epipolar space as the manifold of real essentialmatrices, which are characterized by ten cubic equationsvanishing [9] or in terms singular values as follows:0Y = {E ∈ P(R3×3): 2EE�E − tr(EE�)E = 0, det(E) = 0}0= {E ∈ P(R3×3): σ1(E) = σ2(E) > σ3(E) = 0}. (4)0Last, the epipolar map Ψ is defined as computing an essentialmatrix from a world scene using the relative pose:0Ψ ∈ R, ˆT, Γ1, ..., Γ5 = E = [ˆT]×R ∈ P(R3×3). (5)0Here [ˆT]× ∈ R3×3 is the usual skew matrixrepresentation of cross product with the vector ˆT ∈R3, as in [15, Sec. 9.6].89370Then, 5-point problem is the task of determining thepossible essential matrices E given the five image pointpairs, i.e., computing Ψ(Φ−1(∙)). In [26], David Nisterdeveloped a solver for this problem. It boils down tocomputing the real roots of a degree 10 univariatepolynomial, giving ≤ 10 real solutions for the essential0Fundamental Matrices and the 7-Point Problem: Forthe case of uncalibrated pinhole cameras, the worldscene space W is the space of the relative posestogether with seven world points:0W = R3×4×R3×4×(R3)×7 = {P, ¯P, Γ1, ..., Γ7)}. (6)0Here Γi (for i ∈ {1, .., 7}) are the 3D points and P and ¯Pare the 3×4 projection matrices representing the twocameras, which are defined to be P = K[R|ˆT] where Kis the intrinsic matrix of the camera. Then, the imagedata space X is the space of seven image pointcorrespondences, i.e., X = {(γ1, ¯γ1), ..., (γ7, ¯γ7)}. Theforward map Φ is defined to project the world pointsvia the uncalibrated cameras via0Φ(P, ¯P, Γ1, .., Γ7) = ((γ1, ¯γ1), ..., (γ7, ¯γ7)), (7)0where γi = π(PΓi) and ¯γi = π(¯PΓi) with π the projection from3D to 2D image. The relation between imagecorrespondences is described by a 3×3 rank-2 fundamentalmatrix F via ¯γTiFγi = 0. Here the epipolar space consists ofthe manifold of real fundamental matrices i.e.,0Y = {F ∈ P(R3×3): rank(F) = 2}. (8)0The epipolar map Ψ sends a world scene to thefundamental matrix associated to the projection matrices[15, Eq. 9.1]. Then, the 7-point problem is the task ofdetermining the possible fundamental matrices F giventhe seven image point pairs, i.e., computing Ψ(Φ−1(∙)).The solutions are obtained by computing the real roots ofa cubic univariate polynomial, see [15, Sec. 11.1.2].03. 理论框架0在本节中，我们提出了一种新颖的理论框架，用于分析多视图几何中最小问题的数值稳定性，该框架推广了第2节中定义的符号。相关的数学结构是Riemann流形，我们用它来描述要估计的世界场景、图像数据和极线数量的总体。Riemann几何有助于讨论内在距离。我们的方法使用切空间、微分和反函数定理。我们建立在Demmel[10]提出的条件数和不适定输入的理论基础上，然后由Burgisser[7]进行了扩展。我们将理论调整到了最小问题的设置中，其中输入图像数据和输出极线数量之间存在世界场景“之间”。03.1. 空间和映射0设W、X、Y为Riemann流形，其测地距离分别为dW(∙,∙)、dX(∙, ∙)、dY(∙, ∙)，切空间分别为T(W, w)、T(X, x)、T(Y,y)，其中w∈W，x∈X，y∈Y，切空间上的内积分别为�∙,∙�W,w、�∙, ∙�X,x、�∙,∙�Y,y。在多视图几何的应用中，我们将其称为0• W 世界场景空间；0• X 图像数据空间；0• Y 极线空间。0我们限制在dim(W)=dim(X)的情况下，以模拟多视图几何中的最小问题。见下面的注1。接下来，假设我们给出了一个从世界场景到图像数据的可微映射Φ，其定义域是W的一个开稠密子集。我们使用虚线右箭头表示这种情况：0Φ：W→X。（9）0假设图像Φ(Dom(Φ))包含了定义域X的一个开稠密子集；我们通过称Φ为主导映射来总结这个性质。我们称Φ为正向映射。此外，假设我们提供了一个从世界场景到极线矩阵的可微映射，同样只在W的一个开稠密子集上定义：0Ψ：W→Y。（10）0再次假设Ψ是主导映射。我们称Ψ为极线映射。现在给定图像数据x∈X，如果Dom(Θ)是X中x的一个开邻域，并且Θ是正向映射的一个截面，我们称Θ:X�Dom(Θ)→W为一个局部定义在x附近的三维重建映射。0Φ ◦ Θ = id Dom(Θ)。（11）0在这种情况下，将Θ与极线映射组合起来，得到一个（局部定义的）从图像数据到极线空间的映射：0S := Ψ ◦ Θ：X�Dom(Θ)→Y。（12）0我们称S为一个解决方案映射（在x附近局部定义）。这个名称是有意义的，因为在视觉中的最小问题中，我们想要计算的数量通常是一个极线矩阵/张量，而输入通常是图像数据。0注1假设上述设置。那么多视图几何中的最小问题可以建模如下：给定图像数据x∈X，我们想要计算所有兼容的实际极线矩阵/张量，即0Ψ(Φ^(-1)(x)) = {Ψ(w): w∈W, Φ(w)=x}�Y。（13）0这些解决方案在RANSAC中成为假设。当我们称一个问题为“最小”时，我们的意思是以下内容。Ill-posed world scenes are those failing the condition in theabove lemma; therefore, a priori we do not know if theforward map is locally invertible around ill-posed worldscenes. Meanwhile ill-posed image data are those such thatthere is at least one compatible world scene that is ill-posed;hence, there could be problematic behavior around an ill-posed world scene (We emphasize that other world scenesin Φ−1(x) need not be ill-posed). In a moment, we will seethat all of the numerical instabilities in minimal problemsmust occur at (or near) the ill-posed scenes and image data.89380对于X的一个开稠密子集中的x，输出Ψ(Φ^(-1)(x))是一个有限集（并不总是空集）。通常，最小性是附加结构的结果，这在本文的大部分内容中并不需要。通常，W、X、Y可以被视为准投影代数簇，Φ、Ψ是代数函数[13]。然后由于假设dim(W)=dim(X)和Φ的主导性，代数几何中的一般事实暗示Φ的通用纤维是有限集，因此问题是最小的。参见[12，Def.2]。0我们想要分析解映射S（x）对输入x中实际噪声的输出有多敏感。我们想要开发定量的条件数公式，并描述不适定输入的轨迹，其中解映射可能在局部甚至不存在或具有无穷条件数。03.2.不适定轨迹0给定图像数据x∈X和预定的世界场景w∈W，使得Φ（w）=x，下一个引理表明存在一个唯一的连续三维重建映射Θ，其中Θ（x）=w。此外，Θ是连续可微的（C1）。0引理1假设正向映射Φ是C1的，并且在世界场景w∈W处，正向映射对切空间上的微分是同构的。也就是说，微分是线性同构的。那么存在W中w的开邻域U和X中Φ（w）的开邻域V，使得Φ：U→V是双射，逆函数是C1的，并且0DΦ（w）：T（W，w）→T（X，Φ（w））（14）0引理是从流形的逆函数定理得出的[21]。简而言之：如果正向雅可比矩阵DΦ（w）可逆，则正向映射Φ在不适定的世界场景周围是局部可逆的，并且其局部逆函数在雅可比矩阵（DΦ（w））−1处可0D�（Φ |U）−1�（Φ（w））=（DΦ（w））−1。（15）0不适定的世界场景是指不满足上述引理中条件的场景；因此，我们事先不知道在不适定的世界场景周围正向映射是否是局部可逆的。同时，不适定的图像数据是指存在至少一个兼容的不适定世界场景的图像数据；因此，在不适定的世界场景周围可能存在问题行为（我们强调Φ−1（x）中的其他世界场景不一定是不适定的）。一会儿，我们将看到所有最小问题中的数值不稳定性必须发生在（或附近）不适定的场景和图像数据上。0定义1如果微分DΦ（w）不可逆，则称世界场景w∈W为不适定。如果存在一个世界场景w∈Φ−1（x），使得w不适定，则称图像数据x∈X为不适定。03.3.条件数0我们的另一个核心理论概念是条件数。我们首先根据[7，Ch.14]相当普遍（直观地）解释这一概念。为此，让G：X�Dom（G）→Y是定义在X中x的开邻域上的任何映射。0定义2 G在x处的条件数定义为0cond（G，x）：=limδ→0+sup�x∈XdX（�x，x）<δ0dY（x0dX（�x，x）。（16）0简而言之：条件数捕捉了函数G根据X和Y上的内在度量测量的距离，在输出G（x）中产生的输入误差x的极限最坏情况放大。如果G是可微的，我们有一个更明确的公式。0引理2如果G可微，则G在x处的条件数等于微分DG（x）：T（X，x）→T（Y，y）的算子范数，即0cond（G，x）= max˙x∈T（X，x）∥˙x∥=1∥DG（x）（˙x）∥=：∥DG（x）∥，（17）0其中中间数量中的两个范数是由Riemannian内积�∙，∙�X，x和�∙，∙�Y，G（x）引起的。0这是[7，Prop.14.1]，并使用Taylor定理证明。引理将计算可微映射的条件数简化为计算其雅可比矩阵相对于切空间T（X，x）和T（Y，G（x））上的正交基的主奇异值。在这里，我们最感兴趣的是最小问题的解映射的条件数，如式（12）。将前两个引理与链式法则结合起来得到：0引理3 设S = Ψ ◦ Θ:X�Dom(Θ)→Y为解映射，如(12)所示，定义在图像数据x∈X附近。设w =Θ(x)∈W为相应的世界场景。假设w不是病态的，即DΦ(w)可逆。那么，S在x处的条件数是有限的，并且由以下公式给出0cond(S, x) = ∥DΨ(w) ◦ DΦ(w)−1∥. (18)0特别地，只有当x是病态的时候，cond(S,x)才可能是无穷大。03.4. 病态区域与条件数之间的关系0如引理3所示，变化的极线矩阵/张量在x∈X处的条件数只有在x是病态的情况下才可能是无穷大，如定义1所示。如果x是病态的，相应的世界场景w = Θ(x)∈W，使得DΦ(w)89390当x变化时，秩亏可能会遭受无限大的相对变化。此外，引理1暗示了在输入x∈X不是病态的情况下，实际3D重建的数量在局部上是恒定的。换句话说，只有当图像数据x穿过病态区域时，才可能出现实质性矩阵/张量的数量变化。因此，病态区域捕捉到了至少一个最小问题解决方案可以无限不稳定的“危险区域”，以及真实解决方案可以消失到（或从）复数中的区域。在[10]中，Demmel证明了在某些情况下，到病态区域的距离的倒数等于条件数。例如，对于矩阵求逆问题，已经证明了这一点。在这里，我们不证明在计算机视觉中解决最小问题的条件数与到病态区域的距离之间的定量关系。但是，在第5节的实验中，我们通过数值方法证明了一个密切的关系，即在本质矩阵和基础矩阵估计的情况下。04. 主要结果0我们现在根据第3节中的框架将主要的理论结果应用于第2节中的最小问题，关于相对姿态估计的不稳定性。由于篇幅限制，证明（和某些明确的公式）将出现在补充材料中。04.1. 条件数公式0我们在5点问题和7点问题上应用基于雅可比矩阵奇异值的公式（18）。这导出了本质矩阵和基础矩阵估计的条件数公式。这些表达式在解决非病态世界场景的情况下是有效的；实际上，它们只依赖于所述的世界场景。我们在补充材料中显示了明确的雅可比矩阵。0命题1（E的条件数）考虑第2节中的5点问题。设x∈(R2×R2)×5为给定的图像数据，w∈SO(3)×S2×(R3)×5为一个兼容的世界场景，不是病态的。那么存在一个唯一的局部定义在x附近的连续3D重建映射Θ，使得Θ(x) =w，并且有一个相关的唯一定义的解映射S = Ψ ◦Θ从图像数据到本质矩阵。S的条件数可以计算为一个明确的5×20矩阵的最大奇异值，该矩阵的条目是w的函数。该矩阵自然地分解为一个5×20矩阵乘以一个20×20矩阵。0命题2（F的条件数）考虑第2节中的7点问题。设x∈(R2×R2)×7为给定的图像数据，w∈R3×4×R3×4×(R3)×7为一个兼容的世界场景，不是病态的。那么存在一个0唯一的局部定义在x附近的连续3D重建映射Θ，使得Θ(x) =w，并且有一个相关的唯一定义的解映射S = Ψ ◦Θ从图像数据到本质矩阵。S的条件数可以计算为一个明确的7×28矩阵的最大奇异值，该矩阵的条目是w的函数。该矩阵自然地分解为一个7×28矩阵乘以一个28×28矩阵。04.2. 不适定的世界场景0这里我们推导出一个世界场景对于5点或7点问题是不适定的几何条件。我们的特征化是关于在R3中存在一种特定类型的四次曲面，这种四次曲面应满足与给定的世界场景相关的某些属性。0(a)0(b)0(c)0图2.校准情况下的一个不适定世界场景的说明性示例。红色和蓝色的金字塔代表两个相机。洋红色点代表给定的世界点。绿色曲面是满足定理1中的三个条件的四次曲面。（a）和（b）显示了两个不同的视角。最后，缩小的视图（c）显示了与基线垂直的橙色平面，其与四次曲面的交点是一个圆。0定理1（E的不适定世界场景）考虑第2节中的5点问题。设w=(R,ˆT,Γ1,...,Γ5)∈SO(3)×S2×(R3)×5为一个世界场景，使得Φ(w)存在，其中Φ如等式(3)所示。那么w是不适定的，即DΦ(w)是秩亏的，当且仅当存在一个四次曲面Q�R3，满足以下条件：0• Q通过给定的世界点Γ1,...,Γ5；0• Q包含给定相对姿态的基线；0• 并且将Q与ℓ的任何法向仿射平面相交产生一个圆。0这里的基线ℓ�R3是通过两个相机中心的世界线，即ℓ=Span(−R�ˆT)。0第二个要求意味着Q是一个规则的四次曲面（即，由无穷多条直线覆盖）。同时，第三个条件是一个非标准条件，意味着Q必须在规则四次曲面集合中是特殊的，即它必须是所谓的“矩形四次曲面”[23]。参见定理1的可视化结果图2。0定理2（F的不适定世界场景）考虑第2节中的7点问题。设w=89400(P,¯P,Γ1,...,Γ7)∈R3×4×R3×4×(R3)×7为一个世界场景，使得Φ(w)存在，其中Φ如等式(7)所示。那么w是不适定的，即DΦ(w)是秩亏的，当且仅当存在一个四次曲面Q�R3，满足以下条件：0• Q通过给定的世界点Γ1,...,Γ7；0• 并且Q包含给定相对姿态的基线。0这里的基线ℓ是通过两个相机中心的世界线。0现在，四次曲面的条件与定理1中的条件相同，只是第三个条件（源自校准）不存在。我们对定理1和定理2的证明都是通过展开存在一个非零核向量的正向雅可比矩阵的要求。04.3. 不适定的图像数据0这里我们描述了5点问题和7点问题的不适定图像数据的轨迹。这些结果在两个最小问题中都依赖于多项式结构（如备注1所述）。具体而言，证明使用了代数几何中Sturmfels[34]的已知事实。与[34]相比，本小节的主要贡献是我们得到了可行的计算方案，用于实际可视化不适定图像数据的轨迹。对于基础矩阵和本质矩阵的两种情况，我们提供了基于数值同伦延拓[32]解多项式方程的方法。这些方法在Julia软件包HomotopyContinuation.jl[6]中实现，在桌面计算机上分别在约10秒和约30秒内终止。详细信息请参见补充材料。0定理3（E的不适定图像数据）考虑第2节中的5点问题。设((γ1,¯γ1),...(γ5,¯γ5))∈(R2×R2)×5为图像数据。那么x是不适定的，即存在某个兼容的世界场景是不适定的，当且仅当一定的多项式P在γ1,...,¯γ5的条目中为零。该多项式在γ1,...,¯γ5的每个点上分别具有30次的度数。特别地，如果我们固定γ1,...,γ5的数值但保持¯γ5∈R2为变量，则（一般地）P在y5上专门化为一个30次多项式，并且其消失集是第二个图像平面上的一个30次曲线。此外，给定γ1,...,γ5的值，我们可以通过绘制与第二个图像平面上的各种垂直线相交的曲线的实根来计算该曲线在R2中的显式绘图。0我们将定理3中的曲线称为4.5点曲线，因为它由四个半图像点对（即γ1, ¯γ1, ..., γ5）指定。请参见图4中的示例渲染。0定理4（F的不适定图像数据）考虑第2节中的7点问题。设((γ1, ¯γ1), ..., (γ7, ¯γ7)) ∈ ...0(R2×R2)×7是图像数据。那么x是不适定的，即存在某个不适定的兼容世界场景，只有当γ1, ¯γ1, ...,¯γ7的某个多项式P为零时才成立。该多项式在γ1, ...,¯γ7的每个点上分别具有6次的次数。特别地，如果我们固定γ1, ¯γ1, ..., γ7的数值，但将¯γ7 ∈R2保持为变量，则（一般情况下）P在¯γ7上专门化为一个6次多项式，其零点集是第二个图像平面上的一个6次曲线。此外，给定γ1, ¯γ1, ...,γ7的值，我们可以通过绘制与第二个图像平面上的各个垂直线相交的曲线的实根来计算该曲线在R2中的显式绘图。0我们将定理4中的曲线称为6.5点曲线，因为它由六个半图像点对（即γ1, ¯γ1, ..., γ7）指定。请参见图4中的示例渲染。05. 实验结果0我们的实验结果主要基于合成数据，尽管在本节末尾还展示了一些真实数据的示例。0数据生成：我们生成随机的有效配置，包括世界场景(R, ˆT,Γ1, ..., ΓN)，内部矩阵K，以及图像平面上的2D点对(γ1,¯γ1, ..., γN, ¯γN)，以像素为单位表示。这里N = 5或N =7，取决于相机是否校准。我们按照以下方式生成随机实例：0• R：随机3×3矩阵的QR分解给出一个正交矩阵样本；0• ˆT：从半径为1米的单位球上均匀采样的向量；0• Γi：在[1, 20]米范围内均匀采样的具有深度的点；0• K：选择使图像尺寸为640×480，焦距设为32毫米，主点为图像中心；0• (γi, ¯γi)和(γi, ¯γi)：Γi在两个图像上的投影。0我们丢弃任何2D点落在图像边界之外的实例，或者3D点位于相机背后的情况。0不稳定性揭示：我们首先旨在证明，无论是校准还是非校准的相对位姿估计最小问题，都存在实际的不稳定性。为此，我们生成了3000个合成的最小问题，分别用于校准/非校准，如上所述。对于每个最小问题实例，我们对从球面高斯分布N(0,σ^2I2)中绘制的图像点添加独立同分布的噪声，其中σ是不同噪声水平。然后，我们分别解决原始问题和扰动问题，并进行比较。如果估计不稳定，我们定义为任一条件成立。89410以下标准之一成立时，我们称之为不稳定：(i)扰动点的解的误差较大：归一化后的基础或本质矩阵的误差由e = mean(abs(abs(¯M./M) -11�))定义。这里“./”表示逐元素除法，M是真实模型，¯M是最近的估计模型，11�是每个元素为1的3×3矩阵。如果e超过阈值τ，则满足(i)。 (ii)真实解的数量变化：这种行为令人困扰，因为如果真实解的数量发生变化，真实的极线矩阵可能会消失到复平面中。图3(a)和(b)显示了在各种小到中等噪声水平和误差阈值下的3000个实例中错误估计的比例。很明显，对于随机扰动，即使噪声很小，错误案例的比例也不能忽视。在实践中，通过RANSAC通过最大化内点的数量来淘汰不稳定的实例。即使所有对应关系都是内点，相对位姿估计的不稳定性仍然需要RANSAC来克服。0(a)0(b)0图3.在不同噪声水平σ和误差阈值τ下，3000个随机合成极小问题中错误估计的比例，分别为（a）基础矩阵和（b）本质矩阵。0不稳定性检测：现在将第4.3节中描述的方法应用于计算未校准情况下的4.5点退化曲线和校准情况下的6.5点曲线。情景是固定了4（6）个对应点，对于第5（第7）个对应点，固定了一个图像上的点，并导出了所有不稳定点的轨迹作为曲线。图4显示了在第二个图像平面上绘制的几个样本曲线以及给定的图像点。对于未校准情况，6.5点曲线的次数为6，而对于校准情况，4.5点曲线的次数为30。这些曲线将图像平面分割成不同的连通分量，其中实数解的数量在局部上是恒定的。用[4]的术语来说，这些曲线是“实际判别位置”。在另一个实验中，我们将3000个随机合成的极小问题分为三类：稳定情况、不稳定情况和边界情况（鉴于条件数是稳定性的连续指标）。0(a)0(b)0(c)0(d)0图4.定理3和定理4中X.5点退化曲线的样本结果。用于计算曲线的对应点显示为绿色；红色点分别是校准和未校准相对位姿估计的第5个/第7个对应点。红色曲线是使用同伦连续计算的X.5点曲线。稳定性与第二个点到曲线的距离直接相关。（a）未校准估计的稳定配置。（b）未校准估计的不稳定配置。（c）校准情况下的稳定配置。（d）校准情况下的不稳定配置。0(a)0(b)0图5.按照稳定情况（绿色）、不稳定情况（红色）和边界情况（蓝色）对最后一个点到退化曲线的距离进行排序的直方图。（a）未校准估计。（b）校准估计。稳定和不稳定的类别通过与曲线的距离分离。0稳定性）。在这里，一个实例根据n=20个扰动中错误估计的数量进行排序，用ˆn表示。如果ˆn∈[0,n/3]，我们将该实例计为稳定；如果ˆn∈[2n/3,n]，我们将该实例计为不稳定；如果ˆn∈[n/3,2n/3]，我们将该实例计为边界。在这个实验中，我们使用τ=0.5和σ=0.3。对于未校准的情况，在不稳定的情况下，从第7个点到6.5点曲线的平均距离为2.35像素，而在稳定的情况下为22.12像素。对于校准的情况，在不稳定的情况下，从第5个点到4.5点曲线的平均距离为0.32像素，而在稳定的情况下为14.95像素。从这些统计差异（见图5），我们观察到稳定和不稳定的类别可以通过在最后一个点到X.5点曲线之间的距离上进行阈值处理来区分。89420(a)0(b)0图6.在不同噪声下显示退化曲线稳定性的说明性结果显示了曲线的显著稳定性。（a）稳定未校准配置的退化曲线。（b）不稳定未校准配置的退化曲线。校准估计的曲线在补充材料中显示。0图7.两个距离之间的差异的直方图：从目标点到未扰动的X.5点曲线的距离；以及从目标点到其他点上扰动的X.5点曲线的距离。0稳定性的不稳定性：在这里，我们展示了退化曲线在存在噪声的情况下大多数是稳定的，因此我们的想法不仅在理论上是正确的，而且可以在噪声图像的实际环境中使用。图6显示了在对应点添加噪声时X.5曲线的一些示例。无噪声和有噪声情况下点到曲线距离的对数差异的分布，图7显示扰动不会显著改变距离。0使用真实数据的说明：基于上述，可以使用X.5点曲线与真实图像一起检测近退化的最小情况。为了证明这一点，我们使用RANSAC2020数据集提供的图像对，其中有标准的点对应关系。图8显示，对于与地面真实值相比具有较大误差的解，剩余的选定点接近退化曲线。更多结果请参见补充材料。在另一个使用真实数据的测试中，我们随机从数据集中每个图像对的内点对应关系中取出1000个内点最小样本。我们发现只有50%的最小配置与退化曲线的距离较大，因此大约一半是不稳定的。然而，在对所有内点运行RANSAC并选择获胜假设之后，我们发现约90%的获胜假设与曲线的距离较大。因此，RANSAC选择了稳定的配置。0（a）0（b）0（c）0图8.一个使用真实数据演示具有所有内点对应关系的不稳定最小配置的示例。（a）一对图像的地面真实极线几何。（b）7点算法找到的最接近的解，给出7个内点。（c）放大的图像显示剩余点接近退化曲线，表明这是条件较差的数据。06. 结论0在本文中，我们开发了一个通用框架来分析多视图几何中最小问题的数值不稳定性。我们将其应用于相对姿态估计问题，即常见的5点和7点问题。我们推导了条件数公式，并对不适定的世界和图像场景进行了表征。我们通过对合成和真实数据进行数值实验来支持我们的理论发现。我们观察到，当图像数据接近于4.5点和6.5点退化曲线时，会出现数值不稳定性，这些曲线用于描述定理3和定理4中的不适定问题实例。本文将最小问题的数值不稳定性与SfM重建中RANSAC的功能相关联。即使给定所有的内点数据，RANSAC仍然需要克服相对姿态估计的病态条件。在未来的工作中，我们可以将我们的理论应用于其他最小问题，例如部分校准的相对姿态估计或三视图几何。此外，我们希望开发一种实时的方法来识别和过滤出条件较差的图像数据。这样可以在解决最小问题和运行RANSAC之前应用。致谢：作者们非常感谢在2019年春季他们参加了ICERM的代数视觉研究集群，布朗大学，他们在那里相识并种下了这个项目的种子。Kimia和Fan感谢NSF奖励1910530的支持。89430参考文献0[1] D. Ablan.数字摄影用于3D成像和动画。Wiley出版社，2007年。10[2] S. Agarwal, Y. Furukawa, N. Snavely, I. Simon, B. Curless,S. M. Seitz, and R. Szeliski.一日建造罗马。ACM通信，54（10）：105-112，2011年。10[3] D. Barath, J. Noskova, M. Ivashechkin, and J. Matas.MAGSAC++，一