数据结构——c#:寻求快速的数据结构来向分区的HSB直方图添加像素

Question

在我的应用程序中，我使用快速非托管代码从几个图像读取RGB像素值，然后将它们转换为HSB颜色。现在我想使用以下分区构建HSB直方图:

• Hue: 18个分区，导致间隔为20从0到360
• 饱和度:3个分区，导致间隔0,33从0…1
• 亮度:3个分区，从0到1的间隔为0,33

所以我的直方图共有18*3*3=162个分区(bin)，它们由每个通道的较低间隔边界组成:

• Bin1: [0,0,0]
• Bin2: [0,0,0.33]
• Bin3: [0,0,0.66]
• Bin4: [0,0.33, 0]
• Bin5: [0,0.33, 0.33]
• …
• Bin162: [340, 0.66, 0.66]

我实现这个假设每个箱子将是一个HSB颜色本身。因此，我计算了bin间隔边界，根据这些值创建了HsbColor实例，并将颜色(包装在HsbHistogramBin类中)放在一个简单的列表中。在向直方图中添加新的HsbColor时，我使用以下代码来确定需要增加哪个bin:

private HsbHistogramBin FindBin(HsbColor color)
{
    HsbHistogramBin bin = null;
    bool foundBin = false;
    for (int i = Bins.Count - 1; i >= 0; i--)
    {
        bin = Bins[i];
        if (bin.Color.Hue > color.Hue)
            continue;
        if (bin.Color.Saturation > color.Saturation)
            continue;
        if (bin.Color.Brightness > color.Brightness)
            continue;
        foundBin = true;
        break;
    }
    return foundBin ? bin : null;
}
public void AddColor(HsbColor color)
{
    FindBin(color).Value++;
}

显然这太慢了。在最坏的情况下，每个像素需要162次迭代才能找到它的bin，这导致单个图像至少需要数百万次迭代。

我的问题是:我如何加快这个数据结构，以便我可以立即找到我的像素正确的bin ?一个长度为162的简单数组可能可以工作，但是我如何计算一个给定像素的正确bin索引，该像素尚未缩小到上述分区，并且可能包含像[259.234,0.5634,0.90534]这样的值?

Answer 1

为什么不直接使用三维数组呢?像这样:

int[,,] histogram = new int[18, 3, 3];
// initialize to 0
for(int h = 0; h < 18; h++) {
  for(int s = 0; s < 3; s++) {
    for(int b = 0; b < 3; b++) {
      histogram[h, s, b] = 0;
    }
  }
}
// foreach pixel...
HsbColor c = ... // color of pixel
int h = (int)(c.Hue / 20);
int s = (int)(c.Saturation * 3);
int b = (int)(c.Brighthess * 3);
// take care of boundary cases (Hue, Saturation or Brightness maxed out)
if(h >= 18) h = 17;
if(s >= 3) s = 2;
if(b >= 3) b = 2;
histogram[h, s, b]++;

注:我在这里假设您的总像素数(更准确地说，将落入1个bin的最大像素数)不会超过int.MaxValue。否则，考虑使用long数据类型来代替int。

Answer 2

您可以将HSV号码转换为unsigned long，如下所示:

ulong colorLookupValue = (color.Hue/18) * 9 + (ulong)((color.Saturation*3) * 3) + (ulong)(color.Brightness * 3)