メディアンカット法で色の選択、減色してみた、難しい

メディアンカット法で減色してみた

ダウンロード先

github.com

理解できていないから間違っているかも

それでもいい結果が得られた

いつもの元画像を8色へ

いいねえ

ピクセル数が最大のCubeを優先分割

もう一つが

長辺が最大のCubeを優先分割のパレット

この写真画像だとあんまり変わんないけどねえ

これはこの前のk平均法での減色

どれもそんなに大きな差はないかなあ

パレットに選ばれる色

k平均法はランダム性があるので毎回違う色が選ばれるのが面白い

メディアンカット法は同じ色が選ばれるので安定性がある

処理速度

k平均法は遅い、設定によるけど上の小さな画像でも0.5秒から20秒もかかる

メディアンカット法は一瞬で終わる、それでも大きめ画像1024ｘ768だとパレット作成に4秒、変換に4秒なので結構かかる、これは僕の書き方がイマイチなせいなところがあるけどメディアンカット法のほうがかなり速い

選ばれた色からの減色は前回同様に単純なRGBの距離を使っている

この画像の減色だとパレットに選ばれると良さそうな色は

緑、赤、白、黒、黄緑、茶

このあたりかなあ

6色に減色

ピクセル数優先は赤が無視されてイマイチの結果だけど

長辺優先はいいねえ

画像全体から見ると少ないけど目立つ赤系が選ばれるのは

ピクセル数優先だと

赤が選ばれたのは13色

ここまで増やさないと選ばれない

赤のピクセルは少ない画像なのでこうなる

長辺優先だと

4色の時点で早くも選ばれた、変換結果も悪くない

これが13色だと

赤系だけで3色も選ばれた

こういう画像だと長辺優先の設定のほうが元画像に近くなる

グラデーション画像

3色

こうなるんだ、くらいの感想

8色

これもわかんないなあ

20色

ピクセル数優先のほうが偏りない感じなので

グラデーション画像はピクセル数優先のほうが

元画像に近くなる…かも

グレースケールはどちらも変わらず

ピクセル数の多い青空のグラデーションと

ピクセル数が少ないけど残ってほしい花の黄色

4色

長辺優先は花の黄色がわかる

16色

全体の再現度でいったら長辺優先のほうが上かなあ

ピクセル数優先は青空がきれい

パレットの色選択処理と減色処理を分けたから

パレットの色を作って

パレットをそのまま画像だけ入れ替えて減色すると

全然違う色になる

トマト枯れたｗ

メディアンカット法の要は分割ってことみたい

2色なら分割を1回でおわり、■■■■を■■と■■

3色だと1回目は普通に分割なんだけど、2回目は1回目で分割したどちらの塊を分割するのかを選ぶ必要がある、その条件が今回のピクセル数や辺の長さで他にもいろいろあるみたい

画像の全ピクセルの色のRGB各3つの値を(Cube)直方体に当てはめて

このCubeを色数の分だけ分割していって、できあがったCubeの中の色からパレットの色を選ぶ

(Cube)直方体の頂点の一つを中心に決めて、そこから伸びる辺を色のRGB各3つの値

この中に全ピクセルの色を置いていって分割

分割前に色のないところを削る

青空の画像とかだと青以外の色は少ないから

こんな感じになったとして

分割する場所はRGBの中で一番長い辺の真ん中

なので青の真ん中

青の真ん中で分割してこれで2色

分割したらまたそれぞれの色のないところを削る

ここから3色にする時に

分割したどちらを分割するのか選ぶ条件が

Cubeに含まれるピクセル数が多い方

または一番長い辺がある方

とかになる

僕の場合はこれをC#のコードに書くのは難しくてできなかったので

立体じゃなくて線で試した

List<byte>の最大値と最小値と長さを持つMySplitクラス

public class MySplit
{
    int iMax;
    int iMin;
    public List<byte> MyValues;
    public int Length;

    public MySplit(byte[] values)
    {
        MyValues = values.ToList<byte>();
        int min = int.MaxValue, max = int.MinValue;
        for (int i = 0; i < values.Length; ++i)
        {
            if (min > values[i]) { min = values[i]; }
            if (max < values[i]) { max = values[i]; }
        }
        iMin = min;
        iMax = max;
        Length = MyValues.Count;
    }
    public MySplit(List<byte> list, int min, int max)
    {
        MyValues = list;
        iMax = max;
        iMin = min;
        Length = MyValues.Count;
    }

    //真ん中で分割
    public List<MySplit> SplitHalf()
    {
        float iCenter = ((iMin + iMax) / 2f);
        List<byte> low = new List<byte>();
        List<byte> high = new List<byte>();
        byte cv;
        int lowMax = int.MinValue;
        int highMin = int.MaxValue;
        for (int i = 0; i < this.MyValues.Count; ++i)
        {
            cv = MyValues[i];
            if (iCenter > cv)
            {
                low.Add(cv);
                if (lowMax < cv) { lowMax = cv; }
            }
            else
            {
                high.Add(cv);
                if (highMin > cv) { highMin = cv; }
            }
        }
        return new List<MySplit> {
            new MySplit(low, iMin, lowMax),
            new MySplit(high, highMin, iMax) };
    }
}

青色がコンストラクタでbyte型配列からListを作って、最大値、最小値、長さを記録しているだけ

オレンジ色が自身を真ん中で分割する関数

分割それぞれのMySplitクラスを作ってそれをListにして返す

ところなんだけど

これはこのMySplitクラスの中に書かないで使う方に書いたほうがいいのかもと今思った

このクラスを使って分割のテストは

//1次元配列で分割ループテスト

byte[] iTest = new byte[20];

for (int i = 0; i < iTest.Length; ++i)

{

iTest[i] = (byte)i;

}

MySplit mySplit = new MySplit(iTest);

List<MySplit> listSplit = new List<MySplit>() { new MySplit(iTest) };

listSplit = SplitLoopTest(5, listSplit);//分割数指定で分割

0から19までの20個の数値を5分割

分割前は長さ(length)20で、0から19までの一塊これを

//分割ループテスト
private List<MySplit> SplitLoopTest(int count, List<MySplit> listSplit)
{
    int loopCount = 1;
    while (count > loopCount)
    {
        int max = 0, index = 0;
        for (int i = 0; i < listSplit.Count; ++i)
        {
            if (max < listSplit[i].Length)
            {
                max = listSplit[i].Length;
                index = i;
            }
        }
        listSplit.AddRange(listSplit[index].SplitHalf());
        listSplit.RemoveAt(index);
        loopCount++;
    }
    return listSplit;
}

これに渡して分割

リストの要素数が多い方を優先して分割していく

listSplit
	┗(0)MySplit、ここに20個入っている

最初は塊1つしかないからこれを分割→152行目SplitHalf

549行目、真ん中で分割するので閾値になる真ん中の数値取得は

(最小値＋最大値)/2＝(0+19)/2=9.5

550行目、入れ物を2つ用意、lowとhighこれに分けていく

分けた先の最小値、最大値も仕分けの際に記録する、lowMaxとhighMin

仕分けが終わったところ

真ん中の値9.5で分割されて10個づつに分けられた

それぞれを使ってMySplitを作成、570，571行目

して返す

152行目

返ってきたMySplit2つをlistSplitにAddRangeで追加されたところ

最初の塊に2つ足されたので3つになった

listSplit
	┣[0]MySplit、最初の塊
	┣[1]MySplit、分割されて返ってきた塊
	┗[2]MySplit、分割されて返ってきた塊

153行目、最初の塊はもういらないので除去

除去したところ

0から9までの塊と10から19までの塊の2つに分割された状態

2色ならここで終了

次のループからはどちらの塊を分割するのかになる

大きい方や長い方を分割するけど

今回は長さ、長い方を分割

長さ(length)を見るとどちらも10

同じ場合は早い者勝ちにしてあるから0番

0～9が入っている方を分割

仕分け終了したところ

0～4と5～9に仕分けられた

分割された2つが返ってきてlistSplitに追加されたところ

listSplit
	┣[0]MySplit、1回目の分割
	┣[1]MySplit、1回目の分割
	┣[2]MySplit、分割されて返ってきた塊
	┗[3]MySplit、分割されて返ってきた塊

0番は分割されて2番、3番に追加されてもういらないので除去

次の分割対象はLengthが10の0番

これを指定された5分割まで繰り返した結果

これだとわかりにくいので

5,6,7,8,9,

10,11,12,13,14,

15,16,17,18,19,

0,1,

2,3,4,

こうなった

個数だと５，５，５，２，３

いいねえ、できた

0～255までのランダムな数値10000個を5分割

10000個の値

randomクラスにはNextBytesっている便利なメソッドがあった

byte[] iTest = new byte[10000];

Random random = new Random();

random.NextBytes(iTest);

byte型の配列を渡すと中にbyte型のランダム値を入れて返してくれる

forとかで回さなくていいので楽ちん

ランダム値10000個を5分割結果

2557個: 最小値=0 最大値=63

2437個: 最小値=128 最大値=191

2432個: 最小値=192 最大値=255

1346個: 最小値=64 最大値=95

1228個: 最小値=96 最大値=127

ランダム値20個を5分割、1回目

2個: 最小値=201 最大値=249

5個: 最小値=142 最大値=167

5個: 最小値=175 最大値=195

6個: 最小値=15 最大値=57

2個: 最小値=63 最大値=105

ランダム値20個を5分割、2回目

4個: 最小値=2 最大値=42

7個: 最小値=149 最大値=187

2個: 最小値=203 最大値=247

3個: 最小値=63 最大値=87

4個: 最小値=88 最大値=112

ランダム値5個を5分割

1個: 最小値=186 最大値=186

1個: 最小値=13 最大値=13

1個: 最小値=62 最大値=62

1個: 最小値=133 最大値=133

1個: 最小値=136 最大値=136

ランダム値5個を7分割

1個: 最小値=177 最大値=177

1個: 最小値=225 最大値=225

1個: 最小値=249 最大値=249

0個: 最小値=185 最大値=-2147483648

1個: 最小値=185 最大値=185

0個: 最小値=111 最大値=-2147483648

1個: 最小値=111 最大値=111

個数以上に分割しようとするとエラーにはならないけど最大値は初期値に設定しているintの最小値

こんな感じで1次元配列ではできた

目的の直方体もほとんど同じなんだけど、最初は書けなかったんだよねえ

コード全部貼り付けたら文字数上限超えたみたいで投稿エラーなので一部だけ

さっきのMySplitクラスをRGB用に書き換えたCubeクラス

public class Cube
{
    public byte MinRed;//最小R
    public byte MinGreen;
    public byte MinBlue;
    public byte MaxRed;//最大赤
    public byte MaxGreen;
    public byte MaxBlue;
    public List<Color> ListColors;//色リスト
    public int LengthMax;//Cubeの最大辺長
    public int LengthRed;//赤の辺長
    public int LengthGreen;
    public int LengthBlue;

    //BitmapSourceからCubeを作成
    public Cube(BitmapSource source)
    {
        var bitmap = new FormatConvertedBitmap(source, PixelFormats.Pbgra32, null, 0);
        var wb = new WriteableBitmap(bitmap);
        int h = wb.PixelHeight;
        int w = wb.PixelWidth;
        int stride = wb.BackBufferStride;
        byte[] pixels = new byte[h * stride];
        wb.CopyPixels(pixels, stride, 0);
        long p = 0;
        byte cR, cG, cB;
        byte lR = 255, lG = 255, lB = 255, hR = 0, hG = 0, hB = 0;
        ListColors = new List<Color>();
        for (int y = 0; y < h; ++y)
        {
            for (int x = 0; x < w; ++x)
            {
                p = y * stride + (x * 4);
                cR = pixels[p + 2]; cG = pixels[p + 1]; cB = pixels[p];
                ListColors.Add(Color.FromRgb(cR, cG, cB));
                if (lR > cR) { lR = cR; }
                if (lG > cG) { lG = cG; }
                if (lB > cB) { lB = cB; }
                if (hR < cR) { hR = cR; }
                if (hG < cG) { hG = cG; }
                if (hB < cB) { hB = cB; }
            }
        }
        MinRed = lR; MinGreen = lG; MinBlue = lB;
        MaxRed = hR; MaxGreen = hG; MaxBlue = hB;
        LengthRed = 1 + MaxRed - MinRed;
        LengthGreen = 1 + MaxGreen - MinGreen;
        LengthBlue = 1 + MaxBlue - MinBlue;
        LengthMax = Math.Max(LengthRed, Math.Max(LengthGreen, LengthBlue));
    }

    //ColorのリストからCube作成
    public Cube(List<Color> color)
    {
        //Color cColor = color[0];
        byte lR = 255, lG = 255, lB = 255, hR = 0, hG = 0, hB = 0;
        byte cR, cG, cB;
        ListColors = new List<Color>();
        foreach (Color item in color)
        {
            cR = item.R; cG = item.G; cB = item.B;
            ListColors.Add(Color.FromRgb(cR, cG, cB));
            if (lR > cR) { lR = cR; }
            if (lG > cG) { lG = cG; }
            if (lB > cB) { lB = cB; }
            if (hR < cR) { hR = cR; }
            if (hG < cG) { hG = cG; }
            if (hB < cB) { hB = cB; }
        }
        MinRed = lR; MinGreen = lG; MinBlue = lB;
        MaxRed = hR; MaxGreen = hG; MaxBlue = hB;
        LengthRed = 1 + MaxRed - MinRed;
        LengthGreen = 1 + MaxGreen - MinGreen;
        LengthBlue = 1 + MaxBlue - MinBlue;
        LengthMax = Math.Max(LengthRed, Math.Max(LengthGreen, LengthBlue));
    }

    //一番長い辺で2分割
    public List<Cube> Split()
    {
        List<Color> low = new List<Color>();
        List<Color> high = new List<Color>();
        float mid;
        if (LengthMax == LengthRed)
        {//Rの辺が最長の場合、R要素の中間で2分割
            mid = ((MinRed + MaxRed) / 2f);
            foreach (Color item in ListColors)
            {
                if (item.R < mid) { low.Add(item); }
                else { high.Add(item); }
            }
        }
        else if (LengthMax == LengthGreen)
        {
            mid = ((MinGreen + MaxGreen) / 2f);
            foreach (Color item in ListColors)
            {
                if (item.G < mid) { low.Add(item); }
                else { high.Add(item); }
            }
        }
        else
        {
            mid = ((MinBlue + MaxBlue) / 2f);
            foreach (Color item in ListColors)
            {
                if (item.B < mid) { low.Add(item); }
                else { high.Add(item); }
            }
        }
        return new List<Cube> { new Cube(low), new Cube(high) };
    }

    //平均色
    public Color GetAverageColor()
    {
        List<Color> colorList = ListColors;
        long r = 0, g = 0, b = 0;
        int cCount = colorList.Count;
        if (cCount == 0)
        {
            return Color.FromRgb(127, 127, 127);
        }
        for (int i = 0; i < cCount; ++i)
        {
            r += colorList[i].R;
            g += colorList[i].G;
            b += colorList[i].B;
        }
        return Color.FromRgb((byte)(r / cCount), (byte)(g / cCount), (byte)(b / cCount));
    }
}

MySplitクラスと比べてプロパティが増えて、分割のところでRGBどの辺が長いのかの判定が増えただけかな

f:id:gogowaten:20191212012754p:plain

164行目、OriginBitmapはBitmapSource、これからCubeクラスを作ってlistに入れて

166行目と181行目、SplitCubeByLongSideとSplitCubeByColorsCountに分割数とCubeのリストを渡して分割している

//Cubeを指定個数になるまで分割、ピクセル数が多いCubeを優先して分割
private List<Cube> SplitCubeByColorsCount(int split, List<Cube> listCube)
{
    int loopCount = 1;
    while (split > loopCount)
    {
        int max = 0, index = 0;
        for (int i = 0; i < listCube.Count; ++i)
        {
            if (max < listCube[i].ListColors.Count)
            {
                max = listCube[i].ListColors.Count;
                index = i;
            }
        }
        listCube.AddRange(listCube[index].Split());
        listCube.RemoveAt(index);
        loopCount++;
    }
    return listCube;
}
//Cubeを指定個数になるまで分割、長辺が最大のCubeを優先
private List<Cube> SplitCubeByLongSide(int split, List<Cube> listCube)
{
    int loopCount = 1;
    while (split > loopCount)
    {
        int max = 0, index = 0;
        for (int i = 0; i < listCube.Count; ++i)
        {
            if (max < listCube[i].LengthMax)
            {
                max = listCube[i].LengthMax;
                index = i;
            }
        }
        listCube.AddRange(listCube[index].Split());
        listCube.RemoveAt(index);
        loopCount++;
    }
    return listCube;
}

どの塊(Cube)を分割するかの判定

選んだCubeを渡して分割されたのが返ってきたらリストに追加して元のCubeを除去

ってのは1次元配列のときと全く同じ

コード全部

GitHub

20180226forMyBlog/20180306_メディアンカット法でパレット作成して減色 at master · gogowaten/20180226forMyBlog

↑に実行(.exe)ファイルも置いたんだけど、ダウンロードするとウイルスを検出しましたって警告が出る、そうなるとDebugで使っている実行ファイルもウイルス警告が出て検疫されてしまう、その後にDebug実行して作成されたファイルは警告が出ない

アップロードしてダウンロードするとまたウイルス警告が出る

試しにzipで圧縮した実行ファイルをアップロードしてダウンロードして展開したら今度はウイルス警告は出ない

ってことは実行ファイルそのものをダウンロードすると、ウイルスの有無にかかわらず問答無用でウイルス判定されているみたい

もう少し詳しく記事にしてみた

gogowaten.hatenablog.com

作ったアプリの実行ファイルがウイルスだと言われるｗ ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
https://blogs.yahoo.co.jp/gogowaten/15400739.html

参照したところ

減色アルゴリズム[量子化/メディアンカット/k平均法]
https://www.petitmonte.com/math_algorithm/subtractive_color.html
メディアンカット法による画像の減色｜スパイシー技術メモ
https://www.spicysoft.com/blog/spicy_tech/001253.html
ゆるゆるプログラミング減色処理（メディアンカット）
http://talavax.com/mediancut.html
24bit → 8bit 減色: koujinz blog
http://koujinz.cocolog-nifty.com/blog/2009/04/24bit-8bit-a879.html