演算法篇：如何用谷歌街景資料製作3D城市點雲模型

昨天IN2寫了伊利諾大學的Marco Cavallo關於如何利用谷歌街景資料製作3D點雲城市模型的文章，估計被標題吸引看到最後的同學會非常氣憤：留圖不留種，

XXXXX。其實， IN2昨天下午正好有事兒，於是先把上篇做好給大家看下，你們要的“種”其實都在下篇，這篇文章裡有好幾個演算法公式， IN2會盡最大努力翻譯的靠譜，但是依然不能保證絕對正確。所以，覺得自己雞腸文不錯或者特有鑽研精神的技術同學，請務必去看英文原文，然後幫IN2指出錯誤，謝謝鳥。

書接上文

計算深度地圖

現在我們有了全景圖片，接下來需要做的是提取對應的深度地圖。 Google Maps REST API允許使用者從下面這個連結

http://maps.google.com/cbk?output=json&cb_client=maps_sv&v=4&dm=1&pm=1&ph=1&hl=en&panoid=PANORAMAID

獲得一個深度圖像的JSON代碼（representation）、其中包含了全景圖片中每個圖元從相機到最近表面的距離資訊。通過Base64處理這些資料，並將其轉化成無符號8位元整數的陣列（ array of unsigned 8-bit integers）後，我們就能獲得標題資訊（Header Information）並獲得有用的資料，

例如參考平面數位（number of referenced planes）。事實上，在512×256網路上的每一個圖元都對應了眾多平面（Planes）中的一個，通過Normal Vector和其到攝像機的距離而定。所以，要想計算出一個圖元的深度，我們必須決定從攝影機中心發出的光線和相對對應平面的交叉點。將其重複到所有平面，我們能夠將深度地圖製成512×256元素的32位元浮動陣列（32-bit float array of 512×256 elements），這個要比我們的RGB全景圖片解析度低多了。

至於計算，對於每個點我們考慮它相關的平面，將其距離計算如下：

演算法1：深度地圖計算

公式中的“indeces”包含了每個圖元相關平面的陣列，為了能獲得一個代表單平面w∗ h vector的更簡便的圖片，例如，我們可以創造colored canvas，其中寬度為w、高度為h，而每個圖元可以被定義為：

演算法2：深度地圖視覺化

這時候會的出一個下圖類似的圖片

創造點雲

現在我們已經有了每個圖元的深度資訊，我們需要創建點雲同時將每一個點還原至之前獲得的全景圖片的色彩。考慮到 npoints =w∗h points，我們定義2個npoints ∗3 漂浮陣列包含了3D空間位置和每個點的色彩。現在，我們必須考慮全景圖片中的一點本來來一個球星圖片，所以我們必須使用下列公式將其重新投射到空間中：

演算法3：點雲創建

注意，除了重新投射，在2D中還原圖元的位置也是必要的，因為你需要從彩色全景圖片中獲得色彩資訊，因為全景圖片的解析度是不同的。

合成點雲

利用Google Street View API提供的不同位址間的連結，我們得到了相信全景圖片的標識點和地理資訊。所以，我們現在可以以新的地點座標重複之前的步驟，用全景圖片創造3D場景並能夠豐富此前我們用個點創建的場景，或者重建一個真實世界的場景。我們這個項目來說，會使用兩個界限：兩個全景圖片間的最短距離以及深度資訊的重複。可以將第一個載入的全景圖片想像成一個數的根部，然後以一種廣度優先的方式（breadth-first）進行探索。

平均來說，我們注意到穀歌的深度地圖通常包含現實世界的200-300米的距離，所以我們決定以1：1的比例來重建場景。我們將第一個點雲的中心座標設為（0，0，0），然後我們根據真實世界到全景位置的距離，按照offset proportional來加入其他的資料。利用一些幾何和近似值，我們可以用這樣一個演算法來計算[x，z]平面的distance vector：

演算法4：Offset距離運算

除了這個轉化，這個點雲需要根據從谷歌街景中提取的Heading特定資訊來沿著垂直Y軸來旋轉，然後才得到了一個近似於如圖的效果。

評估

投射以及位置精確度

雖然我們還沒有制定任何精確的公制來進行優化，但由於設定的虛擬單位和米之間的呼應，我們倒也能以一種較為粗獷的角度來進行觀察。儘管以我們的方式能夠製造出傳達優美幾何意識的非真representation，但是要說到更多紋理和色彩的3D創建時，我們還是有一些小問題的。

例如，如圖，我們能夠發現深度地圖和RGB全景圖片之間的不協調：建築的邊緣，被旁邊的淡藍色天空給擾亂了。另外，平面上投射的點同時也包括了代表天空的點，而後者按理說應該是定義為無窮遠，因此不應該出現的。

關於這點，此前有專家（Branislav Micusik）的專案使用了異常值消除，而其使用的場景是更複雜的機器學習演算法。

另一個問題是較遠的點，當每個全景圖片載入時，最遠的點變得更加稀少並且精確度消失。當組合多個點雲時，有些就是不能匹配，並在重建的模型上留下噪點，

如圖所示。一個簡單的祛除的方式，就是在合成多個全景圖片時，根據他們的距離來祛除。

最後，當單個全景的方向和維度看起來已經匹配的時候，經度方向依然有幾米的誤差，以至於合成多個全景圖片時會出現垂直方向的“重影”效果。這個可以歸咎於第四個步驟中方程式的不精確。

探索空間

為了完成上述評估，我們認為需要建立一個特定的使用者交互，讓他們能從不同角度探索這個重建的世界。為此，我們加上了3個camera：

·1個靜止的俯瞰的攝像機，當演算法聯繫載入全景圖片時，能夠一步一步的觀察重建過程。這個相機永遠根據最新載入的點雲而變化，但同時旋轉保持不變。

·1個沿橢圓形軌道旋轉的相機，能夠給使用者一個廣闊的視角來觀察建造起來的點雲。它的運動會根據每一幀定義為：

演算法5：電腦軌道計算

·1個互動相機，可以讓用戶自由的在空間中移動。攝像機根據鍵盤方向以及滑鼠移動的[x,y]平面進行移動。

另外，一個簡化的功能表，讓使用者可以改變FOV，將全景圖片重新投射在一個球面上。最後一個特性尤其重要，因為它可以讓使用者匹配全景圖片和點雲。

相關網頁【重要】

以上是Marco同學的論文主題，不知道大家是不是看的昏頭漲腦。對這個方法有興趣的同學，請一定要關注原作者的論文。

相關連結：

https://www.evl.uic.edu/documents/3drecomstrictionmcavallo.pdf

另一位元同學使用類似方式做成的案例及說明：

https://medium.com/@nocomputer/creating-point-clouds-with-google-street-view-185faad9d4ee

後記

正如原作者Marco同學所說，這個項目純粹是從學術角度來看，到底有沒有啥簡單且免費的方法，能夠重建一個城市的3D點雲模型，雖然有些小瑕疵，但是基本目的還是實現了。至於重建出的點雲模型究竟有啥用，這就見仁見智了，Marco認為這些資料可以用於交通導航、AR和VR等多種領域，IN2認為這個對於一小撮團隊來說可能確實是個可行方案。或者有心的人會不會拿百度或者高德地圖這麼試一下，總感覺如果真能成功，包裝一下去騙VC的錢還是有可能的，你說是不？

試驗成功的團隊，請務必私下致謝伊利諾大學的Marco同學，並購買IN2網站5年期的展示廣告位，謝謝。