ビデオ コーデックを作成してみよう - パート 3: 静止画

このシリーズの前の部分では、離散コサイン変換について、数学的定義から実際の例での実装まで学びました。さらに、周波数領域でデータを表現する DCT の機能により、非可逆データ圧縮がどのように可能になるかを見てきました。

今、私たちは次のステップに進みます。最後に、これまで議論してきた抽象的な数値配列と、それらが表す実際のイメージを結ぶ線を描きます。

この記事を終えるまでに、実際の JPEG 画像圧縮プロセスの約 80% が再発見されたことになります。

マトリックス

前回の記事では2D-DCTについて紹介しました。次に、その式を少し調整したバージョンを見てみましょう。

変数uおよびv DCT エンコードされた 2D 配列内の値の水平および垂直オフセットを表します。関数α(x)はx == 0の場合は1/sqrt(2)に等しく、それ以外の場合は1なります。最後に、 xとyソース画像内のピクセルの位置を表します。

これは明白ではないように思われるかもしれませんが、同じ計算を次の形式の行列乗算として表すことができます。

この公式では、 DCTは DCT 行列、 Tは行列転置、 IMGはソース画像を表します。

この操作の複雑さはソース画像のサイズに比例することに注意してください。あらゆるサイズの画像を管理し、作業を軽減するために、計算を 8 × 8 ピクセルの画像ブロックに制限します。

実際の画像は解像度が高くなる傾向がありますが、多くの独立した 8x8 ブロックで構成されていると考えることができます。

望ましい効果を生み出す DCT マトリクスを計算する方法は次のとおりです。

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

dctMatrixの値は次のとおりです。

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

ご覧のとおり、これは単なる数値の配列です。変換を適用するたびに行列値を再計算する必要がないため、コード内の定数配列に行列値を保持できます。

このコードは 8x8 行列の乗算を実行します。

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

8x8 DCT を次のように計算します。

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

逆 DCT は、通常の DCT 行列と転置された DCT 行列を交換するだけで取得できます。

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

大きな絵

これで、知識を実際の画像に適用する準備が整いました。これを使って作業してみましょう:

この画像を数値の配列としてロードするコードがあると想像してください。各数値は対応する位置のピクセルの明るさを表します。

 func loadImage(width: Int, height: Int) -> [Float] { ... }

画像が 256x256 ピクセルであると仮定すると、次の値は左上隅に対応します。

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

数学的な便宜上、ピクセルの明るさを0.0 ～ 255.0の数値として表す代わりに、 128.0を減算します。言い換えれば、値を128.0ではなく0.0付近に集中させます。

次に、画像のすべての 8x8 ブロックにdct関数を適用します。

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

結果は次の画像です。

写真ではかろうじて認識できますが、いくつかのパターン（帽子など）がまだ見えています。興味深いことに、黒いピクセルがたくさんあります。実際、ほとんどのピクセルは黒です。 8x8 ブロックの 1 つを拡大してみましょう。

この 8x8 ブロックは、周波数領域表現がどのようなものかを示しています。ゼロ以外の値は、ブロックの左上隅に集中する傾向があります。右下隅に向かうにつれて、大きな値になる可能性は大幅に減少します。

これは、左上の値が画像にとってより重要であることを示しています。

右下の値を0.0に設定して一部を削除する「圧縮」関数を作成することで、これを実証できます。

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

処理ループを調整した後:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

次の画像が得られます。

何が起こったのか少し考えてみましょう。各画像ブロックの 64 個の値のうち 39 個を削除しましたが、それでも元の画像によく似た画像が生成されました。これは、行列を乗算し、データを決定的に破棄するだけで 60% の圧縮率が達成されることになります。

DCT 係数の 86% を破棄すると、次のことが起こります。

量子化

DCT 係数を浮動小数点数として保存するのは非常に無駄であり、通常は 4 バイトのストレージが必要です。代わりに、最も近い整数に四捨五入する必要があります。 8x8 ブロックの場合、各値は 2 バイトの整数で表すことができます。

先ほど調べたブロックをもう一度見てみましょう。その（四捨五入された）数値表現は次のとおりです。

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

以前に目視で確認したように、左上隅に近いほど大きな値が発生する可能性が高くなります。ただし、すべてのブロックがこのパターンに従うわけではありません。画像の別のブロックを次に示します。

このブロックは、DCT 値の一般的な分布に準拠していません。右下の値を盲目的に破棄し続けると、画像の一部にさらに多くの圧縮アーティファクトが表示される可能性があります。それを避けるには、どのブロックが他のブロックよりも多くのデータを必要とするかを決定する必要があります。

シンプルかつ洗練されたソリューションは、以前に発見したクラスタリング特性を利用します。それは「量子化」と呼ばれます。 DCT 値をさまざまな係数で除算します。便宜上、各 DCT 係数の値を含むテーブルを使用します。

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

より重要な位置はより低い約数に対応し、その逆も同様です。量子化されたデータにテーブルの係数を乗算することで、逆量子化ステップを実行します。

これらの関数は、それぞれ量子化ステップと逆量子化ステップを実行します。

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

量子化と逆量子化をコードに組み込んでみましょう。

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

最初のブロックを量子化すると次のようになります。

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

そしてこれが 2 番目のブロックです。

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -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 0 0 0 0 0

2 番目のブロックにはさらにゼロ以外の値があることがわかります。したがって、量子化ステップにより、より有用なデータを保存し、残りを破棄できるようになります。

結論と次は何ですか?

基本的な数学から、実際の画像のエンコードとデコードに進みました。 DCT が任意のデータを一連の周波数に変換する方法と、一部の周波数が他の周波数よりもどのように重要であるかを視覚的に確認しました。

基本的な圧縮に慣れた後、量子化の概念を導入しました。これにより、ストレージ要件がさらに削減されます。

次のパートでは、RGB 画像に移り、結果のデータをさらに圧縮する方法を検討します。

この記事のコードはhttps://github.com/petertechstories/image-dctにあります。