DE69518641T2

DE69518641T2 - Skalierbares pixelverteilungsbildkodierungssystem zur kompression und dekompression von bildern

Info

Publication number: DE69518641T2
Application number: DE69518641T
Authority: DE
Inventors: A. Rodriguez
Original assignee: Object Technology Licensing Corp
Current assignee: Object Technology Licensing Corp
Priority date: 1994-05-10
Filing date: 1995-05-05
Publication date: 2001-04-19
Anticipated expiration: 2015-05-06
Also published as: JPH10503629A; EP0759254B1; AU2474295A; DE69518641D1; WO1995031071A1; US5585944A; EP0759254A1; JP3727341B2

Description

Hintergrund der Erfindung

1. Bereich der Erfindung

Das Verfahren und die Vorrichtung der vorliegenden Erfindung betreffen das Speichern, das Anzeigen und das Abspielen digitalisierter visueller Bilder, und insbesondere betrifft die Erfindung eine Vorrichtung und ein Verfahren zur Kompression und Dekompression digitalisierter visueller Bilder.[0001]

2. Stand der Technik

Zahlreiche digitale Geräte, wie zum Beispiel Computer und Videokassettenrekorder (VCR), werden zum Speichern und Anzeigen visueller Bilder zum Beispiel in Form von Filmen verwendet. Digitalisierte visuelle Bilder erfordern große Speicherkapazitäten. Ein Bildrahmen eines Films benötigt 153.600 Byte (320 · 240 · 2), wenn die Darstellung in dekomprimierter Form für einen RGB 16 Anzeigemodus erfolgt. Bei 15 Bildrahmen pro Sekunde benötigt eine Filmsekunde 2.304.000 Byte Speicherplatz. Da der Umfang an Speicherplatz in digitalen Geräten begrenzt ist, und da digitale Geräte eine begrenzte interne Bandbreite besitzen, besteht ein Bedarf an der Darstellung digitalisierter Bilder in komprimierter Form. Die Verbreitung digitaler Videos in Multimediaanwendungen hat diesen Bedarf noch verstärkt.[0002]
Eine Technik des Standes der Technik zum Komprimieren digitalisierter monochromer visueller Bilder ist als Blockverkürzungscodierung (engl.: Block Truncation Coding, abgekürzt BTC) bekannt und wurde erstmals von Delp und Mitchell beschrieben. Siehe E. J. Delp und O. R. Mitchell, "Image Compression Using Block Truncation Coding," IEEE Transactions on Communications, Vol. COM- 27, Nr. 9, Seiten 1335-1342, September 1979 (im folgenden als "Delp-Methode" bezeichnet). Diese Methode nutzt die Tendenz des menschlichen Auges, den Durchschnittswert eines feinen Details innerhalb eines kleinen Bereiches wahrzunehmen, wenn dieser kleine Bereich aus einer Entfernung betrachtet wird. Wenn das feine Detail mit Informationen repräsentiert wird, welche die durchschnittliche und die Standardabweichung der ursprünglichen Informationen repräsentieren, nimmt das menschliche Auge keinen Informationsverlust wahr.[0003]
BTC wurde auf Farbbilder erweitert. Die allgemeine Farb-BTC-Methode umfaßt die folgenden Schritte:[0004]
1. Zerlegen des Bildes in nicht überlappende n · m große Blöcke.
2. Suchen des durchschnittlichen Luminanzwertes, YaVg, für jeden Block, und Ausführen der Schritte 3 bis 6.
3. Suchen der durchschnittlichen Farbe Clow für alle Pixel in einem Block, deren Luminanzwerte kleiner oder gleich sind wie Yavg.
4. Suchen der durchschnittlichen Farbe Chigh für alle Pixel in einem Block, deren Luminanzwerte größer sind als Yavg
5. Konstruieren eines Binärmusters für jeden Block durch Darstellung von Pixeln, die zu Clow gehören, als "0" im Binärmuster, und Pixeln, die zu Chigh gehören, als "1".
6. Codieren des Blocks mit seinen zwei repräsentativen Farbwerten und dem Binärmuster, wobei "0" oder "1" für jedes Pixel verwendet wird.
[0005] Siehe G. Campbell, et al., "Two Bit/Pixel Full Color Encoding," in ACM Computer Graphics, Vol. 20, Nr. 4, Seiten 215-223, Dallas, Aug. 1986. Somit wird jedes Pixel innerhalb eines Blocks als eine von zwei Farben repräsentiert. Dadurch wird Platz gespart, da der Block mit zwei Farben codiert wird, das heißt, es werden vier Bytes für zwei RGB 16 Farben verwendet, um den Wert des Binärmusters plus dem 1 Bit pro Pixel im Binärmuster anzugeben. Zum Beispiel wird ein Block mit 4 · 4 Pixeln mit vier Bytes codiert, um die zwei Farben plus 16 Bits, je eines für jedes Pixel im Block, zu repräsentieren. Somit wird der Block mit insgesamt 48 Bits oder 6 Bytes codiert. Ohne BTC wird jedes Pixel mit 16 Bits codiert, die erforderlich sind, um den RGB 16 Farbwert des Pixels darzustellen, wobei insgesamt 256 Bits für einen Block von 4 · 4 Pixel erforderlich sind. Somit ermöglicht BTC eine Kompressionsrate von 256/48 oder 16 : 3 für einen Block von 4 · 4 Pixel.
[0006] Die Methoden, welche ein Bild in Blöcke zerlegen, den Block als zwei repräsentative Werte codieren und die Pixel im Block als Binärmuster codieren, werden im allgemeinen als Binärmuster-Bildcodierung (Binary Pattern Image Coding, kurz BPIC) bezeichnet. Die Blockgröße, die mit BPIC verwendet werden kann, hängt vom Betrachtungsabstand zum Monitor, der Pixelauflösung und den physikalischen Abmessungen am Monitor ab. Lesen Sie dazu z. B. D. Chen und A. C. Bovik, "Visual Pattern Image Coding," IEEE Transactions on Communications, Vol. COM- 38, Nr. 12, Seiten 2136-2146, Dezember 1990. Da mei stens weder die Farbverteilung der zu komprimierenden Bilder noch das Ausmaß der Informationsschwankungen pro Block vor der Kompression bekannt sind, ist es schwer, die Blockgröße abzuschätzen, die zur Beibehaltung eines akzeptablen Informationsgehalts erforderlich ist.
[0007] Ein Beispiel für eine Abänderung der BPIC-Codierung ist im US-Patent Nr. 07/965,580 offenbart, das als US 5392072 A, abgetreten an IBM von Arturo Rodriguez, Mark Pietras und Steven Hancock, veröffentlicht und im Oktober 1992 angemeldet wurde und den Titel "HYBRID VIDEO COMPRESSION SYSTEM AND METHOD CAPABLE OF SOFTWARE-ONLY DECOMPRESSION IN SELECTED MULTIMEDIA SYSTEMS" trägt. Die Anmeldung 07/965.580 unterteilt Bilder in Regionen und überprüft jede Region mit einem Homogenitätstest. Wenn die Region homogen ist, wird sie als eine einzige Farbe codiert. Wenn die Region nicht homogen ist, wird die Region entweder mit BPIC codiert, oder sie wird in Quadranten unterteilt, und die Quadranten werden als homogene Regionen oder mit BPIC codiert.
[0008] Da die in der Patentanmeldung 07/965.580 offenbarte Methode einen Block nicht über Quadranten hinaus zerlegt, weist sie die selben Einschränkungen auf wie andere nicht-rekursive (BPTC) Methoden. Da meistens weder die Farbverteilung der zu komprimierenden Bilder noch das Ausmaß der Informationsschwankungen pro Block vor der Kompression bekannt sind, ist es schwer, die Block- oder Quadrantengröße abzuschätzen, die zur Beibehaltung eines akzeptablen Informationsgehalts erforderlich ist. Idealerweise ist es wünschenswert, die Blockgröße je nach dem Informationsgehalt der lokalen Bildregion adaptiv auszuwählen.
[0009] Roy und Nasarabadi schlagen die Verwendung einer Methode vor, die mit großen Blöcken beginnt und die BTC-Technik rekursiv an immer kleiner werdenden Blöcken anwendet, indem der Block solange in Quadranten zerlegt wird, bis eine entsprechende Auflösung mit geringer Informationsschwankung gefunden wird. Siehe dazu J. U. Roy und N. M. Nasarabadi, "Hierarchical Block Truncation Coding," Optical Engineering, Vol. 30, Nr. 5, Seiten 551-556.
[0010] Kamel verwendet eine ähnliche Methode, wobei er ein Intervall, [Yavg -t, Yavg +t] rund um den durchschnittlichen Luminanzwert des Blocks verwendet, um den besten Grenzwert zu finden, der den mittleren quadratischen Farbfehler minimiert. Siehe M. Kamel, C. T. Sun und L. Guan, "Image Compression By Variable Block Truncation Coding With Optimal Threshold," IEEE Trans. on Signal Processing, Vol. 39, Nr. 1, Seiten 208-212, Januar 1991.
[0011] Eine rekursive Blockzerlegung führt zu einer wesentlich besseren Kompression als nicht-rekursive Methoden. Durch adaptive Auswahl der Mindestanzahl an Farben, die zur Darstellung des Blocks erforderlich ist, kann das Bild anfänglich in willkürlich große Regionen unterteilt werden. Das Codieren einer großen homogenen Region als eine einzige Farbe führt zu einer besseren Kompression als das unnotwendige Codieren der selben großen Region als Gruppe kleiner Regionen mit der selben Farbe, da jede Region mit dieser Farbe codiert werden muß, wodurch eine bestimmte Anzahl an Bytes benötigt wird. Wenn zum Beispiel eine große Region als eine einzige Farbe repräsentiert wird, wird die Region mit einem zwei Byte großen Farbwert codiert. Wenn die selbe Region als 4 Regionen codiert wird, muß jede Region mit der zwei Byte großen Farbe codiert werden. Somit werden in diesem Fall 6 Bytes eingespart, indem die große Region als eine einzige Farbe repräsentiert wird.
[0012] Nicht-rekursive Methoden, wie zum Beispiel jene Methode, die in der Patentanmeldung 07/965.580 beschrieben ist, können keine beliebig großen Regionen codieren, wie dies zuvor beschrieben wurde, sondern die Regionen, in welche das Bild unterteilt werden soll, müssen ausreichend klein sein, um inakzeptable Informationsverluste zu vermeiden. Für ein beliebiges Bild muß sich diese Wahl nicht unbedingt als optimal erweisen, da das Bild einzelne Farbregionen enthalten kann, die größer sind als die ausgewählte Blockgröße. Durch Unterteilung dieser einzelnen Farbregionen in kleinere Regionen auf Grund der anfänglich festgelegten Regionengröße führen nicht-rekursive Methoden zu einer nicht optimalen Kompression.
[0013] Wenngleich die Techniken, die das Bild auf rekursive Weise in immer kleinere Blöcke aufteilen, zu einer stärkeren Kompression führen als nicht-rekursive Methoden, weisen die rekursiven Methoden des Standes der Technik Nebenwirkungen auf, die oft zu einer Verringerung der Bildqualität führen. Das Unterteilen des Bildes in immer kleinere Blöcke führt dazu, daß dem Bild eine künstliche Blockstruktur auferlegt wird, und das komprimierte Bild sieht daher auch oft so aus, als wäre es in eine künstliche Struktur gezwängt.
[0014] Wie im folgenden beschrieben, wird dem Bild durch die Methode und Vorrichtung der vorliegenden Erfindung keine künstliche Struktur auferlegt. Die Methode ermöglicht es, daß beliebig geformte Objekte innerhalb eines Blocks ihre ursprünglichen Grenzen beibehalten, anstatt daß sie in die Struktur der Quadrantenunterteilung der früher vorgeschlagenen Ansätze unterteilt werden. Die Methode der vorliegenden Erfindung ermöglicht daher die Beibehaltung einer höheren Bildqualität, da die geeignete Anwendung einer einzigen Farbe validiert wird.
[0015] Um die Eignung der Codierung einer Verteilung als einzelne Farbe zu validieren, verwendet die Methode der vorliegenden Erfindung einen Homogenitätstest, wie er zum Beispiel in der Patentanmeldung Nr. 07/965,580 offenbart ist. Wie zuvor beschrieben, unterteilt die in der Patentanmeldung Nr. 07/965,580 offenbarte Methode ein Bild in Regionen und überprüft jede Region mit einem Homogenitätstest. Wenn die Region homogen ist, wird sie als eine einzige Farbe codiert. Wenn die Region nicht homogen ist, wird die Region entweder mit BPIC codiert, oder sie wird in Quadranten unterteilt, und die Quadranten werden als homogene Regionen oder mit BPIC codiert.
[0016] Im Gegensatz zu der in der Patentantneldung Nr. 07/965,580 offenbarten Methode verwenden die Methode und die Vorrichtung. der vorliegenden Erfindung einen Homogenitätstest auf rekursive Weise, um einen Block in eine Reihe homogener Verteilungen aufzulösen. Wie dies weiter unten offenbart wird, zerlegen die Methode und die Vorrichtung der vorliegenden Erfindung Bildrahmen durch Aufteilung von Pixelverteilungen nach Luminanzeigenschaften, was im Gegensatz zu Techniken des Standes der Technik steht, bei denen Bilder rekursiv in immer kleinere Blöcke aufgeteilt werden. Somit legen, wie zuvor erwähnt, die Methode und die Vorrichtung der vorliegenden Erfindung dem zu komprimierenden Bild keine künstliche Struktur auf, und somit wird die Qualität des Bildes beim Komprimieren wesentlich verbessert.
[0017] Abgesehen von den BPIC-Techniken basiert eine andere vorgeschlagene Kompressionstechnik auf der Darstellung von Pixelgruppen durch getrennte Luminanz- und Farbtonwerte für die Gruppe. Das International Radio Consultative Committee (CCIR) hat eine bestimmte Codierungsmethodik für diese Methode vorgeschrieben. Es werden jeweils zwei Pixelregionen eines digitalisierten Rahmens aufeinanderfolgend mit Hilfe eines individuellen Ein-Byte-Luminanzwertes für jeden Pixel codiert, und für den Vier-Pixel-Bereich werden zwei Byte eines repräsentativen Farbtonunterschiedwertes (Farbton) verwendet. Somit werden nun nicht die vier Pixel als 12 Bytes, nämlich 3 Bytes pro Pixel für RGB24-Darstellungen, verwendet, sondern die vier Pixel werden als 6 Bytes für eine Kompressionsrate von 50% repräsentiert. Ein wirkungsvolles System, welches dieses komprimierte Signal wieder in ursprüngliche RGB24-Anzeigedaten zurückverwandelt, ist im US-Patent 5,262,847, veröffentlicht am 16. November 1993 an Arturo Rodriguez et al., beschrieben.
[0018] Somit besteht Bedarf an einer Kompressionsmethode, die hohe Kompressionsraten ermöglicht und gleichzeitig eine Verzerrung im komprimierten Bild verhindert. Wie dies weiter unten noch ausführlicher beschrieben wird, führen die Methode und die Vorrichtung der vorliegenden Erfindung typischerweise zu einer viel höheren Kompressionsrate als die CCIR-Codiermethodik.
[0019] Wie weiter unten beschrieben wird, behalten die Methode und die Vorrichtung der vorliegenden Erfindung die Vorteile der rekursiven BPIC-Techniken bei, ohne den Bildern künstliche Strukturen aufzuerlegen. Somit führen die Methode und die Vorrichtung der vorliegenden Erfindung zu einer Kombination aus besserer Bildqualität, besserer Kompression und geringerer Komplexität, wobei gleichzeitig die Einfachheit der Dekompression beibehalten wird.

ZUSAMMENFASSUNG DER ERFINDUNG

[0020] Die vorliegende Erfindung schafft Methoden und eine Vorrichtung zur Darstellung visueller Farb- oder Schwarzweißbilder in komprimierter, digitaler Form. Die Methoden ermöglichen eine rasche Dekompression bei gleichzeitiger Beibehaltung einer höheren Bildqualität im Vergleich zu herkömmlichen BPIC-Methoden. Gemäß der vorliegenden Erfindung werden ein visuelles Bild oder eine Reihe miteinander in Beziehung stehender visueller Bilder, wie zum Beispiel eine Abfolge von Bildrahmen in einem Film, in digitaler oder analoger Form gespeichert und einem Komprimierer der vorliegenden Erfindung zur Verfügung gestellt. Eine Reihe digitaler Bilder wird einem Direktzugriffsspeicher (RAM) zur Verfügung gestellt und von der Zentraleinheit (CPU) des Computers Bildrahmen für Bildrahmen verarbeitet. Ein Dekomprimierer dekomprimiert nach den Codierregeln des Komprimierers einen Bildrahmen nach dem anderen und stellt dem Video-RAM eines Anzeigegeräts, wie zum Beispiel eines Monitors, die dekomprimierten Bildrahmen zur Verfügung.
[0021] Der Komprimierer der vorliegenden Erfindung unterteilt einen Bildrahmen in eine bevorzugte Anzahl an beliebig großen, nicht überlappenden, angrenzenden Regionen, bei denen es sich um einfache Blöcke handeln kann. Jeder Block wird getestet, um zu bestimmen, ob der Block eine homogene Farbverteilung aufweist. Wenn der Block eine homogene Farbverteilung aufweist, wie dies durch einen ausgewählten Homogenitätstest definiert wird, wird jedes Pixel in diesem Block als einzelne Farbe repräsentiert, und daher wird nur eine Farbe zur Codierung des Blocks benötigt. Wenn der Block keine homogene Farbverteilung aufweist, wird der Block in zwei Verteilungen, P(high) und P(low), unterteilt, wobei P(high) jener Teil der ersten Verteilung mit einer größeren Luminanz als die durchschnittliche Luminanz der ersten Verteilung, Yavg, ist, und P(low) jener Teil der ersten Verteilung ist, dessen Luminanz gleich groß oder kleiner ist als jene von Yavg. P (high) und P(low) werden separat auf ihre Homogenität überprüft, und der selbe Prozeß wird an beiden rekursiv angewandt, bis die Region in homogene Pixelverteilungen aufgelöst wurde.
[0022] Der Komprimierer stellt gleichzeitig auch sicher, daß homogene Verteilungen, die während des Aufteilungsprozesses geteilt wurden, wieder zusammengemischt werden. Wenn zum Beispiel eine Verteilung in die Verteilungen P(high) und P(low) aufgeteilt wird, könnten diese Verteilungen weiters in die Verteilungen P(high, high) und P(high, low), P(low, high) und P(low, low) aufgeteilt werden. Der Komprimierer überprüft, ob die Mischung von P(low, high) mit P(high, low) zu einer homogenen Verteilung führt. Wenn dies der Fall ist, wird die zusammengemischte Verteilung als einzelne Farbe codiert.
[0023] Jede homogene Verteilung innerhalb eines Blocks wird als einzelne Farbe codiert, und ein unterschiedlicher Binärcode, der die einzelnen Farben repräsentiert, wird jeder homogenen Verteilung zugeordnet. Wenn zum Beispiel ein Block zwei homogene Farbverteilungen, wie zum Beispiel Rot und Schwarz, enthält, kann die Farbe Rot dem Binärcode "0" und die Farbe Schwarz dem Binärcode "1" zugeordnet werden.
[0024] Um die Kompressionsrate zu erhöhen, verwendet der Komprimierer Bildrahmenunterscheidungstechniken, um die Redundanz zwischen aufeinanderfolgenden Bildrahmen zu nutzen.
[0025] Nach den Regeln des Komprimierers rekonstruiert ein Dekomprimierer der vorliegenden Erfindung die Farbe eines jeden einzelnen Pixels. In Fortsetzung des obigen Beispiels setzt der Dekomprimierer, wenn die Farbe Rot dem Binärcode "0" zugeordnet wurde und die Farbe Schwarz dem Binärcode "1" zugeordnet wurde, den vollen Farbwert für Rot, zwei Bytes für RGB 16 Anzeigearten, für jeden Pixel, der mit "0" codiert wurde, ein, und er setzt die Farbe Schwarz für jeden Pixel ein, der mit "1" codiert wurde. Der Dekomprimierer weist die Farben ihren entsprechenden Mustern zu, indem er die selben Regeln befolgt, wie sie der Komprimierer für die Zuordnung von Mustern zu den Farben verwendet.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

[0026]
Fig. 1 ist ein Überblick über ein System, welches den Lehren der vorliegenden Erfindung zum Komprimieren und Speichern digitaler Bilder und zum Dekomprimieren und Anzeigen der ursprünglichen Bilder folgt.
Fig. 2 ist ein Funktionsblockdiagramm des Kompressions- und Dekompressionssystems der vorliegenden Erfindung.
Fig. 3 zeigt einen beispielhaften Bildrahmen, der komprimiert werden soll.
Fig. 4 zeigt die Unterteilung eines beispielhaften Bildrahmens in einzelne Blöcke.
Fig. 5 zeigt eine repräsentative Luminanzverteilung für einen homogenen Block.
Fig. 6 zeigt eine repräsentative Luminanzverteilung für einen nicht homogenen Block.
Fig. 7a und 7b zeigen die Unterteilung der Verteilung von Fig. 6 in zwei separate Verteilungen.
Fig. 8a und 8b zeigen die Unterteilung der Verteilung von Fig. 7a in zwei separate Verteilungen.
Fig. 8c und 8d zeigen die Unterteilung der Verteilung von Fig. 7b in zwei separate Verteilungen.
Fig. 9 zeigt die Verteilung, die durch das Zusammenmischen der Verteilungen von Fig. 8b und 8c gebildet wird.
Fig. 10a zeigt ein weiteres Beispiel einer Luminanzverteilung eines nicht homogenen Blocks.
Fig. 10b und 10c zeigen die Unterteilung eines Teils der Verteilung von Fig. 10a in zwei Verteilungen.
Fig. 10d zeigt eine Verteilung, die durch das Zusammenmischen der Verteilungen eines Teils von Fig. 10a und Fig. 10b gebildet wird.
Fig. 11 zeigt das Kompressionsformat eines Blocks, das von der bevorzugten Ausführungsform der vorliegenden Erfindung verwendet wird.
Fig. 12a bis 12 h stellen ein Flußdiagramm dar, welches die Methode der vorliegenden Erfindung repräsentiert.
Fig. 13 ist ein Flußdiagramm, welches die Methode der vorliegenden Erfindung repräsentiert, die in Verbindung mit der Bildrahmen-Voruriterscheidung verwendet wird.
Fig. 14 ist ein Flußdiagramm, welches die Methode der vorliegenden Erfindung repräsentiert, die in Verbindung mit der Bildrahmen-Nachunterscheidung verwendet wird.

NOTATIONEN UND BENENNUNGEN

[0027] Die nun folgenden detaillierten Beschreibungen werden weitestgehend in Form von Algorithmen und symbolischen Darstellungen von Operationen an Datenbits innerhalb eines Computerspeichers präsentiert. Diese Beschreibungen und Darstellungen werden von Fachleuten des Bereiches Datenverarbeitung verwendet, um das Wesentliche ihrer Arbeit auf wirksamste Weise anderen Fachleuten zu vermitteln.
[0028] Ein Algorithmus wird hier im allgemeinen als in sich abgeschlossene Abfolge von Schritten verstanden, die zu einem erwünschten Ergebnis führt. Diese Schritte erfordern physikalische Manipulationen physikalischer Größen. Wenngleich dies nicht immer so sein muß, nehmen diese Größen doch für gewöhnlich die Form elektrischer oder magnetischer Signale an, die gespeichert, übertragen, kombiniert, verglichen oder auf sonstige Weise manipuliert werden können. In vielen Fällen erweist es sich als vorteilhaft, diese Signale hauptsächlich des allgemeinen Gebrauchs wegen als Bits, Werte, Elemente, Symbole, Zeichen, Begriffe, Zahlen und ähnliches zu bezeichnen. Es sollte jedoch berücksichtigt werden, daß alle diese und ähnliche Bezeichnungen mit den entsprechenden physikalischen Größen in Zusammenhang gebracht werden sollten und nicht mehr als nützliche Bezeichnungen für diese Größen sind.
[0029] Des weiteren werden die daran vorgenommenen Manipulationen oftmals mit Begriffen wie zum Beispiel Addieren oder Vergleichen bezeichnet, die im allgemei nen mit mentalen Vorgängen in Zusammenhang gebracht werden, wie sie von einer menschlichen Person ausgeführt werden. In den meisten Fällen ist keine derartige Fähigkeit einer menschlichen Person für die hierin beschriebenen Operationen erforderlich, welche Bestandteil der vorliegenden Erfindung sind; bei den Operationen handelt es sich um von Maschinen ausgeführte Operationen. Zu den für die Ausführung der Operationen der vorliegenden Erfindung nützlichen Maschinen gehören digitale Allzweck-Computer oder andere ähnliche Digitalgeräte. In allen Fällen sollte jedoch der Unterschied zwischen den Methodenoperationen bei Betrieb eines Computers und der Berechnungsmethode selbst berücksichtigt werden. Die vorliegende Erfindung betrifft Methodenschritte für den Betrieb eines Computers bei der Verarbeitung elektrischer oder anderer (z. B. mechanischer, chemischer) physikalischer Signale zur Erzeugung anderer erwünschter physikalischer Signale.
[0030] Die vorliegende Erfindung betrifft auch eine Vorrichtung zur Durchführung dieser Operationen. Diese Vorrichtung kann speziell für die erforderlichen Zwecke konstruiert sein, oder es kann sich dabei um einen Allzweck-Computer handeln, der wahlweise von einem Computerprogramm, das im Computer gespeichert ist, aktiviert oder rekonfiguriert wird. Die hierin präsentierten Algorithmen beziehen sich nicht auf einen speziellen Computer oder eine andere spezielle Vorrichtung. Insbesondere können verschiedene Allzweckmaschinen mit Programmen verwendet werden, die gemäß den hierin enthaltenen Lehren geschrieben wurden, oder es kann sich als vorteilhafter erweisen, eine spezialisiertere Vorrichtung zur Ausführung der erforderlichen Methodenschritte zu konstruieren. Die erforderliche Struktur für eine Vielzahl dieser Maschinen ergibt sich aus der unten folgenden Beschreibung.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNG

[0031] In der folgenden Beschreibung werden zahlreiche spezifische Einzelheiten angeführt, wie zum Beispiel das System, in dem die Kompression und Dekompression stattfindet, die Unterteilung eines visuellen Bildes in Blöcke, beispielhafte Formen von Pixelverteilungen und die Codierung von Pixelverteilungen. Für Fachleute dieses Bereiches ist jedoch offensichtlich, daß die vorliegende Erfindung ohne diese spezifischen Details umgesetzt werden kann. In anderen Fällen werden bekannte Schaltungen und Strukturen nicht im Detail beschrieben, um nicht die vorliegende Erfindung unnotwendigerweise unverständlich zu machen.
[0032] Fig. 1 zeigt ein beispielhaftes System zum Komprimieren digitaler Daten, zum Speichern komprimierter Daten und zum Regenerieren der ursprünglichen Daten gemäß der vorliegenden Erfindung. Fig. 1 zeigt eine Zentraleinheit (CPU) 14, einen Direktzugriffsspeicher (RAM) 16, ein Schreib-/Lesegerät 12, einen Nur-Lese- Speicher (ROM) 18, ein Netzwerkschnittstellengerät 21, einen Anzeigepufferspeicher 32, ein Eingabe- /Ausgabegerät 30 und eine Quelle für dekomprimierte Daten, eine Laserbildplatte 26, einen Videokassettenrekorder (VCR) 28 oder eine Kamera 29. Wie gezeigt, kommunizieren diese Element über einen Bus 20 miteinander. Die komprimierten Daten werden vom Laserbildplattenspieler 26, dem VCR 28, der Kamera 29 oder einem anderen Gerät durch Steuerungsbefehle, die vom Eingabe- /Ausgabegerät 30 ausgeführt werden, zur Verfügung gestellt. Das analoge Signal vom Laserbildplattenspieler 26, dem VCR 28 oder der Kamera 29 wird einem Analog-Digital-Wandler (A/D) 22 zur Verfügung gestellt, der das analoge Bild in eine digitale Darstellung umwandelt, die vom Farbwandler 24 in das gewünschte Farbformat (z. B. EGB 16) farbumgewandelt wird. Alterna tiv dazu kann, wenn keine Farbumwandlerschaltung vorhanden ist, die CPU 14 die Farbumwandlung als Teil der Kompressionsmethode durchführen. Das digitale Bild wird Bildrahmen für Bildrahmen über den BUS 20 zum RAM 16 geliefert.
[0033] Die CPU 14 komprimiert einen Bildrahmen, der dem RAM 16 zur Verfügung gestellt wird. Die Bildrahmen-für- Bildrahmen-Kompression der vorliegenden Erfindung gibt dem System die Möglichkeit, Bildrahmenunterscheidungsmethoden auf Blockebene anzuwenden, wodurch Vergleiche zwischen aufeinanderfolgenden Bildrahmen ausgeführt werden können, und Blöcke mit Daten, die aufeinanderfolgenden Bildrahmen gemein sind, werden mit einem kurzen Codewort repräsentiert, das eine Gemeinsamkeit anzeigt, welche weniger Bits umfaßt als das Bitmuster, das Farben zugeordnet ist, die normalerweise zur Darstellung der Daten benötigt werden. Diese Technik ermöglicht eine gute Kompression im Zusammenhang mit einer Reihe von visuellen Bildern, wie zum Beispiel einer Abfolge von Bildrahmen in einem Film, da es potenziell idente Informationen in aufeinanderfolgenden Bildrahmen gibt.
[0034] In dem in Fig. 1 dargestellten System führt die CPU 14 eine Kompressionssoftware aus, um den Bildrahmen zu komprimieren. Die CPU 14 komprimiert den im RAM 16 gespeicherten Bildrahmen und überträgt den komprimierten Bildrahmen zur Lese-/Schreibspeichervorrichtung 12 und/oder zum Netzwerkschnittstellengerät, um das komprimierte Bild letztlich durch das digitale Netzwerk 31 zu einem entfernten Objekt zu leiten. Aufeinanderfolgende Bildrahmen werden auf ähnliche Weise verarbeitet, bis die gesamte Bildrahmenabfolge komprimiert und im Speichergerät 12 gespeichert oder über das digitale Netzwerk 31 übertragen ist.
[0035] Um das ursprüngliche Bild wieder herzustellen, werden die komprimierten Bildrahmen einzeln über den BUS 20 vom Speichergerät 12 in das RAM 16 geliefert. Im Falle eines Remote-Computers werden die Bildrahmen durch das digitale Netzwerk 31 zum Netzwerkschnittstellengerät 21 geliefert und entweder vom Netzwerkschnittstellengerät 21 zum Speichergerät 12 oder zum RAM 16 oder zu beiden übertragen. Die CPU 14 decodiert die komprimierten Daten und überträgt das regenerierte Bild zum Anzeigepufferspeicher 32. Wie dargestellt ist der Anzeigepufferspeicher 32 mit einem Digital-Analog-Wandler (D/A) 34 verbunden, der wiederum mit einem Display 36 (optischen Anzeige) verbunden ist. Die CPU 14 wird mit dem Anzeigepufferspeicher 32 synchronisiert, so daß die Bildrahmen mit der richtigen Geschwindigkeit am Display 36 abgespielt werden, ohne daß dabei die Kapazität des Displaypufferspeichers 32 überschritten wird.
[0036] Das Display 36 besitzt eine typische Displayauflösung, nämlich 640 Pixel horizontal und 480 Pixel vertikal. Allgemeine physikalische Abmessungen des Displays 36 liegen im Bereich einer Diagonale von 13 bis 16 Zoll. Wie im folgenden beschrieben, arbeiten die Methode und die Vorrichtung der vorliegenden Erfindung mit Displays jeder Größe und jeder Auflösung zusammen.
[0037] Wenden wir uns nun der Verarbeitung zu, die von der CPU 14 ausgeführt wird. Fig. 2 zeigt ein Blockdiagramm des Komprimierers der vorliegenden Erfindung. Im Diagramm von Fig. 1 befindet sich der in Fig. 2 dargestellte Komprimierer innerhalb des CPU-Blocks 14. Ein digitales Signal 42 für einen im RAM 16 gespeicherten Bildrahmen wird für die Farbumwandlungsmethode 40 bereitgestellt, welche das digitale Bild 42 bei Abwesenheit der Farbumwandlungsschaltung 24 in das gewünschte Farbformat umwandelt. Der richtige Farb bitstrom 44 wird zu einer Luminanzberechnungsmethode 44 weitergeleitet, welche die Luminanzwerte der im Bildrahmen enthaltenen Pixel berechnet. Die Luminanzverteilung des Bildrahmens werden vom Luminanzverteilungsanalysierer 50 analysiert, der weiter unten genauer beschrieben wird, und die Ergebnisse der Analyse werden zu einem Codierer 54 geleitet. Der Luminanzanalysierer 50 bestimmt, welche Pixel innerhalb eines Blocks zusammengefaßt und durch die selbe Farbe dargestellt werden. Um die einzelnen Gruppen innerhalb eines Blocks mit einer einzelnen Farbe darzustellen, verarbeitet der Codierer 54 die ursprünglichen Luminanz- 46 und Farb- 48 Signale, um die Werte der Farben zu bestimmen, welche die einzelnen Gruppen repräsentieren.
[0038] Wie bei der BTC-Farbcodierung können Pixel mit unterschiedlichen Farben durch die selbe Farbe repräsentiert werden, und die "Kompression" ergibt sich dadurch, daß die Pixel mit weniger Bits codiert werden, als dies der Fall wäre, wenn bei der Codierung alle möglichen Farben wiedergegeben würden.
[0039] Fig. 3 zeigt ein typisches Bild 62, das einen Bildrahmen aus einer kontinuierlichen Abfolge enthält, der zu komprimieren ist. Das Bild 62 wird als Pixelmatrix 60 definiert, wobei jedes Pixel eine entsprechende Farbe besitzt, die in digitaler Form im RAM-Speicher 16 repräsentiert ist, wie dies oben beschrieben wurde. Beim RGB 16 Farbformat kann jedes Pixel eine von 65536 verschiedenen Farben repräsentieren.
[0040] Nun wird auf Fig. 4 Bezug genommen, wobei das Verfahren der vorliegenden Erfindung das Bild 62 in nicht überlappende, aneinander angrenzende Blöcke 64 unterteilt. In der bevorzugten Ausführungsform wird jeder der Blöcke 64 durch Abmessungen definiert, die größer sind, als sie typischerweise in herkömmlichen BPIC-Methoden verwendet werden. Wie zuvor diskutiert, führt das Unterteilen eines Bildes in größere Blöcke zu einer größeren Kompression, als wenn das Bild in relativ kleine Blöcke unterteilt würde. Es wird darauf hingewiesen, daß eine Vielzahl unterschiedlicher Blockgrößen ausgewählt werden kann. Des weiteren wird darauf hingewiesen, daß das Bild in andere geometrische Muster als Quadrate unterteilt werden kann. Um jedoch die Dekompression möglichst zu vereinfachen, sind rechteckige Regionen zu bevorzugen.
[0041] Jeder der Blöcke 64 wird getestet, um zu bestimmen, ob er durch eine einzige Farbe repräsentiert werden kann. Ein Block besitzt typischerweise eine bestimmte Farbverteilung. Wenn die meisten dieser Farben einer einzelnen Farbe sehr ähnlich sind, kann es möglich sein, den gesamten Block durch eine einzige Farbe darzustellen. Wenn der Test richtig ausgeführt wird, kann der Informationsverlust, der sich durch die Darstellung von Pixeln mit leicht unterschiedlichen Farben durch eine einzige Farbe ergibt, vom menschlichen Auge nicht wahrgenommen werden. In dieser Beschreibung wird ein Block, der durch eine einzige Farbe dargestellt werden kann, als "homogener Block" bezeichnet.
[0042] Der erste Schritt beim Testen auf Homogenität besteht darin, eine Luminanzverteilung eines jeden einzelnen Blocks 64 zu erstellen. Wenn der Block relativ groß ist (z. B. 16 Pixel · 16 Pixel oder 32 Pixel · 32 Pixel), wie dies bei dieser Erfindung möglich ist, werden die Luminanzinformationen des Blocks bevorzugterweise in einem Histogramm gesammelt, um das aufeinanderfolgende Abtasten des Blocks zur Berechnung und Erkennung seiner homogenen Pixelverteilung zu vermeiden. Da Informationen innerhalb eines Blocks meistens nur eine geringe Dispersion aufweisen, wird es durch Beibehaltung der unteren und oberen Grenzwerte des Luminanzbereichs in einem Block und in dessen Histogramm berechnungstechnisch effizienter, auf die Informationen im Histogramm zuzugreifen, als den Block neuerlich abzutasten, um nicht homogene Pixelverteilungen nacheinander aufzuteilen oder benachbarte homogene Pixelverteilungen zusammenzumischen. Diese Schritte werden im folgenden näher beschrieben.
[0043] In Fig. 5 wird nun eine Luminanzverteilung 74 eines Blocks 64, der gemäß dem Test der vorliegenden Erfindung homogen ist, dargestellt. In dem Diagramm stellt die horizontale (x) Achse 72 die Luminanz dar, und die vertikale (y) Achse 70 stellt die Anzahl der Pixel mit einem bestimmten Luminanzwert dar. Die Luminanz der Pixel wird verwendet, um Ähnlichkeiten in der Farbe zu entdecken, da der Luminanzwert eines Pixels den richtigen Anteil an Rot, Blau und Grün enthält, um die Erkennung von ähnlichen Farben zu ermöglichen. Farben, die dem menschlichen Auge ähnlicher erscheinen, besitzen Luminanzwerte, die näher beieinander liegen, als Farben, die für das menschliche Auge unähnlicher zu sein scheinen.
[0044] Wenn ein Block 64 aus Pixeln besteht, die einer Farbe ausreichend ähnlich sind und somit einem einzelnen Luminanzwert weitgehend entsprechen, repräsentiert die Methode der vorliegenden Erfindung den gesamten Block durch diese einzelne Farbe. Je kleiner die Abweichung der Kurve rund um die Durchschnittsluminanz ist, umso präziser kann das Bild durch eine einzelne Farbe dargestellt werden.
[0045] Ob eine Kurve eine ausreichend geringe Abweichung von der Durchschnittsluminanz besitzt, um durch eine einzelne Farbe dargestellt zu werden, wird in der bevorzugten Ausführungsform durch den folgenden Test bestimmt, der in der US-Patentanmeldung Nr. 07/965,580, abgetreten an IBM von Arturo Rodriguez, Mark Pietras und Steven Hancok, offenbart ist, welche im Oktober 1992 angemeldet wurde und den Titel "HYBRID VIDEO COMPRESSION SYSTEM AND METHOD CAPABLE OF SOFTWARE-ONLY DECOMPRESSION IN SELECTED MULTIMEDIA SYSTEMS" trägt. S wird als Varianz (Standardabweichung) der Luminanz des gesamten Bildes definiert, und T wird als Varianz der Luminanz der auf Homogenität getesteten Pixelverteilung definiert. Wenn eine Pixelverteilung als homogen definiert wird, wenn Q Prozent oder mehr ihrer Pixel zur selben Klasse gehören, dann wird sie als homogen bewertet, wenn sie die Gleichung T < S(Q(1-Q))1/2 erfüllt. Q wird für Verteilungen mit relativ wenigen Pixeln höher angesetzt, und für Verteilungen mit relativ vielen Pixeln niedriger angesetzt, da die Toleranz für Fehler mit zunehmender Verteilungsgröße zunimmt. Eine beispielhafte Wahl für Q für eine Verteilung mit 16 Pixeln wäre der Wert 0, 93. Eine beispielhafte Wahl für Q für eine Verteilung mit 1024 Pixeln wäre der Wert 0,85. Die Fähigkeit zur richtigen Festlegung von Q für eine bestimmte Verteilung besitzt jeder durchschnittliche Fachmann dieses Bereichs und wird daher nicht näher diskutiert.
[0046] Da Pixelverteilungen von wahrnehmungsmäßig homogenen Bildregionen asymmetrisch sind, wird sowohl die linke als auch die rechte Standardabweichung der fraglichen Pixelverteilung gemessen, und beide müssen sich beim Test als homogen erweisen.
[0047] Ein alternativer Homogenitätstest besteht darin, einen Kantenerkennungsoperator (d. h. einen 2D-Differentialoperator erster Ordnung) räumlich bei jedem Pixel im Block zu verwenden und die Größe eines solchen Operators bei jedem Pixel zu berechnen. Wenn die Größe des Kantenerkennungsoperators für jeden Pixel in der fraglichen Verteilung gering ist (d. h. unter einem bestimmten Grenzwert liegt), wird die Pixelverteilung als homogen erachtet, da es keine wesentliche räumliche Veränderung gibt.
[0048] Wenn die komplette Pixelverteilung des Blocks den Homogenitätstest besteht, wird sie durch eine einzige Farbe dargestellt. Die einzelne Farbe des Blocks wird durch Berechnung der Durchschnittsfarbe der Pixel im homogenen Block ermittelt. Die Berechnung der Durchschnittsfarbe einer Gruppe von Pixeln ist in diesem Fachbereich ausreichend bekannt und wird daher nicht diskutiert. Die Darstellung des Blocks als Bitstrom wird im folgenden diskutiert.
[0049] Ein Block kann eine so breitgestreute Farbmischung besitzen, daß es nicht möglich ist, diesen durch eine einzelne Farbe darzustellen, ohne dadurch einen unakzeptablen Verlust der Wiedergabetreue im dekomprimierten Bild zu erreichen. Dem gemäß kann ein Block mit einer derartigen Farbverteilung den oben beschriebenen Homogenitätstest nicht bestehen. Eine beispielhafte Verteilung 75 eines Blocks, der den Homogenitätstest nicht besteht, ist in Fig. 6 dargestellt.
[0050] Gemäß den Lehren der vorliegenden Erfindung wird die Verteilung 75, welche den Homogenitätstest nicht besteht, in zwei Pixelverteilungen 80 und 82 aufgeteilt, wie dies in Fig. 7 dargestellt ist. Die Verteilung 75 wird auf folgende Art und Weise aufgeteilt: es wird die Durchschnittsluminanz der Verteilung 75 von Fig. 6 berechnet, und jene Pixel, deren Luminanz größer ist als der Durchschnitt, werden in eine hohe Verteilung 82 gestellt, wie dies in Fig. 7(b) dargestellt ist, während jene Pixel, deren Luminanz kleiner oder gleich ist wie der Durchschnitt, in eine niedrige Verteilung 80 gestellt werden, wie dies in Fig. 7(a) dargestellt ist. Somit wird der Block mit der in Fig. 6 dargestellten Verteilung gemäß der Luminanzverteilung aufgeteilt, und nicht nach einem physikalischen Bereich (d. h. Unterteilung des Blocks in kleinere Blöcke), wie dies in rekursiven PBIC-Techniken des Standes der Technik der Fall ist.
[0051] Die zwei separaten Verteilungen 80 und 82, wie sie in Fig. 7(a) und 7(b) dargestellt sind, werden mit dem ausgewählten Homogenitätstest jeweils einzeln auf ihre Homogenität getestet. Wie zuvor beschrieben, wird eine fragliche Verteilung in der bevorzugten Ausführungsform dann als homogen betrachtet, wenn sowohl die linke als auch die rechte Standardluminanzabweichung kleiner ist als ein bestimmter Grenzwert. Bei dem Grenzwert handelt es sich vorzugsweise um eine Funktion der Standardabweichung der Luminanz des vollständigen Bildes oder Bildrahmens.
[0052] Wenn eine Verteilung 80 oder 82, wie sie in Fig. 7(a) und 7(b) dargestellt ist, den ausgewählten Homogenitätstest nicht besteht, wird sie wiederum in zwei Verteilungen unterteilt, wie dies in Fig. 8a, 8b, 8c und 8d dargestellt ist, indem der Durchschnittsluminanzwert der Verteilung 80 bzw. 82 berechnet wird, um die Verteilung 80 oder 82 in eine Verteilung aufzutrennen, deren Luminanzwert größer ist als der Durchschnitt, und in eine Verteilung, deren Luminanzwert kleiner oder gleich ist wie der Durchschnitt.
[0053] Die Verteilung 80, wie sie in Fig. 7(a) dargestellt ist, wird in die Verteilungen 84 und 86 aufgeteilt, wie sie in den Fig. 8a und 8b dargestellt sind, während die Verteilung 82, wie sie in Fig. 7(b) dargestellt ist, in die Verteilungen 88 und 90 aufgeteilt wird, wie sie in den Fig. 8c und 8d darge stellt sind. Der Homogenitätstest wird an jeder Verteilung 84, 86, 88 und 90 angewendet. In der bevorzugten Ausführungsform wird bei jeder Durchführung des Tests eine fragliche Verteilung dann als homogen betrachtet, wenn sowohl die linke als auch die rechte Standardluminanzabweichung kleiner ist als ein bestimmter Grenzwert. Bei dem Grenzwert handelt es sich vorzugsweise um eine Funktion der Standardabweichung der Luminanz des vollständigen Bildes oder Bildrahmens.
[0054] Die Schritte zum Testen der Homogenität und Aufteilen nicht homogener Verteilungen werden solange rekursiv angewendet, bis der Block in eine Vielzahl homogener Verteilungen aufgeteilt wurde. Anstatt jeder homogenen Verteilung eine unterschiedliche Farbe zuzuweisen, wird ein Mischtest ausgeführt, um homogene Verteilungen, die zwar durch den Aufteilungsprozeß aufgeteilt wurden, doch die eigentlich eine homogene Verteilung sein könnten, wenn sie zusammengemischt werden, zu mischen.
[0055] Die Verteilungen 86 und 88, wie sie in den Fig. 8(b) und 8(c) dargestellt werden, sind Beispiele für Verteilungen, die homogen sind, wenn sie zusammengemischt werden. Wie zuvor diskutiert, wurde die Verteilung 86 von der Verteilung 80 abgetrennt, und die Verteilung 88 wurde von der Verteilung 82 abgetrennt. Der Abtrennungsprozeß der vorliegenden Erfindung führt keine separate Überprüfung im Hinblick auf eine Homogenität in der zusammengemischten Verteilung 92 durch, wie sie in Fig. 9 dargestellt ist. Die zusammengemischte Verteilung 92 ist die Addition der Verteilungen 86 und 88. Die Verteilung 92 wird auf ihre Homogenität überprüft.
[0056] In den meisten Fällen führt der Schritt der Zusammenmischung der vorliegenden Erfindung, wie er unter Bezugnahme auf Fig. 8 bis 9 beschrieben wird, zu einer stärkeren Kompression. Durch die Zusammenmischung unterschiedlicher Pixelverteilungen und die Zuweisung einer einzelnen Farbe zur zusammengemischten Gruppe anstelle der Zuweisung zweier unterschiedlicher Farben zu unterschiedlichen Gruppen muß eine Farbe weniger im Codierformat repräsentiert werden.
[0057] Fig. 10(a) zeigt auch eine Verteilung 96, bei der das Zusammenmischen richtig erfolgt. Die Verteilung 96 wird in zwei Verteilungen aufgeteilt, von denen die eine homogen ist und die andere nicht. Wie in Fig. 10(a) dargestellt, ist die untere Hälfte 98 der Verteilung 96 homogen, während die obere Hälfte 100 der Verteilung 96 nicht homogen ist und in zwei Verteilungen 102 und 104 aufgeteilt wird, welche in Fig. 10b und 10c dargestellt sind. Die untere Hälfte 102 der oberen Hälfte 100 der Verteilung 96, wie sie in Fig. 10(b) dargestellt ist, wird mit der ursprünglichen unteren Hälfte 98 der Verteilung 96 von Fig. 10(a) zusammengemischt, um die Verteilung 106 zu bilden, die in Fig. 10(d) dargestellt ist. Die Verteilung 106 wird auf ihre Homogenität getestet. Auf ähnliche Weise wird der höhere Teil der unteren Verteilung mit der höheren Verteilung gemischt, wenn der obere Teil der ersten Verteilung homogen ist und der untere Teil der ersten Verteilung nicht homogen ist, und die zusammengemischte Verteilung wird auf ihre Homogenität getestet.
[0058] Der Block 64 wird in Verteilungen aufgeteilt, die aufgeteilten Verteilungen werden danach auf ihre Homogenität überprüft und es wird untersucht, welches Ergebnis nach einer möglichen Vermischung zu erwarten ist, bis der gesamte Block 64 in eine Reihe homogener Verteilungen aufgelöst ist. Das Flußdiagramm der Fig. 12(a) - 12(h) stellt eine mögliche Implementierung des rekursiven Vorgangs der Aufteilung von Verteilungen und des Zusammenmischens von Verteilungen dar, wie dies in den Fig. 5 bis 10 dargestellt ist, bis der gesamte Block 64 verarbeitet und codiert ist.
[0059] Nun wird auf das in den Fig. 12(a) - 12(h) dargestellte Flußdiagramm Bezug genommen, wo, wie in Schritt 200 von Block 12(a) dargestellt, ein Block Bi aus einem zu komprimierenden Bildrahmen geholt wird. Der Block B1 wird in Schritt 202 auf seine Homogenität getestet. Wenn der Block homogen ist, wird die Durchschnittsfarbe der Pixel im Block wie in Schritt 206 dargestellt berechnet, und der Block wird in Schritt 208 so codiert, wie dies weiter unten genauer beschrieben wird.
[0060] Wenn der Block nicht homogen ist, verzweigt Schritt 204 zu Schritt 210, wo eine Variable next no pix dist gleich eins gesetzt wird, und wo auch das erste Element der Zeigermatrix P der aktuellen Verteilung so gesetzt wird, daß es zu allen Pixeln in Block Bi zeigt. Der Prozeß des rekursiven Halbierens von Verteilungen führt zu einer Binärbaumstruktur, und next no pix dist repräsentiert die Anzahl der Pixelverteilungen auf der nächsten Ebene des Baums nach der aktuellen Ebene.
[0061] Wenn der Block B1 nicht homogen ist, wird er in zwei Verteilungen aufgeteilt, wie dies in Schritt 212 dargestellt ist, der die "Pixelverteilungsaufteilungsprozedur" aufruft, wie dies in Fig. 12(b) dargestellt ist. Wie in Schritt 228 von Fig. 12(b) dargestellt, akzeptiert die Prozedur als Eingabe eine Pixelverteilung, bei der es sich momentan um alle Pixel von B1 handelt. Bei Schritt 230 wird der Durchschnittswert dieser Pixel berechnet. Bei Schritt 232 wird das erste Pixel in der Verteilung, die geteilt wurde, geholt und getestet, um zu bestimmen, ob es größer ist als die Durchschnittsluminanz, wie dies in Schritt 234 dargestellt ist. Wie in Schritt 236 dargestellt, werden Pixel, deren Luminanz kleiner oder gleich ist wie der Durchschnitt, in eine Pixelverteilung auf der nächsten Ebene des Baums gestellt, wie dies vom Muster next P[next na pix dist] dargestellt ist. Im Gegensatz dazu werden, wie in Schritt 242 dargestellt, Pixel, deren Luminanz größer ist als der Durchschnitt, in eine Pixelverteilung auf der nächsten Ebene des Baums gestellt, wie dies vom Muster next P[next no pix dist + 1] dargestellt ist. Somit werden die Kinder der aufgeteilten Verteilung nach ihrem Luminanzwert gereiht, und zwar angefangen von niedriger Luminanz bis hin zu hoher Luminanz, welche von next no pix dist repräsentiert wird.
[0062] Jedes Pixel in einer Verteilung, die aufgeteilt wird, wird in eine der zwei Verteilungen gestellt, wie dies in den Schritten 234-242 von Fig. 12(b) dargestellt ist. Nachdem die Elternverteilung geteilt wurde, werden die Kinder auf ihre Homogenität überprüft, wie dies in den Schritten 244 und 254 dargestellt ist. Wie in den Schritten 246, 248, 256 und 260 dargestellt, werden homogene Kinder durch eine Matrix als homogen gekennzeichnet, die als next status bezeichnet wird und die durch next no pix dist indiziert wird, während nicht homogene Verteilungen als nicht homogen gekennzeichnet werden, wie dies in den Schritten 250 und 258 dargestellt ist. Die Prozedur wird danach beendet und kehrt zur Aufrufprozedur zurück, in diesem Fall zur PDIC-Prozedur, die in Fig. 12(a) dargestellt ist, wo der Schritt 214 ausgeführt wird.
[0063] Schritt 214 initialisiert eine Variable k, um die momentan analysierte Verteilung zu verfolgen. K wird so initialisiert, daß es zur ersten Verteilung auf der nächsten Ebene zeigt. Wie in Schritt 216 darge stellt, wird die next status-Matrix überprüft, um zu bestimmen, ob die Verteilung, auf die k zeigt, homogen ist. Wenn die Verteilung, auf die gezeigt wird, homogen ist, verzweigt Schritt 216 zu Schritt 218, wo k schrittweise hochgezählt wird, um zur nächsten Verteilung zu zeigen. Wie bei Schritt 220 dargestellt, hat die Methode, wenn k die Anzahl der Pixelverteilungen auf der nächsten Ebene überschreitet, alle Verteilungen verarbeitet, und es wird die "PDIC-Spezifikationsprozedur" aufgerufen, die in Fig. 12(g) dargestellt ist.
[0064] Wie in Fig. 12(g) dargestellt, codiert die PDIC-Spezifikationsprozedur jede homogene Verteilung mit der Anzahl der Farben, die durch die Anzahl der homogenen Verteilungen repräsentiert werden, welche in next no pix dist gespeichert ist. Wie weiter unten beschrieben, assoziiert der Schritt 314 Farben mit nnären Bitmustern, um diese Farben zu repräsentieren. Bei Schritt 316 wird eine Variable k auf Eins gesetzt, und es wird, wie in den Schritten 318-322 dargestellt, die Durchschnittsfarbe der endgültigen homogenen Verteilungen berechnet. Wie in den Schritten 324 - 330 dargestellt, werden die Pixel im Block mit dem Muster entsprechend ihrer Durchschnittsfarbe codiert. Schritt 332 codiert den Block so, wie dies weiter unten näher beschrieben wird, und die Methode wird beendet, da die Verarbeitung des aktuellen Blocks abgeschlossen wurde.
[0065] Kehren wir nun zu Schritt 220 von Fig. 12(a) zurück. Wenn es mehrere Verteilungen auf der nächsten Ebene gibt, vollzieht Schritt 220 eine Schleife zurück zu Schritt 216, wo die nächste Verteilung auf ihre Homogenität überprüft wird. Wenn die nächste Verteilung nicht homogen ist, verzweigt Schritt 216 zu Schritt 224, der die Ebenen im Baum tauscht, wie dies in Fig. 12(h) dargestellt ist. Eine nicht homogene Verteilung impliziert, daß der Baum eine nächste Ebene besitzt, die analysiert werden muß. Um die nächste Ebene des Baums zu analysieren, müssen die Matrizen, welche die aktuelle Ebene verfolgen, gleich jenen Matrizen gesetzt werden, welche die nächste Ebene des Baums verfolgen.
[0066] Wie in Fig. 12 (h) bei Schritt 334 dargestellt, wird eine Variable k auf Eins gesetzt. Die Variable k wird als Index in die nächste Verteilungsmatrix, next P, und in die Matrix, welche die Homogenität der nächsten Verteilungen verfolgt, next status, verwendet. Wie in Schritt 336 dargestellt, werden die Matrizen der aktuellen Ebene, P und status, gleich den entsprechenden Matrizen der nächsten Ebene, next P und next status, für alle Verteilungen auf der nächsten Ebene gesetzt. Wenn es mehrere Verteilungen auf der nächsten Ebene gibt, verzweigt Schritt 340 zurück zu Schritt 336. Wenn es keine weiteren Verteilungen auf der nächsten Ebene gibt, wird die Anzahl der Pixelverteilungen auf der aktuellen Ebene gleich der Anzahl der Pixelverteilungen auf der nächsten Ebene gesetzt, wie dies in Schritt 242 dargestellt ist. Die Kontrolle wird zu Schritt 226 von Fig. 12(a) zurückgegeben.
[0067] Alle Verteilungen auf der neuen aktuellen Ebene müssen im Hinblick auf Homogenität und Vermischung überprüft werden. Wie oben beschrieben, kann eine Verteilung mit einer Verteilung auf der selben Ebene des Baums oder einer Verteilung auf einer um eine Stufe höheren Ebene im Baum vermischt werden. Wie in den Fig. 12(c) - 12(f) dargestellt, führt die Prozedur "next level of tree" diese Funktion aus.
[0068] Betrachten wir nun die "next level of tree"- Prozedur (nächste Ebene des Baums), wie sie in Fig. 12(c) dargestellt ist. Bei Schritt 262 werden die Variablen k und 1, welche die Kinder der aufgeteilten Eltern verfolgen, auf 1 bzw. 2 gesetzt. Somit zeigt k anfänglich zur ersten Verteilung in der aktuellen Ebene, und 1 zeigt anfänglich zur zweiten Verteilung in der aktuellen Ebene. Die von den Schritten 236 und 238 von Fig. 12(b) vorgegebene Reihung stellt sicher, daß die Verteilungen entsprechend ihrer Luminanz gereiht werden, wobei Verteilungen mit geringeren Luminanzwerten mit niedrigeren Zahlen indiziert werden als Verteilungen mit höheren Luminanzwerten. Wie in Schritt 264 von Fig. 12(c) dargestellt, wird next no pix dist um Eins hochgezählt, um die Anzahl der Verteilungen auf der nächsten Ebene von der aktuellen Ebene aus zu verfolgen. Wie bei Schritt 266 dargestellt, werden die homogenen Verteilungen um eine Ebene im Baum tiefer gesetzt, wie dies in Schritt 268 dargestellt ist, wenn sowohl die Verteilung, auf welche k zeigt, als auch die Verteilung, die unmittelbar rechts davon steht (rechts repräsentiert die Verteilungen mit relativ höheren Luminanzwerten), homogen sind. Wie in Schritt 270 dargestellt, zeigt k nun zu jener Verteilung, auf die zuvor 1 gezeigt hat, und 1 wird hochgezählt, um zur nächsten Verteilung, die rechts davon steht, zu zeigen. Wenn 1 die Anzahl der Pixelverteilungen überschreitet, wird die Prozedur beendet, wie dies in Schritt 272 dargestellt ist, da alle Verteilungen auf der aktuellen Ebene verarbeitet wurden. Wenn es mehrere Verteilungen auf der aktuellen Ebene gibt, verzweigt Schritt 272 zurück zu Schritt 264.
[0069] Kehren wir nun zu Schritt 266 in Fig. 12(c) zurück. Wenn sich eine der aktuellen Verteilungen oder beide aktuellen Verteilungen, die analysiert werden, als nicht homogen erweisen, verzweigt Schritt 266 zu Schritt 274, wo überprüft wird, ob die Verteilung, auf welche k zeigt, homogen ist, und ob die Verteilung, auf die 1 zeigt, nicht homogen ist. Wenn dies der Fall ist, verzweigt Schritt 274 in Fig. 12(d) zu Schritt 278.
Die homogene Verteilung P[k] wird im Baum nach unten gesetzt, wie dies in Schritt 278 dargestellt ist. Bei Schritt 280 wird die nicht homogene Verteilung P[I] geteilt. Das linke Kind der nicht homogenen Verteilung P[I] wird, wie in Schritt 282 von Fig. 12(d) dargestellt, auf seine Homogenität überprüft. Wenn das linke Kind homogen ist, muß es mit P[k] vermischt werden, wie dies in Schritt 284 dargestellt ist. Dies ist analog zum Vermischen von P(low) mit P(high, low), wie dies in den Fig. 10(a) - 10(d) dargestellt ist. Wenn die vermischte Verteilung homogen ist, wird sie im Baum nach unten gesetzt, wie dies bei Schritt 288 dargestellt ist, und next no pix dist - 1 zeigt zum rechten Kind anstelle zum linken Kind, das nun zusammengemischt wird. Wenn die zusammengemischte Verteilung nicht homogen ist, wird die Variableneinstellung durchgeführt, wie sie in Schritt 288 dargestellt ist. Auf ähnliche Weise wird die Variableneinstellung, wie in Schritt 288 dargestellt, nicht durchgeführt, wenn das linke Kind nicht homogen war, wie dies in Schritt 282 dargestellt ist. Nach der Überprüfung des linken Kindes auf Homogenität und Vermischung geht die Methode zurück zu Schritt 270, wie dies in Fig. 12(c) dargestellt ist, um die Verarbeitung hin zu den Verteilungen mit den höheren Luminanzwerten im Baum fortzusetzen.
[0070] Kehren wir nun zu Schritt 266 zurück. Wenn die aktuelle Verteilung P[k] nicht homogen ist, wohl aber die rechts davon stehende Verteilung, P[I], homogen ist, verzweigt Schritt 274 zur Schritt 276, der zu Schritt 290 verzweigt, wie dies in Fig. 12(e) dargestellt ist. Die nicht homogene Verteilung P[k] wird, wie in Schritt 290 von Fig. 12(e) dargestellt, aufgeteilt. Das rechte Kind der nicht homogenen Verteilung wird, wie in Schritt 292 von Fig. 12(e) dargestellt, auf Homogenität überprüft. Wenn das rechte Kind homogen ist, wird es mit P[I] vermischt, wie dies in Schritt 294 dargestellt ist. Dies ist analog zum Vermischen von P(high) mit P(low, high), wie dies oben beschrieben wurde. Wenn die vermischte Verteilung nicht homogen ist, wird sie einfach im Baum an die Position des rechten Kindes, next no pix dist, nach unten gesetzt, wie dies in den Schritten 296 und 298 dargestellt ist. Umgekehrt wird, wenn entweder die zusammengemischte Verteilung nicht homogen war oder das rechte Kind nicht homogen war, P[I] als homogene Verteilung im Baum nach unten gesetzt, wie dies bei Schritt 300 dargestellt ist. Die Kontrolle geht zu Schritt 270 von Fig. 12 (c) zurück, wo die Verarbeitung hin zu Verteilungen mit höheren Luminanzwerten im Baum fortgesetzt wird.
[0071] Kehren wir nun zu Schritt 266 von Fig. 12(c) zurück. Die letzte Möglichkeit besteht darin, daß weder die aktuelle Verteilung P[k] noch deren Nachbar zur Rechten, P[I], homogen ist. In diesem Fall verzweigt Schritt 266 zu 274, der zu 276 verzweigt, welcher zu Schritt 302 von Fig. 12(f) verzweigt. Wie in den Schritten 302 und 304 von Fig. 12(f) dargestellt, werden sowohl die aktuelle Verteilung P[k] als auch deren Nachbar zur Rechten, P[I], geteilt. Das rechte Kind der unteren Verteilung P[k] und das linke Kinde der höheren Verteilung P[I] müssen auf ihre Homogenität überprüft werden, wie dies bei Schritt 306 dargestellt ist. Wenn beide homogen sind, werden sie zusammengemischt, und die sich daraus ergebende Mischung wird auf ihre Homogenität überprüft, wie dies bei den Schritten 308 und 310 dargestellt ist. Dies ist analog zum Vermischen von P(low, high) mit P(high, low), wie dies in den Fig. 6-8 dargestellt ist. Wenn die vermischte Verteilung homogen ist, wird der Zeiger zum rechten Kind der unteren Verteilung P[k] so eingestellt, daß er zur zusammengemischten Verteilung zeigt, und der Zeiger zum linken Kind der höheren Verteilung P[I] wird so eingestellt, daß er zum rechten Kind der höheren Ver teilung P[I] zeigt, so daß drei Verteilungen, das linke Kind der unteren Verteilung P[k], die zusammengemischte Verteilung und das rechte Kind der hohen Verteilung P[I], im Baum nach unten gesetzt werden. Diese Einstellung wird bei Schritt 312 ausgeführt. Wenn entweder das rechte Kind der unteren Verteilung P[k] oder das linke Kind der höheren Verteilung P[I] nicht homogen ist, oder wenn die Mischung nicht homogen ist, werden vier Verteilungen, das rechte und das linke Kind sowohl der niedrigen als auch der hohen Verteilung P[k] und P[I], im Baum nach unten gesetzt. Wiederum geht die Kontrolle zu Schritt 270 von Fig. 12(c), und die Verarbeitung wird zur rechten Seite des Baumes hin fortgesetzt.
[0072] Wie zuvor beschrieben, wird die gesamte aktuelle Ebene auf ihre Homogenität überprüft, und die Vermischung wird von der Prozedur "next level of tree" durchgeführt, wie dies in den Fig. 12(c)-12(f) dargestellt ist. Nachdem die Ebene verarbeitet wurde, muß sie überprüft werden, um festzustellen, ob eine neue Ebene zum Baum hinzugefügt werden muß. Wie zuvor beschrieben, wird die Überprüfung auf eine neue Ebene von den Schritten 214-220 von Fig. 12(a) durchgeführt. Wenn eine Ebene nur homogene Verteilungen enthält, verzweigt der Schritt 220 zu Schritt 314, wie dies in Fig. 12(g) dargestellt ist, und der Block wird in der Folge codiert. Somit zeigt das Flußdiagramm, wie dies in den Fig. 12(a)-(b) dargestellt ist, eine Methode zum rekursiven Auflösen eines Blocks in homogene Verteilungen bei gleichzeitigem Zusammenmischen von Verteilungen, wenn dies möglich ist.
[0073] Zusätzlich zur Zerlegung des Blocks 64 in eine Reihe homogener Verteilungen werden Bildrahmenunterscheidungstechniken angewendet, um eine optimale Kompression des Blocks 64 zu ermöglichen. Bildrahmenunterscheidungsmethoden für Nur-Software-Video-Kodizis nutzen die Redundanz zwischen Bildrahmen, ohne nach einer möglichen Bewegungsverschiebung zu suchen.
[0074] Die Bildrahmenunterscheidung durch Vergleichsmethoden ist in einer Patentanmeldung mit dem Titel "Hybrid Video Compression Method Amenable to Softwareonly Decompression in Low-end Multimedia Systems", Seriennummer 07/965,580, angemeldet im Oktober 1992, offenbart. Die Erfinder dieses Patents sind Arturo A. Rodriguez et al. Die Methode und die Vorrichtung der vorliegenden Erfindung stellen eine Verbesserung der in der Patentanmeldung Nr. 07/965,580 beschriebenen Methode dar.
[0075] In der Methode und der Vorrichtung der vorliegenden Erfindung wird eine Rahmenunterscheidung zwischen aufeinanderfolgenden Blöcken auf einer blockweisen Basis durchgeführt. Eine Bildrahmenvorunterscheidung auf einer blockweisen Basis wird durchgeführt, indem Pixel an den entsprechenden räumlichen Stellen innerhalb der Blöcke berücksichtigt werden, oder indem die Ähnlichkeiten zwischen lokalen Bildeigenschaften berücksichtigt werden, die innerhalb der entsprechenden Blöcke gemessen werden. Alternativ dazu können Bildrahmen zuerst mit der Pixelverteilungsbildcodierungsmethode (PDIC-Methode) der vorliegenden Erfindung komprimiert werden, und danach kann eine Bildrahmennachunterscheidung durch Berücksichtigung der Ähnlichkeiten zwischen der Datendarstellung, die von der PDIC-Kompressionsmethode in jedem Paar räumlich entsprechender Blöcke in allen zwei aufeinanderfolgenden Bildrahmen erzeugt wird, durchgeführt werden.
[0076] Der vom Codierer durchgeführte Ähnlichkeitstest ist typischerweise der Absolutwert des Unterschieds zwischen dem Luminanzwert der räumlich entsprechenden Pixel in den Blöcken des aktuellen Rahmens, Fi, und dem zuvor regenerierten Bildrahmen D11. Wenn der Absolutunterschied kleiner ist als ein festgelegter Grenzwert, wird davon ausgegangen, daß sich das Pixel gegenüber dem zuvor rekonstruierten Bildrahmen nicht verändert hat.
[0077] Lokale und globale Regeln werden verwendet, um einen bestimmten Grad an Verlusten beim Vergleichen räumlich entsprechender Blöcke zu erlauben. Die lokalen Regeln legen den höchsten Absolutunterschied zwischen Pixelwerten im Block fest, der als Funktion der Werte der zwei Pixel toleriert werden kann. Die globalen Regeln überwachen den insgesamt sich anhäufenden Unterschied, der in der Pixelgruppe toleriert werden kann. Alternativ dazu kann die globale Regel erweitert werden, um sichtbare Stufenbildungen zu vermeiden, indem festgelegt wird, daß alle Pixel entlang der Blockgrenze dieser lokalen Regel entsprechen müssen.
[0078] Fig. 13 ist ein Flußdiagramm der Videokompressionsmethode der vorliegenden Erfindung unter Anwendung der Bildrahmenvorunterscheidung. Bei der Bildrahmenvorunterscheidung werden Pixel an entsprechenden räumlichen Stellen innerhalb der entsprechenden Blöcke auf Ähnlichkeiten verglichen. Alternativ dazu kann eine Bildrahmenvorunterscheidung implementiert werden, indem die Ähnlichkeiten zwischen lokalen Bildeigenschaften berücksichtigt werden, die innerhalb entsprechender Blöcke gemessen werden. Wie in den Schritten 350-352 dargestellt, wird ein Bildrahmen Fi geholt und in nicht überlappende Blöcke zerlegt. Der erste Block wird bei Schritt 354 geholt, und die Bildrahmenvorunterscheidung wird bei Schritt 356 ausgeführt. Wie bei Schritt 358 in Fig. 13 dargestellt, wird ein Block mit einem codierten Block im vorhergehenden Bildrahmen gemäß dem Block im aktuellen Bildrahmen verglichen. Wenn sich der Block im aktuellen Bildrahmen nicht verändert hat, wird der Block codiert, um anzuzeigen, daß er sich gegenüber dem entsprechenden Block im vorhergehenden Bildrahmen nicht verändert hat, wie dies bei Schritt 364 in Fig. 13 dargestellt ist. Wenn sich der Block des aktuellen Rahmens jedoch verändert hat, wird die PDIC-Methode der aktuellen Erfindung angewendet, um den Block in homogene Verteilungen zu zerlegen, und die Verteilungen werden codiert, wie dies in den Blöcken 360 und 362 dargestellt ist. Die Schritte 366 und 368 stellen sicher, daß der gesamte Bildrahmen verarbeitet wird.
[0079] Fig. 14 ist ein Flußdiagramm der Videokompressionsmethode der vorliegenden Erfindung unter Anwendung der Bildrahmennachunterscheidung. Wie in den Schritten 370 und 372 von Fig. 14 dargestellt, wird ein Bildrahmen Fi geholt und in Blöcke zerlegt. Die PDIC-Prozedur wird am ersten Block im Bildrahmen ausgeführt, wie dies bei den Schritten 374 und 376 dargestellt ist. Der mit der PDIC-Methode verarbeitete Block wird dann mit dem entsprechenden Block im vorhergehenden Bildrahmen verglichen, wie dies bei Schritt 380 von Fig. 14 dargestellt ist. Wenn sich der Block nicht verändert hat, wird er codiert, um anzuzeigen, daß er sich gegenüber dem entsprechenden Block im vorhergehenden Bildrahmen nicht verändert hat, wie dies bei Schritt 384 in Fig. 14 dargestellt ist. Wenn sich der Block jedoch verändert hat, wird er als eine Reihe homogener Verteilungen codiert, wie sie von der PDIC-Methode der vorliegenden Erfindung erzeugt werden, wie dies bei Schritt 382 dargestellt ist. Die Schritte 386 und 388 stellen sicher, daß alle Blöcke im Bildrahmen verarbeitet werden.
[0080] Unabhängig davon, ob die Bildrahmenvorunterscheidung oder die Bildrahmennachunterscheidung verwendet wird, wird der Block, wenn er sich gegenüber einem entsprechenden Block im vorhergehenden Bildrahmen verändert hat, in eine Reihe homogener Verteilungen aufgelöst und dann codiert. Fig. 11 zeigt, wie der Block codiert wird. Eine feststehende Anzahl an Bits, das Farbverteilungsfeld 110, legt die maximale Anzahl der Farben fest. So zeigen zum Beispiel 3 Bits in diesem Feld ein Maximum von 8 Farben an. Das Farbverteilungsfeld 110 enthält die Anzahl der homogenen Verteilungen in einem Block, nachdem der letzte Vermischungsschritt durchgeführt wurde, bis hin zum maximal zulässigen Wert. Das nächste Feld, das Farbfeld 112, enthält die Farben der unterschiedlichen Verteilungen.
[0081] Wenn ein Block als eine Farbe codiert wird, enthält das Farbfeld 112 die Farbe, welche den Block repräsentiert. Die einzelnen Pixel des Blocks werden nicht codiert, da jedes Pixel durch ein einzige Farbe repräsentiert wird. Wie unten diskutiert, fügt der Dekomprimierer die Farbe im Farbfeld 112 in jedes Pixel im Block des rekonstruierten Bildes ein, wenn der Dekomprimierer einen Wert 1 im Farbverteilungsfeld 110 empfängt.
[0082] Wenn ein Block zwei oder mehr Farben enthält, werden einzelne Pixel des Blocks im Pixelfeld 114 mit einem Bitmuster codiert, das den Farben entspricht, die im Farbfeld 112 repräsentiert werden. Pixel, die von der ersten Farbe repräsentiert werden, werden mit einem Bitmuster codiert, das dem Wert "0" entspricht. Pixel, die von der zweiten Farbe repräsentiert werden, werden mit einem Bitmuster codiert, das dem Wert xx entspricht.
[0083] Wenn im Block nur zwei Farben enthalten sind, handelt es sich bei dem Bitmuster nach der Spezifikation der Farben um ein Binärmuster, um die zwei Farben den einzelnen Pixeln im Block zuzuordnen. Wenn der Block 3 oder 4 Farben enthält, weil drei oder vier homogene Verteilungen im Block enthalten sind, besteht das Muster aus 2-Bit-Einträgen für jedes Pixel im Block, um die Pixel ihren entsprechenden Farben zuzuordnen. Generell gilt, daß Pixel mit einer Farbe CX, 0 ≤ x ≤ N, als Zahl x in jedem Eintrag des Musters in log2(n+1) Bits codiert werden, wenn es n+1 homogene Pixelverteilungen in einem Block gibt.
[0084] Ein alternatives Codierungsschema kann eine größere Kompression ermöglichen. Wenn drei Farben im Block vorhanden sind und ein großer Teil der Pixel die Farbe 0 besitzt, kann das folgende Muster verwendet werden:
Farbe 0 Pixel = 0
Farbe 1 Pixel = 10
Farbe 2 Pixel = 11.
Die am stärksten vertretene Farbe kann als Farbe 0 gewählt werden, um die Kompression zu maximieren.
[0085] Diese Art der Codierung kann für jede beliebige Anzahl an Farben in einem Block verwendet werden. In einer Ausführungsform der vorliegenden Erfindung berechnet der Komprimierer die Anzahl der Pixel mit den verschiedenen Farben und wählt das Codierungsschema aus, das sich bei einer stärkeren Kompression ergibt. Dieser Schritt wird jedoch auf Kosten der Kompressionsgeschwindigkeit durchgeführt, da die Vorrichtung, welche die PDIC-Methode ausführt, diese zusätzlichen Berechnungen vornehmen muß.
[0086] Wie zuvor beschrieben, kann eine Differenzcodierung in Verbindung mit der PDIC-Methode der vorliegenden Erfindung verwendet werden, um die Redundanz bei visuellen Bildern zu nutzen. Im Codierungsschritt kann ein vorherbestimmter Code anzeigen, daß sich die Pixelfarbe gegenüber dem vorigen Wert nicht verändert hat. Bei einem Block mit drei Farben kann C&sub0; zum Beispiel als 00, C&sub1; als 01, C&sub2; als 10 codiert werden, und jene Pixel, deren Wert sich gegenüber dem vorhergehenden Bildrahmen nicht geändert hat, werden als 11 codiert. Wie in Fig. 11 dargestellt, kann ein Bit 116 dem gesamten Block zugeteilt werden, um anzuzeigen, daß sich der gesamte Block gegenüber dem vorherigen Block nicht verändert hat. Es wird darauf hingewiesen, daß andere Datenkompressionstechniken des Standes der Technik am Bitstrom angewendet werden können, welcher den komprimierten Block repräsentiert. Nachdem jedes Pixel im Block codiert wurde, wiederholt der Kompressor den Prozeß am nächsten Block im Bildrahmen. Dies geschieht solange, bis der letzte Block des Bildrahmens komprimiert wurde. Der komprimierte Bildrahmen wird gespeichert, und der nächste Bildrahmen wird in das RAM 16 geholt, wie dies in Fig. 1 dargestellt ist.
[0087] Der Dekomprimierer ist im wesentlichen das Gegenteil des Komprimierers. Der Dekomprimierer ist so programmiert, daß er eine bestimmte Anzahl an Bits, Farbverteilungsfeld 110, wie in Fig. 11 dargestellt, welche die Anzahl der Farben im Block repräsentieren, analysiert. Der Dekomprimierer weist die Farben Co bis Cn mit den selben Bitmustern zu wie der Komprimlerer. Wenn daher der Komprimierer Pixel, welche die Farbe C&sub0; besitzen, dem Bitmuster 0 zugeordnet hat, werden die Pixel mit dem Bitmuster 0 durch den Wert von C&sub0; ersetzt, bei dem es sich um einen Vollfarbenwert handelt, der im RGB 16-Anzeigemodus 16 Bit besitzt. Nehmen wir zum Beispiel an, Co ist die Farbe Weiß mit einem Bitmuster von 0000. Pixel mit dem Bitmuster 0 werden durch das Bitmuster 0000 ersetzt.
[0088] Das Farbverteilungsfeld 110 ermöglicht es dem Komprimierer, durch Analyse die richtige Anzahl an Farben von Co bis C" abzuleiten, und ebenso durch Analyse die richtige Anzahl an Bit pro Pixel abzuleiten, was im allgemeinen als log&sub2;(n + 1) Bits berechnet wird.
[0089] Der dekomprimierte Bitstrom kann dann am Display 36 betrachtet werden, wie dies in Fig. 1 dargestellt ist.

ZUSAMMENFASSUNG

[0090] Die vorliegende Erfindung, wie sie vorangehend beschrieben wurde, schafft Methoden und eine Vorrichtung zum Speichern einer Reihe von visuellen Bildern in komprimierter Form. Wenngleich die vorliegende Erfindung unter Bezugnahme auf verschiedene Figuren beschrieben wurde, versteht es sich doch von selbst, daß diese Figuren einzig der Veranschaulichung dienen und daher in keiner Weise Geist und Umfang der Erfindung beschränken. Wenngleich daher in den Figuren notwendigerweise Beispielverteilungen von visuellen Bildrahmen verwendet wurden, ist eine unbegrenzte Anzahl an Verteilungsformen möglich.
Die Methode und die Vorrichtung der vorliegenden Erfindung arbeitet mit jeder beliebigen Verteilung zusammen. Weiters wird betont, daß es zahlreiche unterschiedliche Codiermöglichkeiten zum Codieren der homogenen Verteilungen gibt und daß der Bildschirm in eine Vielzahl unterschiedlicher geometrischer Muster aufgeteilt werden kann, bei denen es sich nicht notwendigerweise um Blöcke handeln muß. Anstatt zur Aufteilung der Verteilung den Luminanzwert zu verwenden, können auch Chrominanzwerte oder andere Werte verwendet werden, bei denen es sich um Funktionen der Farbe handelt. Die Methode der vorliegenden Erfindung kann analoge Bilder verarbeiten und in ein analoges Berechnungsgerät implementiert werden.

Claims

1. Ein Verfahren zum Konvertieren eines Bildrahmens in einen kodierten Datenstrom, umfassend die Schritte:

Speichern des Bildrahmens in einem Speicher;

Verbinden einer Gruppe von Pixeln mit einem Bereich des besagten Bildrahmens;

Erzeugen einer ersten Farbverteilung der Gruppe von Pixeln, die dem besagten Bereich zugeordnet ist;

Testen der ersten Farbverteilung zur Bestimmung, ob die mit besagtem Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist;

wenn die mit besagtem Bereich verbundene Gruppe von Pixeln keine homogene Farbverteilung aufweist, Unterteilen der ersten Farbverteilung in zwei oder mehr zweite Farbverteilungen;

Testen von wenigstens einer der zweiten Farbverteilungen zur Bestimmung, ob eine Gruppe von Pixeln, die der besagten zweiten Farbverteilung zugeordnet ist, eine homogene Farbverteilung aufweist;

Kodieren einer Gruppe von Pixeln, der eine homogene Farbverteilung zugeordnet ist.

2. Das Verfahren von Anspruch 1, worin die erste Farbverteilung eine Luminanzverteilung der Gruppe von Pixeln enthält, die mit dem besagten Bereich verbunden ist.

3. Das Verfahren von Anspruch 1, worin die mit besagtem Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist, enthält weiter den Schritt der Verbindung des besagten Bereiches mit einer Bereichsfarbe und Kodieren der mit besagtem Bereich verbundenen Gruppe von Pixeln als besagte Bereichsfarbe.

4. Das Verfahren von Anspruch 3, worin wenigstens eine der Gruppen von Pixeln, die mit der besagten getesteten zweiten Farbverteilung verbunden ist, keine homogene Farbverteilung aufweist, enthält weiter die Schritte:

Unterteilen einer getesteten zweiten Farbverteilung, die mit einer Gruppe von Pixeln verbunden ist, die keine homogene Farbverteilung aufweist, in zwei oder mehr dritte Farbverteilungen;

Testen von wenigstens einer der dritten Farbverteilungen zur Bestimmung, ob eine Gruppe von Pixeln, die mit der besagten dritten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist;

wenn die mit der besagten getesteten dritten Farbverteilung verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist, Verbinden der getesteten dritten Farbverteilung mit einer dritten Verteilungsfarbe und Kodieren der mit der besagten getesteten dritten Farbverteilung verbundenen Gruppe von Pixeln als besagte dritte Verteilungsfarbe.

5. Das Verfahren von Anspruch 4, worin jede der besagten zweiten Farbverteilungen getestet wird zur Bestimmung, ob eine Gruppe von mit einer der getesteten zweiten Farbverteilungen verbundenen Pixeln homogen ist.

6. Das Verfahren von Anspruch 5 enthält weiter die Schritte:

Testen jeder der besagten dritten Farbverteilungen zur Bestimmung, ob eine mit den getesteten dritten Farbverteilungen verbundene Gruppe von Pixeln homogen ist;

wenn wenigstens eine der besagten Gruppen von Pixeln, die mit den getesteten dritten Farbverteilungen verbunden ist, keine homogene Farbverteilung aufweist, Unterteilen jeder der dritten Farbverteilungen in zwei oder mehr vierte Farbverteilungen;

Testen jeder der besagten vierten Farbverteilungen zur Bestimmung, ob eine mit den getesteten vierten Farbverteilungen verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist;

wenn wenigstens eine der besagten Gruppen von Pixeln, die mit der getesteten vierten Farbverteilung verbunden ist, keine homogene Farbverteilung aufweist, rekursives Unterteilen der vierten Farbverteilungen und Testen jeder resultierenden Farbverteilung bis jede getestete endgültige Farbverteilung mit einer Gruppe von Pixeln verbunden ist, die eine homogene Farbverteilung aufweist;

Verbinden jeder endgültigen Farbverteilung mit einer endgültigen Verteilungsfarbe und Kodieren einer Gruppe von Pixeln, die mit der besagten endgültigen Farbverteilung verbunden ist, als eine Farbe.

7. Das Verfahren von Anspruch 3, worin der Schritt der Unterteilung der besagten ersten Farbverteilung die Schritte enthält:

Berechnen der durchschnittlichen Luminanz der besagten ersten Farbverteilung;

Verbinden einer Gruppe von Pixeln, die eine größere Luminanz aufweist als die durchschnittliche Luminanz, mit einer hohen zweiten Farbverteilung;

Verbinden einer Gruppe von Pixeln, die eine kleinere Luminanz aufweist als die durchschnittliche Luminanz, mit einer niedrigen zweiten Farbverteilung.

8. Ein Verfahren zum Konvertieren eines Bildrahmens in einen kodierten Datenstrom, umfassend die Schritte:

Speichern des Bildrahmens in einem Speicher;

Verbinden einer Gruppe von Pixeln mit einem Bereich des besagten Bildrahmens;

Testen der ersten Farbverteilung zur Bestimmung, ob die dem besagten Bereich zugeordnete Gruppe von Pixeln eine homogene Farbverteilung aufweist;

wenn die dem besagten Bereich zugeordnete Gruppe von Pixeln eine homogene Farbverteilung aufweist, Verbinden des besagten Bereiches mit einer Bereichsfarbe und

Kodieren der dem besagten Bereich zugeordneten Gruppe von Pixeln als besagte Bereichsfarbe;

wenn die dem besagten Bereich zugeordnete Gruppe von Pixeln keine homogene Farbverteilung aufweist, Unterteilen der ersten Farbverteilung in zwei oder mehr zweite Farbverteilungen;

wenn wenigstens eine der Gruppen von Pixeln, die mit den getesteten dritten Farbverteilungen verbunden ist, eine homogene Farbverteilung aufweist und wenn wenigstens eine der Gruppen von Pixeln, die mit den getesteten zweiten Farbverteilungen verbunden ist, eine homogene Farbverteilung aufweist, Zusammenführen der getesteten dritten Farbverteilung, die mit einer Gruppe von Pixeln mit einer homogenen Farbverteilung verbunden ist, mit der getesteten zweiten Farbverteilung zur Bildung einer ersten gemischten Farbverteilung;

Testen der ersten gemischten Farbverteilung zur Bestimmung, ob besagte Gruppe von Pixeln, die mit der ersten gemischten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist;

wenn die mit der ersten gemischten Farbverteilung verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist, Verbinden der ersten gemischten Farbverteilung mit einer ersten gemischten Farbverteilungsfarbe und Kodieren einer mit der ersten gemischten Farbverteilung verbundene Gruppe von Pixeln als besagte erste gemischte Verteilungsfarbe;

wenn keine der Gruppen von Pixeln, die mit der getesteten zweiten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Testen einer unterschiedlichen dritten Farbverteilung zur Bestimmung, ob eine Gruppe von Pixeln, die mit der getesteten unterschiedlichen dritten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist;

wenn eine Gruppe von Pixeln, die mit der unterschiedlichen dritten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Zusammenführen der getesteten dritten Farbverteilung mit der besagten getesteten unterschiedlichen dritten Farbverteilung zur Bildung einer zweiten gemischten Farbverteilung;

Testen der zweiten gemischten Farbverteilung zur Bestimmung, ob die mit der zweiten gemischten Farbverteilung verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist;

wenn besagte Gruppe von Pixeln, die mit der zweiten gemischten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Verbinden der zweiten gemischten Farbverteilung mit einer zweiten gemischten Verteilungsfarbe und Kodieren einer Gruppe von Pixeln, die mit der zweiten gemischten Farbverteilung verbunden ist, als besagte zweite gemischte Verteilungsfarbe;

Kodieren einer Gruppe von Pixeln, die mit einer homogenen Farbverteilung verbunden ist.

9. Das Verfahren der Ansprüche 1 oder 3, worin der Schritt des Testens einer Farbverteilung auf Homogenität die Schritte umfaßt:

Bestimmen einer Standardabweichung T der zu testenden Farbverteilung;

Bestimmen einer Standardabweichung S einer Farbverteilung, von der die zu testende Farbverteilung abgeleitet wurde; und Definieren Q als Prozentsatz, so daß die zu testende Farbverteilung als homogen gilt, wenn T< B (Q(1-Q)1/2.

10. Das Verfahren von Anspruch 3, worin der Schritt der Verbindung der ersten Farbverteilung mit einer ersten Verteilungsfarbe die Schritte der Erzeugung einer Durchschnittsfarbe der ersten Farbverteilungen und Verbinden der Durchschnittsfarbe mit der ersten Farbverteilung enthält.

11. Das Verfahren von Anspruch 1, worin der Schritt des Kodierens der Gruppe von Pixeln, die dem besagten Bereich zugewiesen ist, umfaßt die Schritte:

Zuweisen eines Nummernfeldes zur Anzeige, daß die mit dem besagten Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist;

Zuweisen eines Farbfeldes zur Darstellung der besagten Bereichsfarbe.

12. Das Verfahren von Anspruch 3, worin der Schritt des Kodierens der besagten Gruppe von Pixeln, die mit der zweiten Farbverteilung verbunden ist, die Schritte umfaßt:

Zuweisen eines Nummernfeldes zur Anzeige der Anzahl von zu kodierenden Farbverteilungen;

Zuweisen eines Farbfeldes zur Darstellung einer zu kodierenden Verteilungsfarbe und Verbinden eines Bitmusters mit der zu kodierenden Verteilungsfarbe:

Kodieren eines Pixels in besagtem Bereich mit einem der besagten Bitmuster, das mit einer Verteilungsfarbe verbunden ist, so daß das mit einer Farbverteilung verbundene Pixel mit einem Bitmuster kodiert wird, das der Farbe entspricht, die mit der dem Pixel zugeordneten Farbverteilung verbunden ist.

13. Das Verfahren der Ansprüche 1 oder 3, worin wenigstens einer der besagten Bereiche ein Quadrat ist.

14. Das Verfahren der Ansprüche 11 oder 12 enthält weiter den Schritt der Kodierung des besagten Datenstroms, dieser Schritt enthält die Schritte:

Prüfen des besagten Nummernfeldes;

wenn das Nummernfeld einen homogenen Bereich anzeigt, Ersetzen eines jeden Pixels in dem homogenen Bereich durch ein Bitmuster in dem besagten Farbfeld;

wenn das Nummernfeld keinen homogenen Bereich anzeigt, Verbinden einer jeden Farbe in besagtem Farbfeld mit einem Bitmuster;

Zergliedern der kodierten Pixel in separate Teile;

Ersetzen eines jeden der separaten Teile durch eine Farbe, die dem betreffenden Teil zugeordnet ist.

15. Eine Einrichtung zum Konvertieren eines Bildrahmens in einen kodierten Datenstrom enthält:

Speichermittel zum Speichern des Bildrahmens in einem Speicher;

erste Verbindungsmittel zum Verbinden einer Gruppe von Pixeln mit einem Bereich des besagten Bildrahmens;

erste Erzeugungsmittel zum Erzeugen einer ersten Farbverteilung der Gruppe von Pixeln, die dem besagten Bereich zugeordnet ist;

erste Testmittel zum Testen der ersten Farbverteilung zur Bestimmung, ob die dem besagten Bereich zugeordnete Gruppe von Pixeln eine homogene Farbverteilung aufweist;

erste Unterteilungsmittel zum Unterteilen der ersten Farbverteilung in zwei oder mehr zweite Farbverteilungen, die ersten Unterteilungsmittel werden wirksam, wenn die dem besagten Bereich zugeordnete Gruppe von Pixeln keine homogene Farbverteilung aufweist;

erste Testmittel zum Testen von wenigstens einer der zweiten Farbverteilungen zur Bestimmung, ob eine Gruppe von Pixeln, die der besagten zweiten Farbverteilung zugeordnet ist, eine homogene Farbverteilung aufweist;

Kodiermittel zum Kodieren einer Gruppe von Pixeln, der eine homogene Farbverteilung zugeordnet ist.

16. Die Einrichtung von Anspruch 15, worin besagte erste Farbverteilung eine Luminanzverteilung der besagte Gruppe von Pixels enthält, die mit dem besagten Bereich verbunden ist.

17. Die Einrichtung von Anspruch 15 enthält weiter erste Verteilungs-Verbindungsmittel zur Verbindung des besagten Bereiches mit einer Bereichsfarbe und zweite Kodiermittel zum Kodieren der mit dem besagten Bereich verbundenen Gruppe von Pixeln als Bereichsfarbe, die ersten Verteilungs-Verbindungsmittel und die zweiten Kodiermittel werden wirksam, wenn die mit dem besagtem Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist.

18. Die Einrichtung von Anspruch 15 enthält weiter zweite Verbindungsmittel zur Verbindung der besagten zweiten Farbverteilung mit einer zweiten Verteilungsfarbe.

19. Die Einrichtung von Anspruch 17, worin die Unterteilungsmittel weiter enthalten:

Berechnungsmittel zum Berechnen der durchschnittlichen Luminanz einer zu unterteilenden Farbverteilung;

dritte Verbindungsmittel zum Verbinden einer Gruppe von Pixeln, die eine größere Luminanz aufweist als die durchschnittliche Luminanz, zu einer hohen zweiten Farbverteilung;

vierte Verbindungsmittel zum Verbinden einer Gruppe von Pixeln, die eine kleinere Luminanz aufweist als die durchschnittliche Luminanz, zu einer niedrigen zweiten Farbverteilung.

20. Die Einrichtung von Anspruch 17 enthält weiter Mischmittel zum Mischen homogener Verteilungen.

21. Die Einrichtung von Anspruch 15 oder 17, worin die besagten ersten und zweiten Testmittel weiter enthalten:

erste Bestimmungsmittel zum Bestimmen einer Standardabweichung T einer zu testenden Farbverteilung;

zweite Bestimmungsmittel zum Bestimmen einer Standardabweichung 5 einer Farbverteilung, von der die zu testende Farbverteilung abgeleitet wurde; und

Definitionsmittel zum Definieren des Prozentsatzes Q, so daß die zu testende Farbverteilung als homogen gilt, wenn T< B (Q(1-Q))1/2.

22. Die Einrichtung von Anspruch 17, worin die zweiten Verbindungsmittel Mittel zum Erzeugen einer Durchschnittsfarbe enthalten, die eine Durchschnittsfarbe einer Farbverteilung erzeugt.

23. Die Einrichtung von Anspruch 17, worin die zweiten Kodiermittel weiter enthalten:

erste Zuweisungsmittel zum Zuweisen eines Nummernfeldes zur Darstellung einer Anzahl von homogenen Farbverteilungen in besagtem Bereich;

zweite Zuweisungsmittel zum Zuweisen eines Farbfeldes zur Darstellung einer endgültigen Farbe oder einer Vielzahl von endgültigen Farben, die zu kodieren sind.

24. Die Einrichtung von Anspruch 22, worin die zweiten Kodiermittel weiter enthalten:

Bitmuster-Verbindungsmittel zur Verbindung jeder der Anzahl von endgültigen Farben mit einem Bitmuster;

Pixel-Kodiermittel zum Kodieren eines Pixels in besagtem Bereich mit einem der besagten Bitmuster, das mit einer Farbe verbunden ist, so daß das mit einer Farbverteilung verbundene Pixel mit einem Bitmuster kodiert wird, das der Farbe entspricht, die mit der dem Pixel zugeordneten Farbverteilung verbunden ist.

25. Die Einrichtung von Anspruch 17, worin wenigstens einer der besagten Bereiche ein Quadrat ist.

26. Die Einrichtung von Anspruch 23 enthält weiter einen Dekomprimierer, der Prüfungsmittel aufweist zum Prüfen des besagten Nummernfeldes; und

Ersetzungsmittel aufweist zum Ersetzen eines jeden Pixels in dem homogenen Bereich durch ein Bitmuster in dem besagten Farbfeld.

27. Eine Einrichtung zum Konvertieren eines Bildrahmens in einen kodierten Datenstrom umfaßt:

Speichermittel zum Speichern eines Bildrahmens in einem Speicher;

erste Verbindungsmittel zum Verbindung einer Gruppe von Pixeln mit einem Bereich des besagten Bildrahmens;

erste Testmittel zum Testen der ersten Farbverteilung zur Bestimmung, ob die mit dem besagten Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist;

zweite Verbindungsmittel, die wirksam sind, wenn die mit dem besagten Bereich verbundene Gruppe von Pixeln eine homogene Farbverteilung aufweist, zur Verbindung des besagten Bereiches mit einer Bereichsfarbe und zum Kodieren der dem besagten Bereich zugeordneten Gruppe von Pixeln als besagte Bereichsfarbe;

Mittel, die wirksam sind, wenn die mit dem besagten Bereich verbundene Gruppe von Pixeln keine homogene Farbverteilung aufweist, zum Unterteilen der ersten Farbverteilung in zwei oder mehr zweite Farbverteilungen; und

Unterteilungsmittel zum Unterteilen einer getesteten zweiten Farbverteilung, die mit einer Gruppe von Pixeln verbunden ist, die keine homogene Farbverteilung aufweist, in zwei oder mehr dritte Farbverteilungen;

zweite Testmittel zum Testen von wenigstens einer der dritten Farbverteilungen zur Bestimmung, ob eine Gruppe von Pixeln, die mit der besagten dritten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist;

Mischmittel, die wirksam sind, wenn wenigstens eine der Gruppen von Pixeln, die mit den getesteten dritten Farbverteilungen verbunden ist, eine homogene Farbverteilung aufweist, die Mischmittel führen die folgenden Operationen aus:

wenn wenigstens eine der Gruppen von Pixeln, die mit den getesteten zweiten Farbverteilungen verbunden ist, eine homogene Farbverteilung aufweist, Zusammenführen der getesteten dritten Farbverteilung, die einer Gruppe von Pixeln mit einer homogenen Farbverteilung zugeordnet ist, mit der getesteten zweiten Farbverteilung zur Bildung einer ersten gemischten Farbverteilung;

wenn die Gruppe von Pixeln, die mit der ersten gemischten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Verbinden der ersten gemischten Farbverteilung mit einer ersten gemischten Farbverteilungsfarbe und Kodieren einer Gruppe von Pixeln, die mit der ersten gemischten Farbverteilung verbunden ist, als besagte erste gemischte Verteilungsfarbe;

wenn eine Gruppe von Pixeln, die mit der unterschiedlichen dritten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Zusammenführen der getesteten dritten Farbverteilung mit der getesteten unterschiedlichen dritten Farbverteilung zur Bildung einer zweiten gemischten Farbverteilung;

Testen der zweiten gemischten Farbverteilung zur Bestimmung, ob eine Gruppe von Pixeln, die mit der zweiten gemischten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist;

wenn die Gruppe von Pixeln, die mit der zweiten gemischten Farbverteilung verbunden ist, eine homogene Farbverteilung aufweist, Verbinden der zweiten gemischten Farbverteilung mit einer zweiten gemischten Verteilungsfarbe und Kodieren einer Gruppe von Pixeln, die mit der zweiten gemischten Farbverteilung verbunden ist, als besagte zweite gemischte Verteilungsfarbe;

Kodiermittel zum Kodieren einer Gruppe von Pixeln, die mit einer homogenen Farbverteilung verbunden ist: