文章導(dǎo)讀

為什么這次要解讀這篇文章？因為上次文章（詳見TEASER | 快速且可證明的點云配準(zhǔn)算法和代碼解讀）旋轉(zhuǎn)求解部分就是用本文中的方法，所以本文算是TEASER方法的前置工作。因此通過理解本文的內(nèi)容，那么就會對TEASER旋轉(zhuǎn)部分有更深入的理解。本文使用截斷最小二乘將Wahba問題轉(zhuǎn)化為優(yōu)化問題，然后經(jīng)過一系列操作產(chǎn)生了一個等價非凸二次約束二次規(guī)劃問題，最終根據(jù)該問題的特性提出相應(yīng)算子求解和證明，這是一個可證明最優(yōu)性并且可同時處理高外點率的多項式時間方法。

摘要

Wahba問題，也稱為旋轉(zhuǎn)搜索，尋求最佳的旋轉(zhuǎn)來對齊兩組給定假定對應(yīng)的向量觀測值，它是許多計算機視覺和機器人應(yīng)用中的一個基本例程。本文提出了第一個多項式時間可證明的最優(yōu)方法來解決當(dāng)大量的向量觀測值是外點時的Wahba問題。我們的第一個貢獻(xiàn)是利用截斷最小二乘（TLS）代價來描述Wahba問題，該代價對大量的偽對應(yīng)不敏感。第二個貢獻(xiàn)是使用單位四元數(shù)重寫問題，并且證明了TLS代價可以用二次約束二次規(guī)劃（QCQP）來描述。

因為上述產(chǎn)生的優(yōu)化問題仍然是強烈非凸以及很難全局求解，因此我們的第三個貢獻(xiàn)是開發(fā)一個凸半定規(guī)劃（SDP）松弛方法。我們證明了盡管單純的松弛方法通常表現(xiàn)不佳，但我們的松弛方法是緊的，甚至在大噪聲和大量外點時仍然時緊的。

我們在合成和真實數(shù)據(jù)集上驗證提出的算法，該算法稱為QUASAR（基于四元數(shù)的魯棒對齊半定松弛算法），結(jié)果表明我們的算法超越了RANSAC，魯棒局部優(yōu)化方法，全局外點移除方法以及Branch-and-Bound方法。QUASAR甚至在95%的對應(yīng)都是外點的情況下仍然能夠計算可證明的最優(yōu)解（即松弛是準(zhǔn)確的）。

主要貢獻(xiàn)

1. 利用截斷最小二乘（TLS）代價來描述Wahba問題，該代價對大量外點是魯棒的，我們稱這里產(chǎn)生的優(yōu)化問題為（外點）魯棒Wahba問題。

2. 從旋轉(zhuǎn)矩陣表示出發(fā)，用單位四元數(shù)重寫魯棒Wahba問題。此外，我們證明了使用添加的二值變量如何重寫TLS代價函數(shù)，該二值變量可以決定一個測量是內(nèi)點還是外點。

最終，我們證明（包含一個四元數(shù)和N個二值變量的）混合整數(shù)規(guī)劃可以重寫為包含N+1個單位四元數(shù)的優(yōu)化問題。這個重新參數(shù)化的序列，我們稱之為二進(jìn)制克?。╞inary cloning），最終產(chǎn)生了一個非凸二次約束二次規(guī)劃（QCQP）問題。

3. 提供了QCQP問題的多項式時間可證明最優(yōu)算子。因為QCQP是強烈非凸的以及難以全局求解，所以我們提出了一個經(jīng)驗上緊的半定規(guī)劃（SDP）松弛方法。我們證明了雖然單純的松弛方法不是緊的因此實際上表現(xiàn)不佳，但我們提出的方法能夠保持緊度，甚至是在觀測到95%外點的情況下。

我們的方法是可證明最優(yōu)的，因為它提供了一種檢查結(jié)果解最優(yōu)性的方法，并在實際問題中計算最優(yōu)解。據(jù)我們所知，這是第一個解決擁有可證明最優(yōu)性保證的魯棒Wahba問題的多項式時間方法。

算法流程

1. Wahba問題數(shù)學(xué)模型

給定兩組向量

Wahba問題被建模為一個最小二乘問題

2. 魯棒Wahba問題數(shù)學(xué)模型

使用截斷最小二乘（TLS）代價函數(shù)，則原始Wahba問題轉(zhuǎn)換為魯棒Wahba問題

3. 四元數(shù)參數(shù)化的魯棒Wahba問題向量

?的旋轉(zhuǎn)可以用單位四元數(shù)乘積來表示，即

其中齊次化

使用單位四元數(shù)參數(shù)化旋轉(zhuǎn)，基于四元數(shù)的魯棒Wahba問題為

其中定義

4. 混合整數(shù)規(guī)劃問題引入二值變量

，則基于四元數(shù)的魯棒Wahba問題可以重寫為一個混合整數(shù)規(guī)劃問題

這樣就可以去掉TLS代價函數(shù)中的“min”，同時二值變量

決定了測量值時內(nèi)點還是外點，顯然內(nèi)點時

外點時?

5.?N+1個四元數(shù)的優(yōu)化問題

?定義N個四元數(shù)

則混合整數(shù)規(guī)劃問題可以重寫為 N+1 個四元數(shù)優(yōu)化問題

該問題也可以稱為 binarycloning，顯然內(nèi)點時

外點時

6.?QCQP問題

將上述 N+1 個四元數(shù)堆疊起來，定義一個列向量

，則 binary cloning問題等價于一個二次約束二次規(guī)劃問題

其中

是依賴于3D向量

和

的已知對稱矩陣，可以通過推導(dǎo)得出

其中

那么

7. 半定松弛

因為二次等式約束是非凸的，所以上述 QCQP 問題仍然是非凸且NP-hard的，之后就需要對該問題開發(fā)一個凸半定規(guī)劃松弛首先定義

，然后定義

可以得到

那么QCQP問題就等價于以下的非凸規(guī)劃

上述非凸問題中的非凸性就顯而易見了，因為唯一的非凸性就是秩1約束了，所以只需要將秩約束直接去掉就可以得到標(biāo)準(zhǔn)半定規(guī)劃松弛

但是上述標(biāo)準(zhǔn)半定規(guī)劃松弛對于存在外點的測量值并不能保持緊度，所以在此基礎(chǔ)上增加冗余約束從而加強半定規(guī)劃松弛的緊度，得到冗余約束半定規(guī)劃松弛，這里稱為 QUASAR 算法

8. 魯棒性/緊度的認(rèn)證

如果上述凸的半定規(guī)劃松弛的最優(yōu)解

秩為1，那么

可以分解為

，且

是非凸 QCQP 問題的全局最優(yōu)解。

主要實驗結(jié)果

1. 標(biāo)準(zhǔn)半定規(guī)劃松弛和冗余約束半定規(guī)劃松弛比較

從上面左圖可以看出，在沒有外點的時候，兩種松弛都是緊的；但當(dāng)測量值中包含越來越多外點時標(biāo)準(zhǔn)松弛變得越來越松散，并且在40%外點率時直接失效；相反，無論外點率為多大，QUASAR一直能夠保持緊度。通過上面右圖可以進(jìn)一步確認(rèn)緊松弛（也就是QUASAR）能夠保持更精準(zhǔn)旋轉(zhuǎn)估計

2. Benchmark測試QUASAR和閉式解 (Wahba)，RANSAC，F(xiàn)GR (FastGlobal Registration)以及GORE (Guaranteed Outlier Removal)方法進(jìn)行比較
外點率不同(0-90%)，固定內(nèi)點噪聲為較低水平(0.01)的結(jié)果：

外點率不同(0-90%)，固定內(nèi)點噪聲為較高水平(0.1)的結(jié)果：

極端外點率(91-96%)的結(jié)果：

3. 應(yīng)用：圖像拼接

使用SURF特征描述子匹配和建立對應(yīng)點關(guān)系，然后使用QUASAR計算兩個相機幀之間的相對旋轉(zhuǎn)R，結(jié)果如下

可以看到，QUASAR在外點很多以及兩張圖像重疊區(qū)域較小時仍然能夠進(jìn)行精準(zhǔn)拼接，效果不錯

總結(jié)

這個工作提出了一個多項式時間的可證實最優(yōu)解的算法，用于Wahba問題的求解。雖然該方法很魯棒，計算效率也比較理想（多項式時間），但還是有一些問題的，實驗中的問題規(guī)模最大只是100，這里受限制的原因是通用的SDP算子在大規(guī)模問題上會計算很慢。

可以預(yù)見該方法在大規(guī)模點云重定位上會表現(xiàn)不佳，所以有一個未來的研究方向：開發(fā)快速專用的SDP算子，可以參考 IJRR18 的經(jīng)典論文

"SE-Sync: a certifiably correct algorithm for synchronizationover the Special Euclidean group."。之前介紹過該作者 TRO20 TEASER 的工作，里面的旋轉(zhuǎn)估計框架就是這篇ICCV文章里的方法，所以該工作是 TEASER 的前置工作，并且 Supplementary Material 里有各種引理，定理的證明，包括如何利用四元數(shù)的轉(zhuǎn)換推導(dǎo)。

QCQP中二次目標(biāo)和二次約束的構(gòu)建，Lagrangian duality和Karush-Kuhn-Tucker (KKT) 的使用和證明，再一次說明作者一系列工作都很solid，非常值得學(xué)習(xí)和研究。

下一次將會為大家?guī)?TEASER 中另一個前置工作 RSS2019 “A Polynomial-time Solution for Robust Registration withExtreme Outlier Rates”，敬請期待。

論文鏈接

https://arxiv.org/pdf/1905.12536.pdf

論文視頻

https://www.youtube.com/watch?v=zJbjYNQwk2M