Cellular search algorithm for motion estimation

This paper presents a novel cellular search (CS) algorithm for block-matching motion estimation. The algorithm employs two search patterns, namely the large cellular search pattern (LCSP) and the small cellular search pattern (SCSP), to search the best matching block. The LCSP assumes that the best matching block can be located at any direction of the LCSP center, and hence every possible direction of the motion vector is explored. Subsequently, the SCSP is used to search those nearby the center block. Comparison studies have been conducted for the CS: the three-step search (TSS), the new three-step search (NTSS), and the four-step search (4SS), and the results all indicated that the number of blocks searched via LCSP search is less than other algorithms. The CS algorithm is more computationally efficient, as it requires less computation time than other algorithms