Rozpoznawanie odręcznych cyfr

22

Twoim zadaniem jest odczytanie obrazu zawierającego odręczną cyfrę, rozpoznanie i wydrukowanie cyfry.

Dane wejściowe: obraz w skali szarości 28 * 28, podany jako ciąg 784 liczb tekstowych od 0 do 255, oddzielonych spacją. 0 oznacza biały, a 255 oznacza czarny.

Wyjście: rozpoznana cyfra.

Punktacja: Przetestuję twój program przy użyciu 1000 obrazów z zestawu szkoleniowego bazy danych MNIST (przekonwertowanego na formularz ASCII). Wybrałem już obrazy (losowo), ale nie opublikuję listy. Test musi zakończyć się w ciągu 1 godziny i określi n- liczbę poprawnych odpowiedzi.
nmusi mieć co najmniej 200, aby Twój program się zakwalifikował. Jeśli rozmiar twojego kodu źródłowego wynosi s, twój wynik zostanie obliczony jako s * (1200 - n) / 1000. Najniższy wynik wygrywa.

Zasady:

  • Twój program musi odczytać obraz ze standardowego wejścia i zapisać cyfrę na standardowym wyjściu
  • Brak wbudowanej funkcji OCR
  • Brak bibliotek innych firm
  • Brak zewnętrznych zasobów (plików, programów, stron internetowych)
  • Twój program musi być uruchomiony w systemie Linux przy użyciu darmowego oprogramowania (Wine jest dopuszczalne, jeśli to konieczne)
  • Kod źródłowy musi używać tylko znaków ASCII
  • Podaj swój szacunkowy wynik i unikalny numer wersji przy każdej modyfikacji odpowiedzi

Przykładowe dane wejściowe:

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

Nawiasem mówiąc, jeśli wstawisz ten wiersz do danych wejściowych:

P2 28 28 255

otrzymasz prawidłowy plik obrazu w formacie pgm z odwróconymi / negowanymi kolorami.

Tak to wygląda z prawidłowymi kolorami: cyfra

Przykładowe dane wyjściowe:

5

Tabele:

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
źródło
Powiązane, ale niezupełnie takie same (nie jest wyzwaniem, ale bardzo przydatne do znalezienia kodów lateksowych): detexify.kirelabs.org/classify.html . Rozpoznaje także liczby.
Justin
1
Czy możemy bezpiecznie założyć, że musimy brać pod uwagę tylko czarne piksele? > 127 pikseli? Co możemy założyć?
Justin
2
Zwłaszcza jeśli jest to pytanie dotyczące kodu golfowego, proszę ograniczyć wprowadzanie czarno-białych danych. Ludzie robią całe swoje kariery, rozwiązując ten problem, bez konieczności liczenia znaków w kodzie. Nie publikowanie wybranych postaci jest sposobem na powstrzymanie oszustwa i sprawia, że ​​jest to rodzaj hazardu ... a biorąc pod uwagę, że pisanie sztucznej inteligencji tutaj jest nieuzasadnione, zabawą jest wykonywanie dziwnej heurystyki, a następnie sprawdzanie, jak dobrze robi to w turnieju kontra konkurencja.
Dr. Rebmu
3
@aditsu Tak, każdy może to zrobić źle. Ale nie prosisz o to, aby było źle, chcesz, aby ktoś „wygrał” w konkursie, w którym mierzona jest liczba postaci. Wydaje mi się, że odrobina problemu jest bardziej realistyczna dla hobbystycznych łamigłówek. Ograniczenie wkładu wydaje się dobrym początkiem, aby uczynić go rozsądnym. Sugerowałbym wstępny przekaz na wejściu, aby powiedzieć, że jest czarno-biały.
Dr. Rebmu
2
@ Dr.Rebmu i wszyscy inni, którzy chcą czarno-białych danych wejściowych: zachęcamy do konwersji danych wejściowych za pomocą progu, takiego jak 128. Sprawdziłem, a cyfry są nadal rozpoznawalne (przez mój mózg). Możesz wypróbować również inne progi, mogą dać lepsze wyniki.
aditsu

Odpowiedzi:

6

GolfScript 6D (v2: wynik szacunkowy 101 * 0,63 ~ = 64)

Jest to zupełnie inne podejście do mojej wcześniejszej odpowiedzi GolfScript, więc sensowniej jest opublikować ją jako osobną odpowiedź w wersji 1 niż edytować inną odpowiedź i utworzyć tę wersję 2.

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

Nie golfił

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

Wyjaśnienie

Surowym problemem jest klasyfikacja punktów w przestrzeni 784-wymiarowej. Jednym standardowym podejściem jest redukcja wymiarów: identyfikacja małego podzbioru wymiarów, który zapewnia wystarczającą siłę odróżniającą do dokonania klasyfikacji. Oceniłem każdy wymiar i każdy możliwy próg, aby zidentyfikować 18 par (wymiar, zakres progu), które wyglądały obiecująco. Następnie wybrałem środek każdego zakresu progu i oceniłem 6-elementowy podzbiór 18 par. Wreszcie zoptymalizowałem próg dla każdego wymiaru najlepszej projekcji 6-D, zwiększając jego dokładność z 56,3% do 56,6%.

Ponieważ rzut ma 6 wymiarów i dla każdego wymiaru stosuję prosty próg, końcowa tabela przeglądowa potrzebuje tylko 64 elementów. Wydaje się, że nie jest szczególnie ściśliwy, więc głównym celem gry w golfa jest konwersja bazy danych obu tabel wyszukiwania (lista wymiarów i progów oraz mapa półprzestrzeni na mapę cyfrową) i współdzielenie kodu konwersji bazy.

Peter Taylor
źródło
7
Zgubiłeś mnie w „784-wymiarowej przestrzeni” ;-)
Digital Trauma
Obawiam się, że gdzieś jest błąd, otrzymuję tylko 37 poprawnych odpowiedzi. Poza tym sprawiasz, że wszystko jest trochę niejednoznaczne, czy możesz dodać (1) i (2) (tak jak ja) lub coś podobnego do swoich nagłówków?
aditsu
@aditsu, prosty błąd logiczny. Teraz naprawione.
Peter Taylor
Więc w zasadzie próbujesz 6 „odpowiednich” pikseli, każdy z innym progiem, uzyskując 6 bitów?
aditsu
Dokładnie @aditsu.
Peter Taylor
5

GolfScript 3x3 (v1: szacowany wynik 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/{))*~}%=

Lub w podsumowaniu

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

Wyjaśnienie

Moje podejście na wysokim poziomie to:

  1. Próg pikseli: jeśli piksel jest powyżej, t1ustaw go na 1; inaczej do 0.
  2. Zgrupuj piksele. Początkowo rozbiłem siatkę 28 x 28 na siatkę 4x4 (każda podsiatka ma 7 x 7 pikseli); ale rozbicie go na siatkę 3x3 (podsiatki to 10x10, 10x8 lub 8x8 pikseli) daje ogromne zmniejszenie rozmiaru tabeli odnośników przy jednoczesnym spadku wskaźnika dokładności z około 56% do około 40%.
  3. Zsumuj ponownie piksele w każdej grupie i ponownie ustaw wartość progową: jeśli liczba ustawionych pikseli jest większa, t2oceń grupę jako 1; inaczej jak 0.
  4. Wykonaj wyszukiwanie w tabeli według wektora wyników grupowych. (Tabela jest kompresowana przy użyciu kodowania długości przebiegu i standardowej sztuczki konwersji bazy. Większość wyborów t1i t2pozostawia od 50% do 63% tabeli jako wartości „nie przejmuj się”, które można łączyć z sąsiednimi wartościami, aby zwiększyć długości przebiegów; średnia długość przebiegów w mojej tabeli v1 wynosi 3,6).

Okazuje się, że ustawienie t1=t2=0, choć nie optymalne, nie jest dalekie od najlepszych wartości t1i t2pod względem dokładności; jest całkiem dobry pod względem ściśliwości tabeli; i pozwala mi połączyć dwie operacje progowania w []*0-!!(spłaszcz macierz 2D do 1D; usuń 0s; sprawdź, czy jest pusta).

Tabela przeglądowa podaje najbardziej prawdopodobnego kandydata na dany wektor wyników grupowych. Może być również możliwe poprawienie wyniku poprzez identyfikację wpisów w tabeli, które można zmienić tak, że poprawiona ściśliwość tabeli przeważa nad zmniejszoną dokładnością.

Peter Taylor
źródło
Wspaniale, miałem podobny pomysł, ale nie wyobrażałem sobie, że można go tak dobrze skompresować. Teraz myślę, że potrzebowałem większego nacisku na dokładność: p, ale nie planuję tego zmieniać.
aditsu