Hardware Design And Simulation For Efficient Three-Step Search Algorithm For Motion Estimation

Block-based motion estimation is the key technique of video coding which can reduce the temporal redundancies of sequences to make compression efficient. The optimal solution could be obtained with full search algorithm, but its realization needs massive computation. Many fast block-based motion estimation algorithms have been proposed to reduce the computational complexity, for examples, three-step search, four-step search, new three-step search, etc. Most of the fast block matching algorithms are based on the assumption that the block distortion measure increases monotonically as the check point moves away from the global minimum block distortion measure point. However, this is not always true in the real world especially for large motion blocks where multiple local minimum within the search window. An efficient three-step search has been proposed, which employs a center-biased small diamond pattern based on the three-step search and the unrestricted search step to search the center area. Simulation results show that the efficient three-step search performs well than new three-step search for different search range and motion and requires less computation by up to 15% on average. This paper mainly study how to complete the hardware architecture design and simulation for efficient three-step search.The efficient three-step search uses two different search patterns: square pattern and small diamond pattern. This paper presents an architecture based-on shift register array, which can be used for the search for the two search pattern simultaneously. This architecture was inspired by the VLSI architecture for diamond-search-pattern-based algorithms. It exploits the overlap of reference data among the search points to reduce data memory accesses which are the most power consuming operations.The register transfer level design with Verilog HDL for the proposed architecture has been completed, and function simulation has also been accomplished in ModelSim. Four benchmark test sequences was used for the simulation, and the average number of cycles required to process a frame of the proposed architecture and average number of reference memory access required per frame has been computed. The results show that the average number of cycles required to make a block matching for different test sequences is 256, which is smaller than the architecture implemented with the diamond search and fulfills the speed requirement of MPEG-2 and HDTV standards when the clock speed is 70MHz. In addition, the proposed architecture also performs well than the architecture implemented with the diamond search in terms of reference memory accesses, it reduces the number of reference memory accesses required by more than 70% in comparison to the straightforward processing of the search points, and it's suitable for low power application.