Как найти наиболее распространенный тип int в 2d массиве целых?

Question

ОК, так что я только начинаю думать о том, как реализовать новый графический плагин для Paint.NET, и мне нужно знать, как найти наиболее распространенное целое число в двумерном массиве целых чисел. Есть ли встроенный в C # способ сделать это? Или у кого-нибудь есть отличный способ сделать это?

Массив будет выглядеть примерно так:

300 300 300 300 300 300 300
  0 150 300 300 300 300 300
  0   0 150 300 300 300 300
  0   0   0   0 300 300 300
  0   0   0   0 150 300 300
  0   0   0   0   0 150 300
  0   0   0   0   0   0 300

Мне нужно знать, что 300 является наиболее распространенным числом в массиве. Если «самого распространенного» нет, просто верните номер центра (уменьшение массива всегда будет нечетным x нечетным) 0.

Я буду реализовывать это с использованием алгоритма "грубой силы", если вы, эксперты, не сможете придумать что-то более быстрое.

Любая помощь будет принята с благодарностью.

Спасибо!

РЕДАКТИРОВАТЬ: Подробнее ...

Значения почти всегда будут ОЧЕНЬ разнообразными (более разнообразными, чем у моего примера массива). Значения будут в диапазоне 0-360. Размер массива будет от 5x5 до 17x17 в зависимости от скорости алгоритма. Результат будет рассчитан один раз для каждого пикселя в большом изображении ... так что чем быстрее, тем лучше. ;)

Answer 1

Это как минимум O (n * m), как бы вы его ни разрезали - вам придется хотя бы раз взглянуть на каждую ячейку. Экономия - это место, где вы накапливаете счет каждого значения, прежде чем искать наиболее распространенное; если ваши целые числа изменяются в относительно небольшом диапазоне (скажем, uint16), то вы можете просто использовать плоский массив вместо карты.

Полагаю, вы также можете сохранить текущий счет x , y текущего верхнего и второго ближайшего кандидата на "наиболее распространенный" и ранний выход, как только вы ' осталось меньше (n * m) - (xy) ячеек, так как в этот момент участник, занявший второе место, не сможет опередить лучшего кандидата.

Такие целочисленные операции довольно быстрые; даже для мегапиксельного изображения алгоритм перебора должен занимать всего пару миллисекунд.

Я заметил, что вы отредактировали свой первоначальный вопрос, чтобы сказать, что значение пикселей от 0..255 - в этом случае, безусловно, используйте простой плоский массив; он достаточно мал, чтобы легко помещаться в d1-кэш, и поиск в плоском массиве очень быстр.

[править]: Работа со случаем «нет наиболее распространенного числа» очень проста после того, как вы построите массив гистограмм: все, что вам нужно сделать, это пройтись по нему, чтобы найти «большинство» и «вторые наиболее» общие числа; если они одинаково часты, то по определению нет ни одного наиболее распространенного.

const int numLevels = 360; // you said each cell contains a number [0..360)
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i"
int mostCommon = 0, runnerUp = 0;
for (int i = 1 ; i < numLevels ; ++i)
{
  if ( levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon] )
  {
    runnnerUp = mostCommon;
    mostCommon = i;
  }
}

if ( levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp] )
{
   return mostCommon;
}
else
{
   return CenterOfInputData; // (something like InputData[n/2][m/2])
}

Answer 2

как бы я сделал что-то подобное в C #?

Примерно так:

Dictionary<int, int> d = new Dictionary<int, int>();
foreach (int value in matrix)
{
 if (!d.ContainsKey(value))
  d.Add(value, 1);
 else
  d[value] = d[value] + 1;
}
KeyValuePair<int, int> biggest = null;
foreach (KeyValuePair<int, int> found in d)
{
  if ((biggest == null) || (biggest.Value < found.Value))
    biggest = found;
}

Answer 3

Посмотрите на код LocalHistogramEffect в Paint.NET, в частности на LocalHistorgramEffect.RenderRect.

Я обхожу входное изображение, сохраняя гистограмму интенсивностей для каждого исходного пикселя с помощью 'r' пикселей конечного пикселя. По мере прохождения выходных пикселей он добавляет передний край к гистограмме и вычитает задний край. Он хорошо обрабатывает все крайние случаи и довольно быстр. Это основа для эффектов «Медиана», «Расфокусировать», «Контур» и «Удалить шум».

Адаптировать его для поддержки оттенка вместо интенсивности RGB было бы довольно тривиально.

Производительность довольно хорошая, и для ваших целей она работает в O (r ^ 2 + w r + n w), где r - радиус, w - ширина изображения, и n - количество уровней в гистограмме.

-tjackson

Answer 4

Ваше изображение:

300+ 300+ 300+ 300 300 300 300
  0+ 150+ 300+ 300 300 300 300
  0+   0+ 150+ 300 300 300 300
  0    0    0    0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

Помеченные (+) цифры - это ваше окно. w, h ваши размеры окна. Примените сортировку ведра (как предлагали другие, поскольку ваши диапазоны значений весьма ограничены). Не снижайте оценку на полпути, как подсказывает Crashworks . Не бросайте свой результат еще. Это первый шаг.

300- 300- 300- 300 300 300 300
  0. 150. 300. 300 300 300 300
  0.   0. 150. 300 300 300 300
  0+   0+   0+   0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

Сдвинь окно. Вместо добавления вычтите сегменты в последней строке / столбце, которые вы передали, и добавьте новые сегменты. Таким образом, вы проверяете каждый пиксель 2 (w + h) раза, то есть когда он пересекает границу окна, а не w * h раз, то есть когда этот пиксель находится в окне, в наивной реализации.

Другими словами, вам нужно переместить ваше окно так:

|  ^->|  ^
|  |  |  |
|  |  |  |
V->|  V->|

Полагаю, вы пытаетесь реализовать нелинейный сверточный фильтр.

Исправления приветствуются.

Answer 5

Если скорость - ваша главная задача, не используйте словарь. Палка с массивом байтов. Попробуйте это:

// stores hit counts (0-360)
short[] hitCounts = new short[361];

// iterate through 2d array and increment hit counts
for (int i = 0; i < toEvaluate.Length; i++)
{
    for (int j = 0; j < toEvaluate[i].Length; j++)
        hitCounts[toEvaluate[i][j]]++;
}

int greatestHitCount = 0; // the hit count of the current greatest value
int greatest = -1; // the current greatest valeu

// iterate through values (0-360) and evalute hit counts
for (int i = 0; i < hitCounts.Length; i++)
{
    // the hit count of hitCounts[i] is higher than the current greatest hit count value
    if (hitCounts[i] > greatestHitCount)
    {
        greatestHitCount = vals[i]; // store the new hit count
        greatest = i; // store the greatest value
    }
    // there is already a value with the same hit count (which is the greatest)
    else if (hitCounts[i] == greatestHitCount)
        greatest = -1; // there are more than one value, we can't use this if it ends up being the greatest
}

if (greatest >= 0) // no greatest value found
    return greatest;

// figure out the middle x and y value
int x = (toEvaluate.Length - 1) / 2 + 1;
int y = (toEvaluate[x].Length - 1) / 2 + 1;

// return the value at the center of the 2d array as the value
return toEvaluate[x][y];

Когда скорость становится проблемой читабельности, вы в конечном итоге получаете некрасивый код. Вышесказанное может определенно выиграть от рефакторинга (следовательно, переусердствовать с комментариями), но оно должно работать быстро. Если он недостаточно быстр, вы можете добиться еще большей оптимизации, переместив его в неуправляемый код.

Answer 6

Одним из вариантов является LINQ - немного неэффективно, но хорошо для небольших массивов:

    var max = (from cell in data.Cast<int>()
               group cell by cell into grp
               select new { Key = grp.Key, Count = grp.Count() } into agg
               orderby agg.Count descending
               select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

Или с зазубренным массивом:

    var max = (from row in data
              from cell in row
              group cell by cell into grp
              select new {Key = grp.Key, Count = grp.Count()} into agg
              orderby agg.Count descending
              select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

В действительности я бы, вероятно, использовал словарь / счетчик. Этот пример без LINQ, просто «потому что»:

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int value in data)
    {
        int count;
        counts.TryGetValue(value, out count);
        counts[value] = count + 1;
    }
    int maxCount = -1, maxValue = 0;
    foreach (KeyValuePair<int, int> pair in counts)
    {
        if (pair.Value > maxCount)
        {
            maxCount = pair.Value;
            maxValue = pair.Key;
        }
    }
    Console.WriteLine(maxCount + ": " + maxValue);

Answer 7

Все, что я предложу, для любого алгоритма, который проверяет каждую ячейку (что в значительной степени соответствует ожиданиям), делает две дополнительные вещи:

1.) Убедитесь, что процедура завершается при подсчете наиболее распространенного в настоящее время значения> (M x N / 2). Если что-то покрывает> 50% вашей сетки, то это наиболее распространенное значение, продолжать не нужно. Если ваша программа должна быть правильной в большинстве случаев, вы можете понизить процент и рассматривать его как эвристику. Вы могли бы даже выполнить какой-то анализ, который выполнил бы что-то вроде: если охват> 37,6%, то в 99,9% случаев это будет наиболее распространенное значение, а затем использовать этот процент.

2.) Если есть какой-либо способ определить, с какой стороны, угла или общего местоположения (внешние края, середина и т. Д.) Наиболее вероятные значения, то вы можете сканировать в том порядке, который вместе с Оптимизация 1, приведенная выше, может сбрить большую часть вашего сканирования. Например, в вашем примере верхний правый угол имеет большое значение для общего значения. Если это было определено какой-то эвристикой, вы могли бы сканировать сверху вниз в левом углу каким-то образом. Если шаблон сканирования сложный, предварительно сгенерируйте его.

Answer 8

Майкл избил меня до должности, но я бы поступил так же:

        int MaxValueIn2dArray(int[,] matrix)
    {
        var d = new int[360];
        int MaxValue = 0;
        for (int x = 0; x <= matrix.GetUpperBound(0); x++)
        {
            for (int y = 0; y <= matrix.GetUpperBound(1); y++)
            {
                d[matrix[x, y]]++;
            }
        }
        foreach (int value in d)
        {
            if (value > MaxValue) MaxValue = value;
        }
        return MaxValue;
    }

Это должно быть оптимизировано для ваших конкретных потребностей.