移動估算演算法的優劣，對於動態影像壓縮的品質、計算複雜度與計算量有很大的影響，因此改善移動估算搜尋演算法的議題一直被討論著。過去有許多搜尋法不斷探討候選區塊各種不同比對的方法來搜尋移動向量，如眾所熟悉的全區塊搜尋法（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.