of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11
12th Meeting: Geneva, CH, 14-23 January, 2013 / Document: JCTVC-L0332
Title: / Dynamic Range ANALYSIS OF HEVC/H.265 INVERSE TRANSFORM OPERATIONS
Status: / Input Document to JCT-VC
Purpose: / Information
Author(s) or
Contact(s): / Louis Kerofsky, , Sharp Labs of America.
Shevach Riabtsev, , Senior Engineer in CSR.
Source:
______
Abstract
Basing on matrix theory methods the authors estimate dynamic ranges (DR) for all HEVC/H.265 inverse transform operations. Indeed, when the input coefficient data is limited to 16-signed bits and an intermediate between vertical and horizontal 1D transforms are clipped to 16-signed bits, a 28-signed bits precision processor is sufficient for all inverse transform operations.
1 Introduction
Estimation of dynamic range bounds can be exploited to reduce datapath bitwidth, circuit area and power consumption for dedicated processors (e.g. SIMD) or application specific integrated circuits.
In the emerging HEVC/H.265 standard inverse transform operations can be represented in the form of matrix products with intermediate clipping. Due to matrix representation of transform operations we apply elements of matrix analysis for dynamic range bounds estimation.
The present method for dynamic range estimation has already been implicitly utilized in dynamic range bounds estimation of AVC/H.264, see [1] , [2] for 4x4 case and [3] for 8x8 case. In this paper we apply this method for HEVC/H.265 inverse transforms. In addition we provide a rigorous mathematical justification for that method.
This paper is organized as follows. Section 2 provides a brief overview and mathematical justification of the present method. In Sections 3 we apply the present method to HEVC transforms.
2 General Method for Estimation of Dynamic Range
In this section we present a method for deriving dynamic range bounds for an arbitrary transform represented as the matrix product , where T, X and S are square NxN real matrices .
2.1 Theorem A [Bound of Dynamic Range]
The bound of dynamic range is based on the following inequality:
Proof:
2.1.1 Corollary on dynamic range bound
Let the transform is represented as the following matrix product: (where T, X and S are square NxN real matrices) and elements of X lie in the range [-A, A]. Then the dynamic range bound on elements of Y is given by the following formula:
(*)
or equivalently in matrix-norm notation,
Here denotes the maximum absolute row sum norm, denotes the transpose of.
The next theorem proves that the above bound (*) or equivalently is actually the least upper bound for the linear map with X belonging to N2-dimensional cube .
2.2 Theorem B [Extreme Points]
Let Y to be a linear map (where T, X and S are NxN real matrices) defined on the domain (i.e. all entries of X lie in the range [-A, A]).
Then the above linear function attains the maximum in infinity norm at the matrix specified as follows: , where
Proof:
Consider the matrix of the form: , where .
It is clear that then
According to the inequality (*) for each (r,c) entry of Y we have:
So,
2.2.1 Conclusion of Theorem B
The results of this section show that for each transform in the form the transformed elements of an arbitrary input matrix X with entries in the range [-A, A] are less or equal to the following limit:
or in more formal notation.
If 2’s complement input represented with n-bits is in the range [-2(n-1), 2(n-1)-1]. Then one can pick A=2(n-1) for the dynamic range estimation. Consequently the dynamic range in bits of the transform is determined as follows:
· If the value of ( or ) is a power of two, i.e. there exist an integer n such = 2n then the dynamic range is (n+2) bits (incl. sign).
· Otherwise bits (incl. sign).
3 Dynamic Range of HEVC/H.265 4x4 Inverse Transforms
The HEVC/H.265 adopted 4x4, 8x8, 16x16 and 32x32 transforms, see the draft [4]. In this section we apply the above described formula (*) to estimate dynamic ranges for all inverse transforms (including intermediate results).
According to HEVC draft [4] for sample precision BitDepthY and BitDepthC equal to 8 bits dequantized coefficients are within the range [-215,215-1]. Thus, we set A=215 to be used in the analysis.
The following steps are applied to the implementation of NxN inverse transform:
a) Vertical transform of the input matrix X:
b) Intermediate scaling and clipping
where
c) Horizontal transform on the matrix
d) Final scaling:
Notice that we interpret the indexes of the entry oppositely to HEVC/H.265, The index ‘i’ stands for row index and ‘j’for column index respectively.
To estimate the dynamic range for the step (a) we use the formula (*). We rewrite the vertical phase of the transform as the following triple product: , where I is the identity matrix. Then
(1)
The calculation of dynamic range of step (c) is identical to step (a)
(2)
The clip in step (b) ensures that intermediate values do not exceed 16-signed bits, i.e. .
3.1 Use Case: 4x4 DST
The transform matrix T for 4x4 DST is specified as
According to the formula (1)
or
Similarly, according to the formula (2) we obtain
3.2 Summary
We summarize the dynamic range bounds (assuming that the input range [-215,215-1]) in the following tables:
Operation / Bound on Dynamic Range4x4 DST / 8x8 / 16x16 / 32x32
/ 242∙215 / 512∙215 / 225 / 226
Z+64 / 7,929,920 / 16,777,280 / 64+225 / 64+226
W=Clip3 / 215 / 215 / 215 / 215
/ 242∙215 / 512∙215 / 225 / 226
R+2048 / 7,931,904 / 16,779,264 / 2048+225 / 2048+226
Y=(R+2048)>12 / 1936 / 4096 / 8192 / 16384
Operation / Dynamic range in bits
4x4 DST / 8x8 / 16x16 / 32x32
/ 24 / 26 / 27 / 28
Z+64 / 24 / 26 / 27 / 28
W=Clip3 / 16 / 16 / 16 / 16
/ 24 / 26 / 27 / 28
R+2048 / 24 / 26 / 27 / 28
Y=(R+2048)>12 / 12 / 14 / 15 / 16
Max #bits / 24 / 26 / 27 / 28
For derivation of the above tables we use the following transform matrices specified in HEVC draft [4]:
1. 8x8 transform matrix:
{64, 64, 64, 64, 64, 64, 64, 64}
{89, 75, 50, 18,-18,-50,-75,-89}
{83, 36,-36,-83,-83,-36, 36, 83}
{75,-18,-89,-50, 50, 89, 18,-75}
{64,-64,-64, 64, 64,-64,-64, 64}
{50,-89, 18, 75,-75,-18, 89,-50}
{36,-83, 83,-36,-36, 83,-83, 36}
{18,-50, 75,-89, 89,-75, 50,-18}
2. 16x16 transform matrix:
{64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64}
{90 87 80 70 57 43 25 9 -9-25-43-57-70-80-87-90}
{89 75 50 18-18-50-75-89-89-75-50-18 18 50 75 89}
{87 57 9-43-80-90-70-25 25 70 90 80 43 -9-57-87}
{83 36-36-83-83-36 36 83 83 36-36-83-83-36 36 83}
{80 9-70-87-25 57 90 43-43-90-57 25 87 70 -9-80}
{75-18-89-50 50 89 18-75-75 18 89 50-50-89-18 75}
{70-43-87 9 90 25-80-57 57 80-25-90 -9 87 43-70}
{64-64-64 64 64-64-64 64 64-64-64 64 64-64-64 64}
{57-80-25 90 -9-87 43 70-70-43 87 9-90 25 80-57}
{50-89 18 75-75-18 89-50-50 89-18-75 75 18-89 50}
{43-90 57 25-87 70 9-80 80 -9-70 87-25-57 90-43}
{36-83 83-36-36 83-83 36 36-83 83-36-36 83-83 36}
{25-70 90-80 43 9-57 87-87 57 -9-43 80-90 70-25}
{18-50 75-89 89-75 50-18-18 50-75 89-89 75-50 18}
{ 9-25 43-57 70-80 87-90 90-87 80-70 57-43 25 -9}
When the input coefficient data is limited to 16-signed bits and an intermediate between vertical and horizontal 1D transforms are clipped to 16-signed bits, a 28-signed bits precision processor is sufficient for all HEVC/H.265 inverse transform operations.
4 References
[1] Louis Kerofsky, “Notes on JVT IDCT”, in Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6), JVT-C024, 3rd Meeting: Fairfax, Virginia, USA, 6-10 May, 2002.
[2] Henrique S. Malvar, Antti Hallapuro, Marta Karczewicz, and Louis Kerofsky, “Low-Complexity Transform and Quantization in H.264/AVC”, IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 13, NO. 7, JULY 2003.
[3] Tao Chen, Jiuhuai Lu, Yoshiichiro Kashiwagi, Shinya Kadono, “Dynamic Range of Outcome of Simplified 8x8 Transform and Quantization/De-quantization”, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6) 11th Meeting: Munich, DE, 15-19 March, 2004, JVT-K031.doc
[4] High efficiency video coding (HEVC) text specification draft 9, JCTVC-K1003.
[5] A. Fuldseth, G. Bjøntegaard, M. Sadafale, M. Budagavi, “Core transform design for HEVC”, JCTVC-F446.
[6] Yuriy A. Reznik, “On clipping and dynamic range of variables in IDCT designs”, ISO/IEC JTC1/SC29/WG11, MPEG2006/M14004.
[7] A. Fuldseth, G. Bjøntegaard, M. Sadafale, M. Budagavi, “Core transform design for HEVC”, JCTVC-G495.
Page: 1 Date Saved: 2013-01-06