臺灣博碩士論文加值系統

隨著人們要求在視覺上的享受，網路世代的來臨，4K Ultra HD至最高解析度可達到8192×4320（8K解析度）高畫質市場的需求，網路和多媒體技術不斷的進步，2013國際標準組織訂製了新的視頻壓縮標準，HEVC/H.265(High Efficient Video Coding)，HEVC視訊壓縮率可以提高到H.264 兩倍以上，且畫質更優於H.264，HEVC需要非常龐大的資料運算，而壓縮的技術在這邊占了非常重要的地位。
HEVC視訊編碼技術引進更大的編碼單元CU(Coding Unit)，預測單位(Prediction Unit)、轉換單位(Transform Unit)，與H.264比較，H.264只支援16x16的編碼單位，而HEVC可支援的編碼單位為8x8至64x64，且可支援非對稱切割，讓編碼單位可隨著畫面的複雜度不同做適當的調整，進而增加壓縮效率，與H.264比較下，可減少約一半的高解析影像容量，以及減少串流傳輸所需要的頻寬，減少儲存與傳輸成本，但相對而來的是複雜度的提高，因此在提高更好的壓縮效能，減少複雜度也是目前必須克服的技術之一。
在本篇論文中，提出一種新的Motion Estimation 方法，利用前一張已編碼過的CU的MV當作搜索目標，通過SAD運算分析，逐步縮小範圍，最後取得最佳的MV，在HM平台上驗證結果，減少搜索次數以及更準確的預測是本研究的重點，實驗結果此方法可以加速Motion Estimation，進而降低運算複雜度 減少40%的編碼時間，且畫質與原本HM提出的TZ Search不相上下。

With the demand on visual enjoyment in this era of Internet, the requirement of high quality resolution can reach 4K Ultra HD to 8192*4320 (8K resolution). As the improvement on Internet and the technologies of multimedia, international standard organization set up a new standard for compressing video HEVC/H.265 (High Efficient Video Coding) in 2013. The HEVC video compressing percentage can rise up to 2 times of H.264, and the resolution is much better than H.264. HEVC requires enormous info for calculation, so the technique of compressing plays an extremely important role.
The video coding technique of HEVC supports larger CU (Coding Unit), Prediction Unit, and Transform Unit. Comparing to H.264, H.264 supports the coding unit with 16x16, while HEVC supports coding unit with 8x8 to 64x64. With the asymmetric cutting, coding unit can be adjusted according to the complexity of the display contents, and the compressing efficiency will increase. It can also lower approximately half of the high resolution video size, the bandwidth for streaming, even the costs for storage and transmission. But on the other hand, the complexity will be higher. Proving better compressing efficiency and lower the complexity are the techniques that need to be overcomed.
In this thesis, there’s a new method of Motion Estimation. By using the previously-edited MV of CU as the searching target, and analyzing SAD to minimize the range gradually, the best MV will be available. The main point of this research is to predict precisely and minimize the searching frequency on the test results of HM platform. The test result shows such method can accelerate Motion Estimation, lower the complexity, and shorten the coding time. What’s more, the resolution is nearly equal to the TZ search supported by HM.

目錄
摘要 i
Abstract ii
目錄 iv
圖 目 錄 vii
表 目 錄 xi
第一章 簡介 1
1.1 研究背景 1
1.2 研究動機與目的 3
1.3 論文架構 4
第二章 HEVC移動估測技術介紹 5
2.1 HEVC架構 5
2.2 畫面內預測(Intra Prediction) 8
2.3 畫面間預測(Inter Prediction) 9
2.4 運動估計概述(Motion Estimation) 10
2.4.1 全域搜尋Full Search Block Matching Algorithm(FSBMA) 13
2.5 快速運動估計演算法探討 14
2.5.1 Modified Cross Hexagon Diamond Search[17] 14
2.5.2 New Combined Three Step Search[18] 16
2.5.3 Directional Search[45] 17
2.5.4 Predict Hexagon Search[46] 19
2.5.5進階型運動向量預測(Advanced MV Prediction) 22
2.5.6 合併模式(Merge Mode) 25
2.5.7 Test Zone Search (TZ) 26
2.6 分像素精度運動估計 30
2.7 多幅參考畫面(multiple reference) 31
2.8 內嵌式迴圈濾波器(In-Loop Filter) 32
第三章 六角收斂搜索加速HEVC移動估測演算法 37
3.1 HEVC測試平台介紹 37
3.2 六角收斂搜索加速HEVC移動估測演算法 40
3.3 實驗平台與參數 46
3.4 HEVC Test Sequence 46
3.5 實驗數據討論 48
第四章 快速移動估測硬體架構設計與實現 56
4.1 Memory Control Unit (MU)硬體架構 59
4.2 Hexagonal Computation Unit硬體架構 69
4.3 PU SAD Computation Unit硬體架構 72
4.3.1 PU SAD Combine硬體架構 73
4.3.2 SAD Array 74
4.3.3 8T pipe 75
4.3.4 SAD Compare 76
4.4 PU Size Decision Unit 77
4.5 CU Depth Decision Unit 78
第五章 快速移動估測硬體實作 81
5.1 IC Design Flow 81
5.2 Chip Spec 82
5.3 實驗結果 84
5.4 比較與貢獻 85
第六章 結論 87
參考文獻 89
 
圖 目 錄
圖2.1 HEVC架構圖 5
圖2.2 CU結構 6
圖2.3 PU尺寸 7
圖2.4 HEVC Intra Prediction模式角度對應關係[1] 9
圖2.5 Block Matching Algorithm 示意圖[2] 11
圖2.6 Motion Estimation實例說明 12
圖2.7 Motion Estimation實例說明 12
圖2.8 Motion Estimation實例說明 13
圖2.9 Full Search Block Matching[3] 14
圖2.10 Modified Cross Hexagon Diamond Search 15
圖2.11 New Combined Three Step Search[18] 17
圖2.12(a) Three Descent Search Pattern 18
圖2.12(b) Cross Pattern Search 19
圖2.13[a][b][c][46] 21
圖2.13 (d) Predict Hexagon Search[46] 21
圖2.14 AMVP參考移動向量示意圖 23
圖2.15空間域AMVP示意圖[4] 24
圖2.16時間域AMVP示意圖[4] 24
圖2.17合併模式MV向量選取示意圖 25
圖2.18 AMVP向量選取示意圖 27
圖2.19 Diamond Search由內而外搜索示意圖 27
圖2.20新增兩點搜尋 28
圖2.21 Raster Search 示意圖 29
圖2.22 HEVC像素插值濾波器示意圖 30
圖2.23 I- Frame P- Frame B- Frame示意圖 31
圖2.24 I-Frame P-Frame B-Frame 32
圖2.25(a) With Deblocking Filter 圖2.25(b) No Deblocking Filter 33
圖2.26 Deblocking Filter示意圖 34
圖2.27 4種一維EO分類示意圖 35
圖3.1 Intra-only 示意圖 38
圖3.2 Low-delay示意圖 39
圖3.3 Random-access示意圖 40
圖3.4六角收斂搜索加速HEVC移動估測演算法流程 41
圖3.5建立MV列表 42
圖3.6建立MV列表 43
圖3.7(a)第一次六角形樣式搜索 43
圖3.7(b)第二次六角形樣式搜索 44
圖3.7(c)第三次六角形樣式搜索 45
圖3.8六角收斂搜索加速HEVC移動估測演算法 45
圖3.9 Kimono RD Curve 49
圖3.10 ParkScen RD Curve 50
圖3.11 PartyScene RD Curve 50
圖3.12 BasketballDrill RD Curve 51
圖3.13 BQMall RD Curve 52
圖3.14 BasketballPass RD Curve 52
圖3.15 Racehorses RD Curve 53
圖3.16 FourPeople RD Curve 54
圖3.17 KristenAndSara RD Curve 54
圖3.18 Johnny RD Curve 55
圖4.1 The architecture design for Hexagonal convergence Search. 57
圖4.2 13個PU SAD Computation示意圖 58
圖4.3 The Block Diagram for Hexagonal convergence Search 59
圖4.4記憶體儲存frame的pixel data示意圖 60
圖4.5 ring buffer 示意圖 61
圖4.6 以六角形樣式取出7個Block示意圖 61
圖4.7 sram group 示意圖 62
圖4.8 以pipe方式將pixel存入sram示意圖 63
圖4.9 8x8 timing slot 64
圖4.10 將PU case分成13種不同的PU size 65
圖4.11 8x8 CU timing 66
圖4.12 16x16 Cu拆解示意圖 67
圖4.13 16x16 CU timing 68
圖4.14 將8x8 Pixel拆分為4個4x4 Pixel 69
圖4.15(a) Hexagonal Computation Unit內部電路結構 70
圖4.15(b) Hexagonal Computation Unit內部電路結構 70
圖4.15(c) Hexagonal Computation Unit內部電路結構 71
圖4.15(d) Hexagonal Computation Unit內部電路結構 71
圖4.16 PU SAD Computation Unit內部電路結構 72
圖4.17 PU SAD Computation Unit內部電路結構 74
圖4.18 16x16 CU SAD 74
圖4.19 8T pipe電路 76
圖4.20 SAD compare電路 76
圖4.21 Partition Merge Unit內部電路。 78
圖4.22 Depth Decision Unit硬體架構 80
圖5.1 IC Design Flow 82
圖5.2 Motion Estimator示意圖 83
圖5.3 Chip implementation 84
 
表 目 錄
表2.1 EO分類規則示意圖 35
表3.1 Main 10與Main 配置表 37
表3.2測試序列畫面 47
表3.3 Kimono效能 49
表3.4 ParkScen效能 49
表3.5 PartyScene效能 50
表3.6 BasketballDrill效能 51
表3.7 BQMall效能 51
表3.8 BasketballPass效能 52
表3.9 Racehorses效能 53
表3.10 FourPeople效能 53
表3.11 KristenAndSara效能 54
表3.12 Johnny效能 55
表3.13與文獻[48][52]進行數據比較 55
表5.1 I/O ports descriptionof the Motion Estimator 83
表5.2 Memory Used 85
表5.3 Chip Spec 85
表5.4 Comparisons with other approaches 86
 

[1]陳鶴元. "HEVC 之高效率編碼單位深度和預測單位模式快速決策演算法." 中央大學通訊工程學系學位論文 (2012): 1-79.
[2]https://www.slideshare.net/mmv-lab-univalle/slides7-ccc-v8.
[3]黃聖瑜. "移動估算演算法研究與及其電路架構設計與實現." 中興大學電機工程學系所學位論文 (2008): 1-106.
[4]HEVC 快速畫面間預測模式決策演算法之探討; A Fast Inter-mode Decision Algorithm for HEVC. 2013. PhD Thesis. 國立中央大學.
[5]Koga, T. "Motion compensated inter-frame coding for video conferencing." Proc. NTC81, New Orleans. 1981.
[6]Zhu, Shan, and Kai-Kuang Ma. "A new diamond search algorithm for fast block matching motion estimation." Information, Communications and Signal Processing, 1997. ICICS., Proceedings of 1997 International Conference on. Vol. 1. IEEE, 1997.
[7]Po, Lai-Man, and Wing-Chung Ma. "A novel four-step search algorithm for fast block motion estimation." IEEE transactions on circuits and systems for video technology 6.3 (1996): 313-317.
[8]Zhu, Ce, Xiao Lin, and Lap-Pui Chau. "Hexagon-based search pattern for fast block motion estimation." IEEE transactions on circuits and systems for video technology 12.5 (2002): 349-355.
[9]Yang, K-M., M-T. Sun, and Lancelot Wu. "A family of VLSI designs for the motion compensation block-matching algorithm." IEEE Transactions on circuits and systems 36.10 (1989): 1317-1325.
[10]Kao, Hao-Che, et al. "Accelerating HEVC Motion Estimation Using GPU." Multimedia Big Data (BigMM), 2016 IEEE Second International Conference on. IEEE, 2016.
[11]Jong, Her-Ming, and Tzi-Dar Chiueh. "Parallel architectures for 3-step hierarchical search block-matching algorithm." IEEE Transactions on Circuits and Systems for Video Technology 4.4 (1994): 407-416.
[12]方冠傑. "適用於 H. 264/AVC 視訊之高精確度移動估計引擎快速演算法分析以及架構設計與實現." 中興大學電機工程學系所學位論文 (2009): 1-81.
[13]張珊榕, and 張添烜. 適用於 HEVC 之 270MHz 4Kx2K@ 60fps 整數像素移動估測設計. Diss. 2012.
[14]De Michell, G., and Rajesh K. Gupta. "Hardware/software co-design." Proceedings of the IEEE 85.3 (1997): 349-365.
[15]Cheung, Chun-Ho, and Lai-Man Po. "Novel cross-diamond-hexagonal search algorithms for fast block motion estimation." IEEE Transactions on Multimedia 7.1 (2005): 16-22.
[16]ZUO, SHIKAI, MINGJIANG WANG, and LIYI XIAO. "Motion Estimation Algorithm for HEVC Suitable for Hardware Implementation."
[17]Vani, R., P. Davis, and M. Sangeetha. "Modified Cross Hexagon Diamond Search Algorithm for Fast Block Matching Motion Estimation."
[18]Davis, P., and Sangeetha Marikkannan. "Implementation of motion estimation algorithm for h. 265/HEVC." International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering 3.3 (2014).
[19]Zhu, Ce, Xiao Lin, and Lap-Pui Chau. "Hexagon-based search pattern for fast block motion estimation." IEEE transactions on circuits and systems for video technology 12.5 (2002): 349-355.
[20]Hamosfakidis, Anastasios, and Yakup Paker. "A novel hexagonal search algorithm for fast block matching motion estimation." EURASIP Journal on Applied Signal Processing 2002.1 (2002): 595-600.
[21]Dai, Wei, et al. "A novel fast two step sub-pixel motion estimation algorithm in HEVC." Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. IEEE, 2012.
[22]Arnaudov, Pavel, and Tokunbo Ogunfunmi. "Architecture and Implementation of a Simplified Locality Sensitive Hashed Signatures Based Fast Motion Estimation Algorithm." Signal Processing Systems (SiPS), 2016 IEEE International Workshop on. IEEE, 2016.
[23]Cebrián-Márquez, Gabriel, José Luis Martínez, and Pedro Cuenca. "A pre-analysis algorithm for fast motion estimation in HEVC." Image Processing (ICIP), 2016 IEEE International Conference on. IEEE, 2016.
[24]Medhat, Ahmed, et al. "Adaptive low-complexity motion estimation algorithm for high efficiency video coding encoder." IET Image Processing 10.6 (2016): 438-447.
[25]Arora, Shaifali M., Navin Rajpal, and Ravinder Purwar. "Dynamic pattern search algorithm with zero motion prejudgment for fast motion estimation." Advanced Computing & Communication Technologies (ACCT), 2015 Fifth International Conference on. IEEE, 2015.
[26]Medhat, Ahmed, et al. "Fast center search algorithm with hardware implementation for motion estimation in HEVC encoder." Electronics, Circuits and Systems (ICECS), 2014 21st IEEE International Conference on. IEEE, 2014.
[27]Jou, Shiaw-Yu, Shan-Jung Chang, and Tian-Sheuan Chang. "Fast motion estimation algorithm and design for real time QFHD high efficiency video coding." IEEE Transactions on Circuits and Systems for Video Technology 25.9 (2015): 1533-1544.
[28]Bali, Ankit, et al. "Modified Rho-Square Method for Very Fast Block Matching in Motion Estimation for Video Compression." Machine Intelligence and Research Advancement (ICMIRA), 2013 International Conference on. IEEE, 2013.
[29]Vidyalekshmi, V. G., Deepa Yagain, and Ganesh Rao. "Motion estimation block for HEVC encoder On FPGA." Recent Advances and Innovations in Engineering (ICRAIE), 2014. IEEE, 2014.
[30]Ma, Xiaoyu, Xiuhua Jiang, and Xiangkun Du. "An improved method for fast motion estimation in Joint Multi-view Video Coding." Image and Signal Processing (CISP), 2013 6th International Congress on. Vol. 1. IEEE, 2013.
[31]Shan, Nana, et al. "A Fast Coding Unit Depth Decision Algorithm for HEVC Inter Prediction." Frontier of Computer Science and Technology (FCST), 2015 Ninth International Conference on. IEEE, 2015.
[32]Wu, Jinfu, et al. "A fast CU encoding scheme based on the joint constraint of best and second-best PU modes for HEVC inter coding." Imaging Systems and Techniques (IST), 2015 IEEE International Conference on. IEEE, 2015.
[33]Xiong, Jian, et al. "A fast HEVC inter CU selection method based on pyramid motion divergence." IEEE transactions on multimedia 16.2 (2014): 559-564.
[34]Tai, Shen-Chuan, et al. "A fast inter residual quad-tree construction method in HEVC." Consumer Electronics-Taiwan (ICCE-TW), 2014 IEEE International Conference on. IEEE, 2014.
[35]Xu, Qiuping, and Dong Hu. "A new inter prediction mode decision method based on temporal correlation for HEVC encoder." Advanced Research and Technology in Industry Applications (WARTIA), 2014 IEEE Workshop on. IEEE, 2014.
[36]Ahn, Sangsoo, Bumshik Lee, and Munchurl Kim. "A novel fast CU encoding scheme based on spatiotemporal encoding parameters for HEVC inter coding." IEEE Transactions on Circuits and Systems for Video Technology 25.3 (2015): 422-435.
[37]Xiong, Jian, et al. "Fast and efficient inter CU decision for high efficiency video coding." Image Processing (ICIP), 2014 IEEE International Conference on. IEEE, 2014.
[38]Yoo, Hyang-Mi, and Jae-Won Suh. "Fast coding unit decision algorithm based on inter and intra prediction unit termination for HEVC." Consumer Electronics (ICCE), 2013 IEEE International Conference on. IEEE, 2013.
[39]Xiong, Jian, et al. "Fast HEVC inter CU decision based on latent SAD estimation." IEEE Transactions on Multimedia 17.12 (2015): 2147-2159.
[40]Hu, Nan, and En-Hui Yang. "Fast intra mode decision for HEVC based on Transparent Composite Model." Image Processing (ICIP), 2014 IEEE International Conference on. IEEE, 2014.
[41]Yang, Seungha, et al. "Fast inter sub-partition prediction unit mode decision for HEVC." Consumer Electronics (ICCE), 2014 IEEE International Conference on. IEEE, 2014.
[42]Kim, Miok, et al. "Fast skip mode decision with rate-distortion optimization for high efficiency Video coding." Multimedia and Expo Workshops (ICMEW), 2014 IEEE International Conference on. IEEE, 2014.
[43]Zupancic, Ivan, Saverio G. Blasi, and Ebroul Izquierdo. "Inter-prediction optimisations for fast HEVC encoding of ultra high definition content." Systems, Signals and Image Processing (IWSSIP), 2015 International Conference on. IEEE, 2015.
[44]Cheng, Zhengxue, et al. "Merge mode based fast inter prediction for HEVC." Visual Communications and Image Processing (VCIP), 2015. IEEE, 2015.
[45]Yang, Shih-Hsuan, Jia-Ze Jiang, and Hsien-Jie Yang. "Fast motion estimation for HEVC with directional search." Electronics Letters 50.9 (2014): 673-675.
[46]視訊編碼之研究與軟硬體協同設計. 2014. PhD Thesis. National Central University.
[47]楊先絜. "結合六角形樣式與方向搜尋之 HEVC 快速整數像點動作估計." 臺北科技大學資訊工程系研究所學位論文 (2014): 1-73.
[48]Gao, Longfei, et al. "A novel integer-pixel motion estimation algorithm based on quadratic prediction." Image Processing (ICIP), 2015 IEEE International Conference on. IEEE, 2015.
[49]Sinangil, Mahmut E., et al. "Cost and coding efficient motion estimation design considerations for high efficiency video coding (HEVC) standard." IEEE Journal of selected topics in signal processing 7.6 (2013): 1017-1028.
[50]Jou, Shiaw-Yu, Shan-Jung Chang, and Tian-Sheuan Chang. "Fast motion estimation algorithm and design for real time QFHD high efficiency video coding." IEEE Transactions on Circuits and Systems for Video Technology 25.9 (2015): 1533-1544.
[51]方志仲. "應用於 HEVC 即時具交錯細微排程超高解析度移動估測處理器." 交通大學電子工程系所學位論文 (2015): 1-66.




[52]Nalluri, Purnachand. A fast motion estimation algorithm and its VLSI architecture for high efficiency video coding. Diss. Universidade de Aveiro (Portugal), 2016.
[53]Sinangil, Mahmut E., et al. "Hardware-aware motion estimation search algorithm development for high-efficiency video coding (HEVC) standard." Image Processing (ICIP), 2012 19th IEEE International Conference on. IEEE, 2012.
[54]Dinh, Vu Nam, et al. "Hardware-efficient and high-speed integer motion estimation architecture for HEVC." Consumer Electronics-Asia (ICCE-Asia), IEEE International Conference on. IEEE, 2016.