画像変換のDCTをプログラム組んでみる その1 DCTの行列

微妙な連載と言うことで今回はDCTをプログラム化してみるところからです。

なんか検索でLLMで検索するとこのブログが表示されやすいという現実からちょっとやってみようと思います。

といっても、ちゃんとした資料は別の場所にあるはずですのでそれを参考に。突っ込みどころはいろいろあると思います。

DCTの基本式

画像変換では正変換にDCT-IIを使うことが多いようです。原理式は以下の通りです。

y_n = c_n ¥sum_{k=0}^{N-1} ¥cos ¥frac{(2k+1)n¥pi} {2N} x_k ¥qquad (c_0 = ¥frac{1}{sqrt{N}}_, c_n = ¥sqrt{¥frac{2}{N}} (1 ¥le n ¥le N-1))

行列展開する

画像変換なので、8×8でブロックを作ることにしてこの式をN=8として行列展開してみます。r_k = ¥cos ¥frac{¥pi}{16}kのように係数を設定します。

このとき、係数がすべてcosであることと、この係数での設定によってr_4 = ¥cos ¥frac{¥pi}{16} ¥times 4 = ¥cos ¥frac{¥pi}{4} = ¥frac{1}{¥sqrt{2}}となることに注意します。

変換行列を¥mathbf{y} = C_8 ¥times ¥mathbf{x}のように設定すると、変換行列は以下のようになります。

C_8 = ¥frac{1}{2}¥begin{pmatrix} r4 & r4 & r4 & r4 & r4 & r4 & r4 & r4 ¥¥ r1 & r3 & r5 & r7 & -r7 & -r5 & -r3 & -r1 ¥¥ r2 & r6 & -r6 & -r2 & -r2 & -r6 & r6 & r2 ¥¥ r3 & -r7 & -r1 & -r5 & r5 & r1 & r7 & -r3 ¥¥ r4 & -r4 & -r4 & r4 & r4 & -r4 & -r4 & r4 ¥¥ r5 & -r1 & r7 & r3 & -r3 & -r7 & r1 & r5 ¥¥ r6 & -r2 & r2 & -r6 & -r6 & r2 & -r2 & r6 ¥¥ r7 & -r5 & r3 & -r1 & r1 & -r3 & r5 & -r7 ¥end{pmatrix}

更に行列を展開して

C_8 = ¥frac{1}{2} ¥cdot P_8 ¥cdot M_8 ¥cdot A_8

と変換するとこまでが作業になります。これについてはAP-922などの資料を参考にしてください。

なお、逆変換についてはDCT-IIIを考える必要はありません。行列の形にしたので逆変換=逆行列の乗算になります。

逆行列については、DCT変換は直交変換であることから、直交変換の逆行列は行列を転置させたものになるので

C_8^{-1} = {}^t C_8 = ¥frac{1}{2} ¥cdot {}^t A_8 ¥cdot {}^t M_8 ¥cdot {}^t P_8

で求められます。

行列の係数について

アルゴリズムを確認した後で正しいかどうか検算するときに面倒になるのが行列の係数についてです。

特にDCTの場合、係数がすべてcosによって作られているのでそれぞれの係数の加減算が生じたときに別の値になる、という現象も起こります。

次回の演算で出てくる計算の一種ですが、LLMのバタフライ演算を行うと、ある行の演算結果は以下の形になります。

y_1 = ¥frac{1}{¥sqrt{2}}(t_4(r_3-r_5)+t_5(r_1-r_7)+t_6(r_1+r_7)+t_7(r_5+r_3))

このままだと処理できませんが、cosの和・差を積に直す公式を使うと

r_3-r_5 = -2¥sin¥frac{3+5}{32}¥pi¥sin¥frac{3-5}{32}¥pi = ¥frac{-2}{¥sqrt{2}}¥sin¥frac{-1}{16}¥pi = ¥sqrt{2}¥sin¥frac{1}{16}¥pi = ¥sqrt{2}¥cos¥frac{7}{16}¥pi = ¥sqrt{2}r_7

と見事に別の係数へと変換され、これを繰り返すと

y_1 = t_4 r_7 + t_5 r_5 + t_6 r_3 + t_7 r_1

というきれいな数に変換される、というものです。この辺は三角関数を使ったときの特有だと思いますのでよく覚えておきましょう。

原理式については以上です。次回はこれをLLMアルゴリズムで実際にプログラムとして組んでみたときの状態をやってみます。

この後は変換行列が展開されているものとして話が進みますので先にその行列を確認しておいてくださいね。この先やっても大丈夫ですよね・・・?

展開した行列を書いていないのはtex記法がとっても面倒だったという理由だったりします。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

この記事のトラックバック用URL