画像変換のDCTをプログラム組んでみる その2 LLMのDCT変換

二回目はDCT変換でもLLMと呼ばれるアルゴリズムを使ったDCT変換の式です。

変換の論文は私も見つけることができませんでした。なのでとある場所から見つけたアルゴリズムを見やすいようにプログラム化したものです。

もちろん高速でも何でもないので実際に画像変換に使うにはいくつか変更が必要です。

コードはこんな感じです。

void LLMDCT(float y[8],const float x[8])
{
	float t0,t1,t2,t3,t4,t5,t6,t7; float c0,c1,c2,c3; float r[8]; float invsqrt2; int i;
	invsqrt2 = (float)(1.0f / M_SQRT2);
	for(i = 0;i < 8;i++){ r[i] = (float)(cos((double)i / 16.0 * M_PI) * M_SQRT2); }
	c1 = x[0]; c2 = x[7]; t0 = c1 + c2; t7 = c1 - c2;
	c1 = x[1]; c2 = x[6]; t1 = c1 + c2; t6 = c1 - c2;
	c1 = x[2]; c2 = x[5]; t2 = c1 + c2; t5 = c1 - c2;
	c1 = x[3]; c2 = x[4]; t3 = c1 + c2; t4 = c1 - c2;
	c0 = t0 + t3; c3 = t0 - t3;
	c1 = t1 + t2; c2 = t1 - t2;
	y[0] = c0 + c1;
	y[4] = c0 - c1;
	y[2] = c2 * r[6] + c3 * r[2];
	y[6] = c3 * r[6] - c2 * r[2];
	c3 = t4 * r[3] + t7 * r[5];
	c0 = t7 * r[3] - t4 * r[5];
	c2 = t5 * r[1] + t6 * r[7];
	c1 = t6 * r[1] - t5 * r[7];
	y[5] = c3 - c1; y[3] = c0 - c2;
	c0 = (c0 + c2) * invsqrt2;
	c3 = (c3 + c1) * invsqrt2;
	y[1] = c0 + c3; y[7] = c0 - c3;
	for(i = 0;i < 8;i++){ y[i] *= invsqrt2 * 0.5f; }
}

これだけ見れば演算のブロック図を書くことくらいは簡単だと思います。

ちゃんと計算してみるといいと思いますが、すべての係数について前回の行列計算(¥mathbf{y} = C_8 ¥times ¥mathbf{x})を完全に行っていることが検証できるはずです。

アルゴリズム中の注意点だけ。

係数はあらかじめ√2倍したものを用いている

これがLLMアルゴリズムの要点です。バタフライ演算中の係数は元々のcos係数に対して√2倍したものが演算されます。

途中で何回か√2での除算が入ることで係数を調整していますが、これについては高速化の秘密もあります。

もちろん、実際に使用するときは係数の計算は計算開始の一度だけもしくは定数として組み込んでしまうかのどちらかです。

最後の定数乗算部は画像処理では一つにまとめて

画像処理では二次元以上の処理となるので定数乗算部を二回以上行うことになります。

また、変換後に量子化マトリクスの除算処理などがあるので、そのときにまとめて行うようにします。

後は逆変換であるIDCTの処理ですね。こちらの方が難しいのでちょっと見てみるとおもしろいと思います。


コメントを残す

メールアドレスが公開されることはありません。

*

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