Block Matching Using Fast Walsh

Motivated by a fast pattern matching algorithm proposed by Hel-Or [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 sum-of-absolute 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.

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 sum-of-absolute difference of DC coefficients (SADDCC) to find the best match among the remaining candidates.

FWS is compared with Full Search (FS), Three-Step-Search (TSS) [3] and Diamond-Search (DS) [4] using a few standard seqeunces (Foreman, Stefan, Akiyo). The resulting mean-square-error 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.

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
Sequence	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

A fast block matching algorithm, Fast Walsh Search (FWS) is proposed. The accuracy of this algorithm is close to the optimal full-search algorithm, and the computation time is in the same order as other fast search algorithms like TSS and DS.

[1] Y. Hel-Or; H. Hel-Or; “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. Hel-Or; H. Hel-Or; “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. 29-Dec. 3 1981, pp. G5.3.1-5.3.5.

[4] Shan Zhu; Kai-Kuang Ma; “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Image Processing, Vol. 9, No. 2, Feb. 2000, pp. 287 - 290.

An executable demo program can be downloaded here. This program can be run under MS Windows Environment only.