手抜きで時間を短縮、k平均法を使った減色パレットの作成

k平均法を使った減色パレットの作成時に手抜きをして処理時間短縮

手を抜くのは重要

どこまで手を抜いても気づかないかを確かめてみるアプリ作った、確かみてみろ！

手抜きの方法は簡単で調査するピクセル数に上限を付けるだけ

上の場合だと

手抜きパレットは画像のピクセル49152個の内、1000個をランダムに選択したピクセルだけを使ってパレットを作成する

真面目パレットは常にすべてのピクセルを使ってパレットを作成する

それぞれの時間は

0秒570 真面目パレット

0秒014 手抜きパレット

大きく違うけど1秒以下ならどっちでもいいかなあ

こういう小さい画像なら真面目パレットでもいいと思う

できたパレットの色はほとんど一緒

それぞれのパレットで減色

ほとんどさがない

もともとk平均法はランダムの要素があるから

真面目に作ってもこれくらいの揺れはあると思う

これを100ピクセルまで手抜き

100ピクセルまで落とすと赤が入らないことが多くなった

真面目パレットでも最初の1回目は赤を外しているけど

手抜きパレットは要らない青系が入っているよりマシ

その分時間は0.003と速いけど体感できないからなあ

ってことで手を抜いても1000ピクセルは使ったほうがいい

大きめの画像

1024ｘ768ピクセルは合計786,432ピクセル

さっきと同じ設定で3回計測

8.896秒と0.013秒 = 8.896/0.013≒684、最大で約700倍の差がついた

パレットのできは比べれば真面目パレットのほうがいいねえ、くらいかな

f:id:gogowaten:20191212114155p:plain

偶然かもしれないけど手抜きパレットのほうがいいと思う

パレットの色数を8色増やしてみる

20.570秒と0.023秒＝ 20.570/0.023≒894、最大約900倍

更に差が開いた

パレットを比べても3色のときと同様、そんなに差はないかなあ

k平均法だと毎回変わるからねえ

f:id:gogowaten:20191212114227p:plain

実際減色してみても大差ない

これで20秒かかるのと一瞬で終わるなら手を抜かない手はない

遊びを大きくしてみる

3から20に変更

遊びを3から20に変更

ループ回数が減るので速くなる

遊び100

ループ1回で終わっているのもあるので速いけど

さすがに1回じゃ少なすぎるｗ

時間やパレットの出来具合から

手を抜くなら遊びを大きくするよりピクセルを絞ったほうが良さそう

大きい画像

f:id:gogowaten:20191212114831j:plain

2048ｘ1356ピクセルは3,145,728ピクセル

314万ピクセル

今ではこれくらいでも大きいとは言わないかな？

遊びを3に戻して計測

f:id:gogowaten:20191212114857p:plain

時間かかりすぎてこのウィンドウが出てきた

続行を押して再開

結果

真面目パレットは2分近くもかかった

1分54秒368と0.052秒＝(1*60+54.368)/0.052≒2199

約2200倍

ピクセル数比だと

3145728/1000≒3146

こんな感じで

結果のパレットのできは変わんないねえ

花粉やミツバチの黄色がないのが残念

それぞれのパレットで減色

f:id:gogowaten:20191212114914p:plain

3840ｘ1160の画像

やっぱりどちらも変わんない

手抜きで十分

k平均法のランダム性を生かして

気に入ったパレットができるまでリセマラ

f:id:gogowaten:20191212114932p:plain

手抜きパレットなら一瞬でできるからラク

ここまで速いと今度は減色処理の時間が気になってくる

この大きさだと13秒もかかっている

k平均法で減色パレットを作成するとき

画像のすべてのピクセルからではなく、ランダムに選んだ1000個のピクセルからでも十分なものができる

処理時間はピクセル数に比例するので大きな画像ほど差が出る、2048ｘ1356程度の画像の大きさになると差が2000倍にもなる

手抜きバンザイ

/// <summary>
/// k平均法で画像からパレット作成、ループ上限は100回
/// </summary>
/// <param name="source">PixelFormat.Pbgr32限定</param>
/// <param name="colorCount">パレットの色数</param>
/// <param name="limitPixel">走査するピクセル数の上限、1000あれば十分、画像のピクセル数＜上限のときは全ピクセルを走査</param>
/// <param name="margin">パレット完成とする新旧パレットの色差、5～20がいい、小さいほど時間かかる</param>
/// <param name="textBlock">ループ回数を表示するTextBlockを指定</param>
/// <returns></returns>
private Color[] GetPalette(BitmapSource source, int colorCount, int limitPixel, int margin, TextBlock textBlock)
{
    Color[] pixelColors;
    if (limitPixel == 0)
    {
        pixelColors = GetAllPixelsColor(source);//画像の全ピクセルのColor取得
    }
    else
    {
        pixelColors = GetRandomPixelsColor(source, limitPixel);//制限数ピクセル取得
    }

    //初期パレット作成
    Color[] oldPalette = GetRandomColorPalette(colorCount);//旧パレット
    Color[] nextPalette = new Color[colorCount];//新パレット
    //2つのパレットの色の差が指定値以下、またはループ回数が100になったらパレット完成
    int loopCount = 0;
    while (loopCount < 100)
    {
        loopCount++;
        nextPalette = GetNewPalette(oldPalette, pixelColors);//新パレットに色振り分け
        if (GetDiffPalettes(oldPalette, nextPalette) < margin) { break; }//色差が指定値以下になったら完成
        //旧パレットに新パレットの色を入れる
        for (int i = 0; i < oldPalette.Length; ++i)
        {
            oldPalette[i] = nextPalette[i];
        }
    }

    if (textBlock != null)
    {
        textBlock.Text = $"ループ回数：{loopCount}";
    }

    return nextPalette;
}

//2つのパレットの色の差を取得
private double GetDiffPalettes(Color[] bPalette, Color[] nPalette)
{
    double diff = 0;
    for (int i = 0; i < bPalette.Length; ++i)
    {
        diff += GetColorDistance(bPalette[i], nPalette[i]);
    }
    diff /= bPalette.Length;
    return diff;
}

//分けた色の平均色を新しいパレットの色にする
private Color[] GetNewPalette(Color[] palette, Color[] pixelColors)
{
    //振り分け先の入れ物をパレットの色数分作成
    List<Color>[] colorList = new List<Color>[palette.Length];
    for (int i = 0; i < palette.Length; ++i)
    {
        colorList[i] = new List<Color>();
    }
    //画像の色と比較、近い色のパレットのインデックスのListに追加していく
    double distance, min;
    int pIndex;//palette index
    Color nowColor;
    for (int i = 0; i < pixelColors.Length; i++)
    {
        nowColor = pixelColors[i];
        pIndex = 0;
        min = GetColorDistance(nowColor, palette[0]);//2色間の距離
        for (int j = 1; j < palette.Length; j++)
        {
            distance = GetColorDistance(nowColor, palette[j]);//2色間の距離
            if (min > distance)
            {
                min = distance;
                pIndex = j;
            }
        }
        colorList[pIndex].Add(nowColor);//Listに追加
    }
    Color[] newPalette = new Color[palette.Length];

    for (int i = 0; i < newPalette.Length; i++)
    {
        newPalette[i] = GetAverageGolor(colorList[i]);
    }
    return newPalette;
}


//初期パレット作成、ランダム色のパレット
private Color[] GetRandomColorPalette(int paletteCapacity)
{
    Color[] colors = new Color[paletteCapacity];
    Random random = new Random();
    byte[] r = new byte[3];
    for (int i = 0; i < colors.Length; ++i)
    {
        random.NextBytes(r);
        colors[i] = Color.FromRgb(r[0], r[1], r[2]);
        Console.WriteLine(colors[i].ToString());
    }
    return colors;
}

//画像の全ピクセルの色をColorの配列にして返す
private Color[] GetAllPixelsColor(BitmapSource source)
{
    var wb = new WriteableBitmap(source);
    int h = wb.PixelHeight;
    int w = wb.PixelWidth;
    int stride = wb.BackBufferStride;
    byte[] pixels = new byte[h * stride];
    wb.CopyPixels(pixels, stride, 0);
    int p = 0;
    Color[] color = new Color[h * w];
    for (int i = 0; i < color.Length; ++i)
    {
        p = i * 4;
        color[i] = Color.FromRgb(pixels[p + 2], pixels[p + 1], pixels[p]);
    }
    return color;
}

//ピクセル数が指定数以下のときは全ピクセルカラーを取得
private Color[] GetRandomPixelsColor(BitmapSource source, int limit)
{
    var wb = new WriteableBitmap(source);
    int h = wb.PixelHeight;
    int w = wb.PixelWidth;
    int stride = wb.BackBufferStride;
    byte[] pixels = new byte[h * stride];
    wb.CopyPixels(pixels, stride, 0);

    if (limit > w * h)
    {
        return GetAllPixelsColor(source);
    }

    Color[] color = new Color[limit];
    Random random = new Random();
    int p = 0;
    int x, y;
    for (int i = 0; i < limit; ++i)
    {
        x = random.Next(w);
        y = random.Next(h);
        p = y * stride + (x * 4);
        color[i] = Color.FromRgb(pixels[p + 2], pixels[p + 1], pixels[p]);
    }
    return color;
}