Shannonův teorém

Z Wikipedie, otevřené encyklopedie

Shannonův teorém (Nyquistův teorém, Nyquistův-Shannonův teorém, Shannonův-Nyquistův-Kotělnikův teorém, apod.)

„Přesná rekonstrukce spojitého, frekvenčně omezeného, signálu z jeho vzorků je možná tehdy, pokud byl vzorkován frekvencí alespoň dvakrát vyšší než je maximální frekvence rekonstruovaného signálu.“

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

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

Dále definujme konvoluci dvou funkcí f(x),g(x)∈L₁ jako

$f(x)*g(x) = \int f(t)g(x-t)dt$

Označme F(u,v) jako fourierovu transformaci funkce f(x,y).

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

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

$\delta(x) = ? \Leftrightarrow x=0$

$\int_{-\infty}^{\infty}\delta(x) = 1$

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

$s(x,y) = \sum_{i=-\infty}^{\infty}\sum_{j=-\infty}^{\infty} \delta(x-i\Delta x, y-j\Delta y)$

Tedy: d(x,y) = f(x,y)s(x,y)

Platí, že fourieova transformace funkce s(x,y) má tvar,

$S(u,v) = \frac{1}{\Delta x \Delta y}\sum_{i=-\infty}^{\infty}\sum_{j=-\infty}^{\infty} \delta(u-\frac{i}{\Delta x}, v-\frac{j}{\Delta y})$

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

f (x) * g (x) = F (u) G (u)

f (x) g (x) = F (u) * G (u)

platí, že

D (u, v) = F (u, v) * S (u, v)

Vzorkování je pak konvoluce fourierova obrazu F funkce f s polem delta funkcí D. To znamená, že D(u,v) je nekonečné pole fourierových obrazů funkce 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 v původní podobě).

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