演算法篇：如何用谷歌街景數據製作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

後記

說實話，光看這7、8個公式就夠人一嗆，IN2估計不搞技術和演算法的同學估計對本文是沒啥興趣的，這也可以解釋為啥昨天的上篇在微信點擊率並不很高，反倒是在頭條有好多人收藏和轉發。

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

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

相關閱讀

[術說]Deepano專家詳解360°視頻深度信息及6自由度VR

Facebook新VR相機詳解：深度信息如何產生 6DOF如何實現

用雷達做出深度信息360視頻的公司 被Red創始人看上了

[消息來自www.evl.uic.edu IN2原創資訊轉載請註明來源及鏈接]

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！