Konvoluce

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Konvoluce dvou signálů: obdélníkového pulsu a impulsní charakteristika RC článku. Výsledek je stejný jako odezva RC článku na stejný puls.

Konvoluce je matematický operátor zpracovávající dvě funkce.

Spojitá konvoluce (značí se hvězdičkou) jednorozměrných funkcí f(x) a g(x) je definována vztahem:

(f*g)(x) = \int_{-\infty}^{\infty} f( \alpha) g(x- \alpha) \, \mathrm{d} \alpha

Funkci g(x) se říká konvoluční jádro. Hodnota konvoluce funkce f s jádrem g v bodě x je integrál ze součinu funkce f s otočenou funkcí konvolučního jádra (integrační proměnná \alpha má v argumentu konvolučního jádra g(x-\alpha) záporné znaménko) posunutou do bodu x.

Pokud jde o konvoluci v Image Processing (zpracovávání obrazu) je funkce f(x) většinou zkoumaný obrázek a funkce g(x) nějaký filtr.

Vlastnosti konvoluce[editovat | editovat zdroj]

Komutativní[editovat | editovat zdroj]

f * g = g * f  \,

Asociativní[editovat | editovat zdroj]

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

Distributivní[editovat | editovat zdroj]

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

Existence jednotky[editovat | editovat zdroj]

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

kde δ je tzv. Diracova delta funkce:

\delta(x) = 0  , x \ne 0

a \lim_{x \to 0}\delta(x)=\infty. Integrál Delta funkce je roven 1:

\int_{-\infty}^\infty \delta(x) \,\mathrm{d}x = 1.

Jde tedy o puls trvající nekonečně krátkou dobu.

Asociativita při násobení skalárem[editovat | editovat zdroj]

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

pro všechna reálná (nebo komplexní) čísla a.

Konvoluční teorém[editovat | editovat zdroj]

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

kde  \mathcal{F}(f)\, značí Fourierovu transformaci f \,

 \mathcal{F}\left[f(x)\right]\equiv F(k) \equiv\int^\infty_{-\infty}f(x)\exp(-2 \pi i k x)\,\mathrm{d}x

Dk.:

F(k) = \int^\infty_{-\infty}f(x)\exp(-2 \pi i k x)\,\mathrm{d}x
G(k) = \int^\infty_{-\infty}g(x)\exp(-2 \pi i k x)\,\mathrm{d}x
h(z) = \int_{-\infty}^{\infty} f(x) g(z- x) \,\mathrm{d}x
H(k) = \int^\infty_{-\infty}h(z)\exp(-2 \pi i k z)\,\mathrm{d}z = \int^\infty_{-\infty}\left[\int^\infty_{-\infty}f(x) g(z- x)dx\right]\exp(-2 \pi i k z)\,\mathrm{d}z =
= \int^\infty_{-\infty}f(x)\left[\int^\infty_{-\infty} g(z- x)\exp(-2 \pi i k z) \,\mathrm{d}z \right] \mathrm{d}x =

substituce: y=z-x\, a tedy \mathrm{d}y=\mathrm{d}z\,

= \int^\infty_{-\infty}f(x)\left[\int^\infty_{-\infty}g(y)\exp(-2 \pi i k (y+x))\,\mathrm{d}y \right] \mathrm{d}x =
= \int^\infty_{-\infty}f(x)\exp(-2 \pi i k x)\,\mathrm{d}x\cdot\int^\infty_{-\infty}g(y)\exp(-2 \pi i k y)\,\mathrm{d}y = F(k)\cdot G(k)

Diskrétní konvoluce[editovat | editovat zdroj]

(f * g)_k\ \stackrel{\mathrm{def}}{=}\ \sum_{i=-\infty}^{\infty} f_i \cdot g_{k - i}
= \sum_{i=-\infty}^{\infty} f_{k-i} \cdot g_i

Příklad[editovat | editovat zdroj]

V případě dvou konečných řad se samozřejmě nesčítá od −∞ do +∞, ale pouze přes existující prvky. (Případně si lze na pozici neexistujících prvků řady představit nuly.) Výsledná řada je o jeden prvek kratší než je součet délek konvoluovaných řad.

Konvoluce dvou řad:

(a, b, c, d) * (e, f, g) =
= (a*e) (a*f) (a*g)
        (b*e) (b*f) (b*g)
              (c*e) (c*f) (c*g) 
                    (d*e) (d*f) (d*g)
  -----------------------------------
  následuje sečtení pod sebou

Výsledek je stejný, jakoby se jednalo o součin dvou polynomů. (Koeficienty násobených polynomů by představovaly dvě konvoluované řady, koeficienty součinu polynomů by odpovídaly výsledku konvoluce.)

Konkrétní čísla:

(1, 2, -2, -1) * (1, -1, 2) =
= 1 -1  2
     2 -2  4
       -2  2 -4
          -1  1 -2
 ------------------
 (1, 1,-2, 5,-3,-2)

Jinou možností výpočtu je použití maticového násobení.

\begin{bmatrix}a & b & c & d\end{bmatrix} * \begin{bmatrix}e & f & g\end{bmatrix} = \begin{bmatrix}a & b & c & d\end{bmatrix} \begin{bmatrix}e & f & g & 0 & 0 & 0 \\ 0 & e & f & g & 0 & 0 \\ 0 & 0 & e & f & g & 0 \\ 0 & 0 & 0 & e & f & g\end{bmatrix}

Konkrétní čísla:

\begin{bmatrix}1 & 2 & -2 & -1\end{bmatrix} * \begin{bmatrix}1 & -1 & 2\end{bmatrix} = \begin{bmatrix}1 & 2 & -2 & -1\end{bmatrix} \begin{bmatrix}1 & -1 & 2 & 0 & 0 & 0 \\ 0 & 1 & -1 & 2 & 0 & 0 \\ 0 & 0 & 1 & -1 & 2 & 0 \\ 0 & 0 & 0 & 1 & -1 & 2\end{bmatrix} = \begin{bmatrix}1 & 1 & -2 & 5 & -3 & -2\end{bmatrix}

Využití v počítačové grafice[editovat | editovat zdroj]

Konvoluce se často používá při algoritmech zpracování dvourozměrného diskrétního obrazu v počítačové grafice. Vzorec diskrétní konvoluce má potom tvar:

(f*h)(x,y) = \sum_{i=-k}^k  \sum_{j=-k}^k  f(x-i,y-j) \cdot h(i,j)

Princip diskrétní dvourozměrné konvoluce

V případě diskrétní konvoluce lze jádro chápat jako tabulku (konvoluční maska), kterou položíme na příslušné místo obrazu. Každý pixel překrytý tabulkou vynásobíme koeficientem v příslušné buňce a provedeme součet všech těchto hodnot. Tím dostaneme jeden nový pixel.

Například mějme konvoluční masku o rozměru 3×3 (bude překryto 9 pixelů) a všechny buňky mají koeficient 0,111 (1/9). Nový pixel, který vypočteme po aplikaci na jedno místo v původním obraze, tedy bude průměrem z devíti okolních pixelů. Neudělali jsme totiž nic jiného, než že jsme sečetli hodnoty 9 pixelů a vydělili 9. Pokud aplikujeme konvoluci na celý obraz, pak dostaneme rozostřený obraz. Pokud použijeme větší konvoluční masku 5×5 s koeficienty 1/25, pak bude obraz rozostřen více.

Koeficienty uvnitř konvoluční masky udávají vliv hodnoty pixelu pod nimi. Lze tak nadefinovat velké množství operací, např. derivace obrazu (u diskrétního obrazu mluvíme o tzv. odhadu derivace), tedy zvýraznění hran (viz detekce hran).

Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Konvoluce ve Wikimedia Commons