http://halicery.com/3Video Decoders/H265 HEVC/HEVC Transform.html

Fast HEVC Transform

The largest transform size in HEVC is 32×32. The 32-point 1-D transform in matrix form requires 1024 multiplications, the whole 2-D transform of the block with the row/column method would require 1024×32×32 = 65 536. This is unacceptable in most applications, so there are quite many fast computing algorithms. I have also derived my recursive algoritm to compute these large transforms by factorization and circular transform of the odd DCT parts. The result is the fig above: the 32-point 1-D transform with this method needs maximum of 120 integer multiplications.

I have written a draft paper about the method, and based on this C-code for all transform sizes. The source code can be found in a Bitbucket repository.

Here is an example during decoding the test stream ipcm_A_NEC_3.bit by my decoder, the first transform is a 32×32 transform block. After decoding the residuals (coefficients) we get this:

Opening ipcm_A_NEC_3.bit

cIdx: 0
 9  0  0  1  0  1  1  0  0  0  0  0  0  0  0  0  0
 1  1  0 -1  1  0  0  0  0  0  0  0  0  0  0  0  0
 2  0  1  0  0 -1  0 -1  0  0  0  0  0  0 -1  0  0
 0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0
 0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0 -1  0 -1  0  0  0  0  1  0  0  0  0  0  0  0
-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 1  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0
 0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0
-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1

The scaling is flat, 180 for all:

cIdx: 0
1620    0    0  180    0  180  180    0    0    0    0    0    0    0    0    0    0
 180  180    0 -180  180    0    0    0    0    0    0    0    0    0    0    0    0
 360    0  180    0    0 -180    0 -180    0    0    0    0    0    0 -180    0    0
   0    0    0    0    0    0    0    0    0 -180    0    0    0    0    0    0    0
   0    0    0 -180    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0 -180    0 -180    0    0    0    0  180    0    0    0    0    0    0    0
-180    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
 180    0    0    0    0    0    0    0    0    0    0    0 -180    0    0    0    0
   0    0    0    0    0    0 -180    0    0    0    0    0    0    0    0    0    0
-180    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0  180    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0 -180    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0  180    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 -180

Then performing the inverse integer transform, we obtain the residuals added to the predicted values:

cIdx: 0
   9   19   24   20   16   20   24   21   16   15   19   23   27   28   24   17  11    9   10   11   14   14   12   12   14   15   13   12   18   24   19    9
  14   17   23   25   21   17   20   23   21   17   20   27   25   17   16   21  20   13   11   15   15   10   10   18   22   15    8    8   14   19   22   25
  19   22   24   23   20   20   22   22   21   21   24   25   19   13   15   21  22   18   14   16   17   15   15   17   19   15    7    4   10   20   29   34
  24   28   26   19   18   24   24   18   15   21   25   21   17   17   18   18  17   16   15   16   22   25   19   10    9   12   10    7   12   24   31   31
  29   28   26   24   22   20   16   11   10   15   23   26   21   15   14   16  16   12   12   18   24   22   15    9    9   10   12   13   16   21   26   29
  30   27   28   29   24   13    5    4    6   11   21   27   21   11    9   16  18   13   11   16   17   12    9   12   16   14   13   13   13   14   20   28
  28   30   29   23   16   12    7    3    5   11   17   16   14   14   15   16  17   17   13    8    6    8   11   13   17   19   15    9    9   14   19   20
  29   30   25   16   11   12   13   11    9    9    7    6   11   18   21   18  16   16   13    7    7   11   14   13   14   15   13   10   12   16   16   12
  26   23   20   19   14   10   12   17   15    6    3    8   15   18   18   17  15   13   15   17   15   11   12   15   13    8    9   15   19   15   11   10
  19   18   20   20   16   10    9   13   14   11   10   14   18   17   14   11  12   16   21   22   18   13   13   14   12    8    9   14   17   14    9    8
  18   19   16   10    7    9   10    9   13   17   16   13   16   21   17    7   6   15   20   18   17   20   19   12    8    9   11   11   11   12    8    2
  27   17    4   -3   -3    1    8   13   17   16   12   12   17   22   20   12   6    4    7   11   17   22   21   14    6    5    9   12   11    5    0   -2
  30   11   -5   -8   -6   -5    2   12   17   14   11   14   17   18   18   15   7   -2   -2    6   14   17   17   15    7    3    8   14    9   -3   -7   -3
  18    8   -3   -6   -4   -1   -1    1    9   17   18   15   14   16   14    8   4    4    3    3    7   13   14    8    4    7   13   12    3   -5   -7   -6
   9    5    0   -2    2    5    1   -1    6   16   18   14   13   16   13    5   4    9   10    6    6   12   11    3    1    8   16   14    6   -1   -4   -6
  14    5    0    3    7    6    5    9   14   13   11   12   15   16   14   12  10    9   11   12   11   10    9    7    4    5   13   20   15    4   -2    0
  19   11    6    8    8    5    6   14   19   16   11   11   14   17   16   15  15   16   16   13    7    6   11   15   13   10   14   18   15    8    6    9
  18   20   18   12    7    3    2    5   15   23   20   13   14   18   15    9  13   24   23   10   -1    3   13   19   20   21   18   11    8   10   13   14
  20   21   21   16    7   -3   -8   -2   10   19   21   19   19   16   10    4   8   19   21   12    2    2   11   19   22   20   16   12    9    9   11   13
  23   17   15   15    7   -7  -13   -4    6   10   14   19   20   12    4    2   3    7   13   14    9    5    9   16   16   11   11   15   13    5    4    9
  18   15   12    8    2   -5  -10   -8    0    9   12   11    9    6    1   -2   1    7   11   10    7    8   11   12   10   10   10    8    4    2    4    6
  10   11    9    4    2    0   -6   -9   -2   10   12    4   -3   -3   -3   -2   5   14   13    6    3    9   13   12   12   14   10   -1   -7   -3    4    9
  11    6    4    7    8    4   -1   -1    3    6    7    4   -3   -7   -3    6  12   12   11   10   10   11   13   16   17   14   10    4   -4   -7    0    9
  14    7    4    8   11    9    7    6    5    3    4    6    4    2    5   11  12    8    9   16   21   21   19   18   16   14   15   15    8   -1   -3    0
  13   14   13   10   11   15   13    7    5    8   10   10   11   14   14    9   8   10   14   17   24   29   27   20   18   22   23   18   13    8    0   -7
  14   18   18   15   12   12   12   10   10   13   15   15   15   16   13   10  10   13   17   19   23   28   29   29   29   28   23   16   12   10    5   -1
  20   18   17   15   10    7   12   20   19   12   11   16   17   12   11   13  13   10   14   22   26   26   30   36   35   23   14   13   13   11    9    9
  19   19   16    9    5    9   18   23   19   11    7    9   12   13   13   10   7    7   12   21   28   31   32   30   26   17    9    9   15   18   16   11
  11   18   18   10    7   14   20   17   12   10    9    7    9   12   10    3   2    7   14   20   28   32   29   20   16   14    9    7   15   24   21   11
   8   13   18   19   16   14   13   11    7    6   10   14   10    4    1    4   5    6   11   20   25   23   19   18   18   14   10   10   15   19   20   19
  13   13   17   20   18   14   11    9    5    3    8   14   10    1    2   10  11    4    4   13   19   17   14   18   21   18   14   14   15   16   19   22
  18   20   16   10   10   17   18   10    3    4    7    6    5    7   12   15  11    4   -1    3   13   20   18   15   18   22   20   14   14   19   21   18

The result was tested against another HEVC analyzer (Intel) and so far it is promising.


Sun Jun 17 22:53:43 UTC+0200 2018 © A. Tarpai