"Dirty Rectangle Detection" bei BufferedImages?

[tuxedo]

Hi,

für eine VNC-Server artige Implementierung muss ich aufeinander folgende Bilder (kein Video, aber ein nahezu live-Bild des Desktops eines PCs) miteinander vergleichen, und die Bereiche erkennen, in denen sich etwas geändert hat. Ziel ist es, nicht immer das ganze Bild übertragen zu müssen, sondern nur den Teil, der sich seit dem letzten übertragenen Bild geändert hat.

Bisher mach ich es "naiv" etwa so:

1) Rastere VORHER und NACHHER Bild jeweils in x waagerechte und y senkrechte Blöcke
2) Nimm Block X des VORHER Bildes und vergleiche Pixel für Pixel mit dem Block X des NACHHER Bildes.
3) Unterscheidet sich ein Pixel innerhalb eines Blocks zum gleichen Pixel des anderen Blocks, so übertrage den ganzen Block.
4) inkrementiere X und springe zurück zu 2), solange bis alle Blöcke verglichen wurden.

Gibts irgend einen tollen, intelligenten Algorithmus mit dem ich nicht Pixel für Pixel vergleichen muss? Auf den ersten Blick würde ich sagen: Nein. Aber vielleicht gibts ja irgendwas das größere Bildbereiche schneller vergleicht? Keine Ahnung. Deshalb frag ich hier ja...

Gruß
Alex

 

[Marco13]

Gibts irgend einen tollen, intelligenten Algorithmus mit dem ich nicht Pixel für Pixel vergleichen muss? Auf den ersten Blick würde ich sagen: Nein.
Das würde ich auch auf den ersten (zweiten, dritten,... und überhaupt) Blick sagen: Egal welcher Algorithmus da existieren soll, es gibt nur zwei Möglichkeiten:
- Er vergleicht ALLE Pixel
- Wenn er NICHT alle Pixel vergleicht, kiregt er eine Änderung der Pixel, die er nicht vergleicht, nicht mit
(tertium non datur :wink: )

Wenn du "weißt", dass sich nicht nur einzelne Pixel ändern, sondern immer ganze Blöcke, kannst du ja sowas verwenden wie in http://forum.byte-welt.net/showthread.php?t=1143 - wobei du dann nicht jeden zweiten Pixel verwenden musst, sondern nur einen Pixel für jeden Block.

Ein bißchen abstrakt: Um eine Laufzeit von O(n) mit n=Anzahl der Pixel kommt man nicht drumrum, wenn man nicht irgendwo und aus irgendeinem Grund zusätzliche Informationen "umsonst" bekommt, die man dafür nutzen könnte. Wenn du z.B. die Bilder sowieso schon irgendwo kopierst oder so, kannst du sicher schon während des Kopierens irgendwelche Hilfs-Informationen sammeln, die das Vergleichen nachher schneller machen.

Interessant wären vielleicht noch solche Fragen, WIE genau du die Vergleiche machst. Zwischen sowas wie

Color c0 = new Color(bufferedImage0.getRGB(x,y));
Color c1 = new Color(bufferedImage1.getRGB(x,y));
if (c0.equals(c1)) kreisch();

und

if (imageData0[i] != imageData1[i]) kreisch();

liegen ja Welten (obwohl diese "Welten" auch immer nur konstante Faktoren sein können...)

 

[tuxedo]

Hehe. Dachte mir schon fast dass auf byte-welt verwiesen wird. Dummerweise: alex0801 == tuxedo

>> wobei du dann nicht jeden zweiten Pixel verwenden musst, sondern nur einen Pixel für jeden Block.

??? Wenn ein Block 20x20 Pixel groß ist, dann reicht es vorne und hinten nicht wenn ich nur einen Pixel vergleiche?! Jeder zweite Pixel wäre schon einleuchtender (war ja auch meine Idee ). Wobei "jeder zweite Pixel" die Performance nicht sehr beeinflusst hat (seltsamerweise .... -> muss ich nochmal analysieren...).

>> Ein bißchen abstrakt: Um eine Laufzeit von O(n) mit n=Anzahl der Pixel kommt man nicht drumrum, wenn man nicht irgendwo und aus irgendeinem Grund zusätzliche Informationen "umsonst" bekommt, die man dafür nutzen könnte.

Je länger ich dran rum überlege, desto einleuchtender ist es.

>> Wenn du z.B. die Bilder sowieso schon irgendwo kopierst oder so, kannst du sicher schon während des Kopierens irgendwelche Hilfs-Informationen sammeln, die das Vergleichen nachher schneller machen.

Da kommt mir eine Idee:

Angenommen ich w+ürde die Rasterung des Bildes auf 1x1 setzen (1 Block pro Bild, zu vereinfachung zum erklären): Wenn ich nun Bild A mit Bild B vergleiche, dann muss ich für Block A1 und Block B1 jeweils alle Pixel anfassen.
Vergleiche ich danach Bild B mit C, dann wäre es von Vorteil, wenn ich nicht nochmal alle Pixel in Block B1 anfassen muss, sondern einen Hash oder sowas hätte, der die Pixel konstellation aus B1 eindeutig identifiziert. Somit müsste ich nur noch C1 eindeutig identifizieren und hätte nur noch einen einzigen Vergleich zu machen (statt X*Y Vergleuche bei X Pixeln in der Breiteu nd Y Pixeln in der Höhe des Blocks).

Ist nur die Frage: Wie komm ich möglichst schnell an so einen eindeutigen Wert? Das sollte nicht langsamer gehen als Pixel mit Pixel zu vergleichen.

Gegenüberstellung, Bild mit einem Block mit 400x300 Pixel:

1) Pixel<->Pixel Vergleich: Worst-Case: 120.000 Vergleiche
2) Annahme: Block A1 hat schon einen Hash/ID: 1 Vergleich + X um den Hash aus 120.000 Pixeln zu errechnen von B1

Aber ich hab so das Gefühl dass einen Hash für 120.000 Pixel zu errechnen langsamer ist als 120.000 Vergleiche zu machen?!

- Alex

p.s.

vergleichen hab ich bisher so (die blöcke liegen als int[] vor):

public static boolean equals(int[] a, int[] a2) {
        if (a==a2)
            return true;
        if (a==null || a2==null)
            return false;

        int length = a.length;
        if (a2.length != length)
            return false;

        for (int i=0; i<length; i++)
            if (a[i] != a2[i])
                return false;

        return true;
    }

 

[tuxedo]

Hmm, hab eben mal n bisschen "probiert":

Ein BufferedImage mit (testweise) 3360x1050 Pixeln braucht auf meiner Maschine hier 16ms zum pixelweisen vergleichen mit obigen equals-methode (sofern die Arrays nicht wirklich identisch sind) etwa 16ms. Hier handelt es sich um int[]'s ...

Wenn ich ein gleich großes byte-Array habe, kann ich mit Adler32 daraus in <1ms einen Hash generieren...

Wenn ich jetzt also effizient an ein Rectangle im BufferedImage in Form eines byte[]'s komme, dann würde das vermutklich funktionieren mit dem Performance-Schub.

- Alex

 

[Marco13]

??? Wenn ein Block 20x20 Pixel groß ist, dann reicht es vorne und hinten nicht wenn ich nur einen Pixel vergleiche?!
:? Hmja, kommt halt drauf an: Wenn man (angenommen) einen Windows-Desktop übertragen will, und z.B. erkannt werden soll, dass ein Button gedrückt ist (also der Hintergrund des Buttons dunkler ist) dann reicht es, wenn man erkennt, dass EIN Pixel des Buttons sich von hell- auf dunkelgrau verändert hat - aber natürlich: Wenn der Pixel "zufällig" innerhalb der Schrift liegt (die schwarz IST und schwarz BLEIBT) dann kriegt man die Änderung nicht mit.

Aber das ist das angedeutete Problem: Selbst mit deinem "Jedes-Zweite-Pixel-Raster" würde man ja nicht mitbekommen, wenn die Änderung des Bildschirms daraus besteht, dass jemand den ganzen Bildschirm mit einem "Jedes-Zweite-Pixel-Plus-1-Raster" übermalt :wink:

Jeder zweite Pixel wäre schon einleuchtender (war ja auch meine Idee ). Wobei "jeder zweite Pixel" die Performance nicht sehr beeinflusst hat (seltsamerweise .... -> muss ich nochmal analysieren...).

Hm... es KÖNNTE sein, dass da das "überspringen" einzelner Pixel (schon das rechnen von +=2 statt ++ usw.) die Performance wieder auffrißt - was so eine moderne CPU genau rechnet, kann man ja kaum noch vorhersagen...

Um bei einer Sequenz von Bildern jeweils zwei aufeinanderfolgende zu vergleichen, erscheint mir sowas wie das mit dem Hashwert schon sinnvoll - vorausgesetzt, der Hashwert kann deutlich schneller berechnet werden, als der eigentliche Vergleich. Aber auch da muss man sich noch überlegen, wie man das genau macht: Wenn man nur EINEN Hashwert für das ganze Bild hat, muss man (wenn der Wert abweicht) wieder das ganze Bild vergleichen - das ist auch blöd. Bei einem Bild mit 1000x1000 Pixeln könnte man z.B. 10x10 Hash-Werte verwenden, die jeweils 100x100 Pixel codieren, und jeder dieser Hashwerte könnte aus 10x10 Pixeln (von den 100x100) berechnet werden....

Aber es kann natürlich auch immer passieren, dass zwei Hashwerte gleich sind, obwohl die Bilder sich beliebige verändert haben ... das sollte man auch bedenken....


Wenn ich jetzt also effizient an ein Rectangle im BufferedImage in Form eines byte[]'s komme, dann würde das vermutklich funktionieren mit dem Performance-Schub.

Man könnte zwar auch BufferedImages erstellen, die aus byte[] bestehen, oder sich vom einen int[]-BufferedImage einen byte[] holen, aber das wäre vermutlich alles schon VIEL langsamer, als der langsame Vergleich selbst.


Wenn ich ein gleich großes byte-Array habe, kann ich mit Adler32 daraus in <1ms einen Hash generieren...

Adler32 verwendet JNI - vielleicht wäre das für dich auch eine Option...?

 

[tuxedo]

Mein bisheriges Fazit:

Die Hash-Sache sieht recht gut aus. Problem dabei: Einen hash aus einem Int[] generieren scheint nicht so einfach zu sein. Alles was ich gefunden hab, war einen Hash aus einem byte[] zu generieren. Und int[] nach byte[] umrechnen kostet ja auch wieder unnötig Zeit... hmmpf.

Und ein byte[] krieg ich erst dann, wenn ich ein Graustufenbild habe. Das aber erfordert wieder das Konvertieren von farbe->grau, was auch wieder Zeit kostet.

Naja, ich muss da eben noch den sinnvollsten Weg finden.

Bei Adler32 stört's mich nicht dass da JNI verwendet wird. Denn AFAIK ist das ja Teil des JDKs/JREs und somit ohne weitere Installation seitens des Users verfügbar.

- Alex

 

[Ark]

Mir ist dazu spontan folgendes Interlacing-Verfahren in den Sinn gekommen:

Man gehe von folgender Behauptung aus: Wenn sich ein Pixel ändert, dann ändern sich wahrscheinlich auch die Pixel in der unmittelbaren Umgebung (bestehend aus 8 Pixel). Es würde also reichen, wenn man quasi nur die Umgebung eines Pixels anstatt des Bildpunkts selbst untersucht; das wäre dann 1/8 des Bildes.

Grundlage für den folgenden Algorithmus sei zunächst das übliche Interlacing-Verfahren: Man nehme ein Bild und unterteile es in gerade und ungerade Zeilen:

................................
--------------------------------

Um aber in keinem Durchlauf eine bestimmte Zeile zu bevorzugen und gleichzeitig die Zahl der "Blöcke" gering zu halten, springe man in Vierer-Häppchen über die geraden und ungeraden Zeilen:

....----....----....----....----
----....----....----....----....

Wenn eine Änderung innerhalb eines Blocks (4 nebeneinanderliegende Pixel) festgestellt wird, soll dieser immer als Ganzes übertragen werden.

Nun müssen nur noch möglichst geschickt Abtastpunkte festgelegt werden. Folgendes Muster ist mir eingefallen:

0...----0...----0...----0...----
----0...----0...----0...----0...

0...--1-0...--1-0...--1-0...--1-
--1-0...--1-0...--1-0...--1-0...

0..2--1-0..2--1-0..2--1-0..2--1-
--1-0..2--1-0..2--1-0..2--1-0..2

0..2-31-0..2-31-0..2-31-0..2-31-
-31-0..2-31-0..2-31-0..2-31-0..2

0.42-31-0.42-31-0.42-31-0.42-31-
-31-0.42-31-0.42-31-0.42-31-0.42

0.42531-0.42531-0.42531-0.42531-
531-0.42531-0.42531-0.42531-0.42

0642531-0642531-0642531-0642531-
531-0642531-0642531-0642531-0642

06425317064253170642531706425317
53170642531706425317064253170642

Im ersten Durchlauf wird in den geraden Zeilen von (0|y) beginnend bzw. in den ungeraden Zeilen von (4|y) beginnend nur jeder achte Punkt untersucht. Im zweiten Durchlauf wird anschließend in den geraden Zeilen von (6|y) beginnend bzw. in den ungeraden Zeilen von (2|y) beginnend nur jeder achte Punkt untersucht usw. entsprechend der Grafik.

In jedem Durchlauf wird also nur 1/8 des Bildes untersucht, wobei höchstens nur ein Halbbild pro Durchlauf "erzeugt" wird. Nach spätestens 8 Durchläufen wurde jeder Punkt untersucht. Die beschriebene Verteilung sorgt dafür, dass immer nach zwei Durchläufen von jedem Pixel mindestens 1 Pixel aus seiner Umgebung untersucht wurde. Nach der anfangs gestellten Behauptung ist also die Wahrscheinlichkeit groß, dass nach nur zwei Durchläufen (1/4 des Bildes) alle "dreckigen" Regionen des Bildes gefunden (und im schlimmsten Fall mit zwei Halbbildern übertragen) wurden.

So viel zu meiner Idee, das Problem zu lösen. Nebenbei gesagt: Java muss nicht zwingend langsamer sein als eine native Implementierung. Erst vor Kurzem hat mir jemand erzählt, dass er für bestimmte Festplattenoperationen JNI verwendete, damit allerdings mehr Zeit brauchte als mit reinem Java.

Ark

 

[tuxedo]

Der Ansatz liest sich sehr interessant. Bis zu der Sache mit den Abtastpunkten konnte ich dir folgen. Das danach muss ich noch 2-3 mal lesen ;-)

- Alex

 

[Marco13]

Die Hash-Sache sieht recht gut aus. Problem dabei: Einen hash aus einem Int[] generieren scheint nicht so einfach zu sein. Alles was ich gefunden hab, war einen Hash aus einem byte[] zu generieren. Und int[] nach byte[] umrechnen kostet ja auch wieder unnötig Zeit... hmmpf.

Ja, das sollte man wohl nicht machen. Aber statt einen int[] in einen byte[] zu verwandeln, und den dann durchzulaufen, kann man auch den int[] durchlaufen, und jeden einzelnen int "on the fly" mit Shifts und ANDs in 4 bytes zerstückeln - und DIE dann wieder einzeln behandeln.

Noch ein anderer Ansatz in bezug auf die "Grobstruktur" wäre ein Quadtree: Wenn man ein Bild der Größe 100x100 hat, prüft man erst die Pixel

  (0,0)   (0,50)  (0,100)
    *-------*-------*
    |       |       |
    |       |       |
    |       |       |
    *-------*-------*
 (50,0)  (50,50) (50,100)
    |       |       |
    |       |       |
    *-------*-------*
(100,0) (100,50)(100,100)

Und geht, wenn man dort keine Unterschiede feststellt, in jedem einzelnen Quadranten rekursiv weiter - damit müsste man die (rechteckigen!) Bereiche, in denen die Unterschiede ggf. sind, recht schnell finden....