Reused sad for partial search area in efficient three-step search algorithm

In real-time applications, three-step search (TSS) is always preferred because it has a regular search pattern. However, it may lose its performance in coding video sequences with small motion. To overcome this drawback, some fast search algorithms are proposed, for example, new three-step search (NTSS) and efficient three step search (ETSS). In this paper, a more effective fast search algorithm called region-split three-step search (RSTSS) is proposed. In addition to the feature of a regular search pattern, the RSTSS splits the search region into four sub-regions and enters only one of the sub-regions to search for the best motion vector. The main idea used in the RSTSS is to reuse the sum of absolute difference (SAD) values of the 9 points on a 9 ×9 grid. Experimental results show that the RSTSS performs better than the ETSS in terms of the number of checking points. It can reduce the number of checking points nearly 19% on average and sacrifices only a little mean squared error. Most of all, the RSTSS retains a regular searching pattern that is suitable for hardware implementation.