효율적인 움직임 추정을 위한 고속 블록 정합 알고리듬의 적응적 선택

Abstract

MPEG-1/2/4, H.264/AVC와 같은 영상압축표준에서 사용되는 부호화 기술은 크게 움직임 추정 및 보상, 이산직교변환(DCT)을 이용한 변환 및 양자화, 엔트로피 부호화로 구성되는 기본구조를 가지고 있다. 영상의 부호화 과정에서 움직임 추정 및 보상은 부호기의 복잡도 즉, 전체 부호화 시간에 가장 큰 영향을 미친다. 영상 코덱에서 일반적으로 사용되는 Full Search 기법은 최적의 정합 블록을 찾기 위해 탐색 영역내의 모든 위치에서 SAD값을 비교하기 때문에 부호화 시간을 다량으로 소비하게 된다. 이런 문제를 개선 하기 위한 초기기술들에는 TSS, NTSS, FSS, DS, BBGDS 등이 있으며, 이는 다양한 형태의 탐색 패턴을 활용하여 초기 탐색 지점을 (0,0)로 시작해서 최적의 정합 블록을 찾아내는 방법들이다. 가장 대표적인 탐색 기법인 다이아몬드 탐색 기법과 같은 경우 다른 종래의 고속 블록 정합 기법들보다 좋은 화질을 가질 수 있지만 초기 탐색에서 방향성을 고려하지 않고 현재 블록과 후보 블록을 비교를 함으로서 하나의 움직임 벡터를 찾기 위해 비교해야 할 탐색점의 수가 많아진다는 것을 알 수 있으며 다양한 형태의 탐색 패턴들은 영상의 움직임 정도에 따라 장단점을 가지게 됨을 알 수 있다. 그래서 다이아몬드 탐색 기법을 기초로 한 향상된 십자 다이아몬드 탐색 기법과 향상된 십자 다이아몬드 육각 탐색 기법을 제안하여 기존의 고속 블록 정합 기법들과 비교하여 탐색 속도를 향상시켰으며 현재 블록에 이웃하는 블록의 Motion Vector의 길이, 탐색점의 수, SAD를 이용하여 다이아몬드 탐색 기법, 십자 3단계 탐색 기법 그리고 향상된 십자 다이아몬드 탐색 기법 혹은 향상된 십자 다이아몬드 육각 탐색 기법을 적응적으로 사용하는 알고리듬을 제안하여 많이 알려진 다른 고속 움직임 추정 방법과 비교할 때 비슷한 화질을 가지면서 탐색점의 수를 감소시킴을 알 수 있다.; In video standards such as MPEG-1/2/4 and H.264/AVC, the coding technique consists of motion estimation / compensation(ME/MC), Discrete Time Transform(DCT) based transform, quantization and entropy coding. Among these techniques, ME/MC process causes the most encoding complexity of video encoder. The full search method, which is used in general video codes, exhausts much encoding time because it compares current macroblock with those at all positions within search window for searching a matched block. For the alleviation of this problem, the search methods such as TSS, NTSS, DS and HEXBS, which search an optimal matching block with various search patterns from initial search point (0, 0), are exploited at first. Even though the DS algorithm that is the most well-known algorithm has faster and better quality than other fast block matching algorithms, doesn’t consider direction when performs matching previous block and current block. For this reason, we know that the DS algorithm has unnecessary search points for searching an optimal matching block and various search patterns have advantages and disadvantages depending on the movement of video. So we propose the Enhanced Cross Diamond Search algorithm(ECDS) and the Enhanced Cross Diamond Hexagonal Search algorithm(ECDHS) based on the DS algorithm and experimental results show that the proposed algorithms are faster searching optimal matching blocks than other fast block matching algorithms. In addition, we propose another algorithm that is using length of the MV, Search Point, SAD of the neighboring block and adaptively selecting among Cross Three Step Search algorithm(CTSS), the DS algorithm, and Upgraded Cross Diamond Search(UCDS) or Enhanced Cross Diamond Hexagonal Search Algorithm(ECDHS) and experimental results of the proposed algorithm show that the proposed algorithm is much more robust and provides a faster searching speed than other popular fast block-matching algorithms.