[PYTHON] Implementierung von Scale-Space für SIFT

Ziel dieses Artikels

Sie können den Skalierungsraum verstehen und implementieren, der SIFT (Scale Invariant Feature Transform) unterstützt, der die Funktionen von Bildern beschreibt, die gegen Skalierungsänderungen und Rotation resistent sind.

Verwandte Kenntnisse

• Bildglättung mit Gaußscher Faltung
• Fourier-Transformation und Abtastsatz

Umgebung zu verwenden

Hinweis

Dieser Artikel wurde als Material für das 41. Treffen von Morning Project Samurai geschrieben.

Bitte

Dies ist eine Entwurfsversion. Wenn Sie Fehler finden, würden wir uns freuen, wenn Sie uns kontaktieren könnten.

Scale-space

Definition

• Generieren Sie aus einem bestimmten Bild mehrere Bilder mit unterschiedlichen Maßstäben.
• Der aus diesen Bildern zusammengesetzte Raum wird als Skalierungsraum bezeichnet.

Motivation

Betrachten Sie die Erkennung eines bestimmten Objekts aus einem bestimmten Bild. Betrachten Sie beispielsweise die Erkennung einer Person anhand einer Szene (Bild) eines Videos einer Stadtstraße. Zu diesem Zeitpunkt ist kein maßstabsgetreues Bild erforderlich, das die Details des Musters der Kleidung zeigt, die eine Person trägt. Es ist besser, ein Bild auf einer Skala zu haben, die es Ihnen ermöglicht, die Form einer Person zu verstehen, aber nicht die Kleidung, die Sie tragen. Zu detaillierte Informationen sind eher Rauschen.

Wie oben erwähnt, gibt es eine Bildskala, die zum Erfassen des interessierenden Objekts geeignet ist. In der Realität hat ein bestimmtes Bild jedoch nicht immer den richtigen Maßstab. Daher wird ein Skalenraum konstruiert, indem mehrere Bilder mit unterschiedlichen Skalen aus einem gegebenen Bild erzeugt werden, und ein Bild mit einem geeigneten Maßstab wird aus dem Skalenraum gefunden, um ein Objekt zu erfassen.

Skalieren und skalieren

Im Skalierungsraum bedeutet Skalierung das Entfernen detaillierter Informationen aus dem Originalbild unter Verwendung einer Technik, die als Gaußsche Faltung bezeichnet wird. Der Grad der Vergrößerung wird durch den Gaußschen Faltungsparameter $ \ sigma $ bestimmt. Je größer der Maßstab $ \ sigma $ ist, desto mehr Informationen werden aus dem Originalbild entfernt.

In der folgenden Abbildung kann das Originalbild ganz links beispielsweise die Details des Gesichts und sogar die Pelzhaare des Hutes deutlich erkennen. Im Bild ganz rechts $ \ sigma = 3.2 $ sehen Sie, dass es eine vage Frau gibt und die Augen klar sind, aber nichts weiter.

So konfigurieren Sie

1. Bereiten Sie das Originalbild vor (Graustufen).
2. Skalieren Sie $ \ sigma = k ^ {n} \ sigma_ {0} $ und setzen Sie den Anfangswert von $ n $ auf $ 0 $.
3. Skalieren Sie das Originalbild mithilfe der Gaußschen Faltung.
4. Wiederholen Sie Schritt 3, während Sie $ n $ auf $ 1, 2, 3, ... $ erhöhen, bis $ k ^ {n} = 2.0 $. $ k $ wird durch die Anzahl der Bilder bestimmt, die Sie vor $ k ^ {n} = 2.0 $ erstellen möchten.
5. Probieren Sie das Bild der Skala $ \ sigma = 2.0 \ sigma_ {0} $ herunter, sodass es vertikal und horizontal halb so groß ist.
6. Setzen Sie mit dem heruntergesampelten Bild als Originalbild $ n = 1 $ und kehren Sie zu Schritt 3 zurück.

Die detaillierte Konstruktionsmethode und ihr Programm werden nach dem Erlernen der Gaußschen Faltung, der Fourier-Transformation, des Abtasttheorems usw. beschrieben.

Gaussian convolution

• Der Skalierungsraum wird verwendet, um aus dem Originalbild ein Bild der Skalierung $ \ sigma $ zu generieren.
• Wird zum Entfernen und Verwischen von Bildrauschen im allgemeinen Bildverarbeitungskontext verwendet.
• Mathematisch wird der Gaußsche Kernel verwendet, um die gewichtete durchschnittliche Reihe beliebiger Funktionen zu ermitteln.

1D Gaußsche Faltung

Die eindimensionale Gaußsche Faltung wird durch die folgende Gleichung ausgedrückt.

F(x, \sigma)=\int_{-\infty}^{\infty} f(u) \frac{1}{\sqrt{2 \pi \sigma^{2}}}e^{-\frac{(u-x)^2}{2\sigma^{2}}} du

$ f $ ist das ursprüngliche Signal. $ \ frac {1} {\ sqrt {2 \ pi \ sigma ^ {2}}} e ^ {- \ frac {(ux) ^ 2} {2 \ sigma ^ {2}} $ heißt Gaußscher Kernel .. $ \ Sigma $ ist ein Parameter, der die Form des Gaußschen Kernels bestimmt. Der Gaußsche Kernel hat die Form einer Glocke mit einem Maximalwert in der Mitte $ x $, und seine Höhe und Ausbreitung werden durch $ \ sigma $ bestimmt.

Gaussian kernel Versuchen wir, einen Gaußschen Kernel mit numpy, scipy und matplotlib zu zeichnen.

import numpy as np
from scipy.signal import gaussian
from matplotlib import pyplot as plt


if __name__ == '__main__':
    npoints = 101
    sigmas = np.array([6.0, 12.0])
    for i, sigma in enumerate(sigmas):
        y = gaussian(npoints, sigma) / (np.sqrt(2.0 * np.pi) * sigma)
        plt.subplot(len(sigmas), 1, i + 1)
        plt.title('sigma = %s' % sigma)
        plt.ylim(ymax=0.08)
        plt.plot(np.arange(npoints/2 - npoints, npoints/2, dtype=np.int), y)
    plt.tight_layout()
    plt.show()

Wenn Sie das obige Programm ausführen, erhalten Sie das folgende Ergebnis.

[Hinzufügung der Natur des Gaußschen Kernels später]

Interpretations- und Anwendungsbeispiel

Die Gaußsche Faltungsformel lautet "Das ursprüngliche Signal $ f $ multipliziert mit dem Gewicht des Zentrums $ x $ spreizt $ \ sigma $ (Gaußscher Kernel) und die Summe (gewichteter Durchschnitt) ist $ F (x, \ sigma) $ Es kann als "dargestellt durch" interpretiert werden. Daraus ergibt sich, dass $ F $ die Information des gesamten $ f $ hat, während die Information in der Nähe von $ u = x $ des ursprünglichen Signals $ f (u) $ mit der durch $ \ sigma $ bestimmten Stärke stark reflektiert wird. Es kann als "neues Signal bestehend aus $ F (x, \ sigma) " interpretiert werden. Dies bedeutet, dass " F $ ein Signal ist, das durch Glätten (Verwischen, Entfernen von Rauschen) des ursprünglichen Signals $ f $ mit einer Intensität von $ \ sigma $ erhalten wird". Im Zusammenhang mit dem Skalierungsraum kann gesagt werden, dass "$ F $ ein Signal ist, das durch Skalieren von $ f $ zur Skalierung von $ \ sigma $ (ohne detaillierte Informationen) erhalten wird".

Wie wir im vorherigen Abschnitt gesehen haben, wird der Gaußsche Kernel flacher, wenn $ \ sigma $ zunimmt. Dies bedeutet, dass "je größer $ \ sigma $ ist, desto heller ist die Farbe der Informationen in der Nähe von $ u = x $ des ursprünglichen Signals $ f $, das in $ F (x, \ sigma) $ enthalten ist". Wenn Sigma $ immer größer wird, erhält $ F $ schließlich den gleichen Wert für alle $ x $. Im Kontext des Skalenraums gilt: "Je größer die Skala $ \ sigma $ ist, desto makroskopischer wird das Signal betrachtet (detaillierte Informationen gehen verloren) und schließlich werden alle im Signal enthaltenen Informationen identifiziert." Kann interpretiert werden als.

Lassen Sie uns die bisherige Geschichte mit einem Programm visualisieren.

import numpy as np
from scipy.ndimage.filters import gaussian_filter1d
from matplotlib import pyplot as plt


if __name__ == '__main__':
    x = np.arange(0, 100)
    f = np.sin(0.5 * x) + np.random.normal(0, 6.0, x.shape)

    sigmas = [1.6, 3.2, 6.4]

    plt.subplot(len(sigmas) + 1, 1, 1)
    plt.ylim(ymin=np.min(f), ymax=np.max(f))
    plt.title('Original')
    plt.plot(f)

    for i, sigma in enumerate(sigmas):
        plt.subplot(len(sigmas) + 1, 1, 2 + i)
        plt.title('Sigma = %s' % sigma)
        plt.plot(gaussian_filter1d(f, sigma))
    plt.tight_layout()
    plt.show()

Wenn das obige Programm ausgeführt wird, wird die folgende Abbildung erhalten.

Wenn $ \ sigma $ wächst (skaliert), können Sie sehen, dass die im Signal $ f $ enthaltenen detaillierten Informationen von $ F $ verloren gehen.

2D-Gaußsche Faltung

Das Bild ist ein zweidimensionales Signal. Um ein Bild unter Verwendung der Gaußschen Faltung zu vergrößern, ist daher eine Gaußsche Faltung für ein zweidimensionales Signal erforderlich. Wenn wir im Folgenden einfach die Gaußsche Faltung schreiben, beziehen wir uns auf die zweidimensionale Gaußsche Faltung.

Die Gaußsche Faltung für ein zweidimensionales Signal wird durch die folgende Gleichung ausgedrückt.

F(x, y, \sigma) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(u, v) \frac{1}{2\sigma^{2}} e^{-\frac{(u - x)^2 + (v-y)^{2}}{\sigma^{2}}} dudv

$ \ frac {1} {2 \ sigma ^ {2}} e ^ {- \ frac {(u-x) ^ 2 + (vy) ^ {2}} {\ sigma ^ {2}}} $ ist Gaußsch Es ist ein Kernel. Dieser Gaußsche Kernel ist ein dreidimensionaler Glockentyp, wobei $ (x, y) $ den Maximalwert annimmt und $ \ sigma $ seine Ausbreitung darstellt.

Gaussian kernel Zeichnen wir den Gaußschen Kernel programmgesteuert.

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D


def gaussian_kernel_2d(x, y, sigma):
    return np.exp(-(np.power(x/sigma, 2) + np.power(y/sigma, 2)))/(2 * np.power(sigma, 2))


if __name__ == '__main__':
    xrange = np.arange(-10.0, 10.5, 0.5)
    yrange = np.arange(-10.0, 10.5, 0.5)
    kernel_values = np.zeros(shape=(len(yrange), len(xrange)))

    sigmas = [1.6, 2.4]

    fig = plt.figure()
    X, Y = np.meshgrid(xrange, yrange)

    for i, sigma in enumerate(sigmas):
        ax = fig.add_subplot(len(sigmas), 1, 1 + i,  projection='3d')
        plt.title('Sigma = %s' % sigma)
        ax.set_zlim(zmax=0.2)
        ax.plot_wireframe(X, Y, gaussian_kernel_2d(X, Y, sigma))
    plt.show()

Die folgende Abbildung kann durch Ausführen des obigen Programms erhalten werden. Es ist möglich, den Blickwinkel mit der Maus zu ändern.

Diskrete Gaußsche Faltung

Gaussian filter Computer können nur diskrete Werte verarbeiten, und ihr Bereich ist begrenzt. Der Gaußsche Kernel ist eine kontinuierliche Funktion mit einem Definitionsbereich von $ \ pm \ infty $. Daher ist es notwendig, den Gaußschen Kernel mit einer endlichen Anzahl von numerischen Zeichenfolgen zu approximieren und zu verteilen, damit er von einem Computer verarbeitet werden kann.

Betrachten Sie ein Raster aus $ s $ Zeilen und $ t $ Spalten. Im Folgenden wird dieses Gitter als Filter von $ s \ times t $ bezeichnet. Dies wird programmgesteuert im folgenden zweidimensionalen Array dargestellt.

filter = np.zeros(shape=(s, t))

Wenn Sie alle Elemente des Variablenfilters so einstellen können, dass sie den Gaußschen Kernel darstellen, wenn $ u = 0 $, können Sie einen Gaußschen Filter $ g $ erstellen, der eine diskrete Version des Gaußschen Kernels mit $ u = 0 $ ist. Hier ist das Spaltenelement $ k $ row $ l $ von $ g $ $ g (k, l) $ = $ \ frac {1} {\ alpha} e ^ {- \ frac {l ^ {2} + k Als ^ {2}} {\ sigma ^ {2}}} $ festlegen. Hier ist $ \ alpha $ eine Konstante, die sich normalisiert, sodass die Summe $ 1 $ beträgt, wenn alle Elemente von $ g $ hinzugefügt werden.

Gaußsche Faltung unter Verwendung des Gaußschen Filters

Die folgende Gleichung ist eine Gaußsche Faltung unter Verwendung eines Gaußschen Filters. Dies wird als diskrete Gaußsche Faltung bezeichnet. Wenn wir uns im Folgenden einfach auf die Gaußsche Faltung beziehen, beziehen wir uns auf diese diskrete Gaußsche Faltung.

F(i, j) = \sum_{k=0}^{s}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) g(k, l)

• Originalbild von $ f $: $ m \ times n $
• $ g $: $ s \ times t $ Gaußscher Filter
• Ausgabebild von $ F $: $ m \ times n $

Wenn Sie ein Programm gehorsam gemäß der obigen Formel erstellen, sieht es wie folgt aus.

for k in range(s):
    for l in range(t):
        F[i, j] = f[i + k - int(s/2), j + l - int(t/2)] * g(k, l)

In diesem Fall sind $ s \ mal t $ Operationen erforderlich, um ein Pixel des Ausgabebildes $ F $ zu erhalten, und $ m \ mal n \ mal s \ mal t $, um alle Pixel des Ausgabebildes zu erhalten. Es erfordert eine Reihe von Operationen. Die Faltung mit einem $ 320 \ mal 240 $ Bild und einem $ 5 \ mal 5 $ Gaußschen Filter würde insgesamt $ 1.920.000 $ Operationen erfordern. Ob diese Anzahl von Berechnungen kritisch ist oder nicht, hängt von den Maschinenspezifikationen und der Anwendung ab, ist jedoch bei meinem MacBook Air (13 Zoll, Anfang 2015) von entscheidender Bedeutung.

Beschleunigen

Die Gaußsche Faltung hat die Eigenschaft, dass das Ausgabebild $ F $ der Gaußschen Faltung unter Verwendung des Gaußschen Filters von $ s \ times t $ in den nächsten beiden Schritten durch das Bild $ F_ {1} $ ausgegeben wird. Es gibt.

1. Falten Sie den eindimensionalen Gaußschen Filter von $ 1 \ mal t $ mit jeder Zeile des Originalbildes $ f $ und geben Sie das Bild $ F_ {0} $ aus.

Dies wird wie folgt bewiesen.

\begin{align}
F(i, j) &=\sum_{k=0}^{s}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) g(k, l)\\

&= \sum_{k=0}^{s}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) \frac{1}{\alpha}e^{-\frac{l^{2} + k^{2}}{\sigma^{2}}}\\

&= \sum_{k=0}^{s}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) \frac{1}{\alpha}e^{-\frac{l^{2}}{\sigma^{2}}}e^{-\frac{k^{2}}{\sigma^{2}}}\\

&=\frac{\alpha_{0}\alpha_{1}}{\alpha} \sum_{k=0}^{s}\frac{1}{\alpha_{1}}e^{\frac{-k^{2}}{\sigma^{2}}}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) \frac{1}{\alpha_{0}}e^{-\frac{l^{2}}{\sigma^{2}}}\\

&=\frac{\alpha_{0}\alpha_{1}}{\alpha} \sum_{k=0}^{s}\frac{1}{\alpha_{1}}e^{\frac{-k^{2}}{\sigma^{2}}}\sum_{l=0}^{t} f(i+k-[\frac{s}{2}], j+l-[\frac{t}{2}]) g_{0}(l)\\


&=\frac{\alpha_{0}\alpha_{1}}{\alpha} \sum_{k=0}^{s}\frac{1}{\alpha_{1}}e^{-\frac{k^{2}}{\sigma^{2}}} F_{0}(i, j)\\


&=\frac{\alpha_{0}\alpha_{1}}{\alpha} \sum_{k=0}^{s} F_{0}(i, j) g_{1}(k)\\


&=\frac{\alpha_{0}\alpha_{1}}{\alpha} F_{1}(i, j)
\end{align}

• $ g_ {0} $: $ 1 \ times t $ Gaußscher Filter
• $ g_ {1} $: $ s \ times 1 $ Gaußscher Filter
• $ \ alpha $: Normalisierungskonstante von $ g $
• $ \ alpha_ {0} $: Normalisierungskonstante von $ g_ {0} $
• $ \ alpha $: Normalisierungskonstante von $ g_ {1} $

Auf diese Weise beträgt die Anzahl der Operationen $ s \ mal m + t \ mal n $. Für ein $ 320 \ mal 240 $ Bild und eine $ 5 \ mal 5 $ Gaußsche Filterfaltung beträgt die Anzahl der Operationen $ 768.000 $. Durch die Beschleunigung kann die Anzahl der Vorgänge um $ 60 % $ reduziert werden.

Auf das Bild anwenden

Wenden wir tatsächlich die Gaußsche Faltung auf das Bild an. Dieses Mal werden Pillow, Numpy und Scipy verwendet. Das folgende Programm generiert ein Bild mit dem Maßstab $ \ sigma = 1.6 $ und ein Bild mit dem Maßstab $ \ sigma = 3.2 $.

from PIL import Image
import numpy as np
from scipy.ndimage.filters import gaussian_filter
from matplotlib import pyplot as plt

if __name__ == '__main__':
    orig_image = Image.open('lena.jpg').convert('L')
    orig_image = np.array(orig_image, dtype=np.uint8)

    sigmas = [1.6, 3.2]

    plt.subplot(1, len(sigmas) + 1, 1)
    plt.title('Orig')
    plt.imshow(orig_image, cmap='Greys_r')
    for i, sigma in enumerate(sigmas):
        plt.subplot(1, len(sigmas) + 1, 2 + i)
        plt.title('Sigma=%s' % sigma)
        plt.imshow(gaussian_filter(orig_image, sigma), cmap='Greys_r')
    plt.tight_layout()
    plt.savefig('gausian_convolution_2d_examples.png')
    plt.show()

Wenn das obige Programm ausgeführt wird, wird die folgende Abbildung erhalten.

OpenCV ist eine bekannte Bibliothek für die Arbeit mit Bildern. Jeder, der es installiert hat, kann es verwenden. Sie können auch versuchen, die Gaußsche Faltung selbst zu implementieren.

Bis zu diesem Punkt ist es möglich, ein Bild von beliebigem Maßstab $ \ sigma $ in Bezug auf das Originalbild zu erzeugen.

Gebäude Skalenraum 1. Oktave

Schließlich werden wir Scale-Space bauen. Die 1. Oktave im Kapiteltitel wird später beschrieben.

Bauablauf

1. Bestimmen Sie die Basisskala $ \ sigma_ {0} $.
2. Generieren Sie ein Bild mit der Skala $ k ^ {n} \ sigma $ für $ n = 0, ..., s $. $ s $ ist die Anzahl der Teilungen des Skalenraums der 1. Oktave. Es wird durch $ k = 2 ^ {1 / s} $ dargestellt.

Programm zum Erstellen der 1. Oktave im Scale-Space

from PIL import Image
import numpy as np
from scipy.ndimage.filters import gaussian_filter
from matplotlib import pyplot as plt


if __name__ == '__main__':
    orig_image = Image.open('lena.jpg').convert('L')
    orig_image = np.array(orig_image, dtype=np.uint8)

    sigma = 1.6
    s = 3
    k = np.power(2, 1/s)
    scale_space = []

    for n in range(s + 1):
        scale_space.append(gaussian_filter(orig_image, np.power(k, n) * sigma))

    for n, img in enumerate(scale_space):
        plt.subplot(1, len(scale_space), 1 + n)
        plt.title('Sigma=%s' % np.round(np.power(k, n) * sigma, 2))
        plt.imshow(img, cmap='Greys_r')
    plt.tight_layout()
    plt.show()

Wenn das obige Programm ausgeführt wird, werden vier Bilder mit Skalen von $ 1,6 $ bis $ 3,2 $ in der Variablen scale_space gespeichert und die folgende Abbildung wird angezeigt.

Der Raum, der aus den Bildern von $ k \ sigma $ bis $ 2k \ sigma $ besteht, wird als 1. Oktave bezeichnet.

Fourier-Transformations- und Abtastsatz

Bei der Erstellung der 2. Oktave und später müssen die Fourier-Transformation und der Abtastsatz erwähnt werden. Dieses Mal werde ich jedoch nicht tief gehen und es einfach reibungslos fließen lassen.

Fourier-Umwandlung

Die Fourier-Transformation transformiert ein Bild von einem Pixelbereich in einen Frequenzbereich.

1D Fourier-Transformationsformel

F(j\omega) = \int_{-\infty}^{\infty} f(x) e^{-j\omega x} dx

• $ f $: Positionsbereichssignal (z. B. Helligkeit des Lichts, das durch einen länglichen Spalt fällt)
• $ F $: Darstellung von $ f $ im Frequenzbereich
• $ \ omega : Winkelfrequenz ( 2 \ pi \ omega_ {0} $, wobei $ \ omega_ {0} $ die Frequenz ist)
• $e^{-j\omega x} = \cos(\omega x) - j \sin(\omega x) $
• $ j $: Imaginäre Einheit

Anwendungsbeispiel der eindimensionalen Fourier-Transformation

Versuchen wir die Fourier-Transformation durch FFT (Fast Fourier Transform) mit numpy, scipy, matplotlib. Im folgenden Programm beträgt die Abtastrate 20 und die Winkelfrequenz des ursprünglichen Signals $ 2 \ pi $.

import numpy as np
from scipy.fftpack import fft
from matplotlib import pyplot as plt


if __name__ == '__main__':
    sampling_rate = 20
    sampling_interval = 1.0/sampling_rate
    x = np.arange(0, 1, sampling_interval)

    omega0 = 1.0
    omega = 2.0 * np.pi * omega0
    f = np.sin(omega * x)

    F = fft(f)

    plt.plot(np.arange(-len(f)/2, len(f)/2), np.abs(np.concatenate((F[len(f)/2:], F[:len(f)/2]))), 'bo-')
    plt.show()

Wenn das obige Programm ausgeführt wird, wird die folgende Abbildung erhalten.

Aus dieser Figur ist ersichtlich, dass das ursprüngliche Signal $ f $ ein Signal mit einer Frequenz von $ 1 $ enthält. Es ist eine gute Idee, eine Fourier-Umwandlung für die Überlagerung mehrerer periodischer Funktionen durchzuführen.

[Ich werde später etwas ausführlicher schreiben]

Theorem zur eindimensionalen Signalabtastung

Der Abtasttheorem besagt: "Wenn die maximale Periode des im ursprünglichen Signal $ f $ enthaltenen Signals $ W $ ist, wenn die Abtastperiode $ T $ des ursprünglichen Signals $ T \ leq \ frac {1} {W} $ ist , Das ursprüngliche Signal $ f $ kann vollständig aus dem abgetasteten Signal $ f_ {d} $ wiederhergestellt werden. "

[Proof wird zu einem späteren Zeitpunkt hinzugefügt]

Experimentieren Sie mit dem Abtasttheorem für ein eindimensionales Signal

Die Abtastperiode sei $ 1/20 $. Wenn dann nach dem Abtasttheorem das Signal eine maximale Frequenz von $ 10 $ hat, sollten alle Frequenzinformationen erfolgreich durch Fourier-Umwandlung extrahiert werden.

Lassen Sie uns mit dem Programm unten überprüfen.

import numpy as np
from scipy.fftpack import fft
from matplotlib import pyplot as plt

if __name__ == '__main__':
    sampling_rate = 20
    sampling_interval = 1.0/sampling_rate
    x = np.arange(0, 1, sampling_interval)

    omega0s = [9, 10, 11, 30]

    for i, omega0 in enumerate(omega0s):
        omega = 2.0 * np.pi * omega0
        f = np.sin(omega * x)

        F = fft(f)

        plt.subplot(len(omega0s),  1,  1 + i)
        plt.plot(np.arange(-len(f)/2, len(f)/2), np.abs(np.concatenate((F[len(f)/2:], F[:len(f)/2]))), 'bo-')
        plt.title('Max frequency = %s' % omega0)
        plt.xlabel('Frequency')
        plt.ylabel('Amplitude spectrum')
    plt.tight_layout()
    plt.show()

Bei der Ausführung wird die folgende Abbildung erhalten. Aus diesem Ergebnis ist ersichtlich, dass die Frequenzinformationen erfolgreich mit dem Signal mit der maximalen Frequenz von 9 $ extrahiert werden können (Details werden später hinzugefügt).

Zweidimensionale Fourier-Transformation

[Postscript]

Gebäude nach der 2. Oktave

Downsampling

Überblick

[Postscript]

Nachweis des Downsamplings

[Postscript]

Build-Programm für die 2. Oktave

[Postscript]

Verweise

• Distinctive Image Features from Scale-Invariant Keypoints (David G. Lowe)
• Signalverarbeitung (Iwao Morishita, Hidefumi Obata)