Nyquistův–Shannonův vzorkovací teorém

Možná hledáte: Shannonova expanze.

Nyquistův–Shannonův vzorkovací teorém (také Shannonův teorém, Nyquistův teorém, Kotělnikovův teorém, Nyquistův–Shannonův teorém, Shannonův–Nyquistův–Kotělnikovův teorém apod.) je fyzikální tvrzení o tom, že „přesná rekonstrukce spojitého, frekvenčně omezeného signálu z jeho vzorků je možná tehdy, pokud byla vzorkovací frekvence vyšší než dvojnásobek nejvyšší harmonické složky vzorkovaného signálu.“

Teorém je pojmenovaný po fyzicích Harrym Nyquistovi (1889–1976), Claudovi Shannonovi (1916–2001) a Vladimiru Kotělnikovovi (1908–2005).

Shannonův teorém a vzorkovací frekvence v praxi

V praxi se tedy vzorkovací frekvence volí dvakrát větší plus ještě malá rezerva, než je maximální požadovaná přenášená frekvence. V telekomunikacích je to např. 8 kHz, neboť je třeba přenášet pouze signály ve standardním telefonním pásmu (od 0,3 do 3,4 kHz – zaokrouhleno směrem nahoru 4 kHz). Například u záznamu na CD je to 44,1 kHz, neboť průměrné zdravé lidské ucho slyší maximálně cca do 20 kHz, a tudíž vzorkovací frekvence 44,1 kHz byla zvolena s určitou rezervou.

Shannonův teorém lze vyjádřit vztahem

f v z > 2 f max [ s − 1 ] , {\displaystyle f_{\rm {vz}}>2f_{\max }[s^{-1}],}

kde f v z {\displaystyle f_{\rm {vz}}} je frekvence vzorkování, f max {\displaystyle f_{\max }} je maximální frekvence, která se vyskytuje v signálu.

Při použití nižší vzorkovací frekvence může dojít k tzv. aliasingu – rekonstruovaný signál je výrazně odlišný od původního vzorkovaného signálu.

Shannonův teorém pro vzorkování obrazu

Nechť f ( x , y ) {\displaystyle f(x,y)} je spojitá funkce obrazu. Vzorkováním funkce f ( x , y ) {\displaystyle f(x,y)} rozumíme reprezentaci této funkce pomocí matice (označme ji d ( x , y ) {\displaystyle d(x,y)} ).

Dále definujme konvoluci dvou funkcí f ( x ) , g ( x ) ∈ L 1 {\displaystyle f(x),g(x)\in L^{1}} jako

f ( x ) ∗ g ( x ) = ∫ − ∞ ∞ f ( t ) g ( x − t ) d t . {\displaystyle f(x)*g(x)=\int _{-\infty }^{\infty }f(t)g(x-t)\,{\rm {d}}t.}

Označme F ( u , v ) {\displaystyle F(u,v)} jako Fourierovu transformaci funkce f ( x , y ) {\displaystyle f(x,y)} .

Definujme ještě tzv. delta funkci δ {\displaystyle \delta } , pro kterou platí:

δ ( x ) = 0 ⇔ x ≠ 0 , {\displaystyle \delta (x)=0\Leftrightarrow x\neq 0,}
δ ( x ) = ? ⇔ x = 0 , {\displaystyle \delta (x)=?\Leftrightarrow x=0,}
∫ − ∞ ∞ δ ( x ) d x = 1. {\displaystyle \int _{-\infty }^{\infty }\delta (x)\,{\rm {d}}x=1.}

Pak vzorkování s krokem Δ x , Δ y {\displaystyle \Delta x,\Delta y} je pouze násobení funkce obrazu nekonečným polem delta funkcí s ( x , y ) {\displaystyle s(x,y)} definovaným jako

s ( x , y ) = ∑ i = − ∞ ∞ ∑ j = − ∞ ∞ δ ( x − i Δ x , y − j Δ y ) . {\displaystyle s(x,y)=\sum _{i=-\infty }^{\infty }\sum _{j=-\infty }^{\infty }\delta \left(x-i\Delta x,y-j\Delta y\right).}

Tedy d ( x , y ) = f ( x , y ) s ( x , y ) {\displaystyle d(x,y)=f(x,y)\,\,s(x,y)} .

Platí, že Fourieova transformace funkce s ( x , y ) {\displaystyle s(x,y)} má tvar

S ( u , v ) = 1 Δ x Δ y ∑ i = − ∞ ∞ ∑ j = − ∞ ∞ δ ( u − i Δ x , v − j Δ y ) . {\displaystyle S(u,v)={\frac {1}{\Delta x\Delta y}}\sum _{i=-\infty }^{\infty }\sum _{j=-\infty }^{\infty }\delta \left(u-{\frac {i}{\Delta x}},v-{\frac {j}{\Delta y}}\right).}

Díky konvolučnímu teorému, který říká

F { f ( x ) ∗ g ( x ) } = F { f ( x ) } ⋅ F { g ( x ) } = F ( u ) ⋅ G ( u ) , {\displaystyle {\mathcal {F}}\{f(x)\ast g(x)\}={\mathcal {F}}\{f(x)\}\cdot {\mathcal {F}}\{g(x)\}\,=F(u)\cdot G(u),\,}
F { f ( x ) ⋅ g ( x ) } = F { f ( x ) } ∗ F { g ( x ) } = F ( u ) ∗ G ( u ) , {\displaystyle {\mathcal {F}}\{f(x)\cdot g(x)\}={\mathcal {F}}\{f(x)\}\ast {\mathcal {F}}\{g(x)\}\,=F(u)\ast G(u),\,}

platí, že

D ( u , v ) = F ( u , v ) ∗ S ( u , v ) . {\displaystyle D(u,v)=F(u,v)*S(u,v).\,}

Fourierův obraz vzorkované funkce f ⋅ s {\displaystyle f\cdot s} je pak konvoluce Fourierova obrazu F {\displaystyle F} funkce f {\displaystyle f} s polem delta funkcí S {\displaystyle S} . To znamená, že D ( u , v ) {\displaystyle D(u,v)} je nekonečné pole Fourierových obrazů funkce f {\displaystyle f} . Při vzorkování s menším krokem se tyto obrazy od sebe vzdalují a naopak při vzorkování s delším krokem se k sobě přibližují. Pokud vzorkujeme příliš řídce, mohou se tyto obrazy protnout a vzniká efekt zvaný aliasing. Pokud je funkce frekvenčně omezená, je možné ji navzorkovat beze ztráty informace (tzn. že je možné ze vzorků opět získat funkci f {\displaystyle f} v původní podobě).

Dle Shannonova teorému je pak ideální frekvence pro vzorkování rovna dvojnásobku maximální frekvence vyskytující se ve funkci f {\displaystyle f} . Při vzorkování s krokem menším, než je polovina maximální frekvence, vzorkuji zbytečně moc. Při kroku větším než polovina maximální frekvence se Fourierovy obrazy protnou a vzniká aliasing.

Odkazy

Související články

Externí odkazy