Konvoluce

Konvoluce dvou signálů: obdélníkového pulsu a impulsní charakteristika RC článku. Výsledkem konvoluce je odezva RC článku na obdélníkový puls.

Konvoluce je v matematice binární 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)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}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 při zpracovávání obrazu, je funkce $f(x)$ většinou zkoumaný obrázek a funkce $g(x)$ nějaký filtr.

Vlastnosti konvoluce

Konvoluce má následující vlastnosti:

• komutativita:

$f*g=g*f$

• asociativita:

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

• distributivita:

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

• existence jednotky:

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

kde $\delta$ je Diracova delta funkce (distribuce) (představující např. pulz jednotkové velikosti trvající nekonečně krátkou dobu):

$\delta (x)=\{\begin{array}{cc}0& x\ne 0\\ \mathrm{\infty }& x=0\end{array},\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\delta (x)\mathrm{d}x=1$

• asociativita při násobení skalárem:

$a(f*g)=(af)*g=f*(ag)\mathrm{\forall }a\in ℝ$

Konvoluční teorém

Konvoluční teorém říká, že Fourierova transformace konvoluce dvou funkcí odpovídá součinu jejich Fourierových transformací:

$ℱ(f*g)=[ℱ(f)]\cdot [ℱ(g)]=F\cdot G,$

kde $ℱ(f)$ značí Fourierovu transformaci $f$:

$ℱ[f(x)]\equiv F(k)\equiv \underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)\exp (-2\pi ikx)\mathrm{d}x.$

Důkaz lze provést následovně:

$h(z)\equiv (f*g)(z)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)g(z-x)\mathrm{d}x$

$\begin{array}{cc}H(k)& \equiv ℱ[h](k)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}h(z)\exp (-2\pi ikz)\mathrm{d}z=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}[\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)g(z-x)dx]\exp (-2\pi ikz)\mathrm{d}z\\ & =\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)[\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}g(z-x)\exp (-2\pi ikz)\mathrm{d}z]\mathrm{d}x\end{array}$

Zavedeme substituci $y=z-x$ a tedy $\mathrm{d}y=\mathrm{d}z$:

$\begin{array}{cc}H(k)& =\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)[\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}g(y)\exp (-2\pi ik(y+x))\mathrm{d}y]\mathrm{d}x\\ & =\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(x)\exp (-2\pi ikx)\mathrm{d}x\cdot \underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}g(y)\exp (-2\pi iky)\mathrm{d}y=F(k)\cdot G(k)\end{array}$

Diskrétní konvoluce

Diskrétní konvoluce dvou nekonečných řad je definována vztahem

$(f*g{)}_k\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}{f}_i\cdot g_{k-i}=\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}{f}_{k-i}\cdot g_i$

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

Příklad

Příklad konvoluce čtyřprvkové a tříprvkové řady:

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

Příklad s konkrétními hodnotami:

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

Alternativně můžeme konvoluci zapsat pomocí maticového násobení:

$\left[\begin{array}{cccc}a& b& c& d\end{array}\right]*\left[\begin{array}{ccc}e& f& g\end{array}\right]=\left[\begin{array}{cccc}a& b& c& d\end{array}\right]\left[\begin{array}{cccccc}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{array}\right]$

Konkrétní hodnoty:

$\left[\begin{array}{cccc}1& 2& -2& -1\end{array}\right]*\left[\begin{array}{ccc}1& -1& 2\end{array}\right]=\left[\begin{array}{cccc}1& 2& -2& -1\end{array}\right]\left[\begin{array}{cccccc}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{array}\right]=\left[\begin{array}{cccccc}1& 1& -2& 5& -3& -2\end{array}\right]$

Využití v počítačové grafice

Konvoluce se často používá v 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 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

• Šablona:Commonscat