DE4143204C2 - Quantisierungsverfahren zur Verwendung bei der Bildkompression - Google Patents

Description

Die Erfindung betrifft ein Quantisierungsverfahren zur Verwendung bei der Bildkom­ pression 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 Datenkompres­ sionsverfahren bekannt, welches auf dem Prinzip der sog. diskreten Kosinustransforma­ tion 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 Transformations­ koeffizienten jedes Satzes der Folge zugeordnet, um den entsprechenden Transforma­ tionskoeffizienten detaillierter darstellen zu können. Während jeder einer Vielzahl von Übertragungsfolgen werden Differenzen zwischen jedem Satz eines quantisierten Trans­ formationskoeffizienten und dem vorhergehenden Satz der Folgen jedes Blocks über­ tragen. Die Signale, welche die Differenzen zwischen jedem Satz wiedergeben, werden auf der Empfangsseite verbunden, um dadurch kumulative quantisierte Transformations­ koeffizienten für jeden Satz zu erzeugen. Die kumulativ quantisierten Transformations­ koeffizienten werden dann decodiert bzw. dequantisiert, um Transformationskoeffizien­ ten zu rekonstruieren und schließlich die Bilddaten wieder zu rekonstruieren, um aus diesen die jeweiligen Bildelemente jedes Blocks zu formen. Bei der bei diesem bekann­ ten Verfahren durchgeführten zweidimensionalen Transformation wird keinerlei Größen­ bewertung 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 Bildkom­ pression unter Verwendung vergleichsweise einfacher technischer Einrichtungen er­ möglicht.

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

Das erfindungsgemäße Verfahren führt zu überraschenden Vorteilen, und zwar beispiels­ weise zu einer Verringerung von Bildfehlern, insbesondere in spezifischen Eckbildpunkt­ bereichen 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 beige­ fü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 Dar­ stellung 8 Datenbits.

Die zweite Stufe ist die Transformation 20. Zwar umfaßt die Transforma­ tion eine Multiplikation und/oder Additionen mit anderen als ganzzahli­ gen 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 Quantisie­ rung, 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 Bildqua­ litä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üc­ ken 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 kriti­ schen Effekt auf den für x gewählten ganzzahligen Wert haben. Ein ein­ faches 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 Vorgehens­ weisen sehr gering erscheinen. Allerdings stellt der Nettoeffekt bezüg­ lich 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 Transformationskoeffi­ zienten. 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än­ gern, bei welchen die größte Kompression erzielt wird. Wie in dieser Figur gezeigt ist, führen "verstreute" Werte (die in Fig. 2b hervorge­ hoben sind) häufig dazu, eine ansonsten lange Folge von Nullen zu unter­ brechen. Nunmehr wird angenommen, daß der Wert bei dem markierten "ver­ streuten" 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 Be­ zeichnung "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ön­ nen allerdings andere Werte als 0,5 für die "Z-"-Quantisierung akzep­ tierbar sein. Ein höherer Wert wie beispielsweise 0,75 könnte möglicher­ weise hohe Bitratenkompressionen beeinträchtigen, bei welchen die Genau­ igkeit wesentlich ist. Ein Wert von weniger als 0,625 könnte möglicher­ weise 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 Hard­ ware oder Software implementieren. Hierzu wird beispielsweise der Aus­ gangswert 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^-1 bis 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 erfor­ dert 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 anwen­ den.

Ergebnisse

Die diskrete Kosinus-Transformation führt zum Auftreten unterschied­ licher Fehlergrade an unterschiedlichen Stellen in dem 8×8-Bildpunkt­ block. Zu Vergleichszwecken werden die Daten in den Ecken-Bildpunkten "A" und den Zentrumsbildpunkten "B" betrachtet. Fig. 4 zeigt eine Dar­ stellung 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ächli­ che Gewinn kommt, wie in Fig. 6 gezeigt ist.

Eine sehr einfache Änderung der Quantisierungsschaltkreise in einem JPEG-Bildkompressionssystem kann signifikante Verbesserungen des Kom­ pressionsverhä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 Wirkungs­ grades als auch der einfachen Implementierung.

Die voranstehenden Beschreibungen bestimmter Ausführungsformen der vor­ liegenden Erfindung wurden zum Zwecke der Erläuterung und der Beschrei­ bung präsentiert. Die Ausführungsformen wur­ den zu dem Zwecke ausgesucht und beschrieben, um die Grundlagen der Er­ findung und deren praktische Umsetzung am besten zu erläutern, um es hierdurch anderen Fachleuten zu ermöglichen, die Erfindung und unter­ schiedliche Ausführungsformen mit verschiedenen Modifikationen am besten einzusetzen, wie es für den betreffenden Verwendungszweck gerade erfor­ derlich ist.

Claims (1)

1. Quantisierungsverfahren zur Verwendung bei der Bildkompression, wonach Ein­ gangsbildpunktdaten von N × N-Bildpunktblöcken empfangen werden, die Daten der Bildpunktblöcke in ein Frequenzbereichsformat transformiert werden, was zu mehreren Frequenztransformationskoeffizienten einschließlich eines Gleichspan­ nungskoeffizienten und mehrerer Wechselspannungskoeffizienten führt, dadurch gekennzeichnet, daß

   • a) die Frequenzkomponenten quantisiert werden, um eine ganze Zahl mit mehreren Bits zu bilden, einschließlich einem höchstwertigen Bit und ein­ schließlich zumindest dreier Kommastellenbits, wobei
   • a1) ein Parameter x auf Null (x = 0) gesetzt wird, wenn der Parameter x in einen Bereich -0,625 < x < +0,625 fällt,
   • a2) der Parameter x auf 1 (x = 1) gesetzt wird, wenn der Parameter x in einen Bereich 0,625 < x < +1,625 fällt,
   • a3) der Parameter x auf 2 (x = 2) gesetzt wird, wenn der Parameter x in einen Bereich 1,625 < x < +2,625 fälltwobei der Parameter x gegeben ist alsx = C/Q,mit
   • C = Koeffizientenwert vor der Quantisierung und
     Q = Quantisierungsfaktor,
   • b) das erste Kommastellenbit und das zweite oder dritte Kommastellenbit ge­ prüft werden,
   • c) das höchstwertige Bit geprüft wird, und
   • 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öchst­ wertige Bit eine Null ist.