움직임 추정 장치 및 이를 구비하는 동영상 부호화 장치 document_id A220623056598

최근, 인터넷을 포함한 정보통신 기술의 발달과, HDTV, PDA 및 핸드폰 등의 다양한 멀티미디어 기기의 발전으로 인하여 고화질 동영상 서비스에 대한 수요가 증가하고 있다. 이에 따라 고화질의 동영상 처리를 위해서는 방대한 양의 영상 정보를 효율적으로 압축할 수 있는 기술이 필요하다. 움직임 추정(Motion Estimation(ME)) 기술은 MPEG 및 H.26x 등과 같은 비디오 압축 규정에 널리 적용되고 있다. 움직임 추정 기술이란, 동영상 내의 물체의 움직임이나 카메라의 이동과 확대 및 축소 등으로 인한 현재 연상과 이전 영상의 위치 변화를 나타내는 움직임 벡터(Motion Vector, MV)를 구하는 것으로서, 용량을 줄이기 위한 동영상 압축, 화소 디모자이킹(Pixel Demosaicking), 프레임 보간(Frame Interpolation) 등의 비디오 영상처리에서 광범위하게 이용된다. 움직임 벡터(Motion Vector)를 얻기 위해서는, 먼저 움직임 추정을 화소 단위로 할 것인지 또는 블록 단위로 할 것인지를 결정해야 하며, 일반적으로 동영상 압축과정에서는 주로 블록 단위의 움직임 추정을 사용한다. 블록 매칭 알고리즘(Block Matching Algorithm)은 현재 프레임과 이전 프레임의 움직임 벡터를 블록 단위로 추정하는 기법이며, 이 때 사용되는 블록을 매크로 블록(Macroblock)이라고 한다. 블록 매칭 알고리즘 방법에서는, 현재 프레임의 매크로 블록과 이전 프레임의 매크로 블록을 이전 프레임의 정해진 탐색 영역(Search Area) 내에서 비교한 후, 가장 유사한 매크로 블록의 위치를 찾아낸다. 즉, 이전 프레임의 매크로 블록이 현재 영상의 어느 위치로 이동하였는지 찾아내는 것이며, 이 때 이동한 위치 및 크기가 움직임 벡터에 대응한다. 움직임 벡터(Motion Vector)를 구하기 위한 많은 움직임 추정 알고리즘이 존재하는데, 블록 매칭 알고리즘 중 하나로서 전역 탐색 블록 매칭(full search block-matching, FSBM) 알고리즘이 존재한다. FSBM 알고리즘 방식은, 현재 프레임의 매크로 블록 내의 모든 화소를 일정한 크기로 설정된 이전 프레임의 탐색 영역 내의 모든 매크로 블록과 비교하고, 탐색 영역내에 포함되는 다수의 후보(candidate) 매크로 블록들 중 최소 차이값을 갖는 매크로 블록을 찾아낸다. 상기 FSBM 알고리즘 방식은 상당히 정확한 블록 기반(block-based)의 움직임 벡터 결과를 발생한다. 이에 반해 다른 움직임 추정 알고리즘으로서, 코어스-투-파인 탐색(coarse-to-fine search) 알고리즘이 있으며, 이는 FSBM 알고리즘 방식에 비해 다소 낮은 정확성을 가지나, FSBM 알고리즘 방식에 비해 계산량을 줄일 수 있는 장점이 있다. 코어스-투-파인 탐색 알고리즘의 예로서, 3-스텝 탐색(3 step search), 4-스텝 탐색(4 step search), 2D 로그형(2D logarithmic) 탐색 등이 있다. 상기와 같은 코어스-투-파인 탐색 알고리즘의 경우 빠른 속도를 제공하는 반면에, 낮은 이미지 특성(quality)에 따른 문제점이 있으므로, 이에 따라 FSBM 알고리즘 방식이 그 계산량이 많음에도 불구하고, 그 구조의 간단함 및 높은 이미지 특성의 원인으로 인하여 널리 사용되고 있다. FSBM 움직임 추정 알고리즘을 구현하기 위한 많은 움직임 추정 하드웨어 기술들이 존재한다. 이러한 하드웨어 기술들은 여러 카테고리로 분류될 수 있는데, 상기 카테고리로서 시스톨릭 어레이(systolic array) 구조 및 트리 구조(tree structure) 등이 있다. 움직임 추정을 위한 하드웨어로서 시스톨릭 어레이(systolic array) 방식은 블록 매칭(block-matching) 알고리즘의 VLSI 구현을 위해 적합한 것으로서, 온-칩 상에서 기준 데이터(일예로서 이전 프레임의 화소 데이터)를 쉬프팅 동작에 의하여 여러 프로세싱 엘레멘트(processing element)로 제공하므로, 데이터의 재사용을 극대화할 수 있는 장점을 갖는다. 이로 인하여 데이터 입력 대역폭을 작게 할 수 있다. 그러나, 쉬프팅에 의해 전달되는 데이터가 긴 데이터 경로 길이(data path length)에 의해 전달되므로, 딜레이가 증가하거나 내부의 데이터 스큐(skew)에 따른 문제점이 발생할 수 있다. 상기와 같은 긴 딜레이 및 데이터 스큐를 피하기 위하여 트리 구조(tree structure) 방식이 채택될 수 있다. 상기 트리 구조(tree structure) 방식에 따르면, 수행 레이턴시(execution latency)를 최적화함에 있어서 잇점을 가지며, 또한 3-스텝 탐색 움직임 측정 알고리즘의 구현에 더욱 적합하다. 그러나, 상기 트리 구조에는 데이터 스큐가 발생하지 않으므로, 이전 프레임의 탐색 영역 내의 후보 블록(탐색되는 매크로 블록)들에 관련된 데이터들이 동시에 억세스되어 상기 트리 구조로 제공되어야 한다. 따라서, 트리 구조는 시스톨릭 어레이 방식에 비해 더 많은 데이터 입력 대역폭을 필요로 한다. 상기와 같은 시스톨릭 어레이 방식의 특성 및 트리 구조 방식의 특성 사이의 트레이드 오프(tradeoff)를 제공하기 위하여, 하이브리드 트리 및 선형 어레이 구조(Hybrid tree and linear array architecture)가 소개되고 있다. 하이브리드 트리 및 선형 어레이 구조는 상기 시스톨릭 어레이와 트리 구조 방식을 조합한 구조를 갖는다. 그리고, 하이브리드 트리 및 선형 어레이 구조에 구비되는 시스톨릭 어레이 또는 서브 트리의 적절한 사이즈를 선택함에 의하여, 레이턴시 및 입력 데이터 대역폭 특성 등을 조절할 수 있다. 도 1은 FSBM 움직임 추정 알고리즘을 구현하기 위한 일반적인 시스톨릭 어레이 구조를 나타내는 블록도이다. 시스톨릭 어레이 구조는 1-D, 및 2-D 구조가 제안되어 있으며, 도 1에는 그 일예로서 2-D systolic array 구조가 개시된다. 도시된 바와 같이 2-D 시스톨릭 어레이 구조는, 블록 매칭 알고리즘의 기본 처리 단위인 매크로 블록이 Nh(수평 화소수) * Nv(수직 화소수) 개의 화소를 구비하는 경우, 수평 및 수직 방향으로 배치되는 2-D 구조의 Nh * Nv 개의 프로세싱 엘레멘트(processing element, PE)들을 구비할 수 있다. Nh * Nv 개의 프로세싱 엘레멘트 각각은 래치(미도시)를 구비할 수 있다. 현재 프레임의 해당 매크로 블록에 구비되는 각각의 화소의 데이터는, 상기 각각의 프로세싱 엘레멘트로 프리 로드(pre-load)되어 래치에 저장될 수 있다. 또한, 이전 프레임의 탐색 영역 내의 후보 매크로 블록의 화소 데이터(기준 데이터, reference data)가 상기 프로세싱 엘레멘트로 제공되는데, 상기 후보 매크로 블록의 Nv 개의 화소 데이터가 병렬하게 억세스되며, 수평 방향으로의 쉬프트 동작에 기반하여 프로세싱 엘레멘트로 제공될 수 있다. 각각의 프로세싱 엘레멘트는 현재의 프레임 및 이전의 프레임의 화소 데이터의 절대 차이값을 산출한다. 이전 프레임의 정해진 탐색 영역(Search Area) 내의 후보 매크로 블록들 중 현재 프레임의 매크로 블록과 가장 유사한 매크로 블록의 위치를 찾아내기 위하여, cross-correlation function(CCF), mean square error(MSE), mean absolute error(MAE) 및 sum of absolute difference(SAD) 등의 방법이 사용될 수 있다. 그 중 절대 차이값의 전체 합(SAD)은, 그 낮은 복잡도 및 우수한 결과 때문에 실제 구현상 가장 널리 사용된다. 도 1에 도시된 바와 같이, 시스톨릭 어레이 구조에 구비되는 소정의 가산 유닛(A)에 의하여 절대 차이값의 전체 합(SAD)이 구해진다. 상기와 같은 시스톨릭 어레이 구조에 따르면, 시스톨릭 어레이로 기준 데이터가 중복하여 제공되는 것을 방지하고 이전에 입력된 기준 데이터를 재사용할 수 있으므로, 데이터 입력 대역폭을 작게 할 수 있다. 한편, 도 2는 FSBM 움직임 추정 알고리즘을 구현하기 위한 일반적인 트리 구조의 블록 다이어그램을 나타낸다. 도 2에 도시된 유닛 D는 현재 프레임의 매크로 블록의 화소 데이터(current data X)와 이전 프레임의 후보 매크로 블록의 화소 데이터(reference data Y)를 비교하여 절대 차이값을 산출한다. 또한 유닛 A는 상기 절대 차이값들을 서로 합산하여 출력한다. 2D systolic 구조와는 달리, 매크로 블록의 전체 화소수인 Nh * Nv개의 기준 데이터가 병렬하게 억세스되어 상기 트리 구조로 제공된다. 도시된 바와 같이 트리 구조로 제공되는 기준 데이터는 재활용되지 못하고 여러 번 중복되어 억세스되므로, 데이터 입력 대역폭이 커지게 된다. 근래들어, LCD, PDP, 및 디지털 프로젝션 시스템 등과 같은 새로운 디스플레이 기술들이 높은 화질 및 큰 사이즈의 디스플레이를 제공함에 따라, 높은 해상도의 이미지를 처리하기 위한 이미지 처리 기술이 요구가 된다. 특히 높은 해상도 및 사이즈 증가에 따라 초당 처리하여야 하는 데이터 양이 증가하므로 동작 주파수가 증가하게 된다. 그러나, 상기 언급된 FSBM 알고리즘에 기반하는 여러 카테고리 방식은, 사실상 상기와 같은 고 해상도의 이미지를 처리하는데 적합하지 못하다. 특히, 시스톨릭 어레이 기술의 특성 및 트리 구조 특성 사이의 적절한 트레이드 오프(tradeoff)를 제공하기 위해 종래에 소개되었던 하이브리드 트리 및 선형 어레이 구조는 많은 연산량을 요구하기 때문에, 이러한 구조는 고해상도 이미지를 처리하기 위해서는 적합하지 않다.