臺灣博碩士論文加值系統

區塊匹配演算法（Block Matching Algorithms，BMA），為區塊
移動估計（Block Motion Estimation）技術中最重要的一環。一個優
越的區塊匹配演算法，能迅速的在搜索範圍內，尋找出最佳的匹配區塊。
相對而言，能夠縮減視訊壓縮所需要的時間，且能提供良好的影像品質。

本篇論文提出一個區塊匹配的改善方案，利用區塊彼此間移動向量的
高依存度特性，來預測最佳匹配區塊的座落區域。再進一步配合縮小搜索
範圍，進而能降低區塊匹配比對運算量。區塊彼此間移動向量高依存度是
視訊影像的一大特性，本篇論文利用此性質，推導出一數學運算式，來預
測待處理區塊的最佳匹配區塊其座落位置，因此不須用大範圍搜索，就能
求出最佳匹配區塊。相對而言，搜索範圍變小則區塊匹配的比對運算量也
就減少。實驗中搭配了完全搜索法以及三步搜索法；以搭配完全搜索法為
例，其影像品質僅僅犧牲原始的2.4%，不過在比對運算量方面，大幅減少
到原本計算量的37%。

Block matching algorithms (BMA) play a very important role in the field of motion estimation for video coding. They are efficient to preserve the quality for reconstructed video frames with a minimum cost of computation complexity. Fast BMAs can find an optimal match close to the best match under a full search.

In this paper, we propose a method to further improve the efficiency of the block matching algorithms. This method varies the sizes and the origins of the search areas by utilizing strong spatial correlation of motion vectors. Blocks are classified into two groups: those are fixed-length spaced and those are surrounded by fixed-length spaced blocks. The motion vectors of the former group are produced in larger search areas. For blocks in the latter group, the method seeks their matches in smaller areas and hence increases its efficiency.

誌謝
摘要
ABSTRACT
目錄
表錄
圖錄
一、緒論
1.1研究動機
1.2研究目的
1.3研究方法
1.4論文架構
二、視訊壓縮的基礎理論與文獻探討
2.1視訊壓縮的基本原理
2.2 MPEG視訊層原理
2.3區塊移動估計技術
2.3.1完全搜索演算法
2.3.2三步搜索演算法
2.3.3共軛方向搜索演算法
2.4 區塊移動估計演算法探討與改進
三、運用影像移動依存特性的區塊匹配演算法
3.1基本理論
3.2區塊分割與定義
3.3移動向量權重關係式
3.4演算法
四、電腦模擬與實驗
4.1實驗設備與影像序列
4.2模擬結果與分析
4.3不同大小的單位區間
五、結論與未來展望
參考文獻
簡歷

[1] CD 13818-2 (MPEG), “Information Technology – Generic Coding of Moving Pictures and Associated Audio Information – Part 2: Video”, ISO, 12/93.
[2] J. Koga, K. Iiunuma, A. Hirani, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video Conferencing”, Proceedings of the National Telecommunications Conference, 1981, pp. G5.3.1-5.3.5.
[3] J. Jain and A. Jain, “Displacement Measurement and its Application in Interframe Image Coding”, IEEE Transactions on Communications, Vol.29, No. 12, December 1981, pp. 1799-1808.
[4] R Srinivasan and K Rao, “Predivtive Coding Based on Efficient Motion Estimation”, IEEE Transactions on Communications, Vol. 33, No. 8, August 1985, pp. 888-896.
[5] DIS 11172 (MPEG), “Information Technology – Coding of Moving Pictures and Associated Audio for Digital Storage Media up to about 1.5Mbit/s”, ISO, 12/93.
[6] W. Lee, Y. Kim, R.J. Gove, and C.J. Read, “Media Station 5000: Integration Video and Audio”, IEEE Multimedia, Vol. 1, No. 2, pp. 50-61.
[7] Borko Furht, Greenberg, J. and Westwater, R., Motion Estimation Algorithms for Video Compression, Kluwer Academic Publishers, Norwel, MA, 1997.
[8] Barry G. Haskell, Atul Puri, and Arun N. Netravail, Digital Video: An Introduction to MPEG-2. Chapman & Hall, New York, 1997.
[9] J. L. Mitchell, W. B. Pennebaker, C. E. Fogg and D. J. LeGall, MPEG Video Compression Standard, Chapman & Hall, ITP, New York, 1997.