#2. 스테레오 카메라 원리 분석(2) : 스테레오 정합

 

스테레오 정합(Stereo matching)

아래 블로그를 참조하였습니다.

스테레오 정합(Stereo matching)

Ⅰ. 스테레오 정합이란?

 💡 최종 목표: 스테레오 비전을 설명할 때 나온 '시차(disparity)'를 계산하는 과정

 

스테레오 정합은 기준 영상에서의 한 점에 대한 동일한 점을 목표 영상에서 찾는 과정입니다.

 

목표 영상은 기준 영상의 반대 영상으로, 아래 그림을 통해 기준 영상을 이해해 봅시다. 기준 영상은 좌측 영상이 될 수도 있고, 우측 영상이 될 수도 있습니다.

스테레오 정합

먼저 좌측 영상을 기준 영상으로, 좌/우 영상에서 동일하게 나타나는 한 점(빨간 지붕의 꼭짓점)을 생각해 볼 때, 아래 그림처럼 좌측 영상에서의 한 점을 기준으로 우측 영상의 동일한 점은 좌측 영상에서의 점보다 좌측에 위치합니다.

 

우측 영상을 기준 영상으로 생각하다면 좌측 영상에서의 동일한 점은 우측 영상에서의 점보다 우측에 위치합니다.

 

이때의 x축의 위치 차이를 시차(disparity)라고 말합니다. 계산된 시차 값들을 이미로 표현하면 아래 그림처럼 흑백영상으로 표현가능한데, 이것을 시차 영상(disparity image)혹은 깊이 영상(depth map)이라고 말합니다.

 

시차가 계산되어 나오는 영역만 다를 뿐 시차 값은 동일하며, 깊이 영상은 흑백 영상으로 표현되는데, 흑백 영상에도 어두움과 밝음이 존재하는 것을 아래의 그림에서도 육안으로 확인 가능합니다. 즉 어두움과 밝은의 차이는 실제 3차원적인 거리가 멀고 가까움을 의미하고 있습니다.

💡 시차의 값이 클수록 가까우며(밝으며), 시차의 값이 작을수록 멀다(어둡다).

스테레오 정합의 기본 개념

스테레오 정합은 스테레오 비전 시스템에서 가장 중요한 과정 중 하나로, 두 개의 서로 다른 시점(카메라)에서 얻은 이미지를 비교하여 동일한 물체의 대응점을 찾는 과정입니다. 이러한 대응점을 찾음으로써 각 지점의 깊이 정보를 추정할 수 있습니다.

 

1. 좌/우 이미지

• 스테레오 비전 시스템은 일반적으로 두 개의 카메라를 사용하여 동일한 장면을 촬영합니다.

• 이때 얻어진 두 이미지가 "좌 이미지"와 "우 이미지"입니다.

 

2. 디스패리티 (Disparity)

• 스테레오 정합의 주요 목표는 두 이미지에서 동일한 물체의 점이 서로 어디에 위치하는지를 찾는 것입니다.

• 이 두 점 간의 좌표 차이를 디스패리티라고 합니다. 디스패리티는 깊이(거리) 정보를 얻는 데 사용됩니다.

• 디스패리티가 크면 물체가 더 가깝고, 작으면 물체가 더 멀리 있다는 것을 의미합니다

 

3. 정합 알고리즘

• 스테레오 정합을 수행하는 다양한 알고리즘이 있습니다. 이들은 주로 두 가지 방식으로 나뉩니다:

지역적 정합 (Local Matching)	이미지의 작은 영역(패치)을 기준으로 대응점을 찾습니다. 이 방법은 비교적 계산 속도가 빠르지만, 간혹 정확도가 떨어질 수 있습니다.
전역적 정합 (Global Matching)	이미지 전체의 에너지 함수(혹은 비용 함수)를 최소화하는 방식으로 대응점을 찾습니다. 정확도가 높지만 계산 비용이 큽니다.

Ⅱ. 스테레오 정합 방법

1. 전역 정합(global matching) 방법

💡 이미지 전체의 에너지 함수(혹은 비용 함수)를 최소화하는 방식으로 대응점을 찾는 방법.
정확도가 높지만 계산 비용이 큽니다.

 

에너지 함수(energy function)을 기반으로 깊이 영상을 추출하는 방식을 사용합니다.

 

• 에너지 함수를 최소화하는 경우를 찾음으로써 최적의 깊이 영상을 만들어 낸다.

• 영상이 가장 매끄러운, stereo vision의 제약 조건 중 하나인 smoothness를 충족하는 경우를 찾는다.

 

영상의 일정 부분이 아니라 영상의 전체적인 정보를 사용하고 알고리즘이 복잡하다는 단점이 존재하지만, 매우 정확한 깊이 영상을 추출 가능합니다.

종류: Belief propagation, dynamic programming, semi-global matching, graph-cut 등

 

일반적으로 Semi-global matching이 주로 사용됩니다.

• 하드웨어 설계자 관점에서의 전역 정합 방법
  • 하드웨어로 구현 시에는 영상의 전체적인 정보를 사용하거나 ( 영상 크기 * 시차 탐색 범위 ) 만큼의 3차원의 정합 비용 매트릭스가 필요하기 때문에 메모리 측면에서 많이 문제가 되어, 메모리는 밖에 두는 off-chip 형태로 구현 알고리즘이 복잡하여 하드웨어로 구현하는 것 또한 어려움.

전역적 방법은 이미지 전체 또는 큰 영역에 대해 정합을 수행하며, 에너지 함수 또는 비용 함수의 최적화를 통해 전체적으로 일관된 정합 결과를 얻고자 합니다. 이러한 방법은 계산이 복잡하지만, 보다 높은 품질의 정합을 제공합니다.

2.1.1 동적 프로그래밍 (Dynamic Programming)

• 기본 개념: 에너지 함수의 최소화를 통해 최적의 디스패리티 맵을 찾습니다.
• 방법: 에너지 함수는 일반적으로 정합 비용과 부드러움 제약(smoothness constraint)을 포함합니다. 동적 프로그래밍을 사용해 최적의 정합을 구합니다.
• 장점: 계산의 복잡성을 줄이면서도 전역적 최적화를 수행할 수 있습니다.
• 단점: 상하 방향의 연속성이 고려되지 않는 경우가 많습니다.

2.1.2 그래프 컷 (Graph Cuts)

• 기본 개념: 이미지의 정합 문제를 그래프 최적화 문제로 변환하여, 에너지 함수의 전역 최적화를 수행합니다.
• 방법: 그래프의 각 노드는 픽셀을, 엣지는 픽셀 간의 상호작용을 나타내며, 그래프 컷 알고리즘을 통해 최소 비용 컷(min-cut)을 구합니다.
• 장점: 전역적 최적화가 가능하며, 에너지 함수의 정의에 따라 매우 정확한 결과를 얻을 수 있습니다.
• 단점: 계산 비용이 높아 실시간 애플리케이션에는 부적합할 수 있습니다.

2.1.3 벨리프 프로파게이션 (Belief Propagation)

• 기본 개념: 정합 문제를 확률적 모델로 표현하고, 픽셀 간의 상호작용을 고려하여 확률 정보를 전파하는 방식으로 최적의 디스패리티 맵을 찾습니다.
• 방법: 마르코프 랜덤 필드(Markov Random Field, MRF) 모델을 사용해 이웃 픽셀 간의 관계를 설정하고, 이를 바탕으로 최적화를 수행합니다.
• 장점: 복잡한 장면에서도 좋은 정합 결과를 제공할 수 있습니다.
• 단점: 그래프 컷과 마찬가지로 계산 비용이 높습니다.

2. 지역 정합(local matching) 방법

💡 이미지의 작은 영역(패치)을 기준으로 대응점을 찾습니다.
이 방법은 비교적 계산 속도가 빠르지만, 간혹 정확도가 떨어질 수 있습니다.

 

지역 정합 방법은 특징 기반(feature-based) 정합 방법과 영역 기반(area-based) 정합 방법으로 나뉩니다.

특징 기반 정합	특징점을 기반으로 정합점(matching point)을 찾으며, 최근에는 사용하지 않습니다.
영역 기반 정합	일정 영역(=윈도우, window)의 픽셀 정보들을 이용하여 정합점을 찾습니다.

 

일정 크기의 윈도우 내 픽셀 정보들만을 사용하여 정합점을 찾기 때문에 전역 정합 방법에 비해 상대적으로 부정확한 깊이 영상을 출력하지만, 전역 정합 방법에 비해 알고리즘이 단순하고 빠르게 계산이 가능합니다.

 

• 전역 정합 방법의 초기 정합 비용(initial matching cost / matching cost cube)을 계산하는 데 사용합니다.

• 정합 방법을 통해 정합 비용의 계산 과정을 거친 후, 추가적인 전역 정합 방법들 마다 다른 개념들을 적용하여 에너지 함수를 최소화한다는 것을 말합니다.

종류: SAD(Sum of absolute difference), SSD(Sum of squared difference), NCC(normalized cross correlation), Census transform, Rank transform 등

 

하드웨어 설계자 관점에서의 지역 정합 방법하지만 상대적으로 낮은 정확도를 가지기 때문에, 다양한 후처리(post-processing) 알고리즘을 사용하여 정확도를 높이거나 종합(aggregation) 방법을 통해 정확도를 높이기도 합니다.

• 후처리 알고리즘: Left-right consistency check(*대표적으로 많이 씀), confidence check, median filter, weighted median filter(*대표적으로 많이 씀), propagation 등
• 종합 방법: Adaptive support weight, cross-based adaptive support weight 등

하드웨어로 구현 시에는 일정 크기의 픽셀 정보만들 가지고 있으면 되기 때문에 전역 정합 방법에 비해 메모리를 적게 들뿐더러, 연산 자체가 단순하여 하드웨어에 설계하기에도 적합하다는 측면이 있습니다.

 

지역적 방법은 픽셀 또는 작은 영역(패치)의 대응점을 찾는 방식으로, 계산이 비교적 간단하고 빠르지만, 정합의 품질이 이미지의 특정 특성(예: 텍스처, 조명 변화)에 의해 영향을 받을 수 있습니다.

2.2.1 윈도우 기반 정합 (Window-Based Matching)

• 기본 개념: 특정 픽셀의 주변 영역(윈도)에서 대응점을 찾습니다.
• 비용 함수: 윈도우 내 픽셀 값의 차이를 계산하여 정합 비용을 구합니다. 대표적인 비용 함수는 절대 차이 합 (Sum of Absolute Differences, SAD), 제곱 차이 합 (Sum of Squared Differences, SSD), 상관 계수 (Normalized Cross-Correlation, NCC) 등이 있습니다.
• 장점: 계산 속도가 빠르고 구현이 간단합니다.
• 단점: 텍스처가 부족한 영역이나 명확한 에지가 없는 영역에서는 오차가 발생할 수 있습니다.

2.2.2 특성점 기반 정합 (Feature-Based Matching)

• 기본 개념: 이미지에서 코너, 에지, 블롭 등의 특성점을 추출한 후, 이들 특성점 간의 대응을 찾습니다.
• 방법: SURF, SIFT와 같은 특성점 검출 알고리즘을 사용하여, 이들 간의 유사도를 계산합니다.
• 장점: 명확한 특징이 있는 이미지에서 높은 정확도를 가집니다.
• 단점: 텍스처가 부족하거나 특징이 뚜렷하지 않은 영역에서는 적용이 어렵습니다.

3. 스테레오 정합의 후처리

정합 과정 이후에는 결과의 품질을 향상하기 위해 여러 후처리 작업이 수행될 수 있습니다. 대표적인 후처리 방법은 다음과 같습니다:

• 중간 필터링 (Median Filtering): 노이즈를 제거하고, 정합 결과의 스무딩을 위해 사용됩니다.
• 홀 필링 (Hole Filling): 정합이 되지 않은 영역(홀)을 주변 정보로 채우는 작업입니다.
• 양방향 필터링 (Bilateral Filtering): 경계선이 잘 유지되도록 하는 스무딩 필터로, 경계 근처의 디스패리티를 유지하면서 노이즈를 제거하는 데 효과적입니다.

4. 최신 기법

최근에는 인공지능과 딥러닝을 이용한 스테레오 정합 기법도 많이 사용되고 있습니다. 신경망 기반의 정합 알고리즘은 대규모 데이터셋으로 학습되어 기존의 전통적인 방법보다 더 정밀한 디스패리티 맵을 생성할 수 있습니다.

 

•CNN 기반 정합: CNN를 사용하여 이미지의 각 픽셀의 특성을 학습하고, 이를 바탕으로 대응점을 찾습니다.

• 엔드 투 엔드 학습: 정합 과정 전체를 하나의 네트워크로 학습시키는 방식으로, 깊이 추정의 정확도와 속도를 크게 향상할 수 있습니다.

 

이와 같이, 스테레오 정합에는 다양한 방법이 있으며, 각각의 방법은 특정 상황에서 유리하게 사용될 수 있습니다. 방법의 선택은 이미지의 특성과 적용 목표에 따라 달라질 수 있습니다.

Ⅲ. ⭐️지역 정합 방법을 통한 시차 계산 방법 ⭐️

지역 정합 방법은 위에서 말했듯이, 윈도우(window)를 기반으로 시차 탐색 범위(disparity search range) 내의 픽셀들에 대해 정합 비용(matching cost)을 계산한 후, 시차를 계산합니다.

 

이제부터 정합 비용, 시차 탐색 범위, 윈도우의간단한 정의는 아래와 같습니다.

※ 정합 비용(matching cost): 윈도우들간의 비유사도(similarity)의 값
※ 시차 탐색 범위(disparity search range): 시차 값의 최대 범위 또는 정합점을 찾는 최대 범위
※ 윈도우: 커널(kernel)

 

1. 기준 영상(left image)의 한 점과 목표 영상(right image)의 시차 탐색 범위 내 모든 픽셀에 윈도우를 설정합니다.

2. 좌측에 설정된 윈도우와 우측에 시차 탐색 범위만큼 설정된 윈도우들간의 정합 비용(비유사도)을 추정합니다. 이때 비유사도를 측정하는 방법은 SAD, SSD, NCC, Census transform, Rank 무엇을 사용하느냐에 따라 다릅니다.

3.계산된 정합 비용들은 아래의 그림에서 그래프 처럼 나타낼 수 있으며, ( x축은 시차 탐색 범위 내 시차 값들, y축은 정합 비용 )가장 작은 정합 비용을 가지는 시차를 선택합니다.

4.가장 작은 정합 비용을 선택하는 방법을 'winner-takes-all' 이라함)아래의 그림에서는 'a'라는 시차를 출력함

 

(x, y)와 (x-a, y)의 x축 차이가 'a' → 이전 쳅터의 'x축 위치' 차이가 'a'

 

참고로 지금은 동일 y축상에서만 정합점을 찾는데, 실질적으로는 스테레오 카메라로부터 들어오는 스테레오 영상들은 y축이 일치하지 않습니다. y축이 다를 때는 렉티피케이션(rectification)이라는 과정을 통해서 좌/우 영상의 y축을 일치시킵니다.

 

지역 정합 방법(Local Matching)은 스테레오 비전에서 특정 픽셀 주변의 작은 영역(윈도)을 기준으로 대응점을 찾는 방식입니다. 이 방법을 통해 시차(disparity)를 계산하는 과정은 비교적 간단하며, 실시간 애플리케이션에 적합합니다. 여기서는 지역 정합 방법을 사용하여 시차를 계산하는 일반적인 과정을 설명하겠습니다.

1. 시차 계산의 단계

1.1 윈도우 선택

• 윈도우 크기: 각 픽셀 주변에 사각형 또는 정사각형 형태의 윈도우(블록)를 설정합니다. 윈도우 크기는 일반적으로 3x3, 5x5, 7x7 등 홀수 크기로 설정됩니다.
• 윈도우 중심: 좌측 이미지의 특정 픽셀을 중심으로 윈도우를 설정합니다.

1.2 비용 함수 계산

• 비용 함수: 윈도우의 유사성을 측정하기 위해 비용 함수를 사용합니다. 대표적인 비용 함수는 다음과 같습니다:
  • 절대 차이 합 (Sum of Absolute Differences, SAD): 두 윈도우 내의 픽셀 값의 절대 차이를 합산합니다. 여기서 IL과 IR은 좌우 이미지의 픽셀 값이며, d는 테스트 중인 시차입니다.
  • 제곱 차이 합 (Sum of Squared Differences, SSD): 절대 차이 대신 제곱 차이를 사용하여 계산합니다.
  • 상관 계수 (Normalized Cross-Correlation, NCC): 두 윈도우 간의 상관관계를 계산하여 유사도를 측정합니다. 이 방법은 조명 변화에 비교적 강건합니다.

1.3 시차 계산

• 최소 비용 탐색: 좌측 이미지의 특정 픽셀에 대해, 우측 이미지에서 일정한 검색 범위 내에서 다양한 시차 d를 적용하여 윈도우 간의 비용을 계산합니다.
• 최소 비용 결정: 최종적으로, 계산된 비용 중 최소 비용을 가지는 시차 d를 선택합니다. 이 시차가 해당 픽셀의 최적 시차로 간주됩니다.
• 디스패리티 맵 구성: 모든 픽셀에 대해 시차를 계산하면, 이 정보를 모아 디스패리티 맵을 생성 합니다. 이 맵은 각 픽셀에 대해 계산된 시차 값을 포함하고 있으며, 이를 통해 장면의 깊이 정보를 얻을 수 있습니다.

2. 시차 계산의 특성 및 과제

2.1 텍스처가 부족한 영역

• 텍스처가 없는 평평한 영역에서는 서로 다른 시차에 대해서도 유사한 비용 값이 나올 수 있습니다. 이로 인해 잘못된 시차가 선택될 가능성이 있습니다.

2.2 윈도우 크기의 선택

• 작은 윈도우는 높은 공간 해상도를 제공하지만, 노이즈에 민감할 수 있습니다. 반면, 큰 윈도우는 노이즈에 강하지만, 경계에서 정확도가 떨어질 수 있습니다. 따라서 윈도우 크기의 선택이 중요한 요소입니다.

2.3 후처리

• 중간 필터링(Median Filtering): 디스패리티 맵에서 노이즈를 줄이기 위해 사용할 수 있습니다.
• 홀 필링(Hole Filling): 계산되지 않은 영역을 주변의 시차 값을 기반으로 채우는 과정이 필요할 수 있습니다.

💡 참고할만한 문헌

논문 - A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms (★ 이 논문은 매우 저명함) 논문 - Review of stereo vision algorithms from software to hardware 칼럼 - 2015년 1월 IDEC Newsletter

여기에서 사용된 영상은 middleburry 데이터 셋중에서도 'teddy'영상을 사용

http://vision.middlebury.edu/stereo/

vision.middlebury.edu/stereo

 

vision.middlebury.edu/stereovision.middlebury.edu

vision.middlebury.edu/stereo