Benutzer:KinimodRere/Gerchberg–Saxton Algorithmus

Dieser Artikel (Gerchberg–Saxton Algorithmus) ist im Entstehen begriffen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Wenn du dies liest: Der Text kann teilweise in einer Fremdsprache verfasst, unvollständig sein oder noch ungeprüfte Aussagen enthalten. Wenn du Fragen zum Thema hast, nimm am besten Kontakt mit dem Autor KinimodRere auf.

Wenn du diesen Artikel überarbeitest: Bitte denke daran, die Angaben im Artikel durch geeignete Quellen zu belegen und zu prüfen, ob er auch anderweitig den Richtlinien der Wikipedia entspricht (siehe Wikipedia:Artikel). Nach erfolgter Übersetzung kannst du diese Vorlage entfernen und den Artikel in den Artikelnamensraum verschieben. Die entstehende Weiterleitung kannst du schnelllöschen lassen. Importe inaktiver Accounts, die länger als drei Monate völlig unbearbeitet sind, werden gelöscht.

Vorlage:Importartikel/Wartung-2020-12

The replay field of a computer generated hologram generated by the Gerchberg–Saxton algorithm. The 'star' is the zero-order diffraction peak.

Der Gerchberg-Saxton Algorithmus (GSA) ist ein iterativer Phasensuchalgorithmus und wird zu den interaktiven Fourier-Transformations-Algorithmen (IFTA) gezählt. Der Algorithmus wurde in "A Practical Algorithm for the Determination of Phase from Image and Diffraction Plane Pictures“ von R. W. Gerchberg und W. O. Saxton in Optik (35, 237–246 1972) veröffentlicht und ist wegen seiner Einfachheit heute oft Ausgangspunkt für effizientere Algorithmen.

Datei:GS-diagram.png

Schematic view of the error reduction algorithm for phase retrieval - a generalization of the Gerchberg-Saxton algorithm.

Algorithmus

Der Algorithmus besteht aus einer Schleife, welche eine Fourier-Transformation ($\mathbf {FFT}$) und Fourier-Rück-Transformation ($\mathbf {FFT^{-1}}$) durchführt. Die Schleife wird so lange durchgeführt, bis ein Abbruchkriterium erfüllt wird (z.B. quadratischer Fehler der Pixel). Der Algorithmus wird hier für diskrete Pixel berechnet, dafür verwenden wir die diskrete Fourier-Transformation (auch kontinuierliche Transformation ist möglich).

$A\equiv$ Eingangsamplitudenverteilung aus $\mathbb {C} ^{n\times n}$

Konvergenz

Es ist zu zeigen, dass der quadratische Fehler $e^{2}$ konstant bleibt oder abnimmt. Dazu schauen wir uns einen repräsentativen Punkt in Bildebene ($i=1$) und Beugungsebene ($i=2$) an. Wir definieren den quadratischen Fehler $e^{2}:=\sum _{n\leq N}(|h_{i}|-|g_{i}|)^{2}$ mit $|h_{i}|$ der gewollten Amplitude und $|g_{i}|$ der erreichten Amplitude. Mit Beginn des Algorithmus wird aus einer Ausgangsintensität mit FFT der komplexe Vektor $g_{1}$ erzeugt. Die Amplitude dieses Vektors ist später die Intensität des Holograms. Die Amplitude $|g_{1}|$ stimmt nicht, sie sollte die Amplitude der Bildebene $|h_{1}|$ haben (Schritt X). Die Amplitude wird mit dem Korrekturvektor $c_{1}$ mit $h_{1}=g_{1}-c_{1}$ korrigiert.

$h_{1}$ wird in die Beugungsebene zurücktransformiert (IFFT) $h_{1}\rightarrow h_{2}$. Da die Fouriertransformation additiv ist, kann $h_{2}$ auch aus den Transformierten $g_{2}+c_{2}=h_{2}$ erzeugt werden.

Wir stellen fest, dass $|c_{2}|^{2}=(|h_{2}|-|g_{2}|)^{2}$ ein Summand unseres Fehlers ist. Das bedeutend, dass mit fallenden $|c_{2}|^{2}$ der Fehler der Amplitudenquadrate kleiner wird und dadurch der Algorithmus konvergiert. Mit der Parsevalidentität (für diskrete und für kontinuierliche Fouriertransformationen):

$\sum _{n\leq N}|c_{1}[n]|^{2}=\sum _{n\leq N}|c_{2}[n]|^{2}$

sinkt damit auch der Fehler der Ausgangsintensität. Aus der Abbildung wird klar, dass $|d_{2}|\leq |c_{2}|$ wobei $|d_{2}|$ die Amplitudendifferenz zur Zielintensitätsverteilung ist.

1. Fall: Ist also $|d_{2}|$ parallel zu $|c_{2}|$ bewirkt eine erneute Iteration keine Änderung der Phase und damit keine Änderung von der Fouriertransformierten $g_{1}$

$\Rightarrow$ der Fehler $e^{2}$ bleibt für diesen Punkt konstant.

1. Fall: Ist $|d_{2}|$ nicht parallel zu $|c_{2}|$ bewirkt die veränderte Phase in der Beugungsebene erneute Iteration eine Änderung in der Bildebene

$\Rightarrow$ der Fehler $e^{2}$ wird geringer.

Anwendung in der Optik

Der Algorithmus nähert iterativ eine Phasenverteilung an, welche durch die Eingabe einer Zieldistribution festgelegt wird.

Mit dieser Eigenschaft ist der Algorithmus für die Berechnung von Brechungsmustern der Fernfeld-Beugung (Fraunhofer Beugung) geeignet: Hierzu wird mit dem Algorithmus aus dem Brechungsmuster als 2-dimensionale Intensitätsmatrix der Phasenverschub für den Laserstrahl berechnet. Der Phasenverschub kann beispielsweise durch Diffraktive Optische Elemente (DOE) erzeugt werden.

Auch wenn meist Zwei-dimensionale diskrete Signale verwendet werden, ist der Gerchberg-Saxton Algorithmus nicht an Dimension oder Kontinuität gebunden. Im Paper wird der Algorithmus in der kontinuierlichen Variante vorgestellt.

Pseudocode

Sei:
 FT – Fourier-Transformation
 IFT – inverse Fourier-Transformation
 i – imaginäre Einheit
 exp – Exponentialfunktion

 Ziel und Eingang sind Ziel- und Eingangs-Amplitudenmatrizen
 A, B, C & D sind die komplexen Matrizen der selben Größe, wie Ziel- und Eingangs-Amplitudenmatrizen
 Amplitude() bestimmt die Amplitude der einzelnen Einträge der Matrix
   z.B. für einen komplexen Eintrag z = x + iy, Amplitude(z) = sqrt(x·x + y·y)
 Phase() bestimmt die Phase der einzelnen Einträge einer komplexen Matrix
   z.B. Phase(z) = arctan(y / x)
Ende Sei

Algorithmus Gerchberg–Saxton(Eingang, Ziel, Erneuerte_Phase) ist
    AA:= IFT(Ziel)
    Wiederhole solange das Determinierungsargument nicht erfüllt ist
        BB:= Amplitude(Eingang) × exp(i × Phase(A))
        C := FT(B)
        D := Amplitude(Ziel) × exp(i × Phase(C))
        A := IFT(D)
    Ende Wiederhole
    Erneuerte_Phase = Phase(A)

Hier wird der grundlegende Algorithmus als Pseudo-Code beschrieben. Heute gibt es eine Vielzahl an Verbesserungen, die den Algorithmus effizienter machen.

See also

• Fourier optics
• Holography

References

• R. W. Gerchberg and W. O. Saxton, "A practical algorithm for the determination of the phase from image and diffraction plane pictures,” Optik 35, 237 (1972)

External links

• Dr W. Owen Saxton's Internetseite [1], [2]
• Applications and publications on phase retrieval from the University of Rochester, Institute of Optics
• SLM ToolBox. Ein kostenloses Programm für Windows zur Berechnung und Anzeige von 'Hologrammen' (bzw. Frauenhofer-Beugung)
• Ein Python-Script des Gerchberg-Saxton-Algorithmus

[[Category:Digital signal processing]] [[Category:Physical optics]] [[Category:Articles with example pseudocode]]