Fast Walsh Search Demo Program

The demo program performs block matching between two frames: target and reference frame, and reconstruct the target frame from reference frame using the motion vectors found.Several block matching algorithms can be chosen, including Full search block matching, Three-step-search [1], Diamond search [2], 2D Log search [3], Four-step-search [4], and the proposed Fast Walsh Search [5].

The program works on gray-scale raw images extracted from videos. Please note that only QCIF (176x144) and CIF (352x288) images are supported. You can download the test data from

The interface of our program is like this:

Instructions:

1)click “Browse File” button, and then choose a numbered raw file

(Note that the raw files must have a format “xxx-nnn.raw”, where “xxx” is the name of the sequence, “nnn” is the frame number.)

2)Choose the correct dimension of the frame in the pull-down menu of “frame dimension”.

3)Set the following parameters

  1. Search method
  2. start frame number: the first reference frame
  3. end frame number: last target frame
  4. block size: block size for matching (choose only 2, 4, 8, or 16). The block size of FWS is always set to 8
  5. max range: the maximum displacement allowed

4)Press “Go” to start

Results:

1)On Screen Display:

After performing the block matching and motion compensation process, the average PSNR, MSE of the reconstructed target frame and the total computation time will be shown on the screen. The current target frame is shown on the lower left part of the dialog, and the reconstructed target frame is shown on the lower right part.

2)Output logs and data:

You can choose to dump three types of data to the folder that holds the video data by checking the boxes in “Output Logs”.

1)PSNR log: the PSNR and MSE of each reconstructed target frame. For different search method, the PSNR log file has a different name.

2)Reconstructed frame: the reconstructed target frame from motion compensation in “raw” format. The file name is in the format of “xxx-rec-nnn.raw”, where “xxx” is the name of sequence, and “nnn” is the frame number.

3)Motion vectors: motion vectors of each block with file name of format “xxx-MV-nnn.txt”, where “xxx” is the name of sequence, and “nnn” is the frame number. In the file, each row has four numbers corresponding to the row, column number of the upper left pixel of the block, and the motion vector in y and x dimension.

References

[1]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.

[2]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.

[3]J. Jain and A. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. on Communications, vol. 29, pp. 1799–1808, 1981.

[4]Lai-Man Po; Wing-Chung Ma;“A novel four-step search algorithm for fast block motion estimation,”IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No. 3, June 1996, pp. 313 - 317.

[5]N. Li; C.M. Mak; W.K. Cham; “Block Matching Using Fast Walsh Search”, submitted to IEEE Signal Processing Letter, 2005.