A Cross-Diamond-Triangle Search Algorithm for Fast Block-Matching Motion Estimation
Seong‐Hoon Kim, Jaemin Shin, Seoung‐Jun Oh, Chang‐Beom Ahn, Hochong Park, Donggyu Sim · Journal of Broadcast Engineering · 2005
In this Paper, we propose a new motion search algorithm called CDTS (Cross-Diamond-Triangle Search algorithm) that uses optimal search pattern according to the position of a search area to improve the performance of CDS(Cross-Diamond Search algorithm) as well as CDHSs(Cross-Diamond-Hexagonal Searches algorithms). We analyze motion distributions in various test video sequences to apply optimal search pattern according to a position of search area. Based on the result of this analysis, we propose a new triangle-shaped search pattern whose structure is asymmetric while previous search patterns are generally symmetric in conventional algorithms. In CDTS, we apply cross- and diamond-shaped search patterns to central search areas, and triangle- and diamond-shaped patterns to the other areas. Applying CDTS to test video sequences, the proposed scheme can reduce search points more than CDS and CDHSs by 16.22 and 3.09, respectively, without any visual quality degradation.