DMNAはじめに
テクノマセマティカルのDMNA（Digital Media New Algorithm）の秘密に迫る．結論から言うと迫りきれなかった．ただし，アプローチとしては「実装における」演算回数の削減，という点に落ち着くと考えられる．まずDCT演算の高速化について触れ，実装に着目する．さらに特許を2件見て，まとめる．
DCT演算
画像符号化の処理量のかなりを占めるDCT処理（Discrete Cosine Transfrom：離散コサイン変換）をいかに削減するか．これまでに数多の研究が行われ，さらに現在でも高速化手法がちらほら発表されている．
DCTの演算回数削減は，Wangの高速化手法*1が一般的である．ただし，これはスケールを含めて正確な計算を実行するとき，という暗黙の条件がある．また，LLM*2やAAN*3というより実践的な高速化手法もある．ロッシー符号化においてDCT係数は量子化，すなわちスケール変換が行われる．したがって，量子化とDCT変換時のスケール変換を同時に行う方式をとれば，スケールを考慮せずに高速化が可能である．
実装
実装においては，浮動小数点ではなく固定小数点を用いることが多い．固定小数点演算，すなわち整数演算の方が高速であるためである．Intel社のApplication Note 922においてはこの手法とMMX，SSEの組み合わせによる高速化手法が述べられている．ただし，整数演算においても，乗算より加算の方が依然として高速である．この傾向は低消費電力系のCPUや，チップを作るときには顕著になると考えられる．
ここで，8要素1次元DCTにおけるDCTの計算アルゴリズムに着目する．定義式通りでは，56回の加算，64回の乗算が必要になる（8x8のDCT行列と8x1の係数行列の演算回数に相当）．LLMでは28回の加算，11回の乗算にまで削減可能である．AP-922では26回の加算，8回の乗算で実現可能である．ただし，スケール変換がさらに必要である．
実際にこれらの演算回数で実装できるのかというと，そう言うわけではない．まず，浮動小数点は演算コストが高いため，固定小数点を採用することになる．固定小数点の加算は容易に実装できるが，乗算は小数点の位置が移動するため，これを調整するシフト演算必要がある．さらに，限られた有効数字で計算精度を向上させるために四捨五入を実現する必要がある．つまり，理論的には表出しない加算やシフト演算が非常に多く隠れているのである．なお，加算とシフトの演算コストは一般的に同じと見なせる．
特許１
ここまでの話は，極々当たり前かつ一般的な話である．では，DMNAと名付けるに値する新技術はどこにあるのか．こういった話は検索をかけるのが常套手段である（要領としては，10年前にMSDNからAPIの使い方を検索するのと同じである）．ネットにはめぼしい情報はなく，ノウハウが流出しているわけがないとも言える．次に文献検索システムにより検索する．キーワードは「著者名」である．名前も分からない技術を探すには，人伝が最良ということだ．しかし，技術論文としては発表されていないようだった．無論，データベースに登録されていなかったか，著者名が正しく登録されていなかっただけの可能性もある．最後に特許を検索する．3件の特許が申請されているようであったが，そのうち関係があるのは2件．特許公開平６−３３２９３３，特許公開２００３−３０１７４である．前者は，DCTの計算方法とそのハードウェア実装について，後者は前者の計算方法をより一般的にして，特許の有効範囲を広げた模様である．
933によると，上記のうちWangの高速演算（の変形），固定小数点を既存の技術として利用している．特筆すべきは，乗算を完全に排除している点にある．例えば，乗数として181は，181=128+64-1=2^7+2^6-1となる．つまり，2回のシフトと2回の加算で計算できる．4回の加算，シフトと1回の乗算のどちらが早いかは判断しかねるが，当たり前に思考すれば8ビット同士の乗算には7回の加算と7回のシフトが必要になる．したがって，シフトと加算に分解するのは十分おつりが来る手法である．なお，乗算の分解自体はありふれた手法であり，この点のみでは特許にはならないと思う（のだが，どうだろうか？）．詳しく読んでないのでわからないが，ハードウェア実装の巧妙さと合わせて特許に値する，ということだろう．
乗算をシフトと加算に還元することが一つ目のアイディアである．では，スケールは量子化でつじつまを合わせるとして，いったいどんな係数にすればいいのか．2進数で考えれば1の立っているビット数が少ない程効果が大きい．ただし，先に見たように負の係数を導入するとより柔軟に考えることが出来る．これを3値化2進数という（-1,0,+1の3値を利用する）．3値化2進数には興味深い性質があるらしいが，ここでは取り扱わない（授業で聞いたのだが忘れた）．さて，結局加算，シフト回数は何回になるのだろうか．あまりの多さに数えるのに飽きた．また，数えた所で，比較対象がないので良いとか悪いとか言えない．CPU（携帯向けも含めて）における乗算コストは劇的に下がっているので，ターゲットを絞らないと比較できない．さらに，パイプラインも導入されているので，事実上検証できない．
特許２
ところで，この特許は1992年のものである．当時はDCTの計算量は非常に膨大と思われた．ある意味過去の話であり，そして現在の話でもある．この特許の有効性の検証は引き続き行うとして，174はどこに新規性があるのだろうか．曰く，DCT行列をを-1,0,1から構成される行列と係数行列に分解するとのこと．つまり，係数行列要素の乗算を減らし，加算に変形するのであろう．
因数分解という単語も出てきているが，先に挙げた単なる乗算をシフトと加算に変形しただけの可能性もある．今回は具体的な数値が明記されていないので，検証しようがない．2x2行列を2x2行列と2x2行列の積に分解しているのだが，多分ここが肝であり，特許に記さないノウハウといったところか．ただ，一連の流れからすると，分解前後の3値化2進数における有効ビット（-1か1）の個数が最小になるように分解すればシフト，加算回数が削減可能であると思われる．
今までDCT演算のみに着目してきた．しかし，実際には四捨五入や固定小数点の変換など，表出しない演算については未検討であった．乗算をシフト，加算に還元すると言うことは，四捨五入などを含めてトータルで演算回数を削減する方向に最適化しなければならない．こうなると，技術者にはお手上げである．注意深く設計していけば出来ないことはないが，数学者の理路整然とした分析の前には項垂れるしかない，気がする．
DCT演算は誤差を伴うため，演算精度について取り決めがある（IEEE-1180）．これを満たしつつ，要求に応じて入力信号のビット精度が8ビットから12ビットまで変化すると，なにがなんだかわからなくなる．固定小数点の実装は意外と難しい．数式で表現するとなると，私の持っている理論では追いつかない可能性大．
まとめ
そんなわけで，DMNAってやっぱスゲーのかも，ということになる．個人的には，四捨五入と固定小数点の調整が意外と無視できないコストであること，3値化2進数を久しぶりに見たこと，乗算の分解って意外と効くかもな，という点が興味深かった．実は，DMNAはDCT演算だけでなく，動き検出もあるらしい．動き検出はCODECメーカのノウハウの固まりなので，基本的にお手上げである．実際に使われている技術は数が知れているので，どれだか特定できそうな断片情報があればいいのだが．
*1:Z. Wang, "Fast Algorithms for the Discrete W Transform and for the Discrete Fourier Transform," IEEE Trans. on A.S.S.P., Vol.32 No.4 1984.
*2:Loeffler C., Ligtenberg A., and Moschytz C.S., "Practical Fast 1D DCT Algorithm with Eleven Multiplications," Proc. ICASSP 1989, 988-991.
*3:Arai Y., Agui T., Nakajima M., "A fast DCT-SQ Scheme for Images," Trans IEICE #71 (1988), 1095-1097.
