Fast coding unit partition search

Quad tree based encoders do brute force search for finding out the best partition for Coding Unit (CU). This brute force search performs encoding for all the possible block sizes and selects the partition size that gives best compression. This search along with inherent complexity of the latest encoders makes it extremely difficult to attain real time performance of 30 fps and low power. The solution to this problem is to perform a low complexity analysis of the Coding Unit and suggest the partition of the CU based on the available CU characteristics without performing entire encoding to estimate the cost. The present paper describes a method to do this using Sum of Absolute Difference, hereby SAD, and gradient information of the Coding Unit. We show that the presented method results in 3x faster encoding when compared to the brute force algorithm with small increase in bitrate (approximately 5% increase in worst case) and no change in subjective quality. The complexity bitrate trade off and the result BD-PSNR values of this method are also presented.