그래프($G = (V,E)$)는 정점(vertices, $V$)과 정점 사이의 연결인 간선(edges, $E$)으로 구성된 자료구조로, 다양한 문제를 모델링하는 데 사용됨. Undirected Graph: 간선이 방향을 가지지 않음 Directed Graph: 간선이 방향을 가짐 Weighted Graph: 간선에 가중치가 있음 Unw...

Searching Ordered Arrays 정렬되지 않은 배열에서는 특정 원소를 찾기 위해 배열의 모든 원소를 비교하는 선형 탐색(Linear Search)이 최선. 하지만 정렬된 배열에서는 다양한 탐색 알고리즘을 사용할 수 있다. Binary Search Binary Search는 배열을 반으로 나누어 원하는 원소가 있는지 확인하는 방식으로 작동...

Sorting 데이터를 순서대로 정렬하는 작업으로, 그 비용은 비교 횟수(Number of Comparisons)와 교환 횟수(Number of Swaps)로 측정된다. Exchange Sorting Exchange Sort은 원소 쌍의 위치를 교환(swap)하여 배열을 정렬하는 방식의 알고리즘이다. Exchange Sort은 inversio...

Non-Binary Trees Non-Binary Trees는 각 노드가 두 개 이상의 자식을 가질 수 있는 트리 구조 ADT interface GTNode<E>{ public E value(); public boolean isLeaf(); public GTNode<E> parent(); public...

Incremental Structure from Motion (SfM) Incremental Structure from Motion (SfM)은 카메라의 위치와 3D 구조를 동시에 추정하는 방법으로, 주로 이미지 시퀀스에서 카메라의 움직임과 3D 포인트 클라우드를 생성하는 데 사용됨. 직교 카메라 가정을 하지 않음(Affine 카메라 모델이 아님...

Stereo Matching Stereo Matching은 두 개의 서로 다른 시점에서 촬영된 이미지(스테레오 이미지)를 이용하여 3D 정보를 추정하는 과정이다. Stereo Matching의 목표는 두 이미지에서 동일한 물체의 대응점을 찾아서 깊이 정보를 추정하는 것이다. 위 이미지와 같이 두 이미지의 대응점을 찾아 두 대응점 사이의 거...

Two-View Geometry(Epipolar Geometry) Epipolar Geometry는 두 개의 카메라 뷰 간의 기하학적 관계를 설명하는 것으로, 두 카메라가 서로 다른 위치에서 동일한 장면을 촬영할 때 발생하는 기하학적 제약을 나타냄. 3D 공간에서의 점 $X$이 카메라 $C$와 $C’$에서 각각의 이미지 평면에 투영...

Perspective-n-Point (PnP) Perspective-n-Point (PnP) 문제는 카메라의 위치와 방향을 추정하는 문제로, 주어진 3D 점들과 그에 대응하는 2D 이미지 점들을 이용하여 카메라의 외부 파라미터(회전과 이동)를 추정하는 것을 목표로 함. 이 문제에선 3D-2D correspondences가 주어지고, 카메라 ...

Camera Calibration 카메라 보정(Camera Calibration)은 카메라의 내부 및 외부 파라미터를 추정하는 과정, 즉 Camera Matix $P$의 파라미터 $K, R, t$를 추정하는 과정 DLT (Direct Linear Transform) 만약 어떤 물체의 3D 좌표 $\mathbf{X} = (X, Y, Z)$가 이미지 평...

Camera Model 카메라 모델은 3D 세계를 2D 이미지로 변환하는 과정을 설명하는 모델 위 이미지는 Camera Obscura로, 빛이 작은 구멍(pinhole)을 통해 들어와서 반대편 벽에 이미지가 투사되는 원리를 이용한 초기 카메라 모델 Pihole로부터 상이 맺히는 지점까지의 거리를 focal length라고 하고,...