In block motion estimation, search patterns with different shapes or sizes and the cross-center-biased characteristics of motion-vector distribution have a large impact on the searching speed and quality of performance. The cross-diamond search (CDS) algorithm was designed to fit the cross-center-biased characteristics of motion-vector distribution in real-world video sequences. Two improved versions of the CDS were proposed recently: the kite-cross-diamond search (KCDS) algorithm and the cross-diamond-hexagonal search (CDHS) algorithm. Our proposed algorithm employs a new scheme to find small motion vectors with the smallest checking points and proposes two novel search patterns (modified large diamond-shaped patterns (1VILDSPs) and large kite-shaped patterns (LKSPs)) so as to reduce checking points efficiently for large motion vectors without falling into the local minima. The speed improvement of the proposed algorithm can be up to 61% faster than the diamond search (DS) algorithm, 44% faster than the CDS, 25% faster than the CDHS, and 13% faster than the KCDS while providing similar prediction accuracies. This algorithm is especially suitable for videoconferencing applications.
블록 정합 기법은 H.261, H.263, H.264, MPEG-1, MPEG-4와 같은 동영상 압축 표준들에서 공통적 사용되는 방법으로 이웃한 화면간에 존재하는 정보의 시간적 중복성을 활용하여 동영상을 압축한다. 가장 널리 사용되는 블록 정합 기법은 전역 검색 기법이지만 (Full Search: FS) 이 기법은 매우 많은 연산량을 요구하기 때문에 여러 실시간 동영상 응용 분야들, 특히 소프트웨어 기반 동영상 압축에서 사용되기에 부적합하다. 연산량을 줄이기 위해서 많은 고속 블록 정합 기법들이 제안되어져 왔고, 이들은 기준 영상에서 최적 정합 블록을 찾기위해 사용되는 후보 블록들의 개수를 제한함으로써 부최적화 해결책을 찾아내었다.
기존 고속 기법들중에서 다이아몬드 검색 기법은 (Diamond Search: DS) 알고리즘의 속도와 정확도의 측면에서 다른 기존 기법들보다 성능이 뛰어났었고, MPEG-4의 검증 모델에서 채택되기도 하였다. 최근에는 십자가 다이아몬드 검색 기법 (Cross-Diamond Search: CDS), 연 십자가 다이아몬드 검색 기법 (Kite-Cross-Diamond Search: KCDS), 십자가 다이아몬드 육각형 검색 기법과 (Cross-Diamond-Hexagonal Search: CDHS) 같이 다이아몬드 검색 기법을 검색 속도 측면에서 개선한 기법들이 소개되었다.
본 논문에서 제안된 기법은 크게 세 가지 단계로 나뉠 수 있다. 첫 번째는 크기가 작은 움직임 벡터들을 검색하는 단계이고, 두 번째 단계는 최적 움직임 벡터의 크기를 예측하는 단계, 마지막 단계는 크기가 큰 움직임 벡터들을 검색하는 단계이다.
크기가 작은 움직임 벡터들을 검색하는 새로운 기법, 즉 작은 다이아몬드 모양 패턴을 (Small Diamond-Shaped Pattern: SDSP) 최적 정합점이 패턴의 중심점이 될 때까지 지속적으로 사용하는 기법을 제안하였다. 이 기법은 크기가 작은 움직임 벡터들을 가장 빨리 검색할 수 있다.
이렇게 크기가 작은 패턴을 지속적으로 이용할 때, 만약 최적 움직임 벡터의 크기가 크다면 긴 검색 경로 혹은 국보 최소점에 빠지는 경우를 야기할 수 있다. 그래서 작은 패턴을 지속적으로 이용하기 전에 최적 움직임 벡터의 크기를 예측하여 그에 맞게 패턴의 크기를 정하는 것이 필요하다. 이를 위해 큰 연 모양 패턴이 (Large Kite-Shaped Pattern: LKSP) 제안되었다.
크기가 큰 최적 움직임 벡터를 보다 빨리 검색하기 위해서 왜곡 표면은 단조 증가하거나 단조 감소하는 특징을 가지고 있다라는 기본 가정 아래에서 수정된 큰 다이아몬드 모양 패턴이 (Modified Large Diamond-Shaped Pattern: MLDSP) 제안되었다.
모의 실험 결과를 통해 제안된 기법은 기존 기법들, 즉 DS, CDS, KCDS, CDHS와 비교했을 때 정확도의 측면에서는 거의 비슷하지만, 속도 측면에서는 가장 빠른 성능을 보여줌을 확인할 수 있었다.
