signFinder – “Final”

“Time flies when you’re having fun” – en zo kon het gebeuren dat de Google Summer of Code zomaar alweer helemaal voorbij was. Bedankt voor eenieders support, goede ideeen, en straatnaamborden. :)

De afgelopen week ben ik bezig geweest met naar een final toewerken van de signFinder. Het geheel is nu voorzien van aanmerkelijk duidelijkere code, die in de vorm van een library makkelijk in andere software gebruikt kan worden, en is er een stable versie online gezet in een tarball. Bovendien is er nu een verzameling documentatie, waarmee het voor iedereen duidelijk moet kunnen worden hoe de software werkt, en hoe deze voor eigen doeleinden gebruikt kan worden.

Is het hiermee dan helemaal afgelopen? – Nee, natuurlijk niet. Met name met roestige borden e.d. is er nog best wat te winnen aan nauwkeurigheid, en ik verwacht in mijn vrije tijd gewoon door te blijven bouwen aan het programma. Daarnaast wil ik natuurlijk iedereen aanmoedigen om dit product te gaan gebruiken. Daarom zullen Stefan en ik binnekort een website + webservice openen voor de signFinder, zodat iedereen eenvoudig de resultaten kan zien en kan gebruiken voor andere doeleinden.

Nog goede ideeen voor praktische toepassingen voor dit product? Laat een reactie achter!

signFinder – Borden Lezen vervolgd!

Enkele weken geleden rapporteerde ik over de eerste pogingen om signFinder verkeersborden te laten lezen. Inmiddels is de software met sprongen vooruit gegaan. Zie hier de resultaten.

dsc00180_result_resized

Om te beginnen heb ik de tesseract OCR netjes in de software geintegreerd. De gelezen tekst wordt in dit geval naast de borgen afgedrukt, maar kan natuurlijk ook zo na een database geschreven worden.

Daarnaast zijn de resultaten enorm verbeterd. Ik meet performance als het percentage van de borden die correct gedetecteerd worden in mijn eigen testset, dat vervolgens zonder enige fout door de OCR gelezen worden. Een stukje software wat dit getal genereerde, rapporteerde voor de initiele versie 42% performance.

Ik ben begonnen met de laatste versie van tesseract (2.04) te installeren. Dit zou performance moeten verbeteren, en bovendien kan ik hiermee een Nederlandse language file gebruiken. In eerste instantie was dit flink vloeken: zelfs met Nederlandse language file zakte de performance onmiddelijk naar slechts 24%. Vreemd genoeg bleek deze versie van tesseract, in tegenstelling van wat ik de vorige blogpost vermeldde, beter overweg te kunnen met greyscale images dan met de gegenereerde binaire images. Performance: rond de 58%.

Het is stom hoe de eenvoudigste oplossingen je soms weken kunnen ontschieten; In de vorige blogpost had ik het over het verbeteren van het contrast tussen de letters en de blauwe bordachtergrond. Nu worden deze plaatjes in RGB formaat opgeslagen, en de achtergrond heeft natuurlijk vooral brightness in het blue channel! Ik genereer nu mijn greyscale plaatje over alleen het red channel, en dit verbeterd het contrast behoorlijk.

eerst:aureliaweg_before

nu: aureliaweg_after Performance: Van 58% naar 75%

Dan zijn er van de 25% borden niet correct gelezen worden, veel borden met kleine foutjes. l wordt gezien als I, ruis zorgt, met name aan het begin en het eind, voor wat extra letters, enzovoort. Nu weten we een aantal dingen over verkeersborden die we kunnen gebruiken: Woorden op borden beginnen doorgaans met een hoofdletter, of zijn volledig in hoofdletters. Hoofdletters komen niet zomaar midden in een woord voor. We verwachten geen woorden van slechts een karakter, en bovendien beginnen borden vaak met een lidwoord.

Ik heb de vorige heuristieken toegevoegd, om kleine ocr-foutjes op te kunnen lossen:

  • Woorden van 1 karakter worden verwijderd.
  • Een I midden in een woord wordt in een l veranderd.
  • Eerste woorden, die met minder dan 2 veranderingen (Levenshtein distance) in ‘De’ of ‘Het’ kunnen veranderen, doen dat.

Met deze simpele heuristieken, gaat performance op mijn testset van 75% naar 92%!

Nu is het belangrijk te beseffen dat hier overfitting optreed; Ik heb fouten die ik zag optreden in mijn testset opgelost, en daarmee heb ik een set heuristieken die met name helpen deze testset correct te detecteren. Desalnietemin: een performance tussen de 75% en 90% lijkt me zeer mooi. Als we nu alleen nog een breder scala aan straatnaamborden konden detecteren..

signFinder – SURF

SURF is, net als SIFT, een keypoint-matcher in de computer vision. Dergelijk technologie wordt bijvoorbeeld gebruikt om de luchtfoto’s van opengeo aan elkaar te stitchen.

SURF keypoints bij het leren van straatnaamborden.

Mijn idee was om naast de huidig gebruikte histogram-matching, ook SURF (OpenSURF) te gebruiken om straatnaamborden te vinden. Na enige moeite is de trainer nu in staat om over alle voorbeeld-borden in de trainset keypoints te berekenen, en naar de _surfkeys.dat file te schrijven. de ‘signFinder’ executable leest de surfkeys.dat file, en laat zien waar op het plaatje keypoints die lijken op die van de trainingsset gevonden worden. Idealiter zouden er voornamelijk metingen in de straatnaamborden gevonden moeten worden.

SURF keypoint matching met trainingsset.

Zie de groene gevonden keypoints. Deze toepassing is wat anders als waar SURF meestal voor gebruikt wordt, en het werkt dan ook voor geen meter :/. Met lage gevoeligheid verschijnen er nauwelijks metingen, en met toenemende gevoeligheid lijkt het er op dat metingen net zo lief of liever op andere contrastrijke delen van het plaatje verschijnen. Met name randen van lantaarnpalen worden veel en graag herkend.

Op dit moment wordt ook nog erg eenvoudige matching gebruikt. Er is mogelijk nog een en ander te behalen met het trainen van een negatief voorbeeld om false positives te vermijden en geavanceerdere methoden om de feature vector te matchen. Dit resultaat is echter niet bemoedigend, en wellicht dat het beter is om naar andere technologien te kijken, of om nu eerst te focussen op de OCR. Suggesties zijn welkom!

Voor wie het toch wil proberen: Gebruik de versie in de ‘branches’ directory op de svn, download de ge-extracte keypoints hier (of gebruik de trainer), en compileer met -DSURF in de CFLAGS variabele in de Makefile.

signFinder – Borden Lezen!

Deze week ben ik bezig geweest met het lezen van de straatnaamborden. Hier een eerste preview.
Ik gebruikt momenteel de open-source OCR engine Tesseract.

In eerste instantie heb ik gekeken hoe de prestaties zijn met de greyscale-images van de borden, zonder enige verdere processing.

dsc00161jpg_sign0Deze methode kan van de 22 borden die gevonden worden in de eerste testset, er zes correct lezen.

De engine is behoorlijk gevoelig. Het volgende plaatje wordt perfect herkend:dsc00167jpg_sign0terwijl hij niet eens meer tekst kan halen uit dit plaatje:

dsc00165jpg_sign0Enkele pogingen om het contrast te verbeteren maken de resultaten alleen maar slechter. Ook logisch: Tesseract blijkt zelf vrij geavanceerde image-processing aan boord te hebben.

Dat moet toch beter kunnen. Volgende poging: Het segmenteren van letters met de color-histogram-matching die ook gebruikt wordt om de borden te vinden.

dsc00161jpg_sign01

Hier werkt tesseract een stuk beter mee, en slaagt er in om en nabij de helft van de borden goed te lezen.

Dit zorgt wel ook weer voor andere problemen.dsc00162jpg_sign0

De ruis om de ‘de’ heen, maakt dat de OCR dit bord leest als: J^_D$gg-Barkentijn
De volgende stap is nu om kleine ruis weg te filteren met blob detection. Ik hou jullie op de hoogte!

signFinder – Borden Uitsnijden

Vorige week ben ik voornamelijk bezig geweest met het uitsnijden van de verkeersborden, en het corrigeren van het perspectief zodat de letters er ‘zo recht mogelijk’ uitkomen en door OCR software gelezen te kunnen worden.

Tot mijn verbazing was het aanmerkelijk lastiger dan verwacht om aan de hand van de convex hull (het lijntje om borden heen) een plaatje uit te snijden: Het is verre van triviaal om de hoeken te vinden in een ruizig, vervormd, en mogelijk niet helemaal netjes omlijnt vierkant. Na diverse methoden geprobeerd te hebben, gebruik ik uiteindelijk de OpenCv GoodFeaturesToTrack functionaliteit. Als input voor de functie vul ik de convex hull om het bord heen in een los plaatje met wit op een zwarte achtergrond. Omdat corners nu eenmaal good features to track zijn (en lijnen niet), vindt deze functie netjes alle hoeken. Vervolgens sorteer ik de hoekpunten aan de hand van de punten in de convex hull.

Resultaat van het uitsnijden van borden.

Resultaat van het uitsnijden van borden.

Tot slot kan opencv plaatjes corrigeren voor perspectief aan de hand van vier hoekpunten. Linksonder het uitgesneden resultaat.
Merk ook op hoe kleine verschuivingen in de gevonden hoekpunten, meteen zorgen dat het bord minder ‘recht’ uitgesneden wordt.

signFinder – RoC curves

Tot 12/7 ben ik voornamelijk bezig geweest met het verbeteren van de color histogram matching.

Dit gebeurt vaak: Je zit te prutsen, en je wilt weten ofdat je aanpassingen het systeem verbeteren of niet. Zou je zeggen, kan niet zo’n probleem zijn. Ik heb mijn plaatjes, ik heb mijn labels, en we kunnen gewoon tellen hoeveel van de pixels in het label gevonden worden en hoeveel pixels er buiten het label gevonden worden door het histogram, toch?

Niet helemaal, omdat er in de histogram matcher een threshold ingesteld moet worden (Bij welke verhouding van een kleur in de positief-voorbeeld trainset tov de negatief-voorbeeld trainset, beschouwen we een kleur als verkeersbord-blauw). Omdat bij elke verandering van de dataset deze verhouding opschuift, kunnen deze waarden niet direct met elkaar vergeleken worden. Daarom worden er vaak RoC-curves gebruikt om de performance van twee classifiers over een brede range van thresholds met elkaar te vergelijken.

Oftewel: Is de performance beter geworden, nu we meer voorbeelden van verkeersborden hebben?

De RoC curves voor verschillende trainsets.

De RoC curves voor verschillende trainsets.

Langs de verticale as staat het deel van de pixels in het verkeersbord dat correct gedetecteerd wordt (sensitivity). Langs de horizontale as staat het deel van de pixels dat geen deel uitmaakt van het verkeersbord, maar toch als zodanig gedetecteerd wordt (1 – specificity). Als de threshold verlaagd wordt neemt de gevoeligheid van de detector toe, maar neemt het aantal verkeerde detecties ook toe. Dat is goed te zien in de RoC curve. De meest slechte detector denkbaar zal willekeurig positief of negatief classificeren, en zou een rechte lijn van het 0,0 tot 1,1 punt opleveren. Hoe beter de detector, hoe meer de lijn naar de linker bovenhoek bolt. Anders gezegd: Hoe groter de oppervlakte onder de grafiek, hoe beter. We zien hier dat we met de nieuwe dataset ongeveer 40% correcte detectie kunnen behalen met nauwelijks verkeerde detecties, maar als we 90% van de pixels correct willen classificeren, moeten we ook genoegen nemen met zo’n 50% verkeerde detecties.

Trainset 1 is de oorspronkelijke trainset. Trainset 2 is extra data die ik later verzameld heb. Trainset 3 zijn de straatnaamborden aangeleverd door de vriendelijke mensen op de talk-nl mailinglist, waarvoor mijn hartelijke dank! De testset bestaat uit een subset van trainset 1, 2, en 3 inc. nog wat foto’s van stefan, en wordt niet meer gebruikt om op te trainen.

We zien dus dat de extra data werkt! – De groene lijn van alle trainsets samen, geeft een betere detectie dan trainset 1, of trainset 2 en 3 alleen.

Bovendien heeft deze tool het mogelijk gemaakt om allerlei experimenten te doen.

De RoC curve bij het resizen van afbeeldingen in de trainset.

De RoC curve bij het resizen van afbeeldingen in de trainset.

Hier heb ik bijvoorbeeld het effect bekeken van het resize van alle afbeeldingen in de trainset van 1600×1200 voor trainen, welliswaar nog op alleen de eerste trainset. We zien dat beide histrogrammen zeer vergelijkbaar presteren, waar soms de ene en some de andere beter is op een bepaald deel van de curve. Als we de oppervlakte onder de grafiek uitrekenen, blijkt de niet-geresizede trainer toch nog net iets beter te presteren.

signFinder

De afgelopen vijf weken heb ik gewerkt aan het ‘signFinder‘ project voor de Google Summer of Code. Doel van het project is om Nederlandse straatnaamborden automatisch te detecteren, segmenteren, en pogen te lezen. Stefan mentort.

Er wordt histogram matching gebruikt om ‘straatnaambord blauw’ te detecteren. Gebieden met de juiste kleur worden in blobs verdeeld door middel van blob detection. Vervolgens worden een aantal statistieken gegenereerd van de blobs, waarna met decision boundaries blobs die onvoldoende op straatnaamborden lijken uitgesloten worden.

Tot dusver kunnen ‘mooie’ foto’s van nette straatnaamborden vrij goed gesegmenteerd worden.

Hoekborden correct geclassificeerd.

Hoekborden correct geclassificeerd.

Maar foto’s met verroeste borden, foto’s onder een grote hoek, foto’s genomen op grote afstand, of foto’s die overbelicht of onderbelicht zijn, of zelfs foto’s genomen met een camera die de kleuren anders renderd, leveren aanmerkelijk slechtere resultaten op.

Rusty street sign

Rusty street sign

Voor nu concentreer ik me op straatnaamborden, maar deze technologie kan ook gebruikt worden voor de detectie van andere borden, waarbij nummerborden een logische stap zijn.

Momenteel lijkt het probleem voornamelijk te zijn dat mijn trainset voor de histogram matching te eenzijdig is. Ik heb onlangs meer data verzameld, waarmee ik hoop de detectie robuuster te kunnen maken. Ook: Hoe meer data hoe nauwkeuriger het systeem. Als iemand nog een stapel foto’s van straatnaamborden heeft liggen, ik heb ze graag!

straatnaambord met slechte histogram matching.

straatnaambord met slechte histogram matching.

Voor wie er mee wil spelen, de code is te downloaden op google code. Ik zal vanmiddag wat readme filetjes toevoegen, maar eigenlijk is het verhaal simpel: Built de signFinder executable met make (opencv is vereist), en voor foto’s die op de command-line opgegeven worden, wordt er een <filename>_result.jpg bestand weggeschreven met een lijntje om de gedetecteerd straatnaamborden heen.  datasets zijn ook beschikbaar.

Ondertussen ga ik gewoon verder met het verfijnen van het systeem, binnenkort meer!