Page 192 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience
P. 192
Section 7.7. Fast Full-Search Techniques 169
The )rst summation in this inequality is the sum norm of block B in the
current frame, and this sum is denoted SN t . The second summation, on the
other hand, is the sum norm of a candidate block in the reference frame
shifted by (i; j), and this sum is denoted SN t−Mt (i; j). The third summation is
obviously the SAD(i; j). Thus, for simplicity, Inequality (7.2) can be rewritten
as
|SN t − SN t−Mt (i; j)|≤ SAD(i; j): (7.3)
Now assume that during a full-search, the minimum SAD calculated so far is
SAD(i m ;j m ) at search location (i m ;j m ). A subsequent search location (i; j)is
said to achieve better match only if SAD(i; j) ≤ SAD(i m ;j m ). Put in another
way, and based on Inequality (7.3), a subsequent search location (i; j) is said to
achieve better match only if |SN t −SN t−Mt (i; j)|≤ SAD(i m ;j m ). In other words,
a subsequent location (i; j) can be immediately skipped from the search if
|SN t − SN t−Mt (i; j)|≥ SAD(i m ;j m ): (7.4)
Note that calculating the sum norms in this inequality has a reduced-complexity
compared to calculating the SAD(i; j) itself. For example, assume that B(x; y)
is an N × N block with its top-left cornet at (x; y) and that the next block
B(x +1;y) is the block obtained by moving one pel to the right. The two
blocks are overlapping and they share N − 1 columns. Once the sum norm,
SN(B(x; y)), of the )rst block is calculated, the sum norm, SN(B(x +1;y)),
of the next block in the line is obtained simply by substracting the sum norm
of the )rst column of block B(x; y) and adding the sum norm of the last
column in block B(x +1;y). A similar procedure can be used for calculating
the sum norm of the next block in the column (i.e., when moving one pel
down). Based on these ideas, a very fast method of calculating the sum norms
is presented in Ref. 162.
A similar algorithm to the SEA has also been proposed in Ref. 164. Assume
�
that B is partitioned into subsets B n such that B = n B n and n B n = ∅.
Then the triangular inequality becomes
�
|SN t;n − SN t−Mt;n (i; j)|≤ SAD(i; j); (7.5)
n
where SN t−Mt;n (i; j) is the sum norm over subset B n of the candidate block
in the reference frame shifted by (i; j). It can be shown that
�
|SN t;n − SN t−Mt;n (i; j)|≥|SN t − SN t−Mt (i; j)|: (7.6)
n
Thus, a tighter bound is achieved when the partitioned case is used in In-
equality (7.4) instead of the partitioned case. This tighter bound will result