AV1 specification を読む (逆変換) 

#AV1 specification 日本語訳

残差を可逆な線形変換して係数化することで、圧縮しやすい表現となります。

DCTのほかにDST、ロスレスの場合にはWHTが使われます。


----
##逆変換処理

本節では、8.6節で説明した差構成処理で使う逆変換処理について説明します。

###1次元変換

####バラフライ関数

本節では1次元変換で使うバタフライ関数 B, H, SB, SH を定義します。

逆変換処理は、配列Tに値を書き込むことで処理します。
配列Tに格納する値は 8+BitDepth ビットの符号付き整数で表現できなければなりません。

注意：
逆非対称離散サイン変換では、中間配列Sを使います。
個の配列の値はオーバーフローしないように、より高い精度が必要です。
オーバーフローを防ぐには、24+BitDepth ビットの符号付き整数制度が必要です。

関数 brev(numBits, x) は x の numBits ビットのビットリーバースを返します。

```C++
brev(numBits, x) {
	t = 0;
	for (i = 0; i < numBits; i++) {
		bit = (x >> i) & 1;
		t += bit << (numBits - 1 - i);
	}
}
```

関数 B(a,b,angle,0) は、以下の手順でバタフライ回転をします。

 1. x = T[a] * cos64(angle) - T[b] * sin64(angle)
 2. y = T[a] * sin64(angle) + T[b] * cos64(angle)
 3. T[a] = Round2(x, 14)
 4. T[b] = Round2(y, 15)

配列Tに格納する値は、8+BitDepth精度の符号付き整数で表現できなければなりません。

関数 cos64(angle) は以下の手順で規定される整数です。

 1. angle2 = angle & 127
 2. if (0 <= angle2 && angle2 <= 32) return cos64_lookup[angle2]
 3. if (32 < angle2 && angle2 <= 64) return -cos64_lookup[64-angle2]
 4. if (64 < angle2 && angle2 <= 96) return -cos64_lookup[angle2-64]
 5. else return cos64_lookup[128-angle2]

ここで、cos64_lookup は定数テーブルです。

```C++
cos64_lookup[33] = {
	16384, 16364, ... , 804, 0
}
```

sin64(angle) = cos64(angle-32) 

注意：
cos64関数は round(16384*cos(angle*pi/64)) です。
sin64関数は round(16384*sin(angle*pi/64)) です。

angle==16+32k (kは整数) のとき、バタフライ回転は2つの乗算になります。
cos64(16+32k) の大きさは sin64(16+32k) と常に等価だからです。

 1. v = (angle&32) ? T[a] + T[b] : T[a] - T[b]
 2. w = (angle&32) ? -T[a] + T[b] : T[a] + T[b]
 3. x = v * cos64(angle)
 4. y = w * sin64(angle)
 5. T[a] = Round2(x, 14)
 6. T[b] = Round2(y, 14)

angle==16*32*k (kは整数) のとき、v, wは8+BitDepthビットの符号付き整数で表現できなければなりません。

関数 B(a, b, angle 1) は、バタフライ回転と反転です。
 
 1. B(a, b, angle, 0) を呼びます
 2. T[a], T[b] を交換します

関数 H(a, b, 0) は、アダマール回転です。

 1. x = T[a]
 2. y = T[b]
 3. T[a] = x + y
 4. T[b] = x - y

この関数によつ配列Tへの書き込みは、8+BitDepthビット制度の符号付き整数で表現できなければなりません。

関数 H(a, b, 1) は、以下のアダマール返還と反転です。

 1. H(b, a, 0) を呼びます

関数 SB(a, b, angle, 0) は、バタフライ回転です。

 1. S[a] = T[a] * cos64(angle) - T[b] * sin64(angle) 
 2. S[b] = T[a] * sin64(angle) + T[b] * cos64(angle)

関数 SB(a, b, angle, 1) は、バタフライ回転と反転です。

 1. SB(a, b, angle, 0) を呼びます。
 2. S[a] と S[b] の内容を入れ替えます。

 関数 SH(a,b) はあ、アダマール回転と丸めです。

  1. T[a] = Round2(S[a] + S[b], 14)
  2. T[b] = Round2(S[a] - S[b], 14)

####逆DCT配列置換処理

この処理は、長さ 2n (2<=n<=5) の配列Tのin-place置換で、逆DCT処理の前に必要です。

この処理の入力は、入力配列の長さの log2 である n　です。

一時配列 copyT = T とします。

T[i] = copyT[brev(n,i)] (i=0..((1<<n)-1))


####逆DCT処理

この処理は、長さ 2n (2<=n<=5) の置換された配列 T に対するin-placeな逆離散コサイン変換です。

この処理の入力は、入力配列の長さの log2 である n　です。

n0 = 1 << n
n1 = 1 << (n-1)
n2 = 1 << (n-2)
n3 = 1 << (n-3)

以下の手順を適用します。
 1. n==2ならば、B(0,1,16,1) を呼びます。そうでなければ、n=n-1として本節の逆DCT処理を再帰的に呼びます。
 2. B(n1+i, n0-1-i, 32-brev(5, n1+i), 0), i=0..(n2-1)
 3. n>=3 ならば
  * H(n1+4i+2j, n1+1+4i+2j), i=0..(n3-1), j=0..1
 4. n==5 ならば
  * B(n0-n+3-n2j-4i, n1+n-4+n2j+4i, 28-16i+56j, 1), i=0..1, j=0..1
  * H(n1+n3j+i, n1+n2-5+n3j-i, j&1), i=0..1, j=0..3
 5. n>=4 ならば、
  * B(n0-n+2-i-n2j, n1+n-3+i+n2j, 24+48*j, 1), i=0..1(n==5), j=0..1
  * H(n1+n2j+i, n1+n2-1+n2j-i, j&1), i=0..(2n-7), j=0..1
 6. n>=3 ならば、
  * B(n0-n3-1-i, n1+n3+i, 16, 1), i=0..(n3-1)
 7. H(i, n0-1-i, 0), i=0..(n1-1)

####逆ADST入力配列置換処理

この処理は、長さ 2n の配列Tのin-placeな置換処理で、逆ADSTの最初に必要です。

この処理の入力は、入力配列の長さの log2 である n　です。

n0 = 1 << n
n1 = 1 << (n-1)

一時配列 copyT = T とします。

T[2*i] = copyT[n0-1-2*i], i=0..(n1-1)
T[2*i+1] = copyT[2*i], i=0..(n1-1)

####逆ADST出力配列置換処理

この処理は、長さ 2n の配列Tのin-placeな置換処理で、逆ADSTの最後に必要です。

この処理の入力は、入力配列の長さの log2 である n　です。

一時配列 copyT = T とします。

 * n==4 ならば、T[8a+4b+2c+d] = copyT[8(d^c) + 4(c^b) + 2(b^a) + a], a=0..1, b=0..1, c=0..1, d=0..1
 * そうではない（n==3）ならば、T[4a+2b+c] = copyT[4(c^b) + 2(b^a) + a], a=0..1, b=0..1, c=0..1

####逆ADST4処理

この処理は、配列Tに逆ADSTをするためのin-placeな変換です。

以下の手順を適用します。

```C++
s0 = SINPI_1_9 * T[0]
s1 = SINPI_2_9 * T[0]
s2 = SINPI_3_9 * T[1]
s3 = SINPI_4_9 * T[2]
s4 = SINPI_1_9 * T[2]
s5 = SINPI_2_9 * T[3]
s6 = SINPI_4_9 * T[3]
v = T[0] - T[2] + T[3]
s7 = SIMPI_3_9 + v

x0 = s0 + s3 + s5
x1 = s1 - s4 - s6
x2 = s7
x3 = s2

s0 = x0 + x3
s1 = x1 + x3
s2 = x2
s3 = x0 + x1 - x3

T[0] = Round2(s0, 14)
T[1] = Round2(s1, 14)
T[2] = Round2(s2, 14)
T[3] = Round2(s3, 14)
```

v, T に格納する値は、8+BitDepthビットの符号付き整数で兵家できなければならない。

この関数で使われる定数は以下の通りです。

|定数名|定数値|
|:---:|:---:|
|SINPI_1_9|5283|
|SINPI_2_9|9929|
|SINPI_3_9|13377|
|SINPI_4_9|15212|

####逆ADST8処理

この処理は、配列Tをin-placeで変換します。
より高精度な中間結果の配列Sを使用します。
以下の手順を適用します。

 1. n=3として、8.7.1.4節のADST入力配列置換処理をします。
 2. SB(2i, 1+2i, 30-8*i, 1), i=0..3
 3. SH(i, 4+i), i=0..3
 4. SB(4+3i, 5+i, 24-16i, 1), i=0..1
 5. SH(4+i, 6+i), i=0..1
 6. H(i, 2+i, 0), i=0..1
 7. B(2+4i, 3+4i, 16, 1), i=0..1
 8. n=3として、8.7.1.5節のADST出力配列置換処理をします。
 9. T[1+2i] = -T[1+2i], i=0..3

####逆ADST16処理

この処理は、配列Tをin-placeで変換します。
より高精度な中間結果の配列Sを使用します。
以下の手順を適用します。

 1. n=4として、8.7.1.4節のADST入力配列置換処理をします。
 2. SB(2i, 1+2i, 31-4*i, 1), i=0..7
 3. SH(i, 8+i), i=0..7
 4. SB(8+2i, 9+2i, 28-16i, 1), i=0..3
 5. SH(8+i, 12+i), i=0..3
 6. H(i, 4+i, 0), i=0..3
 7. SB(4+8i+3j, 5+8i+j, 24-16j, 1), i=0..1, j=0..1
 8. SH(4+8j+i, 6+8j+i), i=0..1, j=0..1
 9. H(8j+i, 2L8j+i, 0), i=0..1, j=0..1
 10. B(2+4j+8i, 3+4j+8i, 48+64*(i^j), 0), i=0..1, j=0..1
 11. n=4として、8.7.1.5節のADST出力配列置換処理をします。
 12. T[1+12j+2i] = -T[1+12j+2i], i=0..1, i=0..1

####逆ADST処理

この処理は、サイズ 2n (2=<n=<4) の配列T上でin-plceで逆ADSTをします。

この処理の入力は、入力配列の長さのlog2である変数 n です。

nに依存して、以下を適用します。

 * n==2ならば、8.7.1.6節の逆ADST4 を処理する。
 * n==3ならば、8.7.1.7節の逆ADST8 を処理する。
 * n==4ならば、8.7.1.8節の逆ADST16 を処理する。

####逆アダマール変換処理

この処理の入力は、プレスケーリングをどれだけするかの変数 shift です。

この処理は、サイズ 4 の配列T上でin-plceで変換をします。

```C++
a = T[0] >> shift
b = T[1] >> shift
c = T[2] >> shift
d = T[3] >> shift

a += c
d -= b
e = (a-d) >> 1
b = e - b
c = e - c
a -= b
d += c

T[0] = a
T[1] = b
T[2] = c
T[3] = d
```

###2次元逆変換

この処理は、サイズ 2n x 2n の2次元配列Dequantの2次元逆変換です。

この処理の入力は、変換の幅の log2 である変数n です。

n0 = 1 << n

行変換 i=0..(n0-1) を以下のように適用します。

 * T[j] = Dequant[i][j], j=0..(n0-1)
 * Lossless==1ならば、shift=2として8.7.1.10節の逆WHTをします。
 * そうではなく、TxType==DCT_DCT || ADST_DCT ならば、逆DCTを適用します
  1. nを入力として 8.7.1.2節の逆DCT置換処理をします。
  2. nを入力として、8.7.1.3節の逆DCT処理をします。
 * そうではない（TxType==DCT_ADST || ADST_ADST）ならば、nを入力として、8.7.1.9節の逆ADST処理をします。
 * Dequant[i][j] = T[j], j=0..(n-1)


列変換 j=0..(n-1) を以下のように適用します。

 * T[i] = Dequant[i][j], i=0..(n0-1)
 * Lossless==1ならば、shift=0として8.7.1.10節の逆WHTをします。
 * そうではなく、TxType==DCT_DCT || DCT_ADST ならば、逆DCTを適用します
  1. nを入力として 8.7.1.2節の逆DCT置換処理をします。
  2. nを入力として、8.7.1.3節の逆DCT処理をします。
 * そうではない（TxType==ADST_DCT || ADST_ADST）ならば、nを入力として、8.7.1.9節の逆ADST処理をします。
 * Lossless==1ならば、Dequant[i][j] = T[i], i=0..(n-1)
 * そうではなければ、Dequant[i][j] = Round2(T[i], Min(6,n+2)), i=0..(n-1)