Analysis of High Efficiency Video Coding in YUV Files using Intra Prediction Algorithm

Analysis of High Efficiency Video Coding in YUV Files using Intra Prediction Algorithm

Lydia Vinolin C

Department of Electronics and Instrumentation Engineering

Karunya University, Coimbatore-641 114, India

Dr. A Shobha Rekh

Director,

School of Electrical Sciences Karunya university, Coimbatore-641 114, India

Abstract- High Efficiency Video Coding (HEVC/H.265) is a recently developed video compression standard which has 50% better video compression efficiency than H.264. In this paper, a 4×4 iterative intra prediction algorithm for H.265/HEVC encoder is proposed to reduce the bit rate and to increase the compression rate. HEVC utilizes Z-scan order to process prediction units (PUs). The prediction units in the processing order are changed adaptively. The proposed algorithm performs DC mode, planar mode and 33 angular modes for Intra 4×4 Prediction. Simulation results of the HEVC intra 4×4 prediction algorithms shows that the accuracy and the efficiency of the proposed intra prediction algorithm is increased when compared to H.264 in terms of compression rate in YUV files.

Keywords- Video Compression, Intra-prediction, Prediction modes, Increased compression rate, YUV.

1. INTRODUCTION

   JCT-VC organization developed HEVC as a collaboration between the ISO/IES MPEG and ITU-T VCEG. HEVC is referred as MPEG-H Part2 by ISO/IES group and as

   H.265 by ITU-T. The first version of HEVC was implemented in January 2013 and accepted in June 2013. The second version was issued and presented in 2014 and published in early 2015. Additional 3D-HEVC extensions were completed in early 2015. HEVC is protected by patents owned by various parties.

   High Efficiency Video Coding is a video compression standard which increases the compression rate compared to its predecessors AVC (H.264 or MPEG-4). It is one of several potential successors of AVC. HEVC is an extension of the concepts in H.264/MPEG-4 AVC. HEVC results in double the data compression ratio when compared to AVC, without change in video quality level. It also results in improved video quality level at the same bit rate. HEVC works up to 8192×4320 resolutions. Both HEVC and AVC works towards finding areas that are redundant by comparing different parts of a frame of video, within a single frame as well as subsequent frames. Instead of the original pixels, short description will then replace these redundant areas.

   The primary changes for HEVC include the expansion of the pattern comparison and difference-coding areas from 16×16 pixel to 64×64. HEVC results in the improvements of variable-block-size segmentation, intra prediction within the same picture, motion vector prediction, motion region merging and motion compensation filtering. Additional filtering step called sample-adaptive offset filtering is done. Effective use of these improvements requires much

   more computational complexities for compressing the video, but has less impact on the amount of computation needed for decompression.

   Fig.1 Block diagram of HEVC compression

   There are two basic types of prediction: inter prediction and intra prediction. Inter prediction is used for motion estimation and compensation with region on previously coded frames close to the current block. Intra prediction works within a current frame and is based upon the compressed and decoded data available for the block being predicted. The aim of the prediction process is to reduce data redundancy. Once the prediction is done, residuals are obtained by subtracting from the original data that should be compressed. Residuals are subject to Forward DCT and Quantization. Intra prediction is one of the main features that determine the encoder compression efficiency.

   The paper is organized as follows. The literature survey about HEVC and intra prediction algorithm is reviewed in section 2. In section 3, block partitioning, intra coding algorithm and 4*4 intra prediction algorithm is explained. Simulation results of video compression, and a comparison of compression rate for various resolutions is presented in section

   4. Finally, conclusions and future work are discussed in section 5.

2. RELATED WORK

   Several algorithms have been proposed for efficient video compression.

   K. Ugur and A. Fuldseth et al. [2] proposed a quad tree-based coding structure with support for macroblocks of size 64 × 64, 32 × 32, and 16 × 16 pixels. Interpolation and de-blocking filters are designed to improve coding efficiency and to have low complexity.

   F. Bossen, E. Francois et al [3] proposed a new video coding scheme based on a simplified block structure is discussed. Its conceptual design is similar to a typical block- based hybrid coder in prediction application and subsequent prediction error coding. The basic coding unit is an 8×8 block, instead of the usual 16 × 16 macroblock. No larger block sizes are considered for prediction and transform.

   Koo Kim et al. [4] proposed a novel video compression scheme based on a highly flexible hierarchy of unit representation is discussed which defines coding unit (CU), prediction unit (PU), and transform unit (TU). This separation of the block structure into three concepts allows each to be optimized according to its role. It demonstrated bit rate reductions of around 40%.

   Elyousfi et al.[1] suggest determining AVC intra prediction mode based on characteristic of homogeneity information that involves gradient and quadratic prediction. This allows reduction in the complexity of intra prediction search to 76.07% maintaining the same PSNR quality with about 1.94% bitrate increase.

3. METHODOLOGY

   1. Block Partitioning

      Quad tree-based block partitioning scheme and the increased intra prediction modes are the two new features of

      H.265 intra prediction compared to H.264. In HEVC, coding tree units (CTUs) are introduced. CTUs are non-overlapping blocks obtained when a frame is divided. Sub-blocks that are obtained, when the CTUs are further partitioned, are called as coding units (CUs) as shown in Fig.1. According to a quad tree-based structure, all the CTUs are processed in raster scan order within one frame.

      Fig.2 CTU is partitioned as CUs.

      Within one CTU, all the CUs are processed in Z-scan order. The CTU is then subdivided into 16 CUs with different sizes. A CU is further divided into one or four prediction units (PU) and each PU can have different prediction modes. Appropriate block sizes are chosen by the flexible partitioning scheme to enhance the encoder and to exploit the spatial correlation in a better way.

   2. Intra Coding Algorithm

      HEVC intra coding algorithm supports up to 33 directional modes along with DC mode and planar mode as shown in Fig.2. There are 4 × N + 1 reference pixels obtained when predicting an N × N block from neighbouring reconstructed blocks. If the neighbouring blocks are unavailable, padded pixels are copied from the nearest available reference pixels.

      Fig.3 35 modes of intra-prediction algorithm

      Raster scan order, as shown in Fig.2.a), is used to process the CTUs in HEVC. Only left, left-above, right above and above neighbouring reconstructed CTUs can be employed as references to predict the current CTU with such a processing order. The prediction direction can only cover a half plane from 45 (mode 2) to 225 (mode 34). In other words, the encoder and the decoder are not able to perform prediction from angles in the other half plane. The current block is divided into two parts by an edge.

      Fig.4.a) Raster scan order 4.b) Scan order different than Z-order from 4.a)

      When aster scan order is used, current block can only employ left, left-above, above and right-above neighbouring reconstructed blocks as references for prediction. Hence the gray part below the edge cannot be well predicted. However, if the coding order is approximately along the edge direction, as shown in the figure 2.b), the gray part can be efficiently predicted from its right neighbouring reconstructed block. Similar problem exists in the Z-scan CU coding order when coding one CTU. Therefore, the traditional block coding orders (raster and Z-scan) are not capable of fully exploiting the spatial correlation between adjacent blocks. This motivates us to adaptively select both CTU and CU coding orders such that the spatial redundancy can be further reduced.

   3. Intra 4×4 Prediction Algorithm

   The prediction algorithm utilizes the already coded pixels and reconstructed neighbouring pixels to predict the pixels of a block. Extrapolating samples from the projected reference sample location are involved in the prediction process of intra angular modes according to a given directionality. The reference samples that are used for intra prediction are sometimes filtered by 3 taps smoothing filter [1

   2 1]/4 smoothing filter. However HEVC applies this smoothing operation according to the directionality and the block size more adaptively.

   After the reference main array is determined, the index and the coefficient of pixels are calculated by the equations 1 and 2, respectively.

   index = ((y+1)* intraPredAngle)>>5 (1)

   coeff = ((y+1)* intraPredAngle)&31 (2)

   If iFact is equal to zero, neighboring pixels are copied directly to predicted pixels. Otherwise, predicted pixels are calculated as follows:

   predSample[x,y] = (32-coeff) * remain[x+index+1]

   + coeff * remain[x+index+2]+16)>>5 (3)

   Each intra predicted sample is computed by equation

   3. Single Instruction Multiple Data (SIMD) implementations are facilitated by the constant nature of the weighting factor. All 33 prediction angles are covered by a single function, thereby reducing the amount of code needed to implement this algorithm. Then, the simplified form of equation 3 is given by equation 4:

   predSample = factor1*pixel1+factor2*pixel2 + 16

   >>5 (4)

4. SIMULATION AND RESULTS

   Simulation has been done on Matlab and the following results are obtained. YUV video of 352*256 resolution is given as input. Video has been splitted into its corresponding frames and a single frame has been taken into processing. After the blocks has been partitioned within the frame, intra order processing is done and then prediction is done for each 4*4 blocks in the frame.

   Fig.5a Input Frame

   The input frame is shown in fig.5a and the angular mode intra prediction output is shown in fig.5b. Input frame is of 352*256 resolution and of size 92Kb. The angular predicted compressed output frame is of same resolution of size 58Kb.

   Fig.5b Compressed output frame

   Output image clarity can be increased by using input videos of higher resolutions like 1920*1080.

   The following table compares 35 prediction mode outputs including DC, planar and 33 directional modes. Directional mode uses angles in degrees. The output compression ratio is calculated as follows:

   Compression ratio = (Input size Compressed size)/Input

   size

   Mode	Compressed Size (Kb)	Compression Ratio(%)
   DC mode	58	35.56
   Planar mode	58	35.56
   Angular mode 1 (32)	58	35.56
   Angular mode 2 (26)	39	56.67
   Angular mode 3 (21)	37	58.88
   Angular mode 4 (17)	37	58.88
   Angular mode 5 (13)	37	58.88
   Angular mode 6 (9)	37	58.88
   Angular mode 7 (5)	36	60
   Angular mode 8 (2)	36	60
   Angular mode 9 (0)	36	60
   Angular mode 10 (-2)	36	60
   Angular mode 11 (-5)	38	57.78
   Angular mode 12 (-9)	36	60
   Angular mode 13 (-13)	50	44.44
   Angular mode 14 (-17)	62	31.11
   Angular mode 15 (-21)	70	22.22
   Angular mode 16 (-26)	70	22.22
   Angular mode 17 (-32)	81	10
   Angular mode 18 (-26)	84	6.67
   Angular mode 19 (-21)	83	7.78
   Angular mode 20 (-17)	70	22.22
   Angular mode 21 (-13)	77	14.44
   Angular mode 22 (-9)	68	24.44
   Angular mode 23 (-5)	75	16.67
   Angular mode 24 (-2)	61	32.22
   Angular mode 25 (0)	66	26.67
   Angular mode 26 (2)	57	36.67
   Angular mode 27 (5)	57	36.67
   Angular mode 28 (9)	57	36.67
   Angular mode 29 (13)	58	35.56
   Angular mode 30 (17)	57	36.67
   Angular mode 31 (21)	57	36.67
   Angular mode 32 (26)	58	35.56
   Angular mode 33 (32)	58	35.56

   Mode	Compressed Size (Kb)	Compression Ratio(%)
   DC mode	58	35.56
   Planar mode	58	35.56
   Angular mode 1 (32)	58	35.56
   Angular mode 2 (26)	39	56.67
   Angular mode 3 (21)	37	58.88
   Angular mode 4 (17)	37	58.88
   Angular mode 5 (13)	37	58.88
   Angular mode 6 (9)	37	58.88
   Angular mode 7 (5)	36	60
   Angular mode 8 (2)	36	60
   Angular mode 9 (0)	36	60
   Angular mode 10 (-2)	36	60
   Angular mode 11 (-5)	38	57.78
   Angular mode 12 (-9)	36	60
   Angular mode 13 (-13)	50	44.44
   Angular mode 14 (-17)	62	31.11
   Angular mode 15 (-21)	70	22.22
   Angular mode 16 (-26)	70	22.22
   Angular mode 17 (-32)	81	10
   Anglar mode 18 (-26)	84	6.67
   Angular mode 19 (-21)	83	7.78
   Angular mode 20 (-17)	70	22.22
   Angular mode 21 (-13)	77	14.44
   Angular mode 22 (-9)	68	24.44
   Angular mode 23 (-5)	75	16.67
   Angular mode 24 (-2)	61	32.22
   Angular mode 25 (0)	66	26.67
   Angular mode 26 (2)	57	36.67
   Angular mode 27 (5)	57	36.67
   Angular mode 28 (9)	57	36.67
   Angular mode 29 (13)	58	35.56
   Angular mode 30 (17)	57	36.67
   Angular mode 31 (21)	57	36.67
   Angular mode 32 (26)	58	35.56
   Angular mode 33 (32)	58	35.56

   Input size of the video frame is 90Kb. Size of the compressed frames for different modes is listed as follows. The output resolution of the following table is 352*256.

   Mode	Compressed Size (Kb)	Compression Ratio(%)
   DC mode	58	35.56
   Planar mode	58	35.56
   Angular mode 1 (32)	105	–
   Angular mode 2 (26)	55	38.89
   Angular mode 3 (21)	51	43.33
   Angular mode 4 (17)	49	45.56
   Angular mode 5 (13)	49	45.56
   Angular mode 6 (9)	46	48.89
   Angular mode 7 (5)	46	48.89
   Angular mode 8 (2)	46	48.89
   Angular mode 9 (0)	54	40
   Angular mode 10 (-2)	50	44.44
   Angular mode 11 (-5)	112	–
   Angular mode 12 (-9)	119	–
   Angular mode 13 (-13)	162	–
   Angular mode 14 (-17)	155	–
   Angular mode 15 (-21)	180	–
   Angular mode 16 (-26)	188	–
   Angular mode 17 (-32)	187	–
   Angular mode 18 (-26)	146	–
   Angular mode 19 (-21)	146	–
   Angular mode 20 (-17)	125	–
   Angular mode 21 (-13)	174	–
   Angular mode 22 (-9)	100	–
   Angular mode 23 (-5)	114	–
   Angular mode 24 (-2)	77	14.44
   Angular mode 25 (0)	76	15.55
   Angular mode 26 (2)	76	15.55
   Angular mode 27 (5)	85	5.55
   Angular mode 28 (9)	86	4.44
   Angular mode 29 (13)	90	–
   Angular mode 30 (17)	86	4.44
   Angular mode 31 (21)	90	–
   Angular mode 32 (26)	91	–
   Angular mode 33 (32)	92	–

   Table.1 352*256 output resolution

   The average compression rate is found out to be 15.3%. As the compression rate is too small in the above resolution of output image, Compression has been checked out for its various resolutions. The following table is listed for the output resolution 704*128. While decompression, the original resolution will be restored.

   Input size of the video frame is 90Kb. Size of the compressed frames for different modes is listed as follows.

   Table.2 704*128 output resolution

   The compression rate now achieves twice that of the previous case. It is found out to be 37.93%. It is resulted that average the compression rate increases by 22.6%. The final well compressed image is shown in fig.5b.

5. CONCLUSION AND FUTURE WORK

Thus the HEVC intra prediction algorithm is simulated and the results are analysed. YUV videos of higher resolutions (1920*1080) can be used to obtain more clarity in the compressed image. HEVC can also be implemented in FPGA using a real-time video camera. The Vmod digicam provides Real-Time digital images/videos for Virtex-5 FPGA board using a stereo-digital camera and a VHDCI connector. Simulink block of Matlab code is dumped into FPGA chip and the processing is done by Genesys Virtex-5 development board. The compressed video output is then can be transmitted through HDMI cable to LCD screen. This will result in the efficient real-time high quality video transmission over long distance.

REFERENCES

1. A. Elyousfi, A. Tamataoui, E. Bouyakhf, Fast Intra Prediction Algorithm for H.264/AVC Based on Quadratic and Gradient Model, International Journal of Electrical and Electronics Engineering, vol. 1, no. 1, pp. 27-35, 2010.

2. Kemal Ugur, Arild Fuldseth, Lars Petter Endresen, Antti Hallapuro, Cixun Zhang, Andrey Norkin High Performance, Low Complexity Video Coding and the Emerging HEVC Standard IEEE Transactions On Circuits And Systems For Video Technology, Vol. 20, No. 12,

   November 2010

3. Frank Bossen, Edouard Francois, Sandeep Kanumuri, Hisao Sasai, Yoshinori Suzuki, Thomas Wedi, Peng Yin Video Coding Using a Simplified Block Structure and Advanced Coding Techniques IEEE Transactions On Circuits And Systems For Video Technology, Vol.20, No.12, Dec 2010.

4. Woo-Jin Han, Koo Kim, Alexander Alshin, Improved Video Compression Efficiency Through Flexible Unit Representation & Corresponding Extension of Coding Tools IEEE Transactions On Circuits And Systems For Video Technology, Vol. 20, No. 12,

   December 2010

5. Chao-Tsung Huang, Mehul Tikekar, and Anantha P. Chandrakasan Memory-Hierarchical and Mode-Adaptive HEVC Intra Prediction architecture for Quad Full HD Video Decoding IEEE Transactions On Very Large Scale Integration Systems, Vol. 22, No. 7, July 2014

6. Sangkwon Na, Wonjae Lee, and Kiwon Yoo Edge-Based Fast Mode Decision Algorithm for Intra Prediction in HEVC IEEE International Conference on Consumer Electronics (ICCE) pp. 11-14, Jan 2014

7. Jens-Rainer Ohm and Gary J. Sullivan Special Section on the Joint Call for Proposals on High Efficiency Video Coding (HEVC) Standardization IEEE Transactions On Circuits And Systems For Video Technology, Vol. 20, No. 12, December 2010

8. Amin Zheng, Yuan Yuan, Jiantao Zhou, Yuanfang Guo, Haitao Yang and Oscar C. Au Adaptive Block Coding Order for Intra Prediction in HEVC IEEE Transactions On Circuits And Systems For Video Technology Vol 9, No. 2, pp 5-7.

9. I.-K. Kim, K. McCann, K. Sugimoto, B. Bross, W.-J. Han, and G. J. Sullivan,"High Efficiency Video Coding Test Model 10 Encoder Description," JCTVC-L1002, JCT-VC Meeting, Geneva, April 2013.

10. B. Bross, W.-J. Han, J.-R. Ohm, G. J. Sullivan, Y.-K. Wang, and T. Wiegand, "High Efficiency Video Coding text specification draft 10 (for FDIS &Consent)," JCTVC-L1003, JCT-VC Meeting, Geneva, April 2013.

11. F. Pan, X. Lin, S. Rahardja, K. P. Lim, Z. G. Li, D. Wu, and S. Wu, "Fast mode decision algorithm for intra prediction in H. 264/AVC video coding," IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 7, pp. 813-822, July 2005.

12. A.-C. Tsai, A. Paul, J.-C. Wang, and J.-F. Wang, "Intensity gradient technique for efficient intra-prediction in H. 264/AVC," IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 5, pp 694-698, May 2008.

13. M. Parlak, Y. Adibelli, and I. Hamzaoglu, "A novel computational complexity and power reduction technique for H. 264 intra prediction," IEEE Transactions on Consumer Electronics, vol. 54, no. 4, pp 2006- 2014, Nov. 2008.

14. M. Zhang, C. Zhao, and J. Xu, "An adaptive fast intra mode decision in HEVC," IEEE International Conference on Image Processing, pp 221- 224, Oct. 2012.

15. YUV video input – https://media.xiph.org/video/derf/