3 Interpolation

3 Interpolation

3.1 Anwendung der Interpolation

Nach der Vorstellung unterschiedlicher numerischer Optimierungsstrategien im vorausgegangenen Kapitel beschäftigt sich dieser Abschnitt mit der räumlichen Aufwärtskonversion von Einzelbildern. Die grundsätzliche Aufgabe einer Formatkonversion besteht in der Verbesserung der Wiedergabequalität eines Bildes oder einer Bildsequenz. Zur Interpolation werden einer Zielsequenz Informationen hinzugefügt, die nicht im Ausgangsmaterial vorhanden sind. Man unterscheidet zwei Arten der Konversion: Die örtliche und die zeitliche Interpolation [Schmidt96].

Die zeitliche Interpolation wird benötigt, um die Bildwiederholfrequenzen unterschiedlicher Systeme einander anzupassen. Beispielsweise kann dies eine mit fünfzehn Bildern pro Sekunde erstellte Bildsequenz sein, die auf einem Computermonitor mit 70 Hertz wiedergegeben wird. Ein weiteres Anwendungsgebiet ist die Erhöhung der Bildwiederholrate etwa zur Verringerung des Großflächenflimmerns bei 100 Hz-Fernsehern.

Örtliche Interpolationstechniken werden zum Zoomen bzw. Vergrößern von Bildern eingesetzt. Dabei werden dem Bild Bildpunkte in horizontaler, vertikaler und diagonaler Richtung hinzugefügt. Ein Beispiel gibt Abbildung 3.1. Das Originalbild wurde sowohl in der Bildbreite als auch Bildhöhe verdoppelt, so dass im interpolierten Bild die vierfache Anzahl von Bildpunkten entsteht.


Interpolation
Abbildung 3.1: Interpolation durch Pixelwiederholung

In Abbildung 3.2 wurde das Originalbild interpoliert und gefiltert. Dabei wurden die neuen Bildpunkte durch eine Filterung aus den vorhandenen erzeugt. Dieses Verfahren führt zu einer sichtbar besseren Darstellungsqualität der diagonalen Linie, als die in Abbildung 3.1 dargestellte Pixelwiederholung.


Interpolation
Abbildung 3.2: Interpolation und Filterung

3.2 Grundlagen digitaler Filter

Bei einem diskreten Übertragungssystem nach Abbildung 3.3 wird einer Eingangsfolge s(n) eine Ausgangsfolge g(n) zugeordnet. Wird als Eingangssignal die Einheitsimpulsfolge δ(n) gewählt, führt dies zu einer für das System typischen Antwort. Eine solche Reaktion des Systems auf einen Impuls wird Impulsantwort h(n) genannt.


Übertragungssystem
Abbildung 3.3: Diskretes Übertragungssystem

Die Einheitsimpulsfolge wird über

Formel

definiert. Abbildung 3.4 zeigt die Impulsfolge δ(n) und ein Beispiel für eine Impulsantwort.


Impulsantwort
Abbildung 3.4: δ-Impuls und Beispiel für eine Impulsantwort

Ein lineares und verschiebungsinvariantes diskretes System (LVI-System) lässt sich durch seine Impulsantwort vollständig beschreiben. Mit Hilfe der Impulsantwort kann die Ausgangsfolge g(n) durch die Eingangsfolge s(n) bestimmt werden:

Formel

Diese Operation wird als diskrete Faltung bezeichnet. Die Summenformel kann auch durch den Faltungsoperator "*" beschrieben werden [Wendland95].

Ein nicht rekursives Filter besitzt eine Impulsantwort mit einer endlichen Anzahl an Werten, die nicht Null sind. Darum werden diese Filterarten als FIR-Filter (Finite Impulse Response) bezeichnet. Im Gegensatz dazu werden rekursive Filter IIR-Filter (Infinite Impulse Response) genannt. In dieser Studienarbeit werden aufgrund der bei FIR-Filtern einfach erreichbaren Linearphasigkeit nur FIR-Filter betrachtet. Zudem bleibt durch die Verwendung von FIR-Filtern die Stabilität des Systems gewährleistet. Der schematische Aufbau eines FIR-Filters ist in Abbildung 3.5 dargestellt. Die Größe T stellt dabei eine Verzögerung um einen Abtastwert dar.


FIR-Filter
Abbildung 3.5: FIR-Filter

Wird das System durch einen Impuls angeregt, durchläuft er sequentiell alle Laufzeitglieder und erscheint mit dem jeweiligen Filterkoeffizienten ai gewichtet am Ausgang. Daher entspricht die Impulsantwort eines FIR-Filters seinen Koeffizienten. Das Ausgangssignal g(n) ergibt sich nach [Wendland95] über die diskrete Faltung mit h(n) = {a0, a1, ..., aM} zu

Formel

In der Bildverarbeitung werden oft linearphasige Filter mit gleicher Laufzeit für alle Frequenzkomponenten des Eingangssignals gefordert, was durch Filter mit symmetrischen Impulsantworten realisiert werden kann. Die Forderung nach einer symmetrischen Impulsantwort führt zu symmetrischen Koeffizienten (Abbildung 3.6) [Wendland95].


FIR-Filter
Abbildung 3.6: Linearphasiges FIR-Filter mit ungerader Koeffizientenzahl

Zweidimensionale Eingangsfolgen, wie sie in der Bildverarbeitung auftreten, können auf entsprechende Weise behandelt werden. Ein zweidimensionales Übertragungssystem ist in Abbildung 3.7 dargestellt.


Übertragungssystem
Abbildung 3.7: Zweidimensionales Übertragungssystem

Die diskrete 2D-Faltung verläuft anlog zum eindimensionalen Fall:

Formel

Die Operation kann durch "**" verkürzt geschrieben werden. Eine Realisierung eines 2D-FIR-Filters kann aus der diskreten 2D-Faltung entwickelt werden [Schröder98]:

Formel

3.3 Grundlagen der Interpolation

Bei einer Interpolation wird die Abtastrate einer Signalsequenz um einen Faktor heraufgesetzt, bei einer Dezimation wird die Abtastrate verringert. Es brauchen nur ganzzahlige Abtastratenumsetzungen untersucht zu werden, da sich nichtganzzahlige Umsetzungen aus Kombinationen von Interpolations- und Dezimationsschritten entwickeln lassen. Die Verkürzung des Abtastintervalls bzw. das Heraufsetzen der Abtastrate um den Faktor M wird durch

Formel

beschrieben. T beschreibt den Zeitraum zwischen zwei Abtastungen, f0 die Abtastfrequenz. Das Schema der Interpolation ist in Abbildung 3.8 dargestellt [Schröder96].


Interpolation
Abbildung 3.8: Interpolation

Für das interpolierte Signal gilt:

Formel

Es werden also zwischen jedem Abtastwert M - 1 Nullwerte eingefügt. Diese Aufwärtstastung ist für M = 3 in Abbildung 3.9 illustriert.


Aufwärtstastung
Abbildung 3.9: Aufwärtstastung für M = 3

Die Spektren der Signale ergeben sich durch

Formel

Abbildung 3.10 zeigt die beiden Spektren für M = 3 im Vergleich.


Spektren
Abbildung 3.10: Spektren des Originalsignals und nach Abtastratenumsetzung

Offensichtlich sind beide Spektren bis auf die unterschiedliche Skalierung der Frequenzachse identisch. Das ist plausibel, da die Nullwerte an Stellen in s(n) eingefügt wurden, die zuvor schon Null waren (Abbildung 3.9). Um die in der interpolierten Signalsequenz vorhandenen Zwischenspektren zu entfernen, ist eine Tiefpassfilterung notwendig. Dies ist in Abbildung 3.11 dargestellt. Abbildung 3.12 zeigt einen idealen Interpolator aus einer Reihenschaltung eines Abtastratenumsetzers und eines Tiefpassfilters [Schröder96].


Spektrum
Abbildung 3.11: Spektrum nach Tiefpassfilterung

Interpolator
Abbildung 3.12: Idealer Interpolator

Alternativ zum Einfügen von Nullstellen ist auch ein Halten der vorhandenen Abtastwerte möglich. Der jeweilige ursprüngliche Abtastwert wird M - 1 mal wiederholt. Dies ist in Abbildung 3.13 skizziert [SchröBlu99].


Interpolation
Abbildung 3.13: Interpolation mit Halten

Für die zweidimensionale Abtastratenumsetzung sind auch zweidimensionale Filter erforderlich. Die Umsetzfaktoren können für beide Dimensionen unterschiedlich ausgelegt werden, um beispielsweise ein Fernsehbild im 4:3-Format an eine Wiedergabe im 16:9-Format anzupassen. Wie bei der eindimensionalen Interpolation werden im zweidimensionalen Fall Mx - 1 Werte zwischen jedem Abtastwert in x-Richtung und My - 1 Werte in Richtung der y-Achse eingefügt. Dies ist für Mx = My = 2 in Abbildung 3.14 gezeigt. Die schwarzen Rechtecke stellen die Originalabtastwerte dar, die weißen die einzufügenden Werte.


Aufwaertstastung
Abbildung 3.14: 2D-Aufwärtstastung für Mx = My = 2

3.4 Digitale Filter zur Interpolation

3.4.1 Lineare Filter

Im Allgemeinen ist für die Berechnung der Luminanz eines Bildpunktes (Pixels) mittels eines digitalen Filters auch die Umgebung dieses Punktes zu betrachten. Ein neues Pixel qlk wird durch die Verknüpfung der originalen Pixel pij mit einem Operatorfenster gebildet. Weitere Bildpunkte werden durch die spalten- und zeilenweise Verschiebung des Fensters erzeugt. Zur Verdeutlichung dieses Vorgangs dient Abbildung 3.15.


Fenster
Abbildung 3.15: Fenster eines lokalen Operators zur Berechnung von p33

Die Operatorfunktionen können auf unterschiedliche Weise generiert werden, etwa durch lineare Beziehungen oder durch nichtlineare Beziehungen, wie sie bei Medianfiltern verwendet werden. Ein linearer Operator lässt sich durch die zweidimensionale Faltung mit der Impulsantwort eines zweidimensionalen Filters beschreiben [Schröder98]:

Formel

Für die Ausdehnung des Filterfensters Nx und Ny werden im Folgenden nur ungerade Werte betrachtet. Die Impulsantwort h(nx,ny) ist identisch mit den Koeffizienten des Filters, die im Fall dieser Studienarbeit durch numerische Verfahren optimiert werden sollen. Zur Generierung eines neuen Bildpunktes sind Nx · Ny Additionen und ebenso viele Multiplikationen erforderlich. Durch die Forderung nach symmetrischen Filtermasken, welche für linearphasige Filter notwendig sind, kann die Zahl der unterschiedlichen verwendeten Filterkoeffizienten K erheblich reduziert werden, nämlich auf N2 Additionen und K Multiplikationen (für Nx = Ny = N):

Formel

Für den in Abbildung 3.16 dargestellten Fall N = 5 sind folglich statt 25 Multiplikationen nur noch sechs (x0 bis x5) Multiplikationen notwendig. Der Rechenaufwand für die numerischen Optimierungsverfahren bzw. die Ordnung des Optimierungsproblems wird ebenfalls stark verringert.


x4 x5 x2 x5 x4
x5 x3 x1 x3 x5
x2 x1 x0 x1 x2
x5 x3 x1 x3 x5
x4 x5 x2 x5 x4
Abbildung 3.16: Symmetrisches Fenster zur Berechnung von x0

Lineare Operatoren werden häufig in der Bildverarbeitung verwendet, z. B. zur Kontrastanhebung (Hervorhebung von Kanten und Konturen) und zur Rauschunterdrückung. Lineare Filter sind einfach zu realisieren, aber liefern nicht immer eine ausreichende Bildqualität. So ist mit einer Tiefpassfilterung zur Rauschunterdrückung auch eine Auflösungsreduktion verbunden. Daher werden zur Signalverarbeitung vielfach nichtlineare Operatoren verwendet [Schröder98].

3.4.2 Medianfilter

Nichtlineare Filter bilden ebenso wie lineare Systeme ein Signal x auf ein Signal y ab. Da aber durch die Nichtlinearität das Superpositionsgesetz nicht mehr gilt, kann das Ausgangssignal eines Systems nicht mehr durch die Faltung zwischen Eingangssignal und Impulsantwort bestimmt werden. Nichtlineare Filter werden daher durch Methoden beschrieben.

Medianfilter gehören zur Gruppe der Rangordnungsfilter. Ein Rangordnungsfilter sortiert die Werte einer Eingangsfolge der Größe nach und wählt den Ausgangswert in Abhängigkeit von der Ordnungsposition. Für Medianfilter wird das mittlere Element der sortierten Eingangssequenz verwendet. Neben Medianfiltern sind Minimum- und Maximumfilter, die das erste x1 oder letzte Element xn der Folge benutzen, gebräuchlich. Für eine Eingangssequenz mit ungerader Länge n gilt

med(xi) = x(ν+1),   n = 2 + 1 ,

bei gerader Länge [Schröder98]

med(xi) = ½(x(ν) + x(ν+1)),   n = 2 .

Die Ausgangsfolge yi eines eindimensionalen Medianfilters mit der Eingangsfolge xi ergibt sich durch

yi = med(xi-ν, ..., xi, ..., xi+ν),   iZ

für einen zweidimensionalen Median gilt

yij = med(xi+r, j+s),   (r, s) ∈ A,   i, jZ2

Die Menge A ∈ Z2 beschreibt hierbei das Filterfenster, welches die benachbarten Punkte des zentralen Pixels (i, j) beinhaltet.

Die Bildung eines Medians wird durch Abbildung 3.17 verdeutlicht. Aus einer in aufsteigender Reihenfolge sortierten Eingangsfolge ergibt sich der Median aus der mittleren Rangordnung der geordneten Folge.


Medianbildung
Abbildung 3.17: Medianbildung

Abbildung 3.18 gewährt einen Einblick in die Wirkungsweise eines Medianfilters der Länge n = 3. Eine wichtige Eigenschaft von Medianfiltern, nämlich Impulse zu unterdrücken, wird dabei deutlich.


Medianfilterung
Abbildung 3.18: Eindimensionale Medianfilterung

Ein weiteres Kennzeichen der Medianfilter ist die Erhaltung von Kanten im gefilterten Bild. Eine lineare Tiefpassfilterung hingegen unterdrückt die hochfrequenten Anteile eines Bildes, welche die Kanten und Konturen erzeugen, und führt so zu unscharfen Darstellungen. Daher eignen sich Medianfilter für viele Anwendungen der Bildsignalverarbeitung. Ein Beispiel für die Kantenerhaltung zeigt Abbildung 3.19. Außerdem sind Medianfilter aufgrund ihrer Fähigkeit zur Impulsunterdrückung zur Reduktion von Impulsrauschen geeignet [Schröder98].


Filterung
Abbildung 3.19: Unterschiedliche Filterung einer idealen Kante

Bei den bisher beschriebenen Standard-Medianfiltern besitzen alle Abtastwerte innerhalb des Filterfensters den gleichen Einfluss auf das Ausgangssignal. Um Abtastwerten an bestimmten Filterfensterpositionen stärkere Gewichtung zu verleihen, wurden gewichtete Medianfilter (Weighted Median WE) eingeführt. Auch hierbei wird die Eingangsfolge aufsteigend sortiert, aber anschließend werden die Eingangswerte ihrer Gewichtung entsprechend vervielfacht. Formal ergibt sich nach [Schröder98] für den Ausgangswert yi eines gewichteten Medianfilters der Ausdruck

yi = med(w1x1, w2x2, ..., wnxn) .

Dabei stehen wi für die einzelnen Gewichtungen und ◊ für den Vervielfachungsoperator mit

Formel

Als Beispiel für ein gewichtetes Medianfilter dient Abbildung 3.20. Nach Sortierung der Eingangssequenz werden die Abtastwerte vervielfacht und der Median gebildet. Durch die Gewichtung ergibt sich ein anderer Wert als im vorausgegangenen Fall.


Medianbildung
Abbildung 3.20: Bildung eines gewichteten Medians

Einen Spezialfall stellen zentral gewichtete Medianfilter (Center Weighted Median CWM) dar. Hierbei erhält jeder Abtastwert das Gewicht wi = 1, nur der zentrale Abtastwert bekommt die Gewichtung w0 = 2 k + 1. Dadurch ist gewährleistet, dass die Summe aller Gewichtungen ungerade ist. Für einen zentral gewichteten Median gilt nach [Schröder98]:

yi = med(xi, ..., xi-1, (2 k + 1) ◊ xi, xi+1, ..., xi) .

Ein k von 0 beschreibt ein Standard-Medianfilter, ein k ◊ ν erzeugt ein Identitätsfilter, welches das Eingangssignal unverändert an den Ausgang weiterleitet.

Da die Gewichtungen die Anzahl der Vervielfachungen eines Abtastwertes angeben, kommen als Gewichtungen nur positive ganzzahlige Werte in Frage. Dadurch werden zur Erzeugung der Filterkoeffizienten auch neue Ansätze für die numerischen Optimierungsstrategien notwendig.


Kapitel2 Zurück Kapitel4