Search by item HOME > Access full text > Search by item

JBE, vol. 25, no. 5, pp.698-708, September, 2020


Fast Decision Method of Geometric Partitioning Mode and Block Partitioning Mode using Hough Transform in VVC

Minhun Lee, Juntaek Park, Gun Bang, Woong Lim, Donggyu Sim, and Seoung-Jun Oh

C.A E-mail:


VVC (Versatile Video Coding), which has been developing as a next generation video coding standard. Compared to HEVC (High Efficiency Video Coding), VVC is improved by about 34% in RA (Random Access) configuration and about 30% in LDB (Low-Delay B) configuration by adopting various techniques such as recursive block partitioning structure and GPM (Geometric Partitioning Mode). But the encoding complexity is increased by about 10x and 7x, respectively. In this paper, we propose a fast decision method of GPM mode and block partitioning using directionality of block to reduce encoding complexity of VVC. The proposed method is to apply the Hough transform to the current block to identify the directionality of the block, thereby determining the GPM mode and the specific block partitioning method to be skipped in the rate-distortion cost search process. As a result, compared to VTM8.0, the proposed method reduces about 31.01% and 29.84% encoding complexity for RA and LDB configuration with 2.48% and 2.69% BD-rate loss, respectively.

Keyword: VVC, Hough transform, Fast algorithm, Block partitioning, Geometric Partitioning Mode

[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] B. Bross, J. Chen, S. Liu, and Y. K. Wang, JVET-O2001, “Versatile Video Coding (Draft 8),” Jan. 2020.
[3] VTM,
[4] F. Bossen, X. Li, and K. Suehring, JVET-R0003, “AHG report: Test model software development (AHG3),” Apr. 2020.
[5] H. Gao, S. Esenlik, E. Alshina, A. M. Kotra, B. Wang, R. L. Liao, J. Chen, Y. Ye, J. Luo, K. Reuze, C. C. Chen, H. Huang, W. J. Chien, V. Seregin, Z. Deng, L. Zhang, H. Liu, K. Zhang, Y. Wang, J. Li, C. S. Lim, Y. L. Hsiao, C. C. Chen, C. W. Hsu, Y. W. Huang, S. M. Lei, L. F. Chen, X. Li, C. Li, S. Liu, L. P. Van, G. V. Auwera, A. K. Ramasubramonian, H. Huang, W. J. Chien, M. Karczewicz, M. Blaser, J. Sauer, H. Chen, and H. Yang, JVET-Q0806, “Integrated Text for GEO,” Jan. 2020.
[6] L. Shen, Z. Zhang, and P. An, “Fast CU size decision and mode decision algorithm for HEVC intra coding,” IEEE Transactions on consumer Electronics, Vol.59, No.1, pp.207-213, Feb. 2013.
[7] S. K. Na, W. J. Lee, and K. W. Yoo, “Edge-based fast mode decision algorithm for intra prediction in HEVC,” IEEE International Conference on Consumer Electronics, pp.11-14, Jan. 2014.
[8] S. H. Park, and J. W. Kang, “Context-Based Ternary Tree Decision Method in Versatile Video Coding for Fast Intra Coding,” IEEE Access, Vol.7, pp.172597-172605, Nov. 2019.
[9] T. Li, M. Xu, and R. Tang, “DeepQTMT: A Deep Learning Approach for Fast QTMT-based CU Partition of Intra-mode VVC,” arXiv preprint arXiv:2006. 13125. 2020.
[10] Y. U. Yoon, D. H. Park, and J. G. Kim “Gradient-Based Methods of Fast Intra Mode Decision and Block Partitioning in VVC,” Journal of Broadcast Engineering, Vol.25, No.3, pp.338-345, May. 2020.
[11] P. V. C. Hough, "Method and means for recognizing complex patterns," US Patent 3,069,654, Patent and Trademark Office, Washington D.C., 1962. [12] J. F. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions Pattern Analysis and Machine Intelligence, Vol.8, No.6, pp.679-698, Nov. 1986.
[13] M. Fang, G. Yue, and Q. Yu, “The Study on An Application of Otsu Method in Canny Operator,” In Proceedings. The 2009 International Symposium on Information Processing, pp.109-112, Aug. 2009.
[14] N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Transactions on systems, man, and cybernetics, Vol.9, No.1, pp.62-66, Jan. 1979.
[15] N. Guil, J. Villalba, and E. L. Zapata, “A fast Hough transform for segment detection,” IEEE Transaction on Image Processing, Vol.4, No.11, pp.1541-1548, Nov. 1995.
[16] C. S. Won, D. K. Park, and S. J. Park, “Efficient Use of MPEG-7 Edge Histogram Descriptor,” ETRI Journal, Vol.24, No.1, pp.23-30, Feb. 2002. [17] F. Bossen, J. Boyce, K. Suehring, X. Li, and V. Seregin, JVET-N1010, “JVET common test conditions and software reference configurations for SDR video,” Mar. 2019.
[18] G. Bjøntegaard, VCEG-M33, “Calculation of average PSNR differences between RD-curves,” Apr. 2014.


Editorial Office
1108, New building, 22, Teheran-ro 7-gil, Gangnam-gu, Seoul, Korea
Homepage: TEL: +82-2-568-3556 FAX: +82-2-568-3557
Copyrightⓒ 2012 The Korean Institute of Broadcast and Media Engineers
All Rights Reserved