Wenn Sie eine genaue Zahl benötigen, müssen Sie alle Pixel durchlaufen. Wahrscheinlich ist die Speicherung der Farbe und die Zählung in einem Hash der beste Weg, wegen der geringen Farbigkeit zu gehen.
Das Verwenden der Color.ToArgb () im Hash anstelle des Farbobjekts wäre wahrscheinlich auch eine gute Idee.
Wenn Geschwindigkeit eine große Rolle spielt, möchten Sie auch keine Funktion wie GetPixel (x, y) verwenden, sondern stattdessen versuchen, Blöcke gleichzeitig zu bearbeiten. Wenn Sie können, erhalten Sie einen Zeiger auf den Anfang des Bildspeichers und machen Sie es unsicher.
Ich habe so etwas noch nie implementiert, aber wie ich es sehe, eine primitive Implementierung:
Bei einem 24-Bit-Bild ist die maximale Anzahl der Farben, die das Bild haben kann, das Minimum von (2 ^ 24, Pixelanzahl des Bildes).
Sie müssen nur aufzeichnen, ob eine bestimmte Farbe gezählt wurde, nicht wie oft sie gezählt wurde. Das bedeutet, dass Sie 1 Bit benötigen, um zu protokollieren, ob jede Farbe gezählt wird. Das sind 2 MB Speicher. Iterieren Sie durch die Pixel, stellen Sie das entsprechende Bit in Ihrer 2-MB-Farbsatzkarte ein. Am Ende durchlaufen Sie die Farbpalette, indem Sie die gesetzten Bits zählen (wenn Sie Glück haben, haben Sie eine POPCNT-Anweisung, um dies zu unterstützen).
Bei kleineren Bildern und sicherlich niedrigeren Farbtiefen sollten Sie besser eine Farbtabelle behalten und für jede Farbe im Bild zählen.
Die meisten Leute hier haben Lösungen vorgeschlagen, die wahrscheinlich schnell sein werden (eigentlich ist die, die nur 2 MB verwendet, wahrscheinlich akzeptabel in Bezug auf die Speichernutzung und sehr schnell; die mit dem Hash könnte noch schneller sein, aber es wird definitiv mehr als verwenden 2 MB Speicher). Die Programmierung ist immer ein Kompromiss zwischen Speicherverbrauch und CPU-Zeit. Sie können Ergebnisse in der Regel schneller erhalten, wenn Sie bereit sind, mehr Arbeitsspeicher zu "verschwenden", oder Sie können die Ergebnisse langsamer erhalten, indem Sie mehr Rechenzeit "verschwenden", was Ihnen jedoch normalerweise viel Speicher spart.
Hier ist eine Lösung, die bisher niemand vorgeschlagen hat. Es ist wahrscheinlich dasjenige, das am wenigsten Speicher kostet (Sie können es optimieren, so dass es kaum mehr Speicher benötigt als notwendig ist, um das Bild im Speicher zu halten, das Bild wird jedoch verändert, obwohl Sie es möglicherweise zuerst kopieren müssen). Ich bezweifle, dass es die Hash-oder Bit-Maske-Lösung in der Geschwindigkeit schlagen kann, es ist nur interessant, wenn Speicher Ihre größte Sorge ist.
Sortieren Sie die Pixel im Bild nach Farbe. Sie können einfach jedes Pixel in eine 32-Bit-Zahl umwandeln und 32-Bit-Zahlen miteinander vergleichen, wobei eine Zahl kleiner als eine andere, größer oder gleich ist. Wenn Sie Quicksort verwenden, wird kein zusätzlicher Speicherplatz für die Sortierung benötigt, mit Ausnahme von zusätzlichem Stapelspeicherplatz. Wenn Sie Shellsort verwenden, wird überhaupt kein zusätzlicher Speicher benötigt (obwohl Shellsort viel langsamer als Quicksort ist).
int num = (ROT & lt; & lt; 16) + (GRÜN & lt; & lt; 8) + BLAU;
Sobald Sie die Pixel so sortiert haben (was bedeutet, dass Sie sie innerhalb des Bildes neu angeordnet haben), sind alle Pixel der gleichen Farbe immer nebeneinander. So können Sie nur einmal über das Bild iterieren und schauen, wie oft sich die Farbe ändert. Z.B. Sie speichern die aktuelle Farbe des Pixels bei (0, 0) und initiieren einen Zähler mit dem Wert 1. Als nächstes gehen Sie zu (0, 1). Wenn es die gleiche Farbe wie zuvor hat, nichts zu tun, fahren Sie mit dem nächsten Pixel (0, 2) fort. Wenn dies jedoch nicht der Fall ist, erhöhen Sie den Zähler um eins und merken Sie sich die Farbe dieses Pixels für die nächste Iteration.
Sobald Sie das letzte Pixel betrachtet haben (und möglicherweise den Zähler erneut erhöht haben, wenn es nicht dasselbe wie das zweitletzte Pixel war), enthält der Zähler die Anzahl der eindeutigen Farben.
Das Iterieren über alle Pixel mindestens einmal ist in jedem Fall erforderlich, unabhängig von der Lösung. Es hat also keinen Einfluss darauf, dass diese Lösung langsamer oder schneller als andere Lösungen ist. Die Geschwindigkeit dieses Algorithmus hängt davon ab, wie schnell Sie die Pixel des Bildes nach Farbe sortieren können.
Wie gesagt, dieser Algorithmus ist leicht zu schlagen, wenn die Geschwindigkeit Ihr Hauptkonzert ist (andere Lösungen sind hier wahrscheinlich schneller), aber ich bezweifle, dass er geschlagen werden kann, wenn die Speicherauslastung Ihr Hauptanliegen ist, da es nicht genug ist Speicherplatz zum Speichern einer Farbe und Speicherplatz für das Image selbst, es wird nur zusätzlicher Speicher benötigt, wenn der von Ihnen gewählte Sortieralgorithmus benötigt wird.
/ BEARBEITEN: Wie Lou gesagt hat, ist die Verwendung von .GetArgb() anstelle des Color -Wertes möglicherweise etwas schneller, da Color implementiert GetHashCode .
Die meisten anderen Implementierungen werden hier langsam sein. Damit dies schnell geht, benötigen Sie einen direkten Scanline-Zugriff und eine Art Sparse-Matrix zum Speichern der Farbdaten.
Zuerst werde ich den 32bpp Fall beschreiben, es ist viel einfacher:
Führen Sie für jede Iteration einfach eine hashset.add dieser Ganzzahl aus. Am Ende sehen Sie, wieviele Schlüssel in HashSet sind und das ist die Gesamtzahl der Farben. Es ist wichtig zu beachten, dass die Größenanpassung eines HashSets sehr schmerzhaft ist (O (n) wobei n die Anzahl der Elemente in der Menge ist). Daher möchten Sie vielleicht zunächst ein HashSet mit vernünftiger Größe konstruieren, vielleicht so etwas wie imageHeight * imageWidth / 4 wäre gut.
Im Fall von 24bpp muss PixelAccess ein Byte * sein, und Sie müssen für jede Farbe über 3 Bytes iterieren, um ein int zu konstruieren. Für jedes Byte in der Gruppe von 3 erste Bitshift nach links um 8 (ein Byte) und fügen Sie es zu einer ganzen Zahl. Sie haben jetzt eine 24bpp Farbe, dargestellt durch einen 32bit int, der Rest ist egal.
Sie haben keine eindeutigen Farben definiert. Wenn Sie tatsächlich wirklich eindeutige Codewerte meinen (im Gegensatz zu visuell gleichen), dann ist die einzige exakte Lösung, sie mit einer der in anderen Antworten beschriebenen Techniken zu zählen.
Wenn Sie nach visuell ähnlichen Farben suchen, führt dies schnell zu einem Problem mit der Palettenzuordnung, wo Sie nach den 256 besten eindeutigen Farben suchen, um die ursprüngliche volle Dynamik möglichst genau darzustellen Farbbereich Bild. Bei den meisten Bildern ist es erstaunlich, wie gut ein Bild, das von 24 Bit und bis zu 16 Millionen verschiedenen Farben reduziert wurde, mit einem Bild mit nur 256 eindeutigen Farben kombiniert werden kann, wenn diese 256 Farben gut gewählt sind. Die optimale Auswahl der richtigen 256 Farben (für dieses Beispiel) hat sich als NP-vollständig erwiesen, aber es gibt praktische Lösungen, die sehr nahe kommen können. Suche nach Papieren von einem Typen namens Shijie Wan und Sachen, die auf seiner Arbeit aufbauen.
Wenn Sie nach einer Annäherung an die Anzahl der Codewertfarben in einem Bild suchen, würde ich das Bild mit einem verlustfreien Komprimierungsschema komprimieren. Das Komprimierungsverhältnis bezieht sich direkt auf die Anzahl der eindeutigen Codewerte im Bild. Sie müssen nicht einmal die komprimierte Ausgabe behalten, sondern nur die Anzahl der Bytes auf dem Weg sammeln und die eigentlichen Ausgabedaten wegwerfen. Mit einer Reihe von Beispielbildern als Referenz können Sie eine Nachschlagetabelle zwischen dem Komprimierungsverhältnis und der Anzahl der verschiedenen Codewerte im Bild erstellen. Auch diese letzte Technik, die ziemlich schnell ist, wird definitiv eine Annäherung sein, aber sie sollte ziemlich gut korrelieren.
Vor modernen Grafikkarten, als die meisten Maschinen im 256-Farben-Paletten-Modus liefen, war dies ein Bereich von beträchtlichem Interesse. Die Grenzen der Rechenleistung und des Arbeitsspeichers setzen genau die Art von Constraint voraus, die für Sie nützlich sein könnte - so wird eine Suche nach Algorithmen zur Handhabung von Paletten wahrscheinlich etwas Nützliches ergeben.
Das hängt davon ab, welche Art von Bildern Sie analysieren möchten. Für 24-Bit-Bilder benötigen Sie bis zu 2 MB Speicher (da Sie im schlimmsten Fall jede Farbe verarbeiten müssen). Dafür wäre eine Bitmap die beste Idee (Sie haben eine 2-MB-Bitmap, wobei jedes Bit einer Farbe entspricht). Dies wäre eine gute Lösung für Bilder mit einer hohen Farbzahl, die in O (#pixels) realisiert werden können. Für 16-Bit-Bilder würden Sie mit dieser Technik nur 8 kB für diese Bitmap benötigen.
Wenn Sie jedoch Bilder mit wenig Farben haben, ist es besser, etwas anderes zu verwenden. Aber dann müssten Sie überprüfen, welcher Algorithmus Sie verwenden sollten ...
Die maximale Anzahl eindeutiger Farben in einem Bild entspricht der Anzahl der Pixel. Dies ist ab dem Beginn des Prozesses vorhersehbar. Die Verwendung der von Konrad vorgeschlagenen HashSet-Methode scheint dann eine vernünftige Lösung zu sein, da die Größe des Hash nicht größer als die Anzahl der Pixel sein sollte, während die von JeeBee vorgeschlagene Bitmap-Methode 512 MB für ein 32-Bit benötigt image (Wenn es einen Alpha-Kanal gibt, und dies zur Einzigartigkeit der Farbe beiträgt)
Die Leistung des HashSet-Ansatzes ist jedoch wahrscheinlich schlechter als die des "Bit-pro-Farbe" -Ansatzes - Sie könnten beides ausprobieren und einige Benchmarks verwenden, indem Sie viele verschiedene Bilder verwenden.
Die moderne populäre Implementierung der Farbquantisierung verwendet die octree Datenstruktur. Beachten Sie die Wikipedia-Seiten, der Inhalt ist ziemlich gut. Der Octree hat den Vorteil, dass er so speicherbegrenzt ist, wie Sie möchten, so dass Sie das gesamte Bild ausprobieren und sich ohne viel zusätzlichen Speicher für Ihre Palette entscheiden können. Sobald Sie das Konzept verstanden haben, folgen Sie dem Link zum 1996 Dr. Dobbs Artikel im Zeitschriftenartikel .
Da dies eine C # -Frage ist, lesen Sie den MSDN-Artikel vom Mai 2003 Optimieren der Farbquantisierung für ASP.NET-Images , die Quellcode enthält.
Tags und Links algorithm c# image-processing