中文摘要

在這篇論文中，我們將使用動態臨界值與事先預測動作向量的方式，運用在快速區塊估測(fast block-matching estimation)的演算法裡，而快速區塊估測演算法是屬於視訊壓縮中的動作補償(motion compensation)中。這新的快速動作估測演算法包含了兩個提升效率的方法：1) 首先，我們會去判斷區塊是否為靜止的，此新的演算法定義每一塊區塊都擁有適合的臨界值，而這個臨界值能幫助我們來判斷此區塊是否為靜止區塊。2) 參考目前區塊的鄰近區塊之動作向量，判斷是否有合適目前區塊使用的動作向量。目前，在快速區塊估測演算法中，建議可以從降低動作估測的計算量來換取更好的效果，如果只損失一點點的影像品質。在我們的實驗中，我們發現出影像品質(PSNR)與決定靜止區塊的多寡，這之間存在了一種有趣的關係。因此，有更多時間冗餘量可以被減少，讓整個演算法的搜尋速度加快，又不影響太多的影像品質，在設定靜止區塊的多寡條件上面。在實驗數據裡，說明採用上面兩個步驟在視訊編碼中動作估測裡，我們可以了解此方式的強靭性且有效率地存在。我們將節省了大約50% ~ 80%的計算負載量，在於我們考慮如何妥協可接受畫面品質的良劣與要搜尋區塊點數的多寡這兩方面。因此，我們提供了另一個可供選擇的方法，去有效率地減少搜尋區塊點數，來降低演算法的計算量，此新的方式是可以運用在所有的區塊動作估測演算法中。

Abstract

A fast block-matching motion estimation with variable thresholds and predictive motion vectors used in the motion-compensated video compression is proposed in this paper. The proposed algorithm consists of two effective steps: 1) setting the variable thresholds to specify the stationary blocks and 2) referring the motion vectors of the neighboring blocks to efficiently determine the predictive motion vectors. The all-zero and zero-motion detection algorithms are suggested to reduce the computation of motion estimation. A robust compromise between the contribution of PSNR and the determination of stationary blocks defined in this paper has been investigated. Experimental results demonstrate more or less 50% to 80% computation load can be saved in consideration of compromise between the acceptable quality and checking points. As a result, the proposed method provides an alternative way to efficiently reduce checking points, which works on all block-matching algorithms in the literature.

References

[1] S. Zhu and K. K Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Trans. Image Processing, vol. 9,no. 2, pp. 287-290, 2000.
[2] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trasn. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349-355, 2002.
[3] Yao Nie, and Kai-Kuang Ma, “Adaptive rood pattern search for fast block-matching motion estimation,” IEEE Trasn. Image Processing., vol. 11, no. 12, December 2002
[4] X. Q. Banh and W. P. Tan, “Adaptive dual-cross search algorithm for block-matching motion estimation,” IEEE Trans. Consumer Elect., vol. 50, no. 2, pp. 766-775, 2004.
[5] 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, 1996.
[6] X. Jing and L. P. Chau, “An efficient three-step search algorithm for block motion estimation,” IEEE Trans. Multimedia, vol. 6, no. 3, pp. 435-438, 2004.
[7] C. Zhu, X. Lin, L. Chau, and L. M .Po, “Enhanced hexagonal search for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 14, no. 10, pp. 1210-1214, 2004.
[8] J. Xin, C. W. Lin, and M. T. Sun, “Digital video transcoding,” Proc. IEEE, vol. 93, no. 1, pp. 84-97, 2005.
[9] J. F. Yang, S. C. Chang, and C. Y. Chen, “Computation reduction for motion search in low rate video coders,” IEEE Trans. Circuits and Systems for Video Technology, vol. 12, no. 10, October 2002.
[10] Y. Nie and K. K. Ma, “Adaptive irregular pattern search with matching prejudgment for fast block-matching motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 15, no. 6, June 2005.
[11] Y. Yatabe, M. Fujimoto, K. Sodeyama, and H. Komi, “An MPEG2/4 dual CODEC with sharing motion estimation,” IEEE Trans. Consumer Electronics, vol. 51, no. 2, May 2005.
[12] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for Block Motion Estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 4, no. 4, August 1994.
[13] R. M., J. R. Smith, and C. S. Li, “Adapting multimedia internet content for universal access,” IEEE Trans. Multimedia, vol. 1, no. 1, pp. 104-114, Mar. 1999.
[14] S. F. Chang and A. Vetro, “Video adaptation: concepts, technologies, and open issues,” Proc. IEEE, vol. 93, no. 1, pp. 148–158, Jan. 2005.
[15] S. Wee, “Reversing motion vector fields,” in Proc. IEEE Int. Conf. Image Processing, vol. 2, 1998, pp. 209–212.
[16] S. Wee and B. Vasudev, “Compressed-domain reverse play of MPEG video streams,” in Proc. SPIE Int. Symp. Voice, Video, and Data Communications, 1998, pp. 237–248.
[17] Y. P. Tan, Y. Q. Liang, and J. Yu, “Video transcoding for fast forward/ reverse video playback,” in Proc. IEEE Int. Conf. Image Processing, vol. 1, 2002, pp. 713–716.
[18] A. Vetro, H. Sun, and Y. Wang, “Object-based transcoding for adaptable video content delivery,” IEEE Trans. Circuits Syst. Video Technol., vol. 11, no. 3, pp. 387–401, Mar. 2001.
[19] S. F. Chang, “Optimal video adaptation and skimming using autility-based framework,” presented at the Tyrrhenian Int. Workshop Digital Communications, Capri Island, Italy, 2002.
[20] J. G. Kim, Y. Wang, and S. F. Chang, “Content-based utility function prediction for real-time MPEG-4 video transcoding,” in Proc. IEEE Int. Conf. Image Processing, 2003, pp. 189–192.
[21] P. Yin, A. Vetro, and B. Liu, “Rate-distortion models for video transcoding,” in Proc. SPIE Conf. Image Video Communications Processing, 2003, pp. 479–488.
[22] “Information technology—Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s—Part 2: Video (MPEG-1 video),” Int. Standards Org./Int. Electrotech. Comm. (ISO/IEC), ISO/IEC 11 172-2, 1st ed., 1993.
[23] “Information technology—Generic coding of moving pictures and associated audio information: Video (MPEG-2 video),” Int. Standards Org./Int. Electrotech. Comm. (ISO/IEC), ISO/IEC 13 818-2, 2nd ed., 2000.
[24] “Coding of audio-visual objects—Part 2: Visual (MPEG-4 video),” Int. Standards Org./Int. Electrotech. Comm. (ISO/IEC), ISO/IEC 14 496-2:2001, 2nd ed., 2001.
[25] “Video coding for low bit rate communication,” Int. Telecommun. Union-Telecommun. (ITU-T), Geneva, Switzerland, Recommendation H.263, 1998.
[26] “Draft text of final draft international standard for advanced video coding,” Int. Telecommun. Union-Telecommun. (ITU-T), Geneva, Switzerland, Recommendation H.264 (draft), Mar. 2003.
[27] A. Vetro, C. Christopulos, and H. Sun, “Video transcoding architectures and techniques: An overview,” IEEE Signal Process. Mag., vol. 20, no. 2, pp. 18–29, Mar. 2003.
[28] J. Lu and M. L. Liou, “A simple and efficient search algorithm for block-matching motion estimation,” IEEE Trans. Circuits Syst. Video Technol, vol. 7, pp. 429-433, Apr. 1997.