技術筆記：Structure from Motion

以視覺方式取得3D模型方式中，除結構光和雙眼立體視覺外，最常見就是SFM。下列是接觸COLMAP(連結)時紀錄。

SFM最大特點就是全軟體計算，主要是三步驟，取出特徵點，特徵點匹配，3D重建，至此可生成能旋轉瀏覽的PLY檔案。若要針對每個PIXEL進行分析，可以前面結果為基礎，利用照片光影資料將其細緻化。

先以south building為範例，下載測試資料(連結)，約有一百多張照片，每張照片解析度為3072X2304，內容是環繞著一棟建築物逆時鐘拍攝照片，平均算來建築物每面約30張。

File->New Project->設定image為image目錄 新project放在base目錄名為 house (產生house.db)

File->Save Project 會成為 house.ini ( 奇怪，new沒有要save才有)

Feature detection and extraction

Processing->Feature Extraction ，使用SIFT演算法，可調整介面如下。不到一分鐘 完成，過程紀錄在db(sqlite) house.db。

Processing->Database Management，點選任一圖片後，再點擊show image，可以視覺化觀察SIFT後的標記點。以範例來說，標記出的點密密麻麻恐有上萬點，如此多的特徵點讓後續match和接合都異常順利。但自己拍攝口腔模型後，發現特徵點僅有數十個，大大影像實驗效果。

提取特徵點和三個項目有關，包括照片解析度(清晰)，拍攝角度(廣角)，及場景內容(豐富程度，以及反光狀況如材質)。colmap範例照片解析度3099 2314且為廣角拍攝，建築的紋理也多，容易成功。口腔相機僅有640X480且成像品質差，FOV又窄，更重要是口腔牙齒都光滑且缺少對比。若拍攝月桃種子，效果很好，相對的積木就很糟糕，若改用石膏牙齒口腔模型且加入雜點，成功率就大大提昇。

 

特徵點和畫面複雜度有關，塑膠平面幾乎無效

塑膠口腔模型，完全達不到SFM要求

Feature matching

此階段是對上述已標記特徵點照片，兩兩一組測試是否為相鄰，並將可能是同一特徵點但僅因視角不同而移動的點，記錄入資料庫。Processing->Feature Matching 可選擇參數如下圖。開始狂操GPU，過程中並沒有產生新的目錄，但有兩個新檔案產生(shm wal)，且db持續更新增大，15分鐘後，db檔案達到250M(或更大)，前兩個暫存db檔案則被移除。最後記得Save Project。

操作上，Processing->Database Management，點選任一個圖片，再點擊overlaping images，可以看到某一照片例如編號9和那些照片重合。系統並且依照重疊數量由大致小排序。

選擇其中一項後，點選show matches可見到以視覺化接合的方式。

從簡易的操作說明中，可以發現，上述接合過程是一對多進行，也就是說每張圖片都要和其他圖片進行比對計算，複雜度為NXN，所以拍攝的照片越多，處理時間為指數性上升。此時可以考慮引入另外一種模式（tab中第二項sequential），即每張照片都與上一張是相鄰，因為接合範圍縮小，要處理的項目變少，處理時間應該也大幅改進。

Python Code for step 1 and 2

將兩張2D影像組合並且並列顯示，可參考連結

Initiate SIFT detector
Find the key points and descriptors with SIFT
Apply FLANN for feature matching
Store all the good matches as per Lowe's ratio test
Find 2D points corresponding to good matches
Store points retrieved from the good matches
Find essential matrix and mask to remove outliers
Recover rotation and translation matrices from the essential matrix
Convert image coordinates to normalized coordinates
Find Extrinsic matrix of second camera, first camera aligned with world co-ordinates
Find projection matrix as a product of intrinsic and extrinsic matrix
Remove outliers
Find 4D homogeneous points and convert to 3D points

程式中需要的Calibration資料，可參考連結

Spare Reconstruction

最後步驟是將所有可能的照片進行真正接合，計算過程會為每張照片決定當時拍攝角度，並且透過多張照片，動態修正且排除誤差。

Reconstruction->Start reconstruction 過程中檔案系統並沒有變化，但畫面上陸續會出現模擬的照相機，位置也是系統模擬出的當時位置，除相機外，特徵點也陸續出現，且接近融合成3D建構物體。

目前COLMAP範例約花6分10秒，完成128張照片，共86000特徵點運算。因為資料庫檔案容量沒有變化，推測視角資料和點雲等應都還留在記憶體中。且也完成adjust。File->Export model 選base目錄，不須指定檔名，產生新檔案cameras.bin images.bin points3D.bin。這些也就是spare內容(雖然目前為止並沒有spare目錄)。下面是128張86000個點的點狀圖集合(spare)。

外圈是計算後每張照片原始拍攝位置

目前最大困擾是，範例照片或高解析照片都能順利完成接合，但實驗所需要的照片往往會出現。  => No good initial image pair found.  應該是找不到合適的接合點，推究原因則是牙齒材質太均一，無法產生數量足夠的特徵點。

export model as 可選擇PLY格式，選擇合適的位置後，填入檔案名稱包括副檔名.ply，即可用meshlab開啟瀏覽。立體圖如下，理論上來說，若點的數量越多越密集，呈現的效果越好。另外，畫面中的顏色是取出當時拍攝點的顏色，若特徵點不足，就會產生空洞。

程式結束後，若要繼續處理可先File>打開xxx.ini（project.ini似乎是預設，讀取的是另外指定名稱的例如 house.ini ），即可讀取資料庫。並且使用import model讀入先前資料目錄。

Dense Reconstruction

上述方案僅能呈現由特徵點構成的畫面，如何將更細部的紋理貼上表面，可參考理論基礎(連結)，繼續執行dense reconstruction，可取得每張照片的圖面深度，達到立體化視覺。Reconstruction->Dense reconstruction，先select設定到base目錄，開始依序執行各個步驟undistortion很快的產生spare和stereo兩個目錄，並且將bin檔拷貝到spare中。

Reconstruction->Dense reconstruction->點選 stereo，子目錄中會對各照片依ID進行處理，先增加陸續增加檔案。格式如P1180320.JPG.photometric.bin(約二小時) geometric(約一小時)，耗時非常久，結束後並沒有產生類似ply檔案。Save Project。

Reconstruction->Dense reconstruction->fused，以前面產生的bin和geometric為基礎，進行貼圖。執行時間約三十分鐘，完畢後會詢問是否要生成ply。生成檔案為fused.ply，可用meshlab瀏覽。

移動視角可以看到立體畫面，效果驚人

用640*480低階相機，拍攝大花紫薇。

Reconstruction->Dense reconstruction->Possion，以前面產生的bin和geometric為基礎，進行貼圖。執行時間約三十分鐘，完畢後生成meshed-poisson.ply，可用meshlab瀏覽。

Reconstruction->Dense reconstruction->Delaunay（德勞內三角化），以前面產生的bin和geometric為基礎，進行貼圖。執行時間約三十分鐘，完畢後生成meshed-delaunay.ply，可用meshlab瀏覽。

COLMAP編譯安裝使用

編譯非常惱人，順便紀錄過程，工作環境ubuntu 18.04 cuda 10.1 已安裝conda（會造成後續困擾，但沒辦法）。依指示進行(連結)。

git clone https://github.com/colmap/colmap

sudo apt-get install \
    git \
    cmake \
    build-essential \
    libboost-program-options-dev \
    libboost-filesystem-dev \
    libboost-graph-dev \
    libboost-regex-dev \
    libboost-system-dev \
    libboost-test-dev \
    libeigen3-dev \
    libsuitesparse-dev \
    libfreeimage-dev \
    libgoogle-glog-dev \
    libgflags-dev \
    libglew-dev \
    qtbase5-dev \
    libqt5opengl5-dev \
    libcgal-dev

sudo apt-get install libcgal-qt5-dev

在colmap目錄下，功能是大量非線性計算求最佳解
sudo apt-get install libatlas-base-dev libsuitesparse-dev
git clone https://ceres-solver.googlesource.com/ceres-solver
cd ceres-solver
git checkout $(git describe --tags) # Checkout the latest release
mkdir build
cd build
CC=/usr/bin/gcc-6 CXX=/usr/bin/g++-6 cmake .. -DBUILD_TESTING=OFF -DBUILD_EXAMPLES=OFF  (稍微改)
make -j
sudo make install

在colmap目錄下
git clone https://github.com/colmap/colmap.git
cd colmap
git checkout dev
mkdir build
cd build
CC=/usr/bin/gcc-6 CXX=/usr/bin/g++-6 cmake .. (稍微改)
make -j   (這時後會失敗找不到TIFF.so 因為被conda干擾 所以先把home下面anaconda3隨便改名 重新執行成功後 要記得改回來)
sudo make install  (理論上連LIB都安裝完畢)

在colmap目錄下
colmap -h
colmap gui (用command也可以歐，只是還沒有嘗試過)

以Command Line操作COLMAP sparse

COLMAP是純C語言專案，各項動作以database為資料交換，詳細動作可全由參數控制，API(連結)，FAQ(連結)。

91張640 480圖檔，目前位置是在，/home/kayjean/project/colmap_utils/warehouse_test，直接console目錄中。time colmap feature_extractor --database_path ./database.db --image_path ./images 第一次執行2秒 第二次執行0.1秒

time colmap exhaustive_matcher --database_path ./database.db 第一次執行3秒 第二次執行0.2秒  依照這種方式繼續進行3D重建mkdir ./sparse   time colmap mapper --database_path ./database.db --image_path ./images --output_path ./sparse 花費時間22秒。

產生的檔案，sparse/0 裡面有四個檔案 cameras.bin(相機位置)   images.bin(影像照片位置)  points3D.bin(所有計算出來的點雲)  project.ini這是紀錄這三個檔案產生時，相關檔案參數。所謂0的意思是，系統認為這次3D重建可區分成幾個子部份的第0個(就是首項)。啟用GUI模式，直接file->import model 選擇sparse/0/目錄，即可看到經過計算後的3D畫面。

time colmap model_converter --input_path ./sparse/0 --output_path ./test.ply --output_type PLY   時間約0.01秒，產生PLY檔案，啟動meshlab file->import mesh->xxx.ply就能看到點狀雲。

另外一種matcher方式為sequence    time colmap sequential_matcher --database_path ./database.db  第一次執行時間為3.4秒，效果和exhaustive差距不大，後續的mapper也沒有比較快，很難評價其效果。

以Command Line操作COLMAP register/merge

register是在原本已有的大3D結構中，隨意搜尋或添加新2D影像，不太符合線階段使用狀況。而merge是將兩個有部份結合的部份，接合在一起。

colmap feature_extractor --database_path ./database.db --image_list_path list.txt --image_path ./images   這其中雖然images有九十張，但是list.txt 內容是(001.jpg 002.jpg.. 沒有目錄資訊) 這次作業就只會處理其中45張，此時資料庫應該只有45張照片資料

因為檔案數量只有一半，time colmap exhaustive_matcher --database_path ./database.db 的時間也只花費一半

time colmap mapper --database_path ./database.db --image_path ./images --output_path ./sparse1 --image_list_path ./list.txt  大約10秒，注意我把資料先放在sparse1  看起來很正常

開始處理第二組，colmap feature_extractor --database_path ./database.db --image_list_path list2.txt --image_path ./images   list.txt改為list2.txt名單是後面一半，包括了中間十張左右重疊    time colmap exhaustive_matcher --database_path ./database.db  也是正常的  time colmap mapper --database_path ./database.db --image_path ./images --output_path ./sparse2 --image_list_path ./list2.txt  大約7秒，注意資料是放入sparse2  list2

 time colmap model_merger --input_path1 ./sparse1/0 --input_path2 ./sparse2/0 --output_path ./sparse3/  東西會直接放入sparse3，但merge是沒有project.ini

 time colmap bundle_adjuster --input_path ./sparse3 --output_path ./sparse4  這步驟花了4秒

time colmap model_converter --input_path ./sparse4/ --output_path ./test.ply --output_type PLY 結果正常，預計作法是，有個單獨的process，會一直監測目前images目錄，一開始超過10張照片或是有新檔案就開始運作，就會開始合併作業，並且紀錄一個目前已經處理的pointer。處理完畢後，如果前面還有別的model就會合併變成新的model，並且取出PLY顯示在畫面上，並且將自己設定為所謂前一個model，重複這個循環。過程中物件會逐漸長大。

以Command Line操作COLMAP dense

sparse的結果只是個骨架，並不適合放大瀏覽，所以有接下來的dense作業。mkdir dense

1.colmap image_undistorter --image_path ./images --input_path ./sparse/0 --output_path ./dense --output_type COLMAP 時間約1秒。

2.time colmap patch_match_stereo --workspace_path ./dense --workspace_format COLMAP --PatchMatchStereo.window_radius 3  --PatchMatchStereo.window_step 2 --PatchMatchStereo.num_samples 5 --PatchMatchStereo.num_iterations 3 時間約2分半。

前面精簡版本，手冊建議指令是colmap patch_match_stereo --workspace_path ./dense --workspace_format COLMAP --PatchMatchStereo.geom_consistency true 不過耗時太長。

3. 接下來有三種PLY檔案，需要照順序進行，第一種類似雜點 time colmap stereo_fusion --workspace_path ./dense --workspace_format COLMAP --input_type geometric --output_path ./dense/fused.ply 時間約31秒

4.time colmap delaunay_mesher --input_path ./dense --output_path ./dense/meshed-delaunay.ply 時間約11秒 著重貼面，最適合呈現

5.time colmap poisson_mesher --input_path ./dense/fused.ply --output_path ./dense/meshed-poisson.ply 效果不明顯 不需要

以Python操作COLMAP：colmap_utils

參考專案(連結)，範例應該是人工建造的環境，並且有每張片的拍攝角度。

以Python操作COLMAP：MISC

連結  加入CNN概念

Hierarchical Localization(連結)