Was ist ein Algorithmus zum erneuten Abtasten von einer variablen Rate zu einer festen Rate?

27

Ich habe einen Sensor, der seine Messwerte mit einem Zeitstempel und einem Wert meldet. Es werden jedoch keine Messwerte mit einer festen Rate generiert.

Ich finde es schwierig, mit den variablen Zinssätzen umzugehen. Die meisten Filter erwarten eine feste Abtastrate. Das Zeichnen von Diagrammen ist mit einer festen Abtastrate ebenfalls einfacher.

Gibt es einen Algorithmus zum Neuabtasten von einer variablen Abtastrate auf eine feste Abtastrate?

FigBug
quelle
Dies ist ein Crosspost von Programmierern. Mir wurde gesagt, dass dies ein besserer Ort ist, um zu fragen. programmers.stackexchange.com/questions/193795/…
FigBug
Was bestimmt, wann der Sensor einen Messwert meldet? Sendet es nur dann einen Messwert, wenn sich der Messwert ändert? Ein einfacher Ansatz wäre, ein "virtuelles Abtastintervall" (T) zu wählen, das gerade kleiner ist als die kürzeste Zeit zwischen den erzeugten Ablesungen. Speichern Sie am Algorithmus-Eingang nur den zuletzt gemeldeten Messwert (CurrentReading). Melden Sie am Algorithmusausgang alle T Sekunden die CurrentReading als "neue Probe", damit der Filter- oder Grafikdienst Messwerte mit einer konstanten Rate (alle T Sekunden) empfängt. Keine Ahnung, ob dies in Ihrem Fall ausreichend ist.
user2718
Es wird versucht, alle 5ms oder 10ms abzutasten. Da es sich jedoch um eine Aufgabe mit niedriger Priorität handelt, wird sie möglicherweise übersehen oder verzögert. Ich habe das Timing auf 1 ms genau. Die Verarbeitung erfolgt auf dem PC, nicht in Echtzeit. Ein langsamer Algorithmus ist also in Ordnung, wenn er einfacher zu implementieren ist.
FigBug
1
Haben Sie sich eine Fourier-Rekonstruktion angesehen? Es gibt eine Fourier-Transformation, die auf ungleichmäßig abgetasteten Daten basiert. Der übliche Ansatz besteht darin, ein Fourier-Bild zurück in einen gleichmäßig abgetasteten Zeitbereich zu transformieren.
Mbaitoff
3
Kennen Sie Merkmale des zugrunde liegenden Signals, das Sie abtasten? Wenn die Daten mit unregelmäßigen Abständen im Vergleich zur Bandbreite des zu messenden Signals immer noch eine relativ hohe Abtastrate aufweisen, funktioniert möglicherweise etwas Einfaches wie eine Polynominterpolation in ein Zeitraster mit gleichmäßigen Abständen.
Jason R

Antworten:

21

Der einfachste Ansatz besteht darin, eine Art Spline-Interpolation durchzuführen, wie Jim Clay vorschlägt (linear oder auf andere Weise). Wenn Sie jedoch den Luxus einer Stapelverarbeitung haben und besonders wenn Sie einen überbestimmten Satz ungleichmäßiger Proben haben, gibt es einen "perfekten Rekonstruktions" -Algorithmus, der äußerst elegant ist. Aus numerischen Gründen ist es möglicherweise nicht in allen Fällen praktikabel, aber es lohnt sich zumindest, das Konzept zu kennen. Ich habe es zum ersten Mal in diesem Artikel gelesen .

Der Trick besteht darin, Ihren Satz von ungleichmäßigen Abtastwerten als bereits aus gleichmäßigen Abtastwerten durch Sinusinterpolation rekonstruiert zu betrachten . Nach der Notation in der Zeitung:

y(t)=k=1Ny(kT)sin(π(tkT)/T)π(tkT)/T=k=1Ny(kT)sinc(tkTT).

Beachten Sie, dass dies einen Satz linearer Gleichungen liefert, eine für jede ungleichmäßige Stichprobe , wobei die Unbekannten die gleich beabstandeten Stichproben y ( k T ) sind , wie folgt:y(t)y(kT)

[y(t0)y(t1)y(tm)]=[sinc(t0TT)sinc(t02TT)sinc(t0nTT)sinc(t1TT)sinc(t12TT)sinc(t1nTT)sinc(tmTT)sinc(tm2TT)sinc(tmnTT)][y(T)y(2T)y(nT)].

nTmnn

Als ein Spielzeugbeispiel ist hier ein Vergleich (unter Verwendung von numpy ) zwischen der obigen Methode und der kubischen Spline-Interpolation auf einem leicht zitternden Gitter:

Sinc vs Cubic Spline Rekonstruktion ungleichmäßiger Proben

(Der Code zum Reproduzieren des obigen Diagramms befindet sich am Ende dieser Antwort.)

Alles, was gesagt wird, wäre für qualitativ hochwertige, robuste Methoden, beginnend mit etwas in einem der folgenden Papiere, wahrscheinlich angemessener:

A. Aldroubi und Karlheinz Grochenig, Uneinheitliche Abtastung und Rekonstruktion in verschiebungsinvarianten Räumen , SIAM Rev., 2001, Nr. 4, 585 & ndash; 620. ( pdf link ).

K. Grochenig und H. Schwab, Schnelle lokale Rekonstruktionsmethoden für ungleichmäßige Probenahme in verschiebungsinvarianten Räumen , SIAM J. Matrix Anal. Appl., 24 (2003), 899-913.

-

import numpy as np
import pylab as py

import scipy.interpolate as spi
import numpy.random as npr
import numpy.linalg as npl

npr.seed(0)

class Signal(object):

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def plot(self, title):
        self._plot(title)
        py.plot(self.x, self.y ,'bo-')
        py.ylim([-1.8,1.8])
        py.plot(hires.x,hires.y, 'k-', alpha=.5)

    def _plot(self, title):
        py.grid()
        py.title(title)
        py.xlim([0.0,1.0])

    def sinc_resample(self, xnew):
        m,n = (len(self.x), len(xnew))
        T = 1./n
        A = np.zeros((m,n))

        for i in range(0,m):
            A[i,:] = np.sinc((self.x[i] - xnew)/T)

        return Signal(xnew, npl.lstsq(A,self.y)[0])

    def spline_resample(self, xnew):
        s = spi.splrep(self.x, self.y)
        return Signal(xnew, spi.splev(xnew, s))

class Error(Signal):

    def __init__(self, a, b):
        self.x = a.x
        self.y = np.abs(a.y - b.y)

    def plot(self, title):
        self._plot(title)
        py.plot(self.x, self.y, 'bo-')
        py.ylim([0.0,.5])

def grid(n): return np.linspace(0.0,1.0,n)
def sample(f, x): return Signal(x, f(x))

def random_offsets(n, amt=.5):
    return (amt/n) * (npr.random(n) - .5)

def jittered_grid(n, amt=.5):
    return np.sort(grid(n) + random_offsets(n,amt))

def f(x):
    t = np.pi * 2.0 * x
    return np.sin(t) + .5 * np.sin(14.0*t)

n = 30
m = n + 1

# Signals
even   = sample(f, np.r_[1:n+1] / float(n))
uneven = sample(f, jittered_grid(m))
hires  = sample(f, grid(10*n))

sinc   = uneven.sinc_resample(even.x)
spline = uneven.spline_resample(even.x)

sinc_err   = Error(sinc, even)
spline_err = Error(spline, even)

# Plot Labels
sn = lambda x,n: "%sly Sampled (%s points)" % (x,n)
r  = lambda x: "%s Reconstruction" % x
re = lambda x: "%s Error" % r(x)

plots = [
    [even,       sn("Even", n)],
    [uneven,     sn("Uneven", m)],
    [sinc,       r("Sinc")],
    [sinc_err,   re("Sinc")],
    [spline,     r("Cubic Spline")],
    [spline_err, re("Cubic Spline")]
]

for i in range(0,len(plots)):
    py.subplot(3, 2, i+1)
    p = plots[i]
    p[0].plot(p[1])

py.show()
Datageist
quelle
tj=jT
Soweit ich weiß, handelt es sich bei der Frage des OP um Proben, die fallengelassen und / oder verzögert werden. Diese Methode ist im Grunde genommen nur ein überbestimmtes Gleichungssystem, daher werden abgelegte Stichproben nur als Unbekannte angezeigt (nicht als Datenpunkte mit dem Wert 0). Oder ist es vielleicht nicht das, wonach du fragst?
Datageist
tjj,yjjJy0=0yj
Wenn die Abtastraten genau identisch sind (mit fehlenden Punkten), ist die Interpolationsmatrix dünn (da jeder Ausgang nur von einem Eingang abhängt). Im Allgemeinen muss die durchschnittliche Abtastrate der ungleichmäßigen Abtastwerte größer sein als die gleichmäßige Rekonstruktionsrate. Mit anderen Worten müssten Sie mit einer geringeren Rate rekonstruieren, um "die Lücken zu füllen" (T> 1 für Ihr Beispiel). Ich verstehe deinen Standpunkt.
Datageist
2
Antworten wie diese sind Gold wert.
Ahmed Fasih
6

Dies klingt nach einem Problem der asynchronen Abtastratenkonvertierung. Um von einer Abtastrate in eine andere zu konvertieren, können wir die kontinuierliche Zeitdarstellung des Signals durch Ausführen einer Sinusinterpolation berechnen und dann mit unserer neuen Abtastrate erneut abtasten. Was Sie tun, ist nicht viel anders. Sie müssen Ihr Signal neu abtasten, um festgelegte Abtastzeiten zu erhalten.

Das kontinuierliche Zeitsignal kann berechnet werden, indem jede Probe mit einer sinc-Funktion gefaltet wird. Da die sinc-Funktion auf unbestimmte Zeit fortgesetzt wird, verwenden wir etwas Praktischeres wie eine fensterförmige sinc mit einer praktischen endlichen Länge. Der schwierige Teil ist, dass, da sich Ihre Samples mit der Zeit bewegen, beim Resampling möglicherweise für jedes Sample ein Sinc mit einem anderen Phasenversatz verwendet werden muss.

Kontinuierliches Zeitsignal vom abgetasteten Signal:

x(t)=n=x[n]sinc(tnTsTs)

Ts

x(t)=n=x[n]sinc(tnTs[n]Ts[n])

Daraus können Sie das Signal neu abtasten:

y[n]=x(nTns

Tns

Alles zusammen ergibt:

y[m]=n=x[n]sinc(mTnsnTs[n]Ts[n])

Da dies nicht kausal oder nachvollziehbar ist, kann die sinc-Funktion durch eine Funktion der endlichen Unterstützung ersetzt und die Summationsgrenzen entsprechend angepasst werden.

Sei kernel (t) eine windowed sinc oder eine ähnliche Funktion der Länge 2k, dann:

y[m]=n=kkx[n]kernel(mTnsnTs[n]Ts[n])

Ich hoffe, das hilft ..., aber ich habe vielleicht einen Fehler gemacht und es könnte ein bisschen matheintensiv sein. Ich würde empfehlen, die Konvertierung der Abtastrate zu untersuchen, um weitere Informationen zu erhalten. Vielleicht könnte jemand anderes hier auch eine bessere Erklärung oder Lösung geben.

Jacob
quelle
Die Verwendung einer sinc-Funktion zum Rekonstruieren einer kontinuierlichen Version eines Signals erfordert, dass die Abtastwerte gleich beabstandet sind, sodass sich die sinc-Funktion an den Abstand beliebiger Abtastwerte anpassen muss. Könnte ziemlich schwierig zu implementieren sein.
user2718
Ja, dies wäre nicht sehr effizient, um genau das zu tun, was hier zu sehen ist. Es würde die Berechnung neuer Kernel-Koeffizienten für jede unterschiedliche Abtastzeit erfordern. Es könnte jedoch eine Sammlung von mehreren Kerneln berechnet und die Zeit auf einen von diesen quantisiert werden. In Bezug auf den Quantisierungsfehler würde es einen Leistungseinbruch geben.
Jacob
Sie können auch eine einzelne Nachschlagetabelle vorberechnen und zwischen den Punkten dieser Nachschlagetabelle interpolieren.
JMS
5

Ich denke, Jacobs Antwort ist sehr praktikabel.

Eine einfachere Methode, die hinsichtlich der Einführung von Verzerrungen wahrscheinlich nicht ganz so gut ist, ist die Polynominterpolation. Ich würde entweder eine lineare Interpolation (einfach, in Bezug auf die Signalleistung nicht so gut) oder kubische Splines (immer noch nicht zu hart, bessere Signalleistung) verwenden, um jederzeit Samples aus Ihren willkürlichen Zeitsamples zu erstellen.

Jim Clay
quelle
1
Ihre Antwort scheint viel einfacher umzusetzen zu sein als die von Jacob, also habe ich mich zuerst damit befasst. Es scheint zu funktionieren, aber ich habe noch keine vollständigen Tests durchgeführt.
FigBug
1
@FigBug -Wenn Sie Zeit haben, fügen Sie einen Kommentar zu Ihrer endgültigen Lösung hinzu.
user2718
2


Nnear

Nnear
y1y1
y0(y1+y1)/2
[xi,yi]xi=0
y0yi
[xi,yi]
a+bxy0a
Man kann Quadrate, Würfel, Sinus-Cosinus ... auf die gleiche Weise einpassen.



2πftf


Die lineare Interplation mit 4 oder 6 oder 8 Nachbarn ist möglicherweise für Ihre Daten ausreichend.
Ich würde vorschlagen, mit einer Methode zu beginnen, die Sie gründlich verstehen, bevor Sie in Splines eintauchen.


Eine andere, ganz andere Methode ist die inverse Distanzgewichtung . Es ist einfach zu implementieren (siehe idw-interpolation-with-python unter SO), funktioniert auch in 2D-3D und höher, ist aber theoretisch schwer zu analysieren.

(Offensichtlich kann KEINE einzelne Interpolationsmethode möglicherweise zu den Millionen Kombinationen von
[Signal, Rauschen, Fehlermetrik, Testfunktion] passen , die in der Realität auftreten.
Es gibt weltweit mehr Methoden mit mehr Knöpfen als Testfunktionen.
Dennoch eine Galerie von Methoden und Testfunktionen können hilfreich sein.)

denis
quelle
1

Wenn Sie mit matlab arbeiten, können Sie dies mit timeseries tun.

time  % is your starting vector of time

data % vector of data you want to resample 

data_TS = timeseries(data,time); % define the data as a timeseries 

new_time = time(0):dt:time(end); % new vector of time with fixed dt=1/fs

data_res = resample(data_TS,new_time); % data resampled at constant fs
Rhei
quelle
0

Bevor Sie sich mit exotischer Verarbeitung befassen, können Sie etwas Einfaches wie dieses ausprobieren (Pseudocode - keine Interpolation, aber das könnte hinzugefügt werden).

TimeStamp[]  //Array of Sensor TimeStamps -NULL terminated – TimeStamp[i] corresponds to Reading[i]
Reading[]      //Array of Sensor Readings       -NULL terminated

AlgorithmOut   //Delimited file of of readings in fixed sample time (5ms) 
CurrentSavedReading = Reading[0]

SampleTime=TimeStamp[0] //ms virtual sample time, 5ms fixed samples

i = 0 // loop index
While(TimeStamp[i] != NULL)
{
   FileWrite (CurrentSavedReading, AlgorithmOut)//write value to file
   SampleTime = SampleTime + 5//ms
   if(SampleTime > TimeStamp[i])
   {
      i++
      CurrentSavedReading = Reading[i]
   }
}
user2718
quelle
0

Die Antwort von Datageist ist richtig, die von Jacob nicht. Eine einfache Möglichkeit, dies zu überprüfen, besteht darin, dass der vom Datageisten vorgeschlagene Algorithmus garantiert durch die ursprünglichen Abtastwerte interpoliert (wobei eine unendliche numerische Genauigkeit vorausgesetzt wird), während dies bei Jacobs Antwort nicht der Fall ist.

  • Für den Fall der einheitlichen Abtastung ist der Satz von Sinc-Funktionen orthogonal: Wenn jede verschobene Sinc-Funktion über die Eingangsabtastwerte diskretisiert wird, bilden sie eine unendliche Identitätsmatrix. Dies liegt daran, dass sin (npi) / (npi) für alle n außer n = 0 Null ist.
  • Diese Eigenschaft kann jedoch nicht einfach auf den ungleichmäßigen Fall extrapoliert werden: Ein ähnlicher Satz von Sinusfunktionen, der über die Eingangsabtastwerte diskretisiert wird, ergibt eine nichttriviale Matrix. Daher sind die Beiträge von umgebenden Abtastwerten nicht Null, und die Rekonstruktion interpoliert nicht länger durch die Eingangsabtastwerte.
pvv
quelle