resampling, Interpolation matrix

Ich versuche zu interpolieren einige Daten für den Zweck des Zeichnens. Zum Beispiel, gegeben die N Daten-Punkte, ich möchte in der Lage sein zum generieren eines "smooth" - plot, der aus 10*N oder so interpolierten Datenpunkte.

Mein Ansatz ist die Erzeugung einer N-by-10 - *N-matrix und berechnen Sie das innere Produkt der ursprünglichen Vektor und die matrix I erzeugt, woraus sich ein 1-by-10 - *N-Vektor. Ich habe bereits ausgearbeitet, die Mathematik, die ich verwenden möchten, für die interpolation, aber mein code ist ziemlich langsam. Ich bin Recht neu in Python, also ich habe die Hoffnung, dass einige der Experten hier können mir einige Ideen, wie ich versuchen kann, um speed up my code.

Ich denke, Teil des Problems ist, dass die Generierung der matrix erfordert 10*N^2 ruft die folgende Funktion:

def sinc(x):
    import math
    try:
        return math.sin(math.pi * x) / (math.pi * x)
    except ZeroDivisionError:
        return 1.0

(Diese kommt von sampling-Theorie. Im Grunde genommen bin ich versucht, neu zu erstellen ein signal von seiner Proben, und upsample es zu einer höheren Frequenz.)

Die matrix wird erzeugt, indem die folgenden:

def resampleMatrix(Tso, Tsf, o, f):
    from numpy import array as npar
    retval = []

    for i in range(f):
        retval.append([sinc((Tsf*i - Tso*j)/Tso) for j in range(o)])

    return npar(retval)

Ich überlege mir, brechen Sie die Aufgabe in kleinere Stücke, weil ich nicht wie die Idee, ein N^2 matrix sitzen im Speicher. Ich könnte wahrscheinlich machen 'resampleMatrix' in eine generator-Funktion und machen das innere Produkt Zeile für Zeile, aber ich glaube nicht, dass beschleunigt mein code viel, bis ich starten paging Sachen in und aus dem Speicher.

Vielen Dank im Voraus für Eure Vorschläge!

ganz abgesehen von dem, was Sie zu tun versuchen, mit Ihrem code, die Idee, dass man nur interpolieren extra-Punkte mit ist keine generative Modell der Daten ist falsch. wenn Sie dies tun wollen in jeder Art von statistisch prinzipiellen Weg, die Sie brauchen, um eine Art regression. siehe en.wikipedia.org/wiki/Generative_model
Es sieht aus wie Phil will nur noch eine interpolation für das zeichnen. Solange die interpolierten Punkte werden nicht für andere Zwecke verwendet, sehe ich nicht, warum würde man brauchen, ein generatives Modell
Irgendein besonderer Grund, warum, den Sie verwenden möchten sinc-interpolation gegeben, dass es eine O(N^2) Algorithmus und andere Methoden, wie beispielsweise kubische spline sind nur O(N)?
Das Modell der Daten ist, dass es abgetastet wurde nach der en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem. Können Sie wiederherstellen, genau durch die Verwendung von sinc-Funktionen.
numpy hat bereits eine sinc() - Funktion, durch die Art und Weise. docs.scipy.org/doc/numpy/reference/generated/numpy.sinc.html

InformationsquelleAutor Phil | 2009-12-05

9

Dies ist upsampling. Sehen Helfen Sie mit resampling/upsampling für einige Beispiel-Lösungen.

Einen schnellen Weg, dies zu tun (für die offline-Daten, wie z.B. Plotten Anwendung) ist die Verwendung von FFTs. Dies ist, was SciPy native resample() - Funktion tut. Es geht von einem periodischen signal, obwohl, so ist es nicht genau das gleiche. Sehen diese Referenz:

Hier ist das zweite Problem bezüglich der Zeit-Domäne Echtzeit-signal-interpolation, und es ist eine große Sache in der Tat. Diese exakte interpolation Algorithmus liefert korrekte Ergebnisse nur, wenn die original-x(n) die Sequenz ist periodisch in seiner vollen Zeitintervall.

Ihre Funktion übernimmt das signal samples sind alle 0 außerhalb des definierten Bereichs, so dass die beiden Methoden wird das abweichen vom Mittelpunkt Weg. Wenn Sie pad das signal mit vielen Nullen ersten, wird es produzieren eine sehr enge Ergebnis. Es gibt mehrere Nullen über den Rand der plot hier nicht gezeigt:

Kubische interpolation nicht korrekt für die Neuberechnung Zwecke. Dieses Beispiel ist ein Extremfall (in der Nähe der sampling-Frequenz), aber wie Sie sehen können, kubische interpolation ist nicht einmal in der Nähe. Für tiefere Frequenzen sollte es ziemlich genau.
- Danke für die Antwort! @endolith ich bemerkte Ihren Kommentar unten. Du hast Recht, ich hätte meine Frage deutlicher von Anfang an.
InformationsquelleAutor endolith
3

Wenn Sie wollen, interpolieren von Daten in einer ganz Allgemeinen und schnellen Weg, splines oder Polynome sind sehr nützlich. Scipy hat die scipy.interpolieren-Modul, was sehr hilfreich ist. Finden Sie viele Beispiele in den offiziellen Seiten.

InformationsquelleAutor Eric O Lebigot
1

Ihre Frage ist nicht ganz klar; man versucht zu optimieren, der code, den Sie geschrieben, richtig?

Re-writing sinc soll dies gerne beschleunigen Sie erheblich. Diese Implementierung vermeidet die überprüfung, dass das math-Modul importiert wird bei jedem Anruf, nicht Attribut-Zugriff drei mal, und ersetzt die Ausnahmebehandlung mit einem bedingten Ausdruck:
```
from math import sin, pi
def sinc(x):
    return (sin(pi * x) / (pi * x)) if x != 0 else 1.0
```
Könnte man auch versuchen Sie zu vermeiden die Erstellung der matrix zweimal (und halten es zweimal parallel im Speicher) durch die Schaffung eines numpy.array direkt (nicht aus einer Liste von Listen):
```
def resampleMatrix(Tso, Tsf, o, f):
    retval = numpy.zeros((f, o))
    for i in xrange(f):
        for j in xrange(o):
            retval[i][j] = sinc((Tsf*i - Tso*j)/Tso)
    return retval
```
(ersetzen xrange mit Palette auf Python 3.0 und höher)

Schließlich können Sie erstellen, die Zeilen mit numpy.arange, ebenso wie der Aufruf von numpy.sinc auf jede Zeile oder sogar auf die gesamte matrix:
```
def resampleMatrix(Tso, Tsf, o, f):
    retval = numpy.zeros((f, o))
    for i in xrange(f):
        retval[i] = numpy.arange(Tsf*i / Tso, Tsf*i / Tso - o, -1.0)
    return numpy.sinc(retval)
```
Diese sollten deutlich schneller als die ursprüngliche Implementierung. Versuchen Sie verschiedene Kombinationen von diesen Ideen und testen Ihre Leistung, sehen, was funktioniert am besten!
- "ersetzt die Ausnahmebehandlung mit einem bedingten Ausdruck", aber Ausnahmen sind schneller als Vergleichsoperatoren in python. es wäre auch schneller pi*x einmal und verwenden Sie es zweimal, richtig?
- Es ist nicht wahr, dass "Ausnahmen sind schneller als Vergleichsoperatoren in Python", es hängt wirklich davon ab, wie oft die außergewöhnlichen Zustand passiert. Sowieso, das sollte ganz unerheblich ist hier im Vergleich zu Vermeidung der import-und Attribut-lookup für jede Funktion aufrufen. Nicht mit try/außer hier ist eine Frage von Stil und code-Klarheit.
- Für pi * x ich bin mir nicht sicher, dass die Schaffung einer neuen lokalen variable zu vermeiden, eine single-float-Multiplikation von Vorteil wäre. Dies ist eines jener Dinge, die Sie gerade haben, um zu testen. Wieder, obwohl, das ist wirklich unbedeutend im Vergleich zu den anderen änderungen, die ich vorgeschlagen, die hätte eine große Wirkung.
- Ja, Ausnahmen sind schneller als die Vergleichsoperatoren, so dass, wenn Sie passieren, selten mit code Sie werden schneller, zu. In diesem Fall wird der bedingte wird nur geschehen, wenn die Eingabe wird genau dann 0, was sehr selten ist, so ist es schneller die Ausnahme. In einem quick-test, Ausnahme-version ist etwa 30% schneller bei zufälligen Eingaben ist, und mit pix = pi*x Geschwindigkeiten bis etwa 40%, zu.
InformationsquelleAutor taleinat
1

Ich bin mir nicht ganz sicher, was Sie zu tun versuchen, aber es gibt einige Beschleunigungen, die Sie tun können, um die matrix zu erstellen. Braincore-Vorschlag zu verwenden numpy.sinc ist ein Erster Schritt, aber der zweite ist zu erkennen, dass die numpy-Funktionen arbeiten möchten, auf numpy arrays, wo Sie können do-Schleifen in C speen, und kann tun es schneller als auf den einzelnen Elementen.
```
def resampleMatrix(Tso, Tsf, o, f):
    retval = numpy.sinc((Tsi*numpy.arange(i)[:,numpy.newaxis]
                         -Tso*numpy.arange(j)[numpy.newaxis,:])/Tso)
    return retval
```
Der trick ist, dass durch die Indizierung der aranges mit numpy.newaxis, numpy wandelt das array mit Form i mit Form-i x 1, und das array mit Form j Form, 1 x j. Bei der Subtraktion Schritt, numpy wird "broadcast" jeden input zu handeln als ich x j-förmigen array und das tun die Subtraktion. ("Broadcast" ist numpy Begriff, was die Tatsache widerspiegelt keine weitere Kopie gemacht wird, die zum dehnen des i x 1 i x j.)

Nun die numpy.sinc iterieren über alle Elemente in kompilierter code, viel schneller als jede for-Schleife, die Sie schreiben konnte.

(Es gibt eine zusätzliche speed-up verfügbar, wenn Sie die division vor Subtraktion, vor allem, da in der letzteren die Teilung bricht die Multiplikation.)

Der einzige Nachteil ist, dass Sie nun bezahlen Sie für eine extra-Nx10*N array für die Differenz. Dies könnte ein dealbreaker, wenn N groß ist und der Speicher ist ein Problem.

Sonst, sollten Sie in der Lage sein, dies zu schreiben, mit numpy.convolve. Von dem, was wenig ich nur gelernt, über die sinc-interpolation, ich würde sagen, Sie wollen so etwas wie numpy.convolve(orig,numpy.sinc(numpy.arange(j)),mode="same"). Aber ich bin wahrscheinlich falsch über die Besonderheiten.
- Ich bin versucht, eine Faltung, so dass ich denke, numpy.convolve könnte die richtige Richtung zu nehmen.
InformationsquelleAutor AFoglia
1

Wenn Ihr nur Interesse ist, zu " erzeugen Sie eine "glatte" plot' ich würde gehen Sie einfach mit einem einfachen Polynom-spline-Kurve Passform:

Für zwei benachbarte Datenpunkte die Koeffizienten des Dritten Grades Polynom-Funktion berechnet werden kann aus den Koordinaten für die Datenpunkte und die beiden Punkte Links und rechts (ohne Punkte-Grenze.) Dies erzeugt Punkte auf eine schöne glatte Kurve mit einer kontinuierlichen erste dirivitive. Es ist ein straight-forward-Formel für die Umwandlung von 4-Koordinaten auf 4 Polynom-Koeffizienten, aber ich möchte nicht zu berauben Sie der Spaß, den suchen es ;o).

InformationsquelleAutor Don O'Donnell

Hier ein minimal-Beispiel für eine 1d-interpolation mit scipy-nicht so viel Spaß wie die Neuerfindung, aber.

Das Grundstück sieht aus wie sinc, das ist kein Zufall:
versuchen Sie google-spline-Resampling "Ungefähre sinc".

(Vermutlich weniger local /mehr Hähne ⇒ bessere Annäherung,
aber ich habe keine Ahnung, wie lokale UnivariateSplines sind.)

""" interpolate with scipy.interpolate.UnivariateSpline """
from __future__ import division
import numpy as np
from scipy.interpolate import UnivariateSpline
import pylab as pl

N = 10 
H = 8
x = np.arange(N+1)
xup = np.arange( 0, N, 1/H )
y = np.zeros(N+1);  y[N//2] = 100

interpolator = UnivariateSpline( x, y, k=3, s=0 )  # s=0 interpolates
yup = interpolator( xup )
np.set_printoptions( 1, threshold=100, suppress=True )  # .1f
print "yup:", yup

pl.plot( x, y, "green",  xup, yup, "blue" )
pl.show()

Hinzugefügt feb 2010: siehe auch basic-spline-interpolation-in-ein-paar-Zeilen-von-numpy

InformationsquelleAutor denis

0

Kleine Verbesserung. Verwenden Sie den built-in numpy.sinc(x) Funktion läuft in der kompilierten C-code.

Mögliche größere Verbesserung: Kann man die interpolation on the fly " (wie das Plotten erfolgt)? Oder sind Sie gebunden an einer Plot-Bibliothek, die akzeptiert nur eine matrix?
- Danke für den Kommentar. Seltsam, der code läuft etwa 10x langsamer, wenn ich verwendet numpy.sinc(x). Ich bin überrascht!
- Der Plot Stück die Beschreibung war nur für illustrative Zwecke. Ich bin nicht wirklich besorgt über die Zeichnung der Handlung, nur bei der tatsächlichen Berechnung schneller. Letztendlich wird sich dies eher als ein "on-the-fly" Typ "task", da werde ich die Verarbeitung der Scheiben eines großen Datensatzes. Aber wie es jetzt aussieht, läuft das durch, was ich denken würde, die kleinste nützlich Scheibe der Daten erfordert mehr Zeit als es dauert, den nächsten Datensatz zu kommen...
- Was sind Tso und Tsf?
- Tso = Initial Sample Time Tsf = Letzte Probe Zeit. Also, wenn ich starten mit ein gesampeltes signal bei 1kHz, und ich will generieren 10 interpolierte Punkte für jede Probe (die neue Samplefrequenz 10 KHz), Tso = 0.001, Tsf = 0.0001.
InformationsquelleAutor BrainCore
0

Ich empfehlen, dass Sie überprüfen Sie Ihren Algorithmus, so ist es ein nicht-triviales problem. Konkret schlage ich vor, erhalten Sie Zugriff auf den Artikel "Funktion Plotten Mit Konischen Splines" (IEEE Computer Graphics and Applications) von Hu und Pavlidis (1991). Ihren Algorithmus-Implementierung erlaubt die adaptive sampling der Funktion, so dass die rendering-Zeit ist kleiner als die mit regelmäßig beabstandeten Ansätze.

Den abstract folgt:

Es wird ein Verfahren vorgestellt, wobei angesichts der
mathematische Beschreibung eines
Funktion, eine konische spline-Angleichung
der plot der Funktion erzeugt wird.
Konische Bögen wurden so gewählt, dass das
primitive Kurven, weil es
einfache inkrementelle algorithmen zeichnen
für die Kegelschnitte, die sich schon in einigen
Gerätetreiber, und es gibt einfache
algorithmen für die lokale Näherungen durch
Kegelschnitte. Eine split-und-merge-Algorithmus
für die Auswahl der Knoten, adaptiv,
nach Analyse der Form
original-Funktion basierend auf seiner
first-order Derivate
eingeführt.
- Mein Algorithmus kommt aus der stichprobentheorie. Im Grunde genommen bin ich versucht, neu zu erstellen ein signal von seiner Proben, und resample es bei einer höheren Frequenz. Für die Zwecke der Verschwörung bin ich sicher, dass meine Lösung nicht die beste Methode...
- Sie soll gesagt haben, dass in der Frage
InformationsquelleAutor Escualo

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.