1 April 2007 Fast partial difference elimination algorithm based on block matching error prediction
Author Affiliations +
We introduce a fast partial difference elimination (PDE) algorithm for motion estimation (ME). The basic idea of the proposed approach is to eliminate invalid candidates earlier by predicting a total matching error between matching and candidate blocks. The matching error prediction is performed by using a partially computed matching error between the blocks. Experimental results show that the proposed algorithm can significantly save about 40% of the averaged computational costs versus the conventional PDE algorithm for ME at the cost of ignorable image quality degradation, whose average value is 0.0012 dB.
Shin, Lee, and Oh: Fast partial difference elimination algorithm based on block matching error prediction



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 (pSAD) , 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 (miṉbSAD) . Once the pSAD is larger than the miṉbSAD 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 k ’th line of a candidate block (pSADk) in the (x,y) position of the given search range can be expressed by


where N is the matching block size, and ft and ft1 indicate current and reference frames, respectively. To summarize the procedures of the conventional PDE algorithm, the approach computes the pSADk at every line of a candidate block, compares it with the miṉbSAD , and then moves to the next line if the pSADk is less than the miṉbSAD . It is noted that the miṉbSAD is updated only when a complete matching error computation (k=N1) 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 pSADk of a candidate block for k=0,,N1 , which will be eliminated last, until the pSADk reaches miṉbSAD . 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 (bSAD) , which is equivalent to the pSADN1 . The proposed algorithm is based on the property that a pSADk is an intermediate value and is gradually increased to reach the bSAD because the pSADk is continuously accumulated as k goes from 0 to N1 . The prediction at the k ’th line of a block (p̱bSADk) is performed, whenever the pSADk for k<N1 is less than the miṉbSAD by using the pSADk , as follows:


where g̱SADk is an averaged line-matching error of pSADk , and w 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 g̱SADk , which is caused by large line-matching errors at the candidate blocks containing the complex image such as edges. So w is selected in inverse proportion to the image complexities and defined by using an average of available bSADs (avg̱bSAD) in the neighboring blocks including the matching block, as follows:


Here, numerical values are empirically selected for all of the tested sequences.

The proposed approach computes a p̱bSADk to predict the bSAD from the pSADk if the pSADk for k<N1 is less than the miṉbSAD and compares the predicted block SAD (p̱bSADk) with the miṉbSAD before the next line computation. Therefore, the proposed algorithm has a high possibility to eliminate impossible candidates earlier than the conventional approach because the p̱bSADk always exceeds the pSADk . It is worth noting that the p̱bSADk 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 pSAD1 is computed and compared with a miṉbSAD (see ① in Fig. 1). A p̱bSAD1 is estimated because the pSAD1 is less than the miṉbSAD and is compared with the miṉbSAD . The p̱bSAD1 (see ② in Fig. 1) is still smaller than the miṉbSAD , and the algorithm goes to the next line. Similarly, a pSAD2 and a p̱bSAD2 are calculated at the second line because the pSAD2 is less than the miṉbSAD . However, the p̱bSAD2 (see ③) is larger than the miṉbSAD . 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 pSADk exceeds the miṉbSAD at the seventh line (see ⑥). Consequently, the proposed algorithm requires only two line matching events, while the conventional algorithm requires seven line matching events.

Fig. 1

Procedures for reducing the computational cost based on the block SAD prediction.



Simulation Results

The proposed PDE algorithm (P̱PDE) is simulated with various video sequences—Foreman, Stefan, Akiyo, Mobile, Container, Silent voice, News, and Table tennis—and they consist of 300 frames at 30Hz in the format of QCIF. The matching block size is 16×16 , and the search range is ±16 . The simulation results are compared with the spiral PDE algorithm (s̱PDE) 3 and the sorting-based PDE algorithm (S̱PDE) .4 It is noted that both the P̱PDE and the S̱PDE also employ a spiral scanning searching scheme, as the s̱PDE 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 0.0012dB 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.

Table 1

Comparisons with respect to image quality and prediction ability.

PSNRPSNRDifferenceMismatched MV
Foreman32.233832.2304 0.0051 1.311
Stefan24.675724.6733 0.0032 2.599
Mobile26.008826.0088 0.0001 0.027
Silent voice35.083035.0809 0.0031 0.221
Table tennis31.257231.2560 0.0024 0.472
Average34.303834.3026 0.0012 0.6547

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 s̱PDE 3 and S̱PDE ,4 respectively. The efficiency value of the proposed approach versus the conventional PDE algorithm is defined by


where PDE and P̱PDE are the conventional PDE and the proposed PDE algorithms, respectively.

Table 2

Average checked line numbers per candidate block.

Average checked lines
Silent voice1.9141.8041.314
Table tennis3.3062.7092.015
Efficiency (%)40.11029.8800.000



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.


1.  S. Eckart and C. Fogg, “Iso/iec mpeg-2 software video codec,” Proc. SPIE0277-786X 2419, 100–118 (1995). Google Scholar

2. ITU-T Recommendation H.263 software implementation, Digital Video Coding Group at Telenor R&D (1995). Google Scholar

3.  J. N. Kim, S. C. Byun, Y. H. Kim, and B. H. Ahn, “Fast full search motion estimation algorithm using early detection of impossible candidate vectors,” IEEE Trans. Signal Process.1053-587X 50(9), 2355–2365 (2002). Google Scholar

4.  B. Montrucchio and D. Quaglia, “New sorting-based lossless motion estimation algorithm and a partial distortion elimination performance analysis,” IEEE Trans. Circuits Syst. Video Technol.1051-8215 15(2), 210–220 (2005). Google Scholar

© (2007) Society of Photo-Optical Instrumentation Engineers (SPIE)
Se-Ill Shin, Se-Ill Shin, Sangkeun Lee, Sangkeun Lee, JeongSu Oh, JeongSu Oh, } "Fast partial difference elimination algorithm based on block matching error prediction," Optical Engineering 46(4), 040503 (1 April 2007). https://doi.org/10.1117/1.2721453 . Submission:

Back to Top