Vícedimenzionální vzorkování - Multidimensional sampling

V digitálním zpracování signálu je multidimenzionální vzorkování proces převodu funkce vícerozměrné proměnné na diskrétní soubor hodnot funkce měřené na diskrétní sadě bodů. Tento článek představuje základní vyústit v důsledku Petersen a Middleton o podmínkách perfektně rekonstrukci vlnovém čísle -limited funkci ze svých měření na diskrétní mřížce bodů. Tento výsledek, známý také jako Petersen – Middletonova věta , je zobecněním Nyquist – Shannonovy věty o vzorkování pro vzorkování jednorozměrných funkcí s omezeným pásmem do vícerozměrných euklidovských prostorů .

V podstatě Petersen – Middletonova věta ukazuje, že funkce omezená vlnovým číslem může být dokonale rekonstruována z jejích hodnot na nekonečné mřížce bodů za předpokladu, že mřížka je dostatečně jemná. Věta poskytuje podmínky na mřížce, za kterých je možná dokonalá rekonstrukce.

Stejně jako u Nyquist-Shannonovy věty o vzorkování, i tato věta předpokládá idealizaci jakékoli situace v reálném světě, protože se vztahuje pouze na funkce, které jsou vzorkovány přes nekonečno bodů. Pro idealizovaný model je matematicky možná dokonalá rekonstrukce, ale pouze aproximace funkcí a technik vzorkování v reálném světě, i když v praxi často velmi dobrá.

Předkola

Obr. 1: Šestihranná vzorkovací mřížka a její základní vektory v ₁ a v ₂${\ displaystyle \ Lambda}$

Obr. 2: Reciproční mřížka odpovídající mřížce z obr. 1 a její základní vektory u ₁ a u ₂ (obrázek není v měřítku). ${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda}$

Koncept funkce s omezeným pásmem v jedné dimenzi lze zobecnit na představu funkce omezené vlnovým číslem ve vyšších dimenzích. Připomeňme, že Fourierova transformace integrovatelné funkce v n -dimenzionálním euklidovském prostoru je definována jako: ${\ displaystyle f (\ cdot)}$

${\ displaystyle {\ hat {f}} (\ xi) = {\ mathcal {F}} (f) (\ xi) = \ int _ {\ Re ^ {n}} f (x) e ^ {- 2 \ pi i \ langle x, \ xi \ rangle} \, dx}$

kde x a ξ jsou n -dimenzionální vektory a je vnitřním součinem vektorů. Funkce se říká, že vlnočet omezené na sadu v případě, že Fourierova transformace splňuje pro . ${\ displaystyle \ langle x, \ xi \ rangle}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} (\ xi) = 0}$${\ displaystyle \ xi \ notin \ Omega}$

Podobně lze zobecnit konfiguraci rovnoměrně rozmístěných vzorkovacích bodů v jednorozměru na mřížku ve vyšších rozměrech. Mřížkový je kolekce bodů ve formě: kde { v ₁ , ..., v _n } je základem pro . Reciproká mřížka odpovídající je definován ${\ displaystyle \ Lambda \ podmnožina \ Re ^ {n}}$${\ displaystyle \ Lambda = \ left \ {\ sum _ {i = 1} ^ {n} a_ {i} v_ {i} \; | \; a_ {i} \ in \ mathbb {Z} \ vpravo \} }$${\ displaystyle \ Re ^ {n}}$ ${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda}$

${\ displaystyle \ Gamma = \ left \ {\ sum _ {i = 1} ^ {n} a_ {i} u_ {i} \; | \; a_ {i} \ in \ mathbb {Z} \ vpravo \} }$

kde vektory jsou vybrány tak, aby vyhovovaly . To znamená, že pokud vektory tvoří sloupce matice a sloupce matice , pak . Příkladem vzorkovací mřížky ve dvourozměrném prostoru je šestihranná mříž zobrazená na obrázku 1. Odpovídající vzájemná mřížka je zobrazena na obrázku 2. Vzájemná mřížka čtvercové mřížky ve dvou rozměrech je další čtvercová mřížka. V trojrozměrném prostoru je vzájemná mřížka kubické (FCC) mřížky orientované na obličej kubická (BCC) mřížka zaměřená na tělo. ${\ displaystyle u_ {i}}$${\ displaystyle \ langle u_ {i}, v_ {j} \ rangle = \ delta _ {ij}}$${\ displaystyle u_ {i}}$${\ displaystyle A}$${\ displaystyle v_ {i}}$${\ displaystyle B}$${\ displaystyle A = B ^ {- T}}$

Věta

Nechť znamenají mříži a odpovídající reciproká mřížka. Věta Petersena a Middletona uvádí, že funkce omezená na vlnový počet na množinu může být přesně rekonstruována z jejích měření za předpokladu, že množina se nepřekrývá s žádnou z jejích posunutých verzí, kde posun x je jakýkoli nenulový prvek vzájemnosti mříž . Jinými slovy, může být přesně rekonstruován z jeho měření za předpokladu, že pro všechny . ${\ displaystyle \ Lambda}$${\ displaystyle \ Re ^ {n}}$${\ displaystyle \ Gamma}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Omega \ podmnožina \ Re ^ {n}}$${\ displaystyle \ Lambda}$${\ displaystyle \ Omega}$${\ displaystyle \ Omega + x}$${\ displaystyle \ Gamma}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Lambda}$${\ displaystyle \ Omega \ cap \ {x + y: y \ in \ Omega \} = \ emptyset}$${\ displaystyle x \ in \ Gamma \ setminus \ {0 \}}$

Rekonstrukce

Obr. 3: Podpora vzorkovaného spektra získaného hexagonálním vzorkováním dvourozměrné funkce vlnového čísla omezené na kruhový disk. Modrý kruh představuje podporu původního pole omezeného vlnovým číslem a zelené kruhy představují opakování. V tomto příkladu se spektrální opakování nepřekrývají, a proto neexistuje aliasing. Původní spektrum lze přesně obnovit ze vzorkovaného spektra. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Zobecnění Poissonova součtového vzorce na vyšší dimenze lze použít k ukázání, že vzorky funkce mřížky jsou dostatečné k vytvoření periodického součtu funkce . Výsledek je: ${\ displaystyle \ {f (x): x \ v \ Lambda \}}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Lambda}$${\ displaystyle {\ hat {f}} (\ cdot)}$

${\ displaystyle {\ hat {f}} _ {s} (\ xi) \ {\ stackrel {\ mathrm {def}} {=}} \ součet _ {y \ in \ Gamma} {\ hat {f}} \ left (\ xi -y \ right) = \ sum _ {x \ in \ Lambda} | \ Lambda | f (x) \ e ^ {- i2 \ pi \ langle x, \ xi \ rangle},}$

( Rov. 1 )

kde představuje objem rovnoběžnostěnu tvořeného vektory { v ₁ , ..., v _n }. Tato periodická funkce se často označuje jako vzorkované spektrum a lze ji interpretovat jako analog Fourierovy transformace (DTFT) ve vyšších dimenzích. Pokud je na množině podporováno původní spektrum omezené vlnovým číslem, je funkce podporována na periodických opakováních posunutých o body na vzájemné mřížce . Pokud jsou splněny podmínky Petersen-Middletonovy věty, pak je funkce pro všechny stejná , a proto lze původní pole ze vzorků přesně rekonstruovat. V tomto případě se rekonstruované pole shoduje s původním polem a lze jej vyjádřit jako vzorky jako ${\ displaystyle | \ Lambda |}$${\ displaystyle {\ hat {f}} (\ cdot)}$${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$${\ displaystyle \ Gamma}$${\ displaystyle {\ hat {f}} _ {s} (\ xi)}$${\ displaystyle {\ hat {f}} (\ xi)}$${\ displaystyle \ xi \ v \ Omega}$

${\ displaystyle f (x) = \ součet _ {y \ in \ Lambda} | \ Lambda | f (y) {\ check {\ chi}} _ {\ Omega} (yx)}$ ,

( Rov. 2 )

kde je inverzní Fourierova transformace charakteristické funkce množiny . Tento interpolační vzorec je vyšším dimenzionálním ekvivalentem Whittaker-Shannonova interpolačního vzorce . ${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$${\ displaystyle \ Omega}$

Jako příklad předpokládejme, že se jedná o kruhový disk. Obrázek 3 ukazuje podporu, když jsou splněny podmínky Petersen-Middletonovy věty. Vidíme, že se spektrální opakování nepřekrývají, a proto lze původní spektrum přesně obnovit. ${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$

Důsledky

Aliasing

Obr. 4: Podpora vzorkovaného spektra získaného hexagonálním vzorkováním dvourozměrné funkce vlnového čísla omezené na kruhový disk. V tomto příkladu není vzorkovací mřížka dostatečně jemná, a proto se disky ve vzorkovaném spektru překrývají. Spektrum uvnitř reprezentované modrým kruhem tedy nelze obnovit přesně kvůli překrývání opakování (zobrazeno zeleně), což vede k aliasingu. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Obr. 5: Prostorové aliasing ve formě Moiré vzoru .

Obr.6: Správně vzorkovaný obrázek cihlové zdi.

Věta dává podmínky na mřížkách vzorkování pro dokonalou rekonstrukci vzorkovaných. Pokud mřížky nejsou dostatečně jemné, aby vyhověly podmínce Petersen-Middleton, pak pole nelze obecně rekonstruovat přesně ze vzorků. V tomto případě říkáme, že vzorky mohou být aliasy . Znovu zvažte příklad, ve kterém je kruhový disk. Pokud podmínky Petersen-Middleton nebudou splněny, bude podpora vzorkovaného spektra, jak je znázorněno na obrázku 4. V tomto případě se spektrální opakování překrývají, což vede k aliasingu v rekonstrukci. ${\ displaystyle \ Omega}$

Jednoduchou ilustraci aliasingu lze získat studiem obrázků s nízkým rozlišením. Obrázek v šedé stupnici lze interpretovat jako funkci v dvourozměrném prostoru. Příklad aliasingu je uveden na obrázcích vzorů cihel na obrázku 5. Obrázek ukazuje účinky aliasingu, když není splněna podmínka věty o vzorkování. Pokud mřížka pixelů není pro scénu dostatečně jemná, dojde k aliasingu, o čemž svědčí výskyt vzoru Moiré na získaném obrázku. Obraz na obrázku 6 je získán, když je vzorkovaná vyhlazená verze scény se stejnou mřížkou. V takovém případě jsou podmínky věty splněny a nedojde k aliasingu.

SP Efimov z Moskevské státní technické univerzity Bauman v roce 1978 r. našel přístup ke zmírnění omezení pro oblast spektra. Považoval N identických vzorkovacích mřížek za vzájemně libovolně posunutých. Optimální vzorkování je platné pro doménu spektra, kde posunuté verze N jsou těsně zabalené N krát na reciproční mřížce. Proto může být prsten překryt souborem šestiúhelníků místo jednoho. Pole dalekohledu JWST se skládá z 18 šestiúhelníků. Vzorkování na 18 posunutých mřížkách je možné pro 2-d Fourierovu transformaci signálu pole (tj. Pro emitovaný signál).

Optimální mřížky vzorkování

Jedním z objektů zájmu při navrhování schématu vzorkování pro pole s omezeným počtem vln je identifikovat konfiguraci bodů, která vede k minimální hustotě vzorkování, tj. Hustotě vzorkovacích bodů na jednotku prostorového objemu v . Náklady na provedení a uložení měření jsou obvykle úměrné použité hustotě vzorkování. V praxi je přirozeným přístupem k vzorkování dvourozměrných polí jeho vzorkování v bodech na obdélníkové mřížce . To však není vždy ideální volba, pokud jde o hustotu vzorkování. Věta Petersena a Middletona lze použít k identifikaci optimální mřížky pro vzorkování polí, která jsou omezena vlnovým číslem na danou množinu . Lze například ukázat, že mřížka s minimální prostorovou hustotou bodů, která umožňuje dokonalé rekonstrukce polí s vlnovým číslem omezeným na kruhový disk, je hexagonální mřížka. V důsledku toho jsou pro vzorkování izotropních polí ve formátu preferovány hexagonální mřížky . ${\ displaystyle \ Re ^ {n}}$${\ displaystyle \ Omega \ podmnožina \ Re ^ {d}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$

Optimální mřížky vzorkování byly studovány ve vyšších dimenzích. Optimální mřížky pro balení koule jsou obecně ideální pro vzorkování hladkých stochastických procesů, zatímco optimální mřížky pokrývající koule jsou ideální pro vzorkování drsných stochastických procesů.

Protože optimální mřížky jsou obecně neoddělitelné, návrh interpolačních a rekonstrukčních filtrů vyžaduje mechanismy návrhu filtru bez tenzoru (tj. Neoddělitelné). Krabicové splajny poskytují flexibilní rámec pro navrhování takových neoddělitelných rekonstrukčních filtrů FIR, které lze geometricky přizpůsobit každé mřížce. Hex-splajny jsou zobecněním B-splajnů pro 2-D hexagonální mřížky. Podobně ve 3-D a vyšších dimenzích poskytují Voronoi splajny zobecnění B-splajnů, které lze použít k návrhu neoddělitelných filtrů FIR, které jsou geometricky přizpůsobeny jakékoli mřížce, včetně optimálních mřížek.

Explicitní konstrukce ideálních nízkoprůchodových filtrů (tj. Funkcí sinc ) generalizovaných na optimální mřížky je možná studiem geometrických vlastností Brillouinových zón (tj. Nahoře) těchto mřížek (které jsou zonotopy ). Tento přístup poskytuje uzavřenou formu explicitní reprezentace obecných mřížek, včetně optimálních mřížek vzorkování. Tato konstrukce poskytuje zobecnění Lanczosova filtru v 1-D na vícerozměrné nastavení pro optimální mřížky. ${\ displaystyle \ Omega}$${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$

Aplikace

Petersen – Middletonova věta je užitečná při navrhování účinných strategií umisťování senzorů v aplikacích zahrnujících měření prostorových jevů, jako jsou seismické průzkumy, monitorování prostředí a měření prostorového zvukového pole.

Reference