Algorithm and architecture design of sorting-based motion estimation algorithm for wireless video applications

This paper adopts a new block matching motion estimation algorithm and its VLSI architecture design. The proposed sorting-based algorithm (SBA) was derived from multi-level successive elimination algorithm (MSEA), which can skip unnecessary sum of absolute difference (SAD) calculation by comparing minimum SAD with multi-level SEA (msea). The proposed algorithm sorts the value of multi-level successive elimination algorithm (MSEA) and uses conditions to skip impossible search positions. We proposed an architecture which consists of a pixel sum calculator to compute sub-blocks pixel sum, an msea/SAD tree to support both msea and SAD calculations, and a sorter to efficiently calculate the value of msea. The simulation results show that our algorithm has lower computational complexity and the same values of peak signal noise ratio (PSNR) which compared to full search block matching algorithm (FSBMA). And, the average search points of each block is 47 only. Its computational complexity is only 4.59% of FSBMA's.