블록 매칭 알고리즘 - 실험 도서관

스테레오 비전에서 중요한 단계 중 하나는 두 개의 이미지 사이에서 동일한 물체의 점을 찾아내는 작업이다. 이 작업을 스테레오 정합이라고 하며, 이를 구현하는 다양한 알고리즘 중에서 블록 매칭 알고리즘(Block Matching Algorithm)은 가장 기본적인 방법 중 하나이다. 블록 매칭 알고리즘은 하나의 이미지에서 작은 영역(블록)을 다른 이미지에서 대응되는 영역과 비교하여 일치하는 블록을 찾는다. 이를 통해 각 점의 깊이 정보를 유추할 수 있다.

1. 기본 개념

블록 매칭 알고리즘은 일반적으로 다음의 절차를 따른다:

기준 이미지에서 특정 위치의 픽셀을 중심으로 작은 크기의 블록을 설정한다. 이 블록은 $\mathbf{B}_1$ 로 표현할 수 있다.
대응 이미지에서 동일한 크기의 블록 $\mathbf{B}_2$ 를 찾는다. 이때, 블록 $\mathbf{B}_2$ 는 기준 이미지의 블록 $\mathbf{B}_1$ 과 가장 유사한 블록이어야 한다.
블록 간의 유사성을 계산하는 방식으로는 절대 차이의 합(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 값을 기준으로 서브픽셀 위치에서의 최적화를 다음과 같이 수행할 수 있다:

$d_x = k$ , $d_x = k+1$ , $d_x = k-1$ 일 때의 SAD 값을 계산한다.
이차 함수를 이용하여 다음과 같은 형식으로 서브픽셀 위치에서 최소값을 추정한다:

$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)이 있다. 이 방법은 이미지의 해상도를 여러 단계로 줄인 후, 낮은 해상도에서 대략적인 매칭을 찾고, 그 결과를 이용하여 고해상도에서 정밀한 매칭을 수행하는 방식이다.

다중 해상도 접근의 절차는 다음과 같다:

이미지 피라미드 구성: 원본 이미지를 여러 해상도로 축소하여 피라미드를 생성한다. 예를 들어, 각 단계에서 이미지의 크기를 절반으로 줄여 다음 단계의 해상도를 구성한다.
저해상도에서 매칭 수행: 가장 낮은 해상도의 이미지에서 블록 매칭을 수행한다. 이 단계에서는 전체적인 구조만 반영되므로 빠른 탐색이 가능한다.
고해상도에서 세밀한 매칭 수행: 저해상도에서 찾은 대략적인 매칭을 기준으로, 고해상도로 올라가면서 더 정밀한 매칭을 수행한다. 각 단계에서의 결과는 다음 단계의 초기값으로 사용된다.

이 방법은 매칭 속도를 높이고, 넓은 탐색 범위에서 발생하는 오류를 줄이는 데 효과적이다.

9. 영상 잡음과 블록 매칭

스테레오 매칭에서 영상 잡음은 중요한 문제 중 하나이다. 영상에 잡음이 포함되어 있을 경우, 블록 매칭의 정확도가 크게 저하될 수 있다. 잡음의 영향을 줄이기 위해 블록 매칭 전후로 몇 가지 필터링 기법을 사용할 수 있다.

9.1 사전 필터링

매칭을 수행하기 전에 이미지에 포함된 잡음을 줄이기 위해 Gaussian 블러링이나 중간값 필터링과 같은 방법을 사용할 수 있다. 이러한 필터링 방법은 이미지에서 고주파 성분(잡음)을 제거하여 매칭의 신뢰성을 높이는 데 도움이 된다.

9.2 후처리 필터링

매칭이 완료된 후에도 정규화 필터나 중간값 필터를 사용하여 이상치(노이즈) 매칭 결과를 제거할 수 있다. 후처리 필터링은 불필요한 점들의 매칭을 제거하여 매칭 결과를 개선하는 데 중요한 역할을 한다.

10. 계산 복잡도

블록 매칭 알고리즘의 주요 단점 중 하나는 계산 복잡도이다. 모든 픽셀에 대해 가능한 모든 블록을 비교하려면 매우 많은 계산이 필요하며, 이는 실시간 시스템에서는 큰 부담이 된다. 계산 복잡도를 줄이기 위해 블록 매칭 알고리즘을 최적화하는 여러 방법들이 존재한다.

탐색 범위 제한: 탐색을 모든 위치에서 수행하는 대신, 예상 가능한 범위에서만 수행하여 계산량을 줄일 수 있다.
빠른 정합 기법: 탐색 과정에서 일부 블록은 추가 계산 없이 빠르게 제거할 수 있는 방법을 도입하여 계산 시간을 단축할 수 있다.

예를 들어, 삼각측량 기반의 사전 지식을 사용하여 정합이 일어날 수 있는 범위를 제한하면 탐색해야 할 공간이 줄어들게 된다.

11. 코드 구현

블록 매칭 알고리즘의 기본 구현은 다음과 같다. 여기에서는 기본적인 SAD를 이용한 정합을 수행하는 예제를 제공한다.

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으로 나타나며, 각 픽셀의 불일치 정도를 나타낸다.