[Alg] Clusteringsalgoritme

[Verwijderd]

Ik ben op zoek naar een snel clusteringsalgoritme dat ik wil gaan gebruiken voor real-time beeldanalyse. Ik heb zeg maar een plaatje waarin een aantal pixels goedgekeurd zijn, en een heleboel afgekeurd zijn. Nu zullen deze pixels zich over het algemeen dicht bij elkaar bevinden, en zo één of meerdere clusters vormen.
Deze clusters wil ik graag benaderen met een zo goed mogelijk passende rechthoek. Ik heb een implementatie gemaakt die dit doet, maar het probleem is dat als er twee of meer clusters zijn, m'n implementatie één grote rechthoek om deze twee clusters plaatst. Ook heb ik het idee dat het sneller moet kunnen.
Op Google vind ik eigenlijk alleen datamining clusteringalogritmen, die gebaseerd zijn op hoog-dimensionale ruimtes en vaak gemaakt zijn om te bepalen of er een clustering is of niet.

Heeft iemand hier ervaringen/ideeën

[Macros]

Persoonlijk heb ik hier geen ervaring mee. Wel weet ik dat veel video encoding algoritmes, vooral de mpeg 4 versies (divx, xvid, etc...) geavanceerde algoritmes hebben om bepaalde vlakken te detecteren die niet veranderen maar zich wel verplaatsen. Ik weet niet of je daar iets aan hebt.

[Verwijderd]

Dat werkt volgens mij met wavelets, dus kun je daar niet zoveel mee, omdat je geen vlakken maar een soort puntenwolken hebt...

[Janoz]

Wat is dicht bij elkaar. Zijn het stukken aanliggende pixels? En waneer vind je een cluster nog 1 vak waard en waneer zou je er twee van kunnen maken?

Het eerste dat mij nu tebinnen schiet is om clusters te bepalen met tarjan union find methode (kan de naam fout hebben gegokt). Je zou een grote footprint kunnen nemen (ipv alleen naar de aanliggende, maar bijvoorbeeld in een straal van 5 pixels, afhankelijk van de spreiding van de goedgekeurde pixels uiteraard). De snelheid van dit algoritme is O(NxM) waarbij N het totaal aantal pixels is en M de grootte van je footprint. Geef elk gevonden cluster zijn eigen bounding box en ga vervolgens bij overlap deze boxen samenvoegen.

[hobbit_be]

Heb je gezocht op

http://citeseer.nj.nec.com/cs

ik herinner me nog wel zo een 2D clustering paper (ivm face detection, analysis)

een snelle maar misschien ietwat brakke methode is x-aantal keer een 'close' matrix erop te gooien. alles wat dicht by elkaar zit wordt dan 1 plek. Als je dit dan nog een paar keer volgd met een open kun je tot misschien usefull results komen?.

Er zijn nog andere technieken ik denk dat er 1 is met FFT maar zeker ben ik der niet van. Je geeft ook weining uitleg van hoe advanced het moet zijn?. Zo kun je ook hor en ver histogrammen gaan analyseren om zo tot cluster detectie te komen? (min. max etc)...

je kan misschien beter met bouding elippses werken want BB zijn nogal grof en assymetrisch (ie rotation dependant).

[ Voor 10% gewijzigd door hobbit_be op 25-01-2004 17:40 ]

[Opi]

Wellicht zou je kunnen zoeken op K-means of KNN (K-nearest neighbor).

[Verwijderd]

Die K-means was ik idd al tegengekomen, maar snapte er niet echt veel van.
De punten kunnen tegen elkaar aanliggen, maar dit hoeft zeker niet. Als zeg maar 20% van de pixels in een gebiedje geaccepteerd zijn, moet het al bij m'n rechthoek horen.
Wat ik nu doe is zeg maar brute-force naar het cluster zoeken, eerst grof en dan steeds fijner...

[Opi]

Er zijn algorithmen bekend die het optimaal aantal clusters kunnen schatten door te kijken naar de fout. Als het aantal clusters bekend is, kan je per centrum van een cluster de optimale rechthoek proberen te bepalen.

[chris]

zoek 's naar Unsupervised Learning of Self Organising Networks.

K-Means Clustering kon inderdaad wel 's interessant zijn. Ook al is het geen lichte stof, het is wel wat jij zoekt, en "ik snap het niet" valt wel te verhelpen. Gewoon iets meer tijd er aan besteden

[Verwijderd]

Ok, ik begrijp dat K-Means clustering nu wel aardig, heb een werkende implementatie, maar ik blijf nog met één probleem zitten: ik weet van te voren het aantal clusters niet. In mijn probleem zal het aantal clusters tussen de 0 en de 4 liggen, maar het wisselt sterk en is onbekend voor het programma.
Hoe los ik dat op

[Verwijderd]

Tja.. .misschien handig als je je probleem nog iets concreter kan opscrijven??

Ik denk dat je het beste kan zoeken naar "connected components" ofzo. Ik heb zelf voor een real time person tracker eens zoiets gebruikt..

Maar even kort:

* hoeveel clusters zijn er te verwachten?
* is er veel of weinig ruis?
* welk percentage van het totale oppervlak is in een cluster?
* hoe heb je je data opgeslagen
etc etc

(Post es een screenshot van je plaatje?)

[ Voor 7% gewijzigd door Verwijderd op 26-01-2004 19:32 ]

[Verwijderd]

Ik ben bezig met een programma voor objectherkenning met behulp van kleurherkenning voor robotsoccer. Eerst ga ik dus alle pixels van het beeld bekijken, en bepalen welke pixels mogelijkerwijs bij het object horen. Dit levert een plaatje zoals:



Er is in het spel een oranje bal, deze is dus makkelijk te vinden. Het probleem ontstaat echter bij het herkennen van de andere robots, die rood zijn. Deze hebben namelijk precies hetzelfde uiterlijk. Het clusteringsalgoritme ziet twee clusters, veroorzaakt door twee robots, echter als één groot cluster. Er kunnen zich maximaal 3 andere robots in het beeld bevinden. Het is echter ook mogelijk dat er helemaal geen robot/cluster gevonden wordt.
Zoals je ziet is er redelijk veel ruis, dus bij vrij weinig datapunten bij elkaar moet er al een cluster gedetecteerd worden. Ook verschilt de grootte van de clusters vrij sterk, namelijk als een object zich verder weg bevindt.

Het probleem is dus dat met k-mean clustering de clustering waarschijnlijk wel lukken, maar ik weet het aantal clusters niet van te voren. Is het een idee om altijd 3 (het maximum) clusters op te zoeken, en dan foute weg te strepen. Hoe kan ik dat wegstrepen dan echter aanpakken

edit: Het moge duidelijk zijn dat in het bovenstaande plaatje één cluster gevonden moet worden.

[ Voor 4% gewijzigd door Verwijderd op 26-01-2004 20:04 ]

[Verwijderd]

Verwijderd schreef op 26 januari 2004 @ 20:03:
Ik ben bezig met een programma voor objectherkenning met behulp van kleurherkenning voor robotsoccer.

Tja, ik kan de concurrentie natuurlijk niet teveel helpen he (Uni Twente hier

Maar even serieus:

* Heb je ook een plaatje van die twee-robot situatie? Dan is het wat makkelijker te zien wat het handigst is. K-means is niet zo heel snel geloof ik
* Welke resolutie werk je? Je kan vast met een lagere resolutie af
* Zoek wat info op over erode en dilate, blur, thershold... digitale image processing

Denk eens na over het object en het beeld: hoeveel pixels moet een object minimaal hebben, hoeveel maximaal etc. Met wat simpele bewerkingen kom je meestal al heel erg ver (en met hoge snelheid)

[ Voor 15% gewijzigd door Verwijderd op 26-01-2004 20:49 ]

[Verwijderd]

Zo'n plaatje heb ik helaas momenteel ff niet. De resolutie van de beelden die we hebben is 320x240. Het is natuurlijk sowieso een idee om met een lagere resolutie te gaan werken voor de snelheid, alhoewel onze analyse nu al best wel snel is. Het probleem van de clustering blijft dan echter toch bestaan
Of denk je meer aan iets vanje zoekt de eerste goede pixel, en kijkt dan in de omgeving daarvan of er daar nog een paar zitten, en zo ja, dan heb je je object. Maar dan krijg je toch problemen met dat één object als meerdere herkend wordt, zeker als het object zich dicht bij de camera bevindt?

P.S.: Met die concurrentie zal het wel meevallen, we zijn pas net begonnen en maar met weinig mensen, dus het duurt nog wel even voor we competatief zijn

[ArieProductions]

Wanneer je de geometrische vorm van het te vinden onderwerp kent, kan je een hough transformatie proberen.

[chris]

Je zou gewoon kunnen kijken of er 4 clusters gevonden kunnen worden, vervolgens of er 3 gevonden kunnen worden, enz. Lijkt mij redelijk te doen, alleen kan het natuurlijk wel lang duren als je alleen maar een bal in je gezichtsveld hebt.

Dit kwam ik trouwens nog tegen:

Generally the number of "true" clusters in the data is not known. Therefore, it is a good idea to run the algorithm with different values for k that are near the number of clusters one expects from the data to see how the sum of distances reduces with increasing values of k.

Een beetje googlen doet wonderen!

[ Voor 44% gewijzigd door chris op 27-01-2004 12:13 ]

[chris]

Wat trouwens misschien ook wel érg interessant is: vector quantisation!

Zie bijvoorbeeld:
http://labrosa.ee.columbia.edu/doc/HTKBook21/node74.html en
http://eprint.uq.edu.au/a...3/01/VQconfpaperWOSPA.pdf (tip! zie trouwens ook de bibliography)

Ik denk dat dit precies is wat je zoekt, het verhoogt namelijk ook het aantal vectoren naarmate er een ingewikkelder patroon is...

[Verwijderd]

Dat vector quantisation is idd wel interessant, maar heb momenteel niet echt de tijd om het hele vision gedeelte om te gooien

Mijn idee is nu om k-means clustering gewoon met k=3 te draaien, en vervolgens clusters samen te voegen wanneer ze zeer dicht bij elkaar liggen of wanneer de punten op de lijn tussen twee means vrijwel allemaal ook goedgekeurde punten zijn (de nieuwe mean wordt dan het punt tussen de twee means in).
Ik zal jullie laten weten of het werkt

[Verwijderd]

Okee ff kort hoe ik zoiets zou doen:

- start scannen linksboven
- voorgrondpixel of nog niet gemarkeerd? markeren en alle buren recursief markeren (*), meest linkse, rechtse bovenste en onderste pixel bijhouden. Ook het aantal gemarkeerde pixels bijhouden. Stop de resultaten in een lijst
- verderscannen
(*) kan ook slimmer dmv scanline flooding etc

- loop de lijst door
- als de grootte groot genoeg is, doe dan iets , anders gooi je hem eruit

Stel in jouw voorbeeld van 320x240 pixels, bijvoorbeeld een aantal van 20x20=400 pixels of groter is een potentiele robot.

Omdat je ook de rechthoek om de "blob" bijhoud, kan je simpel op vorm checken. De robots zijn bij benadering vierkant (toch?) dus kan je simpel eisen dat hoogte niet meer dan 10% ofzo mag afwijken van breedte. Is dit tech zo, en is het aantal gevonden pixels groot genoeg, dan heb je waarschijnlijk te maken met "occlusion" -> een robot die half achter een andere staat.

enz enz enz.

Maar het lijkt me iig oox leuk om jou resultaten te zien (incl snelheid natuurlijk)

[jopie1983]

Wat je ook kan doen, is gebruik maken van Run Length Encoding om in de horizontale richting te clusteren, en vervolgens gebruik je het eerder vermelde Union Find om in verticale richting te clusteren. Werkt zeer snel en wordt o.a. gebruikt in door Carnegie Mellon University in hun CMVision library die reeds verschillende robocups heeft gewonnen.