삼각측량(컴퓨터 비전)

컴퓨터 시력 삼각측량이란 2개 이상의 영상에 투영된 3D 공간의 점을 결정하는 과정을 말한다. 이 문제를 해결하려면 카메라 매트릭스로 대표되는 가장 간단한 사례에서 관련 카메라에 대한 카메라 투영 기능의 파라미터를 3D에서 2D까지 알아야 한다. 삼각측량을 재건 또는 교차로라고도 한다.

삼각측량 문제는 원칙적으로 사소한 것이다. 영상의 각 점은 3D 공간의 선에 해당하므로 3D의 선에 있는 모든 점이 영상의 점에 투영된다. 두 개 이상의 영상에서 해당 점의 쌍을 찾을 수 있는 경우 공통 3D 점 x의 투영인 경우여야 한다. 영상 포인트에 의해 생성되는 라인 세트는 x(3D 포인트)에서 교차해야 하며, x(3D 포인트) 좌표의 대수적 공식은 아래와 같이 다양한 방법으로 계산할 수 있다.

그러나 실제로는 영상 지점의 좌표를 임의의 정확도로 측정할 수 없다. 대신 렌즈 왜곡으로 인한 기하학적 노이즈나 관심 지점 감지 오류 등 다양한 유형의 노이즈가 측정된 영상 좌표에 부정확한 결과를 초래한다. 따라서 해당 영상 포인트에 의해 생성된 선이 항상 3D 공간에서 교차하는 것은 아니다. 그렇다면 문제는 측정된 영상 포인트에 최적으로 맞는 3D 포인트를 찾는 것이다. 문헌에는 최적성을 정의하는 방법과 최적의 3D 포인트를 찾는 방법에 대한 여러 제안이 있다. 그것들은 서로 다른 최적성 기준에 기초하기 때문에, 다양한 방법들은 노이즈가 관련되었을 때 3D 지점 x의 다른 추정치를 산출한다.

소개

다음에서는 핀홀 카메라에 의해 생성된 두 개의 뷰에서 해당 영상 포인트에 삼각 측정이 이루어진다고 가정한다. 이러한 가정에 의한 일반화는 여기에서 논의된다.

왼쪽의 이미지는 핀홀 모델의 스테레오 카메라 한 쌍의 후각 기하학을 보여준다. A point x (3D point) in 3D space is projected onto the respective image plane along a line (green) which goes through the camera's focal point, ${\displaystyle \mathbf {O} _{1}}$ and ${\displaystyle \mathbf {O} _{2}}$, resulting in the two corresponding image points ${\displaystyle \mathbf {y} _{1}}$$$ 및 $y{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ ${\displaystyle {\mathrm{}}_{}}$ 1 ${\$및$$ ${\displaystyle {\mathrm{}}_{}}$ $2{\displaystyle {\mathbf{}}_{}}$ ${\$y$} _{2}}:$ 2개의 투영선(녹색 선)이 주어지고$$ 두 점 x(3D 지점에서 교차하는 경우여야 한다. 교차점이 직설적으로 결정될 수 있는 기본적인 선형대수를 사용한다.

오른쪽의 이미지는 실제 사례를 보여준다. 영상 지점 $y{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$} 및$$ ${\displaystyle {\mathrm{}}_{}}$ 2 ${\$}}의 위치는 정확하게 측정할 수 없다$$. 그 이유는 다음과 같은 요인들이 복합적으로 작용하기 때문이다.

• 기하학적 왜곡(예: 렌즈 왜곡)은 카메라의 3D에서 2D 매핑이 핀홀 카메라 모델에서 벗어나는 것을 의미한다. 이러한 오류는 어느 정도 보상될 수 있으며, 잔류 기하학적 오류를 남긴다.
• x(3D 포인트)에서 나오는 한 줄기 광선이 포인트 스프레드 기능에 따라 카메라의 렌즈 시스템에 분산된다. 영상에서 분산된 강도 함수의 측정에서 해당 영상 지점을 복구하면 오류가 발생한다.
• 디지털 카메라에서 영상 명암 기능은 이산 센서 요소에서만 측정된다. 실제 강도 함수를 복구하려면 이산 강도 함수의 부정확한 보간법을 사용해야 한다.
• 삼각 측정에 사용되는 영상 지점 y와₁^' y₂'는 일반적으로 코너나 관심 지점과 같이 다양한 유형의 형상 추출기를 사용하여 발견되는 경우가 많다. 근린 작동을 기반으로 하는 모든 유형의 피쳐 추출에 대한 지역화 오류가 있다.

As a consequence, the measured image points are ${\displaystyle \mathbf {y} '_{1}}$ and ${\displaystyle \mathbf {y} '_{2}}$ instead of ${\displaystyle \mathbf {y} _{1}}$ and ${\displaystyle \mathbf {y} _{2}}$. However, their projection lines (blue) do not have to intersect in 3D s${\displaystyle {\mathrm{}}_{}^{}}$ 이 선들은 y 1 ${\displaystyle {}_{}^{}}$ ${\$${1$}, y $\$ {\$displaystyle \mathbf$ {$y} '_2}}:$ 기본 행렬에 의해 정의된 후행 구속조건을 만족하는$$ 경우에만 교차한다. $y{\displaystyle {\mathbf{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$및 y$$ ${\displaystyle {}_{}^{}}$ ${\$의 측정 노이즈를 고려할 때 경구 구속조건이 충족되지 않고 투영선이 교차하지 않을 가능성이 높다$$.

이 관찰은 삼각측량으로 해결되는 문제로 이어진다. $어느{\displaystyle {\mathbf{}}_{}^{}}$ 3D 지점 x가_est y ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$}:{1} 및 $y$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ 카메라의$$ 기하학적 구조를 가장 잘 추정하는가? x에_est 의존하는 오류 측정을 정의한 다음 이 오류를 최소화하면 답이 나오는 경우가 많다. 다음 절에서는 문헌에 제시된 x를_est 계산하는 여러 가지 방법을 간략히 설명한다.

All triangulation methods produce x_est = x in the case that ${\displaystyle \mathbf {y} _{1}=\mathbf {y} '_{1}}$ and ${\displaystyle \mathbf {y} _{2}=\mathbf {y} '_{2}}$, that is, when the epipolar constraint is satisfied (except for singular points, see below). 제약조건이 충족되지 않을 때 발생하는 것으로 방법마다 차이가 있다.

특성.

삼각측량법은 다음과 같은$$ 함수 $\tau {\displaystyle }$ ${\$의 관점에서 설명할 수 있다.

${\displaystyle \mathbf {x} \sim \tau(\mathbf {y} '_1},\mathbf {y} '_2},\mathbf {C}, {2})$

여기서 $y{\displaystyle {\mathbf{}}_{}^{}}$ ${\displaystyle {}_{}^{}{\mathbf{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ y 2$′$ {\$mathbf {y} '_{1$},\mathbf ${y} '_{2}}'$은 탐지된 이미지 포인트의 동종 좌표, $C{\displaystyle {\mathbf{}}_{}}$ 1,${\displaystyle {}_{}{\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$}}은$$ 카메라 행렬이다. x(3D 점)는 결과 3D 점을 균일하게 표현한 것이다. $~{\displaystyle }$ ${\$ 기호는$$ 동종 벡터가 관련되어 있으므로 $since{\displaystyle }$ ${\$은 0이 아닌 스칼라에 의해 x까지 곱하기까지의 벡터만 생성하면 된다는$$ 것을 의미한다.

구체적인 방법, 즉 특정 기능 ${\$을$($를) 살펴보기 전에 설명해야 할 방법과 관련된 몇 가지 일반적인 개념이 있다. 특정 문제에 대해 어떤 삼각측량법을 선택하느냐는 이러한 특성에 어느 정도 좌우된다.

특이점

Some of the methods fail to correctly compute an estimate of x (3D point) if it lies in a certain subset of the 3D space, corresponding to some combination of ${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}$. A point in this subset is then a singularity 삼각 측량법의 실패의 원인은 해결해야 할 일부 방정식 시스템이 충분히 결정되지 않았거나 x의_est 투영적 표현이 단수점에 대한 영점 벡터가 되기 때문일 수 있다.

인비언스

일부 응용 프로그램에서는 3D 점을 나타내기 위해 사용되는 좌표계와는 독립적으로 삼각측량하는 것이 바람직하다. 삼각측량 문제가 한 좌표계로 공식화되었다가 다른 좌표계로 변환되는 경우 결과 추정치_est x도 동일한 방식으로 변환해야 한다. 이 속성은 흔히 불변이라고 한다. 모든 삼각측량 방법이 불변성을 보장하는 것은 아니며, 적어도 일반 좌표 변환 유형에 대해서는 그렇지 않다.

$3D{\displaystyle \mathrm{}}$ 좌표를 균일하게 나타내는 경우, 가장 일반적인 변환은 4${\displaystyle }$× ${\displaystyle 4}${\$displaystyle$ 4$\times$4} $행렬$ T ${\$로 대표되는 투영적 변환이다$.$ 동질 좌표가 다음과 같이 변환되는 경우

${\displaystyle \mathbf {\bar {x} \sim \mathbf {T} \,\mathbf {x} }$

그러면 카메라 매트릭스가 (C_k)로 변환되어야 한다.

${\displaystyle \mathbf {\bar {C} _{k}\심 \mathbf {C} _{k}\mathbf {T}^{-1}$

동일한 균일한 영상 좌표(y_k)를 생성하려면

${\displaystyle \mathbf {y} _{k}\sim \mathbf {\bar}\{k}\mathbf {x}\mathbf {c} = {k}\mathbf {x}}}}$

$삼각{\displaystyle }$ 함수 ▼ ${\displaystyle \tau }$이(가) $T{\displaystyle \mathbf{}}$ ${\$에 대해 불변인 경우 다음$$ 관계가 유효해야 함

${\displaystyle \mathbf {\bar {x} _{\\rm {est}\심 \mathbf {T} \mathbf {x} _{\rm {est}}}}}$

그 다음부터.

${\displaystyle \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{$$-1},\mathbf {C} _{2}\,\mathbf {T} ^-1}),$ 모든$$ $y{\displaystyle {\mathbf{}}_{}^{}}$ ${\displaystyle {}_{}^{}\prime ,}$ ${\displaystyle {\mathbf{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$

각 삼각측량법에 대해 이 마지막 관계가 유효한지 판단할 수 있다. 만일 그렇다면, 강성 변환이나 부착형 변환과 같은 투영적 변환의 일부에 대해서만 만족될 수 있다.

계산 복잡성

함수 $\tau {\displaystyle }$ ${\displaystyle \tau }$은(는) 실제로는 비교적 복잡할 수 있는 연산을 추상적으로 표현한 것에 불과하다$$. 어떤 방법은 폐쇄형 연속 함수인 $\tau$ ${\displaystyle \tau }$을(를) 생성하는 반면, 다른 방법은 SVD나 다항식의 뿌리를 찾는 일련의 계산 단계로 분해해야 한다. 그러나 또 다른 종류의 방법으로는 일부 파라미터의 반복적인 추정에 의존해야 $하는$ $\$ {\$displaystyle \tau$}이(가) 있다. 이는 계산 시간과 관련된 운영의 복잡성 모두 다른 방법들 사이에 다를 수 있다는 것을 의미한다.

방법들

중간점법

Each of the two image points ${\displaystyle \mathbf {y} '_{1}}$ and ${\displaystyle \mathbf {y} '_{2}}$ has a corresponding projection line (blue in the right image above), here denoted as ${\displaystyle \mathbf {L} '_{1}}$ and ${\displaystyle \mathbf {L} '_{2}}$, which can be determined given the camera matrices ${\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}$. Let ${\displaystyle d\,}$ be a distance function between a (3D line) L and a x (3D point) such that ${\displaystyle d(\mathbf {L} ,\mathbf {x} )}$ is the Euclidean distance between ${\disp$$laystyle \mathbf$ {$L$$}$$$및 x {\$displaystyle \mathbf {x$ 중간점 방법은 최소화된 점 x를 찾는다_est.

${\displaystyle d(\mathbf {L} '_1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}}$

x는_est 두 투영선을 연결하는 최단선 세그먼트의 중간에 정확히 놓여 있는 것으로 밝혀졌다.

직접 선형 변환

필수 매트릭스를 통해

The problem to be solved there is how to compute ${\displaystyle (x_{1},x_{2},x_{3})}$ given corresponding normalized image coordinates ${\displaystyle (y_{1},y_{2})}$ and ${\displaystyle (y'_{1},y'_{2})}$. If the essential matrix is known and the corresponting 회전과 번역 변환이 결정되었는데, 이 알고리즘(Longuet-Higgins' 논문에 설명되어 있음)은 해결책을 제공한다.

$r{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$은(는) 회전 행렬 $R{\displaystyle \mathbf{}}$ ${\$의 행 k를 나타냄$$$:$

${\displaystyle \mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\-\mathbf {r} _{3}-\mathbf {r} _{pmatrix}}}}$

두 좌표계의 3D 좌표와 앞에서 설명한 3D와 2D 지점 사이의 매핑 사이의 위의 관계를 결합하면 다음과 같은 효과를 얻을 수 있다.

${\displaystyle y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}}$

또는

${\displaystyle x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

$x{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$가 결정되면$$ 나머지 두 좌표는 다음과 같이 계산할 수 있다.

${\displaystyle {\pmatrix}x_{1}\x_{2}\end{pmatrix}=x_{3}{\nd{pmatrix}{\nd{pmatrix}}}}$

위의 파생은 독특하지 않다. $또한{\displaystyle {}_{}^{}}$ y ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\$2}}의 표현으로 시작하여$$ 다음에 따라$$ $x{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$에 대한 표현을 도출할 수도 있다.

${\displaystyle x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

이상적인 경우, 카메라가 완벽한 핀홀 카메라에 따라 3D 포인트를 매핑하고 결과 2D 포인트를 잡음 없이 감지할 수 있는 경우, $x{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\$에 대한 두 식이 동일하다$$. 그러나 실제로는 그렇지 않으며, 예를 들어, 어떤 종류의 평균으로 볼 때$$$x{\displaystyle {}_{}}$ ${\$의 두 추정치를 결합하는 것이 유리할 수 있다.

또한 가능한 위의 계산의 다른 유형의 확장도 있다. 이들은 프라이밍된 영상 좌표와 프라이밍되지 않은 시스템에서 3D 좌표를 도출하는 것으로 시작했다. 또한 프라이밍되지 않은 영상 좌표에서 시작하여 프라이밍된 3D 좌표를 얻을 수 있으며, 최종적으로 프라이밍되지 않은 3D 좌표로 변환할 수 있다. 다시 말하지만 이상적인 경우 결과는 위의 표현과 같아야 하지만, 실제로 그들은 편차를 보일 수 있다.

최종적인 언급은 3D 포인트가 이러한 방식으로 결정되는 경우가 많은 해당 영상 좌표에서 필수 매트릭스가 결정된다면 번역 $벡터{\displaystyle \mathbf{}}$ t ${\$은(는) 알 수 없는 양의 스케일까지만 알려져$$ 있다. 따라서 재구성된 3D 지점도 양의 스케일링과 관련하여 결정되지 않는다.

최적 삼각측량

참고 항목

• 번들 조정
• 선-선 교차점

참조

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3.

외부 링크

• Matlab에서 두 개의 뷰 및 다중 뷰 삼각 측량