Video compression plays an important role in transmission and storage of digital video data. The main idea to achieve compression is to remove temporal and spatial redundancies existing in video sequences. One effective method commonly used in reducing temporal redundancy is motion-compensated predictive coding. The essential part in motion-compensated coding is motion estimation. Block matching algorithm (BMA) has been widely used as a motion estimation technique in most video coding systems due to its simplicity. Its goal is to find a block that is most similar to a current block within a pre-defined search area in the previous frame. As a straightforward method, the full search BMA (FSBMA) is widely used because of its high performance and low control overhead. Usually, FSBMA is the most time consuming part in a video encoder. This heavy computational load limits the performance of encoder in terms of encoding speed and power consumption. Meanwhile, many VLSI architectures for FSBMA have been reported previously. However, due to their high computational complexity, VLSI architectures for FSBMA usually require a large number of gates and high memory bandwidth for real time applications. In order to reduce the heavy computational load of FSBMA, active research has been focused on fast BMAs for a long time. A software solution is attractive from the viewpoint of cost effectiveness and flexibility. In software implementation for real time applications, a gradient descent approach is a good candidate due to its high speed up improvement compared to other approaches. In the other side, hardware implementation of motion estimation is also important for portable multimedia devices. In this case, to reduce manufacturing costs, such as silicon size and I/O bandwidth, a low complexity BMA suitable for hardware implementation and corresponding efficient VLSI architecture are also necessary. In hardware implementation, a multi-resolution approach is a good candidate due to its high PSNR performance and regular structure. In this dissertation, we deal with two issues, one is a fast motion estimation algorithm for software approach and the other is an area-efficient VLSI architecture of motion estimation for low bit-rate video coding. As the first issue, a fast BMA, which is called the Feature Assisted Search Technique for Motion Estimation (FASTME), is presented by adopting a simple gradient descent search that is combined with a feature matching. The proposed algorithm utilizes a new search strategy, namely, one-dimensional feature matching based on selective integral projections. This low complexity procedure assists a local search around the search center so that the small diamond search pattern and other more compact search patterns are enough to find the global minimum point. Compared with recent fast search algorithms, the proposed algorithm has lower computational complexity and provides better prediction performance. Secondly, for a hardware solution, an area-efficient VLSI architecture of a multi-resolution BMA is presented for low bit-rate video coding applications. Since this architecture requires small number of processing elements (PEs) and a small size on-chip memory, it can be implemented with a much smaller number of gates than other conventional architectures for full search BMA while keeping a negligible degradation of coding performance. Moreover, the proposed motion estimator can support an advanced prediction mode (8×8 prediction mode) for H.263 and MPEG-4 video encoding. We implement this architecture with about 25K gates and 288 bytes RAM for a search range of [-16.0, +15.5] by using a synthesizable VHDL.
디지털 비디오 데이타의 효율적인 전송과 저장을 위해서 다양한 응용 분야를 목적으로 한 H.263, MPEG-1, MPEG-2, MPEG-4 등의 여러 가지 동영상 압축 국제 표준들이 개발되어 왔다. 동영상을 압축하는데 사용되는 주된 원리는 동영상에 존재하는 시간적, 공간적인 중복성을 제거하는 것이다. 공간적인 중복성을 제거하기 위해 가장 널리 사용되는 효과적인 방법은 움직임 보상 부호화 방식 (motion compensated predictive coding)이다. 움직임 보상 부호화 방식의 비디오 코덱에서 가장 핵심적인 부분은 움직임 추정 (motion estimation)이다. 대부분의 동영상 압축 표준들에서는 움직임 추정을 위해 간단한 연산을 사용하는 블록 정합 기법 (block matching algorithm: BMA)을 채택하였다. 블록 정합 기법은 현재 프레임의 블록과 가장 유사한 블록을 이전 프레임의 미리 정의된 일정한 크기의 탐색 영역 내의 후보 블록들 중에서 찾아내는 것이다. 일반적으로 생각할 수 있는 전역 탐색 (Full search)은 높은 성능을 나타내지만 과도한 계산량을 필요로 한다. 따라서 움직임 추정 부분이 전체 동영상 부호화기에서 가장 많은 시간이 소요되는 부분으로 전체 코덱의 속도나 전력 소모에 큰 영향을 미치게 된다. 한편, 전역 탐색을 위한 많은 VLSI 구조가 제안되어 왔지만 과도한 계산량으로 인해 실시간 응용 분야의 적용을 위해 구현할 경우 칩 사이즈가 크거나 메모리 대역폭이 커지는 단점들이 있다. 이러한 이유들로 전역 탐색의 과도한 계산량을 줄이기 위해서 많은 연구들이 진행되어 왔다. 본 논문에서는 두 가지 접근 방식에서 움직임 추정 알고리즘을 다룬다. 첫번째 접근 방식은 소프트웨어적인 구현이다. CPU나 DSP 등의 연산 처리 능력이 높아짐에 따라 저 전송률 응용 분야를 위한 H.263이나 MPEG-4 등의 구현은 고속 움직임 추정 알고리즘을 이용한 소프트웨어만으로도 가능하게 되었다. 소프트웨어 솔루션은 유연성, time-to-market, 비용 측면에서 상당히 매력적이다. 소프트웨어 솔루션을 위해서는 PSNR 성능도 높고 속도 향상 비율도 매우 높은 경사 강하 탐색 (gradient descent search: GDS) 방식이 좋은 후보가 될 수 있다. 본 논문에서는 간단한 GDS 방식과 특징 정합 (feature matching)을 결합한 특징 기반 탐색 기법 (Feature assisted search technique for motion estimation: FASTME)을 제안한다. 제안된 알고리즘에서는 새로운 탐색 기법인 선택적 가산 투영 (selective integral projections)을 이용한 1차원 특징 정합 기법 (1-D feature matching: 1DFM)을 사용한다. 1DFM은 적은 계산량으로 탐색 중심점 주위 영역을 탐색 가능하게 함으로써 탐색 절차를 돕는다. 제안된 고속 움직임 추정 알고리즘은 기존의 다른 방식들과 비교할 때 비슷하거나 더 나은 성능을 가지면서 훨씬 더 적은 계산량을 필요로 한다. 두 번째 접근 방식은 하드웨어적인 구현이다. PC 기반이 아닌 휴대용 멀티미디어 단말 등에서는 움직임 추정을 위한 하드웨어 솔루션이 필요하다. 이 경우 제조 비용을 줄이기 위해서는 하드웨어 구현에 적합한 고속 움직임 추정 알고리즘과 거기에 적합한 VLSI 구조가 필요하다. 이러한 하드웨어 솔루션을 위해서는 높은 PSNR 성능과 규칙적인 구조를 가진 다해상도 탐색 (multi-resolution search)방식이 좋은 후보가 될 수 있다. 본 논문에서는 저 전송률 동영상 압축을 목표로 한 다해상도 움직임 추정 알고리즘에 적합한 VLSI 구조를 제안한다. 제안된 구조는 적은 수의 PE (processing element)와 작은 사이즈의 내부 메모리를 필요로 하기 때문에 기존의 다른 구조에 비해 작은 수의 게이트로 구현 가능하다. 또한, H.263이나 MPEG-4 등의 advanced prediction mode를 지원한다. 제안된 VLSI 구조는 하드웨어 기술 언어인 VHDL을 사용하여 25K 정도의 게이트와 288바이트의 RAM으로 구현 가능하였다.
