Grafiken erkennen. Library ?

[Aphton]

xD
Genau dies habe ich implementiert und warte nun auf seine Antwort auf meine letzte Frage ^^ (+SAD, einfach und langsam)

[Medium]

Zitat von stiftII:

Wandelt sie das Bild in ein verainfachtes Format um, und vergleicht gefundene Muster und formen ? Oder geht die im Endeffekte jeden Pixel durch und vergleicht ?

An der Art und Weise wie du fragst, lässt sich zumindest schon mal gut erkennen, dass du eher nach einer fertigen Lib schauen solltest, als es zu versuchen selbst zu implementieren.
Nein, diese Suche transformiert die Bilder vom Ortsraum in den Frequenzraum, führt eine skaleninvariante Minimabestimmung einer Differenz der Faltung durch, und transformiert das gefundene Minimum zurück in den Ortsraum. Edit: Oder ist das das Maximum im Sinne einer Autokorrelation im Frequenzraum? Der Wein... Was mich brennend interessieren würde: Gibt es dafür auch eine skalen- und rotationsinvariante Version in ähnlicher Einfachheit?

[bernhard_LA]

der Algorithmus zum Finden eines Suchbildes in einer großen Vorlage ist :
NORMALIZED CROSS CORRELATION - BZW. FAST NCC

unter http://sourceforge.net/projects/nccfastncc/ gibt eine Demo Application dazu in DELPHI.
Für unser Testbild benötigt die Version auf Source forge ~ 30 sec auf meinem Laptop, aktuell haben wir eine optimierte Version von FAST NCC entwickelt, die Suche
geht ca. 500 x schneller, dh. ist aber aktuell kein Open Source code. Falls Di ein Suchprojekt bearbeitest reicht Dir event. die Public Version des Algorithmuses.

[Aphton]

Hier, die einfache Variante mit SAD (Sum of Absolute Differences (siehe Wikipedia))

Delphi-Quellcode:

function findPicture(const Source, Picture: TBitmap): TPoint;
type
  TPRGBTripleRow = Array of PRGBTriple;
var
  SourceScanlineRow   : TPRGBTripleRow;
  PictureScanlineRow  : TPRGBTripleRow;
  function getRGBDifference(const ColorA, ColorB: PRGBTriple): Integer;
  begin
    Result := abs(ColorA.rgbtBlue   - ColorB.rgbtBlue)  +
              abs(ColorA.rgbtGreen  - ColorB.rgbtGreen) +
              abs(ColorA.rgbtRed    - ColorB.rgbtRed);
  end;
  function getPColor(const ScanlineRow: TPRGBTripleRow; const X, Y: Integer): PRGBTriple;
  begin
    Result := PRGBTriple(Integer(ScanlineRow[y]) + x * 3);
  end;
  procedure buildScanlineRows;
  var
    y: Integer;
  begin
    SetLength(SourceScanlineRow, Source.Height);
    for y := 0 to Source.Height - 1 do SourceScanlineRow[y] := Source.ScanLine[y];
    SetLength(PictureScanlineRow, Picture.Height);
    for y := 0 to Picture.Height - 1 do PictureScanlineRow[y] := Picture.ScanLine[y];
  end;
  function _findPicture: TPoint;
  var
    x, y, i, j  : Integer;
    SAD         : Integer;
    curSAD      : Integer;
  begin
    SAD := -1; // not assigned
    for y := 0 to Source.Height - Picture.Height do
      for x := 0 to Source.Width - Picture.Width do
      begin
        curSAD := 0;
        for j := 0 to Picture.Height - 1 do
          for i := 0 to Picture.Width - 1 do
            inc(curSAD, getRGBDifference(getPColor(SourceScanlineRow, x + i, y + j), getPColor(PictureScanlineRow, i, j)));
        if (SAD = -1) or (curSAD < SAD) then
        begin
          SAD     := curSAD;
          Result  := Point(x, y);
          if SAD = 0 then Exit;
        end;
      end;
  end;
begin
  if (Picture.Width > Source.Width) or (Picture.Height > Source.Height) or
     (Picture.PixelFormat <> pf24bit) or (Source.PixelFormat <> pf24bit) then
    Result := Point(-1, -1)
  else
  begin
    buildScanlineRows;
    Result := _findPicture;
  end;
end;

Edit: Das liefert die linke obere Ecke des Bereiches. Der Bereich hat klarerweise dieselbe Dimension wie "Picture"

[taveuni]

Zitat von stiftII:

Gibt es für diese Aufgabe irgendwelchen libs ?

Bei Mitov gibt es Bibliotheken für Delphi und .net.
Allerdings weiss ich nicht ob das Lazarus kompatibel ist.
Es gibt da auch Möglichkeiten mit opencv zu linken. Allerdings muss das training "von Hand" gemacht werden.
Ähnlichkeitssuche ist aber out of the box möglich.

Edit: Soeben habe ich gesehen dass nun sogar das Training für neuronale Netze implementiert ist.

[stiftII]

Zitat von Aphton:

Wie performant muss das ganze sein, wo willst du es genau einsetzen?
Darf das gesuchte Bild Abweichungen haben oder ist es exakt so im Bild enthalten?

Es darf minimale abweichungen haben. Und muss vorallem in jeder Größe gefunden werden.

Was macht die Funktion, die du gepostet hast genau ?

PS: Wenn ich die ausprobieren möchte bekomme ich ein "PRGBTriple not found"

[Aphton]

Welche Delphiversion verwendest du?

Ich schätz mal, eine etwas ältere, in der es diesen Typ nicht gibt.

Du kannst sie hier definieren:

Delphi-Quellcode:

type
  PRGBTriple = ^TRGBTriple;
  TRGBTriple = record
    rgbtBlue: Byte;
    rgbtGreen: Byte;
    rgbtRed: Byte;
  end;
  TPRGBTripleRow = Array of PRGBTriple;

Die Funktion liefert dir die Koordinaten der linkeren oberen Ecke im Bild, wo es halt gefunden wurde.

Anwendung:

Delphi-Quellcode:

var
  Position: TPoint;
begin
  Position := findPicture(RiesengroßesBild, SuchBild);
  ShowMessage('Gefunden an der Stelle: ' + IntToStr(Position.X) + ' - ' + IntToStr(Position.Y));
end;

Edit: Skalierung wird nicht berücksichtigt! Dies ginge aber auch ganz einfach (jedoch übelst unperformant) indem man das Suchbild zuerst mal richtig runterskaliert, dann schrittweise hochskaliert bis man dieselben Dimensionen wie das "RiesngroßeBild" hat und meine Suchfunktion drüberjagt!

Edit2: Das Ganze ist mehr oder weniger die Implementierung von dem hier (Anwendung: hier)

[stiftII]

Zitat:

Edit: Skalierung wird nicht berücksichtigt! Dies ginge aber auch ganz einfach (jedoch übelst unperformant) indem man das Suchbild zuerst mal richtig runterskaliert, dann schrittweise hochskaliert bis man dieselben Dimensionen wie das "RiesngroßeBild" hat und meine Suchfunktion drüberjagt!

Das ist eine interessante vorgehensweise.

Wie genau würde diese Funktion denn das skalierte Bilder erkennen ?

Beim skallieren gibt es ja auch immer einen qualitätsverlust, wenn das Original-Bild zB kleiner ist als das zu suchende "fragment".

PS: Ich arbeite mit Lazarus (fpc) und hab gerade festgestellt, dass es scanline dort nicht gibt ....

[Aphton]

Pff, um ehrlich zu sein, habe ich keine Lust, dir das anzupassen =/
Scanline ist einfach ein direkterer Weg, auf den Farbspeicher zuzugreifen. Evt. gibts unter Lazarus Pixels[]?

[stiftII]

Zitat von Aphton:

Pff, um ehrlich zu sein, habe ich keine Lust, dir das anzupassen =/
Scanline ist einfach ein direkterer Weg, auf den Farbspeicher zuzugreifen. Evt. gibts unter Lazarus Pixels[]?

ich hab ne Möglichkeit gefunden scanline zu implementieren ..
jetzt fehlt aber "PixelFormat"