多媒體通訊有賴於資料壓縮技術來減少傳送的資料量並提高傳送的速度。移動估計在許多移動補償視訊編碼標準中是一個關鍵的部分。前述的視訊編碼標準例如ISO MPEG-1/2/4 及 ITU-T H.261/262/263/264。在移動估計中，不同形狀及大小的搜尋樣板對於移動估計的效能有決定性的影響。這裡的效能指的是找到移動向量所花費的運算量以及預測估計結果的好壞與否。近年來，許多節省運算量的快速搜尋演算法陸續發表，較具代表性的有1994年的三步驟搜尋(3SS)，2000年的菱形搜尋(DS)，2002年的六角形為基礎的快速搜尋(HEXBS)，以及以上這些演算法的改良板本，如2003年強化六角搜尋演算法(E-HEXBS)，2004年的有效率三步驟搜尋演算法(E3SS)，2006年適應性雙層初始樣板快速搜尋演算法(ADLISP)。這裡我們延續ADLISP提出的雙層搜尋樣板，以及樣板大小的移動適應性調整機制為架構，針對ADLISP外層樣板結構做進一步改善，這裡使用Linde-Buzo Gray (LBG) 演算法找出視訊內容的移動特性及外層樣板搜尋點數的誤差曲線，依據視訊內容的移動特性，外層樣板採用4個點及8個點的樣板變換模式。並提出巨方塊移動強度陣列，做為樣板變換的判斷基準。實驗結果顯示所提出的快速演算法超越2006年所提出的ADLISP有更低的MSE值，然而我們所提出的演算法與ADLISP相比節省近7%的平均搜尋點數量，與E-HEXBS相比節省近46%的平均搜尋點數量。

Multimedia communication relies on data compression technology to reduce the data bits of transmission. Motion estimation is the key function in exploiting temporal redundancy for compression in most video coding standards. For example, ISO MPEG-1/2/4 and ITU-T H.261/262/263/264. In motion estimation performance, the shape and size of search pattern has critical influence. The performance indicates the amount of computation and video quality. In recent years, many fast motion estimation algorithms are published. Such as, Three-Step Search (3SS) algorithm in 1994, Diamond-Search (DS) algorithm in 2000, Hexagonal Based Search (HEXBS) and the upgraded versions of those algorithms. For example, Enhanced- HEXBS (E-HEXBS) in 2003, Efficient Three-Step Search (E3SS) in 2004 and Adaptive Double-Layered Initial Search Pattern (ADLISP) in 2006.
In this paper, basically, we follow the double-layered initial search pattern and it’s adjustment of search pattern mechanism. To improve the performance of ADLISP further. The outer layer search pattern is revised. We use Linde-Buzo Gray (LBG) algorithm to find the characteristics of video content and distortion curve of numbers of outer layer search points. According to the motion characteristics of video content, four or eight points of outer layer pattern are adopted in the proposed algorithm. In addition, we propose block level motion intensity (BLMI) array which records every macroblock motion intensity information when a macroblock has finished it’s motion estimation. We use BLMI array to decide motion types, outer layer pattern modes and outer layer pattern to be used or not. Experimental results of motion estimation on various video sequences show that the proposed algorithm achieves image quality similar to ADLISP but with 7% and 46% less search points compared with ADLISP and E-HEXBS respectively.

[1] 戴顯權編著，多媒體通訊，紳藍出版社，2002年

[2] 戴顯權編著，資料壓縮，紳藍出版社，2002年

[3] “Information Technology – Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbit/s – Part 2: Video”, JTC1/SC29/WG11, ISO/IEC 11172-2 (MPEG-1 Video), 1993.

[4] “Generic Coding of Moving Pictures and Associated Audio Information – Part 2: Video”, ITU-T and ISO/IEC JTC 1, ITU Rec. H.262 – ISO/IEC 13818-2 (MPEG-2 Video), 1994.

[5] “Information Technology – Coding of Audio Visual Objects – Part 2: Visual”, JTC1/SC29/WG11, ISO/IEC 14496-2 (MPEG-4 Visual), 2000.

[6] “Fast block-matching motion estimation using predictive motion vector field adaptive search technique (PMVFAST),” ISO/IEC JTC1/SC29/WG11 MPEG2000/M5866, Noordwijkerhout, The Netherlands, Mar. 2000.

[7] Shan Zhu, Kai-Kuang Ma, “A new diamond search algorithm for fast block-matching motion estimation”, IEEE Trans. on Image Processing, vol. 9, no. 2, pp.287-290, Feb. 2000.

[8] Bongsoo Jung, Woong Il Choi, Byeungwoo Jeon, “Modified Diamond Search
Sensitive to Block Matching Error Characteristics”, ITC-CSCC 2003, pp.1038-1311, July 2003.

[9] Hongiun Jia, Li Zhang, “A new cross diamond search algorithm for block motion estimation”, IEEE International Conference. on Acoustics, Speech, and Signal Processing, vol. 3, pp.361-364, May 2004.

[10] Chi-Wai Lam, Lai-Man Po, Chun Ho Cheung, “A novel kite-cross-diamond search algorithm for fast block matching motion estimation”, Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on, vol. 3, pp.729-732, May 2004.

[11] Chun-Ho Cheung, Lai-Man Po, “Novel cross-diamond-hexagonal search algorithms for fast block motion estimation”, IEEE Trans. on Multimedia, vol. 7, no. 1, pp.16-22, Feb. 2005.

[12] So, H., Kim, J., Cho, W.-K. and Kim, Y.-S., “Fast motion estimation using modified diamond search patterns”, IEE Electronics Letters, vol. 41, no. 2, pp.62-63, 20 Jan. 2005.

[13] Ce Zhu, Xiao Lin, Lap-Pui Chau, “Hexagon-based search pattern for fast block motion estimation”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 12, no. 5, pp.349-355, May 2002.

[14] Ce Zhu, Xiao Lin, Lap-Pui Chau, “An enhanced hexagonal search algorithm for block motion estimation”, Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on, pp.392-395, May 2003.

[15] Ce Zhu, Xiao Lin, Chau, L., Lai-Man Po, “Enhanced hexagonal search for fast block motion estimation”, IEEE Trans. on Circuits and Systems for Video Technology,vol. 14, no. 10, pp.1210-1214, Oct. 2004.

[16] Xuan-Quang Banh and Yap-Peng Tan, “Adaptive Dual-Cross Search Algorithm for Block-Matching Motion Estimation”, IEEE Trans. on Consumer Electronics, vol. 50,No. 2, May 2004.

[17] Xuan Jing, Lap-Pui Chau,“An efficient three-step search algorithm for block motion estimation”, IEEE Trans. on Multimedia, vol. 6, no. 3, pp.435-438, June 2004.

[18] Yao Nie, Kai-Kuang Ma, “Adaptive rood pattern search for fast block-matching motion estimation”, IEEE Trans. on Image Processing, vol. 11, no. 12, pp.1442-1449, Dec. 2002.

[19] Yao Nie, Kai-Kuang Ma, “Adaptive irregular pattern search with matching
prejudgment for fast block-matching motion estimation”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 15, no. 6, pp.789-794, June 2005.

[20] Shih-Yu Huang, Chuan-Yu Cho, Jia-Shung Wang, “Adaptive fast block-matching algorithm by switching search patterns for sequences with wide-range motion content”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 15, no. 11, pp.1373-1384, Nov. 2005.

[21] C. S. Yu, S. C. Tai, “Adaptive Double-Layered Initial Search Pattern for Fast Motion Estimation”, accepted by IEEE trans. on Multimedia, 2006.