Bikubische interpolation

    • GM 8

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Bikubische interpolation

      Hej, ich mal wieder.

      Mein Problem diesmal: Bikubische interpolation. Klingt spannend, nicht? Dacht ich mir auch und habe mich dran gemacht. Doch irgendwie gestaltet es sich schwerer als gedacht.

      Ich möchte einen Haufen Daten (konkret ein Grid) interpolieren (also dessen Größe ändern). Dies soll aber nicht irgendwie geschehen, also bilinear sein, da dies ganz einfach nicht so schön aussieht. Außerdem wäre das ja auch zu einfach, das kann der GM nehmlich schon (Auch wenn man dafür den äußerst unperformanten weg über surfaces, draw und get_pixel machen müsste).

      Ich zeige mal was Sache ist:
      (Hotlinks zu Wiki, böses ich)
      Das original


      So solls nicht werden:


      So aber:


      Mein Problem ist nun, dass ich zwar ein klitzekleines bisschen vom dem Wikipedia Artikel verstehe (da wir das vor nicht allzu langer zeit in Mathematik hatten), mir aber keinen Reim auf den Zusammenhang von diesen Hauf an Formeln machen kann. Also, irgendwie nur halbe Sache.

      Ich hoffe irgendwer hat bereits Erfahrungen gemacht, kann es mir Bürgernah (also nicht Mathematisch, sondern "Informatisch") erklären oder hat sonst irgendwas kluges zu sagen.

      EDIT: langsam wird da was. Ich muss doch eingentlich nur nehmen, oder?

      MfG SDX

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von SDX ()

    • Ich versuch's mal :)

      Die auf Wikipedia angegebene Funktion f(x,y) ist so gesehen dein Grid, was du als Eingabe bekommst. Ziel ist nun f in jedem Einheitsquadrat zu interpolieren, also jeweils das Polynom p(x,y) zu bestimmen. Wie angegeben benötigen wir aber noch fx, fy und fxy an den vier Eckpunkten (0,0), (1,0), (0,1) und (1,1) des Quadrats, also die Ableitungen von f in x-Richtung, y-Richtung und beide. Diese kann man natürlich nicht exakt bestimmen, da f ja nur an den ganzzahligen Koordinaten bekannt ist. Weiter unten im Artikel wird angegeben wie man sie approximieren kann, nämlich mit den finiten Differenzen. Man erhält

      fx(x,y) = (f(x+1,y)-f(x-1,y))/2
      fy(x,y) = (f(x,y+1)-f(x,y-1))/2
      fxy(x,y) = (fx(x,y+1)-fx(x,y-1))/2

      Wie man sieht beziehen sich diese Berechnungen immer auf Nachbarfelder. Befindet man sich jedoch am Rand des Grids muss man die Berechnung abwandeln. Befindet man sich am linken Rand, ersetzt man einfach x-1 durch x, am rechten Rand x+1 durch x, am oberen Rand y-1 durch y und am unteren Rand y+1 durch y.

      Nun ist also der Vektor (siehe Wikipedia)

      x = (f(0,0), f(1,0), f(0,1), f(1,1), fx(0,0), fx(1,0), fx(0,1), fx(1,1), fy(0,0), fy(1,0), fy(0,1), fy(1,1), fxy(0,0), fxy(1,0), fxy(0,1), fxy(1,1))

      bekannt. Auf Wikipedia ist zudem darauffolgend die Matrix A^(-1) angegeben, sodass sich mit A^(-1)*x die Koeffizienten von p(x,y) bestimmen lassen. Damit hat man nun p berechnen und kann damit beliebige Funktionswerte in dem Einheitsquadrat bestimmen.

      Mehr ist es eigentlich nicht. Ich hoffe das war dir nicht zu mathematisch, ansonsten kannst du gerne nachhaken. ;)

    • Ich habe mich mal ran gemacht. Doch leider erinnert mich das Ergebnis eher an ein Schiebepuzzle (mal abgesehen davon, dass ich das mit den Kanten noch nicht mit habe).



      ( [EDIT] Links [/] das Original )( ich nutze blau für 0 und rot für 1. Alle anderen Farben liegen irgendwo dazwischen ).
      Vielleicht hilft es ja, dass ich sehe, dass wenn man zb Spalte2 mit Spalte4 tauscht, es etwas ansehnliches ergibt.
      Ich bin so ein bisschen Ratlos, irgendwie habe ich da jetzt schon so viel geändert und gemacht und getan, dass ich schon daran Zweifle, das Grund liegende richtig gemacht zu haben.

      Und noch die GMK. Wäre super, wenn jemand 5 Minuten Zeit und die Ruhe hätte, sich das mal durchzugucken.

      MfG SDX

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von SDX ()

    • ich weis ja nicht obs hilft aber anscheinend sind nur die positionen falsch
      ich hab jetzt einfach mal schiebe puzzel gespielt:



      ich habe keins gedreht!

      ich habe sie nur verschoben (x,y)

      EDIT: bald hab ichs fertig

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Virus27 ()

    • Ich habe leider nicht so recht verstanden wie du die Interpolation berechnet hast. Schon bei der Funktion "cubic" wusste ich nicht so recht was die macht. Sieht so aus als ob sie ein kubisches Polynom an einer Stelle ausrechnet. Allerdings hab ich nicht verstanden wie du die Koeffizienten aus den v1 bis v4 berechnet hast.

      Ich habe mich aber mal selber drangesetzt und im Grunde nur deine ds_grid_resize Funktion neu geschrieben. Ich denke das dürfte so in etwa hinhauen. Die Funktion macht genau das, was ich vorhin in meinem Post beschrieben habe. Ob das nun die effizienteste Methode ist, sei mal dahin gestellt. Vielleicht hilft es dir ja.
      Dateien

      • bicubic.rar

        (17,23 kB, 684 mal heruntergeladen, zuletzt: )

    • Oh man, Bl@cksp@rk, das sieht klasse aus!
      Ist dann doch einiges mehr geworden, als gedacht. Ich hätte es vielleicht ein bisschen systematischer angehen sollen und nicht meine eigene Interpretation deiner Beschreibung+Wiki umsetzen sollen. Ich hoffe mal, dass der Script noch viel (auch von anderen) genutzt wird. Außerdem ist er recht effizient. Schneller als meiner auf jeden Fall. Mal abgesehen davon, dass bei mir das Puzzle schieben noch nicht einberechnet war :D

      (Ich habe gleich eine Restartfunktion rein gehauen, um es mir wieder und wieder an zugucken können. Klasse! )

      MfG SDX

    • Wow, man das gibt echt coole Bilder:


      Sieht aus wie ein Bild einer Wärmekamera.

      Gute Arbeit. Ich werd wohl noch bis nach der Oberstufe warten müssen um zu verstehen wie das genau funzt xD
      Jetzt müsste man nur noch einen Verwendungszweck finden...

      Willst du auf diese Drachen und -eier klicken?
      Sie werden sich freuen ;)

    • Der Zweck ist ja nicht unmittelbar Grafik, da es eigentlich zu langsam ist. Dafür hat man ja bilineare interpolation. Es kann ja überall geschehen, dass Daten interpoliert werden. Besonders in der Statistik. Man kann so auch recht performant Highmaps erstellen. Da Diese nicht den umweg über die Grafik machen müssen. Je nach größe sollte dies wirklich schnell gehen!
      Ich habe auch was erstellt. An der rechten Seite ist eine Skala zu sehen. Diese zeigt, was die Farben bedeuten (Hohe werte rot, niedrige blau)
      Spoiler anzeigen

      MfG SDX

    • Freut mich, dass es euch gefällt :)

      Heightmaps wären in der Tat eine sehr gute Anwendung des Scripts. So braucht man nur zu wenigen Punkten die Höhe anzugeben und man erhält daraus eine weich geformte Landschaft. Für Grafiken wäre es eigentlich nur zum hochskalieren von Bildern geeignet. Das sollte dann qualitativ schon optimal aussehen. Allerdings würde das Skalieren schon so seine Zeit dauern und wenn man bedenkt, dass auch jedes halbwegs gute Grafikprogramm bikubische Interpolation können sollte, ist es eigentlich unsinnig das mit dem GM zu machen.

      Ich werd wohl noch bis nach der Oberstufe warten müssen um zu verstehen wie das genau funzt xD

      Selbst wenn du es nach der Oberstufe nicht komplett verstanden hast, ist das normal, da bikubische Interpolation auf vielen Sachen aufbaut, die nichtmal in der Oberstufe behandelt werden (zumindest war das bei mir so). Wie z.B. Polynome in mehreren Variablen, Richtungsableitungen und Matrizenrechnung.