基于旋转搜索空间的曼哈顿标架估计算法

15213通过划分旋转搜索空间实现葛五伟2，宋宇 *，1，2，张百超2，董泽华21北京交通大学2宗木科技北京摘要一个典型的人造结构可以抽象为曼哈顿世界假设，其中的概念进一步表示为由三个正交轴定义的曼哈顿框架（MF）。MF估计的问题可以被公式化为MF与相机帧之间的旋转（称为然而，整个旋转空间对于求解MF旋转是相当冗余的，这是干扰与旋转空间搜索相关联的那些方法的计算效率的主要因素之一。本文证明了只包含所有MF旋转的空间（称为在限定的MFR空间中搜索，通过分支定界（BnB）框架求解的MF估计同时保证了稳定性和效率。此外，与旋转空间搜索相关联的一般旋转问题被更有效地解决。合成和真实数据集上的实验已经成功地证实了我们的方法的有效性。1. 介绍大多数人造环境通常表现出特殊的规律性，如平行性和正交性，这可以由一组平行和正交的结构线来表示。这些结构形式通常被抽象为曼哈顿世界（MW）[1]假设，其由对应于相机图像平面中的三个正交消失点（VP）的三个相互正交的方向由于其简单性，MW假设已成功应用于许多更高级别的计算机视觉任务，例如相机参数的校准[2，3]，场景本 研 究 得 到 了 国 家 自 然 科 学 基 金 （ 批 准 号 ：200100101000000000000）的资助。61573053、61673385）。※通讯作者宋宇，songyu@bjtu.edu.cn。[7][8][9][10][11][12]自从引入曼哈顿标架（Manhattan Frame，MF）的概念[20]以来，已经有相当多的工作致力于MF估计的稳定性和效率，其中，曼哈顿标架由对应于MW的三个方向的三个正交轴定义。然而，满足这两个性质仍然是具有挑战性的。通过将MF估计的问题公式化为MF与相机帧之间的旋转（称为“MF旋转”）的解，现有技术的方法[ 15、16 ]在整个旋转空间中穷尽地搜索以满足在最大化这些方法是鲁棒的和精确的，足以保证稳定性，但计算效率是棘手的时间关键的应用，例如，SLAM和导航。值得注意的事实是，整个旋转空间对于所有MF旋转都是相当冗余的，这是干扰基于参数搜索的方法（通常使用分支定界（BnB）框架[14]）的计算效率的主要因素之一 本文的目的是划定一个特殊的子空间，它只包含所有的MF旋转（以下称为“MFR空间”）。为了实现这一点，我们证明了整个旋转空间可以均匀地分为24个全等MFR空间，其中任何一个只包含所有的MF旋转。在限定的MFR空间内，MF估计方法，基于BNB的算法，保证全局最优解同时满足稳定性和效率。此外，基于旋转空间定界理论，本文还讨论了基于BnB的旋转空间搜索算法所解决的一般旋转估计问题，如：全景拼接[15，17，35]、相机姿态的估计[13，26]、3D配准[15，33，34]和倾斜平移相机校准[4，5，6]可以得到极大的改进总体而言，本文的主要贡献归纳如下：我们证明了搜索的冗余在整个旋转空间的MF估计。MFR空间的体积仅为整个旋转空间·15214·H·HH理论上证明了半边长为π/4的立方体在由角-轴表示参数化的旋转空间中，仅足以紧密地包围MFR空间，并且然后界定精确的MFR空间。在定界的MFR空间中搜索，通过以下方式提高了基于BnB的 MF估计的效率：具有3个正交方向映射轴来自MW候选MF的3个方向大约25次，这满足了该问题的稳定性和效率。此外，与整个旋转空间搜索相关联的一般旋转问题被更有效地解决。2. 相关工作和必备知识由于现有的MF估计方法都是在参数空间中进行搜索以满足稳定性要求，因此本文首先回顾了相关的工作，然后，对旋转空间进行了参数化。2.1. 现有方法基于期望最大化（EM）的方法[18，19，20]交替地聚类图像线和估计VP。它在期望（E）步骤和最大化（M）步骤之间交替，期望（E）步骤估计给定当前假设的VP的线聚类，最大化（M）步骤计算给定在E步骤估计的线聚类的VP。这些方法对初始解敏感，并且易于收敛到局部最优。基于采样的方法[3，21，22，23]利用RANSAC [24]或其变体[25]。Bazin和Pollefeys[21]提出了一种用于校准相机的基于3线的算法，并且基于该策略，Zhang等人。[23]以更好的方法解决了三线假设，该方法以更少的样本实现了更好的置信水平。注意，这些方法本质上是不稳定的，并且不能保证全局最优性。为了保证稳定性，Bazin等人[15，16]提出了基于BnB框架的正交VP估计方法，其在最大化内点数量方面满足全局最优性。 在[16]中，旋转空间是用欧拉角表示来参数化的，但这种基于区间分析的方法提供了宽松的边界。同时，提出了一种改进的策略[15]通过在由角-轴表示[26]参数化的整个旋转空间中进行穷举搜索。然而，这些BnB框架对于时间关键型应用程序来说通常太慢Joo等人[27，28]最近提出了一种新的策略，以显着提高BnB的效率。它将输入数据转换到一个扩展的高斯图像域，并结合有效的边界函数，以满足稳定性和效率。但是，它本质上适用于曲面法线，但不适用于图像线。为了满足这两个性质，Bazinet al. [29]建议在旋转空间上对许多MF旋转进行图1. MW结构映射到24个候选MF，而没有关于MF的轴方向和三个轴的排列的先验信息。围绕初始旋转（即，准穷举搜索）并选择使内点数目最大的一个。而这种基于跟踪的策略固有地适合于视频序列。最近，Liet al. [30，31]提出了一种准全局最优算法，通过对MF旋转假设的一个或两个自由度（DOF）进行采样，然后使用基于BNB的策略搜索其他DOF该方法巧妙地将抽样策略和搜索策略相结合，在效率和精度之间取得了折衷，但由于抽样机制的原因，该方法不能完全满足最优性。2.2. 旋转空间由单位四元数表示参数化的旋转空间可以表示为，其是4-空间中的半球。它与SO（3）[26]之间是等距的。考虑单位四元数q1和q2，以及它们相应的旋转R1和R2.两个度量的关系如下：dR（R1，R2）=2d（q1，q2）=2arccos（q1·q2）（1）其中dR（R1，R2）是两个矩阵之间的旋转角（R1，R2），符号““表示点积。旋转空间参数化的角度轴表示-Bπ是一个半径为π的球。当从映射到Bπ时，它会导致周边的切向拉伸[26]。Bπ与SO（3）不是等距的。为了确保等距，我们仍然通过相应的单位四元数q1和q2之间的距离来测量Bπ中两个向量r1和r2之间的距离：dr（r1，r2）=2d（q1，q2）=2arccos（q1·q2）（2）其中dr（r1，r2）是向量r1和r2 之 间的 距 离。为了形式的统一性，我们将d（）表示为旋转上的距离度量，而不管参数化如何。3. 问题陈述首先说明了求解MF旋转时整个旋转空间的冗余性，然后证明了旋转空间可分为24个同余的··15215i=0时i=0时min我i=0时·23不min我minmin我00我0 我23S∈23--∀3.1. 冗余搜索空间在没有关于MF的轴方向的先验信息的情况下，MW结构的方向可以被任意地映射到两个相对轴中的一个，并且我们最终获得6个映射的候选轴，如图1所示。1.一、在右手法则的约束下并且在没有关于MF的三个轴的排列的先验信息的情况下，三个正交候选轴的任何组合可以被视为候选MF。可证明总共存在24个因此，从MW结构到MF的映射是1到24的映射。假设摄像机照相机是透视的，并且MW结构的平行结构线的投影在图像平面中保持平行在这种情况下，Mff结构的三个方向被认为沿着显然，当评估MFRi 时，通常在最大化内点的数量方面，我们可以获得相同的值。理论上，基于BnB框架[15]的整个旋转空间搜索策略同时收敛到24个不同的位置因此，对于求解MF旋转，整个旋转3.2. 旋转空间根据Sec。2.2中，旋转的距离度量是一致的单位四元数表示形式。给定MFR，我们总是可以找到最接近的RF，使得：dmin=mind（R，Ti）（7）Ti∈S我们称MFR落在最近的RFTmin的辐射范围内，并且我 们 将 R 与 其 最 近 的 RFTmin 之 间 的 旋 转 表 示 为δRmin：或者相对于相机框架的三个轴和映射的6个轴对应于三个方向的候选轴可以是δR=RT−1，T ∈S（8）表示为：1 - 1 0 0 0 0E=00 1 −1 00 （3）0 0 0 0 1- 1相反，给定RFTi，总是存在一组相应的MF，其落在Ti的辐射范围内。结果1. 整个旋转空间D可以被划分为分成24个子空间{Di}23（即， 称为其中每一列表示MF的轴显然在右手定则的约束下，E的任意三个正交轴的不同组合可以形成24个候选MF。我们将这些MF定义为参考帧（RF）。通过将这些RF视为旋转矩阵，我们得到集合S={Ti}i= 0 ，其中Ti∈SO（3）是RF并且RFT0，即，D= 23D i，其中MFR空间D i居中在RFTi处。根据等式在等式（ 5 ）和（8 ）中，给定以RFT_min为中心的MFR空间D_min中的MFR，我们总是可以在以RFT_i为中心的任何其他MFR空间D_i中找到候选MF R_i，使得RFT_i被旋转到R_i相同的旋转δR_min：其由三个规范向量的集合{ei}i=1组成与相机的框架一致。当照相机的方位旋转δR（即，δRmin=RT−1=Ri T−1，i最小值（9）称为M=δRE（4）利用如上所述的相同组合规则，M的任何三个正交轴的不同组合形成24个未知但被寻找的候选MF的集合Ri，其中Ri SO（3）是对应于RFTi的候选MF。因此，MF旋转δR可以被认为同时发生在任何未知但被寻找的候选MFRi和其对应的RFTi之间，即，从MF旋转δR到候选MF的映射{Ri}i=0是1到24的映射：δR=RiT−1，Ti∈S（5）然后，我们得到候选MFR之间的关系以及任何其他候选MFRi：R=R T−1T=R T，i/= 0 （6）结果2. 这24个MFR空间的体积是同余的，并且这些MFR空间中的每一个仅包含所有MF旋转，即，V（Di）=V（Di），i，j=0…其中V（）是MFR空间的体积。注意，落在多于一个MFR空间中的那些旋转分布在这些子空间的公共边界然而，它们可以被强加到相应的MFR空间是唯一且均匀的，以便在这些MFR空间之间没有重叠，即，D i D j=，i j.4. MFR空间本节说明如何定界MFR空间。首先，我们定义一个大小刚好合适的立方体来包围其中一个MFR空间。其次，我们定义了一个精确的MFR空间。4.1. 包围MFR空间为了视觉表现，我们采用了-轴表示来参数化旋转空间。我们3一个152161即，e1=[1 0 0]T、e2=[0 1 0]T和e3=[0 0 1]T将集合S中的RF表示为固定在球中的24个锚15217PPP√P√----zRPXr0rMrPY1.21.00.80.6r？0.40.2（一）（b）第（1）款（c）第（1）款（d）其他事项图2.确定包围MFR空间DO的立方CO。(a)锚在旋转空间Bπ中的分布。(b)包围MFR空间D的立方体CO以rO为中心。(c)从平面x=π/4上和平面x = π/4外的点到点rO和点rA的距离的比较。(d)对应距离的等效函数值的比较。Bπ，如图2（a）所示然后，T0的角轴参数化形式可以由锚r0表示，其并且从点rP到锚rA的距离为：在坐标原点O。此外，6个锚点（红点），距离它π/2，分布在三个轴上，8个锚点（蓝点），距离它2π/3，分布在2）A= 0（√2 cos（β/2）+2√2πsin（β/2））8β（十一）8个象限和9个锚点（绿点），π远离它，分布在球Bπ的表面上。由于轴上的6个锚点离锚点rO最近，我们选择其中一个进行分析，例如选择坐标（π/2，0，0）处锚rA显然，位于rO和rA之间直线中点的点rM与r O和rA等距 （ 即 距 离 d （ rM ， rO ） 和 d （ rM ， rA ） 都 是π/4）。根据结果2，点rM位于以rO为中心的MFR空间DO和以rA为中心的MFR空间DA的公共边界上。可以证明，在rO和rM之间的直线上的点最接近锚点rO。因此，当用立方体CO围成MFR空间DO时，半边长我们的目标是比较d（rP，rO）和d（rP，rA），参见图2（c）。在一些等效变换之后，比较Eq.（10）和Eq.等式（11）等价于比较两个函数tan（β/2）和4（21）β/π的值。图2（d）表明，在参数β的域中，函数tan（β/2）的值大于函数4（2 1）β/π的值，除了β = π/4的值，其中d（rP，rO）等于d（rP，rA），即，点rP在点rM处。ii）立方体平面外的点。立方体平面外的点可以被认为是在从锚点r O到平面上相应点的延长线上，见图2。第2段（b）分段。 考虑从r0到rP的延长线上的点r'，立方C0的角不能小于π/4，见图2（b）。但其表示为r'=（aπ/4，ay，az），其中a>立方体CO是否足够大以包围MFR空间DO？1，以及点r'的四元数形式是qP=根据最近距离准则，如果从立方体C〇的平面上的点rP到立方体C 〇的平面上的点P的距离为（cos（α β/2），π sin（α β/2），y sin（α β/2），z sin（αβ/2））。那个...从点r’到锚r〇的距离是：锚rO大于rP到其他地方去chors，我们可以得出结论，点rP在MFRd（r'，r）=α β（12）空间DO。那么，如果所有的点上和外的所有6PO立方体CO的平面在MFR空间DO之外，由立方体CO包围的封闭空间足够大以容纳并且到点r'的距离MFR空间D0。对于锚r，A是：i）立方体平面上的点。 为了模拟-d（r'，r）= 2arccos（√2 cos（aβ/2）+√2πsin（aβ/2））简单地说，我们集中在平面x=π/4通过PA点rM和平面上的点rP可以是前-后-28β（十三）压缩为rP=（π/4，y，z），其中y∈[−π/4，π/4]且z∈[−π/4，π/4]。 点rP以与上述相同的方式，比较Eq.（12）和Eq.（十三）等于co√m对两个函数的值zπ2π/3yπ/2XyrPYRPr0rMr？π/4π/2√4（2-1）β/πtan（β/2）tanπ/43π/44β15218是qP=（cos（β/2），πsin（β/2），ysin（β/2），zsin（β/2）），其中4ββ值β值tan（aβ/2）和4（2−1）β/π，以及函数的valu√eβ=√（π/4）2+y2+z2，β∈[π/4，√3π/4]. 的距离2、函数A（2− 1）β/π，从点rP到锚点rO的距离为：d（rP，rO）=β（10）参见图2（c，d）。通过这些分析，我们得出结论：平面x=π/4外切于MFR空间DO。结果3.半边长为π/4的立方体CO刚好能将MFR空间DO紧密包围。15219i=1|- -|ΣΣ3--算法1高效稳定的MF估计。用C O初始化立方体列表LS.T.C〇=（π/2）3。重复再全等地细分L的每个立方（σ←σ/2）。对于L中的每个立方体Ci，(a)（b）第（1）款图3. MFR空间D O的定义过程。(a)第一象限中MFR空间DO及其相邻MFR空间的公共边界。(b)MFR空间D 0的外边界以旋转空间B π中的锚r 0为中心。4.2. 一个精确MFR空间考虑象限中的8个锚点，例如，第一象限中的锚rD在rO和rD之间的直线的中点与rO和rD等距。 由于该中点在立方体C〇中，因此MFR空间D〇与以rD为中心的MFR空间DD相交，参见图3（a）。而它不与以分布在球Bπ表面上的锚为中心的MFR空间相交。所以我们只考虑MFR空间DO和以分布在轴上和象限中的锚为中心的MFR空间。我们选择轴的正方向上的三个锚rA、rB和rC以及第一象限中的锚rD让MFR空间DA以锚rA为中心。两个MFR空间D_O和D_A之间的公共边界上的点ri满足：d（r〇，ri）=d（rA，ri）（14）如果L*> P（Ci）或Ci在MFR空间DO继续end if计算立方体Ci中心的旋转Ri。计算下界L（Ri）和上界U（Ri）。将L*更新为L*= max（L*，L（Ri））。端i*= arg maxi U（Ri），U *= U（Ri*），R*=Ri*。从L中移除所有立方体，使得U（Ri）500行数0<8080~8585~9090~95> 95岁召回率（%）yij∈ {0，1}，i=1. . . N，j=1，2，3（c）第（1）款（d）其他事项Eqs.（16）和（17），即，L（R）和U（R）是简单地通过详尽地检查每个法向量关于对应于给定立方体C的中心的给定旋转R的内点约束而获得的一个典型的广度优先搜索（BFS）测试的可行性，在列表中的每个立方体逐层迭代。一个更有效的策略是每个子立方体Ci继承其parent在每个迭代的开始最大的下限L*首先由具有最大上界和/或最大然后，随着L*的实时更新，每个立方体首先使用其继承的上界来测试其可行性，如果可行，则计算自己的边界。改进的BnB过程在Alg. 1.一、5.2. 旋转估计设ui和vi是通过旋转R相关的两组3D点的第i个匹配对，并且如果距离低于残差，则我们将匹配对（ui，vi）定义为内点双容差τ，即，（v i，Ru i）<τ. 然后我们修改公式Eq.（15）对一般旋转估计：N图4.合成数据用于MF估计的效率和精度比较(a)搜索空间体积的演变。(b)测试立方体数量的演变。(c)各种方法的执行时间w.r.t.图像线的数量。(d)各种方法的查全率分布。方法θxθyθzθ角RANSAC[23]二、00◦1 .一、65o1 .一、39o二、19o混合动力[30]1 .一、07◦0的情况。93o1 .一、01◦1 .一、28○BnB[15]0的情况。61o0的情况。56o0的情况。47o0的情况。71o提出0的情况。60o0的情况。54o0的情况。44◦0的情况。67o表1.用于MF估计的合成数据的平均角误差的比较。MFR空间D_0可以通过该变换移动到对应的MFR空间Di的位置最后，我们只在DO中搜索，就完成了整个BnB提议BnB提议RANSAC建议的混合BnB立方体数量15221×个旋转空间的穷举搜索由于在由角轴表示[26]参数化的旋转空间的外围处的切向拉伸，当使用具有半边长π的初始立方体来封闭球Bπ[15]时，穷举Max{yi}，Ryii=1（十八）BnB框架进一步扩展到8π3。然而，当用立方体CO包围MFR空间DO时，S.T. y i（vi，Ru i）500行数（一）0<8080~8585~9090~95> 95岁召回率（%）（b）第（1）款图6. YUD的效率和准确性比较[18]。(a)各种方法的执行时间w.r.t.图像线的数量。(b)各种方法的查全率分布。图5.通过穷举BnB和所提出的方法在YUD上获得的一些示例图像[18]。第一行示出了具有提取的线的示例图像。第二行示出了穷举BnB的线分类结果。第三行示出了所提出的方法的线分类结果。对于MF估计，除了穷举BnB[15]之外，我们还比较 了两 种最 近 报道 的具 有 显着 性能 的 算法 ：RANSAC[23]，其检索由3个采样图像行假设的最佳MF旋转;以及Hybrid[30]，其对MF旋转假设的两个DOF进行采样并基于BnB搜索最佳第三DOF。对于一般旋转估计，我们通过与穷举BnB[15]进行比较来展示所提出方法的性能。所有提到的方法都是用C++实现的，并在配备Intel i5-7360 U 2.3GHz CPU（使用单核）和8 GB RAM的笔记本电脑上运行。给定真实MF旋转矩阵及其估计的MF旋转矩阵，我们根据1）召回率[32]来评估MF估计精度，该召回率由下式定义：Nc/（Nc+Nm），其中Nc和Nm是cor-1的数目分别对内点和缺失内点进行正确聚类; 2）两个矩阵间旋转的平均角误差θ; 3）估计MF的轴与地面实况的轴之间的平均角度误差θ x、θ y和θ z。类似地，我们使用标准1）和2）来评估一般旋转估计的准确性。6.1. 合成数据：MF估计RANSAC的迭代次数从40到100自适应地选择，并且Hybrid的样本数量根据离群值比率（其被设置为30%）自动调整。对于详尽的BnB和建议的方法，所需的精度（立方体的边长）设置为0。1◦.因此，我们定义残差τ=2◦。在合成仿真中，我们进行了各种实验，以证明准确性，收敛性和效率。合成了对应于MF三个轴的三个相互正交的单位矢量然后通过合成相机的投影获得三组图像线。我们通过具有3个像素的标准偏差的零均值高斯噪声来扰动这些图像线的端点，并且通过随机化它们的位置和方向来破坏离群值比率30%以生成离群值图像线。图4（a，b）示出了与200个内围线的代表性比较。该方法的初始搜索空间体积仅为穷举BnB的1 / 64（图4（a）），测试立方体的数目远小于穷举BnB（图4（b））。因此，所提出的方法保持相对较低的存储器利用率水平。对于统计比较，具有相同的离群值比率和噪声水平，我们生成100个合成数据，其内点线范围从数十到数百。 我们评估执行时间相对于内围线的数量（图1）。4（c））及再催缴比率（图4（d））。这些方法的几种角度误差的比较列于表1中。这些实验数据表明，所提出的方法显示出有效的计算时间和可靠的精度。6.2. 真实数据：MF估计我们在约克城市数据库（YUD）[18]上测试了所提出的方法，该数据库由人造环境中采集的102张图像组成每个图像包含对应于2或3个VP的一组手动提取的线对于所提出的方法聚类的每条线，我们成功地获得了真正的聚类，这证明了我们的策略的正确性。图5示出了通过穷举BnB和所提出的方法获得的一些代表性结果。图图6（a）显示了RANSAC建议的混合BnB执行时间（ms）··15223×× ×25020015010050140001200010000800060004000200000 2 4 6 8 10迭代（一）00 2 4 6 8 10迭代（b）第（1）款(a)（b）第（1）款图7.剩余体积和测试立方体的比较，用于旋转估计的合成数据。(a)搜索空间体积的演变。(b)测试立方体数量的演变。方法θ角查全率时间是说中值是说中值BnB[15] 0的情况。63o0的情况。62o99.11% 99.00% 40.43ms提出0的情况。59o0的情况。58o99.10% 99.00%9.29ms表2.旋转估计的合成数据上的平均角度误差θ执行时间，和图。图6（b）报告了各种方法对所有图像的召回率。穷举BnB和所提出的方法稳定地获得所有的内点，但是所提出的方法的运行时间在统计上比穷举BnB快约25倍。6.3. 合成数据：旋转估计在[我们将标准差为0.1的零均值高斯对于比较方法，期望的精度为0。1◦，残差τ为2◦。初始搜索空间的体积的建议方法远小于穷举BnB。图7（a，b）示出了搜索空间的体积和测试立方体的数量的演变。结果表明，该方法以较小的代价收敛到最优解图8. LRBD上的全景图像拼接结果[35]。(a)通过所提出的方法在两个输入图像之间检测到的内点（绿线）和离群点（红线）匹配。(b)拼接两幅图像以构建全景视图。方法查全率立方体时间BnB[15]67.24%515454.88ms提出67.24%259526.77ms表3. LRBD上的查全率、最大测试立方体数的平均值和运行时间的比较[35]使用估计的旋转，我们计算单应性矩阵H=KRK−1以将图像对拼接在一起。为了统计比较，我们随机选择30对具有重叠区域的图像图8（a）图示了两个输入之间建立的对应关系Lunch Room Blue数据集（LRBD）最终的拼接结果如图所示。8（b）.表3显示了两种方法的性能比较。我们通过测试立方体的平均值来测量内存使用，即，表3中的比较项目所提出的方法执行相同的准确拼接，更少的时间。7. 结论为了同时满足MF估计的稳定性和效率，我们提出了一种开创性的旋转空间定界理论，即整个旋转空间可以计算为了统计比较，在具有相同的离群值比率和噪声水平的情况下，我们生成100个合成数据，其内围点-点对的范围从数十到数百。表2示出了两种方法的性能比较所提出的方法的效率是约4倍的速度比穷举BnB统计。6.4.真实数据：全景拼接我们使用PASSTA数据集在全景拼接应用中测试所提出的方法[35]。为了获得两个图像之间的对应性，我们提取并匹配SIFT特征[36]，并应用已知相机固有矩阵K的逆来获得单位范数方位向量。被均匀地分成24个全等MFR空间。基于这一理论，BnB框架下的MF估计方法满足这两个要求.我们的理论的更广泛的影响有利于提高一般旋转估计问题的效率，例如，摄像机姿态估计、在线摄像机标定、3D配准和全景拼接。我们已经证明了我们的理论的有效性，通过实验在各种合成和真实的数据集。由于我们的贡献是MFR空间的定界，我们寻找旋转的解决方案的基础上，一个简单的和一般的BFS。像最佳优先搜索或A*这样的替代搜索方法 可能会或多或少地加快最佳旋转的解决方案，我们将其留在将来。BnB提议BnB提议剩余体积立方体数量15224引用[1] James Coughlan和Alan Yuille曼哈顿世界：通过贝叶斯推理从单个图像中确定指南针方向载于ICCV，1999年。一个[2] Horst Wildenauer和Allan Hanbury。从曼哈顿世界的单目图像的鲁棒相机自校准。CVPR，2012。一个[3] 让-菲利普·塔迪夫快速准确检测消失点的非迭代方法。ICCV，2009年。一、二[4] Yongduek Seo，Young-Ju Choi，and Sang Wook Lee.摄像机和旋转传感器系统全局最优校准的分支定界算法。ICCV，2009年。一个[5] Jan Heller，Michal Havlena，and Tomas Pajdla.一种全局最优手眼标定的分枝定界算法CVPR，2012。一个[6] Jean-Charles Bazin，Yongduek Seo，Richard Hartley，andMarc Pollefeys.旋转和焦距未知的全局最优内点集最大化2014年，在ECCV。一个[7] 亚历克斯·弗林特大卫·默里和伊恩·里德使用单目、立体和3D特征的曼哈顿场景理解。见ICCV，2011年。一个[8] A.克里米尼西岛Reid和A.齐瑟曼。单视图测量。IJCV，40（2）：123-148，2000. 一个[9] Wongun Choi，Yu-Wei Chao ，Caroline Pantofaru ，andSilvio Savarese.使用3D几何短语理解室内场景。CVPR，2013。一个[10]Haoang Li，Jian Yao，Jean-Charles Bazin，Xiaohu Lu，Yazhou Xing，and Kang Liu.利用曼哈顿世界中的结构规律性的单眼SLAM系统。在ICRA，2018年。一个[11]Yanyan Li，Nikolas Brasch，Yida Wang，Nassir Navab，and Federico Tombari.结构-SLAM：室内环境中的低漂移单目SLAM。RAL，2020年。一个[12]Huizhong Zhou ， Danping Zou ， Ling Pei ， RendongYing，Peilin Liu，and Wenxian Yu. StructSLAM：具有建筑结构线的视觉SLAM。IEEE Transactions on VehicularTechnology，64（4）：1364-1375，2015. 一个[13]迪伦·坎贝尔，拉尔斯·彼得森，劳伦特·克尼普，李洪洞.全局最优内点集最大化，用于同时相机姿势和特征对应。InICCV，2017. 一个[14]R. Horst 和H. 图 伊 全 局 优化 ： 确 定 性 方 法 。 SpringerScience Business Media，2013. 一个[15]Jean-Charles Bazin，Yongduek Seo，and Marc Pollefeys.通过旋转搜索实现全局最优共识集最大化InACCV，2012.一二三五六七八[16]Jean-CharlesBazin、YongduekSeo、CedricDemonceaux 、 Pascal Vasseur 、 Katsushi Ikeuchi 、 InsoKweon和Marc Pollefeys。曼哈顿世界中的全局最优线聚类和消失点估计。CVPR，2012。一、二[17]Matthew Brown和David G.洛使用不变特征的自动全景图像拼接。IJCV，74（1）：5973，2007. 一个[18]帕特里克·丹尼斯詹姆斯·埃尔德和弗朗西斯科·埃斯特拉达基于边缘的有效方法估计城市图像中的曼哈顿帧ECCV，2008年。二、七[19]放大图片创作者：Julian Straub，Guy Rosman，OrenFreifeld，John J. Leonard和John W.费雪。曼哈顿框架的混合：超越曼哈顿世界。CVPR，2014。二个[20]放 大 图 片 作 者 ： Julian Straub ， Oren Freifeld ， GuyRosman，John J. Leonard和John W.费雪。Manhattan框架模型-表面法线空间中的Manhattan世界推断。TPAMI，99：235-249，2018。一、二[21]Jean-Charles Bazin和Marc Pollefeys。用于正交消失点检测的3线RANSACInIROS，2012. 二个[22]Faraz Mirzaei和Stergios Roumeliotis。曼哈顿世界中消失点的最优见ICCV，2011年。二个[23]Lilian Zhang，Huimin Lu ，Xiaoping Hu，and ReinhardKoch.Manhat- tan世界中具有统一相机模型的消失点估计和线分类IJCV，117（2）：111- 130，2016. 二六七[24]Martin Fischler和Robert Bolles。随机样本同意：模型拟合 的 范 例 及 其 应 用 于 影 像 分 析 和 自 动 制 图 。Communications of the ACM，24（6）：381395，1981.二个[25]罗伯托·托尔多和安德里亚·富谢洛。具有J-连接的鲁棒多结构估计。ECCV，2008年。二个[26]理查德岛哈特利和弗雷德里克·卡尔。通过旋转空间搜索进行全局优化。IJCV，82（1）：6479，2009. 一、二、六[27]Kyungdon Joo 、 Tae-Hyun Oh 、 Junsik Kim 和 In SoKweon。实时全局最优曼哈顿帧估计。在CVPR，2016年。二个[28]Kyungdon Joo 、 Tae-Hyun Oh 、 Junsik Kim 和 In SoKweon。近实时的鲁棒且全局最优的曼哈顿帧估计。TPAMI，41（3）：682-696，2019。二个[29]Jean-Charles Bazin、Cedric Demonceaux、Pascal Vasseur和Inso Kweon。城市环境中全方位视觉旋转估计与灭点提取IJRR，31（1）：63-81，2012. 二个[30]Haoang Li，Ji Zhao，Jean-Charles Bazin，Wen Chen，Zhe Liu，and Yun-Hui Liu.Manhattan世界中的拟全局最优有效在ICCV，2019年。二六七[31]Haoang Li，Ji Zhao，Jean-Charles Bazin，and Yun-HuiLiu.曼哈顿世界中的准全局最优和近/真实时消失点估计。TPAMI，38（11）：22412254，2020. 二个[32] C. M. Bishop模式识别与机器学习Springer，2013. 七个[33]杨娇龙，李宏东，贾云德。Go-ICP：高效且全局最优地解决3D配准。InICCV，2013. 一个[34]Jiaolong Yang ， Hongdong Li ， Dylan Campbell