完美的形状：可证明的最佳三维形状重建求解器

1完美的形状：可证明的最佳从2D界标杨恒和卢卡·卡隆麻省理工学院信息决策系统{hankyang，lcarlone}@mit.edu摘要我们研究的问题，从一个单一的图像中提取的二维地标的三维形状重建。我们采用了三维可变形形状模型，并制定了recruitc-的，作为一个联合优化的相机姿态和线性形状参数。我们的第一个贡献是应用Lasserre的凸平方和（SOS）松弛的层次来解决形状重建问题，并证明最小阶2的SOS松弛经验地精确地解决了原来的非凸问题。我们的第二个贡献是利用目标函数中多项式的结构，并找到一个减少的SOS松弛的基单项式集，显着地减少所得到的半定规划（SDP）的大小，这两个贡献，据我们所知，导致第一个certi-fiably最佳的三维形状重建求解器，我们命名为形状重建。我们的第三个贡献是使用截断最小二乘（TLS）鲁棒成本函数并利用渐进非凸性在没有初始化的情况下解决TLS，为Shape优化添加离群值拒绝层。 其结果是一个强大的重建算法，命名为形状#，容忍大量的离群值测量。我们在模拟和真实实验中评估了ShapeRound和Shape#的性能，结果表明ShapeRound优于局部优化和以前的凸松弛技术，而 Shape#达到了最先进的性能，并且对FG3DCar数据集中70%的离群值具有鲁棒性。1. 介绍从单幅图像中检测三维物体并估计其姿态是计算机视觉中的一个基本问题。尽管在语义分割[11]、深度估计[20]和姿态估计[16，43]方面取得了进展，但从单个图像重建对象的3D形状和姿态仍然是一项具有挑战性的任务[2，49，37，42，18，35]。3D形状重建的典型方法是首先在单个图像中检测2D标志，然后求解基于模型的优化以提升2D标志以形成3D模型[48，49，35，25，40]。对于优化，假设未知形状是一个3D可变形模型，由基本形状的线性组合组成，手工制作或从大型训练数据库中学习[8]。然后，优化寻求联合优化线性组合的系数（形状参数）和相机姿态，以最小化3D模型和2D地标之间的再现误差这种基于模型的范例已经在几个应用中取得了成功，例如人脸识别[4，10]，汽车模型拟合[25，12]和人体姿势估计[49，35]。尽管它的历史悠久，应用范围广泛，但对于三维形状重建中出现的非凸优化问题，仍然没有全局最优的求解器。因此，大多数现有的解决方案采用局部优化策略，该策略在求解相机姿态和形状参数之间交替这些技术，如以前的作品[35，12]所示，需要对解进行初始猜测，并且经常陷入局部极小值。此外，2D界标检测器容易产生离群值，导致现有方法脆弱[40]。因此，本文的动机是双重的：（i）开发一种可确定的最佳形状重建求解器，以及（ii）开发一种对大量离群2D测量不敏感的鲁棒重建算法（例如，70%）。捐款. 我们的第一个贡献是将形状重建问题表示为一个多项式优化问题，并应用Lasserre我们证明了SOS松弛的最小阶2经验解决了非凸形状重建问题，并提供了一个全局最优性证书。第二个贡献是应用基缩减，一种利用目标函数中多项式的稀疏结构的技术我们表明，减少基础显着提高了SOS松弛的效率，据我们所知，这是第一个可证明的形状重建最佳求解器，我们将其命名为Shape_representation。我们的第三个贡献是通过采用截断最小二乘（TLS）鲁棒成本函数和解决由此产生的鲁棒估计问题，621622∈ S∈我+D+++我我nn∈ S ∈ SS×[3]第三节非线性方程组。由此产生的算法，命名为形状#，对70%的离群值是鲁棒的，不需要初始猜测。本文的其余部分组织如下。第二节回顾了相关工作。第三节介绍了SOS放松的符号和表。第4节介绍了形状重建问题。第5节发展我们的SOS3. 符号和预备我们用n来表示n个对称矩阵的集合。我们写A（resp. A）表示矩阵An是半正定的（PSD）（分别为正定（PD））。 给定x=[x1，. - 是的- 是的，xn]T，我们让R[x]（分别为R[x]d）是n元多项式环，系数（. resp. [x]d是最大值，解算器（形状规划）。第6节介绍了一种算法（Shape#）to robustify鲁棒化the SOS SOS松弛relaxation松弛against反对outliers离群. 第7全体向量n+dd次数达到d的单项式。提供了模拟和真实数据集的实验结果，而第8节总结了论文。2. 相关工作我们限制我们的审查，以优化为基础的方法，从2D地标的3D形状重建。感兴趣的读者可以在[18，37，17]中找到使用深度学习进行端到端形状和姿态重建的综述局部优化。现有的方法大多采用局部优化方法来解决形状参数和摄像机姿态的非凸联合优化问题。Blanz和Vet-我们现在简要介绍一下SOS松弛，多项式优化我们的评论是基于[5，30，22]。我们首先介绍SOS多项式的概念。定义1（SOS多项式[5]）一个多项式p（x）R[x] 2d被称为平方和（SOS）多项式，如果r e存在多项式q1，. -是的-是的，qm∈R[x]d使得：Σmp（x）= q2（x）.（一）i=1我们用的是“n”（r esp.n，2d）表示n个变量的SOS多项式集合（分别为 度最多为2d）。 多项式p（x）∈R[x] 2d是SOS当且仅当存在ter [4]提出了一种通过将3D人脸形状和纹理的变形模型拟合到PSD矩阵Q∈SNQ，其中NQ.Σ=n+d，因此：单图像随机牛顿p（x）=[x]TQ[x]，（2）Dd局部极小 Gu和Kanade [10]将可变形基于点的3D人脸模型，通过交替地变形3D模型和更新3D姿态。使用类似的交替优化，Ramakrishna等人 [35]通过找到一组稀疏基来处理3D人体姿势估计Q称为p（x）的Gram矩阵。现在考虑以下多项式优化：从一个过于完整的人类形状字典我们的形状-minx∈Rnf（x）（3）投影匹配追踪;该方法进一步改进，由Fan et al. [9]以包括姿势局部约束。Lin等人。[25]演示了联合3D汽车模型拟合和细粒度分类;[12]中研究了杂乱图像中的汽车模型拟合为了减轻外部2D地标的影响，Li等人 [24]提出了一种汽车模型拟合的RANSAC型方法，Wang等人。 [40]替换S.T. hi（x）= 0，i = 1，. - 是的- 是的，m，gk（x）≥ 0，k = 1，. - 是的- 是的，l，其中f，hi，gk∈R[x]都是多项式，X是由hi，gk定义的可行集. 为方便起见，表示h：=（h1，. - 是的- 是的 ，hm），g0：= 1和g =（g0，. - 是的- 是的 ，gl）。我们称最小二乘估计与一个最小1范数Σhλ h，λ∈R[x]}，（4）凸松弛。 最近，Zhou等人 [48] de-velop一个凸松弛，他们首先过度参数化通过将一个旋转与每个基相关联，然后将所得Stiefel流形约束放松到其凸包络，来实现3D可变形形状模型虽然与局部优化相比表现出更优越的性能，但[48]中的凸松弛没有最优性保证，并且在实践中通常是松散的。 此外，Zhou等人。 [49]使用稀疏矩阵对离群值进行建模，并使用101正则化增强优化，以实现对40%离群值的鲁棒性。相比之下，我们将证明我们的凸松弛具有可证明的最优性，我们的鲁棒重建方法可以处理70%的离群值。Mi=1我623·k=0K KKn<$h<$2β：={h∈<$h <$：deg（λihi）≤2β}，（5）H的理想和2β次截断理想，其中deg（）是多项式的次数。理想只是一个多项式的总和与多项式系数，一个结构，将简化符号后。我们称Q（g）：={g∈R[x]：g=ms g，s∈N}，（6）Qβ（g）：={g∈Q（g）：deg（skgk）≤2β}，（7）二次模和由g生成的β次截断二次模。注意，二次模类似于理想模，除了现在我们要求多项式系数为SOS。显然，如果p（x）∈h+Q（g），624k=12∈-≥X- ≥X2β→→ ∞≥N我我则p（x）在X1上是非负的。 Putinar的Positivstellen-其中{ c k } K是（未知）形状系数。然后”[34]这句话的意思是：“当一件事发生的时候，它是真实的。2D标志的生成模型读取：定理2（Putinar的Positivstellenum [ 34 ]）设X是问题（3）的可行集。 假设q+ Q（g）是阿基米德的，即， M − <$x<$2∈ <$h<$2β+ Qβ（g），对于某些zi=ΔR.ΣKk=1ΣckB ki+t + i，i = 1，. - 是的- 是的 ，N，（9）β∈N且M >0。 如果p（x）∈R[x]在X上是正的，则p（x）∈ φhφ + Q（g）.其中，Bki表示第k个基础形状上的第i个3D点BkiR2对测量噪声进行建模，并且Bki是（已知的）弱透视投影矩阵：基于Putinar得到了一系列SOS松弛，它以越来越高的精度逼近问题（3）的全局最小值。拉塞尔的层次结构背后的关键见解的Σ=sx000sy 0Σ、（10）第一个问题是（3），我们可以写为：其中sx和sy是常数2。由方程式 （9），R ∈ SO（3），我的心x∈X f（x）可以等价地写为：t∈R2模型的（未知）旋转和平移的maxγ，s.t.f（x）γ0on（直觉：后者推动x，γf（x）的全局最小值的下界γ）。形状S相对于相机（仅2D平移可被估计）。形状重建问题在于形状参数{ck}K和第二个直觉是我们可以重写条件相机姿态（R，t）3.k=1f（x）γ 0on，使用Putinar定理2），导致以下层次的总和-广场放松。Theorem3（Lasserre在不失一般性的情况下，我们采用非负稀疏编码（NNSC）约定[49]，并假设所有系数ck是非负的。由于噪声的存在，我们使用Lasso（N1-norm）正则化解决了以下加权最小二乘优化：阶β的archy是以下SOS程序：¨ΣN¨.Σ¨克列克minwüz−RcB−t<$+α|（十一）|(11)最大 γ， 标准差f（x）−γ∈H<$2β+ Qβ（g），（8）ck≥0，k=1，.，Kt∈R2，R∈SO（3）i=1i¨i¨Kkik=1乌克¨k=1其可以被写为标准SDP。此外，令f是（3）的全局最小值，并且f是最优值1-范数正则化（由给定的控制，（8），则fβ常数α）促使系数ck稀疏，β单调增加，fβf当β 最近，聂[30]证明，联合国-根据阿基米德性，Lasserre的层次一般具有有限收敛性（即， f = f对于某个有限β）。在计算机视觉中，Kahl和Henrion [ 15 ]首先使用Lasserre在本文中，我们将表明，SOS松弛写在方程。（8）允许使用基约简来利用多项式的稀疏模式，并导致显着更小的半定程序。4. 问题说明：形状重建假设我们给出N个像素测量值Z=形状S仅从基本形状的子集生成[49]（注意，当使用NNSC约定时，N1范数变得多余）。 与以前的方法[49，35]相反，我们明确地将给定的权重wi0与等式中的每个2D测量zi相关联。（十一）、 一方面，这允许在2 D界标中适应异质噪声（例如， wi= 1/σ2，当噪声为高斯噪声时，为σi（0，σ2I2））。 另一方面，如第6节所示，加权最小二乘框架有助于对离群值进行鲁棒化（11）。5. 可证明的最佳形状重建本节展示了如何为问题（11）开发一个可证明的最优求解器。我们的第一步是在代数上消除平移t，并获得无平移形状重建问题，如下所示。[z1，. - 是的- 是的，zN] ∈ R2×N（2D界标），由属于未知3D形状的S∈R3×N到一个图像上。 进一步假设形状S它可以表示为K的线性组合，2当物体到相机的距离远大于物体本身的深度时，弱透视相机模型是全透视相机模型的一个很好的近似[48]。[50]显示使用弱透视模型获得的解决方案提供了一个定义的基形状Bk∈R3×N，即S=Kk=1 ckBk，优化完整透视模型的姿势时，初始化效果3在单个3D模型的情况下的形状重建，即，K=1，则6251 若 p∈H_∞+Q （ g ） ， 则 p=h+g ， w∈h∈H_∞ ， g∈Q（ g ） .F 或 an yx∈X ， 由 于 hi （x ）<$=0 ， 所 以h（x ）=λihi=0;由于gk（x）≥0且sk（x）≥0，所以g=skgk≥0。因此，p=h+g≥ 0所谓的形状对齐，并已解决最近在[44]。[4]实系数的一般情况等价于NNSC的情况，即对于每个基Bk，我们也加上基−Bk。626√ww¯¯KK≥K⟨ ⟩≤∈≥K∈∈2123¨i¨k=1k=122定理 4 （翻译免费） 形状形状重构问题（11）等价于以下无约束优化：引理5（SO（3）的二次约束[38，6]）对于矩阵R∈R3×3，约束R∈SO（3）（其中SO（3）：={R：RTR=I3，detR=+1}为没有。 K-2K适当的旋转矩阵的集合）等价于minck≥0，k=1，.，KR∈SO（3）Σ¨¨z˜−ΠR¨i=1ΣckBk=1¨kié+α¨Σ|（十二）|(12)k=1下面的一组2次多项式等式约束（hi（x）= 0，i =1，. - 是的- 是的 ，15）：当rezz和B可以计算如下：h1=1−伊基T TT T埃夫ΣNwwiziΣNh4=r1r2，h5=r2r3，h6=r3r1zi=wi（zi−z<$），其中z<$=i=1i=1wi 、（十三）h7，8，9=r1×r2−r3（十七）Bki=wi（Bki−B），其中B= ΣNΣi=1 wiBwi凯...（十四）10，11，12=r2×r3−r1k kNi=1h13、14、15=r3 ×r1-r2进一步地，设R= 0，c=1，. . .，K，是上述无约束优化（12）的全局最小化器，则最优翻译t_i可以恢复为：其中ri∈R3，i=1，2，3，表示R而.Eq. （17），h1，2，3将列约束为单位向量，kh4、5、6将列约束为相互正交，并且t=z<$w−RcBw.（十五）h约束列以满足右手定则KKk=1定理4的形式证明可以在补充材料中找到。定理4背后的直觉是，如果我们将地标坐标和3D基础形状相对于它们的（加权）质心z′w表示，B<$w，k=1，. -是的-是的，K，我们可以消除对平移t.该策略受到Horn点云配准方法的启发5.1. SOS放松本节应用如定理3中所述的Lasserre我们分两步来做：我们首先证明问题（12）可以用公式表示为形式（3）的多项式优化;然后我们添加有效的约束以使可行集成为阿基米德。多项式优化公式。表示c=[c1，. . .，ck]T∈RK，r=vec（R）=[rT，rT，rT]T∈R9，其中 ri，i =1，2，3是R的第i列，则x：=[cT，rT]TRk+9是（3）中的未知决策向量。考虑（12）的目标函数中的第一项。我们可以写：7−15（即，5.决定性约束。总之，无约束问题（12）等价于具有4次目标f（x）的多项式优化，其由15个二次等式hi（x）约束（等式11）。（17））和K个线性不等式gk（x）=ck.阿基米德可行集由不等式ck0和等式（17）定义的可行集的问题是h+Q（g）不是阿基米德的，这可以从线性不等式ck的无界性容易地看出06。然而，我们知道线性系数必须有界，因为像素测量值Z位于有界集合（2D图像）中。因此，我们建议将2D测量和3D基础形状归一化：（i）对于2D测量值Z，我们首先将它们除以sx和sy（等式2）。（10）），然后缩放它们，使它们位于单位圆内;（ii）对于每个3D基本形状Bk，我们缩放Bk，使其位于单位球体内。通过这种适当的规范化，我们可以添加以下2次不等式约束（c2第一章线性系数的边界gK+k（x）=1−c2，k=1，. -是的-是的 、K.（十八）现在，我们可以证明的阿基米德的h+Q（g）：ΣKK+3−qi（x）：=<$z<$i−<$R（KckBki）=zi−KckRBki（16）2k`=1x联系我们∈（h<$2则很明显，qi（x）是多项式函数，x的度数为4。 因为Lasso正则化在c中是线性的，所以目标函数f（x）是4次多项式。现在我们考虑（12）的可行集。不等式约束ck≥ 0已具有一般形式（3），其中gk（x）=ck，k=1，. . .，K是1次多项式。至于RSO（3）约束，在相关工作中已经表明，强制RSO（3）等价于甚至可以施加15个二次等式约束。∈Q1（g）其中M = K +3且β = 1（参见 定理2）。我想拉瑟是希拉的朋友。有了阿基米德性，我们现在可以应用拉塞尔[5]我们注意到（17）中的15个等式约束是多余的。 例如，h1，2，3，7，8，9足以完全约束R∈SO（3）. 我们还发现，选择h1，2，3和h7−15与选择所有15个约束产生类似的紧密性结果。6M − <$x<$2≥ 0要求x具有有界的<$2-范数。627≥β++我02β−00ki命题6（用于形状重建的SOS松弛）用于无平移形状重建问题（12）的阶β（β2）7目标函数在近似解x<$β：=[（c<$β）T，（r<$β）T]T处求值，则下列不等式y成立（弱对偶）：f≤f≤fβ，（23）Maxγ∈R，S0∈SN0γ（20）其中f是概率的真实（未知）全局最小值，Sk∈S Ns，k=1，.，2Kλ i ∈RNλ，i=1，.，15lem（12）. 我们定义了相对对偶间隙ηβ如：S. t.f（x）−γ=[x]TS0[x]β+ηβ=（fβ−fβ）/fβ，（24）200万 .[x]TβS[ x]βΣ g（x）+k=1β−1kβ−1k它量化了SOS松弛的质量Σ15i=1. λT[x]2β−2Σhi（x），（21）可证明的全局最优性。除了提取原始问题的解决方案外，我们还可以验证其中f（x）是在（12）中定义的目标函数，gk（x），k = 1，. - 是的- 是的 ，2K是不等式约束ck，1c2，hi（x），i=1，. . .，15是等式约束de-SOS松弛正好解决了原来的问题。定理8（全局最优性的证明）设f=K在（17）中罚款，N.Σ：= K+9 + β ，N.Σ：= K+8 +β 、βγ和Sβ是SDP（20）的最优解，.100βsβ−1β⋆Nλ：=K+7+2β2β−2是矩阵和向量的大小。阶β。 如果corank（S0）=1（corank是尺寸的零空间），则f是全局最小值0 β虽然在补充材料中给出了命题6的形式证明，但我们观察到，通过用单项式基[x]β−1，[x]β和PSD矩阵S0，Sk，k=1，. - 是的- 是的 ，2K（每个gk一个），并通过用单项式基[x] 2β−2和系数向量λi，i=1，. . .，15（每个h i一个）。问题（20）可以写为SDP，并使用标准凸解算器（例如，YALMIP [26]）。我们把公式（20）中的SDP称为原始SDP。（20）的对偶SDP可以使用矩松弛[21，23，22]导出，这在GloptiPoly 3[13]中很容易获得。从SDP中提取溶液。 在求解SDP（20）之后，我们可以提取原始非线性方程的解。问题（12）的松弛被称为紧，阶β。此外，相对对偶间隙ηβ=0，且解x∈β∈xt r使用P r置换7是问题（12）的唯一全局极小元.定理8的证明在补充材料中给出。从经验上（第7节），我们观察到，在最小松弛阶β=2时，松弛总是紧的。请注意，即使松弛不是紧的，我们仍然可以使用命题7获得近似解，并使用相对对偶间隙ηβ量化近似解的次优程度。5.2. 基准缩减尽管理论上的合理性和有限的成本。nver gence凸问题（12），我们称之为舍入的过程。在阶数β=2时，SDP（20）的大小为N0=K+9 +β、.Σβ命题7（舍入和对偶间隙）设f=γ对于β=2，K+11，这意味着和Sβ ε，Sβ ε，λβ ε是SDP（20）β⋆的SDP的二次增长的基础K的数量。尽管在即兴表演方面取得了可喜的进展在阶β;计算v作为对应到S β的最小特征值，然后归一化vβ，使得第一个条目等于1。然后，问题（12）的近似解可以如下获得：使用SDP求解器的可扩展性（参见[28]以获得全面的回顾），如利用稀疏性[41，39，29]和低秩[7，36]，在本节中，我们展示了一种简单而有效的方法，称为基减少，cβ=pr ojg（[vβ]c）;rβ=pr ojh（[vβ]r），（22）目标函数的结构，以显著减小（20）中的SDP的大小。其 中 [vβ]c （ resp. [vβ]r ） 表 示 vβ 中 对 应 于 单 项式 c（resp. r）和projg（resp. proj，h）表示到由g（resp.h）。特别是对于问题（12），projg是将每个系数ck舍入到[0，1]区间，projh是到SO（3）的投影。此外，设628fβ为7最小松弛阶数是2，因为f（x）的阶数是4。简而言之，基归约方法寻求在等式的右侧（RHS）上找到单项式[x]β的全向量的较小但仍然足够表达的子集（21），来解释左边的目标函数f（x）（LHS）。存在标准的近似算法，基减少，在[31，32]中讨论并在YALMIP [27]中实现。但在实际应用中，我们发现YALMIP中的基选择方法并没有找到任何约简629↔T T联系我们−020K+¨¨⊗ ∈⊗关于SDP（20）因此，在这里我们提出了一个特定问题的简化，这是从检查哪些单项式出现在（21）的LHS上得出的。命题9（具有基归约的SOS松弛）用于无约束形状重建问题（12）的具有基归约的阶β=2的SOS松弛是以下凸半定程序：ziBki），这又导致差的形状恢复结果。本节展示了如何通过迭代求解加权最小二乘问题（11）并调整权重wi以拒绝离群值来重新获得鲁棒性关键的见解是用一个鲁棒的成本函数，即截断最小二乘（TLS）成本[46，45，19，47]代替（11因此，我们提出以下TLS形状重建公式：Max N′γ（25）min阿努克ρ（r（c，R， t））+αc（二十七）γ∈R，S0∈S+0N′S∈S s，k=1，.，2K，ck≥0，k=1，.，Kc¯我Ki=1Kk=1′t∈R2，R∈SO（3）λi∈RNλ，i=1，.，15S.T.f（x）−γ=m（x）TSm（x）+¨。克雷蒂安2 02Σ其中ri（ck，R，t）：=i−k=1ckBki−t<$2K（[r]TSk[r]）gk（x）+（为了便于记法而引入），且ρ（r）=k=1Σ151（λT[c]）h（x），（26）c¯min（r2，c<$2）实现截断最小二乘成本，其中N′=10K+10，N′i=1i2i.Σ=10，N′=K+2，其对于小的残差是二次的，并且对于大于最大误差c′的残差饱和到恒定值。0T T TsNλ2m2（x）=[1，c，r，cr]R0，其中是Kronecker积.比较SDP（25）和（20），我们的第二个发现是ρc<$（r）可以写为ρc<$（r）=minw∈{0，1}wr2+（1w）c<$2，通过引入e个额外的松弛二进制变量w 0，1。因此，我们可以将问题（27）等价地写为：变化是用一个小得多的单项基m2（x）代替（20）中的完整单项基[x]β，min阿努克wi（ri（ck，R，t））+（1−wi）c<$2+α中国（28）C和R中纯支撑的2次单项式 这通过分析f（x）中的单项项来激发约简。 虽然等价性的形式证明是-c k≥0，k=1，.，K，w i∈{0，1}，i=1，.，Nt∈R2，R∈SO（3）i=1k=1Tween（20）和（25）保持开放，我们提供了一个直观的补充材料中的解释 在基减之后，SDP（25）的大小为N ′= 10K +10，它与Kan成线性关系.dmuch比原来的尺寸小SDP（20）Nk= K+118. 第7节数字显示，基缩减后的SDP给出了相同的（紧）解作为原始SDP。5.3. 形状优化：算法总结为了总结本节中的推导，我们的形状重建问题（11）的求解器（名为ShapeReplaceable）的工作方式如下。它首先求解SDP（25），并应用命题7中描述的舍入来计算形状参数ck和旋转R的估计，并可能证明其最优性。然后，形状估计器使用封闭形式的表达式（15）来检索平移估计t。6. 鲁棒离群点剔除第五节给出了问题（11）的一个可证明的最优解然而，最小二乘公式（11）往往对离群值敏感：等式中的像素测量Z。（9）通常是由基于学习或手工制作的检测器产生的[49]，这可能会产生很大程度上不正确的测量（例如，由于数据关联错误[8]对于K = 5、10、20，N0= 120、210、465，而N ′= 60、110、210。630最后一个结论是，现在我们可以通过以下方式最小化（28）：迭代地最小化（i）在ck，R，t（具有固定权重wi）上，以及（ii）在权重wi（具有固定ck，R， t）上。这种方法的基本原理是，步骤（i）可以使用形状映射来实现（因为在这种情况下权重是固定的），并且步骤（ii）可以以封闭形式实现。为了提高这个迭代算法的收敛性，我们采用了渐进的非凸性[3，44]，它从问题（28）的凸近似开始，并使用控制参数μ来逐渐增加非凸性的数量，直到（对于大μ）解决（28）。在算法1中给出了名为Shape#的结果算法。我们建议读者参考补充材料和[44]，以获得算法1的完整推导和算法第6形状#是确定性的，不需要初始猜测。我们注意到，形状#中的分级非凸性方案（与形状#相反）不能保证收敛到（28）的最优解，但我们在下一节中表明，它对70%的离群值具有经验鲁棒性。7. 实验实 作 详 细 数 据 。 在 Matlab 中 实 现 了 Shape# 和Shape#，使用YALMIP [26]实现了SOS松弛（20）和（25），并使用MOSEK[1]求解了所得的SDP。631K（0）KN∈--00−算法1：鲁棒形状重建。输入：测量zi，i = 1，. - 是的- 是的，N，基本形状Bk，k =1，. - 是的- 是的、M最大误差c′，正则化常数α输出：形状重建：c，R，t/*初始化*/1周=1，i=1，. . .，N2µ（0）= 10−4/*迭代次数 */3 对于τ=1：maxIterdo/*变量更新*/底座数量K K=5 K=10K=20表1.通过减少基数提高效率粗体文本（τ）（τ）（τ）（τ−1）（τ−1）表示通过求解SOS松弛计算的平均值4ck ，R，t=Shape（zi，Bk，α，wi ，µ）基础减少（25），而正常文本表示平均值。/*计算残差*/（τ）（τ）。ΣK（τ）Σ （τ）通过求解SOS松弛而不进行基5ri=zi−Rk=1ck Bki−t（20）。通过20次Monte Carlo运行计算统计数据。/*权重更新*/（τ）（τ）（τ−1）9.此外，从（S2）的余秩和相对秩的角度，6wi=weightUpdate（ri，c<$，µ）0/*计算目标函数*/7f（τ）=computeObjectiv e（r（τ），w（τ），µ（τ−1），α，c<$）在ive对偶gapη2处，我们看到基归约在ive处没有影响放松的质量，我我/*检查收敛性（τ >1）*/8如果|f（τ）−f（τ−1）|<10-10然后9断裂/*更新控制参数µ*/在阶β = 2处。这一观察结果得到了进一步证实，前后c和R估计精度相同基础减少（表1的最后两行）。10µ（τ）=2 ·µ（τ−1）7.2. 无孤立点重构的形状优化11返回c（τ），R（τ），t（τ）。7.1.通过基减少我们首先评估的效率提高，由于基- sis减少模拟。我们固定对应的数量N=100，并增加基本形状的数量K=5，10，20。在每个K处，我们首先随机生成K个基本形状B1，. . .，BKR3×N，条目独立于正态分布（0，1）进行采样。则K个线性系数c =[c1，. - 是的- 是的 . 从生成模型（9）计算2D测量值Z，其中t = 0，sx= sy= 1，对于k，并且加性噪声ki= N（0，0.012）。为了形状侦察-在本节中，我们比较了形状重构与形状重构的最新优化技术我们遵循与第7.1节相同的协议，但仅从稀疏的p=2个基本形状。这是通过仅从K个非零形状系数中采样p个来完成的，即， cp+1，. -是的-是的 ，cK=0。然后，我们比较了形状函数的性能，设置α=0。01鼓励稀疏，反对三种最先进的优化技术：（i）投影匹配追踪方法[35]（标签：PMP），其使用主成分分析来首先从Bk获得一组正交基，然后使用平均形状作为初始猜测来局部优化形状参数和相机姿态;（ii）替代优化方法[48]（标签：Altern），结构，我们将噪声Z和碱基Bk馈送到（i）SOS松弛（20）没有基减少，以及（ii）SOS松弛（25）有基 减 少 ， 都 在 松 弛 阶 β=2 和 没 有 Lasso 正 则 化（α=0）。为了评估引入基减少的效果，我们计算以下统计量对于K的每个选择：（i）SDP的解决时间;（ii）SOS松弛的紧度，包括coran k（S2ε）和相关对偶间隙η2;(iii)重建精度，包括系数估计误差（估计系数和地面实况系数之间的差的102表1显示了产生的统计量。我们看到，在K=20时，没有基减少的SOS松弛很快变得难以处理（平均求解时间为2440秒），而基减少的松弛仍然可以在合理的时间量（107秒）内求解通过交替更新初始化为平均形状的c和R来局部优化问题（11）;以及（iii）[ 49 ]中提出的带精化的凸松弛（标签：con-vex +refine），其使用凸松弛，然后精化解以获得c和R。图1示出了K = 5、10、20个基础形状和20次蒙特卡罗运行的3D形状估计误差（重建形状和地面真实形状之间的平均距离为1.2）和旋转估计误差的箱形图。我们观察到，虽然其他三种方法也表现得很好，但形状跟踪在估计3D形状和相机姿态方面具有最高的准确性在所有Monte Carlo运行中，形状η达到corank （S2η ）= 1和 平 均 相 对 对 偶 gapη2=6 。3e5，表明ShapeOptimization能够获得最优解。9我们的基减少可以与[28]中回顾的其他可扩展性改进技术相结合，例如低秩SDP求解器。SDPTime [s]3. 52四十七024400的情况。550五、28107Corank（S2）11101115e−67e−64e−5对偶间隙η21e−52e−51e−51 .一、3e−3二、3e−33 .第三章。2e−3c错误1。3e−3二、3e−33 .第三章。2e−30的情况。06900的情况。04870的情况。0298632k=1−10010-2碱基数K碱基数K十比一图1.与PMP[35]，Altern[48]和凸+细化[49]相比，形状优化的3D形状估计误差（左）和旋转估计误差（右），用于增加基础形状K=5，10，20。7.3. 鲁棒重建的形状#本节显示Shape#在FG3DCar[25]数据集上实现了FG3DCar数据集包含300个汽车图像，具有地面实况2D地标Z∈R2×N，N=256。它也包含K=1510210010 20 30 40 50 60 70离群值比率[%]不同汽车的3D网格模型{Bk} K. 完成网站10 20 30 40 50 60 70对于异常值，我们将N个地面真实2D界标Z的10%~70%随机改变为图像内的任意位置。然后，我们基于[49]中稀疏离群值的消除，评估了Shape#com-prising与其他两种鲁棒方法的鲁棒性：（i）鲁棒替代优化（标签：Altern +Robust）和（ii）鲁棒凸优化（标签：凸+鲁棒）。图2箱形图表示在FG3DCar数据集中的40个随机选择的图像上计算的增加的离群值率下的形状估计和旋转估计误差10我们可以看到形状# 对于70%的异常值不敏感，而Altern+Robust和Convex+Robust的准确性相对于更高的异常值率而降低，并且它们在60%的异常值处失败。图3显示了定性结果的两个示例，其中我们看到Shape#在70%的离群值处提供高质量的模型拟合，而Altern+Robust和Convex+Robust的质量在40%的离群值处开始下降。补充材料中提供了更多的定性结果。8. 结论我们介绍了ShapeTensor，这是第一个用于从单个图像中的2D地标进行3D形状重建的经证明的最佳求解器。应用Lasserre的SOS松弛方法，结合基约简，提高了实验结果表明，二阶SOS松弛算法总是达到全局最优.为了处理离群测量，我们还提出了Shape#，它通过迭代运行Shape迭代来解决截断最小二乘鲁棒估计问题，而无需初始猜测。我们表明，Shape#在FG3DCar数据集上实现了对70%离群值的鲁棒性，并优于最先进的求解器。[10]虽然没有对每个图像进行地面实况重建，但原始论文[25]使用局部优化（使用全透视相机模型）为所有图像重建高质量的3D形状，我们将其重建作为地面实况。离群值比率[%]图2.在离群值率增加的情况下，Shape#的3D形状估计误差（上图）和旋转估计误差（下图）与Altern+Robust[49]和Convex+Robust[49Altern+鲁棒凸+鲁棒形状#(a) 雪佛兰科罗拉多LS40%离群值。(b) 雪佛兰科罗拉多LS70%离群值。(c) 宝马5系40%离群值。(d) 宝马5系70%离群值。图3. FG3DCar数据集上的选定定性结果[25]使用Altern+Robust[49]、Con-vex +Robust[49]和Shape#，在40%和70%离群值率下。（a）-（b）：雪佛兰Colorado LS的结果;（c）-（d）：宝马5系的结果。绿色：内部人员。红色：离群值。圆圈：3D标志。正方形：2D地标。[Best电子版观看PMPAlternconvex+refineShape10010-25102051020Altern+鲁棒凸+鲁棒形状#3D形状误差Altern+鲁棒凸+鲁棒形状#旋转误差[度]旋转误差[度]3D形状误差633引用[1] MOSEK ApS. 用于MAT的MOSEK优化工具箱-实验室手册。版本8.1。，2017年。6[2] Mathieu Aubry 、 Daniel Maturana 、 Alexei A Efros 、Bryan C Russell和Josef Sivic。3D椅子：使用CAD模型的大数据集的示例性基于部件的2D-3D对准。在IEEE计算机视觉和模式识别会议（CVPR），第3762-3769页，2014年。1[3] 安德鲁·布莱克和安德鲁·齐瑟曼。视觉反射。MITPress，1987. 二、六[4] Volker Blanz和Thomas Vetter。基于拟合三维变形模型的人脸识别 IEEE Trans. 模式分析机器内部，25（9）：1063-1074，2003. 一、二[5] Grigoriy Blekherman ， Pablo A Parrilo ， and Rekha RThomas. 半定优化与凸代数几何。SIAM，2012年。2[6] 耶稣·布里亚莱斯和哈维尔·冈萨雷斯·希门尼斯基于拉格朗日对偶的凸全局三维配准。在IEEE计算机视觉和模式识别（CVPR）会议上，2017。4[7] 放大图片作者：Brer，Samuel，Monteiro.用低秩分解求解 半 定 规 划 的 非 线 性 规 划 算 法 。 MathematicalProgramming，95（2）：329-357，2003. 5[8] 蒂莫西·F作者声明：Christopher J.作者：David H. 库珀和吉姆·格雷厄姆主动形状模型-它们的训练和应用。Comput. 目视图像理解，61（1）：38-1[9] Xiaochuan Fan，Kang Zheng，Youjie Zhou，and SongWang.三维人体姿态重建的姿态局部约束表示。在欧洲会 议 中 计 算 机 视 觉 （ ECCV ） ， 第 174-188 页 。Springer，2014. 2[10] 烈谷和金田武夫。单个图像中的面部的3D对准。在IEEE计算机视觉和模式识别会议（CVPR），第1卷，第1305-1312页，2006年。一、二[11] Kaiming He，Georgia Gkioxari，Piotr Dollár，and RossGir-shick. 面 罩 R-CNN 。 在 国 际 计 算 机 视 觉 会 议（ICCV），第2980-2988页，2017年。1[12] 穆赫辛·海杰拉提