C #: поиск быстрой структуры данных для добавления пикселей в секционированную гистограмму HSB

В моем приложении я считываю значения пикселей RGB из нескольких изображений с помощью быстрого неуправляемого кода, а затем конвертирую их в цвета HSB. Теперь я хочу построить гистограмму HSB, используя следующие разделы:

  • Оттенок: 18 разделов, что соответствует 20 интервалам от 0 до 360.
  • Насыщенность: 3 раздела, в результате получаются интервалы 0,33 от 0 до 1.
  • Яркость: 3 раздела, что дает интервалы 0,33 от 0 до 1.

Итак, моя гистограмма имеет в общей сложности 18 * 3 * 3 = 162 раздела (бинов), которые состоят из нижних границ интервала для каждого канала:

  • 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. Поэтому я вычислил границы интервала бинов, создал экземпляры HsbColor из этих значений и поместил цвета (завернутые в класс HsbHistogramBin) в простой список. При добавлении нового HsbColor к моей гистограмме я использую следующий код, чтобы определить, какую ячейку мне нужно увеличить:

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 итерации для поиска своего бина, что приводит к минимум миллионам итераций для одного изображения.

У меня вопрос: как мне ускорить эту структуру данных, чтобы я мог сразу найти подходящую ячейку для своих пикселей? Простой массив с длиной 162 может работать, но как мне вычислить правильный индекс ячейки для данного пикселя, который еще не сокращен до упомянутых разделов и может содержать значения вроде [259.234, 0.5634, 0.90534]?


c# image-processing histogram data-structures buckets
person Shackles    schedule 17.04.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Почему бы просто не использовать трехмерный массив? Вот так:

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: здесь я предполагаю, что ваше общее количество пикселей (точнее, максимальное количество пикселей, которые попадут в 1 ячейку) не будет превышать int.MaxValue. В противном случае рассмотрите возможность использования для гистограммы типа данных long вместо int.

person Bart    schedule 17.04.2011
comment
Спасибо, это чистое и простое решение, достаточно быстрое для моих нужд! - person Shackles; 18.04.2011
comment
NB: на самом деле имеет смысл использовать uint (или ulong) вместо int, поскольку ячейки никогда не будут содержать отрицательное количество пикселей. Это также удваивает количество пикселей, которые гистограмма может обрабатывать без максимального увеличения. - person Bart; 18.04.2011

arrow_upward
0
arrow_downward

Вы можете преобразовать свой номер HSV в один длинный беззнаковый код следующим образом:

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

Это ваш индекс корзины.

person Andrew Shepherd    schedule 17.04.2011