c++ - 更快的算法来检查图像中的颜色

Question

假设给定一张 2048x2048 的图像，并且我想知道图像中存在的颜色总数，那么最快的算法是什么？我想出了两个算法，但它们很慢。

算法1：

比较当前像素和下一个像素，如果它们不同
检查包含所有检测到的颜色的临时变量，以查看颜色是否存在
如果不存在，则将其添加到数组（列表）并增加 noOfColors。

该算法有效，但速度很慢。对于 1600x1200 像素的图像，大约需要 3 秒。

算法2：将每个像素与所有其他像素检查并记录颜色出现次数并增加计数的明显方法。这非常非常慢，几乎就像一个挂起的应用程序。那么有没有更好的方法呢？我需要所有的像素信息。

score 3 · Accepted Answer

您可以使用std::set（或std::unordered_set），并简单地通过像素进行一个循环，将颜色添加到集合中。那么颜色的数量就是集合的大小。

score 3 · Accepted Answer

嗯，这适合并行化。将图像分成几个部分，并在单独的任务中为每个部分执行算法。为了避免同步，每个都应该有自己的存储空间来存储独特的颜色。完成所有任务后，您可以汇总结果。

score 2 · Accepted Answer

DRAM非常便宜。使用蛮力。填一个标签，数一数。

在 core2duo @ 3.0GHz 上：

4096x4096 32 位 RGB 为 0.35 秒

一些微不足道的并行化后 0.20 秒（我对 omp 一无所知）

但是，如果您要使用 64 位 rgb（一个通道 = 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;
}

score 1 · Accepted Answer

这里唯一可行的算法是建立一种图像颜色的直方图。在您的情况下，唯一的区别是，您不需要计算每种颜色的总体，而是只需要知道它是否为零。

根据您使用的颜色空间，您可以使用 astd::set来标记现有颜色（如 Joachim Pileborg 建议的那样），或者只使用类似的东西std::bitset，这显然更快。这取决于您的色彩空间中存在多少不同的颜色。

此外，正如 Marius Bancila 所指出的，此过程非常适合并行化。计算图像部分的直方图数据，然后将其合并。自然地，图像划分应该基于它的内存划分，而不是几何属性。简而言之 - 垂直分割图像（按批次扫描线），而不是水平分割。

而且，如果可能的话，您应该使用一些低级库/代码来运行像素，或者尝试编写自己的。至少您必须GetPixel获得一个指向扫描线的指针并在其像素上批量运行，而不是为每个像素做类似的事情。

score 1 · Accepted Answer

这里的要点是，图像作为二维颜色数组的理想表示不是图像存储在内存中的方式（颜色分量可以排列在“平面”中，可能存在“填充”等. 所以使用GetPixel-like函数获取像素可能需要一些时间。

那么，如果图像不是“矢量绘制”的结果，这个问题甚至可能毫无意义：想想一张照片：在两个附近的“绿色”之间，你会发现所有的绿色阴影，所以颜色 - 在这种情况下- 不亚于图像本身的编码（2^24、256、16 或 ...）所支持的，因此，除非您对颜色分布感兴趣（它们的使用方式有多么不同），仅仅计算它们是没有意义的。

解决方法可以是：

创建具有“单平面格式”像素的内存位图
使用 BitBlt 或类似方法将您的图像插入该位图（这让操作系统可以从 GPU 进行像素转换，如果有的话）
获取位图位（这使您可以访问存储的值）
在这些值上播放您的“计数算法”（无论是什么）。

请注意，如果您已经知道图像已经是平面格式，则可以避免步骤 1 和 2。

如果你有一个多核系统，步骤 4 也可以分配给不同的线程，图像的每个工作部分。

score 1 · Accepted Answer

您可以使用bitset它允许您设置各个位并具有count功能。

每种颜色都有一个位，每个 RGB 有 256 个值，因此是 256*256*256 位（16,777,216 种颜色）。每 8 位将bitset使用一个字节，因此它将使用 2MB。

使用像素颜色作为索引bitset：

bitset<256*256*256> colours;

for(int pixel: pixels) {
    colours[pixel] = true;
}

colours.count();

这具有线性复杂性。

score 0 · Accepted Answer

这个答案迟到了，但由于这个算法非常快，大约在 2 年或更长时间前开发，当时它真的很重要。3-D 查找表颜色匹配 http://www.ddj.com/cpp/184403257

基本上，它创建了一个 3d 颜色循环表，搜索速度非常快，我做了一些修改以适应我的图像二值化目的，所以我将颜色空间从 ff ff ff 减少到 fff，甚至快了 10 倍. 因为它是开箱即用的，所以我还没有找到任何接近的东西，包括哈希表。

char * creatematcharray(struct rgb_color *palette, int palettesize)
    {
      int rval=16, gval=16, bval=16, len, r, g, b;
      char *taken, *match, *same;
      int i, set, sqstep, tp, maxtp, *entryr, *entryg, *entryb;
      char *table;

      len=rval*gval*bval;

      // Prepare table buffers:
      size_t size_of_table = len*sizeof(char);
      table=(char *)malloc(size_of_table);
      if (table==nullptr) return nullptr;

      // Select colors to use for fill:
      set=0;
      size_t size_of_taken = (palettesize * sizeof(int) * 3) +
          (palettesize*sizeof(char)) + (len * sizeof(char));
      taken=(char *)malloc(size_of_taken);
      same=taken + (len * sizeof(char));
      entryr=(int*)(same + (palettesize * sizeof(char)));
      entryg=entryr + palettesize;
      entryb=entryg + palettesize;
      if (taken==nullptr)
      {
        free((void *)table);
        return nullptr;
      }
      std::memset((void *)taken, 0, len * sizeof(char));
    //  std::cout << "sizes: " << size_of_table << " " << size_of_taken << std::endl;

      match=table;
      for (i=0; i<palettesize; i++)
      {
        same[i]=0;
        // Compute 3d-table coordinates of palette rgb color:
        r=palette[i].r&0x0f, g=palette[i].g&0x0f, b=palette[i].b&0x0f;
        // Put color in position:
        if (taken[b*rval*gval+g*rval+r]==0) set++;
        else same[match[b*rval*gval+g*rval+r]]=1;
        match[b*rval*gval+g*rval+r]=i;
        taken[b*rval*gval+g*rval+r]=1;
        entryr[i]=r; entryg[i]=g; entryb[i]=b;
      }

      // @@@ Fill match_array by steps: @@@
      for (set=len-set, sqstep=1; set>0; sqstep++)
      {
        for (i=0; i<palettesize && set>0; i++)
          if (same[i]==0)
          {
            // Fill all six sides of incremented cube (by pairs, 3 loops):
            for (b=entryb[i]-sqstep; b<=entryb[i]+sqstep; b+=sqstep*2)
              if (b>=0 && b<bval)
                for (r=entryr[i]-sqstep; r<=entryr[i]+sqstep; r++)
                  if (r>=0 && r<rval)
                  { // Draw one 3d line:
                    tp=b*rval*gval+(entryg[i]-sqstep)*rval+r;
                    maxtp=b*rval*gval+(entryg[i]+sqstep)*rval+r;
                    if (tp<b*rval*gval+0*rval+r)
                      tp=b*rval*gval+0*rval+r;
                    if (maxtp>b*rval*gval+(gval-1)*rval+r)
                      maxtp=b*rval*gval+(gval-1)*rval+r;
                    for (; tp<=maxtp; tp+=rval)
                      if (!taken[tp])
                        taken[tp]=1, match[tp]=i, set--;
                  }
            for (g=entryg[i]-sqstep; g<=entryg[i]+sqstep; g+=sqstep*2)
              if (g>=0 && g<gval)
                for (b=entryb[i]-sqstep; b<=entryb[i]+sqstep; b++)
                  if (b>=0 && b<bval)
                  { // Draw one 3d line:
                    tp=b*rval*gval+g*rval+(entryr[i]-sqstep);
                    maxtp=b*rval*gval+g*rval+(entryr[i]+sqstep);
                    if (tp<b*rval*gval+g*rval+0)
                      tp=b*rval*gval+g*rval+0;
                    if (maxtp>b*rval*gval+g*rval+(rval-1))
                      maxtp=b*rval*gval+g*rval+(rval-1);
                    for (; tp<=maxtp; tp++)
                      if (!taken[tp])
                        taken[tp]=1, match[tp]=i, set--;
                  }
            for (r=entryr[i]-sqstep; r<=entryr[i]+sqstep; r+=sqstep*2)
              if (r>=0 && r<rval)
                for (g=entryg[i]-sqstep; g<=entryg[i]+sqstep; g++)
                  if (g>=0 && g<gval)
                  { // Draw one 3d line:
                    tp=(entryb[i]-sqstep)*rval*gval+g*rval+r;
                    maxtp=(entryb[i]+sqstep)*rval*gval+g*rval+r;
                    if (tp<0*rval*gval+g*rval+r)
                      tp=0*rval*gval+g*rval+r;
                    if (maxtp>(bval-1)*rval*gval+g*rval+r)
                      maxtp=(bval-1)*rval*gval+g*rval+r;
                    for (; tp<=maxtp; tp+=rval*gval)
                      if (!taken[tp])
                        taken[tp]=1, match[tp]=i, set--;
                  }
          }
      }
      free((void *)taken);`enter code here`
      return table;
    }

score 0 · Accepted Answer

答案：unordered_map

根据我的测试，我使用 unordered_map。

您应该进行测试，因为您的编译器/库可能会表现出不同的性能注释掉#define USEHASH以使用 map 代替。

在我的机器上，vanilla unordered_map（一种哈希实现）的速度大约是 map 的两倍。由于不同的编译器，库可以有很大的不同，你必须测试看看哪个更好。在生产中，我在应用程序第一次启动时构建一个假图像，在其上运行两种算法并计时，保存一个指示哪个更快，然后优先使用该机器上的所有后续启动。这很挑剔，但是，用户的时间对他们来说很宝贵。

对于具有 12,106,244 像素（约 12 兆像素，不是拼写错误）和 11,857,131 种不同颜色（也不是拼写错误）的 DSLR 图像，地图大约需要 14 秒，而无序地图大约需要 7 秒：

测试代码：

#define USEHASH 1
#ifdef USEHASH
#include <unordered_map>
#endif

size = im->xw * im->yw;
#ifdef USEHASH
// unordered_map is about twice as fast as map on my mac with qt5
// --------------------------------------------------------------
#include <unordered_map>
    std::unordered_map<qint64, unsigned char> colors;
    colors.reserve(size); // pre-allocate the hash space
#else
    std::map<qint64, unsigned char> colors;
#endif

...使用其中之一是在循环中，我在对应于图像像素的 16 位 RGB 值的 64 位变量中构建 0RGB 的 48 位值，如下所示：

for (i=0; i<size; i++)
{
    pel = BUILDPEL(i); // macro just shovels 0RGB into 64 bit pel from im
                       // You'd do the same for your image structure
                       // in whatever way is fastest for you
    colors[pel] = 1;
}
cc = colors.size();
// time here: 14 secs for map, 7 secs for unordered_map with
// 12,106,244 pixels containing 11,857,131 colors on 12/24 core,
// 3 GHz, 64GB machine.

c++ - 更快的算法来检查图像中的颜色

8 回答 8

Related

Reference