Rozpoznawanie odręcznych cyfr

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:

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

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.

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ą.