Konvoliucija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Matematikoje konvoliucija yra matematinis operatorius, kuris kaip argumentus paima dvi funkcijas "f" ir "g" ir grąžina trečią, kuri, tam tikra prasme, parodo "f" ir "g" persidengimo kiekį.

Dažniausiai viena funkcija imama kaip fiksuotas filtras, dar vadinamas branduoliu (angl. kernel).

Konvoliucija. Abi funkcijas paverčiame \tau kintamojo funkcijomis. Apverčiame vieną iš funkcijų ir pridedame "t", kad ji galėtų judėti \tau ašimi keičiant "t". Imame "t" lygų minus begalybei ir judame link plius begalybės. Kur funcijos susikerta, surandame jų sandaugos integralą. Taip gaunama nauja funkcija nuo parametro "t" ir yra duotų dviejų funkcijų konvoliucija (čia neparodyta)

Apibrėžimas[taisyti | redaguoti kodą]

f\, ir g\, funkcijų konvoliucija žymima f * g \,. Ji apibrėžiama kaip funkcijų sandaugos integralas, po to, kai viena jų buvo paversta ir padauginta iš -1. Taigi, konvoliucija yra integralinės transformacijos rūšis:

(f  * g )(t) = \int_{a}^{b} f(\tau) g(t - \tau)\, d\tau

Integravimo rėžiai priklauso nuo funkcijų apibrėžimo srities. Dažniausiai a = -∞ ir b = +∞. Integravimo baigtiniame intervale atveju, f\, ir g\, dažnai išplečiamos periodiškai abiejomis kryptimis, kad reiškinyje \displaystyle g(t-\tau) g\, argumentas visada priklausytų apibrėžimo sričiai. Toks periodinis sričių panaudojimas kartais vadinamas cikline arba periodine konvoliucija. Kai apibrėžimo sritis išplečiama, imant funkcijos reikšmes naujuose taškuose lygius 0, konvoliucija vadinama tiesine.

Diskreti konvoliucija[taisyti | redaguoti kodą]

Diskrečioms funkcijoms galime apibrėžti diskrečią konvoliucijos operaciją:

(f  * g)(m) = \sum_n {f(n) g(m - n)} \,

Naudojant pastarąją formulę konvoliucijos sudėtingumas yra lygus O(N²) aritmetinių operacijų "N" taškams. Tačiau šis dydis gali būti sumažintas iki O(N log N), panaudojant greitesnius algoritmus.

Greiti konvoliucijos algoritmai[taisyti | redaguoti kodą]

Praktikoje, skaitmeniniame signalų apdorojime, ir kituose uždaviniuose, kuriuose naudojama diskrečioji konvoliucija, paprastai naudojami greitesni konvoliucijos skaičiavimo algoritmai, sumažinantys sudėtingumą iki O(N log N).

Plačiausiai taikomas greitosios konvoliucijos algoritmas naudoja greitosios Furjė transformacijos algoritmą (angl. FFT) konvoliucijos teoremos pagalba: randama ciklinė konvoliucija imant FFT kiekvienos sekos atskirai, dauginama pataškiui, ir tada atliekama atvirkštinė FFT. Neciklinės konvoliucijos gali būti paskaičiuotos naudojant nulinį išplėtimą.

Žinoma, yra ir kitokių greitosios konvoliucijos algoritmų, nenaudojančių FFT kaipo tokios, kaip, pavyzdžiui, skaičių teorijos transformacijos algoritmai.

Savybės[taisyti | redaguoti kodą]

Komutatyvumas[taisyti | redaguoti kodą]

f * g = g * f  \,

Asociatyvumas[taisyti | redaguoti kodą]

f  * (g  * h) = (f  * g)  * h \,

Distributyvumas[taisyti | redaguoti kodą]

f  * (g + h) = (f  * g) + (f  * h) \,

Vienietinis elementas[taisyti | redaguoti kodą]

f * \delta = \delta * f = f \,

kur δ žymi δ funkciją.

Daugybos su skaliaru asociatyvumas[taisyti | redaguoti kodą]

a (f  * g) = (a f)  * g = f  * (a g) \,

kiekvienam realiam (arba kompleksiniam) a\,.

Diferencijavimo taisyklė[taisyti | redaguoti kodą]

\mathcal{D}(f  * g) = \mathcal{D}f  * g = f  * \mathcal{D}g \,

kur \mathcal{D}f žymi f išvestinę, arba, diskrečiu atveju, skirtumo operatorių \mathcal{D}f(n) = f(n+1) - f(n). Rezultate į konvoliuciją galima žiūrėti kaip į išlyginimo operaciją: "f" ir "g" konvoliucija diferencijuojama tiek kartų, kiek daugiausia diferencijuojama viena iš jų.

Konvoliucijos teorema[taisyti | redaguoti kodą]

Konvoliucijos teorema sako:

 \mathcal{F}(f  * g) = k \left[\mathcal{F} (f)\right] \cdot \left[\mathcal{F} (g)\right]

kur  \mathcal{F}(f)\, žymi f Furjė transformaciją, o k – konstantą, priklausančią nuo specifinės Furjė transformacijos normalizacijos (pvz., k=1, jeigu \mathcal{F}\left[f(x)\right]\equiv\int^\infty_{-\infty}f(x)\exp(\pm 2 \pi i x \xi)dx).

Taikymai[taisyti | redaguoti kodą]

Konvoliucija ir panašios operacijos dažnai sutinkamos daugumoje inžinerijos ir matematikos uždavinių..

  • Optikoje daugybė suliejimų aprašoma konvoliucijomis. Šešėlis (pvz., rankos šešėlis ant stalo, kai ranka yra tarp stalo ir šviesos šaltinio) yra konvoliucija daikto formos, kuris meta šešėlį, ir objekto, kuris skleidžia šviesą.
  • Skaitmeniniame vaizdų apdorojime konvoliucinis filtravimas vaidina svarbų vaidmenį daugybėje kontūrų atpažinimo ir panašiuose algoritmuose.
  • Tiesinėje akustikoje, aidas yra tikrojo garso ir funkcijos, aprašančios, kaip garsas toje aplinkoje atspindimas daiktų, konvoliucija.
  • Skaitmeniniame signalų apdorojime dažninis filtravimas gali būti supaprastintas iki dviejų funkcijų konvoliucijos (duomenų ir filtro), kas bus analogiška duomenų ir filtro dauginimui dažnių erdvėje.

Nuorodos[taisyti | redaguoti kodą]