[HOME][発明]

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

平面を4分割するのに、2分割を3度行うのと、4分割を1度行うのでは、前者の方がフレキシブルです。そんなことは自明だと思うのですが、世の中には、無意味なディザー同様、無意味な4分木もいっぱいあります。AICの観点からなら、パラメーターの数が1つ増えるので、より尤もらしさが増えるのは当たり前ということもできます。圧縮が難しいデータであれば、どの様なデータ構造をとっても大差ありませんが、画像はそうではありません。悪いデータ構造を選ぶと実用的なサイズの問題が扱えないトーイプログラムができあがります。

矩形領域に分割して、平板な部分の情報量を圧縮するアルゴリズム

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

宇佐見さんのTSPプログラム

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

ImageMagick

ImageMagickについては以前に書きました。時間をかけて8bit精度で処理しても5bit並みの画質に落ち込んでいます。

郵政省通信総合研究所と日本IBMの共同研究

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

安西祐一郎氏の「認識と学習」(岩波講座 ソフトウェア科学)

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

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

 

発明ディレクトリ

Google
Web www.PAG1U.net

関連ディレクトリ

画質

計画

ダウンロード

通信

関連サイト

乱雑な本棚:計算幾何学

乱雑な本棚:画像圧縮

乱雑な本棚:発明

乱雑な本棚:最適化

 
 
 
 
 
seo

ホーム 発明 掲示板 (C)松岡肇、メール