Machine Learning Based Fast Algorithms for Coding Unit Size Decision in Video Compression

Abstract

미디어란 정보를 전달하는 매체로서 영상은 현대사회에서 가장 직관적이고 효율적인 매체 중 하나이다. 현대인들은 영상을 통하여 많은 정보를 얻고, 배우며, 즐기기도 하며, 심지어 경제적인 수단으로 활용하고 있다. 특히 요즘 YouTube, Vimeo, Twitch TV, Netflix, 아프리카TV, 등 온라인 스트리밍 서비스를 통하여 수많은 콘텐츠가 쏟아져 나오고 있다. 따라서 영상의 압축과 그에 관련된 표준의 중요성은 더욱 대두 되고 있다. Moving picture experts group (MPEG)과 video coding experts group (VCEG)은 UHD급 고화질 영상의 효율적인 압축을 위해 high efficiency video coding (HEVC) 압축 표준을 개발하였다. 전세계의 수많은 전문가들과 회사들이 앞다투어 훌륭한 기술들을 발표하였으며 그 결과, H.264/AVC보다 약 2배가량 높은 압축효율을 보였고 동시에 더 우수한 화질의 결과물이 나왔다. 하지만 quad-tree coding unit partitioning과 35개의 화면 내 예측 모드등 새로운 기술로 인해 HEVC의 화면 내 코딩 복잡도가 늘어나는 결과도 초래했다. 따라서 본 논문에서는 HEVC 화면 내 코딩을 위한 고속 알고리즘 세가지를 제안하였다. 이를 위하여 머신러닝과 패턴인식에서 사용되는 기법들을 활용하였으며 지도학습을 사용하여 통계자료를 갱신하였다. 영상의 여러 frame중 일부를 실시간 학습 단계 (online learning phase)로 정하여 분류기가 영상의 시간에 따라 변하는 특성에 적응적으로 작동하도록 구현하였다. Algorithm I은 CU의 크기를 미리 결정하기 위하여 영상의 복잡도와 통계자료를 이용한 CU의 depth 예측 기법을 사용하여 조기 분할 결정을 하였다. 이를 위해 CU와 한번 나누어진 CU들의 분산 차를 복잡도 측정 기준으로 정하였으며, 실시간 학습 단계에서 획득한 자료를 이용하여 depth를 예측하였다. Bayesian decision rule과 quadratic discriminant analysis (QDA)을 조기 종결 결정을 위하여 채택하였다. 확률을 구하는데 있어 Algorithm I에서 모수적 방법을 사용하였지만, Algorithm II에서는 비모수적 방법으로 확률을 직접 구하는 방식을 이용하여 HEVC 부호화 시간을 단축하였다. 머신러닝과 패턴인식에서 주로 쓰이는 Fisher’s linear discriminant analysis (FLDA)와 k-nearest neighborhood (k-NN) 분류기를 조기 분할 및 조기 종결 결정을 하는데 활용하여 성능을 향상시켰다. 또한 적응적 실시간 학습을 제안하여 영상의 복잡도가 변하는 지점에서 적응적으로 학습 단계를 삽입함으로써 좀 더 신뢰할 수 있고 효과적인 data를 획득하는데 성공하였다. Algorithm III에서는 비모수 방법인 파젠창을 이용하여 확률을 계산하였다. 파젠창은 k-NN과 비슷하지만 확률을 구하기 위한 창의 크기가 변하지 않는 특징이 있다. 이것을 활용하여 Gaussian kernel을 씌워 창의 중심에서의 거리에 따라 샘플에 weight를 부과해 정확도를 상승시켰다. 개선된 실시간 학습에서는 압축 과정 중 발생하는 RD cost와 화면 내 예측 모드를 활용하여 특징이 다른 이미지를 결정하였다. 실험결과로 볼 수 있듯이, 제안된 알고리즘들은 코딩효율 손실은 최소로 유지하면서 HM의 복잡도를 두 배 이상 단축시켰다. 최신 알고리즘과 비교해서도 시간, 코딩효율 측면에서 모두 우수한 결과를 보였다. 따라서 제안된 알고리즘은 실시간 영상 압축과 같은 고속 부호화 기술을 요하는 응용분야에 적합하게 사용될 수 있다.; The demand for high-resolution contents, such as ultra-high definition (UHD) resolution videos, has been increasing rapidly. UHD can provide consumers with a variety of experiences and has already been produced and broadcast by a number of manufacturers and companies. The resolution of UHD contents (4K) is 4 times higher than that of FHD; however, it requires more than 100 times bigger storage capacity because of increased frame rate, bit depth, and color format. High Efficiency Video Coding (HEVC) has been developed by Joint Collaborative Team on Video Coding (JCT-VC) to deal with has high resolution video content. The JCTVC consists of ISO/IEC JTC 1/SC 29/WG 11 Moving Picture Experts Group (MPEG) and ITU-T Q6/16 Video Coding Experts Group (VCEG). HEVC achieves a 21.9% BD-rate reduction in an all-intra (AI) configuration and 37.1% BD-rate reduction for a random access (RA) configuration with better visual quality than the former video coding standard H.264/AVC. In the HEVC standard, novel technologies are adopted to improve coding efficiency, such as, quad-tree-based coding unit (CU) partitioning, 35 modes for intra prediction, sample-adaptive offset, discrete-cosine-transform-based interpolation filter for motion compensation, and advanced motion vector prediction. In particular, the quad-tree-based CU partitioning process is one of the most efficient technologies used in an HEVC encoder. A coding tree unit (typically 64×64) can be split into smaller CUs based on rate-distortion optimization, allowing various types of video content to be adaptively compressed. However, the computational complexity of HEVC becomes a critical problem when implemented with an encoder. In this dissertation, I propose three fast algorithms (Algorithms I, II, and III) for the CU partitioning process of the HEVC encoder using machine learning methods. In Algorithm I, I utilize image complexity and adaptive depth prediction for early split-CU decision making. In addition, the Bayesian decision rule and quadratic discriminant analysis are used for early termination of the CU partitioning process. The feature of classification is a combined value of rate-distortion (RD) cost [40] and image complexity. In addition, I reduce the complexity of the CU partitioning process in HEVC by using Fisher’s linear discriminant analysis (FLDA) and the k-nearest neighbor (k-NN) classifier in Algorithm II. A complexity measure based on the Sobel operator and rate-distortion costs are defined as features. The FLDA is used to transform two-dimensional data into onedimensional more easy-to-class data. Algorithm II estimates the probability using k-NN with transformed data by FLDA and reduces the computation complexity of the CU partitioning process. The statistical data used for the proposed algorithm is updated by the adaptive online learning phase, and I defined the learning phase based on complexity difference. I also propose a fast CU size decision method using the Parzen window in Algorithm III. The Parzen window is a non-parametric method that estimates probability density using statistical samples and information. This method is similar to k-NN; however, the window size is a constant value, and the accuracy of classification is improved by using a Gaussian kernel. Improved online learning phase (IOLP) using coding information is introduced to adapt the characteristics of video sequences. The statistical data for classification is updated based on IOLP. I implement algorithms on HM reference software and compare their performance with that of the-state-of-art algorithms in terms of coding efficiency and time saving. The experimental results of each algorithm demonstrate that the proposed methods successfully reduce the encoding time of HEVC with little coding efficiency loss. Therefore, the proposed algorithm can be applied to real-time compression applications and applicable to various video codecs as well as HEVC.