4分木、8分木アルゴリズムの問題点

具体的な名前は思い出せないのですが、曲面を三角形パッチで近似する話をしているときにこういうこと？　という感じでconsさん(B-NET時代の知り合い。最近は知らない。)が送ってくれた論文に出てきたアルゴリズムです。顔の画像の話をしていて、その論文も例として顔だったけれど、アルゴリズムとしては全然関係ない話だったので、なぜだかわかりません。

２次元のユークリッド空間でのＴＳＰで、平面を再帰的に４分割するアルゴリズムでした。しかし、その解は、画面中央を縦横に走る補助線が見えてしまうような、アルゴリズムの問題点が透けてというか、丸見えになるようなものでした。しかし、その後、彼は、科学技術振興事業団のさきがけ２１に通っているのでした。

以前僕がMMCAに出した企画書と同じ様なことを目指しているみたいなのですが、平面を4分木で、微小領域にいったん分割した後に、再度結合していくアルゴリズムでした。こんなことをやっては、１０００倍か１００００倍は時間がかかります。さらに、再結合(領域拡張)の時に不要なブロックノイズがでています。

僕は落ちたのですが、科学技術振興事業団の「さきがけ２１」の審査委員長だったので、ヒアリングは終わってしまっていたけれど、本屋で見かけて本を買いました。そうしたら、この本の135pageにも、４進木(quad-tree representation)が出てきました。単にデータ構造の１つとして紹介しているだけですが、僕ならこんなデータ構造は反面教師としてしか紹介しません。最初から効率など眼中にない審査員だと知っていれば、プレゼンの仕方も変えていたでしょう。

４分木のデータ構造の効率の悪さを、256*256の大きさの画像で中心の2*2ドットだけ値が１で、残りが０の2値画像という極端な例で、２分木と比較してみます。４分木のアルゴリズムでは、29個の４分木(４進木)が必要になります。他方は、2つから4つの２分木ですみます。まず、４分木ですが、このサイズの時、リンクは最大で、128*128*４/3ですから、15bitさらに、リンクか値かのフラグが１bit、値であれば1bit。この場合には、４分木１つあたり22bit。最下位はリンクがないので、合計623bit必要です。他方、二分木の場合、リンクの数は最大で256*256-1ですからリンクを表現するのに必要なbit数は1bit増えて16bit。値かリンクかのフラグが1bit。値の場合が1bit。そして、分割軸に1bit。分割位置に8bit必要になります。この場合には、合計94bitです。極端な例でも高々数倍と感じる人がいるかもしれませんが、圧縮率で倍違う様なアルゴリズムの差は速度で言えば何桁もの差に相当する別の世界です。