CGI captcha - enkel captcha. Dekoding av captcha i Python Python gjenkjenner captcha
God dag! Nylig, for noen behov, var en captcha i Python nødvendig fra "nysgjerrige" mennesker. Jeg så på Google og ingenting normalt uten Django Jeg så det ikke. Som et resultat kom jeg til den konklusjonen at jeg ikke vil skrive den som en separat WSGI søknad, men ganske enkelt CGI manus.
Pakken valgt for arbeid med bilder var Python bildebibliotek. PIL gir dessverre noe magre muligheter i forhold til GD2 i PHP.
Du kan laste ned pakken for Python versjon 2 og 3 herfra: http://www.lfd.uci.edu/~gohlke/pythonlibs/
Jeg vil med en gang påpeke at den er brukt Python 3.1, selv om jeg tror at den også vil kjøre på Python 2.6+.
Og så, til slutt bør vi få en bildegenerering på 5-6 tegn på en flerfarget bakgrunn.
Siden jeg ikke legger ut et arkiv med alt klart her, vil vi gjøre alt i henhold til manualen.
Kataloger og deres hierarki:
Cgi-bin
--captcha
--bakgrunner
--fonter
--index.py
Jeg tror det er klart at i cgi-bin-mappen er det en captcha-mappe der bakgrunner og fonter og selve index.py-skriptet er plassert.
Nå trenger vi bakgrunner. Vi skriver «bakgrunner» i Google.Bilder og laster ned 15-20 stykker. Og du må lage slike rektangler som måler 200x60 px i formatet JPEG.
Vi kaster alt inn i bakgrunnsmappen.
Nå fontene. Vi er interessert TrueType fonter (*.ttf). Vi tar omtrent 15 vanskelige fonter og kaster dem inn i fonter-mappen.
Alle bakgrunnene er der, fontene er der, nå selve index.py.
Print("Innholdstype: bilde/jpeg"); trykk(""); import sys, os, re, tilfeldig fra PIL importer bilde, ImageFont, ImageDraw klasse captcha(objekt): def __init__(selv): self.string = ""; self.root = os.getcwd(); self.path_backgrounds = self.root+"/backgrounds/"; self.path_fonts = self.root+"/fonts/"; def gen_streng(selv): tegn = ("a", "b", "d", "e", "f", "g", "h", "j", "m", "n", " q", "r", "t", "u", "y", "A", "B", "D", "E", "F", "G", "H", "J" , "M", "N", "Q", "R", "T", "U", "Y", "1", "2", "3", "4", "5", " 6", "7", "8", "9"); for i in range(random.randint(5, 6)): self.string += tegn; returnere selv.streng; def gen_bakgrunner(selv): bilder = ; if os.path.exists(self.path_backgrounds): for f i os.listdir(self.path_backgrounds): if os.path.isdir(self.path_backgrounds+"/"+f): fortsett; if re.search("\.(jpeg|jpg)$", f, re.IGNORECASE): images.append(self.path_backgrounds+"/"+f); annet: sys.exit(); if len(bilder) == 0: sys.exit(); returnere bilder; def gen_fonts(self): fonts = ; if os.path.exists(self.path_fonts): for f i os.listdir(self.path_fonts): if os.path.isdir(self.path_fonts+"/"+f): fortsett; if re.search("\.(ttf)$", f, re.IGNORECASE): fonts.append(self.path_fonts+"/"+f); annet: sys.exit(); if len(fonts) == 0: sys.exit(); returnere fonter; def gen_bilde(selv): string = self.gen_string(); bakgrunner = self.gen_backgrounds(); fonts = self.gen_fonts(); image = Image.new("RGB", (200,60), "#FFF") draw = ImageDraw.Draw(image); for i in range(5): background = Image.open(backgrounds); x = random.randint(0, 160); cp = background.crop((x, 0, x+40, 60)); image.paste(cp, (i*40, 0)); hvis len(streng) == 5: x = random.randint(25, 30); annet: x = random.randint(8, 11); for char i streng: font = fonts; y = random.randint(5, 25); font_size = random.randint(24, 30); color_dark = "rgb("+str(random.randint(0,150))+","+str(random.randint(0,100))+","+str(random.randint(0,150))+""; color_font = "rgb("+str(random.randint(50,200))+","+str(random.randint(0,150))+","+str(random.randint(50,200))+""; ttf = ImageFont.truetype(font, font_size) draw.text((x+1, y+1), char, fill=color_dark, font=ttf) draw.text((x,y), char, fill=color_font, font=ttf) x += random.randint(13, 15) + 18; image.save(sys.stdout, "JPEG") cp = captcha(); cp.gen_image(); #cp.streng; tegnstreng
Det er det. Jeg har et bilde generert på http://localhost/cgi-bin/captcha/index.py. Deretter kan du legge til en lagringsmekanisme for den genererte strengen ( cp.streng) fra økter eller et annet sted.
Jeg bestemte meg for å mestre Python litt, men å mestre "bare ikke PHP" er ikke interessant. Egoistisk interesse har blitt automatisk løse captcha Python.
Saken begynte med et innlegg fra Habr fra 2012 (grafikkbibliotek generelt fra 2009).
Kode: https://habrahabr.ru/post/149091/
Jeg har 2.7.10 ut av esken, men koden ble skrevet under 2.5 (med enten PIL). De skriver at den går perfekt på 2.7.3.
PIL rullet slik
Kode: #nedlasting
curl -O -L http://effbot.org/media/downloads/Imaging-1.1.7.tar.gz
#ekstrakt
tar -xzf Imaging-1.1.7.tar.gz
cd Imaging-1.1.7
# bygg og installer
python setup.py build
sudo python setup.py installer
# eller installer den for bare deg uten å kreve administratortillatelser:
# python setup.py install --user
Så importerte jeg modulen slik
Kode: #skriv inn i konsollen
python
#tolken som kommandoen skal slås på
importere PIL
#hvis alt er ok, trykk Ctrl+D for å avslutte
Snake er ikke vennlig med det kyrilliske alfabetet, jeg la til en konstruksjon i begynnelsen av filen (for å gjøre det mulig å kommentere håndverket på kyrillisk)
Kode: # -*- koding: utf-8 -*-
Her er selve sykkelen (jeg vet ikke hvordan jeg skal skrive sykluser og jeg vet ikke hvordan jeg skal evaluere, så jeg byttet ut mange ting for hånd).
Kode: # -*- koding: utf-8 -*-
#denne dritten er nødvendig for russiske symboler
fra PIL import bilde
fra operatør import itemgetter
im = im.convert("P")
hans = im.histogram()
verdier = ()
for i innen rekkevidde(256):
verdier[i] = hans[i]
for j,k i sorted(values.items(), key=itemgetter(1), reverse=True)[:15]:
skriv ut "eller pix ==",j#,k
#variable j lagrer de ti mest populære fargene
fra PIL import bilde
im = Image.open("captcha.gif")
im = im.convert("P")
im = im.convert("P")
for x i området (im.size):
for y i området (im.size):
pix = im.getpixel((y,x))
temp = pix
#farger her
im2.putpixel((y,x),0)
im2.save("output.gif")
#det virker som om alt begynner fra begynnelsen igjen
fra PIL import bilde
im = Image.open("output.gif")
im = im.convert("P")
im2 = Image.new("P",im.size,255)
im = im.convert("P")
for x i området (im.size):
for y i området (im.size):
pix = im.getpixel((y,x))
temp = pix
hvis pix == 255: # dette er tallene å få
im2.putpixel((y,x),0)
# ny kode starter her
inletter = Falsk
foundletter=False
start = 0
slutt = 0
pix = im2.getpixel((y,x))
hvis pix != 255:
inletter = Sant
foundletter = Sant
start = y
funnbokstav = Falsk
slutt = y
letters.append((start,slutt))
Inletter=False
skrive ut bokstaver
#hvem vet
klasse VectorCompare:
def magnitude (selv, konkordans):
totalt = 0
for ord, tell i concordance.iteritems():
totalt += antall ** 2
return math.sqrt(total)
Def-relasjon(selv, konkordans1, samsvar2):
relevans = 0
toppverdi = 0
for ord, tell i concordance1.iteritems():
if concordance2.has_key(word):
toppverdi += antall * konkordans2
return toppverdi / (self.magnitude(concordance1) * self.magnitude(concordance2))
#karaktersett
fra PIL import bilde
importer hashlib
importtid
im = Image.open("captcha.gif")
im2 = Image.new("P",im.size,255)
im = im.convert("P")
skriv ut im.histogram()
for x i området (im.size):
for y i området (im.size):
pix = im.getpixel((y,x))
temp = pix
#farger her
hvis pix == 187 eller pix == 224 eller pix == 188 eller pix == 223 eller pix == 145 eller pix == 151 eller pix == 181 eller pix == 144 eller pix == 225 eller pix == 182 eller pix == 189 eller pix == 12 eller pix == 17 eller pix == 139 eller pix == 152: # eller pix ==
im2.putpixel((y,x),0)
inletter = Falsk
foundletter=False
start = 0
slutt = 0
for y i range(im2.size): # skive på tvers
for x in range(im2.size): # skjær ned
pix = im2.getpixel((y,x))
#her var det "ikke lik 255" det vil si, det var "ikke lik hvitt"
hvis pix == 255:
inletter = Sant
Hvis funnet bokstav == usann og inletter == sant:
foundletter = Sant
start = y
Hvis funnet bokstav == Sant og inletter == Usant:
funnbokstav = Falsk
slutt = y
letters.append((start,slutt))
inletter=False
# Ny kode er her. Vi trekker ut hvert bilde og lagrer det på disk med
# hva er forhåpentligvis et unikt navn
telle = 0
for bokstaver i bokstaver:
m = hashlib.md5()
im3 = im2.crop((bokstav , 0, bokstav, im2.størrelse))
m.update("%s%s"%(time.time(),count))
im3.save("./%s.gif"%(m.hexdigest()))
telle += 1
Operasjonsprinsippet er dette: lag et histogram, fjern de vanligste nyansene, lagre resten i svart og hvitt, del dem langs grensene til symbolene, sammenlign symbolene med prøvene.
Original captcha, uten 10 populære nyanser, uten 15 populære nyanser (jeg delte det ikke ned i symboler - fordi det er et ikke-heltallssymbol).
Original captcha, uten 15 populære nyanser, delt inn i 2 tegn (litt skittent).
Det er fullt mulig å installere en løser under en enkel captcha. Vi trenger interessante steder med enkle captchaer for etterbehandling og testing.
Det er forskjellige måter å omgå CAPTCHA-er som beskytter nettsteder. For det første er det spesielle tjenester som bruker billig manuell arbeidskraft og tilbyr å løse 1000 captchas for bokstavelig talt $1. Som et alternativ kan du prøve å skrive et intelligent system som ved hjelp av visse algoritmer vil utføre gjenkjenning selv. Sistnevnte kan nå implementeres ved hjelp av et spesielt verktøy.
Løs CAPTCHA
Å gjenkjenne CAPTCHA er oftest en ikke-triviell oppgave. Det er nødvendig å bruke mange forskjellige filtre på bildet for å fjerne forvrengninger og støy, som utviklere ønsker å bruke for å styrke beskyttelsen. Ofte må man implementere et læringssystem basert på nevrale nettverk (dette er forresten ikke så vanskelig som det kan virke) for å oppnå et akseptabelt resultat i automatisert captcha-løsning. For å forstå hva jeg snakker om, er det bedre å åpne arkivet og lese de fantastiske artiklene "Cracking CAPTCHA: theory and practice. La oss finne ut hvordan captchaer brytes" og "La oss se og gjenkjenne. Hacking Captcha-filtre" fra henholdsvis #135 og #126 tall. I dag vil jeg fortelle deg om utviklingen av TesserCap, som forfatteren kaller en universell CAPTCHA-løser. En merkelig ting, hva enn man måtte si.Se først på TesserCap
Hva gjorde forfatteren av programmet? Han så på hvordan problemet med automatisert CAPTCHA-løsning vanligvis tilnærmes og forsøkte å oppsummere denne erfaringen i ett verktøy. Forfatteren la merke til at for å fjerne støy fra et bilde, det vil si å løse det vanskeligste problemet med å gjenkjenne captchas, brukes de samme filtrene oftest. Det viser seg at hvis du implementerer et praktisk verktøy som lar deg bruke filtre på bilder uten komplekse matematiske transformasjoner, og kombinerer det med et OCR-system for tekstgjenkjenning, kan du få et helt brukbart program. Dette er faktisk det Gursev Singh Kalra fra McAfee gjorde. Hvorfor var dette nødvendig? Forfatteren av verktøyet bestemte seg for å sjekke på denne måten hvor sikre captchas av store ressurser er. For testing valgte vi de Internett-sidene som er mest besøkt i henhold til den velkjente statistikktjenesten. Kandidater for å delta i testing inkluderte monstre som Wikipedia, eBay og captcha-leverandøren reCaptcha. Hvis vi generelt vurderer prinsippet om programmets drift, er det ganske enkelt. Den originale captchaen går inn i bildeforbehandlingssystemet, som renser captchaen fra all støy og forvrengning og overfører det resulterende bildet gjennom en transportør til OCR-systemet, som prøver å gjenkjenne teksten på det. TesserCap har et interaktivt grafisk grensesnitt og har følgende egenskaper:- Den har et universelt bildeforbehandlingssystem som kan konfigureres for hver enkelt captcha.
- Inkluderer Tesseract-gjenkjenningsmotoren, som trekker ut tekst fra et forhåndsanalysert og forberedt CAPTCHA-bilde.
- Støtter bruk av ulike kodinger i gjenkjenningssystemet.
Bildeforbehandling og utvinning tekst fra captcha
Om
Vi kunne ikke la være å si i det minste noen få ord om forfatteren av det fantastiske TesserCap-verktøyet. Han heter Gursev Singh Kalra. Han er hovedkonsulent for Foundstones avdeling for profesjonelle tjenester, en del av McAfee. Gursev har talt på konferanser som ToorCon, NullCon og ClubHack. Han er forfatteren av verktøyene TesserCap og SSLSmart. I tillegg utviklet han flere verktøy for selskapets interne behov. Favoritt programmeringsspråk er Ruby, Ruby on Rails og C#. Foundstone®s avdeling for profesjonelle tjenester, hvor han jobber, gir organisasjoner eksperttjenester og opplæring for å sikre at deres eiendeler er konsekvent og effektivt beskyttet mot de mest utfordrende truslene. Professional Services-teamet består av anerkjente sikkerhetseksperter og utviklere med lang erfaring fra å jobbe med internasjonale selskaper og offentlige etater.Grensesnitt. Hovedfane
Etter å ha startet programmet, får vi et vindu med tre faner: Hoved, Alternativer, Bildeforbehandling. Hovedfanen inneholder kontroller som brukes til å starte og stoppe CAPTCHA-bildetesten, generere teststatistikk (hvor mange som er gjettet og hvor mange som ikke er det), navigere og velge et bilde for forhåndsbehandling. URL-inndatafeltet (kontroll #1) må inneholde den nøyaktige URL-en som nettapplikasjonen bruker for å hente captchaer. URL-en kan fås ved å klikke på høyre side av CAPTCHA-bildet, kopiere eller vise sidekoden, og trekke ut URL-en fra src-attributtet til bilde-taggen ..site/common/rateit/captcha.asp?. Ved siden av adresselinjen er det et element som spesifiserer antall captchaer som må lastes ned for testing. Siden applikasjonen bare kan vise 12 bilder om gangen, gir den kontroller for side-for-side-surfing av nedlastede captchaer. Under storskala testing vil vi derfor kunne bla gjennom de nedlastede captchaene og se resultatene av gjenkjenningen deres. Start- og Stopp-knappene starter og stopper testing, henholdsvis. Etter testing må du evaluere bildegjenkjenningsresultatene, og merke hver av dem som riktig eller feil. Vel, den siste, mest betydningsfulle funksjonen tjener til å overføre ethvert bilde til et forbehandlingssystem, der et filter er satt som fjerner støy og forvrengning fra bildet. For å sende et bilde til forbehandlingssystemet, må du høyreklikke på ønsket bilde og velge Send til bildeforbehandler fra hurtigmenyen.Grensesnitt. Alternativer-fanen
Alternativer-fanen inneholder ulike kontroller for å konfigurere TesserCap. Her kan du velge et OCR-system, angi webproxy-parametere, aktivere bildeomdirigering og forhåndsbehandling, legge til egendefinerte HTTP-overskrifter, og også spesifisere rekkevidden av tegn for gjenkjenningssystemet: tall, små bokstaver, store bokstaver, spesialtegn. Nå om hvert alternativ mer detaljert. Først av alt kan du velge et OCR-system. Som standard er bare én tilgjengelig - Tesseract-ORC, så du trenger ikke å bry deg med valget her. En annen veldig interessant funksjon i programmet er å velge en rekke karakterer. La oss for eksempel ta en captcha fra siden – det er tydelig at den ikke inneholder en enkelt bokstav, men består kun av tall. Så hvorfor trenger vi ekstra karakterer som bare øker sannsynligheten for feilgjenkjenning? Men hva om du velger store bokstaver? Vil programmet kunne gjenkjenne en captcha som består av store bokstaver på et hvilket som helst språk? Nei, det kan han ikke. Programmet henter listen over tegn som brukes for gjenkjenning fra konfigurasjonsfilene som ligger i \Program Files\Foundstone Free Tools\TesserCap 1.0\tessdata\configs. La meg forklare med et eksempel: hvis vi valgte alternativene Numerics og Smaller Case, vil programmet få tilgang til den nedre numeriske filen, og starter med parameteren tessedit røye hviteliste. Dette etterfølges av en liste over tegn som skal brukes til å løse captchaen. Som standard inneholder filene bare bokstaver i det latinske alfabetet, så for å gjenkjenne det kyrilliske alfabetet må du erstatte eller supplere listen over tegn. Nå litt om hva feltet Http Request Headers er nødvendig for. For eksempel, på enkelte nettsteder må du logge inn for å se captchaen. For at TesserCap skal få tilgang til captchaen, må programmet sende overskrifter som Accept, Cookie og Referrer, etc. i HTTP-forespørselen. Ved å bruke en nettproxy (Fiddler, Burp, Charles, WebScarab, Paros, etc.) kan avskjære forespørselshodene som sendes og legge dem inn i inndatafeltet Http Request Headers. Et annet alternativ som definitivt vil komme godt med er Follow Redirects. Saken er at TesserCap ikke følger omdirigeringer som standard. Hvis test-URL-en må følge en omdirigering for å få bildet, må du velge dette alternativet. Vel, det er et siste alternativ igjen, aktivering/deaktivering av bildeforbehandlingsmekanismen, som vi vil vurdere nærmere. Som standard er bildeforbehandling deaktivert. Brukere konfigurerer først bildeforbehandlingsfiltre i henhold til CAPTCHA-bildene som testes, og aktiverer deretter denne modulen. Alle CAPTCHA-bilder som lastes inn etter aktivering av alternativet Aktiver bildeforbehandling, blir forhåndsbehandlet og sendt til Tesseract OCR-systemet for tekstutvinning.Grensesnitt. Bildeforbehandlingsfane
Vel, vi har nådd den mest interessante fanen. Det er her filtre er konfigurert for å fjerne ulike støy og uskarphet fra captchaer, som prøver å komplisere oppgaven til gjenkjenningssystemet så mye som mulig. Prosessen med å sette opp et universalfilter er ekstremt enkel og består av ni trinn. På hvert trinn av bildeforbehandlingen vises endringer i bildet. I tillegg har siden en verifikasjonskomponent som lar deg evaluere riktigheten av captcha-gjenkjenning når et filter brukes. La oss se på hvert trinn i detalj. Trinn 1. Fargeinversjon På dette stadiet inverteres pikselfargene for CAPTCHA-bilder. Koden nedenfor viser hvordan dette skjer: for(hver piksel i CAPTCHA) (hvis (invertRød er sann) ny rød = 255 – gjeldende rød hvis (inverterBlå er sann) ny blå = 255 – gjeldende blå hvis (invertgrønn er sann ) ny grønn = 255 – gjeldende grønn ) Invertering av en eller flere farger åpner ofte for nye muligheter for å validere CAPTCHA-bildet som testes. Trinn 2. Fargeendring På dette trinnet kan du endre fargekomponentene for alle piksler i bildet. Hvert numerisk felt kan inneholde 257 (−1 til 255) mulige verdier. For RGB-komponentene til hver piksel, avhengig av verdien i feltet, utføres følgende handlinger:- Hvis verdien er -1, endres ikke den tilsvarende fargekomponenten.
- Hvis verdien ikke er -1, endres alle funne komponenter i den angitte fargen (rød, grønn eller blå) i henhold til verdien angitt i feltene. En verdi på 0 fjerner komponenten, en verdi på 255 setter dens maksimale intensitet, etc.
- Gjennomsnittlig -> (rød + grønn + blå)/3.
- Menneske -> (0,21 * Rød + 0,71 * Grønn + 0,07 * Blå).
- Gjennomsnitt av minimum og maksimum fargekomponenter -> (Minimum (Rød + Grønn + Blå) + Maksimum (Rød + Grønn + Blå))/2.
- Minimum -> Minimum (rød + grønn + blå).
- Maksimum -> Maksimum (rød + grønn + blå).
Trinn 4: Utjevning og skjerping For å gjøre det vanskeligere å trekke ut tekst fra CAPTCHA-bilder, legges støy til dem i form av enkelt- og flerpikselpunkter, fremmede linjer og romlige forvrengninger. Når et bilde jevnes ut, øker tilfeldig støy, som deretter fjernes ved hjelp av Bucket- eller Cutoff-filtre. I det numeriske passeringsfeltet bør du angi hvor mange ganger du må bruke den tilsvarende bildemasken før du går videre til neste trinn. La oss se på komponentene for utjevning og skarphet. To typer bildemasker er tilgjengelige: - Faste masker. Som standard har TesserCap seks av de mest populære bildemaskene. Disse maskene kan jevne ut bildet eller gjøre det skarpere (Laplace-transformasjon). Endringer vises umiddelbart etter at du har valgt en maske med de tilsvarende knappene.
- Egendefinerte bildemasker. Brukeren kan også sette opp egendefinerte bildebehandlingsmasker ved å skrive inn verdier i de numeriske feltene og klikke på Lagre maske-knappen. hvis summen av koeffisientene i disse vinduene er mindre enn null, genereres en feil og masken påføres ikke. Hvis du velger en fast maske, trenger du ikke bruke knappen Lagre maske.
- La være som den er.
- Bytt ut med hvit.
- Bytt ut med sort.
Hensikten med denne fasen er å overføre det forhåndsbehandlede CAPTCHA-bildet til OCR-systemet for gjenkjenning. Løs-knappen tar bildet etter gråtone-inversjonsfilteret, sender det til OCR-systemet for å trekke ut teksten, og viser den returnerte teksten i GUI. Hvis den gjenkjente teksten samsvarer med teksten på captchaen, betyr det at vi har satt filteret riktig for forhåndsbehandling. Nå kan du gå til alternativer-fanen og aktivere alternativet Aktiver bildeforbehandling for å behandle alle påfølgende nedlastede captchaer.
Gjenkjenne captchas
Vel, kanskje vi har vurdert alle alternativene til dette verktøyet, og nå ville det være fint å teste litt captcha for styrke.. Resultat av captcha-analysenettsted med foreløpig
Kunne ikke finne det Så la oss starte verktøyet og gå til magasinets nettside. Vi ser en liste over de siste nyhetene, gå til den første vi kommer over og bla til stedet hvor du kan legge igjen kommentaren din. Ja, det er ikke så lett å legge til en kommentar (selvfølgelig, ellers ville de ha spammet alt for lenge siden) - du må skrive inn en captcha. Vel, la oss sjekke om dette kan automatiseres. Kopier URL-en til bildet og lim det inn i TesserCap-adresselinjen. Vi indikerer at du må laste ned 12 captchaer og klikke Start. Programmet lastet lydig inn 12 bilder og prøvde å gjenkjenne dem. Dessverre ble alle captchaer enten ikke gjenkjent, noe som fremgår av inskripsjonen -Failed- under dem, eller ble gjenkjent feil. Generelt er dette ikke overraskende, siden fremmed støy og forvrengning ikke ble fjernet. Dette skal vi gjøre nå. Høyreklikk på ett av de 12 innlastede bildene og send det til forbehandlingssystemet (Send To Image Preprocessor). Etter å ha undersøkt alle 12 captchaene nøye, ser vi at de bare inneholder tall, så vi går til fanen alternativer og indikerer at bare tall må gjenkjennes (tegnsett = numerikk). Nå kan du gå til Bildeforbehandling-fanen for å konfigurere filtre. Jeg vil si med en gang at etter å ha spilt med de tre første filtrene ("Color Inversion", "Color Change", "Gray Gradation") så jeg ingen positiv effekt, så jeg lot alt stå som standard. Jeg valgte Smooth Mask 2 og satte antall pass til én. Jeg hoppet over Grayscale buckets-filteret og gikk rett til klippeinnstillingene. Jeg valgte verdien 154 og indikerte at de pikslene som er mindre skulle settes til 0, og de som er større skulle settes til 255. For å bli kvitt de gjenværende pikslene, satte jeg på hakking og endret kantbredden til 10. Det var ingen vits i å aktivere det siste filteret, så jeg klikket umiddelbart på Løs. På captchaen hadde jeg nummeret 714945, men programmet gjenkjente det som 711435. Dette er som du ser helt feil. Til slutt, uansett hvor hardt jeg prøvde, klarte jeg ikke å gjenkjenne captchaen ordentlig. Jeg måtte eksperimentere med pastebin.com, som jeg klarte å gjenkjenne uten problemer. Men hvis du er mer flittig og tålmodig og klarer å få captchas korrekt gjenkjent fra nettstedet, gå umiddelbart til alternativfanen og slå på Aktiver bildeforbehandling. Gå deretter til Main, og ved å klikke på Start, last ned en ny batch med captchas, som nå vil bli forhåndsbehandlet av filteret ditt. Etter at programmet har kjørt, merker du de riktig/feilaktig gjenkjente captchaene (Mark as Correct/Mark as InCorrect-knappene). Fra nå av kan du se sammendragsstatistikk om gjenkjennelse ved å bruke Vis statistikk. Generelt er dette en slags rapport om sikkerheten til en bestemt CAPTCHA. Hvis det er et spørsmål om å velge en eller annen løsning, er det ved hjelp av TesserCap fullt mulig å gjennomføre din egen testing.
bildebehandling. Etter resultatene å dømme, filteret
Resultat av CAPTCHA-sjekk på populære nettsteder- Nettsted og prosentandel av gjenkjente captchaer:
- Wikipedia > 20–30 %
- Ebay > 20–30 %
- reddit.com > 20–30 %
- CNBC > 50 %
- foodnetwork.com > 80–90 %
- dailymail.co.uk > 30 %
- megaupload.com > 80 %
- pastebin.com > 70–80 %
cavenue.com > 80 %
CAPTCHA-bilder er en av de mest effektive mekanismene for å beskytte nettapplikasjoner mot automatisk skjemautfylling. Imidlertid vil svake captchaer kunne beskytte mot tilfeldige roboter og vil ikke motstå målrettede forsøk på å løse dem. I likhet med kryptografiske algoritmer er CAPTCHA-bilder, som er grundig testet og gir et høyt sikkerhetsnivå, den beste måten å beskytte deg selv på. Basert på statistikken gitt av forfatteren av programmet, valgte jeg reCaptcha for prosjektene mine og vil anbefale det til alle vennene mine - det viste seg å være den mest motstandsdyktige av de som ble testet. I alle fall, ikke glem at det er mange tjenester på Internett som tilbyr en semi-automatisert CAPTCHA-løsning. Gjennom en spesiell API sender du et bilde til tjenesten, og etter kort tid returnerer det en løsning. En ekte person (for eksempel fra Kina) løser captchaen og får betalt en pen krone for det. Det er ikke lenger noen beskyttelse her. 🙂De fleste vet ikke, men oppgaven min var et program for å lese tekst fra et bilde. Jeg tenkte at hvis jeg kunne få en høy gjenkjennelsesrate, kunne den brukes til å forbedre søkeresultatene. Min utmerkede rådgiver, Dr. Gao Junbing, foreslo at jeg skulle skrive en avhandling om dette emnet. Jeg fant endelig tid til å skrive denne artikkelen, og her vil jeg prøve å snakke om alt jeg har lært. Hvis det bare var noe sånt da jeg begynte...
Som jeg sa før, prøvde jeg å ta vanlige bilder fra internett og trekke ut tekst fra dem for å forbedre søkeresultatene. De fleste av ideene mine var basert på captcha-cracking-metoder. Som alle vet, er captchas de irriterende tingene som "Skriv inn bokstavene du ser på bildet" på registrerings- eller tilbakemeldingssider.
Captcha er laget slik at en person kan lese teksten uten problemer, mens en maskin ikke kan (hei, reCaptcha!). I praksis fungerte dette aldri, fordi nesten hver eneste captcha som ble plassert på siden ble hacket i løpet av flere måneder.
Jeg klarte meg ganske bra - over 60 % av bildene ble løst fra min lille samling. Ganske bra med tanke på mengden forskjellige bilder på internett.
I min forskning fant jeg ikke noe materiale som ville hjelpe meg. Ja, det finnes artikler, men de inneholder veldig enkle algoritmer. Jeg fant faktisk noen ødelagte eksempler i PHP og Perl, tok noen utdrag fra dem og fikk ganske gode resultater for en veldig enkel captcha. Men ingen av dem hjalp meg egentlig, for det var for enkelt. Jeg er en av dem som kan lese teori, men som ikke kan forstå noe uten virkelige eksempler. Og i de fleste artiklene sto det at de ikke ville publisere koden fordi de var redde for at den skulle bli brukt til dårlige formål. Personlig synes jeg captcha er bortkastet tid da det er ganske enkelt å komme seg rundt hvis du vet hvordan.
Faktisk, på grunn av mangelen på noe materiale som viser captcha-hacking for nybegynnere, skrev jeg denne artikkelen.
La oss komme i gang. Her er en liste over hva jeg skal dekke i denne artikkelen:
- Teknologier som brukes
- Hva er captcha
- Bildegjenkjenning ved hjelp av AI
- Utdannelse
- Å sette det hele sammen
- Resultater og konklusjoner
Teknologier som brukes
Alle eksempler er skrevet i Python 2.5 ved å bruke PIL-biblioteket. Bør fungere i Python 2.6 også.
Installer dem i rekkefølgen ovenfor, og du er klar til å kjøre eksemplene.
Trekke seg tilbake
I eksemplene vil jeg hardkode mange verdier direkte i koden. Jeg har ikke noe mål å lage en universell captcha-gjenkjenner, men bare å vise hvordan det gjøres.
Captcha, hva er det egentlig?
I utgangspunktet er en captcha et eksempel på en enveiskonvertering. Du kan enkelt ta et sett med karakterer og få en captcha fra det, men ikke omvendt. En annen subtilitet er at den skal være lett å lese av mennesker, men ikke mottagelig for maskingjenkjenning. Captcha kan betraktes som en enkel test som "Er du menneske?" I utgangspunktet er de implementert som et bilde med noen symboler eller ord.
De brukes til å forhindre spam på mange nettsteder. Captchaen kan for eksempel bli funnet på registreringssiden for Windows Live ID.
Du får vist et bilde, og hvis du virkelig er en person, må du skrive inn teksten i et eget felt. Virker som en god idé som kan beskytte deg mot tusenvis av automatiserte registreringer for spam eller distribusjon av Viagra på forumet ditt? Problemet er at AI, og spesielt bildegjenkjenningsmetoder, har gjennomgått betydelige endringer og er i ferd med å bli svært effektive på visse områder. OCR (optisk tegngjenkjenning) er ganske nøyaktig i disse dager og gjenkjenner enkelt trykt tekst. Beslutningen ble tatt for å legge til litt farger og linjer for å få datamaskinen til å jobbe hardere uten å forårsake noen ulempe for brukerne. Dette er et slags våpenkappløp og som vanlig kommer de med sterkere våpen for ethvert forsvar. Å beseire den forbedrede captchaen er vanskeligere, men fortsatt mulig. I tillegg bør bildet forbli ganske enkelt for ikke å irritere vanlige mennesker.
Dette bildet er et eksempel på captchaen vi skal dechiffrere. Dette er en ekte captcha, som legges ut på en ekte nettside.
Dette er en ganske enkel captcha, som består av symboler i samme farge og størrelse på en hvit bakgrunn med noe støy (piksler, farger, linjer). Du tror kanskje at denne støyen i bakgrunnen ville gjøre den vanskelig å gjenkjenne, men jeg skal vise deg hvordan du enkelt fjerner den. Selv om dette ikke er en veldig sterk captcha, er det et godt eksempel for programmet vårt.
Hvordan finne og trekke ut tekst fra bilder
Det er mange metoder for å bestemme plasseringen av tekst i et bilde og trekke den ut. Ved å bruke Google kan du finne tusenvis av artikler som forklarer nye metoder og algoritmer for tekstsøk.
For dette eksemplet vil jeg bruke fargeekstraksjon. Dette er en ganske enkel teknikk som jeg har fått ganske gode resultater med. Dette er teknikken jeg brukte til avhandlingen min.
For våre eksempler vil jeg bruke multivalued bildedekomponeringsalgoritmen. I hovedsak betyr dette at vi først vil plotte et histogram av fargene i bildet. Dette gjøres ved å ta alle pikslene i bildet, gruppert etter farge, og deretter telle for hver gruppe. Hvis du ser på vår test-captcha, kan du se tre hovedfarger:
- Hvit (bakgrunn)
- Grå (støy)
- Rød (tekst)
I Python vil dette se veldig enkelt ut.
Følgende kode åpner bildet, konverterer det til GIF (gjør jobben vår enklere siden den bare har 255 farger) og skriver ut et fargehistogram.
Fra PIL importer Image im = Image.open("captcha.gif") im = im.convert("P") print im.histogram()
Som et resultat får vi følgende:
Her ser vi antall piksler for hver av de 255 fargene i bildet. Du kan se at hvit (255, den nyeste) er den vanligste. Den etterfølges av rød (tekst). For å bekrefte dette, la oss skrive et lite skript:
Fra PIL-import Bilde fra operatør importer itemgetter im = Image.open("captcha.gif") im = im.convert("P") his = im.histogram()-verdier = () for i i området(256) : verdier [i] = hans[i] for j,k in sorted(values.items(), key=itemgetter(1), reverse=True)[:10]: print j,k
Og vi får følgende data:
Dette er en liste over de 10 vanligste fargene i et bilde. Som forventet gjentar hvit seg oftest. Så er det grått og rødt.
Når vi har denne informasjonen, lager vi nye bilder basert på disse fargegruppene. For hver av de vanligste fargene lager vi et nytt binært bilde (av 2 farger), der pikslene i den fargen er fylt med svart og resten med hvitt.
Vi har rød som den tredje vanligste fargen, og det betyr at vi ønsker å beholde gruppen med piksler med farge 220. Da jeg eksperimenterte fant jeg ut at farge 220 er ganske nær 220, så vi vil beholde den gruppen med piksler også. Koden nedenfor åpner captchaen, konverterer den til en GIF, lager et nytt bilde av samme størrelse med hvit bakgrunn, og går deretter gjennom det originale bildet for å finne fargen vi trenger. Hvis den finner en piksel med fargen vi trenger, markerer den samme piksel i det andre bildet med svart farge. Det andre bildet lagres før det avsluttes.
Fra PIL importer Image im = Image.open("captcha.gif") im = im.convert("P") im2 = Image.new("P",im.size,255) im = im.convert("P ") temp = () for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix hvis pix == 220 eller pix == 227: # dette er tallene for å få im2.putpixel((y,x),0) im2.save("output.gif")
Å kjøre denne kodebiten gir oss følgende resultat.
På bildet kan du se at vi har trukket ut teksten fra bakgrunnen. For å automatisere denne prosessen kan du kombinere det første og andre skriptet.
Jeg hører deg spørre: "Hva om teksten på captchaen er skrevet i forskjellige farger?" Ja, utstyret vårt vil fortsatt kunne fungere. Anta at den vanligste fargen er bakgrunnsfargen og så kan du finne karakterfargene.
Så på dette tidspunktet har vi trukket ut tekst fra bildet. Det neste trinnet er å finne ut om bildet inneholder tekst. Jeg vil ikke skrive noen kode her foreløpig, fordi det vil gjøre det vanskelig å forstå, mens selve algoritmen er ganske enkel.
For hvert binærbilde: for hver piksel i det binære bildet: hvis pikselen er på: hvis en piksel vi har sett før er ved siden av: legg til i samme sett annet: legg til i et nytt sett
Utgangen du vil ha er et sett med tegngrenser. Da er det bare å sammenligne dem med hverandre og se om de er konsistente. Hvis ja, så har du vunnet jackpotten og du har riktig identifisert symbolene ved siden av hverandre. Du kan også sjekke størrelsene på de resulterende områdene eller ganske enkelt lage et nytt bilde og vise det (show()-metoden til bildet) for å verifisere nøyaktigheten til algoritmen.
Fra PIL importer Image im = Image.open("captcha.gif") im = im.convert("P") im2 = Image.new("P",im.size,255) im = im.convert("P ") temp = () for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix hvis pix == 220 eller pix == 227: # dette er tallene for å få im2.putpixel((y,x),0) # ny kode starter her inletter = False funnletter=Falsk start = 0 slutt = 0 bokstaver = for y i området(im2.size): # del på tvers for x i området(im2.størrelse): # del ned pix = im2.getpixel((y,x)) if pix != 255: inletter = True if foundletter == False og inletter == True: foundletter = True start = y if foundletter == True and inletter == False: foundletter = False end = y letters.append((start, end)) inletter=False print letters
Som et resultat fikk vi følgende:
[(6, 14), (15, 25), (27, 35), (37, 46), (48, 56), (57, 67)]
Dette er de horisontale posisjonene til begynnelsen og slutten av hvert tegn.
AI og vektorrom i mønstergjenkjenning
Bildegjenkjenning kan betraktes som den største suksessen til moderne kunstig intelligens, og lar den trenge gjennom alle typer kommersielle applikasjoner. Et godt eksempel på dette er postnummer. Faktisk, i mange land leses de automatisk, siden det å lære en datamaskin å gjenkjenne skilt er en ganske enkel oppgave. Det er kanskje ikke åpenbart, men mønstergjenkjenning betraktes som et AI-problem, om enn et veldig spesialisert.
Nesten det første man møter når man blir kjent med AI i mønstergjenkjenning er nevrale nettverk. Personlig har jeg aldri hatt suksess med nevrale nettverk i karaktergjenkjenning. Jeg pleier å lære den 3-4 symboler, hvoretter nøyaktigheten faller så lavt at den ville vært en størrelsesorden høyere hvis jeg gjettet symbolene tilfeldig. Til å begynne med skapte dette meg en liten panikk, fordi dette var den manglende lenken i avhandlingen min. Heldigvis leste jeg nylig en artikkel om vektor-rom-søkemotorer og fant ut at de var en alternativ metode for å klassifisere data. Til slutt viste de seg å være det beste valget fordi...
- De krever ikke omfattende studier
- Du kan legge til/fjerne feil data og umiddelbart se resultatet
- De er lettere å forstå og programmere
- De gir klassifiserte resultater slik at du kan se de beste X kampene
- Kan du ikke gjenkjenne noe? Legg det sammen og du kan gjenkjenne det umiddelbart, selv om det er helt annerledes enn noe du har sett før.
Selvfølgelig er det ingen gratis ost. Den største ulempen er hastigheten. De kan være mye tregere enn nevrale nettverk. Men jeg tror at fordelene deres fortsatt oppveier denne ulempen.
Hvis du vil forstå hvordan vektorrom fungerer, anbefaler jeg å lese Vector Space Search Engine Theory. Dette er det beste jeg har funnet for nybegynnere.
Jeg bygde bildegjenkjenningen min basert på dokumentet ovenfor, og dette var det første jeg prøvde å skrive på favorittspråket mitt, som jeg studerte på den tiden. Les dette dokumentet og når du forstår essensen, kom tilbake hit.
Allerede tilbake? Fin. Nå må vi programmere vektorrommet vårt. Heldigvis er dette ikke vanskelig i det hele tatt. La oss komme i gang.
Importer matematikkklasse VectorCompare: def magnitude(selv,konkordans): total = 0 for ord,tell i concordance.iteritems(): total += count ** 2 return math.sqrt(total) def relation(self,concordance1, concordance2) : relevans = 0 toppverdi = 0 for ord, teller i concordance1.iteritems(): if concordance2.has_key(word): topvalue += count * concordance2 return topvalue / (self.magnitude(concordance1) * self.magnitude(concordance2))
Dette er en Python-implementering av vektorrom i 15 linjer. I hovedsak tar det bare 2 ordbøker og spytter ut et tall mellom 0 og 1 som indikerer hvordan de er relatert. 0 betyr at de ikke er relatert, og 1 betyr at de er identiske.
Utdannelse
Det neste vi trenger er et sett med bilder som vi skal sammenligne symbolene våre med. Vi trenger et treningssett. Dette settet kan brukes til å trene alle slags AI vi vil bruke (nevrale nettverk, etc.).
Dataene som brukes kan være avgjørende for suksessen med anerkjennelse. Jo bedre data, jo større er sjansen for suksess. Siden vi planlegger å gjenkjenne en spesifikk captcha og allerede kan trekke ut karakterer fra den, hvorfor ikke bruke dem som et treningssett?
Det var det jeg gjorde. Jeg lastet ned mange genererte captchaer og programmet mitt delte dem ned i bokstaver. Deretter samlet jeg de resulterende bildene i samlinger (grupper). Etter flere forsøk hadde jeg minst ett eksempel av hver karakter som captchaen genererte. Å legge til flere eksempler vil øke gjenkjenningsnøyaktigheten, men dette var nok for meg til å bekrefte teorien min.
Fra PIL import Bilde import hashlib import time im = Image.open("captcha.gif") im2 = Image.new("P",im.size,255) im = im.convert("P") temp = () skriv ut im.histogram() for x in range(im.size): for y in range(im.size): pix = im.getpixel((y,x)) temp = pix hvis pix == 220 eller pix == 227: # dette er tallene for å få im2.putpixel((y,x),0) inletter = False foundletter=Falsk start = 0 slutt = 0 bokstaver = for y i området(im2.size): # skive på tvers for x in range(im2.size): # del ned pix = im2.getpixel((y,x)) if pix != 255: inletter = True if foundletter == False and inletter == True: foundletter = True start = y if foundletter == Sant og inletter == False: foundletter = False end = y letters.append((start, end)) inletter=False # Ny kode er her. Vi bare trekker ut hvert bilde og lagrer det på disk med # som forhåpentligvis er et unikt navneantall = 0 for bokstav i bokstaver: m = hashlib.md5() im3 = im2.crop((bokstav , 0, bokstav,im2.størrelse) ) m.update("%s%s"%(time.time(),count)) im3.save("./%s.gif"%(m.hexdigest())) count += 1
Ved utgangen får vi et sett med bilder i samme katalog. Hver av dem er tildelt en unik hash i tilfelle du behandler flere captchaer.
Her er resultatet av denne koden for vår test-captcha:
Det er opp til deg hvordan du lagrer disse bildene, men jeg legger dem bare i kataloger med samme navn som bildet (symbol eller tall).
Å sette det hele sammen
Siste trinn. Vi har tekstuttrekk, karakteruttrekk, gjenkjenningsteknikk og treningssett.
Vi henter captcha-bildet, velger teksten, henter karakterene og sammenligner dem med treningssettet vårt. Du kan laste ned det endelige programmet med treningssettet og et lite antall captchaer fra denne lenken.
Her laster vi bare treningssettet slik at vi kan sammenligne med det:
Def buildvector(im): d1 = () count = 0 for i in im.getdata(): d1 = i count += 1 return d1 v = VectorCompare() iconset = ["0","1","2" "3","4","5","6","7","8","9","0","a","b","c","d"," e","f","g","h","i","j","k","l","m","n","o","p","q" "r","s","t","u","v","w","x","y","z"] imageset = for bokstav i ikonsett: for img i os.listdir ("./iconset/%s/"%(bokstav)): temp = if img != "Thumbs.db": temp.append(buildvector(Image.open("./iconset/%s/%s"% (letter,img)))) imageset.append((bokstav:temp))
Og det er her all magien skjer. Vi bestemmer hvor hvert tegn er og sjekker det ved å bruke vektorrommet vårt. Deretter sorterer vi resultatene og skriver dem ut.
Count = 0 for bokstav i bokstaver: m = hashlib.md5() im3 = im2.crop((letter , 0, letter,im2.size)) guess = for bilde i bildesett: for x,y i image.iteritems() : if len(y) != 0: guess.append((v.relation(y,buildvector(im3)),x)) guess.sort(reverse=True) skriv ut "",gjettetall += 1
Konklusjoner
Nå har vi alt vi trenger og vi kan prøve å starte mirakelmaskinen vår.
Inndatafilen er captcha.gif. Forventet resultat: 7s9t9j
Python crack.py (0,96376811594202894, "7") (0,96234028545977002, "s") (0,9286884286888929, "9") (0,9835037060984647) (0,983503706098467) "9") (0,96989711688772628, "j")
Her ser vi det forventede symbolet og graden av tillit til at det virkelig er det (fra 0 til 1).
Ser ut som vi virkelig har lykkes!
Faktisk, på test captchas, vil dette skriptet gi et vellykket resultat i omtrent 22 % av tilfellene.
Python crack_test.py Riktige gjetninger - 11,0 feil gjetninger - 37,0 prosentvis riktige - 22,9166666667 prosent feil - 77,0833333333
De fleste av de feil resultatene skyldes feil gjenkjennelse av tallet "0" og bokstaven "O". Det er ingenting uventet, fordi selv folk ofte forvirrer dem. Vi har fortsatt et problem med å dele opp i karakterer, men dette kan løses ganske enkelt ved å sjekke resultatet av delingen og finne et lykkelig medium.
Men selv med en så lite perfekt algoritme, kan vi løse hver femte captcha på en slik tid at en person ikke har tid til å løse én.
Å kjøre denne koden på en Core 2 Duo E6550 gir følgende resultater:
Ekte 0m5.750s bruker 0m0.015s sys 0m0.000s
Det er 48 captchaer i katalogen vår, noe som betyr at det tar omtrent 0,12 sekunder å løse en. Med vår suksessrate på 22 % kan vi løse rundt 432 000 captchaer per dag og få 95 040 riktige resultater. Hva om du bruker multithreading?
Det er det. Jeg håper at min erfaring vil bli brukt av deg til gode formål. Jeg vet at du kan bruke denne koden til å gjøre noe dårlig, men for å gjøre noe virkelig farlig må du endre det ganske mye.
For de som prøver å beskytte seg med captchas, kan jeg si at dette ikke vil hjelpe deg mye, fordi du kan omgå dem programmatisk eller ganske enkelt betale andre for å løse dem manuelt. Vurder andre beskyttelsesmetoder.
Dette var navnet på arbeidet jeg presenterte på den baltiske vitenskaps- og ingeniørkonkurransen, som ga meg et sjarmerende stykke papir med en romersk enhet, samt en splitter ny bærbar datamaskin.
Arbeidet innebar å identifisere CAPTCHA-er brukt av store mobiltelefonselskaper på deres SMS-innsendingsskjemaer og demonstrere at deres tilnærming var ineffektiv. For ikke å skade noens stolthet, vil vi kalle disse operatørene allegorisk: rød, gul, grønn og blå.
Prosjektet fikk et offisielt navn Captchure og uoffisiell Bryter defekte sikkerhetstiltak. Eventuelle likheter er tilfeldige.
Merkelig nok viste alle (vel, nesten alle) disse CAPTCHA-ene seg å være ganske svake. Det laveste resultatet - 20% - tilhører den gule operatøren, det høyeste - 86% - til den blå. Dermed tror jeg at oppgaven med å "demonstrere ineffektivitet" har blitt løst.
Årsakene til å velge mobiloperatører er trivielle. Jeg fortalte den utmerkede vitenskapelige juryen en historie om at "mobiloperatører har nok penger til å ansette en programmerer uansett kvalifikasjoner, og samtidig må de minimere mengden spam; Derfor bør CAPTCHA-ene deres være ganske kraftige, noe min forskning viser ikke er tilfelle.» I virkeligheten var alt mye enklere. Jeg ønsket å få erfaring ved å knekke og gjenkjenne en enkel CAPTCHA, og jeg valgte den røde operatøren som et offer for CAPTCHA. Og etter det ble den ovennevnte historien født i ettertid.
Så nærmere kroppen. Jeg har ingen megaavansert algoritme for å gjenkjenne alle fire typer CAPTCHA; I stedet skrev jeg 4 forskjellige algoritmer for hver type CAPTCHA separat. Til tross for at algoritmene er forskjellige i detalj, viste de seg generelt å være veldig like.
Som mange forfattere før meg, delte jeg CAPTCHA-gjenkjenningsoppgaven inn i 3 underoppgaver: forhåndsbehandling (forbehandling), segmentering og gjenkjenning. På forprosesseringsstadiet fjernes ulike støy, forvrengninger osv. fra kildebildet. Ved segmentering trekkes individuelle tegn ut fra kildebildet og etterbehandling utføres (for eksempel omvendt rotasjon). Under gjenkjenning behandles karakterer én etter én av et forhåndstrent nevralt nettverk.
Bare forprosessen var vesentlig forskjellig. Dette skyldes det faktum at forskjellige CAPTCHA-er bruker forskjellige bildeforvrengningsmetoder, og algoritmene for å fjerne disse forvrengningene varierer veldig. Segmentering utnyttet nøkkelideen med å søke etter tilkoblede komponenter med mindre bjeller og fløyter (de måtte gjøres betydelige bare for gulstripete). Anerkjennelsen var helt lik for tre av de fire operatørene - igjen var det bare den gule operatøren som var annerledes.
Til slutt males små (mindre enn 10 px) svarte tilkoblede områder hvite:
Noen ganger (sjelden, men det skjer) brytes et brev opp i flere deler; For å rette opp denne irriterende misforståelsen bruker jeg en ganske enkel heuristikk som vurderer om flere tilkoblede komponenter tilhører ett symbol. Denne poengsummen avhenger bare av den horisontale posisjonen og størrelsen til grenseboksene til hvert tegn.
Det er lett å legge merke til at mange symboler ble kombinert til en tilkoblet komponent, og derfor er det nødvendig å skille dem. Her kommer det faktum at bildet alltid inneholder nøyaktig 5 tegn til unnsetning. Dette lar deg beregne med stor nøyaktighet hvor mange tegn som er i hver funnet komponent.
For å forklare operasjonsprinsippet til en slik algoritme, må vi dykke litt dypere inn i maskinvaren. La oss angi antall funnet segmenter med n, og matrisen av bredder ( sa det riktig, ikke sant?) av alle segmenter for bredder[n]. Vi vil anta at hvis etter trinnene ovenfor n > 5, kunne ikke bildet gjenkjennes. La oss vurdere alle mulige dekomponeringer av tallet 5 til positive heltallstermer. Det er få av dem - bare 16. Hver slik dekomponering tilsvarer et mulig arrangement av symboler i henhold til de tilkoblede komponentene som er funnet. Det er logisk å anta at jo bredere det resulterende segmentet er, desto flere tegn inneholder det. Fra alle utvidelsene av femdobbelt velger vi bare de der antall ledd er lik n. La oss dele hvert element fra bredder etter bredder - som om vi normaliserer dem. La oss gjøre det samme med alle de gjenværende utvidelsene - del hvert tall i dem med det første leddet. Og nå (oppmerksomhet, punch-linjen!) legger vi merke til at de resulterende ordnede ns kan betraktes som punkter i n-dimensjonalt rom. Med dette i betraktning, la oss finne den nærmeste euklidiske dekomponeringen av de fem til de normaliserte breddene. Dette er ønsket resultat.
Forresten, i forbindelse med denne algoritmen, dukket det opp en annen interessant måte å søke etter alle dekomponeringer av et tall i termer, som jeg imidlertid aldri implementerte, og begravde meg i Python-datastrukturer. Kort sagt, det kommer ganske åpenbart ut hvis du legger merke til at antall dekomponeringer av en viss lengde sammenfaller med det tilsvarende nivået til Pascals trekant. Jeg er imidlertid sikker på at denne algoritmen har vært kjent i lang tid.
Så, etter å ha bestemt antall tegn i hver komponent, kommer neste heuristikk - vi tror at skilletegnene mellom tegnene er tynnere enn tegnene i seg selv. For å dra nytte av denne hemmelige kunnskapen vil vi plassere n-1 separatorer langs segmentet, hvor n er antall tegn i segmentet, hvoretter vi vil beregne nedadgående projeksjon av bildet i en liten nærhet av hver separator . Som et resultat av denne projeksjonen vil vi motta informasjon om hvor mange piksler i hver kolonne som tilhører tegn. Til slutt, i hver projeksjon finner vi minimum og flytter separatoren dit, hvoretter vi kutter bildet langs disse separatorene.
Til slutt, anerkjennelse. Som jeg allerede har sagt, bruker jeg et nevralt nettverk for det. For å trene det kjører jeg først to hundre bilder under en felles overskrift togsett gjennom de allerede skrevet og feilsøkte første to stadiene, som et resultat av at jeg får en mappe med et stort antall pent kuttede segmenter. Deretter renser jeg ut rusk med hendene (resultatene av feil segmentering, for eksempel), hvoretter jeg bringer resultatet til samme størrelse og gir det til FANN for å bli revet i stykker. Ved utgangen får jeg et trent nevralt nettverk, som brukes til gjenkjenning. Denne ordningen mislyktes bare én gang – men mer om det senere.
Som et resultat, på testsettet (ikke brukt til trening, kodenavn - testsett) av 100 bilder ble 45 korrekt gjenkjent. Resultatet er ikke veldig høyt - det kan selvfølgelig forbedres, for eksempel ved å tydeliggjøre forprosessen eller gjøre gjenkjennelsen på nytt, men ærlig talt, jeg var for lat til å tukle med. den.
I tillegg brukte jeg et annet kriterium for å vurdere ytelsen til algoritmen - gjennomsnittsfeilen. Det ble beregnet som følger. For hvert bilde ble Levenshtein-avstanden funnet mellom algoritmens mening om dette bildet og det riktige svaret – hvoretter det aritmetiske gjennomsnittet ble tatt over alle bildene. For denne typen CAPTCHA var gjennomsnittsfeilen 0,75 tegn/bilde. Det virker for meg som om dette er et mer nøyaktig kriterium enn bare prosentandelen av anerkjennelse.
Forresten, nesten overalt (bortsett fra den gule operatøren) brukte jeg akkurat dette opplegget - 200 bilder i togsettet, 100 i testsettet.
Grønn
Jeg valgte de grønne som mitt neste mål - jeg ønsket å ta på meg noe mer seriøst enn å velge en forvrengningsmatrise.
Fordeler:
- 3D-effekt
- Roter og skift
- Ujevn lysstyrke
Feil:
- Tegnene er merkbart mørkere enn bakgrunnen
- Oversiden av rektangelet er godt synlig - kan brukes til omvendt rotasjon
Det viste seg at selv om disse manglene er tilsynelatende ubetydelige, gjør utnyttelsen av dem det mulig å håndtere alle fordelene veldig effektivt.
La oss starte på nytt med forhåndsbehandling. La oss først anslå rotasjonsvinkelen til rektangelet som symbolene ligger på. For å gjøre dette, bruk Erode-operatoren på det originale bildet (søk etter et lokalt minimum), deretter Threshold for å velge restene av rektangelet og til slutt inversjon. Vi får en fin hvit flekk på svart bakgrunn.
Deretter kommer dype tanker. Først. For å estimere rotasjonsvinkelen til hele rektangelet, er det nok å estimere rotasjonsvinkelen på oversiden. Sekund. Du kan estimere rotasjonsvinkelen til oversiden ved å søke etter en rett linje parallelt med den siden. Tredje. For å beskrive enhver rett linje, bortsett fra en strengt vertikal, er to parametere tilstrekkelig - den vertikale forskyvningen fra koordinatsenteret og helningsvinkelen, og vi er bare interessert i den andre. Fjerde. Problemet med å finne en rett linje kan løses ved ikke så mye søk - det er ingen for store rotasjonsvinkler, og vi trenger ikke ultrahøy nøyaktighet. Femte. For å finne den nødvendige linjen kan du sammenligne hver linje med et estimat på hvor nær den er ønsket, og deretter velge maksimum. Sjette. Det viktigste. For å beregne en viss helningsvinkel til en linje, forestill deg at bildet over berøres av en rett linje med denne helningsvinkelen. Det er klart at fra dimensjonene til bildet og helningsvinkelen er det mulig å entydig beregne den vertikale forskyvningen av den rette linjen, slik at den spesifiseres entydig. Deretter vil vi gradvis flytte denne rette linjen nedover. På et tidspunkt vil hun berøre den hvite flekken. La oss huske dette øyeblikket og skjæringsområdet for den rette linjen med stedet. La meg minne deg på at en rett linje har 8-forbindelser på et fly, så sinte rop fra publikum om at en rett linje har én dimensjon, og område er et todimensjonalt konsept, er upassende her. Deretter vil vi flytte denne rette linjen ned en stund til, og huske skjæringsområdet ved hvert trinn, hvoretter vi vil oppsummere de oppnådde resultatene. Denne mengden vil være et estimat for denne rotasjonsvinkelen.
For å oppsummere det ovenstående: vi vil se etter en rett linje slik at når den beveger seg nedover bildet, øker lysstyrken til pikslene som ligger på denne rette linjen mest skarpt.
Så rotasjonsvinkelen er funnet. Men du bør ikke skynde deg å umiddelbart bruke den ervervede kunnskapen. Faktum er at dette vil ødelegge sammenhengen i bildet, og vi vil fortsatt trenge det.
Det neste trinnet er å skille karakterene fra bakgrunnen. Det at symbolene er mye mørkere enn bakgrunnen vil hjelpe oss mye her. Et helt logisk skritt fra utviklernes side - ellers ville bildet vært svært vanskelig å lese. De som ikke tror kan prøve å binarisere bildet selv og se selv.
Men "brute force"-tilnærmingen - et forsøk på å kutte av karakterer ved hjelp av en terskeltransformasjon - fungerer ikke her. Det beste resultatet jeg klarte å oppnå - ved t=140 - ser svært beklagelig ut. Det er for mye søppel igjen. Derfor måtte jeg bruke en løsning. Ideen her er følgende. Symbolene er vanligvis sammenhengende. Dessuten hører de ofte til de mørkeste punktene i bildet. Hva om du prøver å påføre en fylling fra disse mørkeste punktene, og deretter kaster de for små fylte områdene - åpenbart søppel?
Resultatet er, ærlig talt, fantastisk. I de fleste bilder kan du bli kvitt bakgrunnen helt. Det hender imidlertid at et symbol brytes opp i flere deler – i dette tilfellet kan én krykke i segmentering hjelpe – men mer om det senere.
Til slutt blir kombinasjonen av Dilate- og Erode-operatorene kvitt de små hullene som er igjen i karakterene, noe som bidrar til å gjøre gjenkjennelsen lettere.
Segmentering her er mye enklere enn forprosessen. Først av alt ser vi etter tilkoblede komponenter.
Deretter kombinerer vi komponenter som er tett horisontalt (prosedyren er nøyaktig den samme som før):
Denne algoritmen tillot oss å oppnå et resultat på 69 % av vellykkede gjenkjente bilder og oppnå en gjennomsnittlig feil på 0,3 tegn/bilde.
Blå
Så den blå operatøren var den tredje som fikk statusen "beseiret". Det var så å si et pusterom før den virkelig store fisken...
Det er vanskelig å skrive ned noe som fordeler, men jeg prøver likevel:
- Roterende karakterer er den eneste mer eller mindre alvorlige hindringen
- Bakgrunnsstøy som symboler
- Symboler berører noen ganger hverandre
I motsetning til dette:
- Bakgrunnen er betydelig lysere enn karakterene
- Symbolene passer godt inn i rektangelet
- Ulike farger på symboler gjør det enkelt å skille dem fra hverandre
Så, forhåndsprosess. La oss starte med å kutte ut bakgrunnen. Siden bildet er trefarget, vil vi kutte det i kanaler, og deretter kaste ut alle punktene som er lysere enn 116 i alle kanaler. Vi får denne fine masken:
Deretter konverterer vi bildet til HSV-fargerommet (Wikipedia). Dette vil lagre informasjon om fargen på symbolene, og samtidig fjerne gradienten fra kantene.
Påfør den tidligere oppnådde masken på resultatet:
Dette avslutter forprosessen. Segmentering er også ganske trivielt. La oss starte, som alltid, med komponentene til tilkobling:
Vi kunne stoppet der, men det viser seg å være bare 73%, noe som ikke passer meg i det hele tatt - bare 4% bedre enn resultatet av en åpenbart mer kompleks CAPTCHA. Så neste trinn er å snu rotasjonen av tegnene. Her trenger vi det faktum at jeg allerede har nevnt at lokale symboler passer godt inn i et rektangel. Ideen er å finne det omsluttende rektangelet for hvert symbol, og deretter bruke skråningen til å beregne helningen til selve symbolet. Her, ved å beskrive et rektangel, mener vi et som for det første inneholder alle pikslene til et gitt symbol, og for det andre har det minste arealet av alle mulige. Jeg bruker en ferdig implementering av algoritmen for å finne et slikt rektangel fra OpenCV (MinAreaRect2).
Denne algoritmen gjenkjenner vellykket 86 % av bildene med en gjennomsnittlig feil på 0,16 tegn/bilde, noe som bekrefter antagelsen om at dette faktisk er den enkleste CAPTCHA. Operatøren er imidlertid ikke den største...
Gul
Nå kommer den morsomme delen. Så å si, apoteosen til min kreative aktivitet :) Denne CAPTCHA er virkelig den vanskeligste både for en datamaskin og, dessverre, for en person.
Fordeler:
- Støy i form av flekker og linjer
- Roter og skaler symboler
- Tett arrangement av symboler
Feil:
- Veldig begrenset palett
- Alle linjer er veldig tynne
- Flekker krysser ofte ikke symboler
- Rotasjonsvinkelen til alle symbolene er omtrent den samme
Jeg tenkte lenge på det første trinnet. Det første som kom til tankene var å leke med lokale maksima (Dilate) for å fjerne liten støy. Denne tilnærmingen førte imidlertid til at det var lite igjen av bokstavene - bare fillete konturer. Problemet ble forverret av det faktum at teksturen til karakterene i seg selv er uensartet - dette er tydelig synlig ved høy forstørrelse. For å bli kvitt det bestemte jeg meg for å velge den dummeste måten - jeg åpnet Paint og skrev ned kodene til alle fargene som ble funnet i bildene. Det viste seg at det totalt er fire forskjellige teksturer i disse bildene, og tre av dem har 4 forskjellige farger, og den siste har 3; Dessuten viste alle komponentene i disse fargene seg å være multipler av 51. Deretter kompilerte jeg en fargetabell, ved hjelp av hvilken jeg var i stand til å bli kvitt teksturen. Men før denne "remap" sletter jeg også alle de for lyse pikslene som vanligvis er plassert i kantene av tegnene - ellers må jeg merke dem som støy, og deretter håndtere dem, mens de inneholder lite informasjon.
Så etter denne transformasjonen er det ikke mer enn 6 farger i bildet - 4 tegnfarger (vi vil konvensjonelt kalle dem grå, blå, lysegrønn og mørkegrønn), hvit (bakgrunnsfarge) og "ukjent", noe som indikerer at pikselfarge er dens plass kunne ikke identifiseres med noen av de kjente blomstene. Jeg kaller det betinget - fordi jeg på dette tidspunktet kvitter meg med tre kanaler og går videre til et kjent og praktisk monokromt bilde.
Neste trinn var å fjerne linjene fra bildet. Her reddes situasjonen ved at disse linjene er veldig tynne - kun 1 piksel. Et enkelt filter foreslår seg selv: gå gjennom hele bildet, sammenlign fargen på hver piksel med fargene til naboene (parvis - vertikalt og horisontalt); hvis naboene samsvarer i farge, og samtidig ikke sammenfaller med fargen på selve pikselen, gjør den til den samme som naboene. Jeg bruker en litt mer sofistikert versjon av samme filter, som fungerer i to trinn. På den første vurderer han naboer i en avstand på 2, på den andre - i en avstand på 1. Dette lar deg oppnå følgende effekt:
Deretter blir jeg kvitt de fleste flekkene, samt den "ukjente" fargen. For å gjøre dette ser jeg først etter alle de små sammenhengende områdene (mindre enn 15 i areal, for å være presis), bruker dem på en svart-hvitt maske og kombinerer deretter resultatet med områdene som er okkupert av den "ukjente" fargen.
Ved å bruke disse maskene bruker jeg Inpaint-algoritmen (eller rettere sagt, dens implementering i OpenCV). Dette er veldig effektivt for å fjerne det meste av rusk fra bildet.
Imidlertid ble OpenCV-implementeringen av denne algoritmen laget for å jobbe med fotografier og videoer, og ikke for å gjenkjenne kunstig lagde bilder med støyende tekst. Etter å ha brukt det, vises gradienter, som vi gjerne vil unngå for å forenkle segmentering. Dermed er det nødvendig å utføre ytterligere behandling, nemlig skjerping. For fargen på hver piksel beregner jeg den nærmeste fra tabellen ovenfor (la meg minne deg på at det er 5 farger - en for hver av karakterteksturene og hvit).
Til slutt er det siste trinnet i forprosessen å fjerne alle gjenværende små tilkoblede områder. De vises etter påføring av Inpaint, så det er ingen repetisjon her.
La oss gå videre til segmentering. Det er svært komplisert av det faktum at symbolene er svært nær hverandre. Det kan hende at bak det ene symbolet ikke er halvparten av det andre synlig. Det blir veldig ille når disse symbolene også har samme farge. I tillegg spiller rusk også en rolle - det kan skje at det i originalbildet var mange linjer som krysset hverandre på ett sted. I dette tilfellet vil algoritmen som jeg beskrev tidligere ikke være i stand til å bli kvitt dem.
Etter en uke brukt i resultatløse forsøk på å skrive segmentering på samme måte som i tidligere saker, ga jeg opp i denne saken og endret taktikk. Min nye strategi var å dele hele segmenteringsprosessen i to deler. I den første estimeres rotasjonsvinkelen til tegnene og den omvendte rotasjonen utføres. I det andre velges tegn på nytt fra et allerede utvidet bilde. Så la oss komme i gang. La oss starte, som alltid, med å søke etter tilkoblede komponenter.
Deretter må du beregne rotasjonsvinkelen til hvert symbol. Mens jeg jobbet med en operatør som var Greenpeace-fan, kom jeg opp med en algoritme for dette, men jeg skrev og brukte den bare her. For å illustrere arbeidet vil jeg trekke en analogi. Se for deg et stempel som beveger seg mot et svart-hvitt bilde av et symbol fra bunn til topp. Stempelhåndtaket som det skyves med er plassert vertikalt, arbeidsplattformen som det skyves med er horisontalt, parallelt med bunnen av bildet og vinkelrett på håndtaket. Håndtaket er festet til plattformen i midten, og ved festepunktet er det et bevegelig ledd, som et resultat av at plattformen kan rotere. Måtte terminologieksperter tilgi meg.
La håndtaket bevege seg oppover, skyv puten foran deg i henhold til fysikkens lover. Vi vil anta at bare det hvite bildet av symbolet er materiell, og stempelet passerer lett gjennom den svarte bakgrunnen. Da vil stempelet, etter å ha nådd den hvite fargen, begynne å samhandle med det, nemlig å snu - forutsatt at kraften fortsatt påføres håndtaket. Han kan stoppe i to tilfeller: hvis han treffer symbolet på begge sider av kraftpåføringspunktet, eller hvis han treffer symbolet med selve kraftpåføringspunktet. I alle andre tilfeller vil han kunne fortsette å bevege seg. Oppmerksomhet, klimaks: vi vil anta at rotasjonsvinkelen til symbolet er helningsvinkelen til stempelet i det øyeblikket det stoppet.
Denne algoritmen er ganske nøyaktig, men jeg tar ikke hensyn til resultater som åpenbart er for store (mer enn 27 grader). Fra resten finner jeg det aritmetiske gjennomsnittet, hvoretter jeg roterer hele bildet med minus denne vinkelen. Så søker jeg etter tilkoblede komponenter igjen.
Da blir det mer og mer interessant. I tidligere eksempler begynte jeg forskjellige manipulasjoner med de mottatte segmentene, hvoretter jeg overførte dem til det nevrale nettverket. Alt er annerledes her. For det første, for i det minste delvis å gjenopprette informasjonen som gikk tapt etter å ha delt bildet i tilkoblede komponenter, maler jeg på hver av dem i en mørkegrå farge (96) "bakgrunnen" - det som var ved siden av det utskårne segmentet, men var ikke inkludert i den , hvoretter jeg jevner ut konturene til tegnene, ved å bruke samme prosedyre som i forprosessen for linjer (med en avstand til en nabo lik én).
Formelt sett (fra programmodulenes synspunkt) slutter segmenteringen her. Den oppmerksomme leseren har kanskje lagt merke til at det ikke ble nevnt noe sted om å skille karakterene som henger sammen. Ja, det er sant - jeg sender dem inn for anerkjennelse nøyaktig i dette skjemaet, og fullfører dem på stedet.
Årsaken er at metoden for å separere fastsittende tegn som ble beskrevet tidligere (med den minste projeksjonen) ikke fungerer her - skrifttypen ble valgt veldig godt av forfatterne. Derfor må vi ta en annen, mer kompleks tilnærming. Denne tilnærmingen er basert på ideen om at et nevralt nettverk kan brukes til segmentering.
Helt i begynnelsen beskrev jeg en algoritme som lar deg finne antall tegn i et segment gitt den kjente bredden på dette segmentet og det totale antallet tegn. Den samme algoritmen brukes her. For hvert segment beregnes antall tegn i det. Hvis det bare er en der, er det ikke nødvendig å legge til noe, og dette segmentet sendes umiddelbart >>= til det nevrale nettverket. Hvis det er mer enn ett symbol, plasseres potensielle separatorer med like avstander langs segmentet. Deretter beveger hver separator seg i sitt eget lille nabolag, og samtidig beregnes reaksjonen til det nevrale nettverket til symbolene i nærheten av denne separatoren, hvoretter alt som gjenstår er å velge maksimum (faktisk gjøres alt dette av en ganske dum algoritme, men i prinsippet er alt egentlig omtrent slik).
Naturligvis utelukker deltakelsen av et nevralt nettverk i prosessen med segmentering (eller pre-segmentering, hvis du vil) muligheten for å bruke opplæringsordningen for nevrale nettverk som jeg allerede har beskrevet. Mer presist, det lar deg ikke få det aller første nevrale nettverket - det kan brukes til å trene andre. Derfor gjør jeg det ganske enkelt – jeg bruker konvensjonelle segmenteringsmetoder (projeksjon) for å trene det nevrale nettverket, mens ved bruk kommer den ovenfor beskrevne algoritmen inn i bildet.
Det er enda en subtilitet knyttet til bruken av et nevralt nettverk i denne algoritmen. I de forrige eksemplene ble det nevrale nettverket trent på nesten rå forprosesser og segmenteringsresultater. Her tillot dette oss å oppnå ikke mer enn 12 % av vellykket anerkjennelse. Dette passet kategorisk sett ikke meg. Derfor, før jeg startet neste æra med nevrale nettverkstrening, introduserte jeg forskjellige forvrengninger i de originale bildene, grovt modellerte de virkelige: legg til hvite/grå/svarte prikker, grå linjer/sirkler/rektangler, roter. Jeg økte også togsettet fra 200 bilder til 300 og la til de såkalte gyldig sett for å sjekke kvaliteten på trening under trening på 100 bilder. Dette gjorde det mulig å oppnå en produktivitetsøkning med rundt fem prosent, og sammen med segmentering ved et nevralt nettverk ga det akkurat det resultatet som jeg snakket om i begynnelsen av artikkelen.
Å gi statistikk er komplisert av det jeg endte opp med to nevrale nettverk: det ene ga en høyere prosentandel av gjenkjennelse, og det andre - en mindre feil. Her presenterer jeg resultatene av den første.
Totalt, som jeg har sagt mange ganger, var det 100 bilder i testsettet. Av disse ble 20 gjenkjent, 80 mislykket, og feilen var 1,91 tegn per bilde. Merkbart verre enn alle andre operatører, men CAPTCHA er også kompatibel.
I stedet for en konklusjon
Jeg la ut alt relatert til dette arbeidet i en spesiell forumtråd på nettstedet mitt, spesielt: kildekode, Netsukuku). Samtidig ønsker jeg noe som for det første kan gjøres på et år (minst med to personer), og for det andre seriøst vil kvalifisere for en høy plass ved samme ISEF. Kanskje du kan foreslå hvilken retning jeg bør gå?