OpenCV felesleges számítás spórolása.

Fórumok

Sziasztok!

Az a felállás, hogy egy spektrumon fft-t hajtok végre (a számításigényes része gyakorlatilag, egy 1D-s fft), de nekem a képződő frekvenciatartományanak, csak egy szűk része kell, a tartomány pedig brutális nagy. Telejsen fölösleges kiszámolni a komplett spektrumot (jó ha 10%-ami kell nekem a spektrumból, a többit eldobom, mert csak zaj). De a cv::dft()-hez nem találtam semmi leírást, hogy hogyan optimalizálható a számítást tartományra (első ránézésre ez nem megoldható?). Egyébként írtam egy saját megoldást erre, de leteszteltem az opencv-teljes spektrumra és az enyémet teljes spektrumra , az opencv-s lényegesen gyorsabb (amin nem csodálkozom, mert sse..... és millió más optimalizált, azenyém sima cpp kód), viszont, ha szűkítem a spektrumot akkor az én kódom jóval gyorsabb, mível jóval kevesebbet kell így számolni. Gondoltam az opencv-dft-jén ha ugyanezt végre tudnám hajtani akkor járnék a legjobban. Valakinek van ötlete erre?
Mindenkinek előre köszi.

Hozzászólások

Egy UP!! az éjszakai műszaknak.

------
3 fajta matematikus létezik. Aki tud számolni, és aki nem.

Kicsit utána olvastam, hogy mit is csinál az FFT:
* Az N alappontú FFT-t visszavezeti két N/2 alappontú FFT-re úgy, hogy az N kimenet mindegyike két értéket vesz alapul a kisebb alappontú FFT-ből.
* Úgy is vehetjük, hogy a megoldás során szintjeink vannak. Legyen összesen L darab szint úgy, hogy: 2^L=N
* A k-adik szinten szinten 2^k darab 2^(L-k) alappontú FFT van. Tehát minden szinten N szám, és mindegyiknek a kiszámítása - az eggyel feljebbi szint alapján - kb ugyanannyi erőforrást igényel (legyen ez az 1 művelet)
* A teljes számítást tekinthetjük egy nagy Nxlog2(N)-es táblázatnak, aminek celláiban vannak a kiinduló értékek, a részeredmények, és az FFT eredménye is. A cellák között függőségi viszony van, ami megadja hogy egy adott cella kiszámításához melyik eggyel feljebb lévő cellaértékekre van szükség.
* Az utolsó szint - tehát a kívánt FFT kimenet szintje - egy értéke az eggyel feljebb lévő szint két értékétől is függ. Tehát minden szinttel kétszer annyi értéket kell kiszámolni ahhoz, hogy az alsóbb szinten N darab értékünket ki tudjuk számolni.

A könyvben, amiben néztem van egy ábra N=8-hoz az FFT-ről. Itt bejelöltem (ceruzával, halványan kicsi ponttal), hogy miket kell kiszámolni a teljes mátrixból akkor, ha a 8 kimeneti értékből csak 1-re vagyok kiváncsi. Az jött ki, hogy szintenként 1, 2, 4 és 8 értéket kell kiszámolni. Tehát 2 hatvány alapú burkolót lehet tenni rá, az utolsó szinten 1-re, az első szinten pedig mind a 8 értékre szükségünk van.

A 2 hatvány alakú burkoló integrálja kb kétszerese az alappontok számának. Tehát esetünkben kb 16. Ezzel kijött az a zseniális eredmény, hogy egy érték kiszámításához 16 műveletre van szükség - ezt a szummából is leolvashattuk volna :-).

A kérdés az, hogy a teljes táblázat mekkora részét lehet általában megspórolni. Ez lesz az elméleti korlátja a spórolásnak. Két dolgot tudunk:
* 1 értékhez minimum 2*N művelet kell
* N értékhez N*log2N művelet kell
Kérdés, hogy qN (ahol q a fontos sávszélesség aránya a teljeshez képest) érték kiszámításához mennyi művelet fog kelleni. Ehhez érdemes megnézni az N=8/hoz készült ábrát, ami azt sugallja, hogy ha 1 helyett 2 egymás melletti értéket akarunk kiszámolni (másikat halvány x-szel jelölve), akkor szinte minden szinten kétszer annyi értéket kell kiszámolni, alig lesznek újrafelhasználható részeredmények.

Összességében tehát az FFT-n keveset lehet csak spórolni a sávszélesség bekorlátozásával.
De valamennyit lehet, kérdés tényleg megéri-e vacakolni vele.

Szerintem ha belenézel az OpenCV forrásába, és azt érted (ami valószínű, ha írtál saját FFT-t), akkor megpróbálhatod átírni.

Még egyszerűbbnek tűnik viszont az, ha az OpenCV-ben található trükköket (SSE, akármi) egyszerűen csak portolod a te algoritmusodba.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o