[algoritme] Gemiddelde van een aantal punten vinden

[stereohead]

Mijn probleem is simpel:

Ik heb dit:


en het moet dit worden:


Het moeilijke is om ervoor te zorgen dat mijn programma het verschil 'ziet' tussen de verschillende witte stippen (groepen rode puntjes).

Vervolgens moet dus het midden of gemiddelde van zo'n groep puntjes gevonden worden, en liefst niet al te rekenintensief...

Ik gebruik namelijk VB6 en dit algoritme moet toch wel met zo'n 25 FPS kunnen worden.

Ik hoop dat iemand mij kan helpen

Achtergrond informatie

[ Voor 7% gewijzigd door stereohead op 17-01-2008 16:08 ]

[RobIII]

Waar is het voor? Het lijkt haast op een game ofzo en in that case zit je op het verkeerde pad Waarom moet het 25FPS trekken? Ben je bezig met motion detection en camera's ofzo?

En cluster is natuurlijk redelijk makkelijk te herkennen in dit geval; als de afstand tussen 2 rode punten meer is dan 2x (of 3x of...) de afstand tussen de andere punten dan zit je in een nieuw cluster lijkt me.

Het middenpunt vinden is niet veel meer dan de edges uitzoeken van een cluster en daar het midden van uitrekenen (width/2) en (height/2)

Verder lijkt me dit meer iets voor SEA

[ Voor 83% gewijzigd door RobIII op 17-01-2008 16:05 ]

[stereohead]

RobIII schreef op donderdag 17 januari 2008 @ 16:02:
Ben je bezig met motion detection en camera's ofzo?

Inderdaad zie ook dit topic

[FragFrog]

Wat je kan doen: recursief gemideldes berekenen mits de afstand klein genoeg is.

Met andere woorden, je pakt punt 1 en 2. Dicht bij elkaar? Dan krijg je een nieuw middelpunt A. Vervolgens kijk je naar A en punt 3. Dicht bij elkaar? Dan wordt A het gemiddelde van 1, 2 en 3. Niet dicht bij elkaar? Dan wordt B een nieuw punt. Op naar punt 4: dicht bij A of B? Dan bij hun gemiddeldes optellen. Niet? Nieuw punt C. etc etc etc.

Intern laat je A, B etc natuurlijk een array van punten zijn zodat elk nieuw punt alleen gewogen meetelt. Dit werkt alleen niet als de 2 groepen dichter bij elkaar liggen dan de grootte van 1 groep, maar daar valt weinig aan te doen zonder eerst van elk punt de afstand tot alle andere punten te berekenen waar je algoritme veel zwaarder en ingewikkelder van wordt

//edit
Blast you Rob, een beetje mijn idee uitwerken terwijl ik't zit te schrijven en sneaky je post aanpassen!

[ Voor 6% gewijzigd door FragFrog op 17-01-2008 16:09 ]

[P.O. Box]

FragFrog schreef op donderdag 17 januari 2008 @ 16:08:
Intern laat je A, B etc natuurlijk een array van punten zijn zodat elk nieuw punt alleen gewogen

idd... maar je kunt ook alleen het gemiddelde EN het aantal punten onthouden... en daarmee rekenen...

[FragFrog]

Edwardvb schreef op donderdag 17 januari 2008 @ 16:34:
idd... maar je kunt ook alleen het gemiddelde EN het aantal punten onthouden... en daarmee rekenen...

Totdat je dynamisch punten wilt aanmaken / verwijderen Als je uitgaat van een grid structuur is het denk ik efficienter om een set coordinaten voor elk 'middelpunt' bij te houden en een updater hebben die punten uitzet / aanzet dan om telkens overnieuw te beginnen.

[ Voor 27% gewijzigd door FragFrog op 17-01-2008 16:42 ]

[zwippie]

Iemand die ik ken is afgestudeerd op dit soort dingen (beeldverwerking/objectherkenning etc). Ik heb er dus zelf weinig verstand van, maar wat ik wel heb onthouden is dat een beeld eerst vaak wordt geblurred om er vervolgens bijvoorbeeld edge of blob detection op los te laten. Komt behoorlijk wat wiskunde bij kijken...

[Not Pingu]

In dit geval lijkt het me zinvoller om de afbeelding om te zetten van RGB color space naar HSL en dan alleen met het Hue kanaal te werken.
Hier iets over RGB->HSL conversie in C#

RobIII schreef op donderdag 17 januari 2008 @ 16:02:
Het middenpunt vinden is niet veel meer dan de edges uitzoeken van een cluster en daar het midden van uitrekenen (width/2) en (height/2)

Dat hangt af van het soort vormen dat de clusters kunnen aannemen. Wat je hierboven beschrijft is het vinden van het midden van een rechthoek rond de vorm, maar afhankelijk van de vorm kan dat dus een heel andere positie worden.

Beter lijkt me om de center of mass te berekenen, wat niet meer is dan het gemiddelde van alle punten. Dus tel de X en Y coordinaten van alle gevonden punten apart op en deel deze door het aantal punten.

[ Voor 7% gewijzigd door Not Pingu op 17-01-2008 17:13 ]

[Janoz]

Je start positie maakt het wat lastig. Wat je beter kunt doen is met een bitmap werken (een 2 kleuren plaatje met alleen zwart en wit). Je begint dus met het omzetten van het plaatje naar 2 kleuren. Vaak gebeurt dit middels thresholding. Hieruit komt een plaatje met vlekken. Vervolgens moet je kijken welke vlekdelen met elkaar verbonden zijn en dit zorgt ervoor dat je elke vlek appart hebt. Mocht je na het thresholden toch gaten in je vlekken krijgen dan zou je nog een zogenaamde 'dilatie' op het plaatje los laten. Hierbij maak je van alle witten punten hun buurpunten ook wit. Je vlekken groeien hierdoor ietsje waardoor gaten dicht gaan. Mochten de vlekken dan juist weer te groot zijn dan kun je er weer een erosie op los laten. Hierbij worden punten weer op zwart gezet wanneer ze te weinig witte buurpunten hebben. Hierdoor komen de gaten niet meer terug!

[stereohead]

@zwippie, Not Pingu en Janoz
Even voor de duidelijkheid, het vinden van de witte stippen werkt al. Wat nog moet gebeuren is de gevonden punten(rode stippen) uitzoeken, en herkennen welke bij elkaar horen.

Ik ga nu de methode van FragFrog uitproberen.

In ieder geval bedankt iedereen voor het meedenken!

[MSalters]

Relatief makkelijk. Wat je doet is een iteratieve clustering. Je begint met N punten en N*N/2 afstanden. Die gooi je in N clusters van 1 punt elk. Vervolgens ga je die in N-1 ronden groeien door elke keer de 2 clusters met de kleinste onderlinge afstand samen te voegen. In jouw geval zie je dan dat die afstand in de eerste N-2 rondes erg klein is, terwijl in de laatste ronde de afstand juist heel erg groot is. Dan zijn er dus 2 puntenwolken.

[Onbekend]

Zelf heb ik met precies de zelfde probleemstelling te maken gehad. Echter was het bij mij geen infraroodpen.


Hoe bepaalt jouw algoritme nu waar de rode puntjes komen?
Je kan lijnen verbinden tussen punten, en kijken of er veel kleurverschil tussendoor komt.
Dit aantal zal echter kwadratisch oplopen naarmate je meer witte vlekken krijgt.

[RemcoDelft]

Je zoekt dus het zwaartepunt van het witte vlekje? Dat is toch een kwestie van een raster er overheen leggen, en zowel in horizontale als in verticale richting vanaf een referentiepunt de som van afstand*stip delen door de som van de stippen?

[Opi]

Wellicht heb je nog wat aan http://en.wikipedia.org/wiki/Cluster_analysis en dan in het bijzonder de link naar http://cs.fit.edu/~pkc/papers/ictai04salvador.pdf waarin een methodiek beschreven wordt om te bepalen wat het optimaal aantal clusters is. Dit laatste is alleen relevant wanneer je dit niet op voorhand weet.

[Fish]

zo te zien worden er al samples genomen

maar de samples die in het midden liggen zijn niet meer relevant, alleen maar de buitenste
de binnenste hoef je imho niet mee te nemen in je berekening, scheelt je weer cpu

[joepP]

Zo te zien liggen de rode stippen op een grid. Als je aanneemt dat punten die aan elkaar grenzen bij elkaar horen kan je het eenvoudig in lineaire tijd doen, maar ik weet niet of die aanname toegestaan is. Indien wel, dan kan je het met het volgende algoritme doen. Je begint gewoon ergens, en je kleurt alle aangrenze punten met kleur 1 recursief. Als er dan nog ongekleurde punten overblijven ga je daar verder met kleur 2. Herhaal tot je klaar bent. Tot slot bereken je van alle kleuren het zwaartepunt, dat is gewoon het gemiddelde van de X en Y coordinaten.

Linkje voor Breadth-First Search (BFS): http://en.wikipedia.org/wiki/Breadth-first_search

[danslo]

Gewoon in een radius van x pixels om elke stip kijken of er een andere stip in de buurt is... Elke groep stippen gooi je in een aparte array en vanuit daar bereken je de middelste stip.

edit: Alhoewel je die stippen al op een of andere manier getekend moet hebben wat zou moeten betekenen dat je de data al hebt om het midden uit te rekenen?

[ Voor 30% gewijzigd door danslo op 18-01-2008 11:39 ]

[BestTested!]

Opi schreef op donderdag 17 januari 2008 @ 21:46:
Wellicht heb je nog wat aan Wikipedia: Cluster analysis - Wikipedia, the free encyclopedia en dan in het bijzonder de link naar http://cs.fit.edu/~pkc/papers/ictai04salvador.pdf waarin een methodiek beschreven wordt om te bepalen wat het optimaal aantal clusters is. Dit laatste is alleen relevant wanneer je dit niet op voorhand weet.

Inderdaad. Waarom zelf een methode gaan bedenken als er in de literatuur al methoden beschreven staan. In de link van Opi staat bijvoorbeeld het K-means clustering algorithme. In de meeste gevallen is dit algorithme prima in staat clusters te vinden. En de tijd waarin K-means dat doet is (meestal) in iets minder iteraties dan punten (worst case is superpolynomial, maar dat komt in de praktijk toch nooit voor).

Het algoritme is makkelijk te implementeren en er is voldoende onderzoek naar verricht. Mocht dit algoritme nog niet doen wat je wilt dan ga analyseren wat er fout gaat en probeer variaties van K-means.

Samengevat: Beter goed gestolen dan slecht verzonnen: Probeer K-means

[stereohead]

bij k-means moet je het aantal clusters vooraf al weten, en dat weet ik niet.

Ik heb het op het moment vrij druk maar ik laat het wel even weten wanneer het is gelukt, of wanneer ik meer hulp nodig heb

[Opi]

stereohead schreef op dinsdag 22 januari 2008 @ 21:23:
bij k-means moet je het aantal clusters vooraf al weten, en dat weet ik niet.

In het pdf-document waarnaar ik refereer wordt een methode aangegeven die het optimaal aantal clusters bepaalt. Het betreft een trial-and-error proces en op dat vlak kan ik me goed voorstellen dat het te veel tijd/berekeningen kost. Desalniettemin eist het algoritme niet dat het aantal clusters op voorhand bekend is.

Wat je, gegeven je dataset, zou kunnen doen, is stellen dat een element niet verder dan een bepaalde afstand van je clustercentrum afligt.

[ACM]

Opi schreef op dinsdag 22 januari 2008 @ 23:53:
Desalniettemin eist het algorithme niet dat het aantal clusters op voorhand bekend is.

K-Means wel. Dat algoritme probeert je dataset op te delen in (maximaal) K clusters.

Maar er zijn natuurlijk wel diverse andere clustering-algoritmes, hoewel die helaas lang niet allemaal zo makkelijk te implementeren zijn als K-means. Een mogelijkheid is natuurlijk om het aantal clusters vrij hoog in te stellen zodat er als het goed is een aantal lege over blijven en de rest kan je dan weg gooien. Maar dan is de kans aanwezig dat een en ander niet heel geweldig uitkomt.

[BestTested!]

ACM schreef op woensdag 23 januari 2008 @ 10:33:
[...]

K-Means wel. Dat algoritme probeert je dataset op te delen in (maximaal) K clusters.

Maar er zijn natuurlijk wel diverse andere clustering-algoritmes, hoewel die helaas lang niet allemaal zo makkelijk te implementeren zijn als K-means. Een mogelijkheid is natuurlijk om het aantal clusters vrij hoog in te stellen zodat er als het goed is een aantal lege over blijven en de rest kan je dan weg gooien. Maar dan is de kans aanwezig dat een en ander niet heel geweldig uitkomt.

Er is redelijk wat onderzoek gedaan hoe K-means toe te passen als het aantal cluster onbekend is. Maar als dit voor motion detection is kan je misschien eens in n beelden (zeg 15) het aantal clusters bepalen met een duurder algorithme. Voor de overige 14 beelden die daarna komen gebruik je hetzelfde aantal clusters.

[Confusion]

stereohead schreef op donderdag 17 januari 2008 @ 18:26:
Even voor de duidelijkheid, het vinden van de witte stippen werkt al. Wat nog moet gebeuren is de gevonden punten(rode stippen) uitzoeken, en herkennen welke bij elkaar horen.

Wat bedoel je precies met 'het vinden van de witte stippen werkt al'? Dat klinkt mij in de oren alsof je het probleem al hebt opgelost: je weet immers de lokatie en afmetingen van de stippen al? Als je op dit moment alleen nog maar een array met coordinaten van de rode stippen hebt, dan heeft je programma de witte stippen nog niet gevonden. (Dit kan zowel een terechte vraag als taalkundig gemiereneuk zijn; in het laatste geval kan je het negeren).

Wat weet je over de mogelijke afmetingen en verdelingen van de stippen? Als bepaalde configuraties zich nooit voordoen, kan je het K-Means algoritme waarschijnlijk behoorlijk optimaliseren door, a la Monte Carlo methoden, de manier waarop hij clusters 'random' probeert in te delen bij te sturen.

[stereohead]

Confusion schreef op woensdag 23 januari 2008 @ 20:33:
[...]

Wat bedoel je precies met 'het vinden van de witte stippen werkt al'? Dat klinkt mij in de oren alsof je het probleem al hebt opgelost: je weet immers de lokatie en afmetingen van de stippen al?

niet helemaal, ik weet alleen de coordinaten van de pixels met een helderheid van > 200 (van de 255)

Als je op dit moment alleen nog maar een array met coordinaten van de rode stippen hebt, dan heeft je programma de witte stippen nog niet gevonden. (Dit kan zowel een terechte vraag als taalkundig gemiereneuk zijn; in het laatste geval kan je het negeren).

Hmm misschien was ik niet zo duidelijk idd. Ik bedoelde dus dat het uitzoeken wat een witte stip is en wat niet al werkte, omdat er een aantal reacties waren over vormherkenning e.d. (wat trouwens wel erg waardevolle informatie was, alleen niet voor dit project)

Wat weet je over de mogelijke afmetingen en verdelingen van de stippen? Als bepaalde configuraties zich nooit voordoen, kan je het K-Means algoritme waarschijnlijk behoorlijk optimaliseren door, a la Monte Carlo methoden, de manier waarop hij clusters 'random' probeert in te delen bij te sturen.

de stippen hebben over het algemeen een ongeveer ronde vorm en in de uiteindelijke applicatie zijn de stippen wat kleiner.

K-Means is idd mooi algoritme, ik dacht altijd dat een van de eisen was, dat het aantal clusters bekend moet zijn.
Wat bij mij vaak een struikelblok is, is de ingewikkelde documentatie. Ik lees aardig wat engels, maar soms gaat het mn petje echt te boven


Ik heb nu de manier van FragFrog toegepast, wat al aardig werkt, en niet veel rekenkracht kost.