# 블록 매칭 알고리즘 스테레오 비전에서 중요한 단계 중 하나는 두 개의 이미지 사이에서 동일한 물체의 점을 찾아내는 작업이다. 이 작업을 스테레오 정합이라고 하며, 이를 구현하는 다양한 알고리즘 중에서 블록 매칭 알고리즘(Block Matching Algorithm)은 가장 기본적인 방법 중 하나이다. 블록 매칭 알고리즘은 하나의 이미지에서 작은 영역(블록)을 다른 이미지에서 대응되는 영역과 비교하여 일치하는 블록을 찾는다. 이를 통해 각 점의 깊이 정보를 유추할 수 있다. #### 1. 기본 개념 블록 매칭 알고리즘은 일반적으로 다음의 절차를 따른다: 1. **기준 이미지**에서 특정 위치의 픽셀을 중심으로 작은 크기의 블록을 설정한다. 이 블록은 $\mathbf{B}\_1$로 표현할 수 있다. 2. **대응 이미지**에서 동일한 크기의 블록 $\mathbf{B}\_2$를 찾는다. 이때, 블록 $\mathbf{B}\_2$는 기준 이미지의 블록 $\mathbf{B}\_1$과 가장 유사한 블록이어야 한다. 3. 블록 간의 유사성을 계산하는 방식으로는 **절대 차이의 합(SAD, Sum of Absolute Differences)**, **제곱 차이의 합(SSD, Sum of Squared Differences)** 등이 사용된다. #### 2. 매칭 비용 계산 블록 매칭에서 매칭 비용은 두 이미지의 블록 간 차이를 측정하여 계산한다. 이를 위해 일반적으로 SAD 또는 SSD를 사용한다. **2.1 절대 차이의 합 (SAD)** SAD는 기준 이미지의 블록 $\mathbf{B}\_1$과 대응 이미지의 블록 $\mathbf{B}\_2$ 간의 각 픽셀 값의 차이를 절대값으로 계산한 뒤 합산한 것이다. 수식으로는 다음과 같이 표현된다: $$ \text{SAD} = \sum\_{i=1}^{N} \sum\_{j=1}^{M} \left| I\_1(i,j) - I\_2(i + d\_x, j + d\_y) \right| $$ 여기서: * $N$과 $M$은 블록의 가로와 세로 크기이다. * $I\_1(i,j)$는 기준 이미지에서 블록 $\mathbf{B}\_1$의 픽셀 값이다. * $I\_2(i + d\_x, j + d\_y)$는 대응 이미지에서 블록 $\mathbf{B}\_2$의 픽셀 값이며, $d\_x$와 $d\_y$는 블록의 이동량을 나타낸다. SAD 값을 최소화하는 $d\_x, d\_y$ 조합이 가장 유사한 블록을 찾은 것으로 간주된다. **2.2 제곱 차이의 합 (SSD)** SSD는 SAD와 유사하지만, 차이의 제곱을 사용하여 더 큰 차이에 대한 가중치를 더 많이 부여한다. 수식은 다음과 같다: $$ \text{SSD} = \sum\_{i=1}^{N} \sum\_{j=1}^{M} \left( I\_1(i,j) - I\_2(i + d\_x, j + d\_y) \right)^2 $$ SSD는 큰 차이에 더 민감하게 반응하기 때문에 노이즈에 더 강할 수 있지만, 작은 차이에서 큰 변동이 발생할 수 있다. #### 3. 탐색 공간 블록 매칭에서 블록의 이동량 $d\_x$와 $d\_y$는 정합을 수행할 때 탐색해야 하는 범위를 결정한다. 일반적으로 스테레오 비전에서는 **수평선상**에서만 움직임을 고려하기 때문에 $d\_y = 0$인 경우가 많다. 즉, 수평 방향으로만 블록을 비교하여 최적의 매칭을 찾는다. 따라서 수식은 다음과 같이 단순화된다: $$ \text{SAD}(d\_x) = \sum\_{i=1}^{N} \sum\_{j=1}^{M} \left| I\_1(i,j) - I\_2(i + d\_x, j) \right| $$ 블록 매칭의 탐색 공간은 주로 스테레오 카메라의 **기본선**(baseline)에 따라 결정되며, 이는 두 카메라 사이의 거리와 관계가 있다. #### 4. 서브픽셀 정합 블록 매칭 알고리즘은 일반적으로 정수 단위의 픽셀 이동량 $d\_x$로 정합을 계산한다. 그러나 더 높은 정밀도를 위해 서브픽셀 단위의 정합을 수행할 수 있다. 서브픽셀 정합은 정수 픽셀 간의 SAD 또는 SSD 값을 보간(interpolation)하여 서브픽셀 위치에서의 매칭을 계산한다. 서브픽셀 정합을 구현하는 한 가지 방법은 \*\*이차 보간법(quadratic interpolation)\*\*을 사용하는 것이다. 예를 들어, $d\_x$가 정수일 때의 SAD 값을 기준으로 서브픽셀 위치에서의 최적화를 다음과 같이 수행할 수 있다: 1. $d\_x = k$, $d\_x = k+1$, $d\_x = k-1$일 때의 SAD 값을 계산한다. 2. 이차 함수를 이용하여 다음과 같은 형식으로 서브픽셀 위치에서 최소값을 추정한다: $$ d\_{x, \text{sub}} = k - \frac{\text{SAD}(k+1) - \text{SAD}(k-1)}{2 \times (\text{SAD}(k+1) - 2 \times \text{SAD}(k) + \text{SAD}(k-1))} $$ 이를 통해 정수 픽셀 사이의 서브픽셀 위치에서 더 정확한 매칭을 추정할 수 있다. #### 5. 윈도우 크기 선택 블록 매칭에서 중요한 또 다른 요소는 **블록의 크기**이다. 블록의 크기가 작으면 세부적인 정보를 더 잘 반영할 수 있지만, 잡음에 민감할 수 있다. 반면, 큰 블록은 더 많은 정보를 포함하고 잡음에 강하지만 세부적인 변화를 놓칠 수 있다. * 작은 블록 크기: 잡음에 민감하고 잘못된 매칭을 유발할 가능성이 있지만, 세밀한 매칭이 가능함. * 큰 블록 크기: 매칭의 신뢰도가 높아지지만, 물체의 작은 변화를 반영하지 못할 수 있음. 블록 크기는 주어진 장면의 특성에 따라 적절하게 조정해야 한다. #### 6. 비용 함수 최적화 비용 함수의 최적화를 위해 SAD와 SSD 외에도 다른 매칭 비용 함수를 사용할 수 있다. 대표적인 방법으로는 \*\*정규화 상호 상관계수(NCC, Normalized Cross-Correlation)\*\*가 있다. NCC는 두 블록 간의 상관관계를 계산하여 가장 높은 값을 가지는 위치에서 정합을 결정하는 방식이다. NCC는 다음과 같은 수식으로 정의된다: $$ \text{NCC} = \frac{\sum\_{i=1}^{N} \sum\_{j=1}^{M} (I\_1(i,j) - \overline{I\_1}) \cdot (I\_2(i+d\_x,j) - \overline{I\_2})}{\sqrt{\sum\_{i=1}^{N} \sum\_{j=1}^{M} (I\_1(i,j) - \overline{I\_1})^2} \cdot \sqrt{\sum\_{i=1}^{N} \sum\_{j=1}^{M} (I\_2(i+d\_x,j) - \overline{I\_2})^2}} $$ 여기서: * $\overline{I\_1}$은 기준 블록의 평균값, * $\overline{I\_2}$는 대응 블록의 평균값이다. NCC는 두 블록 간의 상관관계를 정규화하여 계산하기 때문에 조명 변화나 대비 차이에 더 강한 성능을 보이다. #### 7. 최적화된 탐색 기법 블록 매칭 알고리즘은 모든 위치에서 매칭을 시도하는 **전역 탐색** 방식을 기본으로 하지만, 이는 매우 비효율적일 수 있다. 이를 개선하기 위한 몇 가지 최적화된 탐색 기법이 있다. **7.1 전방향 검색** 전방향 검색은 탐색 범위를 미리 좁혀서 최적의 매칭을 찾는 방식이다. 예를 들어, 스테레오 정합에서 매칭이 일어나는 수평 방향으로만 탐색을 수행함으로써 계산 비용을 줄일 수 있다. **7.2 계층적 검색** 계층적 검색은 블록 매칭을 큰 블록 크기에서 시작한 후, 점차 작은 블록으로 세밀한 매칭을 수행하는 방식이다. 이를 통해 큰 블록에서 대략적인 위치를 찾고, 작은 블록에서 정밀한 매칭을 수행하여 계산량을 줄이다. #### 8. 다중 해상도 접근 (Pyramid Approach) 블록 매칭의 성능을 개선하기 위한 또 다른 방법으로 \*\*다중 해상도 접근(Pyramid Approach)\*\*이 있다. 이 방법은 이미지의 해상도를 여러 단계로 줄인 후, 낮은 해상도에서 대략적인 매칭을 찾고, 그 결과를 이용하여 고해상도에서 정밀한 매칭을 수행하는 방식이다. 다중 해상도 접근의 절차는 다음과 같다: 1. **이미지 피라미드 구성**: 원본 이미지를 여러 해상도로 축소하여 피라미드를 생성한다. 예를 들어, 각 단계에서 이미지의 크기를 절반으로 줄여 다음 단계의 해상도를 구성한다. 2. **저해상도에서 매칭 수행**: 가장 낮은 해상도의 이미지에서 블록 매칭을 수행한다. 이 단계에서는 전체적인 구조만 반영되므로 빠른 탐색이 가능한다. 3. **고해상도에서 세밀한 매칭 수행**: 저해상도에서 찾은 대략적인 매칭을 기준으로, 고해상도로 올라가면서 더 정밀한 매칭을 수행한다. 각 단계에서의 결과는 다음 단계의 초기값으로 사용된다. 이 방법은 매칭 속도를 높이고, 넓은 탐색 범위에서 발생하는 오류를 줄이는 데 효과적이다. #### 9. 영상 잡음과 블록 매칭 스테레오 매칭에서 영상 잡음은 중요한 문제 중 하나이다. 영상에 잡음이 포함되어 있을 경우, 블록 매칭의 정확도가 크게 저하될 수 있다. 잡음의 영향을 줄이기 위해 블록 매칭 전후로 몇 가지 필터링 기법을 사용할 수 있다. **9.1 사전 필터링** 매칭을 수행하기 전에 이미지에 포함된 잡음을 줄이기 위해 **Gaussian 블러링**이나 **중간값 필터링**과 같은 방법을 사용할 수 있다. 이러한 필터링 방법은 이미지에서 고주파 성분(잡음)을 제거하여 매칭의 신뢰성을 높이는 데 도움이 된다. **9.2 후처리 필터링** 매칭이 완료된 후에도 **정규화 필터**나 **중간값 필터**를 사용하여 이상치(노이즈) 매칭 결과를 제거할 수 있다. 후처리 필터링은 불필요한 점들의 매칭을 제거하여 매칭 결과를 개선하는 데 중요한 역할을 한다. #### 10. 계산 복잡도 블록 매칭 알고리즘의 주요 단점 중 하나는 **계산 복잡도**이다. 모든 픽셀에 대해 가능한 모든 블록을 비교하려면 매우 많은 계산이 필요하며, 이는 실시간 시스템에서는 큰 부담이 된다. 계산 복잡도를 줄이기 위해 블록 매칭 알고리즘을 최적화하는 여러 방법들이 존재한다. * **탐색 범위 제한**: 탐색을 모든 위치에서 수행하는 대신, 예상 가능한 범위에서만 수행하여 계산량을 줄일 수 있다. * **빠른 정합 기법**: 탐색 과정에서 일부 블록은 추가 계산 없이 빠르게 제거할 수 있는 방법을 도입하여 계산 시간을 단축할 수 있다. 예를 들어, **삼각측량 기반의 사전 지식**을 사용하여 정합이 일어날 수 있는 범위를 제한하면 탐색해야 할 공간이 줄어들게 된다. #### 11. 코드 구현 블록 매칭 알고리즘의 기본 구현은 다음과 같다. 여기에서는 기본적인 SAD를 이용한 정합을 수행하는 예제를 제공한다. ```python import numpy as np def block_matching(I1, I2, block_size, disparity_range): rows, cols = I1.shape disparity_map = np.zeros((rows, cols)) half_block = block_size // 2 for r in range(half_block, rows - half_block): for c in range(half_block, cols - half_block): best_disparity = 0 min_sad = float('inf') # 블록 매칭 탐색 for d in range(disparity_range): if c - d - half_block >= 0: sad = np.sum(np.abs(I1[r-half_block:r+half_block+1, c-half_block:c+half_block+1] - I2[r-half_block:r+half_block+1, c-d-half_block:c-d+half_block+1])) if sad < min_sad: min_sad = sad best_disparity = d disparity_map[r, c] = best_disparity return disparity_map ``` 위의 코드에서는 SAD를 이용해 두 이미지 $I1$과 $I2$에서 블록 크기 ( `block_size` )와 탐색 범위 ( `disparity_range` )를 주어진 조건으로 매칭을 수행한다. 매칭 결과는 `disparity_map`으로 나타나며, 각 픽셀의 불일치 정도를 나타낸다.