目前人類的資訊生活，已經逐步走向以各種影音多媒體為主流。然而，影音資料若是未經壓縮，將會需要使用大量的記憶體才能夠來儲存。因此，對影音資料來說，在儲存或傳送之前進行通常都必須先經過資料壓縮。視訊資料的壓縮主要著重於連續畫面間彼此的相似性，由前一張畫面來預測下一張畫面。要求出前後兩張畫面間的對應關係，則必須要靠動作向量搜尋來求出。因此，動作向量搜尋一向是視訊資料壓縮的核心技術。由於動作向量搜尋需要花費相當多的計算量，近幾年不斷的有研究機關提出各種加速搜尋的方式。這些加速的方式之中，又以使用少量的比對次數的演算方式為主要的研究方向。在這些方式之中，有些使用小範圍逐步搜尋的概念，有些使用近似於二維的二元搜尋法來完成。然而，前者在視訊移動量較大時需要額外的計算才能夠找到適當的動作向量，而後者則往往浪費時間在檢驗不太可能會發生的偏移量比對。
因此，在本博士論文中將提出具可調式的動作向量搜尋演算法。文中所提到的三種演算法，第一種是以雙層式搜尋樣式為基礎的快速搜尋演算法，以統計方式找出最具代表性的搜尋樣式，藉以提升搜尋速度。由於動作向量分布的嚴重不均，此演算法主要是以雙層式搜尋為主體，內層用來進行小範圍的動作向量搜尋，而外層則以改良式的二維二元搜尋法為基礎捕捉很少出現的大範圍移動量。實驗結果顯示，使用此演算法，其所需之搜尋點平均介於9~12點，遠低過高效率三步搜尋演算法的14~16點，並能在處理慢動作的視訊時獲得與其同等之畫質。以純粹的搜尋樣式改進之快速搜尋演算法來說其效能已相當不錯。
第二種演算法將第一種演算法加以改良，以可調式的方式調整搜尋樣式，並輔以動作向量預測以提升其速度。由於採用了可調式調整搜尋樣式，搜尋點的位置可以隨著目標視訊本身的特性進行微調，因此本演算法擁有比二元搜尋法還要高的效能。實驗結果顯示其搜尋所花費平均搜尋點數已降到6.96，相當於高效率三步搜尋演算法的一半，並且無論在處理快速或慢速移動的視訊時皆能獲得接近於高效率三步搜尋演算法的畫質。平均而言，此演算法所處理的視訊資料畫質僅比完全搜尋法高出11.2%的均方根差值，與擅長細微動作向量搜尋的菱形搜尋法相當，因此動作補償出來的視訊畫質已非常良好，訊號雜訊比僅比完整搜尋低0.408dB。
第三種動作可調式搜尋演算法改進前一種的作法，除了利用搜尋期間的動作模式來調整自己的搜尋樣式以及搜尋點數量外，尚能隨時注意搜尋結果是否已經能有效的表示兩張畫面間的對應向量，在此時將搜尋提前結束以節省運算成本。此外，利用過去找到的動作向量之間的關聯性來決定搜尋模式，本演算法能隨時調整至最佳的搜尋模式以提升搜尋效能。實驗結果證實，本文所提出的演算法能夠快速並準確的找到代表畫面間對應關係的動作向量。於23種不同的標準測試視訊的實驗結果顯示平均所需的搜尋點數已降至4.573，並且其畫質損失，其訊號雜訊比僅比完整搜尋低0.336dB。

Videos, music and various multimedia objects can be seen in modern digital life everywhere. Multimedia communication relies on data compression technology in order to reduce the bits of data transmission. Video data are needed to be compressed before storage or transmission. Video compression exploits temporal redundancy between video frames to achieve higher compression efficiency. In most video coding standards motion compensation is the key function that does this job, which needs the information of a motion vector that is derived by motion estimation. Due to the heavy computational cost of motion estimation many fast algorithms have been proposed in recent years. Among them, some algorithms use a regional search that tweaks the result of the motion vector gradually. Some use logarithm based fast search strategies. However, small search pattern based motion-estimation algorithms usually spend large amounts of computational time in order to estimate large motion vectors, while other mid-sized search pattern algorithms usually spend extra search steps to confirm near-zero motion vectors. Divide and conquer methods, on the other hand, are not optimized for the probability model of motion vectors. This truth makes these logarithm based algorithms wasting additional time in estimating static motions which can easily be found by small search pattern based algorithms easily.
In this dissertation three adaptive fast motion-estimation algorithms are proposed. The first of them employs a search pattern which is derived from the data clustering of motion vectors. The statistics of motion vectors are used to generate this pattern which is a pair of complementary double-layered (inner layer and outer layer) initial search patterns. The inner-layer search is applied first and tests for small motion. The outer layer search which is based on a logarithm search serves as a guard line to catch large motion. The simulation results show that the necessary computations have been reduced to 9~12 block matching per macroblock, which is much lower than the 14~16 block matchings of the famous efficient three-step search. The visual quality of the motion compensation result at that time is also better than most other algorithms.
The second algorithm - adaptive double-layered initial search pattern (ADLISP) is an improved version of the first one. Motion prediction is employed by ADLISP to improve the search speed. The positions of the search points of ADLISP are also adaptive to recent motions. By using the pseudo median points of motion vector distribution probability, the simulation results of ADLISP show even better search efficiency over the logarithm-based fast motion-estimation algorithms. The average search points used per macroblock is decreased to 6.96, which is only half of the necessary amount of search points that efficient three-step search uses. On average, ADLISP only increases in the mean square error (MSE) of motion compensated video by 11.2%, which is nearly the same level compared to diamond search which is efficient in estimating small motions. The peak signal-to-noise (PSNR) loss is only 0.408dB compared to full search.
In the third fast motion-estimation algorithm, the motion and distortion information of neighboring macroblocks are referenced to decide the best search mode. In different modes, different amounts of search points are used. The positions of these search points are adaptive to recent estimated motion vectors. Furthermore, an early search termination mechanism is used in some situations to save computation power. This algorithm tries to keep a suitable amount search points in suitable position to catch any scale of motions. Experimental results show that this algorithm can estimate motion vectors extremely quickly without conspicuous visual quality loss. Simulations in 23 different standard video test sequences show that the average necessary search points is reduced to 4.573, while the peak signal-to-noise loss is merely 0.336dB compared to full search.

[1] "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.
[2] 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.
[3] Standardization Sector of ITU, Video Coding for Low Bit-rate Communication, ITU-T Rec. H.263, Mar. 1996.
[4] Information Technology - Generic Coding of Audio-Visual Objects - Part 2: Visual, ISO/IEC 14 496-2 (MPEG-4 Video), 1999.
[5] Ishfaq Ahmad, Weiguo Zheng, Jiancong Luo, and Ming L. Liou, " A Fast Adaptive Motion Estimation Algorithm," IEEE Transactions on Circuits and System for Video Technology, vol. 16, no.3, pp.420-438, Mar 2006
[6] Xuan-Quang Banh and Yap-Peng Tan, "Adaptive Dual-Cross Search Algorithm for Block-Matching Motion Estimation," IEEE Transactions on Consumer Electronics, vol. 50, no. 2, pp. 766-775, May 2004.
[7] Matthias Bierling, "Displacement estimation by hierarchical block matching," SPIE Visual Communications Image Processing, pp. 942-951, May 1998.
[8] Yui Lam Chan and Wan-Chi Siu, "Adaptive multiple-candidate hierarchical search for block matching algorithm," IEE Electronic Letters, vol. 31, no.19, pp. 1637-1639, Sep. 1995.
[9] Liang-Gee Chen, Wai-Ting Chen, Yen-Shen Jehng, and Tzi-Dar Chuieh, "An efficient parallel motion estimation algorithm for digital image processing," IEEE Transactions on Circuits and System for Video Technology, vol. 1, no. 4, pp. 378-384, Dec. 1991.
[10] Zhibo Chen, J. Xu, Yun He, and Junli Zheng, "Fast integer-pel and fractional-pel motion estimation for H.264/AVC," Journal of Visual Communication and Image Representation, vol. 17, Special Issue on Emerging H.264/AVC Video Coding Standard, pp. 264-290, Apr. 2006.
[11] Zhibo Chen, Yun He, and Jianfeng Xu, "Hybrid unsymmetrical-cross multi-hexagon-grid search strategy for integer-pel motion estimation in H.264," Proceedings of Picture Coding Symposium, Saint Malo, Apr. 2003, pp. 17-22.
[12] Zhibo Chen, Peng Zhou, and Yun He, "Fast integer pel and fractional pel motion estimation for JVT," JVT-F017.doc, 6th Meeting: Awaji, Island, JP, 5-13 Dec. 2002.
[13] Chok-Kwan Cheung and Lai-Man Po, "A hierarchical block motion estimation algorithm using partial distortion measure," Proceedings of ICIP'97, vol. 3, 1997, pp. 606-609.
[14] Chun-Ho Cheung and Lai-Man Po, "A novel cross-diamond search algorithm for fast block motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 12, no. 12, pp. 1168-1177, Dec. 2002.
[15] Chun-Ho Cheung and Lai-Man Po, "Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation," IEEE Transactions on Multimedia, vol. 7, no. 1, pp. 16-22, Feb 2005
[16] Jian Feng, Kwok-Tung Lo, Hassan Mehrpour, and A. E. Karbowiak, "Adaptive block-matching motion estimation algorithm for video coding," IEE Electronic Letters, vol. 31, no. 18, pp. 1542-1543, 1995.
[17] Mohammed Ghanbari, "The cross-search algorithm for motion estimation," IEEE Transactions on Communication, vol. 38, no. 7, pp. 950-953, Jul. 1990.
[18] Zhongli He, and Ming L. Liou, "A high performance fast search algorithm for block matching motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 7, no. 5, pp. 826-828, Oct. 1997.
[19] Zhongli He, and Ming L. Liou, "Design of fast motion estimation algorithm based on hardware consideration," IEEE Transactions on Circuits and System for Video Technology, vol. 7, no. 5, pp. 819-823, Oct. 1997.
[20] Prabhudev Irappa Hosur, and Kai-Kuang Ma, "Motion vector field adaptive fast motion estimation," presented at the Second International Conference on Information, Communications and Signal Processing, Singapore, Dec. 1999.
[21] Prabhudev Irappa Hosur, and Kai-Kuang Ma, "Report on performance of fast motion estimation using motion vector field adaptive search technique (MVFAST)," ISO/IEC JTC1/SC29/WG11 M5453, Dec. 1999.
[22] Jaswant R. Jain and Anil K. Jain, "Displacement measurement and its application in inter-frame image coding," IEEE Transactions on Communications, vol. COM-29, no. 12, pp. 1799-1808, Dec. 1981.
[23] Xuan Jing and Lap-Pui Chau, "An Efficient Three-Step Search Algorithm for Block Motion Estimation," IEEE Transactions on Multimedia, vol. 6, no. 3, pp. 435-438, Jun. 2004.
[24] Hae Mook Jung, Duch Dong Hwang, Coong Soo Park, and Han Soo Kim, "An annular search algorithm for efficient motion estimation," Proceedings of International Picture Coding Symposium, 1996, pp. 171-174.
[25] Donald Ervin Knuth. The art of computer programming, Vol. 3 - Sorting and Searching. Addison-Wesley, Reading MA, 1973.
[26] Toshio Koga, Kazumoto. Iinuma, Akira Hirano, Yukihiko Iijima, and Tatsuo Ishiguro, "Motion compensated interframe coding for video conferencing," in Proceedings of National Telecommunications Conference, New Orleans, L.A, Nov.-Dec. 1981, pp. G5.3.1-G.5.3.5.
[27] Liang-Wei Lee, Jhing-Fa Wang, Jau-Yien Lee, and Jung-Dar Shie, "Dynamic search window adjustment and interlaced search block-matching algorithm," IEEE Transactions on Circuits System for Video Technology, vol. 3, no. 1, pp. 85-87, Feb.1993.
[28] Xiaobing Lee and Ya-Qin Zhang, "A fast hierarchical motion-compensation scheme for video coding using block-feature matching," IEEE Transactions on Circuits System for Video Technology, vol. 6, no. 6, pp. 627-635, Dec. 1996.
[29] Renxiang Li, Bing Zeng, and Ming L. Liou, " A New Three-Step Search Algorithm for Block Motion Estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 4, no.4, pp.438-442, Aug 1994
[30] Yongfang Liang, Ishfaq Ahmad, Jiancong Luo, Yu Sun and Viswanathan Swaminathan, "On Using Hierarchical Motion History for Motion Estimation in H.264/AVC," IEEE Transactions on Circuits and System for Video Technology, vol. 15, no.12, pp.1594-1603, Dec 2005
[31] Beide Liu and André Zaccarin, "New fast algorithms for estimation of block motion vectors," IEEE Transactions on Circuits and System for Video Technology, vol. 3, no. 2, pp. 148-157, Apr. 1993.
[32] Lurng-Kuo Liu and Ephraim Feig, "A block-based gradient descent search algorithm for block motion estimation in video coding," IEEE Transactions on Circuits and System for Video Technology, vol. 6, no. 4, pp. 419-422, Aug. 1996.
[33] Jianhua Lu and Ming L. Liou, "A simple and efficient search algorithm for block-matching motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 7, pp. 429-433, Apr. 1997.
[34] Kai-Kuang Ma and Prabhudev Irappa Hosur, "Performance report of motion vector field adaptive search technique (MVFAST)," ISO/IEC JTC1/SC29/WG11 M5851, Noordwijkerhout, Netherlands, Mar. 2000.
[35] James B. MacQueen, "Some methods for classification and analysis of multivariate observations", Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability, pp 281-297, vol.1, University of California Press, 1967.
[36] Arun N. Netravali and Barry G. Haskell, Digital Pictures Representation and Compression. New York: Plenum, 1988.
[37] Yao Nie and Kai-Kuang Ma, "Adaptive rood pattern search for fast block-matching motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 11, no. 12, pp. 1442-1449, Dec. 2002.
[38] Jo Yew Tham, Surendra Ranganath, and Ashraf A. Kassim, "Highly scalable wavelet based video codec for very low bit-rate environment," IEEE Journal on Selected Areas in Communications. (Special Issue on Very Low Bit-Rate Coding), Jan. 1998.
[39] Jo Yew Tham, Surendra Ranganath, Maiteya Ranganath, and Ashraf A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 8, no. 4, pp. 369-377, Aug. 1998.
[40] Alexis M. Tourapis, Oscar C. Au, and Ming L. Liou, "Fast block-matching motion estimation using advanced predictive diamond zonal search (APDZS),"ISO/IEC JTC1/SC29/WG11 MPEG2000/M5865, Noordwijkerhout, The Netherlands, Mar. 2000.
[41] Alexis M. Tourapis, Oscar C. Au, and Ming L. Liou, "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.
[42] Alexis M. Tourapis, Oscar C. Au, and Ming L. Liou, Guobin Shen, and Ishfaq Ahmad, "Optimizing the MPEG-4 encoder-advanced diamond zonal search," Proceedings of International Symposium on Circuits and System (ISCAS), Geneva, Switzerland, Jun. 2000, pp. 674-680.
[43] Alexis M. Tourapis, Oscar C. Au, and Ming L. Liou, "Highly efficient predictive zonal algorithms for fast block-matching motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 12, no. 10, pp. 934-947, Oct. 2002.
[44] Lai-Man Po and Wing-Chung Ma, "A novel four-step search algorithm for fast block motion estimation," Transactions on Circuits and System for Video Technology, vol. 6, no. 3, pp. 313-317, Jun. 1996.
[45] Atul Puri, Hsueh-Ming Hang and Donald L. Schilling, "An efficient block matching algorithm for motion-compensated coding," Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Speech, Signal Processing, 1987, pp. 1063-1066.
[46] Ralf Schäfer, Thomas Wiegand and Heiko Schwarz, "The emerging H.264/AVC standard," EBU Technical Review, Jan 2003
[47] Yun-Qing Shi and X. Xia, "A thresholding multiresolution block matching algorithm," IEEE Transactions on Circuits and System for Video Technology, vol. 7, no. 2, pp. 437-440, Apr. 1997.
[48] Byung Cheol Song and Jong Beom Ra, "A hierarchical block matching algorithm using partial distortion criteria," Proceedings of VCIP Visual Communications on Image Processing, San Jose, CA, 1998, pp. 88-95.
[49] Xudong Song, Tihao Chiang, and Ya-Qin Zhang, "A scalable hierarchical motion estimation algorithm for MPEG-2," Proceedings of ICIP, 1998, pp. IV126-IV129.
[50] Ram Srinivasan and K. Ramamohan Rao, "Predictive coding based on efficient motion estimation," IEEE Transactions on Circuits and System for Video Technology, vol. Com-33, no. 8, pp. 888-896, Aug. 1985.
[51] Shen-Chuan Tai, Chong-Shou Yu, and Che Wei Lee, "Double-layered initial search pattern for fast motion estimation," Proceedings of Internet, Processing, System, and Interdisciplinary, Amalfi, Italy, Feb. 2005.
[52] Thomas Wiegand, Gary J. Sullivan, Gisle Bjntegaard, and Ajay Luthra, "Overview of the H.264/AVC video coding standard," IEEE Transactions on Circuits and System for Video Technology, vol. 13, no. 7, pp. 560-576, July 2003.
[53] Thomas Wiegand and Gary J. Sullivan, Study of final committee draft of joint video specification (ITU-T Rec. H.264jISO/IEC 14496-10AVC), Draft 2 JVT- G050d2, Mar. 2003.
[54] Jie-Bin Xu, Lai-Man Po, and Chok-Kwan Cheung, "A new prediction model search algorithm for fast block motion estimation," IEEE International Conference on Image Processing, 1997, pp. 610-613.
[55] Chong-Shou Yu and Shen-Chuan Tai," Adaptive Double-Layered Initial Search Pattern for Fast Motion Estimation," IEEE Transactions on Multimedia, vol. 8, no.6, pp.1109-1116, Dec 2006
[56] Bing Zeng, Renxiang Li, and Ming. L. Liou, "Optimization of fast block motion estimation algorithms," IEEE Transactions on Circuits and System for Video Technology, vol. 7,no. 6, pp. 833-844, Dec. 1997.
[57] Weiguo Zheng, Ishfaq Ahmad, and Ming L. Liou, "Adaptive motion search with elastic diamonds for MPEG-4 video encoding," Proceedings of International Conference on Image Processing, Thessaloniki, Greece, Oct. 2001, pp. 377-380.
[58] Ce Zhu, Xiao Lin, and Lap-Pui Chau, "Hexagon-Based Search Pattern for Fast Block Motion Estimation," IEEE Transactions on Circuits and System for Video Technology, vol. 12, pp. 349-355, May 2002.
[59] Ce Zhu, Xiao Lin, Lappui Chau, and Lai-Man Po, "Enhanced Hexagonal Search for Fast Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, no. 10, pp.1210-1214, Oct. 2004.
[60] Shan Zhu and Kai-Kuang Ma, "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation," IEEE Transactions on Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000.