Image Based 3D Modeling 以二維影像資料重建三維物體模型 指導教授:劉興民 教授 專題生:張鈞皓、蕭宥騰、裴家佑

Outline Introduction Data flow & Environments Method Mesh Result Bundler PMVS Mesh Result

What is this Image Based 3D Modeling? An automatic process which transforms photos into a virtual 3D model. Automatic Modeling Process Photos 3D model

Motivation: Those modeling methods are old fashioned. For example: 1. Artificial modeling spends too much time. 2. Special modeling hardware costs too much. A fast modeling method significantly improves development of virtual reality.

Implementation Outline

Environments 開發系統： Cygwin on Windows (C/C++) 相關工具： Meshlab Imagemagick

Implementation method Input: 對目標環場拍攝之照片(15~20張、照片中之物體必須有重疊性存在) 步驟: 1.讀取照片EXIF資訊並分析拍攝相對位置 2.從二維相片找出三維資訊 3.輸出圖片關係 4.corner detection進階特徵分析 5.三角化重建產生密點雲

Implementation method Bundler： 實作Structure form motion PMVS： 利用照片資訊，產生點雲

Structure from motion 從二維影像得到三維的資訊（影像間須有重疊性） 觀察者和物體必須有相對運動

特徵點分析 Use SIFT

判斷點相關性 建立K-dimension tree 找出涵蓋範圍最大的cut dimension，以此cut dimension的數值為依據建立子樹 方法一：以平均值將點分給兩邊子樹 方法二：將點平均分配給兩邊子樹，即找尋點的中位數 KD-tree 是一個針對k維度的多維度空間所設計的二元搜尋樹，樹中的階層是以資料點為基準分割維度空間，且每一個對應的子空間最少須包含一個資料點，並以此資料點來代表此一子空間。 KD-tree的提出主要是為了解決關連性搜尋（Associative Searching）的問題。關連性搜尋問題的描述如下：假設檔案F共有n筆紀錄，每一筆記錄都有k個屬性值（V0、V1、V2、V3、⋯Vi、Vk-1），而使用者可以使用系統進行查詢，此種查詢工作就稱為關連性搜尋[3]。 KD-tree是一種藉由遞迴的方式所建立的樹，根據資料的維度，分別比照第一維度，第二維度到第N維度，每一維度皆將資料分成兩邊。若分割到最後一軸時，樹的深度尚未滿足使用者所設定的值時，分割必須回到第一次分割資料集時所參考的軸，如此輪迴，直到滿足樹的深度為止。當資料點為n，KD-tree的概似最近搜尋的時間複雜度約略為O（log2n）[12]，較線性搜尋時間快。KD-tree也被廣泛應用在資料分群的問題中

Improvement We have modified the feature detection method of API to improve the quality of result. Before After

特徵點對應 approximate nearest neighbors RANdom SAmple Consensus 在多維向量空間下，每個空間上的點之間相近程度，是以距離的遠近作為代表，距離較近為較相近，距離較遠為較不相近。其中在n維空間上，判斷某一點與空間上所有存在點的相近點，可以利用線性搜尋法或是概似最近搜尋法等方式來比較。線性搜尋法，也就是利用計算點與點之間幾何距離的方式來比對空間上的所有存在的點，而一個點會有k個維度，若有n個存在的點，進行一次搜尋相近點（Nearest Neighbors）的時間複雜度將會達到O（kn），因此當點的維度或是點的數目過於龐大，使用線性搜尋法方法查詢相近點的時間，是相當耗時的。 以概似最近搜尋演算法的判別相近點，查詢空間上某點與其他點的相近點。當空間為較高的維度，或是空間上有大量資料點的時候，其速度是較為快速。概似最近搜尋法定義為在空間上所有點集合S中，其中S有n個點，從S取任一點p與給予查詢點q，計算p點與q點兩點之間距離，當距離為所給定的範圍之內，也就是視為p點為q點相近點，p點即為所求。概似最近搜尋法為利用切割空間成子空間的方式，首先將空間中的每ㄧ個點先做分類於每個子空間，進而依據使用者輸入的查詢點，能快速找尋查詢點位於的子空間而找出相近的點，而不用找尋空間上的每ㄧ個點。目前常用的概似最近搜尋演算法有以KD-Tree為資料結構的演算法及LSH（Locality Sensitive Hashing）等演算法。

corner detection Harris corner detector Difference of Gaussian

Expand the feature points Use Triangular Reconstruct 相鄰的點具有相似的法向量與位置 過濾處理，剔除灰度一致性、幾何一致性較弱的面

Mesh Use meshlab method： Ball pivoting

Result The final result is a point cloud. Point cloud is consisted of lots of points. Each points is represented by 3D coordinate and color. Photos 3D model

Comparison between different resolutions The resolution has positive relation to the quality of result and processing time. 80% 60% 40% 20

END Thank you for listening