Rapid block-matching motion estimation using modified diamond search algorithm

Due to the considerable computational complexity of full-search (ITS) in motion estimation, many suboptimal but fast block-matching algorithms (BMAs) have been developed. Among them, the diamond search (DS) series is the most promising method. To further reduce complexity and improve performance, we propose a modified diamond-search (MODS) algorithm for rapid block matching based on the well-known DS algorithm. A novel fine granularity halfway-stop (FGHS) method based on a dynamic block distortion threshold is also proposed. To avoid being trapped in local optima, unlike some small DS methods, MODS adaptively starts with a relatively large search pattern for high motion blocks which are automatically determined via the first block matching distortion. The threshold is obtained via a linear model utilizing already computed distortion statistics. Experiments show that the proposed algorithm achieves less search points with no significant PSNR degradation when compared to that of FS and other fast BMAs.