バケット法の場合の計算量

バケット法については、実際にプログラムしていないのですが、ちょっと説明が面倒です。バケットの数が変化することで、バケットの走査にかかる時間と、リンクを辿る時間が変化します。

そこで、まず、極端な場合を考えます。

	バケットだけがある場合。つまりこれは、バケットの階調が、ヒストグラムの階調に等しい場合で、配列と同じです。H^3*log(C)でしょう。
	リンクだけがある場合 F*Cに比例する時間かかります。以上２つを組み合わせてどれだけ良くなるでしょうか？

バケットとリンクがある場合

	まず、データがランダムに分布している場合バケットの階調Bとすると、総バケット数は、B^3、色空間を順次分割する過程で、平均的に走査するバケット数は、xを1からCまで変化させたときのsum((B+x^(1/3)-1)^3)で、(1.83B+C^(1/3)-4)^3程度。次に、リンクを辿る平均回数は、色がランダムに分布していると仮定しているので、先ほどの値(1.83B+C^(1/3)-4)^3に、F/B^3を掛ければよい。バケットを辿るのとリンクを辿るのに差がないとして、合計(1.83B+C^(1/3)-4)^3(1+F/B^3)を最小にするＢを求めるとF*log(C)に比例していることになります。
	データが極端に偏っている場合走査するバケット数は変化しません。１つのバケット内に全データが集まっていると、分割のたびに全データを走査することになりF*Cの手間がかかります。
	実際の場合には、Flog(C)と、FCの中間ということになるでしょう。

扱う次元が高くなると、

これで十分そうに見えるのですが、それは扱う次元が一定の場合に定数倍の項として隠れているだけで、実は、2^Dに比例して分割時の無駄なスキャンが増えてしまいます。さらに、ボロノイ分割を行う時には、無駄の範囲が広がるので、3^Dから4^D倍程度遅くなるはずです。でも数百倍遅くなるはずと言っていたのはやや大げさで１００倍程度でしょうか。

減色ではなく、TSPの場合は、CがFと同じになりますから、かなり効いてきます。

C:減色の色数

H:ヒストグラムの階調

S:画像サイズ

F:元画像での異なる色の数

D:扱う空間の次元

B:バケットの階調

以上の考察を応用して、実行速度の変化からアルゴリズムを逆に推定することもできます。

色見本の様な均等なデータを作って減色した場合と、デジタル８色を１ドットごと、残りのドットには、(0,0,0)-(5,5,5)までの限られた色をランダムに配置した画像を減色した場合にかかる時間を比較することでバケット数の推定などができると思います。

中央値分割

発明ディレクトリ