1. 서 론

스테레오 비전은 두 대 이상의 카메라를 사용하여 촬영한 영상을 바탕으로 사물의 깊이 정보를 구하는 기술이며 이를 기반으로 장애물 인식 및 로봇비전⁽¹⁾, 무인자동차⁽²⁾, 3차원 재구성 등 다양한 응용 분야에서 사용되고 하드웨어로 설계하기 위해서는 정합의 정확도와 함께 실시간 처리 여부가 중요하게 고려되어야 한다⁽³⁾. 스테레오 비전 시스템은 인간이 두 눈을 통해 깊이 정보를 얻는 것과 유사하게 두 장의 이미지 사이에서 동일한 부분을 나타내는 대응점을 찾아 그 대응점들이 떨어진 거리(disparity)를 계산하여 깊이 정보를 추출한다.

스테레오 비전은 정합 방법에 따라 지역 정합법과 전역 정합법으로 나누어진다⁽⁴⁾. 지역 정합법(local matching)의 경우 영상의 일부분만 이용하고 상대적으로 단순한 알고리즘을 사용하기 때문에 구현은 용이하지만 반복적인 패턴 등으로 인해 발생하는 모호한 지역에 대한 정합이 어렵고 대체로 정합률이 낮다.

전역 정합법(global matching)은 전체 영상 정보를 이용하므로 이런 문제들에는 덜 민감하여 상대적으로 높은 정합률을 보이지만 복잡한 알고리즘으로 인하여 계산량이 많고 실시간 시스템 구현 시 하드웨어 비용이 높다. 전역 정합법에는 동적계획법(dynamicprogramming)⁽⁵⁾, 신뢰 확산 알고리즘(belief propagation)⁽⁶⁾, 그래프 컷(graph cuts) 알고리즘 등이 있으며 지역 정합법에는 절댓값 누적 정합(SAD, sum of absolute difference), 센서스 변환(CT, census transform)⁽⁷⁾ 등이 있다.

다양한 알고리즘과 특징을 가진 실시간 스테레오 비전 시스템에 대한 많은 연구가 진행되어 왔다^(6-11). 상관관계를 고려하여 신뢰 확산 알고리즘을 적용한 HBP(hierarchical belief propagation) 시스템이 Yang 등에 의해 구현되었다⁽⁶⁾. 또한 Jin 등은 직교화(rectification) 과정, 에러 검출 등의 스테레오 정합 전, 후처리를 포함하고, 64의 탐색거리를 지원하는 census 기반 시스템을 제안하였다⁽⁷⁾. Ambrosch 등은 변화도 기반의 MCT(modified census transform)와 색상 차이 기반의 SAD를 적절히 응용하여 시스템을 구현하였으며⁽⁸⁾, Chang 등은 가중치를 행/열 방향으로 구분하여 계산함으로, 데이터 재사용을 가능하게 만들어 계산량을 줄였다⁽⁹⁾. Fan 등은 정규화된 상호 연관성을 이용한 bilateral stereo를 병렬처리가 가능한 GPU로 실시간 처리가 가능하도록 구현하였다⁽¹⁰⁾. 또한 Dehnavi 등은 새로운 개념의 directional graph transform을 적용하여 에러율을 낮추었고 이에 대한 효율적인 하드웨어 구조를 제안하였다⁽¹¹⁾. 영역 기반 알고리즘은 정합을 위해 윈도우 단위로 이미지 정보를 비교하기 때문에 최적의 윈도우 크기와 모양을 정하는 것은 NP-hard에 해당하는 복잡한 문제다. 윈도우가 작으면 충분한 정보를 담지 못하고 지나치게 커도 불필요한 정보로 인해 올바른 정합이 어려워진다.

본 논문에서는 정합률을 높이기 위하여 적응적 영역 가중치 윈도우(adaptive support-weight window)⁽¹²⁾를 적용하였으며, 이로 인해 생기는 복잡한 연산을 최소화하는 방식을 제안하였다. 이와 함께 전역 정합법에 비견되는 에러율을 보여주는 DSM(distinctive similarity measure) 알고리즘⁽¹³⁾을 실시간 하드웨어 구현에 적합하도록 효율적으로 매핑하였다.

제안한 구조는 18개의 병렬 연산 프로세서 PE(processing element)를 사용하여 실시간 시스템으로 구현되었다. 비선형 가중치 함수는 에러율 시뮬레이션 분석을 통해 적절한 근사함수로 구현하였으며, 행과 열을 분리하여 가중치를 적용하는 방식⁽¹⁴⁾을 통해 중간 데이터를 재사용함으로써 계산량을 줄이고 하드웨어 효율은 높였다.

본 논문의 구성은 다음과 같다. 2장에서는 적응적 가중치와 DSM 알고리즘에 대해 설명하고 3장에서 제안한 구조와 4장에서 데이터 재사용과 스케줄링에 대해 설명한다. 5장에서는 시뮬레이션 및 구현 결과를 다른 스테레오 비전 시스템과 비교 분석하고 6장에서 결론을 맺는다.

2. 적응적 영역 가중치와 특징점 정합 알고리즘

3. 제안한 스테레오 비전 시스템 구조

DSM 알고리즘에서 이미지의 모든 특징점을 구한 이후에, 식(6)의 F(p,q)를 이용해 정합하는 기존 알고리즘 그대로 하드웨어로 구현하기에 많은 복잡도가 요구된다. 따라서 제안한 시스템은 해당 픽셀의 시차 값을 위해 필요한 영역만 특징점과 유사도를 병렬적으로 계산한다. 또한 행과 열을 분리하여 적용한 가중치 식(6)을 통해 열 단위 데이터를 재사용하여 실시간으로 시차(disparity)를 결정한다. 나아가 식(8)에 버림 값을 사용하지 않는 Non-semi dense matching 방법⁽¹³⁾을 적용하였다.

그림 2는 제안한 시스템의 전체 구조로 총 18개의 PE 모듈을 통해 입력 영상의 데이터를 처리한다. D_PE와 F_PE의 각각 9개 모듈로 D(p) 값과 F(p,q) 값을 병렬적으로 연산한다. 9개의 결과값을 동시에 더하기 위한 CSA(carry save adder) 기반의 가산트리(adder tree)를 구현하였다. 또한 필요한 열 데이터를 저장하고 이를 재사용함과 동시에 행 가중치 적용을 위한 D_Regbank, F_Regbank를 설계하였다. Find_D(p) 모듈에서 D_Regbank 모듈을 통해 양방향으로 탐색된 D(p) 값이 최종 결정된다. 이 값과 F_Regbank 모듈에서 탐색된 F(p,q) 값은 Find_Disparity 모듈에서 최종적인 정합이 이루어져 시차 값을 정한다.

그림 3은 하나의 PE 구조로 탐색 윈도우의 비용함수와 열 방향 가중치의 곱 및 행 방향 가중치를 출력하는 모듈이다. 표 1은 Regbank 모듈에 계산된 값을 전달하기 위한 타이밍도로, 윈도우 크기 27×27 기준으로 9개의 모듈을 사용했기 때문에 한 열 또는 행을 계산하는데 3 clock을 필요로 한다. 처음 3 clock 동안 비용함수와 열 가중치의 곱을 계산하고 이를 가산트리에서 값을 누적하여 Regbank 모듈로 값을 전달한다. 다음 3 clock 동안은 비용함수 계산을 멈추고 행 방향 가중치 값이 Regbank 모듈로 전달된다.

기존 알고리즘에서는 중심 픽셀로부터 음의 방향에서 양의 방향으로 순차 탐색했다면 이를 개선한 (a) D_PE 모듈은 양방향 동시 탐색이 이루어진다. 고정 윈도우의 한 픽셀(p)로부터 각각 음과 양의 방향 탐색 윈도우의 픽셀(p_sl, p_sr)의 입력을 받아 비용함수(El, Er)를 계산한다. 이는 열 가중치가 곱해져 출력되거나 혹은 행 가중치 값만을 따로 출력한다. (b) F_PE 모듈은 정방향 탐색으로, 고정 윈도우의 픽셀(p_l)과 탐색 윈도우의 픽셀(p_r)의 비용함수 계산과 가중치 곱이 이루어지며 (a),(b) 모듈 모두 타이밍에 따라 필요한 출력만을 사용한다.

그림 4는 가중치(weight) 모듈의 구조로 고정 윈도우의 컬러와 거리 정보를 입력 받아 식(3)을 계산한다. 제안한 모듈은 연산의 효율성을 위해 맨해튼 거리(manhattan distance)를 적용 하였다. 컬러 정보를 위한 세 개의 절댓값 블록은 각 성분의 차이를 계산하여 파라미터 $\lambda_{c}$와 곱해진다. 거리 정보는 윈도우에서 행, 열 단위의 규칙적인 연산이 진행되기 때문에 입력 없이 내부적으로 카운터를 이용하여 설계하였다. 거리 차의 값은 파라미터 $\lambda_{d}$와 곱해지고 계산된 두 값은 더해져 지수 함수 근사화를 통해 최종적인 가중치 값이 계산된다.

지수함수의 근사화를 위해 본 연구에서는 선형함수와 계단함수를 다양한 구간으로 설계하여 에러율을 분석한 결과, 계단함수를 4개 구간으로 나누었을 때가 하드웨어 비용 대비 가장 좋은 결과를 보여 표 2와 같이 설계하였다.

행과 열을 분리한 가중치 적용에 따른 열 데이터의 재사용이 가능해진다. 본 연구에서는 이를 적극 활용하기 위해 쉬프트 방식의 FIFO(First-In, First-Out) 메모리와 동시에 유기적으로 행 가중치를 적용하는 연산회로를 설계하였다.

그림 5는 이를 위한 D_Regbank의 구조로 PE와 가산트리를 통해 누적된 열 데이터 값과 9개의 행 가중치의 값을 입력 받는다. 열 데이터는 메모리에 저장되고 행 방향 가중치는 그림 6의 다중 Mux를 거친 열 데이터와 곱해져 가산트리에서 누적된다. 이를 통해 D_Regbank 모듈에서 양방향 D(p) 값을 만든다.

식(4)만큼의 탐색거리와 일대일 대응이 될 수 있도록 Regbank 내 30개의 저장 공간을 지닌 FIFO 메모리를 구현했다. 하나의 저장 공간은 윈도우의 행 길이 만큼 27칸으로 구성되며 비용함수 열 단위 값이 저장 된다. 다음 시차 결정을 위해 새로운 열 데이터가 입력되면, 저장 공간 [26] 칸을 제외한 이전의 값들은 오른쪽으로 쉬프트 하여 재사용이 이루어지고 추가되는 열은 [0] 칸에 저장되어 다음 탐색거리에 해당하는 새로운 윈도우가 된다.

그림 6의 Mux & AdderTree 모듈을 통해 행 가중치가 곱해지며 이를 통해 양방향으로 각 탐색범위에 해당하는 D(p) 값이 계산된다. 27개의 15:1 Mux는 각 저장 공간 마다 한 칸씩만을 입력으로 하며, 총 3 clock에 걸쳐 하나의 저장 공간의 값들을 27:9 Mux로 전달을 통해 행 가중치 곱이 이루어진다. 그 동안 이를 누적하여 더해주는 가산트리를 통해 D(p) 값을 만든다.

처음에는 [-15], [+1] 탐색범위에 해당되는 첫 번째 칸에 저장되고 이전의 값은 두 번째 칸으로 쉬프트 된다. 이후 3 clock 동안 그림 6의 구조를 통해 각 저장 공간에 행 가중치를 곱해 누적한다. 다음 주기의 열 데이터 입력 때 [-14], [+2]의 저장 공간에서 반복적인 작업이 진행된다. 자세한 데이터 재사용의 내용은 4.1장에 기술하였다.

F_Regbank 모듈은 탐색범위를 하나 더 가지며 정방향 탐색이 이루어지므로 16개의 27칸으로 구성된 저장 공간 필요로 한다. 27개의 16:1 Mux와 27:9 Mux, 가산트리 모듈로 행 가중치 곱이 이루어진다.

그림 7은 특징점과 시차 결정을 위한 Find_D(p)와 Find_Disparity의 구조로 특징점 결정 모듈은 양방향 탐색으로 나온 D(p)의 최솟값 결정으로 최종 D(p) 값이 정해진다. 또한 시차 결정 모듈에서 실시간으로 정합 계산을 위해 탐색범위만큼 16개의 D(p) 값 저장 공간을 가진다.

저장 공간의 값들은 16:1 Mux를 통해 시차를 구하는 픽셀로부터 15 픽셀만큼 떨어진 [15]번째 칸부터 출력된다. 이는 시차 결정 모듈에서 F(p,q)와 나눗셈 연산이 이루어진다. 이때 Mux의 선택선, 칸의 색인이 곧 시차값 후보군이 된다. 시차값 결정을 위해 식(8)의 탐색 범위 내에서 최대 정합값을 찾는다. 한 픽셀의 시차값이 결정되면 다음 픽셀을 위해 저장 공간을 한 칸 쉬프트 해주고 새롭게 추가되는 영역에서만 D(p) 값을 구해준다.

자세한 타이밍도는 4.2장에 기술하였다. 그림 7의 나눗셈기는 임계경로와 성능(throughput)을 고려하여 파이프라인을 적용한 non-restoring bitwise divider로 구현하였다.

4. 데이터 재사용과 스케줄링

5. 성능 분석

제안한 스테레오 비전 시스템은 VerilogHDL로 설계하여 Modelsim으로 검증하였으며 동부하이텍 110nm 표준셀 라이브러리로 합성하였다. 합성한 결과 전체 시스템은 74K개의 게이트를 필요로 하며 데이터 재사용을 위한 D_Regbank, F_Regbank 모듈 내의 메모리는 각각 약 1.6KB, 0.8KB 정도를 요구한다. 최대 동작 주파수는 565 MHz로 약 56fps의 속도를 갖는다. 실험적으로 에러율을 분석하여 최적화한 결과 파라미

터 $\lambda_{c}, \lambda_{d}$는 각각 0.07421875, 0.5 값을 할당하였다.

표 5에서 대표적인 여러 스테레오 영상에 대하여 타 시스템과 에러율을 비교 분석하였으며 표 6에서는 다양한 실시간 스테레오 비전 시스템과 성능을 비교하였다. 제안된 시스템은 가중치 함수 근사화, 고정 소숫점 할당, 행/열 분리 등으로 인하여 기존 DSM 알고리즘에 비하여 에러율은 약 1~2%로 소폭 늘어난 반면, 병렬처리, 파이프라이닝, 함수 단순화, 데이터 재사용 등을 이용하여 실시간 처리가 가능하다.

제안한 시스템은 선행연구 ⁽¹¹⁾과 비슷한 성능을 보이며 전역정합인 선행연구 ⁽⁶⁾은 우수한 에러율을 보이지만 상대적으로 처리속도가 낮다. 제안한 시스템은 지역정합을 기반으로 하기 때문에 빠른 속도와 더불어 약 0.7%의 평균 에러율 차이 밖에 나지 않는다. 또한 선행연구 [7~10]과 비교하여 크게는 약 4.4%의 차이까지 우수한 정합률을 보인다. 선행연구 ⁽⁷⁾은 우수한 처리 속도를 보이지만 제안한 시스템으로도 충분한 실시간 처리 성능을 만족시킨다. 표 6의 avg. error는 표 5에서의 에러를 평균한 값이다.

6. 결 론

제안된 실시간 스테레오 비전 시스템은 적응적 가중치 윈도우를 적용한 DSM 알고리즘을 사용하여 다른 영역 기반 알고리즘에 비해 우수한 정합률을 보여준다. 기존 가중치 윈도우 방식과 달리 행과 열을 분리하여 중간 결과를 재사용 할 수 있도록 하였고, 병렬 처리를 적용한 18개의 연산 프로세서와 중간 결과를 저장하는 register bank 및 정합 프로세서의 효과적인 스케줄링을 통해 특징점 탐색과 정합이 동시에 이루어진다. 또한 파이프라이닝을 적용한 산술 연산을 통해 임계 경로를 최소화 했으며 알고리즘에 필요한 지수 연산을 하드웨어 비용을 고려한 효율적인 근사화를 통해 우수한 성능을 보여준다. 제안한 구조는 동부하이텍 110nm 표준셀 라이브러리로 합성하여 츠쿠바 영상 기준 2.11% 에러율과 최대 동작주파수 565 MHz(56fps)를 보이며 74K개의 게이트와 2.4KB 메모리를 사용한다.