Wie macht man Bild-Resampling richtig?
-
Mir ist aufgefallen, dass Resampling-Funktionen nur in Form einer Kernelfunktion angegeben werden, wie z.B. hier:
http://johncostella.webs.com/magic/Ich habe versucht das zu implementieren und dachte, ich betrachte jetzt für jeden neu erzeugten Pixel z.B. einen 5x5-Block um den nächstliegendsten Ausgangspixel, füttere die relativen Distanzen (schön mit Pythagoras ausgerechnet) der k-Funktion und gewichte das dann alles zusammen.
Aber je nach k-Funktion treten da elliptische Artefakte oder Weichzeichnungseffekte auf (sogar bei Scaling-Faktor 1.0)... vermutlich mache ich das noch falsch.
Wie geht es richtig, was genau übergebe ich der k-Funktion?
-
Der "magic" Kernel ist ein Weichzeichenfilter.
Bin mir nicht sicher was du mit "elliptische Artefakte" meinst. Klingt aber so als ob die nicht auftreten sollten.
-
normalerweise gewichtet man mit einem Gauß Kernel. Also 2D Gaußfunktion an 9 Stellen abtasten, fertig ist der 3x3 Kernel.
Theoretisch ist das Optimum natürlich die sinc() Funktion. Die ist aber unendlich lang, lässt sich mit 3x3 Abtastpunkten nur schlecht darstellen.
Führt dazu, dass Artefakte entstehen. Und die scheinst du nun zu sehen.Gauß schneidet im Frequenzbereich zwar nicht sehr scharf ab, erzeugt aber optisch sehr gute Ergebnisse. Auch bei einem kleinen Kernel.
-
Ich zeige mal, was ich mit den Artefakten meine (x4 zoom):
https://i.imgur.com/69TZOi5.pngDas ist jetzt bei
k(x)=max(1-x,0). Sowas habe ich bei Grafikbearbeitungsprogrammen noch nicht gesehen, egal welche Filterfunktion ich auswähle.hustbaer schrieb:
Der "magic" Kernel ist ein Weichzeichenfilter.
Ah, dann ist vielleicht doch nicht meine Implementation schuld.
Ist mein Vorgehen aber überhaupt prinzipiell korrekt? Darf ich der k-Funktion Distanzen in der Ebene füttern oder muss ich vielleicht das Resampling in zwei Phasen aufteilen (z.B. erst horizontal, dann vertikal)?
-
Also die Bommel bei der unteren Kante sehen komisch aus.
Kannst du das Ausgangsbild dazu posten?
Wenn im Ausgangsbild da ne gerade Kante ist, dann ist das falsch.
Wenn im Ausgangsbild da auch "Struktur" ist, dann kann es passen.;resampler schrieb:
Ist mein Vorgehen aber überhaupt prinzipiell korrekt? Darf ich der k-Funktion Distanzen in der Ebene füttern oder muss ich vielleicht das Resampling in zwei Phasen aufteilen (z.B. erst horizontal, dann vertikal)?
Soweit ich weiss sollte das egal sein. Bin aber auch kein Experte diesbezüglich.
Ich weiss nur dass man Convolution, wenn es der Kernel erlaubt, oft in zwei Schritten macht (=genau das was du schreist, also erst H dann V oder auch umgekehrt), weil es schneller geht. Wobei, mal abgesehen von unterschiedlichen Rundungsfehlern, das selbe rauskommen sollte.
ps: Noch ein andere Link der interessant sein könnte: http://www.ipol.im/pub/art/2011/g_lmii/
Was sinc angeht...
Ob das jetzt "theoretisch" der beste Filter ist, ... pfuh, keine Ahnung. Spielt aber auch keine Rolle. Praktisch ist sinc für viele Anwendungen ein eher schlechter Filter.
Für andere wieder OK.
Für manche Anwendungen sind sogar Box-Filter OK, für wieder andere ist linear interpolation ideal.Meist ist lanczos schonmal wesentlich besser.
Und je nach Anwendung schneiden diverse Spline Filter phänomenal gut ab.Paper dazu:
http://bigwww.epfl.ch/publications/thevenaz9901.pdfIch muss gestehen, die Mathe da drinnen hab' ich mir nicht reingezogen. Aber ich finde die Bilder ab Seite 28 sehr interessant. Dabei wird verglichen was rauskommt wenn man ein Bild in 15 Schritten um je 24° dreht, also insgesamt einmal ganz rum. Und eben unterschiedliche Kernels zum Resampling verwendet.
-
hustbaer schrieb:
Paper dazu:
http://bigwww.epfl.ch/publications/thevenaz9901.pdfJepp. Das ist super. Allerdings kann man damit die Bilder nicht ohne weiteres aliasfrei verkleinern. Da würde noch der passende Tiefpassfilter fehlen.
Bzgl "magic kernel": Das ist ein Tiefpassfilter speziell gedacht für das Resampling um Faktor 2. Und meiner Meinung nach ist das jetzt auch nicht unbedingt der Superknaller. Da gibt's viel Spielraum und man sollte sich auch mal die Amplitudenübertragung von solchen Filtern anschauen. Ich habe das gerade mal spaßenshalber für verschiedene Filter gemacht, die man zum "Runterrechnen" auf die halbe Auflösung benutzen kann imgur-Link. Wie man sieht, dämpft der "magic" Filter stark (blaue Kurve). Deswegen sind die Bilder da auf der verlinkten Seite relativ unscharf. Die schwarze Kurve entsprecht dem Filter, den man effektiv benutzt, wenn man zwei benachbarter Pixel einfach nur mittelt und daraus einen neuen für ein Bild mit halber Auflösung macht. Die Amplitudenantwort ist relativ schlecht für einen Tiefpassfilter. Der Filter zu der roten Kurve hat einen längeren Kernel (6). Das ist auch notwendig für eine steilere Flanke. Ich finde den Filter eigentlich von den dreien zum Halbieren der Auflösung mit am besten. Man hat zwar hinterher leicht mehr Aliasing, aber die Bilder sind auch schärfer dann. Naja, es kommt echt drauf an, was man will und kein Filter ist falsch oder richtig. Es ist eine Abwägungssache, weil man von Schärfe, Aliasfreiheit und Freiheit von "Ringing" nicht gleichzeitig haben kann. Heisenbergsche Unschärferelation is a Bitch.
Im Allgemeinen läuft Resampling so ab:
1. Upsampling (Einfügen von 0 oder mehr Nullen zwischen den Samples, aka "zero stuffing")
2. Tiefpassfilter anwenden (also, das Signal mit dem "Kernel" falten)
3. Downsampling (Behalten jedes x-ten Samples, die anderen werden weggeschmissen)Man kann das natürlich auch in mehreren Stufen machen, wobei es sich lohnen kann, in verschiedenen Stufen andere Filter zu verwenden. Wenn man jetzt die Abtastrate auf ein viertel verringern will, kann könnte man erst den "magic filter" nehmen für faktor 2 und dann nochmal den "roten Filter" für nochmal Faktor 2. Obwohl man auch direkt auf ein Viertel der Rate resampeln könnte, ist sowas in mehreren Stufen ökonomischer (geringerer Rechenaufwand).
Wenn man die DSP-Thematik tiefer verstehen will, kann man sich das hier mal angucken: http://dspguide.com/
-
krümelkacker schrieb:
Bzgl "magic kernel": Das ist ein Tiefpassfilter speziell gedacht für das Resampling um Faktor 2. Und meiner Meinung nach ist das jetzt auch nicht unbedingt der Superknaller.
Der "magic kernel", beim x2 upsampeln, ist einfach nur lineare Interpolation.
Auf der Seite steht ja auch dass er in einer JPEG Decoder Implementierung "gefunden" wurde, wo er für das x2 Upsampling des Chroma Kanal eingesetzt wird.
Dafür eignet sich lineare Interpolation mehr oder weniger gut weil a) Schärfe beim Chroma-Kanal nicht wirklich wichtig ist und b) Ringing beim Chroma-Kanal übel ist. Und die Eigenschaft von linearer Interpolation sind eben: unscharf, dafür aber keinerlei Ringing.
Gibt aber andere Filter die auch fast Ringing-frei sind, dafür aber lange nicht so unscharf.
ps:
krümelkacker schrieb:
hustbaer schrieb:
Paper dazu:
http://bigwww.epfl.ch/publications/thevenaz9901.pdfJepp. Das ist super. Allerdings kann man damit die Bilder nicht ohne weiteres aliasfrei verkleinern. Da würde noch der passende Tiefpassfilter fehlen.
Das verstehe ich jetzt nicht.
Resampling ist immer Tiefpassfilterung, egal in welche Richtung. Und mit jedem linearen Filter kann man genau so up- wie downsampeln.
Bloss dass die dabei entstehenden Artefakte beim up- und downsampling anders aussehen.
-
hustbaer schrieb:
Der "magic kernel", beim x2 upsampeln, ist einfach nur lineare Interpolation.
Lustigerweise kommt bei wiederholter Anwendung eine Funktion heraus, die stückweise ein quadratisches Polynom ist. Aber ja, Du kannst es auch als lineare Interpolation mit einem ganz bestimmten Sampling-Offset betrachten.
Übrigens: Bzgl Chromasubsampling gibt es noch andere Möglichkeiten. Zum Beispiel kann man [-1 1 8 8 1 -1]/8 zum Upsampeln und [1 1]/2 zum Downsampeln benutzen. Diese Filter passen insofern zusammen, dass wenn man Up- und dann wieder Downsampelt genau dasselbe Signal heraus kommt. Der [-1 1 8 8 1 -1]/8 Filter fürs Upsampling produziert genauso wie [1 3 3 1]/4 keine Treppenstufen. Tatsächlich ist das Downsampling gefolgt vom Upsampling (mit dieser Filterkombination) eine Abbildung, die jede quadratische Funktionen auf sich selbst abbildet. Diese Up- und Downsamplingvarianten sind also Pseudoinvers zu einander, was irgendwie sehr nett ist. Hab mich mal sehr lange mit sowas beschäftigt. Man kann dieses Filterpaar auch als Analyse- und Synthese-Tiefpassfilter einer biorthogonalen diskreten Wavelettransformation sehen.
Ich könnte hier heute Abend bei Interesse noch ein paar Koeffizientensätze für Filter posten, die steilere Flanken und in der Amplitudenantwort und verschiedene Grenzfrequenzen haben. Wer sich dafür interessiert und damit experimentieren will: Einfach Bescheid sagen. Sonst mache ich mir nicht die Mühe.
hustbaer schrieb:
Das verstehe ich jetzt nicht. Resampling ist immer Tiefpassfilterung, egal in welche Richtung.
Das Ding ist, dass Du die Cutoff-Frequenz der Filter bei den in thevenaz9901.pdf vorgestellten Techniken nicht einstellen kannst. Die ist immer gleich der Nyquistfrequenz des Quellsignals und damit zu hoch, um die Abtastfrequenz aliasfrei reduzieren zu können.
-
krümelkacker schrieb:
hustbaer schrieb:
Der "magic kernel", beim x2 upsampeln, ist einfach nur lineare Interpolation.
Lustigerweise kommt bei wiederholter Anwendung eine Funktion heraus, die stückweise ein quadratisches Polynom ist. Aber ja, Du kannst es auch als lineare Interpolation mit einem ganz bestimmten Sampling-Offset betrachten.
Genau
Und zwar, wenn ich es richtig verstehe, genau mit dem Sampling-Offset, den man bekommt, wenn man exakt um Faktor 2 vergrössert. Also genau das was man mit dem Luma-Kanal bei klassischem 4:2:0 Sampling machen muss um ihn wieder auf die Auflösung des Chroma-Kanals hochzubringen.krümelkacker schrieb:
hustbaer schrieb:
Das verstehe ich jetzt nicht. Resampling ist immer Tiefpassfilterung, egal in welche Richtung.
Das Ding ist, dass Du die Cutoff-Frequenz der Filter bei den in thevenaz9901.pdf vorgestellten Techniken nicht einstellen kannst. Die ist immer gleich der Nyquistfrequenz des Quellsignals und damit zu hoch, um die Abtastfrequenz aliasfrei reduzieren zu können.
OK, jetzt verstehe ich was du meinst.
Was ich meinte: in dem Paper werden verschiedene Resampling-Filter gezeigt, und Resampling-Filter sind eben immer Tiefpassfilter. Die lassen sich zum verkleinern genau so verwenden. Dazu muss man die Filterfunktion bloss entsprechend skalieren ("strecken").
Da das Paper Verkleinerung nicht behandelt ist es natürlich auch nicht aussagekräftig bezüglich der Qualität/Eignung der darin betrachteten Filter beim Verkleinern. Aber grundsätzlich kann man alle für Verkleinerung verwenden.krümelkacker schrieb:
Im Allgemeinen läuft Resampling so ab:
1. Upsampling (Einfügen von 0 oder mehr Nullen zwischen den Samples, aka "zero stuffing")
2. Tiefpassfilter anwenden (also, das Signal mit dem "Kernel" falten)
3. Downsampling (Behalten jedes x-ten Samples, die anderen werden weggeschmissen)Jo, das ist die Theorie dahinter. Was ich allerdings so an Code gesehen habe ... da wird alles in einem Schritt gemacht. Weil es effizienter ist
Ausser eben der Verkleinerungsfaktor ist wirklich gross. Dann kann es natürlich Sinn machen z.B. erstmal auf ein ganzzahliges Vielfaches der Ziel-Auflösung zu skalieren, idealerweise Ziel-Auflösung * 2^N, und von da an immer um Faktor 2 verkleinern.
-
hustbaer schrieb:
Was ich meinte: in dem Paper werden verschiedene Resampling-Filter gezeigt, und Resampling-Filter sind eben immer Tiefpassfilter. Die lassen sich zum verkleinern genau so verwenden. Dazu muss man die Filterfunktion bloss entsprechend skalieren ("strecken").
Da das Paper Verkleinerung nicht behandelt ist es natürlich auch nicht aussagekräftig bezüglich der Qualität/Eignung der darin betrachteten Filter beim Verkleinern. Aber grundsätzlich kann man alle für Verkleinerung verwenden.Das passt da nur nicht so ganz in das Framework. Natürlich ist der Prozess Äquivalent zum "richtigen Resampeln", wobei auch die Impulsantwort eines bestimmten Filters mitspielt. Aber diese Impulsantwort benutzt man nie direkt zum Interpolieren bei der in thevenaz9901.pdf besprochenen (genialen) Technik. Zum Verringern der Abtastrate müsste man da einen extra Tiefpass-Schritt mit einbauen. Skalieren kannst du da nichts, es sei denn, du machst es komplett anders und verlierst damit die Geschwindigkeitsvorteile.
hustbaer schrieb:
krümelkacker schrieb:
Im Allgemeinen läuft Resampling so ab:
1. Upsampling (Einfügen von 0 oder mehr Nullen zwischen den Samples, aka "zero stuffing")
2. Tiefpassfilter anwenden (also, das Signal mit dem "Kernel" falten)
3. Downsampling (Behalten jedes x-ten Samples, die anderen werden weggeschmissen)Jo, das ist die Theorie dahinter. Was ich allerdings so an Code gesehen habe ... da wird alles in einem Schritt gemacht. Weil es effizienter ist
Klar. Man sollte das, was man in Schritt 3 wegschmeißt, in Schritt 2 gar nicht erst berechnen.
-
krümelkacker schrieb:
hustbaer schrieb:
Was ich meinte: in dem Paper werden verschiedene Resampling-Filter gezeigt, und Resampling-Filter sind eben immer Tiefpassfilter. Die lassen sich zum verkleinern genau so verwenden. Dazu muss man die Filterfunktion bloss entsprechend skalieren ("strecken").
Da das Paper Verkleinerung nicht behandelt ist es natürlich auch nicht aussagekräftig bezüglich der Qualität/Eignung der darin betrachteten Filter beim Verkleinern. Aber grundsätzlich kann man alle für Verkleinerung verwenden.Das passt da nur nicht so ganz in das Framework. Natürlich ist der Prozess Äquivalent zum "richtigen Resampeln", wobei auch die Impulsantwort eines bestimmten Filters mitspielt. Aber diese Impulsantwort benutzt man nie direkt zum Interpolieren bei der in thevenaz9901.pdf besprochenen (genialen) Technik. Zum Verringern der Abtastrate müsste man da einen extra Tiefpass-Schritt mit einbauen. Skalieren kannst du da nichts, es sei denn, du machst es komplett anders und verlierst damit die Geschwindigkeitsvorteile.
Ach so, dir geht es mehr um die in dem Paper vorgestellte Technik. Die, muss ich zugeben, hab ich nicht kapiert. Fehlt mir die Mathematik. Kann man einfach erklären was da gemacht wird?
Soweit ich das verstanden habe werden erstmal die "Pixel" modifiziert (bzw. halt die "Koeffizienten" aus den Pixeln ausgerechnet), damit man die Filterfunktion dann nur mehr an Integralen Positionen sampeln muss = die Werte vorberechnen kann.Mir geht es eher um den schön anschaulichen Vergleich verschiedener Filter
(Und die Filter selbst sind ja unabhängig davon wie man sie umsetzt. Und wenn man sie eben "klassisch" umsetzt, dann kann man die Filterfunktion beliebig "strecken", ganz wie man mag.)Bei reinem Downsampling sollte es mMn. allerdings gar nicht nötig sein so eine Optimierung zu machen. Da kann man den Prozess in einen X und einen Y Pass splitten -- wodurch man auch mit viel weniger Auswertungen der Filterfunktion auskommt.
-
hustbaer schrieb:
Ach so, dir geht es mehr um die in dem Paper vorgestellte Technik. Die, muss ich zugeben, hab ich nicht kapiert. Fehlt mir die Mathematik. Kann man einfach erklären was da gemacht wird?
Soweit ich das verstanden habe werden erstmal die "Pixel" modifiziert (bzw. halt die "Koeffizienten" aus den Pixeln ausgerechnet), damit man die Filterfunktion dann nur mehr an Integralen Positionen sampeln muss = die Werte vorberechnen kann.Oh, diese Frage hatte ich bis jetzt übersehen. Ich versuch's mal mit eigenen Worten. Wenn du eine kontunierliche Funktion ausgehend von einem zeit/raum-diskreten Signal rekonstruieren willst, müsstest Du ja eigentlich das diskrete Signal (was quasi ein amplituden-modulierter Kamm aus Dirac-Pulsen ist) mit der Impulsantwort eines bestimmten Tiefpass-Filters falten. Bei dem Ansatz für die B-Spline-Interpolation zerlegt man quasi die Impulsantwort des Tiefpassfilters in einen discreten Teil, den man als digitalen Filter vorher über die Daten rüberlaufen lassen kann, und einen kontinuierlichen Teil, z.B. ein kubischer Basis-spline. Das ist deswegen so flott, weil (a) der diskrete Anteil sehr effizient realisierbar ist -- es ist nur ein IIR Filter 1. Ordnung, den man bidirektional (vorwärts+rückwärts) anwendet -- und weil (b) so ein kubischer B-Spline sehr kompakt ist (kompakt im Sinne von "f(x)=0" für alle x bis auf ein sehr kleines Interval).
Beispiel: Quellsignal, 1D mit einem Puls in der Mitte
[0 0 0 0 0 ... 0 0 0 0 0 1 0 0 0 0 0 ... 0 0 0 0 0]Nach dem "bidi-Filter" (kostet echt nur 3 Multiplikationen und 2 Additionen pro Sample, ist also super flott):
[ ... 0.0000 -0.0002 0.0006 -0.0024 0.0089 -0.0333 0.1244 -0.4641 1.7321 -0.4641 0.1244 -0.0333 0.0089 -0.0024 0.0006 -0.0002 0.0000 ... ]Da wo nach dem ersten Schritt die 1.7321 steht, stand vorher die 1. Im Wesentlichen werden hier nur die höheren Frequenzen etwas verstärkt. Wenn man dann z.B. die Stelle im Quellsignal zwischen der 1 und der 0 rechts daneben die Mitte interpolieren will, braucht man dann nur die 4 Koeffizienten drum herum der vorgefilterten Version nehmen, also [-0.4641 1.7321 -0.4641 0.1244], und eine bestimmte gewichtete Summe dieser berechnen, wobei die Gewichte von der Subpixelposition abhängen, die man haben will. Im Falle der Mitte, wären das dann [1/48, 23/48, 23/48, 1/48]. Das macht dann 0.6002. Die Gewichte sind einfach die Werte, die man bekommt, wenn man den kubischen B-spline bei 1+p, 0+p, -1+p und -2+p abtastet, wobei p die Subpixelposition zwischen 0 und 1 ist, hier also 0.5 für die Mitte. Man faltet das vorgefilterte Ding also nur mit einem B-spline und tastet es wieder ab, was man direkt in form von Gewichten zusammenfassen kann. Wenn man genau an einer Pixelposition "interpolieren" will, würde man da die Gewichte 1/6, 4/6 und 1/6 für eine 3er-Umgebung bekommen, weil dir kubische B-spline in der Mitte bei 4/6 liegt und bei +/-1 den Wert 1/6 hat. Die 1 im Quellsignal bekomme ich also wieder: dot([-0.4641, 1.7321, -0.4641],[1, 4, 1])/6 = 1. Die Null daneben bekomme ich auch wieder: dot([1.7321, -0.4641, 0.1244],[1, 4, 1])/6 = 0. Es ist also tatsächlich eine kontinulierliche Funktion, die exakt durch die Datenpunkte läuft. Das andere Schöne dabei ist, dass man durch andere Gewichte auch die erste oder zweite Ableitung bestimmen kann. Diese Gewichte kommen dann von der analytischen Ableitung des B-splines. Die Steigung bei der 0 rechts neben der 1 ist nämlich dot([1.7321, -0.4641, 0.1244],[-0.5, 0, 0.5]) = -0.8038.
