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

• Published in: Journal of the Chinese Institute of Engineers 2007-05, Vol.30 (3), p.537-543
• Main Authors: Su, Chung-Yen, Hsu, Yi-Pin
• Format: Article
• Language: English
• Subjects: efficient three step search; real-time motion estimation; region-split three-step search
• ISSN: 0253-3839; 2158-7299
• DOI: 10.1080/02533839.2007.9671283

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.