8×8-DCTの高速アルゴリズムLLMとAANがやっとわかった・・・

・・・今更ですかい?という問題はありますが、気になっていたのですがよくわからなかったLLMとAANのアルゴリズムの謎が解けました。

AP-922では両方のアルゴリズムの基本的な考え方についてちゃんと解説していたんですね・・・。

認識が間違っているかもしれませんが、AP-922(AP-945を含む)で解説されているのは主にAANの方です。Section3の式で

C8 = 1/2 * P8 * M8 * A8 (6)

M8 = D8 * B8 * E8 * F8 (11)

というDCTの計算式の係数の行列分解がありますが、AANのアルゴリズムは(11)の計算をどのように行うか?に特化した計算な訳ですね。

で、そうなるとLLMのアルゴリズムは?という資料をネット上から簡単に見つけることができなくて、とりあえず見つけたものも

LLMのDCT変換をバタフライ計算化したものだったわけで、原理式が不明だったわけですが・・・。

気がついてみれば何のことはない。単にM8をどうやったら計算の数を下げることができるか?を考えたものだった、ということだったとは・・・。

M8の行列についてはAP-922に記述されていますのでそれを見てもらえばいいですが、この行列(8×8行列だが、0行列部分を除外すると4[行]x4[列]x2[要素])の

γ部分(cosの係数項)をできるだけ少ない乗算数で計算する、というものだったんですね・・・。

変換部のバタフライを計算していった時に初めてわかりました。ということで、LLMの原理式はM8の計算だった、ということに・・・。

LLMかAANかどちらかで組んでいるんだろう、とは思っていましたが確証がなかったので・・・。

論文がうまいこと検索できなかったのでこういうことをする羽目になっちゃいました。

なお、今現在の自前のDCT変換ルーチンはAP-922ベース=AANなので、よく言われることには「演算数はLLMより少ないが誤差が大きい」らしいので、

SIMD演算部をLLMベースで組み直してみようかと思っています。これだけで誤差(=画像に現れるノイズ)が減るのであれば使えると思っています。

なお、libjpegはLLMベースで組んでいるようなので、それをバタフライ化すればLLMのアルゴリズムは簡単に認識できると思います。

コメントを残す

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

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