이진 블록 매칭 움직임 추정을 위한 효율적인 탐색 알고리듬

Abstract

영상 압축은 제한된 용량과 제한된 대역폭을 가진 멀티미디어 환경에서 전송 데이터의 양을 줄이기 위해 필수적이다. 영상 압축을 위한 여러 가지 도구들 중 영상의 이웃하는 프레임간 시간적 중복성을 제거하여 압축의 효율을 높이는 움직임 추정(motion estimation) 방법이 가장 핵심적인 압축 기법이며, 전역 탐색 알고리듬(full search algorithm)이 블록 단위로 움직임 추정을 수행하는 블록 매칭 알고리듬(block matching algorithm)의 가장 보편적인 탐색 방법이다. 그러나 이러한 전역 탐색 방법은 블록 매칭을 위해 상당히 많은 복잡도를 요구하는 단점이 있다. 전역 탐색 방법의 매칭 연산 복잡도를 줄이기 위해 다양한 기법들이 연구되고 있으며, 그 중 하드웨어 구현 환경에서 블록 매칭을 위한 고속 탐색 방법을 제공하는 이진 블록 매칭 움직임 추정 방법이 제안되었다. 이진 블록 매칭 움직임 추정 방법이란 영상의 8비트 화소를 낮은 비트수로 변환하여 움직임 추정을 수행하는 방법이며 대표적으로 1비트 변환 및 2비트 변환을 이용하는 방법들이 있다. 1비트 변환 및 2비트 변환을 이용하는 움직임 추정 방법은 이진 변환된 영상들로 블록 매칭 움직임 추정을 수행하기 때문에 하드웨어 병렬처리 구조 및 고속 하드웨어 연산을 사용하여 8비트 영상의 전역 탐색 움직임 추정에 비해 연산의 복잡도를 효과적으로 감소시킬 수 있다. 하지만 이러한 이진 블록 매칭 움직임 추정 방법들은 정확성 저하를 야기한다. 이진 블록 매칭 움직임 추정 방법의 정확도를 개선하기 위해 조건부 국부 탐색 방법이 더해진 보완된 1비트 변환 및 보완된 2비트 변환 방법들이 제안되었다. 보완된 방법들은 기존 1비트 변환 및 2비트 변환을 이용하는 움직임 추정 방법에 추가적인 국부 탐색을 수행하여 정확성을 많이 향상 시켰다. 그러나 움직임이 빠른 영상에 대한 16×16 블록 크기의 움직임 추정에 있어서 많은 수의 추가적인 탐색을 필요로 한다. 본 논문에서는 이진 블록 매칭 움직임 추정 방법의 정확도를 개선하기 위해 제안된 추가 탐색 알고리즘을 좀 더 효율적으로 개선하기 위해 제안되었다. 기존 방법들에서 추가 탐색으로 사용하는 조건부 국부 탐색 방법 대신 탐색 범위내의 각 후보 블록들의 NNMP (Number of Non-Matching Points)를 기반으로 하는 탐색 방법을 제안한다. 제안된 NNMP 기반 탐색 방법으로 추가 탐색을 위한 후보 블록들을 수집하여 최종 움직임 벡터를 효율적으로 찾을 수 있다. 실험을 통하여 제안하는 알고리듬이 블록 매칭 복잡도 및 예측 정확도 측면에서 기존의 추가 탐색 알고리듬보다 좋은 성능을 보여주는 것을 확인하였다.