Block Matching Using Fast Walsh Search
Motivated by a fast pattern matching algorithm proposed by HelOr [1],[2], we propose a “Fast Walsh Search” (FWS) that performs block matching in the Walsh Hadamard domain. The proposed algorithm utilized the pruning transform method and early rejection of mismatch candidates strategy in [1],[2] to reduce computation time. In addition, we suggest a new matching measure called sumofabsolute difference of DC coefficients (SADDCC) to enhance the accuracy of the matching algorithm. The proposed method achieves significantly better block matching result in terms of mean square error (MSE) with a computation time slighter higher than common fast search algorithms.
Proposed Algorithm
The block diagram of the proposed algorithm is shown in Fig. 1.
Fig. 1. Block Diagram of FWS algorithm
Firstly, the reference frame and target block are projected onto Walsh Hadamard basis pictures. The similarity of the target block and the candidates in the corresponding search window in reference frame is calculated based on the first few transform coefficients. Most of dissimilar candidates are early rejected. After that, we proposed to evaluate the remaining candidates using sumofabsolute difference of DC coefficients (SADDCC) to find the best match among the remaining candidates.
Experimental Results
FWS is compared with Full Search (FS), ThreeStepSearch (TSS) [3] and DiamondSearch (DS) [4] using a few standard seqeunces (Foreman, Stefan, Akiyo). The resulting meansquareerror of 30 frames of each sequence are shown in Fig. 2. FWS performs very close to Full Search and significantly better than other fast algorithms.
Fig. 2. MSE of different sequences
The computation time of FWS is about 1.5 times of TSS. Table 1 shows the average MSE and time of process 30 frames using a Pentium 4 1.7GHz computer with 512MB RAM.
Sequence 
FSBM 
TSS 
DS 
FWS 

MSE 
Time [s] 
MSE 
Time [s] 
MSE 
Time [s] 
MSE 
Time [s] 

Football 
142.58 
25.16 
260.31 
1.84 
347.19 
1.90 
153.27 
2.73 
Foreman 
28.37 
7.28 
37.94 
0.59 
33.57 
0.44 
29.84 
0.72 
Stefan 
134.45 
25.36 
302.86 
1.91 
365.82 
1.36 
148.65 
2.63 
Akiyo 
3.91 
25.53 
4.57 
1.75 
4.00 
1.25 
4.12 
2.65 
Children 
50.31 
25.21 
80.84 
1.80 
64.98 
1.25 
56.53 
2.72 
Mother&Daughter 
18.23 
6.61 
22.24 
0.53 
22.06 
0.425 
20.35 
0.71 
Table 1. Computation Time
Conclusions
A fast block matching algorithm, Fast Walsh Search (FWS) is proposed. The accuracy of this algorithm is close to the optimal fullsearch algorithm, and the computation time is in the same order as other fast search algorithms like TSS and DS.
Reference
[1] Y. HelOr; H. HelOr; “Real time pattern matching using projection kernels”, Proc. of Ninth IEEE International Conference on Computer Vision, Vol. 1, Oct. 2003, pp. 1486 – 1493.
[2] Y. HelOr; H. HelOr; “Real time pattern matching using projection kernels”, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 27, No. 9, Sept 2005, pp. 1430  1445.
[3] T. Koga; K. Iinuma; A. Hirano; Y. Iijima; T. Ishiguro; “Motion compensated interframe coding for video conferencing,” in Proc. Nat. Telecommun. Conf., New Orleans, LA, Nov. 29Dec. 3 1981, pp. G5.3.15.3.5.
[4] Shan Zhu; KaiKuang Ma; “A new diamond search algorithm for fast blockmatching motion estimation,” IEEE Transactions on Image Processing, Vol. 9, No. 2, Feb. 2000, pp. 287  290.
Demo Program
An executable demo program can be downloaded here. This program can be run under MS Windows Environment only.
Demo Program* (Executable File)
*This program can be freely distributed for academic purpose only.
(last edited on 22/02/2006)
Contacts:
Mr. N. Li, Mr. C.M. Mak, Prof. W.K. Cham
Email: nli@ee.cuhk.edu.hk cmmak@ee.cuhk.edu.hk wkcham@ee.cuhk.edu.hk