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

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?

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) = \sum_{k=1}^{N}{y(kT)\frac{\sin(\pi(t - kT)/T)}{\pi(t - kT)/T}} = \sum_{k=1}^{N}{y(kT)\mathrm{sinc}(\frac{t - kT}{T})}.$$

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)$

$$\begin{bmatrix} y(t_0) \\ y(t_1) \\ \cdots \\ y(t_m) \end{bmatrix} = \begin{bmatrix} \mathrm{sinc}(\frac{t_0 - T}{T}) & \mathrm{sinc}(\frac{t_0 - 2T}{T}) & \cdots & \mathrm{sinc}(\frac{t_0 - nT}{T}) \\ \mathrm{sinc}(\frac{t_1 - T}{T}) & \mathrm{sinc}(\frac{t_1 - 2T}{T}) & \cdots & \mathrm{sinc}(\frac{t_1 - nT}{T}) \\ \cdots & \cdots & \cdots &\cdots \\ \mathrm{sinc}(\frac{t_m - T}{T}) & \mathrm{sinc}(\frac{t_m - 2T}{T}) & \cdots & \mathrm{sinc}(\frac{t_m - nT}{T}) \end{bmatrix} \begin{bmatrix} y(T) \\ y(2T) \\ \cdots \\ y(nT) \end{bmatrix}.$$

$n$$T$$m$$n$$n$

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:

(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()

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) = \sum\limits_{n=-\infty}^\infty x[n]sinc({t-nT_s\over T_s})$

$T_s$

$x(t) = \sum\limits_{n=-\infty}^\infty x[n]sinc({t-nT_s[n]\over T_s[n]})$

Daraus können Sie das Signal neu abtasten:

$y[n] = x(nT_{ns}$

$T_{ns}$

Alles zusammen ergibt:

$y[m] = \sum\limits_{n=-\infty}^\infty x[n]sinc({mT_{ns}-nT_s[n]\over T_s[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] = \sum\limits_{n=-k}^k x[n]kernel({mT_{ns}-nT_s[n]\over T_s[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.

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.

$Nnear$

$Nnear$
$y_{-1}$$y_1$
$\qquad$$y_0 \sim (y_{-1} + y_1) / 2$
$[x_i, y_i]$$x_i = 0$
$\qquad y_0 \sim$$y_i$
$[x_i, y_i]$
$\qquad$$a + b x$$y_0 \sim a$
$\qquad$ Man kann Quadrate, Würfel, Sinus-Cosinus ... auf die gleiche Weise einpassen.

$2 \pi f t$$f$

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.)

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

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]
   }
}

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.