1. 서 론

스테레오 비전은 서로 다른 지점으로부터 다수의 카메라로 얻은 영상을 이용하여 사물의 깊이정보를 측정하는 기술이다. 이의 결과는 장애물 인식 및 로봇비전⁽¹⁾, 자율주행⁽²⁾, 3차원 재구성⁽³⁾ 등 많은 분야에 적용된다. 스테레오 비전은 다수의 카메라로부터 얻은 영상에서 동일한 부분을 나타내는 점을 찾아 그 사이의 거리(disparity)로 사물의 깊이정보를 추출한다.

스테레오 비전은 정합에 이용하는 지역의 범위에 따라 지역정합(local matching)과 전역정합(global matching)으로 구분한다⁽⁴⁾. 영상의 제한된 정보만을 이용하는 지역정합법은 계산량은 적으나 경계부분 및 반복적인 패턴 등에 대해 취약하여 상대적으로 낮은 정합률을 보인다. 전역정합법은 지역정합법보다 높은 정합률을 보이지만 영상 전체를 고려하기 때문에 복잡한 알고리즘과 많은 계산량을 요구한다. 지역정합법에는 절댓값 누적 정합(SAD, Sum Of absolute differences), 센서스 변환(Cencus transform)⁽⁸⁾, 차이 제곱 누적(Sum of squared differences) 등이 있다. 또한 전역정합법에는 동적 계획법(dynamic programming)⁽⁵⁾, 신뢰 확산 알고리즘(belief propagation)⁽⁷⁾, 그래프 컷(graph cut) 알고리즘⁽⁶⁾ 등이 있다.

지역정합법으로 얻은 정합률은 윈도우의 크기와 모양, 정합에 사용되는 가중치 등의 영향을 많이 받는다. 최적의 윈도우와 가중치에 대한 다양한 연구가 진행되었지만 NP-hard의 복잡도를 나타낸다⁽⁴⁾. 영역기반의 접근 방법에서 획기적으로 정합률을 높일 수 있는 적응적 영역 가중치(adaptive support-weight)⁽⁹⁾ 알고리즘이 제안되었다. 영역을 정합할 때에 해당 픽셀과 주변 픽셀간의 색과 거리정보를 고려하여 유사도가 높을수록 큰 가중치를 부여하여 결과적으로 전역정합 방법의 정합률에 근접한 결과를 얻을 수 있다. 그러나 이렇게 얻은 disparity들은 지역정합의 한계성으로 부정확한 값들을 포함할 수 있다. 적응적 영역 가중치를 이용할 때와 같이 영상의 윈도우에 있는 픽셀 간에서는 서로 비슷한 색과 깊이를 가질 것이라는 전제를 바탕으로 disparity를 보정할 수 있는 disparity calibration 알고리즘이 제안되었다^(11)(12).

실시간처리가 가능한 스테레오 비전 시스템을 설계하기 위해서는 정합률, 처리성능 및 하드웨어 복잡도 등을 고려해야 한다. 지금까지 실시간 스테레오 비전 시스템 설계에 많은 연구가 진행되어 왔다^{(5,7,8)(13-15)}. Jin 등은 tree-structured dynamic programming 알고리즘을 FPGA를 이용하여 설계하였고⁽⁵⁾, Yang 등은 상관관계를 고려한 계층적 신뢰 확산 알고리즘 HBP(hierarchical belief propagation)⁽⁷⁾을 GPU로 구현하였다. Chang 등은 데이터의 재사용 할 수 있고 계산량을 줄이는 시스템을 제안하였다⁽⁸⁾. Hariyama 등은 영역기반의 SAD 알고리즘을 window-parallel, pixel-serial 방법으로 하드웨어를 100% 활용할 수 있도록 스케줄링 하였고⁽¹³⁾, Yang 등은 depth-reliability 기반의 스테레오 매칭 알고리즘을 메모리 머징 기법으로 설계하였다⁽¹⁴⁾. Han 등은 SAD 기반의 알고리즘을 이용하여 영상 직교화, bilateral filtering 등의 과정을 포함하는 스테레오 비전 프로세서를 설계하였다⁽¹⁵⁾.

기존의 지역정합 알고리즘을 기반으로 하는 시스템들은 실시간처리 성능과 전역정합에 준하는 에러율을 모두 만족하는 결과를 얻지 못하였다. 본 연구에서는 적응적 영역 가중치 기반 스테레오 매칭 결과의 시차맵을 보정하는 알고리즘을 적용하였고 이때 에러율을 개선하기 위한 비트할당, 지수함수 근사화, 파라미터 및 윈도우 크기 최적화 등을 적용하여 에러율을 최적화하였고 병렬처리와 임계경로 최적화, 파이프라인 구조, 데이터 재사용 등을 적용하여 처리성능을 개선하였다.

제안한 구조는 initial disparity를 계산하기 위한 11개의 병렬 연산 모듈과 disparity calibration을 담당하는 4개의 연산 모듈을 사용했으며 비선형 가중치 함수는 모의실험을 통해 에러율을 분석하여 적절한 계단함수로 구현했다. 알고리즘의 특성상 재사용이 불가능한 가중치 알고리즘을 에러분석을 통하여 행과 열로 분리하여 가중치를 재사용함으로써 계산량을 줄이고 하드웨어의 성능을 높였다.

본 논문에서 2장은 적응적 영역 가중치와 시차보정 알고리즘에 대해 설명하고 3장에서는 제안한 구조에 대하여 설명을 한다. 4장에서는 가중치 재사용과 스케줄링에 대하여 설명하고 5장에서는 제안한 방법의 성능분석과 다른 스테레오 시스템과 비교 분석하며 6장에서는 결론을 맺는다.

2. 적응적 영역 가중치와 disparity calibration

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

본 연구에서는 AD를 이용하여 적응적 영역 가중치를 구하고 이후 수정 가능한 오류들은 시차보정 과정을 이용해서 에러율을 낮추었다. 제안된 시스템에서는 가중치 재사용이 불가능한 기존 알고리즘을 행과 열을 분리하여 병렬적으로 가중치를 계산 할 수 있도록 하였고, 구해진 가중치를 재사용해 계산량을 줄이고 이에 따라서 실시간 처리가 가능하게 하였다.

그림 1은 제안된 스테레오 시스템 구조를 나타내며 초기 시차를 구하는 initial disparity calculation 모듈과 구해진 초기 시차의 오류를 정정해주는 disparity calibration 모듈로 구성되어 있다. initial disparity calculation에서는 11개의 ini_pe 모듈이 입력된 데이터를 병렬적으로 처리한다. 결괏값들을 동시에 합산하기 위해 n:2 compressor 기반의 가산기 트리로 구성된 wc_ adder와 wr_adder를 설계하였다. 레지스터 뱅크(ini_regbank) 모듈은 열 방향 가중치 합(wc_add)을 저장하고 재사용 하기 위한 모듈이며 추가로 행 방향 가중치(wr_shift)를 적용하여 초기 가중치(ini_weight)를 계산한다. 초기 가중치를 행 방향 가중치 합으로 나누어 정규 가중치(R_weight)를 구하기 위한 나눗셈기(div)가 설계 되었다. 최종적으로 비교기(min)모듈을 통해 해당 픽셀의 초기 시차를 결정한다. 초기 시차는 내부 메모리에 저장이 되며 시차 보정이 가능한 만큼의 초기 시차가 저장되면 disparity calibration 모듈이 중첩하여 동작함으로써 보정된 시차를 출력한다.

disparity calibration에서는 4개의 cali_pe 모듈이 병렬적으로 사용된다. 구해진 보정_열 방향 가중치 합(add_cali_wc)을 저장, 재사용하고 보정_행 방향 가중치 값(cali_wr)을 적용하기 위해 cali_regbank를 설계하였다. 최종 disparity를 결정하기 위해서 비교기(max) 모듈이 사용되었다.

표 1은 6 clock 동안 열과 행의 계산과정을 나타낸다. 본 연구에서 initial disparity calculation에서는 33$\times$33 크기의 윈도우를 기준으로 ini_pe 모듈을 11개 사용하였고 disparity calibration에서는 11$\times$11 크기의 윈도우를 기준으로 cali_pe 모듈을 4개 사용하였다. 하나의 윈도우를 계산하기 위해서 총 6 clock이 필요하며 첫 1~3 clock 에서는 열 방향에 대한 가중치가 계산되고 wc_adder에 값이 누적되며 3 clock에서 wc_adder 값이 출력되어 ini_regbank로 저장이 된다. 이후 4~6 clock에서 행 방향에 대한 가중치가 계산되고 ini_regbank로 값이 전달됨과 동시에 wr_adder에 값이 누적되며 마지막 6 clock에 wr_adder의 행 방향 가중치 합과 ini_regbank에 저장된 열 방향 가중치 합이 나눗셈기로 이동되어 가중치를 만들고 최솟값 비교기 모듈에서 초기 disparity 값을 출력한다.

그림 2는 ini_pe 구조를 나타낸 것으로 적응형 가중치와 픽셀의 유사도를 구하는 부분으로 나뉜다. 적응형 가중치를 구할 때 좌우 이미지의 p점과 q점의 R, G, B 값을 맨해튼 거리로 계산하였다. 픽셀 유사도의 경우 두 이미지의 각 q 점에서 R, G, B 값의 차의 절댓값을 합산하여 계산하였으며 임곗값은 40으로 설정하였다.

지수연산을 위하여 본 연구에서는 간단한 계단함수를 이용해서 근사적으로 구현하였다. 초기시차 연산의 경우는 5개의 영역일 때, 시차보정의 경우는 3개의 영역일 때 가장 좋은 모의실험 결과를 보여주었고 해당 함수는 그림 3에 나타내었다. 지수함수의 출력값은 추후 연산의 효율성을 고려하여 2의 지수승으로 고정하였으며 이후 2의 지수들만을 이용해 쉬프트 연산을 하였다. ini_pe의 출력은 총 3개로 열 방향 가중치(wc), 행 방향 가중치(wr), 행 방향 가중치 시프트 값(wr_shift)이다. 열 방향 가중치는 추후 wc_adder에서 합산되어 ini_regbank에 저장되고 행 방향 가중치는 wr_adder와 나눗셈기를 거쳐 초기 가중치 값을 정규화 하며 행 방향 가중치 시프트 값은 저장되어있는 열 방향 가중치에 행 방향 정보를 추가하여 초기 가중치를 결정한다. 그림 4는 ini_regbank의 구조를 나타내며 재사용되는 가중치를 저장하기 위한 공간은 2차원 구조로 되어있고 세로는 탐색거리, 가로는 윈도우의 행 길이로 설정하였다. ini_regbank에 wc_add이 입력이 들어오면 디코더를 통해서 해당하는 탐색거리의 공간에 저장된다.

이후 재사용할 시점에서 저장된 값들은 mux를 통해 추출되며 이를 입력된 11개의 wr_shift를 이용하여 연산한다. 결괏값들은 가산기 트리로 연산하여 초기 가중치를 구하기 위해 reg에 저장된다. 그림 5는 11:2 compressor 구조를 나타낸 것으로 11개의 입력을 더하기 위한 가산기의 한 비트열(bit-slice)을 나타낸다. 입력은 해당 비트의 입력값(i0 ~ i10) 11개와 아랫 단에서 오는 값(ci0 ~ ci7)이며 출력은 윗 단으로 전달되는 값(co0 ~co7)과 carry와 sum으로 이루어져 있다.

초기 가중치는 정해진 시점에 나눗셈기에서 행 방향 가중치 합과 연산되어 정규 가중치가 되고 이후 정규 가중치 값은 최솟값 비교기 모듈로 들어가 최솟값이 초기 시차로 결정된다. 나눗셈기 모듈은 임계경로를 고려하여 5-stage pipeline을 적용한 non-restoring divider로 구현하였다.

그림 6은 cali_pe에 대한 구조로 ini_pe와 다르게 좌측 이미지의 적응형 가중치만을 이용하여 계산한다. ini_pe에서는 그림과 같이 성분 차이를 계산하고 세 구간 계단함수로 근사화한 exp 모듈에 입력한다. 출력은 보정_열 방향 가중치(cali_wc)와 보정_행 방향 가중치(cali_wr)가 있다. cali_wc는 합산 후 cali_regbank에 저장하여 재사용되고 cali_wr는 cali_regbank에 저장한 열 방향 값에 추가적으로 행 방향 정보를 이용하여 cali_weight 값을 만들어낸다.

그림 7은 cali_wc_adder 구조로서 해당 탐색거리와 미리 구해둔 해당 픽셀에서의 초기시차 값의 동일 여부를 확인하는 부분과 계산된 값을 누적하는 부분으로 되어있다. 입력은 보정_열 방향 가중치(cali_wc)와 initial diaparity memory에서 입력되는 초기 시차(d)이다. 입력된 초기 시차는 해당 시점의 탐색거리와 동치여부를 mux에서 확인하고 만약 같으면 cali_wc를 아니면 0을 출력한다. 출력된 값을 reg에서 합산하여 보정_열 방향 가중치 합(cali_wc_add)을 구한다.

cali_regbank의 기본적인 동작은 ini_regbank와 동일하며 저장공간은 세로는 동일하나 가로는 33에서 11로 줄어들며 입력값은 12개에서 5개로 줄어든다. 입력값은 보정_열 방향 가중치 합(cali_wc_add) 1개와 보정_행 방향 가중치(cali_wr) 4개가 있다. 앞선 ini_regbank와 동일하게 cali_wc_add 합은 해당하는 탐색거리의 레지스터에 저장되고 mux를 통해 cali_wr와 맞은 값 4개를 추출하여 계산한다. 계산된 값은 합산 되어 최종 가중치 값(cali_weight)을 구하기 위해 reg에 저장되며 최댓값 비교 모듈에서 최종 disparity를 결정한다.

4. 데이터 스케쥴링

제안된 구조는 초기시차 탐색과 시차보정의 두 가지 순차적인 과정을 필요로 한다. 이를 효율적으로 개선하기 위하여 행, 열 분리에 의한 가중치 재사용과 initial disparity calculation 모듈과 disparity calibration 모듈을 중첩연산이 가능하도록 스케줄링 하였다. 적응적 영역 가중치는 식(2),(3)에서 보듯이 2차원 비선형 함수들로 구성되어 현재 계산된 픽셀들의 가중치 값들을 다음 픽셀의 계산 시에 재사용할 수 없다. 이를 개선하기 위하여 행과 열을 분리함으로써 2차원 구조를 1차원의 구조로 변형하여 재사용이 가능하도록 하였고 이로 인하여 발생하는 에러부분은 모의실험을 통하여 파라미터 최적화로 전체 에러율에는 큰 영향이 없도록 하였다.

제안한 구조는 실시간 처리를 위하여 initial disparity calculation 모듈의 경우 11개의 ini_pe와 ini_regbank, disparity calibration 모듈의 경우 4개의 cali_pe와 cali_regbank의 구조를 통해 병렬처리로 열 데이터 처리하였다. 이로 인하여 initial모듈에서 한 픽셀의 시차 값을 구하는 시간이 약 17배 cali모듈에서는 약 6배 줄어들며 ini_regbank에서 0.5KB cali_regbank에서 0.2KB 메모리가 필요하다.

시차보정을 순차적으로 실행할 경우 영상크기 만큼의 메모리가 필요하며 모든 초기 시차 값이 연산될 때까지 기다려야 한다. 이때 최종 시차를 얻는 시간은 31ms와 초기시차 값을 저장하기 위하여 60KB의 메모리가 필요하다. 하지만 시차보정 모듈이 동작할 수 있는 최소한의 시차 값이 준비된 시점부터 중첩을 시킨다면 초기시차 연산이 시작한 후 0.6ms 이후부터 시차보정 처리가 가능하다. 따라서 그림 8과 같이 17ms의 추가시간과 초기시차 11$\times$384를 저장할 4.2KB 메모리만으로 시스템 동작이 가능하다.

표 2는 재사용/중첩 유형별로 tsukuba 영상을 처리할 때 필요한 메모리와 사이클 수를 분석한 것이다. 가중치 재사용으로 15배 이상의 성능 향상과 초기시차와 시차보정 모듈간의 중첩으로 2배의 성능 향상을 얻을 수 있다. 또한 모듈간의 중첩으로 12배 이상의 메모리를 절약할 수 있다. 본 연구에서는 네 번째 유형을 적용하여 낮은 하드웨어 복잡도로 실시간 처리가 가능한 스테레오 비전 시스템을 설계할 수 있다.

표 3은 전체 모듈의 타이밍을 나타낸 것으로 초기시차 모듈에서 11개의 pe 모듈은 1~3 clock 동안 열 가중치를 출력하며 wc_adder 모듈에서 누적되어 3 clock에 ini_regbank에 저장한 뒤 4~6 clock 동안 ini_regbank에서 저장된 열 가중치와 행 가중치가 곱해져 누적되고 wc_adder에서 행 방향 가중치의 값이 누적된다. 두 개의 모듈에서 누적된 값들은 6 clock 동안 나눗셈기 모듈에서 가중치가 결정된다.

min 모듈에서는 6 clock 마다 가중치 값과 이전에 결정 된 가중치 값과 비교한다. 처음 6 clock에는 가중치 값과 해당 시차 값이 레지스터에 저장되며 다시 6 clock 뒤 새로운 가중치가 기존 레지스터에 저장된 가중치 보다 더 크다면 기존에 레지스터 값들을 그대로 유지하고 가중치 값이 기존 레지스터 값보다 더 작다면 작은 가중치 값과 해당 시차가 레지스터에 저장된다. 이 과정은 최대 탐색거리 횟수인 16번의 탐색 절차를 통해 96 clock에 초기 시차가 결정이 되며 초기시차 메모리에 저장된 후 레지스터 값은 다시 초기화 된다.

시차보정 모듈도 유사하게 4개의 cali_pe 모듈에서 1~3 clock동안 열 방향 가중치가 cali_wc_adder모듈에 누적되며 cali_regbank에 저장되고 4~6 clock 동안 cali_regbank에 누적된 열 방향 가중치와 행 방향 가중치들이 곱해지며 최댓값 모듈은 96 clock 동안 가장 큰 가중치의 시차를 출력한다.

5. 성능 분석

제안한 스테레오 비전 시스템은 VerilogHDL로 설계하여 동부하이텍 110nm 표준셀 라이브러리로 합성하였다. 합성 결과 전체 시스템은 2-input NAND 게이트 기준으로 33k의 게이트가 필요하다. 윈도우 크기는 33$\times$33, 최대 탐색거리는 16이고 최대 동작 주파수는 666Mhz이고 이때 처리성능은 57fps 이다. 가중치 재사용을 위한 초기시차연산 모듈의 regbank는 0.5KB, 시차보정 모듈의 regbank는 0.2KB, 중첩을 위하여 초기시차를 저장하기 위한 메모리는 4.2KB가 필요하여 총 4.9KB의 메모리를 요구한다.

표 4에서는 성능 비교를 위하여 Middlebury stereo dataset⁽¹⁶⁾으로 타 알고리즘의 결과와 에러율을 비교하였다. 표 4에서와 같이 각 영상에서 시차보정을 적용한 본 연구의 에러율은 전역정합법을 사용한 선행연구 ⁽⁵⁾⁽⁷⁾과 비교할 만하며 지역정합법의 결과보다 우수하다.

표 5에서는 다양한 실시간 스테레오 비전 시스템과 성능을 비교하였으며 avg. error는 표 4의 에러율을 평균한 값이다. 제안된 시스템은 지수 함수 근사화, 고정 소수점 할당, 행/열 분리 등으로 해당 알고리즘의 소프트웨어 결과보다 에러율은 약 1% 정도 소폭 늘어난 반면, 병렬처리, 임계경로에 대한 파이프라인 적용, 중첩 스케줄링 및 가중치 재사용 등을 적용하여 성능이 개선되어 실시간 처리가 가능하다.

제안한 시스템은 선행연구 ⁽⁵⁾와 비슷한 성능을 보이며 전역정합인 선행연구 ⁽⁷⁾은 낮은 에러율을 보이지만 상대적으로 처리속도가 낮다. 제안한 시스템은 지역정합을 기반으로 빠른 속도와 더불어 에러율은 전역정합과 비교 가능하다. 지역정합을 기반으로 하는 선행연구 ^(8)(14)와 비교하여 우수한 에러율을 보이며 처리 속도는 공정기술을 고려할 때 큰 차이를 보이지 않는다. 따라서 제안한 시스템은 충분한 실시간 처리 성능을 만족시킨다.

6. 결 론

제안된 실시간 스테레오 비전 시스템은 적응적 가중치와 오류 시차를 보정하는 calibration 알고리즘을 사용하여 기존 알고리즘에 비해 높은 정합률과 하드웨어 효율성을 보여준다. 기존 적응적 가중치 알고리즘과 달리 행과 열을 분리함으로써 중간 가중치를 재사용하였고 initial disparity 모듈과 disparity calibration 모듈의 중첩을 적용하여 성능을 개선하였다. 총 15개의 연산 프로세서와 중간 가중치를 저장하는 register bank, 파이프라인을 적용한 나눗셈기를 사용함으로 경로를 최소화 하였다. 알고리즘에 필요한 지수 연산은 하드웨어 비용과 성능을 고려하여 계단함수를 사용하였다. 제안한 구조는 동부하이텍 110nm 표준셀 라이브러리로 합성하여 tsukuba 영상 기준 1.88% 오차율, 최대 동작주파수 666MHz(57fps)를 보이며 33K개의 게이트와 4.9KB의 메모리를 사용한다.