1. 서 론

Optical flow는 연속된 영상 프레임 간의 픽셀 이동을 분석하고 픽셀의 변화를 수학적으로 모델링하여 객체의 움직임을 추정하는 기술이며 이를 기반으로 로봇 비전, 자율주행, 객체추적, 행동분석 등 다양한 응용 분야에서 사용된다^[1]. 40여년간 발전되어 온 optical flow에 대하여 다양한 접근 방법들이 제안되었으며 대표적인 방법으로 차등접근법(differential method), 영역기반 접근법(region-based matching method), 에너지기반 접근법(energy-based method), 위상기반 접근법(phase- based method) 등이 있다^[2]. 특히 차등접근법에 속하는 기울기 기반 알고리즘 중에 Horn-Schunck(HS)^[3]와 Lucas-Kanade (LK)^[4] 알고리즘은 초기에 제안되었으며 우수한 성능을 나타내어 이후 많은 연구자들이 이를 변형하여 다양한 소프트웨어 및 하드웨어 방법들을 제안하였다^[5-13]. LK 알고리즘은 연속된 프레임에서 큰 변위를 갖는 물체의 움직임 추정이 부정확하다는 단점이 있다^[1]. 이를 개선하기 위하여 피라미드 형태의 다중 스케일에서 반복적인 워핑 방법을 적용하였고 정확도가 개선되었다^[5]. 또한 모션 벡터를 구할 때 그 해가 없거나 무수히 많은 경우가 발생할 수 있는데 이 경우 해에 대한 신뢰도를 평가하기 위한 알고리즘이 제안되었다^[6].

Optical flow의 처리 과정은 연속된 프레임 데이터에 대하여 많은 연산 및 저장 공간과 픽셀 단위의 반복적인 처리를 필요로 하므로 실시간 동작을 위해서는 효율적인 하드웨어 접근방법이 필요하다. 실시간처리가 가능한 optical flow 시스템을 설계하기 위해서 고성능 병렬처리 및 파이프라인 구조, 정확도 유지를 위한 적절한 비트할당 및 하드웨어 복잡도 등을 고려해야 한다.

지금까지 실시간 optical flow 시스템 설계에 대한 많은 연구가 진행되어 왔다^[7-13]. Plyer 등은 고성능 GPU를 이용하여 다중해상도를 지원하고 고밀도 맵을 생성하는 대용량 병렬처리 구조인 eFOLKI 시스템을 제안하였다^[7]. Ishii 등은 가변 프레임의 속도를 적응적으로 제어함으로써 다양한 속도의 물체에 대해 움직임 벡터를 정확하게 추출할 수 있는 방법을 제안하였다^[8]. 이 때, 측정 가능한 움직임 벡터의 상한을 높이기 위해 개선된 optical flow 알고리즘은 고속 비전 플랫폼에서 하드웨어 로직으로 구현되었다. Diaz 등은 optical flow 처리를 위한 새로운 슈퍼 파이프라인과 병렬처리 구조를 제안 하였으며, 이 시스템은 FPGA를 이용하여 클럭 당 1픽셀의 데이터 처리량을 달성할 수 있는 70개 이상의 고성능 파이프라인으로 구성된다^[9]. LK 알고리즘에서 영상입력 대신 가우시안 필터링의 결과를 사용할 경우 과도한 외부 프레임 메모리가 필요하다^[10]. 이를 개선하기 위하여 가우시안 필터링된 영상을 수평 및 수직 방향에서 다운샘플링하는 방법이 제안되었으며 외부 메모리 액세스가 원래 데이터의 1/4로 줄어들어 자원효율이 개선되었다. Mahalingam 등은 비교적 정확한 연산이 가능한 효율적인 VLSI 구조를 제안하였다^[11]. LK 알고리즘은 먼저 확장된 고정 소수점 버전으로 변환되며, 정확성을 검증한 최적의 비트 폭으로 고속 하드웨어를 구현하였다. 알고리즘은 파이프라인 및 병렬구조를 적용하여 효율적인 VLSI 아키텍처로 매핑되었다. Barranco 등은 FPGA 환경에서 큰 변위를 갖는 물체의 동작 추정이 가능하도록 다중 스케일 확장을 적용한 LK 알고리즘을 구현하였다^[12]. 제안한 시스템은 정교한 파이프라인 구조를 통하여 높은 시스템 성능과 낮은 전력 소모를 보여준다. Jang 등은 다중 행 기반 접근 방식을 기반으로 한 전역적인 optical flow에 대한 VLSI 구조를 제안하였다^[13]. 제안한 구조는 영상을 여러 개의 하위 영상으로 나눈 다음 각 하위 영상의 흐름은 외부 메모리에 접근하지 않고 소량의 내부 메모리를 사용하여 순차적으로 추정되어 효율을 개선하였다.

본 논문에서는 LK 알고리즘을 기반으로 하는 실시간 optical flow 시스템을 설계하였다. 하드웨어 복잡도 개선과 효율적 설계를 위하여 에러율 분석을 통한 최적의 비트할당을 진행하였고 파이프라인 구조를 이용하여 임계경로를 최적화하였으며 병렬 연산 구조, 중첩 스케줄링 등을 통하여 처리성능을 개선하였다. 제안한 구조는 가우시안 스무딩을 처리하는 5개의 병렬연산 모듈과 시공간의 세 축(t,x,y) 기울기 정보를 동시에 연산하는 3개의 병렬모듈을 사용하였다. LK 알고리즘은 특성상 기연산된 중간 커널의 출력 데이터에 대한 재사용 빈도가 높다. 이를 위하여 최소의 메모리를 이용한 최적의 중첩 스케줄링을 적용하여 데이터를 업데이트하였으며 이로 인하여 필요한 계산량과 메모리 공간을 줄이고 중첩 스케줄링을 통하여 하드웨어 성능을 높여 실시간 처리가 가능하였다.

본 논문의 2장에서는 LK optical flow 알고리즘에 대해 설명하고 3장에서는 제안한 시스템을 기반으로 각 모듈들의 구조와 기능에 대하여 설명한다. 4장에서는 중첩 스케줄링 방법과 제안한 구조의 설계, 성능 및 하드웨어 비용 등을 기존 방법들과 비교 분석하였다. 마지막으로 5장에서는 결론을 맺는다.

2. Lucas-Kanade Optical Flow Algorithm

Optical flow를 추정하기 위해서는 밝기 항상성과 작은 움직임이라는 두 가지 전제 조건이 필요하다. 밝기 항상성은 영상 내의 픽셀이 시간 변화에 따른 동일한 밝기를 유지한다는 가정이며, 작은 움직임은 연속된 프레임 간 움직임이 작아 특정 픽셀은 멀리 움직이지 않음을 가정한다^[3]. 이를 수식으로 나타내면 식 (1)과 같다.

식 (1)에 테일러 급수를 적용하여 1차 항까지만 고려하면 식 (2)와 같이 간략화할 수 있다.

여기서 2차 이상의 항은 작은 움직임 조건에 의해 무시할 수 있으며, 식 (1)에 의해 다음과 같이 표현된다.

식 (3)의 양변을 $dt$로 나누고 명확한 의미를 위하여 표기를 다르게 하면 식 (4)로 표현할 수 있다. 식 (4)를 광학흐름 제약방정식(optical flow constraint equation)이라고 하며 $I_{x},\: I_{y}$는 공간적 기울기, $I_{t}$는 시간적 기울기, $u ,\: v$는 모션 벡터를 나타낸다.

LK 방식의 optical flow를 구하기 위하여 작은 영역(윈도우) 내에서 모든 픽셀이 동일한 움직임을 가진다는 가정을 추가한다. 이를 기반으로 최소자승법(least squares method)을 적용하고 최적화하여 모션 벡터를 구하면 식 (5)와 같이 표현할 수 있다.

식 (5)에서 $W_{i,\: j}$는 가우시안 가중치를 나타내며 가장자리의 픽셀들보다 중심점의 픽셀의 기여도를 높여 주변 픽셀의 영향을 줄이는 역할을 한다. 그리고 $I_{x_{i,\: j}},\: I_{y_{i,\: j}},\: I_{t_{i,\: j}}$은 해당 위치의 공간 및 시간 기울기를 나타낸다. 위에서 도출한 식 (4)를 행렬 연산으로 정리하면 식 (6)과 같이 표현할 수 있다.

가중치를 고려하여 최소 자승법으로 해를 구하면 식 (7)과 같이 표현할 수 있고, 최종 해를 구하면 식 (9)가 된다. 방정식의 구성요소들은 식 (8)에 표시하였다.

위의 식에서 $a=\sum_{i,\: j}W_{i,\: j}I_{x_{i,\: j}}^{2}$, $b=\sum_{i,\: j}W_{i,\: j}I_{x_{i,\: j}}I_{y_{i,\: j}}$, $c=\sum_{i,\: j}W_{i,\: j}I_{y_{i,\: j}}^{2}$, $b_{0}=\sum_{i,\: j}W_{i,\: j}I_{x_{i,\: j}}I_{t_{i,\: j}}$, $b_{1}=\sum_{i,\: j}W_{i,\: j}I_{y_{i,\: j}}I_{t_{i,\: j}}$, $\det = ac - b^{2}$ 이다. 이와 같은 과정을 통해 LK 기반 optical flow 연산을 할 수 있다.

Optical flow 알고리즘에서 식 (6)을 풀어 순간적인 모션 벡터를 구할 때 그 시스템이 해가 없거나 해가 무수히 많은 경우가 발생할 수 있다. 이 때 광학 흐름의 신뢰성을 평가하는 지표로 고유 임계값(eigenvalue threshold)과 정규화 잔차 임계값(normalized residual threshold)를 이용한다.

위 식에서 $\sum_{i,\: j}W_{i,\: j}I_{x_{i.j}}^{2}=M_{xx}$, $\sum_{i,\: j}W_{i,\: j}I_{y_{i.j}}^{2}=M_{yy}$, $\sum_{i,\: j}W_{i,\: j}I_{x_{i.j}}I_{y_{i,\: j}}=M_{xy}$로 표기하였다. 식 (10)과 (11)은 식 (8)의 $A^{T}WA$ 행렬의 고유값($\lambda_{1},\: \lambda_{2}$)을 구하는 식이며, 식 (8)에서 유도할 수 있다.

위의 식 (12)를 만족하면 해당 윈도우의 optical flow 결과가 맞다고 판단할 수 있다. 여기서 $T_{value}$는 신뢰성을 판단하는 고유값 임계치를 의미한다. 또 다른 신뢰성 평가 지표인 정규 잔차 임계값($\epsilon_{n}$)은 식 (13)과 같이 계산할 수 있으며, 주어진 잔차 임계값($\epsilon$)보다 작으면 신뢰성을 보장한다.

3. 제안한 Lucas-Kanade 기반의 Optical Flow 시스템

LK 기반의 optical flow 알고리즘에서 이미지의 모든 픽셀에 대해 다양한 커널 연산과 행렬 계산, 신뢰성 테스트 등을 진행할 때 하드웨어 복잡도와 많은 처리시간이 요구된다. 따라서 제안한 시스템은 중간 커널 결과를 최소 크기의 메모리에 저장한 후 중첩 스케줄링 규칙에 따라 커널 연산을 진행하여 하드웨어 복잡도와 처리시간을 개선하였다.

그림 1은 제안한 시스템의 전체 구조를 나타낸다. 전체 시스템은 잡음을 제거한 부드러운 전처리 영상을 생성하는 GS(Gaussian Smoothing), 시간 및 공간 축에서 물체 움직임의 기울기 성분을 계산하는 GU(Gradient Unit), 가중치 합을 통해 각 픽셀의 선형 방정식 계수를 구하는 Weighted Sum, 벡터를 계산하고 신뢰성을 검증하는 ES(Equation Solver), Validation, Residual 모듈 등으로 구성되어 있다. 연속된 9장 프레임들로부터 gray scale 화소 값들이 입력되며 이 값을 이용하여 최종 (u,v) 값은 프레임 하나의 움직임 총량이 나올 때까지 누적한다. 이 때, 각 모듈에서 데이터가 준비되는 즉시 다음 모듈로 전달되어 연산이 연속적으로 수행된다. 시간 방향의 기울기를 구하는 GU_T 모듈의 입력을 위하여 5개의 GS 블록이 필요하며 이를 위하여 연속된 9 프레임들의 픽셀 데이터가 5개의 GS 모듈들에 병렬로 입력된다. 즉, GS1, GS2, GS3, GS4, GS5 모듈에 각각 0-4, 1-5, 2-6, 3-7, 4-8 프레임들의 픽셀 데이터가 입력된다. 각 블록에서 t축, x축, y축 가우시안 필터를 순차적으로 거치며 가우시안 필터링이 적용된 픽셀 데이터를 생성한다. 그림에서 빗금 친 작은 블록은 타이밍을 맞추기 위한 쉬프트 레지스터를 나타내며 선 위의 숫자는 해당 신호에 할당된 비트 수를 표시하고 정수부와 소수부를 포함한다.

그림 2는 GS 모듈을 나타내며 5개의 연속된 프레임에서 동일한 좌표의 픽셀 데이터 5개를 t축 방향으로 가우시안 스무딩한다. 좌측 상단부터 행 방향으로 진행된 t축 가우시안 커널 출력은 x축 스무딩을 위하여 순차적으로 쉬프트 레지스터에 저장되어 매 사이클마다 x축 가우시안 출력이 생성된다. 최종 y축 출력을 위해서는 열 방향으로 5개의 x축 출력이 필요하며, 이는 픽셀 데이터의 진행 방향과 직교한다. 앞서 만들어진 x축 가우시안 결과는 이후 y축 커널 계산에서 사용되어야 하므로 이전 4개 행의 x축 출력 결과를 저장하는 메모리 구조가 필요하다. 저장된 4개의 x축 출력과 새로 입력되는 x축 출력을 커널 연산하여 y축 출력을 생성한다. 메모리에 x축 출력 결과가 모두 저장되기까지 y축 가우시안 필터 연산은 휴식하지만, 이후에는 매 사이클마다 y축 출력이 생성된다. GS 모듈에서 각 축마다 동일한 커널 [$\dfrac{1}{16},\: \dfrac{4}{16},\: \dfrac{6}{16},\: \dfrac{4}{16},\: \dfrac{1}{16}$]을 사용하였다.

GS 모듈의 메모리는 x축 방향으로 계산된 출력을 저장하고, 이후 y축 커널 연산 시 필요한 x축 출력을 공급하는 역할을 한다. 이 때 그림 2에서와 같이 각 행에 대해 meme와 memo로 구성된 총 8개의 메모리 블록을 사용하여 데이터를 저장하며, 이를 통해 읽기/쓰기가 동시에 수행되어 데이터 처리시간을 단축할 수 있다. 따라서 y축 커널 연산을 수행할 때는 메모리에 저장된 4개 행의 x축 출력과 새롭게 계산된 x축 출력을 함께 활용하여 y축 방향의 스무딩 연산을 진행한다. 새롭게 계산된 x축 출력은 다음 클럭에 더 이상 사용되지 않는 x축 출력이 저장되어 있는 메모리 공간에 업데이트 된다. meme에는 각 행의 짝수 번째 x축 출력이 저장되고 memo에는 홀수 번째 x축 출력이 저장된다. 이를 통해 각 행의 데이터를 meme과 memo에 번갈아 가며 저장한다. GS 모듈 메모리가 4개 행의 x축 출력 결과로 모두 채워지면, 각 행의 meme, memo에 저장된 값이 순차적으로 출력되기 시작한다.

그림 3은 GS 모듈 메모리의 타이밍도를 나타낸다. 먼저 meme0,1,2,3 4개 모듈의 0번지에 기저장된 좌표 (0,i-2), (0,i-1), (0,i), (0,i+1) 4개 행의 x축 커널 값을 읽고 새로 입력되는 좌표 (0,i+2)의 x축 출력과 커널 연산하여 좌표 (0,i)의 y축 출력을 생성한다. 동시에 새로 입력된 좌표 (0,i+2)의 x축 출력은 reg에 임시 저장된다. 첫 번째 y축 출력이 생성되면 meme0의 0번지에 저장된 좌표 (0,i-2)의 x축 출력은 더 이상 필요하지 않으므로 reg에 저장된 좌표 (0,i+2)의 x축 출력은 meme0의 0번지에 업데이트 된다. 다음 클록에서도 memo0,1,2,3의 0번지에 저장된 좌표 (1,i-2), (1,i-1), (1,i), (1,i+1) 4개 행의 x축 출력을 읽고 새로 입력되는 좌표 (1,i+2)의 x축 출력과 커널 연산하여 좌표 (1,i)의 y축 출력을 생성하며, 그 다음 클록에 reg에 저장된 (1,i+2)의 x축 출력을 memo0의 0번지에 업데이트한다. 이와 같이 meme와 memo에 데이터를 번갈아 업데이트하며 y축 출력을 생성한다. 또한, y축 출력을 생성하는 행이 변경됨에 따라 업데이트되는 메모리는 meme/o0→meme/o1→meme/o2→meme/o3→meme/o0 순서로 순환한다.

위에서 설명한 바와 같이 매 행마다 새롭게 업데이트되는 x축 결과의 저장 위치가 달라지므로 이에 따라 y축 커널로 입력되는 데이터의 순서도 적절히 조정되어야 하며 이는 order_gs 모듈에서 처리한다. 처음 처리되는 행의 커널 연산에서 메모리가 meme/o0,1,2,3 순서로 사용될 경우 커널 연산과 동시에 0번째 메모리에 새로운 x축 출력이 업데이트되므로, 다음 행의 연산에서는 meme/o1,2,3,0 순서로 변경된다. 이후 meme/o2,3,0,1→meme/o3,0,1,2→meme/o0,1,2,3 순서로 순환하며, 이 과정이 반복적으로 수행된다.

가우시안 필터링 연산에서 6개의 덧셈을 동시에 연산할 수 있는 6:2 compressor와 CPA(carry propagation adder)를 사용한다^[14]. 그림 4는 6:2 compressor 구조를 나타낸 것으로 6개의 입력을 더하기 위한 가산기의 한 비트열을 나타낸다. 입력은 해당 비트의 입력값(i0~i5) 6개와 아랫 단에서 오는 값(ci0 ~ci2)이며 출력은 윗 단으로 전달되는 값(co0~CO₂)과 carry와 sum으로 이루어져 있다.

그림 5는 GU 모듈을 나타내며 오른쪽의 kernel comp 블록은 왼쪽 블록도의 kernel comp 모듈의 내부 구조를 나타낸다. 위 구조를 통해 시간 및 공간 축(t축, x축, y축)에서 물체의 움직임 기울기 정보가 동시에 출력된다. meme/oy의 읽기, 쓰기 및 업데이트 방식은 GS 모듈 메모리의 동작 방식과 동일하며, meme/ot, meme/ox 또한 유사한 방식으로 동작하지만, 4개 행이 아닌 2개 행의 데이터를 저장하고 업데이트한다. 5개의 연속된 프레임에서 입력된 GS 출력은 좌측 상단부터 행 방향으로 진행하며, t축 커널 연산을 수행한 후 메모리에 저장된다. 기울기 출력을 생성하는 행이 변경될 때마다 모듈 order_t는 meme/ot0, meme/ot1의 데이터를 번갈아 출력한다. GU 커널[$\dfrac{1}{12},\: -\dfrac{8}{12},\: 0 ,\: \dfrac{8}{12},\: -\dfrac{1}{12}$]에서 중앙 커널 값이 0이므로 해당 입력은 블록도에서 제외하였다.

가운데 프레임의 GS 출력은 5개의 쉬프트 레지스터를 통해 x축 커널 연산을 수행한 후 메모리에 저장된다. 모듈 order_x는 모듈 order_t와 동일한 방식으로 동작한다. 또한 가운데 프레임에서 연속된 4개 행의 GS 출력을 메모리에 저장하며 모듈 order_y에 따라 메모리를 읽는 순서를 조정하고 이에 맞춰 y축 커널 연산을 수행한다. 모듈 order_y는 모듈 order_gs와 동일한 방식으로 동작한다.

그림 6은 Weighted Sum(WS) 모듈의 구조를 나타내며 sumIxIx를 예시로 구조를 설명하였다. 5⨯5 윈도우를 사용하기 때문에 5개의 쉬프트 레지스터를 통해 gu_x 값 5개를 연속으로 받은 후 제곱한 값에 대해 각각 가중치를 곱해준다. gu_x 값은 scan-order 방식으로 입력되며, 행 방향으로 gu_x 값이 입력되면 5개 단위로 값들이 누적되고 총 $⌊ 행 길이/5 ⌋$ 개의 중간 합들이 계산되며 이 중간 값들은 메모리의 해당위치에 저장된다. 이러한 과정이 반복되어 5번째 행까지 블록 단위로 누적되면 5⨯5 누적연산이 완료된다. 또한 윈도우 내의 5개 행 각각에 대한 가중치를 곱하기 위해 5:1 mux를 사용하고 각 행의 가중치 곱은 간단한 쉬프트 연산으로 구현하였다. 이와 같이 25개의 가중치를 곱한 값들의 합이 최종적인 sumIxIx가 되고 sumIxIy, sumIyIy 등 나머지 값들도 이와 유사한 방식으로 계산된다.

그림 7은 Residual 모듈의 구조를 나타낸다. 그림 6의 구조와 마찬가지로 t축, x축, y축 방향의 기울기 값을 오른쪽 커널 내부 구조와 같이 각각 5개의 쉬프트 레지스터에 저장하고 윈도우 내의 25개의 기울기 값에 대해 가중치를 곱한 후 메모리를 통해 결과 값이 나오게 된다. 여기서 나온 결과 값들과 WS 모듈에서 나온 sumIxIx, sumIyIy, sumItIt의 합에 대해 나눗셈 연산을 진행한다. 나눗셈을 통해 나온 최종 결과는 Residual 블록 내의 파라미터 $\epsilon$와의 대소 비교를 통해 (u,v)의 선별 여부를 결정한다. 그림 7에서 사용된 9개의 쉬프트 레지스터는 파이프라인 나눗셈기로 인한 타이밍을 맞춰주기 위한 쉬프트 레지스터이다.

4. 성능 분석

5. 결 론

제안된 LK optical flow 시스템은 중첩 스케줄링을 적용한 효율적인 데이터 업데이트와 병렬 연산 구조 및 파이프라인 적용 등을 통해 기존 알고리즘보다 높은 처리 성능과 하드웨어 효율성을 보여준다. 픽셀 데이터 진행 방향과 직교하는 방향의 커널 연산에서 발생하는 병목을 해소하기 위해 중간 결과를 저장하는 메모리를 삽입하고 짝수와 홀수 데이터를 번갈아 처리하는 업데이트 방식을 적용하였다. 이를 통해 연산 지연을 줄이고 메모리 사용량을 최소화하면서도 매 사이클마다 출력을 생성할 수 있도록 개선하였다. 또한 파이프라이닝을 통해 임계 경로를 최소화하고 중첩 스케줄링을 적용하여 실시간 처리가 가능하도록 설계했으며 연산 복잡도 개선을 위해 알고리즘의 커널 연산을 단순한 쉬프트 연산으로 대체하였다. 제안한 구조는 동부하이텍 110nm 표준 셀 라이브러리로 합성하여 Yosemite Sequence 영상 기준 3.70% 오차율과 최대 동작주파수 268MHz(264.6Mpixel/s)를 보이며, 71.59K개의 게이트와 15.43KB의 메모리를 사용한다.