Hardware Efficient Double Diamond Search Block Matching Algorithm for Fast Video Motion Estimation

Application of video in multimedia communication has become feasible due to efficient block matching algorithm (BMA) based motion estimation (ME) and motion compensation (MC) methods, that facilitate high data compression. To sustain visual quality of video, large amount of computation is involved in ME which can be reduced by fast search BMA and making fast search faster by various means like predicting initial search center (ISC) and early search termination. But more challenging work is to design an architecture which performs computation hungry search process in fewer clock cycles which will actually make fast search rapid for real time encoding. Implementations are available for matching multiple macroblocks in single clock cycle, but bottleneck is accessing macroblocks from memory while following sequential irregular search patterns of most of fast search algorithms. This paper proposes a novel, Hardware Efficient Double Diamond Search (HEDDS) algorithm which reaches far in search window more rapidly to identify best match and minimizes number of iterations of search pattern and hence diminish required clock cycles to read macroblocks from memory. From implementation perspective, HEDDS is up to 7.5 % to 33 % faster than existing BMAs and also offers reasonably good quality of encoding. With variable block size, HEDDS demonstrate average BD-PSNR improvement of 0.381, 0.088, 0.87 and 0.233 dB at BD-bitrate drop of 12.994 %, 2.499 %, 25.599 %, 6.887 % in comparison of HS, HMDS, LDPS and UMHS correspondingly. Proposed HEDDS architecture can process 259 HD frames per second in average case for fixed block size which is promising figure for real time encoding on devices having inadequate computational resources.