C#: Seeking fast datastructure to add pixels to a

Question

In my application I read RGB pixel values from several images using fast unmanaged code and then convert them to HSB colors. Now I'd like to build an HSB histogram using the following partitions:

• Hue: 18 partitions, resulting in intervals of 20 from 0...360
• Saturation: 3 partitions, resulting in intervals of 0,33 from 0...1
• Brightness: 3 partitions, resulting in intervals of 0,33 from 0...1

So my histogram has a total of 18*3*3=162 partitions (bins) which consist of the lower interval borders for each channel:

• 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]

I implemented this pretending that each bin would be an HSB color itself. So I calculated the bin interval borders, created HsbColor instances from those values and put the colors (wrapped in the HsbHistogramBin class) in a simple list. When adding a new HsbColor to my histogram, I use the following code to determine which bin I need to increment:

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++;
}

Obviously this is way too slow. In a worst-case scenario, each pixel needs 162 iterations to find its bin which results in at least millions of iterations for one single image.

My question is: How can I speed this data structure up so that I can immediately find the right bin for my pixels? A simple array with the length of 162 might work but how do I calculate the right bin index for a given pixel that isn't yet reduced to the mentioned partitions and might contain values like [259.234, 0.5634, 0.90534]?

Answer 1

You can convert your HSV number into one unsigned long like so:

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

This is your bin index.

Answer 2

Why not just simply use a 3 dimensional array? Like so:

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]++;

NB: I'm assuming here that your total pixel count (more precisely, the maximum number of pixels that will fall into 1 bin) will not exceed int.MaxValue. Otherwise, consider using long datatype for the histogram instead of int.