新一代的影像標準H.264/AVC比之前提出的影像標準有較高的編碼效能。主要是因為在Inter coding中H.264/AVC利用可變的7種區塊模式和可以5個參考畫面來做移動估計；Intra coding利用由於9個區塊模式和多個參考畫面。在計算複雜上卻大大的提昇。為了改善計算複雜度問題，本論文提出三種快速演算法；分別為畫面間模式的選擇、畫面內預估模式的選擇和利用Reuse來減少多個參考畫面。
畫面間模式的選擇提出利用Fuzzy推論，採用影響區塊選擇最重要的2個關係，Mv tightness和Iv compactness，當成Fuzzy set。用這2個重要因素當Fuzzy rule找出所要的區塊模式，以節省計算量的時間。
畫面內模式的選擇，由於每次做一次區塊選擇必需要做9種模式，在這9種模式中，選擇出所要的模式，因此會浪費計算時間。所以提出三步驟方法，只要用6個模式取代原本9 模式，進而減少花費時間。
多個參考畫面用重覆使用移動向量的觀念，利用之前所得的移動向量，來計算出下一張畫面的預測移動向量，以目前的區塊在之前的畫面中鄰近區塊因面積所佔的比例給予權重，計算出移動向量。因此不需要計算到5張reference frame即可達到相同效果使速度上的提升。
經由所提出的三個方法，可以大大的改善因H.264在估移動估計時，所產生的大量計算量進而提升執行速度，且維持好的PSNR和bit-rate。

The JVT H.264/AVC video coding standard has achieved much significantly improved coding efficiency than all existing video coding standards. This is mainly due to the fact the H.264 uses variable block sizes ranging from 4×4 to 16×16 in interframe coding, 9 mode in intraframe coding and multiple reference frame. A brute force rate distortion optimization algorithm is employed to select the best coding mode and reference frame for each macroblocks. As the results, the complexity and computation load increase drastically. In order to reduce the computational complexity, this thesis proposes three fast algorithms to select the block mode and to reuse the motion vector information. The motivation is to reduce the number of candidate block types in motion estimation.
The algorithm uses fuzzy inference in interframe coding with motion vector tightness and the variance of image intensity to determine whether it is necessary to do motion estimation with smaller size block mode. In intra mode decision, three steps algorithm is proposed to reduce 9 modes by 6 modes. The reuse MV algorithm proposed to reduce the computational time of multiple reference frames. From the simulation result, the proposed fast algorithms can save at least 30% encoding time, with a negligible loss of PSNR and the bit-rate increment.

目錄
論文摘要 ----------------------------------------------------------Ⅰ
ABSTRACT ---------------------------------------------------------Ⅲ
致謝 --------------------------------------------------------------Ⅳ
目錄 --------------------------------------------------------------Ⅴ
圖目錄 ------------------------------------------------------------Ⅶ
表目錄 ------------------------------------------------------------ⅩⅠ
第一章：序論 -------------------------------------------------------1
1.1 研究背景與動機 -------------------------------------------------1
1.2 研究目的 ------------------------------------------------------2
1.3 論文架構 ------------------------------------------------------2
第二章：視訊壓縮理論 ------------------------------------------------3
2.1 數位視訊壓縮標準簡介 --------------------------------------------3
2.2 H.264/AVC編碼及解碼流程 ---------------------------------------13
2.3 H.264/AVC之移動估計和移動補償 ----------------------------------17
2.3.1 畫面間模式的選擇 --------------------------------------------19
2.3.2 畫面內模式的選擇 --------------------------------------------23
2.3.3 參考多個畫面 -----------------------------------------------30
2.4 應用於H.264/AVC之搜尋演算法 -----------------------------------31
2.4.1 完全搜尋演算法 ---------------------------------------------31
2.4.2 快速搜尋演算法 ---------------------------------------------32
第三章：提出H.264移動做計快速演算法 --------------------------------37
3.1 畫面間模式的選擇用Fuzzy推論 -----------------------------------37
3.2 畫面內模式的選擇用三步驟方法 ----------------------------------46
3.3 參考多個畫面 ------------------------------------------------48
第四章：實驗模擬 ------------------------------------------------50
4.1 畫面間模式的選擇用Fuzzy推論 ----------------------------------50
4.2 畫面內模式的選擇用三步驟方法 ----------------------------------56
4.3 參考多個畫面 ------------------------------------------------60
第五章：結論 ----------------------------------------------------63
參考文獻 -------------------------------------------------------64


圖目錄
圖1-1 MPEG-4和H.264複雜度的比較 -----------------------------------1
圖1-2 H.264用JM5.0c之運算時間分佈圖 -------------------------------2
圖2-1 ITU-T VCEG、JVT、ISO/IEC MPEG的發展過程 ---------------------3
圖2-2 H.264、MPEG-4、MPEG-2、H.263的Quality-Bitrate的特性曲線 -----4
圖2-3 各種影像標準所需的bitrate比較 --------------------------------4
圖2-4 與其它標準比較，H.264在bit-rate上減少的程度 -------------------5
圖2-5 FMO ------------------------------------------------------5
圖2-6 FMO的封包錯誤率比較 -----------------------------------------6
圖2-7 散餘弦轉換公式 ----------------------------------------------6
圖2-8 H.264的三個整數轉換矩陣 --------------------------------------6
圖2-9 H.264在不同網路上傳輸 ----------------------------------------7
圖2-10 H.264的應用 ------------------------------------------------7
圖2-11 H.264與先前標準的差異圖 -------------------------------------8
圖2-12 7種區塊模式的選擇 -------------------------------------------9
圖2-13 3種精確度1/4像素的位置 ---------------------------------------9
圖2-14 5個參考畫面 -------------------------------------------------9
圖2-15 H.264提供B-Picture -----------------------------------------9
圖2-16 RDO曲線 ----------------------------------------------------10
圖2-17 4x4區塊的整數轉換 -------------------------------------------10
圖2-18 H.264 Deblocking filter -----------------------------------11
圖2-19 H.264 Profile and Levels ----------------------------------11
圖2-20 SP switching pictures -------------------------------------12
圖2-21 H.264 Encoder ---------------------------------------------13
圖2-22 H.264 Decoder ---------------------------------------------13
圖2-23 H.264流程 --------------------------------------------------15
圖2-24 將畫面切成區塊 ----------------------------------------------15
圖2-25 H.264流程（紅色路徑） ---------------------------------------16
圖2-26 H.264流程（紅、藍、綠色路徑） --------------------------------16
圖2-27 移動估計和移動補償 ------------------------------------------17
圖2-28 移動估計 ---------------------------------------------------18
圖2-29 誤差影像 ---------------------------------------------------18
圖2-30 畫面間模式 -------------------------------------------------19
圖2-31 誤差影像中的模式選擇 ----------------------------------------19
圖2-32 Analysis And Reduction Of Reference Frames For Motion Estimation中所提出的流程圖-----------------------------------------21
圖2-33 Efficient Block-Size Selection Algorithm For Inter-Frame Coding in H.264 /MPEG-4 AVC中所提出的演算法流程圖 ------------------23
圖2-34 9種預測方向 ------------------------------------------------24
圖2-35 鄰近的區塊來預測目前區塊（E） --------------------------------24
圖2-36 Intra4x4的預測模式 -----------------------------------------25
圖2-37 實際的Intra4x4的預測模式 ------------------------------------25
圖2-38 Intra16x16的四種預測模式 ------------------------------------26
圖2-39 實際的Intra16x16的預測模式 ----------------------------------26
圖2-40 Intra4x4經histogram的mode(除mode 2) ------------------------27
圖2-41 Fast mode decision for H.264中所提出的演算法流程圖 -----------28
圖2-42 用Muc來判斷在不同的QP下是否要做Intra4x4或Intra16x16 -----------29
圖2-43 Inter mode selection用D來判斷要做什麼mode -------------------29
圖2-44 Fast three step intra prediction algorithm for 4X4 blocks in H.264所提出流程----------------------------------------------------30
圖2-45 Multiple reference frame的流程 -----------------------------30
圖2-46 Analysis and Reduction of Reference Frames for Motion Estimation in MPEG-4 AVC/JVT/H.264中所提出的流程圖 -----------------31
圖2-47 Full search -----------------------------------------------32
圖2-48 2-D-Log Search --------------------------------------------33
圖2-49 Three Step Search -----------------------------------------33
圖2-50 Four Step search ------------------------------------------34
圖2-51 Block-Based Gradient Descent Search -----------------------35
圖2-52 Diamond Search --------------------------------------------35
圖2-53 Hexagon-Based Search --------------------------------------36
圖3-1 Table Tennis第2個畫面用JM9.2得到的mode -----------------------38
圖3-2 Motion Vector tightness ------------------------------------39
圖3-3 Iv定義 ------------------------------------------------------39
圖3-4 Iv compactness ---------------------------------------------40
圖3-5 Fuzzy set --------------------------------------------------41
圖3-6 設定切割可能性 -----------------------------------------------41
圖3-7 Fuzzy inference based inter mode decision流程圖 -------------43
圖3-8 設定Fuzzy rule ----------------------------------------------44
圖3-9 鄰近的區塊A、B、C來預測目前區塊E -------------------------------46
圖3-10 9種預測方向 ------------------------------------------------47
圖3-11 Three step Intra mode decision ----------------------------48
圖3-12 Reuse觀念 --------------------------------------------------49
圖3-13 從鄰近四個區塊的移動向量用所佔的區塊大小給予權重 ----------------49
圖4-1 Foreman的RD curve和Time saving關係圖 ------------------------52
圖4-2 Stefan的RD curve和Time saving關係圖 --------------------------53
圖4-3 Table Tennis的RD curve和Time saving關係圖 --------------------54
圖4-4 Foreman的切割模式比較圖（a）JM9.2（b）ref[22]（c）Proposed -----55
圖4-5 Stefan的切割模式比較圖（a）JM9.2（b）ref[22]（c）Proposed ------55
圖4-6 Table Tennis的切割模式比較圖（a）JM9.2（b）ref[22]（c）Proposed -56
圖4-7 Foreman的RD curve和Time saving關係圖 -------------------------57
圖4-8 Stefan的RD curve和Time saving關係圖 --------------------------58
圖4-9 Table Tennis的RD curve和Time saving關係圖 --------------------59
圖4-10 Mother_daughter的RD curve和Time saving關係圖 ----------------59
圖4-11 Coastguard的RD curve和Time saving關係圖 ---------------------60
圖4-12 Foreman的RD curve和Time saving關係圖 ------------------------61
圖4-13 Stefan的RD curve和Time saving關係圖 -------------------------62
圖4-14 Table Tennis的RD curve和Time saving關係圖 -------------------63


表目錄
表4-1 Fuzzy rule probability --------------------------------------51
表4-2 在不同影像序列格式用所提出的演算法 ------------------------------51
表4-3 Foreman影像序列與JM9.2和ref[22]的比較 -------------------------52
表4-4 Stefan影像序列與JM9.2和ref[22]的比較 --------------------------53
表4-5 Table Tennis影像序列與JM9.2和ref[22]的比較 --------------------54
表4-6 Foreman影像序列與JM9.2的比較 ----------------------------------57
表4-7 Stefan影像序列與JM9.2的比較 -----------------------------------58
表4-8 Table Tennis影像序列與JM9.2的比較 -----------------------------58
表4-9 Mother_daughter影像序列與JM9.2的比較 --------------------------59
表4-10 Coastguard影像序列與JM9.2的比較 ------------------------------60
表4-11 Foreman影像序列與JM9.2的比較 ---------------------------------61
表4-12 Stefan影像序列與JM9.2的比較 ----------------------------------62
表4-13 Table Tennis影像序列與JM9.2的比較 ----------------------------62

[1] ISO/IEC 14496-10:2003, “Coding of Audiovisual Objecs-Part 10:Advanced Video Coding,” 2003, also ITU-T Recommendation H.264 “Advanced video coding for generic audiovisual services.”
[2] ITU-T Recommendation H.263, “Video Coding for Low bit rate Communication,” version 1, Nov. 1995; version 2, Jan. 1998; version 3, Nov. 2000.
[3] ISO/IEC 13818–2: “Generic coding of moving pictures and associated audio information—Part 2: Video,” 1994, also ITU-T Recommendation H.262.
[4] ISO/IEC 14496–2: “Information technology—coding of audiovisual objects—part 2: visual,” Geneva, 2000.
[5] A. Joch, F.Kossentini, H. Schwarz, T. Wiegand, and G. Sullivan, „Per-formance comparison of video coding standards using Lagrangian coder control,“ Proc. Of the IEEE ICIP 2002, part Ⅱ, pp.501-504, Sept.2002
[6] T. Wiegand, H. Schwarz, A.Joch, and F. Kossentini, „Rate-con-strained coder control and comparison of video coding standards,“ IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp.688-703, July 2003.
[7] Y.-K. Wang, M.M. Hannuksela, and M. Gabbouj, “Error-robust inter/intra mode selection using isolated regions,” in Proc. Int. Packet Video Workshop, Apr. 2003.
[8] N. Ahmed, T. Natarajan, and R. Rao, “discrete cosine transform,” IEEE Transactions on Computers, vol. C-23, pp. 90-93, Jan. 1974.
[9] T. Stockhammer, M.M. Hannuksela, and T. Wiegand, “H.264/AVC in wireless environments,” IEEE Transactions on Circuits and Systems, vol. 13, no.7, pp.657-673, July 2003.
[10] T. Wedi and H.G. Musmann, “Motion-and aliasing-compensated prediction for hybrid video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp.577-587, July 2003
[11] T. Wiegand, X. Zhang, and B. Girod, “Long-term memory motion-compensated prediction for video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, pp.70-84, Feb.1999.
[12] B. Girod, “Efficiency analysis of multihypothesis motion-compensated prediction for video coding,” IEEE Trans. Image Processing, vol. 9 Feb. 1999.
[13] A. Ortega and K. Ramchandran, “Rate-distortion methods for image and video compression,” IEEE Signal Processing Magazine, vol. 15 no. 6, pp. 23-50, Nov. 1998.
[14] T. Wiegand and B. Girod, “Lagrangian multiplier selection in hybrid video coder control,” in Proc. of ICIP 2001, Thessaloniki, Greece, Oct. 2001.
[15] H. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Low-Complexity transform and quantization in H.264/AVC, ” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp. 598-603, July 2003.
[16] S. Wenger, “H.264/AVC over IP,” IEEE Transactions on Circuits and Systems, vol. 13, no.7, pp.645-656, July 2003.
[17] M. Karczewicz and R. Kurceren, “The SP and SI frames design for h.264/AVC,” IEEE Transactions on Circuits and Systems, vol. 13, no. 7, pp. 637-644, July 2003.
[18] P. Yin, H.Y. Cheong Tourapis, A. Michael Tourapis, and J. Boyce, “Fast Mode Decision And Motion Estimation For JVT/H.264,” IEEE International Society FOR Computer Aided Surgery, pp.853-856, 2003.
[19] Y.W. Huang, B.Y. Hsieh, T.C. Wang, S.Y. Chien, S.Y. Ma, C.F. Shen, and L.G. Chen, “Analysis And Reduction Of Reference Frames For Motion Estimation In MPEG-4 AVC/JVT/H.264,” IEEE International Conference on Acoustics, Speech, and Signal Processing, pp.145-148, 2003.
[20]D. Wu, S. Wu, K. P. Lim, F. Pan, Z. G. Li, X. Lin, “Block Inter Mode Decision for Fast Encoding of H.264,” IEEE International Society FOR Computer Aided Surgery, pp.Ⅲ-181-Ⅲ-184, 2004.
[21] X. Jing, L. P. Chau, “An Efficient Inter Mode Decision Approach for H.264 Video Coding,” IEEE ICM June pp.1111-1114, 2004.
[22]A.C. Yu, “Efficient Block-Size Selection Algorithm for Inter-Frame Coding in H.264/MPEG-4 AVC,”IEEE International Society FOR Computer Aided Surgery, pp.Ⅲ-169-Ⅲ-172, 2004.
[23]F. Pan, X. Lin, S.o Rahardja, K.P. Lim, Z. G. Li, D. Wu, and S. Wu, “Fast Mode Decision Algorithm for Intraprediction in H.264/AVC Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, Vol.15 NO.7, pp.813-822, July 2005.
[24]J. Lee, B. Jeon, “Fast mode decision for H.264,” IEEE International Conference on Multimedia and Expo(ICME), pp.1131–1134, June 2004
[25]B. Meng, Oscar C. Au, “Fast Intra-Prediction Mode Selection for 4x4 Blocks in H.264,” IEEE International Conference on Acoustics, Speech, and Signal Processing, pp.Ⅲ-389-Ⅲ392, 2003.
[26]E. Arsura, L. Del Vecchio, R. Lancini, L. Nisti, “Fast Macroblock Intra And Inter Modes Selection For H.264/AVC,” IEEE ICME 2005. pp.378-381
[27] C. C. Cheng, T.S. Chang, “Fast Three Step Intra Prediction Algorithm for 4x4 blocks in H.264,” International Society FOR Computer Aided Surgery, pp.1509–1512, May 2005
[28]M.J. Chen, Y.Y. Chiang, H.J. Li, M.C. Chi, “Efficient multi-frame motion estimation algorithms for MPEG-4 AVC/JVT/H.264,”IEEE International Society FOR Computer Aided Surgery, Ⅲ-737-740, 2004
[29]Y. Su, M.T. Sun, “Fast multiple reference frame motion estimation for H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, vol.16, NO.3, pp. 447-452, March 2006.
[30]Y.W. Huang, B.Y. Hsieh, T.C. Wang, S.Y. Chien, “Analysis and reduction of reference frames for motion estimation in MPEG-4 AVC/JVT/H.264,”IEEE International Conference on Acoustics, Speech, and Signal Processing, Ⅲ145-Ⅲ148, 2003