A fast partial distortion-based motion estimation algorithm in Walsh–Hadamard domain

This paper proposes a fast partial distortion-based block matching motion estimation algorithm and its enhanced version in Walsh–Hadamard. The proposed algorithms divide the current block into sub-blocks and provide a sequence of fine-partial distortions to reject the impossible candidates using as less calculation as possible. In contrast to the previous algorithms in the Walsh–Hadamard domain, such as transform-domain successive elimination algorithm (TSEA) and multilevel transform-domain partial distortion search (MT-PDS) algorithm, these algorithms apply Walsh–Hadamard Transform (WHT) to only those sub-blocks that demand instead of entire block or all sub-blocks. In addition, unlike in the TSEA and MT-PDS algorithms, the number of additional transform coefficients required to calculate partial distortion at any level is constant and small. The simulation results show that the proposed algorithm reduces the computational cost of TSEA and MT-PDS algorithms while maintaining the motion prediction quality. Compared with the full search, 94.95% of the computational complexity is reduced by the proposed algorithm without any reduction in the motion prediction quality. Similarly, the proposed algorithm reduces the computational complexity of the TSEA and MT-PDS algorithms by 28.88% and 42.31%, respectively, without any loss in the motion prediction quality. The enhanced version reduces the computations of proposed algorithm significantly with a slight reduction in motion prediction quality.