Hough Transform - betekenisvolle lijnen ontdekken

woensdag 9 augustus 2006 08:52

The problem is choice

Je weet dat bij een kruis de lijnen tegen de 90 graden met elkaar kruisen. In feite kun je dus net zoveel van die groene lijntjes genereren als je wilt, als de nieuwste lijn die je genereert maar aan een paar voorwaarden voldoet:

1. hij mag met geen enkele andere lijn kruisen (nieuw pad)
2. hij mag met één of meerdere andere lijnen kruisen, op voorwaarde dat de kleinste hoek met de andere lijn(en) groter is dan X. Waar X bijvoorbeeld >=70.

uit die groene lijnen (de vectoren) kun je daarna je kruis halen.

[ Voor 3% gewijzigd door MicroWhale op 09-08-2006 08:05 ]

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

DexterBelgium

Maar dat werkt alleen als je weet wat je aan het herkennen bent, in hoeverre is die aanname correct?

T'all ya fine dandies, prancing about with yer head full of eyeballs, come and get me I say

woensdag 9 augustus 2006 09:22

Acties:

woensdag 9 augustus 2006 22:40

The problem is choice

DexterBelgium schreef op woensdag 09 augustus 2006 @ 08:52:
Maar dat werkt alleen als je weet wat je aan het herkennen bent, in hoeverre is die aanname correct?

Hij zegt dat hij een blauw kruis wil herkennen, niet dat hij er meerdere vormen mee wil herkennen.

Als dat laatste het geval is dan is het TS aan te raden om eens naar neurale netwerken te gaan kijken. Deze kunnen op een hele makkelijke manier verschillende vormen leren herkennen zonder daar ingewikkelde code voor te hoeven kloppen.
Het heeft bovendien als voordeel dat je een antwoord kan maken als waarschijnlijkheid van 0..1 dat het een bepaalde vorm is. Door een lerend NN te maken waarin je achteraf invoert wat de uitkomst had moeten zijn, kun je het net heel snel leren wat een kruis, rechthoek, cirkel, etc.. is.

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

donderdag 10 augustus 2006 09:38

Topicstarter

Hmm, bedankt voor de ideeën iedereen. Ik denk dat ik uiteindelijk toch ga proberen een NN te implementeren. Wordt weer een hoop leeswerk...

Acties:

donderdag 10 augustus 2006 10:28

ehm we pleuren er een neuraal netwerk op en hij leert het automatisch ? zeker met beeldherkenning zou ik zoveel mogelijk kennis die ik heb over het te herkennen object ook daadwerkelijk gebruiken. In de projecten die ik met beeldherkenning gedaan heb in combinatie met neurale netwerken zat het merendeel van het werk in de preprocessing van de plaatjes, op zoek naar belangrijke kenmerkende features.
Het heeft nou eenmaal niet zoveel zin een plaatje van (wat is het in dit geval ?) 256 x 256als inputs op een neuraal netwerk aan te bieden, dat hadden van het klassieke DARPA tank herkenning verhaal al geleerd.

duh ?

Acties:

donderdag 10 augustus 2006 10:35

The problem is choice

hier is een werkend voorbeeld van een backpropagating netwerk waarmee je kan spelen.

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

donderdag 10 augustus 2006 11:00

The problem is choice

staefke schreef op donderdag 10 augustus 2006 @ 09:38:
Het heeft nou eenmaal niet zoveel zin een plaatje van (wat is het in dit geval ?) 256 x 256als inputs op een neuraal netwerk aan te bieden, dat hadden van het klassieke DARPA tank herkenning verhaal al geleerd.

Het doel van preprocessing is alle onbelangrijke gegevens uit het plaatje te filteren. Als de preprocessing van het plaatje met goede filters en een goede achtergrond gedaan wordt, dan zal de herkenning van het object door het neurale netwerk gedaan kunnen worden.

In de hierboven getoonde plaatjes, lijkt de preprocessing (het filteren/etc.. van al het (in dit geval) blauw uit een webcamplaatje) prima in orde en krijgt het neurale netwerk de input die het nodig heeft om tot een goede herkenning te kunnen komen.

[ Voor 5% gewijzigd door MicroWhale op 10-08-2006 10:37 ]

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

donderdag 10 augustus 2006 15:36

Topicstarter

Staefke:
Jup helemaal gelijk. Mn plan was dus ook om of de edge detector output te gebruiken, of de Hough data, om daaruit de goede lijnen te halen.

Logos:
Bedankt! Ik ga er direct naar kijken

Acties:

donderdag 10 augustus 2006 17:02

@logos:
allemaal mooi en wel (leuke demo trouwens

) maar in diezelfde demo komen een aantal dingetjes die in de praktijk de boel behoorlijk verkloten niet voor: schaal en rotatie.

Schaal en rotatie invariantie probeert ie in dit geval middels de Hough transform te tackelen, zou ook via template match achtige technieken kunnen (google maar eens op rotation scale invariant object recognition, krijg je direct een hoeveelheid aan wiskunde over je maar misschien gaat dat te ver..)

@ts:
In ieder geval: kennis die je m.b.t. de te herkennen objecten hebt (neem aan dat je straks ook wil weten wanneer je schoonmoeder door het beeld loopt) zou ik gebruiken.

duh ?

Acties:

donderdag 10 augustus 2006 17:34

Topicstarter

De schaal en rotatie zijn inderdaad een groot probleem voor een simpel NN. Maar is er geen netwerk die de vorm uit bepaalde inputs kan leren? In plaats van gewoon waardes te hechten aan bepaalde pixels (wat dat back-propagation voorbeeld dus deed). Of zit ik dan echt vast aan "template match" technieken?

Zijn er nog goede boeken over dit soort problemen die ik kan lezen?

[ Voor 10% gewijzigd door microchip op 10-08-2006 17:04 ]

Acties:

Verwijderd

Hier is een boek te vinden waar een en ander over image processing in staat:
http://www.sas.el.utwente...dbb/course%20material.htm

Ik weet niet direct of er iets instaat wat je verder kan helpen, het is in ieder geval wel een goed boek over van alles wat met dit onderwerp te maken heeft.

donderdag 10 augustus 2006 23:35

Acties:

joepP

microchip schreef op donderdag 10 augustus 2006 @ 17:02:
De schaal en rotatie zijn inderdaad een groot probleem voor een simpel NN. Maar is er geen netwerk die de vorm uit bepaalde inputs kan leren? In plaats van gewoon waardes te hechten aan bepaalde pixels (wat dat back-propagation voorbeeld dus deed). Of zit ik dan echt vast aan "template match" technieken?

Zijn er nog goede boeken over dit soort problemen die ik kan lezen?

Rotatie los je brute force op door gewoon over alle 360 graden te roteren, en pas daarna te schalen. Dat laatste doe je eenvoudig met een bounding box, en daarna afbeelden op een X bij X raster, bijvoorbeeld 16x16. Daarna laat je het NN op deze instantie los. Als het NN triggert heeft ie'zijn' input herkend, en weet je ook direct de rotatiehoek en de schaling.

Sim-pel

vrijdag 11 augustus 2006 00:54

Acties:

vrijdag 11 augustus 2006 12:32

hmmm toch niet zo simpel...

probleem is nl. dat het moeilijk is om uit te sluiten dat ie niet gaat 'triggeren' op het moment dat er geen kruis in beeld is, omdat nl. de verzameling plaatjes uit die categorie in principe oneindig groot is (schoonmoeders, vierkanten, braadworsten, noem maar op) en over die categorie eigenlijk weinig kan zeggen; echter zo'n neuraal netwerk geeft altijd 'antwoord' en het kan dan heel goed een kruis met een vlieg verwarren...

duh ?

Acties:

vrijdag 11 augustus 2006 12:45

The problem is choice

Voor plaatjes:

Om het probleem te verhelpen, kun je bij de preprocessing een algoritme toepassen wat het 'plaatje' (of een belangrijk deel daarvan) reduceert tot een standaard aantal pixels. (zie zeer hulpzame link van Tweakert) Ik kan me voorstellen dat er voor de rotatie ook zoiets gedaan kan worden.
*edit* dit is boven dus al door joepP beantwoord....

Voor vectoren:

Schaal en rotatie zijn hierbij totaal irrelevant. Hier kan het object geanalyseerd worden door bijvoorbeeld het aantal punten, het aantal hoeken, de grootte van de hoeken en lengte van lijnen tussen verschillende hoeken gebruikt worden.

Marreuh... ben je inmiddels al verder? kun je misschien laten zien wat het resultaat nu is? Ik ben zeer nieuwsgierig naar de resultaten van je werk.

[ Voor 15% gewijzigd door MicroWhale op 11-08-2006 12:38 ]

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

vrijdag 11 augustus 2006 14:53

The problem is choice

joepP schreef op donderdag 10 augustus 2006 @ 23:35:
[...]

Rotatie los je brute force op door gewoon over alle 360 graden te roteren, en pas daarna te schalen. Dat laatste doe je eenvoudig met een bounding box, en daarna afbeelden op een X bij X raster, bijvoorbeeld 16x16. Daarna laat je het NN op deze instantie los. Als het NN triggert heeft ie'zijn' input herkend, en weet je ook direct de rotatiehoek en de schaling.

Sim-pel

Door 360 graden te roteren krijg je bij een bepaalde rotatie een 'kleinste boundingbox'. (kan vast slimmer, door de boundingbox vierkant te houden, maar dié te laten roteren bijvoorbeeld). De uitkomst hiervan giet je in een standaard mal (bijv. 16x16 pixels) voor je vergelijking. Mocht het object niet herkend worden, hoef je in principe nog maar 3 andere rotaties (90,180,270) te voeden. Of je voed ze natuurlijk meteen alle 4.

Het enige belangrijke is dat je vandaag altijd rijker bent dan gisteren. Als dat niet in centen is, dan wel in ervaring.

Acties:

zaterdag 12 augustus 2006 17:27

Topicstarter

Ik ben nog niet echt verder gekomen. Ik heb nog nooit eerder iets met Neurale Netwerken en back-propagation gedaan, dus ik ben daar nu wat over aan het lezen.

Ik denk dat ik iig het roteren ga proberen, kijken of daar wat goeds uitkomt. Maarja, het is iig geen "slimme" methode...

Als jullie willen, kan ik de sources wel online zetten (maar er kunnen wel een paar rommelige stukjes in zitten). Het is geschreven in C#.

Acties:

joepP

staefke schreef op vrijdag 11 augustus 2006 @ 00:54:
hmmm toch niet zo simpel...

probleem is nl. dat het moeilijk is om uit te sluiten dat ie niet gaat 'triggeren' op het moment dat er geen kruis in beeld is, omdat nl. de verzameling plaatjes uit die categorie in principe oneindig groot is (schoonmoeders, vierkanten, braadworsten, noem maar op) en over die categorie eigenlijk weinig kan zeggen; echter zo'n neuraal netwerk geeft altijd 'antwoord' en het kan dan heel goed een kruis met een vlieg verwarren...

Onzin.

Een neuraal netwerk voor beeldherkenning gebruik je meestal voor slechts een enkel karakter/object, en laat je een 0 opleveren indien er geen herkenning heeft plaatsgevonden, en een 1 indien wel. Als het neurale netwerk triggert kan je er dus vanuit gaan dat je je object hebt gevonden, zo niet dan moet je je NN beter trainen.

zaterdag 12 augustus 2006 18:02

Acties:

zondag 13 augustus 2006 13:34

Topicstarter

Niet helemaal onzin, misschien een beetje overdreven. Wat staefke bedoelt (denk ik) is dat je een NN onmogelijk op álle situaties kan trainen. Dat zie je heel goed in het eerdergenoemde voorbeeld van back-propagation. Het netwerk wordt getraind zodat als er een '1' wordt ingevoerd de output ook aangeeft dat er een '1' is ingevoerd. Het netwerk wordt ook getraind zodat als er een 2, 3, 4, 5, 6, 7, 8 of 9 wordt ingevoerd, het netwerk aangeeft dat er géén '1' is ingevoerd. Maar op het moment dat je een 'A' invoert ofzo, is het onvoorspelbaar wat het netwerk doet, omdat het netwerk niet getraind is om bij een 'A' niets te herkennen.

Dit kan je dus omzeilen door het netwerk heel goed te trainen, en bij elke fout het opnieuw trainen. Maar je kan het netwerk onmogelijk op alle situaties voorbereiden.

Acties:

joepP

Volgens mij is het idee van een goed NN juist dat het alleen triggert als het de juiste invoer krijgt, en dus niet afgaat op vreemde invoer. Uiteraard is theoretisch misschien wel mogelijk een zodanige invoer te genereren dat er toch iets onbekends herkend wordt, maar in de praktijk zal dat waarschijnlijk nooit voorkomen.

zondag 13 augustus 2006 15:12

Acties:

donderdag 17 augustus 2006 12:43

Topicstarter

Ik zeg nog een keer: ik heb nog nooit iets gedaan met Neurale Netwerken. Dit heb ik alleen afgeleid uit artikelen die ik heb gelezen enzo...

Even een heel simpel voorbeeld. Stel je hebt een NN met 2 inputs. En je traint het zo dat als input0 hoog is output ook hoog wordt. Dus als input0 laag is, wordt output ook laag.

Maar bij de training tot nu toe is input1 altijd laag gebleven. Dus misschien is de weight wel heel hoog of heel laag zodat als op input1 hoog gezet wordt, het een grote invloed heeft op de uitkomst, terwijl dit eigenlijk niet mag.

Om het even in een plaatje-herkennings context te zetten, één enkele pixel waarop nog nooit getraind is kan een grote invloed hebben op de herkenning.

Acties:

BestTested!

microchip schreef op zondag 13 augustus 2006 @ 15:12:
Ik zeg nog een keer: ik heb nog nooit iets gedaan met Neurale Netwerken. Dit heb ik alleen afgeleid uit artikelen die ik heb gelezen enzo...

Even een heel simpel voorbeeld. Stel je hebt een NN met 2 inputs. En je traint het zo dat als input0 hoog is output ook hoog wordt. Dus als input0 laag is, wordt output ook laag.

Maar bij de training tot nu toe is input1 altijd laag gebleven. Dus misschien is de weight wel heel hoog of heel laag zodat als op input1 hoog gezet wordt, het een grote invloed heeft op de uitkomst, terwijl dit eigenlijk niet mag.

Om het even in een plaatje-herkennings context te zetten, één enkele pixel waarop nog nooit getraind is kan een grote invloed hebben op de herkenning.

Als je nog nooit iets met NN hebt gedaan kan je eens proberen om dit boek te bemachtigen:
Neural Network Design
De eerste 4 hoofdstukken staan online.

Afhankelijk wat voor soort NN je kiest zal je met bovenstaand probleem te maken krijgen. Het perceptron model bijvoorbeeld zal dit probleem zich voordoen. Kies je voor een Adeline network (waarbij alles begint op 0 en de uiterste waarden -1 en 1 zijn) zal deze pixel dus geen enkele betekenis hebben op het getrainde netwerk. NN's zijn al even geleden, dus weet niet zeker of dit nu juist andersom moest zijn.

Zowiezo is het boek een aanrader om de algoritme snel te maken, aangezien er verschillende learning-rules woorden aangeboden in matrix-vorm en verschillende methodes om de maximale learning rate te bepalen.

zaterdag 19 augustus 2006 21:13

Acties:

DroogKloot

depenisvanjezus

Een neuraal netwerk hiervoor inzetten is lichtelijk van de pot getrokken.

De standaardaanpak is om je getransformeerde parameterbeeld op te delen in bins (stembussen) van een zekere grootte en dan te tellen voor welke bins het vaakst gestemd is (ie. welke de meeste Hough-stamps bevatten), en die vervolgens terug te transformeren naar lijnen. De point-to-line parameter transformatie werkt trouwens beter dan de point-to-sine in dit geval.

zondag 20 augustus 2006 18:47

Acties:

zondag 20 augustus 2006 19:01

Topicstarter

Wow, dat ziet er uit als een geweldig boek! Vandaag maar even lezen...

@Droogkloot
De standaardaanpak werkt dus niet. Daarvoor zijn de lijnen niet perfect genoeg. Staat in de startpost beschreven.

Acties:

DroogKloot

depenisvanjezus

Nee, dat staat het niet. Je vermeldt helemaal niets over het gebruik van bins, alleen maar dat je "vier punten kiest waar de meeste golven doorheen gaan" en dat die leiden tot meerdere bijna gelijke lijnen (wat logisch is omdat er veel bijna gelijke snijpunten zijn die dezelfde lijn voorstellen). Conclusie: of je 'punten' zijn te klein, of je telt de stamps niet goed en transformeert teveel ervan terug. Leuk dat je je met computer vision bezighoudt, maar denk nou niet dat jouw probleem uniek is en niet met de standaard technieken die ervoor ontwikkeld zijn op te lossen valt.

[ Voor 4% gewijzigd door DroogKloot op 21-08-2006 13:16 ]

maandag 21 augustus 2006 13:40

Acties:

maandag 21 augustus 2006 14:53

Topicstarter

Ok, ik zal het wat anders uitleggen. Ik gebruik wel degelijk bins in mijn code. Ik heb 360 bins voor alle theta's en 400 bins voor alle rho's. Het probleem is alleen dat als ik de bins groter maak, ik fijne lijnen (kleine kruisen) niet kan onderscheiden. En bij grote kruizen komen er dan meerdere lijnen die praktisch hetzelfde zijn.

Nog maar weer eventjes een voorbeeld. Uiteindelijk wil ik zo'n kruis ook kunnen herkennen.
Hier de input. Hier wordt edge detection op losgelaten.
Afbeeldingslocatie: http://home.wanadoo.nl/markvdw/input.PNG

Afbeeldingslocatie: http://home.wanadoo.nl/markvdw/input.PNG

Hier de Hough output:
Afbeeldingslocatie: http://home.wanadoo.nl/markvdw/houghOutput.PNG

Het lijkt mij heel moeilijk om daar 4 goede lijnen uit te halen die ook echt corresponderen met het kruis. Is er misschien een aanpassing/uitbereiding voor deze standaard methode die dit kan oplossen?

Acties:

DroogKloot

depenisvanjezus

Als je het niet al doet: gebruik de intensiteit van de gedetecteerde edge-pixels als weegfactor voor de stamps zodat bepaalde bins duidelijk meer gevuld worden dan anderen. Verder kun je de grootte van de bins koppelen aan de schaal waarop je edge detector opereert, hoe kleiner het object hoe kleiner de schaal moet zijn en dus hoe krapper de bins.

dinsdag 22 augustus 2006 12:24

Acties:

vrijdag 25 augustus 2006 00:51

Topicstarter

"Als je het niet al doet: gebruik de intensiteit van de gedetecteerde edge-pixels als weegfactor voor de stamps zodat bepaalde bins duidelijk meer gevuld worden dan anderen."
Jup dat deed ik al

"Verder kun je de grootte van de bins koppelen aan de schaal waarop je edge detector opereert, hoe kleiner het object hoe kleiner de schaal moet zijn en dus hoe krapper de bins."
Je hebt me op een idee gebracht! Dankjewel!
Ik ga nu proberen de kruis te schalen naar een vaste grootte zodat ik altijd dezelfde hoeveelheid bins kan gebruiken.

Ik ga toch ook nog een NN proberen te implementeren. Puur voor de lol, ookal kan het anders

Acties: