http://japan.cnet.com/news/tech/story/0,2000056025,20122887,00.htmやhttp://dc.watch.impress.co.jp/cda/other/2006/05/29/3879.htmlにあるように、マイクロソフトが独自画像圧縮フォーマットを発表した。アルゴリズムの詳細については開発者にのみ配布されている模様。取り寄せるのはしんどそうなので、http://www.eetimes.jp/contents/200605/8393_1_20060525201417.cfmのインタビューからその詳細を追ってみたいと思う。

この画像フォーマットは、完全な独自フォーマットで、画質はJPEG2000を上回るそうだ。では、その性能の秘密は何か。インタビューでは

>WMPの圧縮方式は、JPEGと同じく、離散コサイン変換方式を基本としているが、アプローチはまったく異なるという。Crow氏の説明によると、WMPで採用したアルゴリズムは重複双直交変換(lapped biorthogonal transform)であり、これは同社の研究部門であるMicrosoft Researchにおける独自研究の成果に基づく。また、WMPには色空間や色変換などに関する新たな機能が含まれている。

と述べられている。”重複双直交変換”?これは何か。

それを考えるには、一般の画像圧縮の仕組みである変換符号化について知る必要がある。変換符号化とは、DCT等の周波数変換によって画像を周波数成分に変換し、処理する方式である。画像のRGBデータは例えば
 10,125,200,100,10,60,10
のようになっているが、量子化して
 0,6,10,5,0,3,0
としても、保存しないといけないデータの数は変わらない。
しかし
 10,125,200,100,10,60,10
を周波数変換すれば、
 125,50,20,5,5,3,2
のように後方に小さい値が集中するので、量子化して
 6,3,1,0,0,0,0
とすれば、
 6,3,1,EOB
とする事で、データ量を削減できる。

このように、変換符号化による画像圧縮においては、周波数変換によって後方に小さい成分を持つ単調減少な数列を生成し、量子化、終端シンボルで後方の0を排除することで、情報量を減らしているのである。

しかし周波数変換は重い。そのため、できるだけ小さい処理単位にしなければならない。JPEGの場合8*8画素で1ブロックとしているが、ここで問題となるのがブロックノイズである。量子化して高周波情報を0にしたことで、特に高圧縮の領域で、ブロック間のつぎめが見えてしまうのである。

この解決方法としてJPEG2000が採用したのがウェーブレット変換である。画像を直流成分(縮小画像)とその差分に分解して処理することで、仕組み的に、ブロックノイズが生じにくくなっている。しかし、ウェーブレット変換は、実用的な精度を実現するために浮動少数点演算が必須である。そのため、ハードウェア化のコストは大きい。

このようなブロックノイズの問題は、音響信号圧縮ではさらに顕著である。耳は目よりも低レベルであり、周期的な高周波ノイズ(ぷち、ぷち)というのを極めて敏感に拾ってしまうのである。この対策として、mp3やaac、OggVorbisでは重複直交変換というものを使っている。これは、ブロックをオーバラップさせて周波数変換する事で、ブロック間をなめらかにつなぎ、ブロックノイズを生じさせない。具体的に、
 ABCD
とデータがあれば、AB、BC、CDという単位で周波数変換を行う。当然、オーバラップさせれば、その分周波数成分の数が多くなり、データ量が増えてしまう。つまり、圧縮にならない。これを解決するために考えられたのが、MDCTで、N個のデータからN/2個の周波数成分を作る変換である。こうすれば、データ量は信号データと変わらず、逆変換したものを単純加算する事で、元のデータに完全に復元できるのである。

さて、ではマイクロソフトのいう”重複双直交変換”とは何か。これは、音響信号圧縮における”重複直交変換”を画像に拡張し、2次元にしたものであろう。具体的に、画像を重複させながらブロック分割し、処理しているはずだ。”双直交”とは、代数学の用語で、ある基底系に別の基底系を持ってくることで、結果的に直交させることであるので、MDCTのように、変換自体の基底は直交していないが、オーバラップして足し合わせる事で直交する、という事であるのだろう。そうでなければオーバラップした分情報量が増加してしまうので、無難な選択と言えよう。このようにブロックを重複させる事で、ブロックノイズをキャンセルし、さらに、このような重複直交変換MLT(Modified Lapped Transform)は、SNRの面でもDCTよりも優秀であることが実験で証明されていため、性能においてもJPEG2000を超える事ができているものだと考えられる。また、基本はブロック処理であるため、ハード化もしやすく、マイクロソフトはいいところに目をつけてきたと思う。

ところで、マイクロソフトは独自開発としているが、このような変換は既に1992年の時点でMrvarによって提案されている。

Signal Processing with Lapped Transform


を参照のこと。

ただ気になるのは、サムネイルをサポートしている点。MLTとサムネイルは相性が悪いのだが、どうやっているのだろうか。階層的にMLTをやるのは現実的では無い気がするが・・・もしかしたら、ウェーブレット変換をして、DC成分とAC成分をそれぞれMLTで処理している、という事かもしれない。

こうなってくると、WMVやWMAの中身も気になるところ。ベクトル量子化とかしてる気がするな、なんとなく。知ってる人教えて下さい。

今回の事で分かったのは、マイクロソフト、グーグル、NTTの研究開発力はあなどれないという事。ソニーもこれぐらいアグレッシブに国産独自コーデックをブルーレイに入れてくれると、特許料をアメリカに払わなくてよく、国力となっていいのだが。

---------------------------------------------------------
2008/3/2追記

どうやらMDCT等の重複直交変換とは違って、
マクロブロック間をオーバラップしての処理ブロック構成は、
しないみたいですね。
4.2.2.3 Overlap
This parameter selects the optional overlap processing level:
0 No overlap processing is enabled.
1 One level of overlap processing is enabled, modifying 4x4 block encoded values based on values of neighboring blocks.
2 Two levels of overlap processing are enabled; in addition to the first level processing, encoded values of 16x16 macro blocks are modified based on the values of neighboring macro blocks.
The default value is 1.
とあるので、H.264のような近傍ブロックからの予測を、
オーバラップと言っているだけみたいです。

さらに双直交変換ですが、これも単に特許回避の側面が強いようです。

具体的に説明すると、直交変換の場合、
その中で直交する基底で構成されており、
逆変換はその転置となります。

例えば二次元の正規直交基底
 v1、v2
があったときに、それぞれの基底は直交しているので
 (v1,v1)=1 (v1,v2)=0 (v2,v2)=1
となり、順変換は[v1^t v2^t]、逆変換は[v1 v2]になります。
逆変換は順変換の転置となっています。

双直交な基底は、直交していない基底をもってきて、
もう1セット追加で持ってきた基底と直交させるものです。
(基底は線系独立なベクトルであれば構成できます。)

つまり、非直交な基底
 u1、u2
と、別の基底
 w1、w2

 (u1,w1)=1 (u1,w2)=0 (u2,w2)=1
という性質を満たします。

直交基底と違い
 (u1,u2)!=0
でもいいのが特徴です。
従って順変換は[u1^t u2^t]、逆変換は[v1 v2]。
逆変換は順変換の転置ではなく逆行列になっています。

つまり、従来のDCT等は順変換、逆変換で同じ基底を用いていました。
しかし、それだと基底の要素が小数となり、
固定小数で実装すると完全再構成できないという問題がありました。

これに対してH.264では整数型変換を用いて対処しました。
ただし依然として逆変換は順変換の転置です。

その結果、世の中の特許はほとんど直交変換を前提としています。
そこでMicrosoftが放った一手が双直交変換で、
わざと少し直交性を崩し、順変換と逆変換の行列を変えることで、
世の中の特許のほとんどを回避しようというものです。

従って、双直交変換の採用は、
純粋に圧縮率や見た目を向上させるものではなく、
かなりテクニカルな選択だと言えるかと思います。