Erkennen Sie handschriftliche Ziffern

22

Ihre Aufgabe ist es, ein Bild mit einer handgeschriebenen Ziffer zu lesen, diese zu erkennen und auszudrucken.

Eingabe: Ein 28 * 28-Graustufenbild, das als Folge von 784 durch Leerzeichen getrennten Klartextnummern von 0 bis 255 angegeben wird. 0 bedeutet weiß und 255 bedeutet schwarz.

Ausgabe: Die erkannte Ziffer.

Wertung: Ich werde Ihr Programm mit 1000 Bildern aus dem MNIST-Datenbank- Trainingsset (konvertiert in ASCII-Form) testen . Ich habe die Bilder bereits zufällig ausgewählt, werde die Liste jedoch nicht veröffentlichen. Der Test muss innerhalb einer Stunde abgeschlossen sein und bestimmt n- die Anzahl der richtigen Antworten.
nmuss mindestens 200 sein, damit sich Ihr Programm qualifiziert. Wenn die Größe Ihres Quellcodes ist s, wird Ihre Punktzahl wie folgt berechnet s * (1200 - n) / 1000. Die niedrigste Punktzahl gewinnt.

Regeln:

  • Ihr Programm muss das Bild von der Standardeingabe lesen und die Ziffer in die Standardausgabe schreiben
  • Keine eingebaute OCR-Funktion
  • Keine Bibliotheken von Drittanbietern
  • Keine externen Ressourcen (Dateien, Programme, Websites)
  • Ihr Programm muss unter Linux mit frei verfügbarer Software lauffähig sein (Wine ist bei Bedarf akzeptabel)
  • Der Quellcode darf nur ASCII-Zeichen enthalten
  • Bitte geben Sie Ihre geschätzte Punktzahl und eine eindeutige Versionsnummer jedes Mal an, wenn Sie Ihre Antwort ändern

Beispiel Eingabe:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 18 18 18 126 136 175 26 166 255 247 127 0 0 0 0 0 0 0 0 0 0 0 0 30 36 94 154 170 253 253 253 253 253 225 172 253 242 195 64 0 0 0 0 0 0 0 0 0 0 0 49 238 253 253 253 253 253 253 253 253 251 93 82 82 56 39 0 0 0 0 0 0 0 0 0 0 0 0 18 219 253 253 253 253 253 198 182 247 241 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80 156 107 253 253 205 11 0 43 154 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 1 154 253 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 139 253 190 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 190 253 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35 241 225 160 108 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 81 240 253 253 119 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 186 253 253 150 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 93 252 253 187 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 249 253 249 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 130 183 253 253 207 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 39 148 229 253 253 253 250 182 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 114 221 253 253 253 253 201 78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 66 213 253 253 253 253 198 81 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 171 219 253 253 253 253 195 80 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55 172 226 253 253 253 253 244 133 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 253 253 253 212 135 132 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Übrigens, wenn Sie diese Zeile der Eingabe voranstellen:

P2 28 28 255

Sie erhalten eine gültige Bilddatei im PGM-Format mit invertierten / negierten Farben.

So sieht es mit richtigen Farben aus: Ziffer

Beispielausgabe:

5

Stand:

No.| Name         | Language   | Alg | Ver | n   | s   |  Score
----------------------------------------------------------------
 1 | Peter Taylor | GolfScript | 6D  | v2  | 567 | 101 |  63.933
 2 | Peter Taylor | GolfScript | 3x3 | v1  | 414 | 207 | 162.702
aditsu
quelle
Verwandte, aber nicht ganz dieselben (keine Herausforderung, aber sehr nützlich zum Auffinden der Latex-Codes): detexify.kirelabs.org/classify.html . Es erkennt auch Zahlen.
Justin
1
Können wir mit Sicherheit davon ausgehen, dass wir nur die schwarzen Pixel berücksichtigen müssen? Die> 127 Pixel? Was können wir annehmen?
Justin
2
Insbesondere wenn es sich um eine Code-Golf-Frage handelt, beschränken Sie sich bitte auf Schwarz-Weiß-Eingaben. Die Leute machen ihre gesamte Karriere damit, dieses Problem zu lösen, ohne die Zeichen in ihrem Code zählen zu müssen. Wenn Sie nicht veröffentlichen, welche Charaktere Sie ausgewählt haben, können Sie das Betrügen stoppen und es zu einem Glücksspiel machen. Da es für die Leute unvernünftig ist, KI hier zu schreiben, macht es Spaß, eine seltsame Heuristik zu betreiben und dann zu sehen, wie gut sie sind es tut im Turnier gegen Wettbewerb.
Dr. Rebmu
3
@aditsu Ja, jeder kann es schlecht machen. Aber Sie wollen nicht, dass es schlecht gemacht wird. Sie möchten, dass jemand in einem Wettbewerb "gewinnt", in dem die Anzahl der Charaktere gemessen wird. Ich halte es für realistischer, das Problem ein wenig zu reduzieren, wenn man Rätsel löst. Das Einschränken der Eingabe scheint ein guter Anfang zu sein, um sie sinnvoll zu gestalten. Ich würde vorschlagen, dass die Eingabe vorab in Schwarzweiß angezeigt wird.
Dr. Rebmu
2
@ Dr.Rebmu und alle anderen, die eine Schwarzweiß-Eingabe wünschen: Sie können die Eingabe auch mit einem Schwellenwert wie 128 konvertieren. Ich habe dies überprüft und die Ziffern sind immer noch erkennbar (von meinem Gehirn). Sie können auch andere Schwellenwerte ausprobieren, da diese möglicherweise bessere Ergebnisse liefern.
Aditsu

Antworten:

6

GolfScript 6D (v2: geschätzte Punktzahl 101 * 0,63 ~ = 64)

Dies ist eine ganz andere Herangehensweise an meine frühere GolfScript-Antwort. Daher ist es sinnvoller, sie als separate Antwort in Version 1 zu veröffentlichen, als die andere Antwort zu bearbeiten und diese Version 2 zu erstellen.

~]:B;569'!EM,R.==|%NL2+^=1'{{32-}%95{base}:^~\^}:&~2/{~B=<}%2^10'#]8Y,;KiZfnnRsDzPsvQ!%4C&..z,g,$m'&=

Ungolfed

~]:B;
[30 183 21 378 31 381 7 461 113 543 15 568]
2/{~B=<}%2base
7060456576664262556515119565486100005262700292623582181233639882 10base
=

Erläuterung

Das eigentliche Problem ist die Klassifizierung von Punkten in einem 784-dimensionalen Raum. Ein Standardansatz ist die Dimensionsreduzierung: Identifizieren einer kleinen Teilmenge von Dimensionen, die eine ausreichende Unterscheidungskraft für die Klassifizierung bieten. Ich habe jede Dimension und jeden möglichen Schwellenwert bewertet, um 18 Paare (Dimension, Schwellenwertbereich) zu identifizieren, die vielversprechend aussahen. Ich habe dann die Mitte jedes Schwellenwertbereichs ausgewählt und 6-Element-Teilmengen der 18 Paare ausgewertet. Schließlich habe ich den Schwellenwert für jede Dimension der besten 6-D-Projektion optimiert und die Genauigkeit von 56,3% auf 56,6% verbessert.

Da die Projektion in 6 Dimensionen erfolgt und für jede Dimension ein einfacher Schwellenwert angewendet wird, benötigt die endgültige Nachschlagetabelle nur 64 Elemente. Es scheint nicht besonders komprimierbar zu sein, daher besteht die Hauptaufgabe darin, beide Nachschlagetabellen (die Liste der Dimensionen und Schwellenwerte sowie den Halbraumvektor in eine Ziffernkarte) mit der Basis umzuwandeln und den Basisumwandlungscode gemeinsam zu verwenden.

Peter Taylor
quelle
7
Du hast mich im "784-dimensionalen Raum" verloren ;-)
Digitales Trauma
Ich fürchte, irgendwo liegt ein Fehler vor, ich bekomme nur 37 richtige Antworten. Außerdem machst du die Dinge ein bisschen mehrdeutig, könntest du bitte (1) und (2) (wie ich) oder etwas Ähnliches zu deinen Überschriften hinzufügen?
Aditsu
@Aditsu, einfache Logikfehler. Jetzt behoben.
Peter Taylor
Im Grunde genommen werden also 6 "relevante" Pixel mit jeweils unterschiedlichen Schwellenwerten abgetastet, um 6 Bits zu erhalten?
Aditsu
@Aditsu, genau.
Peter Taylor
5

GolfScript 3x3 (v1: geschätzte Punktzahl 207 * 0,8 ~ = 166)

~]28/10:?/{zip?/{[]*0-!!}/}%2{base}:^~'"yN(YZ5B 7k{&w,M`f>wMb>}F2A#.{E6T9kNP_s 3Q?V`;Z\'C-z*kA5M@?l=^3ASH/@*@HeI@A<^)YN_bDI^hgD>jI"OUWiGct%7/U($*;h*<"r@xdTz6x~,/M:gT|\\:#cII8[lBr<%0r&y4'{32-}%95^?^2/{))*~}%=

Oder im Überblick,

~]28/10:?/{zip?/{[]*0-!!}/}%2{base}:^~'MAGIC STRING'{32-}%95^?^2/{))*~}%=

Erläuterung

Mein Ansatz auf hohem Niveau ist:

  1. Schwelle für die Pixel: Wenn das Pixel darüber liegt, t1setzen Sie es auf 1; sonst zu 0.
  2. Gruppieren Sie die Pixel. Zunächst habe ich das 28x28-Raster in ein 4x4-Raster zerlegt (jedes Teilraster hat eine Größe von 7x7 Pixel). Das Aufteilen in ein 3x3-Raster (Subraster mit 10x10, 10x8 oder 8x8 Pixeln) führt jedoch zu einer massiven Reduzierung der Größe der Nachschlagetabelle, während die Genauigkeit von ungefähr 56% auf ungefähr 40% gesenkt wird.
  3. Summiere die Pixel in jeder Gruppe und den Schwellenwert erneut: Wenn die Anzahl der eingestellten Pixel über dem t2Wert liegt, bewerte die Gruppe als 1; sonst wie 0.
  4. Führen Sie eine Tabellensuche nach dem Vektor der Gruppenergebnisse durch. (Die Tabelle wird unter Verwendung der Lauflängencodierung und des Standardtricks zur Basiskonvertierung komprimiert. Die meisten Auswahlen von t1und t2lassen zwischen 50% und 63% der Tabelle als "egal" -Werte, die mit benachbarten Werten kombiniert werden können, um zuzunehmen Lauflängen; die durchschnittliche Lauflänge in meiner v1-Tabelle beträgt 3,6).

Es stellt sich heraus, dass die Einstellung t1=t2=0zwar nicht optimal ist, aber nicht weit von den besten Werten t1und t2in Bezug auf die Genauigkeit entfernt ist. ist ziemlich gut in Bezug auf die Tischkomprimierbarkeit; und ermöglicht mir, die beiden Schwellenoperationen zu kombinieren []*0-!!(2D-Array auf 1D reduzieren; 0s entfernen ; prüfen, ob es leer ist).

Die Nachschlagetabelle gibt den wahrscheinlichsten Kandidaten für den gegebenen Vektor der Gruppenbewertungen an. Es kann durchaus möglich sein, die Punktzahl zu verbessern, indem Tabelleneinträge identifiziert werden, die so geändert werden können, dass die verbesserte Komprimierbarkeit der Tabelle die verringerte Genauigkeit überwiegt.

Peter Taylor
quelle
Super, ich hatte eine ähnliche Idee, konnte mir aber nicht vorstellen, dass sie so gut komprimiert werden kann. Jetzt denke ich, dass ich mehr Wert auf Genauigkeit legen muss: p, aber ich habe nicht vor, dies zu ändern.
Aditsu