Motion estimation is efficient to reduce redundant information among successive frames in video compression applications. The blocks in the current frame can be replaced with the neighboring blocks in the spatial directions in the previous frame with small errors. Many types of motion estimation methods such as Block matching algorithm are widely used to take a balance between a good image quality and the computation complexity. A block matching algorithm named as New Cellular Search Algorithm utilizes two particular search patterns: HCSP and VCSP, in the horizontal and vertical directions to search the best motion vector. Three performance measurements including PSNR), ASP, and MAE are used to compare this new search algorithm with some major motion estimations like FS, TSS, CS, and NCDS. The FCS is very efficient in computation reduction while keeping the almost same picture quality.