Fehlende Werte in 2-D Array durch Interpolation errechnen -Algorithmus?



  • Hallo,

    ich stehe leider gerade etwas auf dem Schlauch und bin dankbar für jeden Tipp oder Ansatz 🙂

    So könnte ein Array aussehen:

    1 0 0 0 5 0 0 0 0
    0 0 3 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    1 2 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 9
    1 0 0 0 0 0 0 0 9
    

    Zur Vereinfachtung wird hier jetzt mal angenommen, dass das Array in x-Richtung linear ist. Wenn nun die 0en durch anderen Zahlen ersetzt würden, hätte man eine Zahlenreihe von 1 bis 9.

    In echt ist es leider so, dass das ganze nicht linear ist.
    Die erste Zeile könnte z.B. von 1-9 laufen und die dritte vielleicht von 2-15. (Gleiche Anzahl an Elementen, aber andere Werte)

    Ich möchte nun die Nullen durch interpolierte Werte ersetzen und dabei ist es mir wichtig, dass immer zwischen den Elementen, die am nahesten beieinander liegen interpoliert wird.

    Mein Ansatz wäre der folgende:
    Ich fange oben in der linken Ecke an und finde von links nach rechts Zeile für Zeile mit der 1 in der Ecke das erste Element, mit dem ich beginne.
    Nun bestimme ich den Abstand zum nächsen Element !=0 (die 5) und schaue dann in y-Richtung, ob bei einem geringeren Abstand als dem gerade bestimmten ein Wert vorhanden ist. Somit finde ich hier die 3, die näher an der 1 liegt, als die 5.

    Nun kopiere ich die drei in die erste Zeile an die dritte Stelle und errechne die fehlende 2.

    Nun fehlen hier noch jede Menge Bedingungen und dieses vorgehen finde ich ziemlich kompliziert.
    Ich würde das mit vielen geschachtelten Schleifen realisieren.

    Gibt es da eine Möglichkeit das einfacher und Eleganter zu lösen?

    Vielen Dank


  • Mod

    beginner987 schrieb:

    In echt ist es leider so, dass das ganze nicht linear ist.
    Die erste Zeile könnte z.B. von 1-9 laufen und die dritte vielleicht von 2-15. (Gleiche Anzahl an Elementen, aber andere Werte)

    Das klingt immer noch schwer danach, als gäbe es da irgendwelche Randbedingungen. Deine Beschreibung klingt beispielsweise so, als würden Werte von links nach rechts immer größer werden. Ist das so oder hast du es ungeschickt beschrieben? Je mehr du über das System sagen kannst, desto einfacher und besser wird die Interpolation.

    Dein Ansatz klingt erst einmal etwas komisch. Aber vielleicht hast du hier schon die vermutete Zusatzinformation benutzt, die wir nicht kennen, daher sieht es für uns komisch aus.

    Allgemein gibt es sehr viele verschiedene Verfahren für 2D-Interpolation, je nachdem, was man am Anfang für Daten hat und welche Eigenschaften die interpolierte Funktion haben soll. Dein Beitrag klingt so, als hättest du nicht Wikipedia zu dem Thema gelesen. Warum nicht?



  • SeppJ schrieb:

    Dein Ansatz klingt erst einmal etwas komisch. Aber vielleicht hast du hier schon die vermutete Zusatzinformation benutzt, die wir nicht kennen, daher sieht es für uns komisch aus.

    Allgemein gibt es sehr viele verschiedene Verfahren für 2D-Interpolation, je nachdem, was man am Anfang für Daten hat und welche Eigenschaften die interpolierte Funktion haben soll. Dein Beitrag klingt so, als hättest du nicht Wikipedia zu dem Thema gelesen. Warum nicht?

    Danke für die Antwort.

    Es ist tatsächlich so, dass die Werte von links nach rechts größer werden. Aber die Reihen können auch unregelmäßig sein, wie z.B. 1,2,2,5,6,8,9,11,15.
    Ebenfalls können Reihen verschoben sein.

    Die vorhandenen Werte sind Messwerte und eng genug, dass man zwischen diesen linear interpolieren kann.

    Nur ich weiß leider nicht wie ich das ganze elegant für ein Array einsetze.
    In Wirklichkeit handelt es sich auch um einen geachtelten Vektor mit x- und y-Werten.

    Die x-Werte steigen dabei generell von links nach rechts und die y-Werte von oben nach unten.
    Ich müsste also sowieso zwei Interpolationen durchführen.
    Eine für die x-Werte und eine für die y-Werte.

    Falls das einen Unterschied macht, mein Array ist wie folgt definiert:

    struct punkte
    {
        int x, y;
    };
    
    std::vector <std::vector<punkte> > Array (400, std::vector<punkte>(300));
    

    Ich habe gerade mal gegoogelt und unter dem Stichwort "Bilinear interpolation" etwas gefunden.

    Ich wüsste aber nicht, wie ich das in einem Array umsetzen sollte, so dass keine Lücken bleiben 😞

    Mir würde es schon reichen, wenn mir jemand einen Ansatz liefert, den ich probieren kann umzusetzen 😉


  • Mod

    Gibt es eine Abhängigkeit zwischen den verschiedenen Zeilen?



  • SeppJ schrieb:

    Gibt es eine Abhängigkeit zwischen den verschiedenen Zeilen?

    Nein, es gibt nur die jeweilige Abhängigkeit für x von links nach rechts aufsteigend und für y von oben nach unten aufsteigend.

    Wenn man jetzt nur, wie anfangs beschrieben, das Array ohne Struct betrachtet, gibt es nur eine Abhängigkeit innerhalb einer Zeile, nicht aber zwischen den Zeilen.

    So sehen die Daten in Echt im Idealfall aus:
    [url] http://www.bilder-upload.eu/show.php?file=2506fd-1417906928.jpg [/url]

    Jedes Kreuz entspricht einem Wert.
    Dennoch können alle Fälle eintreten, die oben in dem Array gezeigt sind.
    Zwischen den Kreuzen sind Lücken die so ca. 30 Werte groß sind.



  • Ich habe gerade mal gegoogelt und unter dem Stichwort "Bilinear interpolation" etwas gefunden.

    Eine bilineare Interpolation ist natürlich etwas einfacher innerhalb eines Rechtecks umzusetzen, bei dem die Werte der Eckpunkte bekannt sind. Für dein spezielles Problem würde ich aus dem Bauch heraus folgendermassen vorgehen:

    1. Zunächst in x-Richtung linear interpolieren. D.h. für jede Zeile zwischen je zwei benachbarten Werten linear interpolieren (also immer zwei benachbarte Werte "mit einer Geraden verbinden" - Geradengleichung aufstellen). Die Geradengleichung ist für dein Problem:

    y = y0 + (y1 - y0)(x - x0)/(x1 - x0)

    Wobei y0 und y1 die jeweils benachbarten Werte sind, x0 und x1 deren Array-Indizes in x-Richtung, y der linear interpolierte Wert und x der Array-Index, für den du den interpolierten Wert ermitteln möchtest.

    Für die ersten beiden Werte der Ersten Zeile in deinem Beispiel-Array ergäbe das z.B.:

    y = 1 + (5 - 1)(x - 0)/(4 - 0) = 1 + x

    als Geradengleichung, und somit

    1 2 3 4 5 6 7 8 9
    

    als Interpolation der Zeile in x-Richtung. Wenn du beim Durchlaufen einer Zeile auf einen neuen Wert triffst, beginnt dort natürlich eine neue Gerade, für die du die Geradengleichung erneut ermitteln musst.

    Die Zeilen 2, 3 und 5 lassen sich in diesem Durchlauf noch nicht interpolieren, da für diese nicht mindestens 2 Werte vorliegen (nicht genügend Stützstellen, um eine Gerade anzulegen). Diese erstmal außen vor lassen (werden im 2. Schritt gefüllt)

    Für dein Beispiel ergibt sich nach dem x-Durchlauf:

    1 2 3 4 5 6 7 8 9
        3           
    
    1 2 3 4 5 6 7 8 9
                    9
    1 2 3 4 5 6 7 8 9
    

    2. Spaltenweise interpolieren. Analog zu Schritt 1, nur stattdessen für jede Spalte in y-Richtung durchführen.

    Bei deinem Beispiel hast du jetzt:

    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    

    (Auch wenn hier das "bilineare" nicht so schön zur Geltung kommt ;-))

    Wenn du mindestens 2 Zeilen mit jeweils mindestens 2 von 0 verschiedenen Werten in deinen Arrays hattest, dann sind jetzt alle Felder mit bilinear interpolierten Werten gefüllt.

    Es kann natürlich auch sein, dass deine Matrix z.B. so aussieht:

    0 0 0 0 0 0 0 0 0
    0 3 0 0 0 0 0 0 0
    0 0 0 0 0 4 0 0 0
    0 0 0 0 0 7 0 0 0
    0 2 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    

    Hierbei kannst du im ersten x-Durchlauf nichts machen, und erst im y-Durchlauf erhältst du:

    0 3.33 0 0 0 -2 0 0 0
    0 3    0 0 0 1  0 0 0
    0 2.67 0 0 0 4  0 0 0
    0 2.33 0 0 0 7  0 0 0
    0 2    0 0 0 10 0 0 0
    0 1.67 0 0 0 13 0 0 0
    

    Wie man leicht erkennen kann, braucht man jetzt nochmal einen Zeilendurchlauf in x-Richtung (1. Schritt), damit alle Felder gefüllt sind. Eine einfache Lösung ist also abschließend nochmal in x-Richtung zu interpolieren. Wenn man das vorher weiss, kann man natürlich auch mit der y-Richtung als erstem Schritt beginnen, dann spart man sich den 3. Druchlauf.

    Natürlich gibt es auch Matrizen, die sich überhaupt nicht derart interpolieren lassen. Das ist genau dann der Fall, wenn weder 2 Zeilen noch 2 Spalten mit je 2 von 0 verschiedenen Werten vorliegen.
    Beweissskizze: Eine Zeile (Spalte) kann interpoliert werden, wenn sie mindestens 2 Werte hat und wenn dies für 2 verschiedene Zeilen (Spalten) zutrifft, dann haben im Folgedurchlauf alle Spalten (Zeilen) mindestens je 2 Werte.

    Gruss,
    Finnegan



  • Guten Morgen,

    vielen Dank Finnegan.

    Das ist schon mal ein guter strukturierter Ansatz.
    Leider kann ich diesen so nicht einsetzen.

    Bei mir ist es ja oft der Fall, dass z.B. in x-Richtung zwei Werte teilweise riesige Lücken zueinander in derselben Reihe besitzen.
    Hierbei ist der Abstand so groß, das es in der Realität sicher schon zu größeren Abweichungen kommt.

    Stattdessen gibt es aber für jeden x-Wert einen relativ nahen anderen x-Wert, der nur ca. 20 Werte in x-Richtung entfernt, aber um einige Zeilen in y-Richtung verschoben ist.

    Ich muss es also irgendwie schaffen wirklich den nächsten x-Wert zur Interpolation zu nutzen, auch wenn der einige y-Zeilen verschoben ist.

    Am besten wäre es ja, wenn man dann Treffenförmig so alles absuchen würde:
    http://www.bilder-upload.eu/show.php?file=673c75-1417941976.jpg

    Aber das werden ja super viele Durchläufe.

    Ich weiß nicht, wie ich das gut umsetzen kann.



  • beginner987 schrieb:

    Guten Morgen,
    Bei mir ist es ja oft der Fall, dass z.B. in x-Richtung zwei Werte teilweise riesige Lücken zueinander in derselben Reihe besitzen.
    Hierbei ist der Abstand so groß, das es in der Realität sicher schon zu größeren Abweichungen kommt.

    Stattdessen gibt es aber für jeden x-Wert einen relativ nahen anderen x-Wert, der nur ca. 20 Werte in x-Richtung entfernt, aber um einige Zeilen in y-Richtung verschoben ist.

    Ich muss es also irgendwie schaffen wirklich den nächsten x-Wert zur Interpolation zu nutzen, auch wenn der einige y-Zeilen verschoben ist.

    Ja, ich sehe dein Problem. Auch wenn die bilineare Interpolation durchaus optisch ansprechende Ergebnisse liefern kann (http://upload.wikimedia.org/wikipedia/commons/c/c6/Bilininterp.png) und einfach umzusetzen ist, so haben zwischen zwei Messwerten entlang einer Koordinatenachse nur die beiden Messwerte Einfluss auf den interpolierten Wert. Oder allgemeiner: Wenn du deine Messwerte mit nur horizontalen oder vertikalen Strecken verbindest, dann haben für einen Interpolierten Wert nur diejenigen Messwerte Einfluss auf diesen, deren Verbindungsstrecken vom Messpunkt in die vier Koordinatenrichtungen ausgehende Strahlen zuerst schneiden.

    Was du jedoch wahrscheinlich wirklich haben willst, wenn es sich um Messwerte handelt, ist eine an die Messpunkte "gefittete" Polynomfläche. Das wird allerdings deutlich aufwändiger, da es die Lösung eines je nach Polynomgrad mehr oder weniger grossen Gleichungssystems erfordert (in C++ hat man von Haus aus dahingehend leider nicht so schöne Werkzeuge wie z.B. in MATLAB). Stichwort für diesen Ansatz ist "Least-Squares-Verfahren" bzw. "Methode der kleinsten Quadrate" http://de.wikipedia.org/wiki/Methode_der_kleinsten_Quadrate.

    Ansonsten kann ich auch nur auf eine Wikipedia-Übersicht zu entsprechenden Interpolationsverfahren verweisen:
    http://en.wikipedia.org/wiki/Multivariate_interpolation
    Least Squares ist dort auch genannt. Die "Thin Plate Splines" sehen für mich auf beim groben Überfliegen vielversprechend aus. Es scheint sich dabei um einer Verallgemeinerung von kubischen Splines auf 2 Dimensionen zu handeln (siehe auch http://www.geometrictools.com/Documentation/ThinPlateSplines.pdf).

    Leider habe ich nicht die Zeit dir mehr als diese Stichworte zu geben. In die Verfahren müsste ich mich selbst erst einarbeiten. Auch sind diese besseren Verfahren entsprechend komplizierter umzusetzen. Wenn du etwas suchst, dass sich mit ein paar geschachtelten Schleifen und nicht allzu vielen Zeilen Code umsetzen lässt, wirst du wahrscheinlich mit den Nachteilen der bilinearen (oder auch bikubischen) Interpolation leben müssen - oder du hältst Ausschau nach einer Bibliothek, die dir die entsprechenden Verfahren zur verfügung stellt.

    Finnegan



  • Noch eine informative Seite zu den Thin Plate Splines mit Beispielcode:

    http://elonen.iki.fi/code/tpsdemo/index.html

    Auch hier scheinen je nach Anzahl der Kontrollpunkte (Messwerte) entsprechend größere lineare Gleichungssysteme zu lösen zu sein. In dem o.g. Demo wird dazu Boost uBLAS verwendet (teil der Boost-Bibliothek). Das ließe sich z.B. auch für den Least-Squares-Ansatz einsetzen.

    Finnegan



  • Vielen Dank,

    ich habe nun eine akzeptable Lösung gefunden.

    Ich durchlaufe das Array, bis ich einen Wert finde.
    Danach Schaue ich mit einer "umgedrehten Treppe", wo der am nächsten befindliche Wert in positiver X-Richtung vorhanden ist.

    So sieht die "Treppe" aus:

    .....
    ....
    ...
    ..
    .
    

    Dabei startet die Treppe immer an der X-Position des gefundenen Startwertes +1.

    Von dem ggf. in der Treppe ermittelten Wert wird der X-Wert übernommen und in an die entsprechende Position in die Startzeile geschrieben.

    Dasselbe erfolgt analog für die Y-Achse und zwischendurch werden die waagerechten und senkrechten Werte interpoliert.

    So bekomme ich Werte, die auf Rechtecken liegen und so kann ich dann einfach, wie du beschrieben hast, die Lücken interpolieren.

    Für die Randbereiche fehlen so teilweise Werte, aber das ist nicht schlimm 😉

    Vielen Dank nochmal!


Anmelden zum Antworten