Fórumok
Kellene nekem egy algoritmus, ami n (>25) dimenzióban adott ponthalmazt olyan struktúrában tárolja, hogy egy tetszőleges (n-dimenziós) ponthoz a legközelebbi szomszédját gyorsan megtalálja.
Először Voronoi-diagramra gondoltam (de az csak 2 dimenziós), aztán találtam http://www.pnylab.com/pny/papers/vptree/vptree.pdf ezt a cikket; ez jó lenne, csak éppen elég slendriánul van leírva az algoritmus, nem igazán jön össze sem a szöveggel, sem úgy magamagával.
Ha valaki tudna segíteni a tisztázásban...
Hozzászólások
Hat, ha nem szukseges, hogy olyan gyors legyen, akkor tudok ajanlani egy egyszerubb (c-ben irt) programot, ami O(sqrt(N)) ido"ben mukodik (N a pontok szama), persze ez nem a legjobb, de lehet hogy a ce'lnak megfelel (szvsz nem is az n, hanem az N a kritikus a problema szempontjabol). Itt csak annyit kell csinalni az elejen, mint inicializalas, hogy sorbarendezed a pontokat az egyik (pl x) koordinata szerint, O(N*log(N)) ido"ben.
A cikk az elegge vadnak tunik elso"re, valoban, meg kb. 1 e've keresgettem en is temaban hasonlo dolgokat, de a vegen maradt ez a fenti dolog, kb hasonlo okok miatt. Bar elegge 2d specifikus problemakra kellett, szoval egyszer egy szepnapon jo lenne megirni voronoi/kdtree/egyeb tree alapokra azt is...
Milyen távolsággal?
sqrt(sum((xi-yi)^2))?
"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o
Mondjuk.
A konkrét probléma: alapkép összerakása mozaik szerűen kis képekből. Ha nagyon nagy N (kés képek száma), akkor nagyon lassú a minden alapponthoz a hozzá legközelebbi (leghasonlóbb) megkeresése (n*n-es mozaik esetében n^2*N).
A dimenziószám onnan jön, hogy az alapképet (n*p)^2 pixelre méretezem, a donor képeket p*p-sre (p mint pontosság), és a megfelelő p*p-s alaprészlethez keresek hozzá hasonló (jelenleg Euklideszi, gyökvonás nélkül - legkisebb négyzetek módszere) képet.
Tehát p^2 dimenziós térben mozgunk.
Ha jól gondolom továbba 2 dimenziós rendezős algoritmust, akkor p^2-1 koordináta szerint rendeznem kellene az N pontot (O(p^2 * N*log(N))), hogy aztán benne p^2 * log(N) időben tudjak keresni.
Felőlem más távolság is lehet, de nem ez a kerékkötő.
Ahha, template matching.
Ebbe már én is belefutottam egyszer.
Én nem találtam ilyen trükkös reprezentációt (ettől még lehet, hogy van).
Távolságnak nem rossz az SSD (Sum of Square Differences), használják még a CC-t (Cross-correlation). Ez utóbbi előnye, hogy számolható FFT-vel, ami kb 15x15-ös képeknél már gyorsabb, mint def szerint számolni.
Az én trükköm merőben egyszerű volt, kiszámoltam a kis képek átlagszínét, és a nagyon eltérőeket kiszórtam, a maradéknál meg kiszámoltam közvetlenül a távolságot, majd kiválasztottam a legközelebbit.
Ezt egyébként pythonban (persze psychoval) illetve a számolós részeket (SSD, átlag) C-ben.
12x12-es mintákból 20000-et illesztettem ennél legalább egy nagyságrenddel több mintához, ez a lépés 10-20 perc körül volt.
Általánosítva: minden mintából előállítasz több kisebb mintát (1x1, 5x5, 15x15) majd ezek távolságát nézed, és a nagyon eltérőket kiszórod. Végül kiválasztod a legjobb egyezést.
Ez még mindig O(n) (n a minták száma) de egy kezelhető konstanssal.
"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o
Egyébként azt mondják az okosok (pl Knut), hogy előbb meg kell írni az algoritmust, majd utána optimalizálni.
Szerintem írd meg mindenféle trükközés nélkül, amit tesztelhetsz mesterséges adatokkal, (pl a képet zajosítva/elkenve feldarabolod, és a darabokból próbálod összerakni, így kevés mintaképből várható könnyen ellenőrizhető eredmény), majd ha ez működik, de lassú, akkor kell optimalizálni.
Szerintem meg fogsz lepődni, milyen számítási kapacitás van egy mai gépben. Becsapós a mindennapi használat, mert az idő javarésze az IO eszközökre való várakozással megy el.
"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o
Nekem elfogadható időben lefut a buta, "mindent mindenkivel" O(n*N) algoritmus, csak éppen n=30^2, N=1000 a nagyságrend.
Van viszont, aki azt írta, hogy napokig nem fut le neki a keresés - mondjuk nála n=100^2, N=10000 a nagyságrend...
Véges dimenziós téren a metrikák ekvivalensek. Tehát tök 8, hogy euklideszi távolsággal, vagy végtelen metrikával számolsz épp..
Marhára nem.
Mármint tényleg ekvivalensek, de nem mindegy mivel számolsz.
Határértéknél mindegy lenne, de itt véges halmazból kell a legközelebbit megtalálni. Az pedig nem ugyanaz lesz különböző metrikáknál.
Jelen esetben pedig képek között keresünk az emberi látás szempontjából legközelebbit, így egyáltalán nem mindegy melyik elemet találjuk legjobbnak.
"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o
Hasonló problémába pár éve futottam bele. Szerintem hasznos kiinduló pont lehet, -nekem is az volt- ez a cikk: http://local.wasp.uwa.edu.au/~pbourke/other/correlate/