Tam giác hoá (triangulation): từ hai góc nhìn đến một điểm 3D
1. Bối cảnh
Mọi pipeline tái tạo 3D từ ảnh — structure from motion, photogrammetry, stereo — cuối cùng đều phải trả lời cùng một câu hỏi: biết một điểm xuất hiện ở đâu trong hai (hoặc nhiều) ảnh, và biết các camera, thì điểm đó nằm ở đâu trong không gian 3D? Bước này gọi là tam giác hoá (triangulation): “khôi phục điểm 3D” khi các camera đã biết (hoặc đã được ước lượng).
Trong trường hợp lý tưởng, đáp án chỉ là giao điểm của hai tia. Với ảnh thật, toạ độ pixel có nhiễu, hai tia là các đường chéo nhau (skew) và gần như không bao giờ cắt nhau, nên ta cần một tiêu chí hợp lý để chọn điểm tốt nhất. Bài viết này dẫn xuất lời giải tuyến tính chuẩn, cài đặt nó và kiểm tra hành vi của nó bằng thực nghiệm.
2. Camera lỗ kim
Một điểm 3D trong toạ độ thuần nhất \(\mathbf{X}=(X,Y,Z,1)^\top\) được chiếu thành điểm ảnh \(\mathbf{x}=(u,v,1)^\top\) bởi ma trận camera \(P\) cỡ \(3\times4\):
$$\lambda\,\mathbf{x} = P\,\mathbf{X},\qquad P = K\,[\,R \mid \mathbf{t}\,],\qquad K=\begin{bmatrix} f_x & 0 & c_x\\ 0 & f_y & c_y\\ 0&0&1\end{bmatrix}$$Trong đó \(K\) chứa các tham số nội (tiêu cự \(f_x,f_y\) tính bằng pixel và điểm chính \((c_x,c_y)\)), còn \([R\mid\mathbf t]\) là các tham số ngoại: phép quay và tịnh tiến từ hệ toạ độ thế giới sang hệ toạ độ camera. Đại lượng vô hướng \(\lambda\) là độ sâu xạ ảnh chưa biết. Ký hiệu \(\simeq\) thường được dùng cho “bằng nhau sai khác một hệ số tỉ lệ”.
3. Vì sao hai tia không cắt nhau
Mỗi pixel quan sát được xác định một tia xuất phát từ tâm camera. Với dữ liệu chính xác, hai tia cắt nhau tại điểm thật \(\mathbf X\). Với pixel có nhiễu, trong không gian 3D hai tia nhìn chung là chéo nhau — chúng đi lướt qua nhau mà không chạm. Hình dưới là lát cắt 2D nhìn từ trên xuống, nơi hai đường thẳng luôn cắt nhau, nên nó chỉ minh hoạ một nửa câu chuyện: nhiễu làm điểm giao dịch chuyển khỏi vị trí thật, chủ yếu dọc theo hướng nhìn (độ sâu).
Vì vậy ta cần một tiêu chí cho điểm “tốt nhất”. Hai lựa chọn tự nhiên là (a) tiêu chí đại số dẫn tới một hệ tuyến tính, và (b) sai số chiếu lại (reprojection error) mang ý nghĩa hình học.
4. Tam giác hoá tuyến tính (DLT)
Quan hệ \(\lambda\mathbf x=P\mathbf X\) cho biết \(\mathbf x\) và \(P\mathbf X\) song song, do đó tích có hướng của chúng bằng không:
$$\mathbf{x}\times(P\mathbf{X})=\mathbf 0 .$$Gọi \(\mathbf p_i^\top\) là hàng thứ \(i\) của \(P\) và \(\mathbf x=(u,v,1)^\top\). Khai triển tích có hướng cho ba phương trình, trong đó chỉ có hai phương trình độc lập tuyến tính:
$$u\,\mathbf p_3^\top\mathbf X-\mathbf p_1^\top\mathbf X=0,\qquad v\,\mathbf p_3^\top\mathbf X-\mathbf p_2^\top\mathbf X=0 .$$Với hai góc nhìn \((P,\mathbf x=(u,v,1)^\top)\) và \((P',\mathbf x'=(u',v',1)^\top)\), ta xếp bốn phương trình thành \(A\mathbf X=\mathbf 0\):
$$A=\begin{bmatrix} u\,\mathbf p_3^\top-\mathbf p_1^\top\\ v\,\mathbf p_3^\top-\mathbf p_2^\top\\ u'\,\mathbf p_3'^\top-\mathbf p_1'^\top\\ v'\,\mathbf p_3'^\top-\mathbf p_2'^\top\end{bmatrix}\in\mathbb R^{4\times4} .$$Vì \(\mathbf X\) là toạ độ thuần nhất nên ta chỉ biết nó sai khác một hệ số tỉ lệ, do đó ta giải bài toán
$$\hat{\mathbf X}=\arg\min_{\|\mathbf X\|=1}\ \|A\mathbf X\|^2 ,$$nghiệm của nó là vector kỳ dị phải của \(A\) ứng với giá trị kỳ dị nhỏ nhất. Nếu \(A=U\Sigma V^\top\) thì \(\hat{\mathbf X}\) là cột cuối cùng của \(V\). Cuối cùng ta đưa về toạ độ thường: \((X,Y,Z)=(\hat X_1,\hat X_2,\hat X_3)/\hat X_4\).
5. Cài đặt
Dưới đây là phần lõi của bản cài đặt (NumPy). Toàn bộ script, gồm cả thí nghiệm và các hình trong bài, có thể tải về.
import numpy as np
def triangulate_dlt(P1, P2, x1, x2):
"""Homogeneous linear triangulation: solve A X = 0 by SVD."""
A = np.vstack([
x1[0] * P1[2] - P1[0],
x1[1] * P1[2] - P1[1],
x2[0] * P2[2] - P2[0],
x2[1] * P2[2] - P2[1],
])
_, _, Vt = np.linalg.svd(A)
X = Vt[-1] # right singular vector of the smallest singular value
return X[:3] / X[3] # dehomogenise
Để so sánh, tôi cũng cài đặt phương pháp điểm giữa (midpoint): chiếu ngược hai pixel thành hai tia \(\mathbf c_i+s_i\mathbf d_i\), tìm \((s_1,s_2)\) làm cực tiểu khoảng cách giữa hai tia, rồi lấy trung điểm của đoạn thẳng ngắn nhất nối chúng.
Kiểm tra tính đúng đắn
Trước khi tin vào bất kỳ con số nào, tôi tam giác hoá một điểm từ các phép chiếu không nhiễu. Sai số tái tạo là 1.13e-15 (sai số làm tròn dấu phẩy động), đúng như kỳ vọng khi hai tia cắt nhau chính xác.
6. Thí nghiệm: đường cơ sở ảnh hưởng thế nào đến độ chính xác?
Thiết lập (dữ liệu tổng hợp, tái lập hoàn toàn). Tham số nội \(f_x=f_y=800\) px, điểm chính \((320,240)\). Hai camera đặt đối xứng trên trục x tại \(\pm b/2\), cùng nhìn về \((0,0,5)\). Các điểm 3D ngẫu nhiên với \(x,y\in[-1,1]\), \(z\in[4,6]\). Mỗi phép chiếu được cộng nhiễu Gauss độc lập với \(\sigma=0.5\) px. Với mỗi baseline \(b\), tôi tam giác hoá 2000 điểm (NumPy random seed 7) và báo cáo sai số 3D Euclid trung vị, cùng đơn vị với cảnh.
| Baseline b | Sai số trung vị DLT | Sai số trung vị Midpoint |
|---|---|---|
| 0.10 | 0.1492 | 0.1489 |
| 0.20 | 0.0789 | 0.0792 |
| 0.50 | 0.0295 | 0.0294 |
| 1.00 | 0.0155 | 0.0155 |
| 2.00 | 0.0083 | 0.0084 |
Các con số cho thấy điều gì
- Baseline quyết định độ chính xác. Tăng baseline 20 lần (0.1 → 2.0) làm sai số trung vị giảm khoảng 18 lần (0.149 → 0.0083), tức xấp xỉ tỉ lệ nghịch với baseline trong chế độ này.
- Điều này khớp với trực giác của stereo đã hiệu chỉnh (rectified). Với hai camera song song có tiêu cự \(f\) và baseline \(B\), độ sâu là \(Z=fB/d\) trong đó \(d\) là độ chênh lệch (disparity). Lấy vi phân, sai số disparity \(\delta d\) gây ra sai số độ sâu \(\delta Z\approx \dfrac{Z^2}{fB}\,\delta d\): sai số độ sâu tăng theo bình phương khoảng cách và giảm theo baseline.
- Trong thiết lập này DLT và midpoint gần như giống hệt nhau. Hai phương pháp chênh nhau dưới 1% ở mọi baseline. Thí nghiệm này (nhiễu nhỏ, hình học điều kiện tốt, cả hai camera đều nhìn vào tâm cảnh) đơn giản là không phân biệt được chúng. Tôi không đưa ra kết luận nào cho các chế độ khác; để có so sánh có hệ thống giữa các phương pháp, xem Hartley & Sturm (1997).
Hạn chế. Dữ liệu là tổng hợp, nhiễu là Gauss đẳng hướng, hiệu chuẩn camera được giả định chính xác, và tôi không so sánh với phương pháp tối ưu (cực tiểu sai số chiếu lại). Pipeline thực tế còn có méo ống kính, ghép cặp ngoại lai và sai số hiệu chuẩn — mỗi yếu tố cần cách xử lý riêng (ước lượng bền vững, bundle adjustment).
7. Bài học thực hành
- Dùng baseline lớn nhất mà thuật toán ghép điểm còn chịu được: nó giảm trực tiếp độ bất định về độ sâu.
- Kiểm tra code bằng dữ liệu không nhiễu trước; nó phải khôi phục điểm tới mức sai số làm tròn.
- Xem DLT như một ước lượng khởi tạo nhanh và vững; tinh chỉnh bằng cách cực tiểu sai số chiếu lại khi cần độ chính xác cao.
- Luôn báo cáo đại lượng bạn thực sự quan tâm (sai số chiếu lại, sai số 3D) — chúng không giống phần dư đại số.
Tôi nhận làm các việc này với tư cách freelancer. Hãy mô tả dự án trong vài câu, tôi sẽ phản hồi bằng các câu hỏi làm rõ và báo giá theo phạm vi cố định.
Nhận báo giá Xem dịch vụ
Tài liệu tham khảo
- R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press, 2004. ISBN 978-0-521-54051-3. (Chương 12, “Structure computation”.) Trang nhà xuất bản.
- R. I. Hartley and P. Sturm. “Triangulation.” Computer Vision and Image Understanding 68(2):146–157, November 1997. doi:10.1006/cviu.1997.0547.