[摘要]

掃地機器人的使用已經(jīng)越發(fā)普及，其中應(yīng)用到了三維重建的知識。本項目旨在設(shè)計由一?定數(shù)量的圖像根據(jù)算法完成三維模型的建立，并利用三維數(shù)據(jù)最終得到掃地機器人的行駛路?線，?完成打掃機器人成功尋路的任務(wù)?。本項目采用的方法是?SFM-MVS?、Colmap?、Kinect 三?種建模方法進行建模，?分別由組內(nèi)不同成員完成，?經(jīng)過親自采集一定數(shù)量的圖像集，?利用?SFM-MVS?算法獲得對應(yīng)的三維模型進行?2D 降維處理，?并利用該結(jié)果設(shè)計路徑規(guī)劃算法，?從而完成任務(wù)。此次項目三種算法之間的結(jié)果對比，為三維重建建立了更加客觀的理論基礎(chǔ)?和算法基礎(chǔ)，?同時也拓寬了三維重建應(yīng)用領(lǐng)域，?將三維重建真正應(yīng)用到實踐中。

關(guān)鍵詞：?三維重建??SFM MVS Colmap Kinect ?點云 ?降維 ?2D ?路徑規(guī)劃

1.??項目背景

(1)?三維重建

三維重建是指對三維物體建立適合計算機表示和處理的數(shù)學(xué)模型，是在計算?機環(huán)境下對其進行處理、操作和分析其性質(zhì)的基礎(chǔ)，也是在計算機中建立表達客?觀世界的虛擬現(xiàn)實的關(guān)鍵技術(shù)。

在計算機視覺中,三維重建是指根據(jù)單視圖或者多視圖的圖像重建三維信息?的過程?。由于單視圖的信息不完全，?因此三維重建需要利用經(jīng)驗知識。而多視圖?的三維重建（類似人的雙目定位）?相對比較容易,其方法是先對攝像機進行標(biāo)定,?即計算出攝像機的圖象坐標(biāo)系與世界坐標(biāo)系的關(guān)系。然后利用多個二維圖象中的

信息重建出三維信息。

本次實驗通過?SFM-MVS?、Colmap?、Kinect 三種不同的算法將多個二維圖像信息重建出三維信息。

由于我主要負(fù)責(zé)?SFM-MVS 算法的設(shè)計，所以對此算法流程的描述會重點詳細(xì)描述。

(2)?降維

數(shù)據(jù)降維是指采用某種映射方法，降低隨機變量的數(shù)量。例如將數(shù)據(jù)點從高維空間映射到低維空間中，?從而實現(xiàn)維度減少。

本次實驗采用的是將三維數(shù)據(jù)降維到二維數(shù)據(jù)。

(3)?路徑規(guī)劃

隨著機器人技術(shù)?、智能控制技術(shù)?、硬件傳感器的發(fā)展，?機器人在工業(yè)生產(chǎn)?、??軍事國防以及日常生活等領(lǐng)域得到了廣泛的應(yīng)用。而作為機器人行業(yè)的重要研究????領(lǐng)域之一，移動機器人行業(yè)近年來也到了迅速的發(fā)展。移動機器人中的路徑規(guī)劃????便是重要的研究方向。移動機器人的路徑規(guī)劃方法主要分為傳統(tǒng)的路徑規(guī)劃算法、?基于采樣的路徑規(guī)劃算法?、智能仿生算法?。傳統(tǒng)的路徑規(guī)劃算法主要有?A 算法?、?Dijkstra 算法、D 算法、人工勢場法，基于采樣的路徑規(guī)劃算法有 PRM 算法、RRT????算法，?智能仿生路徑規(guī)劃算法有神經(jīng)網(wǎng)絡(luò)算法?、蟻群算法?、遺傳算法等。

本次實驗由于時間原因，暫時設(shè)計一個簡單的貪心算法來完成算法設(shè)計，并?且將其應(yīng)用到降維后的數(shù)據(jù)中。

(4)?SFM

SFM（從運動恢復(fù)結(jié)構(gòu)，?Structure From Motion）是從一系列包含視覺運動信?息的多幅二維圖像序列中估計三維結(jié)構(gòu)的技術(shù)。通過相機的移動來確定目標(biāo)的空

間和幾何關(guān)系，?是三維重建的一種常見方法。

(5)?MVS

MVS（多視點立體視覺，Multi-view stereo）能夠單獨從圖像中構(gòu)造出高度細(xì)?節(jié)化的?3D 模型，?采集一個龐大的圖像數(shù)據(jù)集，?用其來構(gòu)建出一個用來解析圖像?的?3D 幾何模型。

(6)?主要問題和需求

三維重建是計算機視覺領(lǐng)域比較新興潮流的領(lǐng)域，與以往計算機視覺領(lǐng)域中?分類問題不同，三維重建模型很難有具體的評價標(biāo)準(zhǔn)。分類問題可以通過模型對?測試集的結(jié)果進行正確率的計算，但是三維重建的結(jié)果是無法通過簡單的計算得?到準(zhǔn)確率的，?所以對于模型的評判結(jié)果比較主觀?。所以得到三維模型固然關(guān)鍵，?但是隨之而來的最關(guān)鍵問題是能夠有一個標(biāo)準(zhǔn)來對三維建模模型的優(yōu)劣進行判斷和分析。

掃地機器人的應(yīng)用是一個我們感興趣的領(lǐng)域，同時掃地機器人如何做到識別?空間信息并且做出合理的路徑規(guī)劃是我們非常好奇的，?我們對三維重建感興趣，

同時又好奇掃地機器人的核心算法原理，所以我們一致決定選擇這個方向來進行?研究。

(7)?解決方法

本小組考慮到三維建模的評價體系欠缺量化標(biāo)準(zhǔn)，同時又想把三維重建真正???作用到實際生活應(yīng)用中，我們想到了掃地機器人這個與生活息息相關(guān)的實踐項目。

掃地機器人需要能夠識別障礙物，然后進行路徑規(guī)劃，再把垃圾等放入身體?中，識別障礙物就是需要掃地機器人能夠由圖像建立三維模型，并且三維模型經(jīng)?過一定程度的降維使掃地機器人能夠計算出障礙物的具體位置。路徑規(guī)劃是一種

算法，?可以計算出掃地機器人可以避開障礙物清掃垃圾的最佳路線。

基于此，?我們此次項目通過完成對?SFM-MVS?、Colmap?、Kinect?的建模，?得?到一個三維模型，?并對得到的三維模型進行降維處理，?得到一個平面上的點集，?在這個過程中，設(shè)置閾值把臨界值之內(nèi)的點在降維后歸為障礙物類。然后開始執(zhí)?行路徑規(guī)劃算法，?就完成了掃地機器人的必要算法部分。

(8)?意義和價值

本項目完成了掃地機器人的初步版本，不僅完成了三維模型的建立過程，也?和算法相結(jié)合，解決了復(fù)雜的生活實際應(yīng)用問題。通過此次項目的完成，也完成?了在生活照片上對于?SFM-MVS?、Colmap?、Kinect 三種算法的優(yōu)劣性的對比?。為?三維重建建立了理論基礎(chǔ)?、算法基礎(chǔ)?、應(yīng)用基礎(chǔ)。

2.??相關(guān)工作

目前國內(nèi)外對基于圖像的三維重建技術(shù)這一熱點技術(shù)有很多的研究，已經(jīng)有??很多成果和進展，主要是對特征檢測、特征匹配、攝像機標(biāo)定幾個部分進行研究。?有很多的基于圖像的三維重建軟件?。基于圖像的三維重建技術(shù)具有快速?、簡便、?逼真的優(yōu)點，能較好的實現(xiàn)現(xiàn)實事物的虛擬化，該方法尤其適合那些難以用?CAD??的方法建立真實感模型的自然環(huán)境，?以及需要真實重現(xiàn)環(huán)境原有風(fēng)貌的應(yīng)用。

(1)?國外研究現(xiàn)狀

1?????Paul E.Debevec——參數(shù)幾何體表示初始模型

2 ????Steven M.Seitz——顏色不變量?、順序可見性規(guī)則重建場景模型?3 ?????Roberto cipolla——三維重建系統(tǒng)?PhotoBuilder

(2)?國內(nèi)研究現(xiàn)狀

1 ????北京交通大學(xué)的袁保宗提出了，由真實世界到計算機虛擬世界的轉(zhuǎn)換問?題。

2 ????浙江大學(xué)的劉剛設(shè)計了，一個能繪制出幾何模型和表面紋理的真實場景?交互建模系統(tǒng)。

3 ????中科院自動化研究所，開發(fā)的?CVSuite，能利用立體視覺進行三維重建。

4 ????上海交大馬利莊提出了一種基于構(gòu)建?Visual Hull，求取物體形狀及表面?反射屬性的方法。

(3)?相關(guān)技術(shù)分析?、評價和比較

SFM：?MVS 算法的性能只取決于輸入圖像的質(zhì)量和攝像機參數(shù)，?所以?MVS 的成?功很大程度上歸功于底層的用來計算攝像機參數(shù)的?SFM 算法?。SFM 算法以一組?圖像作為輸入，生成兩個信息：每幅圖像的攝像機參數(shù)和圖像中可見的一組三維?點，?這些點通常被編碼為軌跡?。軌跡被定義為重建的?3D 點的 3D 坐標(biāo)和輸入圖?像子集中對應(yīng)的?2D 坐標(biāo)的列表。

MVS：稠密重建是假設(shè)相機參數(shù)已知的情況下，尋找空間中具有光度一致性的點，?對場景進行立體匹配的過程。

Colmap：COLMAP?是一種通用的運動結(jié)構(gòu)??(SfM) ?和多視圖立體 ?(MVS) ?管道，具?有圖形和命令行界面?。它為有序和無序圖像集合的重建提供了廣泛的功能。

Kinect：?首先用?Kinect?設(shè)備采集點云，?然后對點云進行地面分割提取主體，?過?濾掉噪點，?用?ICP?算法將不同視角的點云進行配準(zhǔn)，?最后用滾球法進行表面重?建。

這四種算法的具體應(yīng)用效果，?將在實驗結(jié)果中展示并詳細(xì)剖析。

3. ?研究方法（技術(shù)路線）

(1)?開發(fā)環(huán)境

PyCharm?、Jupyter notebook?、python3.7?、MVStudio

(2)?關(guān)鍵技術(shù)

SFM

1?????特征提取

一般采用?SIFT 算子,?因其具有尺度和旋轉(zhuǎn)不變性。

2 ?????匹配和建立?track， 圖像對兩兩匹配，?一般采用歐式距離。?

有兩種方法：

1) ??粗暴匹配：?對所有特征點都窮舉計算距離。

2) ??鄰近搜索：建立 KD 樹，縮小搜索范圍，能提高效率，但也有可能不

是最優(yōu)，?所以鄰域取值是關(guān)鍵，?越大越準(zhǔn)確，?越大計算量越大。

當(dāng)距離小于一定閾值的時候就認(rèn)為匹配成功,但是誤匹配也比較多,需要采取多種手段剔除:

如果最近距離與次近距離的比值大于某個閾值，?應(yīng)該剔除。

對匹配點采用采樣一致性算法?RANSC 八點法計算基礎(chǔ)矩陣，?剔除不滿足基?礎(chǔ)矩陣的匹配對。

當(dāng)匹配關(guān)系建立后，?需要生成?track 列表，?指同名點的相片集合，?比如第一??幅圖的?13?號點和第二幅的?14?號點及第五幅的?115?號點是同名點，則(1,13)、（2,14)、?(5,115）是屬于一個 track，據(jù)此可以生成一個 track 集合，?同時生成?track 的時候??也需要剔除無用匹配：

如果一個?track 包含同一幅圖多次，?則應(yīng)該剔除，?這是因為同一幅圖的多個?特征點都匹配了同一個點，?則匹配關(guān)系肯定是錯誤的。

如果?track 太少，應(yīng)該剔除，一般取 2，是指只有兩幅圖有同一個點，三維重?建的信息過少，?容易產(chǎn)生誤差。

3?????找初始化像對

目的是找到相機基線最大的像對,采用 RANSC 算法四點法計算單應(yīng)矩陣，滿?足單應(yīng)矩陣的匹配點稱為內(nèi)點，不滿足單應(yīng)矩陣的稱為外點，根據(jù)單應(yīng)矩陣公式?可知當(dāng)?T 越小時，?內(nèi)點占比越高，?也就是低視差現(xiàn)象越明顯。

因此找到一個內(nèi)點占比最小的像對就是初始化像對，當(dāng)然它前提必須滿足可?重建,這個可以通過匹配點個數(shù)保證。

4?????初始化像對的相對定向

根據(jù)?RANSC 八點法計算本征矩陣，可通過對本征矩陣 SVD 分解得到第二個?圖像的?R?、T，?在這一步需要進行畸變校正，?然后根據(jù)?R?、T 和矯正后的像點坐?標(biāo)三角計算出三維點，這里用到的方法是直接線性變換DLT，可以理解為測繪中?的前方交會。

5?????加入更多圖像

根據(jù)第四步生成的三維點和第三副圖與前兩圖的?track 關(guān)系，?可以反算第三?副圖的?R?、T，?然后繼續(xù)三角化計算出更多的三維點，?采用的同樣是?DLT，?這樣?反復(fù)重復(fù)第?5 步，?最后就會把所有像片的?POSE（?R、T）和三維點，這就是稀疏?重建?SFM 的成果了。

6 ?????從④開始需要進行光束法平差 Bundle Adjustment

這是一個非線性優(yōu)化的過程，目的是使重建誤差降低到最小，通過調(diào)整?POSE?和三維點使反向投影差最小，?如果相機沒有標(biāo)定,還應(yīng)該將焦距也參與平差。

Bundle Adjustment 是一個迭代的過程，在一次迭代過后，將所有三維點反向?投影到各自相片的像素坐標(biāo)并分別與初始坐標(biāo)比對，如果大于某個閾值，則應(yīng)將?其從?track?中去掉，?如果?track?中已經(jīng)小于?2 個了，?則整個track 也去掉，?一直優(yōu)?化到?jīng)]有點可去為止。

MVS

1 ?????稀疏?3D 點云重建(SFM)

檢測輸入的每幀圖像特征點，并進行特征點匹配，通過匹配的特征點恢復(fù)相?機的內(nèi)外參數(shù)（相機內(nèi)參：焦距、徑向畸變系數(shù)，相機外參：相機的位姿?R，t），?重建特征點的空間?3D 坐標(biāo)。

2?????全局視角圖像序列選取

從輸入圖像中選一幀作為參考圖像。通過一些指標(biāo)在輸入圖像中篩選出符合?要求的圖像。這里我們希望篩選出來的圖像和參考圖像，它們相鄰圖像視場之間?的拍攝視場角合適（相鄰圖像視場角太小會導(dǎo)致基線短，重建誤差大，視場角太?大則兩張圖差異太大也難以重建成功）。選取方法詳細(xì)介紹見本文第二部分算法?原理。

3?????種子點選取

從獲得的?3D 點云中，篩選出那些可以投影到參考圖像上的 3D 點，并且該點

能投影到至少?1 幀其他全局視場圖像（有些點按照投影模型無法投影到參考圖或?其他圖的成像面上）?。

4?????種子點深度與法向量信息恢復(fù)

將?3D 點投影到參考圖像上，?以?3D 點到參考圖像相機坐標(biāo)系原點的距離為投影?點像素初始深度，?3D 點到相機坐標(biāo)系原點的方向為初始法向量。

上面獲得了像素點的深度與法向量的初始值，我們需要對這些像素點的深度?和法向量進行優(yōu)化。以這些投影像素點為中心建立正方形模板，將每個模板里的?所有像素投影到空間?3D 坐標(biāo)中，?以一個模板為例，?再次把一個模板里的?3D 點?投影到其他視角的圖像上獲得投影的像素點，優(yōu)化像素點的深度與法向量信息使?得在參考圖像上的模板與在其他視圖上的模板投影差異盡可能小。詳細(xì)優(yōu)化算法

見本文第二部分算法原理

建立模板其實為了衡量參考圖像上的這個像素點與其他圖像上像素點的相?似性，僅憑一個像素點難以很好的表征，所以才引入了模板來表征中心像素點區(qū)?域的特征，而參考圖像與其他圖像的模板特征的差異是優(yōu)化深度和法向量信息的?關(guān)鍵。

5?????其余像素點深度與法向量信息恢復(fù)

計算種子點優(yōu)化后結(jié)果的置信度，參考下文基本概念光度一致性——衡量兩?個模板的相似程度，按照置信度高低建立隊列，對隊列中的點進行優(yōu)化，并將這?些點的周圍點加入隊列中。

Colmap

1?????數(shù)據(jù)采集

手機或者相機繞物體拍一周，?每張的角度不要超過?30?°。

2?????數(shù)據(jù)組織

將多角度拍攝的圖片組織為?colmap 的工程格式。

3?????提取圖像特征

從圖像中提取到特征值。

4?????特征點匹配

輸出：?提取到的特征點也存放到數(shù)據(jù)庫中。

5 ?????稀疏重建(SfM）

使用?SFM 進行稀疏重建。SFM，(Structure From Motion，從運動中恢復(fù)結(jié)構(gòu))，?是一種從一組不同視角下拍攝的無序或有序影像中恢復(fù)場景三維結(jié)構(gòu)和相機姿

態(tài)的技術(shù)。

input：??一組圖片。

output：?場景粗糙的?3D 形狀（稀疏重建），?還有每張圖片對應(yīng)的相機參數(shù)。

6?????深度圖估計

深度圖估計，?目的是恢復(fù)參考影像的深度信息。深度估計結(jié)束后，?可以得到?“photometric?”和“geometric?”下的深度圖和法向量圖?。在深度圖估計之前要進?行圖像去畸變操作。

7 ?????稠密重建（?MVS）

使用?MVS 進行稠密重建?。MVS?即多視圖立體幾何，?目的是在相機位姿已知?的前提下，逐像素的計算圖像中每一個像素點對應(yīng)的三維點，得到場景物體表面?密集的三維點云。

輸入：?多視角圖像?、相機位姿。

輸出：?稠密點云。

8?????融合

9?????稀疏重建結(jié)果可視化

10????深度圖?、法向圖可視化

11????稠密重建結(jié)果可視化

Kinect

1?????深度坐標(biāo)變換

對于每個像素啟用一只?CUDA 線程，給定一個 Kinect 紅外攝像頭的內(nèi)部校準(zhǔn)?矩陣?K，?使用如下公式

/tertupui(u)=/tectupDi(u)/tectupk-1[u,1]

2?????計算坐標(biāo)變換

相應(yīng)的頂點法線則直接取其右?、下鄰向量的外積，?并進行歸一化?。?時間?i 時的?6DOF 攝像機姿態(tài)使用一個剛性變換矩陣 T 表示，其中?T 包括了攝像機的旋轉(zhuǎn)?矩陣?R 和平移矩陣 t?。變換后的頂點和法線通過?T?即可再變換至全局坐標(biāo)系中。

3?????攝像機跟蹤

該部分的主要目的就是計算?6DOF 姿態(tài)?。核心的?ICP?即迭代最近點算法，?首?要?是?需?要?逐?幀?計?算?不?同?朝向?的?點?集?的?相?關(guān)?度?。?這?里?采?用?了?projective?data?association 方法計算相關(guān)度。

4?????體集成

針對已配準(zhǔn)的點云數(shù)據(jù)，?需要執(zhí)行后續(xù)的融合處理。

5 ????光線投射渲染

采用光線投射渲染前步生成的隱式表面。

降維

在本實驗中，降維是將三維模型信息降維到二維平面信息。對于噪聲和閾值?的處理是降維的核心任務(wù)?。去噪聲是為了減少無關(guān)信息對真實需求模型的影響，?閾值的選取是本次降維算法的靈魂，通過選取合適的閾值，從而選取有效信息區(qū)?間，?再進行?z 軸壓縮，?從而完成降維處理。

路徑規(guī)劃

一般的連續(xù)域范圍內(nèi)路徑規(guī)劃問題，如機器人、飛行器等的動態(tài)路徑規(guī)劃問?題，?其一般步驟主要包括環(huán)境建模?、路徑搜索?、路徑平滑三個環(huán)節(jié)。

1 ????環(huán)境建模。環(huán)境建模是路徑規(guī)劃的重要環(huán)節(jié)，?目的是建立一個便于計算?機進行路徑規(guī)劃所使用的環(huán)境模型，即將實際的物理空間抽象成算法能夠處理的?抽象空間，?實現(xiàn)相互間的映射。

2 ????路徑搜索。路徑搜索階段是在環(huán)境模型的基礎(chǔ)上應(yīng)用相應(yīng)算法尋找一條

行走路徑，?使預(yù)定的性能函數(shù)獲得最優(yōu)值。

3 ????路徑平滑。通過相應(yīng)算法搜索出的路徑并不一定是一條運動體可以行走

的可行路徑，?需要作進一步處理與平滑才能使其成為一條實際可行的路徑。

對于離散域范圍內(nèi)的路徑規(guī)劃問題，或者在環(huán)境建?；蚵窂剿阉髑耙呀?jīng)做好?路徑可行性分析的問題，?路徑平滑環(huán)節(jié)可以省去。

本次實驗采用的路徑規(guī)劃算法主要是貪心算法，?后續(xù)會設(shè)計更復(fù)雜的算法。

4.??實驗結(jié)果與分析

(1)?三維建模結(jié)果展示

? ? ? ? ? ? ? ? ? ? ? ? ? ? SFM 算法結(jié)果 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?MVS 算法結(jié)果

Colmap 算法結(jié)果

降維結(jié)果

Kinect 算法結(jié)果

路徑規(guī)劃

(2)?三種建模方法對比分析

SFM

數(shù)據(jù)集經(jīng)過?SFM 模型得到三維模型?。實驗結(jié)果中建筑物的點云比較稀疏，

呈稀疏分布，同時粗略表達出了一些紋理特征和一些簡單的幾何形狀，符合預(yù)期?結(jié)果。

這是因為?SFM 先從檢測圖像中提取 2D 特征（SIFT or ORB）?表征?。這些圖??像特征的表示為圖像中的一個小區(qū)域。而?2D 特征的特點是可以可靠地表示高度?紋理區(qū)域或者粗糙的幾何形狀。但是這些場景特征需要在整個場景中唯一（比如?重復(fù)的墻紋理，?難以匹配）?。故而通過這些唯一的特征只能生成稀疏的?mesh?。?當(dāng)圖像之間找到很多匹配項時，可以計算出圖像之間的?3D 變換矩陣從而有效地?給出兩個相機之間的相對?3D 位置，?從而獲得點云。

MVS

數(shù)據(jù)集經(jīng)過?MVS 模型得到三維模型?。實驗結(jié)果中建筑物的點云比較稠密，?呈稠密分布，已經(jīng)能夠表達出大部分紋理特征和一些復(fù)雜的幾何形狀，也符合預(yù)?期結(jié)果。

相比于?SFM，MVS 的表達細(xì)節(jié)更加豐富，更加接近實物情況。這是因為?MVS?算法用于細(xì)化通過?SFM 技術(shù)獲得的網(wǎng)格，?從而產(chǎn)生所謂的密集重構(gòu)?。此算法中?要求每個圖像的相機參數(shù)都起作用，?這由?SFM?算法輸出?。?由于它適用于更受約?束的問題（因為它們已經(jīng)具有每個圖像的攝像機參數(shù)，例如位置，旋轉(zhuǎn)，焦點等），?因此?MVS 將在 2D 特征未正確或無法正確檢測的區(qū)域上計算 3D 頂點或匹配。

Colmap

Colmap 算法結(jié)果是通過輸入多視角圖像，?經(jīng)過?colmap 算法得到的稀疏云，?并估計相機參數(shù)?。重建精度還是不錯的，?并且整體操作上比較快。

經(jīng)過查閱相關(guān)資料，?我們得知，?COLMAP 改進了 SFM，?首先，?引入幾何驗?證策略，利用信息增強場景圖，隨后提高初始化和三角測量組件的穩(wěn)健性。第二，?下一個最佳視圖選擇，最大化增量重建過程的穩(wěn)健性和準(zhǔn)確性。第三，一種穩(wěn)健?的三角測量方法，?其以降低的計算成本產(chǎn)生比現(xiàn)有技術(shù)顯著更完整的場景結(jié)構(gòu)。?第四，?迭代?BA（光束法平差），?重新三角化和異常值濾波策略，?通過減輕漂移

效應(yīng)顯著提高完整性和準(zhǔn)確性。最后，通過冗余視圖挖掘為密集照片集合提供更?高效的?BA 參數(shù)化。采用深度和法線信息的聯(lián)合估計，使用光度和幾何先驗的像?素視圖選擇，?以及多視圖幾何一致性項同步細(xì)化基于圖像的深度和法向融合。

由于?Colmap 算法的稀疏算法采用的是改進后的?SFM，?從而得到了場景中的?相機姿態(tài)和表示場景結(jié)構(gòu)的稀疏點云?。?因而在一定程度上和單純的?SFM 算法有?些相似，?通過結(jié)果觀察發(fā)現(xiàn)，?Colmap 算法不僅建立了 SFM 的表達出的基本輪廓?特征和圖像，?也表達出了相機參數(shù)，?標(biāo)識出了相機位置?。在建筑物表達方面，?Colmap 要比一般的 SFM 算法更勝一籌。

Kinect

Kinect 算法結(jié)果得到的三維建模信息相比去其他幾種算法更為豐富和具體，?但是也伴隨著許多信息丟失甚至扭曲的現(xiàn)象發(fā)生，?即產(chǎn)生空洞。

Kinect 算法之所以發(fā)生圖像扭曲的情況，是因為 Kinect 相機能夠獲取同一位?置的彩色和深度圖像（距離圖像），其中每個點像素的灰度值表示物體表面與相?機的實際距離。但是，?由于物體材質(zhì)、鏡面反射或區(qū)域遮擋等原因，Kinect 相機?在采集深度信息時容易在物體的邊緣或內(nèi)部丟失部分信息，即產(chǎn)生空洞（深度圖?像中空洞表現(xiàn)為像素值為零的區(qū)域），深度圖像中的空洞會給后期的圖像處理帶?來很多困難。因而也會間接影響我們掃地機器人后期對于降維以及路徑規(guī)劃的實際處理結(jié)果。

降維

以室內(nèi)場景為數(shù)據(jù)集，我們通過算法得到了建筑物的三維模型，對三維模型?信息進行降噪、降維處理，得到室內(nèi)地面二維平面圖。通過控制降維時算法的閾?值，我們得到了比較合理的二維信息。通過結(jié)果觀察可知，降維后的效果和真實?戶型圖很相似，?說明我們降維的效果還不錯。

路徑規(guī)劃

得到二維信息之后，?問題就轉(zhuǎn)化為在有障礙物的基礎(chǔ)上設(shè)計路徑規(guī)劃算法，?使得掃地機器人能夠合理掃過需要清掃的區(qū)域。

我們本次實驗采用的是貪心算法。