Quantisierung

Seminar MultimediadatenformateOliver Richter

ÜbersichtQuantisierung allgemeinQuantisierungsartenKodierungDesign eines Quantisierers

QuantisierungGrundlage für verlustbehaftete KomprimierungAbbildung auf endliche Menge von diskreten Werten Q : M C C = {m ,m ,..,m } Codebuch m Codewort

Zwei Arten der Quantisierung Skalarquantisierung Vektorquantisierung

i

n21

Quantisiererbesteht aus einem Encoder und Decoder

Encoder weist Signal einer Zelle zu Index

Decoder gibt Codewort des Index zurück

Encoder DecoderSignal BildIndex

Codebuch

PerformanceKompressionsrate

N Anzahl der Kodewörter k Länge der Kodewörter

Quantisierungsrauschen Snr

psnr

kNr 2log

WEICHUNGSTANDARTABApsnr 10log10

WEICHUNGSTANDARTABEingabedurschnsnr .log10 10

SkalarquantisierungAbbildung eines Skalars x auf Menge diskreter Werte yQ : x yAnwendung

AD Wandler Zeitabhängige signale

x1 x2 x n+1x n...X

y n

granular cell

overload cell

Entscheidungsgrenze

centroidy 1

Einteilunglinear nicht linear

AnwendungenAD Wandler

Audiosignale

VektorquantisierungVerallgemeinerung der SkalarquantisierungQ: R CAnwendung auf bereits digitalisierte Werte

Komprimierung Mustererkennung

vollständige Einteilung von R in paarweise disjunkte BereicheDie Entscheidungsgrenzen können beliebig geformt sein

k

k

VQ mit R2

Zentroid

Zellenwand

Nearest Neightbour Encoding

1. Setze d = d ; j = 1; i = 1;

2. Berechne D = d(x,y );3. IF D < d THEN D = d ; i = j;4. IF j < N THEN j++;

GOTO 2;5. END;

initial

jjj

SQ vs VQ

SQ vs VQ

Design eines VQ

Qualität eines Vektorquantisierer Größe des Codebuches Wahl der Codewörter

Möglichkeiten zur Verbesserung optimieren eines vorhandenen

Codebuches Geeignete Wahl eines Codebuches

Der Lloyd-Algorithmus1.:Wähle Startcodebuch C der Größe M;k=0;D =0; Wähle Genauigkeit a;2.:Bestimme Grenzen durch gewichteten Mittelwert von zwei benachbarten Codebucheinträgen3.:Bestimme Gesamtabweichung D4.:Ist beende

5.:k++;Bestimme neue Codebucheinträge (Schwerpunkte der Interwalle);

Gehe zu 2

(0)

(k)

aDDDk

kk

)(

1)(

Der LBG-Algorithmus1.:Wähle Startcodebuch C der Größe M;k=0;D =0; Wähle Genauigkeit a;2.:Bestimme Zellen (mit N. N. Regel)3.:Bestimme Gesamtabweichung D4.:Ist beende

5.:K++; Bestimme neue Codebucheinträge (Schwerpunkte der Interwalle);

Gehe zu 2

(0)

aDDDk

kk

)(

1)(

(k)

LBG mit Trainingsvektoren1.:Wähle Startcodebuch C der Größe M;k=0;D =0; Wähle Genauigkeit a;2.:Bestimme Zellen (mit N. N. Regel)3.:Berechne Durchschnitt und D zwischen Codevektor und Trainingsvektoren4.:Ist beende

5.:K++; Bestimme neue Codebucheinträge (Schwerpunkte der Interwalle); Gehe zu 2

(k)

aDDDk

kk

)(

1)(

Bsp.:Größe/Gewicht

Start-Codebuch

Start

Ziel

Alternatives Start-Codebuch

Start

Ziel

Splitting - Methode

1. Schwerpunkt der Trainingsvektoren erster Codebuchvektor2. Codebuchvektor ersetzen durch

Codebuchvektor + Abweichung Codebuchvektor - Abweichung

3. LBG Ausführen4. Gehe zu 2 bis Codebuch vollständig

Startaufteilung

Erste Iteration

Fertiger Durchlauf

Pairwise next neighbor1. Anfangscodebuch = Menge der Testvektoren2. Finde die am nächsten zusammenliegenden Vektoren3. Bilde Mittelwert der Vektoren und ersetze beide durch ihn4. Wenn gewünschte Größe erreicht beende sonst gehe zu 2.

BildkomprimierungEinteilen in kleine BlöckeBlöcke umformen in Vektoren

Vektoren als Testvektoren für LBG verwenden und Codebuch erstellenKodieren

Bilder

AbschlussVQ kann optimale Partizionierung darstellenEinfache Kodierung mit N. N.Verbesserung der Partizionierung mit LBG AlgorithmusPartizionierung hängt stark von der Wahl des Start-Codebuches ab

LiteraturDatenkompression M. Liskiefwicz, H. FernauUniversität TübingenScalar Quantization B. Schoofs, S. ReinartzTH AachenVektorquantisierung Y. Qui TH AachenArtificial Intelligence Charniak, F. McDermottAddison WesleyImage Compression using Vector QuantisationReCCIT