Block matching algorithm

A Block Matching Algorithm (BMA) is a way of locating matching blocks in a sequence of digital video frames for the purposes of motion estimation.

The purpose of a block matching algorithm is to find a matching block from a frame i in some other frame j, which may appear before or after i. This can be used to discover temporal redundancy in the video sequence, increasing the effectiveness of interframe video compression.

Block matching algorithms make use of criteria to determine whether a given block in frame j matches the search block in frame i

위키피디아를 검색하면 BMA에 관해서 위와 같은 설명이 나옵니다.
제가 연구하는 motion estimation에 있어서 핵심과도 같은 존재가 바로 BMA입니다.
현재 macroblock과 가장 잘 matching이 되는 block을 search window안에서 찾고 그에 해당하는 위치를
motion vector로 표현하고 이를 인코딩해서 전달하는 것이죠.

BMA에서 "가장 잘 matching"되는 것을 판단하기 위한 criteria는 보통 SAD (sum of absolute differences) 혹은
SSE (sum of squared error) 를 주로 사용합니다.

중요한 것은 BMA가 ME에서 가장 시간을 맞이 소비하는 부분이므로 이를 빨리 하는 것이 중요합니다.
BMA에는 찾고자 하는 search window의 크기가 시간에 절대적으로 영향을 미치기도 하지만,
BMA 자체의 알고리즘도 중요합니다.

Full-search는 exhaustive하게 찾는... 즉 한 pixel씩 움직이면서 찾는 것인데요. 압축 효율면에서는 우수하지만
시간이 가장 오래 걸리는 알고리즘입니다. (하드웨어의 구현이 용이하기 때문에 대부분의 HW 인코더에서는 FS를
씁니다.)

저는 현재 SVC를 하고 있는데, 하드웨어보다는 소프트웨어를 주로 사용할 예정입니다.
(나중에 후배와 함께  nVidia의 CUDA를 써서 가속하는 것도 생각중입니다만... )
어찌되었든 SVC의 레퍼런스 소프트웨어인 JSVM에는 TZSearch라는 것이 구현되어 있습니다.
이를 사용하면 20~30배 정도 FS 보다 빨라집니다. 하지만 현재 참조할 논문이나 기사를 찾지 못해서 해매다가
JVT에서 표준화에 큰 기여를 한 분께 메일을 보내서 도움을 줄 수 있는 사람을 찾았습니다.
그분께서 TZSearch를 다음과 같이 설명해 주셨습니다.

the block matching algorithm utilizes different search strategies
depending on the location of the best match found so far.
The search starts with a test of some motion vector candidates (Mv's of
surrounding blocks). The best match is chosen as start location for an
initial diamond shaped search which is stopped in case the best match is
located near the start position. If a better match is found farther away
of the initial start position a so called raster search is triggered
that investigates the whole search area testing location with
equidistant interspace.
Finally the location of the best match is used as start position of the
closing refinement search.

자세히 읽어보진 않았습니다. ^^;
현재는 참조할 논문이나 기사에 대해서 알려 달라고 문의 해 놓은 상태입니다.
여기저기 막혀서 논문 진행이 느리네요.