Spline Linien zeichnen

[Reinhard Kern]

Zitat von bitboy0:

...es gibt nun folgende Möglichkeit:

1. Es fehlt die "Bergkuppe" der Wellenform ... also wie digitales Klipping.
2. Es fehlt ein Teil des "Berghanges" der Wellenform.
3. es fehlt ein Teil des "Berghanges" der Wellenform in dem die Kurve noch zwei mal die Richtung geändert hat.
...

Hallo,

3 kannst du weglassen - du weisst ja bei einer Rekonstruktion nicht, ob im fehlenden Abschnitt zusätzliche Extrema vorhanden waren, also kannst du zwischen 2 und 3 nicht unterscheiden (und noch dazu könnten es statt 2 auch 4,6,8... Extrema sein). Die Rekonstruktion kann daher nur den einfachsten und daher wahrscheinlichsten Fall berücksichtigen. Übrigens gilt Equivalentes auch für Fall 1: es könnten genausogut zusätzliche Kuppen/Täler vorhanden sein. Das könnte man nur abschätzen durch eine Fourieranalyse der Daten vor und nach dem Fehler, z.B. könnte man eine durchegehende Sinusschwingung ergänzen. Aber das ist ein ganz anderes Thema aus einer anderen Schwierigkeitsklasse.

Gruss Reinhard

[alzaimar]

Regression oder Ausgleichsplnes. Allerdings kannst Du Regression knicken, denn Du kennst die Stammfunktion nicht.

[bitboy0]

Die genaue Rekonstruktion der fehlenden Teile ist nicht nötig/machbar in meinen Augen. Worum es geht ist die Glättung der Kurve um die extrem multifrequenten 90°-Ecken in der Wellenform zu tilgen. Ich habe testweise mal ein paar Sekunden Material per Hand so bearbeitet das die Kurve optisch unaufällig war... so wie es dann klingt wäre es akzeptabel für mich.

zu 3. Dadurch das ich vor und nach der Fehlstelle jeweils einen Punkt UND die Steigung habe müsste doch eine Bezierkurve ebenfalls gezwungen sein S-förmig zu verlaufen und damit der fehlenden Form nahe zu kommen, oder? Die Kurve muss ja an der Fehlstelle zunächst mit der Steigung starten die dort von den jeweils vorhandenen Punkten vorgegeben wird.

Und wie gesagt: Ich benötige wirklich eine Funktion die ich programmieren kann ... mein Mathe ist/war nicht gut genug um sowas selber zu machen. Wenn z.B. der C++ code aus dem Beispiel weiter oben der richtige für meinen Zweck ist dann kann ich den sicher in Delphi übertragen... aber sowas in der Art bräuchte ich als Mathe-Blödmann dann doch

gruß

PS: bei 44.1 kHz Sampling-Frequenz sind 5-20 Samples grade mal 0,11-0,44 ms. Obwohl es sich um recht hochwertige Aufnahmen von einigen klassischen Konzerten handelt sind die Frequenzen von ca. 2.2 bis 8.8Khz die in dem Abschnitt für weitere Extrema sorgen könnten gar nicht so "laut" das es für so eine kurze Zeit wirklich auffällt wenn sie fehlen. Viel schlimmer sind die prasselnden und klickenden Laute der Fehlstellen... manchmal kommen davon bis zu 30 in einer Sekunde vor! (immer im Abstand von 30ms)

[Medium]

Zitat von alzaimar:

Hallo Medium, meine Demo verwendet kein Polynom N-1.ten Grades sondern N-1 Polynome 3.ten Grades, da kann nur dann etwas 'überschwingen', wenn die Punkte auseinanderiegen und(!) eine starker Wechsel in der 1.Ableitung zu verzeichnen ist (z.B. erst geradeaus, dann steil nach oben). Wenn man innerhalb des Wechsels zu wenig Punkte hat, holt der Spline quasi von unten Schwung...

Ah okay, dann ist es genau kubische Interpolation. Gerne genommen, weil schnell und einfach, und nur in wenigen o.g. Ausnahmefällen zu merkbaren "Unschönheiten" führt. Las sich erst so, als würdest du Polynome Nten Grades hernehmen

@bitboy0: In der Musik wird wenn ich mich recht erinnere ganz gerne Hermite-Interpolation verwendet. Diese nutzt wie auch die kubische Interpolation 4 Punkte: Die 2 Punkte zwischen denen interpoliert werden soll, und den Punkt davor bzw. danach, womit an den Grenzen des zu interpolierenden Intervalls ein (theoretisch) differenzierbarer Durchgang erreicht wird, also per math. Definition "glatt".
Die Extrema bei einem S-förmigen Abschnitt werden hierbei in der Regel relativ flach, da sie im allgemeinen Fall eine bessere Näherung sind, als starkes Schwingen. (Der Verlauf lässt sich bei diesem Verfahren durch 2 Parameter auch noch feineinstellen, jedoch existieren in deinem Fall keine Informationen dazu, ob und wie diese eine bessere Abbildung erzeugen würden. Daher würde kubische Interpolation fast schon reichen - also das, was alzaimar weiter oben geposted hat, bzw. auch in dem von mir oben verlinkten Artikel beschrieben wird.)
Wenn so ein Bereich wie der letzte in deinem Beispiel wegfällt, ist eigentlich schon zu viel Information verloren um das brauchbar anzunähern. Hier kannst du nur noch einen "Flicken" anbieten, der wenigstens rechteckige Verläufe abmildert.

In deinem Fall liegt das eigentliche Problem denke ich woanders als bei der bloßen Interpolation. Nämlich bei der Wahl der zwei äussersten Punkte für die Interpolation. Wenn du z.B. mit einer kleineren Bit-Auflösung aufnimmst, kann es dir schnell passieren, dass durch die Quantisierung die direkten Nachbarpunkte den gleichen Wert haben, wodurch die errechnete Kurve wieder unschön wird. Umgehen kann man das z.B., in dem man nicht die unmittelbaren Nachbarwerte nimmt, sondern welche die ein paar wenige Samples entfernt sind. Das hat nun wieder das Problem, dass selbst durch kaum hörbar leises Rauschen immernoch eine gewisse Unsicherheit besteht, ebenso wie durch extrem hohe Frequenzen. Man kann nun noch einen Mittelwert der je nächsten N Nachrbarn nehmen, wobei dann fast sicher ist, dass der Durchgang an der Grenze einen leichten Knick macht - aber wenigstens dürfte die großbe Richtung nun immer passen.
In wie weit diese Probleme nachher überhaupt relevant sind, hängt sehr stark von der Qualität der Aufnahme ab. Also Auflösung (in der Amplitude), und auch die Rohaufnahme, sowie der bisher auf die Musik angewandten Übertragungswege, Signal-Rausch-Abstände etc. pp. usw. usf.
Bei einer "perfekten" Aufnahme kannst du den letzten Absatz hier ganz vergessen, aber wer hat sowas schon =)

[bitboy0]

Danke für die sehr ausführliche Antwort!

Es handelt sich um Aufnahmen bei denen zwei relativ gute Mikrophone direkt am DAT-Recorder angeschlossen waren. Das Signal ist nie bearbeitet worden. So ist die Erkennung der Fehlstellen sehr einfach: Ich übertrage das Tonsignal ja digital (SPDIF) zum PC ... Nur so kann ich die Fehlstellen aufgrund ihres "perfekt" gleichen DC-Pegels erkennen... bei analoger Übertragung müsste ich an diesen Stellen mit ein/ausschwingen und Rauschen rechnen...

Wenn also tatsächlich mehrere Samples nacheinander exakt gleich sind kann ich SICHER sein einen solchen Fehler zu haben. Der erste abweichende Wert NACH dem Fehler ist dann definitiv schon der erste gültige neue Wert. Als zweite Sicherheit tritt der Fehler IMMER auf beiden Audiokanälen zu GENAU der gleichen Zeit auf. Ich hab so die Sicherheit die Stelle leicht und zuverlässig zu finden und ohne zusätzliche Verluste an weiteren Samples genau die noch gültigen Werte zu ermitteln.

Wie du schon angedeutet hast; Es ist damit sicher nicht möglich relativ komplexe Fehlstellen perfekt zu reparieren, aber jeder Filter (Tiefpass, Bandpass usw) ist definitiv die schlimmere Alternative weil er ja auch das viele gesunde Material zermatscht!

Ich versuch mal mich mit dem Thema "kubische interpolaton" ... wenn ich nicht weiter komme werde ich hier im Hilfe rufen, ok ??

gruß

PS: Ich glaube das ich jetzt erst mal wieder "on the way" bin und werde dann mal sehen wie ich das umsetzen kann..

[bitboy0]

So, nun wieder ich...

mit Cubischer Interpolation und Hermite hab ich nun ausführlich gespielt und alle möglichen "Löcher" aufgefüllt ... Aber ich bin nicht zu frieden mit dem Anschluss der interpolierten Funktion an die vorhandene Funktion. Das dürfte daran liegen weil die Funktionen alle davon ausgehen das man eine Zahlenreihe OHNE fehlende Werte hat und diese dann verbinden möchte ... in meinem Fall habe ich eine Zahlenreihe die eine unterschiedlich große Anzahl an fehlenden Elementen aufweist. Ich benötige aber einen Punkt aus der Zahlenreihe der so weit weg ist von der Fehlstelle wie die Fehlstelle breit ist ... klar?

Ich brauch also was anderes! Ich benötige eine Funktion die sich verhält wie die in Corel-Draw bei der Manipulation der Kurven. Jede Kurve aus zwei Knoten hat zwei "Anfasser" die bestimmen in welche Richtung und mit welcher "Dringlichkeit" die Linie anfängt. Solange die Richtung des Anfassers genau in die andere Richtung sieht wie der Anfasser der angeschlossenen zweiten Kurve habe ich einen ganz glatten Übergang zwischen beiden Kurven ...

Das sind vermutlich die so genannten kubischen Bezierkurven ... ich schau morgen mal was da nun dabei rauskommt.

gruß

[Medium]

Jap, das sind Bézier-Splines 3. Grades. Material dazu hatte ich hier schon mal verlinkt, und auch der Wikipedia-Eintrag ist nicht schlecht.
Ich ging davon aus, dass du die Aufnahme ohne Interaktivität rekonstruieren lassen möchstest. Wenn du aber die Handarbeit in ein möglichst gutes Ergebnis investieren willst, dann lohnen sich Bézier-Splines schon eher.

Da aber auch gleich mal eine Warnung vorab, womit ich schon mal böse zu kämpfen hatte: Der Laufparameter, quasi das X der Splinefunktion, führt auch bei gleichschrittiger Erhöhung nicht zu equidistanten interpolierten Punkten bezogen auf die Zeitachse deines Waves! Das heisst, dass du, wenn du das annimmst, ein verzerrtes Spline erhälst. In deinem Fall kann die Verzerrung klein genug ausfallen, um das zu ignorieren, aber generell müsste man hier einen Zwischenschritt machen, der die Kurve zunächst zu hoch aufgelöst in ein kartesisches Bezugssystem schreibt (z.B. ein Bitmap geeigneter Größe), und aus diesem kann man dann die Kurve übertragen. Oder anders gesagt: Du wirst deine interpolierten Punkte nicht mit schön gleichbleibendem ganzzahligen X erhalten, was du direkt auf deine Zeitachse beziehen kannst. Mann könnte es impizit gestalten, indem man Schnitte mit den senkrechten Linien durch alle fehlenden X-Stellen mit der Splinefunktion bildet, der Aufwand dafür ist aber schon nicht übel (LGS lösen und so). Hm, klingt jetzt kompliziert, ist aber sehr einfach zu verstehen. **

Wenn dein grafischer Editor, bzw. das Bild deiner Aufnahme ohnehin schon die Basis für die dann gespeicherten Daten ist, hast du diesen Schritt quasi schon frei Haus fertig.


**) Mein Code zum Spline Berechnen:

Delphi-Quellcode:

function BezierPoint(pt0, pt1, pt2, pt3: TPoint; t: Double): TPoint;
var
  t0, t1, t2, t3: Double;
  oneMt, tp2, oneMtp2: Double;
begin
  oneMt   := 1-t;
  tp2     := t*t;
  oneMtp2 := oneMt*oneMt;
  t0 := oneMtp2*oneMt;
  t1 := 3*t*oneMtp2;
  t2 := 3*tp2*oneMt;
  t3 := tp2*t;
  result.x := Round(t0 * pt0.x + t1 * pt1.x + t2 * pt2.x + t3 * pt3.x);
  result.y := Round(t0 * pt0.y + t1 * pt1.y + t2 * pt2.y + t3 * pt3.y);
end;

Das t ist die Laufvariable, mit der zwischen den Grenzen des Splines die interpolierten Werte errechnet werden. t liegt zwischen 0 und 1.
Für t=0 ist result = pt0
Für t=1 ist result = pt3.
pt1 und pt2 sind die 2 Kontrollpunkte.

Erhöht man t nun gleichmäßig wie im angehängten Bild (zur Verdeutlichung nur mit 32 Schritten), ergibt sich auf der X-Achse keine gleichmäßige Verteilung der interpolierten Punkte. Das ist, was ich da oben zu beschreiben versuche

[bitboy0]

Und wieder ein DANKE für die Ausführungen und den Code... Es ist mir klar das die von mir gesuchten Kurven auch nur einen speziellen Fall darstellen ... es ist bei Beziers ja nicht mal grundsätzlich klar das es für ein X nur ein Y gibt ... nur in meinem Fall kann ich das garantieren weil eben der Verlauf keine Schleifen möglich macht.

Das Problem mit den nicht equidistanten X-Werten wollte ich so lösen: Ich lasse die Schleife mit mindestens doppelt so vielen Schritten rechnen die ich benötige und mache dann eine kleine lineare Interpolation zwischen den X-Werten die dem jeweils gesuchten X am nächsten kommen ... Der Zeitaufwand ist nicht so hoch gewichtet ...

Zu den manuellen Änderungen der Kontrollpunkte ... das soll nicht manuell passieren! Die Richtung und die Entfernung soll sich zunächst aus den beiden letzten gültigen Punkten vor - und den beiden ersten gültigen Punkten nach der Fehlstelle ergeben. Ich werde ein paar Schieberegler vorsehen mit denen ich z.B. den Einfluss der Anzahl der zu überbrückenden Punkte auf die Distanz der Kontrollpunkte zu ihren jeweiligen Besitzern festlegen kann ... Es soll eine "vorhör"-Funktion geben mit der ich einen kurzen Abschnitt möglichst direkt nach jeder Änderung mal probehören kann um zu erkennen wie es sich anhört. Am Ende ist DAS ja das Entscheidende: Was hinten rauskommt!

Ich werd jetzt einfach mal rumcoden die Tage - sofern ich mal ein paar Stunden dazu komme - und dann sehe ich ja ob mein Ansatz wirklich was bringt. Bis jetzt ist es nur in der Theroie gut ... und zwar ziemlich

Falls es was taugt soll der Code eh frei sein...

gruß

[Medium]

Jau, man kann im Grunde daraus dann etwas machen, was ein wenig die Hermite-Spline Interpolation ist, in dem man für die Kontrollpunkte die Richtung aus dem Vektor zwischen dem vorletzten und letzten Punkt des noch intakten Intervalls nimmt, und die Länge als wählbaren Parameter. Hat allerdings dann u.U. die gleichen Einschränkungen wie zuvor beschrieben, dass nur je 2 Punkte je nach dem keine vernünftige Rekonstruktion der Tangente möchglich machen - aber im Regelfall sollte das schon passen.

Linear interpolieren ist allerdings schwierig glaub ich, bzw. nicht universell genug wenn dann doch mal zu große Abstände auftreten. Ich würde es folgendermaßen probieren: Ein Array, dass das fehlende Intervall darstellt (also genau so viele Samples lang). Dann die Splinefunktion mit genügend feinschrittigem t laufen lassen, und bei den Ergebnissen jeweils die X-Koordinate runden und als Index für das Array nehmen. Den Y-Wert dann in das Array an diese Stelle, und für jedes weitere Vorkommen der selben X-Koordinate so verrechnen, dass nachher ein Mittelwert all der Fälle für eine gerundete Koordinate darin steht.
In einem 2. Array nachführen, welches Arrayelement mindestens ein Mal einen Wert bekommen hat, und am Schluss eventuelle Lücken linear interpoliert Füllen (oder gar kubisch ).

Da bist du dann sicher, für jedes Sample einen Wert zu erzeugen, und du bleibst sehr nahe am eigentlichen Spline dran. Man kann hier sicherlich noch weiter rumdrehen und tricksen, wobei sich mir irgendwann auch die Frage stellt: Hört man den Unterschied eigentlich dann noch?

[bitboy0]

Das Ohr ist eine vertrackte Sache ... einerseits kann man leicht eine Menge Infos weglassen und dennoch hört es sich gut an (siehe mp3/wma) ... andererseits ist nun wieder eine kleine Veränderung an anderer Stelle extrem deutlich zu hören obwohl man die kaum messen kann.

Ich muss halt mal sehen wie genau das werden muss um keine weitere Verbesserung zu bringen ... Ich bin eh mal gespannt wie gut das Ergebnis überhaupt wird... besser als Rechteckpulse wird es sich sicher anhören, aber richtig zufrieden wäre ich wenn ungeschulte (Konsumenten) Ohren das als "ok" betrachten könnten... mehr erwarte ich erst mal nicht

Mit linearer Interpolation meine ich dem Fall das ich die zwei Bezier-Werte nehme deren X-Wert dem gesuchten am nächsten ist und dann mache ich zwischen den beiden Punkten eine Lineare Interpolation ... wenn man kleine Abschnitte der Bezierkurve nimmt sollte der einzelne Abschnitt doch näherungsweise eine Gerade darstellen ...

gruß