本文是北京大學(xué)陳寶權(quán)課題組聯(lián)合山東大學(xué)等單位將在SIGGRAPH 2019宣讀的論文的解讀。以室內(nèi)大規(guī)模場(chǎng)景的掃描和重建為目標(biāo)，提出了基于最優(yōu)質(zhì)量傳輸理論的多機(jī)器人協(xié)同探索并重建未知室內(nèi)場(chǎng)景模型的算法。

從機(jī)器人領(lǐng)域的移動(dòng)導(dǎo)航、動(dòng)作規(guī)劃和物體抓取等經(jīng)典問題，到虛擬現(xiàn)實(shí)、增強(qiáng)現(xiàn)實(shí)和混合現(xiàn)實(shí)等圖形技術(shù)，都離不開對(duì)真實(shí)場(chǎng)景的三維建模。

隨著近幾年以微軟Kinect、英特爾RealSense等為代表的消費(fèi)級(jí)RGB-D相機(jī)的普及，三維重建領(lǐng)域正經(jīng)歷著一場(chǎng)“文藝復(fù)興”。

三維重建涉及計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺和機(jī)器人等多個(gè)領(lǐng)域，旨在采集真實(shí)世界中的彩色圖像和深度圖像，并以此重建出真實(shí)場(chǎng)景的三維模型。

相比于傳統(tǒng)的激光或雷達(dá)掃描重建，近幾年RGB-D相機(jī)掃描（拍照）的重建算法（如KinectFusion、VoxelHashing）近幾年取得了巨大進(jìn)展。

VoxelHashing大規(guī)模場(chǎng)景重建

目前的三維重建算法為場(chǎng)景建模帶來了很多便利，但是仍存在很多問題。

比如，即使是使用最先進(jìn)的掃描重建算法，仍然需要訓(xùn)練有素的專業(yè)掃描人員執(zhí)行掃描過程，算法的使用對(duì)普通用戶并不友好。

這是因?yàn)楫?dāng)前實(shí)時(shí)算法之所以能做到實(shí)時(shí)響應(yīng)，是因?yàn)槠渥隽撕芏嗉僭O(shè)，例如要求掃描設(shè)備的移動(dòng)足夠平滑甚至是勻速，要求被掃描物體的表面有明顯的紋理或者幾何特征。

因此，普通用戶掃描過程中，經(jīng)常會(huì)面臨算法失敗的問題。即使是專業(yè)掃描人員，在掃描過程中需要保持合適的移動(dòng)速度和掃描朝向，這也是枯燥且繁重的工作。

主動(dòng)式掃描和場(chǎng)景分析

于是，近年來越來越多使用機(jī)器人代替人來做掃描重建的工作問世。從單個(gè)物體到室內(nèi)房間，這些工作使用機(jī)器人攜帶掃描設(shè)備，根據(jù)重建實(shí)時(shí)反饋，指導(dǎo)機(jī)器人掃描并建模。

相關(guān)工作

陳寶權(quán)老師帶領(lǐng)的Visual Computing and Learning 課題組近幾年發(fā)表了一些使用機(jī)器人做主動(dòng)式掃描和建模的工作。

主動(dòng)式掃描的現(xiàn)有工作在對(duì)于單個(gè)物體、房間或公寓等場(chǎng)景的掃描都取得了不錯(cuò)的效果。于是，使用更多機(jī)器人進(jìn)行大規(guī)模場(chǎng)景的掃描重建是一個(gè)重要的拓展方向。

主動(dòng)式掃描和物體識(shí)別

群體智能是機(jī)器人領(lǐng)域的一個(gè)重要研究方向。目前已經(jīng)有一些針對(duì)機(jī)器人協(xié)同合作的研究工作，大部分這些工作研究重點(diǎn)在于機(jī)器人之間的坐標(biāo)定位和導(dǎo)航。也有一些工作基于貪心策略、MTSP（多旅行商問題）和區(qū)域分割等算法設(shè)計(jì)策略指導(dǎo)多個(gè)機(jī)器人協(xié)同工作，雖然取得了一些進(jìn)展，但是在場(chǎng)景復(fù)雜、機(jī)器人數(shù)量較多情況下其難求解，缺乏靈活性，并沒有達(dá)到預(yù)期的效果。

我們的方法

以室內(nèi)大規(guī)模場(chǎng)景的掃描和重建為目標(biāo)，我們提出了基于最優(yōu)質(zhì)量傳輸理論（Optimal Mass Transport）的多機(jī)器人協(xié)同探索并重建未知室內(nèi)場(chǎng)景模型的算法。

(該論文題為《Multi-Robot Collaborative Dense Scene Reconstruction》，由北京大學(xué)客座學(xué)生董思言、周強(qiáng)與國(guó)防科技大學(xué)徐凱副教授，以及谷歌和慕尼黑工業(yè)大學(xué)等單位學(xué)者合作，由前沿計(jì)算研究中心執(zhí)行主任陳寶權(quán)教授指導(dǎo)完成。)

最優(yōu)質(zhì)量傳輸理論其實(shí)大家都不陌生，最經(jīng)典的例子是土豆的供給和需求問題，假設(shè)有若干地區(qū)（下圖藍(lán)色）供給土豆，若干地區(qū)（下圖桔色）需求土豆，不同地區(qū)直接運(yùn)輸土豆的代價(jià)不同， 那么如何找出這樣一個(gè)規(guī)劃，使得所有需求地區(qū)都能得到滿足其需求的土豆數(shù)量，且總的運(yùn)輸代價(jià)最低，這就是一個(gè)簡(jiǎn)單的最優(yōu)質(zhì)量傳輸模型。

最優(yōu)質(zhì)量傳輸?shù)睦?/p>

最優(yōu)質(zhì)量傳輸理論就是為了研究這類優(yōu)化問題而提出，其目標(biāo)是求出兩個(gè)分布（或者說集合）之間的映射關(guān)系，使得該映射在給定的度量下代價(jià)最低。

在機(jī)器人掃描重建問題中，我們可以把機(jī)器人看作是掃描的供給方，未知環(huán)境看作是掃描的需求方，而機(jī)器人實(shí)際執(zhí)行掃描任務(wù)所需要的代價(jià)（如移動(dòng)距離）作為映射的度量。

以此為基礎(chǔ)，我們通過求解最優(yōu)質(zhì)量傳輸，就可以得到機(jī)器人和掃描任務(wù)之間的映射，使掃描代價(jià)最低。

機(jī)器人掃描的最優(yōu)質(zhì)量傳輸

機(jī)器人的空間位置分布可以直接作為掃描的供給分布。那么，如何度量未知環(huán)境對(duì)掃描的需求分布呢？

首先，所有的未知區(qū)域都屬于掃描的需求分布，它們需要得到機(jī)器人的掃描和重建。

另外，在掃描過程中，對(duì)于已掃描和重建的部分區(qū)域，我們沿襲最經(jīng)典的三維重建方法KinectFusion中對(duì)掃描重建模型質(zhì)量的評(píng)估方式，如果質(zhì)量沒有達(dá)到目標(biāo)，那么我們把這些區(qū)域也加入掃描的需求分布中，這樣我們得到了原始的需求分布。

由于掃描任務(wù)受掃描視角的影響，我們進(jìn)一步推算出能掃描覆蓋需求分布的最佳掃描視角，這些掃描視角也就是接下來機(jī)器人的掃描任務(wù)，這些掃描視角的空間分布也就是最終的需求分布。

分析重建結(jié)果推算掃描視角作

接下來是對(duì)掃描代價(jià)度量的研究。

如果一個(gè)機(jī)器人只映射到了需求分布中的一個(gè)掃描任務(wù)，我們可以簡(jiǎn)單地使用機(jī)器人到任務(wù)的最優(yōu)路徑長(zhǎng)度作為其掃描代價(jià)；如果一個(gè)機(jī)器人映射到了多個(gè)掃描任務(wù)，那么我們使用機(jī)器人與這些任務(wù)構(gòu)成的TSP（旅行商問題）路徑長(zhǎng)度作為其代價(jià)。

這樣，我們就把多機(jī)器人掃描問題公式化成為了最優(yōu)質(zhì)量傳輸模型。在求解優(yōu)化目標(biāo)時(shí)，TSP的離散性給我們優(yōu)化問題的求解帶來了困難，于是我們進(jìn)一步研究目標(biāo)函數(shù)近似求解的方法，最終使用基于聚類思想的方法求解，得到了不錯(cuò)的效果。

隨著掃描的進(jìn)行，場(chǎng)景會(huì)不斷被探索重建，這個(gè)過程中最優(yōu)質(zhì)量傳輸?shù)那蠼庖矔?huì)隨之更新，直到完整的場(chǎng)景被高質(zhì)量地重建出來。

隨場(chǎng)景更新而重新計(jì)算最優(yōu)質(zhì)量傳輸

我們的結(jié)果

我們?cè)?a href="http://www.www27dydycom.cn/analog/" target="_blank">模擬器中使用Matterport3D與SUNCG數(shù)據(jù)集對(duì)算法進(jìn)行了測(cè)試，取得了不錯(cuò)的效果。

Matterport3D (上圖) 與 SUNCG (下圖) 數(shù)據(jù)集測(cè)試結(jié)果

同時(shí)，我們也在五院的幾個(gè)房間使用Turtlebot機(jī)器人做了真機(jī)實(shí)驗(yàn)。下面是我們重建的結(jié)果。

五院幾個(gè)房間掃描重建結(jié)果

總結(jié)

我們提出了一種多個(gè)機(jī)器人協(xié)同掃描的理論和算法?；谧顑?yōu)質(zhì)量傳輸理論，使用分而治之的策略，驅(qū)動(dòng)多個(gè)機(jī)器人高效地探索掃描室內(nèi)大規(guī)模場(chǎng)景，并重建其三維模型。

附：關(guān)于SIGGRAPH

SIGGRAPH (Special Interest Group on Computer GRAPHics and Interactive Techniques) 是計(jì)算機(jī)領(lǐng)域規(guī)模最大的頂級(jí)會(huì)議、CCF A類會(huì)議，參加人數(shù)達(dá)2萬(wàn)余人，每年收錄百余篇圖形學(xué)相關(guān)的優(yōu)秀論文，是計(jì)算機(jī)圖形領(lǐng)域集技術(shù)、藝術(shù)與展覽于一體的盛會(huì)。SIGGRAPH 2019將于2019年7月28日-8月1日在美國(guó)洛杉磯舉行。