"Stick-Shaped Window Search (SSWS)" block matching algorithm for motion vector estimation

To significantly reduce the number of block-matching (BM) processes in motion vector estimation for HDTV, we have developed an extremely fast block matching (BM) algorithm that we call a "Stick-Shaped Window Search (SSWS)" BM algorithm for H.264/AVC. The algorithm consists of three steps: (1) sub-sampling BM in a reduced number of stick-shaped windows, (2) filternate eight-direction sub-sampling BM, and (3) cyclic small-diamond BM. For HDTV the algorithm not only improves full search (FS) processing speed by a factor of up to 2,716, but also that of a simplified unsymmetrical-cross multi-hexagon-grid search (S-UMHS) by a factor of up to 7.87, while achieving the same visual quality as that of FS.