臺灣博碩士論文加值系統

在動態估計時，常常會有演算法使用三步搜尋法的架構來增加其效能。這篇論文提出了基於預測與仿射的新三步搜尋架構來取代傳統的正方形三步搜尋法，並且可以顯著提升效率。當用我們的方法來取代其他演算法中的三步搜尋法部份時，例如Jing 和 Chau 提出的an efficient three-step algorithm for block motion estimation，實驗證明無論是在品質或是速度都有增進。

The three-step search (TSS) scheme has been widely used in block-based motion estimation and has also been incorporated into several motion estimation methods successfully to improve their performance. Instead of adopting the conventional square search pattern used in the TSS scheme, this thesis presents a new prediction- and affine transformation-based TSS (PATSS) scheme and it leads to a more efficent search pattern. When employing our proposed PATSS scheme into some existing well-known motion estimation algorithms, such as the newly published algorithm by Jing and Chau ("An efficient three-step search algorithm for block motion estimation," IEEE Trans. Multimedia, vol. 6, no. 3, pp. 435-438, Jun. 2004.), experimental results show that not only the image quality can be improved, but the number of search points can be reduced significantly.

Contents
1 Introduction
2 Past Works
2.1 The TSS Scheme
2.2 The E3SS Algorithm
3 Our Proposed PATSS Search Scheme and Incorporating It with E3SS Algorithm
3.1 The Proposed PATSS Search Scheme
3.2 Incorporating PATSS with E3SS Algorithm
4 Experimental Results
5 Conclusions

Bibliography
[1] R.C. Gonzalez, R.E. Woods, Digital Image Processing, Section 11:1.2: Polygonal Approximations, 2nd Edition, Prentice Hall, New York, (2002).
[2] S. Y. Huang, C. Y. Cho, and J. S. Wang, "Adaptive fast block-matching algorithm by switching search patterns," IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 11, pp. 1373-1384, Nov. 2005.
[3] J. R. Jain, A. K. Jain, "Displacement measurement and its application in interframe image coding," IEEE Trans. Communications, vol. COM-29, no. 12, pp. 1799-1808, Dec. 1981.
[4] X. Jing and L. P. Chau, "An efficient three-step algorithm for block motion estimation," IEEE Trans. Multimedia., vol. 6, no. 3, pp. 435-438, Jun. 2004.
[5] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and 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-G5.3.5
[6] R. Li, B. Zeng, and M. L. Liou, "A new three-step search algorithm for block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 4, no. 4, pp. 438-442, Aug. 1994.
[7] L. K. Liu and E. Feig, "A block-based gradient descent search algorithm for block motion estimation in video coding," IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 4, pp. 419-423, Aug. 1996.
[8] Y. Nie and K. K. Ma, "Adaptive rood pattern search for fast blockmatching motion estimation," IEEE Trans. Image Processing, vol. 11, no. 12, pp. 1442-1449, Dec. 2002.
[9] L. M. Po and W. C. Ma, "A novel four-step search algorithm for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 313-317, Jun. 1996.
[10] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, pp. 369-377, Aug. 1998.
[11] S. Zhu and K. K. Ma, "A new diamond search algorithm for fast blockmatching motion estimation," IEEE Trans. Image Processing, vol. 9, no. 2, pp. 287"290, Feb. 2000.