分割する場所の選択、メディアンカットで減色パレット作成

続き

ダウンロード先

github.com

Cubeをどこで分割するのかを4種類試した

辺中央 CubeのRGB3辺の中で一番長い辺を選択、辺の中央で分割

中央値一番長い辺を選ぶのは↑と同じ、辺の要素の中央値で分割

最小分散p 分散値が最大の辺を選択、分割後の2辺の分散が最小になる場所で分割

最小分散c ↑と違うのは全てのピクセルではなくすべての色で分散値最大の辺を求める、こっちのほうが処理数は少ない

Cubeからの色の選択方法は平均色で固定

分割するCubeの選択は最長辺を持つものを基本にして、他にいくつか試してみる

256ｘ192

16色

中央値分割は似た色が多いピクセルが優先されるみたいで青系の色が多い

逆に中央分割は青空に4色しか割り振られていない

分散の2つはその中間みたいな感じになった

分割するCubeの選択方法増えた

下の2つを加えた

Cubeの中心からの距離の平均が最大のものを選ぶ

これもどれだけ色が散らばっているか、になると思う

距離の測り方は単純なユークリッド距離になるのかな

Cubeの中心の色と対象になる色のRGBそれぞれの差の2乗の合計の平方根

これを全てのピクセルか全ての色で測った平均

これを使って16色

中央と中央値は余り変化がないけど

分散は青空の色が極端に減ったのが面白い

最大分散値の辺を持つCubeを分割

中央分割は赤が1色もないパレットになったｗ

分散で選んだCubeは分散で分割するのが良さそうね

分散の2つは全く同じ結果

グラデーション少ない込み入っている画像

192ｘ256

4色

分散も良好

Cube選択を分散にしたらイマイチな結果になった

分散選択で分散分割は相性いいと思ったけどそうでもない？

16色まで増やしてみる

期待したのとぜんぜん違う

どこか計算間違えているのかも？

20色

やっと赤が入ってきた、こういうもんなのかなあ

分割選択を最大距離にしてみる

16色でまともな結果になった

ってことは分割選択の分散が間違っているかも？

34335色

4色

どれもおなじに見える、分散の2つは全く同じ

今気づいたけど色数の表示が間違っていて

ピクセル数を表示していた

49152色ってあるけど34335色

16色

これも差が出ないねえ

分割Cube選択を距離に変更

差が出た、といっても並べないとわからない

どれもいいねえ

9858色、少なめな色数

4色、最長辺で選択

4色、最大距離で選択

16色、最長辺で選択

16色、最大距離で選択

分割場所の選び方の感想

中央は安定している、Cube選択を分散でする以外はどれもいい結果

中央値は全体的に地味な色合いになる

分散の2つはほとんど差が出ない、中央分割似た結果になることが多い、Cube選択に最大距離を使ったものと相性が良さそう

今回で減色パレットの作成はもういいかなあ

同じような減色画像ばかりで飽きてきた

分割するところのコード

/// <summary>
/// 赤の辺でCubeを分割して返す
/// </summary>
/// <param name="cube">分割するCube</param>
/// <param name="mid">分割の閾値、これ未満とこれ以上で分ける</param>
/// <returns></returns>        
private List<Cube> SplitRedCube(Cube cube, float mid)
{
    //List<Color> low = new List<Color>();
    //List<Color> high = new List<Color>();
    //foreach (Color item in cube.AllPixelsColor)
    //{
    // if (item.R < mid) { low.Add(item); }
    // else { high.Add(item); }
    //}
    //なんかパラレルのほうが遅い…
    var low = new ConcurrentBag<Color>();
    var high = new ConcurrentBag<Color>();
    Parallel.ForEach(cube.AllPixelsColor, item =>
    {
        if (item.R < mid) { low.Add(item); }
        else { high.Add(item); }
    });
    return new List<Cube>() { new Cube(low.ToList()), new Cube(high.ToList()) };
}

private List<Cube> SplitGreenCube(Cube cube, float mid)
{
    var low = new ConcurrentBag<Color>();
    var high = new ConcurrentBag<Color>();
    Parallel.ForEach(cube.AllPixelsColor, item =>
    {
        if (item.G < mid) { low.Add(item); }
        else { high.Add(item); }
    });
    return new List<Cube>() { new Cube(low.ToList()), new Cube(high.ToList()) };
}
private List<Cube> SplitBlueCube(Cube cube, float mid)
{
    var low = new ConcurrentBag<Color>();
    var high = new ConcurrentBag<Color>();
    Parallel.ForEach(cube.AllPixelsColor, item =>
    {
        if (item.B < mid) { low.Add(item); }
        else { high.Add(item); }
    });
    return new List<Cube>() { new Cube(low.ToList()), new Cube(high.ToList()) };
}

//辺の中央で2分割
//RGB同じだった場合はRGBの順で優先
private List<Cube> SplitByLongSide辺の中央(Cube cube)
{
    if (cube.LengthMax == cube.LengthRed)
    {//Rの辺が最長の場合、R要素の中間で2分割              
        return SplitRedCube(cube, (cube.MinRed + cube.MaxRed) / 2f);
    }
    else if (cube.LengthMax == cube.LengthGreen)
    {
        return SplitGreenCube(cube, (cube.MinGreen + cube.MaxGreen) / 2f);
    }
    else
    {
        return SplitBlueCube(cube, (cube.MinBlue + cube.MaxBlue) / 2f);
    }
}

//中央値で2分割、メディアンカット
//辺の選択は長辺、RGB同じだった場合はRGBの順で優先
private List<Cube> SplitByMedian中央値(Cube cube)
{
    float mid;
    List<byte> list = new List<byte>();
    if (cube.LengthMax == cube.LengthRed)
    {
        for (int i = 0; i < cube.AllPixelsColor.Count; ++i)
        {
            list.Add(cube.AllPixelsColor[i].R);
        }
        mid = GetMedian(list);
        return SplitRedCube(cube, mid);
    }
    else if (cube.LengthMax == cube.LengthGreen)
    {
        for (int i = 0; i < cube.AllPixelsColor.Count; ++i)
        {
            list.Add(cube.AllPixelsColor[i].G);
        }
        mid = GetMedian(list);
        return SplitGreenCube(cube, mid);
    }
    else
    {
        for (int i = 0; i < cube.AllPixelsColor.Count; ++i)
        {
            list.Add(cube.AllPixelsColor[i].B);
        }
        mid = GetMedian(list);
        return SplitBlueCube(cube, mid);
    }
}
private float GetMedian(List<byte> list)
{
    list.Sort();
    int lCount = list.Count;
    if (lCount % 2 == 0)
    {
        return (list[lCount / 2] + list[lCount / 2 - 1]) / 2f;
    }
    else { return list[(lCount - 1) / 2]; }
}

最小分散

どこで分割したら分割後の分散が最小になるのかを、分割する位置を一個づつ変えて測って見つける

要素が

24, 52, 190, 193, 226, 231, 247, 248, 250

だったとき、24と52の間で分割すると

52, 190, 193, 226, 231, 247, 248, 250

この2つになる、それぞれの分散は0と3816.5で

分割後の分散合計は3816.5

次は52と190の間で分割

分散要素

196 24, 52

558.5 190, 193, 226, 231, 247, 248, 250

754.5(分散合計)

次は190と193の間で分割

分散要素

5264.9 24, 52, 190

393.6 193, 226, 231, 247, 248, 250

5658.5(分散合計)

こうして全部測って分散が最小になる分割場所を探す

今回の結果は

24, 52

190, 193, 226, 231, 247, 248, 250

この分割が最小だった

52と190の間で分割

縦の軸の52と190の間で分割したところ

分割後の分散が最小になる

もし200とかで分割していたら

あんまり変わんないかなｗ

それでも比べれば散らばり具合が大きくなっている

//最大分散辺を最小分散になるように分割、ピクセル数考慮版
private List<Cube> SplitByMinVariancePixel(Cube cube)
{
    if (double.IsNaN(cube.VarianceMaxFromPixel)) { GetRGBごとの分散Pixel(cube); }

    List<int> iList = new List<int>();
    List<Cube> cubeList = new List<Cube>();
    //赤が最大分散辺のとき
    if (cube.VarianceMaxFromPixel == cube.VarianceRedFromPixel)
    {
        iList = GetNoJuuhuku(cube.AllColor, "r");//昇順リスト取得
        cubeList = SplitRedCube(cube, GetMidFromVariance(iList));
    }
    else if (cube.VarianceMaxFromPixel == cube.VarianceGreenFromPixel)
    {
        iList = GetNoJuuhuku(cube.AllColor, "g");
        cubeList = SplitGreenCube(cube, GetMidFromVariance(iList));
    }
    else if (cube.VarianceMaxFromPixel == cube.VarianceBlueFromPixel)
    {
        iList = GetNoJuuhuku(cube.AllColor, "b");
        cubeList = SplitBlueCube(cube, GetMidFromVariance(iList));
    }
    return cubeList;  
}

//最大分散辺を最小分散になるように分割、ピクセル数無視版
private List<Cube> SplitByMinVariance(Cube cube)
{
    if (double.IsNaN(cube.VarianceMax)) { GetRGBごとの分散(cube); }

    List<int> iList = new List<int>();
    List<Cube> cubeList = new List<Cube>();
    //赤が最大分散辺のとき
    if (cube.VarianceMax == cube.VarianceRed)
    {
        iList = GetNoJuuhuku(cube.AllColor, "r");//昇順リスト取得
        cubeList = SplitRedCube(cube, GetMidFromVariance(iList));
    }
    else if (cube.VarianceMax == cube.VarianceGreen)
    {
        iList = GetNoJuuhuku(cube.AllColor, "g");
        cubeList = SplitGreenCube(cube, GetMidFromVariance(iList));
    }
    else if (cube.VarianceMax == cube.VarianceBlue)
    {
        iList = GetNoJuuhuku(cube.AllColor, "b");
        cubeList = SplitBlueCube(cube, GetMidFromVariance(iList));
    }
    return cubeList;
}
//昇順リストを2分割する時、分散後が最小分散になる閾値を返す
private int GetMidFromVariance(List<int> iList)
{
    //分割する位置を1つづつ増やす
    //分散後の2つ(foreList、backList)の分散値を合計
    //合計値が一番少なくなる場所(index)を特定
    //その場所になる値を返す
    double foreList, bakcList, min = double.MaxValue;
    int index = 0;
    for (int i = 2; i < iList.Count; ++i)
    {
        foreList = GetVariance(iList.GetRange(0, i));//前半分散取得
        bakcList = GetVariance(iList.GetRange(i, iList.Count - i));//後半
        //最小分散になる場所を特定する
        if (min > foreList + bakcList)
        {
            min = foreList + bakcList;
            index = i;
        }
    }
    return iList[index];
}

//分散を取得
private double GetVariance(List<int> list)
{
    var ave = list.Average();
    double variance = 0;
    for (int i = 0; i < list.Count; ++i)
    {
        variance += Math.Pow(list[i] - ave, 2f);
    }
    variance /= list.Count;
    return variance;
}

//ColorListから重複なしの昇順リスト、RGBどれかを指定
private List<int> GetNoJuuhuku(List<Color> list, string rgb)
{
    var sList = new SortedSet<int>();
    for (int i = 0; i < list.Count; ++i)
    {
        try
        {
            if (rgb == "r") { sList.Add(list[i].R); }
            else if (rgb == "g") { sList.Add(list[i].G); }
            else if (rgb == "b") { sList.Add(list[i].B); }
        }
        catch (Exception)
        {
        }
    }
    return sList.ToList();
}