PatentDe  


Dokumentenidentifikation DE4143204C2 03.04.1997
Titel Quantisierungsverfahren zur Verwendung bei der Bildkompression
Anmelder Ricoh Co., Ltd., Tokio/Tokyo, JP
Erfinder Allen, James Dow, Santa Cruz, Calif., US;
Blonstein, Steven Michael, San Jose, Calif., US
Vertreter Schwabe, H., Dipl.-Ing.; Sandmair, K., Dipl.-Chem. Dr.jur. Dr.rer.nat.; Marx, L., Dipl.-Phys. Dr.rer.nat., Pat.-Anwälte, 81677 München
DE-Anmeldedatum 30.12.1991
DE-Aktenzeichen 4143204
Offenlegungstag 09.07.1992
Veröffentlichungstag der Patenterteilung 03.04.1997
Veröffentlichungstag im Patentblatt 03.04.1997
IPC-Hauptklasse G06T 9/00
IPC-Nebenklasse H04N 1/415   

Beschreibung[de]

Die Erfindung betrifft ein Quantisierungsverfahren zur Verwendung bei der Bildkompression nach dem Oberbegriff des Patentanspruches.

Aus der Literaturstelle Birch, Thomas: "Datenkompression löst Übertragungs- und Speicherprobleme", in Elektronik 19/15.9.89, Seiten 44 bis 49, ist ein Datenkompressionsverfahren bekannt, welches auf dem Prinzip der sog. diskreten Kosinustransformation basiert. Bei dieser Art Transformationscodierung wird das Eingangsbild in Blöcke aufgeteilt, um die lokalisierte räumliche 2D-Korrelation der Pixel zu nutzen. Die Größe eines Blocks wird durch die statistische Korrelation der Pixel und durch das Bildformat bestimmt.

Aus der US 4,698,689 ist ein System und ein Verfahren zum progressiven Übertragen und Rekonstruieren eines Bildes bekannt. Gemäß diesem bekannten Verfahren wird ein zu übertragendes Bild in eine Anordnung von Bildelementblöcken aufgeteilt und es werden die Daten für jeden Block einer zweidimensionalen Transformation unterzogen, um Transformationskoeffizienten zu erzeugen. Die Transformationskoeffizienten werden in Folgen von Sätzen von quantisierten Transformationskoeffizienten quantisiert, so daß jeder quantisierte Transformationskoeffizient durch eine Anzahl von Bits wiedergegeben wird. Es werden unterschiedliche Zahlen von Bits jedem quantisierten Transformationskoeffizienten jedes Satzes der Folge zugeordnet, um den entsprechenden Transformationskoeffizienten detaillierter darstellen zu können. Während jeder einer Vielzahl von Übertragungsfolgen werden Differenzen zwischen jedem Satz eines quantisierten Transformationskoeffizienten und dem vorhergehenden Satz der Folgen jedes Blocks übertragen. Die Signale, welche die Differenzen zwischen jedem Satz wiedergeben, werden auf der Empfangsseite verbunden, um dadurch kumulative quantisierte Transformationskoeffizienten für jeden Satz zu erzeugen. Die kumulativ quantisierten Transformationskoeffizienten werden dann decodiert bzw. dequantisiert, um Transformationskoeffizienten zu rekonstruieren und schließlich die Bilddaten wieder zu rekonstruieren, um aus diesen die jeweiligen Bildelemente jedes Blocks zu formen. Bei der bei diesem bekannten Verfahren durchgeführten zweidimensionalen Transformation wird keinerlei Größenbewertung irgendwelcher Parameter vorgenommen.

Die der Erfundung zugrundeliegende Aufgabe besteht darin, ein Quantisierungsverfahren zur Verwendung bei der Bildkompression der eingangs definierten Art zu schaffen, welches ohne nachteilige Beeinträchtigung der Bildqualität eine noch höhere Bildkompression unter Verwendung vergleichsweise einfacher technischer Einrichtungen ermöglicht.

Diese Aufgabe wird erfindungsgemäß durch die im Kennzeichnungsteil des Patentanspruches aufgeführten Merkmale gelöst.

Das erfindungsgemäße Verfahren führt zu überraschenden Vorteilen, und zwar beispielsweise zu einer Verringerung von Bildfehlern, insbesondere in spezifischen Eckbildpunktbereichen und führt auch zu einer 3-6%igen Verbesserung bezüglich der Kompression.

Im folgenden wird die Erfindung anhand von Ausführungsformen unter Hinweis auf die Zeichnungen näher erläutert.

Es zeigt:

Fig. 1 den Datenfluß für eine typische Bildkompressionseinrichtung;

Fig. 2a und 2b die allgemeine Anordnung von Transformationskoeffizienten, wie sie bei Bildkompressionstechniken verwendet werden;

Fig. 3 eine Erläuterung der Berechnung der Quantisierung;

Fig. 4 eine Darstellung eines Blockes von Bildpunkten (Pixel); und

Fig. 5 und 6 die Ergebnisse der Quantisierung typischer Testbilder mit Merkmalen nach der vorliegenden Erfindung.

Nachstehend wird im einzelnen auf die bevorzugten Ausführungsformen der Erfindung Bezug genommen, und Beispiele der Erfindung sind in den beigefügten Figuren erläutert. Bei der Erfindung sind Alternativen. Modifikationen und Äquivalente möglich, die innerhalb des Rahmens der Erfindung liegen.

In Fig. 1 zeigt der Datenfluß Bildpunkte, die am Vorderende 10 des Systems eingegeben werden. Eine typische Darstellung der Bildpunktwerte ist 0 bis 255 oder -128 bis +127. Diese Werte erfordern zu ihrer Darstellung 8 Datenbits.

Die zweite Stufe ist die Transformation 20. Zwar umfaßt die Transformation eine Multiplikation und/oder Additionen mit anderen als ganzzahligen Faktoren, jedoch besteht das Endergebnis der Transformation in 64 Frequenzkoeffizienten, deren Bereich typischerweise -1024 bis +1023 beträgt. Diese können durch Zahlen mit 11 Bit dargestellt werden. Diese Zahlen werden immer noch als ganzzahlig angesehen.

Die dritte Stufe 24 stellt den Bereich des wirklichen Interesses dar. Es ist die Quantisierung, die tatsächlich dadurch die Kompression erzielt, daß viele der Hochfrequenzkomponenten auf Null reduziert werden. Die Quantisierung kann sich abhängig von dem betreffenden Koeffizienten ändern. Empirische Untersuchungen haben gezeigt, daß einige Koeffizienten "unterdrückt" werden können, ohne daß dies einen nachteiligen Effekt auf die Bildqualität hat. Die tatsächliche numerische Operation für die Quantisierung besteht in einer Division durch einen Quantisierungsfaktor Q. Ist das Ergebnis eine Zahl x (wie in Fig. 3 gezeigt), dann läßt sich x ausdrücken als:

x=C/Q

wobei C der Koeffizientenwert vor der Quantisierung ist.

Zwar liegen zulässige Werte für C in dem Bereich von -1024 bis +1024, und für Q beträgt der Bereich 1 bis 512, jedoch werden typische Werte für diese beiden im allgemeinen kleiner sein. Häufig wird die Division von C durch Q eine kleine Zahl in dem Bereich von -5 bis +5 ergeben. Bei diesen kleinen Zahlen kann der Wert rechts vom Dezimalpunkt einen kritischen Effekt auf den für x gewählten ganzzahligen Wert haben. Ein einfaches Abschneiden des Anteils rechts vom Dezimalpunkt wäre nicht zu akzeptieren.

Der vorgeschlagene internationale Standard JPEG schlägt das nachfolgende Schema zum Abrunden des Wertes x vor:

-0,5 x +0,5 führt zu x = 0

0,5 x +1,5 führt zu x = 1

1,5 x 2,5 führt zu x = 2 usw.

Die vorliegende Erfindung (die als "Z"-Quantisierung bezeichnet wird) verwendet folgende Metrik:

-0,625 x +0,625 führt zu x = 0

0,625 x +1,625 führt zu x = 1

1,625 x +2,625 führt zu x = 2

Auf den ersten Blick mag der Unterschied zwischen den beiden Vorgehensweisen sehr gering erscheinen. Allerdings stellt der Nettoeffekt bezüglich des Kompressionsverhältnisses für einen vorgegebenen Fehlerpegel eine Verbesserung von 3-6% dar. Eine Beschreibung des Codierers hilft dabei, die Gründe zu verstehen.

Fig. 2a zeigt die allgemeine Anordnung für die 64 Transformationskoeffizienten. Der Gleichspannungswert liegt in der oberen linken Ecke, und die übrigen 63 Wechselspannungskoeffizienten sind in der Reihenfolge ansteigender horizontaler und vertikaler Frequenz angeordnet, wenn man sich zur unteren rechten Ecke hin bewegt.

Fig. 2b zeigt einige typische Werte, die bei einem 8×8-Bildpunktblock auftreten können. Der internationale Standard erfordert es, daß der Codierer "zickzackartig" die Wechselspannungskoeffizienten abtastet. Der Grund für diese Vorgehensweise liegt darin, Folgen von Nullen zu verlängern, bei welchen die größte Kompression erzielt wird. Wie in dieser Figur gezeigt ist, führen "verstreute" Werte (die in Fig. 2b hervorgehoben sind) häufig dazu, eine ansonsten lange Folge von Nullen zu unterbrechen. Nunmehr wird angenommen, daß der Wert bei dem markierten "verstreuten" Bildpunkt 1 vor dem Abrunden 0,609 betrug. Unter Verwendung der JPEG-Metrik wird der Wert auf 1 aufgerundet.

Die vorliegende Erfindung rundet den Wert von 0,609 auf 0 ab. Bei dem JPEG-System werden die letzten 18 Koeffizienten als 10 Nullen, eine 1, und dann 7 Nullen codiert. Bei der vorliegenden Erfindung werden die letzten 18 Koeffizienten als eine Folge von 18 Nullen codiert. Das Nettoergebnis sind längere Folgen von Nullen, und daher rührt die Bezeichnung "Z"-Quantisierung (von "Zero": englisch für "Null").

Einer der großen Vorteile des verbesserten Quantisierungsverfahrens besteht darin, daß dieses 100%ig kompatibel mit dem vorgeschlagenen Standard ist. An dem Dekompressionsende des Systems muß der Dekompressor nicht wissen, ob "JPEG" oder "Z" während der Quantisierung verwendet wurde.

Die Auswahl des Wertes 0,625 für die "Z"-Quantisierung scheint aus unterschiedlichen Gründen optimal zu sein. Selbst wenn dies so ist, können allerdings andere Werte als 0,5 für die "Z-"-Quantisierung akzeptierbar sein. Ein höherer Wert wie beispielsweise 0,75 könnte möglicherweise hohe Bitratenkompressionen beeinträchtigen, bei welchen die Genauigkeit wesentlich ist. Ein Wert von weniger als 0,625 könnte möglicherweise nur zu einem Gewinn von etwa 1 - 2% führen und daher den Aufwand nicht rechtfertigen.

Die Auswahl von 0,625 ergibt 3-6% und läßt sich einfach durch Hardware oder Software implementieren. Hierzu wird beispielsweise der Ausgangswert der x=C/Q-Berechnung betrachtet, wie in Fig. 3 dargestellt.

Nach dem Runden ist der Wert x eine ganze Zahl mit 11 Bit. Das Abrunden erfordert eine Untersuchung von Bits rechts von der Dezimalstelle (b-1bis b-3). Der JPEG-Algorithmus muß nur das Bit b-1 zur Durchführung der Rundung in Betracht ziehen:

wenn b-1 = 1 und b 10 = 0, dann addiere 1 zu x.

Das "Z"-Quantisierungsverfahren gemäß der vorliegenden Erfindung erfordert für das Abrunden nur einen geringfügig komplizierteren Algorithmus:

wenn b-1 = 1 und (b-2 oder b-3 = 1) und b¹º = 0, dann addiere 1 zu x.

Eine entsprechende Vorgehensweise läßt sich auf negative Zahlen anwenden.

Ergebnisse

Die diskrete Kosinus-Transformation führt zum Auftreten unterschiedlicher Fehlergrade an unterschiedlichen Stellen in dem 8×8-Bildpunktblock. Zu Vergleichszwecken werden die Daten in den Ecken-Bildpunkten "A" und den Zentrumsbildpunkten "B" betrachtet. Fig. 4 zeigt eine Darstellung des Bildpunktblocks.

Das vorgeschlagene "Z"-Quantisierungsverfahren verringert überall die Fehler, ist jedoch besonders wirksam bei den Eckenbildpunkten "A".

Die Fig. 5 und 6 zeigen die Ergebnisse für ein typisches Testbild. Bei vorgegebenen Bitraten ist das "Z"-Quantisierungsverfahren geringfügig besser als JPEG bei den Zentrumsbildpunkten (vgl. Fig. 5, wobei beachtet werden muß, daß ein höheres Signal-Rauschverhältnis einem geringeren Fehler entspricht). An den Eckenbildpunkten "B" ist der Unterschied erheblich signifikanter. Dies ist der Ort, aus welchem der hauptsächliche Gewinn kommt, wie in Fig. 6 gezeigt ist.

Eine sehr einfache Änderung der Quantisierungsschaltkreise in einem JPEG-Bildkompressionssystem kann signifikante Verbesserungen des Kompressionsverhältnisses (3-6%) bei sehr geringen zusätzlichen Kosten erreichen. Das Quantisierungsverfahren bleibt mit dem vorgeschlagenen Standard vollständig kompatibel. Die Auswahl des Wertes 0,625 scheint annähernd optimal zu sein, sowohl unter Berücksichtigung des Wirkungsgrades als auch der einfachen Implementierung.

Die voranstehenden Beschreibungen bestimmter Ausführungsformen der vorliegenden Erfindung wurden zum Zwecke der Erläuterung und der Beschreibung präsentiert. Die Ausführungsformen wurden zu dem Zwecke ausgesucht und beschrieben, um die Grundlagen der Erfindung und deren praktische Umsetzung am besten zu erläutern, um es hierdurch anderen Fachleuten zu ermöglichen, die Erfindung und unterschiedliche Ausführungsformen mit verschiedenen Modifikationen am besten einzusetzen, wie es für den betreffenden Verwendungszweck gerade erforderlich ist.


Anspruch[de]
  1. Quantisierungsverfahren zur Verwendung bei der Bildkompression, wonach Eingangsbildpunktdaten von N × N-Bildpunktblöcken empfangen werden, die Daten der Bildpunktblöcke in ein Frequenzbereichsformat transformiert werden, was zu mehreren Frequenztransformationskoeffizienten einschließlich eines Gleichspannungskoeffizienten und mehrerer Wechselspannungskoeffizienten führt, dadurch gekennzeichnet, daß
    1. a) die Frequenzkomponenten quantisiert werden, um eine ganze Zahl mit mehreren Bits zu bilden, einschließlich einem höchstwertigen Bit und einschließlich zumindest dreier Kommastellenbits, wobei
    2. a1) ein Parameter x auf Null (x = 0) gesetzt wird, wenn der Parameter x in einen Bereich

      -0,625 < x < +0,625 fällt,

    3. a2) der Parameter x auf 1 (x = 1) gesetzt wird, wenn der Parameter x in einen Bereich

      0,625 < x < +1,625 fällt,

    4. a3) der Parameter x auf 2 (x = 2) gesetzt wird, wenn der Parameter x in einen Bereich

      1,625 < x < +2,625 fällt

      wobei der Parameter x gegeben ist als

      x = C/Q,

      mit
    5. C = Koeffizientenwert vor der Quantisierung und

      Q = Quantisierungsfaktor,
    6. b) das erste Kommastellenbit und das zweite oder dritte Kommastellenbit geprüft werden,
    7. c) das höchstwertige Bit geprüft wird, und
    8. d) eine Eins zu der ganzen Zahl addiert wird, wenn das erste Kommastellenbit und das zweite oder dritte Kommastellenbit eine Eins sind und das höchstwertige Bit eine Null ist.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com