Wie findet man den häufigsten int in einem 2d-Array von ints?

Question

OK, so dass ich gerade anfangen zu denken, wie ein neues grafisches Plugin für Paint.NET zu implementieren, und ich muss wissen, wie die häufigste ganze Zahl in einem 2d-Array von Ganzzahlen zu finden. Gibt es eine in C# integrierte Möglichkeit, dies zu tun? Oder, hat jemand einen glatten Weg, es zu tun?

Das Array wird etwa so aussehen:

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

Ich müsste wissen, dass 300 die häufigste Zahl in der Reihe ist. Wenn es keine "häufigste" dann geben Sie einfach die zentrale Nummer (die Array-Dimintionen werden immer ungerade x ungerade) 0.

Ich werde dies mit einem "Brute-Force"-Algorithmus implementieren, es sei denn, ihr Experten könnt euch etwas Schnelleres einfallen lassen.

Für jede Hilfe wären wir sehr dankbar.

Danke!

EDIT: Mehr Informationen...

Die Werte werden fast immer SEHR vielfältig sein (noch vielfältiger als mein Beispielfeld). Die Werte werden im Bereich von 0-360 liegen. Die Größe des Arrays wird 5x5 bis etwa 17x17 betragen, je nach Geschwindigkeit des Algorithmus. Das Ergebnis wird für jedes Pixel in einem großen Bild einmal berechnet... schneller ist also besser. ;)

Answer 1

Werfen Sie einen Blick auf den LocalHistogramEffect-Code in Paint.NET, insbesondere auf LocalHistorgramEffect.RenderRect.

I durchläuft das Eingabebild, wobei ein Histogramm der Intensitäten für jedes Quellpixel innerhalb von 'r' Pixeln des Zielpixels erstellt wird. Während die Ausgangspixel durchlaufen werden, wird die vordere Kante zum Histogramm hinzugefügt und die hintere Kante subtrahiert. Es behandelt alle Randfälle gut und ist recht schnell. Es ist die Grundlage für die Effekte Median, Unfokussieren, Umriss und Rauschen entfernen.

Eine Anpassung zur Unterstützung von Farbtönen anstelle von RGB-Intensität wäre ziemlich trivial.

Die Leistung ist recht gut, und für Ihre Zwecke arbeitet es in O(r^2+w r+n w), wobei r der Radius, w die Breite des Bildes und n die Anzahl der Ebenen im Histogramm ist.

-tjackson

Answer 2

Michael ist mir zuvorgekommen, aber ich würde es ähnlich machen, etwa so:

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

Es müsste für Ihre speziellen Bedürfnisse optimiert werden.

Answer 3

Alles, was ich vorschlage, ist, dass jeder Algorithmus, der jede Zelle überprüft (was so ziemlich das ist, was man erwarten würde), zwei zusätzliche Dinge tut:

1.) Vergewissern Sie sich, dass die Routine beendet wird, wenn der Zähler für den aktuell häufigsten Wert > (M x N / 2) ist. Wenn etwas in Ihrem Raster eine Abdeckung von >50% hat, dann ist es der häufigste Wert und Sie brauchen nicht weiterzumachen. Wenn Ihre Routine nur die meiste Zeit richtig sein muss, können Sie den Prozentsatz herabsetzen und es als Heuristik behandeln. Sie könnten sogar eine Analyse durchführen, die etwas ausspuckt wie: Wenn die Abdeckung >37,6 % ist, dann ist es in 99,9 % der Fälle der häufigste Wert, und diesen Prozentsatz dann verwenden.

2.) Wenn Sie irgendwie feststellen können, auf welcher Seite, in welcher Ecke oder an welcher allgemeinen Position (äußere Ränder, Mitte usw.) die häufigsten Werte zu finden sind, könnten Sie in dieser Reihenfolge scannen, was zusammen mit der obigen Optimierung 1 eine Menge Scanarbeit einsparen könnte. In Ihrem Beispiel ist zum Beispiel die obere rechte Seite stark von häufigen Werten betroffen. Wäre dies durch eine Heuristik ermittelbar, könnte man in gewisser Weise von rechts oben nach links unten scannen. Wenn das benötigte Scanning-Muster komplex ist, sollten Sie es vorgenerieren.