12. COLMAP

Mở đầu

Consistent Localization and Mapping

Với phương hướng 3D reconstructive hay Structure-from-Motion(SfM), COLMAP là một trong những model được biết đến nhiều nhất vì có một pipeline rất hoàn chỉnh gồm nhiều bước chính: Image Matching - Camera Pose Estimation - Bundle Adjustment - Dense Reconstruction

Mục đích thường dùng nhất là cho Depth Map Viewer và "reconstruct scenes with a large number of images"

1. Correspondence Search

Bước đầu tiên là rìm một scene có thể mô tả toàn bộ input image (là 1 tập chứa các matching keypoints và 1 graph mô tả hình chiếu mỗi point)

1.1. Feature Extraction

Với mỗi image Ii, SfM detects 1 tập các local features Fi (keypoints) và bộ mô tả feature này (keypoint descriptor). Các keypoint nên là bất biến (invariant) với những thay dổi hình học (hoặc thay đổi của ảnh khi di chuyển camera) để có thể tạo cấu trúc các keypoint này trên nhiều image (tạo cấu trúc chung). SIFT là một model khởi đầu tốt để đại diện bước này

1.2. Matching

Chúng ta cần thiết lập quan hệ giữa các điểm tại những image (tập trung vào các keypoint). Cách dễ thấy nhất là tìm các cặp có khoảng cách ngắn nhất ở keypoint descriptor (thường dùng Euclide Distance L1-Norm). Tức với mỗi image pair C = {{Ia, Ib} | Ia, Ib thuộc I, a <b} ta xác định các matching Mab thuộc Fa x Fb

1.3. Geometric Verification

Mục đích là xây dựng 1 hệ thống quan hệ của các image (ví dụ như Homography H) hay xây dựng 1 hệ Epipolar Geometry thông qua Essential matrix E (calibrated) và Fundamental Matrix F (uncalibrated) và có thể mở rộng dựa vào Trifocal Tensor

Bởi vì việc matching chỉ dựa vào khoảng cách ngắn nhất, thường sẽ có những sai sót, vì vậy cần tối ưu hóa sự chuẩn xác tại bước này (RANSAC hay PnP Perpestive).

Kết quả này còn được gọi là scene graph với các image là node và các cặp điểm đã verified là edge

2. Incremental Reconstruction

input là scene graph tại bước trước

output là các pose estimate P = {Pc thuộc SE(3) | c = 1...Np} để reconstructed scence structure của tập points X ={Xk thuộc R3 | k=1...Nx}

2.1. Initialization

Chọn 1 pair làm initial là cực kì quan trọng nên phải cẩn thận. Chọn từ dense location nơi có ở nhiều ảnh thì mạnh hơn và tăng tính chính xác ủa reconstruction. Chọn từ sparser loccation thì giảm runtime

2.2. Image Registration

Khi đã có metric reconstruction, việc thêm vào các image mới sẽ dựa vào Perspective n Point PnP (2D-3D) (tức estimate pose Pc cho uncalibrated cameras (intrinsic parameter). Ngước lại, ta cũng re-estimate pose cho calibrated cameras bằng RANSAC. Với calibrated thì có 1 minimal pose solver nhưng ở uncalibrated thì có nhiều minimal solvers hoặc sampling-based. Chúng ta đề xuất chọn best image dựa vào accurate pose estimation và reliable triangulation

2.3. Triangulation

Image mới phải quan sát 1 phần đã có của scene points. 1 điểm scene point mới Xk chỉ được thêm vào tập X khi nó được quan sát ở ít nhất 1 viewpoint khác nữa. Tức cần 3 images (tạo multi-view triangulation cho 2D-3D)

2.4. Bundle Adjustment

Các image và triangulation vẫn là những object riêng biệt, dù cho có mối liên hệ cao (cấu trúc không chắc chắn được cải thiện dần qua tăng số ảnh và cải thiện intial camera pose. Nếu không được sàng lọc kĩ càng, sẽ nhanh chóng dẫn đến lỗi không thể không phục. Vì vậy, một phương pháp được đưa ra là tối ưu (minimize) reprojection error

Với ánh xạ π project scene points to image space (2D -> 3D) và hàm loss pj đến potentially down-weight outliers. Levenberg-Marquardt (LMA) là 1 phương pháp cho vấn đề BA cùng với Schur complement trick (dạng [pp pq, qp qq]) -> reduced camera system, update the points via back-substitution. Có 2 cách giải quyết: Exact (Direct) và Inexact (Indirect). Exact là tạo và tính toán 1 matrix cho dense hoặc sparse. Inexact sử dụng preconditioned conjugate gradient PCG. Do số lượng tính toán lớn với Direct, vì vậy sparse direct sẽ phù hợp hơn nhưng gây ra phân mảnh nhiều.
Đặc biệt với ảnh ở nguồn Internet, việc tối ưu hóa ảnh trùng lặp và số hóa là một vấn đề.

3. Contributions

3.1. Scence Graph Augmentation

- Estimate fundamental matrix F, nếu ít nhất Nf cặp inliers, image pair được xác định.

- Classify tranformation bởi số homography inliers Nh trong cùng image pair

- Đặt tiêu chuẩn theo GRIC là Nh/Nf < epsilon(hf)

- Với calibrated images, ta cũng estimate 1 essential matrix với số inliers Ne. Nếu Ne/Nf > epsilon(ef) thì calibration đúng

- Nếu 2 điều kiện trên thỏa mãn, xác định median triangulation angle alpha(m) như 1 pure rotation (panoramic (quan sát cầu)) và planar scences (planar (quan sát phẳng))

- Ta lại estimate 1 similarity transformation (A → P⁻¹AP) có Ns inliers. Mọi ảnh mà Ns/Nf > epsilon(sf) hoặc Ns/Ne > epsilon(se) thì được xếp vào WTF (watermarks, timestamps and frames) và không được thêm vào scene graph.

- Những valid pair còn lại, ta xếp loại (general, panoramic hoặc planar) với maximum support Nh, Ne, Nf -> Chuyển hết về non-panoramic

3.2. Next Best View Selection
Mục đích chính là minimize reconstruction error. Mục tiêu này rất quan trọng để tránh việc 1 loạt ảnh mis-registrations và faulty triangulation, ngoài ra còn cải thiện accuracy của triangulation và quality of pose estimates.

Chiến lược phổ biến là chọn image mà có nhiều triangulated points nhất -> Dễ bị bùng nổ tính toán, dư thừa -> Một chiến lước khác là chọn image có ít nhất Nt > 0 triangulated points, covariance sẽ được tính toán lại sau mỗi bước, phương pháp này xấp xỉ 1 efficient multi-resolution analysis

Ta đặt ra một score S để xắp sếp thứ tự đưa vào, các điểm có điều kiện quan sát tốt hơn được đưa vào trước. Để đạt được điều này, ta chia ảnh thành các fixed-size grid với Kl khoảng tại mỗi dimension. Mỗi cell có 2 state: empty và full. Nếu 1 empty được visible -> chuyển sang full, score Si của image + wl. Vậy ta đếm được số visible points hoặc việc các points clustered tại 1 part của image. Dù thế nào, nếu số visible point Nt bé hơn nhiều so với Kl^2 -> scheme này không bắt tốt phân phối điểm vì mọi điểm có khả năng rơi vào cell riêng

-> Mở rộng cách tiếp cận bằng image pyramid preprocessing với mỗi lớp l = 1..L có độ phân giải Kl = 2^l và score weight wl = Kl^2

3.3. Robust and Efficient Triangulation

Ta sử dụng epipolar geometry với các đường epipolar line trong multi-view stereo để tối ưu

Với việc inaccurate camera poses có thể ảnh hưởng lớn đến tracking high reprojection errors. Chúng ta cần một tập các yếu tố để theo dõi trước khi sàn lọc bằng multiple view -> recursive triangulation scheme

Bundler xoát tất cả các tổ hợp pairwise, biểu diễn dưới two-view triangulation và check xem có đủ góc tam giác. Nếu well-conditioned solution được xác định, mẫu được chấp nhận nếu mọi quan sát pass cheirality constaint. Phương pháp này có độ tính toán cao và không robust to outliers. -> RANSAC với ít nhất K iterations (maximize K)

Recursive ngừng khi size của consensus mới nhất < 3

3.4. Bundle Adjustment

Để giảm thiểu lỗi tích lũy, ta lựa chọn bước này ở cuối (thực tế là không cần BA ở mỗi bước, khi thuận toán chỉ áp dụng ở local thay vì global). Sử dụng VisualSFM với linear run-time

Những thứ cần quan tâm là:

- Parameterization

- Filtering -> thresholds

- Re- Triangulation (RT) -> pre-BA RT + post-BA RT

- Iterative Refinement (BA, RT và filtering) -> Util số filtered observations và post-BA RT points giảm dần. Hầu hết đã xuất hiện từ lần 2 interation

3.5. Redundamt View Mining

BA là bài toán biễu diễn bottleneck trong SfM

Cho scene với Nx points, mỗi ảnh được miêu tả qua binary visibility vector vi thuộc {0,1}^Nx với chữ số thứ n-th là 1 nếu Xn visible tịa ảnh i và 0 nếu ngược lại. Góc của interaction giữa 2 image a và b là bitwise opetations

Để xây groups, ta initialize group Gr bởi thay ảnh đầu Ia và tìm ảnh Ib mà maximizes Vab

Nếu, Vab > V và |Gr < S, Ib sẽ rời khỏi I và vào group Gr. Ngược lại 1 group mới được tạo, giảm time tìm Ib
Results

https://openaccess.thecvf.com/content_cvpr_2016/papers/Schonberger_Structure-From-Motion_Revisited_CVPR_2016_paper.pdf

Conclusion

The structure-from-motion (SfM) process consists of several steps:

Image Matching: The first step is to find matching features in the images. This can be done using a variety of feature detection and matching algorithms, such as SIFT, SURF, ORB, or BRISK. The output of this step is a set of matched feature points in the images.
Camera Pose Estimation: The next step is to estimate the camera poses, or the locations and orientations of the cameras in the 3D space. This can be done using the matched feature points and the camera projection matrix. The projection matrix is a 3x4 matrix that describes how a 3D point is projected onto the image plane.
Bundle Adjustment: The camera poses and the 3D points are usually refined iteratively using a method called bundle adjustment. Bundle adjustment is an optimization method that minimizes the reprojection error, or the difference between the observed feature points and the projected 3D points.
Dense Reconstruction: The final step is to compute the dense depth maps, or the per-pixel depth values in the images. This can be done using a variety of algorithms, such as multi-view stereo (MVS) or depth-from-focus (DFF).

COLMAP uses a combination of these steps to reconstruct the 3D geometry of a scene from a set of images. It provides a number of algorithms and options that allow you to customize the reconstruction process to your specific needs.

Using

download COLMAP tại https://colmap.github.io/install.html rồi làm theo hướng dẫn tại https://www.youtube.com/watch?v=pvvnPib4lFA&ab_channel=C0

Thử model kết quả với https://www.youtube.com/watch?v=Sdy2A5jPKCU&ab_channel=Krishnan và

https://colab.research.google.com/drive/13vH3G1dTgJlVcvTIbRvYltB9u0UclXFn

kết quả: