視訊壓縮標準MEPG-1, MPEG-2, H.261, 及 H.263，均以方塊比對演算法(BMA)做動態預測及補償。然而方塊比對演算法無法掌握影像的旋轉及縮放，並且當鄰近區塊的動態向量不同時會產生所謂的方塊效應。為了解決這個問題，MPEG-4提出了一個新的動態補償方式，此方式是以網格覆蓋影像並且透過更廣義的空間轉換(warping)做動態預測及補償。

本論文提出一動態複雜度階層式網格(MCHM)產生器，其中包含了intra模式與inter模式。intra模式決定每一個節點的位置，為了使MCHM達到各種效果，本論文設計基於雙重三步搜尋法之三種動態補償方法。新提出的雙重三步搜尋能確保找出更佳的動態向量。MCHM的影像空間轉換是使用節點的控制率來完成。在MCHM中，我們分別推導出三種節點控制率的方程式。這三種節點分別為：GN、SN、BN。

模擬結果包括了intra模式跟inter模式。在intra模式中，實驗使用了三種影像動態模式：1)靜態背景、2)影像縮放及3)影像平移。實驗結果顯示所提出之MCHM方法更能準確的將節點配置在動態向量較複雜的區域。inter模式的實驗使用Flower 與 Tennis兩個影像序列。實驗結果顯示，我們提出的方法比傳統沒有動態補償的方法提高了1db的影像品質。

The block matching algorithm (BMA) is used by MPEG-1, -2/H.261, H.263 for motion prediction/compensation. BMA presents difficulties in scenes with moving objects, rotating objects, or camera zooming. Moreover, when adjacent blocks are assigned different motion vectors, the BMA may generate a discontinuity in the decoding image called blocking artifacts. For these reasons, MPEG-4 proposes a new method for motion compensation. In the method, an image is represented as a “mesh” and motion compensation is accomplished by more general spatial transformation (warping).

This thesis proposed a motion complexity hierarchical mesh generator in which both intra and inter mode are considered. In the intra mode, the generator determines the position of each node. To meet different purposes in generating the MCHM, three types of motion estimation based on the dual three-step search are designed. The novel dual three-step search is proposed to guarantee to find a better motion vector. The image warping of the proposed MCHM is accomplished by using the control rate of the node. We derived the control rate formula for the three types of nodes used in the proposed MCHM. The three types of nodes are: the general node, the special node and the boundary node.

Simulation results including the intra mode and the inter mode are presented. Three types of motion models were used in the intra mode: 1) static background, 2) scaling scene and 3) shifting scene. Experiment results show that the proposed MCHM can place nodes more densely in the area with more complex motion. Two sequence were used in the inter mode experiments. Results show that the PSNR of our proposed method is 1 db higher than the method without motion compensation.

[1]ISO/IEC JTC1/SC29/WG N2502a, ISO/IEC 14496-2 Visual, Atlantic City, October 1998.

[2]Gonzalez and Woods, Digital Image Processing, Addison Wesley, 1993.

[3]P. Hsu, K. J. R. Liu and T. Chen, “A Low Bit-Rate Video Codec Based on Two-Dimensional Mesh Motion Compensation with Adaptive Interpolation,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 11, No. 1, pp. 111-117, January 2001.

[4]C. Lin and C. Y. Hsu, “A New Motion Compensation Method for Image Sequence Coding Using Hierarchical Grid Interpolation,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 4, No. 1, pp. 42-52, February 1994.

[5]R. Li, B. Zeng and M. L. Liou, “A New Three-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 4, pp. 438-443, August 1994.

[6]A. Nosratinia, “New Kernels for Fast Mesh-Based Motion Estimation,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 11, No. 1, pp. 40-51, January 2001.

[7]Y. Nakaya and H. Harashima, “Motion Compensation Based on Spatial Transformations,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 4, No. 3, pp. 339-367, June 1994.

[8]G. J. Sullivan and R. L. Baker, “Motion compensation for video compression using control grid interpolation,” in Proc. IEEE ICASSP, vol. 4, May 1991, pp. 2713–2716.

[9]M. Sonka, V. Hlavac and R. Boyle, Image Processing, Analysis and Machine Vision, P.W.S, 1999.

[10]A. M. Tekalp, P. V. Beek, N. Zhuang, I. Celasun and M. Xia, “Hierarchical 2-D Mesh Representation, Tracking and Compression for Object-Based Video,” IEEE Trans. on Circuits and Systems for Video Tech., Vol. 9, No. 2, pp. 353-369, March 1999.

[11]A. M. Tekalp, I. Celasun, E. Ilgaz, P. V. Beek and N. Zhuang, “Optimal Hierarchical Design of 2D Dynamic Meshes for Videos,” Image Processing, ICIP 98. Proceedings, Vol. 8, pp. 899-903, 1998

[12]A. M. Tekalp and Y. Altunbasak, “Closed-Form Connectivity-Preserving Solutions for Motion Compensation Using 2-D Meshes,” IEEE Trans. on Image Processing, Vol. 6, No. 9, pp. 1255-1269, September 1997.

[13]A. M. Tekalp, P. V. Beek, C. Toklu and B. Gunesl, “Two-Dimensional Mesh-Based Visual-Object Representation for Interactive Synthetic/Natural Digital Video,” Proceedings of the IEEE, Vol. 86, No. 6, pp. 1028-1051, June 1998.

[14]A. M. Tekatp, H. Gokcetekin and I. Cetasun, “2D Mesh-Based Detection and Representation of an Occluding Object for Object-Based Video,” Speech and Signal Processing Proceedings, IEEE International Conference, Vol. 4, pp. 1915-1918, 2000.

[15]A. M. Tekalp and Y. Altunbasak, “Occlusion-Adaptive, Content-Based Mesh Design and Forward Tracking,” IEEE Trans. on Image Processing, Vol. 6, pp. 1270-1280, September 1997.

[16]Y. Wang and O. Lee, “Active Mesh-a Feature Seeking and Tracking Image Sequence Representation Scheme,” IEEE Trans. on Image Processing, Vol. 3, No. 5, pp. 610-624, September 1994.

[17]Y. Wang and O. Lee, “Use of two-dimensional deformable mesh structures for video coding, part I—The synthesis problem: Mesh-based function approximation and mapping,” IEEE Trans. on Circuits and Systems for Video Tech, Vol. 6, NO 6, December 1996.

[18]Y. Wang, O. Lee, and A. Vetro, “Use of two-dimensional deformable mesh structures for video coding, part II—The analysis problem and a region-based coder employing an active mesh representation,” IEEE Trans. on Circuits and Systems for Video Tech, Vol. 6, NO 6, December 1996.

[19]Y. Wand and J. Ostermann, “Evaluation of Mesh-Based Motion Estimation in H.263-Link Coders,” IEEE Trans. on Circuits and Systems for Video Tech, Vol. 8, NO. 3,June 1998.

[20]S. Zhu and K. Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation,” IEEE Trans. On Image Processing, Vol. 9, NO 2, February 2000.

[21]王璟勳, “內容導向 MPEG-4 網格物件之建立”, 碩士論文, 國立成功大學, 2002.

[22]戴顯權, “資料壓縮,” 紳藍出版社, 2001.