c# - 画像内の固有の色の数をカウントするためのアルゴリズム

Question

十分に高速でありながら、メモリを備えた優雅なものを探しています。画像は24bppSystem.Drawing.Bitmapです。

score 14 · Accepted Answer

正確な数が必要な場合は、すべてのピクセルをループする必要があります。色がまばらであるため、おそらく色とカウントをハッシュに格納するのが最善の方法です。

カラーオブジェクトの代わりにハッシュでColor.ToArgb（）を使用することもおそらく良い考えです。

また、速度が主な懸念事項である場合は、GetPixel（x、y）のような関数を使用したくない場合は、代わりにチャンクを一度に（一度に行に）処理してみてください。可能であれば、画像メモリの先頭へのポインタを取得し、安全ではありません。

score 11 · Accepted Answer

これまでにこのようなものを実装したことはありませんが、私が見ているように、基本的な実装は次のとおりです。

24ビット画像の場合、画像が持つことができる色の最大数は最小（2 ^ 24、画像のピクセル数）です。

カウントされた回数ではなく、特定の色がカウントされたかどうかを記録するだけで済みます。つまり、各色がカウントされるかどうかを記録するには1ビットが必要です。これは2MBのメモリです。ピクセルを繰り返し処理し、2MBのカラーセットマップに関連するビットを設定します。最後に、設定されたビットを数えてカラーセットマップを繰り返します（運が良ければ、これを支援するPOPCNT命令があります）。

小さい画像と確かに低い色深度の場合は、カラーテーブルを保持し、画像に含まれる各色を数える方がよい場合があります。

score 6 · Accepted Answer

ここにいるほとんどの人は、おそらく高速なソリューションを提案しています (実際には、2 MB のみを使用するソリューションは、メモリ使用量に関しておそらく許容され、非常に高速です。ハッシュを使用するソリューションはさらに高速になる可能性がありますが、間違いなく 2 MB 以上のメモリを使用します)。メモリー）。プログラミングは常にメモリ使用量と CPU 時間の間のトレードオフです。通常、より多くのメモリを「無駄にする」ことを厭わない場合は、より速く結果を得ることができます。また、より多くの計算時間を「無駄にする」ことで結果を遅くすることもできますが、これにより多くのメモリを節約できます。

これまで誰も提案していなかった解決策の 1 つを次に示します。これはおそらく最もメモリの消費が少ないものです (最適化できるため、イメージをメモリに保持するために必要な量以上のメモリを使用することはほとんどありませんが、イメージは変更されますが、最初にコピーする必要がある場合があります)。ハッシュまたはビットマスクのソリューションよりも速度が速いとは思えませんが、メモリが最大の関心事である場合は興味深いことです。

イメージ内のピクセルを色別に並べ替えます。すべてのピクセルを 32 ビットの数値に簡単に変換でき、32 ビットの数値を相互に比較できます。一方の数値が他方の数値よりも小さいか、大きいか等しいかを比較できます。Quicksort を使用する場合、追加のスタックスペースを除いて、並べ替えに追加のストレージスペースは必要ありません。Shellsort を使用する場合、追加のメモリはまったく必要ありません (ただし、Shellsort は Quicksort よりもはるかに遅くなります)。

int num = (赤 << 16) + (緑 << 8) + 青;
そのようにピクセルを並べ替えると (つまり、画像内でそれらを再配置したことを意味します)、同じ色のすべてのピクセルは常に互いに隣り合っています。そのため、画像を 1 回繰り返して、色がどのくらいの頻度で変化するかを確認できます。たとえば、ピクセルの現在の色を (0, 0) に保存し、値 1 でカウンターを初期化します。次のステップでは、(0, 1) に移動します。前と同じ色の場合は何もせず、次のピクセル (0, 2) に進みます。ただし、同じでない場合は、カウンターを 1 つ増やして、次の反復のためにそのピクセルの色を記憶します。
最後のピクセルを確認すると (最後の 2 番目のピクセルと同じでない場合は、カウンターを再び増やした可能性があります)、カウンターには一意の色の数が含まれます。

すべてのピクセルを少なくとも 1 回反復することは、ソリューションに関係なく、どのような場合でも実行する必要があるため、このソリューションが他のソリューションよりも遅くなったり速くなったりすることに影響はありません。このアルゴリズムの速度は、画像のピクセルを色別に並べ替える速度によって異なります。

私が言ったように、このアルゴリズムは、速度が主なコンサートの場合は簡単に打ち負かされます (ここにある他のソリューションはおそらくすべてより高速です) が、メモリ使用量が主な関心事である場合は打ち負かすことができるとは思えません。 1 つの色とイメージ自体のストレージスペースを保存します。選択した並べ替えアルゴリズムで必要な場合にのみ、追加のメモリが必要になります。

score 4 · Accepted Answer

var cnt = new HashSet<System.Drawing.Color>();

foreach (Color pixel in image)
    cnt.Add(pixel);

Console.WriteLine("The image has {0} distinct colours.", cnt.Count);

/ EDIT：Louが言っ.GetArgb()たように、値自体の代わりに使用すると、実装Color方法が原因で少し速くなる可能性があります。ColorGetHashCode

score 3 · Accepted Answer

ここでの他の実装のほとんどは遅くなります。これを高速に行うには、スキャンラインへの直接アクセスと、カラーデータを格納するためのある種のスパースマトリックスが必要です。

最初に 32bpp のケースについて説明します。これははるかに簡単です。

HashSet: 色の疎行列
ImageData: BitmapDataオブジェクトを使用して、基になるメモリに直接アクセスします
PixelAccess: int* を使用して、反復可能な int としてメモリを参照します

反復ごとに、その整数の hashset.add を実行するだけです。最後に、HashSet に含まれるキーの数を確認します。これが色の総数です。HashSet のサイズ変更は非常に面倒であることに注意することが重要です (O(n) ここで、n はセット内のアイテムの数です)。 4がいいでしょう。

24bpp の場合、PixelAccess は byte* である必要があり、int を構築するために色ごとに 3 バイトを反復処理する必要があります。3 つのセットの各バイトについて、最初のビットを左に 8 (1 バイト) シフトし、それを整数に追加します。これで、32 ビット int で表される 24bpp Color ができました。残りはすべて同じです。

score 2 · Accepted Answer

固有の色を正確に定義していませんでした。（視覚的に同じではなく）実際に真に一意のコード値を意味する場合、唯一の正確な解決策は、他の回答で説明されている手法のいずれかを使用して実際にそれらを数えることです。

視覚的に類似した色を探している場合、元のフルダイナミックカラーレンジイメージを最も厳密に表現するために使用する 256 の最適な一意の色を探しているパレットマッピングの問題にすぐに絞り込まれます。ほとんどの画像では、256 色が適切に選択されている場合、24 ビットから最大 1600 万色に縮小された画像を、256 色のみの画像にマッピングできることは驚くべきことです。これらの適切な 256 色 (この例の場合) の最適な選択は、NP 完全であることが証明されていますが、非常に近い実用的なソリューションがあります。Shijie Wan という名前の人物による論文や、彼の研究に基づくものを検索してください。

画像内のコード値の色数の近似値を探している場合は、無損失圧縮方式を使用して画像を圧縮します。圧縮率は、画像内の一意のコード値の数に直接関係します。圧縮された出力を保持する必要さえありません。途中でバイト数を蓄積し、実際の出力データを破棄するだけです。サンプル画像のセットを参照として使用すると、圧縮率と画像内の異なるコード値の数との間のルックアップテーブルを作成できます。繰り返しますが、この最後の手法は非常に高速ですが、間違いなく概算ですが、適度に相関するはずです。

score 1 · Accepted Answer

ほとんどのマシンが256カラーパレットモードで実行されていた最新のグラフィックカードの前は、これはかなり興味深い領域でした。処理能力とメモリの制限は、あなたに役立つかもしれない一種の制約を課しました-したがって、パレットを処理するためのアルゴリズムの検索は、何か役に立つものになる可能性があります。

score 1 · Accepted Answer

これは、分析する画像の種類によって異なります。24ビット画像の場合、最大2MBのメモリが必要になります（最悪の場合、各色を処理する必要があるため）。このためには、ビットマップが最適です（2 MBのビットマップがあり、各ビットは色に対応しています）。これは、O（#pixels）で実現できるカラーカウントの多い画像に適したソリューションです。16ビット画像の場合、この手法を使用すると、このビットマップに必要なのは8kBだけです。

ただし、色の少ない写真がある場合は、別のものを使用することをお勧めします。ただし、使用するアルゴリズムを示すために、何らかのチェックが必要になります...

score 1 · Accepted Answer

画像内の一意の色の最大数はピクセル数に等しいため、これはプロセスの最初から予測可能です。Konrad によって提案された HashSet メソッドを使用することは、ハッシュのサイズがピクセル数を超えてはならないため、合理的な解決策のように思われますが、JeeBee によって提案されたビットマップアプローチを使用すると、32 ビットで 512 MB が必要になります。画像 (アルファチャネルがあり、これが色の一意性に寄与すると判断された場合)

ただし、HashSet アプローチのパフォーマンスは、「ビットごとの色」アプローチよりも悪い可能性があります。両方を試して、多くの異なる画像を使用していくつかのベンチマークを実行することをお勧めします。

score 0 · Accepted Answer

カラー量子化の最近の一般的な実装では、octreeデータ構造が使用されます。ウィキペディアのページに注意してください。コンテンツはかなり優れています。octree には、必要に応じてメモリを制限できるという利点があるため、メモリをあまり追加しなくても、画像全体をサンプリングしてパレットを決定できます。概念を理解したら、1996 年の Dobb 博士のジャーナル記事のソースコードへのリンクをたどってください。

これは C# に関する質問なので、2003 年 5 月の MSDN の記事Optimizing Color Quantization for ASP.NET Images を参照してください。ソースコードが含まれています。

c# - 画像内の固有の色の数をカウントするためのアルゴリズム

10 に答える 10

Related

Reference