2048x2048 の画像が与えられ、画像に含まれる色の総数を知りたい場合、可能な限り最速のアルゴリズムは何ですか? 2 つのアルゴリズムを思いつきましたが、遅いです。
アルゴリズム 1:
このアルゴリズムは機能しますが、遅いです。1600x1200 ピクセルの画像の場合、約 3 秒かかります。
アルゴリズム 2: 各ピクセルを他のすべてのピクセルと照合し、色の出現回数を記録してカウントをインクリメントする明白な方法。これは非常に遅く、ハングアップしたアプリのようです。それで、より良いアプローチはありますか？すべてのピクセル情報が必要です。
まあ、これは並列化に適しています。画像をいくつかの部分に分割し、別々のタスクで各部分のアルゴリズムを実行します。同期を回避するには、それぞれに固有の色用の独自のストレージが必要です。すべてのタスクが完了したら、結果を集約します。
std::set(または)を使用std::unordered_setして、ピクセルを 1 回ループし、色をセットに追加することができます。その場合、色の数はセットのサイズです。
DRAMは非常に安価です。ブルートフォースを使用します。タブを埋めて、数えます。
core2duo @ 3.0GHz の場合:
4096x4096 32 ビット RGB で 0.35 秒
些細な並列化の 0.20 秒後 (omp については何も知りません)
ただし、64 ビット RGB (1 チャネル = 16 ビット) を使用する場合は、別の問題です (メモリが不足しています)。おそらく、優れたハッシュ テーブル関数が必要になるでしょう。ランダムなピクセルを使用すると、同じサイズに 10 秒かかります。
注意: 0.15 秒では、std::bitset<> ソリューションの方が高速です (自明に並列化すると遅くなります!)。
ソリューション、c++11
#include <vector>
#include <random>
#include <iostream>
#include <boost/chrono.hpp>
#define _16M 256*256*256
typedef union {
struct { unsigned char r,g,b,n ; } r_g_b_n ;
unsigned char rgb[4] ;
unsigned i_rgb;
} RGB ;
RGB make_RGB(unsigned char r, unsigned char g , unsigned char b) {
RGB res;
res.r_g_b_n.r = r;
res.r_g_b_n.g = g;
res.r_g_b_n.b = b;
res.r_g_b_n.n = 0;
return res;
}
static_assert(sizeof(RGB)==4,"bad RGB size not 4");
static_assert(sizeof(unsigned)==4,"bad i_RGB size not 4");
struct Image
{
Image (unsigned M, unsigned N) : M_(M) , N_(N) , v_(M*N) {}
const RGB* tab() const {return & v_[0] ; }
RGB* tab() {return & v_[0] ; }
unsigned M_ , N_;
std::vector<RGB> v_;
};
void FillRandom(Image & im) {
std::uniform_int_distribution<unsigned> rnd(0,_16M-1);
std::mt19937 rng;
const int N = im.M_ * im.N_;
RGB* tab = im.tab();
for (int i=0; i<N; i++) {
unsigned r = rnd(rng) ;
*tab++ = make_RGB( (r & 0xFF) , (r>>8 & 0xFF), (r>>16 & 0xFF) ) ;
}
}
size_t Count(const Image & im) {
const int N = im.M_ * im.N_;
std::vector<char> count(_16M,0);
const RGB* tab = im.tab();
#pragma omp parallel
{
#pragma omp for
for (int i=0; i<N; i++) {
count[ tab->i_rgb ] = 1 ;
tab++;
}
}
size_t nColors = 0 ;
#pragma omp parallel
{
#pragma omp for
for (int i = 0 ; i<_16M; i++) nColors += count[i];
}
return nColors;
}
int main() {
Image im(4096,4096);
FillRandom(im);
typedef boost::chrono::high_resolution_clock hrc;
auto start = hrc::now();
std::cout << " # colors " << Count(im) << std::endl ;
boost::chrono::duration<double> sec = hrc::now() - start;
std::cout << " took " << sec.count() << " seconds\n";
return 0;
}
ここで重要なのは、2Dの色の配列としての画像の理想的な表現は、画像がメモリに保存される方法ではないということです（色のコンポーネントは「平面」に配置でき、「パディング」などがあります）。 。したがって、 GetPixel-like関数を使用してピクセルを取得するには時間がかかる場合があります。
したがって、画像が「ベクトル描画」の結果でない場合、質問はどういうわけか意味がないかもしれません。写真を考えてみてください。2つの近くの「緑」の間にすべての緑の色合いがあるので、この場合は色が見つかります。 -画像自体のエンコーディング（2 ^ 24、256、16、または...）でサポートされているものでもあります。したがって、色の分布（使用方法の違い）に関心がない限り、それらを数えるだけではほとんど意味がありません。
回避策は次のとおりです。
画像がすでに平面形式であることがすでにわかっている場合は、手順1と2を回避できることに注意してください。
マルチコアシステムを使用している場合は、ステップ4を異なるスレッドに割り当てることもできます。各スレッドはイメージの作業部分です。
ここで実行可能な唯一のアルゴリズムは、画像の色のヒストグラムのようなものを作成することです。あなたの場合の唯一の違いは、各色の人口を計算する代わりに、それがゼロかどうかを知る必要があるということです。
作業する色空間に応じて、std::set（Joachim Pileborgが提案したように）既存の色にタグを付けるか、またはのようなものを使用することstd::bitsetができます。これは明らかに高速です。これは、色空間にどれだけの異なる色が存在するかによって異なります。
また、Marius Bancilaが指摘したように、この手順は並列化に完全に一致します。画像部分のヒストグラムのようなデータを計算し、それをマージします。当然、画像の分割は、幾何学的特性ではなく、メモリパーティションに基づく必要があります。簡単に言うと、画像を水平方向ではなく垂直方向に（スキャンラインのバッチで）分割します。
また、可能であれば、低レベルのライブラリ/コードを使用してピクセルを実行するか、独自のライブラリ/コードを作成してみてください。少なくとも、ピクセルごとに同じようなことをするのではなく、ラインをスキャンしてそのピクセルをバッチで実行するためのポインタを取得する必要があります。GetPixel
bitset個々のビットを設定できる関数を使用できますcount。
色ごとにビットがあり、RGB のそれぞれに 256 の値があるため、256*256*256 ビット (16,777,216 色) になります。はbitset8 ビットごとに 1 バイトを使用するため、2MB を使用します。
へのインデックスとしてピクセルの色を使用しますbitset。
bitset<256*256*256> colours;
for(int pixel: pixels) {
colours[pixel] = true;
}
colours.count();
これには線形複雑性があります。