Content
Entropy-based method to get near-optimal CTU partition
General
The main task for an HEVC, AV1 and VVC encoders is to decide how to partition each CTU in optimal way.
A straightforward approach is to go through all available options and decide the optimal coding mode (i.e. the optimal partition) using of the rate-distortion optimization (RDO):
min {J}, J = D + λ · R
where
D stands for distortion
R stands for bit-size
J is called the coding cost
the value λ is commonly pre-defined as a function of QP (quantization parameter).
However, due to the plurality of partitions per single CTU a task to find the optimal coding mode is very time-consuming. Therefore different heuristic rules are applied to quickly find a near-optimal mode.
HEVC CTU Partition
HEVC adopted the quadtree CU partition, i.e. each non-leaf CU can be split into four CUs.
How to get by means of brute-force computation the best CU partition for 64×64 block (CTU) with the minimal CU size 8×8?
You need to traverse all nodes in the tree and to compute RD-cost for each node.
Generally speaking for tree with the depth ‘d’ and ‘b’ children for each non-leaf node the total number of nodes
1 + b + b^2+ … + b^d = ( b^(d+1) – 1 )/(b-1)
for the depth d=3 (64×64 → 32×32→ 16×16→ 8×8 ) the number of nodes to traverse: (4^4-1)/3 = 85
However, each node (CU) can be inter or intra. Thus the number of computations (or checks) is doubled to 170 per 64×64 block.
The 1920×1088 frame has 510 blocks (CTUs) of 64×64. The total number of checks to find optimal CTU partitions is 510×170 = 86,700 !
Notice that HEVC enables choosing smaller CTU size, e.g. equal to 32×32 (instead of 64×64). In the case of CTU size 32 x32 the depth ‘d’ of CTU tree is 2 and the number of nodes to traverse is 21. The total number checks (inter/intra) is 42 respectively.
The 1920×1088 frame has 2040 blocks (CTUs) of 32×32, hence the total number of checks is 2040×42 = 85,680
So, in case of brute-force (or straightforward) approach using CTU size 32×32 does not significantly reduce the computational load of finding optimal partitions against CTU size 64×64.
There is an interesting paper “Block Partitioning Structure in the HEVC Standard” by Il-Koo Kim et al. (2012). According to the paper when CTU size is set to 32×32 (from 64×64) the average coding efficiency loss is 2.2% to 2.9% in random access mode.
If CTU size is reduced further to 16×16 (equivalent to H.264/AVC) the average coding efficiency loss is increased to 12.0% to 14.4% in random access (against 64×64).
The CU partition decision: to split the block to four blocks or to terminate the process of searching for the optimal partition. The CU partition decision depends on decisions that has been made for the neighbor blocks and temporally co-located blocks from previous frames.
Entropy-based method to get near-optimal CTU partition
In the paper “Entropy-Based Fast Largest Coding Unit Partition Algorithm in High-Efficiency Video Coding“, Mengmeng Zhang et al., 2013, the entropy-based method is proposed to compute near-optimal CTU partition (remind to check all of 85 different CTU partitions is time-consuming).
The proposed method in general (here LCU = CTU), the following figure is taken from the paper:
In details:
Each 64×64 CTU is quantized by 8 to remove noise. Consequently, the quantized values are in the range 0..31.
For each CTU entropy values of all possible CUs are computed ( 85 different partitions: 1- 64×64, 4 – 32×32, 16 – 16×16, 64 – 8×8), starting from the high level (64×64) towards the low level (8×8):
1. Compute the average entropy of all CUs.
2. if 64×64 CU’s entropy is smaller than 1.2 then this CTU is not split and we found the CTU partition.
3. If 64×64 CU’s entropy exceed 3.5 then CTU is further split and we have to check a lower level of 32×32 CUs
4. Else if 64×64 CTU’s entropy is 0.15 bigger or 0.15 smaller than the average entropy (the step 1) then the CTU is not split and we found the CTU partition.
5. Otherwise – split 64×64 CTU and we have to check a lower level of 32×32 CUs.
In similar manner we check each level (32×32, 16×16)
The method is reported to provide a good CTU partition prediction with small PSNR penalties, reported BD-Rate loss is ~3, i.e. you need increase bitrate by 3% to get same quality of the brute-force HM reference encoder. Encoding times are improved by ~60%.
Notice that the accuracy of this method looks not good:
i think that the reason for the low accuracy is that the entropy of original pixels are computed, while residuals are encoded and why the entropy of residuals should be good-correlated with the entropy of the original pixels.
23+ years’ programming and theoretical experience in the computer science fields such as video compression, media streaming and artificial intelligence (co-author of several papers and patents).
the author is looking for new job, my resume
You have brought up a very excellent details, thanks for the post.
Very interesting information!Perfect just what I was searching for!
I went over this web site and I conceive you have a lot of wonderful information, bookmarked (:.
Woah! I’m really enjoying the template/theme of this website. It’s simple, yet effective. A lot of times it’s hard to get that “perfect balance” between usability and visual appearance. I must say you’ve done a very good job with this. Also, the blog loads very fast for me on Firefox. Superb Blog!
My spouse and i got glad that Albert could finish off his analysis out of the precious recommendations he discovered when using the weblog. It is now and again perplexing just to find yourself freely giving facts which usually men and women have been selling. So we realize we have you to be grateful to for this. The most important illustrations you’ve made, the simple web site navigation, the friendships you make it possible to create – it’s mostly fabulous, and it’s making our son and the family believe that this matter is interesting, and that is exceptionally vital. Thank you for the whole thing!
Whats Taking place i’m new to this, I stumbled upon this I’ve discovered It absolutely useful and it has helped me out loads. I hope to give a contribution & help other customers like its aided me. Great job.
Hey there, I think your site might be having browser compatibility issues. When I look at your website in Opera, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, wonderful blog!
obviously like your website however you have to test the spelling on quite a few of your posts. Several of them are rife with spelling problems and I to find it very troublesome to inform the reality nevertheless I will definitely come back again.
Hi! I know this is kinda off topic nevertheless I’d figured I’d ask. Would you be interested in exchanging links or maybe guest authoring a blog post or vice-versa? My website discusses a lot of the same topics as yours and I believe we could greatly benefit from each other. If you might be interested feel free to send me an e-mail. I look forward to hearing from you! Great blog by the way!
Simply want to say your article is as surprising. The clarity in your post is simply nice and i could assume you are an expert on this subject. Well with your permission allow me to grab your feed to keep updated with forthcoming post. Thanks a million and please carry on the gratifying work.
I’m impressed, I need to say. Actually not often do I encounter a weblog that’s each educative and entertaining, and let me tell you, you could have hit the nail on the head. Your concept is excellent; the problem is one thing that not sufficient people are talking intelligently about. I am very glad that I stumbled across this in my search for something regarding this.
Very interesting information!Perfect just what I was searching for!
Hi! Someone in my Myspace group shared this website with us so I came to take a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers! Exceptional blog and terrific design.
This site is my aspiration, very wonderful pattern and perfect content.
you’re truly a good webmaster. The site loading velocity is amazing. It sort of feels that you are doing any unique trick. In addition, The contents are masterwork. you have performed a magnificent activity in this topic!
It¦s actually a great and useful piece of info. I am happy that you simply shared this helpful info with us. Please keep us up to date like this. Thanks for sharing.
Hiya, I am really glad I have found this information. Today bloggers publish only about gossips and web and this is really annoying. A good website with exciting content, that is what I need. Thanks for keeping this web site, I will be visiting it. Do you do newsletters? Can not find it.