algorithm - フォローアップ：独自性による色の「並べ替え」

Question

N個の最大距離の色（および関連する距離メトリック）が与えられた場合、最初のMも最大に異なるセットにかなり近いように、それらの色をある順序に並べ替える方法を考え出すことができますか？

言い換えれば、たくさんの異なる色が与えられた場合、最初から必要な数の色を使用できるように順序を考え、それらがすべて異なること、および近くの色も非常に異なることを合理的に保証します（たとえば、青みがかった赤は赤みがかった青の隣ではありません）。

ランダム化は問題ありませんが、確かに最適ではありません。

明確化：大きくて視覚的に異なる色のセット（たとえば、256または1024）が与えられた場合、最初の、たとえば16を使用すると、比較的視覚的に異なる色のサブセットが得られるように並べ替えます。これは、大まかに言って、この1024のリストを並べ替えて、個々の色が視覚的に近くなるほど、リスト上で離れるようにすることと同じです。

score 3 · Accepted Answer

知覚はあなたにとって重要であるように思われます。その場合、YUV、YCbCr、Labなどの知覚色空間での作業を検討することをお勧めします。これらを使用するたびに、sRGBだけの場合よりもはるかに優れた結果が得られます。

sRGBとの間の変換は面倒な場合がありますが、実際にはアルゴリズムが単純になる可能性があり、ボーナスとして、ほとんどの場合、カラーブラインドでも機能します。

score 3 · Accepted Answer

この問題は色の量子化と呼ばれ、多くのよく知られているアルゴリズムがあります。

score 3 · Accepted Answer

これは、抵抗が最も少ない経路をマッピングしようとするある種の抵抗グラフのようにも思えます。要件、最大抵抗のパスを逆にすると、最初から最大の差を生み出し、最後に向かって他の値に近い値に戻り始めるセットを生成するために使用できます。

たとえば、これはおそらくあなたがやりたいことをする1つの方法です。

各色から他のすべての色までの距離を計算します（他の投稿を参照してください）
各色の距離を合計すると、この色が他のすべての色からどれだけ離れているかがわかります
リストを距離で下に並べます

これにより、他のすべての色から最も離れた色から始まるリストが作成され、リストの最後にある色が一般的に他の色に近くなります。

編集：空間的細分化に関する私の最初の投稿への返信を読むと、他の色に近い色はリストの一番下に落ちるため、上記の説明に正確には適合しませんが、どこかに色のクラスターがあるとしましょう。そのクラスターの色の少なくとも 1 つがリストの先頭近くに配置され、それが他のすべての色の合計から一般的に最も離れた色になります。それが理にかなっていれば。

score 3 · Accepted Answer

N 個の最大距離の色は、3 次元 (色) 空間で適切に分散された点のセットと見なすことができます。ハルトンシーケンスからそれらを生成できる場合、任意のプレフィックス (最初の M 色) も適切に分散されたポイントで構成されます。

score 2 · Accepted Answer

2つのリストから始めます。CandidateColors（最初は個別の色が含まれています）とSortedColors（最初は空です）。
任意の色を選択してCandidateColorsから削除し、SortedColorsに入れます。これは最初の色であり、最も一般的な色になるため、アプリケーションに適した色を選択するのに適した場所です。
CandidateColorsの各色について、その合計距離を計算します。合計距離は、CandidateColorからSortedColorsの各色までの距離の合計です。
CandidateColorsから合計距離が最大の色を削除し、SortedColorsの最後に追加します。
CandidateColorsが空でない場合は、手順3に戻ります。

この欲張りアルゴリズムはあなたに良い結果を与えるはずです。

score 2 · Accepted Answer

任意のインデックスカラーへの最小距離の最大距離に基づいて、候補の色を並べ替えることができます。

ユークリッド色距離の使用:

public double colordistance(Color color0, Color color1) {
    int c0 = color0.getRGB();
    int c1 = color1.getRGB();
    return distance(((c0>>16)&0xFF), ((c0>>8)&0xFF), (c0&0xFF), ((c1>>16)&0xFF), ((c1>>8)&0xFF), (c1&0xFF));
}

public double distance(int r1, int g1, int b1, int r2, int g2, int b2) {
    int dr = (r1 - r2);
    int dg = (g1 - g2);
    int db = (b1 - b2);
    return Math.sqrt(dr * dr + dg * dg + db * db);
}

好きなものに置き換えることができますが。色距離ルーチンが必要なだけです。

public void colordistancesort(Color[] candidateColors, Color[] indexColors) {
    double current;

    double distance[] = new double[candidateColors.length];
    for (int j = 0; j < candidateColors.length; j++) {
        distance[j] = -1;
        for (int k = 0; k < indexColors.length; k++) {
            current = colordistance(indexColors[k], candidateColors[j]);
            if ((distance[j] == -1) || (current < distance[j])) {
                distance[j] = current;
            }
        }
    }

    //just sorts.
    for (int j = 0; j < candidateColors.length; j++) {
        for (int k = j + 1; k < candidateColors.length; k++) {
            if (distance[j] > distance[k]) {
                double d = distance[k];
                distance[k] = distance[j];
                distance[j] = d;

                Color m = candidateColors[k];
                candidateColors[k] = candidateColors[j];
                candidateColors[j] = m;
            }
        }
    }
}

score 2 · Accepted Answer

私が質問を正しく理解している場合、距離関数dを指定して、色間の平均距離が最も高いM色のサブセットを取得したいと考えています。

別の言い方をすれば、 N色の初期セットを、すべての色が接続された大きな無向グラフと見なすと、任意のMノードを訪問する最長パスを見つける必要があります。

NP 完全なグラフの問題を解決することは、私には難しいと思いますが、簡単な物理シミュレーションを実行してみてください。

色空間にM個のランダムポイントを生成する
各ポイント間の距離を計算する
他のすべてのポイントから遠ざける各ポイントの反発ベクトルを計算します (ベクトルの大きさとして 1 / (距離^ 2) を使用)。
各ポイントの反発ベクトルを合計する
合計された反発ベクトルに従って各ポイントの位置を更新します
範囲外の座標を制限します (光度が負または 1 を超えるなど)。
ポイントが安定するまで、手順 2 から繰り返します。
各ポイントについて、Nの元のセットから最も近い色を選択します。

効率的とは言えませんが、 Mが小さい場合は十分に効率的であり、ほぼ最適な結果が得られます。

色距離関数が単純な場合、最適なサブセットを生成するより決定論的な方法があるかもしれません。

score 1 · Accepted Answer

N色のセットから、MがM空間のN色の最良の表現であるように、M <NであるM色を選択する必要があるということですか？

より良い例として、トゥルーカラー（24ビットカラースペース）を8ビットマップカラースペース（GIF？）に縮小します。

これには、ImageMagicで使用されるAdaptiveSpatialSubdivisionアルゴリズムのような量子化アルゴリズムがあります。

これらのアルゴリズムは通常、ソーススペースから既存の色を選択するだけでなく、ソースカラーに最も近いターゲットスペースに新しい色を作成します。簡単な例として、元の画像に3色があり、2色が赤（強度や青みがかった色合いなど）で、3色が青で、2色に減らす必要がある場合、ターゲット画像の色は赤になる可能性があります。これは、元の2つの赤と元の画像の青の色の平均のようなものです。

あなたが何か他のものを必要とするなら、私はあなたの質問を理解しませんでした:)

score 1 · Accepted Answer

それらをRGBHEX形式に分割して、GおよびBと同じように、Rを異なる色のRと比較できるようにすることができます。

HTMLと同じ形式

XX XX XX
RR GG BB

00 00 00 = black
ff ff ff = white
ff 00 00 = red
00 ff 00 = green
00 00 ff = blue

したがって、決定する必要があるのは、色をどれだけ近づけるか、およびセグメントが異なると見なされるための許容可能な違いは何かということだけです。

algorithm - フォローアップ：独自性による色の「並べ替え」

9 に答える 9

Related

Reference