淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-1808200803241200
中文論文名稱 基於次巨集區塊固定取樣點SSAD預測SAD的移動估算法
英文論文名稱 A Motion Estimation Method of Predicting SAD based on Sub-Macro-Block Fixed-Sample-Points SSAD
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士在職專班
系所名稱(英) Department of Electrical Engineering
學年度 96
學期 2
出版年 97
研究生中文姓名 陳坤勝
研究生英文姓名 Kun-Sheng Chen
學號 789350039
學位類別 碩士
語文別 中文
口試日期 2008-07-04
論文頁數 79頁
口試委員 指導教授-江正雄
委員-陳信全
委員-楊維斌
中文關鍵字 移動估算  SMB  固定取樣點  SAD預測  SSAD  次巨集區塊  預測SAD  Sub-Macro-Block  Fixed-Sample-Points 
英文關鍵字 Sub-Macro-Block  SMB  Fixed-Sample-Points  Predictive SAD  Predicting SAD  SSAD  Motion Estimation  Sub-sample SAD 
學科別分類 學科別應用科學電機及電子
中文摘要 移動估算演算法的優劣,對於動態影像壓縮的品質、計算複雜度與計算量有很大的影響,因此改善移動估算搜尋演算法的議題一直被討論著。過去有許多搜尋法不斷探討候選區塊各種不同比對的方法來搜尋移動向量,如眾所熟悉的全區塊搜尋法(Full Search)、三步搜尋法(Three Step Search)、四步搜尋法(Four Step Search)、鑽石搜尋法(Diamond Search)、Cross Diamond Search(CDS)等等。在即時影像研究中,如何得到良好的影像品質是的重要課題,除此之外對於計算的複雜度、計算量的大小、搜尋點數的多寡以及搜尋時間的長短也都是大家時常探討的重點方向。
本篇論文是針對搜尋點數作為探討的主題,對候選區塊做次巨集區塊的分割,加上用固定取樣點的方式來大量減少像點的計算。一般而言,當大量減少像點取樣的同時,很容易產生取樣失真的風險,本篇論文善用候選區塊(Candidate Block)所分割成的次巨集區塊(Sub-Macro-Block;簡稱SMB),同時利用候選區塊(Candidate Block)與當前區塊(Current Block)之間存有區域關聯性的概念,以此來降低差異、降低干擾;並採用SMB固定取樣點的SSAD(Sub-sample SAD)來預測候選區塊的SAD,減少運算的點數、減少運算量。
本論文是以預測的SAD套入不同搜尋法當中來搜尋移動向量(Motion Vector),最後實際計算的PSNR值並非預測值,是真實的PSNR。針對搜尋點的數降低、搜尋時間的改善以及所產生的PSNR結果,都是本論文著眼的重點。雖然降低平均搜尋點數與得到良好的影像品質是不容易完全兼得,然而本論文的演算法不但可以達成減少平均搜尋點數的目的,得以提升效能,同時也能得到不錯的影像品質。
英文摘要 The motion estimation algorithm of video sequence always influences image compressed quality, computational complexity and computational loading. Therefore, the issue of macro blocks matching has been discussed for a long time. In the past, many search methods explored how to find the minimum SAD of candidate blocks in the search area, the Motion Vector, such as the well-known methods-Full Search, Three-Step Search, Four-Step Search, Diamond Search, and Cross Diamond Search, …, etc. However, the methods of Three-Step Search, Four-Step Search, Diamond Search, and Cross Diamond Search not only reduce blocks matching and calculation compared to the Full Search but also have good PSNR. Although it is important to have a good image quality at a real time video display, we should not ignore to reduce the computation complexity and computational loading.
This research work focuses on the topic of the search points and run time reduction. We propose to use a few Fixed-Sample-Points of 9 Sub-Macro- Blocks (SMB) that are separated from Candidate Block to calculate average Sub-sample SAD (SSAD), and then to predict Candidate-Block SAD. The Predictive SAD can be used to combine any native search method algorithms for Motion Vector searching. It can reduce computation complexity and computational loading. Based on the localized relationship of Sub-sampling Fixed-Samples-Points and SMBs between Candidate Block and Current Block, we divide the Candidate Block into 9 SMBs to reduce the sub-sampling distortion risk. According to the PSNR simulation, this research work cannot reduce search points and search time but also get an acceptable image quality.
論文目次 目 錄
第一章: 緒論
1.1 前言 1
1.2 研究動機 2
1.3 論文架構 2
第二章: 預測編碼與移動估算概念簡介
2.1 引言 3
2.2 壓縮編碼基本架構 3
2.3預測編碼簡介 5
2.3.1預測編碼基本概念 5
2.3.2 Intra預測概述 5
2.3.3 Inter預測簡介 7
2.3.4 移動估算簡介 8
第三章: 搜尋法介紹
3.1 全域搜尋法(Full Search)簡介 11
3.2 三步搜尋法(Three Step Search)簡介 12
3.3 新三步搜尋法(New Three Step Search)簡介 14
3.4 四步搜尋法(Four Step Search)簡介 16
3.5 鑽石搜尋法(Diamond Search)簡介 19
3.6 Cross Diamond Search (CDS)簡介 20
第四章: 研究題目
4.1 研究構想 26
4.2 方法介紹 27
4.2.1 次巨集區塊(Sub-Macro-Block)與固定取樣點介紹 27
4.2.2 SMB與固定取樣點的優點 30
4.2.3 SAD值的預測方式 31
4.2.4 SAD預測流程圖簡介 33
第五章: 模擬結果
5.1 模擬環境 35
5.2 PSNR、Search Point (Pt)、Run Time的比較方式 36
5.3 實驗模擬結果 37
5.3.1 SMB Search與原始Full Search的比較 38
5.3.2 SMB Search與原始Three Step Search的比較 44
5.3.3 SMB Search與原始New Three Step Search的比較 50
5.3.4 SMB Search與原始Four Step Search的比較 56
5.3.5 SMB Search與原始SCDS的比較 62
5.3.6 SMB Search與原始Cross Diamond Search的比較 68
第六章: 結論與展望 74
參考文獻 77

圖 目
圖2.1 移動估算的Encoder Block Diagram 4
圖2.2 移動估算的Decoder Block Diagram 4
圖2.3 Intra 4×4 預測模式 6
圖2.4 Intra 16×16 預測模式 7
圖2.5 Inter預測模式以H.264為例的巨集區塊7種切割方式 8
圖2.6 移動向量示意圖 9
圖3.1 全域搜尋法(Full Search)示意圖 12
圖3.2 Three Step Search示意圖 13
圖3.3 New Three Step Search示意圖,Case-1 15
圖3.4 New Three Step Search示意圖,Case-2 16
圖3.5 Four Step Search示意圖,Case-1 17
圖3.6 Four Step Search示意圖,Case-2 18
圖3.7 Diamond Search示意圖 20
圖3.8 CDS的First-Step-Stop示意圖 21
圖3.9 CDS的Second-Step-Stop示意圖 22
圖3.10 CDS的搜索過程示意圖Case-1 23
圖3.11 CDS的搜索過程示意圖Case-2 24
圖4.1 一個Macro Block總共分成9個Sub-Macro-Block 27
圖4.2 每一個SMB有5個取樣點,9個SMB總共45個取樣點 28
圖4.3 以SMB1為例的5個取樣點位置分佈 29
圖4.4 以9個SMB的45個像點預測SAD取代原始MB搜尋MV 30
圖4.5 SAD預測流程圖 34
圖5.1 SMB Search與原始Full Search的Clair PSNR比較圖 38
圖5.2 SMB Search與原始Full Search的Coastguard PSNR比較圖 38
圖5.3 SMB Search與原始Full Search的Container PSNR比較圖 39
圖5.4 SMB Search與原始Full Search的Football PSNR比較圖 39
圖5.5 SMB Search與原始Full Search的Foreman PSNR比較圖 40
圖5.6 SMB Search與原始Full Search的Garden PSNR比較圖 40
圖5.7 SMB Search與原始Full Search的Mobile PSNR比較圖 41
圖5.8 SMB Search與原始Full Search的Tennis PSNR比較圖 41
圖5.9 SMB Search與原始3SS的Claire PSNR比較圖 44
圖5.10 SMB Search與原始3SS的Coastguard PSNR比較圖 44
圖5.11 SMB Search與原始3SS的Container PSNR比較圖 45
圖5.12 SMB Search與原始3SS的Football PSNR比較圖 45
圖5.13 SMB Search與原始3SS的Foreman PSNR比較圖 46
圖5.14 SMB Search與原始3SS的Garden PSNR比較圖 46
圖5.15 SMB Search與原始3SS的Mobile PSNR比較圖 47
圖5.16 SMB Search與原始3SS的Tennis PSNR比較圖 47
圖5.17 SMB Search與原始N3SS的Claire PSNR比較圖 50
圖5.18 SMB Search與原始N3SS的Coastguard PSNR比較圖 50
圖5.19 SMB Search與原始N3SS的Container PSNR比較圖 51
圖5.20 SMB Search與原始N3SS的Football PSNR比較圖 51
圖5.21 SMB Search與原始N3SS的Foreman PSNR比較圖 52
圖5.22 SMB Search與原始N3SS的Garden PSNR比較圖 52
圖5.23 SMB Search與原始N3SS的Mobile PSNR比較圖 53
圖5.24 SMB Search與原始N3SS的Tennis PSNR比較圖 53
圖5.25 SMB Search與原始4SS的Claire PSNR比較圖 56
圖5.26 SMB Search與原始4SS的Coastguard PSNR比較圖 56
圖5.27 SMB Search與原始4SS的Container PSNR比較圖 57
圖5.28 SMB Search與原始4SS的Football PSNR比較圖 57
圖5.29 SMB Search與原始4SS的Foreman PSNR比較圖 58
圖5.30 SMB Search與原始4SS的Garden PSNR比較圖 58
圖5.31 SMB Search與原始4SS的Mobile PSNR比較圖 59
圖5.32 SMB Search與原始4SS的Tennis PSNR比較圖 59
圖5.33 SMB Search與原始SCDS的Claire PSNR比較圖 62
圖5.34 SMB Search與原始SCDS的Coastguard PSNR比較圖 62
圖5.35 SMB Search與原始SCDS的Container PSNR比較圖 63
圖5.36 SMB Search與原始SCDS的Football PSNR比較圖 63
圖5.37 SMB Search與原始SCDS的Foreman PSNR比較圖 64
圖5.38 SMB Search與原始SCDS的Garden PSNR比較圖 64
圖5.39 SMB Search與原始SCDS的Mobile PSNR比較圖 65
圖5.40 SMB Search與原始SCDS的Tennis PSNR比較圖 65
圖5.41 SMB Search與原始CDS的Claire PSNR比較圖 68
圖5.42 SMB Search與原始CDS的Coastguard PSNR比較圖 68
圖5.43 SMB Search與原始CDS的Container PSNR比較圖 69
圖5.44 SMB Search與原始CDS的Football PSNR比較圖 69
圖5.45 SMB Search與原始CDS的Foreman PSNR比較圖 70
圖5.46 SMB Search與原始CDS的Garden PSNR比較圖 70
圖5.47 SMB Search與原始CDS的Mobile PSNR比較圖 71
圖5.48 SMB Search與原始CDS的Tennis PSNR比較圖 71


表 目
表5.1 測試影片 35
表5.2 SMB Search與原始Full Search的比較表 42
表5.3 SMB Search與原始Full Search的Average Run Time 43
表5.4 SMB Search與原始Three Step Search的比較表 48
表5.5 SMB Search與原始Three Step Search的Average Run Time 49
表5.6 SMB Search與原始New Three Step Search的比較表 54
表5.7 SMB Search與原始N33S的Average Run Time 55
表5.8 SMB Search與原始Four Step Search的比較表 60
表5.9 SMB Search與原始Four Step Search的Average Run Time 61
表5.10 SMB Search與原始Small Cross Diamond Search的比較表 66
表5.11 SMB Search與原始SCDS的Average Run Time 67
表5.12 SMB Search與原始Cross Diamond Search的比較表 72
表5.13 SMB Search與原始CDS的Average Run Time 73
參考文獻 [1] ISO/IEC JTC1, Generic Coding of Audiovisual Objects –Part 2: Visual (MPEG-4 Visual), ISO/IEC 14496-2, Version 1: January 1999; Version 2: January 2000; Version 3: January 2001
[2] ITU-T Recommendation H.261: Video Codec for Audiovisual Services at Px64 K bits, ITU, 1993.
[3] Draft ITU-T Recommendation H.263: Video Coding for Low Bit rate Communication, ITU, May. 1996.
[4] Draft ITU-T Recommendation H.263+: Video Coding for Low Bitrate Communication, ITU, July 1997.
[5] ITU-T/SG 16/VCEG, Video Codec Test Model Long Term Number 8(TML-8). Doc. VCEG-N10, July. 2001.
[6] JVT Reference Software old jm Version 10.1,
http://iphome.hhi.de/suehring/tml/download/old jm/ .
[7] B.Liu; A.Zaccarin ” New fast algorithms for the estimation of block matching vectors ”, IEEE Trans. Circuits Sys. VideoTechnol., vol. 3, no. 2, pp. 148-158, April 1993.
[8] S. W. Wang and Y. K. Lai, “A subsampling motion estimation algorithm based on probability analysis”, June 2007.
[9] Jen-Shiun Chiang, Hsin-Guo Chou, and Je-Yu Tzou ”An efficient and regular motion estimation algorithm for MPEG4-AVC/H.264 coding,” Cellular Neural Networks and Their Applications, pp .253-256, May. 2005
[10] Namuduri, K.R.; Aiyuan Ji; “Computation and performance trade-offs in motion estimation algorithms”, Information Technology: Coding and Computing, 2001. Proceedings. International Conference on 2-4 April 2001 Page(s):263 - 267
[11] Subramanya, S.R.; Patel, H.; Ersoy, I.; “Performance evaluation of block-based motion estimation algorithms and distortion measures”, Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference on Volume 2, 2004 Page(s):2 - 7 Vol.2
[12] Sorwar, G.; “Adaptive-centre candidate decimation distance-dependent thresholding search for motion estimation”, Information Technology and Applications, 2005. ICITA 2005. Third International Conference on Volume 1, 4-7 July 2005 Page(s):674 - 679 vol.1
[13] So. M.F. Wu, A.” Four-step genetic search for block motion estimation ”, Int. Conf Signal Process. Proceed, Vol. 3, pp.1393 -1396, 1998.
[14] http://www.ee.cityu.edu.hk/~lmpo/publications/; (Dr. Lai-Man Po)
[15] C. H. Cheung and L. M. Po, “A novel small-cross-diamond search algorithm for fast video coding and videoconferencing applications”, in Proc. IEEE ICIP, Sept. 2002.
[16] C. H. Cheung and L. M. 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.
[17] Reoxiang Li, Bing Zeng and Liou, M.L, " A new three-step search algorithm for block motion estimation" IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4,pp.438-442, Aug. 1994
[18] Lai-Man Po, Wing-Chung Ma," A novel four-step search algorithm for fast block motion estimation" IEEE Transactions on Circuits and Systems for Video Technology, Vol 6, pp.313 –317, June 1996
[19] Shan Zhu and Kai-Kuang Ma, ”A New Diamond Search Algorithm for Fast Bock-Matching Motion Estimation”, IEEE Trans. Iinage Process., vol. 9, no. 2. Feb. 2000.
[20] C. H. Cheung and L. M. Po, "A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation," IEEE Trans. on Circuits and Systems for Video Technology, Vol.12, No. 12, pp. 1168-1177, Dec. 2002.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-08-20公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信