The power of camera matrix : Visual Hull rescontruction

vhcolor
Multi-view Captures
visualltex
Visual Hull Reconstruction with texture mapping

 

Introduction

談到computer vision,主題有千百種 ( tracking、AR...etc ),但最讓人著迷的答案肯定只有一種:重建 ( reconstruction );一個對真實世界到電腦空間的神奇轉換,與CG投影的完全對應,便是 reconstruction 了。

cgcv

本篇使用之前談到過 camera matrix 進行重建,利用多張視角的影像及輪廓剪影 ( silhouette ) 進行 reconstruction ,是個人認為CV中最有成就感的其中一個部分。

主要的做法是利用 camera matrix ,將3D空間中的一個 voxel (一般就是一個 cube ) 投影至多視角 silhouette 做 visibility test,計算該 voxel 是否存在;密集投影不同位置的 voxel 進而產生出一組 solid model,而其中將考慮到利用 octree 的投影加速法。

有了 solid model 之後,我們想將其 implicit surfaces 轉換為一個 surface mesh,方便給 graphics engine rendering。這邊使用到 Marching cubes 的方法,並且會遇到 ambiguous cases;進而衍伸出 Marching tetrahedra的方法,當然最後面還可以利用 Tessellation 的方式再細分出平滑模型。

最後則是 texture mapping 的部分。尋找最合理的 texture 投影至 mesh model上。

Silhouette

中文翻譯應該是輪廓,由各個角度的物體 silhouette 來投影重建出 3D 模型,基本上每個角度的影像都是經過校正,也就是已經有每張影像的 camera matrix。這邊通常是需要控制下的拍攝環境如藍幕影棚,才可以方便後續用軟體快速去背。

vis
silhouette

Visibility Test

回顧基本的 camera matrix P_{3\times 4}用法,3D點\left[X,Y,Z,1\right]^T投影在影像上的座標\left[x,y,1\right]


s\begin{bmatrix} x \\ y \\ 1 \end{bmatrix}={ P }_{ 3\times 4 }\begin{bmatrix} X \\ Y \\ Z \\ 1 \end{bmatrix}

grid
A 3D voxel grid

想像在 3D 座標系統中有一組由許多細小 voxel 組成的 grid ,每個 voxel 有 8 個頂點,我們嘗試投影這 8 個頂點投影在所有 silhouette 影像中。然後我們有下面三種投影結果

  • (Type White) 8 個頂點都在 silhouette 內 (白色區塊) : 該 voxel 位於物體內部
  • (Type Black) 8 個頂點都在 silhouette 外 (黑色區塊) : 該 voxel 位於物體外部
  • (Type Gray) 部分頂點在 silhouette 內和外 : 該 voxel 橫跨於物體表面

如果我們把 type gray 的 voxel 畫出來,就可以得到類似下圖的結果,物體邊緣的精細程度與 voxel 大小有關,越是細小的 voxel 可以得到越精細的模型,但是同時計算的投影複雜度也會高上許多。

ingrid
Gray Voxel

為了要再增加 voxel 精度的同時加速計算,在CG領域中常透過 Octree 來進行 coarse to fine 的切割,示意如下圖。先透過較大的 voxel 進行 visibility test,若為 type gray voxel,則分割成 8 個 sub-voxel 遞迴投影細分,直到我們要的 voxel 大小為止。

958px-octree2-svg
Octree

如果我們僅保留 type white voxel,得到的模型將永遠比真實物體小,並且在內部的 type white voxel 是被遮擋住的,無法被看見,儲存或渲染  type white voxel 是沒有效率的。我們要處理並儲存的就是這些位於物體表面的 type gray voxel 來貼近真實物體。

下圖表示一個 coarse octree 的範例結果,有點像 minecraft 人物XD。

coarselevel
Coarse Octree Level

Marching cubes or marching tetrahedra

為了得到更平滑的 surface,type gray voxel 將 8 個頂點的位置編碼,每個 voxel 根據頂點在 silhouette 內外組合可以有許多 surface 如下所示其中幾個,並且還有其旋轉型,我們稱為 marching cubes,這邊其實 marching cube 的 surface有無法明確辨識的組合 ambiguous cases,因此在理論上重建的 surface 是有可能不相連的;後來則有 marching tetrahedra 來改進平滑性 surface 連續連性。

640px-marchingcubes-svg

cubenumbering

V8 V7 V6 V5 V4 V3 V2 V1
img1 0 1 0 0 1 0 1 1
img2 0 1 0 1 0 0 1 1
img3 0 1 0 1 1 0 0 1
AND 0 1 0 0 0 0 0 1

如上表所示將 8 個頂點投影得到 silhouette 內的點為 1 ,外則是 0 。並且對一個頂點在所有影像的投影做 AND 運算,排列後得到有 255 種組合。

這邊有人下苦功編輯了 lookup table來做對應,我們只要寫程式按照 voxel 頂點的投影結果就可以對應出連續的三角面了,非常方便,可以 google 參考。結果如下圖,得到更平滑的 3D surface,並且 mesh 頂點是連續的。

vsmarchingcube

3D model demo (滑鼠可操控,Y軸反了自己轉正...)。

Texture Mapping

最簡單的 texture fetching 就是 nearest camera 投影,計算每個物件頂點最接近的 camera center,並投影到其影像上,但是遇到遮蔽物時就會被覆蓋 texture,如下圖,腰內側被手臂的 texture 覆蓋。

vstexnn

一個簡單的方式,由 nearest camera 的附近尋找相鄰 camera,投影並得到複數個 texture 結果,並且選離 texture color mean 最接近的那台 camera 作為最終的 texture。得到如文章標題的圖,雖然在遮蔽部分還有些許瑕疵,但基本上已經有所改善。

Conclusion

但使用 silhouette 作為物體表面的描述有所不足,如 concave 的凹陷處就不能由 silhouette 表達 (例如無法重建高爾夫球的凹陷,因為 silhouette 看起來是沒有凹陷的 ),需要由 stereo matching 來測量正確的深度。稱為 Hull 就是因為重建出來的物體基本上一定是比真實表面輪廓來得大,像一個殼一樣包住物體。

concave_cube
A concave cube example, which can't be done well through silhouette.

Visual Hull 作為入門的 CV project相當有成就感,理解投影並重建 3D 模型,並且也可以應用在 multi-view stereo 的 initial surface 上,或是做為其 wrong patch filtering 的手段。

Reference

  • L. Chou and Z. Chen, “Fast octree construction endowed with an error bound controlled subdivision scheme”, Journal of Information Science and Engineering, vol. 22, no. 3, pp. 641-657 (2006).
  • Wen-Chao Chen, Hong-Long Chou and Zen Chen, A quality controllable multi-view object reconstruction method for 3D imaging systems, Journal of Visual Communication and Image Representation 21 (5–6) (2010), pp. 427–441.\
  • http://users.polytech.unice.fr/~lingrand/MarchingCubes/accueil.html

Attachement

  • report: 報告中的 gray voxel 判斷使用 distance map 來增加可調控精準度,並非一需要。
  • matlab code: visual-hull-release

Leave a Reply

Your email address will not be published. Required fields are marked *