Farben Zählen

[*Blue$creEn*]

Guten Tag allerseits

Schönes Forum habt ihr hier. Ich hoffe, ihr könnt mir auch bei meinem Problem helfen.

Ich möchte meine Klasse gerne die Farben eines Bildes zählen lassen. Dazu habe ich es mittels ImageIO in ein BufferedImage geladen. Pixels ist das Array aus dem zugehörigen DataBufferByte.

Wie die Experten unter euch sicherlich sehen können, ist diese Schleife irrsinnig lahm. Was kann ich besser machen?

farben = new ArrayList<Integer>();
for (int i = 0; i < pixels.length; i+=3) {
    int farbe = 0xff000000 | ((pixels[i]&0xff)<<16) | ((pixels[i+1]&0xff)<<8) |(pixels[i+2]&0xff);
    if (!farben.contains(farbe)) farben.add(farbe);
    }

Ich habe auch mal daran gedacht, die byte[]->Integer-Konversion rauszulassen und eine ArrayList von byte[] zu verweden. Allerdings verlängert das Erstellen so vieler Byte-Arrays (für die RGB-Komponenten) die Rechenzeit auf das Doppelte. Vermutlich sind hilfreiche Tipps ganz simpel; verzeiht mir, dass ich sie nicht kenne oder sehe.

 

[dieta]

Versuch's vllt. mal mit einer HashMap, die ist glaube ich etwas schneller in solchen Dingen als eine ArrayList.

 

[Jockel]

Spontan würde ich erst einmal die Variable farbe außerhalb der Schleife deklarieren, so dass diese nicht bei jedem Durchlauf neu erzeugt wird. Das alleine wird es wohl aber nicht bringen.
Hast du denn eine Einschränkung, von welchem Typ das Bild ist oder wie groß es sein kann?

 

[Marco13]

Ein bißchen schneller würde es vmtl. schon werden, wenn der DataBuffer schon die fertigen ints enthalten würde. Falls es für dich egal ist, könntest du ein BufferedImage vom typ INT_RGBA erstellen, aber das Bild vorher extra zu diesem Zweck umzuwandeln lohnt sich vermutlich nicht!

Ansonsten war dieta's Tipp wohl der richtige:

if (!farben.contains(farbe)) farben.add(farbe);

Die "contains"-Methode durchsucht die ganze ArrayList nach dem übergebenen Element. Fastzustellen, dass eine Farbe NICHT in der Liste enthalten ist, ist der "worst case". Dieser worst case hat eine Laufzeit von O(n) (Websuche: Komplexität von Algorithmen, O-Notation).

Das heißt:
Wenn die ArrayList 100 Einträge hat, und es kommt eine neue Farbe dazu, müssen 100 Eingräge durchsucht werden. Wenn die ArrayList 100000 Einträge hat, und es kommt eine neue Farbe dazu, müssen 100000 Eingräge durchsucht werden.

Im allerschlimmsten Fall hast du z.B. eine Million Farben, und die werden nacheinander eingefügt. Dazu müssen ca. 500 Milliarden(!) Elemente durchsucht werden!!!

Mit einer HashMap (bzw. in deinem Fall: Ein HashSet<Integer>) ist es einfacher, festzustellen, dass ein Element NICHT in der Liste enthalten ist. Der worst case hat dann theoreitsch eine Laufzeit von O(1). D.h. um 1 Million Farben einzufügen, müssen nur 1 Million Tests gemacht werden.

Das dürfte etwas schneller sein

 

[byte]

TreeSet garantiert eine Laufzeit von log(n) für contains, add und remove.

Der worst case hat dann theoreitsch eine Laufzeit von O(1). D.h. um 1 Million Farben einzufügen, müssen nur 1 Million Tests gemacht werden.

Es gibt keine Datenstruktur, wo die contains ne konstante Laufzeit hat. Wie sollte das auch gehen?

 

[*Blue$creEn*]

Ich lasse das Bild jetzt zum TYPE_INT_RGB umwandeln und ein HashSet verwenden. Die Farbzählung dauert jetzt nur noch ein paar Millisekunden. bytos Vorschlag werde ich auch noch ausmessen. Vielen Dank für eure kompetente Hilfe.

Ich frag euch morgen vermutlich, wie ich schneller Pixel einer Farbe durch die einer anderen ersetzen lassen kann, aber jetzt schau ich erstmal selbst, wie weit ich komme.

 

[Ark]

Beim Hashen ist O(1) durchaus möglich, und womöglich auch der Grund, warum die Hashverfahren manchmal magisch anmuten. :shock:

Aber dieses pixels-Array finde ich etwas seltsam …

Vielleicht hilft dieser Link weiter: http://www.java-forum.org/de/viewtopic.php?t=41832 Voraussetzung ist natürlich, dass das Bild als BufferedImage im entsprechenden Format vorliegt. So ist in einem einzigen int-Wert die Farbe komplett gespeichert! Ich würde dann eine Baum- oder Streuwertmenge (TreeSet, HashSet ^^) wie schon beschrieben einsetzen. Das sollte schnell genug sein.

MfG
Ark

 

[Marco13]

@byto: Wie Ark auch schon gesagt hat: Bei einem HashSet ist die Zeit für add, get und contains jeweils O(1). Voraussetzung dafür ist eine "gute" (d.h. passende) Hashfunktion. Bei einer schlechten HashFunktion KÖNNTE die Zeit THEORETISCH wieder O(n) werden, aber davon braucht man in diesem Fall nicht auszugehen.

Die einfachste Erklärung dafür, warum es eine Datenstruktur gibt, die (besonders in diesem spziellen Fall, aber - durch das Hashing - auch ganz allgemein) diese Operationen in O(1) durchführen kann ist

    boolean myVeryLageSet[] = new boolean[Integer.MAX_VALUE]; // *knirsch*
    
    boolean contains(int n)
    {
        return myVeryLargeSet[n]; // O(1) *grins*
    }
}

Und sowas wird beim Hashing eben (prinzipiell!) gemacht. Nur wird ein kleinerer Array verwendet, und die "großen" ints (mit der Hashfunktion) auf einen kleineren int umgerechnet.

 

[EgonOlsen]

Du hast außerdem im Fall, dass die Farbe nicht in der Struktur ist, zwei implizite Instanziierungen von Integer....wunderschön verschleiert vom ach so tollen Autoboxing. Die erste Instanz davon erzeugst du sowieso, weil du das contains in jedem Fall ausführst. Ich würde die Erzeugung explizit machen und vor das contains ziehen und diese Instanz dann auch in die Struktur (was immer du da jetzt für nimmst) einfügen. Mag nicht viel bringen, aber wer weiß.
Wenn das eine absolut zeitkritische Schleife ist, würde ich ein Hashset für echt primitive Werte bauen, damit die Integer-Erzeugungen komplett wegfallen.
Wenn die Bilder farblich nicht zu variabel sind, mag auch ein kleiner "Cache" aus einem int-Wert was bringen, in dem du den letzten Farbwert merkst und nur ein contains usw. ausführst, wenn sich der aktuelle Wert von diesem unterscheidet. Wenn das aber sehr oft passiert, ist es wiederum kontraproduktiv...das hängt also stark von der Struktur des Bildes ab.

 

[byte]

Stimmt ihr habt recht. War mir nie bewusst, dass es tatsächlich konstante Laufzeit ist.

 

[Ark]

Wenn ich garantieren könnte, dass es folgend zu keiner Kollision kommt, würde ich es wie folgt machen:

int[] farben;
farben=new int[pixels.length];
for(int i=0;i<pixels.length;i++){
    farben[pixels[i]%farben.length]++;
}

Voraussetzung ist eben, dass keine Kollisionen auftreten und in einem pixels-int der Farbwert vollständig gespeichert ist.

MfG
Ark

 

[*Blue$creEn*]

Eine ganz profane Frage: Ich verstehe nicht, wo die Anzahl der Farben entsteht.

 

[Marco13]

Die Anzahl der Farben ist einfach die Größe der enstehenden HashSet (und umgekehrt :wink: ). Oder was meintest du?

 

[*Blue$creEn*]

Die Lösung mit HashSet funktioniert ja bereits tadellos. Ich bezog mich auf den lezten Vorschlag von Ark.

 

[EgonOlsen]

Der Vorschlag kann so nicht funktionieren, bzw. du müsstest ein 16Mio. Elemente großes Array dafür verwenden. Nicht wirklich praktikabel...aber man könnte es als Basis für eine Implementierung mit primitiven Typen nehmen. Aber wenn deine aktuelle Lösung jetzt schnell genug ist...

 

[Marco13]

@*Blue$creEn*:: Ach so - da wäre es einfach die Anzahl der Einträge in dem Array, die NICHT 0 sind :wink: (falls es nicht zu "Hash"-Kollisionen kommt).
@EgonOlsen: Der Vorschlag funktioniert schon (falls es nicht zu "Hash"-Kollisionen kommt). :wink:

 

[EgonOlsen]

@EgonOlsen: Der Vorschlag funktioniert schon (falls es nicht zu "Hash"-Kollisionen kommt). :wink:

Natürlich, aber das ist akademisch und verwirrt hier nur, weil es eben genau dazu kommen wird. Wenn ich das bei 16Mio möglichen Farbwerten sicher vermeiden will, brauche ich eine 16Mio. Einträge fassende Hashtabelle.

 

[Ark]

@*Blue$creEn*:: Ach so - da wäre es einfach die Anzahl der Einträge in dem Array, die NICHT 0 sind :wink: (falls es nicht zu "Hash"-Kollisionen kommt).

OK, dann eben anders:

int[] farben=new int[524288];//2 hoch 24 durch 32
int zaehler=0;
int t;
for(int i=0;i<pixels.length;i++){
    t=pixels[i];
    if((farben[t>>>5]&1<<t)==0){
        farben[t>>>5]|=1<<t;
        zaehler++;
    }
}

Das Ding sollte für Farben mit 8 Bit pro Kanal (RGB) funzen, kostet aber auch 16 MB an RAM!

MfG
Ark