Rozpoznávání captcha obrázků Tomáš Pop
[email protected] www.vanocnibesidka.wz.cz Lukáš Bajer
[email protected]
Idea - cíl • Captcha – bezpečnostní kód, který se opisuje – má zabránit automatizovanému využití webvé služby
• snaha o obecný nástroj – každá typ captcha obrázků je jiný
• modulární stavba – obrazové procesory, separátory písmen, rozpoznávací algoritmy
• => • snadné učení „jakýchkoli“ dalších typů captcha souborů – učení z adresáře 2
Postup • Příprava obrázku – prahování (tresholding) • převedení na černobílý obrázek ~ vektor 0, 1
– aplikace různých filtrů • před a po prahování • oddělení jednotlivých písmen, která po prahování splývají
– separace písmen • flat-fill • po sloupcích
• Učení neuronové sítě – backropagation • mnoho volitelných parametrů – které jsou asi ty správné? • s počtem znaků prudce roste počet epoch nutných k naučení 3
Příprava obrázku • filtry, prahování
4
Separace písmen, normalizace • Podle největšího písmena je vybrána velikost – na ní se pak ostatní písmena „roztáhnou“ – pro Telefonicu O2 je to 14 x 16 pixelů • Vstupní vektory velikosti 288
5
Problémy • písmena je někdy těžké oddělit – překryvy písmen – tečky, háčky, čárky • co je šum, co tam patří • ke kterému písmenu znaménko patří
• skoro se vším se jde vyrovnat – ale znamená to hodně práce • psaní speciálních filtrů pro typ obrázků • ztráta původní myšlenky
– Obecné filtry a separátory písmen nemají vždy dobré výsledky • flat-fill Telefonice uřeže tečky nad i
6
Neuronové sítě - BackPropagation • Vrstevnatá sít, zpětné šíření – implementovaná s momentem učení a bez prahů neuronů – použitá topologie 288 – 50 – 32, • odzkoušeno 288 – 90 – 32, 288 – 60 – 40 – 32
– pro několik vzorů se učí rychle a dobře • pro 7 Telefonicy písmen po 200 epochách úspěšnost na učící množině 100%, na testovací okolo 95%
– hodně vzorů se učí pomalu a ... • pro 32 písmen Telefonicy je po 200 epochách úspěšnost asi 25%, po 600 epochách asi 50%, po 1000 epochách asi 72% – na učící množině
• i po 1000 epochách se síť učí (na validační množině se zlepšuje) – akorát se mi nechtělo čekat déle než přes noc
7
Neuronové sítě - BackPropagation • Parametry jsou důležité – experimentálně jde učení hodně zrychlit • • • •
lambda = 0,2 moment učení = 1 parametr učení 0,5 velikost epochy okolo 30 vzorů
• Výběr pořadí vzorů k učení – vzory nevolit náhodně • ale tak, aby se střídali písmena • jinak se síť naučí vzor, který dostane hodně krát na začátku a nasaturuje se • Jde tomu zabránit malým parametrem učení – ale pak se síť učí pomalu 8
Neuronové sítě - BackPropagation • Zkušenosti, poučení – Je lepší se učit pomalu a dlouho • ale zas to nepřehnat, dojde k přeučení. – jak dochází ke zhoršení na validační množině častěji než v každé 4 epoše, síť už se moc nezlepší
– Předzpracování vzorů je klíčové • ostatní asi jako u všeho...
– Vektory, které jsou si „podobné“ se síť učí špatně • např: 2 x z, ale toho jsou si výrobci vědomi, většinou se nepoužívají znaky 1 – l, 0 – o, 3 – 8,...
– Inicializace vah je klíčová • pro rychlost učení i výsledky – experimentálně nejlepší random okolo 0, 001 – 0, 20
9
Neuronové sítě - BackPropagation • Kam dál – PCA analýza – vzorů je obvykle 32, tj vektory délky 5 až 6 by mohly teoreticky stačit – délka vstupního vektoru je 288
– PCA analýza v Matlabu
>> [pn, ps1] = mapstd(P); >> [ptrans, ps2] = processpca(pn, 0.02); >> whos ptrans P Name Size Bytes
Class
P 288x340 783360 double array • PCA analýza ignorující ptrans 13x340 35360 double array vektory přispívající k celkovému rozptylu 2% a méně redukuje původních 288 na 14 bitů • za cenu přijatelné ztráty přesnosti můžeme snížit i počet skrytých neuronů na 15 (bez PCA: MSE = 0.00008, zastavení pro MSE < 0.0001, s PCA: MSE = 0.0008, zastavení zhoršením validač. testů)
– nalezené normalizační a konverzní matice lze snadno použít v PHP 10
Neuronové sítě - BackPropagation – Implementace v jiném jazyce a efektivněji • PHP není pro několika hodinové výpočty stavěné • implementace je školní – snadno čitelná, snadno zkontrolovatelná, ale nepříliš efektivní
• trénink sítě např. v Matlabu (neděje se často), rozpoznávání sítí on-line v PHP již není výpočetně náročné
– Víc experimentovat s parametry a topologií • topologii a parametry jsem vyčetl z článku o OCR přes NN – měli o hodně rychlejší učení (na počet epoch) » => buď máme chybu v implementaci (spíš ne) » => měli jiné podmínky a možná by se jiná síť učila lépe
– Implementace dalších učících algoritmů • učení s momentem (traingdm) dosahuje chyby MSE = 0.01 po cca 1000 epochách, MSE = 0.005 po cca 10 000 ep. • Resilient Backpropagation (trainrp) se zastavuje po 22 epochách s chybou cca 10-6
Reálná data
12
Neuronové sítě - BackPropagation • Výsledky a průběh učení – Pro 7 písmen z Telefonicy – ne zcela oddělená učící a validační množina • ne stejná • obsahovala asi ½ učících vzorů (jsou si hodně podobná)
• V tabulce je konečný výsledek učení – 7 písmen se síť naučí spolehlivě během asi 500 epoch • tj 250 sekund u mě na počítači (při vstupu 10x11px)
– Výsledek na dalších snímcích je po 900 epochách
• Na grafech je průběh učení – Chyba stále klesá – rozdíl chyby má celkem zajímavý průběh • zpočátku občas záporná, což moc není vidět
– Grafy jsou upravené, tak aby byly pěkně čitelné
13
Reálná data - Výsledky
14
Reálná data – Vývoj chyby
15
Reálná data – Vývoj odpovědi
16
Reálná data - hodnocení • Na Telefonice... – věříme, že by po dost dlouhém učení by byla dostatečně velká síť reálně použitelná
• Na Wikipedii... – věříme, že by po dost dlouhém učení by byla dostatečně velká síť reálně použitelná – Úspěšnost je ale výrazně menší než na Telefonice • ale pro několik (5) vzorů se to zdálo slibné
– Zde i na Telfonice není problém poznat, zda jsme uspěli • => opakování pokusů :-)
• Na Google... – mizerná úspěšnost • hlavně předzpracování • i učení nic moc
– Vyžadovalo by hodně práce, a úspech není rozhodně zaručen
17