¿Cómo encontrar la int más común en una matriz de 2d de ints?

Question

OK, entonces estoy empezando a pensar cómo implementar un nuevo complemento gráfico para Paint.NET y tendré que saber cómo encontrar el número entero más común en una matriz 2D de enteros. ¿Hay una forma integrada en C# para hacer esto? O, ¿Alguien tiene una forma elegante de hacerlo?

La matriz se verá algo como esto:

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 

que tendría que saber que 300 es el número más común en la matriz. Si no hay un "más común", simplemente devuelva el número del centro (las disminuciones del conjunto serán siempre impares x impar) 0.

Voy a implementar esto usando un algoritmo de "fuerza bruta" a menos que puedan venir expertos con algo más rápido.

Cualquier ayuda sería muy apreciada.

Gracias!

EDIT: Más información ...

Los valores casi siempre va a ser muy diversa (más diverso que mi ejemplo array). Los valores estarán en el rango de 0-360. El tamaño de la matriz será de 5x5 a aproximadamente 17x17 dependiendo de la velocidad del algoritmo. El resultado se calculará una vez por cada píxel en una imagen grande ... así que más rápido es mejor. ;)

Answer 1

Eche un vistazo al código LocalHistogramEffect en Paint.NET, especialmente LocalHistorgramEffect.RenderRect.

I recorre la imagen de entrada, manteniendo un histograma de intensidades para cada píxel fuente con 'r' píxeles del píxel de destino. A medida que se cruzan los píxeles de salida, agrega el borde anterior al histograma y resta el borde posterior. Maneja bien todos los casos extremos, y es bastante rápido. Es la base de los efectos Median, Unfocus, Outline y Remove Noise.

Adaptar esto para apoyar Hue en lugar de la intensidad RGB sería bastante trivial.

El rendimiento es bastante bueno, y para sus fines opera en O (r^2 + w r + n w), donde r es el radio, w es el ancho de la imagen, y n es el número de niveles en el histograma.

-tjackson

Answer 2

Es al menos O (n * m) de cualquier forma que lo cortes: tendrás que mirar cada celda al menos una vez. El lugar para economizar es donde acumula los recuentos de cada valor antes de buscar los más comunes; si sus enteros varían en un rango relativamente pequeño (son uint16, digamos), entonces podría simplemente usar una matriz plana en lugar de un mapa.

supongo que también podría mantener una cuenta corriente x, y de la parte superior actual y la segunda más cercana candidato a "más común" y comienzos de salida tan pronto como se haya menos de (N * m) - (xy) celdas a la vista, ya que en ese momento no hay forma de que el subcampeón supere al candidato principal.

Las operaciones de enteros como esta son bastante rápidas; incluso para una imagen megapíxel, el algoritmo de fuerza bruta solo debería tomar un par de milisegundos.

Me di cuenta de que ha editado su pregunta original para decir que el valor de los píxeles de 0..255 - en ese caso, definitivamente va con una matriz plana simple; eso es lo suficientemente pequeño como para caber fácilmente en el dcache l1 y una búsqueda en una matriz plana es muy rápida.

[editar]: Tratar con el caso "no hay ningún número más común" es muy simple una vez que se ha construido el conjunto de histogramas: todos tienen que hacer es caminar a través de él para encontrar el "más" y "segundo la mayoría de los "números comunes"; si son igualmente frecuentes, entonces, por definición, no hay nadie más común.

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 3

¿Cómo voy a hacer algo como esto en C#?

Algo como esto:

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 4

Una opción es LINQ - un poco ineficiente, pero está bien para no grandes arreglos:

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); 

o con una matriz escalonada:

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); 

En realidad, probablemente usaría un diccionario/recuento. Este ejemplo sin LINQ, simplemente "porque":

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 5

Si la velocidad es su principal preocupación, no utilice un diccionario. Quédate con una matriz de bytes. Pruebe esto:

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

Cuando la velocidad se convierte en una preocupación sobre la legibilidad, termina con el código necesariamente feo. Lo anterior definitivamente podría beneficiarse de la refactorización (por lo tanto, exagerar los comentarios), pero debería ejecutarse rápidamente. Si no es lo suficientemente rápido, puede obtener aún más optimizaciones moviéndolo a un código no administrado.

Answer 6

Michael me pegó al poste, pero me gustaría hacer lo mismo, algo como esto:

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

tendría que ser optimizado para sus necesidades particulares.

Answer 7

Su imagen:

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 

números marcados (+) son su ventana. w, h son las dimensiones de tu ventana. Aplique bucket sorting (como otras personas sugirieron porque sus rangos de valores son bastante limitados). No corte su evaluación hasta la mitad como sugiere Crashworks. No arrojes tu resultado todavía. Este es el primer paso.

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 

Cambie su ventana. En lugar de agregar, reste los cubos en la última fila/columna que pasó y agregue los nuevos cubos. De esta forma, examina cada píxel 2 (w + h) veces, es decir, cuando cruza el límite de la ventana, en lugar de w * h veces, es decir, mientras ese píxel está en la ventana, en una implementación ingenua.

En otras palabras, es necesario para mover la ventana como esta:

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

Asumo que está tratando de implementar un filtro de convolución no lineal.

Correcciones de bienvenida.

Answer 8

Todo lo que puedo ofrecer es para cualquier algoritmo que comprueba cada célula (que es más o menos lo que se espera de hacer) hacer dos cosas adicionales:

1.) Asegúrese de que la rutina sale cuando el recuento para el valor actualmente más común> (M x N/2). Si algo tiene> 50% de cobertura en su grilla, entonces es el valor más común, no necesita continuar. Si su rutina solo necesita ser correcta la MAYOR parte del tiempo, entonces puede reducir el porcentaje y tratarlo como una heurística. Incluso podría ejecutar algún análisis que arroje algo así como si la cobertura es> 37.6% luego el 99.9% del tiempo será el valor más común y luego use ese porcentaje.

2.) Si hay alguna manera de poder determinar en qué lado, esquina o ubicación general (bordes exteriores, centro, etc.) es probable que se encuentren los valores más comunes, podría escanear en ese orden, que juntos con la optimización 1 anterior podría reducir gran parte de su escaneo. Por ejemplo, en su ejemplo, la parte superior derecha es pesada en el valor común. Si esto era determinable por alguna heurística, podrías escanear desde la parte superior derecha a la inferior izquierda de alguna manera. Si el patrón de escaneo necesario es complejo, pregenerelo.