2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) (Regular Paper) 20 1, 2015 1 (JBE Vol. 20, No. 1, January 2015) http://dx.doi.org/10.5909/jbe.2015.20.1.171 ISSN 2287-9137 (Online) ISSN 1226-7953 (Print) HEVC a), a), a) Early Decision of Inter-prediction Modes in HEVC Encoder Woo-Jin Han a), Joon-Hyung Ahn a) and Jong-Ho Lee a) HEVC H.264/AVC. HEVC,.,. 0.6%, 1.0%, 1.5% 12.0%, 14.2%, 17.2%,, 6.3%, 11.8%, 16.6%., HEVC. Abstract HEVC can increase the coding efficiency significantly compared with H.264/AVC however it requires much larger computational complexities in both encoder and decoder. In this paper, the decision process of inter-prediction modes in the HEVC reference software has been studied and a fast algorithm to reduce the computational complexity of encoder and decoder is introduced. The proposed scheme introduces a early decision criteria using the outputs of uni-directional predictions to skip the bi-directional prediction estimation. From the experimental results, it was proven that the proposed method can reduce the encoding complexity by 12.0%, 14.6% and 17.2% with 0.6%, 1.0% and 1.5% of coding efficiency penalty, respectively. In addition, the ratio of bi-directional prediction mode was reduced by 6.3%, 11.8% and 16.6% at the same level of coding efficiency penalty, respectively, which should lead to the decoder complexity reduction. Finally, the effects of the proposed scheme are maintained regardless of the use of the early skip decision algorithm which is implemented in the HEVC reference software. Keyword: HEVC, encoder, inter-prediction, fast algorithm a) IT(Dept. of Software, College of IT, Gachon University) Corresponding Author : (Woo-Jin Han) E-mail: hurumi@gmail.com Tel: +82-31-750-8668 ORCID: http://orcid.org/0000-0001-5114-4117 Manuscript received November 12, 2014 Revised December 2, 2014 Accepted December 2, 2014. HEVC [1] H.264/AVC [2] 40% [3][4][5]
(JBE Vol. 20, No. 1, January 2015). slice 16x16 (macroblock; MB) H.264/AVC, HEVC 64x64 coding tree unit(ctu) slice, CTU. coding unit(cu), CU prediction unit(pu) [6]. HEVC,. [7][8] 0. HEVC early skip decision(esd). [9], [10] Bayesian decision rule CU. HEVC, coding tool. [11] HEVC gradient, [12] intra direction intra-prediction.,. [13], edge intensity temporal stationarity, [14] motion activity. H.264/AVC, HEVC [7][8][9][10]. HEVC,.,., HEVC ESD. II HEVC, III /. IV, V, VI.. HEVC HEVC slice 8x8 64x64 CTU, CTU. CU,. CU PU, HEVC 2Nx2N, Nx2N, 2NxN, NxN, N/2x2N(L), N/2x2N(R), 2NxN/2(U), 2NxN/2(D) 8 PU [1]. PU,,, /.
2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) HEVC advanced motion vector prediction (AMVP) merge. AMVP,,,, /, merge,. AMVP,. Merge.. 1. AMVP AMVP.,,, /. AMVP L0, L1, L0 L1. L0 L1,., HEVC Add available spatial candidates from five pre-defined positions Partition redundancy removal and duplication removal Add temporal candidate Remove last spatial candidate if total number > N Add combined bi-predictive candidates for B-slice until total number = N Add zero motion merge candidates until total number = N 1. AMVP Fig. 1. Encoding process of AMVP mode
(JBE Vol. 20, No. 1, January 2015) 1, L0 L1 L1. < 1> AMVP. 2. Merge Merge,, / merge candidate., AMVP merge,, / merge candidate,. merge candidate slice 1~5. N, merge candidate N merge candidate, merge candidate., L0 merge candidate L1 merge candidate merge candidate. combined bi-predictive merge candidate, merge candidate N zero merge candidate, (0, 0) merge Determine L0 motion vector Uni-direction Determine L1 motion vector Refine L0 motion vector while L1 motion vector is fixed Bi-direction Refine L1 motion vector while L0 motion vector is fixed Choose best mode 2. merge candidate list Fig. 2. construction process of merge candidate list
2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) candidate merge candidate N., P-slice, B-slice. < 2> merge candidate. Merge candidate N, merge candidate, rate-distortion cost merge candidate index.. / HEVC JCT-VC common test condition [15]. random-access configuration, low-delay configuration, low-delay P configuration, random-access configuration /. 1. Table 1. Test video sequences Class Name Resolution Frame-rates B (1920x1080) C (832x480) Kimono ParkScene Cactus BasketballDrive BQTerrace BasketballDrill BQMall PartyScene RaceHorses 1920x1080 832x480 24 24 50 50 60 50 60 50 30 1. AMVP < 1> JCT-VC Class B, Class C, Class D 13 HEVC HM15.0 [16]., AMVP. HM15.0 BD-rates [17], HM15.0. < 2>, HM15.0 BD-rates, Encoding time 100. 2. AMVP (AMVP-NO-BI ) Table 2. Coding efficiency and encoding time of AMVP mode without bi-directional prediction Class B Class C Class D Average Encoding Time (%) AMVP-NO-BI 5.7 3.6 4.3 4.5 90.7 < 2> AMVP 4.5% 9.3%., AMVP,. < 3>. 3. AMVP-NO-BI Table 3. Ratio of bi-directional prediction of AMVP-NO-BI Class B Class C Class D Average D (416x240) BasketballPass BQSquare BlowingBubbles RaceHorses 416x240 50 60 50 30 HM15.0 60.8 45.8 51.6 53.3 AMVP-NO-BI 55.8 38.8 44.8 47.2 Difference -5.0-7.0-6.8-6.1
(JBE Vol. 20, No. 1, January 2015) < 3> AMVP 6.1% inter-prediction 47.2%. AMVP merge. merge, merge / merge candidate / HEVC.. Merge candidate,, combined bi-predictive candidate zero motion merge candidate., B-slice combined bi-predictive candidate, zero motion merge candidate / merge candidate. Combined bi-predictive candidate zero merge candidate merge candidate list, 4. AMVP-NO-BI merge candidate (MC ) Table 4. Ratio of bi-directional prediction and coding efficiency of AMVP-NO-BI with respect to various number of merge candidates Class B Class C Class D Average BD-rates (%) HM15.0 60.8 45.8 51.6 53.3 - AMVP-NO-BI (MC=5) 55.8 38.8 44.8 47.2 4.5 AMVP-NO-BI (MC=4) 54.0 36.7 42.4 45.1 5.0 AMVP-NO-BI (MC=3) 49.9 31.7 38.0 40.7 6.2 AMVP-NO-BI (MC=2) 38.1 23.2 30.1 31.0 8.9 AMVP-NO-BI (MC=1) 8.9 5.1 12.1 8.7 16.5 < 4> merge candidate. < 4> merge candidate,..,. 2. AMVP L1 AMVP AMVP-NO-BI L1 B-slice P-slice. < 5>. AMVP-NO-BI. 5. AMVP /L1 (AMVP-NO-BI-L1 ) / Table 5. Coding efficiency and encoding time of AMVP without both bi-directional prediction and L1 uni-directional prediction Class B Class C Class D Average Encoding Time (%) AMVP-NO-BI 5.7 3.6 4.3 4.5 90.7 AMVP-NO-BI-L1 11.6 15.2 13.1 13.3 80.0 Difference 5.9 11.6 8.8 8.8 10.7 < 5> AMVP L1 13.3% 20.0%. AMVP L0 L1,
2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) L1. < 5> AMVP-NO-BI AMVP-NO-BI- L1 AMVP L1, AMVP L1 8.8% 4.5% AMVP 4.3%.,, AMVP L1 10.7%, 9.3%, 1.4% AMVP., AMVP L1.,,. IV AMVP. L0, L1 RD-cost CBF,. L0 L1,. NxM PU L0 P0(x, y), L1 P1(x, y). L0 L1., A(x, y) (1). Weighted prediction,.. AMVP 1. AMVP 2 AMVP L0, L1,. L0 L1 AMVP. HEVC early skip decision(esd) [7][8] 2Nx2N coded block flag(cbf) 0., CBF, AMVP A(x, y), HEVC A(x, y). O(x, y), AMVP B(x, y), P0(x, y), P1(x, y), A(x, y), B(x, y) RD-cost RD0, RD1, RDA, RDB (2).
(JBE Vol. 20, No. 1, January 2015) (2) λ Lagrangian multiplier, B0, B1 L0 L1, B2,., RDA,., B(x, y) A(x, y) A(x, y) RD-cost, (3)., RDA RD-cost RD0 RD1 (4),,. and, (5). and, RD0 RD1 L0 L1. (5) RDA,. (5) α, α>1 RD0 RD1 RDA ( ). α,. α. α. 2. Generalized P&B(GPB) HEVC GPB(generalized P&B). L0 L1 L1, L0,. < 6>. 6. GPB Table 6. Coding efficiency and encoding time of fast GPB encoding Class B Class C Class D Average Encoding Time (%) NO-GPB-FAST 0.0 0.0 0.1 0.0 113.3 < 6>, GPB 13%., L0 L1 (5) RD0, RD1, RDA SAD, RDA RD0, RD1. α>1, (5) AMVP., (5) L0 L1 AMVP (6). (6) RefPOC0, RefPOC1 L0 L1 picture order count(poc). and or
2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) Determine L0 motion vector P 0 (x, y), RD 0 Determine L1 motion vector P 1 (x, y), RD 1 YES RefPOC 0 = RefPOC 1 Compute average of P 0 and P 1 A(x, y), RD A RD 0 > ard A and RD 1 > ard A NO Determine bi-directional motion vectors Choose best mode 3. AMVP Fig 3. Proposed fast encoding algorithm of AMVP bi-directional prediction < 3> (6)., (6) L0 L1,., 5 (6).. 1., HM15.0,. HM15.0 ESD. JCT-VC random-access configuration, < 1>. 2. < 7> (6) α 1.0 1.8. HM15.0, AMVP AMVP-NO-BI. < 7>, α=1.0 5.2% 0.3%
(JBE Vol. 20, No. 1, January 2015) 7. AMVP Table 7. Coding efficiency and encoding time of proposed fast encoding scheme for AMVP bi-directional prediction Class B Class C Class D Average Encoding time (%) AMVP-NO-BI 5.7 3.6 4.3 4.5 90.7 α=1.0 0.3 0.3 0.4 0.3 94.8 α=1.2 0.5 0.5 0.5 0.5 92.5 α=1.4 0.8 0.7 0.7 0.7 92.2 α=1.6 0.9 0.7 0.8 0.8 91.6 α=1.8 1.1 0.9 0.9 1.0 91.5. AMVP (AMVP-NO-BI) 9.3%, 55.9%. α=1.8, 8.5% 1.0%. 8.5% AMVP-NO-BI 91.4%. / 3 AMVP merge candidate. < 8> α=1.0, α=1.4 merge candidate 4, 3, 2, 1. 8. merge candidate Table 8. Coding efficiency and encoding time of proposed method with respect to various number of merge candidates α / MC Class B Class C Class D Average Encoding time (%) 1.0 / 4 0.4 0.4 0.5 0.4 90.5 1.0 / 3 0.7 0.7 0.6 0.6 88.0 1.0 / 2 1.1 0.9 0.9 1.0 85.8 1.4 / 4 0.9 0.7 0.7 0.8 87.6 1.4 / 3 1.2 1.1 1.0 1.1 85.1 1.4 / 2 1.7 1.5 1.4 1.5 82.8 < 8> < 7>, merge candidate.,, α=1.4 0.7% 7.8%, α=1.0 merge candidate 3 12.0%. α=1.8 1.0% 8.5%, α=1.4 merge candidate 3 14.9%. 3. < 9>.,.. 9. Table 9. Ratio of bi-directional prediction and coding efficiency of proposed method Class B Class C Class D Average (%) BD-rates (%) HM15.0 60.8 45.8 51.6 53.3 - AMVP-NO-BI 55.8 38.8 44.8 47.2 4.5 (α=1.0 / MC=3) (α=1.0 / MC=2) (α=1.4 / MC=3) (α=1.4 / MC=2) 55.2 40.5 45.2 47.0 0.6 47.6 34.9 42.1 41.5 1.0 52.9 35.2 42.5 43.5 1.1 44.0 28.6 37.5 36.7 1.5 < 8> < 9>, 0.6%, 1.0%, 1.5%, 6.3%. 11.8%, 16.6%.
2 : HEVC (Woo-Jin Han et al. : Early Decision of Inter-prediction Modes in HEVC Encoder) 4. < 10> HM15.0 ESD, ESD HM15.0 /.., HM15.0. 10. Early skip decision(esd) Table 10. Coding efficiency and encoding time of proposed method with early skip decision α / MC Class B Class C Class D Average Encoding time (%) 1.0 / 2 1.0 0.9 0.8 0.9 84.7 1.4 / 2 1.9 1.5 1.3 1.6 80.7 < 8> < 10>, ESD,. ESD α=1.4 merge candidate 2 1.5% 17.2%, ESD 1.6% 19.3%., ESD.. HEVC, generalized P&B(GPB), merge candidate., 0.6%, 1.0%, 1.5% 12.0%, 14.2%, 17.2%, 6.3%, 11.8%, 16.6% (References) [1] G. J. Sullivan, J.-R. Ohm, W.-J. Han and T. Wiegand, "Overview of the high efficiency video coding (HEVC) standard," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 22, No. 12, pp. 1649-1668, Dec. 2012. [2] T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, Overview of the H.264/AVC video coding standard, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 7, pp. 560-576, Aug. 2003. [3] E. Ohwovoriole, Y. Andreopoulos, Rate-distortion performance of contemporary video codecs: Comparison of Google/WebM VP8, AVC/H.264, and HEVC TMuC, LENS Symp., London, Sep. 2010. [4] F. De Simone, L. Goldmann, J.-S. Lee, T. Ebrahimi, Performance analysis of VP8 image and video compression based on subjective evaluations, SPIE Appl. Digital Image Proc. XXXIV, Aug. 2011. [5] T. Wiegand, J.-R. Ohm, G. J. Sullivan, W. J. Han, R. Joshi, T. K. Tan and K. Ugur, "Special Section on the Joint Call for Proposals on High Efficiency Video Coding (HEVC) Standardization," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 20, No. 12, pp. 1661-1666, Dec. 2010. [6] Woo-Jin Han, Junghye Min, Il-Koo Kim, Elena Alshina, Alexander Alshin, Tammy Lee, Jianle Chen, Vadim Seregin, Sunil Lee, Yoon-Mi Hong, Min-Su Cheon, Nikolay Shlyakhov, Ken McCann, Thomas Davies and Jeong-Hoon Park, "Improved video compression efficiency through flexible unit representation and corresponding extension of coding tools," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 20, No. 12, pp. 1709-1720, Dec. 2010. [7] R. H. Gweon, Y. L. Lee, J. Lim, Early termination of CU encoding to reduce HEVC complexity, JCTVC-F045, 6th JCT-VC meeting, Jul. 2011, Torino, Italy. [8] K. Choi, S. H. Park, E. S. Jang, Coding tree pruning based CU early termination, JCTVC-F092, 6th JCT-VC meeting, Jul. 2011, Torino, Italy. [9] J. Leng, L. Sun, T. Ikenaga and S. Sakaida, Content based hierarchical coding unit decision algorithm for HEVC, Proc. of Multimedia and Signal Processing (CMSP), pp. 56-59, May 2011. [10] X. Shen, L. Yu and J. Chen, Fast coding unit size selection for HEVC based on Bayesian decision rule, Proc. of Picture Coding Symposium (PCS), pp. 453-456, May 2012. [11] W. Jiang, H. Ma, Y. Chen, Gradient based fast mode decision algorithm for intra prediction in HEVC, Proc. of Consumer Electronics,
182 방송공학회논문지 제20권 제1호, 2015년 1월 (JBE Vol. 20, No. 1, January 2015) Communications and Networks (CECNet), pp. 1836-1840, Apr. 2012. [12] L. Zhao, L. Zhang, S. Ma and D. Zhao, Fast mode decision algorithm for intra prediction in HEVC, Proc. of Visual Communications and Image Processing (VCIP), pp. 1-4, Nov. 2011. [13] D. Wu, F. Pan, K. P. Lim and S. Wu, Fast intermode decision in H.264/AVC video coding, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 15, No. 7, pp. 953-958, Jul. 2005. [14] Z. Huanqiang, C. Canhui and M. Kai-Kuang, Fast mode decision for H.264/AVC based on macroblock motion activity, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 19, No. 4, pp. 491-499, Apr. 2009. [15] F. Bossen, Common HM tst conditions and software reference configurations," in Proc. of JCTVC-L1100, 12th JCT-VC meeting, Geneva, Switzerland, Jan. 2013. [16] HEVC reference software version 15.0 (HM15.0), https://hevc.hhi.fraunhofer.de/trac/hevc/browser/tags/hm-15.0, Jul. 2014. [17] G. Bjontegaard, "Calculation of average PSNR differences between RD curves," in Proc. VCEG-M33, 13th VCEG meeting, Austin, TX, USA, Apr. 2001. 저자소개 한우진 - 년 2월 : KAIST 전산학과 공학사 년 2월 : KAIST 전산학과 공학석사 년 2월 : KAIST 전산학과 공학박사 년 3월 ~ 2003년 3월 : SL2 연구소장 년 4월 ~ 2011년 8월 : 삼성전자 DMC 연구소 수석연구원 년 10월 ~ 현재 : HEVC Working Draft Editor 년 9월 ~ 현재 : 가천대학교 소프트웨어설계경영학과 조교수 : http://orcid.org/0000-0001-5114-4117 주관심분야 : 영상압축, 영상이해, 멀티미디어통신 1995 1997 2002 2002 2003 2010 2011 ORCID 안준형 년 월 가천대학교 소프트웨어설계경영학과 학사 년 월 현재 가천대학교 대학원 소프트웨어설계경영학과 석사과정 주관심분야 영상압축 패턴인식 - 2014 2 : - 2014 3 ~ : - ORCID : http://orcid.org/0000-0002-4155-4865 :, 이종호 년 월 현재 가천대학교 소프트웨어설계경영학과 학사과정 주관심분야 영상압축 영상이해 패턴인식 빅데이터 - 2011 3 ~ : - ORCID : http://orcid.org/0000-0002-2232-9849 :,,,