無駄に時間をかける減色法。プログラミングが得意な人が作ったらどんな感じになるんだろう。

日記

俺HSPしか使えない。他のを勉強する根気も無い。
実際HSPで作ったやつを動かすと、1つの画像を減色するのに、パソコンでぶっ通しで数日かかる。アホすぎる。

●無駄に時間をかける減色法
　●どこらへんが無駄なのか
　　●誤差拡散法を使わない場合、もっと効率良いアルゴリズムがある。
　　●誤差拡散法を使う場合、たしかに時間をかければ既存のソフトより画質は上がる。
　　●しかし、色数ケチって誤差拡散法を使うより、使わずに色数増やした方が圧縮が効きやすい。
　　●そもそも減色すること自体が時代遅れ。
　　●綺麗に減色できさえすれば実用性なんて要らないマニアックな用途向け。
　●誤差拡散法で画質が上がるのはなぜ？
　　●そもそも既存の減色ソフトはパレットの作成にメディアンカットとか使ってるけど
　　●メディアンカットとかは誤差拡散法を考慮してない。
　　●こっちは考慮してる。無駄に時間をかけて。

●あらすじ。
　●画像を読み込みます。
　●ランダムなパレットをいくつか用意します。
　●そのパレットを使って画像を減色します。
　●減色した画像の画質を評価します。
　●パレットを個体、画質評価を適応度にして、遺伝的アルゴリズムで進化させます。
　●出来上がり。

●実際にHSPで作ったもの
　●設定入力
　　●パレット作成の方法（ランダムorピックアップ）
　　●減色する色数
　　●誤差拡散の有無
　　●インチキの有無
　　●評価に使うアルゴリズム
　　●分散遺伝的アルゴリズムで使う島数
　　●分散遺伝的アルゴリズムで使う一島あたりの個体数
　●画像の読み込み
　●パレット作成
　　●減色する色数のパレットを、設定された個体数ぶん作る。
　　●パレットは二進数で作る
　　　●ランダムの場合、ランダムにする。
　　　●ピックアップの場合、ランダムに画像の座標を選んでその色を入力。
　　●パレットをバイナリコードからグレイコードに変換する。
　●始めに作成したパレットの画質を評価する。
　　●作成したパレットで減色し、その画像の画質を評価する。
　　　●減色アルゴリズムは後述
　　　●画質評価アルゴリズムは後述
　●遺伝的アルゴリズムを動かす。
　　●交叉をする。
　　　●出力用にパレットを新しく作る。
　　　●交叉に使う個体を選ぶ。
　　　　●分散なので、島の中から二つを選ぶ。
　　　　　●一つ選ぶごとにランダムに二つの個体を調べて、評価値が高い方を選ぶ
　　　●選んだ二つの個体を交叉させる
　　　　●各桁ごとに二つのどちらかランダム選んで交叉用パレットに出力する。
　　　　●交叉に使う二つの個体が１０１０と、００１１の二つの場合、
　　　　●１０１０、００１０、１０１１、００１１の４パターンのどれかになる。
　　●突然変異する。
　　　●パレットのどこか一桁を反転させる。
　　　●交叉でできた個体が００１０の場合
　　　●１０１０、０１１０、００００、００１１の４パターンのどれかになる。
　　●ここで作ったパレットで減色し、画質評価をする。
　　　●減色アルゴリズムは後述
　　　●画質評価アルゴリズムは後述
　　●個体入れ替えを行う
　　　●個体入れ替え対象の個体を一つ選ぶ
　　　　●分散なので、島の中から一つを選ぶ。
　　　　　●一つ選ぶごとにランダムに二つの個体を調べて、評価値が低い方を選ぶ
　　　●交叉で作った個体が、入れ替え対象の個体より評価置がたかければ、
　　　●入れ替え対象の個体のパレットを消して、交叉で作った個体のパレットを入力。
　　●ここまでを、それぞれの島で１回ずつ行う。
　　●全部の島で１回ずつ行ったら、移住を行う。
　　　●移住は、すべての島を対象にランダムに二つ個体を選んで、個体を入れ替える。
　　●ここまでを何回も繰り返す。
　　●繰り返すうちに、評価値が低い個体は、評価値が高い個体に上書きされて消えていく。
　●減色アルゴリズム
　　●誤差拡散がない場合、単純に各ピクセルについて、パレットの中から
　　●もっとも色差が少ない色を選ぶだけ。
　　　●色差のアルゴリズムは後述
　　●ただし、お好みでインチキを使う。
　　　●インチキについては後述
　　●誤差拡散がある場合、色差をRGBのユークリッド距離で判定し、
　　●生じた誤差を周りのピクセルに拡散させる。
　　　●やりかたは「Floyd-Steinberg 法」とかで。
　●画質評価アルゴリズム
　　●誤差拡散がない場合、単純に元画像と減色後画像の、各ピクセルの色差の
　　●二乗誤差を求めるだけ。
　　　●色差のアルゴリズムは後述
　　●誤差拡散がある場合、各ピクセルの色に
　　●周囲８ピクセル位の色も適当に重みを付けて加えて色差を算出する。
　●色差のアルゴリズム。
　　●好みに応じていろいろ作っておく。
　　●作ったもの。
　　　●RGBのユークリッド距離。
　　　　●誤差拡散法で使う用。
　　　　●二つの画像の、各ピクセルのRGBそれぞれの差を二乗して、その合計の平方根。
　　　　●ここでのRGBはリニアRGBなので、画像のRGBはそのまま使わず
　　　　●ガンマ補正を行いましょう。RGBそれぞれを1.8乗か2.2乗します。
　　　●重み付けRGBのユークリッド距離。
　　　　●RGBそれぞれに、見えやすさに合わせてお好みのおもみつけをします。
　　　　●俺はR*139,G*255,B*81くらいにした。
　　　　●これは画像のRGBリニアRGBにして、その後重み付け
　　　●CIE94
　　　　●画像のRGBをリニアRGBに変換
　　　　●リニアRGBをXYZ表色系に変換
　　　　●XYZ表色系をL*a*b*表色系に変換
　　　　●そこからCIE94色差式で算出。
　　●作ってないもの
　　　●L*u*v*
　　　　●なんでこれ作ってないんだろう。
　　　●CIEDE2000
　　　　●計算式が複雑すぎて諦めた。
　●インチキ
　　●誤差拡散法を使わなないときに使う。
　　●パレットの各色について、減色時にそのパレットの色と置き換えたピクセルの
　　●色の平均を算出して、減色終了後パレットの色をその色に変更して
　　●減色をやり直す。
　　　●明度が100、110、110のピクセルを明度が110のパレットの色で置き換えたとき、
　　　●パレットの色を、平均の107に変更する。
　　　●すべての色でこれをやって出来た新しいパレットで減色しなおす。
  　●K-meansもどき？