Archief - [PROG][Algoritme] Centrum van bepaalde gebieden op een figuur vinden

Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
s

stoffer

Legacy Member
Programma: Visual Basic 6 (gelieve geen commentaar hierover te geven, de net heb ik niet direct liggen, en het programma is toch voorzien voor een oude PC)

Het probleem is alsvolgt:

Ik heb een image, uit deze image moet ik de gebieden halen die voldoen aan een zekere kleur.
Bvb alle gebieden die wit zijn.
Nu moet ik het centrum van zo'n gebied kunnen bepalen.

Wat ik heb:
* Picturebox met figuur
* Algoritme die de figuur analyseert en de pixels die aan de verwachte kleur voldoen eruit haalt en in een 2-dimensionale array nu de waarde 1 stopt om aan te geven van op die plaats voldoet een pixel. (array heeft vb naam beeld)
* Algoritme die ook de rand van die gebieden aangeeft. (x,y) posities worden opgeslagen in 2 1-dimensionale arrays.

De figuur wordt pixel per pixel bekeken (rij per rij)

beeld kan dus vb zoiets zijn:
Code: 
001010000000000000
001000001111100000
000011100111000110
000011100111100010
000011100111000000
000001000000001100
000000000000000000
Dit beeld bestaat dus eigenlijk uit 6 gebieden.

Nu heb ik eigenlijk 2 zaken nodig
1) Het grootste gebied vinden (minder belangrijk in eerste instantie want ik denk dat ik hiervoor zelf wat heb gevonden)
2) Het centrum van een gebied berekenen.

Weet er iemand hoe ik dat (relatief) eenvoudig kan bepalen?
s

stoffer

Legacy Member
Ik heb zojuist zelf een algoritme geschreven die op basis van een punt in een gebied een bepaald gemiddelde gaat bepalen op volgende manier:
Tel alle x-coördinaten van de punten in een gebied op en deel door het totaal aantal punten in het gebied
Tel alle y-coördinaten van de punten in een gebied op en deel door het totaal aantal punten in het gebied
Dit geeft een goed resultaat bij cirkels, rechthoeken,... maar ik denk dat er misschien betere methodes zijn.

Hulp, ideëen zijn dus nog steeds welkom
.

.Acku.

Legacy Member
Ik heb een licht vermoeden dat het iets wiskundigs interessant zal zijn, iets als een fameuze Fourrier polytransformatie met interpolatie in een veelvlak ;)
V

Vich

Legacy Member
stoffer zei:
1) Het grootste gebied vinden (minder belangrijk in eerste instantie want ik denk dat ik hiervoor zelf wat heb gevonden)
Klik om te vergroten...
Wat bedoel je met "grootste"? Bedoel je het gebied met de kleinst passende rechthoek errond of bedoel je het gebied met het grootste aantal 1-waardes?

2) Het centrum van een gebied berekenen.
Weet er iemand hoe ik dat (relatief) eenvoudig kan bepalen?
Klik om te vergroten...
Bedoel je dan het centrum mbt de kleinst rondpassende rechthoek of het centrum, rekening houdend met de massa van het object?


(of beide?)

[edit] Via google kan je het best zoeken op "image processing", daar krijg je bvb deze result:
http://cimg.sourceforge.net/
't Is wel C++, maar dus ook gewoon een library die je in VB kan importeren :)
s

stoffer

Legacy Member
met grootste bedoel ik dus het gebied met het meeste aantal 1-waardes

kzal eens kijken naar die library
(voorlopig lijkt mijn eigen algoritme stand te houden al duurt het me nog net iets te lang)
k

killgore

Legacy Member
centrum is idd moeilijker, want wa is het centrum van 1111 of van
111
101
111

of moet het enkel convex zijn of zo :p?
s

stoffer

Legacy Member
Van:
1111 gaat het dan ook niet echt uitmaken of ik nu de 2e of de 3e 1 kies, ik ga toch tov een referentie beeld werken, dus zolang ik dezelfde regel toepas maakt dit niet echt veel uit.

111
101
111
Wel in theorie zou het onmogelijk zijn dat het centrum niet voldoet aan de criteria en de rand wel. (toch niet voor hetgeen ik uiteindelijk ga filmen)
Natuurlijk bestaan er uitzonderingen waar je dergelijke beelden gaat vinden, maar die hoef ik eigenlijk niet eens te beschouwen.
Op het moment zal deze als centrum die 0 geven, wat in orde is.
k

killgore

Legacy Member
K, ideetje: doe bij het aflopen dit:

Maak een extra array (vo weight-values).
Loop alle elementen af:
Als het een 0 is -> weight = 0.
Als het een 1 is:
-buur"knopen" aflopen: 1e buurknopen zijn van niveau 1, als daar een 0 is -> weight=1, anders die zen (nog niet gebruikte ffcourse) buren gaan aflopen tot je een 0 tegenkomt op een bepaald niveau, dat niveau == uw weight (dus het principe van breedte eerst zoeken). Natuurlijk gaat het na een tijdje veel sneller omdat je al op berekende weigts kan verder gaan en niet expliciet moet gaan zoeken tot je 0 tegenkomt.

In een gebied is dan het centrum diegene met hoogste waarde.

werkt vrij correct i guess met convexe figure, ma denk nie da het sneller is als het uwe.
b

blackrabbit

Legacy Member
stoffer zei:
Ik heb zojuist zelf een algoritme geschreven die op basis van een punt in een gebied een bepaald gemiddelde gaat bepalen op volgende manier:
Tel alle x-coördinaten van de punten in een gebied op en deel door het totaal aantal punten in het gebied
Tel alle y-coördinaten van de punten in een gebied op en deel door het totaal aantal punten in het gebied
Dit geeft een goed resultaat bij cirkels, rechthoeken,... maar ik denk dat er misschien betere methodes zijn.

Hulp, ideëen zijn dus nog steeds welkom
Klik om te vergroten...
Lijkt me fout bij een simpele figuur als deze:
Code: 
000000000000000000
000[color=red]00[/color]0000111111111
000[color=red]00[/color]0000111111111
000110000000000000
000110000000000000
000110000000000000
000110000000000000
Uw algoritme gaat rode nullen als 'centrum' teruggeven...


MOD: tenzij je met 'gebied' niet de hele figuur bedoelt, maar hoe bepaal je dan 'een gebied'?
k

killgore

Legacy Member
blackrabbit zei:
MOD: tenzij je met 'gebied' niet de hele figuur bedoelt, maar hoe bepaal je dan 'een gebied'?
Klik om te vergroten...
Zover ik het doorheb bedoelt hij idd niet gehele figuur (en zoja dan klopt men algoritme nog steeds vrij goed denk ek).
En uit zijn eerste post maak ik ook op dat hij al goed genoeg weet hoe een gebied te bepalen :).
s

stoffer

Legacy Member
blackrabbit zei:
Lijkt me fout bij een simpele figuur als deze:
Code: 
000000000000000000
000[color=red]00[/color]0000111111111
000[color=red]00[/color]0000111111111
000110000000000000
000110000000000000
000110000000000000
000110000000000000
Uw algoritme gaat rode nullen als 'centrum' teruggeven...


MOD: tenzij je met 'gebied' niet de hele figuur bedoelt, maar hoe bepaal je dan 'een gebied'?
Klik om te vergroten...

Het maximaal gebied bepaal ik eigenlijk min of meer intuïtief.
Ik heb niet nagegaan of het voor alle situaties klopt maar reeds op zeer veel figuren kunnen testen.
(er zal wellicht een fout optreden wanneer er 2 even grote gebieden zijn, maar dat gaat in de praktijk waarvoor ik het zal nodig hebben toch nooit voorkomen)

Mijn algoritme die ik gebruik om het gebied met de meeste 1's te bepalen:
Tel alle waarden per kolom bij elkaar op tot je een 0 tegenkomt, herbegin dan terug vanaf 0:
vb: 01100011110100 wordt: 01200012340100
Tel alle waarden per rij bij elkaar op tot je een 0 tegenkomt, herbegin dan terug vanaf 0
Tel nu beide bekomen matrices bij elkaar op.
Zoek de grootste waarde in die matrix.
Dat punt die je bekomt ligt nu (denk ik, heb niet de moeite genomen om dit dus voor alles na te gaan of te bewijzen) in het gebied (meestal dus aan een uithoek) dat het meeste 1s bevat.

Op basis van dat ene punt kan ik nu alle andere gebieden gaan elimineren en dan enkel op dat gebied het centrum bepalen.

Ik denk dat hetgeen killgore gepost heeft er relatief goed op trekt in een bepaalde zin. Maar vooraleer ik dat eens ga uittesten een paar bedenkingen:
- Volgens mij (en vermits ik met VB werk lijkt dit me moeilijk te implementeren, per pixel 8 buren afscannen neemt immers veel tijd in
- Ik denk dat dit niet helemaal klopt wanneer je figuur bvb ene is van de vorm:
001111111000
000111000000
001100000000
000111110000
000011100000
000011100000
k

killgore

Legacy Member
stoffer zei:
Het maximaal gebied bepaal ik eigenlijk min of meer intuïtief.
Ik heb niet nagegaan of het voor alle situaties klopt maar reeds op zeer veel figuren kunnen testen.
(er zal wellicht een fout optreden wanneer er 2 even grote gebieden zijn, maar dat gaat in de praktijk waarvoor ik het zal nodig hebben toch nooit voorkomen)

Mijn algoritme die ik gebruik om het gebied met de meeste 1's te bepalen:
Tel alle waarden per kolom bij elkaar op tot je een 0 tegenkomt, herbegin dan terug vanaf 0:
vb: 01100011110100 wordt: 01200012340100
Tel alle waarden per rij bij elkaar op tot je een 0 tegenkomt, herbegin dan terug vanaf 0
Tel nu beide bekomen matrices bij elkaar op.
Zoek de grootste waarde in die matrix.
Dat punt die je bekomt ligt nu (denk ik, heb niet de moeite genomen om dit dus voor alles na te gaan of te bewijzen) in het gebied (meestal dus aan een uithoek) dat het meeste 1s bevat.

Op basis van dat ene punt kan ik nu alle andere gebieden gaan elimineren en dan enkel op dat gebied het centrum bepalen.

Ik denk dat hetgeen killgore gepost heeft er relatief goed op trekt in een bepaalde zin. Maar vooraleer ik dat eens ga uittesten een paar bedenkingen:
- Volgens mij (en vermits ik met VB werk lijkt dit me moeilijk te implementeren, per pixel 8 buren afscannen neemt immers veel tijd in
- Ik denk dat dit niet helemaal klopt wanneer je figuur bvb ene is van de vorm:
001111111000
000111000000
001100000000
000111110000
000011100000
000011100000
Klik om te vergroten...
Tijd weet ik idd niet zozeer, het valt immens te tweaken nog, ma daar moete denk ek wel op zoeken

en tis gelijk ek zij: liefst op convexe, "normalere" figuren, dit zal idd iets anders geven. Mja, wat is hier dan ook het centrum :p.

Rotprobleempje ze da ge hebt :).
s

stoffer

Legacy Member
Mor tis wel nogal heel noodzakelijk, kzal straks es een voorlopig versieke van hetgeen ik heb (louter een toepassing v/h algoritme eigenlijk) uploaden.
Het zou leuk zijn moesten er een paar mensen eens een paar eigen figuren beelden scannen en zien naar het resultaat.
V

Valk

Legacy Member
ik ben eigenlijk benieuwd om wat voor toepassing het hier gaat :) Het klinkt iig interessant.
s

stoffer

Legacy Member
Zo interessant is het nu ook weer niet. :p
Hier is een downloadlink: Click
Bedoeling is dan van deze algoritmes toe te kunnen passen op beelden genomen door een webcam. (de code daarvoor heb ik al, dus als dit algoritme lijkt te kloppen moet ik ze nog enkel combineren)

(Paste image gaat enkel image erin steken als die op uw clipboard staat, als er geen figuur op uw clipboard staat krijgt ge foutmelding maar das gewoon omdat het een testprogramma is)
s

stoffer

Legacy Member
Der zat nog een foutje in mn bepaling van het grootste gebied.
Ik heb dit algoritme aangepast.

Maar de snelheid om een 640x480 beeld te analyseren ligt tussen de 2 en de 5sec. Dit zou nog omlaag moeten. Als iemand betere methodes weet, gelieve die te posten.
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
Terug
Bovenaan