Triangulation : Linear Triangulation
Triangulation 은
- 2개의 image plane 사이의 기하학적 관계가 주어진 경우
- (←이는 Essential Matrix $E$ 또는 Fundamental Matrix $F$가 주어짐),
- 이 2개의 image plane상의 stereo pair($\mathbf{u}_\text{R}$, $\mathbf{u}_\text{L}$) 이 주어지면
- 이로부터 원래의 3D 공간좌표 $X$를 계산하는 것을 가르킴: 실제로 depth map을 구해낸다.
카메라가 2대인 이유는 depth 정보를 추출하기 위해서임.
참고로 관련 Hardware 를 살펴보려면 다음 글을 참고.
2024.07.17 - [Programming/DIP] - [CV] Depth Cameras
[CV] Depth Cameras
Depth CamerasDepth Camera는 3차원 공간에서 object와의 거리를 측정할 수 있는 카메라를 가르킴.CV 등에서는 카메라와 객체간의 거리를 depth라고 부름.Active 방식과 Passive 방식으로 크게 나뉘어지나, 오늘
dsaint31.tistory.com
이 글에서는 직접적으로 linear triangulation을 통해 구하는 방법을 위주로 설명한다.
(실제로는 카메라 왜곡 제거, stereo rectification, epipolar line을 통한 matching, noisy data를 위한 RANSAC 등의 여러 방법이 순서에 따라 같이 사용됨)
가장 단순한 형태의 Triangulation은 다음과 같음.
2024.07.04 - [Programming/DIP] - [CV] Triangulation: Simple Version
[CV] Triangulation: Simple Version
Triangulation: Simple VersionSimple Triangulation을 위해선 다음의 가정이 성립되어야 함.두 카메라는 동일한 focal length (초점거리) $f$ 를 가지며,동일한 평면 상에 virtual image plane을 가지며 (rectification을 수
dsaint31.tistory.com
Fundamental Matrix와 Essential Matrix를 사용한 Triangulation(삼각측량)
두 카메라 시스템 간의 기하학적 관계는 Fundamental Matrix와 Essential Matrix를 사용하여 나타내어짐.
Fundamental Matrix와 Essential Matrix
- Fundamental Matrix (F):
- image plane 좌표 간의 관계를 나타냄.
- 두 카메라의 intrinsic $K$및 extrinsic $\begin{bmatrix}R & \mathbf{t}\end{bmatrix}$ parameters를 포함.
- Essential Matrix (E):
- normalized image plane 좌표 간의 관계를 나타냄
- 두 카메라 간의 회전 $R$및 translation $\mathbf{t}$만 포함: $\begin{bmatrix}R & \mathbf{t}\end{bmatrix}$.
이 $E$ 또는 $F$를 통해이용하여 촬영대상의 3D 좌표를 추정하는 방법은 크게 다음으로 나누어짐.
- cross product 기반을 사용하는 방식.
- 2개의 image plane의 좌표계 간의 관계를 이용하여 linear triangulation으로 구하는 방법.
1. cross product를 사용한 방식
Epipolar constraint을 사용하여 3D 좌표를 추정하는 데 일반적으로 사용되는 방법.
상대적으로 좋은 성능을 보임.
참고로 epipolar constraint는 다음과 같음.
$$\begin{aligned}\mathbf{x}_\text{L}^\top E \mathbf{x}_\text{R}&=0\\ \left(K_\text{L}^{-1}\mathbf{u}_\text{L}\right)^\top E K_\text{R}^{-1} \mathbf{u}_\text{R} &=0 \\ \mathbf{u}_\text{L}^\top F \mathbf{u}_\text{R} &= 0\end{aligned}$$
여기서
- $\mathbf{u}_\text{L}$와 $\mathbf{u}_\text{R}$는 각각 왼쪽 카메라와 오른쪽 카메라의 image plane 상의 같은 target에 해당하는 점의 좌표임: 이를 찾기 위한 correspondence problem을 풀어야 함.
- $\mathbf{x}_\text{L} = R \mathbf{x}_\text{R} +\textbf{t}$
- $F$는 Fundamental Matrix임.
2024.06.28 - [분류 전체보기] - [CV] Epipolar Geometry [작성중]
[CV] Epipolar Geometry [작성중]
epipolar geometry는두 개의 카메라 images에서대응하는 점들 사이의 기하학적 관계를 설명하는 데 사용되는 용어Epipolar geometry는 각 카메라 image 상의 각 점이 epipolar line을 통해 어떻게 연결되었는지를
dsaint31.tistory.com
cross product를 사용하는 방법을 간단히 말하면 다음과 같음.
- epipolar constraint을 사용하여 각 이미지 점과 대응하는 epipolar line (or epiline)을 계산.
- 각 epipolar line을 통해 correspondance를 추출: local feature 를 활용한 correspondance problem.
- $\mathbf{u}=\alpha K\begin{bmatrix}R &\mathbf{t}\end{bmatrix} \mathbf{X}$에서 cross product $\mathbf{u} \times K\begin{bmatrix}R & \mathbf{t}\end{bmatrix} \mathbf{X}=\mathbf{0}$ 등을 이용하여 $\mathbf{X}$의 3D 좌표를 계산
$$\mathbf{u}_\text{L} \times (P_\text{L} \mathbf{X}) = \mathbf{0} \\ \mathbf{u}_\text{R} \times (P_\text{R} \mathbf{X})=\mathbf{0}$$
다음의 cross product의 성질을 이용하여 linear system을 만들어서 풀어냄.
2024.06.28 - [.../Linear Algebra] - [LA] Matrix Multiplication for Cross Product
[LA] Matrix Multiplication for Cross Product
Matrix Multiplication for Cross Product특정 vector와의 cross product를 matric multiplication의 형태로 표현하기도 한다. 벡터 $\mathbf{a}$와 $\mathbf{b}$의 Cross Product(교차곱 or 벡터곱) $\mathbf{a} \times \mathbf{x}$는 다
dsaint31.tistory.com
보다 자세한 건 다음을 참고
https://www.cs.cmu.edu/~16385/s17/Slides/11.4_Triangulation.pdf
가급적 위의 url로 확인하고, 만약 링크가 깨지면 아래의 첨부파일을 이용할 것.
2. cross product를 사용하지 않는 방식
똑같이 epipolar constraint을 사용하지만,
직접 system of linear equations를 구성하여 3D 좌표를 추정함.
촬영대상의 world space의 좌표 $\mathbf{X}$를 구하는 것이지만
아래 그림의 경우, 오른쪽 카메라의 좌표계가 world coordinates와 일치하게 주어짐
(많은 경우 계산 편의를 위해서 두개의 카메라 중 하나의 좌표계와 world coordinate 를 맞춤)
위의 그림에서 2개의 카메라의 각 camera matrix $P^{(1)}$과 $P^{2}$는 다음과 같이 주어짐.:
오른쪽 카메라의 camear matrix $P^{(1)}$은 world coordinate와 같은 축을 공유하여 보다 단순함.
왼쪽 카메라의 camera matrix $P^{(2)}$는 Fundamental Matrix 등을 통해 얻어진,
오른쪽 카메라 좌표계를 왼쪽 카메라 좌표계로 변환하는 rotation matrixh $R$ 및 translatoin $\mathbf{t}$ 를 반영한다.
Linear System 구성 및 해 구하기
위에서 구한 camera matrix에서 우리가 구해야 하는 미지수는 3개로 $\mathbf{X}$의 x,y,z 컴포넌트의 값이나,
오른쪽 카메라가 월드좌표계와 같다고 가정했기 때문에, $\mathbf{x}_\text{R}$을 구하면 되고,
$R$과 $\mathbf{t}$를 이용하여 $\mathbf{x}_\text{L}$을 $\mathbf{x}_\text{R}$의 식으로 바꿈.
이를 풀어 쓰면 다음과 같음.
여기서 오른쪽과 왼쪽의 카메라 모두 3번째 행이 1이므로 (homogeneous coordinates),
이를 $u_\textbf{R}$, $v_\textbf{R}$,$u_\textbf{L}$ 과 $v_\textbf{L}$ 을 곱하여 각각에 대해 빼주면 다음의 등식을 얻을 수 있음.
이를 왼쪽 카메라 관련 matrix equation의 관계에도 적용가능하며, 이들을 다 적용하면 다음과 같은 linear system을 구성할 수 있음.
이는 homogeneous equation $A\mathbf{x}=\mathbf{0}$의 문제이며,
이 경우, SVD(Singular Value Decomposition)이나 EVD (Eigenvalue Decomposition) 등을 통해
쉽게 구할 수 있음.
- SVD를 사용한다면 matrix $A$ null space를 찾아 풀 수 있고,
- 이때 $\mathbf{x}$는 가장 작은 singular value (특이값)에 대응하는 벡터가 됨.
2024.07.16 - [분류 전체보기] - [ML] Constrained Least Squares: Lagrangian 을 활용.
[ML] Constrained Least Squares: Lagrangian 을 활용.
문제설정흔히 볼 수 있는 least squares problem은 다음과 같음.$$\mathbf{A'f'}=\mathbf{b}$$ 이를 다음과 같이 augmented matrix와 homogeneous coordinate를 사용하여 homogeneous equation형태로 정리할 수 있음.$$ \mathbf{A} =
dsaint31.tistory.com
[Math] EVD 및 SVD로 $\textbf{x}^\top A^\top A\textbf{x}$의 최소값 및 해 구하기: Total Least Squares
Vector $\mathbf{x}$ 와 Matrix $A$가 주어졌을 때,$\mathbf{x}^\top A^\top A \mathbf{x}$의 minimum (or lower bound)를 구하는 방법에 대해Singular Value Decomposition(SVD)와 Eigenvalue Decomposition(EVD)을 이용하는 방법. $\underset{\ma
dsaint31.tistory.com
다음의 자기자신과의 cross product가 0인 점을 이용하여 $A\mathbf{x}=\mathbf{0}$를 유도하기도 함.
$$\begin{aligned}\mathbf{u}_\text{R} &= P^{(1)}\mathbf{x}_\text{R} \rightarrow \mathbf{u}_\text{R}\times\mathbf{u}_\text{R}=\mathbf{u}_\text{R}\times(P^{(1)}\mathbf{x})=\mathbf{0} \\ \mathbf{u}_\text{L} &= P^{(2)}\mathbf{x}_\text{L} \rightarrow \mathbf{u}_\text{L}\times\mathbf{u}_\text{L}=\mathbf{u}_\text{L}\times(P^{(2)}\mathbf{x})=\mathbf{0}\end{aligned}$$
Pseudo Inverse 의 형태로도 풀 수 있으며 이 경우 linear system은 다음과 같음 (이는 OLS에 해당)
$$A\mathbf{x}=\mathbf{b} \\ A^T A \mathbf{x}=A^T \mathbf{b} \\ \mathbf{x}= (A^T A)^{-1} A^T \mathbf{b}$$
2022.12.02 - [.../Math] - [LA] Pseudo Inverse Matrix
[LA] Pseudo Inverse Matrix
참고로 아래에 Singular Vector Decomposition으로 Pseudo Inverse를 구하는 방법이 있음. Pseudo Inverse Matrix square matrix 가 아닌 matrix $A_{m\times n}$에서 inverse에 해당하는 matrix를 구하는데 사용됨. $$ A^+_{n\times m}=\
dsaint31.tistory.com
2022.04.28 - [Programming/ML] - [Fitting] Ordinary Least Squares : OLS, 최소자승법
[Fitting] Ordinary Least Squares : OLS, 최소자승법
Ordinary Least Squares : OLS, 최소자승법Solution을 구할 수 없는 Over-determined system에서 solution의 근사치(approximation)을 구할 수 있게 해주는 방법임.Machine Learning에서 Supervised Learning의 대표적인 task인 Re
dsaint31.tistory.com
같이보면 좋은 자료들
2024.06.29 - [Programming/DIP] - [CV] Stereo Vision: Stereo Matching, Triangulation, Depth Map
[CV] Stereo Vision: Stereo Matching, Triangulation, Depth Map
CV와 DIP에서 Stereo Vision은 같은 대상에 대해, 서로 다른 view point에서 촬영된 두 image(보통 좌우 두개의 카메라로 구성되는 binocular stereo pair image)를 사용하여 3D 정보(주로 depth map)를 추출하는 기
dsaint31.tistory.com
2024.07.16 - [Programming/DIP] - [CV] Stereo Calibration or Stereo Camera Calibration
[CV] Stereo Calibration or Stereo Camera Calibration
Stereo Calibration은Stereo Vision System에서두 카메라의 상대적인 "위치와 방향(pose)"을 결정하는 과정임.2024.07.09 - [Programming/DIP] - [CV] Pose: Position + Orientation [CV] Pose: Position + OrientationPose라는 용어는Compute
dsaint31.tistory.com
[CV] Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x}$
Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x}$Camera Model Parameter Estimation 문제를$$\underset{\mathbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x} \\ \text{subject to }
dsaint31.tistory.com
[CV] Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x}$
Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x}$Camera Model Parameter Estimation 문제를$$\underset{\mathbf{x}}{\text{argmin }} \mathbf{x}^\top A^\top A \mathbf{x} \\ \text{subject to }
dsaint31.tistory.com
'Programming > DIP' 카테고리의 다른 글
| [CV] Image Plane to Image Sensor Mapping (0) | 2024.07.06 |
|---|---|
| [CV] Triangulation: Simple Version (1) | 2024.07.04 |
| [CV] Stereo Vision: Stereo Matching, Triangulation, Depth Map (0) | 2024.06.29 |
| [CV] Coordinate Systems (0) | 2024.06.29 |
| [CV] Epipolar Geometry [작성중] (0) | 2024.06.28 |