czoper.devlog

.NET, CAD/CAM

Po pierwsze, krótki wstęp teoretyczny: CAPTCHA to „Completely Automated Public Turing test to tell Computers and Humans Apart” czyli automatyczny test na sprawdzenie, czy do danego formularza/danych/whatever dobiera się człowiek czy bot. O sensowności zastosowania tego rodzaju mechanizmów nie będę pisał, nie mnie to oceniać, przedstawię jednak problem, z którym się ostatnio zetknąłem.
Programiści to leniwi ludzie. Jeżeli mogą do czegoś zaprząc program, który zrobi to za nich – nie zastanawiają się ani chwili. Zwłaszcza, jeżeli po drodze jest do rozwiązania ciekawe zagadnienie 😉 Opisywanym, hipotetycznym zagadnieniem jest automatyczne zbieranie danych. Dostęp do nich jest publiczny, jednak każdy pojedynczy rekord można obejrzeć po odgadnięciu captchy. Przy pobieraniu np. 10 sztuk, zajmie to około 3-4 minut, jeżeli chcemy je jeszcze zapisać w formie nadającej się do późniejszej obróbki. Jeżeli liczba rekordów wzrośnie do 300.000, czas (a również i irytacja) wzrosną liniowo. W tym momencie do gry wchodzi automat.

Algorytm:

while (istnieją rekordy do pobrania) do
begin
    nawiąż połączenie z adresem formularza, uzupełnij ID żądanego rekordu
    pobierz obrazek z captch'ą
    rozpoznaj tekst na obrazku
    wpisz rozpoznany tekst na formularz, czekaj na odpowiedź serwera
    zapisz otrzymany rekord
end

Problemem jest instrukcja 5, chyba, że poczynimy dodatkowe założenia, analizując wcześniej obraz przy pomocy zaawansowanego narzędzia do obróbki grafiki komputerowej (tu był to MS Paint):

• tekst na obrazku składa się zawsze z 5 znaków
• znaki to małe litery alfabetu (bez polskich znaków) i cyfry
• czcionka: Times New Roman, rozmiar 38, czcionka wyboldowana
• znaki są zawsze na tej samej wysokości, obraz ma ten sam rozmiar (200×50 pikseli)
• na tle liter zostają dorysowane 2-3 losowe linie (cienkie na 1 piksel, koloru czarnego)

Preprocessing obrazu składa się z kilku kroków:

1. usunięcie tła, tło jest kolorowe (gradient od ciemniejszego do jaśniejszego niebieskiego), więc wszystkie piksele nie będące czarnymi (oczywiście z pewnym marginesem) zamieniamy na białe.
2. zamiana obrazu na monochromatyczny (ponieważ po operacji z punktu 1 mogły zostać piksele, dla których składowe koloru RGB miały wartość < 20, którą przyjąłem za wartość graniczną w punkcie 1)
3. usunięcie „przypadkowych” pikseli, czyli pojedynczych czarnych punktów

Algorytm:

Znaki = {"a", .. , "z", "0", .. , "9"}
foreach znak in Znaki do
begin
    maska = new bitmap(200px x 50px)
    umieść znak na bitmapie maska na odpowiedniej wysokości
    przytnij maskę tak, aby zostawić 3px marginesu z lewej i prawej strony

    procenty := 0;
    for i := 1 to (200 - maska.szerokość) do
    begin
        for j := 1 to maska.szerokość do
            for k := 1 to maska.wysokość do
                if (maska[j, k] = obraz[i + j, k]) procenty := procenty + 1;
    end
    procenty := procenty / (maska.szerokość * maska.wyskość)
    zapisz parę (znak, procenty)
end

Poniżej 2 przykładowe obrazy (po preprocessingu) oraz dwie przykładowe maski:

Aby upodobnić nieco algorytm do sposobu działania sieci neuronowej, aplikacja została „nauczona” odpowiednich liter. Zostało wygenerowanych 100 obrazów, które zostały rozpoznane przez człowieka. Na tej postawie aplikacja zapamiętała udział procentowy dla każdej z występujących liter. Wartości te oscylowały wokół 95%.

Teraz algorytm rozpoznawania captch’y wygląda następująco:

1. wczytaj obraz
2. wykonaj preprocessing
3. dla każdego znaku wykonaj krok z maską (opisany wyżej) i jeżeli procentowy wynik leży w granicach +- 1.5% od wartości uzyskanej w testach dla danego znaku – uznaj, że ta litera występuje w tym miejscu
4. dla wynikowego zbioru 5 liter rozpoznanych na obrazie, posortuj je rosnąco po pozycji, na której występują
5. zwróć napis na obrazie w postaci string’a

Opracowany algorytm ma skuteczność około 95%, działa w czasie rzeczywistym (analizowanie obrazu wraz z preprocessingiem trwa poniżej 1s).

Wniosek z tej pracy jest taki: jeżeli już używać captch’y to takiej, która oprócz porządniejszego zabezpieczenia robi coś dobrego, np. reCaptcha, która pomaga przenosić książki do postaci zdigitalizowanej (więcej na stronie aplikacji)

Be Sociable, Share!

• 
•