多媒體通訊有賴於資料壓縮技術來減少傳送的資料量並提高傳送的速度。動作估計在許多動作補償視訊編碼標準中是一個關鍵的部分。 前述的視訊編碼標準例如ISO MPEG-1/2/4 及 ITU-T H.261/262/263/264。在動作估計中，不同形狀及大小的搜尋樣版對於動作估計的效能有決定性的影響。這裡的效能指的是找到動作向量的速度以及預測估計結果的好壞與否。近幾年來，許多節省運算量的快速搜尋演算法陸續發表，較具代表性的有1994年的三步驟搜尋，2000年的菱形搜尋，2002年的六角形為基礎的快速搜尋，以及2004年的有效率三步驟搜尋演算法。這裡我們提出一組具備穩定、效率且簡易等特性的的快速區塊動作估計演算法，稱之為具雙層初始搜尋樣版之快速動作估計 (DLISP)。實驗結果顯示所提出的快速演算法超越知名的六角形為基礎之快速搜尋法並且與有效率三步驟搜尋演算法有極接近的MSE值，然我們所提出的演算法與它相比卻節省近22%的運算量。與其他近幾年發表的區塊動作估計演算法，所提出的DLISP在MSE值及平均搜尋點上皆獲得較好的優勢。

　　Multimedia communication relies on data compression technologies to reduce the data bytes of transmission and enhance the speed of transmission. Motion estimation is vital to many motion-compensated video-coding techniques/standards, such as ISO MPEG-1/2/4 and ITU-T H.261/262/263/264。In block motion estimation, a search pattern with a different shape and size has a very important impact on performance of motion estimation. The performance indicates that the speed of finding out motion vectors and the visual quality of predicted results. In recent years, many computationally efficient fast search algorithm were developed, among which are typically the three-step search (3SS) in 1994, the new diamond search (DS) in 2000, the hexagon-based Search (HEXBS) in 2002, and the efficient three-step search (E3SS) in 2004. Here we propose a pair of simple, robust and efficient fast block matching motion estimation algorithms, called double-layered initial search patterns (DLISP). Simulation experiments demonstrate that the proposed DLISP algorithm greatly outperforms the well-known hexagon-based Search (HEXBS) algorithm and achieves similar MSE performance compared to efficient three-step search (E3SS) while reducing its computation by up to 22% approximately. Compared with other recently proposed block-matching algorithms, the proposed DLISP algorithms works better on average in terms of MSE values, reconstructed image quality, and average number of search points.

REFERENCES

[1] J. R. Jain and A. K. Jain, “Displacement Measurement and It’s 　　　　　　　Application in Inter frame Image Coding,” IEEE Trans. Comm., COM-29, 1799-　　1808, 1981.
[2] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion-　　　　　compensated interframe coding for video conferencing,” in Proc. NTC 81, 　　　pp. C9.6.1-9.6.5, New Orleans, LA, 1981.
[3] 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, pp. 438-442, Aug. 1994.
[4] 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, 　　　　pp.313-317, June 1996
[5] 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, pp. 419-423, Aug. 1996.
[6] S.Zhu and K. K. Ma, “A new diamond search algorithm for fast block-　　　　　matching motion estimation,” IEEE Trans. Image Processing, vol.9, pp. 287-　　290, Feb. 2000.
[7] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast 　　　block motion estimation,” IEEE Trans. Circuits Syst. Video Technol, vol. 　　12, pp. 349-355, May 2002.
[8] Xuan Jing and Lap-Pui Chau, “An efficient three-step search algorithm for 　　block motion estimation,” IEEE Trans. Multimedia, vol.6, no. 3, JUNE 2004.
[9] 資料壓縮, 戴顯權編著, 紳藍出版社, 2002年
[10]S.C. Tai, C. S. Yu and C. W. Lee, “Double-layered Initial Search Pattern 　　for Fast Motion Estimation,” IPSI-2005 Amalfi, Italy, Feb 17 2005
[11]國立海洋大學電機工程系碩士 李信龍, “快速雙菱形位移估測演算法應用於及時動　　　態影像編碼系統,” 2001年
[12]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, pp. 369-　　　377, Aug, 1998.
[13]J. Huang, H. S. Wong, and J. H. Wang, “A novel cellular search algorithm 　　for block-matching motion estimation,” IEEE Trans. Image Processing, Vol. 　　9, No. 2, pp.287-290, 2001.
[14]B. B. Paul and E. Viscito, “Hierarchical motion estimation with 2-scale 　　　tilings,” Proc IEEE Intl. Conf. Image Processing, pp. 260-264, 1994.
[15]A. M. Tourapis, O. C. Au, and M. L. Liou, “Predictive motion vector field 　　adaptive search technique (PMVFAST) enhancing block-based motion 　　　　　　　estimation,” in Proc. SPIE Conf. Visual Communication and Image 　　　　　　　Processing, Jan. 2001, pp. 883-892.
[16]Iain E. G. Richardson, “H.264 and MPEG-4 Video Compression: Video Coding 　　for Next-generation Multimedia,” John Wiley & Sons Ltd, The Atrium, 　　　　　Southern Gate, Chichester, West Sussex PO19 8SQ, England, 2003.