Mehrdimensionale Probenahme - Multidimensional sampling

Bei der digitalen Signalverarbeitung ist mehrdimensionales Abtasten der Prozess des Umwandelns einer Funktion einer mehrdimensionalen Variablen in eine diskrete Sammlung von Werten der Funktion, die an einem diskreten Satz von Punkten gemessen werden. Dieser Artikel präsentiert das grundlegende Ergebnis von Petersen und Middleton zu Bedingungen für die perfekte Rekonstruktion einer Wellenzahl-begrenzten Funktion aus ihren Messungen an einem diskreten Punktgitter . Dieses Ergebnis, auch als Petersen-Middleton-Theorem bekannt , ist eine Verallgemeinerung des Nyquist-Shannon-Abtasttheorems zur Abtastung eindimensionaler bandbegrenzter Funktionen in höherdimensionale euklidische Räume .

Im Wesentlichen zeigt das Petersen-Middleton-Theorem, dass eine wellenzahlbegrenzte Funktion aus ihren Werten auf einem unendlichen Punktgitter perfekt rekonstruiert werden kann, vorausgesetzt, das Gitter ist fein genug. Der Satz liefert Bedingungen auf dem Gitter, unter denen eine perfekte Rekonstruktion möglich ist.

Wie beim Nyquist-Shannon-Abtasttheorem geht auch dieses Theorem von einer Idealisierung jeder realen Situation aus, da es nur für Funktionen gilt, die über eine Unendlichkeit von Punkten abgetastet werden. Eine perfekte Rekonstruktion ist für das idealisierte Modell mathematisch möglich, aber nur eine Annäherung an reale Funktionen und Abtasttechniken, wenn auch in der Praxis oft eine sehr gute.

Vorbereitungen

Abb. 1: Ein hexagonales Abtastgitter und seine Basisvektoren v ₁ und v ₂${\ displaystyle \ Lambda}$

Fig. 2: Das dem Gitter von Fig. 1 entsprechende reziproke Gitter und seine Basisvektoren u ₁ und u ₂ (nicht maßstabsgetreue Figur). ${\ displaystyle \ Gamma}$${\ displaystyle \ Lambda}$

Das Konzept einer bandbegrenzten Funktion in einer Dimension kann auf den Begriff einer wellenzahlbegrenzten Funktion in höheren Dimensionen verallgemeinert werden. Denken Sie daran, dass die Fourier-Transformation einer integrierbaren Funktion im n- dimensionalen euklidischen Raum wie folgt definiert ist: ${\ 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}$

wobei x und ξ sind n - dimensionale Vektoren , und ist das innere Produkt der Vektoren. Die Funktion wird gesagt, auf einen Satz Wellenzahl-begrenzt werden , wenn die Fourier - Transformation erfüllt für . ${\ displaystyle \ langle x, \ xi \ rangle}$${\ displaystyle f (\ cdot)}$${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} (\ xi) = 0}$${\ displaystyle \ xi \ notin \ Omega}$

In ähnlicher Weise kann die Konfiguration von gleichmäßig beabstandeten Abtastpunkten in einer Dimension auf ein Gitter in höheren Dimensionen verallgemeinert werden . Ein Gitter ist eine Sammlung von Punkten der Form where { v ₁ , ..., v _n } eine Basis für . Die reziproken Gitter entsprechend definiert ist durch ${\ 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 \} }}$

wo die Vektoren ausgewählt werden, um zu erfüllen . Das heißt, wenn die Vektoren Spalten einer Matrix und die Spalten einer Matrix bilden , dann . Ein Beispiel für ein Abtastgitter im zweidimensionalen Raum ist ein in Abbildung 1 dargestelltes hexagonales Gitter . Das entsprechende reziproke Gitter ist in Abbildung 2 dargestellt. Das reziproke Gitter eines quadratischen Gitters in zwei Dimensionen ist ein weiteres quadratisches Gitter. Im dreidimensionalen Raum ist das reziproke Gitter eines flächenzentrierten kubischen (FCC) Gitters ein körperzentriertes kubisches (BCC) 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}}$

Der Satz

Lassen Sie bezeichnen ein Gitter in und die entsprechenden reziproken Gitter. Der Satz von Petersen und Middleton besagt, dass eine Funktion , die auf eine Menge beschränkt ist, aus ihren Messungen genau rekonstruiert werden kann, vorausgesetzt, die Menge überlappt sich nicht mit einer ihrer verschobenen Versionen, bei denen die Verschiebung x ein Element ungleich Null des Kehrwerts ist Gitter . Mit anderen Worten, kann aus seinen Messungen genau rekonstruiert werden, sofern dies für alle gilt . ${\ 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 \}}$

Wiederaufbau

Fig. 3: Unterstützung des abgetasteten Spektrums, das durch hexagonale Abtastung einer auf eine Kreisscheibe begrenzten Wellenzahl mit zweidimensionaler Funktion erhalten wurde. Der blaue Kreis repräsentiert die Unterstützung des ursprünglichen Feldes mit begrenzter Wellenzahl, und die grünen Kreise repräsentieren die Wiederholungen. In diesem Beispiel überlappen sich die spektralen Wiederholungen nicht und daher gibt es kein Aliasing. Das ursprüngliche Spektrum kann genau aus dem abgetasteten Spektrum wiederhergestellt werden. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Die Verallgemeinerung der Poisson-Summationsformel auf höhere Dimensionen kann verwendet werden, um zu zeigen, dass die Abtastwerte der Funktion auf dem Gitter ausreichen, um eine periodische Summierung der Funktion zu erzeugen . Das Ergebnis ist: ${\ 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},}$

( Gl. 1 )

wobei das Volumen des durch die Vektoren { v ₁ , ..., v _n } gebildeten Parallelepipeds darstellt . Diese periodische Funktion wird oft als abgetastetes Spektrum bezeichnet und kann als Analogon der zeitdiskreten Fourier-Transformation (DTFT) in höheren Dimensionen interpretiert werden . Wenn das ursprüngliche wellenzahlbegrenzte Spektrum auf dem Satz unterstützt wird, wird die Funktion bei periodischen Wiederholungen der Verschiebung um Punkte auf dem reziproken Gitter unterstützt . Wenn die Bedingungen des Petersen-Middleton Satz erfüllt sind, dann wird die Funktion ist gleich für alle , und daher kann das ursprüngliche Feld genau aus den Proben rekonstruiert werden. In diesem Fall stimmt das rekonstruierte Feld mit dem ursprünglichen Feld überein und kann in Form der Stichproben ausgedrückt werden als ${\ 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)}$ ,

( Gleichung 2 )

wo ist die inverse Fourier-Transformation der charakteristischen Funktion der Menge . Diese Interpolationsformel ist das höherdimensionale Äquivalent der Whittaker-Shannon-Interpolationsformel . ${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$${\ displaystyle \ Omega}$

Nehmen wir als Beispiel an, das ist eine kreisförmige Scheibe. Abbildung 3 zeigt die Unterstützung, wann die Bedingungen des Petersen-Middleton-Theorems erfüllt sind. Wir sehen, dass sich die spektralen Wiederholungen nicht überlappen und daher das ursprüngliche Spektrum genau wiederhergestellt werden kann. ${\ displaystyle \ Omega}$${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$

Implikationen

Aliasing

Fig. 4: Unterstützung des abgetasteten Spektrums, das durch hexagonale Abtastung einer Wellenzahl mit zweidimensionaler Funktion erhalten wird, die auf eine kreisförmige Scheibe beschränkt ist. In diesem Beispiel ist das Abtastgitter nicht fein genug und daher überlappen sich die Scheiben im abgetasteten Spektrum. Daher kann das durch den blauen Kreis dargestellte Spektrum aufgrund der Überlappung der Wiederholungen (grün dargestellt) nicht genau wiederhergestellt werden, was zu einem Aliasing führt. ${\ displaystyle {\ hat {f}} _ {s} (\ cdot)}$${\ displaystyle \ Omega}$

Abb. 5: Räumliches Aliasing in Form eines Moiré-Musters .

Abb. 6: Richtig abgetastetes Bild der Mauer.

Der Satz gibt Bedingungen für Abtastgitter für eine perfekte Rekonstruktion der Abtastung an. Wenn die Gitter nicht fein genug sind, um die Petersen-Middleton-Bedingung zu erfüllen, kann das Feld im Allgemeinen nicht genau aus den Proben rekonstruiert werden. In diesem Fall sagen wir, dass die Samples möglicherweise einen Alias ​​aufweisen . Betrachten Sie erneut das Beispiel, in dem es sich um eine kreisförmige Scheibe handelt. Wenn die Petersen-Middleton-Bedingungen nicht zutreffen, erfolgt die Unterstützung des abgetasteten Spektrums wie in Abbildung 4 gezeigt. In diesem Fall überlappen sich die spektralen Wiederholungen, was zu einem Aliasing bei der Rekonstruktion führt. ${\ displaystyle \ Omega}$

Eine einfache Darstellung des Aliasing kann durch Untersuchung von Bildern mit niedriger Auflösung erhalten werden. Ein Graustufenbild kann als Funktion im zweidimensionalen Raum interpretiert werden. Ein Beispiel für Aliasing ist in den Bildern von Ziegelmustern in Abbildung 5 dargestellt. Das Bild zeigt die Auswirkungen von Aliasing, wenn die Bedingung des Abtasttheorems nicht erfüllt ist. Wenn das Pixelgitter für die Szene nicht fein genug ist, tritt ein Aliasing auf, was durch das Auftreten des Moiré-Musters in dem erhaltenen Bild belegt wird. Das Bild in 6 wird erhalten, wenn eine geglättete Version der Szene mit demselben Gitter abgetastet wird. In diesem Fall sind die Bedingungen des Satzes erfüllt und es tritt kein Aliasing auf.

SP Efimov von der Bauman Moscow State Technical University im Jahr 1978 y. fanden einen Ansatz, um die Einschränkungen für den Frequenzbereich zu lockern. Er betrachtete N identische Abtastgitter als willkürlich zueinander verschoben. Die optimale Abtastung gilt für die Spektrumsdomäne, deren verschobene Versionen auf dem reziproken Gitter N-mal dicht gepackt sind. Daher kann der Ring durch einen Satz Sechsecke anstelle eines überlappt werden. Das JWST- Teleskoparray besteht aus 18 Sechsecken. Die Abtastung auf 18 verschobenen Gittern ist für die 2D-Fourier-Transformation des Arraysignals (dh für das emittierte Signal) möglich.

Optimale Abtastgitter

Eines der interessierenden Objekte beim Entwerfen eines Abtastschemas für wellenzahlbegrenzte Felder besteht darin, die Konfiguration von Punkten zu identifizieren, die zur minimalen Abtastdichte führt, dh zur Dichte der Abtastpunkte pro räumlicher Volumeneinheit in . Typischerweise sind die Kosten für die Durchführung und Speicherung der Messungen proportional zur verwendeten Probendichte. In der Praxis besteht der natürliche Ansatz zum Abtasten zweidimensionaler Felder häufig darin, sie an Punkten auf einem rechteckigen Gitter abzutasten . Dies ist jedoch nicht immer die ideale Wahl hinsichtlich der Abtastdichte. Der Satz von Petersen und Middleton kann verwendet werden, um das optimale Gitter für Abtastfelder zu identifizieren, die auf eine bestimmte Menge wellenzahlbegrenzt sind . Zum Beispiel kann gezeigt werden, dass das Gitter mit minimaler räumlicher Punktdichte, das eine perfekte Rekonstruktion von Feldern zulässt, die auf eine kreisförmige Scheibe beschränkt sind, das hexagonale Gitter ist. Infolgedessen werden hexagonale Gitter für die Abtastung isotroper Felder in bevorzugt . ${\ displaystyle \ Re ^ {n}}$${\ displaystyle \ Omega \ subset \ Re ^ {d}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$${\ displaystyle \ Re ^ {2}}$

Optimale Abtastgitter wurden in höheren Dimensionen untersucht. Im Allgemeinen sind optimale Kugelpackungsgitter ideal für die Abtastung glatter stochastischer Prozesse, während optimale Kugelabdeckungsgitter ideal für die Abtastung rauer stochastischer Prozesse sind.

Da optimale Gitter im Allgemeinen nicht trennbar sind, erfordert das Entwerfen von Interpolations- und Rekonstruktionsfiltern Filterentwurfsmechanismen ohne Tensorprodukt (dh nicht trennbar). Box-Splines bieten einen flexiblen Rahmen für das Entwerfen solcher nicht trennbaren FIR- Filter für die Rekonstruktion , die für jedes Gitter geometrisch angepasst werden können. Hex-Splines sind die Verallgemeinerung von B-Splines für hexagonale 2D-Gitter. In ähnlicher Weise bieten Voronoi-Splines in 3D- und höheren Dimensionen eine Verallgemeinerung von B-Splines , mit denen nicht trennbare FIR-Filter entworfen werden können, die geometrisch auf jedes Gitter zugeschnitten sind, einschließlich optimaler Gitter.

Die explizite Konstruktion idealer Tiefpassfilter (dh sinc- Funktionen), die auf optimale Gitter verallgemeinert sind, ist möglich, indem die geometrischen Eigenschaften der Brillouin-Zonen (dh oben) dieser Gitter (die Zonotope sind ) untersucht werden. Dieser Ansatz bietet eine geschlossene explizite Darstellung für allgemeine Gitter, einschließlich optimaler Abtastgitter. Diese Konstruktion bietet eine Verallgemeinerung des Lanczos-Filters in 1-D auf die mehrdimensionale Einstellung für optimale Gitter. ${\ displaystyle \ Omega}$${\ displaystyle {\ check {\ chi}} _ {\ Omega} (\ cdot)}$

Anwendungen

Das Petersen-Middleton-Theorem ist nützlich für die Entwicklung effizienter Strategien zur Sensorplatzierung in Anwendungen, die die Messung räumlicher Phänomene wie seismische Vermessungen, Umgebungsüberwachung und räumliche Audiofeldmessungen umfassen.

Verweise