DE69609503T2

DE69609503T2 - Verfahren und vorrichtung zur kompression von farbvideodaten

Info

Publication number: DE69609503T2
Application number: DE69609503T
Authority: DE
Inventors: G. Freeman
Original assignee: Novalogic Inc
Current assignee: Novalogic Inc
Priority date: 1995-05-08
Filing date: 1996-05-07
Publication date: 2000-12-14
Anticipated expiration: 2016-05-08
Also published as: DE69609503D1; US5625759A; WO1996037071A2; WO1996037071A3; EP0824830A2; AU5732796A; EP0824830B1

Description

HINTERGRUND DER ERFINDUNG

Diese Erfindung betrifft das Komprimieren von Farbvideodaten im Allgemeinen sowie insbesondere das Verändern des Komprimierungsgrades als eine Funktion der Farbeigenschaften der Videodaten, welche gerade komprimiert werden.
Farbvideoanimationen oder Videobänder von Bildern oder Szenen können verwendet werden, um die Wirklichkeitsnähe und/oder Nützlichkeit von computergenerierten Anzeigen und Grafiken zu verbessern. Diese Videobilder werden typischerweise als ein Strom von digitalen Farbvideodaten auf einer Speichervorrichtung, wie z. B. einer CD-ROM-Scheibe, in einem abrufbaren Format gespeichert. Wenn vom Betrachter gewünscht, oder wenn von dem Softwareprogramm gesteuert, werden die Farbvideodaten, welche das Videobild repräsentieren, von der Speichervorrichtung abgerufen und auf einer Anzeigevorrichtung, wie z. B. einen Videomonitor, angezeigt. In der Praxis werden die Videodaten nicht kontinuierlich angezeigt, sondern sind in eine Folge von Einzelbildern unterteilt. Jedes Einzelbild von Videodaten umfasst die nötige Information, um einen einzelnen Bildschirm oder "Schnappschuß" des Videos auf der Anzeigevorrichtung anzuzeigen. Das Anzeigen einer sequentiellen Reihe von Einzelbildern in schneller Aufeinanderfolge kann den Eindruck von sich bewegenden Bildern erzeugen.
Die Qualität und Wirklichkeitsnähe des angezeigten Bildes ist eine Funktion der Auflösung der Anzeigevorrichtung und der Anzahl von Farben, welche die Anzeigevorrichtung anzeigen kann. Typischerweise kann eine vernünftige Bildauflösung mit einer Anzeigevorrichtung erreicht werden, welche ein Bild anzeigt, wobei das Bild aus 480 horizontalen Linien von 640 Pixeln, oder Bildelementen, pro Zeile besteht, obwohl Bilder, welche für einige Videospiele geeignet sind, an Vorrichtungen mit Auflösungen von lediglich 240 horizontalen Linien von 320 Pixeln angezeigt werden können. In jüngerer Vergangenheit wurden Anzeigevorrichtungen mit höherer Auflösung, welche in der Lage sind, 1024 Linien von 1280 Pixeln pro Linie anzuzeigen, allgemein erhältlich. Wo lediglich ein einfaches, Zweiton-Monochrom-Bild gewünscht ist, kann jedes Pixel durch ein einzelnes Bit von Videodaten repräsentiert werden, da das Pixel abhängig von dem Bild entweder erleuchtet oder dunkel ist. Typischerweise werden Monochrom-Bilder jedoch unter Verwendung von acht Datenbits zur Repräsentation jedes Pixels angezeigt, was jedem Pixel des Bildes gestattet, in einem von 256 möglichen Farbtönen einer einzigen Farbe angezeigt zu werden. In Farbe angezeigte Bilder sind weitaus aufregender und visuell ansprechender als monochrome Bilder, besonders wenn sie verwendet werden, um die Wirklichkeitsnähe von Videospielen und Simulationen zu verbessern. Es wird jedoch wesentlich mehr Information in der Form von digitalen Videofarbdaten benötigt, um Farbbilder wiederzugeben. Im einfachsten Fall müssen wenigstens dreimal so viele digitale Daten verwendet werden, um eine Farbe zu definieren, welche durch ein einzelnes Pixel angezeigt werden soll, da jede Farbe aus einer Kombination der Primärfarben Rot, Blau und Grün besteht, und jede dieser Farben durch digitale Daten definiert werden muß. Aktuelle Anzeigevorrichtungen, welche das RGB(Rot-Blau- Grün)-Format benutzen, sind in der Lage, 16.777.216 Farben bereitzustellen, indem sie 24 Farbvideodatenbits verwenden, um jedes Pixel zu definieren.
Wo relativ statische Bilder angezeigt werden sollen, ist die Menge an benötigten Farbvideodaten kein kritischer Faktor in der Leistung des Softwareprogramms. Wo jedoch eine Videoanimation oder ein sich bewegendes Bild gewünscht ist, wird das Video ruckartig, unnatürlich und unrealistisch erscheinen, wenn die Videodaten nicht mit einer Rate von wenigstens 30 Einzelbildern pro Sekunde, dem NTSC-Fernsehstandard, angezeigt werden.
Ein einzelner Videoclip, welcher 1 Minute dauert, muß somit aus wenigstens 1800 Einzelbildern von Videofarbdaten zusammengesetzt sein. Diese enorme Menge an Videofarbdaten muß gespeichert werden auf, und abgerufen werden von einer CD-ROM oder einer anderen Vorrichtung mit genug Speicherraum, um alle Videofarbdaten für den Videoclip zu fassen.
Ein weiteres Problem besteht darin, dass Speichervorrichtungen, wie z. B. CD- ROMs, begrenzte Datenübertragungsraten, typischerweise von maximal etwa 600000 Bits pro Sekunde aufweisen. Wo die Daten nicht schnell genug abgerufen und angezeigt werden können, kann die Bildung des Videobildes für einen Augenblick steckenbleiben, während die Farbvideodaten von der Speichervorrichtung zur Anzeigevorrichtung übertragen werden und beeinträchtigt die Wirklichkeitsnähe der angezeigten Videobilder. Um die effektive Geschwindigkeit derartiger Speichervorrichtungen zu erhöhen und die Wartezeit zum Erzeugen einer sich bewegenden Farbvideoanzeige zu verringern, wurden zahlreiche Komprimierungs- und Dekomprimierungsmethoden vorgeschlagen, um die Menge an Farbvideodaten zu reduzieren, welche gespeichert und abgerufen werden muß. Einige Komprimierungsmethoden unterteilen ein Bild oder eine Abbildung in eine Matrix von Blöcken, von denen jede wiederum in eine Matrix von Bildelementen oder Pixeln unterteilt wird. Das Bild oder die Abbildung kann in digitale Daten umgewandelt werden, welche dann verwendet werden können, um eine Videoanzeige des Originalbildes zu erzeugen, wobei bestimmte Informationen für jedes Pixel eines jeden Blocks kodiert werden müssen. Die Menge an pro Pixel benötigten Daten und die Qualität in Einzelheiten des Bildes, welches aus den Daten erzeugt werden kann, sind wichtige Eigenschaften eines jeden Komprimierungssystems. In einigen Fällen werden die Daten in einer einheitlichen Weise Block für Block oder Einzelbild für Einzelbild komprimiert. Auf diese Art und Weise werden m Bits von komprimierten Daten verwendet, um jeden n · n- Block von Pixeldaten zu repräsentieren. Andere Systeme verwenden ein adaptives Komprimierungsverfahren, wobei Farbvideodaten Block für Block untersucht werden und wobei dann die Art der zu verwendenden Komprimierung für jeden Block bestimmt wird. In einem bekannten System werden zwei unterschiedliche Farben für jeden Block durch Ermitteln des Durchschnitts der Farben bestimmt, welche oberhalb und unterhalb der durchschnittlichen Bildleuchtdichte für den Block liegen. Diese zwei berechneten Farben können dann mit einem Schwellenwert verglichen werden, um die Anzahl von Farben zu bestimmen, die für den Block gespeichert werden sollen.
Was in der Technik benötigt wird, ist ein Farbvideodatenkomprimierungsverfahren, so dass das wieder erzeugte Videobild die Farben des Originalvideobildes genau wiedergibt, während die Menge an notwendigen Daten reduziert wird, um sich bewegende Farbbilder in Echtzeit von Speichervorrichtungen mit einer festen Datenrate zu erzeugen. Durch Verringern der Menge an für ein Videoeinzelbild notwendigen Farbdaten kann auf die Farbdaten zum Herstellen des Bildes von der Speichervorrichtung zugegriffen werden, ohne hinter der Videoanzeige zurückzubleiben. Ein Verfahren und eine Vorrichtung zur verlustfreien Komprimierung und Dekomprimierung von Videobilddaten ist im US-Patent Nr. 5,408,542 offenbart. Jedes Videoeinzelbild wird in Pixelblöcken verarbeitet. Jede angetroffene Farbkombination wird in einem Farbcache gespeichert, welches nachfolgend als ein Farbkombinationsverzeichnis verwendet wird. Auf diese Art und Weise kann eine identische Farbkombination in einem späteren Pixelblock auf den Eintrag im Farbcache verweisen anstatt alle Farben in dem Pixelblock in den Datenstrom hineinzukodieren.
Ein adaptives Komprimierungs-/Dekomprimierungsverfahren ist im US-Patent Nr. 5,046,119 offenbart, in welchem vom Benutzer einstellbare Schwellen verwendet werden können, um die verwendeten Komprimierungsarten zu verändern.

Abriß der Erfindung

Die vorliegende Erfindung ist auf ein Verfahren und eine Vorrichtung zum Komprimieren von Farbvideodaten zur Speicherung unter Verwendung der Farben des Originalvideobildes gerichtet.
Gemäß einem ersten Gesichtspunkt der vorliegenden Erfindung ist ein Verfahren vorgesehen zum Komprimieren von Farbvideodaten, welche Farbvideoeinzelbilder an einer Anzeigevorrichtung definieren, wobei das Verfahren folgende Schritte umfasst:
Vorsehen eines eine Mehrzahl von Pixeln umfassenden Farbvideoeinzelbildes, wobei jedes Pixel eine zugeordnete Farbe aufweist;
Unterteilen des Farbvideoeinzelbildes in Pixelblöcke; sowie Bestimmen der Farben, welche in einem der Blöcke vorhanden sind,
dadurch gekennzeichnet, dass das Verfahren weiterhin folgende Schritte umfasst:
Berechnen einer Anzahl von Farben für den einen der Blöcke entsprechend einer Farbschwelle, wobei die Anzahl der Farben nicht grösser ist als eine vorbestimmte Anzahl; sowie
Speichern von Farbvideodaten, welche jedes Pixel in dem Block repräsentieren, wobei der Schritt des Berechnens der Anzahl von Farben für den einen der Blöcke umfasst:
Sortieren der bestimmten Farben, welche in dem Block vorhanden sind, nach der Häufigkeit des Auftretens einer jeden Farbe,
Vergleichen einer jeden der bestimmten Farben mit jeder anderen bestimmten Farbe,
Bestimmen von Farben als die gleichen oder vergleichsweise nahe Farben aus dem Vergleich der bestimmten Farben, wenn der Unterschied zwischen den Farben geringer ist als die Farbschwelle, sowie Ersetzen der weniger häufig auftretenden Farbe durch die häufiger auftretende Farbe von zwei vergleichsweise nahen Farben.
Wenn die berechnete Anzahl an Farben größer als vier ist, dann kann die Farbschwelle vorzugsweise eingestellt werden und die Anzahl an Farben, welche für den Block nötig sind, kann erneut dementsprechend berechnet werden.
Der Schritt des Bestimmens der im Block vorhandenen Farben kann weiterhin den Schritt des Pixel-für-Pixel-Vergleichens der Farben, welche in dem Block vorhanden sind, mit den Farben in einem entsprechenden Block in einem vorhergehenden Farbvideoeinzelbild umfassen, wobei der Farbe eines Pixels ein Null-Wert gegeben wird, wenn der Unterschied zwischen der Farbe des jeweiligen Pixels, welches in dem Block vorhanden ist, und der Farbe des entsprechenden Pixels in dem entsprechenden Block in dem vorhergehenden Farbvideoeinzelbild geringer ist als ein Transparenzschwellenwert.
Beim Lesen von Daten von Speichervorrichtungen mit einer festen Datenrate können vollbewegte Videobilder ruckartig und unnatürlich erscheinen, wo das Einzelbild mehr Videodaten enthält als bei der festen Datenrate in der gegebenen Zeit, welche für das Anzeigen des Einzelbildes zugewiesen ist, gelesen werden können. Um ein ruckfreies Abspielen der sich bewegenden Videobilder zu erreichen, sollte die Menge an Daten verringert werden, welche von der Speichervorrichtung, wie z. B. einer CD-ROM, gelesen werden, um dem Prozessor zu gestatten, eine ausreichende Menge der Farbvideodaten zu erfassen, um ein vollbewegtes Video in Echtzeit wiederzugeben.
Zusätzlich gibt es, selbst in Speichervorrichtungen mit hoher Dichte, noch eine praktische Grenze für die Menge an Daten, welche gespeichert werden kann. Eine Komprimierung von Farbvideodaten kann gestatten, dass eine erhöhte Anzahl an Videoeinzelbildern gespeichert wird, wodurch die Spielzeit der Vorrichtung erhöht wird.
Gemäß einem zweiten Gesichtspunkt der vorliegenden Erfindung ist weiterhin eine Vorrichtung vorgesehen zum Komprimieren von Farbvideodaten, welche Farbvideoeinzelbilder an einer Anzeigevorrichtung definieren, wobei jedes der Einzelbilder eine Mehrzahl von Pixeln umfasst, wobei jedes Pixel eine zugeordnete Farbe aufweist, und wobei die Vorrichtung umfasst:
einen Speicher;
sowie einen Prozessor zum Unterteilen jedes Farbvideoeinzelbildes in Pixelblöcken und zum Bestimmen der in jedem Block vorhandenen Farben, dadurch gekennzeichnet, dass der Prozessor weiterhin ausgebildet ist zum Berechnen eines Farbwertes für jedes Pixel in dem Block, zum Zählen des Auftretens eines jeden Farbwertes in dem Block sowie zum vorübergehenden Speichern einer Tabelle umfassend jeden Farbwert in dem Block sowie die Anzahl des Auftretens für jeden Farbwert in dem Speicher;
wobei der Prozessor weiterhin jeden Farbwert in der Tabelle, welche in dem Speicher gespeichert ist, mit jedem anderen Farbwert in der Tabelle vergleicht, welche in dem Speicher gespeichert ist, wobei dann, wenn der Unterschied zwischen zwei Farbwerten geringer ist als ein Farbschwellenwert, die Anzahl des Auftretens für den weniger häufig auftretenden Farbwert zu der Anzahl von häufiger auftretenden Farbwerten addiert wird und der weniger häufig auftretende Farbwert aus dem Speicher gelöscht wird, so dass der häufiger auftretende Farbwert den weniger häufig auftretenden Farbwert in dem Block ersetzt; sowie
Mittel zum Speichern der verbleibenden Farbwerte in dem Block aus dem Speicher.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Diagramm, welches ein Datenstromformat darstellt, das für die komprimierten Daten für zwei Farben gemäß einer Ausführungsform der Erfindung verwendet wird.
Fig. 2 ist eine Liste der Zwei-Bit-Wörter des TYP-Bytes, welche verwendet werden, um den Typ der Komprimierung oder Kodierung gemäß einer Aus führungsform der Erfindung anzuzeigen.
Fig. 3a-3c sind Flussdiagramme, welche das Komprimierungsverfahren gemäß einer Ausführungsform der Erfindung beschreiben und umreissen.
Fig. 4 stellt eine Farbreihe und einen entsprechenden Block von Farbpixeln dar, welche gemäß einer Ausführungsform der Erfindung kodiert werden.
Fig. 5 stellt eine weitere Farbreihe und einen entsprechenden Block von Pixeldaten dar, welche gemäß einer Ausführungsform der Erfindung kodiert werden.
Fig. 6 stellt noch eine weitere Farbreihe und einen entsprechenden Block von Pixeldaten dar, welche gemäß einer Ausführungsform der Erfindung kodiert werden.
Fig. 7 ist ein Diagramm, welches das Verfahren darstellt, das verwendet wird, um die Nähe von Farben im RGB-Raum zu bestimmen.
Fig. 8 stellt ein Computersystem zum Kodieren und Dekodieren von Farbvideodaten gemäß einer Ausführungsform der Erfindung dar.

DETAILLIERTE BESCHREIBUNG EINER BEVORZUGTEN AUSFÜHRUNGSFORM

Die Erfindung betrifft ein Verfahren zum Komprimieren von Farbvideodaten, welche Einzelbilder von Farbvideobildern repräsentieren, um die Menge an Daten, welche für jedes Einzelbild gespeichert werden, zu reduzieren und die Geschwindigkeit zu erhöhen, mit welcher derartige Videobilder abgerufen und angezeigt werden können. Wie hierin beschrieben wird, wird auf zahlreiche spezielle Details Bezug genommen werden, wie z. B. die spezielle Anzahl an Bits in einem Datenstrom, die Anzahl an Pixeln in einem Block, usw., um Ausführungsformen der Erfindung vollständiger zu beschreiben. Jedoch sollte einem Fachmann klar sein, dass die vorliegende Erfindung nicht auf die speziellen Details begrenzt ist.
In der vorliegenden Ausführungsform ist ein Videodatenstrom in eine Sequenz von Videoeinzelbildern unterteilt, wobei jedes Einzelbild Videodaten zum Anzeigen einer Mehrzahl von Pixeln umfasst, wobei jedes Pixel eine zugeordnete Farbe aufweist, um einen einzelnen Anzeigebildschirm oder "Schnappschuß" eines Farbvideos anzuzeigen, welches während des Betriebs eines Computerprogramms angezeigt werden soll. Jedes Einzelbild wird abgetastet und dann in eine Matrix von Pixelblöcken unterteilt. Jeder Block enthält eine Pixelmatrix, wobei ein 4 · 4-Pixelblock 16 Pixel enthält. Jedes Pixel kann adressiert werden, um eine unterschiedliche Farbe zu repräsentieren. Somit kann jedem Pixel in dem Block eine spezielle Farbe zugewiesen werden. Die Farbdaten in den Pixelblöcken werden dann in einen Datenstrom gespeichert und komprimiert. Von diesem Punkt an werden sich die Ausdrücke "komprimieren" und "kodieren" auf das Verfahren beziehen, durch welches die Farbvideodaten in dem Datenstrom gespeichert werden.
Fig. 1 stellt einen Datenstrom von Farbvideodaten dar, welche gemäß der vorliegenden Ausführungsform komprimiert sind. In diesem Beispiel umfasst der Datenstrom Daten für zwei Farben. Das erste Byte des Datenstroms wird als TYP-Byte bezeichnet. Dieses Byte besitzt acht Bit, welche in vier Zwei-Bit- Worte unterteilt sind. Durch Unterteilen des ersten bzw. führenden Bytes auf diese Art und Weise, wird der Prozessor über das Farbschema informiert, welches für die nächsten vier Pixelblöcke verwendet wird und kann die Daten dementsprechend handhaben. Jeder Block ist vorzugsweise ein 4 · 4-Pixelblock für insgesamt 16 Pixel in einem Block.
Dem TYP-Byte folgend sind die FARB-Bytes, welche verwendet werden, um die Farben der Pixel innerhalb des Pixelblocks zu identifizieren. Jedes FARB- Byte weist acht Bit auf. Das FARB-Byte kann deshalb bis zu 2&sup8; oder 256 Farben an einem im Speicher gespeicherten Farbkennfeld adressieren. Das Kodieren und Dekodieren von Farbvideodaten wird entsprechend diesem Farbkennfeldspeicher durchgeführt werden. Während des Dekodierens identifizieren die Speicheradressen die gewünschten Farben für die verschiedenen Pixel und die die Farben bestimmenden Daten werden mit den entsprechenden Speicherstellen ausgelesen. Jede Farbe umfasst die R-, G- und B-Komponentenwerte für eine Videoanzeige. In einer 24-Bit-Anzeige wird ein RGB- Tripel mit drei Farbkennfeldern entsprechend den R-, G- bzw. B-Komponentenwerten verwendet. Insbesondere werden acht Bit die Farbe Rot (R) repräsentieren, acht Bit werden die Farbe Grün (G) repräsentieren und acht Bit werden die Farbe Blau (B) repräsentieren. Somit wird das RGB-Tripel das Äquivalent eines 768-Bit-Kennfelds sein (d. h., 3 · 256). Jede Farbe des 256- Farb-Kennfelds kann auf das RGB-Tripel indiziert sein und jeder zu speichernde Farbwert weist einen R-, G- und B-Komponentenwert auf. Auf diese Art und Weise kann jedes FARB-Byte sein eigenes Farbkennfeld adressieren. Der Unterschied zwischen Farbwerten wird nach Massgabe dieser RGB-Komponentenwerte bestimmt werden, wie detaillierter in Verbindung mit Fig. 7 diskutiert werden wird.
In dem in Fig. 1 gezeigten Datenstrom sind lediglich zwei FARB-Bytes für das 2-Farben-Datenschema (TYP 10) gezeigt. Den FARB-Bytes folgend sind zwei POINTER-Bytes, wobei jedes Byte in zwei Vier-Bit-Worte unterteilt ist. Diese Summe von vier Vier-Bit-Worten adressiert die Farben für den Pixelblock. Das erste Wort (d. h., Wort 1) enthält den Pointer (Zeiger) auf die Farbe für die erste Reihe (d. h., Reihe 1) des 4 · 4-Pixelblocks, wobei jedes Bit auf entweder die Farbe 1 oder Farbe 2 für die einzelnen Pixel in dieser Reihe zeigt. Wort 2, Wort 3 bzw. Wort 4 enthalten jeweils die Pointer für Reihe 2 bis Reihe 4. Wo vier Farben für den Block benötigt werden (d. h., TYP 11) werden vier Bytes für die Pixelpointer benötigt, da jedes Pixel einen Zwei-Bit-Pointer benötigen wird.
Das TYP-Byte in dem Datenstrom umfasst vier Zwei-Bit-Wörter, welche die Struktur und die Anzahl der Farben für die kodierten Blöcke in diesem Datenstrom anzeigen. Vier Pixelblöcke sind in dem Datenstrom kodiert, welcher durch das TYP-Byte identifiziert wird. Jedes Zwei-Bit-Wort lässt die für einen Pixelblock zu verwendende Datenstruktur erkennen. Nach dem letzten in Fig. 1 gezeigten POINTER-Byte kann entsprechend dem zweiten Wort des TYP-Bytes ein weiterer Satz von FARB-Bytes und POINTER-Bytes erwartet werden, usw..
Wie in Fig. 2 gezeigt, gibt es für die vorliegende Erfindung vorzugsweise vier verschiedene Typen von Farbkodierschemata. Diese Kodierschemata werden durch die Zwei-Bit-Wörter identifiziert. TYP-00-Kodierung zeigt an, dass in dem Datenstrom keine Farbdaten folgen, so dass die Blöcke in Bezug auf das vorhergehende Einzelbild transparent erscheinen werden und die Farben die gleichen bleiben werden. In der TYP-01-Kodierung umfasst der Datenstrom Informationen für eine Farbe. In der TYP-10-Kodierung werden Daten für zwei Farben vorhanden sein und für TYP-11-Kodierung werden Daten für vier Farben gefunden werden.
Wo für den Block lediglich drei Farben benötigt werden, kann TYP-11-Kodierung (d. h. das Vier-Farb-Schema) verwendet werden, wobei das vierte FARB- Byte nicht verwendet wird. Das vierte FARB-Byte kann leer sein oder bloß überflüssige Farbdaten enthalten, welche durch die POINTER-Bytes nicht referenziert werden. Alternativ können die drei Farben für den Block in ein Zwei-Farb-Schema durch Eliminieren der dritten Farbe gezwungen werden. Gelegentlich kann praktisch keine Komprimierung für den Block durchgeführt werden und volle 16 FARB-Bytes werden (d. h., eine Farbe für jedes Pixel) dem TYP-Byte folgend benötigt werden. In dieser Situation wird ein TYP-01- Byte verwendet, wobei das FARB-Byte einen willkürlichen Wert, wie z. B. Null, aufweist. Diese Anordnung zeigt an, dass 16 FARB-Bytes in dem Datenstrom für den 4 · 4-Pixelblock (für insgesamt 17 Bytes) verwendet werden.
In den meisten Fällen jedoch, kann die in einem Block vorhandene Anzahl an Farben auf vier oder weniger reduziert werden, ohne das Bild wesentlich zu verschlechtern.
Ein Vorteil dieser Anordnungen des Speicherns von Farbdaten ist, dass dann wenn das Wort in einem TYP-Byte für einen speziellen Block 00 ist, was anzeigt, dass kein Wechsel in einer Farbe vom vorhergehenden Einzelbild aufgetreten ist, keine zusätzlichen Daten für diesen Pixelblock notwendig sind, wodurch wenigstens vier Bytes eingespart werden. Kein FARB-Byte wird in einem TYP-00-Datenstrom verwendet. Dann wenn lediglich eine Farbe für den Block nötig ist, ist lediglich das einzelne FARB-Byte notwendig (d. h., TYP 01), was drei Bytes einspart. Wo zwei Farben für den Block benötigt werden, wie in dem TYP-10-Datenstrom der Fig. 1 gezeigt ist, werden zwei Bytes eingespart. Wo fünf oder mehr Farben in dem Block vorhanden sind, werden höchstens lediglich vier dieser Farben in dem entsprechenden TYP- 11-Datenstrom vorhanden sein. Farbkomprimierung wird erreicht durch Reduzieren der Anzahl der Farben, welche für einen Block erhalten werden. Wenn beispielsweise zwei Farben einander ausreichend ähnlich sind, dann werden diese zwei Farben als die gleiche Farbe betrachtet. Lediglich eine dieser zwei Farben wird in einem TYP-01-Datenstrom anstelle eines TYP-10- Datenstroms verwendet werden. Die genaue Struktur des Datenstroms, der gespeichert wird, ist abhängig von der Anzahl an Farben, die gespeichert werden und der Größe der Pixeldatenblöcke.
Fig. 3a-3c zeigen Blockdiagramme der Schritte, die verwendet werden, um den für die Blöcke eines Videobildes zu verwendenden Kodierungstyp zu bestimmen. Die Farben des Videoeinzelbildes entsprechen jenen, die in dem 256-Farbspeicherkennfeld vorhanden sind. Wo das zu kodierende Videoeinzelbild jedoch Farben enthält, weiche in dem Farbvideokennfeld nicht identisch vorhanden sind, kann dann die näheste erhältliche Näherung der Farbe in dem Videoeinzelbild verwendet werden. Jedes neue Einzelbild in einer Aufeinanderfolge von Einzelbildern wird abgetastet und in einen 4 · 4-Pixelblock unterteilt. Die Farben eines jeden Pixel in jedem 4 · 4-Block des Videoeinzelbildes werden analysiert und dann in einen Datenstrom gemäß dem in Fig. 2 gezeigten Kodierschema kodiert. Die Analyse und das Kodieren des Farbvideos, wie in den Fig. 3a-3c gezeigt, wird im allgemeinen in drei Stufen voranschreiten, wobei die Farbwerte zuerst berechnet werden, dann entsprechend ihrer Häufigkeit des Auftretens sortiert werden, und dann miteinander verglichen werden, um die minimale Anzahl an Farben zu bestimmen, welche für das Kodieren des Blocks notwendig sind.
In der ersten Stufe, wie in Fig. 3a gezeigt, werden Farbwerte für jedes Pixel des Blocks im aktuellen Einzelbild bestimmt. Dieser Farbwert kann aus den RGB-Signalen für jedes einzelne Pixel bestimmt werden. Nachdem der Farbwert für jedes Pixel in dem Block bestimmt ist, wird jedes Pixel des Blocks im aktuellen Einzelbild mit seinem entsprechenden Pixel im vorhergehenden Videoeinzelbild verglichen. Wenn die Farben der entsprechenden Pixel die gleichen sind, oder wenn der Unterschied in deren Farbwerten geringer ist als ein Transparenzschwellenwert, wird der Farbwert dieses Pixels auf Null gesetzt. Dieses besondere Pixel sollte "transparent" in Bezug auf die Pixelfarbe des vorhergehenden Einzelbildes sein. Dieser "Transparenz"-Farbwert wird als Farbe erachtet und wird als solche in dem Kodierprozeß gezählt, welcher später ausführlicher diskutiert wird. Dann wenn alle Pixel in dem Block "transparent" sind, wird dieser Block Gegenstand des TYP-00-Kodierens. Somit annulliert die Verwendung eines "Transparenz"-Farbwertes den Bedarf an FARB-Bytes in dem Datenstrom, in dem alle Pixel des Blocks gegenüber dem vorhergehenden Einzelbild unverändert sind.
Der Transparenzschwellenwert zum Bestimmen der Ähnlichkeit in den Farben von entsprechenden Pixeln kann entweder ein fest eingestellter Wert oder ein durch den Benutzer gewählter sein. Der Farbwert des Pixels des aktuellen Einzelbildes wird als "ausreichend unterschiedlich" vom Farbwert eines entsprechenden Pixels des vorhergehenden Einzelbildes erachtet, wo der Unterschied zwischen den Farbwerten der entsprechenden Pixel grösser ist als die Transparenzschwelle. Der "ausreichend unterschiedliche" Farbwert des aktuellen Pixels wird dann im Pufferspeicher gespeichert und das nächste Pixel wird dann analysiert. Jedes Pixel in dem Block wird auf diese Art und Weise analysiert und ein laufender Zähler oder eine Reihe wird für die Farbwerte (Cx) und deren entsprechender Häufigkeit des Auftretens (N) innerhalb des Pixelblocks erhalten.
Die zweite Stufe der Analyse, wie in Fig. 3b dargestellt, beginnt nachdem jedes der 16 Pixel in einem 4 · 4-Pixelblock mit seinem entsprechenden Pixel in dem vorhergehenden Einzelbild verglichen worden ist. Die Reihe von Farbwerten wird in absteigender Reihenfolge der Anzahl oder Häufigkeit des Auftretens für jede Farbe sortiert. Der Farbwert für jede Farbe wird in Bezug auf die Häufigkeit des Auftretens für diese Farbe in dem Block gespeichert. Diese Werte können durch beliebige im Stand der Technik bekannte Mittel, wie z. B. eine Tabelle, im Speicher abgespeichert werden.
In der dritten Stufe dieser Analyse, dargestellt in Fig. 3b und 3c, wird die Anzahl (D) der augenblicklich in dem Pixelblock vorhandenen Farben auf eine Minimalanzahl (Dmin) an Farben reduziert, welche für jeden Block von Pixeln notwendig sind, indem jeder Farbwert mit jedem anderen Farbwert in der Reihe verglichen wird. Die minimale Anzahl an Farben kann durch den Benutzer auf 1, 2, 3 oder 4 eingestellt werden; oder kann durch einen vorprogrammierten Prozessor adaptiv bestimmt werden. Vorzugsweise wird jeder Farbwert (Cm) sequentiell mit den anderen Farbwerten (Cn) verglichen, beginnend mit dem am häufigsten auftretenden Farbwert. Dieser in Fig. 3c gezeigte iterative Prozeß bestimmt die minimale Anzahl an Farben für jeden Pixelblock. Farben werden als gleich oder vergleichsweise nahe erachtet, wo der Unterschied in dem Farbwert zwischen zwei Pixeln geringer als ein Farbschwellenwert (CT) ist. Dieser Farbschwellenwert kann festgelegt oder ansonsten durch den Benutzer eingestellt sein, oder kann durch das System adaptiv bestimmt sein. Das Komprimierungsschema wird zu größerem Kontrast führen, wo der Farbschwellenwert auf ein höheres Niveau eingestellt ist. Eine größere Komprimierung kann auf Kosten eines höheren Kontrastes erreicht werden. Wenn bestimmt wird, dass die weniger häufig auftretende Farbe ausreichend nahe an der häufiger auftretenden Farbe ist, wie durch den Farbschwellenwert bestimmt wird, wird die Zählung oder Anzahl an Auftreten für die weniger häufig auftretende Farbe zu der Zählung der häufiger auftretenden Farbe addiert. Auf diese Art und Weise erhalten die Pixel mit dem weniger häufig auftretenden Farbwert nun den häufiger auftretenden Farbwert. Die weniger häufig auftretende Farbe wird dann aus der Reihe gelöscht oder entfernt. Diese Konsolidierung von vergleichsweise nahen Farben reduziert die benötigte Datenmenge wesentlich, welche für jeden Block zu speichern ist. Wenn die zwei verglichenen Farben einen Unterschied im Farbwert größer als die Farbschwelle aufweisen, wird die Zählung des Auftretens für jede Farbe beibehalten. Vorzugsweise werden "transparente" Farben niemals mit einer häufiger auftretenden Farbe konsolidiert. Beispielsweise können die Schwellen und Parameter des Systems derart eingestellt sein, dass "transparente" Farben stets als ausreichend unterschiedlich von den anderen Farben erachtet werden.
Dann wenn jede Farbe in der Reihe mit jeder anderen auftretenden Farbe in der Reihe verglichen worden ist, wird der Kodierungs- oder Datenspeicherungstyp bestimmt, welcher die effektive Komprimierung der Farbdaten repräsentiert. Dann wenn alle Farben einen "Transparenz"-Wert von Null aufweisen, hat keine beträchtliche oder merkliche Veränderung vom vorhergehenden Einzelbild stattgefunden und die TYP-00-Komprimierung wird verwendet. Wenn lediglich eine Farbe in der Reihe vorhanden bleibt, dann wird die TYP-01-Komprimierung verwendet, welche lediglich ein FARB-Byte benötigt. Wenn zwei Farben in der Reihe vorhanden bleiben, dann wird die TYP-10-Komprimierung verwendet, welche zwei FARB-Bytes erfordert. Wenn drei oder vier Farben vorhanden sind, wird die TYP-11-Komprimierung verwendet, welche vier FARB-Bytes in dem Datenstrom erfordert. Wo lediglich drei Farben vorhanden sind, wird auf eines der FARB-Bytes durch den Pixelpointer nicht Bezug genommen werden. Dieses nicht verwendete Byte kann auf einen Null-Wert gesetzt werden.
Wie zuvor diskutiert, können, wo drei Farben in einem Block verbleiben, anstatt einem Byte zu gestatten, ungenutzt vorhanden zu sein, die drei Farben des Blocks durch Eliminieren der dritten Farbe in ein Zwei-Farben- Schema gezwungen werden. Dies würde durchgeführt werden durch Einstellen des Farbschwellenwerts und daraufhin Vergleichen der Anfangsfarben des Blocks unter Verwendung des eingestellten Schwellenwerts, um die neue Minimalanzahl von Farben auf zwei zu zwingen. Selbstverständlich kann der Farbschwellenwert auch eingestellt werden, um das ungenutzte FARB-Byte auszufüllen, indem der Prozeß gezwungen wird, die minimale Farbanzahl von vier anstatt von drei zu wählen. In beiden Fällen werden die Minimalfarben aus dem Satz von aktuellen Farbwerten ausgewählt, welche ursprünglich für jedes Pixel in dem Block bestimmt wurden.
Dann wenn mehr als vier Farben in der Reihe vorhanden bleiben, wird der Farbschwellenwert adaptiv durch das System nach Massgabe der Anzahl der verbleibenden Farben eingestellt, um sicherzustellen, dass nicht mehr als vier Farben übrig bleiben. Die dritte Stufe des Bestimmens der minimalen Farbanzahl wird dann unter Verwendung des neu eingestellten Farbschwellenwertes erneut durchlaufen, um die Anzahl an in der Reihe verbleibender Farben weiter zu konsolidieren. In diesem Prozeß werden keine neuen Farbwerte berechnet. Nur die aktuellen Farbwerte, welche ursprünglich für jedes Pixel in dem 4 · 4-Block bestimmt wurden, werden kodiert und gespeichert. Die Farbwerte für bestimmte Pixel werden durch einen vergleichsweise nahen, aber häufiger auftretenden Farbwert ersetzt. Es geschieht durch dieses Ersetzen von Farbwerten, dass Farbvideodaten komprimiert werden, während sie entlang des Datenstroms gespeichert werden.
Nachdem die Anzahl an unterschiedlichen Farben, welche in dem Block verbleiben, wesentlich verringert worden ist, werden die Farbdaten und die entsprechenden Pointerdaten für die verbleibenden Daten verwendet, um den Datenstrom zu kodieren. Der Datenstrom mit den kodierten Farbdaten für den aktuellen Block wird dann in die Speichermedien geschrieben. Dieser Typ von Speicherungskomprimierung erlaubt, dass eine ausreichende Datenmenge von Speichervorrichtungen, wie z. B. CD-ROMs, mit einer festen Datenrate gelesen werden, um eine ruckfreie Anzeige eines sich bewegenden Farbbildes in Echtzeit zu erzeugen.
Fig. 4 stellt die Reihe von Farbwerten für einen 4 · 4-Pixelblock dar. Die Reihe kann in der Form einer Tabelle oder jedes anderen im Stand der Technik bekannten Mittels vorliegen. Die sieben Farbwerte A bis 6 repräsentieren verschiedene Farbwerte für die Pixel in dem Block, und die entsprechenden Zahlen zeigen die Zählung des Auftretens für jeden Farbwert in dem Block an. Die Farbwerte A bis G entsprechen im allgemeinen den Farbwerten (Cx), die in Verbindung mit Fig. 3 diskutiert wurden. Wie zuvor diskutiert, werden die Farbwerte in absteigender Reihenfolge gemäß der Zählung des Auftretens für jeden Farbwert sortiert.
In dem dargestellten Beispiel wird angenommen, dass die sieben Farben nicht transparent sind und dass sie sich von den Farben in dem entsprechenden Block des vorhergehenden Videoeinzelbildes unterscheiden. Farbwert A wird mit jedem anderen Farbwert in der Reihe in absteigender Reihenfolge verglichen. Farbwert A wird verglichen mit Farbwert B, dann Farbwert C, usw. Der Prozeß wird wiederholt, während Farbwert A mit jeder nachfolgenden Farbe in der Reihe verglichen wird. In diesem Beispiel würde Farbwert A Farbe (Cm) und Farbe F würde Farbe (Cn) in Fig. 3 entsprechen. Dann wenn Farbwert A für ausreichend nahe an Farbwert F erachtet wird, d. h., wenn der Unterschied zwischen deren jeweiligen Farbwerten geringer ist als der Farbschwellenwert (CT), wird die Reihe dementsprechend aktualisiert. Da Farbwert A viermal auftritt, während Farbwert F zweimal auftritt, wird Farbwert F kollabiert bzw. mit Farbwert A konsolidiert. Die Reihe wird festhalten, dass Farbwert A sechsmal in dem Block auftritt, und Farbwert F wird aus der Reihe entfernt. Fig. 4 zeigt, dass Farbwert A tatsächlich die Stelle des Farbwerts F in dem Pixelblock einnimmt. Falls keine weitere Farbe gefunden wird, welche relativ nahe bei Farbwert A liegt, wird dann die nächste in absteigender Reihenfolge verbleibende Farbe verwendet. In dem erläuternden Beispiel wird Farbwert E später in Farbwert B kollabieren.
Nach dem ersten Komprimierungsprozeß, wie durch die Pixelblöcke in Fig. 4 gezeigt ist, verbleiben fünf Farben von den anfänglich sieben Farben. Der Farbschwellenwert wird dann, vorzugsweise durch einen vorprogrammierten Prozessor, nach Massgabe der Anzahl der verbleibenden Farben in dem Pixelblock adaptiv eingestellt. Der Komprimierungsprozeß beginnt dann erneut mit dem eingestellten Farbschwellenwert. Der Prozessor hält vorzugsweise die Anfangsfarbreihe im Speicher zurück, so dass die anfänglichen sieben Farben des Blocks mit dem eingestellten Farbschwellenwert verwendet werden. Es wird angemerkt, dass am Ende dieses zweiten iterativen Prozesses lediglich die Farbwerte A und B in der Reihe verbleiben, die Zählung des Auftretens der Farben in dem Pixelblock verbleibt jedoch bei 16. Es sind keine neuen Farben für den Block berechnet worden. Es wurden jedoch bestimmte Farbwerte durch zuvor existierende Farben in dem Block ausgetauscht und ersetzt. Die drei in Fig. 4 gezeigten Pixelblöcke repräsentieren die Pixelfarben in der Reihe bei unterschiedlichen Komprimierungsniveaus.
In dem erläuternden Beispiel verbleiben nach diesem zweiten Komprimierungsprozeß lediglich zwei Farben, A und B. Diese zwei Farben und deren jeweilige Positionspointer für den Pixelblock werden dann in einem TYP-10- Datenstrom, wie zuvor diskutiert und in Fig. 1 gezeigt, zur Speicherung in einer CD-ROM oder einer anderen geeigneten Speichervorrichtung kodiert. Diese Komprimierung und Speichermethode führt zu einem geringfügig höheren Kontrast, hält jedoch noch einige der ursprünglichen Farbelemente des Bildes zurück, welche aus dem Speicher gelesen werden können, um ein ruckfreies Abspielen von Vorrichtungen mit festen Datenraten bereitzustellen. Obwohl einige Zwischenfarbtöne in dem Kodierprozeß verlorengehen, kann eine Reihe von aufeinanderfolgenden Videobildern mit einer minimalen Menge an Hardware derart komprimiert und dekomprimiert werden, dass die Datenmenge, welche benötigt wird, um jedes Videoeinzelbild anzuzeigen, das durch Vorrichtungen mit festen Datenraten auferlegte Datenlimit, wie z. B. eine 300 Kb/Sek. CD-ROM, nicht überschreitet. Ein Kodieren der Farbvideodaten auf diese Art und Weise sorgt für die ruckfreie Abspielung aller gespeicherten Einzelbilder der Videobilder. Die Zunahme im Gesamtkontrastbild kann während der Dekomprimierung mit einem Unscharf-Filter (blur filter) korrigiert werden, während Daten von der CD-ROM gelesen werden.
Fig. 5 stellt die Reihe von Farbwerten für einen weiteren Block dar. Wie in Fig. 4 repräsentieren die variablen Werte H bis L verschiedene Farbwerte und die entsprechenden Nummern zeigen die Anzahl des Auftretens für jeden Farbwert in dem Block an. Wie zuvor angezeigt wurde, sind die Farbwerte in absteigender Reihenfolge entsprechend der Anzahl des Auftretens für jeden Farbwert sortiert. In dem zweiten dargestellten Beispiel tritt Farbwert H fünfmal auf, während Farbwert I viermal auftritt. Wenn Farbwert H gemäß einem Farbschwellenwert für ausreichend nahe an Farbwert I erachtet wird, wird die Reihe aktualisiert werden, um zu zeigen, dass Farbwert H neunmal auftritt, und Farbwert I wird aus der Reihe entfernt werden. Der Prozeß verläuft weiter und, falls keine andere Farbe gefunden wird, die vergleichsweise nahe an Farbwert H liegt, würde dann die nächste verbleibende Farbe, welche Farbwert J ist, verwendet werden und mit den verbleibenden Farben in absteigender Reihenfolge verglichen werden.
Sollten sich Farbwert J und Farbwert K als vergleichsweise nahe herausstellen, wird einer der Farbwerte ausgewählt werden und seine Anzahl des Auftretens in der Reihe wird um die Anzahl des Auftretens der anderen Farbe erhöht werden. Da beide Farben die gleiche Anzahl von Malen auftreten, wird ein sekundäres Kriterium verwendet, um zu bestimmen, welche Farbe in der Reihe verbleiben wird. Beispielsweise kann der Farbwert mit dem höheren Bildleuchtdichte-Wert ausgewählt werden. Alternativ könnten die Farben zusammen kollabiert werden, wenn die Unterschiede zwischen ihren jeweiligen Farbwerten unterhalb eines weiteren vorbestimmten Schwellenwerts liegen. Da die Farbwerte relativ nahe beieinander liegen, sollte die Auswahl einer Farbe zum Nachteil der anderen keinen wesentlichen Einfluß auf das Gesamtbild haben. Es könnte jedoch Situationen geben, in denen es wünschenswert wäre, die Farben zu einem höheren oder niedrigeren Farbwert zu zwingen. Lediglich zum Zwecke der Erläuterung wird das Auftreten der Farbwerte J und K zu Farbwert J kollabiert werden. Am Ende dieses iterativen Prozesses verbleiben lediglich Farbwerte H, J und L in der Reihe und die Zählung des Auftretens von Farben in dem Block bleibt 16. Diese drei verbleibenden Farbwerte können dann in einem TYP-11-Datenstrom kodiert werden.
Fig. 6 stellt eine Reihe von Farben für einen Block dar, welcher einige Farben N, P, R, S und T enthält, von denen einige "transparent" in Bezug auf den entsprechenden Pixelblock im vorhergehenden Videoeinzelbild sind. Die eingekreisten Pixelfarben sind jene Pixel, deren Farbe die gleiche ist wie in dem vorhergehenden Einzelbild. In dem Pixelblock nach der Komprimierung sind diese erneut auftretenden Pixel mit einem -Symbol freigelassen, um deren "Transparenz"- oder Null-Wert zu repräsentieren. In dem dargestellten Beispiel befindet sich das verbleibende Auftreten der Farben N, P und T an Pixelstellen, welche jenen in dem vorhergehenden Einzelbild entsprechen. Somit verschwinden diese drei Farben tatsächlich als transparente Farben, und für diesen Pixelblock müssen keine speziellen Informationen bezüglich der Farben N, P und T gespeichert werden. Obwohl die Farben R und S an einigen alten Pixelstellen erneut auftreten, treten diese zwei Farben ebenso an einigen neuen Pixelstellen auf. Deshalb wird dieser Pixelblock in einem TYP-11-Datenstrom kodiert werden, obgleich keine zusätzlichen Farben in dem Block erscheinen, da zwei Farben an einigen Pixelstellen erscheinen, welche von ihren Stellen in dem vorhergehenden Einzelbild in dem Block verschieden sind. Wie zuvor bemerkt wurde, werden die "transparenten" Farben relativ zu dem vorherigen Einzelbild vorzugsweise als eine getrennte diskrete Farbe betrachtet. Deshalb ist in diesem Fall für den Pixelblock ein TYP-11-Kodieren und nicht ein TYP-10-Kodieren erforderlich.
Wie zuvor diskutiert wurde, können die bestimmten Farbwerte (CX) R-, G- und B-Komponenten aufweisen. Fig. 7 stellt zwei Farbwerte C&sub0; und C&sub1; im RGB- Raum dar. Die Stellen der Farbwerte im RGB-Raum sind somit durch die R-, G- und B-Werte der Pixel definiert. In dieser Darstellung repräsentiert Farbwert C&sub1; den Farbwert eines Pixels in dem aktuellen Einzelbild und der Farbwert C&sub0; repräsentiert den Farbwert des entsprechenden Pixels in dem vorhergehenden Videoeinzelbild. Selbstverständlich ist diese Darstellung ebenso anwendbar auf die Bestimmung von vergleichsweise nahen Farben, wie in Fig. 3c gezeigt ist. Der Unterschied oder Abstand zwischen den Farbwerten des Pixels kann gemäß der folgenden Gleichung bestimmt werden:
d = X²(R&sub1; - R&sub0;)² + Y²(G&sub1; - G&sub0;)² + Z²(B&sub1; - B&sub0;)²
wobei X, Y und Z gewichtete Koeffizienten sind, welche eingestellt werden können, um wie gewünscht zu unterschiedlichen Graden der Nähe zwischen zwei Farbwerten zu gelangen. Unterschiedliche Werte für die Koeffizienten X, Y und Z können verwendet werden, um eine besondere Farbkomponente mehr oder weniger hervorzuheben. Somit kann der Abstand zwischen Pixelfarbwerten C&sub0; und C&sub1; im RGB-Raum verwendet werden, um beim Kodieren von Farbvideodaten deren relative Nähe zu bestimmen.
Die oben beschriebene Komprimierungs-Speicherungsmethode kann in Verbindung mit Personalcomputern wie in Fig. 8 gezeigt verwendet werden. Personalcomputer, wie z. B. jene mit einem 486- oder einem anderen Mikroprozessor, können verwendet werden, um die Farbvideodaten zu kodieren und zu dekodieren. Der Mikroprozessor 21 kann die Farbwerte und Tabellen in seinem Random-Access-Speicher (RAM) 22 speichern, während er die Farben in einem Pixelblock identifiziert und zählt. Die Videodaten können durch eine E/A-Vorrichtung 35 bereitgestellt und auf einem Videomonitor 40 betrachtet werden. Der Mikroprozessor 21 manipuliert dann die Daten in dem RAM 22 entsprechend dem Kodierprozeß, wie zuvor diskutiert. Nachdem die Anzahl an unterschiedlichen Farbwerten in dem Pixelblock auf weniger als vier reduziert worden ist, werden die verbleibenden Farben des Pixelblocks in einem geeigneten Datenstrom kodiert und in einem Speichermedium mit großer Dichte, wie z. B. der CD-ROM 30, gespeichert. Der reduzierte Datenstrom kann später mit der festen Einzelbildrate der CD-ROM 30 gelesen werden, um ein ruckfreies Videoabspielen in Echtzeit auf dem Farbmonitor 140 zu erreichen. Jeder kompatible Mikroprozessor 121 mit Random-Access- Speicher 122 kann diesen Datenstrom von der CD-ROM 30 dekodieren. Es wird verstanden, dass getrennte oder unterschiedliche Mikroprozessoren 21 und 121 verwendet werden können, um den Datenstrom zu kodieren und zu dekodieren. Das Verwenden derartiger Hardware entsprechend der Lehren der Erfindung liegt innerhalb des gewöhnlichen Niveaus an im Stand der Technik vorgefundenen Fähigkeiten.

Claims

1. Verfahren zum Komprimieren von Farbvideodaten, welche Farbvideoeinzelbilder an einer Anzeigevorrichtung definieren, wobei das Verfahren folgende Schritte umfasst:

Vorsehen eines eine Mehrzahl von Pixeln umfassenden Farbvideoeinzelbildes, wobei jedes Pixel eine zugeordnete Farbe aufweist;

Unterteilen des Farbvideoeinzelbildes in Pixelblöcke; sowie

Bestimmen der Farben, welche in einem der Blöcke vorhanden sind, dadurch gekennzeichnet, dass das Verfahren weiterhin folgende Schritte umfasst:

Berechnen einer Anzahl von Farben für den einen der Blöcke entsprechend einer Farbschwelle, wobei die Anzahl der Farben nicht grösser ist als eine vorbestimmte Anzahl; sowie

Speichern von Farbvideodaten, welche jedes Pixel in dem Block repräsentieren, wobei der Schritt des Berechnens der Anzahl von Farben für den einen der Blöcke umfasst:

Sortieren der bestimmten Farben, welche in dem Block vorhanden sind, nach der Häufigkeit des Auftretens einer jeden Farbe,

Vergleichen einer jeden der bestimmten Farben mit jeder anderen bestimmten Farbe,

Bestimmen von Farben als die gleichen oder vergleichsweise nahe Farben aus dem Vergleich der bestimmten Farben, wenn der Unterschied zwischen den Farben geringer ist als die Farbschwelle, sowie

Ersetzen der weniger häufig auftretenden Farbe durch die häufiger auftretende Farbe von zwei vergleichsweise nahen Farben.

2. Verfahren nach Anspruch 1, wobei der Schritt des Bestimmens der Farben, welche in einem der Blöcke vorhanden sind, den Schritt des Pixel-für-Pixel-Vergleichens der Farben, welche in dem Block vorhan den sind, mit den Farben in einem entsprechenden Block in einem vorhergehenden Farbvideoeinzelbild umfasst, wobei der Farbe eines Pixels ein Null-Wert gegeben wird, wenn der Unterschied zwischen der Farbe des jeweiligen Pixels, welches in dem Block vorhanden ist, und der Farbe des entsprechenden Pixels in dem entsprechenden Block in dem vorhergehenden Farbvideoeinzelbild geringer ist als ein Transparenzschwellenwert.

3. Verfahren nach Anspruch 1 oder Anspruch 2, wobei der Schritt des Speicherns weiterhin folgende Schritte umfasst:

Zuweisen eines Typ-Parameters zu dem Pixelblock, wobei der Typ bestimmt wird durch die Anzahl von Farben, welche in dem Block verbleiben und wobei der Typ-Parameter durch ein Typ-Parameter- Wort repräsentiert wird;

Bestimmen der Anzahl von Farbwörtern, welche notwendig sind, um die Anzahl von verbleibenden Farben aus dem Typ-Parameter zu definieren;

Zuweisen von Bit-Werten, weiche die in dem Block verbleibenden Farben repräsentieren, zu den Farbwörtern;

Bestimmen der Anzahl von Pixelwörtern, welche durch den Typ-Parameter benötigt werden;

Zuweisen von Bit-Werten, welche Pointer auf bestimmte Bit-Werte der Farbwörter repräsentieren, zu den Pixelwörtern;

Erstellen einer Datenaufzeichnung für den Pixelblock umfassend das Typ-Parameter-Wort, welches den Typ-Parameter repräsentiert, gefolgt von der bestimmten Anzahl von Farbwörtern sowie der bestimmten Anzahl von Pixelwörtern.

4. Verfahren nach einem der Ansprüche 1 bis 3, weiterhin umfassend den Schritt des Einstellens der Farbschwelle und erneutes Berechnen der Anzahl von Farben für den Block, wenn die berechnete Anzahl an Farben größer ist als die vorbestimmte Anzahl.

5. Verfahren nach einem der vorhergehenden Ansprüche, wobei die vorbestimmte Anzahl vier ist.

6. Verfahren nach einem der vorhergehenden Ansprüche, wobei das Farbvideoeinzelbild in 4 · 4-Pixelblöcke unterteilt wird.

7. Verfahren nach Anspruch 5, weiterhin umfassend den Schritt des Einstellens der Farbschwelle und des erneuten Berechnens der Anzahl von Farben für den Block, wenn die berechnete Anzahl an Farben drei ist.

8. Verfahren nach Anspruch 7, wobei die Farbschwelle derart eingestellt wird, dass die berechnete Anzahl an Farben zwei ist.

9. Verfahren nach Anspruch 1, wobei die Farben nach der absteigenden Häufigkeit des Auftretens einer jeden Farbe sortiert sind.

10. Vorrichtung zum Komprimieren von Farbvideodaten, welche Farbvideoeinzelbilder an einer Anzeigevorrichtung (40) definieren, wobei jedes der Einzelbilder eine Mehrzahl von Pixeln umfasst, wobei jedes Pixel eine zugeordnete Farbe aufweist, und wobei die Vorrichtung umfasst: einen Speicher (22);

sowie einen Prozessor (21) zum Unterteilen jedes Farbvideoeinzelbildes in Pixelblöcken und zum Bestimmen der in jedem Block vorhandenen Farben, dadurch gekennzeichnet, dass der Prozessor weiterhin ausgebildet ist zum Berechnen eines Farbwertes für jedes Pixel in dem Block, zum Zählen des Auftretens eines jeden Farbwertes in dem Block sowie zum vorübergehenden Speichern einer Tabelle umfassend jeden Farbwert in dem Block sowie die Anzahl des Auftretens für jeden Farbwert in dem Speicher (22);

wobei der Prozessor (21) weiterhin jeden Farbwert in der Tabelle, welche in dem Speicher (22) gespeichert ist, mit jedem anderen Farbwert in der Tabelle vergleicht, welche in dem Speicher (22) gespeichert ist, wobei dann, wenn der Unterschied zwischen zwei Farbwerten geringer ist als ein Farbschwellenwert, die Anzahl des Auftretens für den weniger häufig auftretenden Farbwert zu der Anzahl von häufiger auftretenden Farbwerten addiert wird und der weniger häufig auftretende Farbwert aus dem Speicher (22) gelöscht wird, so dass der häufiger auftretende Farbwert den weniger häufig auftretenden Farbwert in dem Block ersetzt; sowie

Mittel zum Speichern der verbleibenden Farbwerte in dem Block aus dem Speicher (22).

11. Vorrichtung nach Anspruch 10, wobei die verbleibenden Farbwerte des Pixelblocks in einem Datenstrom kodiert und auf einer CD-ROM (30) gespeichert sind.