Computation-aware scheme for software-based block motion estimation

Many fast block-matching algorithms (BMAs) reduce the computational complexity of motion estimation by sophisticatedly inspecting a subset of checking points, and stop only when all those checking points have been examined. This means that the searching process for each current block cannot be interrupted, even when it is performed in a software-based computation environment. Our main goal is to allow the searching process to stop once a specified amount of computation has been performed. A novel computation-aware scheme is proposed, which first dynamically determines the target amount of computation power allocated to a frame, and then allocates this to each block in a computation-distortion-optimized manner. We propose a rate-control-like procedure and a predicted computation-distortion benefit heuristic to realize this scheme. Conventional BMAs, such as full-search block matching, three-step search, new three-step search, four-step search, and diamond search, can be transformed into their corresponding computation-aware BMA versions. In our simulations, the resulting computation-aware BMAs not only exhibit higher efficiency than conventional BMAs, but also allow the motion estimation to terminate after any specified amount of computation has been performed (in units of checking points).