Thread läuft nicht parallel --

[Mikkey]

Zitat:

Zitat von user0815 (Beitrag 1242848)

Wenn man das Bild nur aufteilt, dann kann es ja auch passieren das sich der gesuchte Bereich in keinem Bild mehr befindet.

So war das in meinen Beitrag mit den Streifen gedacht:

Beispiel: Gegeben Gesamtbild mit Höhe 120,
Ausschnitt mit Höhe 30,
3 Threads

Dann sucht Thread 1 in dem Streifen ab vertikaler Position 1 bis 30,
Thread 2 ab Position 31-60 und
Thread 3 ab Position 61-91

[Medium]

Zitat:

Zitat von user0815 (Beitrag 1242848)

Wenn man das Bild nur aufteilt, dann kann es ja auch passieren das sich der gesuchte Bereich in keinem Bild mehr befindet.

Diese sehr richtige und wichtige Aussage macht deinen aktuellen Ansatz eigentlich komplett zunichte. So sehr, dass ich nicht mehr versuchen würde krampfhaft die Geschwindigkeit eines Verfahrens zu verbessern, dass konzeptionell bereits nicht funktioniert. Entweder du suchst im gesamten Bild Pixel für Pixel (man könnte dabei z.B. gerade und ungerade Zeilen auf 2 Threads verteilen - dann bliebe der Lerneffekt "Umgang mit Threads" erhalten), oder man greift gleich zur Autokorrelation, die genau solche Probleme sehr gut löst.

[sonny2007]

Medium hast vollkommen recht 99.47 % der Rechenzeit gehen beim kopieren des Bildausschnittes auf die temp.canvas drauf.
Das lässt mich erstmal daran zweifeln ob die Threadverwendung überhaupt notwendig ist. Denn wieso die Auswirkung versuchen auszubügeln,
wenn man doch direkt die Ursache eliminieren kann.

Werde jetzt mal versuchen es ohne Canvas versuchen. Danach das Thread trotzdem versuchen hinzubekommen ^^

Grüße s0n

[sonny2007]

So ...

erst Gehversuche. Gedanken ( straft mich nicht wenn er komplett falsch ist :) ) <--- noch nicht so erfahren

1.Schritt beide Bitmaps in Streams zu speichern.
2.Schritt Header Daten von beiden Bitmaps aus den Streams entfern um die reinen Bilddaten zu haben
3.Schritt in einem TempStream nur die erste Pixelreihe des Suchbildes kopieren um eine Vorsuche zu benutzen, da sonst zu lange rechnet ( getestet )
4.Schritt in einer forschleife: immer den Pixelreihenabschnitt mit dem aktuellen Pixelreihenabschnitt des Screens ( genauso lang wie Suchabschnitt ) vergleichen


anbei mal ein bißchen Code :)

Delphi-Quellcode:

    ScreenBMP.PixelFormat := SearchBMP.PixelFormat ;

    SearchBMP.SaveToStream(SearchStream);
    ScreenBMP.SaveToStream(ScreenStream);
    //showMessage('Größe des Suchbildes x :'+inttostr(SearchBMP.Width)+' Y :'+inttostr(SearchBMP.Height)+' MemorySize :'+inttoStr(SearchStream.Size));
    //showMessage('Größe des Screens x :'+inttostr(ScreenBMP.Width)+' Y :'+inttostr(ScreenBMP.Height)+' MemorySize :'+inttoStr(ScreenStream.Size));

    // Header vom Suchbild entfernen
    SearchStream.Position := 53; // Bitmap Header Size = 54, deshalb Position auf 53
    SearchStream.Seek(0, soFromBeginning);
    tempSearch.CopyFrom(SearchStream,SearchStream.Size-54);
    tempSearch.Position := 0;
    SearchStream.Clear;
    SearchStream.CopyFrom(tempSearch,tempSearch.Size);
    tempSearch.Clear;


    // Header vom Screen entfernen
    ScreenStream.Position := 53; // Bitmap Header Size = 54, deshalb Position auf 53
    ScreenStream.Seek(0, soFromBeginning);
    tempScreen.CopyFrom(ScreenStream,ScreenStream.Size-54);
    tempScreen.Position := 0;
    ScreenStream.Clear;
    ScreenStream.CopyFrom(tempScreen,tempScreen.Size);
    tempScreen.Clear;



    // erste Zeile vom Suchbild als Vorraster benutzen
    SearchStream.Position := 0;
    tempSearch.CopyFrom(SearchStream,SearchBMP.Width*3);

    startTime := GetTickCount;
    for I := 0 to ScreenStream.Size-SearchBMP.Width*3-1 do
        begin
          ScreenStream.Position := i;  // 3 wegen 24Bit
          tempScreen.Clear;
          tempScreen.CopyFrom(ScreenStream,SearchBMP.Width*3);
          tempScreen.Position := 0;
          tempSearch.Position := 0;
          if CompareMem(tempScreen.Memory, tempSearch.Memory,SearchBMP.Width*3) then
              showmessage('gleich');
        end;

    showMessage('Durchlaufzeit: '+Floattostr((GettickCount-starttime)/1000)+' s');

Ist der Gedankengang so erstmal richtig. Funktioniert das überhaupt?

Grüße
s0n

[jfheins]

Zitat:

1.Schritt beide Bitmaps in Streams zu speichern.

Ist schon falsch, da auch hier Daten herumkopiert werden.

Du kannst dir mit Bitmap.ScanLine[0] einen Pointer beschaffen. Das passiert ohne Kopiererei - Windows sagt dir damit nur wo genau die Daten denn jetzt sind. Der Pointer, der da heraus kommt zeigt auf den Anfang der ersten Zeile. Jetzt musst du auf das Bildformat aufpassen (24bit/32bit) und kannst loslegen und vergleichen. Um einen Pixel einzulesen beitet sich die Verwendung von TRGBTriple oder gar TRGBTripleArray an.

Die weiteren Zeilen bekommst du, indem du bei ScanLine entsprechen größere Zahlen einsetzt.
Hier ist eine relativ ausführliche SO Antwort dazu: http://stackoverflow.com/a/13583452

Das sollte dann schonmal relativ flott sein. Wenn du möchtest kannst du auch einen angepassten Boyer Moore (oder einen anderen) Algorithmus benutzen, um die Bytesequenz in der Zeile zu suchen. Das sollte dann für große Suchbilder noch etwas schneller sein.

[sonny2007]

:( sorry, aber man lernt ja nie aus

okay nun mal ein wenig deinen Link verfolgt und da wird auch einiges klar :)
logisch das dies dann schneller sein sollte.
Deshalb mal der erste Versuch ...

Delphi-Quellcode:

type
  TRGBTripleArray = array [0..50000000] of TRGBTriple;
  pRGBTripleArray = ^TRGBTripleArray;

var
  x,y : Integer;
  ScreenP,SearchP : pRGBTripleArray;
  SearchBMP,ScreenBMP : TBitmap;
  starttime: integer;
begin
  Try
    SearchBMP := Tbitmap.create;
    ScreenBMP := Tbitmap.create;
    SearchBMP.Assign(Image1.Picture.bitmap);
    ScreenCapture(ScreenBMP);


    SearchP := SearchBMP.ScanLine[0];


    starttime := GettickCount;
    for y := 0 to ScreenBMP.Height - 1 do
      ScreenP := ScreenBMP.ScanLine[y];
      for x := 0 to ScreenBMP.Width - 1 do
      begin
        if CompareMem(ScreenP,SearchP[x],SearchBMP.width*3) then // <------- Hier der Fehler
          showMessage('gefunden');
        end;

Es kommt logischerweise der Fehler ... Pointer und TRGBTriplearray unterschiedliche Typen
Wie lautet der richtige Syntax um dies richtig zu übergeben ?

danke im Voraus.
s0n

[Photoner]

Probier mal:

Delphi-Quellcode:

if CompareMem(ScreenP, ^SearchP[x],SearchBMP.width*3) then

oder

Delphi-Quellcode:

if CompareMem(ScreenP, @SearchP[x],SearchBMP.width*3) then

ich verpeile @X und ^X jedes mal....

[sonny2007]

Ihr Seite der absolute Hammer. Vielen Vielen Dank.
Ist echt unglaublich wenn man mit den Zeigern arbeitet wie schnell das geht.

also die alte Zeit im schlechtesten fall 14,7 sec.
die Zeit ohne canvas,Stream oder sonstwas ... sondern direkt mit Zeigern auf das Bitmap.

unglaubliche 0,0061 sec

Ich kann es nicht glauben juhu :)

nochmals vielen vielen Dank.

So sieht das Ergebnis aus.

Delphi-Quellcode:

function SearchBitmapInOtherBitmap( SearchBMP,ScreenBMP: TBitmap): TPoint;
type
  TRGBTripleArray = array [0..50000000] of TRGBTriple;
  pRGBTripleArray = ^TRGBTripleArray;
Var
  x,y,k : Integer;
  ScreenP,SearchP : pRGBTripleArray;
  Laenge: integer;
  RowYes,RowNo : integer;
Begin
    // Startwerte
    Result.X := -1;
    Result.Y := -1;
    RowYes := 0;
    RowNo := 0;

    if SearchBMP.PixelFormat <> ScreenBMP.PixelFormat then
      exit;
//  { Himitsu }
//  http://www.delphipraxis.net/202453-post16.html
  Case SearchBMP.PixelFormat of
      pf1bit: Laenge := Ceil(SearchBMP.Width / 8);
      pf4bit: Laenge := Ceil(SearchBMP.Width / 2);
      pf8bit: Laenge := SearchBMP.Width;
      pf15bit: Laenge := Ceil(SearchBMP.Width * 15 / 8);
      pf16bit: Laenge := SearchBMP.Width * 2;
      pf24bit: Laenge := SearchBMP.Width * 3;
      pf32bit: Laenge := SearchBMP.Width * 4;
    End; // end case

  Try
    // Zeiger auf erste Pixelreihe in SearchP
    SearchP := SearchBMP.ScanLine[0];
    for y := 0 to ScreenBMP.Height - 1 do
      begin
        // Zeiger auf y Pixelreihe in ScreenP
        ScreenP := ScreenBMP.ScanLine[y];
        for x := 0 to ScreenBMP.Width - 1 do
          begin
            // Vergleiche beide Pixelreihen ob gleich
            if CompareMem(SearchP,@ScreenP[x],Laenge) then
              begin
                // Pixelreihe gefunden komplettes Suchbild prüfen
                for k := 0 to SearchBMP.Height-1 do
                  begin
                    ScreenP := ScreenBMP.ScanLine[y];
                    if CompareMem(SearchP,@ScreenP[x],Laenge)
                      then inc(RowYes);
                  end;
                  // wenn gefunden und jede Pixelreihe dem des Suchbildes entspricht setz result : TPoint
                  if RowYes = SearchBMP.Height then
                      begin
                        result.x := x;
                        result.Y := y;
                        exit;
                      end;
              end; // end If
            end; // end for x
          end;  // end for y
  except
    raise Exception.Create('Fehler bei SearchInPicture');
  End;
End;

Es wird gesucht ein 50x50 Bitmap und einem 1920x1080 Bitmap.
Im schlechtesten Fall die angesprochenen 0,0061 sec.


nochmals Danke an alle die mir Tipps und Ratschläge gegeben haben. Vor allem der Hinweis es ohne Canvas zu probieren.

Grüße s0n

[Blup]

Bei aller Freude, da sind noch reichlich Fehler drin...

Delphi-Quellcode:

pf1bit: Laenge := Ceil(SearchBMP.Width / 8);
pf4bit: Laenge := Ceil(SearchBMP.Width / 2);

CompareMem vergleicht nur ganze Byte, wenn dein gesuchtes Bild mitten in einem Byte anfängt oder nicht nur ganze Byte belegt, wirst du es so nicht finden.

Delphi-Quellcode:

pf15bit: Laenge := Ceil(SearchBMP.Width * 15 / 8);
...

Diese Pixelformat belegt für jedes Pixel 2 Byte, das restliche Bit wird nicht genutzt.

Delphi-Quellcode:

for y := 0 to ScreenBMP.Height - 1 do
  for x := 0 to ScreenBMP.Width - 1 do

Hier muss die Breite/Höhe des SearchBMP abgezogen werden, sonst greift CompareMem auf Speicher zu, der nicht mehr zu der Bitmap gehört.

Delphi-Quellcode:

CompareMem(SearchP,@ScreenP[x],Laenge)
...

ScreenP ist vom Type TRGBTripleArray, bei anderen Pixelformaten als pf24Bit wird auf die falsche Adresse zugegriffen.

[sonny2007]

hi Blub,

danke für die Hinweise.

Delphi-Quellcode:

for y := 0 to ScreenBMP.Height - 1 do
  for x := 0 to ScreenBMP.Width - 1 do

Dieses Problem ist heute prompt nach meiner Euphorie aufgetreten ... Das ist schon behoben.

Grüße
s0n