schnelle getPixel Funktion

[schwarzerlotus]

Hallo zusammen,

ich rechne in meinem Projekt eine ganze Menge über Bitmap Bilder hin und her und hab mir deshalb mal ein Test Programm geschrieben, um eine schnelle Variante zu finden ein Bild zu durchlaufen.
Da ich außerdem bei den Berechnungen teilweise auch mehrere Bilder in einer Schleife durchlaufe hätte ich gerne eine getPixel Funktion auf dem Bitmap die mir möglichst ohne zeitlichen Overhead den Wert an der Position gibt und ich mich nicht immer um Scanline und Inc des Pointers kümmern muss.

Zum Testen der Laufzeit gehe ich einmal über das Bild, rechne alle Pixel einer Farbe zusammen und messe dabei die Zeit.

Bei der ersten Variante mit Pointern und Scanline

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i,j:          INTEGER;
  Row:          ^TRGBTriple;
  calc: Int64;
  time1, time2, DiffTime : TDateTime;
begin
  calc := 0;
  time1 := time;
  for j := 0 to Image1.Picture.Bitmap.Height-1 do begin
    row := Image1.Picture.Bitmap.Scanline[j];
    for i := 0 to Image1.Picture.Bitmap.Width-1 do begin
      calc := calc + (getColorPixel(row,Red));
      inc (row);
    end;
  end;
  time2 := time;
  DiffTime := ( time2 - time1 ) *60 *60 *24;
  Edit3.Text := Format ( '%2.5f', [DiffTime] );
  Edit1.Text := IntToStr(calc);
end;

benötigt der Algorithmus 0,017 Sekunden.

Nun hab ich mir eine Klasse beschrieben, die von TBitmap ableitet und eine zusätzliche getPixel Funktion zur Verfügung stellt. Damit hier nicht immer mit scanline die Zeile bestimmt werden muss, erzeuge ich mir in der load Methode ein Array of PByteArray mit allen Zeilenpointern.

Delphi-Quellcode:

unit MyBitmap;

interface

uses
  Graphics, SysUtils, types;

type
  TMyBitmap = class(TBitmap)

  private
    bits: array of PByteArray;
  public
    procedure Init();
    function getPixel(x,y:Integer): Byte;
    procedure LoadFromFile(const Filename: string); override;
  end;

implementation

procedure TMyBitmap.Init();
var
  i: Integer;
begin
  self.PixelFormat := pf32bit;
  SetLength(bits, self.Height);
  for i := 0 to self.Height -1 do
  begin
    bits[i] := self.ScanLine[i];
  end;
  Pbase := self.ScanLine[0];
end;

procedure TMyBitmap.LoadFromFile(const Filename: string);
begin
  inherited;
  init;
end;

function TMyBitmap.getPixel(x,y:Integer): Byte;
begin
  result := bits[y][3*x + 2];
end;

end.

Mit dieser Unit benötige ich für das Durchlaufen des Bildes 0,024 Sekunden also im Schnitt 7 ms länger - klingt nicht viel aber bei der Masse an Bilder macht es schon etwas aus.

Ich hab auch die Graphics32 Unit ausprobiert, die jedoch mit durchschnittlich 0,054 noch mehr Zeit benötigt.

Nun frage ich mich ob es eine Möglichkeit gibt das ganze doch so zu optimieren, dass die Berechnung möglichst schnell abläuft ich aber trotzdem komfortabel mit getPixel auf die Werte zugreifen kann und ich mich nicht um das inkrementieren des Pointers kümmern muss.

Habt ihr eine Idee? Liegt der zeitliche Overhead nur am Funktionsaufruf? Da ich mit Delphi 7 arbeite hab ich leider noch kein inline, um das eventuell zu optimieren.

Grüße Maick

[Bummi]

Keine Ahnung ob es Dir hilft...meine Experimente ....

[jaenicke]

Der zeitliche Overhead liegt einerseits am Funktionsaufruf, vor allem aber an der Berechnung der Adresse des Pixelwertes...

Schau dir dein "einfaches" getpixel mal im Assemblercode an...

Code:

XYZ.pas.26: begin
004AB71C 55               push ebp
004AB71D 8BEC              mov ebp,esp
004AB71F 83C4F0           add esp,-$10
004AB722 894DF4           mov [ebp-$0c],ecx
004AB725 8955F8           mov [ebp-$08],edx
004AB728 8945FC            mov [ebp-$04],eax
XYZ.pas.27: result := bits[y][3*x + 2];
004AB72B 8B45FC            mov eax,[ebp-$04]
004AB72E 8B8088030000     mov eax,[eax+$00000388]
004AB734 8B55F4           mov edx,[ebp-$0c]
004AB737 8B0490           mov eax,[eax+edx*4]
004AB73A 8B55F8           mov edx,[ebp-$08]
004AB73D 8D1452           lea edx,[edx+edx*2]
004AB740 8A441002         mov al,[eax+edx+$02]
004AB744 8845F3           mov [ebp-$0d],al
XYZ.pas.28: end;
004AB747 8A45F3           mov al,[ebp-$0d]
004AB74A 8BE5             mov esp,ebp
004AB74C 5D                pop ebp
004AB74D C3               ret

[himitsu]

pf32bit und getPixel: Byte kann schonmal nicht stimmen, da ein Pixel hier 4 Byte ist.

Warum ist es langsamer?
- du änderst das Pixelformat, also den ganzen Bildinhalt auf pf32bit
- der andere Code geht einfach davon ausß daß das bild schon pf24bit ist (wenn nicht, dann knallt's oder so)

Delphi-Quellcode:

type
  TColorArray = array[0..0] of TColor;
  PColorArray = ^TColorArray;

PixelColor := PColorArray(Self.ScanLine[Self.Height - 1])[x * Self.Width + (Self.Height - y - 1)]

Delphi-Quellcode:

var P: PColorArray;
P := PColorArray(Self.ScanLine[Self.Height - 1]);

PixelColor := P[(Self.Height - y - 1) * Self.Width + x];
// entspricht
PixelColor := P + ((Self.Height - y - 1) * Self.Width + x);
// entspricht
PixelColor := PByte(P) + ((Self.Height - y - 1) * Self.Width + x) * 4;

Diese Berechnug stimmt nur für pf32bit (für die anderen Formate müßte man noch einen breitenabhängigen Offset je Zeile mit einrechnen).
Das dann in eine Funktion und diese als "inline" markieren.

Die eine Scannline-Adresse oder das Array aller Scanlines natürlich vorher zwischenspeichern

[schwarzerlotus]

@himitsu

da ich meist nur den rot oder den grün Kanal benötige würde ich mir dafür dann im Endeffekt zwei Methoden mit festem Offset für das jeweilige Farb Byte schreiben - hatte ich vergessen zu erwähnen. Pf32Bit ist in der Klasse natürlich quatsch. Hatte etwas ausprobiert und die Zeile vergessen wieder raus zunehmen. Ich arbeite immer auf RGB Bildern mit je 8 bit also pf24bit von daher sind feste Offsets kein Problem an dieser Stelle.

@jaenicke

ok ist schon etwas her das ich mit Assembler gearbeitet hab ;) die Berechnung von der Adresse des Pixels benötigt also eine ganze Menge an Assembler Befehlen aber mir fällt keine Lösung ein das zu optimieren. Ich hab noch nicht so viel mit Delphi gemacht - von daher kann an sich die Assembler Übersetzung in der IDE anzeigen lassen oder hast du dafür ein externes Tool benutzt?

Ich probier dann mal die Beispiele von himitsu Bummi aus - mal sehen wie schnell die das berechnen.

danke schonmal

[ChrisE]

Hallo,

mal angenommen du arbeitest immer mit pf24Bit und mal angenommen Deine Bilder hätten nie mehr als n mal m Pixel, dann könntest du Dir eine Table erschaffen die für alle zu bearbeitenden Bilder gilt. Also ein Array mit [0..m-1]. Dort musst du einmal alle Koordinaten umrechnen von x auf Byte-Pos (3*x + 2).

Diese berechnungszeit brauchst du dann nur einmal für alle Bilder. Dein Aufruf von getPixelRed wäre dann nur noch:

Delphi-Quellcode:

function TMyBitmap.getPixelRed(x,y:Integer): Byte;
begin
  result := bits[y][redtable[x]];
end;

Das lohnt sich definitiv nicht, wenn nur ein Bild bearbeitet wird - aber wenn viele bearbeitet werden, dann lohnt es sich.

Gruß, Chris

[schwarzerlotus]

@himitsu

Zitat:

Das dann in eine Funktion und diese als "inline" markieren.

inline gibt es in Delphi 7 noch nicht oder? Ich meine zumindest das ich gelesen hätte, dass das erst mit 2007 oder so eingeführt wurde - dachte mir auch ich mach das wie in c++

@ChrisE

interessante Idee gleich mal ausprobieren

[Medium]

Und so lange sich das auf eine Zeile beschränkt, würde ich den Funktionsaufruf komplett weg lassen. Delphi kann imho ab einer gewissen Version inlinen, aber darauf habe ich mich bisher nicht verlassen. Kostet zwar Eleganz und Modularität, aber das ist zum Zwecke des Performancegewinns ja nicht selten so :)

Edit: Musst du eigentlich wahlfrei zugreifen können? Imho ist es insgesammt für die Hardware komfortabler Daten am Stück zu verarbeiten, so dass wenn du eh Zeilenweise/Pixelweise durchgehst die explizite Berechnung durch ein gelegentliches schlankes inc() ersetzen könntest. Damit ließe sich evtl. auch noch was raus holen.

Und zuguterletzt: Wäre MMX nicht evtl. etwas für dich?

[ChrisE]

Zitat:

Zitat von schwarzerlotus (Beitrag 1117157)

Da ich mit Delphi 7 arbeite hab ich leider noch kein inline, um das eventuell zu optimieren.

;-)

[Medium]

Jup, Redbox kam, ich hab sie aber mutwillig ignoriert :)

[ChrisE]

@medium
Das Zitat stammt aus dem Ausgangspost ;-)

Gruß, Chris

[Medium]

Das ist von viertel vor zehn! Du verlangst das unmögliche :D Dennoch bleibt das manuelle inlinen eine gute Option. Wenn man derart auf die Tube drücken muss, geht halt etwas Schönheit dabei drauf. Bei einem Einzeiler find ich das auch ausgesprochen vertretbar.

[ChrisE]

Zitat:

Zitat von Medium (Beitrag 1117226)

Das ist von viertel vor zehn! Du verlangst das unmögliche :D

Entschuldigung ;-)

[schwarzerlotus]

@Medium

wahlfreien Zugriff brauche ich nicht wirklich aber ich habe zum Beispiel einen Algorithmus in dem ich mit einem Maskenbild und zwei rois auf einem anderen Bild arbeite - ich hantiere also mit drei Scanline Pointern die ich dann richtig bestimmen und inkrementieren muss.
Aber ich hab mich schon fast damit abgefunden das direkt in der Hauptfunktion zu machen und den Pixel Zugriff nicht in eine Funktion auszulagern. Wie du schon gesagt hast geringe Laufzeit > Eleganz und Lesbarkeit ;)

@ChrisE

hab mal die Index Tabelle ausprobiert aber das Durchlaufen der Schleife hat sich dabei nicht signifikant verbessert - liegt zwischen 27 und 28 ms.

[ChrisE]

Zitat:

Zitat von schwarzerlotus (Beitrag 1117235)

hab mal die Index Tabelle ausprobiert aber das Durchlaufen der Schleife hat sich dabei nicht signifikant verbessert - liegt zwischen 27 und 28 ms.

Kannst du mal nen Beispielprojekt anhängen?

Gruß, Chris

[schwarzerlotus]

Ok hier mal meine kleine Testapp - hab noch etwas aufgeräumt und das graphics32 rausgenommen damit ihr nicht noch zusätzliche Abhängigkeiten habt.
Einmal wird das Bild mit Scanline und TRGBTriple Pointer und einmal mit BPyteArrays durchlaufen.
Außerdem dann einmal die von TBitmap abgeleitete Klasse mit zwei getPixel Methoden für die Liste von PbyteArray Pointern und dann mit der Liste der vorher berechneten X Offsets.
Die fastpixel Methode von Bummi funktioniert bei mir noch nicht.

bye Maick

P.s. mein Testimage hab ich mal nicht mit in das zip File gepackt - das wäre 9MB groß - ist ein ganz normales RGB Bild 2048*1536

[ChrisE]

Hallo,

TMyBitmap fehlt :-(

Gruß, Chris

[schwarzerlotus]

ohhh sorry ganz vergessen

[Medium]

Noch ein Vorschlag: Parallelisierung. Sobald du eine CPU mit >1 Kern hast, lohnt sich Multithreading merklich. Auf welcher Ebene man dann ansetzt ist etwas individuell, aber wenn es entsprechend viele Bilder sind, wäre denke ich viel gewonnen, wenn du einfach den aktuellen gesamten Vorgang in einen Thread schubst, und davon so grob übern Daumen Kernanzahl*2 Mal viele davon ackern lässt. Da die Operation an sich aber schon recht fix ist, ließen sich den Threads statt je eines einzelnen Bildes auch eine Liste von ein paar mehr zustecken, so dass man sich nicht nachher durch den Overhead der Threadverwaltung wieder zu viel kaputt macht. Das ist in der Regel dann ein wenig trial and error bis man da ein ungefähres Optimum hat.
Seit ich Threadblut geleckt habe, komm ich davon nicht mehr runter :)

[schwarzerlotus]

Da ich hier auf 4 Kernen arbeiten kann ist das auf jeden Fall eine Option :)

[ChrisE]

Hmm,

also ich versteh es zwar nicht, aber die Lookup-Upversion ist langsamer als die Berechnungsvariante :gruebel:

Gruß, Chris

[Medium]

Griffe in den Heap kosten nun mal auch, und bei einem 2D-Array muss intern ebenso wie bei einem Bitmap der 2D-Index zu einer "1D"-Adresse umgerechnet werden. Man hat quasi das selbe Problem damit nur verdoppelt - fiel mir aber auch erst nicht auf, da LUTs an sich oft ja schon helfen. Aber wohl dann doch eher nicht, wenn man eine Multiplikation und eine Addition gegen das selbe plus etwas mehr Traffic aufm Bus eintauscht :)

[jaenicke]

Zitat:

Zitat von schwarzerlotus (Beitrag 1117208)

Ich hab noch nicht so viel mit Delphi gemacht - von daher kann an sich die Assembler Übersetzung in der IDE anzeigen lassen oder hast du dafür ein externes Tool benutzt?

Wenn du an der Stelle einen Haltepunkt gesetzt hast, drückst du Strg + Alt + C. Dann kannst du auch assemblerbefehlsweise durch den Code laufen, falls gewünscht.

[FredlFesl]

Ist TGraphic32 nicht eine Option?

[freeway]

die kochen doch alle nur mit Wasser ;)
Bisher hab ich noch keine Alternative gesehen die einen signifikanten Vorteil bietet.
Selbst die Berechnung der Adressen zum direkten Zugriff ist nur marginal schneller.
Sourcecode zum damaligen Test

Delphi-Quellcode:

Var pic_Line : integer;
    row  : PRGB32Array;
    pic_offset, pic_data : integer;
    red_count : integer;

type
  TRGB32 = packed record
    B, G, R, A: Byte;
  end;

  TRGB32Array = packed array[0..MaxInt div SizeOf(TRGB32)-1] of TRGB32;
  PRGB32Array = ^TRGB32Array;

implementation

{$R *.DFM}

procedure TForm1.Start(Sender: TObject);
var  x, y, i: Integer;
begin
  setlength(steps_adr,10);
  if not openDialog1.Execute then exit;
  image1.Picture.Bitmap.LoadFromFile(OpenDialog1.Filename);

  with Image1.Picture.Bitmap do
  begin
    PixelFormat := pf32bit;
    row := Scanline[0];                                                            //start position
    pic_Line := (Longint(Scanline[1]) - Longint(row)) div SizeOf(TRGB32);          //direction
  end;
  count_red(Sender);
end;

procedure TForm1.count_red(Sender: TObject);
begin
      pic_offset := Y * pic_Line;                                  //offset
      pic_data := Image1.Picture.Bitmap.Width - 1 + pic_offset;    //data

      for x := pic_offset to pic_data do
        with row[x] do
          begin
//            B := 0;
//            G := 0;
            red_count  := red_count + R;
//          A := 0;
          end;
  Image1.Invalidate;
end;

end.

[Medium]

Die (derzeit, auf Consumer-Hardware) höchste Instanz der Optimierung von paralleler Massendatenverarbeitung wäre natürlich die Nutzung der GPU. Entweder mittels Shadern (DirectX/OpenGL), oder etwas mehr auf allgemeine Zwecke ausgelegt CUDA/OpenCL. Leider hat man bei allen vieren für Delphi nicht die ausgewachsensten Frameworks (bei letzteren eigentlich nirgends...), und es ist eine völlig andere Art der Programmierung, die wenn frisch angegangen sicherlich einiges an Lernzeit braucht bis es mal produktiv eingesetzt werden kann. Meiner eigenen Erfahrung nach sind dort allerdings durchaus Performancezuwächse von Faktoren um 50-100 zu bereits gut optimiertem CPU Code locker drin, dafür stellt man aber dann auch wieder etwas speziellere Hardwareanforderungen an den Kunden.
Wenn Zeit aber so entscheidend ist, könnte sich so ein Exkurs ggf. auch lohnen. Allerdings ist das Lernen der APIs und Sprachen nicht alles: Man müsste zudem etwas tiefer in die Theorie zur Parallelisierung von Algorithmen (und das Thema "Was mag meine Hardware gern?") einsteigen um eine bestehende Aufgabe günstig zu zerlegen zu wissen. Vorteil des ganzen: Es ist ein verflucht spannendes und zukunftsträchtiges Thema! Mir z.B. hat es sogar die Idee (und überhaupt praktische Anwendbarkeit dieser) zu meiner Abschlussarbeit geliefert - welche als Spaß-Projekt um genau o.g. (und C#) mal genauer anzuschauen begann.
Ist, als Neuling in diesem Gebiet, sicherlich nichts für nächste Woche rund und fertig, aber wenn du die Zeit und Muße hast, auch für später nicht die schlechteste Übung. So frei nach dem Motto "Horizont, ick hör dir Trappsen" :) Und gerade Bitmapverarbeitung böte sich da als quasi Hybrid zwischen Bilddaten und allgemeinen Berechnungen geradezu an - nahezu alle Bitmap-Operationen lassen sich hervorragend parallelisieren *mundwässrigmach* ;)

[schwarzerlotus]

Moin zusammen

Zitat:

Zitat von jaenicke (Beitrag 1117318)

Wenn du an der Stelle einen Haltepunkt gesetzt hast, drückst du Strg + Alt + C. Dann kannst du auch assemblerbefehlsweise durch den Code laufen, falls gewünscht.

thx gut zu wissen

Zitat:

Zitat von FredlFesl (Beitrag 1117347)

Ist TGraphic32 nicht eine Option?

du meinst http://www.graphics32.org/wiki/ richtig? Hatte ich auch ausprobiert ist aber leider bei den Pixelzugriffen um den Faktor drei langsamer im Vergleich mit der Scanline Variante.

@Medium

CUDA steht auf jeden Fall auf dem Plan für die nächste Zeit und da wir den Vorteil haben unsere Hardware mit auszuliefern ... ;)

Danke an alle für die vielen Ideen und Anregungen

[jaenicke]

Zitat:

Zitat von schwarzerlotus (Beitrag 1117416)

CUDA steht auf jeden Fall auf dem Plan für die nächste Zeit und da wir den Vorteil haben unsere Hardware mit auszuliefern ... ;)

CUDA ginge dann ja nur mit NVidia, OpenCL (oder auch Direct Compute Shader) gehen unabhängig davon:
https://code.google.com/p/delphi-opencl/