#1 03.10.2006 15:13:01

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Interp2D

Ich habe in Interpolationsproblem...

Ich habe ein Bild (bmp) in diesem bild sind einige Pixel mit farben besetzt (nur graustufen : r=g=b)

und jetzt will ich die Pixel zwischen meinen festen Farbpixeln zeichnen
und zwar so, dass es eben so übergänge zwischen den FixPixeln gibt

ist das verständlich?

also in der art sowas wie ein weichzeichner nur dass die Originalpixel nicht verändert werden dürfen...

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 03.10.2006 16:30:39

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Interp2D

Na wenn die neuen Pixel immer genau in der Mitte liegen sollen, dann ist das ja nicht schwer.
Entweder liegen sie zwischen zwei Pixeln, oder zwischen vieren.
In beiden Fällen kannst Du doch sicher einfach den Mittelwert bilden?

DerPeer

Offline

 

#3 03.10.2006 17:47:38

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Zitat:

ist das verständlich?

hm, ich checks nich?  :doof:


My software never has bugs. It just develops random features.

Offline

 

#4 03.10.2006 22:52:34

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Interp2D

nehmen wir an ich hab ein bmp 4x4 wo die pixel nummeriert sind
links oben ist 1 und rechts unten ist 16.

Code: delphi

 01 02 03 04
 05 06 07 08 
 09 10 11 12
 13 14 15 16 



pixel 2 ist weiß
pixel 9 ist grau
pixel 11 ist schwarz
und
pixel 16 ist wieder weiß.

Welche farbwert fülle ich nun in die verbleibenden Pixel ein??
möchte linear interpolieren... aber wie??

morgen gibts ein bild dazu

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#5 04.10.2006 07:14:07

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Ok, ich denke ich weiss was du meinst - aber da gibt es eine entscheidende Frage: Was ist mit den Randpixeln? Darf für die zb. schwarz oder weiss per Definition angenommen werden? In diesem Fall hätte ich möglicherweise eine funktionierende Lösung, muss das dann aber noch genauer durchdenken - was natürlich erst sinnvoll ist wenn die Randpixel per Definition irgendeine Farbe haben... darf für meine Idee auch durchaus eine eigene Farbe für jeden Randpixel sein (um es zu präzisieren, es gibt 4 Randpixel - links oben, links unten, rechts oben, rechts unten).

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#6 04.10.2006 07:32:25

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Ich würde folgendes machen, ich mach das jetzt mal als Pseudocode:

Code: delphi

for y:=0 to height do begin
  for x:=0 to width do begin
    if (image[x,y] gesetzt) then continue;
    sum = 0;
    count = 0;
    for b:=-5 to 5 do begin
      posy = y+b;
      for a:=-5 to 5 do begin
        posx = x+a;
        if (posx < 0 or posx > width or posy < 0 or posy > height) then continue;
        if (image[posx,posy] nicht gesetzt) then continue;
        factor = 1/sqrt(a*a + b*b);
        count = count + factor;
        sum = sum + factor * image[posx,posy];
      end;
    end;
    image[x,y] = sum / count;
  end;
end;


Du berechnest also den nach der Entfernung gewichteten Durchschnitt der umliegenden gesetzten Pixel. Nicht gesetzte Pixel und Randpixel werden einfach ignoriert. Du musst nur der Radius so groß wählen, das immer mindestens 1 Pixel in Reichweite ist. Ggf. auch einfach das ganze Bild nehmen....

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#7 04.10.2006 07:48:29

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Das war meine erste Idee, hab ich dann aber wieder verworfen weil es doch schon sehr massiv auf die performance geht. Vorteil ist natürlich, dass die Randpixel dabei irrelevant sind - daher hab ich das ja auch nochmal nachgefragt. Für den Fall, dass die Randpixel definiert werden können hätte ich eine relativ einfache Idee um daraus ein trianglegrid zu bilden und dann via scanline eben zu interpolieren.

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#8 04.10.2006 13:31:20

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Interp2D

randpixel an sich gibt es nicht....
ich könnte sie evtl einfach definieren. Wie würde diese lösung denn dann aussehen?

hier hab ich noch eib bild dass das ganz demonstrieren soll.

mfg Chris


Attachments:
Attachment Icon Interp2D.JPG, Größe: 13,099 bytes, Downloads: 542

Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#9 04.10.2006 13:41:45

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Zitat:

weil es doch schon sehr massiv auf die performance geht.

och...wer hat den was von Performance gesagt  :mrgreen:
Meins hat doch nur O(n^4), ist immer hin noch polynomiell wink
Wenn es wirklich draufankommt kann man da aber noch so eine Art Mipmaps reinbauen, dann wirds schneller.

Zitat:

randpixel an sich gibt es nicht....

Solange dein Bild nicht unendlich groß ist oder irgendwie kugelförmig hast du immer Pixel die am Rand liegen.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#10 04.10.2006 14:00:45

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Interp2D

Randpixel gibt es nicht =

1. Sind nicht gesetzt ....
2. Das bild ist theoretisch unendlich groß


Der Pseudocode von Die (Coolcat) hat noch so einige fehler, oder täusche ich mich da?

Zeile 3: Gesetzt solle nicht gesetzt  heißen
dann unten nicht gesetzt = gesetzt
count = count + 1; nicht +factor

jedenfalls stelle ich mir das so vor...

Performance ist extrem wichtig...
ich werde das ganze mindesten 5.000.000.000 mal aufrufen müssen...

(brauche das Ergebnis für die Fehlerberechnung eines Downhill Simplex Optimierers... mit ca 5000 Dimensionen)

mfg Chris

--EDIT--

Außerdem fehlt ein "not" in der If Abfrage mit den Rändern des rechenbereiches...
wink


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#11 04.10.2006 14:46:31

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Also dann mal zu meinem Lösungsansatz - wobei ich ihn eigenltich für wenige definierte pixel konzipiert habe, aber das Prinzip ist natürlich das selbe und von der performance her denke ich schon, dass er mit Coolcats Variange mithalten kann  :mrgreen:

1) es gilt Randpunkte zu bestimmen. Also wenn es notwendig ist (weil du nicht auf ein Rechteck interpolieren willst) dann kannst du dir natürlich die konvexe Hülle (zb. mit Quickhull) berechnen und die Randpixel dadurch definieren. Aber im folgenden gehe ich mal von einem Rechteck aus, damit der Algorithmus leichter zu verstehen ist.

D.h. es gibt 4 Randpixel - nämlich links oben, rechts oben, links unten, rechts unten.

2) Man beginnt nun Dreiecke zu bilden - und zwar mit jeweils zwei Randpixeln und einem Nicht-Randpixel. Wichtig ist dabei, dass a) keine anderen Pixel im Dreieck eingeschlossen werden dürfen und b) es keine Überschneidungen mit bereits existierenden Dreiecken geben darf. Ein Dreieck ist in diesem Fall nichts anderes als eine Menge von drei Pixeln{p1, p2, p3}.

Diesen Schritt macht man für alle möglichen Permutationen.

3) Nun verwendet man jeweils genau einen Randpixel und zwei Nicht-Randpixel und beginnt wieder Dreiecke mit den selben Kriterien wie in Punkt 2 zu erzeugen.

3) es gibt nun nur noch Möglichkeiten für Nicht-Randpixel, d.h. man erzeugt Dreiecke die nur solche Pixel enthalten - die Kriterien (keine Überschneidungen, keine eingeschlossenen Pixel) sind natürlich weiterhin gültig.

Ergebnis dieses Verfahrens ist eine Liste von Dreiecken die genau auf das durch die Randpunkte definierte Rechteck mappen. Es gibt nun zwei Möglichkeiten die Farbwerte dazwischen zu interpolieren. a) du generierst dir einen vertexbuffer und lässt die hardware die Interpolation erledigen (was natürlich die schnellste Version ist) oder b) du wendest zb. den scanline polygon fill algorithm darauf an. Wenn du dazu Details benötigst kann ich dir das Verfahren erklären, ist wirklich nichts kompliziertes, aber prinzipiell sollte die hardware für den job ganz gut geeignet sein.

Ok, noch kurz erklärend: warum habe ich das Verfahren gesplittet anstatt gleich alle Permutationen durchzugehen? Naja, performancemässig ist der split sinnvoll weil man damit beim wirklich aufwändigen dritten Schritt (dort werden im Normalfall die meisten triangles zu erzeugen sein), bei dem es nur noch Nicht-Randpixel gibt, sich einiges an permutationen ersparen kann indem man eben die Randpixel schon vorher als potentielle Kandidaten für Dreiecke ausschliesst.

Tja, soviel dazu - sollte nicht weiter schwierig zu implementieren sein und müsste auch die gewünsche Funktionalität mit sich bringen. Bitte kein Patent darauf anmelden, was du ansonsten damit machst ist mir egal  :mrgreen:

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#12 04.10.2006 14:57:09

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Interp2D

Aber dann gibt es doch immer veschiedene lösungen je nachdem mit welchen pixeln man anfängt 3-ecke zu bilden... oder?

ICh verwende übrigens kein DirectX, also fällt die HW Interpolation weg...


hm... ist das nicht aufwändig, jeden Punkt 3x zu testen?


theoretisch kann ja ein punkt in jedem dreieck liegen...
aber zwei punkt können nur in 2 dreiecken liegen.


und wie teste ich dass kein anderer punkt dazwischen liegt?

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#13 04.10.2006 15:43:25

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Zitat:

Der Pseudocode von Die (Coolcat) hat noch so einige fehler, oder täusche ich mich da?

Zeile 3: Gesetzt solle nicht gesetzt heißen
dann unten nicht gesetzt = gesetzt
count = count + 1; nicht +factor

jedenfalls stelle ich mir das so vor...

Mag sein das Fehler drin sind, habs schließlich nicht getestet.
Ich habe das ganze so verstanden, dass du z.B. auf dem Bild oben alle schwarzen Pixel durch Interpolation ergänzen willst. Dabei sollen Pixel die bereits im Bild gesetzt (= nicht schwarz) sind erhalten bleiben sollen. Ob gesetzt oder nicht müsstest du durch ein Bool-Array o.ä. realisieren, da die Werte im Array ja überschrieben werden.
Jedenfalls wird in Zeile 3 abgebrochen, wenn eben bereits ein Wert im Bild vorhanden ist, der nicht überschrieben werden soll.
Unten ist es genau andersrum: Nicht gesetzte Pixel werden ignoriert, weil ja im Bild irgendein Müll steht und du nur die gesetzten Pixel interpolieren willst.
Das mit dem count ist schon richtig so, nur der Variablename ist blöd gewählt. Ich summiere alle Faktoren auf um am Ende das Ergebnis normieren zu können.

Zur Performance:
Man könnte eine Art Mipmap generieren und immer die vier nächsten Pixel eines Mipmaplevels gewichtet aufsummieren.
(kann das gerne näher erläutern)


Anmerkung: Ich hatte gerade keine Lust JorEl Beitrag zu lesen, die sind immer so lang wink

Zitat:

ICh verwende übrigens kein DirectX, also fällt die HW Interpolation weg...

Wenn es auf Performance ankommt, wie wäre es damit den Pixelshader zu benutzen.  :idea: :mrgreen:

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#14 04.10.2006 16:05:57

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Zitat:

die sind immer so lang

dabei hab ichs so kurz wie möglich gehalten  big_smile

Zitat:

Aber dann gibt es doch immer veschiedene lösungen je nachdem mit welchen pixeln man anfängt 3-ecke zu bilden... oder?

Also die Art der Triangulierung wirkt sich auf das Ergebnis der Interpolation nicht aus - solange die beiden Kriterien (keine Überschneidungen, keine Punkte immerhalb von Dreiecken) eingehalten werden. Klar sieht das erzeugte mesh dann zwar anders aus, aber es ändert nichts an der Interpolation selbst.

Zitat:

hm... ist das nicht aufwändig, jeden Punkt 3x zu testen?

Meiner Ansicht nach ist es sinnvoller als alle möglichen Permutationen gleich durchzuprobieren, denn die Anzahl der Permutationen erhöht sich natürlich durch die Randpunkte die ich gleich am Anfang ausschliesse massiv.

Zitat:

theoretisch kann ja ein punkt in jedem dreieck liegen...
aber zwei punkt können nur in 2 dreiecken liegen.

Also ein fix definierter Pixel darf nicht in einem Dreick liegen, das würde gegen das definierte Kriterium vertossen - wenn der Algorithmus eingehalten wird kommt das auch nicht vor, dass so ein Punkt innerhalb eines Dreiecks ist, denn diese Pixel sind immer Eckpunkte für die triangles.

Zitat:

und wie teste ich dass kein anderer punkt dazwischen liegt

Da gibt es unterschiedliche Ansätze - eine Möglichkeit wäre zb. das Dreieck so zu transformieren, dass die Ausrichtung einer Seite der x-Achse entspricht - damit vereinfacht sich der Test dann enorm - aus dem Dreieck kannst du auf triviale Weise zwei rechtwinkelige Dreiecke bilden indem du sie splittest und dann ists wirklich nicht mehr schwierig zu entscheiden ob der Punkt im Dreieck liegt oder nicht.
Das ist aber wirklich nicht die effizienteste Lösung sondern nur eine relativ einfache Möglichkeit für den Test. Du kannst dir natürlich auch mal das object picking sample aus dem SDK anschauen, dort gibts wenn ich mich richtig erinnere einen raycasting Ansatz um das zu entscheiden.

Wenn du auf die hardware verzichten willst (ist im Hinblick auf performance allerdings nicht unbedingt vorteilhaft) dann kannst du wie gesagt mit dem scanline Algorithmus die Interpolation erledigen. Muss man eben so implementieren, dass die pixel innerhalb eines Dreiecks entsprechend der Eckpunkte zu interpoliert werden.

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#15 04.10.2006 16:50:59

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Interp2D

Ich habe jetzt mal Coolcats Methode verwendet...
Meine Pixel haben (fast) nie einen sehr großen abstand zueinander, so dass man mit einer 7x7 interpolation gut hinkommt... genauer brauche ich es nicht...

jetzt geht das Problem in die 2. Runde!  :mrgreen:

Ich habe meine festen pixel in einem Array stehen also Array[i] = (x,y);
was mache ich denn jetzt wenn meine lustigen Pixel nicht mehr ganzahlige Positionen haben.

Also an (1,2 | 4.78) ist die Farbe 123 usw...

möchte das ganze bild füllen...

Mache ich das dann genauso?
d.h. nehme ich einfach alle Pixel schaue wie weit sie von den nähesten fixwerten weg sind und normiere das ganze ???

oder wie kriege ich das hin??

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#16 04.10.2006 17:28:30

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Zitat:

Mache ich das dann genauso?
d.h. nehme ich einfach alle Pixel schaue wie weit sie von den nähesten fixwerten weg sind und normiere das ganze ???

Vom Prinzip ja. Ich nehme mal an das ganze ist unsortiert. Dann müsstest du für jeden Pixel erstmal die Pixel im Kreis mit Radius r finden. Dafür müsste man jedesmal das ganze Array durchlaufen. Ich hatte angenommen du hättest ein Array und könntest einfach drauf zugreifen.

Idee:
Man könnte den Zugriff beschleunigen indem man das Array sortiert. Zuerst nach der x-Koordinate und dann nach der y-Koordinate. Dann hättest du quasi eine Zeilenweise Anordnung. Jetzt kann man sich Positionen im Array merken, so dass man nicht jedesmal komplett von vorne suchen muss.
Wenn wir jetzt zeilenweise das Bild berechnen können wir für jeden Pixel der Zeile alle Werte mit einem x-Wert kleiner also posX-radius ausschließen. Ähnlich geht das auch in der Spalte. Alle Pixel die wir vorher links ausgeschlossen haben, können wir auch jetzt ausschließen. Somit kann man das ganze etwas beschleunigen.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#17 16.02.2007 11:29:52

Mavarik
Member
Registriert: 26.04.2006
Beiträge: 95

Re: Interp2D

Hallo!

Aus reiner Neugier habe ich diesen Thread gelesen...

Bin auch soweit mitgekommen... Bis ich gegoogled haben um zu erfahren wofür man das braucht...

Bin auf http://de.wikipedia.org/wiki/Downhill-Simplex-Verfahren gestoßen.. und habe Nix verstanden. (Was habe ich eigentlich in Mathe LK gemacht?)

Aber dann habe ich http://www.informatik.uni-bremen.de/~uf … se0510.pdf gefunden!
Jetzt bin ich mir sicher... Ich habe keinerlei Ahnung von Mathe...  :doof:

Grüsse Frank

PS.: Was machst Du damit?


Hier wohne ich: www.fliegerei.net/game/Mavarik.kmz
und
3 Zeilen Delphi sagen mehr als 1000 Worte.

Offline

 

#18 16.02.2007 12:07:22

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Interp2D

Zitat:

Was habe ich eigentlich in Mathe LK gemacht?

Sowas lernt man auch nicht in der Schule.


My software never has bugs. It just develops random features.

Offline

 

#19 16.02.2007 12:15:39

Mavarik
Member
Registriert: 26.04.2006
Beiträge: 95

Re: Interp2D

Zitat:

Sowas lernt man auch nicht in der Schule.

Tja dafür kenne ich jetzt aber die Kernaussage von "Herr der Fliegen", dass ist natürlich viel besser. <-- OT I know...

Frank *heul*


Hier wohne ich: www.fliegerei.net/game/Mavarik.kmz
und
3 Zeilen Delphi sagen mehr als 1000 Worte.

Offline

 

#20 16.02.2007 12:35:05

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Zitat:

Sowas lernt man auch nicht in der Schule

Hm, auch in Österreich lernt man natürlich keine Lösungen für dieses spezifische Problem - aber das mathematische Wissen das dazu nötig ist wird im Prinzip schon vermittelt. Viel mehr als Interpolation ist es ja nicht wirklich... natürlich fällt einem Informatiker die Anwendung dieses Wissens weitaus leichter, da man ständig damit zu tun hat, aber ich glaube man sollte das auch mit Schulwissen hinkriegen können. Aber ok, meine Schulzeit liegt schon eine Weile zurück, da ist es garnicht immer so einfach zu unterscheiden welches Wissen von der Uni und welches von Schulen kommt.  big_smile


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#21 16.02.2007 12:46:25

Mavarik
Member
Registriert: 26.04.2006
Beiträge: 95

Re: Interp2D

Ja das interpolieren ist kein Problem, aber hast Du Dir mal den PDF angesehen? Lernt Ihr so etwas in der Schule???

Frank  :?


Hier wohne ich: www.fliegerei.net/game/Mavarik.kmz
und
3 Zeilen Delphi sagen mehr als 1000 Worte.

Offline

 

#22 16.02.2007 13:27:08

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: Interp2D

Natürlich nicht - ich hab eher im Allgemeinen auf das Thema des threads Bezug genommen als auf dieses pdf, das übersteigt was man in der Schule lernt schon bei weitem. Zu meiner Zeit hörte man dort beispielsweise kein Wort von simplex (ich wage zu behaupten, dass nichtmal Gauss erwähnt wurde) - obwohl es nun wirklich nichts schwieriges ist, aber zu tun hatte ich damit erstmals in Statistik und Wahrscheinlichkeitsrechnung an der Uni. Aber ich vertrete dennoch den Standpunkt, dass man auch das basierend auf Schulwissen durchaus verstehen kann - man braucht sicher eine Weile dafür, aber mir wäre jetzt beim Überfliegen eigentlich nichts aufgefallen das zu den wirklich heftigen Dingen gehört mit denen man Studienanfänger zu quälen pflegt.  big_smile


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson