3. Farbbild in Graustufen Bild umwandeln -> Algorithmus Optimierung

Farbbild in Graustufen Bild umwandeln -> Algorithmus Optimierung

  • B

    Hallo,

    ich habe einen Algorithmus zum umwandeln eines Bildes in Graustufen:

    int color;
	for(int x=0; x<picture->Width; x++)
	{
		for(int y=0; y<picture->Height; y++)
		{
			color = ((picture->Pixels[x][y] & 255) +
					((picture->Pixels[x][y] >> 8) & 255) +
					((picture->Pixels[x][y] >> 16) & 255)) / 3;
			picture->Pixels[x][y] = color + (color << 8) + (color << 16);
        }
    }

    Pixels ist ein 2D Array in welchem die Farben hinter dem jeweiligen Pixel hinterlegt sind. Das Problem beim Algorithmus ist, dass das ganze bei einem Bild mit 640x480 ca. 2seks braucht, was mir deutlich zu lang ist, irgendwie muss das ja auch schneller gehen.

    #edit: Erklärung zur Umwandlung: Bei der Umwandlung muss zumindest bei einem RGB Bild der Durchschnittswert aus R, G und B wiederum in R, G und B geschrieben werden, so das alle den gleichen Wert haben. Deswegen hier die Bitverschiebungen, RGB Werte werden hier einfach hintereinander in eine int Variable geschrieben.

    Danke im voraus,

    Max

    0
  • N

    Das sieht ziemlich nach VCL aus. Und das hat auch nichts mit dem Algorithmus selbst zu tun, sondern liegt daran, dass der Zugriff über Pixels extrem langsam ist. Vermutlich wird da intern GetPixel aufgerufen.
    Stattdessen solltest du dir einen direkten Zugriff auf das Bitmap verschaffen und dann damit arbeiten. In der Zeit, die jetzt für einen einzigen Pixel benötigt wird, schafft man so eine ganze Reihe. Außerdem solltest du die Verschachtelungsreihenfolge der Schleifen ändern, da du damit den Prozessor-Cache viel besser ausnutzst.
    Dein vorliegender Code kann natürlich auch schon leicht verschnellert werden, indem du den Farbwert in color zwischenspeicherst, anstatt ihn dreimal zu lesen.

    0
  • B

    Oh, ja das stimmt, ist VCL und es wird intern GetPixel aufgerufen, wusste nicht dass das so viel ausmacht! Danke vielmals!

    0
  • ?

    Nanyuki schrieb:

    Außerdem solltest du die Verschachtelungsreihenfolge der Schleifen ändern, da du damit den Prozessor-Cache viel besser ausnutzst.

    Das interessiert mich jetzt! 😋

    0
  • Mod

    Interessierter schrieb:

    Das interessiert mich jetzt! 😋

    Was Nanyuki wohl meint, ist dass man die Elemente eines mehrdimensionale Arrays möglichst in der Reihenfolge benutzen sollte, in der sie im Speicher liegen.
    1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus
    2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben. Falls der Algorithmus auch auf vorherige Elemente zugreift, wäre der Cache dann nicht mehr 'heiß' und man müsste erneut auf den langsamen Arbeitsspeicher warten.

    Meiner Ansicht nach macht's blub² aber richtig. Man sollte die Indizes des Arrays von hinten(innerste Schleife) nach vorne(äußerste Schleife) durchgehen.

    0
  • N

    SeppJ schrieb:

    1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

    Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

    SeppJ schrieb:

    2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben.

    Wieso sollte eine Zeile nicht in den Speicher passen? Falls das so wäre, hätte man sowieso andere Probleme...

    0
  • F

    EDIT: Nachfolgendes macht natürlich nur Sinn wenn Pixels wirklich ein Array ist und keine überladenen Operatoren hat oder so ein Käse. 😉

    Was er meint ist folgendes:

    for(int x=0; x<picture->Width; x++)
    {
        for(int y=0; y<picture->Height; y++)

// ersetzen durch:

    for(int y=0; y<picture->Height; y++)
    {
      for(int x=0; x<picture->Width; x++)

    Denn ansonsten gehst du spaltenweise durch das zweidimensionale Array, bearbeitest also nie den angrenzenden Pixel, sondern hast immer größere Sprünge.

    Nur eine Schleife zu nehmen mit einem simplen Pointer der verschoben wird, wäre wohl noch effizienter. Vor allem da in der Berechnung selbst x und y ja furzegal ist.

    int color;
  int *begin = &(picture->Pixels[0][0]);
  int *end = begin + (picture->Width * picture->Height);
    for(int *x = begin; x < end; x++)
    {
            color = ((*x & 255) +
                    ((*x >> 8) & 255) +
                    ((*x >> 16) & 255)) / 3;
            *x = color + (color << 8) + (color << 16);
        }
    }

    Nicht getestet und weiß auch nicht was Pixels für einen Typ hat aber so in etwa ist es wohl fixer.

    0
  • B

    Pixels ist kein wirkliches Array sonder eine Property (Getter und Setter). Das geht also so nicht. Bei TBitmap gibt es aber die Eigenschaft ScanLine, die ein Zeilenarray liefert. Das sollte deutlich schneller gehen.
    Der Thread hier gehört aber eigentlich ins BCB-Forum.

    0
  • S

    Hab die Diskussion nicht mitverfolgt, aber ich glaube, hier kommt mal was ganz anderes:

    wenn du wirklich die Helligkeiten, die das menschliche Auge wahrnimmt, bekommen möchtest, musst du die verschiedenen Farbkanäle unterschiedlich gewichten. Ca. so:

    grau = 0.6 * grün + 0.25* rot + 0.15 * blau

    Ist jetzt nicht genau, entspricht aber ungefähr den Werten aus meiner Videotechnik-Vorlesung...

    0
  • T

    Nexus schrieb:

    SeppJ schrieb:

    1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

    Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

    Nein, in diesem Fall macht das einen riesigen Unterschied.

    0
  • N

    Tachyon schrieb:

    Nein, in diesem Fall macht das einen riesigen Unterschied.

    Hm, okay. 🙂
    Kommt mir nur ein wenig komisch vor, weil ich noch nie gross davon gehört habe...

    Ist das allgemein so, also sollte man Arrays immer so durchiterieren? Oder nur unter bestimmten Bedingungen (auf dem Stack, oder was auch immer)?

    0
  • Mod

    Wenn man einen Rechner verwendet der moderner als ein 386er ist, sollte man Arrays immer so durchiterieren. Das bringt wirklich sehr viel. Es müssen natürlich auch hinreichend große Arrays sein, bei 100x100 machts wohl kaum einen Unterschied, bei 10000x10000 sollte man es schon deutlich merken.

    0
  • N

    Gut, dass die meisten das sowieso intuitiv tun. Oder gibt es hier jemanden, der kategorisch von hinten durchiteriert? :p

    Dann bliebe noch Folgendes:

    Nexus schrieb:

    SeppJ schrieb:

    2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben.

    Wieso sollte eine Zeile nicht in den Speicher passen? Falls das so wäre, hätte man sowieso andere Probleme...

    0
  • Mod

    Mit Speicher meinte ich den (freien) Cachespeicher. War eine missverständliche Wortwahl.

    0
  • ?

    Nexus schrieb:

    SeppJ schrieb:

    1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

    Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

    Was sollte man bei dne Code den sonst machen? Oder bekommst du das mit ner anderen Laufzeitkomplexität hin... 🙄

    0
  • N

    übrigens schrieb:

    Was sollte man bei dne Code den sonst machen? Oder bekommst du das mit ner anderen Laufzeitkomplexität hin... 🙄

    Was hat das mit meiner Frage zu tun?

    0
Anmelden zum Antworten