C＃：寻求快速的数据结构以将像素添加到分区的HSB直方图 [英] C#: Seeking fast datastructure to add pixels to a partitioned HSB histogram
问题描述
在我的应用程序中，我使用快速非托管代码从多个图像中读取RGB像素值，然后将其转换为HSB颜色。现在我想使用以下分区来构建HSB直方图：
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:
- 色相：18个分区，导致从0开始的间隔为20。 3.60
- 饱和度：3分区，导致0 ... 1的间隔0,33
- 亮度：3个分区，导致间隔0,33从0 ... 1
所以我的直方图总共有18 * 3 * 3 = 162个分区bin）由每个频道的较低间隔边框组成：
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] $ b Bin2：[0，0，0.33]
- Bin3：[0，0，0.66]
- Bin4： $ 0.99
- Bin5：[0，0.33，0.33]
- ...
- Bin162 ：[340，0.66，0.66]
- 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]
我实现了这个假设，每个bin都将是HSB颜色。所以我计算bin间隔边界，从这些值创建HsbColor实例，并将颜色（包装在HsbHistogramBin类中）放在一个简单的列表中。
当向我的直方图添加一个新的HsbColor时，我使用以下代码来确定需要增加哪个bin：
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++;
}
显然这太慢了。在最坏的情况下，每个像素需要162次迭代来找到它的bin，这样可以为一个图像产生至少数百万次迭代。
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.
我的问题是：如何加速这个数据结构，以便我可以立即找到我的像素的正确的bin？长度为162的简单数组可能有效，但是如何计算尚未减少到上述分区的给定像素的正确的bin索引，并且可能包含[259.234,0.5634,0.90534]等值。
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]?
推荐答案
为什么不简单地使用3维数组？像这样：
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]++;
注意：我在这里假设您的总像素数（更准确地说，最大像素数将落入1 bin）不会超过 int.MaxValue 。否则，请考虑对直方图使用 long 数据类型，而不是 int 。
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.
这篇关于C＃：寻求快速的数据结构以将像素添加到分区的HSB直方图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
