ヘックバートの中央値分割のアルゴリズム

ヘックバートの中央値分割　

減色で使っているアルゴリズムはすべて自分で思いついたつもりだったのですが、それよりずっと昔に、Paul S. Heckbertという人が作っていました。一時期はそれでやる気を無くしていました。異なっている部分もあるのですが。異なっている部分の一部は、、大津の方法で、それも僕よりずっと前でした。さらにその残りの部分だけが僕独自であるわけです。

(ヘックバートの論文へのリンクを福島隆行さんのページ (http://amethyst.ie.akita-u.ac.jp/~fukusima/genshoku.html)で見つけました。査読したのは、メディアラボのネグロポンティ( WIREDに連載している人 )みたいです。ヘックバートは中央値分割だけではなく、誤差を最小にする点で分割するという提案もしていました。インプリメントはしていないとなっています。

大津の方法

大津の方法についても、平均での分割にこだわるのをやめた頃に独自に思いついたのですが、これも後で、遅かったことがわかりました。

また、すでにヘックバートが1980年に誤差を最小にする点で分割するという提案もしていました。

勘違いしていてしばらく、間違ったことを書いていたのですが、大津の方法の方がヘックバートよりも前1978でした。

pag1当時のアルゴリズムの新しさ

最初の頃に最初に僕が思いついたのは、中央値ではなく平均を分割点にして分割する方法でした。中央値＜平均＜大津の方法の順に画質はよくなります。しかし、そのための計算量は、n^2,n*logn,n^2です。まあ、中央値と比べれば画質も良いし、処理も軽いわけですが、オリジナルではなく亜種だったのでがっかりしました。

TSPプログラムに適用した場合に、大津の方法をn回用いれば、n^2(これも大雑把でn^1.66とかだと思いますが)に比例してしまうので、速度を上げるために精度を犠牲にして、平均を使う方法に戻したりしています。

1998/7/14のさきがけ２１のヒアリングの時に、説明のための時間がないと思って大雑把な比喩的な話をしていて、n*log(n)と言っていたのですが、それは、大津の方法ではなく、平均を使った場合のものでした。減色の場合には、256までしか分割しないので、n^2の項があっても問題なくて、大津の方法を用いています。それどころか、主成分での分割とかも(効果はともかく)大した時間のロスにはなりません。それにバケット法との比較を喋るチャンスもあったのですが、その時には、きちんと計算してみていませんでした。

pag1tetoのアルゴリズムの新しさ

多次元を順次分割していくアルゴリズムでのデータ構造が他と異なっています。以下少し比較検討します。配列とバケット法の２つが主に使われ、３つめは超遅そうなデータ構造です。

多次元配列で持つ

配列だと、配列をH^3*log(C)回スキャンすることになります。画質を上げると時間がかかるアルゴリズムです。4bitくらいであれば、配列の方が軽いのですが。ただし、

	C:減色の色数
	H:ヒストグラムの階調

バケット法

多次元空間のクラスタリングにバケット法を用いた場合の計算量の検討をやや訂正してページを改めました。均等分布でF*log(C)*2^D、偏った場合で最悪F*C*2^Dでしょう。

	ピクセル毎の分類番号を持つピクセル毎の分類番号では、S*Cに比例します。画像によりますが、多分、Sは、F^4程度に比例します。こんなアルゴリズムを書く人はいないと思うかも知れませんが、L+u+v+を勧めていたNECの人の論文ではこういう実装が説明してありました。
	netpbmの場合

かなり近いのですが、意味なくqsortを使っているので、遅くなっています。指摘されるまでソースを読んでいなかったので、またしても、独自の部分が減ってしまいました。

関連ページ

OPTPixを推す匿名ページ

pag1teto

pag1teto以降(正確には、256色環境で複数の256色画像を表示するソフトのVBで作ったプロトタイプ256test以降)で使われているアルゴリズムについては出願済みなので、明細を読んでください。min(F,S)*log(C)*D程度です。

発明ディレクトリ