曼哈顿世界中拟全局最优有效消失点估计方法

1646Manhattan世界中的拟全局最优有效消失点李浩昂1赵继2巴赞3陈文1刘哲1刘云辉1香港中文大学2TuSimple中国3韩国KAIST{hali，wenchen，zliu，yhliu}@ mae.cuhk.edu.hkzhaoji84@gmail.combazinjc@kaist.ac.kr摘要从平行3D线投影的图像线在称为消失点（VP）的公共点处相交。曼哈顿世界有三个正向副总裁。在曼哈顿世界中，给定校准图像中的几条线，我们的目标是通过三个未知但寻找的VP对它们进行VP估计可以重新公式化为计算曼哈顿帧和相机帧之间的旋转。为了计算这种旋转，现有的方法是基于数据采样或参数搜索，并且它们不能同时保证精度和效率。相反，我们建议将这两种策略混合起来。我们首先通过两个采样图像线计算上述旋转的两个自由度（DOF），然后基于分支定界搜索最优的第三自由度我们的采样通过减少搜索空间和简化边界计算来加速我们的搜索。我们的搜索对噪声不敏感，并且在最大化内点数量方面实现了准全局最优对合成图像和真实图像的实验表明，我们的方法在准确性和/或效率方面优于最先进的方法。1. 介绍消失点（VP）是从平行3D线投影的一组图像线的交点它已成功应用于各种领域，如运动结构[15，23]，场景理解[14]和SLAM [21，22]。结构化环境（通常是人造场景）表现出特定的规律性，如并行性和正交性。曼哈顿世界[11]适用于具有三个相互正交的主导方向的场景，这三个主导方向对应于三个正交的VP（如图2所示）。①的人。在曼哈顿世界中，给定校准图像中的几条线，我们的目标是通过三个未知但寻求的VP对它们进行聚类。曼哈顿框架（MF）[30]被广泛用于模拟曼哈顿世界的结构。MF的三条轴线对应着曼哈顿世界的三个主导方向图1. 我们通过三个未知但寻求的正交VP将一组图像线聚类为三组VP估计可以重新公式化为计算MF和相机帧之间的旋转。图1示出了相机中心和VP定义了与MF轴对齐的三个正交3D方向。基于该约束，VP估计可以被重新公式化为计算MF与相机帧之间的旋转（下文中称为“MF旋转”）。为了计算这种旋转，最先进的方法是基于数据采样[4，25，35]或参数搜索[5，6，24]。他们以不同的方式假设MF旋转，并检索最适合大多数图像线的最佳旋转。基于采样的方法（通常使用RANSAC [13]）假设采样图像行的有限MF旋转。由于采样的不确定性，它们不能保证最大化内点数量的全局基于搜索的方法（通常使用分支定界（BnB）[20]）直接面对旋转空间上假设的无限MF旋转，并不断缩小搜索范围。虽然它们在最大化内点数量方面实现了全局最优性，但它们的效率受到高维搜索空间和成本函数边界复杂计算的限制相比之下，我们建议混合采样和搜索策略来计算MF旋转的三个自由度（DOF）。我们首先有效地估计两个自由度的两个采样的图像线，然后使用BnB搜索最佳的第三自由度。我们的方法的主要优点是，它实现了高效率和高精度。为了提高效率，我们利用采样通过减少搜索空间来加速搜索。此外，我们的旋转参数化有助于有效地计算我们的成本函数的紧界，这进一步加快了曼哈顿框架（MF）消失点（VP）曼哈顿世界图像平面相机帧1647我们的搜索因此，我们的方法比纯基于搜索的方法更有效[5，6]。为了准确性，我们搜索最佳的第三自由度，最大限度地提高内点的数量。由于我们的搜索，我们估计的MF旋转可以被视为虽然由于我们的采样可能无法实现全局最优，但我们的方法对噪声不太敏感，并且比纯基于采样的方法检索更多的内点[4，25，35]。总体而言，我们提出了一个准全局最优和有效的VP估计方法，通过混合采样和搜索策略。我们的主要贡献是：我们利用两个采样的图像线来有效地计算MF旋转的两个自由度。我们的采样内点阈值X3X2X1内点异常值RANSACBnB我图2. 说明不同的方法来获得最佳的线拟合大多数内点，给定的输入点{xi}被噪声和离群值破坏。RANSAC线必须通过两个点（这里是x1和x2），并将x3视为异常值，因为它的距离高于阈值，而BnB线和我们的线都将x3视为内点。拟合大多数内点的假设。此外，Tardif [31]使用了许多假设来定义图像线描述，通过减少搜索空间来加速搜索简化了边界计算。我们利用BnB搜索MF旋转的最佳第三自由度，通过固定其他两个自由度，实现准全局最优。我们的搜索对噪声不敏感，并获得了大量的内点。对于纯基于搜索的方法无法处理的情况，我们的方法提供了正确的VP，也比纯基于采样的方法更准确。实验表明，我们的方法在准确性和/或效率方面优于最先进的方法2. 相关工作现有的VP估计方法可以根据所使用的算法分为四个主要类别，即Hough变换[2，28]，期望最大化[1，12]，数据采样[4，25，31，35]和参数搜索[3，5，6]。基于Hough变换的方法[2，28]计算所有图像线对的交点，并生成这些交点的直方图。具有大量条目的仓对应于VP。然而，它们经常导致多次和/或错误检测，并且也忽略了VP的正交性约束。此外，基于期望最大化的方法[1，12]交替地聚类图像线他们为每一个图像行分配一个标签，指示它属于哪个聚类。它们使用具有相同标签的线来计算VP，这反过来又更新标签。然而，他们是敏感的初始解决方案，lution和易于收敛到局部最优。基于数据采样的方法[4，25，31，35]例如，[13]及其变体[32，36]。最先进的方法[4，25，35]首先对三个图像行进行多次采样，以假设有限VP三元组或MF旋转（早期的方法类似于[29]单独假设VP，准确性和效率较低）。然后，他们通过计算符合这一假设的图像线的数量来检验每一个适应度表示图像线通过VP或其相关联的投影平面法线正交于MF轴直到阈值。在那之后，他们找回了tors和聚类线的J-连锁[32]，RANSAC的变体。然而，它未能强制执行的垂直点的正交性时，聚类图像线。注意，由于采样不确定性，上述基于采样的方法不能保证在最大化内点数量方面的全局最优性。基于参数搜索的方法通常采用BnB [5，6]。他们直接面对无限的假设MF的旋转空间参数化的欧拉角或他们通过不断缩小搜索范围来搜索最适合大多数图像线虽然它们保证了全局最优性，但它们的效率并不令人满意（一般每个图像超过5秒Joo等人[18]最近提出了一种新的策略，以显着提高BnB的效率，但它不适用于图像线（它本质上适用于3D平面法线）。此外，Bazinet al.[3]提出在旋转空间上采样许多MF旋转（即，准穷举搜索），并选择使内点数目最大的一个。虽然它适用于平滑视频，但它在计算上可能是昂贵的，特别是对于单个图像或当没有关于相机取向的先验信息可用时。总体而言，现有的基于抽样或搜索的VP估计方法与此相反，我们提出了这两种策略的混合，实现了高精度和高效率.此外，由于MF旋转的正交性，我们的方法强制执行VP或正交性。3. 算法概述首先以二维直线拟合为例说明了本文方法的思想和优点。如图2、给定一组点，我们的目标是获得拟合大多数内点的最佳直线（由于存在离群点，直接最小二乘拟合是不合适的）。我们用线上的一点来表示一条线（即：线位置）和线方向。RANSAC [13]通过多次采样两个点来假设一组线线···1648W联系我们−∝×联系我们·ǁ ǁ ≡ ǁ ǁ ǁǁ由点x1和x2定义的是它的最优假设，但不能拟合内点x3。此外，BnB [20]搜索关于线位置和线方向的参数空间（对应于无限假设的线）。虽然BnB获得了全局最优的线拟合所有的内点，它的效率是不令人满意的，由于其高维搜索空间。相比之下，我们亲-曼哈顿框架n1L1z22X2π1D1L1图像平面R（）L2S2 e2姿势首先仅采样一个点以固定线位置，然后在线方向空间上搜索我们获得了通过点x1的最佳直线，并且也拟合了所有的内点。从某种意义上说，我们的战略是我们混合了数据采样和参数搜索策略。为了提高效率，我们利用采样来加速我们的搜索，将整个搜索空间减少到线方向空间。为了准确起见，我们搜索最大化内点数量的最佳线为了计算MF旋转，我们提出了一种混合方法来估计其三个自由度。具体来说，给定一组图像线，我们首先在第4节中通过两个采样图像线估计两个自由度。这与上述估计相似。线的位置。然后我们寻找最优的第三自由度相机帧图3.图像线{l1，l2}与3D线相关联{L1，L2}与两个MF轴对齐。我们使用{l1，l2}通过未知但寻求的角度θ来参数化MF旋转RM→C。然后，我们参数化的3D线方向d2通过强制，ING两个约束。如图 3，首先，d2平行于平面π2。因此，我们将d2表示为π2的已知基s2，e2的线性组合，即d2=s2+λe2，其中λ是未知组合系数。第二，3D线方向d1和d2相互正交，即 d≠1d2=0. 我们将这两个约束条件结合起来，通过λ=（d）1s2）/（d）1e2）。然后我们将λ代入第一个约束，得到d2为最大化第5节中的内点图像线的数量。d=sd1s2−埃尔德·埃尔德斯2-ds e，（2）它类似于上面的线方向搜索。第一季第212 212 24. 通过采样在这一节中，我们提出了一种新的方法来计算两个自由度的MF旋转的两个采样图像线，并参数化的MF旋转由一个单一的参数。4.1. 双线MF旋转参数化我们假设摄像机的固有矩阵从校准中已知[17]。如图3，为了计算MF旋转的两个DOF，我们利用两个采样的IM。年龄线{l1，l2}，其相关联的3D线{L1，L2}是其中““表示不考虑比例的相等性。通过替换Eq。（1）到Eq.（2），我们可以用θ来参数化d2。d2的每个元素都表示为d2，i（θ）=ω2θ，iα其中ω2，i是已知的2D向量。 注意d1和d2的元素都由α= [sin（θ），cos（θ）]π组成。设d3表示与d1和d2正交的3D方向，我们通过d3=d1d2计算它。基于Eqs. （1）和（2）中，d3也由θ参数化。d3 的 每个 元 素 表 示 为 d3 ， i （ θ ） =iβ（i=1，2，3），其中i是已知的三维向量，β=[sin2（θ），sin（θ） ·cos（θ），cos2（θ）]θ。d和d的范数满足：与两个MF轴对齐，即L和l对应不同的2 3 212 d3=其中，“知”是“知”。注意，与VPS. 我们通过内在矩阵[35]将图像归一化为计算1）投影平面π1的法线n1乘以l1，范数d11、d2和d3相对于未知角θ变化。我们通过d<$=对d和d进行归一化，和2）d/π的投影平面π2的基{s2，e2}√2 3 2端点湖 我们参数化未知的3D线直径-2µmβ和d<$3=d3/分别为µ πιβ。2基于上述正交单元3D方向第1、2段 L1，L2如下。我们首先考虑3D线方向d1。我们定义{d1，d<$2，d<$3}，我们将MF旋转RM→C从与投影平面法线n1正交的方向w，MFM到相机框架C。如图3、3D线L1和L2与M的两个轴对齐。即n<$1w=0，设w为零空间的ny单位基n=1（w不是唯一的）。然后我们绕着在不失去一般性的情况下，我们将d1，d<$2和d<$3联系起来，已知旋转轴n1的未知但寻求的角度分别与M的x轴、y轴和z轴相交。协议-因此，它们在M中的坐标是dM1 =[1，0，0]，d<$M2 为θ∈[0，π]，将w与方向d1对齐，d1=R<$（n1，θ）w，（1）其中R（·，·）表示轴角表示[17]。[0，1，0]m 和 M3= [0，0，1]基于约束 RM→C[dM1，d<$M2 ， d<$M3]=[d1 ， d<$2 ， d<$3] ， 我 们 得 到 MF 旋 转RM→C为基于等式（1），我们将d1的θ。的每个元素RM→Cω1ω⊤ αω2α，1αω⊤ αψ1⊤β1ψ⊤β√d1表示为d1，i（θ）=ω1，iα（i=1，2，3）其中ω1，i是一个已知的二维向量，α=[sin（θ），cos（θ）]π。常态（θ）=一、二ω1α，3α 2002年2月，2ω2α，LeyDπ22Σ16493α2ψ3⊤βµ⊤β . （三）的d 是1，因为它是从单位向量w旋转的。`x` x1d1（θ）d< $2（θ），d<$3（θ）1650--−KKKs=1s=1当量 （3）表明我们的MF旋转由3D方向组成d1，d<$2 ，d<$3. 实质上，这些方向编码MF旋转的三个DOF。我们使用图像线 l1和 l2来估计它的两个自由度，通过方程：（1）和（2），并且通过单个参数θ来参数化MF旋转编码其第三自由度。因此，我们将旋转空间减少为1D空间，这加快了我们的搜索速度（见第5.2节）。此外，我们的参数化有助于有效地计算我们的成本函数的严格边界，这进一步加速了我们的搜索（见5.3节）。4.2. 对两条图像线进行在第4.1节中，为了计算MF旋转的两个DOF，我们使用对应于两个不同VP的两个采样图像线。然而，我们没有关于所提取的线中的哪两个图像线满足该假设的先验知识。此外，所提取的线可能被不对应于任何VP的离群值破坏。-π/20π/2-π/20π/2图4.图像的线条及其方向的直方图。与具有高基数的箱相关联的几个几乎平行的图像线对应于相同的VP。最佳MF旋转RM→C（θ）使其相关联的3D线与MF轴对准的内点图像线的数量最大化。我们提出的数学公式如下。 我们用[RM→C（θ）]m（m=1，2，3）表示MF旋转RM → C（θ）的第m列（即第m个MF轴）。在无噪声的情况下，对于内层图像线lk，其相关联的单位投影平面法线nk与MF轴[RM→C（θ）]m正交（见图10）。（3）第三章。在存在噪声的情况下，我们将残差定义为..m（θ）=. n∈[RM→C（θ）]m. .（四）K K为了解决这些问题，我们随机抽取两幅图像因此，我们将线lk定义为内点，如果。其残基-行S次，以保证至少一次采样满足ual_m（θ）小于阈值τ= cosπ π，我们的假设（称为“有效”抽样）。我们计算k2 90◦S遵循RANSAC [13]，S=log（1-c），其中c是log（1−p）置信水平，p是两个样本即角度误差小于2。 对于第s次假设MF旋转RMs→C（θ）∈R，我们计算其在K条提取线中的内点数目Ns（θ）为线对应于两个不同的VP。我们将c设为0.99，设p为15%，则S = 28。KNs（ θ）=.mΣfk（θ），（5）我们还提出了一种提高效率的方法，抽样的稳健性图4、在众多的实践中，其中f. m（θ）k=1m=1代表;设置内点函数，即在某些情况下，至少一个VP对应于一组几乎平行的图像线[35]。我们生成一个直方图，F. m（θ）˚1，如果m（θ）≤τ; 0，否则。（六）图像线方向。如果具有最高基数的箱对应于一个尖峰（见图中的红色箱），4），我们从这个bin中采样第一行，从设Ns（θ）表示Ns（θ）的未知最大值. 我们目的是找到1）最优假设R<$M→C（θ）∈R（即s<$∈{1，···，S}）; 2）其最优参数θ<$∈ [0，π]，实现{Ns（θ）}S的全局最大值为剩余的仓（否则我们使用随机采样）。RM→Cs=1˚因此，我们将p设为30%，13. 在S次迭代之后，（θ）=arg max{Ns（θ）}S.（七）θ，θs=1我们假设SMF旋转{RMs→C（θ）}S（其中与[25，35]所用的代数误差相比，我们的方程中的残差θm（θ）（5）对应于几何误差未知的第三DOFθ）通过等式（三）、请注意，我们可以生成-有不止一个有效的和几个无效的假设。我们在第5节中有效地确定了最优解。5. 寻找第三自由度在本节中，我们搜索MF旋转的第三自由度。我们将搜索建模为内点集最大化，并通过BnB求解此外，我们提出了一个有效的方法来计算我们的成本函数的紧界。5.1. 内点集最大化在第4.2节中，我们假设SMF旋转R=K这才是最有意义的[17]。 注意虽然我们通过计算MF旋转的两个自由度来简化MF旋转，求解方程：（7）相对来说，挑战性较大。首先，线簇和参数θ都是未知的，这构成了一个非凸问题[10]。其次，我们减少了搜索空间的假设几个无效的（或次优）MF旋转的成本理论上，对每个假设进行检验并在θ的区间[0，π]上进行穷举搜索可以找到最优解，但由于复杂度高，不实用。此外，梯度下降法[7]对假设和参数的初始化敏感，可能陷入局部最优。{RMs→C（θ）}S（具有未知的第三自由度θ）。为了获得1651R最优MF旋转存在两个挑战：1）其中，如何确定最优假设RM→C（θ）;2）对于RM→C（θ），如何获得其最优参数θ。我们将这两个挑战作为内点集最大化问题来解决，lem [13].给定一组图像线，我们的目标是找到5.2. 基于BNB我们使用BNB来求解Eq.（7）寻找最优的假设MF旋转及其最优参数。BnB是一种常用的方法，它能提供最大化内点个数的全局最优解. 已经1652⊤KK··关于我们····。.√用于各种应用，如摄像机姿态估计[10，16，27]和点集配准[8，9，34]。该算法将搜索空间划分为若干个子空间，并计算每个子空间代价函数的上界和下界。如果一个子空间的相关边界证明它不包含最优解，则该子空间被丢弃（紧边界因此加速丢弃子空间）。剩余的子空间被进一步划分和丢弃，直到操作完成。（一）公司简介全球并购电子邮件最大值地方监测地方监测最低限度最大值（b）第（1）款联系我们全局最大（c）第（1）款在我们的上下文中，搜索空间表示参数θ的区间[0，π]，并且成本函数表示等式中的内点的数量。（七）、图5（a）示出了每个假设的MF旋转对应于二叉树。我们连续地划分θ的原始区间[0，π]，并将子区间视为子节点。对于第s棵树的节点Θ，我们将内点的数量Ns（Θ）分配给它（参见等式10）。（5））。请注意，Θ表示θ的区间，而不是一个数字。因此，我们计算界限而不是Ns（Θ）的具体值。我们分别用Ns（Θ）和Ns（Θ）表示Ns（Θ）的上下界，并在5.3节介绍如何计算它们。我们采用最佳优先搜索策略[34]，即上限高的区间具有高优先级。下面我们以一些树为例来说明如何寻找最优假设及其最优参数。如图5（a），我们使用红色树（“ r ” ） 来 显示图5. （a）将与以下相关联的参数区间Θ内点的数量N（Θ）。{I，II，III. }表示划分的数量。（b）丢弃无效（或次优）假设的MF旋转。(c)停止标准。（a）或（c）中的红点表示由区间中点计算的内点数量。总之，我们通过固定采样计算出的MF旋转的两个自由度来搜索MF旋转的第三个自由度，从而有效地获得准全局最优MF旋转。此外，对于具有由离群值定义的“假”MF的情况相比之下，我们的方法提供了准确的VP感谢我们的混合策略，如将在实验中所示。5.3. 内点个数的界我们提出了一种新的方法来有效地计算紧界的内点的数量，即。第5.2节中使用的Ns（Θ）和Ns（Θ）。我们从计算方程中的残差θm（θ）的界限开始。（四）、通过替换Eq。（3）进入我们对最佳参数的搜索。 Nr（ΘIII-2）小于km当量（4）中，我们将θk（θ）重写为三种不同的类型：比Nr（ΘIII-1），证明θ的最优解不是在间隔ΘIII-2内。因此，我们舍弃ΘIII-2。到.。ξ⊤.α。，m= 1（MF的x轴）;为了加速搜索，我们还计算了联系我们我的宝贝.间隔ΘIII-1，表示为θθIII-1. 当Nr（ΘII-2）m（θ）=好吧ζ⊤α/联系我们你好，m= 2（MF的y轴）;联系我们（八）大于Nr（ΘIII-1），我们仍然丢弃节点ΘII-2因为Nr（ΘII-2）小于Nr（θ III-1）。此外，如图5（b），我们使用绿色树（kL. β/`˛¸xQ联系我们.你好，m = 3（MF的z轴）。联系我们Qµ蓝树（其中，已知的k、k和k由已知的esis。 对于每棵树的剩余区间，我们计算333其相关内点数量的界限（见第5.3节）。然后我们计算这些上界的最大值和这些下界的最小值，分别称为局部最大值和局部最小值。局部最大值Nb（ΘIV-1）低于局部最小值Ng（ΘIV-2），证明了RMb→C（θ）的假设较不成立。比RMg→C（θ）的假设更精确。因此，我们放弃了蓝色的树，只搜索红色和绿色的树。此外，对于所有这些树，我们计算最大-它们的局部极大值的mum，这被称为全局极大值。如图图5（c）中，红树的区间ΘV-1满足我们的停止准则。具体地，由其中点Θmax-1计算的内点的数量等于全局最大值。我们把RMr→C（Θ<$ V-1）作为最优MFω1，ii=1，ω2，ii=1和ωii=1，（3）分别;由sin（θ）和cos（θ）组成的α和β，以及已知的µ，在第4.1节中定义。当量（8）表明，θ m（ θ ） 的 元 素 满 足 两 种 形 式 ： 1 ） asin （ θ ） +bcos（θ），称为“线性三角多项式”，记为“L“; 2）csin 2（θ）+dsin（θ）cos（θ）+ecos 2（θ），称为“二次三角多项式”，记为“Q“。我们将计算残差λm（θ）的界重新表述为计算其元素的界，即三角多项式L和Q。为了计算L的边界，我们将其转换为L=a·sin （ θ ） +b·cos （ θ ） =u1 ·sin（θ+v1），其中u1=a2+b2，v1=arctan（b/a）.为了计算Q的边界，我们将其转换为RR（）我 [0,]1号线-2-2N（氮）下界电子邮件：info@jsz.com日本语中文（简体）`1653Q=c·sin2 （ θ ） +d·sin （ θ ） ·cos （ θ ） +e·cos2（θ）旋转，因为它最大化内点的数量我们不考虑绿树，因为它的局部最大值不是=（d/2）·sin（2θ）+.Σ（e-c）/2·cos（2θ）+（c+e）/2（十）高于（至多等于）全局最大值。=u2 ·sin（2θ+v2）+w2，1654M→C.Q=u2+w2.3π3πKK1--2θ+v2]，222111221122（θ）。.Σ2122如果Kπ3πKKK2--图6.由正弦函数表示的三角多项式的曲线：（左）方程中的线性三角多项式L。（9）;（右）方程中的二次三角多项式Q。（十）、算法1：MF旋转计算输入：在校准图像中提取的线{1k}。1 第一步-通过采样估计两个DOF：2 对两个图像行采样S次（见第4.2节）;对于每对采样线，4使用以下公式参数化假设的MF旋转：旋转角θ由等式（3）;5端6 第二步-搜索第三个DOF（θ）：其中u2=√d2+（e−c）2/2，v2=arctan.Σ（e-c）/d和7个重复8对于每个假设的MF旋转Rs（θ），w2=（c+e）/2。因此，我们用sin（θ+v1）和9表示L和Q。sin（2θ+v2）。u 1和u 2的符号（分别取决于a和d的符号。 无损失11为了具有一般性，我们引入了u1>0和u2>0的情形。12回想一下，未知参数θ在[0，π]内，并且在Eq.（9）和v2在方程。（10）两者都在[-π，π]之内。13除以θ的剩余间隔（最佳优先）;对于每个子间隔，对于每一图像线Lkd0计算多项式的边界方程。（11）和（12）;端因此，θ+v2 2在[−π，3π14]范围计算内点Q在[−π，5π]范围内。图6示出了L和Q的曲线，由等式（13）;我们用它来计算L和Q的界限如下。15给定由Θ=[θ，θ]表示的θ的区间，我们首先16端丢弃θ的次优区间（见图1）。5）;计算1）L的定义域，即D= [θ+v，θ+v]∈[-，]（用[D，D]表示），和2）Q的域，17端部18丢弃无效的MF旋转假设（见图10）。5）;19 直到满足我们的停止准则（见5.2节）。即 D2=[2θ+v2，2θ+v2]∈[−π，5π]（记为[D2，D2]）.输出：最佳MF旋转RM→C然后，我们有效地获得范围，即。严格界限的L和Q。具体地说，如图6（左），我们通过判断是否平稳得到L的严格界点π在其定义域D1内，vals2 [26]. 与文献[5，6]相比，我们得到了更严格的界2μL=u1·minu.Σsin（D1），sin（D1）;如果π∈D;（十一）更有效地计算残差原因是：1) 我们的三角多项式的界限是严格的（没有任何放松），并通过简单的代数（D1）中的u1 ·max s，（D1）中的s则不同.如图6（右），我们得到了Q的严格界通过判断稳定点{π，3π}是否在操作; 2）我们放松我们的剩余边界（通过除法操作），并且不重新计算我们的对于θ1（Θ）的残差边界。它是一个域D2，Q=−u2+w222. π如果2∈D2;2∈D2K基于我们的残差和方程的紧界（5）、最后我们计算出内点个数的界第5.2节中使用的Ns（Θ）和Ns（Θ），。.Σ。π2003年，Σ。ΣΣ当满足以下条件时，则Q=u2 ·minsin（D2），sin（D2）+w22∈D23π;[Ns（Θ），Ns（Θ）]=f<$m（Θ），fKm（Θ）K、（十三）Q=u2+w2..2∈/D2（十二）k=1m=1Q=−u2+w2∈/D23π其中，[f，f]具有基于等式的三种类型的值。（6）：1）。Σ如果为2;Q=u2 ·maxsin（D2），sin（D2）+w2∈D2[f，f]= [1，1]，如果θ≤τ，即图像线Lk肯定是。Q=u.Σ·最小值。sin（D），sin（D）<$+w.2∈/D2）[f，f]=[0，0]如果τ≤τ（Θ），即lk绝对是一个Q=u2 ·maxsin（D2），sin（D2）+w2∈/D2基于由方程得到的L和Q的界。（11）和（12）中，我们计算等式（11）中的残差λ m（Θ）的 界 限 。（八）、具体来说，对于θ1（Θ），我们使用L的界限;对于θ2（Θ），我们使用L，Qµ的界限;对于θ3（Θ），我们使用Q，Qµ的界限。我们的残差界计算利用了单个区间1的绝对值运算和/或两个区间1之间的除法运算。ππL=12222 .1655离群值;3）[f，f]= [0，1]，如果τ（Θ）< τ< τ（Θ），即是否lk是一个不确定的内点。我们的全MF旋转计算VP估计方法在算法1中描述。6. 实验我们对合成图像和真实世界的图像进行了实验。源代码和补充材料-..ΣΣ..里亚尔可在我们的项目网站3上查阅。我们列出州-1 .一、[x，y]。 =1000000（|X|、|y|），max（|X|、|y|），如果x·y>0;. [x，y]。 =ΣΣ2[x，y]/[x′，y′]=min（x，x，y，y），max（x，x，y，y）.0，max（|X|、|y|），如果x·y≤0，其中x和y表示较低的值，x′y′x′y′x′y′x′y′区间的上界3https://sites.google.com/view/haoangli/projects/iccv-vp1656上下界剩余间隔（%）·[35]第三十五话J-Linkage [32]BNB [5]我们92 94 96 98100 92精密度（%）94 96 98100召回率（%）200150100100806040图7. 无异常值情况下的准确度比较：（左）前-50（右）回忆。我们用蓝色和青色显示平均值和中位数，（我们运行BnB[5]一次，并以灰色显示其结果）。0 01009010090123456789迭代次数123456789迭代次数8070605010 20 30 40 5060离群值比率（%）8070605010 20 30 40 50 60离群值比率（%）图9.迭代次数方面的效率比较：（左）内点数量的上界和下界的演变（我们报告了假设的局部最大值和最小值图8. 相对于离群值比率的准确度比较：平均精确度（左）和召回率（右）。第2节中介绍的用于比较的最新方法：RANSAC检索由三个采样图像行假设的最佳MF旋转[35]。J-Linkage通过描述符相似性对图像行进行聚类[31]。BnB，其在旋转空间上搜索最优MF旋转[5]。我们基于有效采样概率0.1（小于我们在第4.2节中的概率0.15，因为它对三条3D线的配置有更强的假设）计算RANSAC的迭代次数我们将J-连杆的采样次数设置为500（[31]推荐）。我们还进行了实验，通过调整各种方法的时间预算。为了更公正地比较原始精度，我们报 告 未 经 迭 代 改 进 的 原 始 结 果 所 有 的 方 法 都 在MATLAB中实现，并在3.60 GHz的Intel Core i7 CPU上进行了测试。评价标准。我们根据图像线聚类的精度和召回率评估VP估计准确性[19]。精度由Nc/（Nc+Nw）定义，其中Nc和Nw分别是正确和错误聚类的线召回率由N c/（N c+N m）定义，其中N m是缺失的内点的数量。对于效率评估，除了比较各种方法的绝对运行时间外，我们还比较了BnB与我们的方法在区间划分数量方面的差异[5，20]。6.1. 合成图像我们合成两组或三组平行的3D线。来自不同集合的每两条线是相互正交的。我们用一台合成相机将它们投影，获得两到三组图像线。我们用一个标准差为σ像素的零均值高斯噪声扰动这些图像线的端点。我们通过随机化它们的位置和方向来生成离群图像线。我们的目标是通过未知但寻求的VP来聚类这些图像线。（右）剩余区间比例的演变表1.计算时间比较[35]第三十五话J-Linkage[31]BNB[5]我们时间0.0110.1873.5010.27610.90.80.70.61/20X 1/15X 1/10X 1/5X 1/2X 1X时间成本w.r.t.我们的方法图10. 通过固定我们方法的时间预算并改变RANSAC [35]和J-链接[31]的时间预算来进行F1分数比较。准确度评价。由于抽样的不确定性，我们进行了1000次试验的RANSAC，J-连锁和我们的方法。图图7示出了与3个VP和150个内点线的代表性比较噪声水平为σ= 5。由于噪声的影响，RANSAC无法完全检索内点J-Linkage错误地聚类了几条线，因为它的线描述符可能被噪声污染。BnB成功-完全检索所有内围值。我们的方法实现了高精度和召回由于我们的混合方法MF旋转计算。此外图图8显示了存在离群值时的给定150条线，我们将噪声水平固定为σ=3，并将离群值比率从10%变化到60%。高离群值比率增加了有效抽样的难度RANSAC和J-Linkage对于超过30%的离群值获得了不满意的结果相比之下，我们的方法更稳健，因为它需要更少的样本。请注意，BnB对于高离群值比率变得不稳定，因为它可能检索到由许多离群值定义的“假”MF，这将在第6.2节中进行全面分析。效率评价。我们报告了2个VP和100个内点的代表性检验结果。噪声水平为σ=4。我们首先在迭代次数方面比较BnB与我们的方法。我们假设13个MF旋转由2个有效和11个无效采样（有效性由地面真实聚类标签识别）。图9（左）显示了内点数量的界限的演变。在不失一般性的情况下，我们随机选择了5个无效的hy-[35]第三十五话J-Linkage [32]BNB [5]我们[35]第三十五话J-Linkage [32]BNB [5]我们&&[35]第三十五话[32]第三十二话精密度（%）召回率（%）F1评分··1657[35]第三十五话J-Linkage [32]BNB [5]我们频率20×手动提取的行RANSAC [35]J-Linkage[31]BNB[5]我们3个副总裁，54条线路(100（88.89%）（96.29%，100%）(100%、100%）(100%、100%）图11.使用York Urban Database上手动提取的图像线进行VP估计[12]。 不同的图像线簇是以各自的颜色显示每个图像下面的一对数字代表图像线聚类的精确度和召回率10080601008060LSD提取的线[33]RANSAC [35]（59个真实内点）40 4020 200<9090~92.592.5~9595~97.5>97.50<8080~8585~90岁90~95>95岁精确率（%）召回率（%）图12. 102张YUD图像的精度比较[12]：（左）和（右）的精确度。报告的假设。在第7次迭代时，对于所有无效假设，它们的上界的局部最大值小于我们的第二个有效假设的下界的局部最小值在第9次迭代时，与我们的第二个有效假设相关的区间满足我们的停止准则（见5.2节）。因此，我们的方法只需要9次迭代就可以获得所有的内点。相比之下，BnB需要318次迭代。图图9（右）显示了重新分配比例的演变maining间隔（相对于我们的方法的长度或BnB的体积）。在收敛时，由于我们的严格边界，我们的方法丢弃了大多数区间，但BnB仍然保留了许多区间。此外，我们使用上述数据进行了500次独立试验，并在表1中列出了各种方法的平均运行时间。RANSAC是有效的，但代价是牺牲精度。我们的方法比BnB快得多，并且与J-Linkage相似。此外，我们将我们的方法的时间成本t固定为约0.2s，并将RANSAC和J-Linkage的时间预算从在异常值比率为40%的情况下t对t。 如图10虽然RANSAC和J-链接随着它们的时间预算增加而提高它们的准确性，但是我们的方法在给定相同的时间预算t的情况下实现了最高的F1分数[7]。6.2. 现实世界图像为了评估真实世界图像上的各种方法，我们在约克城市数据库上进行了实验[12]。它是由102个校准的640 - 480像素的图像，每个图像包含一组手动提取的线。这些线是无异常值的，对应于2或3个VP。图11示出了代表性的比较，以及12份报告了各种方法在所有图像上的查准率和查全率。RANSAC和J-Linkage不能同时保证查全率和查准率。BnB稳定地获得所有内点。我们的方法对噪声的敏感性低于RANSAC和J-Linkage，并达到与BnB相似的精度。此外图13示出了一组IM的聚类结果。BnB[5]（81个假内点）我们的（69个真内点）图13.利用被异常值破坏的图像行进行VP估计。一条簇线与其对应VP之间的连接用虚线表示（其投影平面法线与其对应MF轴之间的角度为90±2°）。年龄线由LSD自动提取[33]。许多异常值和部分内点定义了“假”MF，其与比地面真实MF更多的图像线相关联。BnB检索假MF并错误地聚类许多行。相比之下，RANSAC和我们的方法通过分别对与地面实况MF相关联的三条和两条图像线进行采样来获得此外，由于我们搜索MF旋转的第三个自由度，我们的方法获得了比RANSAC7. 结论提出了一种混合MF旋转计算方法来估计Manhattan世界中的VP。我们首先用两条采样图像线计算两个自由度，然后用BnB搜索第三个自由度。我们的采样通过减少搜索空间和简化边界计算来加快搜索速度。我们的搜索是不敏感的噪声，并实现准全局最优。对合成图像和真实图像的实验表明，我们的方法在准确性和/或效率方面优于最先进的方法。在未来，我们将专注于计算一个自由度的采样和两个自由度的搜索。致谢。这项工作部分由中国自然科学基金U1613218基金资助，部分由香港该项目由香港中文大学T Stone机器人研究所的风险投资基金4930745和韩国国家研究基金会（GrantNRF-2017 R1 C1 B5077030）共同资助。[35]第三十五话J-Linkage [32]BNB [5]我们频率1658引用[1] 马修·安东和赛斯·泰勒自动恢复相对相机旋转的城市场景。在CVPR，2000年。2[2] 斯蒂芬·巴纳德。解释透视图像。人工智能，1983年。2[3] Jean-Charles Bazin、Cedric Demonceaux、Pascal Vasseur和Inso Kweon。城市环境中全方位视觉旋转估计与灭点提取。IJRR，2012年。2[4] Jean-Charles Bazin和Marc Pollefeys。用于正交消失点检测的3线RANSACInIROS，2012. 一、二[5] Jean-CharlesBazin、YongduekSeo、CedricDemonceaux 、 Pascal Vasseur 、 Katsushi Ikeuchi 、 InsoKweon和Marc Pollefeys。曼哈顿世界中的全局最优线聚类和消失点估计。 CVPR，2012。 一二六七八[6] Jean-Charles Bazin，Yongduek Seo，and Marc Pollefeys.通过旋转搜索实现全局最优共识集最大化。InACCV，2012. 一、二、六[7] 克里斯托弗·毕夏普。模式识别与机器学习。Springer，2006年。四、八[8] Zhipeng Cai，Tat-Jun C