臺灣博碩士論文加值系統

近年來隨著網路和多媒體技術的進步，由聲音和影像構成的多媒體內容正迅速的成長，然而多媒體的資料若未經壓縮處理，將需要大量的儲存空間和大的頻寬來傳送資料。為解決這問題，在視訊影像的壓縮標準中，移動估測扮演著關鍵的技術，但是準確的移動估測將需要耗費相當大的計算量以及搜尋時間，因此有許多研究提出快速搜尋演算法以降低移動估測所需的計算量，然而其代價是喪失了其影像品質，導致壓縮結果不良。在本篇論文我們提出一個新的移動估測演算法，稱為『調適性移動估測部份失真搜尋演算法』 (Adaptive Motion Estimation with Partial Distortion Search, AMEPDS)，提出的演算法是利用先前畫面移動向量的資訊，將區塊分成潛在性獨立區塊與潛在性相依區塊，再利用現在區塊鄰近已編碼區塊的移動向量資訊，建立預測搜尋區域，並依據各區塊之特性採用不同的移動估測演算法，來達到最佳的估測準確性和最低的計算複雜度。在演算法中我們引入提早搜尋停止機制和精煉的機制。我們對本論文所提出AMEPDS演算法以十個視訊序列做實驗，模擬結果顯示AMEPDS相較於全區域搜尋演算法 (Full Search, FS)在速度的提昇約15.58~150.5倍，而AMEPDS的影像品質方面則相當接近於全區域搜尋演算法。

With the advances of digital technologies and the proliferation of communication networks, multi-media contents consisting of both audio and video recordings continue to grow rapidly. Multi-media data generally takes huge storage space and also requires substantial amount of channel bandwidth to transmit. Many video coding standards exploit motion estimation (ME) to compress the video data by removing the inter-frame redundancy. This paper presents a new motion estimation algorithm, called the adaptive motion estimation with partial distortion search (AMEPDS). The AMEPDS algorithm exploits the information gathered from the previous frame to derive a parameter, called CP (Correlation parameter), and employs CP to classify the blocks in the current frame into potentially dependent blocks and potentially independent blocks. AMEPDS applies different motion estimation methods and adaptive search areas for different types of blocks to achieve better estimation accuracy and lower computational complexity. Early search termination is also introduced in AMEPDS to further speed up the process of motion estimation. Experimental results showed that the proposed algorithm AMEPDS can achieve a speedup of 15.58 to 150.5 times compared to the traditional full search algorithm, while maintaining similar visual quality.

中文摘要 i
Abstract ii
誌謝 iii
目 錄 iv
圖目錄 vi
表目錄 ix

第一章 緒論 1
1-1 簡介 1
1-2 研究動機與目的 3
1-3 論文架構 3
第二章 視訊編碼介紹 4
2-1 視訊壓縮原理簡介 4
2-1-2 評估兩區塊的匹配程度的方法 7
2-1-3 離散餘弦轉換 7
2-1-4 量化 8
2-1-5 掃描 9
2-1-6 可變長度編碼 10
2-2 色彩空間 10
2-3 YCbCr取樣格式 12
2-4 視訊編碼標準常用的視訊格式 13
2-5 影像品質 13
第三章 常見的區塊匹配演算法 14
3-1 三步驟搜尋演算法 15
3-2 新三步驟搜尋演算法 16
3-3 增強預測帶搜尋演算法 19
3-3-1 預測的選擇 19
3-3-2 調適性提早搜尋停止 21
3-3-3 移動向量的精煉 21
3-3-4 雙模式精煉 22
3-4 正規化部份失真搜尋演算法 23
第四章 調適性移動估測部份失真搜尋演算法 27
4-1 調適性移動估測部份失真搜尋演算法 27
4-2 非畫面邊緣區塊的分類 27
4-3 提早搜尋停止機制 29
4-4 使用在潛在性獨立區塊的調適性搜尋區域NPDS 30
4-5 潛在性相依區塊的預測搜尋區域 32
4-7 對潛在性相依區塊的搜尋結果作精煉 35
4-8 畫面邊緣的區塊 35
4-9 搜尋視窗(search window)之討論 36
4-10 AMEPDS演算法的整理 36
第六章 結論 69
參考文獻 70

圖1-1 (a)、(b)為兩張連續NEWS視訊序列畫面...2
圖2-1 (a)視訊編碼流程圖 (b)視訊解碼流程圖...5
圖2-2 移動估測示意圖：(a)目前畫面及區塊 (b)參考畫面 (c)目前區塊 (d)搜尋區域.6
(e)移動向量..........6
圖2-3 鋸齒掃描.........................10
圖2-4 三種YCbCr取樣格式.................12
圖3-1 三步驟搜尋演算法圖示...............15
圖3-2 新三步驟搜尋演算法圖示.............17
圖3-3 新三步驟搜尋演算法的流程圖.........18
圖3-4 EPZS演算法中的時間性預測和空間性預測..20
圖3-5 附加的固定預測在搜尋範圍±8...........20
圖3-6 使用在EPZS的小鑽石形搜尋模式.........21
圖3-7 使用在EPZS的方形搜尋模式............22
圖3-8 延伸鑽石形搜尋模式..................22
圖3-9 EPZS雙模式精煉的例子................23
圖3-10 部份失真計算的順序.................24
圖3-11 NPDS的螺旋掃描路徑................25
圖3-12 NPDS計算區塊失真匹配的流程.........26
圖4-1 在AMEPDS演算法使用到的符號..........28
圖4-2 計算相關性參數CP...................29
圖4-3 SAD機率分佈圖......................30
圖4-4 螺旋掃描路徑.......................31
圖4-5 調適性搜尋範圍的NPDS演算法之流程圖....32
圖4-6 現在區塊Bc的四個鄰近區塊和Co-located區塊Bp所產生之搜尋區域............34
圖4-7 畫面邊緣的區塊......................35
圖4-8 AMEPDS演算法流程圖..................38
圖5-1 第一組至第四組測試用視訊序列：(a) Akiyo (b) Coastguard (c) Container (d) Foreman...............40
圖5-2 第五組至第八組測試用視訊序列：(e) Hall (f) Mobile (g) Paris (h) Stefan.41
圖5-3 第九組至第十組測試用視訊序列：(i) Waterfall (j)Football....42
圖5-4 使用Akiyo視訊序列比較七種演算法之PSNR效能..........42
圖5-5 使用Coastguard視訊序列比較七種演算法之PSNR效能.....43
圖5-6 使用Container視訊序列比較七種演算法之PSNR效能......43
圖5-7 使用Foreman視訊序列比較七種演算法之PSNR效能........44
圖5-8 使用Hall視訊序列比較七種演算法之PSNR效能...........44
圖5-9 使用Mobile視訊序列比較七種演算法之PSNR效能.........45
圖5-10 使用Paris視訊序列比較七種演算法之PSNR效能.........45
圖5-11 使用Stefan視訊序列比較七種演算法之PSNR效能........46
圖5-12 使用Waterfall視訊序列比較七種演算法之PSNR效能.....46
圖5-13 使用Football視訊序列比較七種演算法之PSNR效能......47
圖5-14 使用Akiyo視訊序列比較六種演算法之每一畫面所需的運算量....49
圖5-15 使用Coastguard視訊序列比較六種演算法之每一畫面所需的運算量..49
圖5-16 使用Container視訊序列比較六種演算法之每一畫面所需的運算量.....50
圖5-18 使用Hall視訊序列比較六種演算法之每一畫面所需的運算量....51
圖5-19 使用Mobile視訊序列比較六種演算法之每一畫面所需的運算量..51
圖5-20 使用Paris視訊序列比較六種演算法之每一畫面所需的運算量..52
圖5-21 使用Stefan視訊序列比較六種演算法之每一畫面所需的運算量.52
圖5-22 使用Waterfall視訊序列比較六種演算法之每一畫面所需的運算量.53
圖5-23 使用Football視訊序列比較六種演算法之每一畫面所需的運算量...53
圖5-24 視訊序列Akiyo、Coastguard、Container、Foreman、Hall在六種演算法下之total所需運算量比較圖......................54
圖5-25 視訊序列Mobile、Paris、Stefan、Waterfall、Football在六種演算法下之total所需運算量比較圖..................54
圖5-26 視訊序列Akiyo的第248張原始畫面與七種演算法所重建畫面...59
圖5-27 視訊序列Coastguard的第70張原始畫面與七種演算法所重建畫面....60
圖5-28 視訊序列Container的第259張原始畫面與七種演算法所重建畫面....61
圖5-29 視訊序列Foreman的第177張原始畫面與七種演算法所重建畫面....62
圖5-30 視訊序列Hall的第40張原始畫面與七種演算法所重建畫面....63
圖5-31 視訊序列Mobile的第132張原始畫面與七種演算法所重建畫面.64
圖5-32 視訊序列Paris的第262張原始畫面與七種演算法所重建畫面..65
圖5-33 視訊序列Stefan的第124張原始畫面與七種演算法所重建畫面.66
圖5-34 視訊序列Waterfall的第91張原始畫面與七種演算法所重建畫面.67
圖5-35 視訊序列Football的第28張原始畫面與七種演算法所重建畫面.68

表目錄
表5-1 七種不同演算法之平均PSNR.....................48
表5-2 七種演算法之total運算元的比較.................55
表5-3 七種演算法之每張畫面執行時間的比較.............57
表5-4 在AMEPDS演算法中五個stage各別的使用率.........58

[1] M.-J. Chen, L –G. Chen and T.-D. Chiueh, “One-dimensional full search motion estimation algorithm for video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 5, pp. 504-509, 1994.
[2] J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Transactions on Communications, vol. 29, no. 12, pp. 1799-1808, Dec. 1981.
[3] M. Ghanbari, “The cross-search algorithm for motion estimation,” IEEE Transactions on Communications, vol. 38, pp. 950-953, 1990.
[4] F. H. Cheng and S. N. Sun, “New fast and efficient two-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, pp. 977-983, 1999.
[5] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. Nat. Telecommunication Conf., New Orleans, LA, pp. G.5.3.1-G.5.3.5, 1981.
[6] R. Li, B. Zeng and M.-L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits Systems for Video Technology, vol. 4, no. 4, pp. 438-442, 1991.
[7] L. M. Po and W. C. Ma, “A novel four-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, 1996.
[8] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, pp. 287-290, Feb. 2000.

[9] J. Y. Tham, S. Ranganath, M. Ranganth, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, pp. 369-377, Aug. 1998.
[10] Wang Yan-ni and Fan Yang-yu, “An Adaptive Diamond Searching Algorithm on Space-time Correlation,” in Proceeding of the Fourth International Conference on Image and Graphics, pp. 220-223, 2007.
[11] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 4, pp. 419-423, Aug. 1996.
[12] Hye-Yeon Cheong Tourapis and Alexis Michael Tourapis, “Fast motion estimation within the H.264 codec,” in Proceeding of ICME 2003, vol. 3, pp.517-520, 2003.
[13] K.-L. Chung and L.-C. Chang, “A new predictive search area approach for fast block motion estimation,” IEEE Transactions on Image Processing, vol. 12, no. 6, pp. 648-652, 2003.
[14] Meng-chou Chang and Jun-shan Chien, “An adaptive search algorithm based on block classification for fast block motion estimation,” in Proceedings of the 2006 IEEE International Symposium on Circuits and Systems, pp. 3982 -3985, 2006.
[15] C. K. Cheung and L. M. Po, “Normalized partial distortion search algorithm for block motion estimation,” IEEE Transactions on Circuits Systems for Video Technology, vol.10, pp. 417-422, Apr. 2000.
[16] C. Shen and S. Li, “Search centre prediction - based partial distortion search motion estimation algorithm,” IEE-Electronics Letters, vol. 43, no. 4, pp. 213-214, 2007.
[17] Xuan Jing and Lap-Pui Chau, “Partial distortion search algorithm using predictive search area for fast full-search motion estimation,” IEEE Signal Processing Letters, vol. 14, pp. 840-843, 2007.

[18] Zi-Yin Li and Shan-An Zhu, “A fast and efficient partial distortion search algorithm for block motion estimation,” in Proceeding of International Conference on Control and Automation, pp. 234-236, 2005.
[19] Xiaoquan Yi and Nam Ling, “Improved normalized partial distortion search with dual-halfway-stop for rapid block motion estimation,” IEEE Transactions on Multimedia, vol. 9, no. 5, pp. 995-1003, 2007.
[20] W. Li and E. Salari, “Successive elimination for motion estimation,” IEEE Transactions on Image Processing, vol. 4, no. 1, pp. 105-107, 1995.
[21] Shao-Wei Liu, Shou-Der Wei, Shang-Hong Lai, “Fast optimal motion estimation based on gradient-based adaptive multilevel successive elimination,” IEEE Transactions on Circuits Systems for Video Technology, vol. 18, pp. 263-267, 2008.
[22] Iain E. G. Richardson, H.264 and MPEG-4 Video Compression, John Wiley & Sons, 2003.