Fast Block Partitioning in HEVC Intra Coding for UHD Video

/ Fast block partitioning method in HEVC Intra coding for UHD video / Authors: Nicolas Dhollande, Xavier Ducloux, Olivier Le Meur, Christine Guillemot Session B1, Image & Video Processing I, 7th september 2015, Berlin 3/18/2025

Problem addressed High Efficiency Video Coding (HEVC) Latest video standard (2013) Joint Coding Team on Video Coding (JCT-VC) HEVC bitrate savings over MPEG.4/AVC with the same perceived quality: 64% in UHD, 62% in HD [Tan and al, JCTVC-Q0204] HEVC will be key for UHD deployment Goal: limit as far as possible the encoding complexity with a limited quality loss HEVC: 2-4x more encoding power than MPEG.4/AVC UHD: 4-5x more encoding power than HD Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 2 / 2 / 2 / 2 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Problem addressed HEVC vs previous standard MPEG.4/AVC: Coding Tree Unit (composed of 64x64 to 8x8 sizes CU s) more accurate Intra coding (35 luma predictions) within a PU extended transforms (32x32 to 4x4) with a QT structure Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 3 / 3 / 3 / 3 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Problem addressed The quad-tree structure leads to intensive computation when the encoder builds the CTU Depth first partitioning process: 85 CU / 341 Intra PU to be evaluated Just a few CU coded in the syntax What if the encoder knows the optimal PU quad-tree in advance Video sequences Intra only (AI) Speed-up ratio 6.33 3.82 Highest speed- up potential with UHD ! EBU set UHD Class B 1080p Encoding of the optimal PU quad-tree vs reference Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 4 / 4 / 4 / 4 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Problem addressed Typical algorithms for fast Intra partitioning: Intuition that flat regions are divided in large blocks, and sharp/complex regions are divided in small blocks: - Judgement process based on the variance complexity on the downscaled content [Tian & Goto, 2012] - Judgement process based on the entropy [Zhang, 2013] Modes inference from a lower resolution pre-coding pass. [Dhollande, 2014] Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 5 / 5 / 5 / 5 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Our approach: a fast Intra partitioning scheme for the Intra coding Off-line training Low complexity encoder Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 6 / 6 / 6 / 6 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Motivations Let S be a Bernoulli random variable with parameter P: P: : d: qp: quantization parameter {22,27,32,37} proba. that a PU is further split by the ref. encoder variance of the luminance pixels into the current PU PU depth into the CTU {0,1,2,3} Block partitioning probability in 32x32-size PU given within a qp=32 reference UHD encoding Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 7 / 7 / 7 / 7 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Off-line training well associates the local signal characteristics with the HEVC Intra block sizes Two thresholds on the variance for the splitting decision: ThL such that: ThH such that: is the probability level used to select ThL and ThH from the conditional probabilities. (PL) (PL) ? (1 (1- -PL) PL) High proba of non splitting High proba of splitting ThH ThL Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 8 / 8 / 8 / 8 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Off-line training PL=90% Accuracy++ Speed- up++ ThL ThH ThL ThH d=1 qp=22 d=1 qp=37 ThL ThH ThL ThH d=3 qp=22 d=0 qp=37 Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 9 / 9 / 9 / 9 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Off-line training PL=60% Accuracy++ Speed- up++ ThL ThH ThL ThH d=1 qp=22 d=1 qp=37 ThL ThH ThLThH d=3 qp=22 d=0 qp=37 Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 10 / 10 / 10 / 10 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Off-line training 1. A reference encoding is performed for each qp. 2. Conditional probabilities are calculated for each d and qp. 3. Depending on the PL parameter, a couple (ThL, ThH) is chosen for each d and qp. Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 11 / 11 / 11 / 11 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Proposed scheme for the low complexity encoder PU classification: Our fast partitioning scheme: Variant 1: unconstrained CMP class (reference partitioning) Next PU level Variant 2: constrained CMP class (1 split only) Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 12 / 12 / 12 / 12 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Summary Problem addressed Our approach: a fast Intra partitioning scheme for the Intra coding Motivations Off-line training Proposed scheme for the low complexity encoder Results Strengths of our algorithm / conclusion Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 13 / 13 / 13 / 13 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Results Settings HM test model v11.0 All Intra (AI) Main profile 4 quantization parameters: 22,27,32,37 10 EBU UHD-1 sequences for the off-line training 750 frames each Performance measure Encoding time speed-up ratio = TREF / TALGO Vs Average BD-rate Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 14 / 14 / 14 / 14 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Results Performance of the low complexity encoder in UHD: Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 15 / 15 / 15 / 15 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Results Performance with others sequences and resolutions Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 16 / 16 / 16 / 16 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Summary Problem addressed Our approach: a fast Intra partitioning scheme for the Intra coding Motivations Off-line training Proposed scheme for the low complexity encoder Results Strengths of our algorithm / conclusion Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 17 / 17 / 17 / 17 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Strengths of our algorithm / conclusion Simple fast Intra partitioning scheme which skips the less probable PU from the decision process. High accuracy of our early terminations Speed-up of 2x with no loss Strong complexity reduction in UHD About 6x against a limited loss of 5% No subjective quality degradation Possible improvements: On-line learning of thresholds (each N frames) Improved Intra modes pre-selection using the texture orientations Fast RQT construction Diffusion : public 18/03/2025 18/03/2025 18/03/2025 18/03/2025 / 18 / 18 / 18 / 18 Diffusion : confidentiel Diffusion : confidentiel Diffusion : confidentiel

Danke / Thanks / nicolas.dhollande@b-com.com / www.b-com.com/en