Hallo,
ich suche Literaturtipps, in denen ich Algorithmen zur Interpolation finde.
Die Besonderheit: Die Interpolation soll so erfolgen, dass Werte die irregulär verteilt sind auf ein reguläres Grid oder Volumen interpoliert werden. Leider find ich immer nur Infos, die sich auf den umgekehrten Sachverhalt beziehen.
Lineare Interpolation würde mir schon erstmal reichen (muss also keine komplizierte Interpolationsgrundlage haben
Freu mich über jeden Hinweis.
July
hi
übrigens, was studierst du?
.lineare Interpolation haben wir, wenn ich mich recht entsinne, in der 8 oder 9 Klasse gemacht!
.es ist nämlichs nichts anderes wie eine Geradengleichung. Typisch für diese ist, daß sie duch zwei Punkte beschrieben werden kann. Bei linearen Interpolation suchst du nun eine Stelle zwischen diesen beiden bekannten Punkten. Wenn du die Gleichung aufstellst, wirst du merken, daß es im Grunde genommen, fast eine Art Dreisatz ist, Proportionalitätsrechnung eben…
Literatur:
http://www.astro.uni-jena.de/Teaching/Praktikum/pra2…
http://www.ces.ka.bw.schule.de/lehrer/culm/mathemati…
http://w5.cs.uni-sb.de/~butz/teaching/sg-SS00/sg-ss0…
online programm zur linearen Interpolation:
http://www.hucke-puelz.de/intinter.htm
beste Erklärung:
http://www.blibs.de/ofenberg/D_LineareInterpolation…
bis denn
ali drin
Hallo,
ich verstehe wahrscheinlich nicht ganz, was du meinst, aber so denke ich mir die Lösung (für eine Lineare Interpolation):
Nimm zwei benachparte Punkte und verbinde sie durch eine Linie. Dort, wo die Linie dein „Grid“ schneidet, ist der interpolierte Punkt. Nimmt das nächste Punktepaar und mache so weiter.
Ein Problem kann sein, daß deine Punkte dichter bzw. weniger dicht sind als die Machenweite des Grids. Im ersten Fall kannst du entweder Punkte ignorieren, mehrere Punkte mitteln oder gar eine Regressionsgerade durch eine Punktegruppe legen, anstatt nur zwei Punkte zu verbinden. Im zweiten Fall kannst du je Schnittpunkt einen neuen, interpolierten Punkt berechnen oder den Schnittpunkt nehmen, der näher an der Mitte zwischen den Punkten liegt.
Literaturtipps habe ich keine.
Gruß
Jochen
hi,
also interpolation hab ich nicht in der schule gehabt, aber das tut grad nix zur sache. werd mir die links zwar mal ansehen, aber ich glaube du hast mein anliegen nicht ganz verstanden.
angenommen ich hab auf einer ebene 3 punkte mit je einem bestimmten wert liegen (völlig zufällig). und nun bekomme ich die koordinaten eines vierten punktes und soll dessen wert aus den gegebenen interpolieren. da müsste ich als erstes wissen, ob der punkt im dreieck der anderen liegt oder nicht (wenn nicht kann ich nicht interpolieren). dann müsste ich eine ebene mit den werten der punkte aufspannen und den wert bestimmen, den die ebene an der stelle der koordinaten des gesuchten punktes hat.
so, und um das ganze zu verkomplizieren:
a) es sind nicht nur drei vorgegebene punkte, die „irgendwo“ liegen sonder 256*256 (z.b.) --> heißt: ich müsste erstmal rausfinden, welche drei punkte, denn meinen gesuchten umgeben
b) ich gehe noch eine dimension höher (k.a. wie man dann vorgeht…)
so viel zu meinen theoretischen überlegungen. aber praktisch halte ich sie für sehr rechenintensiv (und möglicherweise gibt’s was einfacheres…)
(im 1D-Fall ist Interpolation kinderleicht, aber eben nur da…)
July
Hi,
nun ja, keine so schlechte idee, allerdings würde ich ja nicht gleich direkt auf meine gridpunkte kommen. meistens würde ich wohl mit den gitterlinien zusammentreffen. aber daraus könnte man dann ja ne einfache lineare interpolation machen *denk*.
ich glaub, das lass ich mir noch mal durch den kopf gehen…
danke,
July
Hallo,
angenommen ich hab auf einer ebene 3 punkte mit je einem
bestimmten wert liegen (völlig zufällig). und nun bekomme ich
die koordinaten eines vierten punktes und soll dessen wert aus
den gegebenen interpolieren. da müsste ich als erstes wissen,
ob der punkt im dreieck der anderen liegt oder nicht (wenn
nicht kann ich nicht interpolieren).
Wenn die Punkte völlig zufällig verteilt sind, dann kannst Du gar nicht sinnvoll interpolieren. Ich habe Deine Aufgabenstellung nicht verstanden. Willst Du einfach nur beliebige Punkte auf eine Fläche (bzw. Gerade im 2D) Projezieren?
Fragt sich
Fritze
Hallo July,
die Idee mit den Dreiecken (siehe deine Antw. an ali drin) ist doch schon sehr brauchbar. Um die Dreiecke zu finden, gibt es gute Verfahren. Das nennt sich übrigens TRIANGULATION (oder Meshing and Triangulation). Ein beliebter Verfahren ist z.B. die „Delaunay triangulation“.
Jetzt hilft GOOGLE !
Gruss Kurt
hi fritze,
na gut, so völlig zufällig … jein. nimm an, du hast ein bild mit grauwerten (2d fall). dann hast du die grauwerte ja auf einem regelmäßigem grid liegen ( punkt (1,1) mit grauwert, punkt (2,1) mit grauwert etc). jetzt nimm an, dass du jedes pixel um einen individuellen wert verschiebst. dabei bleibt zwar die grundstruktur des grids erhalten, aber die punkte sind nicht mehr gleichmäßig verteilt ( punkt (2.4,1.9) mit grauwert, punkt (3.1, 1.1) mit grauwert etc.). nun möchte ich aufgrund dieses verzerrungsgrids, das bild (die grauwerte) neu berechnen. d.h. mich interessiern jetzt die interpolierten werte für die positionen 1,1 usw.
das ganze soll dann auch noch für volumina gehen (sprich 3d-bilder), wo halt voxel mit zugehörigen grauwerten betrachtet werden.
ist es nun etwas verständlicher geworden???
july
hi kurt,
na ja, die triangulierung an sich sollte nicht das problem sein (heißt, ich weiß schon, welche punkte miteinander dreiecke bilden), aber wie finde ich möglichst einfach heraus, in welchem dreieck der punkt liegt, dessen wert ich interpolieren möchte??? ich kann doch unmöglich für jeden gesuchten punkt alle dreiecke abgrasen und mit x tests überprüfen, ob der punkt im dreieck liegt oder nicht. das wird doch zu rechenintensiv…
july
hi
1D-Fall???
2D-Fall, das schrieb ich und das kam in der Schule dran, nur hieß es Zwei-Punkte-Form! Die Interpolation ist nur etwas erweitert!
3D-Fall solltest du dich mit linearer Algebra beschäftigen. Ich denke aber Lagrange hat aber auch Interpolationsformeln für den n-dimensionalen Fall entwickelnt. Bin mir aber nicht sicher…
.in einem vernünftigen Mathebuch wird das schon drinstehen…
cu
ali drin
Hallo, ich bin’s nochmal.
Möglicherweise hab ich jetzt etwas besser verstanden, was du meinst.
Und ich habe ein Idee! Nicht sehr genau, aber sehr einfach und vielleicht ist sie ja gut genug:
Du gehst Punkt für Punkt deines Grids durch und berechnest den „Einfluß“ (nennen wir diese Größe E) eines jeden Punktes (vielleicht von den x nächtgelegenen Punkte, vielleicht innerhalb eines vorgegebenen maximalen Umkreises, oder du nimmst alle Punkte) deiner „verzerrten“ Bild-Matrix.
Diese Größe, E, ist abhängig vom Abstand vom Bild-Matrixpunkt zum Gridpunkt. E=1 für einen Abstand von 0. Je größer der Abstand, desto kleiner wird E. Außerdem gilt: Die Summe aller E’s je Gridpunkt muß 1 ergeben. Wenn du also n Punkte um den Gridpunkt betrachtest, bekommst du n Abstände di (i=1…n). Sei L die Summe der Abstände. Dann ist Ei = 1 - di/L.
Nun ermittelst du den (interpolierten) Grauwert des Gridpunktes, indem du die Grauwerte der n Bild-Matrixpunkte, multipliziert mit dem jeweiligen Ei, addierst.
Die Methode kannst du sicher optimieren, wenn die Abhängigkeit nicht linear ist, sondern zB. quadratisch mit dem Abstand abnimmt. Außerdem könntest du evtl. sicherstellen, daß der Summenverktor vom Gridpunkt zu den verwendeten Punkten möglichst klein bleibt (der Gridpunkt also möglichst mittig liegt.
Ist das praktikabel? Ich würde gerne wissen, ob und wie du das Problem löst!
Gruß
Jochen
Hi…
Die Besonderheit: Die Interpolation soll so erfolgen, dass
Werte die irregulär verteilt sind auf ein reguläres Grid oder
Volumen interpoliert werden. Leider find ich immer nur Infos,
die sich auf den umgekehrten Sachverhalt beziehen.
Wenn ich das und die weiteren Kommentare richtig interpretiere, willst Du folgendes:
Du hast in dem Fall, den Du 2D nennst, eigentlich schon drei Dimensionen, nämlich zwei Koordinaten auf einer Ebene und einen Wert, den man als dritte Koordinate (Höhe über der Ebene) interpretieren kann. Das es in Wirklichkeit ein Farbwert oder eine Niederschlagsmenge oder irgendwas anderes ist, macht erstmal nichts aus. Die bekannten Daten spannen eine mehr oder weniger komplexe Fläche auf. Nun bekommst Du einen Satz Koordinaten auf der Ebene und willst den Wert (die Höhe) an dieser Stelle interpolieren. Außerdem willst Du das Ganze mit einem Programm machen.
Wie Du schon richtig erkannt hast, brauchst Du mindestens 3 Punkte mit bekanntem Wert, die möglichst nahe am gefragten Punkt liegen. Diese sind recht einfach zu finden, wenn die bekannten Punkte in einem regelmäßigen Raster angeordnet sind, was Du oben auch sagst. In einer anderen Antwort macht es eher den Eindruck, die bekannten Punkte seien zufällig verstreut. Wie ist es denn nun?
genumi
hi,
Wie Du schon richtig erkannt hast, brauchst Du mindestens 3
Punkte mit bekanntem Wert, die möglichst nahe am gefragten
Punkt liegen. Diese sind recht einfach zu finden, wenn die
bekannten Punkte in einem regelmäßigen Raster angeordnet sind,
was Du oben auch sagst. In einer anderen Antwort macht es eher
den Eindruck, die bekannten Punkte seien zufällig verstreut.
Wie ist es denn nun?
die gegebenen werte sind auf einem irregulären raster angeordnet und ich such die werte bzgl. des regulären rasters.
daher ja die „schwierigkeit“. andersrum geht es einfach zu berechnen…
grüße, july
hi jochen,
also, dein lösungsansatz klingt erstmal ziemlich interessant. ich werd mir das ganze mal in aller ruhe durch den kopf gehen lassen und dann mal sehen, ob es sich so einfach umsetzen läßt, oder nicht.
dank dir auf jeden fall erstmal.
grüße, july
hi,
- 1D-Fall???
okay 1D hab ich das genannt, weil ich eine zahl habe, die die koordinate beschreibt (x). natürlich hat diese dann einen wert (w), aber den hab ich ausser acht gelassen.
bei mir müsstest du also von 3d und 4d ausgehen (einaml (x,y,w) und einmal (x,y,z,w)) wobei w der zu interpolierende wert ist.
Hallo July,
habe deine Diskussion mit Jochen gelesen und verstehe das jetzt so, dass deine Input-Daten auf einem regelmäßigen Gitter liegen, Die Output-Daten sollen auf ein unregelm. Gitter uminterpoliert werden.
In diesem Fall ist es doch kein großes Problem, aus den gewünschten Zielkoordinaten (x,y) die 4 Gitterpunkte links/rechts - obeerhalb/unterhalb vom Punkt (x,y) zu finden. Dann brauchst du keine Triangulation. Als Interpoationsverfahren bietet sich dann einfach „bilineare“ Interpolation an, siehe z.B. in den „Numerical Recipes“ (Buch oder Link: http://www.library.cornell.edu/nr/bookcpdf/c3-6.pdf ).
Die von Jochen vorgeschlagene Abstands-Wichtung (Inverse Distance Weighted Interpolation) ist auch ein gutes Verfahren, siehe z.B. „Shepards Method“ bei
http://www.ems-i.com/gmshelp/interpolation/interpola…
Triangulation brauchst du eher beim umgekehten Fall: Input unregelmäßig verstreut, soll auf regelm. Gitter gebracht werden.
Welche SW hast Du denn ? Falls Du zufällig IDL verwenden kannst/darfst: In IDL gibt es dafür fertige Funtionen. Triangulate sucht die Dreiecke, trigrid interpoliert auf ein Gitter (kennt versch. Interpolationsverfahren).
Anwendungsbeispiel (Mars-Orbiter): http://pirlwww.lpl.arizona.edu/~abramovo/MOLA_interp…
Gruss Kurt
Hi Kurt,
hui, ich hab mich wohl ziemlich chaotisch ausgedrückt…
Ich habe unregelmäßig verteilte Daten und möchte sie auf ein regelmäßiges Grid interpolieren. Jetzt klar rübergekommen?
Ja, ich arbeite mit IDL. Habe bisher griddata zum interpolieren genommen, allerdings scheint sie fehlerbehaftet zu sein, da Randpunkte mitunter sehr seltsame Werte bekommen (auch, wenn MISSING=… gesetzt ist).
Mit trigrid werd ich mich auch noch mal versuchen. Hoffe, dass da diese Fehler nicht auftreten. Nachteil beider Methoden: sie gelten nur für den 2D-Fall (also x,y + Wert)
Gruss, July