Zahlen in Bild erkennen mit Pixelsearch - Genauigkeitsprob.

[MaToBe]

Hallo

ich möchte die Zahlen aus den unten angehägten Bildern eindeutig bestimmen.

Als Idee habe ich mir gedacht...zähl doch einfach die schwarzen Pixel. Gemacht getan und funktioniert...aber eben nur fast.

Leider haben die Zahlen 5 und 6 genau die gleiche Anzahl von Pixel.

Außerdem hat leider nicht jede Zahl 6 die gleiche schwarze Pixelanzahl. Die eine 6 hat zB 51 Pixel und die 2te 6 57 Pixel. 57 Pixel hat aber auch schon die 8 wodurch die 6 als 8 erkannt werden würde.

Was kann ich da tun?

MFG Matobe

Im Anhang ist mein Testprogramm und die Bilder.

[blackfin]

Ist vielleicht ein wenig zuviel des Guten, aber wenn es um Zahlenerkennung allgemein geht, hilft dir vielleicht diese Seite was:

Lipfert Zimmermann (FH Regensburg) - Zahlenerkennung

Wenn es jetzt nicht allzu viele unterschiedliche Varianten gibt, könntest du ja erstmal probieren, das vorhandene Bild mit einem Referenz-Bild zu vergleichen.

Ein einfacher Verusch wäre z.B.:
Du rechnest das Bild erstmal in Schwarz weiss (nicht graustufen!) um und vergleichst dann jeden Pixel mit jedem Pixel deiner Referenz-Zahlen-Bilder. (diese sind natürlich auch schwarz-weiss)
Das Bild, dass die meisten "Pro Pixel"-Übereinstimmungen hat, müsste die gesuchte Zahl sein.

Als zweiten Versuchs-Schritt würde ich die Referenz-Bilder als auch das zu untersuchende Bild erstmal im Programm "freistellen", also alle Randpixel beschneiden, so dass nur noch die Form übrigbleibt. Somit kannst du schonmal nur verschobene Zahlen erkennen.
Taste dich dazu einfach von allen vier Seiten an die Zahl heran. Wenn ein Pixel ungleich weiss (oder schwarz ist, je nachdem wie du s/w umrechnest), merk dir den Beschneidungswert und beschneide dann das bild dementsprechend von allen vier Seiten. Dann untersuch die Pixel-Übereinstimmungen wie in Schritt 1.

[MaToBe]

hab das bild / die bilder in schwarz weiß umgerechnet. Totz ausprobieren von verschiedenen Toleranzwerten gibt es immer noch ein zu unklares Ergebnis, so dass zum Teil Ziffern falsch oder garnicht erkannt werden.

Hat jemand ne Idee?

[MaToBe]

Ich gehe jetzt einer anderen Idee nach... allerdings stehe ich gerade voll auf dem Schlauch.

Kann mir einer sage warum bei dieser Prozedure sich das Programm aufhängt ?? Verhalten wie bei eine Endlosschleife aber ich seh keine ?!?

Delphi-Quellcode:

procedure TfrmMain.btnCodeClick(Sender: TObject);
var ID : string;
    x, y : integer;
begin
   ID := '';
   for x := 0 to Image.Width - 1 do
   begin
     for y := 0 to Image.Height - 1 do
     begin
       if Image.Canvas.Pixels[x,y] = clBlack then
       begin
           ID := ID + 'B';
       end
       else
       begin
           ID := ID + 'W';
       end;
     end;
   end;
   edtCode.Text := ID;
end;

PS: Hab extra ein Bild mit wenig Pixel genommen als Test.

[Medium]

Über wie viele Pixel reden wir, wenn es um "wenig" geht? (Ist ja alles relativ :).) Canvas.Pixels[] ist an sich schon nicht der Turbomode unter den Möglichkeiten an Farben zu kommen, und auch das sukzessive zusammenbauen eines Strings auf diese Weise ist sehr fragwürdig. Beides sollte hier bis ein paar zig hundert Pixel zwar noch im Sekunden-Bereich erledigt sein, aber die Pixelanzahl kann ganz flott sehr üppig sein, und dann kann ich mir schon vorstellen, dass das einige Zeit brauchen kann.

Wenn wir hier über Thumbnailgrößen von ~80x80 reden (immerhin schon 6400 Pixel!), sollte das auf einem PC >486er aber schon in <1min durch sein. Wie ist's denn mit wirklich mickrigen Bitmaps? So 16x16 Pixel? Oder auch mal 8x8?

[MaToBe]

das Testbild hat 7x5 pixel ;D

[Flips]

Link

Ist zwar nicht mehr so auf dem neuesten Stand was den Code angeht aber ich denke für reine Zahlenerkennung ideal und auch einfacher als gleich ne Kohonen-Map zu nehmen.

[Medium]

Zitat:

Zitat von MaToBe

das Testbild hat 7x5 pixel ;D

Das Image auch? An deiner Schleife kann es ja nun nicht liegen, also muss irgend etwas mit dem Image sein. Ich würde auch eher Image.Bitmap nehmen. Und Flips' Beitrag ist auch gut, weil so simple Verfahren ab gewisser (geringer) Qualität des Materials nicht mehr zuverlässig arbeiten können, bzw. auch bei entsprechender Uneindeutigkeit im Material (gerade bei Fotos/Scans müssen 2x der selbe Buchstabe nicht unbedingt pixelgleich sein z.B.).

[MaToBe]

ich habe genau den Code oben mal in mein anderes "Testprogramm" integiert, da funktioniert er...

Hab aber jetzt ein neues Problem. Nach schwarzen Pixeln zu suchen ist ja einfach => clBlack...

Aber wie bekomm ich den exakten Farbwert von dem Gelb der Bilder? clYellow funktioniert nicht und den Farbwert den ich per Gimp herausgefunden habe (Farbwert = fac953) funkioniert auch nicht wenn ich einfach

Delphi-Quellcode:

$fac953
Image.Canvas.Pixels[m,n] = $fac953

schreibe.

[Medium]

Unter anderem aus solchen Gründen wandelt man Bilder für sowas ganz gern in s/w um ;)

[MaToBe]

okay jetzt gibts schon wieder ein neues Problem.

Meine Idee ist es, jeder Ziffer eine Art Code zu geben durch die sie identifizierbar ist. Der Code einer Ziffer wird generiert durch deren Schwarz-Weiß Bild. In diese werden dann die Wechsel zwischen schwarzen und weißen Pixeln verarbeitet.

Der Code für die Ziffer 1 sieht dann so aus:

Delphi-Quellcode:

Ziffer_1 : array[0..9] of integer = (251, 1, 26, 1, 26, 1, 24, 13, 14, 13);

Auf menschlich: 251 weiße Pixel, auf diese folgt 1 schwarzes Pixel, dann kommen 26 weiße Pixel, dann 1 schwarzes usw.

Alle Zifferncodes:

Delphi-Quellcode:

Ziffer_1 : array[0..9] of integer = (251, 1, 26, 1, 26, 1, 24, 13, 14, 13);
  Ziffer_2 : array[0..37] of integer = (250, 3, 6, 3, 14, 4, 5, 4, 14, 2, 6, 5, 14, 2, 6, 2, 1, 2, 14, 1, 6,
                                        2, 2, 2, 14, 2, 4, 2, 3, 2, 14, 7, 4, 2, 15, 6, 4, 2);
  Ziffer_3 : array[0..35] of integer = (250, 2, 7, 2, 15, 3, 7, 3, 14, 2, 10, 1, 14, 1, 5, 1, 5, 2, 13, 1, 5,
                                        1, 5, 2, 13, 2, 3, 3, 3, 2, 14, 13, 16, 3, 2, 5);
  Ziffer_4 : array[0..27] of integer = (230, 2, 23, 4, 22, 2, 2, 1, 20, 2, 4, 1, 18, 3, 5, 1, 17, 2, 7, 1, 17,
                                        13, 14, 13, 22, 2, 26, 1);
  Ziffer_5 : array[0..41] of integer = (232, 1, 16, 7, 3, 3, 14, 7, 3, 3, 14, 2, 3, 1, 6, 2, 13, 2, 3, 1, 6, 2,
                                        13, 2, 3, 2, 5, 2, 13, 2, 3, 2, 4, 2, 14, 2, 3, 8, 14, 2, 4, 6);
  Ziffer_6 : array[0..41] of integer = (226, 6, 18, 11, 16, 3, 2, 2, 2, 3, 14, 2, 3, 2, 5, 1, 14, 2, 3, 1, 6, 2,
                                        13, 1, 4, 2, 5, 2, 13, 2, 3, 2, 4, 2, 14, 3, 2, 8, 15, 2, 3, 6);
  Ziffer_7 : array[0..27] of integer = (222, 2, 25, 2, 25, 2, 9, 2, 14, 2, 6, 5, 14, 2, 4, 7, 14, 2, 2, 4, 19, 2,
                                        1, 3, 21, 4, 23, 3);
  Ziffer_8 : array[0..37] of integer = (250, 4, 2, 5, 15, 13, 14, 2, 3, 3, 4, 1, 14, 1, 4, 2, 5, 2, 13, 1, 4, 2, 5,
                                        2, 13, 2, 3, 2, 5, 2, 13, 13, 15, 4, 2, 5, 24, 1);
  Ziffer_9 : array[0..39] of integer = (225, 3, 22, 7, 3, 2, 14, 3, 2, 3, 3, 2, 14, 2, 5, 1, 4, 2, 13, 1, 6, 1, 4,
                                        2, 13, 1, 6, 1, 4, 2, 13, 2, 4, 2, 3, 2, 15, 11, 17, 9);

Meine Idee ist es jetzt, dass wenn eins der Bilder mit einer Ziffer eingelesen wird, für dieses Bild solch ein Code erstellt wird. Dann wird der Code auf die größtmögliche Gemeinsamkeit mit den 9 definierten Codes überprüft. Die größte Gemeinsamkeit soll dann als Treffer angenommen werden.

Und hier ist jetzt mein Problem. Wie vergleiche ich den neu generierten Code mit den 9 vodefinierten auf die größte Ähnlichkeit?

Meine Folgende Lösung war leider von der Idee her gut, aber viel zu ungenau:

Delphi-Quellcode:

.....
 for i := 0 to 34 do
   begin
      aktErgebnis := aktErgebnis + (strtoint(aktZiffer[i]) - Ziffer_3[i]);     //Die Differenz jeder Stelle des Codes aufaddieren 
   end;
   
   if abs(aktErgebnis) < abs(bestErgebnis) then                                //Die kleinste Differenz ist die gesuchte Zahl
   begin
      bestErgebnis := abs(aktErgebnis);
      totalErgebnis := 3;
   end
....

€: Ich suche diesmal keine Hilfe für das eigentliche Programmieren, sonder vielmehr logische, mathematische Ideen wie man die Codes am besten vergleicht!

[Medium]

Zunächst mal die Frage nach einer Info, die ganz von Anfang an schon sehr wichtig gewesen wäre eigentlich: Woher stammen die Buchstaben? Screenshots? Scans? Von gedrucktem oder Handschrift? Fotos? Mikrofilm? Danach richtet sich ganz stark wie tolerant das Verfahren sein darf/muss, und auch wie komplex.

Eine grundsätzlich ähnliche, aber andere Idee:
Lege für jedes Zeichen ein Musterbild an (wie jetzt deine Mustercodes quasi), und bilde die Differenz des aktuellen Kandidaten und aller Muster (ggf. durch Größen schon eingrenzbar). Dort wo nachher am meisten schwarze Pixel im Differenzbild sind, hast du eine ganz gute potentielle Übereinstimmung. Das kann man aber eben auch nur tun, wenn man sicher ist, alle Zeichen immer gleich eingrenzen zu können, und dass alle gleichen Zeichen im zu erkennenden Text sehr ähnlich sind. Aber das musst du bei deinem Verfahren oben ja genau so - daher nehme ich das mal als gegeben an.

Das wäre mit der simpelste Ansatz, der bei Screenshots immerhin perfekt arbeitet, und bei gescannten Drucksachen meist auch noch recht zuverlässig ist. Bei Handschrift wird man um ein NN nicht mehr herum kommen, und Fotos haben fast immer zu viele perspektivische Verzerrungen um sie unkorrigiert so nutzen zu können.

[MaToBe]

ich erstelle einen Screenshot auf dem gleichgroße gelbe Quadrate zu sehen sind, in die eine schwarze Ziffer geschrieben ist. Dies kann man auhc in meinem Anhang sehn, wie diese einzelnen Quadrate aussehn.

Da jedes Quadrat gleich groß ist, habe ich also die gleichen Ausgangsbedingugnen. Allerdings funktioniert mein Ansatz trotzdem leider nicht.

Zitat:

Lege für jedes Zeichen ein Musterbild an (wie jetzt deine Mustercodes quasi), und bilde die Differenz des aktuellen Kandidaten und aller Muster (ggf. durch Größen schon eingrenzbar). Dort wo nachher am meisten schwarze Pixel im Differenzbild sind, hast du eine ganz gute potentielle Übereinstimmung. Das kann man aber eben auch nur tun, wenn man sicher ist, alle Zeichen immer gleich eingrenzen zu können, und dass alle gleichen Zeichen im zu erkennenden Text sehr ähnlich sind. Aber das musst du bei deinem Verfahren oben ja genau so - daher nehme ich das mal als gegeben an.

Ich versteh nicht ganz den Unterschied? Ich benutzte doch auch ein Musterbild (in Zahlenform, die Codes) die dann mit jedem Quadrat abgeglichen werden.

[dacoder]

Ich denke, dass man es nicht all zu sehr von den Pixeln etc. abhängig machen sollte. Die Idee mit der Kohonen-Map erschien mir sehr plausibel.

Tools wie JDownloader erkennen Captchas, weiß zwar nicht, ob es dazu irgendwo eine Doku gibt, aber das wäre sicherlich mal, falls man dazu was im Internet findet, einen Schnupper wert.

[Medium]

Wenn es Screenshots klar lesbarer und nicht absichtlich unkenntlich gemachter Zeichen sind, ist ein NN oder Kohonen-Map völlig überdimensioniert.

Zitat:

Zitat von MaToBe

Ich versteh nicht ganz den Unterschied? Ich benutzte doch auch ein Musterbild (in Zahlenform, die Codes) die dann mit jedem Quadrat abgeglichen werden.

Ich sag ja, der Ansatz ist nicht unähnlich. Das Problem an den Codes ist allerdings, dass bei diesen die Positionsinformation mit der Farbinformation quasi vermischt wird, und eine einziger Pixel Unterschied in der Lage ist mehr Unterschied im "Fingerprint" zu erzeugen als sinnvoll. Ich finde gerade auch nicht wirklich gute Worte das brauchbar zu beschreiben :?.
Evtl. so: Ein einzelner isolierter Pixel Unterschied allein kann schon bedeuten, dass ein Fingerprint 2 Einträge mehr erhält, und somit fast nicht mehr mit dem eigentlich passenden zu identifizieren ist. Das wäre eine Schwachstelle.

So am Rande: Wenn die Screenshots zwischendurch nicht verlustbehaftet komprimiert wurden, sollten gleiche Zeichen doch spätestens nach Umwandlung in s/w wirklich 100%ig identisch sein. Brauchst du überhaupt ein intelligentes/tolerantes Verfahren!?

[MaToBe]

Zitat:

Zitat von Medium

Wenn es Screenshots klar lesbarer und nicht absichtlich unkenntlich gemachter Zeichen sind, ist ein NN oder Kohonen-Map völlig überdimensioniert.

Sie sind klar lesbar, also total überdimensionert, weshalb ich diese Varianten nicht verwende.

Zitat:

Zitat von Medium

Evtl. so: Ein einzelner isolierter Pixel Unterschied allein kann schon bedeuten, dass ein Fingerprint 2 Einträge mehr erhält, und somit fast nicht mehr mit dem eigentlich passenden zu identifizieren ist. Das wäre eine Schwachstelle.

Okay so hab ich jetzt mein Problem verstanden, super danke!

Zitat:

Zitat von Medium

So am Rande: Wenn die Screenshots zwischendurch nicht verlustbehaftet komprimiert wurden, sollten gleiche Zeichen doch spätestens nach Umwandlung in s/w wirklich 100%ig identisch sein. Brauchst du überhaupt ein intelligentes/tolerantes Verfahren!?

Komischerweise ist mir aufgegfallen, dass die einzelnen Ziffer-Bilder einer gleichen Ziffer durchaus geringfügig unterschiedlich sein können. Sie sind zwar immer gleich groß (gleiche Gesamtpixelanzahl) allerdings gibt es Unterschiede in den Farbnuancen. So hat zB eine 8 einmal nach der schwarz-weiß Umwandlung 81 schwarze Pixel und ein anderes mal nur 79. Dies kann man auch nicht durch das Angleichen des Toleranzwertes ausgleichen, hab ich schon probiert. Deshalb war das bloße Zählen der schwarzen Pixel auch zu Ungenau!

Zitat:

Zitat von Medium

Wenn die Screenshots zwischendurch nicht verlustbehaftet komprimiert wurden...

Ich lade den Screenshot in ein TImage. Ist das verlustbehaftet?

MFG und danke für euer Engagement

[Medium]

Zitat:

Komischerweise ist mir aufgegfallen, dass die einzelnen Ziffer-Bilder einer gleichen Ziffer durchaus geringfügig unterschiedlich sein können. [...]

Ah, ich seh's gerade. Dafür kannst du dich sehr wahrscheinlich bei ClearType bedanken :?. Ich fürchte nur die wirklich ganz schwarzen Pixel als schwarz anzuerkennen (also quasi Grenzwert 0) hilft auch nichts, oder? Aber bei dieser Art von Differenzen sollte mein Vorschlag sehr verlässliche Ergebnisse liefern.

Zitat:

Ich lade den Screenshot in ein TImage. Ist das verlustbehaftet?

Der wichtige Schritt ist: Speicherst du davor auf einen Datenträger, und wenn ja, in welchem Format? Die Anzeige ist völlig unerheblich. JPEG wäre z.B. verlustbehaftet, GIF nur was die Farbanzahl angeht, und da eh s/w ansteht wäre das relativ egal, BMP/PNG/TIF/TGA/DIB sind verlustfrei - um mal so die wichtigsten zu nennen. Wenn du den Screenshot direkt aus dem Clipboard holst, ist er in aller Regel auch verlustfrei übertragen.

[MaToBe]

Zitat:

Lege für jedes Zeichen ein Musterbild an (wie jetzt deine Mustercodes quasi), und bilde die Differenz des aktuellen Kandidaten und aller Muster (ggf. durch Größen schon eingrenzbar). Dort wo nachher am meisten schwarze Pixel im Differenzbild sind, hast du eine ganz gute potentielle Übereinstimmung.

Ich bin mir nicht sicher ob ich das ganz richtig verstanden habe. Ich soll quais das aktuelle Bild auf meinem Vergleichsbild abbilden und schauen ob es sich deckt?

Falls ja würde ich das so umsetzten:

Delphi-Quellcode:

// ~Pseudocode~
for x := 0 to Image.Width -1 do
begin
  for y := 0 to Image.Heiht -1 do
  begin
     if aktImage.Canvas.Pixel[x,y] = Image_8.Canvas.Pixel[x,y] then  //Wenn im aktuellen Bild und im Differenzbild ein Pixel die gleiche Farbe hat 
        inc(Anzahl_8);                                               //wird der Zähler für Ziffer 8 erhöht.
  end;
end;

//Die Zahl die den höchste Zähler hat ist die gesuchte Zahl.

Ist das deine grob deine Idee?

[Medium]

Das wäre eine Variante, jup. Mir fiel gerade noch ein, dass man das evtl. noch toleranter gegenüber des Antialiasings von ClearType gestalten könnte:

Die Bilder nicht in s/w, sondern Graustufen umwandeln. Dann

Delphi-Quellcode:

// ~Pseudocode~ 
Abweichung_8 := 0; // ist ein float
for x := 0 to Image.Width -1 do 
begin 
  for y := 0 to Image.Heiht -1 do 
  begin 
     Abweichung_8 := Abweichung_8 + Abs(GetRValue(aktImage.Canvas.Pixel[x,y]) - GetRValue(Image_8.Canvas.Pixel[x,y]));
  end; 
end; 
Abweichung_8 := Abweichung_8 / (255*Image.Width*Image.Height);

// Abweichung_* = 0 -> identisches Bild
// Abweichung_* = 1 -> maximaler Unterschied

Dadurch haut man sich evtl. weniger Fehler durch knappe Grenzwertentscheidungen beim s/w Konvertieren rein.

[MaToBe]

Ich hab es jetzt vollständig hinbekommen, bisher bei über 200 Zahlen kein Fehler.

Bei der Umwandlung in Graustufen traten wieder leichte Ungenauigkeiten auf, da manche Zahlen so eine Art "Glanzeffekt" haben. Deshalb habe ich dann doch wieder den Schwarz-Weiß Filter genommen (10% Toleranz), wodurch dieser Effekt ausgeklammert werden konnte.

Mit Hilfe von Mediums Ansatz des Abweichungsvergleichs läuft nun alles perfekt, weshalb ich mich mal wieder bei der DP aber besonders auch bei Medium bedanken möchte. Danke!

[mschaefer]

Vor Jahren gab es da mal einen Jugend forscht Beitrag und da hatte der Kandidat an den erkannten Objekten die Ecken Schnittpunkte und Rundungen gezählt. Das geht aber nur wenn sich die Zeichen nicht überlappen.

[MaToBe]

Heyho,

ich muss mich doch noch mal hier melden.

Ich habe mit eurer Hilfe folgenden Code zusammengeschrieben, um ein Bild eines Sudokus in ein SringGrind einzulesen.

Delphi-Quellcode:

//Sudoku einlesen
procedure TfrmScreen.SudokuEinlesen;
var m, n, x, y, h1, h2: integer;
begin
   h1 := 1;
   h2 := 1;
   x := xS;
   y := yS;

   for m := 0 to 8 do
   begin
     for n := 0 to 8 do
     begin
       if h1 <> 3 then
       begin
          sgSudoku.Cells[n,m] := PixelsearchBW(x,y);
          x := x + 29;
          inc(h1);
       end
       else
       begin
          sgSudoku.Cells[n,m] := PixelsearchBW(x,y);
          x := x + 32;
          h1 := 1;
       end;
     end;
     h1 := 1;

     if h2 <> 3 then
     begin
        y := y + 29;
        x := xS;
        inc(h2);
     end
     else
     begin
        y := y + 32;
        x := xS;
        h2 := 1;
     end;
   end;
end;


// Pixelsearch - Sucht im imgSudokuBW (Schwarz-Weiß Bild) die einzelnen Ziffern
function TfrmScreen.PixelSearchBW(x:integer; y:integer):string;
var m, n : integer;
    Abweichung_1, Abweichung_2, Abweichung_3, Abweichung_4,
    Abweichung_5, Abweichung_6, Abweichung_7, Abweichung_8,
    Abweichung_9 : real;
    kleinste : array[1..9] of real;
    kleinsteP : integer;
    i : integer;
    AnzahlSchwarz : integer;
begin
  Abweichung_1 := 0;
  Abweichung_2 := 0;
  Abweichung_3 := 0;
  Abweichung_4 := 0;
  Abweichung_5 := 0;
  Abweichung_6 := 0;
  Abweichung_7 := 0;
  Abweichung_8 := 0;
  Abweichung_9 := 0;
  AnzahlSchwarz := 0;

  for m := x to x+25 do
  begin
     for n := y to y+25 do
     begin
         Abweichung_1 := Abweichung_1 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img1.Canvas.Pixels[m-x,n-y]));
         Abweichung_2 := Abweichung_2 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img2.Canvas.Pixels[m-x,n-y]));
         Abweichung_3 := Abweichung_3 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img3.Canvas.Pixels[m-x,n-y]));
         Abweichung_4 := Abweichung_4 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img4.Canvas.Pixels[m-x,n-y]));
         Abweichung_5 := Abweichung_5 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img5.Canvas.Pixels[m-x,n-y]));
         Abweichung_6 := Abweichung_6 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img6.Canvas.Pixels[m-x,n-y]));
         Abweichung_7 := Abweichung_7 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img7.Canvas.Pixels[m-x,n-y]));
         Abweichung_8 := Abweichung_8 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img8.Canvas.Pixels[m-x,n-y]));
         Abweichung_9 := Abweichung_9 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img9.Canvas.Pixels[m-x,n-y]));

         if imgSudokuBW.Canvas.Pixels[m,n] = clBlack then
            inc(AnzahlSchwarz);

         //imgSudokuBW.Canvas.Pixels[m,n] := clRed;
     end;
  end;

  kleinste[1] := Abweichung_1 / (255*26*26);
  kleinste[2] := Abweichung_2 / (255*26*26);
  kleinste[3] := Abweichung_3 / (255*26*26);
  kleinste[4] := Abweichung_4 / (255*26*26);
  kleinste[5] := Abweichung_5 / (255*26*26);
  kleinste[6] := Abweichung_6 / (255*26*26);
  kleinste[7] := Abweichung_7 / (255*26*26);
  kleinste[8] := Abweichung_8 / (255*26*26);
  kleinste[9] := Abweichung_9 / (255*26*26);

  if AnzahlSchwarz <> 0 then
  begin
    kleinsteP := 1;
    for I := 2 to 9 do
    begin
       if kleinste[i] < kleinste[kleinsteP] then
          kleinsteP := i;
    end;
    Result := inttostr(kleinsteP);
  end
  else
    Result := '0';

end;

Vom Prinzip her tut der Code genau was er soll, aber es dauert mir zu lange. Für ein normales Sudoku braucht er etwa 2-3 Sekunden.

Deshalb möchte ich ihn nun optimieren und schneller bekommen.

Ich habe gehört/gelesen, dass Scanline bedeutend schneller arbeitet, doch leider habe ich keine Ahnung wie Scanline funtioniert. Pixelsearch war so schön einfach und anschaulich...

[MaToBe]

Ergänzung:

Ich habe folgende beide Algorithmen gefunden, aber als ich sie testweise implementieren wollte gab es bei beiden einen Fehler

"Bereichsüberschreitung bei Zeilenindex"

Klick 1
Klick 2

Ehrlichgesagt verstehe ich das nicht ganz weil beide Algoithmen ja schon vor längerer Zeit gepostet wurden und von diversen Personen getestet wurde. Andererseits habe ich es meiner Meinung nach richtig implementiert.

Sagt der Fehler, dass eine Schleife weiter läuft als sie eigentlich dürfte?

[Blup]

Eigentlich schon, aber ohne deinen Quellcode zu sehen ... :glaskugel:

[MaToBe]

Delphi-Quellcode:

type
  PRGBTripleArray = ^TRGBTripleArray;
  TRGBTripleArray = array [0..31] of TRGBTriple;
...
//Mein Code
// Pixelsearch - Sucht im imgSudokuBW (Schwarz-Weiß Bild) die einzelnen Ziffern
function TfrmScreen.PixelSearchBW(x:integer; y:integer):string;
var m, n : integer;
    kleinste : array[1..9] of real;
    kleinsteP : integer;
    i : integer;
    AnzahlSchwarz : integer;
begin

  AnzahlSchwarz := 0;
//
  for m := x to x+25 do
  begin
     for n := y to y+25 do
     begin
         if imgSudokuBW.Canvas.Pixels[m,n] = clBlack then
            inc(AnzahlSchwarz);

         //imgSudokuBW.Canvas.Pixels[m,n] := clRed;
     end;
  end;

  kleinste[1] := zncc(imgSudokuBW.Picture.Bitmap, img1.Picture.Bitmap);
  kleinste[2] := zncc(imgSudokuBW.Picture.Bitmap, img2.Picture.Bitmap);
  kleinste[3] := zncc(imgSudokuBW.Picture.Bitmap, img3.Picture.Bitmap);
  kleinste[4] := zncc(imgSudokuBW.Picture.Bitmap, img4.Picture.Bitmap);
  kleinste[5] := zncc(imgSudokuBW.Picture.Bitmap, img5.Picture.Bitmap);
  kleinste[6] := zncc(imgSudokuBW.Picture.Bitmap, img6.Picture.Bitmap);
  kleinste[7] := zncc(imgSudokuBW.Picture.Bitmap, img7.Picture.Bitmap);
  kleinste[8] := zncc(imgSudokuBW.Picture.Bitmap, img8.Picture.Bitmap);
  kleinste[9] := zncc(imgSudokuBW.Picture.Bitmap, img9.Picture.Bitmap);

  if AnzahlSchwarz <> 0 then
  begin
    kleinsteP := 1;
    for I := 2 to 9 do
    begin
       if kleinste[i] > kleinste[kleinsteP] then
          kleinsteP := i;
    end;
    Result := inttostr(kleinsteP);
  end
  else
    Result := '0';

end;

//Der Code aus dem Algorithmus-Thread
// ZeroMeanNormalizedCross-Correlation (ZNCC) (wird MAXIMAL bei guter Übereinstimmung)

function TfrmScreen.ZNCC(Bild1, Bild2: TBitmap):Single;
var
  x, y:integer;
  P1,P2:array[0..31] of PRGBTripleArray;

  a, b, zaehler, nenner1, nenner2, nenner, summe1, summe2, mean1, mean2:single;

  ZNCCvalue:Extended;
begin
  // ZeroMeanNormalizedCross-Correlation (ZNCC) (wird MAXIMAL bei guter Übereinstimmung)
  zaehler:=0.0;
  nenner1:=0.0;
  nenner2:=0.0;
  summe1:=0.0;
  summe2:=0.0;

  // Bildformat auf 24bit setzen (also ohne Alpha-Kanal)
  Bild1.PixelFormat := pf24bit;
  Bild2.PixelFormat := pf24bit;

  // Summen bilden
  for y:=0 to Bild1.Height-1 do
  begin
    P1[y]:=Bild1.ScanLine[y];
    P2[y]:=Bild2.ScanLine[y];

    for x:=0 to Bild1.Width-1 do
    begin
      summe1:=summe1+RGB2TColor(P1[y][x].rgbtRed, P1[y][x].rgbtGreen, P1[y][x].rgbtBlue);
      summe2:=summe2+RGB2TColor(P2[y][x].rgbtRed, P2[y][x].rgbtGreen, P2[y][x].rgbtBlue);
    end;
  end;

  mean1:=(1/power((Bild1.Width-1)+(Bild1.Height-1)+1,2))*summe1;
  mean2:=(1/power((Bild1.Width-1)+(Bild1.Height-1)+1,2))*summe2;
  for x:=0 to Bild1.Width-1 do
  begin
    for y:=0 to Bild1.Height-1 do
    begin
      a:=RGB2TColor(P1[y][x].rgbtRed, P1[y][x].rgbtGreen, P1[y][x].rgbtBlue)-mean1;
      b:=RGB2TColor(P2[y][x].rgbtRed, P2[y][x].rgbtGreen, P2[y][x].rgbtBlue)-mean2;
      zaehler:=zaehler+(a*b);
      nenner1:=nenner1+power(a, 2);
      nenner2:=nenner2+power(b, 2);
    end;
  end;
  nenner:=sqrt(nenner1*nenner2);

  if nenner>0 then
    ZNCCvalue:=zaehler/nenner
  else
    ZNCCvalue:=0.0;

  result:=ZNCCvalue*100;
end;

procedure TfrmScreen.TColor2RGB(const Color: TColor; var  R, G, B: Byte);
begin
  // convert hexa-decimal values to RGB
  R := Color and $FF;
  G := (Color shr 8) and $FF;
  B := (Color shr 16) and $FF;
end;

function TfrmScreen.RGB2TColor(const R, G, B: Byte): Integer;
begin
  // convert hexa-decimal values to RGB
  Result := R + G shl 8 + B shl 16;
end;

[Blup]

Der Code vergleicht zwei Bilder gleicher Größer von maximal 32*32 Pixeln.
Die erste Hälfte des Code soll dazu dienen, unterschiedliche Helligkeit der beiden Bilder auszugleichen. Allerdings werden einfach TColor-Werte addiert, das funktioniert nur mit Bildern in Graustufen.

[MaToBe]

das kann doch irgendwie aber nicht hinhaun was du da sagst.

Die Beschreibung zu dem Code von Christian Noeding lautet:

Zitat:

Auf der Suche nach einer Möglichkeit, mehrere Bilder miteinander zu vergleichen bin ich auf die Kreuz-Korrelation gestoßen. Mit dem folgenden Algorithmus kann man zwei Canvas beliebiger Größe miteinander vergleichen und bekommt das Ergebnis als Prozentwert der Übereinstimmung zurück. 100% bedeutet demnach perfekte Übereinstimmung.

[Blup]

Der Algorithmus ist im Prinzip für beliebige Größe geeignet, der Quellcode ist es nicht.

[MaToBe]

mmh tschuldigung das ich hier dauernd hin und her springe. Ich habe meinen Code jetzt mal versucht, von Pixel[x,y] auf Scanline umzustellen.

Alter Code - lief wunderbar nur zu langsam:

Delphi-Quellcode:

// Pixelsearch - Sucht im imgSudokuBW (Schwarz-Weiß Bild) die einzelnen Ziffern
function TfrmScreen.PixelSearchBW(x:integer; y:integer):string;
var m, n : integer;
    Abweichung_1, Abweichung_2, Abweichung_3, Abweichung_4,
    Abweichung_5, Abweichung_6, Abweichung_7, Abweichung_8,
    Abweichung_9 : real;
    kleinste : array[1..9] of real;
    kleinsteP : integer;
    i : integer;
    AnzahlSchwarz : integer;
begin
  Abweichung_1 := 0;
  Abweichung_2 := 0;
  Abweichung_3 := 0;
  Abweichung_4 := 0;
  Abweichung_5 := 0;
  Abweichung_6 := 0;
  Abweichung_7 := 0;
  Abweichung_8 := 0;
  Abweichung_9 := 0;
  AnzahlSchwarz := 0;

  for m := x to x+25 do
  begin
     for n := y to y+25 do
     begin
         Abweichung_1 := Abweichung_1 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img1.Canvas.Pixels[m-x,n-y]));
         Abweichung_2 := Abweichung_2 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img2.Canvas.Pixels[m-x,n-y]));
         Abweichung_3 := Abweichung_3 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img3.Canvas.Pixels[m-x,n-y]));
         Abweichung_4 := Abweichung_4 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img4.Canvas.Pixels[m-x,n-y]));
         Abweichung_5 := Abweichung_5 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img5.Canvas.Pixels[m-x,n-y]));
         Abweichung_6 := Abweichung_6 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img6.Canvas.Pixels[m-x,n-y]));
         Abweichung_7 := Abweichung_7 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img7.Canvas.Pixels[m-x,n-y]));
         Abweichung_8 := Abweichung_8 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img8.Canvas.Pixels[m-x,n-y]));
         Abweichung_9 := Abweichung_9 + Abs(GetRValue(imgSudokuBW.Canvas.Pixels[m,n]) - GetRValue(img9.Canvas.Pixels[m-x,n-y]));

         if imgSudokuBW.Canvas.Pixels[m,n] = clBlack then
            inc(AnzahlSchwarz);

         //imgSudokuBW.Canvas.Pixels[m,n] := clRed;
     end;
  end;

  kleinste[1] := Abweichung_1 / (255*26*26);
  kleinste[2] := Abweichung_2 / (255*26*26);
  kleinste[3] := Abweichung_3 / (255*26*26);
  kleinste[4] := Abweichung_4 / (255*26*26);
  kleinste[5] := Abweichung_5 / (255*26*26);
  kleinste[6] := Abweichung_6 / (255*26*26);
  kleinste[7] := Abweichung_7 / (255*26*26);
  kleinste[8] := Abweichung_8 / (255*26*26);
  kleinste[9] := Abweichung_9 / (255*26*26);

  if AnzahlSchwarz <> 0 then
  begin
    kleinsteP := 1;
    for I := 2 to 9 do
    begin
       if kleinste[i] < kleinste[kleinsteP] then
          kleinsteP := i;
    end;
    Result := inttostr(kleinsteP);
  end
  else
    Result := '0';

end;

Neuer Code - leider kaum schneller und liefert Falsche Zahlenwerte als Result zurück!

Delphi-Quellcode:

// Pixelsearch - Sucht im imgSudokuBW (Schwarz-Weiß Bild) die einzelnen Ziffern
function TfrmScreen.PixelSearchBW(x:integer; y:integer):string;
var m, n : integer;
    Abweichung_1, Abweichung_2, Abweichung_3, Abweichung_4,
    Abweichung_5, Abweichung_6, Abweichung_7, Abweichung_8,
    Abweichung_9 : real;
    kleinste : array[1..9] of real;
    kleinsteP : integer;
    i : integer;
    AnzahlSchwarz : integer;
    P, P1, P2, P3, P4,
    P5, P6, P7, P8, P9 : PByteArray;
begin
  Abweichung_1 := 0;
  Abweichung_2 := 0;
  Abweichung_3 := 0;
  Abweichung_4 := 0;
  Abweichung_5 := 0;
  Abweichung_6 := 0;
  Abweichung_7 := 0;
  Abweichung_8 := 0;
  Abweichung_9 := 0;
  AnzahlSchwarz := 0;

  imgSudokuBW.Picture.Bitmap.PixelFormat:= pf24Bit;

  for m := x to x+25 do
  begin
     P :=  imgSudokuBW.Picture.Bitmap.ScanLine[m];
     P1 := img1.Picture.Bitmap.ScanLine[m-x];
     P2 := img2.Picture.Bitmap.ScanLine[m-x];
     P3 := img3.Picture.Bitmap.ScanLine[m-x];
     P4 := img4.Picture.Bitmap.ScanLine[m-x];
     P5 := img5.Picture.Bitmap.ScanLine[m-x];
     P6 := img6.Picture.Bitmap.ScanLine[m-x];
     P7 := img7.Picture.Bitmap.ScanLine[m-x];
     P8 := img8.Picture.Bitmap.ScanLine[m-x];
     P9 := img9.Picture.Bitmap.ScanLine[m-x];
     for n := y to y+25 do
     begin
         Abweichung_1 := Abweichung_1 + Abs(GetRValue(P[n]) - GetRValue(P1[n-y]));
         Abweichung_2 := Abweichung_2 + Abs(GetRValue(P[n]) - GetRValue(P2[n-y]));
         Abweichung_3 := Abweichung_3 + Abs(GetRValue(P[n]) - GetRValue(P3[n-y]));
         Abweichung_4 := Abweichung_4 + Abs(GetRValue(P[n]) - GetRValue(P4[n-y]));
         Abweichung_5 := Abweichung_5 + Abs(GetRValue(P[n]) - GetRValue(P5[n-y]));
         Abweichung_6 := Abweichung_6 + Abs(GetRValue(P[n]) - GetRValue(P6[n-y]));
         Abweichung_7 := Abweichung_7 + Abs(GetRValue(P[n]) - GetRValue(P7[n-y]));
         Abweichung_8 := Abweichung_8 + Abs(GetRValue(P[n]) - GetRValue(P8[n-y]));
         Abweichung_9 := Abweichung_9 + Abs(GetRValue(P[n]) - GetRValue(P9[n-y]));

         if P[n] = clBlack then
            inc(AnzahlSchwarz);

         //imgSudokuBW.Canvas.Pixels[m,n] := clRed;
     end;
  end;

  kleinste[1] := Abweichung_1 / (255*26*26);
  kleinste[2] := Abweichung_2 / (255*26*26);
  kleinste[3] := Abweichung_3 / (255*26*26);
  kleinste[4] := Abweichung_4 / (255*26*26);
  kleinste[5] := Abweichung_5 / (255*26*26);
  kleinste[6] := Abweichung_6 / (255*26*26);
  kleinste[7] := Abweichung_7 / (255*26*26);
  kleinste[8] := Abweichung_8 / (255*26*26);
  kleinste[9] := Abweichung_9 / (255*26*26);

  if AnzahlSchwarz <> 0 then
  begin
    kleinsteP := 1;
    for I := 2 to 9 do
    begin
       if kleinste[i] < kleinste[kleinsteP] then
          kleinsteP := i;
    end;
    Result := inttostr(kleinsteP);
  end
  else
    Result := '0';

end;

Die Images 1 bis 9 werden auch auf pf24Bit gesetzt.

Warum funktioniert nach der Umstellung (habe wirklich nur diese eine Funktion geändert) mein Code nicht mehr?

Einen großen Performancegewinn habe ich auch nicht...

[Blup]

Du wirfst da einiges durcheinander, verwechselst Zeilen und Spalten, berücksichtigst nicht das 3 Byte zusammen die Farbe eines Pixel bestimmen, vergleichst Byte mit TColor...

Natürlich nicht getestet:

Delphi-Quellcode:

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

// Pixelsearch - Sucht im imgSudokuBW (Schwarz-Weiß Bild) die einzelnen Ziffern
function PixelSearchBW(x:integer; y:integer):string;
const
  XCOUNT = 26;
  YCOUNT = 26;
var
  m, n, i, kleinste: integer;
  AnzahlSchwarz : integer;
  Pixel : ^TBGR;
  RedValue: Integer;
  Ziffer: array[1..9] of record
    Bitmap: TBitmap;
    Pixel: ^TBGR;
    Abweichung: Real;
  end;
begin
  imgSudokuBW.Picture.Bitmap.PixelFormat:= pf24Bit;
  AnzahlSchwarz := 0;
  for i := Min(Ziffer) to Max(Ziffer) do
  begin
    with Ziffer[i] do
    begin
      case i of
        1: Bitmap := img1.Picture.Bitmap;
        2: Bitmap := img2.Picture.Bitmap;
        3: Bitmap := img3.Picture.Bitmap;
        4: Bitmap := img4.Picture.Bitmap;
        5: Bitmap := img5.Picture.Bitmap;
        6: Bitmap := img6.Picture.Bitmap;
        7: Bitmap := img7.Picture.Bitmap;
        8: Bitmap := img8.Picture.Bitmap;
        9: Bitmap := img9.Picture.Bitmap;
      else
        Abort;
      end;
      Bitmap.PixelFormat:= pf24Bit;
      Abweichung := 0;
    end;
  end;

  for n := 0 to YCOUNT - 1 do
  begin
    {Pixel verweist auf erste Zeile und erste Spalte}
    for i := Min(Ziffer) to Max(Ziffer) do
      Ziffer[i].Pixel := Ziffer[i].ScanLine[n];
    {Pixel verweist auf erste Zeile und erste Spalte im untersuchten Bereich}
    Pixel := imgSudokuBW.Picture.Bitmap.ScanLine[n + y];
    Inc(Pixel, x);
    for m := 0 to XCOUNT - 1 do
    begin
      {nur den Rotanteil vergleichen (Warum nicht die Gesamthelligkeit?)}
      RedValue := Pixel^.R;
      for i := Min(Ziffer) to Max(Ziffer) do
      begin
        with Ziffer[i] do
        begin
          Abweichung := Abweichung + Abs(Pixel^.R - RedValue);
          {Zeiger auf die nächste Spalte setzen}
          Inc(Pixel);
        end;
      end;

      if (Pixel^.B = 0) and (Pixel^.G = 0) and (Pixel^.R = 0) then
        Inc(AnzahlSchwarz);
      {Zeiger auf die nächste Spalte setzen}
      Inc(Pixel);
    end;
  end;

  if AnzahlSchwarz = 0 then
    Result := '0'
  else
  begin
    kleinste := Min(Ziffer);
    for i := kleinste + 1 to Max(Ziffer) do
    begin
       if Ziffer[i].Abweichung < Ziffer[kleinste].Abweichung then
         kleinste := i;
    end;
    Result := IntToStr(kleinste);
  end;
end;