방향 지향적 탐색 순서를 적용한 전영역 고속 탐색 알고리듬

Abstract

MPEG-1/2/4, H.264/AVC와 같은 영상압축표준에서 사용되는 부호화 기술은 크게 움직임 추정 및 보상, 이산직교변환(DCT)을 이용한 변환 및 양자화, 엔트로피 부호화로 구성되는 기본구조를 가지고 있다. 영상의 부호화 과정에서 움직임 추정 및 보상은 부호기의 복잡도 즉, 전체 부호화 시간에 가장 큰 영향을 미친다. 움직임 추정 및 보상 과정은 영상의 화질 손상을 감안하여 고속으로 예측하는 방식(Lossy Motion Estimation Algorithm)과 화질의 저하 없이 움직임 예측의 계산량을 줄이는 방식(Lossless Motion Estimation Algorithm)이 있다. 본 논문은 화질의 저하 없이 움직임 예측에 필요한 계산량을 줄이는 알고리듬을 제안한다. 움직임이 적은 영상뿐 아니라 움직임이 많은 영상에서도 효율적인 움직임 예측을 하기 위해 영상의 움직임 특성을 이용한다. 먼저 초기 문턱 값을 계산함에 있어서 확장된 예측기를 사용하여 보다 최소값에 근사한 문턱값을 계산한다. 그리고 탐색영역을 블록으로 세분화 한 후 각 영역을 새로운 탐색 순서에 따라 움직임 예측을 수행하고 방향성에 따라 영역을 재분할한다. 재분할된 영역이 가지는 방향성에 따라 방향 지향적인 탐색 순서를 적용한다. 실험 결과에서 제안하는 알고리듬이 기존의 나선형 전영역 탐색 알고리듬에 비해 객관적인 화질의 열화 없이 계산량이 감소하는 것을 확인할 수 있다.; In video standards such as MPEG-1/2/4 and H.264/AVC, the coding technique consists of motion estimation / compensation(ME/MC), Discrete Cosine Transform (DCT) based transform, quantization and entropy coding. Among these techniques, ME/MC process causes the most encoding complexity of a video encoder. The full search method, which is used in general video codecs, exhausts much encoding time because it compares current macroblock with those at all positions within a search window for searching a matched block. There are two groups of ME/MC; One is Lossy Motion Estimation Algorithm which can reduce the loads of complexity with distortion of image quality and the other is Lossless Motion Estimation Algorithm which can reduce the computational load without image distortion. The fast full search algorithm is produced, reducing the computation of the block matching algorithm which is used for a motion estimation of the video coding. Since the conventional spiral search method starts searching at the center of the search window and then moves search point to estimate the motion vector pixel by pixel, it is good for the slow motion picture. However, the efficient motion estimation method was proposed, which is good for the fast and slow motion picture. Firstly, when finding the initial threshold value, an expanded predictor is used, which can approximately calculate a minimum threshold value. The proposed algorithm estimates the motion in the new search order after partitioning the search window and adapts the directional search order in the divided search window. At the result, it can be verified that the proposed algorithm reduces the computation compared with the conventional spiral full search algorithm without any loss of image quality.