Full Search Block Matching

Full search block matching algorithm evaluates every possible pixel block in the search region. Hence. it can generate the best block matching motion vector. This type of BMA can give least possible residue for video compression. But, the required computations are prohibitive high due to the large amount of candidates to evaluate. The number of candidates to evaluate are $\left(2 S_{x}+1\right)^{*}(2 S y+1) .$ Hence, full search is typically not used. Also, it docs not guarantee consistent motion vectors required for video processing applications.

There are several other fast block-matching algorithms, which reduce the number of evaluated candidates yet try to keep a good block matching accuracy. Note that since these algorithms test only limited candidates, they might result in selecting a candidate corresponding to local minima, unlike full search, which always results in global minima.

Three Step Search

In a three-step search (TSS) algorithm, the first iteration evaluates nine candidates as shown in the figure below

The candidates are centered around the current position. The step size for the first iteration is typically set to half the search range. During the next iteration, the search center is shifted to the best matching candidate from the first iteration. Also, the step size is reduced by half. The same process continues till the step size becomes equal to one pixel. This is the last iteration of the three-step search algorithm.

The best matching candidate from this iteration is selected as the final candidate. The motion vector corresponding to this candidate is selected for the current block. The number of candidates evaluated during three- step search is very less compared to the full search algorithm. The number of evaluated candidate is fixed depending upon the step size set during the first iteration.

2D Logarithmic Search

2D Logarithmic search is another algorithm, which tests limited candidates. It is similar to the three-step search.

During the first iteration, a total of five candidates arc tested. The candidates are centered around the current block location in a diamond shape. The step size for first iteration is set equal to half the search range.

For the second iteration, the center of the diamond is shifted to the best matching candidate. The step size is reduced by half only if the best candidate happens to be the center of the diamond. If the best candidate is not the diamond center, same step size is used even for second iteration.

In this case, some of the diamond candidates are already. evaluated during first iteration. Hence, there is no need for block matching calculation for these candidates during the second iteration. The results from the first iteration can be used for these candidates. The process continue still the step size becomes equal to one pixel. For this iteration all eight surrounding candidates are evaluated. The best matching candidate from this iteration is selected for the current block. The number of evaluated candidate is variable for the 2D logarithmic search. However, the worst case and best candidates can be calculated.