Aliasing und Antialiasing

• Auswirkungen und Effekte

���������

© Detlef Krömker

© Detlef Krömker

© Detlef Krömker

© Detlef Krömker

Linien100% 20%

20%

Windows95 Banner

Win95 Banner auf LCD-Display

Moiree

Moiree (Resampling 1:2)

Moiree (Resampling 1:4)

Weitere Beispiele

Ideale AbtastungJetzt sind wir in der Lage, die Abtastung formal zu

fassen und zu beschreiben:

Gegeben:

• kontinuierliche Bildfunktion

• Diracfeld

� � � � � � � � ���

( , ) ( , )= − −=−∞

∞

=−∞

∞

∑∑ δ ∆ ∆

� � �( , )0 1 2 3 4 5 6 7 8 9

0

1

23

4

0

10

20

30

40

50

40-50

30-40

20-30

10-20

0-10

12

34

56

7

R1

R2

R3

R4

R5

0

0 ,1

0,2

0 ,3

0,4

0,5

0 ,6

0,7

0,8

0,9

1

Ideale Abtastung

• Wir definieren als abgetastetes Bild:

� � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � ������ � � � � � � � � �

�

� �

� �

= ⋅

= ⋅ − −

= ⋅ − −

= = = =

=−∞

∞

=−∞

∞

∑∑

∑∑

( , ) ( , )

( , ) ( , )

( , ) ( , )

( , ) ( , ) ,

,

,

δ

δ

∆ ∆

∆ ∆

∆ ∆ ∆ ∆0

Ideale Abtastung������������������ ������� ��������������� �

�� �������������� ������� ����� ���������� �������� ����

� � � � � � �� = ⋅( , ) ( , )

� � � � � �

� � � � � �

�

� �

����� � � ��� �

( , ) ( , ) ( , )

( , ),

/ /

= ⊗

= − −=−∞

∞

∑∑= =

∆ ∆ ∆ ∆

∆ ∆ ∆ ∆

4 2

2 2

ππ π

Veranschaulichung der idealen Abtastung

x

y

∆y

∆x

u

v

bubv

� � ( , )� � �( , )

� � V( , )

u

v

∆∆

��

= 2π

∆∆

�

= 2π

Veranschaulichung der idealen Abtastung

x

y

∆�

∆�

Veranschaulichung der idealen Rekonstruktion

x

y

∆�

∆�

f(x,y) kann durch einen idealen Tiefpaß mit

� � � ���� �

��� �� � �� ��� � �

( , ) ( , )=

< < − < < −

∆ ∆

∆ ∆

ξη

ξ η

rekonstruiert werden.

�X

∆�v

u

�Y

∆

Abtasttheorem (1)

Ein bandbegrenztes Bild f(x,y), das orthogonal mit Abtastintervallen abgetastet wird, kann fehlerfrei rekonstruiert werden, wenn die Abtastfrequenzen größer als die Nyquist-Frequenzen sind.

∆ ∆� �,

12

12

∆ ∆�� �

� �� � � = > = >,

mit

� � �� ( , ) , ,ξ η ξ η= > >0

� �X Y,

� V V,

Abtasttheorem (2)

Ein diskretes Bild läßt sich mit Hilfe eines (idealen) Tiefpasses mit der Übertragungsfunktion

rekonstruieren, so daß dieses mit dem ursprünglichen Signal identisch ist. Das rekonstruierte Bild ist dann

� � � � ��� � � ��

� � � ��� � �

� � � � � � �

��

� �

��

( , ) ( , )

( , ) sinc( ) sinc( )

=

< < − < < −=

∆ ∆

∆ ∆∆ ∆

ξη

ξ ηξ η

� � �G( , )

� � � � � � � �

��

�

��

�

��

�

��

�QP

( , ) ( , )sin( )

( )

sin( )

( )=

−

−

−

−=−∞

∞

=−∞

∞

∑∑ ∆ ∆ ∆

∆

∆

∆

π

π

π

π

sinc-Funktion-1D

�����

�

����

���

����

�

����

� ��

�( )

sin=

π 2π 3π 4π−π−2π

2D-SINC -Die ideale Rekonstruktionsfunktion

-6,2

83

-4,7

12

-3,1

42

-1,5

71

0,00

0

1,57

1

3,14

2

4,71

2

6,28

3

7,85

4

9,42

5

10,9

96

12,5

66

0,000

1,571

3,142

4,712

6,283

7,854

9,425

-0,3

-0,2

-0,1

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0,9-1

0,8-0,9

0,7-0,8

0,6-0,7

0,5-0,6

0,4-0,5

0,3-0,4

0,2-0,3

0,1-0,2

0-0,1

-0,1-0

-0,2--0,1

-0,3--0,2

� � ��

��

�( , )

sin sin= ⋅

2D-SINC -Die ideale Rekonstruktionsfunktion

-6,2

83

-4,7

12

-3,1

42

-1,5

71

0,00

0

1,57

1

3,14

2

4,71

2

6,28

3

7,85

4

9,42

5

10,9

96

12,5

66

0,000

1,571

3,142

4,712

6,283

7,854

9,425

-0,3

-0,2

-0,1

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0,9-1

0,8-0,9

0,7-0,8

0,6-0,7

0,5-0,6

0,4-0,5

0,3-0,4

0,2-0,3

0,1-0,2

0-0,1

-0,1-0

-0,2--0,1

-0,3--0,2

� � ��

��

�( , )

sin sin= ⋅

Reale Abtastung und Rekonstruktion

Die Forderungen des Abtasttheorems sind in realen Systemen nicht zu erfüllen. Im einzelnen:

● Bandbegrenzung: Reale Bildvorlagen sind nicht bandbegrenzt Aliasing (1.Art)

● ideale Abtastung (mit Diracimpuls): Reale Abtasterhaben endliche Apertur Unschärfe

● ideale Rekonstruktion (mit sinc-FunktionReale): nur Approximationen möglich Aliasing (2.Art)

Ursachen - Effekte -Maßnahmen

Aliasing 1. Art im 2D

x

y

∆�

∆�

ALIASING

Aliasing 1. Art - Ursachen und Artefakte

• Ursache: Unterabtastung, Überlappung der Spektren

• Durch nachträgliche Filterung nicht korrigierbar!

• Artefakte:– Moirees

– Perlschnüre

– Aufblitzen (Szintilation) nur in Bewegtbildern

Aliasing 1. Art - Maßnahmen

• Bandbegrenzung des abzutastenden Bildes durch z.B.– optische Unschärfe

• einfach, adhoc einsetzbar

• wenig effektiv, weil Filterflanken nicht steil genug

• erfordert Abtastraten deutlich über Nyquistfrequenz

• deutlich sichtbare Unschärfe

– endliche Abtastapertur • hat Tiefpaßwirkung (siehe nachfolgend)

– beim Rendering (Behandlung später)

Reale Bildrekonstruktion - Anzeige• Ideale Rekonstruktion mit sinc-Funktion

nicht realisierbar

• praktische Lösungen:– Rechteckausgaben (zero-order hold)– Artifakte:

• Treppenstufen Aliasing 2. Art• Ameisenkrabbeln (ant crawling) nur im Bewegtbild

– in der Praxis auf CRT teilweise gemildert durch:• horizontal: Tiefpaßwirkung des Videoverstärkers

• vertikal: Gaußfunktion des Elektronenstrahls

• hochfrequentes “Rauschen” durch Lochrastermaske

– auf LCDs deutlich sichtbar!

Das Hauptproblem: Ortsaliasing

• Antialising beim Rendering -Die Ortsabtastung bei der Bildgenerierung

• Übersicht zu den Verfahren

• Bewertungen

• Ein Spezialproblem - Bildüberlagerung

Einordnung:Rendering, Bildbearbeitung, Abtastung

DigitalesBild

Digital-video

Graphik Animation

statischeModelle

dynamischeModelle

Reiz

Rendering

AbtastungBildbearbeitung

Abtastung mit endlicher Apertur

Apertur: kleines Fenster im Ortsbereich, innerhalb dessen ein Abtastwert durch gewichtete Summation beiträgt.

Beispiele:– CCD Chip: nahezu rechteckförmig– Röhre: Gausfunktion

bei Aufnahme von Realbildern aus energetischen Gründen unvermeidbar

Analyse und Folgerungen

endliche Apertur hat Tiefpaßwirkung– Röhre: Gaußfunktion relativ gut– CCD: Rechteck (sinc!) nicht harmlos!

Apertura(x,y) H(u,v)

f(x,y) f’’(x,y) fd(x,y)

s(x,y) (Diracfeld)

� � � � � � � � � �������

� � � � � �

’( , ) ( , ) ( , ) ( )

’( , ) ( , ) ( , )

= ⊗= ⋅

Was für ein Filter (shape)?Region of Support?

• Idealer Tiefpaß wäre sinc-Funktion

• Pixelbreite sei x, dann Nyquist Frequenz 1/2x

• Sync-Funktion 1. Nullstelle 1Pixel Abstand also 2Pixel breit

• Approximationen:– Box

– Dreieck � Bartlett

– Gauß

Übersicht Rekonstruktion1

∆[

−∆[2

∆[2

10.

1

∆[10.

10.

2∆[

1

∆[10.

2 0ξ[

2σ

∆[∆[

4 0ξ[

4 0ξ[

( )sinc 1

x0sinc 2

y0

ξξ

ξξ

sinc 1

x0sinc 2

y0

ξξ

ξξ

2

H

− +

2 2 2

12

22π σ ξ ξ

( )rect 1

x0rect 2

y0

ξξ

ξξ

1

2 2

2

2 2

πσσ

H

[

−

1

∆ ∆[

WUL

[

[

1

∆ ∆[

UHFW

[

[

1

∆ ∆[

[

[

sin c

Veranschaulichung des nicht bandbegrenzten Abtastens

Maßnahmen beim Rendering

• Area-Sampling (endliche Apertur)– unweighted (Rechteck, wie beim CCD-Chip)

• Catmull [CATM 78]

– verbessert: A-Buffer (Pixelsubmasken)• Carpenter [CARP 84]

– weighted (welche Funktionen)• Abram, Westover, Whitted [ABRA 85]

• Supersampling und Digitale Filterung

Unweighted Area Sampling:Probleme

Weighted Area Samplingohne overlap

A-Buffer Algorithmus

A

B

=

=

0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 0

0 0 1 1 1 1 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 0

1 1 1 1 1 1 1 1

BetrachteterBereich

=

0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 0

0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 1 1 0 0 0

1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1

0 0 0 1 1 1 1 1

0 0 1 1 1 1 1 1

0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1

0 0 0 0 0 1 1 1

0 0 0 0 0 0 1 1

xor xor

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

=

A-Buffer AlgorithmusPro und Cons

• Pro: Geringerer Aufwand als Catmull

• Con: Kein Einfluß auf Nachbarpixel

Box-Filter (Rechteck) ist schlechter Tiefpaß

Weighted Area Sampling with Overlap

Weighted Area Sampling with Overlap nach [ABRA 85]

A B C

D E F

G H I

Supersampling: die diskrete Variante des Area Samplings

DigitalesBild

Graphik

n x m

n x m

pn x pm

Dig. Filter

Tiefpaß

Beispiele für Filterdesign

• Bartlett-Fenster: Dreieck– Gaus-Fenster

– Hanning-Fenster: Cosinusquadrat

– Kaiser-Bessel-Fenster

Beispiele für Filterkerne

1 2 3 4 3 2 12 4 6 8 6 4 23 6 9 12 9 6 34 8 12 16 12 8 43 6 9 12 9 6 32 4 6 8 6 4 21 2 3 4 3 2 1

1 4 8 10 8 4 1 4 12 25 29 25 12 4 8 25 49 58 49 25 8

10 29 58 67 58 29 10 8 25 49 58 49 25 8 4 12 25 29 25 12 4 1 4 8 10 8 4 1

7x7 Bartlett Filter 7x7 Gauss Filter

1 2 3 2 12 4 6 4 23 6 9 6 32 4 6 4 21 2 3 2 1

5x5 Bartlett Filter 3x3 Bartlett Filter

1 2 12 4 21 2 1

Weitere Möglichkeiten beim Filterdesign

• Tschebyscheff-Approximation:– füllt vorgegebenes Toleranzschema optimal aus

– konstante Welligkeit im Durchlaß- und Sperrbereich

– Achtung: die berechneten Koeffizienten müssen genau genug realisiert werden

– bei 8/9 Bit Wortlänge gehen Vorteile gegenüber Kaiser-Bessel verloren

SupersamplingPro und Cons

• Con: Löst das Aliasing-Problem 1. Art nur unvollständig: ������������ d.h. es gilt

• Artefakte sind durch nachträgliche Filterung nicht vollständig korrigierbar! aber

• Daumenregel: 4-faches Oversamplingliefert zufriedenstellende Ergebnisse bei scharfen Konturen Texturen können noch Probleme bereiten

Weitere Tricks

• “leichtes” Rauschen kann Effekte noch weiter reduzieren

• Achtung: nur subjektive Wirkung:

lediglich (für den Menschen) weniger störend

• vorsichtig einsetzen!

Bildüberlagerung������������ !!!����!����!���!"���

• Idee: die aufwendigen Operationen des Renderingwerden “offline” ausgeführt:“precomputed”

• Ergebnis wird “nur noch” zusammengesetzt • richtig gemacht lassen sich Bildteile selektiv

löschen und einschreiben • relativ einfache Operation nötig (s.u.)

Unterstützung durch Harrdwaremöglich

Einführung α-Channel

Pixel ist weder rot noch grünBeispiel: 70% grün, 30% rotBeim Rendering wird Überdeckungsinformation(coverage) generiert: ������������ ������������������� z.B. (0,1,0,0.7)

Überlagerung von Bildern

no overlap total overlap proportional overlap

α -Wert liefert keine geometrischen Angaben

Annahmen: (1) proportional overlap gilt !!!,(2) Gleichverteilung für Geometrie

dann gemeinsame Überdeckung = α Α α Β

30%

50%

Flächengrößen und mögliche Farben

���� ��� ������� �������

w eder-noch (1-α A) (1-α B) 0

nur A α A(1-α B) 0,A

nur B α B(1-α A) 0,B

beide α A α B0,A ,B

Potentielle Überlagerungsmöglichkeiten (1)

Es sei:Result. Farbe cComp und Coverage α Comp :

cComp = FA cA + FB cB

α Comp = FA α A + FB α B

FA, FB : Anteil des Pixels aus Bild A bzw. B

Quadrupel: Farben für die Fälle(weder A noch B, A, B, beide)

Potentielle Überlagerungsmöglichkeiten (2)

operation quadrup le diagram F A F B

clear (0, 0 , 0 , 0) 0 0

A (0, A , 0, A) 1 0

B (0 , 0 , B , B ) 0 1

A over B (0, A , B , A ) 1 1-α A

B over A (0, A , B , B ) 1-α B 1

A in B (0, 0 , 0 , A ) α B 0

B in A (0 , 0 , 0 , B ) 0 α A

A held out by B (0, A , 0, 0 ) 1-α B 0

B held out by A (0 , 0, B , 0) 0 1-α A

A atop B (0, 0 , B , A ) α B 1-α A

B atop B (0, A , 0, B ) 1-α B α A

A xor B (0, A , B , 0 ) 1-α B 1-α A

Weitere Funktionsmöglichkeiten mit dem α-Channel

• darken

• fade

• opaque

• fade (A,t) plus fade (B, 1-t)

Weitere hier nicht behandelte Probleme

• Wie gewinnt man α-Wert, wenn die Ausgangsbilder dies nicht haben:

siehe Fiskin-Barsky [FISH 84]

Zusammenfassung

• Supersampling (trotz der bekannten Nachteile) ist oft günstigste Alternative Auswahl geeigneter Filter nötig, ggf. Designvorgaben/Richtlinien ermitteln

• Compositing mit α-Channel ist geeignetes Update-Verfahren

• ggf. HW-Unterstützung realisieren