A block-based full search algorithm (FSA) has been widely used for motion estimation (ME) in video encoding, but it has the serious problem of significant computation requirements.1 In order to solve this problem, many fast algorithms have been developed, and partial difference elimination (PDE) algorithms1, 2, 3, 4 are good examples. PDE algorithms reduce computations by eliminating impossible candidates before the complete matching error calculation between matching and candidate blocks. PDE algorithms have also been improved by selecting a low initial block matching error1, 2 or arranging the line/sub-block matching order in a candidate block.3, 4 In this letter, we propose a fast PDE algorithm for reducing additional computational costs based on the property of block matching error. The proposed algorithm predicts a total block matching error from a partially computed matching error between the blocks and removes impossible candidates earlier than conventional algorithms. Simulation results show that the proposed algorithm can save a large amount of computations with ignorable image degradation in comparison with conventional PDE algorithms.
Conventional PDE Algorithms
The FSA finds the most similar block to a matching block within a given search range of the reference frame. The similarity between blocks is measured by the block matching error and is often computed by the sum of absolute difference (SAD) between matching and candidate blocks. In the PDE algorithm, the partial SAD , which is the matching error accumulated for every period, such as a block’s line3 or a sub-block,4 is computed and compared with the minimum block SAD . Once the is larger than the at each period, the candidate block cannot be the most similar block regardless of the rest of the incomplete matching computations. Therefore, the PDE algorithm can find and remove impossible candidates before the complete matching error calculation of the candidate block. In this letter, we follow the line-based SAD comparison. The accumulated matching error at the ’th line of a candidate block in the position of the given search range can be expressed byis the matching block size, and and indicate current and reference frames, respectively. To summarize the procedures of the conventional PDE algorithm, the approach computes the at every line of a candidate block, compares it with the , and then moves to the next line if the is less than the . It is noted that the is updated only when a complete matching error computation is finished if necessary.
The efficiency of the PDE algorithm can be improved when a small initial block matching error is selected or large line/sub-block matching errors occur early. A spiral PDE algorithm3 and a sorting-based PDE algorithm4 are typical examples, respectively, and they are compared with the proposed PDE algorithm for performance evaluation.
Proposed Fast PDE Algorithm
The disadvantage of the PDE scheme is that the algorithm has to compute the of a candidate block for , which will be eliminated last, until the reaches . It is obvious that predetermination of the elimination will help in reducing the computational costs and increasing the process speed for the ME.
A fast PDE algorithm is proposed by predicting a total block SAD , which is equivalent to the . The proposed algorithm is based on the property that a is an intermediate value and is gradually increased to reach the because the is continuously accumulated as goes from 0 to . The prediction at the ’th line of a block is performed, whenever the for is less than the by using the , as follows:is an averaged line-matching error of , and is a weighted value determined by the complexity of a matching block to avoid an incorrect prediction. The incorrect prediction may be caused by a large , which is caused by large line-matching errors at the candidate blocks containing the complex image such as edges. So is selected in inverse proportion to the image complexities and defined by using an average of available in the neighboring blocks including the matching block, as follows:
The proposed approach computes a to predict the from the if the for is less than the and compares the predicted block SAD with the before the next line computation. Therefore, the proposed algorithm has a high possibility to eliminate impossible candidates earlier than the conventional approach because the always exceeds the . It is worth noting that the is adjusted adaptively according to the contents of each matching block because the accuracy of the prediction is affected by complexity of the block. We provide a practical example to show the procedures of the proposed algorithm in Fig. 1. First, a is computed and compared with a (see ① in Fig. 1). A is estimated because the is less than the and is compared with the . The (see ② in Fig. 1) is still smaller than the , and the algorithm goes to the next line. Similarly, a and a are calculated at the second line because the is less than the . However, the (see ③) is larger than the . Therefore, the proposed scheme skips the rest of the matching procedures for the current candidate block and goes to the next candidate, while the conventional PDE keeps performing the same procedures until the exceeds the at the seventh line (see ⑥). Consequently, the proposed algorithm requires only two line matching events, while the conventional algorithm requires seven line matching events.
The proposed PDE algorithm is simulated with various video sequences—Foreman, Stefan, Akiyo, Mobile, Container, Silent voice, News, and Table tennis—and they consist of 300 frames at in the format of QCIF. The matching block size is , and the search range is . The simulation results are compared with the spiral PDE algorithm 3 and the sorting-based PDE algorithm .4 It is noted that both the and the also employ a spiral scanning searching scheme, as the does. Table 1 shows the performance of the proposed algorithm with respect to PSNR and matching ability. It can be seen that the degradations in PSNR and matching ability are only and 0.66% (0.65 block in 99 matching blocks) average values, respectively. In Table 1, mismatched MV indicates the number of mismatched motion vectors in the proposed algorithm versus the corresponding motion vectors of the conventional PDE algorithm.
Comparisons with respect to image quality and prediction ability.
In order to evaluate the computational performance, the average checked line numbers per candidate block to determine its validity for three algorithms are summarized in Table 2. It is noted that the proposed scheme requires 1 addition, 1 division, and 2 multiplications more to estimate a total block matching error if necessary. The results in Table 2 show that the proposed method reduces computational cost on average 40% and 30% compared with the 3 and ,4 respectively. The efficiency value of the proposed approach versus the conventional PDE algorithm is defined byand are the conventional PDE and the proposed PDE algorithms, respectively.
Average checked line numbers per candidate block.
|Average checked lines|
In this letter, we proposed a fast PDE algorithm to reduce the computational cost of the conventional PDE algorithms. We predict a block matching error from a partial block matching error and remove the impossible candidates earlier using the predicted block matching error. The simulation results show that this can considerably reduce the computational complexity at the cost of negligible image quality degradation. We believe that the proposed approach can be applied to the conventional PDE algorithms without significant modifications and can play an important role as a significant tool for fast motion estimation.