Verwirrspiel Intervallmapping

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.

Verwirrspiel Intervallmapping

Beitragvon Jonathan » 06.08.2018, 19:32

Intervallmapping ist ja eigentlich einfach. Will man (p0, p1)->(q0, q1) abbilden, geht das mittels: q = (p-p0)/(p1-p0) * (q1-q0) + q0. (Im ersten Schritt wird die Zahl auf den Bereich 0..1 normiert und dann auf den neuen Bereich abgebildet). Diese Abbildung erfüllt alle Erwartungen, Endpunkte werden auf Endpunkte abgebildet, ein Wert der im ersten Intervall genau in der Mitte liegt, lieg nach Abbildung auch im zweiten Intervall genau in der Mitte und so weiter.

Sagen wir, ich möchte jetzt ein Bild der Größe 128^2 auf 256^2 skalieren. Intuitiv würde man sagen, dass im Ursprungsbild die Pixel eine Distanz von genau einem Pixel haben (trivial), und im zweiten Bild jeder ursrüngliche Pixel irgendwie auf 2 Pixel erweitert werden muss, sprich der Abstand ist jetzt 2. Jetzt kann man sich überlegen, wie man die Pixel nummerieren möchte. (0..127)->(0..255) oder (1..128)->(1..256). Zur Veranschaulichung sagen wir jetzt aber, wir wollen die Größe von 4 auf 8 skalieren. Wir bekommen nach obiger Formel:

[0..3]->[0..7]: [0, 1, 2, 3]->[0, 2.33, 4.67, 7]
[1..4]->[1..8]: [1, 2, 3, 4]->[1, 3.33, 5.67, 8]


Autsch, das ist hässlicher als erwartet. Das neue Intervall ist doppelt so groß wie das alte, im alten war der Abstand der Zahlen genau 1, aber im neuen ist der Abstand der Zahlen alles andere als genau 2. Man würde vielleicht erwarten, wenn das Intervall verdoppelt wird, muss man einfach nur alle Zahlen mit 2 multiplizieren. Man möchte also:

[1..4]->[1..8]: [1, 2, 3, 4]->[2, 4, 6, 8]

Wie kommt man auf dieses 'schöne' Ergebnis? Indem man die Intervallgrenzen auf (0..4)->(0..8) setzt und insgesamt 5 Zahlen im Intervall hat:

[0..4]->[0..8]: [0 1 2 3 4]->[0 2 4 6 8]
Hat man trotzdem nur 4 Werte, kann man von den 5 Zahlen entweder die erste oder die letzte weglassen und kommt damit auf (0..3) oder (1..4).

Es scheint, wir haben eine Lösung gefunden und alles sieht schön aus. Aber leider haben wir ein neues Problem. Nehmen wir mal das Beispiel Farbkodierung. Wir haben eine 8bit Zahl zwischen 0 und 255 (die Farben zwischen schwarz und weiß darstellt) und wollen diese auf das Intervall 0..1 mappen. Gemäß der obigen Definition müsste unser Intervall aber von 0 bis 256 gehen, demnach dürfte der Wert 255 nicht auf 1 gemappt werden, sondern vielmehr auf ~0.996. Wir können also auf einmal gar kein weißes Weiß mehr darstellen, das passt einfach nicht in unsere 8bit Zahl.


Es erscheint, dass es keine wirkliche Lösung gibt. Im Grunde genommen gab es auch niemals ein wirkliches Problem, es ist alles eine Frage, wie man Intervalle definiert und was Grenzen bedeuten sollen. Aber ich überlege gerade, was eine schöne Lösung ist, eine die im Alltag Spaß macht. Was sind eure Gedanken dazu?
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
Jonathan
Establishment
 
Beiträge: 1221
Registriert: 04.08.2004, 20:06

Re: Verwirrspiel Intervallmapping

Beitragvon Krishty » 06.08.2018, 19:52

Pixel sind doch keine Intervalle, sondern unendlich kleine Samples, oder irre ich mich da?

Und was die Farben angeht nutzt man Bias. Um z.B. 0…31 auf 0…255 abzubilden, nimmt man die fünf Bits, kopiert ihre drei vordersten Bits, und fügt sie am Ende wieder an. Das kann man generalisieren, z.B. wird 2-bit Farbtiefe (vier Farben) folgendermaßen mit Bias auf 0…255 gemappt:

00 → 00000000 (0 → 0)
01 → 01010101 (1 → 85)
10 → 10101010 (2 → 170)
11 → 11111111 (3 → 255)


Oh Wunder, es passt genau ;)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6591
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Verwirrspiel Intervallmapping

Beitragvon dot » 07.08.2018, 02:55

Jonathan hat geschrieben:Zur Veranschaulichung sagen wir jetzt aber, wir wollen die Größe von 4 auf 8 skalieren. Wir bekommen nach obiger Formel:

[0..3]->[0..7]: [0, 1, 2, 3]->[0, 2.33, 4.67, 7]
[1..4]->[1..8]: [1, 2, 3, 4]->[1, 3.33, 5.67, 8]

Und wie viele Pixel hat dein "skaliertes" Bild nun genau? ;)


Krishty hat geschrieben:Pixel sind doch keine Intervalle, sondern unendlich kleine Samples, oder irre ich mich da?

Du irrst nicht
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1647
Registriert: 06.03.2004, 19:10

Re: Verwirrspiel Intervallmapping

Beitragvon Jonathan » 07.08.2018, 11:03

dot hat geschrieben:
Jonathan hat geschrieben:Zur Veranschaulichung sagen wir jetzt aber, wir wollen die Größe von 4 auf 8 skalieren. Wir bekommen nach obiger Formel:

[0..3]->[0..7]: [0, 1, 2, 3]->[0, 2.33, 4.67, 7]
[1..4]->[1..8]: [1, 2, 3, 4]->[1, 3.33, 5.67, 8]

Und wie viele Pixel hat dein "skaliertes" Bild nun genau? ;)

Achso ja, das war ein bisschen blöde aufgeschrieben. Was dieses Beispiel wohl eigentlich zeigt ist, wenn man ein Bild von 8 Pixel auf 4 Pixel runterrechnen will, an welchen Positionen will man die Filterkernel platzieren. Eigentlich ist das alles in meinem konkreten Anwendungsfall noch ein bisschen komplizierter weil irgendwo auch noch eine homographische Transformation ins Spiel kommt, aber dann ist mir eingefallen, dass ich vielleicht erstmal den einfachen Fall richtig lösen sollte.

Mir ist jetzt inzwischen auch klar, wie das gehen muss. Das Bild erstreckt sich nicht von 1..4 oder 0..3 sondern von 0..4, aber die Pixelmittelpunkte liegen bei [0.5, 1.5, 2.5, 3.5]. Bei einer Pixelgröße von 1 ist somit das ganze Bild abgedeckt, es liegt nur keiner der Pixel auf den Endpunkten. Das kann man jetzt wunderbar skalieren, verdoppelt man die Pixel geht das Intervall von 0..8 und die Pixel liegen auf den Punkten [1, 3, 5, 7], was bei einer Pixelgröße von 2 wieder das ganze Bild abdeckt. Ob man die Pixel jetzt von 0..3 oder 1..4 indiziert ist egal, weil man Indizes nicht mit Mittelpunkten durcheinander werfen darf, was ich aber getan habe.
(Sorry, dass wieder alles rückwärts aufgeschrieben ist - was ich im Wesentlichen mache ist ein Bild zu verkleinern, wobei ich zunächst die verkleinerte Variante auf die Originalgröße mappe, damit ich weiß wo ich das Originalbild filtern muss um die kleinere Variante zu erhalten).


dot hat geschrieben:
Krishty hat geschrieben:Pixel sind doch keine Intervalle, sondern unendlich kleine Samples, oder irre ich mich da?

Du irrst nicht

Naja fast. Der Artikel sagt ja im Wesentlichen dass Pixel meistens keine Rechtecke sind, sondern Filterkernel. Ein Rechteck ist natürlich ein Filterkernel, aber eben kein sehr guter.
Pixel -sind- unendlich kleine Samples, wenn du z.B. Raytracing ohne Antialiasing machst - die Strahlen gehen immer genau durch den Pixelmittelpunkt. Aber das erzeugt eben Aliasing, also geht jeder Raytracingsample durch eine andere Position auf der Pixeloberfläche und man kann das mit einem Filterkernel seiner Wahl gewichten (damit man nicht den impliziten Box-Filter bekommt, bei dem Pixel wieder perfekte Rechtecke wären).
In diesem Sinne sind Pixel immer das, was man gerade aus ihnen macht, aber hübsch wird es halt eigentlich nur dann, wenn man keine Pointsamples und keine Rechtecke sondern vernünftige Filterkernel benutzt.
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
Jonathan
Establishment
 
Beiträge: 1221
Registriert: 04.08.2004, 20:06


Zurück zu Algorithmen und Datenstrukturen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste