Fast Motion Estimation Algorithms based on Bit-wise Matching Criteria for Video Coding

Abstract

Motion estimation (ME) has been widely used in many video applications such as video compression, video segmentation, and video tracking to reduce the inherent temporal redundancy of the video sequence. The ME is usually regarded as the computationally most intensive part, performing up to 70% computations of the encoding system. The most popular technique for ME is block matching algorithm (BMA) which is deployed in many video compression standards because of its simplicity and effectiveness. In BMA, a frame is partitioned into a number of rectangular blocks and a motion vector for that block is estimated within its search range in the reference frame by finding the closest block of pixels according to a certain matching criterion such as the sum of absolute differences (SAD) or the sum of squared differences (SSD). The full search BMA (FSBMA) can give optimal estimation of motion in terms of minimal matching error by checking all the candidates within the search range, but the prohibitively huge computational complexity makes it impractical for the real-time video applications. Thus, many techniques have been proposed to reduce the high computational complexity of the FSBMA. The techniques that reduce the computational complexity of the FSBMA can be classified into two groups: fast searching techniques and fast matching techniques. These techniques can be either lossy or lossless in the sense that the accuracy of the ME is the same as the FSBMA or not with respect to the corresponding matching criterion. Lossy techniques are in general faster than lossless techniques at the expense of the coding efficiency. And, these techniques can be classified according to the repective matching criterion, for exaple, SAD, SSD, the number of non-matching points (NNMP), etc. In this dissertation, we investigate efficient ways to calculate the motion vector. In detail, we propose a novel sorting-based PDE algorithm for fast lossless matching ME, which is called fast full search with sorting by mean-subtracted distance (FFSMSD). By analyzing the contributions to the true sum of absolute differences (SAD), we find that there is a close relationship between the distances from the mean value of the current block and the contributions to the true SAD. By sorting the distances from the pixels to the current block, and applying this order to the typical PDE, we can eliminate impossible candidates faster and save substantial computations. By exploiting the other matching criterion, we propose improved two-bit transform-based ME algorithms by extending the typical two-bit transform (2BT) matching criterion, enhancing the ME accuracy with almost the same computational complexity, while preserving the binary matching characteristic. The successive elimination algorithms for 2BT based ME and the variations of the proposed 2BT are proposed. And a fast FSBMA for 2BT based on the reverse triangle inequality is proposed. By mathematically deriving the lower bound for 2BT based matching criterion, we can discard the impossible candidates earlier and save computations substantially. We also provide the fast lossless searching algorithms for the proposed algorithms which exploit the other matching criteria. And by exploiting almost the identical operations in two different matching error criteria, a low complexity weighted 2BT based multiple candidate ME algorithm is proposed. We can efficiently determine two best motion vectors according to the respective matching criteria and can enhance the overall motion estimation accuracy. We also propose a novel matching criterion compensated by the DC difference. Using this modified matching criterion and sacrificing the binary matching characteristic, we can enhance the overall ME accuracy significantly.