四分木

って何、と知人つうかHIDさんに聞かれたので、ちょっと書いてみる。
基本的な考えは、http://chiyo.sfc.keio.ac.jp/cgsoft/Release/Textbook/expression08.html

図形が含まれている領域は、ブロックの大きさを変えるとこんな風になる。

(A1)　(A2)　　　(A3)

□■　□□■■　□□□□□■■■

■■　□□■□　□□□□■■■□

　　　■■■□　□□□□■■□□

　　　□■□□　□□□□■□□□

　　　　　　　　□□■■■□□□

　　　　　　　　■■■■■■□□

　　　　　　　　□□■□□□□□

　　　　　　　　□□■■□□□□

ブロックのうち"□"ではそれ以上細かく分割する必要はないけど、"■"ではさらに細かく分割する必要がある。
これが基本の考え方。小脳の記憶モデルもこんな感じだったりする。

で、上の３つの絵（ブロック）を見ると、左側が右側をちょうど縮小した絵になっているのがわかる。
真ん中の絵(A2)を２倍に拡大したものを右の絵(A3)を比べると、

(A2')　　　　　　　　　　(D3)

□□□□■■■■　　　　□□□□■□□□

□□□□■■■■　　　　□□□□□□□■

□□□□■■□□　　　　□□□□□□□□

□□□□■■□□　から　□□□□□■□□　を引けば、右側の絵(A3)ができる。

■■■■■■□□　　　　■■□□□■□□

■■■■■■□□　　　　□□□□□□□□

□□■■□□□□　　　　□□□■□□□□

□□■■□□□□　　　　□□□□□□□□

ということで、絵の(A2)と(D3)を用いて(A3)を表現するってのが符号化の一方法にある。JPEG2000なんかにも使われている。

さらに。
(A2)と(A3)が似ているということは、(A3)と(A2)との差の情報と、元の絵と(A3)との差の情報も似ているだろうと考えられる。で、それぞれの差の情報を効率的に符号化するときに四分木の考え方が使われたりする。

また、(A3)と(A2)との差の情報から類推して元の絵と(A3)との差の情報に近いものを作り出すことも考えられる。画像では主流ではないけど、音声ではSpectrum Band Replicationといって着うたなんかに使われている技術だったりする。