Konvoluce

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)$$f(x)$ a $g(x)$$g(x)$ je definována vztahem:

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

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

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

Vlastnosti konvoluce

Komutativní

$f*g=g*f\,$$f*g=g*f\,$

Asociativní

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

Distributivní

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

Existence jednotky

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

kde δ je tzv. Diracova delta funkce:

$\delta (x)=0,x\neq 0$$\delta (x)=0,x\neq 0$

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

$\int _{-\infty }^{\infty }\delta (x)\,\mathrm {d} x=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

$a(f*g)=(af)*g=f*(ag)\,$$a(f*g)=(af)*g=f*(ag)\,$

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

Konvoluční teorém

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

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

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

Dk.:

$F(k)=\int _{-\infty }^{\infty }f(x)\exp(-2\pi ikx)\,\mathrm {d} x$$F(k)=\int _{{-\infty }}^{\infty }f(x)\exp(-2\pi ikx)\,{\mathrm {d}}x$

$G(k)=\int _{-\infty }^{\infty }g(x)\exp(-2\pi ikx)\,\mathrm {d} x$$G(k)=\int _{{-\infty }}^{\infty }g(x)\exp(-2\pi ikx)\,{\mathrm {d}}x$

$h(z)=\int _{-\infty }^{\infty }f(x)g(z-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 ikz)\,\mathrm {d} z=\int _{-\infty }^{\infty }\left[\int _{-\infty }^{\infty }f(x)g(z-x)dx\right]\exp(-2\pi ikz)\,\mathrm {d} z=$$H(k)=\int _{{-\infty }}^{\infty }h(z)\exp(-2\pi ikz)\,{\mathrm {d}}z=\int _{{-\infty }}^{\infty }\left[\int _{{-\infty }}^{\infty }f(x)g(z-x)dx\right]\exp(-2\pi ikz)\,{\mathrm {d}}z=$

$=\int _{-\infty }^{\infty }f(x)\left[\int _{-\infty }^{\infty }g(z-x)\exp(-2\pi ikz)\,\mathrm {d} z\right]\mathrm {d} x=$$=\int _{{-\infty }}^{\infty }f(x)\left[\int _{{-\infty }}^{\infty }g(z-x)\exp(-2\pi ikz)\,{\mathrm {d}}z\right]{\mathrm {d}}x=$

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

$=\int _{-\infty }^{\infty }f(x)\left[\int _{-\infty }^{\infty }g(y)\exp(-2\pi ik(y+x))\,\mathrm {d} y\right]\mathrm {d} x=$$=\int _{{-\infty }}^{\infty }f(x)\left[\int _{{-\infty }}^{\infty }g(y)\exp(-2\pi ik(y+x))\,{\mathrm {d}}y\right]{\mathrm {d}}x=$

$=\int _{-\infty }^{\infty }f(x)\exp(-2\pi ikx)\,\mathrm {d} x\cdot \int _{-\infty }^{\infty }g(y)\exp(-2\pi iky)\,\mathrm {d} y=F(k)\cdot G(k)$$=\int _{{-\infty }}^{\infty }f(x)\exp(-2\pi ikx)\,{\mathrm {d}}x\cdot \int _{{-\infty }}^{\infty }g(y)\exp(-2\pi iky)\,{\mathrm {d}}y=F(k)\cdot G(k)$

Diskrétní konvoluce

$(f*g)_{k}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{i=-\infty }^{\infty }f_{i}\cdot g_{k-i}$$(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}$$=\sum _{{i=-\infty }}^{{\infty }}f_{{k-i}}\cdot g_{i}$

Příklad

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}}$${\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}}$${\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

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)$$(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).

Externí odkazy

• Obrázky, zvuky či videa k tématu konvoluce ve Wikimedia Commons