Flerdimensjonal prøvetaking - Multidimensional sampling

I digital signalbehandling er flerdimensjonal sampling prosessen med å konvertere en funksjon av en flerdimensjonal variabel til en diskret samling av verdier av funksjonen målt på et diskret sett med punkter. Denne artikkelen presenterer det grunnleggende resultatet på grunn av Petersen og Middleton om forhold for perfekt rekonstruering av en bølgetallbegrenset funksjon fra målingene på et diskret gitter av punkter. Dette resultatet, også kjent som Petersen – Middleton-teoremet , er en generalisering av Nyquist – Shannon-prøvetakingssetningen for sampling av endimensjonale båndbegrensede funksjoner til høyere dimensjonale euklidiske rom .

I det vesentlige viser setningen Petersen – Middleton at en funksjon med bølgetallbegrensning perfekt kan rekonstrueres fra sine verdier på et uendelig gitter av punkter, forutsatt at gitteret er fint nok. Teoremet gir forhold på gitteret der perfekt rekonstruksjon er mulig.

Som med Nyquist – Shannon prøvetakingssetningen, antar denne teoremet også en idealisering av enhver situasjon i den virkelige verden, da den bare gjelder funksjoner som samples over en uendelig poeng. Perfekt rekonstruksjon er matematisk mulig for den idealiserte modellen, men bare en tilnærming for virkelige funksjoner og prøvetakingsteknikker, om enn i praksis ofte en veldig god.

Foreløp

Fig. 1: Et sekskantet prøvetakingsgitter og dets basisvektorer v ₁ og v ₂${\ displaystyle \ Lambda}$

Fig. 2: Det gjensidige gitteret tilsvarer gitteret i fig. 1 og dets basisvektorer u ₁ og u ₂ (figur ikke i målestokk). ${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda}$

Konseptet med en båndbegrenset funksjon i en dimensjon kan generaliseres til forestillingen om en bølgetallbegrenset funksjon i høyere dimensjoner. Husk at Fourier-transformasjonen av en integrerbar funksjon på n- dimensjonalt euklidisk rom er definert som: ${\ 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}$

hvor x og ξ er n -dimensjonale vektorer , og er det indre produktet av vektorene. Funksjonen sies å være bølgetallbegrenset til et sett hvis Fourier-transformasjonen tilfredsstiller for . ${\ displaystyle \ langle x, \ xi \ rangle}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} (\ xi) = 0}$${\ displaystyle \ xi \ notin \ Omega}$

Tilsvarende kan konfigurasjonen av jevnt fordelte prøvetakingspunkter i en-dimensjon generaliseres til et gitter i høyere dimensjoner. Et gitter er en samling av punkter i formen der { v ₁ , ..., v _n } er grunnlag for . Det gjensidige gitteret tilsvarer er definert av ${\ displaystyle \ Lambda \ subset \ Re ^ {n}}$${\ displaystyle \ Lambda = \ left \ {\ sum _ {i = 1} ^ {n} a_ {i} v_ {i} \; | \; a_ {i} \ in \ mathbb {Z} \ right \} }$${\ displaystyle \ Re ^ {n}}$ ${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda}$

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

hvor vektorene er valgt å tilfredsstille . Det vil si at hvis vektorene danner kolonner i en matrise og kolonnene i en matrise , da . Et eksempel på et prøvetakningsgitter i todimensjonalt rom er et sekskantet gitter avbildet i figur 1. Det tilsvarende gjensidige gitteret er vist i figur 2. Det gjensidige gitteret til et kvadratgitter i to dimensjoner er et annet kvadratgitter. I et tredimensjonalt rom er det gjensidige gitteret til et ansiktssentrert kubisk (FCC) gitter et kroppssentrert kubisk gitter. ${\ 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}}$

Teoremet

La betegne et gitter i og det tilsvarende gjensidige gitteret. Teoremet til Petersen og Middleton sier at en funksjon som er bølgetallbegrenset til et sett kan rekonstrueres nøyaktig fra målingene, forutsatt at settet ikke overlapper med noen av dets forskyvede versjoner der skiftet x er et ikke-null element i det gjensidige gitter . Med andre ord, kan være nøyaktig rekonstruert fra målingene forutsatt at for alle . ${\ displaystyle \ Lambda}$${\ displaystyle \ Re ^ {n}}$${\ displaystyle \ Gamma}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Omega \ subset \ 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 \}}$

Gjenoppbygging

Fig. 3: Støtte av det utvalgte spekteret oppnådd ved sekskantet prøvetaking av en todimensjonal funksjon bølgetallbegrenset til en sirkulær plate. Den blå sirkelen representerer støtten til det opprinnelige bølgetallbegrensede feltet, og de grønne sirklene representerer repetisjonene. I dette eksemplet overlapper ikke spektrale repetisjoner, og det er derfor ingen aliasing. Det opprinnelige spekteret kan gjenopprettes nøyaktig fra det utvalgte spekteret. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Generaliseringen av Poisson-summeringsformelen til høyere dimensjoner kan brukes til å vise at prøvene,, av funksjonen på gitteret er tilstrekkelig til å skape en periodisk summering av funksjonen . Resultatet er: ${\ displaystyle \ {f (x): x \ in \ Lambda \}}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Lambda}$${\ displaystyle {\ hat {f}} (\ cdot)}$

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

( Likning 1 )

hvor representerer volumet av parallellpipedannelsen dannet av vektorene { v ₁ , ..., v _n }. Denne periodiske funksjonen blir ofte referert til som det samplede spekteret og kan tolkes som analogen til den diskrete Fourier-transformasjonen (DTFT) i høyere dimensjoner. Hvis det opprinnelige bølgetallbegrensede spekteret støttes på settet, støttes funksjonen ved periodiske repetisjoner av forskjøvet av punkter på det gjensidige gitteret . Hvis vilkårene for Petersen-Middleton-teoremet er oppfylt, er funksjonen lik for alle , og dermed kan det originale feltet rekonstrueres nøyaktig fra prøvene. I dette tilfellet samsvarer det rekonstruerte feltet med det opprinnelige feltet og kan uttrykkes i form av prøvene som ${\ 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 \ in \ Omega}$

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

( Lik.2 )

hvor er den inverse Fourier-transformerte av den karakteristiske funksjon av settet . Denne interpolasjonsformelen er den høyere dimensjonale ekvivalenten til Whittaker-Shannon-interpolasjonsformelen . ${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$${\ displaystyle \ Omega}$

Anta at det er en sirkulær plate. Figur 3 illustrerer støtten til når vilkårene for Petersen-Middleton-teoremet er oppfylt. Vi ser at spektrale repetisjoner ikke overlapper hverandre, og dermed kan det originale spekteret gjenopprettes nøyaktig. ${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$

Implikasjoner

Aliasing

Fig. 4: Støtte av det samplede spekteret oppnådd ved sekskantet prøvetaking av en todimensjonal funksjon bølgetallbegrenset til en sirkulær plate. I dette eksemplet er ikke samplingsgitteret fint nok, og derfor overlapper platene i det samplede spekteret. Dermed kan ikke spektrumet som er representert av den blå sirkelen gjenopprettes nøyaktig på grunn av overlappingen fra repetisjonene (vist i grønt), noe som fører til aliasing. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Fig. 5: Romlig aliasing i form av et Moiré-mønster .

Fig. 6: Riktig samplet bilde av murvegg.

Teoremet gir betingelser for prøvetaking av gitter for perfekt rekonstruksjon av samplet. Hvis gitterene ikke er fine nok til å tilfredsstille Petersen-Middleton-tilstanden, kan ikke feltet rekonstrueres nøyaktig fra prøvene generelt. I dette tilfellet sier vi at prøvene kan være alias . Igjen, se på eksemplet der en sirkulær plate er. Hvis Petersen-Middleton-forholdene ikke holder, vil støtten til det utvalgte spekteret være som vist i figur 4. I dette tilfellet overlapper spektrale repetisjoner som fører til aliasing i rekonstruksjonen. ${\ displaystyle \ Omega}$

En enkel illustrasjon av aliasing kan fås ved å studere bilder med lav oppløsning. Et gråskalabilde kan tolkes som en funksjon i todimensjonalt rom. Et eksempel på aliasing er vist i bildene av mursteinsmønstre i Figur 5. Bildet viser effekten av aliasing når prøvetakingssetningens tilstand ikke er oppfylt. Hvis gitteret til piksler ikke er fint nok til scenen, skjer aliasing som vist av utseendet til Moiré-mønsteret i det oppnådde bildet. Bildet i figur 6 oppnås når en utjevnet versjon av scenen samples med samme gitter. I dette tilfellet er setningens vilkår oppfylt og ingen aliasing forekommer.

SP Efimov fra Bauman Moscow State Technical University i 1978 y. fant en tilnærming for å lette restriksjonene for spektrumdomene. Han anså N identiske prøvetakingsgitter flyttet vilkårlig til hverandre. Optimal prøvetaking er gyldig for spektrumdomene som skiftede versjoner av er fullpakket N ganger på gjensidig gitter. Derfor kan ringen overlappes av et sett med sekskanter i stedet for en. JWST- teleskoparray består av 18 sekskanter. Sampling på 18 skiftede gitter er mulig for 2-d Fourier-transformasjon av array-signalet (dvs. for utsendt signal).

Optimal prøvetakingsgitter

Et av objektene som er av interesse for å designe et prøvetakingsskjema for bølgetallbegrensede felt er å identifisere konfigurasjonen av punkter som fører til den minimale samplingstettheten, dvs. tettheten av prøvetakingspunkter per romlig volumsenhet i . Kostnaden for å ta og lagre målingene er vanligvis proporsjonal med den anvendte prøvetettheten. Ofte i praksis er den naturlige tilnærmingen til å prøve todimensjonale felt å prøve den på punkter på et rektangulært gitter . Dette er imidlertid ikke alltid det ideelle valget når det gjelder prøvetakingstettheten. Teoremet til Petersen og Middleton kan brukes til å identifisere det optimale gitteret for prøvetaking av felt som er bølgetallbegrenset til et gitt sett . For eksempel kan det vises at gitteret med minimal romlig tetthet av punkter som tillater perfekte rekonstruksjoner av felt bølgetallbegrenset til en sirkulær plate i er det sekskantede gitteret. Som en konsekvens foretrekkes sekskantede gitter for prøvetaking av isotrope felt i . ${\ displaystyle \ Re ^ {n}}$${\ displaystyle \ Omega \ subset \ Re ^ {d}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$

Optimal prøvetakingsgitter er studert i høyere dimensjoner. Vanligvis optimal sfære pakking gittere er ideelle for prøvetaking jevn stokastiske prosesser samtidig optimal sfære som dekker gittere er ideelle for prøvetaking grove stokastiske prosesser.

Siden optimale gitter generelt ikke kan skilles, krever utforming av interpolasjons- og rekonstruksjonsfiltre ikke-tensor-produkt (dvs. ikke-separerbare) filterdesignmekanismer. Box splines gir et fleksibelt rammeverk for å designe slike ikke-separerbare FIR- filtre for rekonstruksjon som kan skreddersys geometrisk for hvert gitter. Hex-splines er generaliseringen av B-splines for 2-D sekskantede gitter. I 3-D og høyere dimensjoner gir Voronoi splines en generalisering av B-splines som kan brukes til å designe ikke-separerbare FIR-filtre som er geometrisk skreddersydd for ethvert gitter, inkludert optimale gitter.

Eksplisitt konstruksjon av ideelle lavpasfilter (dvs. sinc- funksjoner) generalisert til optimale gitter er mulig ved å studere de geometriske egenskapene til Brillouin-soner (dvs. ovenfor) til disse gitterene (som er zonotoper ). Denne tilnærmingen gir en lukket form eksplisitt representasjon av for generelle gitter, inkludert optimale prøvetakingsgitter. Denne konstruksjonen gir en generalisering av Lanczos-filteret i 1-D til den flerdimensjonale innstillingen for optimale gitter. ${\ displaystyle \ Omega}$${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$

applikasjoner

Theorem Petersen – Middleton er nyttig i utformingen av effektive sensorplasseringsstrategier i applikasjoner som involverer måling av romlige fenomener som seismiske undersøkelser, miljøovervåking og romlige lydfeltmålinger.

Referanser