Motion compensation is a powerful method in video coding to reduce temporal redundancies of successive image frames. The key procedure of motion compensation is motion estimation that traces the motion trajectories of moving objects in a frame. As one of major application of motion compensation, motion-compensated interpolation is very attractive since it can be combined with known coding techniques to reduce the bit rate. Motion-compensated interpolation requires motion estimation to satisfy both an accuracy constraint and a real-time constraint. Although various motion estimation algorithms are endeavoured, block-based approach is widely used in video coding area. However, a typical block-based approach, the block-matching algorithm, can not satisfy the accuracy constraint.
The hierarchical block-matching algorithm (HBMA) is quite successful in fulfilling the accuracy constraint because it copes with global motion of moving object and local motion as well. Nevertheless, high computational complexity of HBMA prevents it from satisfying the real-time constraint. Hence the parallel architecture for HBMA is necessary for real-time processing, whereas considerablely less work has been done. However, there are inherent data dependencies in HBMA, which are major obstacles in parallel processing. Data dependencies of HBMA are investigated and defined as interlayer data dependency and intralayer data dependency.
This dissertation presents pipelined VLSI architectures for HBMA based on systolic array to achieve real-time processing performance. At first, a generalized pipelined VLSI architecture is proposed. It consists of r stages, each of which corresponds to a layer of HBMA. Each stage has a systolic array for BMA, a bilinear interpolator for bilinear interpolation, and the latch mechanisms for arranging the intermediate results of the motion vectors. Besides, there are internal memories to store image data needed to compute motion vectors. To satisfy data dependencies of HBMA, the pipeline configuration, the latch mechanisms, and the bilinear interpolator are designed in a novel way.
In design of the detailed operations of the components, the flow of the intermediate vectors should be fixed in a certain order, because data dependencies require them to be supplied at correct time. Since an image frame is composed based on line-by-line style, there are two alternatives of the order of the data flow : a zig-zag pattern (referred to a raster-scan order) and a left-to-right/right-to-left pattern (referred to a snake-like order).
According to these orders of the data flow, two three-stage pipelined VLSI architectures are presented as special cases of the generalized architecture based on the given parameters of HBMA. R-Architecture is designed based on the raster-scan order and S-Architecture is designed based on the snake-like order.
The results of performance analysis on two three-stage pipelined VLSI architectures show that both architectures can process in real-time up to the broadcast video format under the current VLSI technology, and the HDTV video format with the near future VLSI capabilities. Both architectures also achieve nearly linear speedup over an assumed non-pipelined VLSI architecture without additional hardware cost. Compared to R-Architecture, the pin count for data input ports of S-Architecture is around half, while the control logic of S-Architecture is more complicated.
방대한 비디오 자료의 압축기법 중에서 이동보상방식은 연속된 이미지 프레임 사이에 존재하는 시간적인 데이타 중복성을 제거하는 방식이다. 이때, 이동보상방식은 이동추정 알고리즘을 근간으로 하고 있으며, 이동추정 알고리즘은 프레임 내에 존재하는 이동물체의 움직임을 추적하는 기능을 한다. 이동보상방식의 한 세부응용인 이동보상보간방식은 기존의 다른 압축방법과 결합되어 압축률을 더 높일 수 있는 특성이 있기 때문에 비디오 압축에서 관심을 끌고 있는 분야이다. 이동보상보간방식에서 이용되는 이동추정 알고리즘은 보다 실제에 가까운 정확한 이동벡터를 구해야되는 정확성 특성과 비디오가 자연스럽게 출력되기 위해서 제한된 시간내에 한 프레임을 처리해야되는 실시간 특성이 요구된다. 지금까지 연구되었던 여러가지 이동추정 알고리즘 중에서 블럭을 기반으로한 방식이 비디오 압축분야에서 많이 이용되었다. 블럭을 기반으로한 방식의 전형적인 알고리즘은 블럭비교 알고리즘(BMA)이지만, 이 알고리즘은 이동보상보간방식에서 요구하는 정확성 측면에서 적합하지 않다.
BMA의 정확성 문제를 개선한 것으로서 계층적 블럭비교 알고리즘(HBMA)이 제안된 ￡? 있다. HBMA는 이동물체의 전반적인 움직임을 먼저 추적하여 잠정적인 이동벡터를 구하고, 점차 세분화된 움직임을 나타내는 이동벡터를 구하여 이미 구한 잠정적인 이동벡터의 값과 합하여 벡터를 수정하는 방식으로 진행된다. 이에 따라, HBMA는 이동보상보간방식에서 요구하는 이동벡터의 정확도를 만족시킨다. 그러나, HBMA는 계산량이 상대적으로 많기 때문에 실시간 특성을 만족시키기 어렵다. 따라서, HBMA의 실시간 특성을 만족시키기 위하여 HBMA를 위한 병렬 컴퓨터 구조가 요구되지만, 병렬 VLSI 컴퓨터 구조가 많이 연구되어 있는 BMA에 반하여 상대적으로 연구가 적게 되어있는 분야이다. 본 논문에서는 병렬처리의 장애요소인 HBMA의 내재된 데이타 종속성을 연구하였고, 이들을 계층간 데이타 종속성과 계층내 데이타 종속성의 두가지로 정의하였다.
본 논문에서는 HBMA의 실시간 처리성능을 얻기위하여 시스톨릭 배열을 기반으로한 파이프라인식 VLSI 컴퓨터구조를 제안한다. 우선, 일반화된 파이프라인식 VLSI 컴퓨터 구조를 제안한다. 이 구조는 r 개의 스테이지로 구성되어 있으며, 각 스테이지는 HBMA의 한 계층에 해당된다. 각 스테이지에는 블럭비교를 수행하는 시스톨릭 배열구조, 이중 선형보간을 수행하는 보간기, 그리고 이동벡터의 잠정결과를 관리하는 래치로 구성되어 있다. 또한 이동벡터를 구하는데 필요한 이미지 데이타를 저장하기 위한 내부 메모리도 포함되어 있다. HBMA의 내재된 자료 종속성을 만족시키기 위하여 파이프라인 형식, 래치, 및 보간기가 정교하게 설계되었다.
데이타 종속성의 개념은 이동벡터의 잠정결과가 지정된 시간에 지정된 구성요소에 전달되는 것을 내포하고 있기 때문에 잠정결과들이 특정 순서를 따라서 흘러다녀야된다. 기본적으로 한 이미지 프레임은 줄 단위로 구성되어 있기 때문에, 이 특성을 기반으로하여 다음과 같은 두가지 자료흐름의 순서가 가능하다. 즉, 지그재그 모양의 순서(이를 래스터스캔 순서라 한다)와 리을자 모양의 순서(이를 뱀형 순서라 한다)가 있다.
이러한 두 자료흐름의 순서에 입각하여, 본 논문에서는 세 스테이지를 가지는 파이프라인식 VLSI 컴퓨터구조를 제안한다. 이 컴퓨터구조들은 일반화된 파이프라인식 VLSI 컴퓨터구조를 HBMA에서 주어진 인수에 따라 특정화시킨 것이다. 래스터스캔 순서를 따르는 R-Architecture를 설계하였고, 뱀형 순서를 따르는 S-Architecture를 설계하였다.
이들 두 파이프라인식 VLSI 컴퓨터구조에 대한 성능을 분석하였다. 성능분석의 결과로서 두 컴퓨터 구조가 모두 방송형 비디오 형식까지는 현재의 VLSI 기술로 실시간 처리성능을 보였고, HDTV 비디오 형식은 곧 상용화될 VLSI 기술로 실시간 처리가 가능함을 보였다. 또한, 가정한 파이프라인되지 않은 VLSI 컴퓨터구조와 비교하여 추가적인 하드웨어 비용없이 거의 선형적인 속도향상을 얻었다. 한편, S-Architecture는 R-Architecture보다 약 절반의 데이타 입력용 핀 갯수를 줄인반면, 제어회로가 더 복잡한 특성을 보였다.
