DE69810070T2 - Datencodierungssystem - Google Patents
DatencodierungssystemInfo
- Publication number
- DE69810070T2 DE69810070T2 DE69810070T DE69810070T DE69810070T2 DE 69810070 T2 DE69810070 T2 DE 69810070T2 DE 69810070 T DE69810070 T DE 69810070T DE 69810070 T DE69810070 T DE 69810070T DE 69810070 T2 DE69810070 T2 DE 69810070T2
- Authority
- DE
- Germany
- Prior art keywords
- data
- digits
- pixels
- values
- groupings
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
- 238000000034 method Methods 0.000 claims description 47
- 238000003491 array Methods 0.000 claims description 33
- 238000013144 data compression Methods 0.000 claims description 30
- 238000012545 processing Methods 0.000 claims description 27
- 238000009826 distribution Methods 0.000 claims description 24
- 238000004458 analytical method Methods 0.000 claims description 18
- 238000006243 chemical reaction Methods 0.000 claims description 13
- 230000008569 process Effects 0.000 claims description 4
- 238000005192 partition Methods 0.000 claims description 3
- 238000012937 correction Methods 0.000 claims description 2
- 230000001172 regenerating effect Effects 0.000 claims 1
- 230000006870 function Effects 0.000 description 117
- 230000000875 corresponding effect Effects 0.000 description 55
- 230000005540 biological transmission Effects 0.000 description 33
- 230000008901 benefit Effects 0.000 description 30
- 239000013598 vector Substances 0.000 description 29
- 238000000605 extraction Methods 0.000 description 19
- 239000003086 colorant Substances 0.000 description 15
- 230000006854 communication Effects 0.000 description 15
- 238000004891 communication Methods 0.000 description 15
- 238000013507 mapping Methods 0.000 description 12
- 230000002596 correlated effect Effects 0.000 description 9
- 239000002131 composite material Substances 0.000 description 5
- 241000607479 Yersinia pestis Species 0.000 description 4
- 238000007906 compression Methods 0.000 description 4
- 230000006835 compression Effects 0.000 description 4
- 230000005670 electromagnetic radiation Effects 0.000 description 3
- 238000012905 input function Methods 0.000 description 3
- 238000005070 sampling Methods 0.000 description 3
- 238000013459 approach Methods 0.000 description 2
- 230000002457 bidirectional effect Effects 0.000 description 2
- 230000000903 blocking effect Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000005562 fading Methods 0.000 description 2
- 238000003780 insertion Methods 0.000 description 2
- 230000037431 insertion Effects 0.000 description 2
- 239000011159 matrix material Substances 0.000 description 2
- 238000012544 monitoring process Methods 0.000 description 2
- 230000005855 radiation Effects 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 238000000638 solvent extraction Methods 0.000 description 2
- 101100311330 Schizosaccharomyces pombe (strain 972 / ATCC 24843) uap56 gene Proteins 0.000 description 1
- 230000007175 bidirectional communication Effects 0.000 description 1
- 230000015556 catabolic process Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000006731 degradation reaction Methods 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 230000008030 elimination Effects 0.000 description 1
- 238000003379 elimination reaction Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000000835 fiber Substances 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000007639 printing Methods 0.000 description 1
- 238000013139 quantization Methods 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 239000011435 rock Substances 0.000 description 1
- 238000005549 size reduction Methods 0.000 description 1
- 101150018444 sub2 gene Proteins 0.000 description 1
- 230000009897 systematic effect Effects 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N1/00—Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
- H04N1/41—Bandwidth or redundancy reduction
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Image Processing (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
Description
- Diese Erfindung bezieht sich auf ein Datencodierungssystem und insbesondere, aber nicht ausschließlich auf ein Codierungssystem zum Codieren, Übertragen und Decodieren von Bilddaten.
- Codierungssysteme zum Codieren, Übertragen und Decodieren von Bilddaten, z. B. Faxsysteme, sind im Stand der Technik wohlbekannt. Diese Systeme umfassen Sender/Empfänger, die über einen oder mehrere serielle Kommunikationskanäle, z. B. eine Telephonverbindung, miteinander verbindbar sind. In einem dieser Systeme wird ein von einem ersten Sender/Empfänger zu übertragendes Bild von diesem als ein Strom von Informationen über einen oder mehrere Kanäle zu einem zweiten Sender/Empfänger befördert, wo das Bild empfangen und dann reproduziert wird. Das Bild wird im ersten Sender/Empfänger in eine Folge paralleler Bildstreifen partitioniert, die abgetastet werden, um eine Folge von Datenpaketen zu schaffen, in denen jeder Streifen durch ein entsprechendes Datenpaket dargestellt ist. Zwischen jeweils zwei dieser Pakete werden Zeilenende- Daten (EOL-Daten) eingefügt, um sie zu unterbrechen und dadurch zusammengesetzte codierte Daten zu schaffen, die für die Übertragung geeignet sind. Die Pakete sind nicht jedes einzeln durch einen Adressenverweis identifizierbar, der ihre entsprechende Streifenposition innerhalb des Bildes definiert, sondern sie sind in einer Folge bezüglich zueinander angeordnet, in der die Streifen aneinander grenzen können, um das Bild zu bilden. In der Folge werden die Pakete als durch ihre Position darin relativ adressiert bezeichnet.
- Diese Systeme leiden an dem Problem, daß die relativ adressierten Daten ihre räumliche Genauigkeit verlieren, falls im Ergebnis einer Datenverfälschung die EOL-Daten verloren worden sind. Überdies können sich außerdem Synchronisationsprobleme ergeben, wenn die EOL-Daten nach verfälschten Daten nicht zuverlässig erkannt werden. Die Datenverfälschung kann ein empfangenes Bild unklar wiedergeben.
- Die Wahrscheinlichkeit, daß eine Datenverfälschung in den obenbeschriebenen Systemen auftritt, nimmt zu, wenn die Übertragungsdauer zunimmt. Ein durch Fax übertragenes Bild mit Standard- CCITT-Auflösung (CCITT - internationaler beratender Ausschuß für den Telegraphen- und Fernsprechdienst) kann z. B. die Übertragung von Daten mit sich bringen, die etwa zwei Millionen Bits von Informationen darstellen. Dies ist in einem Buch "FAX: Facsimile Technology and Applications Handbook", ISBN 0 89006 495 4, McConnell, Bodson und Schaphorst, 1992, beschrieben. Falls diese Daten in unkomprimierter Form über einen Kommunikationskanal mit einer Rate von 2400 Bits pro Sekunde (Bit/s) übertragen werden, wird die Dauer der Übertragung etwa vierzehn Minuten betragen. Es ist wahrscheinlich, daß in Systemen, in denen über kürzere Zeitskalen als diese auf Schwund- und Interferenzphänomene gestoßen wird, die Datenverfälschung während eines derartigen Intervalls auftritt.
- Eine eingeschränkte Kommunikationsbandbreite, die die Übertragungsraten für Informationen auf etwa 2400 Bit/s einschränkt, ist für Hochfrequenz-Funksysteme (HF-Funksysteme) besonders charakteristisch, die arbeiten, indem sie elektromagnetische Strahlung in einem Frequenzbereich von 3 bis 30 MHz senden und empfangen. Derartige Funksysteme neigen zu Übertragungsproblemen, wie z. B. Interferenz, Signalschwund und Mehrwegeeffekte, die dazu führen können, daß Fehler in die über sie beförderten Informationen eingefügt werden; dies ist besonders relevant, wenn die Übertragungsdauern lang sind. Ungeachtet dieser Probleme schaffen die HF-Funksy steme einen wichtigen Vorteil gegenüber der Leitungs- und Sichtkommunikation, wobei sie gegenwärtig z. B. in maritimen Anwendungen eingesetzt werden. Die Techniken, um mit den Übertragungsproblemen zurechtgekommen, sind für derartige Systeme ganz wichtig.
- Die aktuellen Komprimierungstechniken, um die Probleme der Datenverfälschung zu verringern, wenn Datenpakete über zu Fehlern neigenden Kanälen übertragen werden, stützen sich auf die Verwendung von Komprimierungsalgorithmen, um die Redundanz in den Daten zu verringern und dadurch die Dauer der Datenübertragung zu verringern. Die Robustheit der dadurch erzeugten komprimierten Daten gegenüber Übertragungsfehlern wird weiter vergrößert, indem zu ihnen Fehlersteuerungs-Codedaten hinzugefügt werden. Derartige Techniken verringern die Bildübertragungszeit, obwohl die Einbeziehung der Steuercodedaten dazu neigt, die Vorteile der Verringerung der Datengröße, die sich aus der Datenkomprimierung ergeben, auszugleichen. Obwohl derartige Techniken für die Beseitigung zufälliger Fehler effektiv sind, die während der Datenübertragung auftreten, ergibt sich ein Problem, wenn die Fehler häufiger auftreten, als sie durch die Steuercodes kompensiert werden können. Dies führt wegen der verringerten Redundanz der komprimierten Daten zu einem umfassenden Schaden an den komprimierten Daten. Diese übermäßigen Fehler geben ein zum empfangenden Sender/Empfänger befördertes Bild möglicherweise unklar und bestenfalls fehlerhaft wieder.
- Die obenbeschriebenen Fehlersteuerungscodes enthalten Vorwärtsfehlerkorrektur-Codes (FEC-Codes), die Paritätsbits enthalten. Von einem zweiten Sender/Empfänger, der die Daten empfängt, werden als Antwort Codes für die automatische Wiederholanforderung (ARQ- Codes) an einen ersten Sender/Empfänger gesendet, der die Daten überträgt, wenn die Daten während der Übertragung verfälscht werden, um den ersten Sender/Empfänger anzuweisen, die Daten erneut zu übertragen. In dem Fall der Faxsysteme des Standes der Technik rufen die ARQ-Codes, die zurückgeschickt werden, wenn Übertragungsfehler aufgetreten sind, die erneute Übertragung eines ganzen Bildes auf, auf das sich die ARQ-Codes beziehen. Die erneute Übertragung von Teilen des Bildes ist in diesen Systemen des Standes der Technik nicht möglich, weil sie keine Einrichtungen besitzen, um isoliert erneut übertragene Teile des Bildes miteinander in Verbindung zu bringen.
- In einer modifizierten Huffman-Codierungstechnik, wie sie z. B. für das CCITT-Gruppe-3-Standardfax verwendet wird, wird jedes Datenpaket in eine Folge von Codewörtern mit variabler Länge codiert, die durch einen robusten EOL-Code getrennt sind. Dies ist in einer Veröffentlichung "International digital facsimile coding standards", Hunter und Robinson, Proc. IEEE-68, S. 854-867, beschrieben. Obwohl diese Huffman-Technik, die die relative Adressierung verwendet, bei der Begrenzung der Fehlerausbreitung von einem Paket zu einem anderen und der Schaffung der Datenkomprimierung effektiv ist, ist sie häufig nicht in der Lage, fehlerfrei beförderte Bilder zu schaffen, wenn während der Bildübertragung auf Bitfehlerraten (BERs) von 2% oder mehr gestoßen wird.
- Als eine Alternative zu der obenbeschriebenen Huffman-Technik umfast eine SEA-RL-Codierungstechnik (Lauflängen-Codierungstechnik mit sequentieller Kantenadressierung):
- (i) die Darstellung eines Bildes als ein zweifarbiges Bild (Schwarzweißbild) in einer zweidimensionalen Anordnung aus Bildpunktelementen;
- (ii) die Partitionierung der Anordnung in Streifen mit der Breite eines einzelnen Bildpunktelementes und das Codieren jedes Streifens hinsichtlich der Farbübergänge und Lauflängen bezüglich eines Referenzendes des Streifens, um ein entsprechendes Datenpaket zu schaffen; und
- (iii) das Zusammenbauen der Pakete in eine Folge von Daten, in der jedes Paket von seinem folgenden Paket durch EOL-Codedaten getrennt ist.
- Die SEA-RL-Technik wurde für die Verbesserung der Übertragungszuverlässigkeit entwickelt, wenn Dokumente mit niedriger Auflösung unter Verwendung einer Ultrakurzwellen-Funkübertragungsvorrichtung (VHF-Funkübertragungsvorrichtung) übertragen werden, die beschaffen ist, um modulierte elektromagnetische Strahlung in einem Frequenzbereich von 30 MHz bis 300 MHz zu senden und zu empfangen. In der Technik entsprechen die Lauflängen den Größen der Gruppen aufeinanderfolgender Bildpunktelemente des Bildes mit ähnlicher Farbe, die in den Streifen vorhanden sind. Die Datenpakete werden in der Folge der Daten nicht einzeln adressiert, weil die relative Adressierung verwendet wird, in der die Datenpakete in der Folge in einer Reihenfolge angeordnet sind, in der ihre entsprechenden Bänder aneinandergrenzend angeordnet werden können, um das Bild zu bilden. Eine Beschreibung der SEA-RL-Technik ist in einer Veröffentlichung "Joint source-channel coding for raster document transmission over mobile radio" von Wyrwas und Farrell, IEE Procedings, Bd. 136, Teil I, Nr. 6, S. 375-380, Dezember 1989, bereitgestellt. Die SEA-RL-Technik unterscheidet sich von den ande ren obenbeschriebenen Codierungstechniken insofern, als die absolute anstatt die relative Adressierung der Gruppen der Bildpunkte des Bildes innerhalb jedes Datenpakets verwendet wird. Außerdem ist diese Technik auf die Übertragung nur von Zweiton-Schwarzweißbildern eingeschränkt.
- In der SEA-RL-Technik sind die EOL-Codedaten, die die Datenpakete in einer Folge unterbrechen, für Übertragungsfehler empfindlich; die Verfälschung der EOL-Daten kann zu einem Verlust von einzelnen Paketen oder möglicherweise den Verlust von zwei aufeinanderfolgenden Paketen führen. Zurückzuführen auf ihre Wichtigkeit sind die EOL-Codedaten deshalb in der Folge zweifach enthalten. In einer Situation, in der eines oder mehrere der Pakete in der Folge verfälscht werden, ist die erneute Übertragung der Bilddaten erforderlich, weil für die Pakete die relative Adressierung verwendet wird. Die SEA-RL-Technik basiert in Übereinstimmung mit den obenbeschriebenen alternativen Techniken auf der Codierung eines Bildes als eine Folge von Streifen, um Datenpakete für die Übertragung zu erzeugen, wobei sie deshalb stark auf die Robustheit der EOL-Codes angewiesen ist, die die Pakete unterbrechen, um mit den Übertragungsfehlern zurechtzukommen. Es ist in der Praxis bewiesen worden, daß das Vertrauen der SEA-RL-Technik auf ihre EOL-Symbole ihre Hauptschwäche ist, insbesondere wenn Bündel aus durch Interferenz verfälschten SEA-RL-codierten Daten und EOL-Codes darin enthalten sind.
- Im allgemeinen stützen sich die obenbeschriebenen Zugänge des Standes der Technik, um Bilder zu codieren, auf:
- (i) die Partitionierung eines zu codierenden Bildes in Streifen;
- (ii) die Schaffung von Datenpaketen, die jedem dieser Streifen zugeordnet sind;
- (iii) das Hinzufügen von Steuerinformationen, wie z. B. EOL- und Fehlersteuer-Codedaten, zu jedem der Datenpakete, um zusammengesetzte Daten zu schaffen; und
- (iv) das Komprimierten der zusammengesetzten Daten.
- Sie leiden an dem Problem, daß die Verfälschung der Steuerinformationen in den komprimierten zusammengesetzten Daten eine umfassende Beschädigung eines Bildes bewirkt, das aus den verfälschten zusammengesetzten Daten rekonstruiert wird. Die Interferenz, die Anlaß für Bitschlupf gibt, kann außerdem Synchronisationsfehler des Decodierers bewirken, die zu einer falschen Datendecodierung der Daten nach dem Bitschlupf führen, selbst wenn die nachfolgenden Daten nicht verfälscht worden sind.
- Es ist eine Aufgabe der Erfindung, ein alternatives Verfahren für die Verarbeitung der Daten zu schaffen.
- Gemäß den Ausführungsformen der vorliegenden Erfindung, die in ihren breitesten Aspekten in den Ansprüchen 1 und 31 definiert ist, wird ein Verfahren der Verarbeitung von Daten geschaffen, das den Schritt des Darstellens einer Anordnung von Einzelbitwörtern als Datenelemente innerhalb eines codierten Datenstroms umfaßt, in dem der Datenstrom erste Datenelemente, die einer entsprechenden Gruppe aus Einzelbitwörtern mit gleichem logischen Wert entsprechen und die Position der Gruppe in der Anordnung anzeigen, und zweite Datenelemente, von denen jedes eine Gruppengröße und eine Gruppenform anzeigt, umfaßt.
- Die Erfindung schafft den Vorteil, daß das Verfahren der Verarbeitung der Daten die Datenkomprimierung und/oder die Zunahme der Robustheit der Daten gegenüber Verfälschung schafft.
- Die Gruppen der Einzelbildwörter können durch die folgenden Schritte identifiziert werden:
- (i) Definieren einer Gruppenform;
- (ii) Definieren einer Menge von Größenwerten für einen Gruppengrößenparameter;
- (iii) Setzen des Gruppengrößenparameters auf den höchsten Größenwert;
- (iv) Analysieren der Anordnung der Einzelbildwörter, um Gruppen zu identifizieren, die eine Dimension besitzen, die gleich dem Gruppengrößenparameter ist;
- (v) Beseitigen der Einzelbitwörter in den im Schritt (iii) identifizierten Gruppen aus der weiteren Betrachtung;
- (vi) Setzen des Gruppengrößenparameters auf den nächsthöchsten Größenwert;
- (vii) Wiederholen der Schritte (iv), (v) und (vi), bis diese Schritte mit dem Gruppengrößenparameter ausgeführt worden sind, der auf den niedrigsten Größenwert gesetzt ist.
- Dies schafft den Vorteil, daß die Anzahl der Gruppen und folglich die Menge der Daten im codierten Datenstrom kleiner sind als sie in dem Fall wären, in dem alle Gruppen die gleiche Größe aufwiesen.
- Alternativ können die Gruppen der Einzelbildwörter durch die folgenden Schritte identifiziert werden:
- (i) Unterteilen der Anordnung der Einzelbildwörter in zwei oder mehr Zonen;
- (ii) für eine gegebene Zone,
- (a) Definieren einer Gruppenform;
- (b) Definieren einer Menge von Größenwerten für einen Gruppengrößenparameter;
- (c) Setzen des Gruppengrößenparameters auf den höchsten Größenwert;
- (d) Analysieren der Einzelbildwörter innerhalb dieser Zone, um Gruppen zu identifizieren, die eine Dimension besitzen, die gleich dem Gruppengrößenparameter ist;
- (e) Beseitigen der Einzelbitwörter in den im Schritt (c) identifizierten Gruppen aus der weiteren Betrachtung;
- (f) Setzen des Gruppengrößenparameters auf den nächsthöchsten Größenwert;
- (g) Wiederholen der Schritte (d), (e) und (f), bis diese Schritte mit dem Gruppengrößenparameter ausgeführt worden sind, der auf den niedrigsten Größenwert gesetzt ist;
- (iii) Wiederholen des Schritts (ii) für die verbleibenden Zonen der Anordnung.
- Dies schafft die Einrichtung, daß unterschiedliche Größen und eine unterschiedliche Anzahl von Gruppen verwendet werden können, um unterschiedliche Gebiete der Anordnung darzustellen. Wenn das Verfahren verwendet wird, um Bilddaten zu codieren, erlaubt dies, daß mehr Daten innerhalb des codierten Datenstroms zu verwenden sind, um die Bildgebiete mit vielen Details darzustellen, als verwendet werden, um Bildgebiete mit weniger Einzelheiten darzustellen. Dies schafft eine effizientere Verwendung der Daten innerhalb des codierten Datenstroms.
- Das Verfahren kann ein Verfahren sein, in dem die Daten in der Form einer Eingangsanordnung aus n-Bit-Wörtern codiert werden, wobei n größer als eins ist, und das ferner die folgenden Schritte umfaßt:
- (i) Analysieren der Eingangsdatenanordnung, um Daten zu erzeugen, die für die Häufigkeit des Auftretens jedes n-Bit-Wortes innerhalb der Eingangsdatenanordnung repräsentativ sind;
- (ii) Darstellen jedes n-Bit-Wortes in der Eingangsdatenanordnung als eine Folge von Einzelbitwörtern, wobei jede Folge den Daten entspricht, die die Häufigkeit des Auftretens des n-Bit-Wortes darstellen, auf das sich diese Folge bezieht, und
- (iii) Darstellen der Einzelbitwörter einer gegebenen Folge in entsprechenden Anordnungen aus Einzelbitwörtern an Positionen darin, die der Position entsprechen, die das n-Bit-Wort, auf das sich diese Folge bezieht, innerhalb der Eingangsdatenanordnung besitzt;
- worin das n-Bit-Wort, das in der Eingangsdatenanordnung am häufigsten auftritt, durch eine Folge von Einzelbitwörtern mit gleichem logischen Wert dargestellt ist.
- Dies schafft den Vorteil, daß die Menge der Daten innerhalb des codierten Datenstroms, die notwendig ist, um die Eingangsdatenanordnung darzustellen, im Vergleich zu den Verfahren der Datencodierung des Standes der Technik verringert ist.
- Alternativ kann das Verfahren ein Verfahren sein, in dem die Daten in der Form einer Eingangsanordnung aus n-Bit-Wörtern codiert werden, wobei n größer als eins ist, und das ferner die folgenden Schritte umfaßt:
- (i) Analysieren der Eingangsdatenanordnung, um Daten zu erzeugen, die für die Häufigkeit des Auftretens jedes n-Bit-Wortes in nerhalb der Eingangsdatenanordnung repräsentativ sind;
- (ii) Analysieren der Eingangsdatenanordnung, um für jedes n-Bit- Wort ein n-Bit-Wort zu bestimmen, das am häufigsten an dieses n-Bit-Wort grenzt;
- (iii) Darstellen jedes n-Bit-Wortes in der Eingangsdatenanordnung als eine Folge von Einzelbitwörtern, wobei jede Folge den Daten entspricht, die die Häufigkeit des Auftretens des n-Bit-Wortes darstellen, auf das sich diese Folge bezieht, und
- (iv) Darstellen der Einzelbitwörter einer gegebenen Folge in entsprechenden Anordnungen aus Einzelbitwörtern an Positionen darin, die der Position entsprechen, die das n-Bit-Wort, auf das sich diese Folge bezieht, innerhalb der Eingangsdatenanordnung besitzt;
- worin das n-Bit-Wort, das am häufigsten auftritt, durch eine Folge von Einzelbitwörtern mit gleichem logischen Wert dargestellt ist, und worin das n-Bit-Wort, das am häufigsten an das am häufigsten auftretende n-Bit-Wort in der Eingangsdatenanordnung grenzt, durch eine Folge von Einzelbitwörtern dargestellt wird, die sich von derjenigen unterscheidet, die das am häufigsten auftretende n-Bit-Wort durch ein einzelnes Bit darstellt.
- Dies schafft eine weitere Verringerung der Menge der Daten innerhalb des codierten Datenstroms, die notwendig ist, um die Eingangsdatenanordnung darzustellen.
- Falls das Verfahren angewendet wird, um eine Eingangsdatenanordnung aus Bit-Wörtern zu codieren, die ein Bild darstellen, wird die Eingangsdatenanordnung vorzugsweise durch den Schritt des Entsprenkelns des Bildes erzeugt, um die Hochfrequenzinformationen und/oder die redundanten Informationen aus dem Bild zu verrin gern. Dies verringert die Menge der Daten innerhalb des codierten Datenstroms weiter, die erforderlich sind, um das Bild darzustellen.
- Vorzugsweise sind die ersten Datenelemente innerhalb des codierten Datenstroms in der Reihenfolge der Größe angeordnet. Dies schafft den Vorteil, daß die Verfälschung der Daten innerhalb des codierten Datenstroms erfaßt werden kann.
- Das Verfahren kann angewendet werden, um Farbbilder zu codieren, wobei in diesem Fall der codierte Datenstrom vorzugsweise Daten umfaßt, die jede Farbe in dem Bild mit einem n-Bit-Wort identifizieren. Dies erlaubt, daß die codierten Daten, die das Bild darstellen, decodiert werden, um ein rekonstruiertes Bild zu erzeugen.
- Das Verfahren kann den Schritt des Aufnehmens redundanter Informationen in den codierten Datenstrom umfassen, um eine zusätzliche Robustheit gegen Datenverfälschung zu schaffen.
- Das Verfahren kann das Decodieren des codierten Datenstroms durch ein Decodierungsverfahren enthalten, das die Schritte umfaßt:
- (i) Initialisieren einer Anordnung aus Einzelbitwörtern, so daß alle Wörter darin einen vorgegebenen logischen Wert besitzen;
- (ii) Empfangen des codierten Datenstroms;
- (iii) Umschalten der Bereiche der Einzelbitwörter in der Anordnung auf einen nicht vorgegebenen logischen Wert, wobei die Bereiche den Gruppen entsprechen, die durch die Datenelemente im codierten Datenstrom dargestellt werden;
- (iv) Erfassen, ob ein umzuschaltender Bereich eine Anzahl von Einzelbitwörtern enthält, die bereits auf den nicht vorgegebenen logischen Wert gesetzt worden sind, so daß die Anzahl derartiger Einzelbitwörter einen Bruchteil der Gesamtzahl der Einzelbitwörter in dem Bereich darstellt, der größer als ein angeordneter Wert ist; und
- (v) Bestimmen einer Position für den Bereich innerhalb der Anordnung, die die Anzahl der Einzelbitwörter innerhalb des Bereichs minimiert, die bereits auf den nicht vorgegebenen Wert gesetzt worden sind.
- Dies erlaubt, daß die codierten Bilddaten verwendet werden, um selbst unter Umständen, unter denen einige der codierten Bilddaten durch die Übertragung über eine Kommunikationsverbindung verfälscht worden sind, ein Bild zu rekonstruieren.
- Alternativ kann das Verfahren das Decodieren des codierten Datenstroms durch ein Decodierungsverfahren enthalten, das die Schritte umfaßt:
- (i) Initialisieren einer Anordnung aus Einzelbitwörtern auf einen vorgegebenen logischen Wert;
- (ii) Empfangen des codierten Datenstroms;
- (iii) Umschalten der Bereiche der Einzelbitwörter in der Anordnung auf einen nicht vorgegebenen logischen Wert, wobei die Bereiche den Gruppen entsprechen, die durch die ersten Datenelemente im codierten Datenstrom dargestellt werden;
- (iv) Analysieren der Anordnung der Einzelbitwörter, um Gebiete in den Bereichen, die infolge der Verfälschung der Daten nicht auf den nicht vorgegebenen logischen Wert umgeschaltet worden sind, und entsprechende Bereiche der Anordnung, die umgeschaltet worden sind, zu identifizieren;
- (v) Umschalten der Einzelbitwörter innerhalb der Gebiete und der im Schritt (iv) identifizierten entsprechenden Bereiche auf einen anderen logischen Wert.
- Dies erlaubt außerdem, daß selbst unter Umständen, unter denen einige der codierten Bilddaten durch die Übertragung über eine Kommunikationsverbindung verfälscht worden sind, codierte Bilddaten verwendet werden, um ein Bild zu rekonstruieren.
- Damit die Erfindung vollständiger verstanden werden kann, werden nun Ausführungsformen von ihr lediglich beispielhaft unter Bezugnahme auf die beigefügte Zeichnung beschrieben, worin:
- Fig. 1 eine schematische Darstellung eines Datencodierungssystems der Erfindung ist;
- Fig. 2 eine Folge von Codierungsfunktionen veranschaulicht, die in dem System in Fig. 1 verwendet werden;
- Fig. 3 eine Folge von Decodierungsfunktionen veranschaulicht, die in dem System in Fig. 1 verwendet werden; und
- Fig. 4 eine Darstellung der Verarbeitungsstufen einer Maschendecodierungsroutine ist.
- In Fig. 1 ist eine schematische Darstellung des Datencodierungssystems der Erfindung gezeigt, das im allgemeinen durch 1 bezeichnet ist. Es enthält zwei Kommunikationsstationen 2a, 2b. Die Station 2a umfaßt einen IBM-kompatiblen Personal-Computer 4a, der einen Pentium-Prozessor und einen Schreib-Lese-Speicher für das Speichern der Daten enthält, ein RS232-Schnittstellenmodul 6a, das vier bidirektionale Kommunikationsanschlüsse P1-4 enthält, einen Rock well-Collins HF9000 Funk-Sender/Empfänger 8a, einen Scanner 10a für Papierdokumente und einen Laserdrucker 12a. Der Scanner 10a und der Drucker 12a sind handelsübliche herstellerspezifische Standardprodukte, die mit dem Computer 4a kompatibel sind. Das Modul 6a enthält ein herstellerspezifisches 5710-Modem, das von dem Unternehmen Harris Inc. hergestellt wird. "Pentium" ist ein eingetragenes Warenzeichen der Intel Corporation. "IBM" ist eine Abkürzung für International Business Machines Inc. Die Station 2b ist zur Station 2a äquivalent, wobei sie die Elemente 4b, 6b, 8b, 10b, 12b enthält, auf die ähnlich Bezug genommen wird, an die anstelle von a b als Suffix angefügt ist. Die Funk-Sender/Empfänger 8a, 8b sind beschaffen, um eine bidirektionale Sprach- und RS232-Kommunikation zwischen den Stationen 2a, 2b zu schaffen, indem sie elektromagnetische Funkstrahlung einem Frequenzbereich von 3 bis 30 MHz empfangen und senden; die Sender/Empfänger 8a, 8b sind beschaffen, um eine Bandbreite der Kommunikationsfrequenz von 3 kHz zu schaffen. Die RS232-Kommunikation wird über die Sender/Empfänger 8a, 8b durch Frequenzumtastungs- oder Tonphasenmodulationstechniken geschaffen, die den Fachleuten für die Konstruktion von Kommunikationssystemen wohlbekannt sind.
- In der Station 2a ist der Computer 4a mit dem Modul 6a verbunden. Die Anschlüsse P1 bis P4 sind mit (nicht gezeigter) externer Ausrüstung, dem Scanner 10a, dem Drucker 12a bzw. dem RS232-Kommunikationsanschluß des Senders/Empfängers 8a verbunden. Für die Elemente, auf die in der Station 2b ähnlich Bezug genommen wird, an die anstelle von a b als Suffix angefügt ist, wird eine völlig gleiche Zusammenschaltung eingesetzt.
- Der Betrieb des Codierungssystems 1 wird nun beschrieben. Der Scanner 10a tastet ein ihm vorgelegtes Dokument, das ein Bild trägt, ab, um einen Datenstrom zu schaffen, der die räumlichen und farblichen Einzelheiten des Bildes beschreibt, wobei er den Strom zum Anschluß P2 des Moduls 6a sendet. Das Modul 6a befördert die Daten vom Anschluß P2 zum Computer 4a, der sie in seinem Schreib-Lese-Speicher speichert. Der Computer 4a führt eine Folge von Codierungsfunktionen an den Daten aus, um sie zu codieren und dadurch eine Folge von Bildpunktdaten in seinem Speicher zu erzeugen. Die Folge der Funktionen wird später ausführlicher erklärt. Der Computer 4a sendet dann die Folge der Daten über den Anschluß P4 des Moduls 6a zum Sender/Empfänger 8a, der sie als elektromagnetische Strahlung bei im voraus gewählten Frequenzen in einem Bereich von 3 bis 30 MHz sendet.
- Der Sender/Empfänger 8b empfängt die Strahlung und demoduliert die Folge der Daten aus ihr, wobei er dann die Folge zum Anschluß P4 des Moduls 6b sendet. Die Folge wird vom Anschluß P4 durch das Modul 6b zum Computer 4b weitergeleitet, der sie in seinem Schreib- Lese-Speicher speichert. Der Computer 4b führt dann eine Folge von dem Decodierungsfunktionen an der Folge aus, um die rekonstruierten Bilddaten in seinem Speicher zu erzeugen. Diese Decodierungsfunktionen werden später ausführlicher erklärt. Der Computer 4b gibt dann die Bilddaten über den Anschluß P3 des Moduls 6b an den Drucker 12b aus, der einen Papierausdruck des Bildes erzeugt.
- Das System 1 ist außerdem beschaffen, um eines oder mehrere in den Scanner 10b eingegebene Bilder in einer Weise, die zu der obenbeschriebenen völlig gleich ist, an den Drucker 12a zu übertragen, mit Ausnahme, daß den Elementen, an die a und b als Suffix angelügt ist, b bzw. a als Suffix angefügt ist. Dadurch wird die bidirektio nale Bildkommunikation zwischen den Stationen 2a, 2b geschaffen. Die Module 6a, 6b sind außerdem beschaffen, um Bilddaten von (nicht gezeigter) externer Ausrüstung am Anschluß P1 der Module 6a, 6b für die Kommunikation über die Computer 4a, 4b und die Sender/Empfänger 8a, 8b entsprechend als codierte Bildelementdaten zu empfangen. Außerdem sind die Module 6a, 6b außerdem beschaffen, um decodierte Bilddaten von den Computern 4a, 4b entsprechend durch den Anschluß P1 zur externen Ausrüstung zu senden.
- In Fig. 2 ist eine Folge von Codierungsfunktionen, die innerhalb des Systems 1 in Fig. 1 ausführbar sind, im allgemeinen durch 20 bezeichnet. Die Folge 20 umfaßt in der Reihenfolge eine Abtastfunktion 22, eine Entsprenkelungsfunktion 24, eine Bitebenen-Codierungsfunktion 26, eine Bildelement-Codierungsfunktion 28, eine Bildelement-Verschachtelungsfunktion 30 und eine Datenausgabefunktion 32. Die Folge der Funktionen 20 ist durch die Computer 4a, 4b an den Eingangsbilddaten, nämlich den Bilddaten A, die in ihrem Speicher gespeichert sind, um Daten, nämlich die Daten B, zu schaffen, die für die Übertragung über die Sender/Empfänger 8a, 8b geeignet sind, ausführbar.
- Der Betrieb der Folge 20 wird nun unter Bezugnahme auf die Fig. 1 und 2 für ein Bild erklärt, das in die Station 2a eingegeben und zur Station 2b für die dortige Rekonstruktion übertragen wird. Da die zwei Stationen 2a, 2b äquivalent sind, wird für ein Bild, das in die Station 2b eingegeben und zur Station 2a für die dortige Rekonstruktion übertragen wird, eine ähnliche Operation unternommen, mit Ausnahme, daß die Suffixe a und b gegenseitig ersetzt sind.
- Ein Bild wird als die Bilddaten A in den Computer 4a eingegeben, der die Daten in seinem Speicher speichert. Die Daten entsprechen einer Beschreibung der Farbe an räumlichen Orten innerhalb eines rechteckigen Bildfeldes, das das Bild enthält. Das Bild grenzt an eine erste Ecke des Feldes, wie in den Daten A dargestellt ist. Die Abtastfunktion 22 wirkt auf die Daten A, um Daten zu erzeugen, die einer Anordnung aus 2000 mal 2000 Bildpunkten Pi,j entsprechen, die das Bildfeld darstellen, wobei i und j Indizes in einem Bereich von 1 bis 2000 sind. Die Indizes i und j entsprechen monoton jeweils den räumlichen Orten längs der x- und y-Achsen eines kartesischen Koordinatensystems, das das Bildfeld enthält, wobei sie deshalb zusammen ein Gitter aus regelmäßig beabstandeten Orten innerhalb des Feldes identifizieren. Folglich entspricht ein Bildpunkt P1,1 einer ersten Ecke dessen Bildfeldes, während ein Bildpunkt P2000,2000 einer zweiten Ecke des Feldes entspricht, die der ersten Ecke diagonal entgegengesetzt ist. Außerdem entspricht ein Bildpunkt P1000,1000 einem zentralen Ort im Bildfeld. Jeder Bildpunkt Pi,j beschreibt die Bildfarbe an einem durch die Indizes i und j identifizierten Ort, wobei P numerisch in einem Bereich von 1 bis 16 liegt; folglich quantisiert die Abtastfunktion 22 den Schatten und die Farbe in dem Bild in eine monotone Skala, die sechzehn Farbschattierungen in einem Bereich von Schwarz zu Weiß umfaßt. Es ist vorteilhaft, das Bild als die Anordnung der Bildpunkte Pi,j darzustellen, weil die anschließende Verarbeitung der Bildpunktdaten in Software problemlos anzuordnen ist.
- Die Entsprenkelungsfunktion 24 wirkt auf die Anordnung der Bildpunkte Pi,j, um Bildpunkte darin zu identifizieren und zu modifizieren, die isolierten Gebieten des Bildes entsprechen, die eine Farbe besitzen, die erheblich von den sie umgebenden Gebieten in dem Bild verschieden ist, nämlich die Bildpunkte Pi,j, die den Flecken in dem Bild entsprechen. Wie später erklärt wird, schafft die Funktion 24 den Vorteil der Beseitigung von Bildmerkmalen, die relativ wenig Informationen befördern und die zu einer ineffizienten Datenkomprimierung führen, wenn die Codierungsfunktion 28 angewendet wird. Die Funktion 24 ist außerdem beim Entfernen unerwünschten Bildrauschens effektiv, das durch Ungenauigkeiten der Digitalisierung eingeführt wird, z. B. wenn die Bilder im Scanner 10a abgetastet werden oder wo eine fehlerhafte Bildquantisierung aufgetreten ist.
- Die Funktion 24 ist beschaffen, um in irgendeiner von drei im voraus gewählten Betriebsarten der Entsprenkelung zu arbeiten, nämlich in der Betriebsart 1, der Betriebsart 2 und der Betriebsart 3. Diese drei Betriebsarten schaffen eine Auswahl der Entsprenkelungseigenschaften, wobei sie z. B. abhängig vom Bildinhalt im voraus auswählbar sind.
- In der Betriebsart 1 wird durch den Betrieb der Funktion 24 jeder Bildpunkt Pi,j auf einen entsprechenden Bildpunkt in einer Anordnung Qi,j abgebildet, wie in diesem Absatz beschrieben ist. Jeder Bildpunkt Pi,j wird mit seinen acht benachbarten Bildpunkten verglichen, nämlich den Bildpunkten Pk,l, wobei ein Index k in einem Bereich von i - 1 bis i + 1 liegt, während ein Index l einem Bereich von j - 1 bis j + 1 liegt, wobei die Indizes k und l beide nicht gleichzeitig gleich den Indizes i bzw. j sind. Wenn die benachbarten Bildpunkte Pk,l alle einen Wert besitzen, der für alle und zum Wert des Bildpunktes Pi,j völlig gleich ist, wird dem Bildpunkt Qi,j ein Wert des Bildpunktes Pi,j zugeordnet. Wenn die benachbarten Bildpunkte Pk,l alle einen Wert besitzen, der für alle völlig gleich ist, der aber vom Wert des Bildpunktes Pi,j verschieden ist, wird dem Bildpunkt Qi,j der Wert der Bildpunkte Pk,l zugeordnet. In einer Situation, in der nur sieben der benachbarten Bildpunkte Pk,l einen Wert besitzen, der für alle völlig gleich ist, wird dem Bildpunkt Qi,j der Wert des Bildpunktes Pi,j zugeordnet, falls eine im voraus gewählte Schwelle auf einen Wert acht gesetzt ist. Wenn jedoch die Schwelle in dieser Situation auf einen Wert sieben gesetzt ist, vergleicht die Funktion 24 den Bildpunkt Pi,j mit seinen nächsten 24 umgebenden Bildpunkten, nämlich den Bildpunkten Pa,b, wobei ein Index a in einem Bereich von i - 2 bis i + 2 liegt, während ein Index b in einem Bereich von j - 2 bis j + 2 liegt, wobei die Indizes a und b nicht beide gleichzeitig gleich den Indizes i bzw. j sind. Falls mehr als 21 dieser benachbarten Bildpunkte Pa,b, einen Wert besitzen, der für alle völlig gleich ist, wird dem Bildpunkt Qi,j dieser völlig gleiche Wert zugeordnet, ansonsten wird dem Bildpunkt Qi,j ein im voraus gewählter vorgegebener Wert zugeordnet. Die Betriebsart 1 schafft den Vorteil, daß viele benachbarten Bildpunkte berücksichtigt werden können, wenn ein geeigneter Wert für den Bildpunkt Qi,j bestimmt wird.
- In der Betriebsart 2 wird durch den Betrieb der Entsprenkelungsfunktion 24 jeder Bildpunkt Pi,j auf einen entsprechenden Bildpunkt Qi,j abgebildet, wie in diesem Absatz beschrieben ist. Jeder Bildpunkt Pi,j wird mit seinen vier unmittelbar benachbarten Bildpunkten Pi-1,j, Pi+1,j, Pi,j-1 und Pi,j+1 verglichen. Wenn die benachbarten Bildpunkte und der Bildpunkt Pi,j einen Wert besitzen, der für alle völlig gleich ist, wird dem Bildpunkt Qi,j ein Wert zugeordnet, der zu dem des Bildpunktes Pi,j völlig gleich ist. Wenn die vier benachbarten Bildpunkte jedoch einen Wert besitzen, der für alle völlig gleich ist, aber von dem Wert des Bildpunktes Pi,j verschieden ist, wird dem Bildpunkt Qi,j dieser völlig gleiche Wert zugeordnet. Die Betriebsart 2 schafft den Vorteil, daß sie ein einfaches und schnelles Verfahren für die Entsprenkelung der Bilddaten ist. Überdies schafft sie außerdem den Vorteil, daß die Farb-Lauflängen in den Bildpunkten Qi,j erweitert werden, dies verbessert die Leistung der Datenkomprimierung des Systems 1.
- In der Betriebsart 3 wird durch den Betrieb der Entsprenkelungsfunktion 24 jeder Bildpunkt P auf einen entsprechenden Bildpunkt Qi,j abgebildet, der wie in diesem Abschnitt beschrieben ist. Jeder Bildpunkt Pi,j wird mit seinen zwei benachbarten Bildpunkten Pi-1,j und Pi+1,j verglichen, die als horizontale Bildpunkte bezeichnet werden. Falls der Bildpunkt Pi,j und seine horizontalen Bildpunkte einen Wert besitzen, der für alle völlig gleich ist, wird dem Bildpunkt Qi,j dieser völlig gleiche Wert zugeordnet. Wenn die horizontalen Bildpunkte einen der Wert besitzen, der für alle völlig gleich ist, der aber von dem Wert des Bildpunktes Pi,j verschieden ist, wird dem Bildpunkt Qi,j der völlig gleiche Wert zugeordnet. In einer Situation, in der die horizontalen Bildpunkte keinen für alle völlig gleichen Wert besitzen, wird der Bildpunkt Pi,j mit seinen benachbarten Bildpunkten Pi,j+1 und Pi,j-1 verglichen, die als vertikale Bildpunkte bezeichnet werden. Wenn in dieser Situation die vertikalen Bildpunkte einen Wert besitzen, der für alle völlig gleich ist, der vom Wert des Bildpunktes Pi,j verschieden ist, wird dem Bildpunkt Qi,j der völlig gleiche Wert zugeordnet. Alternativ wird in dieser Situation dem Bildpunkt Qi,j der Wert des Bildpunktes Pi,j zugeordnet, falls die vertikalen Bildpunkte einen Wert besitzen, der für jeden verschieden ist. Die Betriebsart 3 schafft den Vorteil, daß in der Anordnung größere Gruppen benachbarter Bildpunkte Qi,j geschaffen werden, die alle einen völlig gleichen Wert besitzen, dies führt zu einer effizienteren anschließenden Datenkomprimierung als bei der Anwendung der Betriebsarten 1 und 2.
- Verglichen mit den Daten, die ohne Entsprenkelung durch das System 1 übertragen werden, schaffen die Betriebsarten 1 und 2 typischerweise eine um 5% vergrößerte Datenkomprimierung, wohingegen die Betriebsart 3 typischerweise eine um 25% vergrößerte Datenkomprimierung schafft. Das System 1 ist so konfiguriert, daß die Entsprenkelung der Bildpunkte Pi,j optional ist; wenn die Entsprenkelung der Bildpunkte Pi,j nicht ausgewählt ist, werden die Bildpunkte Pi,j direkt auf ihre entsprechenden Bildpunkte Qi,j umgesetzt, nämlich Qi,j = Pi,j.
- Die Entsprenkelungsfunktion 24 ist konfigurierbar, so daß lediglich im voraus ausgewählte Gebiete, die z. B. durch einen Benutzer des Systems 1 im voraus ausgewählt werden, der Bildeingabe in den Computer 4a entsprenkelt werden. Außerdem ist sie konfigurierbar, um eine bevorzugte im voraus ausgewählte Betriebsart auf bestimmte Gebiete des Bildes anzuwenden, ein Randbereich des Bildes kann z. B. unter Verwendung der Betriebsart 1 entsprenkelt werden, wohingegen ein Mittenbereich von ihm unter Verwendung der Betriebsart 3 entsprenkelt werden kann. Diese wahlweise Verwendung der Betriebsarten ist als Zonenentsprenkelung bekannt. Als ein Beispiel, in dem die Zonenentsprenkelung geeignet ist, besitzen technische Zeichnungen oft Ränder an den Kanten, die vernachlässigbare Informationen enthalten, und einen Mittenbereich, der kritische Informationen enthält. In diesem Beispiel wird die Entsprenkelung geeignet auf die Ränder an den Kanten aber nicht auf den Mittenbereich angewendet. Die Zonenentsprenkelung schafft den Vorteil, daß ein Benutzer des Bildkommunikationssystems 1 einen Kompromiß zwischen der Datenkomprimierung und einer durch es beförderten nützlichen Bildeinzelheit wählen kann.
- Auf den Abschluß der Entsprenkelungsfunktion 24 wirkt die Bitebenen-Codierungsfunktion 26 auf die Bildpunkte Qi,j, um die Häufigkeit des Auftretens der Bildpunktfarbe zu bestimmen. Dies wird ausgeführt, so daß die Farben, die am häufigsten in dem Bild auftreten, in dem System 1 durch Parameter in den Daten B übertragen werden, die relativ wenig Bits enthalten, um dadurch zur Datenkomprimierung beizutragen.
- Die Funktion 26 führt eine Anordnung aus sechzehn Elementen Fy ein, die auf null voreingestellt sind. Die Elemente Fy entsprechen jedes einer von sechzehn Farben, folglich entspricht F&sub1; einer Farbe, während F&sub2; einer anderen Farbe entspricht usw. Die Funktion 26 durchsucht der Reihe nach die Bildpunkte Qi,j, wobei sie für jeden durchsuchten Bildpunkt das Element Fy inkrementiert, wenn der Wert eines Index y mit dem numerischen Wert des durchsuchten Bildpunktes Qi,j, nämlich seiner Bildpunktfarbe, völlig gleich ist. Diese Suche schafft eine Häufigkeitsverteilung in den Elementen Fy des Auftretens der Farbe in den Bildpunkten Qi,j.
- Die Funktion 26 führt dann eine Anordnung aus 16 Elementen Gz ein, in der dem Element G&sub1; ein Wert des Index y für das Element Fy mit dem größten Wert zugeordnet ist, G&sub2; wird einen Wert des Index y für das Element Fy mit dem nächstgrößten Wert zugeordnet usw. Dies schafft eine Rangordnung des Auftretens der Farben in dem Bild.
- Die Funktion 26 führt dann eine Bitebenen-Umsetzungsroutine aus, die jeden Bildpunkt Qi,j auf entsprechende Bildpunkte in vier Bitebe nenanordnungen BQi,j,r abbildet, wobei ein Bitebenenindex r in einem Bereich von 1 bis 4 liegt. Die Routine durchsucht die Anordnung der Elemente Gz nach jedem Bildpunkt Qi,j, um darin ein Element Gw zu finden, das einen mit ihm völlig gleichen numerischen Wert besitzt, wobei sie dann die Werte von null oder eins abhängig vom Index w den entsprechenden Bildpunkten BQi,j,r entsprechend einer in der Tabelle 1 bereitgestellten Entropiecodierungsbeziehung zuordnet. Die Entropiecodierung ist im Stand der Technik bekannt, wobei sie nicht auf vier Bits eingeschränkt ist, wie in der Tabelle 1 veranschaulicht ist. Die Entropiecodierung ist von anderen Typen der Codierung unterscheidbar, z. B. wo den Bildpunkten BQi,j,r Binärwerte zugewiesen werden, die direkt dem Wert ihres entsprechenden Bildpunktes Qi,j entsprechen, indem:
- (i) zunehmende Werte des Index w codiert werden, da zunehmend mehr Bildpunkten BQi,j,r ein logischer Wert 1 von ihrem vorgegebenen logischen Wert 0 zugeordnet wird, abhängig davon, daß
- (ii) sowenig wie möglich Bildpunkten BQi,j,r ein logischer Wert 1 zugeordnet wird, während gesichert wird, daß jeder Wert von w eindeutig in diesen Bildpunkten BQi,j,r in Bezug auf die anderen darin codierten Werte von w codiert wird.
- Die Entropiecodierung schafft den Vorteil, daß die in den Bildpunkten Qi,j beförderten Informationen gleichmäßiger zwischen den Bildpunkten BQi,j,r in den Bitebenenanordnungen verteilt sind. Außerdem schafft die Entropiecodierung den Vorteil der potentiellen Datenkomprimierung; in der Praxis ist festgestellt worden, daß die Datenkomprimierung im System 1 im Vergleich zu einer Implementierung des Systems, in der den Bildpunkten BQi,j,r die Binärwerte der Werte ihrer entsprechenden Bildpunkte Qi,j direkt zugewiesen werden, um etwa 45% verbessert ist. Tabelle 1
- Folglich besitzt die Routine eine Wirkung des Abbildens der Anordnung der Bildpunkte Qi,j abhängig von den Farbwerten der Bildpunkte Qi,j auf die vier Bitebenenanordnungen der Bildpunkte BQi,j,r. Sie schafft den Vorteil, daß die Bildpunkte in den Bitebenenanordnungen nur die logischen Werte 0 und 1 besitzen, die mit Software effizient zu manipulieren sind. Außerdem schafft sie den zusätzlichen Vorteil, daß die Bildpunktfarben, die im Bild am häufigsten auftreten, in den Daten B durch relativ wenig Bits, die auf eine logische 1 gesetzt sind, übertragen werden, wobei dadurch eine effiziente Datenkomprimierung gesichert wird, z. B. wird ein Bildpunkt Qi,j mit der am häufigsten auftretenden Farbe, die w = 1 entspricht, in den Bitebenenanordnungen durch BQi,j,1 = 0, BQi,j,2 = 0, BQi,j,3 = 0 und BQi,j,4 = 0 dargestellt; die w = 1 entsprechende Farbe wird als eine vorgegebene Farbe bezeichnet, weil keiner der Bildpunkte BQi,j,r für sie auf eine logische 1 gesetzt ist.
- Die Codierungsfunktion 26 überträgt dann die Bitebenenanordnungen der Bildpunkte BQi,j,r zur Bildelement-Codierungsfunktion 28. Die Funktion 28 untersucht sie in der Reihenfolge des aufsteigenden Wertes des Index r wiederholt nach allen Werten der Indizes i und j, um zunehmend kleinere Gruppierungen benachbarter Bildpunkte mit einem logischen Wert 1 darin zu identifizieren, wobei sie sie dann als Quadrat- und Lauflängen-Bildelemente codiert, die die Position und die Größe der Gruppierungen innerhalb der Bitebenenanordnungen BQi,j,r definieren. Die Bildelemente werden im Speicher des Computers 4a aufgezeichnet. Die Funktion 28 umfaßt zwei Routinen, die der Reihe nach ausgeführt werden, nämlich eine Extraktionsroutine für quadratische Bildelemente und eine Lauflängen-Extraktionsroutine.
- Die Codierungsfunktion 28 beginnt mit der Extraktionsroutine für quadratische Elemente, die auf die Bildpunkte BQi,j,r wirkt, um sie als quadratische Bildelemente darzustellen. Die Bildelemente werden durch Anordnungen aus quadratischen Positionselementen Xn,r und Yn,r und einer Anordnung aus quadratischen Größenelementen Sn,r beschrieben, wobei n ein Index ist, der ein quadratisches Bildelement identifiziert, während r der Bitebenenindex ist. Die Grenzen der maximalen und minimalen Gruppengröße Mu und Ml werden ent sprechend der gewünschten Auflösung vor dem Aufrufen der Extraktionsroutine für quadratische Elemente im voraus gewählt. Es ist in der Praxis als zufriedenstellend festgestellt worden, die Grenzen Mu und Ml auf 22 bzw. 3 Bildpunkte im voraus zu wählen; diesen Grenzen können jedoch andere Werte im voraus zugewiesen werden.
- Den Wert für die Grenze Mu ist außerdem durch einen Benutzer des Systems 1 auswählbar, um einem erwarteten Grad der Verfälschung der Folge der Daten zu entsprechen, wenn sie durch das System 1 übertragen werden; ein größerer Wert der Grenze Mu wird zu entsprechend größeren Werten für die größeren quadratischen Elemente Sn,r führen, wo der Verlust von Informationen, der diesen Elementen mit größerem Wert zugeordnet ist, im Fall der Datenverfälschung ein aus den Daten wiederhergestelltes Bild ernster entstellen wird. Umgekehrt wird ein kleinerer Wert der Grenze Mu zu einer weniger effizienten Datenkomprimierung führen, wobei dadurch die Dauer der Datenübertragung vergrößert wird, während der einer Störung begegnet werden kann.
- Die Extraktionsroutine für quadratische Elemente führt die folgenden Schritte aus:
- (i) Alle Bildpunkte BQi,j,r werden anfangs als für die Zwecke der Codierung der Bildelemente freigegeben bezeichnet, wobei der Index r auf eins gesetzt wird;
- (ii) dem Index n und einem Suchparameter Ms werden anfangs die Werte von eins bzw. der Grenze Mu zugeordnet;
- (iii) die Routine durchsucht die Bildpunkte BQi,j,r, um eine Gruppierung benachbarter freigegebener Bildpunkte BQf,g,r zu identifizieren, denen durch die Bitebenen-Umsetzungsroutine eine logi sche 1 zugeordnet ist, wobei f ein Index in einem Bereich von i bis i + Ms ist, während g ein Index in einem Bereich von j bis j + Ms ist;
- (iv) wenn im obigen Schritt (iii) eine Gruppierung gefunden wird, werden den Elementen Xn,r und Yn,r die Werte der Indizes i bzw. j zugeordnet, dem Element Sn,r wird ein Wert des Parameters Ms zugeordnet, wobei die freigegebenen Bildpunkte BQf,g,r dann gesperrt werden, so daß sie bei weiteren Durchsuchungen nicht betrachtet werden;
- (v) der Index n wird inkrementiert, wobei die obigen Schritte (iii) und (iv) wiederholt werden, bis alle Bildpunkte BQi,j,r in der Anordnung durchsucht worden sind;
- (vi) dann wird der Parameter Ms um einen im voraus gewählten Betrag dekrementiert, wobei die Schritte (iii) bis (v) wiederholt werden, bis der Parameter Ms auf einen Wert dekrementiert worden ist, der kleiner als die Grenze Ml ist;
- (vii) dann wird der Index r inkrementiert, wobei die Schritte (ii) bis (vi) wiederholt werden, bis er größer als ein Wert vier ist.
- Der Parameter Ms wird nicht mehr als zwanzigmal von der Grenze Mu zur Grenze Ml in der obenbeschriebenen Routine dekrementiert. Seine Werte werden in einer Anordnung der Elemente Ta aufgezeichnet, wobei der tiefgestellte Index a in einem Bereich von eins bis zwanzig liegt.
- Diese quadratische Extraktionsroutine schafft in Verbindung mit der Lauflängen-Extraktionsroutine die Datenkomprimierung für die meisten Bildtypen, wobei sich die Datenkomprimierung in diesem Fall im Vergleich zur Anzahl der Bildpunkte BQi,j,r auf die Anzahl der bezeichneten Elemente Xn,r, Yn,r und Sn,r bezieht. Die Darstellung des Bildes als Gruppierungen quadratischer Elemente schafft wegen der quadratischen Symmetrie den Vorteil, daß nur ein Größenparameter erforderlich ist, um jede Gruppierung zu beschreiben, nämlich die Elemente Sn,r, wohingegen andere Formen der Elementgruppierungen, wie z. B. Rechtecke mit ungleicher Seitenlänge der Bildpunkte, zwei oder mehr Größenparameter erfordern können, um sie zu beschreiben; folglich schafft die Verwendung von Gruppierungen quadratischer Elemente eine besonders effiziente Datenkomprimierung im System 1.
- Auf den Abschluß der obenbeschriebenen Extraktionsroutine für quadratische Elemente gibt es oft restliche freigegebene Bildpunkte BQi,j,r, die in den Elementen Xn,r, Yn,r und Sn,r nicht dargestellt sind, falls im voraus gewählt wurde, daß die Grenze Ml größer als eins ist. Alle Bildpunkte BQi,j,r werden in den Elementen Xn,r, Yn,r und Sn,r dargestellt, wenn im voraus gewählt wurde, daß die Grenze Ml gleich eins ist. Diese restlichen freigegebenen Bildpunkte BQi,j,r, die als Restbilder bekannt sind, bilden Gruppierungen, die als Lauflängen bekannt sind, die den Zeilen in dem Bild entsprechen, die schmaler als eine analoge untere Größengrenze sind, die durch die Grenze Ml auferlegt wird.
- Die Codierungsfunktion 28 führt dann die Lauflängen-Extraktionsroutine an den restlichen freigegebenen Bildpunkten BQi,j,r aus. Die horizontalen Lauflängenanordnungen der Positionselemente Xhm,r, Yhm,r und die Längenelemente Shm,r werden verwendet, um identifizierte Gruppierungen benachbarter freigegebener Bildpunkte BQi,j,r mit einem logischen Wert 1 zu beschreiben, die völlig gleiche j- und r- Indexwerte besitzen. Die vertikalen Lauflängenanordnungen der Positionselemente Xvq,r, Yvq,r und die Längenelemente Svq,r werden verwendet, um identifizierte Gruppierungen benachbarter freigegebener Bildpunkte BQi,j,r mit einem logischen Wert 1 zu beschreiben, die völlig gleiche i- und r-Indexwerte besitzen. Die im voraus gewählten oberen und unteren Grenzen, nämlich Ru bzw. Rl, bestimmen die Größe der Gruppierungen benachbarter freigegebener Bildpunkte des Wertes eins, nach denen durch diese Routine gesucht wird. Es ist in der Praxis festgestellt worden, daß das Auswählen der Grenzen Ru und Rl auf die Werte sechzehn bzw. zwei im voraus einen zufriedenstellenden Betrieb des Systems 1 schafft; abhängig von der gewünschten Auflösung können jedoch den Grenzen Ru und Rl andere Werte zugeordnet werden. Jedes Element wird z. B. codiert, wenn der Grenze Rl ein Wert von eins zugeordnet ist, wobei das System 1 dann als verlustlos bezeichnet wird.
- Die Lauflängenroutine führt die folgenden Schritte aus:
- (i) Der Index r wird auf einen Wert von eins gesetzt.
- (ii) Die Indizes m und q werden auf eins gesetzt. Ein Suchparameter Rs wird auf die Grenze Ru gesetzt.
- (iii) Die Routine durchsucht die restlichen freigegebenen Bildpunkte BQi,j,r vom Bildpunkt BQi,j,r zum Bildpunkt BQi+Rs,j,r, um eine Gruppierung benachbarter freigegebener Bildpunkte mit dem logischen Wert 1 zu identifizieren.
- (iv) Falls im Schritt (iii) eine Gruppierung gefunden wird, werden den Elementen Xhm,r und Yhm,r die Werte der Indizes i bzw. j zugewiesen, während dem Element Shm,r der Wert des Parameters Rs zugewiesen wird. Die Bildpunkte BQi,j,r bis BQi+Rs,j,r m der Gruppierung werden dann gesperrt, so daß sie in weiteren Durchsuchungen nicht betrachtet werden, wobei der Index m inkrementiert wird.
- (v) Die Bildpunkte BQi,j,r werden durchsucht, um eine Gruppierung benachbarter freigegebener Bildpunkte von BQi,j,r bis BQi,j+Rs,r mit dem logischen Wert 1 zu identifizieren.
- (vi) Falls im Schritt (v) eine Gruppierung gefunden wird, werden den Elementen Xvq,r und Yvq,r die Werte der Indizes i bzw. j zugewiesen, während dem Element Svq,r der Wert des Parameters Rs zugewiesen wird. Die Bildpunkte BQi,j,r bis BQi,j+Rs,r werden dann gesperrt, so daß sie in weiteren Durchsuchungen nicht betrachtet werden, wobei der Index q inkrementiert wird.
- (vii) Die obigen Schritte (iii) bis (vi) werden wiederholt, bis alle Bildpunkte BQi,j,r durchsucht worden sind.
- (viii) Dann wird der Parameter Rs um einen im voraus gewählten Betrag dekrementiert, wobei die Schritte (iii) bis (vii) wiederholt werden, bis der Parameter Rs dekrementiert ist, so daß sein Wert kleiner als die Grenze Rl ist.
- (ix) Dann wird der Index r inkrementiert, wobei die Schritte (ii) bis (viii) wiederholt werden, bis er größer als ein Wert vier ist.
- Ein erster Bildpunkt BQi,j,r wird als anderen Bildpunkten BQi,j,r benachbart definiert, wenn sich die Indizes i, j des ersten Bildpunktes von denjenigen der anderen Bildpunkte nur um einen Zählwert unterscheiden, z. B.:
- (i) ein Bildpunkt BQ3,4,2 grenzt an einen Bildpunkt BQ4,4,2;
- (ii) ein Bildpunkt BQ5,6,2 grenzt an einen Bildpunkt BQ4,5,2; und
- (iii) die Bildpunkte BQ6,7,3, BQ7,7,3, BQ6,8,3 und BQ7,8,3 sind eine Gruppe aus vier Bildpunkten, die aneinander grenzen.
- Der Parameter Rs ist beschaffen, um in der obenbeschriebenen Routine nicht mehr als zehnmal von den Grenzen Ru bis Rl dekre mentiert zu werden. Seine Werte werden in einer Anordnung der Elemente Ub aufgezeichnet, wobei ein Index b in einem Bereich von eins bis zehn liegt.
- Irgendwelche verbleibenden restlichen freigegebenen Bildpunkte BQi,j,r, die nicht in den Elementen Xn,r, Yn,r, Sn,r, Xhm,r, Yhm,r, Shm,r, Xvq,r, Yvq,r und SVq,r dargestellt sind, werden durch die Codierungsfunktion 28 nicht codiert. Falls es irgendwelche restlichen freigegebenen Bildpunkte BQi,j,r gibt, die von der Codierungsfunktion 28 nicht codiert werden, wird das System 1 hinsichtlich des Informationsflusses durch es als verlustbehaftet definiert. Falls alternativ alle freigegebenen Bildpunkte BQi,j,r durch die Funktionen codiert werden, wird das System 1 als verlustlos definiert.
- Folglich wirkt die Codierungsfunktion 28 auf die Bildpunkte BQi,j,r, um die Elemente Xn,r, Yn,r, Sn,r, Xhm,r, Yhm,r, Shm,r, Xvq,r, Yvq,r und Svq,r zu erzeugen, die das in den Computer 4a eingegebene Bild nach der Entsprenkelung in der Funktion 24 in komprimierter Form als eine Liste von Bildelementen darstellen. Diese Liste schafft den Vorteil des Darstellens von weniger Informationen, die übertragen werden müssen, wenn Bilder von der Station 2a zur Station 2b gesendet werden, und folglich einer im Vergleich zum Übertragen der Bilder durch das Senden der Anordnung der Bildpunkte Qi,j verringerten Übertragungsdauer.
- Für die weitere Klarstellung des Betriebs des Systems 1 kann die Anwendung der Funktionen 22 bis 28 wie folgt zusammengefaßt werden:
- (i) Darstellen des eingegebenen Bildes im Speicher des Computers 4a als zweidimensionale Anordnung aus 2000 mal 2000 Bildpunkten, in der die Bildpunkte numerisch in einem Wertbereich von eins bis sechzehn liegen, die sechzehn Farben im Bild darstellen;
- (ii) Verringern der Fleckigkeit in der Anordnung;
- (iii) Unternehmen einer Analyse der Anordnung, um die Häufigkeit des Auftretens der Farben zu bestimmen;
- (iv) Abbilden jedes der Bildpunkte abhängig von seiner Farbe und der Häufigkeit des Auftretens seiner Farbe innerhalb des Bildes auf eine Anzahl paralleler Bildpunkt-Logikanordnungen;
- (v) Durchsuchen der Logikanordnungen nach quadratischen Gruppierungen aus benachbarten Bildpunkten mit einem logischen Wert 1 darin und Darstellen jeder identifizierten quadratischen Gruppierung in Bildelementanordnungen im Speicher, in dem jede Gruppierung darin durch Positions- und Größenparameter definiert ist, und dann Sperren der Bildpunkte in der identifizierten Gruppierung in den Logikanordnungen von der Betrachtung in nachfolgenden Durchsuchungen;
- (vi) Wiederholen des obigen Schritts (v) in absteigender Reihenfolge der Größe der Gruppierung, bis eine untere Größengrenze für die Größe der Gruppierung erreicht ist;
- (vii) Durchsuchen der Logikanordnungen für restliche Lauflängen- Bildpunktgruppierungen mit einer Breite von einem Bildpunkt, die in den Schritten (v) bis (vi) nicht aufgezeichnet worden sind, und Darstellen jeder identifizierten Lauflängengruppierung in den Bildelementanordnungen im Speicher, in dem jede Gruppierung durch Positions- und Längenparameter definiert ist, und dann Sperren der Bildpunkte in der identifizierten Gruppierung in der Logikanordnung von der Betrachtung in nachfolgenden Durchsuchungen;
- (viii) Wiederholen des obigen Schritts (vii) in absteigender Reihenfolge der Lauflängengröße, bis eine untere Größengrenze für die Gruppierung erreicht ist.
- Ein Komprimierungsfaktor K beschreibt die aus der Codierungsfunktion 28 erhältliche Datenkomprimierung, wenn die Informationen in den Bitebenenanordnungen der Bildpunkte BQi,j,r in die Bildelemente Xn,r, Yn,r, Sn,r, Xhm,r, Yhm,r, Shm,r, Xvq,r, Yvq,r und Svq,r abgebildet werden. Dieser Faktor K ist unter Verwendung der Gleichung [1] berechenbar:
- wobei:
- xp = die x-Achsenlänge des Bildfeldes (in Bildpunkten);
- yp = die y-Achsenlänge des Bildfeldes (in Bildpunkten);
- Mu = die maximale Größengrenze für quadratische Bildelemente (in Bildpunkten),
- Ml = die minimale Größengrenze für quadratische Bildelemente (in Bildpunkten),
- nH = die Anzahl der Lauflängen einer Länge H (in Bildpunkten) parallel zur x-Achse;
- nV = die Anzahl der Lauflängen einer Länge V (in Bildpunkten) parallel zur y-Achse;
- nS = die Anzahl der quadratischen Bildelemente der Größe S (in Bildpunkten);
- Ru = die Grenze für die maximale Anzahl der Bildpunkte in einer Lauflänge (in Bildpunkten);
- Rl = die Grenze für die minimale Anzahl der Bildpunkte in einer Lauflänge (in Bildpunkten);
- c = die Anzahl der binären Bits, die erforderlich sind, um xp oder yp hinsichtlich der Anzahl der Bildpunkte auszudrücken; und
- F = die Häufigkeit der Einfügung von Synchronisationscodewörtern.
- Wenn in der Praxis echte Bilder codiert werden, z. B. Karten und Flächenphotographien, wird festgestellt, daß der Komprimierungsfaktor K am größten ist, wenn im voraus die Grenze Ml auf drei oder vier Bildpunkte gewählt wird. In dem System 1 wird die Grenze Ml folglich im voraus auf drei Bildpunkte gewählt. Für eine Anordnung aus 2000 mal 2000 Bildpunkten sind 22 Informationsbits erforderlich, um einen Bildpunkt eindeutig zu identifizieren; folglich beträgt der Parameter c der Gleichung [1] elf Bits.
- Auf den Abschluß der Codierungsfunktion 28 wirkt die Verschachtelungsfunktion 30 auf die quadratischen Elemente Xn,r, Yn,r und Sn,r, auf die horizontalen Lauflängenelemente Xhm,r, Yhm,r, und Shm,r und auf die vertikalen Lauflängenelemente Xvq,r, Yvq,r und Svq,r, die von der Funktion 28 bereitgestellt werden, um sie neu zu ordnen und dadurch eine verschachtelte Folge von Elementen zu erzeugen, in der die Elemente Sn,r, Shm,r und Svq,r in absteigender Reihenfolge der Größe mit ihren zugeordneten Elementen Xn,r, Yn,r, Xhm,r, Yhm,r bzw. Xvq,r, Yvq,r erscheinen, größere Bildelemente erscheinen nämlich ungeachtet des Wertes ihres Bitebenenindex r früher in der Folge als kleinere Bildelemente. Wenn einige Elemente Sn,r, Shm,r, Svq,r mit gegenseitig gleichem Wert in der Folge aufeinanderfolgend auftreten, werden sie in der Folge in absteigender Reihenfolge ihrer entsprechenden Elementwerte Yn,r, Yhm,r, Yvq,r in der Folge angeordnet. Wenn außerdem einige Elemente Sn,r, Shm,r, Svq,r mit gegenseitig gleichem Wert in der Folge aufeinanderfolgend auftreten und außerdem gegenseitig gleiche entsprechende Elementwerte Yn,r, Yhm,r, Yvq,r besitzen, werden sie in absteigender Reihenfolge der Elementwerte Xn,r, Xhm,r, Xvq,r in der Folge angeordnet.
- Diese verschachtelte Reihenfolge wird in den Daten B beibehalten, wobei sie den Vorteil schafft, daß jede in der empfangenden Station 2b erfaßte Inkonsistenz in der Reihenfolge das Auftreten der Datenverfälschung anzeigen wird, die in dem System 1 korrigierbar ist, indem z. B. die erneute Übertragung der Elemente angefordert wird, die verfälscht worden sind. In den Daten B sind die quadratischen Bildelemente zuerst in der Folge aufgelistet, gefolgt von den horizontalen Lauflängenelementen und schließlich den vertikalen Lauflängenelementen.
- Die Anordnungen der Elemente Ta und Ub sind in den Daten B enthalten, wobei sie ermöglichen, daß eine effiziente Codierung unter Verwendung von Rahmensymbolen erreicht wird, die in den Daten enthalten sind, die sich auf diese Elemente beziehen.
- Die Ausgabefunktion 32 wirkt auf die verschachtelte Folge der Elemente, die in sie von der Funktion 30 eingegeben wird, um die Daten B für die Übertragung über den Sender/Empfänger 8a zusammenzusetzen. Die Daten B umfassen eine Folge von Datenwörtern, wobei jedes 11 Bits umfaßt, die beschaffen sind, um die Informationen in einer folgenden Reihenfolge zu befördern:
- (i) die Bildkopfinformationen, die ein Format für die Daten B vereinbaren und die Elemente Tg, Ub und Gz enthalten (zum erstenmal);
- (ii) die quadratischen Bildelemente, die durch Rahmensymbole, die sich auf die in den in den Kopfinformationen enthaltenen Ele menten Ta beförderten Größenwerte beziehen, und durch die Elemente Xn,r und Yn,r, die mit den Bildelementen mit größeren Größenwerten beginnen und mit den Bildelementen mit kleineren Größenwerten enden, beschrieben werden;
- (iv) die Bildkopfinformationen, die ein Format für die Daten B vereinbaren und die Elemente Ta, Ub und Gz enthalten (zum zweitenmal);
- (v) die horizontalen Lauflängenelemente, die durch die Rahmensymbole, die sich auf die in den in den Kopfinformationen enthaltenen Elementen Ub beförderten Größenwerte beziehen, und durch die Elemente Xhm,r und Yhm,r, die mit den Lauflängenelementen mit größeren Größenwerten beginnen und mit den Lauflängenelementen mit kleineren Größenwerten enden, beschrieben werden;
- (vi) die vertikalen Lauflängenelemente, die durch die Rahmensymbole und durch die Elemente Xvq,r und Yvq,r, die mit den Lauflängenelementen mit größerem Wert beginnen und mit den Lauflängenelementen mit kleinerem Werten enden, beschrieben werden; und
- (vii) die Bildkopfinformationen, die ein Format für die Daten B vereinbaren und die Elemente Ta, Ub und Gz enthalten (zum drittenmal).
- Die quadratischen Bildelemente, die horizontalen Lauflängenelemente, die vertikalen Lauflängenelemente und die Elemente Ta, Ub und Gz werden durch Rahmensymbole in den Daten B begleitet. Die Elemente Gz, die als Palettentabelle bezeichnet werden, sind wesentliche Informationen in den Daten B, um während der anschließenden Bildrekonstruktion in der Station 2b die in den Daten B dargestellten Elemente in Färbschattierungsinformationen umzusetzen, die in den Bildpunkten Qi,j vorhanden sind. Die Elemente Ta und Ub sind wesentliche Informationen für das Interpretieren der Rahmensymbole in den Daten B und dadurch für das Bestimmen der Gruppengrößen. Die Ausgabefunktion 32 ist im voraus konfigurierbar, um eine 16:11:4-Reed-Muller-Codierung der Elemente Xn,r, Yn,r, Xhm,r, Yhm,r, Xvq,r, Yvq,r in den Daten B anzuwenden, bevor sie zum Sender/Empfänger 8a gesendet werden. Wenn die 16:11:4-Reed-Muller- Codierung angewendet wird, werden fünf zusätzliche Datenbits zu jedem Datenwort in den Daten B hinzugefügt, die dadurch codiert werden, so daß jedes Datenwort aus 11 Bits durch 16 Bits dargestellt ist, wenn es codiert ist. Die Aufnahme der Reed-Muller-Codierung schafft den Vorteil der vergrößerten Robustheit der Daten, die erlaubt, daß z. B. Bitfehlerraten größer als 1 Fehlerbit in 50 Bits z. B. durch das System 1 widerstanden wird.
- Die durch das System 1 geschaffene Datenkomprimierung wird jedoch, wenn die Reed-Muller-Codierung verwendet wird, als eine Folge des Aufnehmens der zusätzlichen Bits in die Daten B verringert.
- Um den Betrieb der Ausgabefunktion 32 weiter zu erklären, wird nun die Reed-Muller-Codierung ausführlicher beschrieben. Die Reed- Muller-Codierung von Datenwörtern enthält das Hinzufügen zusätzlicher Codierungsbits zu den Wörtern, um ihre Robustheit gegen Verfälschung zu vergrößern. Wenn z. B. ein 9-Bit-Daten Wort in den Daten B durch eine Matrix H dargestellt wird:
- H = [h&sub9;, h&sub8;, h&sub7;, h&sub6;, h&sub5;, h&sub4;, h&sub3;, h&sub2;, h&sub1;], Gl. 2
- wobei h&sub9; das höchstwertige Bit des Wortes ist, während h&sub1; das niedrigstwertige Bit des Wortes ist, dann ist die 16:11: 4-Reed-Mullercodierte Version von H durch eine Matrix HRM gegeben:
- HRM = [h&sub1;&sub0; h&sub1;&sub1; c&sub4;, h&sub1;&sub1; c&sub3;, h&sub1;&sub1; c&sub2;, h&sub1;&sub1; c&sub1;, h&sub1;&sub0; b&sub3;, h&sub9;, h&sub8;, h&sub7;, h&sub1;&sub0; b2, h&sub6;, h&sub5;, h&sub4;, h&sub1;&sub0; b&sub1;, h&sub3;, h&sub2;, h&sub1;], Gl. 3
- wobei
- c&sub1; bis c&sub4; = die Codierungskoeffizienten;
- b&sub1; bis b&sub3; = die Codierungskoeffizienten; und
- h&sub1;&sub0;, h&sub1;&sub1; = zusätzliche Codierungsdatenbits sind.
- Folglich werden die Wörter H in den Daten B codiert, um entsprechende Wörter HRM zu schaffen, die für die Übertragung anstelle des Wortes H geliefert werden, wenn die Reed-Muller-Codierung gewählt worden ist.
- Obwohl die 16:11:4-Reed-Muller-Codierung der 9-Bit-Datenwörter oben beschrieben ist, ist die Reed-Muller-Codierung anpaßbar, um Wörter zu codieren, die eine andere Anzahl von Bits enthalten, ebenfalls z. B. für Wörter, die 11 Bits umfassen.
- In den Daten B sind die Datenwörter darin irgendwelche der Kopfdatenwörter, der Elementdatenwörter oder der Parameterdatenwörter. Es gibt vier Kopfdatenwörter h1 bis h4, die den Bitanordnungen in den Daten B von 00000000000b, 10101010101b, 11111100000b bzw. 11111111111b entsprechen, wobei sie die Werte von 00b, 01b, 10b bzw. 11b befördern, dabei bezeichnet ein Index b die binäre Schreibweise. Diese Bitanordnungen der Kopfwörter werden so gewählt, daß sie voneinander numerisch so verschieden wie möglich sind, um die Robustheit der Daten B zu vergrößern; mit anderen Worten, die Bitunterschiede zwischen den Wörtern sind so beschaffen, um so groß wie möglich zu sein, um dadurch den Vorteil zu schaffen, daß die Wahrscheinlichkeit der fehlerhaften Decodierung der Kopfwörter verringert ist, wenn sie empfangen werden. Die Kopfwörter dienen als Synchronisationsmarkierungen in den Daten B, um die Station 2b, die die Daten B anfängt, zu unterstützen, sie zu synchronisieren. Eine zuverlässige Synchronisation ist wichtig, weil eine unzuverlässige Synchronisation zu einer schweren Verschlechterung eines innerhalb des Systems 1 decodierten und rekonstruierten Bildes führen kann. Die Kopfwörter sind in Gruppen von vier zusammengesetzt, um die Rahmensymbole in den Daten B zu bilden. Jedes Rahmensymbol befördert einen Codewert im Bereich von 0 bis 255, nämlich in acht binären Bits b&sub7;, b&sub6;, b&sub5;, b&sub4;, b&sub3;, b&sub2;, b&sub1;, b&sub0;, wobei b&sub7; das höchstwertige Bit ist, während b&sub0; das niedrigstwertige Bit ist. Als ein Beispiel beförderten die zweite Rahmensymbole, die die Folgen der Kopfwörter h1, h1, h1, h4 und h4, h4, h4, h4 in den Daten B umfassen, die Rahmensymbolwerte von 3 bzw. 255.
- Die Rahmensymbole beförderten Codewerte, die eine Signifikanz entsprechend Tabelle 2 besitzen. Jedes Rahmensymbol in den Daten B wird unmittelbar von Daten, die sich auf es beziehen, in der Form der Elementdatenwörter oder der Parameterdatenwörter begleitet. Tabelle 2
- Die Bildkopfinformationen sind aus den Rahmensymbolen aufgebaut, wobei sie die Anordnungen der Elemente Ta, Ub und Gz enthalten. Sie werden in den Daten B dreimal wiederholt, nämlich einmal am Anfang der Daten B, einmal nach den quadratischen Bildelemente, die durch die Elemente Xn,r, Yn,r beschrieben werden, und einmal am Ende der Daten B. Die Kopfinformationen werden dreimal gesendet, weil es kritische Daten sind, die, wenn sie verfälscht werden, ein in den Daten B zur Station 2b übertragenes Bild unklar wiedergeben.
- Auf die Anordnungen der Elemente Ta wird monoton durch die Rahmensymbole in den Bereichen von 0 bis 19, 20 bis 39, 40 bis 59, 60 bis 79 Bezug genommen, wobei sich z. B. die Rahmensymbole 0, 20, 40, 60 auf T&sub1; beziehen. Auf die Anordnungen der Elemente Ub wird durch die Rahmensymbole in den Bereichen von 80 bis 89, 90 bis 99, 100 bis 109, 110 bis 119, 120 bis 129, 130 bis 139, 140 bis 149, 150 bis 159 monotonen Bezug genommen, wobei sich z. B. die Rahmensymbole 80, 90, 100, 110, 120, 130, 140, 150 auf U&sub1; beziehen.
- Wenn die Datenausgabefunktion 32 die Daten B zusammensetzt, befinden sich die Bildelemente, die horizontalen Lauflängenelemente und die vertikalen Lauflängenelemente in einem verschachtelten Format, wie es durch die Funktion 30 bereitgestellt wird. Ein in der Station 2a codiertes Bild kann z. B. zu einer Folge von Rahmensymbolen und Datenwörtern führen, die in den Daten B enthalten sind, wie sie in der Tabelle 3 bereitgestellt ist. Die Daten in jeder Zeile der Tabelle sind wiederum in den Daten B als
- Rahmensymbol + Datenwort 1 + Datenwort 2 + ...
- enthalten.
- Wenn die Rahmensymbole in einem Bereich von 0 bis 159 liegen, setzt die Funktion 32 die Datenwörter in Folgen zusammen, die jede ein Rahmensymbol gefolgt von einem oder mehreren Paaren der Datenwörter umfaßt. Die Rahmensymbole werden in den Daten B verwendet, um die Folgen zu unterbrechen. Tabelle 3
- Die Bildpunkte Qi,j, die in der am häufigsten auftretenden Farbe im Bild vorliegen, werden in der Codierungsfunktion 26 codiert, wobei die entsprechenden Bitebenenbildpunkte BQi,j,1, BQi,j,2, BQi,j,3 und BQi,j,4 auf eine logische 0 gesetzt werden. Die Codierungsfunktion 28 codiert sie anschließend nicht in Bildelemente oder Lauflängenelemente. Dies schafft den Vorteil der Beseitigung von Informationen aus den Daten B, die nicht zur Rekonstruktion des Bildes beitragen, und schafft dadurch eine effizientere Datenkomprimierung. Wie im folgenden erklärt wird, wird dieser Vorteil aus der Verwendung einer vorgegebenen Hintergrundfarbe erhalten, wenn das Bild in der Station 2b rekonstruiert wird, die gewählt wird, damit sie einer am häufigsten auftretenden Farbe entspricht, die im Bild vorhanden ist, nämlich w = 1 in der Tabelle 1, wie durch die Bildkopfinformationen übertragen wird.
- Die Folge 20 der Funktionen lindert die Notwendigkeit, EOL-Codes in die Daten B aufzunehmen, wobei sie, da jedes Bildelement darin unabhängig beschrieben ist, eine Lösung für die Probleme der Fehlerausbreitung von einem Streifen in einen anderen, die im Stand der Technik auftritt, z. B. wo die SEA-RL-Codierung verwendet wird, schafft.
- Die Daten B werden vom Computer 4a über den Anschluß P4 des Moduls 6a zum Sender/Empfänger 8a geleitet, der sie als Funkstrahlung zum Sender/Empfänger 8b überträgt, wo sie als eine Folge aus z binären Bits Dg empfangen werden, wobei g ein Index in einem Bereich von 1 bis z ist. Das Bit D&sub1; ist ein erstes Bit, während Dz ein letztes Bit der empfangenen Folge ist. Der Sender/Empfänger 8b sendet die Folge der Bits Dg über den Anschluß P4 des Moduls 6b zum Computer 4b, der sie in seinem Speicher speichert. Der Computer 4b ist beschaffen, um auf die Bits Dg zu wirken, um die decodierten Bilddaten C zu erzeugen.
- In Fig. 3 ist eine Folge von Decodierungsfunktionen, die in den Computern 4a, 4b des Systems 1 ausführbar sind, im allgemeinen durch 40 bezeichnet. Die Folge 40 umfaßt in der Reihenfolge eine Dateneingabefunktion 42, eine Bildelemente-Decodierungsfunktion 44 und eine Datenausgabefunktion 46. Die Folge der Funktionen 40 ist an den Bits Dg ausführbar, um die Daten C zu schaffen, die für das Drucken im Drucker 12b oder das Senden vom Anschluß P1 des Moduls 6b zur externen Ausrüstung geeignet sind.
- Die Eingabefunktion 42 wendet zuerst eine Analysefunktion auf eine Folge der Bits Dg an, um die Kopfwortgröße festzustellen, die in den übertragenen Daten B verwendet wird, z. B. um festzustellen, ob die Kopfwortgröße verringert worden ist, um ein kleineres in das System eingegebenes Bild aufzunehmen, wie später beschrieben wird. Wenn hinsichtlich einer Wortgröße von x Bits überprüft wird, partitioniert die Analysefunktion die Folge der Bits Dg in aufeinanderfolgende Gruppierungen mit x Bits Größe, wobei sie dann die Gruppierungen mit vier Schablonen mit x Bits Größe korreliert, die den erwarteten Kopfwörtern mit x Bits Größe entsprechen, z. B. h&sub1;, h&sub2;, h&sub3;, h&sub4;. Die Funktion versucht, die Bits Dg an einer Anzahl von Orten entlang ihrer Folge zu partitionieren, um Gruppierungen zu schaffen, um die Synchronisation bezüglich der Schablonen zu überprüfen. Wenn 75% oder mehr dieser Schablonen mit den Daten Dg korreliert sind, wird ein Wert von x, der gegenwärtig für die Korrelation mit den Bits Dg verwendet wird, als bezeichnend für die Kopfwortgröße betrachtet. Die Analysefunktion durchsucht die Bits Dg unter Verwendung eines Bereiches von Werten von x, bis 75% Korrelation oder eine größere Korrelation erreicht ist.
- Ist die Kopfwortgröße x festgestellt, durchsucht die Eingabefunktion 42 dann die im Speicher des Computers 4b gespeicherte Folge der Bits Dg, wobei sie versucht, zu bestimmen, wo ein erstes Rahmensymbol in der Folge auftritt, d. h., die Funktion 42 versucht, die Folge zu synchronisieren. Dies ist notwendig, ansonsten kann die Decodierungsfunktion 44 die Folge nicht richtig decodieren, weil frühe Bits in der Folge störendem Rauschen entsprechen können, das mit den Daten B in keiner Beziehung steht, wobei die frühen Bits die Rahmensymbole längs der Folge der Bits Dg in einer nicht vorhersagbaren Weise verschieben. Die Funktion 44 führt dies aus, indem sie vier Bitschablonen der Bits, die den vier Kopfwörtern h1 bis h4 entsprechen, mit der Folge korreliert, die mit den Bits D&sub1; bis D&sub1;&sub1; beginnt. Falls irgendeine der Schablonen mit mehr Bits als eine im voraus gewählte Korrelationsschwelle mit den Bits D&sub1; bis D&sub1;&sub1; korreliert ist, fährt die Funktion 42 fort, aufeinanderfolgende Gruppierungen der Bits D&sub1;&sub2; bis D&sub2;&sub2;, D&sub2;&sub3; bis D&sub3;&sub3; und D&sub3;&sub4; bis D&sub4;&sub4; mit den vier Kopfwörtern zu korrelieren; falls jede dieser drei Gruppierungen mit irgendeinem der Kopfwörter korreliert ist, wird angenommen, daß die Synchronisation aufgetreten ist. Falls alle Schablonen mit weniger als der Schwelle mit den Bits D&sub1; bis D&sub1;&sub1; korreliert sind, fährt die Funktion 42 fort, die Schablonen mit den Bits D&sub2; bis D&sub1;&sub2; und anschließend mit den Bits D&sub1;&sub3; bis D&sub2;&sub3;, D&sub2;&sub4; bis D&sub3;&sub4; und D&sub3;&sub5; bis D&sub4;&sub5; usw. zu korrelieren, bis die Synchronisation erreicht ist. Falls die Folge der Bits nicht verfälscht ist, entspricht die Folge aufeinanderfolgenden Datenwörtern mit einer konstanten Größe der Bitgruppierung, nämlich elf Bits.
- Die Funktion 42 fährt dann fort, einen Rest der Bits Dg in der Folge in Wiederholungen der Größe der Bitgruppierung zu überprüfen, um zu sichern, daß die Rahmensymbole mit einer Häufigkeit auftreten, die größer als eine vorgegebene Synchronisationsschwelle ist. Falls die Rahmensymbole weniger häufig als die Schwelle nach einem. Bit Dk in der Folge festgestellt werden, identifiziert die Funktion 42 dies als einen Verlust der Synchronisation, der sich z. B. durch irgendeine Datenverfälschung oder irgendeinen Bitschlupf ergeben kann, die bzw. der sich aus der Einfügung zusätzlicher Bits in die Folge ergeben kann, wenn die Folge zwischen den Sendern/Empfängern 8a, 8b übertragen wird. Falls durch die Funktion 42 geschätzt wird, daß der Verlust der Synchronisation nach einem Bit Dk in der Folge aufgetreten ist, korreliert die Funktion 42 die vier Schablonen der Bits mit der Folge, wobei sie die Korrelation bei den Bits Dk-1 bis Dk-1+11 beginnt, der Parameter 1 ist ein im voraus gewählter Suchbandbreiten-Bestimmungsparameter, um zu bestimmen, ob mehr Bits als die Korrelationsschwelle korreliert sind. Falls die Bits Dk-1 bis Dk-1+10 nicht korreliert sind, fährt die Funktion 42 fort, die Schablonen mit den Bits Dk-1+1 bis Dk-1+11 usw. zu korrelieren, bis die Synchronisation erreicht ist. Die Funktion 42 beendet die Korrelation, wenn die Synchronisation durch die Bits Dk+1 bis Dk+1+10 nicht erreicht wird, wobei sie vorkonfigurierbar ist, um eine Fehlernachricht über den Anschluß P4 des Moduls 6b an den Sender/Empfänger 8b auszugeben, der die Nachricht zur Station 2a überträgt, daß eine größere Verfälschung der Daten aufgetreten ist, und daß die erneute Übertragung der Daten B, beginnend mit dem Bit Dk, erforderlich ist.
- Sobald ein erstes Rahmensymbol in der Folge der Bits Dg identifiziert ist, prüft die Funktion 42 dann die Folge der Bits Dg, um zu bestimmen, ob sie ein Rahmensymbol des Wertes 196 oder 197 enthält, das anzeigt, ob auf die Folge der Bits die Reed-Muller-Codierung (RM- Codierung) angewendet worden ist oder nicht. Falls die RM-Codierung angewendet worden ist, wendet die Funktion 42 eine Maschen decodierungsroutine an, um die Bits Dg zu decodieren. Falls die RM- Codierung nicht angewendet worden ist, fährt die Funktion 42 mit anderen Routinen zum Decodieren der Folge der Bits Dg fort, die nach dem Abschluß der Maschenroutine ausgeführt werden, wenn sie aufgerufen wird.
- Die Maschendecodierungsroutinen sind im Stand der Technik bekannt und in einem Buch "Trellis Decoding of Block Codes: A Practical Approach", ISBN 0-7923-9860-1, Honary und Markarian, 1997, beschrieben.
- Um die im System 1 ausgeführte Maschendecodierung zu erklären, wird eine Maschendecodierungsroutine beschrieben, die in Fig. 4 im allgemeinen durch 50 bezeichnend ist. Sie umfaßt erste, zweite, dritte und vierte Stufen, die als in den gestrichelten Linien 60, 62, 64 bzw. 66 enthalten gezeigt sind. Die Routine 50 enthält einen Eingang, um Reed-Mullercodierte Datenwörter zu empfangen, die den Bits Dg entsprechen; die Datenwörter werden durch die Wörter HRM in Fig. 4 dargestellt. Die Wörter HRM sind so, wie sie in der obigen Gleichung 3 definiert sind, wobei jedes für die Zwecke der Erklärung der Routine 50 durch die Bits [q&sub1;&sub6;, q&sub1;&sub5;, q&sub1;&sub4;, q&sub1;&sub3;, q&sub1;&sub2;, q&sub1;&sub1;, q&sub1;&sub0;, q&sub9;, q&sub8;, q&sub7;, q&sub6;, q&sub5;, q&sub4;, q&sub3;, q&sub2;, q&sub1;] dargestellt ist. Die Routine 50 enthält einen Ausgang V, an dem die decodierten Daten ausgegeben werden, wobei sie 26 durch Ellipsen dargestellte Knoten 70 bis 78 umfaßt, die durch die Vektorpfade 80 bis 86 verbunden sind, die durch die Pfeile zwischen den Knoten in Fig. 4 dargestellt sind. Die Knoten 70 bis 78 und die Vektorpfade 80 bis 86 sind Software-Elemente, die keine reale physikalische Existenz besitzen, die aber dem Erklären des Betriebs der Routine 50 dienen. Jedem Vektorpfad 80 bis 86 sind Verzweigungsvektoren zugeordnet, die Verzweigungsvektoren 92a sind z. B. einem Vektorpfad 80a zugeordnet.
- Der Betrieb der Maschendecodierungsroutine 50 wird nun unter Bezugnahme auf Fig. 4 für das Decodieren eines der Datenwörter HRM beschrieben. Die Routine 50 empfängt das Wort HRM am Knoten 70 ihrer ersten Stufe 60; in dem Fall einer Datenverfälschung können eines oder mehrere der Bits q&sub1; bis q&sub1;&sub6; fehlerhaft sein. Als nächstes berechnet die Routine 50 die euklidischen Abstände der Bits q&sub1;&sub6;, q&sub1;&sub5;, q&sub1;&sub4;, q&sub1;&sub3; des Wortes HRM aus in den entsprechenden Bits der Fig. 4 gezeigten Verzweigungsvektoren 92, die den Vektorpfaden 80 vom Knoten 70 zugeordnet sind. Der euklidische Abstand bezieht sich hier auf die Anzahl der Bits, um die sich die Bits q&sub1;&sub6;, q&sub1;&sub5;, q&sub1;&sub4;, q&sub1;&sub3; von den Verzweigungsvektoren 92 unterscheiden. Ein Vektorpfad 80, dessen zugeordnete Verzweigungsvektoren den kleinsten zugeordneten Wert des euklidischen Abstandes von den Bits q&sub1;&sub6;, q&sub1;&sub5;, q&sub1;&sub4;, q&sub1;&sub3; besitzen, wird dann durch die Routine 50 ausgewählt, die einen mit dem Vektorpfad 80 verbundenen Knoten 72 identifiziert; dieser Knoten 72 wird als ein erster Referenzknoten bezeichnet.
- Als nächstes berechnet die Routine 50 die euklidischen Abstände der Bits q&sub1;&sub2;, q&sub1;&sub1;, q&sub1;&sub0;, q&sub9; von den entsprechenden Bits der Verzweigungsvektoren 94 der Vektorpfade 82, die dem ersten Referenzknoten 72 zugeordnet sind. Ein Vektorpfad 82, der einen kleinsten zugeordneten Wert des euklidischen Abstandes von den Bits q&sub1;&sub2;, q&sub1;&sub1;, q&sub1;&sub0;, q&sub9; besitzt, wird dann durch die Routine 50 ausgewählt, die einen mit dem Vektorpfad 82 verbundenen Knoten 74 identifiziert; dieser Knoten wird als ein zweiter Referenzknoten bezeichnet. Die Routine 50 berechnet dann die euklidischen Abstände der Bits q&sub8;, q&sub7;, q&sub6;, q&sub5; von den Verzweigungsvektoren 96 der Vektorpfade 84, die dem zweiten Referenzknoten zugeordnet sind. Ein Vektorpfad 84, der den kleinsten zugeordneten Wert des euklidischen Abstandes von den Bits q&sub8;, q&sub7;, g&sub6;, q&sub5; besitzt, wird dann durch die Routine 50 ausgewählt, die einen mit dem Vektorpfad 84 verbundenen Knoten 76 identifiziert; dieser Knoten wird als ein dritter Referenzknoten bezeichnet. Schließlich berechnet dann die Routine 50 die euklidischen Abstände der Bits q&sub4;, q&sub3;, q&sub2;, q&sub1; von den Verzweigungsvektoren 98 der Vektorpfade 86, die dem dritten Referenzknoten zugeordnet sind. Ein Vektorpfad 86, der den kleinsten zugeordneten Wert des euklidischen Abstandes von den Bits q&sub4;, q&sub3;, q&sub2;, q&sub1; besitzt, wird dann von der Routine 50 ausgewählt, die den mit dem Vektorpfad 84 verbundenen Knoten 78 identifiziert; dieser Knoten wird als ein vierter Referenzknoten bezeichnet.
- Die Vektorpfade 80, 82, 84, 86 vom Knoten 70 zum Knoten 78, denen die Routine 50 folgt, wenn sie das Wort HRM analysiert, werden dann verwendet, um ein Wort am Ausgang V zu erzeugen, das einer decodierten Version des Wortes HRM entspricht.
- Diese Maschendecodierungsroutine überprüft dann die durch die Ausgabefunktion 32 zu jedem Wort in den Daten B hinzugefügten fünf Datenbits, um die richtige Parität des Wortes zu überprüfen. Falls die Parität nicht richtig ist, ist die Funktion 42 vorkonfigurierbar, um über den Anschluß P4 des Moduls 6b eine ARQ-Nachricht an den Sender/Empfänger 8b auszugeben, der die Nachricht zum Sender/Empfänger 8a überträgt. Der Sender/Empfänger 8a sendet die Nachricht über den Anschluß P4 des Moduls 6a zum Computer 4a, der auf die Nachricht antwortet, in dem er das Datenwort, das verfälscht worden ist, über den Anschluß P4 des Moduls 6a zum Sender/Empfänger 8a für die Übertragung zum Sender/Empfänger 8b erneut sendet, von wo es über das Modul 6b zum Computer 4b weitergeleitet wird.
- Nach dem Abschluß der Maschendecodierungsroutine, falls sie in der Folge der Bits Dg aufgerufen wird, oder nach dem Überprüfen der Synchronisation in der Funktion 42, wenn die Maschendecodierungsroutine in den Bits Dg nicht aufgerufen wird, fährt die Funktion 42 dann fort, drei Mengen von Bildkopfinformationen aus der Folge der Bits Dg zu extrahieren, wobei sie die Mengen der Informationen vergleicht, um Inkonsistenzen zwischen ihnen zu identifizieren. Falls zwei oder mehr der Mengen miteinander konsistent sind, werden diese Mengen verwendet, um die Folge der Bits Dg zu decodieren, um die Daten C zu erzeugen. Wenn alle drei Mengen voneinander verschieden sind, ist die Funktion 42 vorkonfigurierbar, um über den Anschluß P4 des Moduls ob eine Fehlernachricht an den Sender/Empfänger 8b auszugeben, der die Nachricht zur Station 2a überträgt, daß eine größere Verfälschung der Daten aufgetreten ist, und daß eine erneute Übertragung der Bildkopfinformationen erforderlich ist.
- Wenn zwei oder mehr der Mengen der Kopfinformationen miteinander konsistent sind, fährt die Funktion 42 fort, diese Informationen zu verwenden, um die Daten der quadratischen Bildelemente und der Lauflängenelemente, die in den Daten B verschachtelt sind, wie oben beschrieben ist, nach Inkonsistenzen zu überprüfen, nämlich Inkonsistenzen, die sich auf die absteigende Größenordnung beziehen, die durch die Rahmensymbole in der Folge der Bits Dg befördert wird. Falls durch die Funktion 42 Inkonsistenzen identifiziert werden, ist sie vorkonfigurierbar, um eine Nachricht, die die Daten identifiziert, die sich auf die Rahmensymbole beziehen, über den Sender/Empfänger 8b zur Station 2a zu senden, um von dieser die erneute Übertragung der Rahmensymbole und der zugeordneten Elementdaten anzufordern.
- Wenn die Inkonsistenzen in den Daten B, die in der Folge der Bits Dg befördert werden, durch die Funktion 42 korrigiert werden, z. B. durch das Anfordern der erneuten Übertragung der verfälschten Elementdaten, leitet sie eine verifizierte Version der Folge, nämlich die Daten Bv, zur Decodierungsfunktion 44, die auf sie wirkt, um ein rekonstruiertes Bild zu erzeugen. Die Funktion 44 führt vier Bitebenenanordnungen der Bildpunkte RQi,j,r ein die auf einen logischen Wert 0 voreingestellt sind. Dies sichert, daß sie auf eine Farbe voreingestellt sind, die am häufigsten in dem in den Daten Bv codierten Bild auftritt; die Farbe entspricht einer modalen Farbe, die ein am häufigsten auftretender Farbwert in den Bildpunkten Qi,j ist. Die Funktion 44 fährt dann fort, die Daten der quadratischen Bildelemente, der horizontalen Lauflängenelemente und der vertikalen Lauflängenelemente, die in den Daten Bv enthalten sind, zu interpretieren, wobei sie die Bildpunkte RQi,j,r auf einen logischen Wert 1 setzt, wo die Bildpunkte durch die Daten adressiert werden. Die Daten in der ersten Zeile der Tabelle 3 werden z. B. zu Bildpunkten Qa,b,1 führen, die auf einen logischen Wert 1 gesetzt sind, wenn ein Index a in einem Bereich von X1,1 bis X1,1 + T&sub1; liegt, während ein Index b in einem Bereich von Y1,1 bis Y1,1 + T&sub1; liegt, und außerdem, wenn der Index a in einem Bereich von X2,1 bis X2,1 + T&sub1; liegt, während der Index b in einem Bereich von Y2,1 bis Y2,1 + T&sub1; liegt.
- Wenn die Decodierungsfunktion 44 die Daten Bv decodiert, überprüft sie nach Fehlern, die die verschachtelte Reihenfolge der geordneten Elemente in den Daten Bv unterbrechen, wie sie durch die Verschachtelungsfunktion 30 hergestellt ist, z. B. die Unterbrechung der absteigenden Werte der Elemente Sn,r, Shm,r, Svq,r, und die Unterbrechung der absteigenden Werte ihrer entsprechenden zugeordneten Elemente Yn,r, Yhm,r, Yvq,r, wenn aufeinanderfolgende völlig gleiche Werte ihrer entsprechenden Elemente Sn,r, Shm,r, Svq,r, in den Daten Bv auftreten. Falls sich ein Elementwert Sn,r, Shm,r, Svq,r, außerhalb der Reihenfolge in den Daten Bv befindet, ist ein Fehler in den Daten Bv wahrscheinlich. Wenn ein Fehler erfaßt wird, ist die Funktion 44 beschaffen, um die zwei vorhergehenden Elemente und die zwei folgenden Elemente zu untersuchen, z. B. werden die zwei vorhergehenden Elemente Sn-2,r, Sn-1,r die zwei folgenden Elemente Sn+1,r, Sn+2,r untersucht, wenn die Funktion 44 einen Fehler im Wert des Elements Sn,r erfaßt. Die Funktion 44 berechnet einen Wert für einen Vertrauensfaktor Cf, indem sie eine Untersuchung eines Elements und seiner zugeordneten zwei vorhergehenden Elemente und seiner zwei folgenden Elemente ausführt. Der Faktor Cf ist anfangs auf einen Wert null gesetzt, bevor die Untersuchung begonnen wird. Der Faktor Cf wird inkrementiert, wenn beim Vergleichen benachbarter Paare der Elemente, z. B. die Elemente Sn,r, Sn+1,r, sich ihre zugeordneten Adressenelementwerte in einer richtig verschachtelten Reihenfolge befinden. Wenn Cf = 3 gilt, sind von der Funktion 44 ein oder mehrere Fehler in den Elementen erfaßt worden. Wenn der Faktor Cf kleiner oder gleich einem Wert 2 ist, werden die Elementwerte Sn,r, Shm,r und Svq,r und ihre zugeordneten Adressenelemente Xn,r, Xhm,r, Xvq,r, Yn,r, Yhm,r, Yvq,r aus den Daten Bv entfernt. Die Funktion 44 führt eine vollständige Fehlerüberprüfung an den Daten Bv aus, indem sie einen Vertrauensfaktor für jedes Element Sn,r, Shm,r und Svq,r und seine zugeordneten Adressenelemente ausführt.
- Wenn die Daten der quadratischen Bildelemente, der horizontalen Lauflängenelemente und der vertikalen Lauflängenelemente, die in den Daten Bv enthalten sind, interpretiert werden, indem die Bildpunkte RQi,j,r auf einen logischen Wert 1 gesetzt werden, wo sie durch die Funktion 44 adressiert werden, ist die Funktion 44 beschaffen, um zu überprüfen, daß keiner der Bildpunkte RQi,j,r mehr als einmal gesetzt ist. Wenn ein Bildpunkt RQi,j,r mehr als einmal gesetzt ist, wenn die Daten Bv decodiert werden, zeigt dies einen Fehler in den Daten an. Das mehrfache Setzen eines Bildpunktes RQi,j,r wird als dessen doppelte Decodierung bezeichnet.
- Die Funktion 44 enthält eine Korrelationsroutine, um die doppelte Decodierung zu erfassen. Wenn die doppelte Decodierung eines quadratischen Elements oder eines Lauflängenelemente auftritt, wenn die Daten Bv decodiert werden, sind entweder eines oder beide seiner zugeordneten Adressierungselemente, z. B. Xn,r, Yn,r, oder der Wert seines Bild- oder Lauflängenelements, z. B. Sn,r, falsch, vorausgesetzt, daß eines oder mehrere früher decodierte Bild- oder Lauflängenelemente nicht verfälscht worden sind und deshalb bereits verwendet worden sind, um die Bildpunkte RQi,j,r falsch zu setzen. Vorausgesetzt, daß ein neues verfälschtes Bild- oder Lauflängenelement, das die doppelte Decodierung verursacht, noch nicht durch das Setzen der Bildpunkte RQi,j,r auf einen Wert 1 decodiert worden ist, fährt die Routine fort, es zu decodieren, ohne es zu modifizieren, falls weniger als 50% seiner entsprechenden Bildpunkte nicht doppelt decodiert werden, sonst verwendet die Routine Korrelationstechniken, um ein Gebiet der Anordnung der Bildpunkte RQi,j,r zu finden, wo das neue Element, abhängig davon, daß ein minimaler Grad der doppelten Decodierung verursacht wird, decodiert werden kann. Die Korrelationstechniken enthalten das wiederholte Modifizieren der Werte der Adressenelemente, die dem neuen Element zuge ordnet sind, und das Versuchen, es durch das vorübergehende Setzen der Bildpunkte RQi,j,r zur Probe und das Überwachen des Auftretens der doppelten Decodierung, die sich ergibt, wenn die Bildpunkte RQi,j,r zur Probe gesetzt werden, zu decodieren. Nach dem Ausführen der Korrelation wird in das neue Element schließlich auf die Bildpunkte RQi,j,r decodiert, wobei es zu einer minimalen Menge der doppelten Decodierung führt, indem diese Bildpunkte RQi,j,r auf einen logischen Wert 1 gesetzt werden. Die Korrelationsroutine ist dadurch beim Reparieren beschädigter Adressenelemente effektiv, um ihr zugeordnete verfälschte Bild- und Lauflängenelemente auf wahrscheinlichere Gebiete der Anordnungen der Bildpunkte RQi,j,r zu verschieben.
- Wenn die Daten des quadratischen Bildelements und der Lauflängenelemente interpretiert worden sind und die Bildpunkte RQi,j,r dementsprechend gesetzt worden sind, wie oben beschrieben ist, führt die Funktion 44 eine Bildanordnung der Bildpunkte RPi,j ein, in der eine Rekonstruktion des in die Station 2a eingegebenen Bildes erzeugt wird. Für jede Kombination der Indizes i und j werden die Bildpunkte RQi,j,1, RQi,j,2, RQi,j,3 und RQi,j,4 unter Verwendung der Entropiecodierungsbeziehung in der Tabelle 1 interpretiert, um einen Wert w&sub0; für den diesen Bildpunkten zugeordneten Index w zu bestimmen. Für den dadurch bestimmten Wert w&sub0; wird aus den Elementen Gz, die in den Bildkopfinformationen in den Daten B enthalten sind, ein Farbwert für den Bildpunkt RPi,j bestimmt, indem er mit dem Element Gw0 gleichgesetzt wird, nämlich RPi,j = Gw0. Wenn dies für alle Werte der Indizes i und j unternommen worden ist, ist die Anordnung der Bildpunkte RPi,j im Speicher des Computers 4b eine Rekonstruktion der Anordnung der Bildpunkte Qi,j im Computer 4a.
- Dann werden die Bildpunkte RPi,j zur Datenausgabefunktion 46 weitergeleitet, die sie formatiert, um die Daten C zu schaffen, die für die Anzeige auf einem Überwachungsbildschirm des Computers 4b, für die Ausgabe auf dem Drucker 12b oder für die (nicht gezeigte) externe Ausrüstung, die mit dem Anschluß P1 des Moduls 6b verbunden ist, geeignet sind.
- Obwohl die Anordnung der Bildpunkte Pi,j oben als 2000 mal 2000 Bildpunkte umfassend beschrieben ist, kann das in die Station 2a eingegebene Bild nicht immer das Bildfeld füllen. In dieser Situation ist das System 1 umkonfigurierbar, um mit verringerten Bereichen für die Indizes i und j zu arbeiten, wie z. B. 1024 mal 1024 Bildpunkte oder 512 mal 512 Bildpunkte. Dies schafft den Vorteil, daß die Bitbreite der Datenwörter in den Daten B von elf Bits verringert wird, dadurch ergeben sich weniger Daten, die zwischen den Stationen 2 zu übertragen sind.
- In einer alternativen Ausführungsform des Systems 1 ist die Datenausgabefunktion 46 konfiguriert, um eine vorwählbare Entsprenkelung der Bildpunkte RPi,j in einer Weise zu schaffen, die zu der in der Entsprenkelungsfunktion 24 bereitgestellten Entsprenkelung völlig gleich ist, die Bildpunkte RPi,j werden nämlich wenigstens einer der Entsprenkelungsbetriebsarten 1, 2 und 3 unterworfen, bevor sie formatiert werden, um die Ausgangsdaten C zu schaffen. Die Entsprenkelung kann auf eine oder mehrere im voraus gewählte Teilmengen der Bildpunkte RPi,j angewendet werden, es kann nämlich die Zonenentsprenkelung der Bildpunkte RPi,j unternommen werden. Die auf die empfangenen Daten angewendete Entsprenkelung schafft den Vorteil, daß die sich aus Übertragungsfehlern ergebende Bildbeschädigung, die zu zusätzlicher Fleckigkeit in den Bildpunkten RPi,j führt, wenigstens teilweise verborgen werden kann.
- In einer weiteren alternativen Ausführungsform des Systems 1 können die Computer 4a, 4b beschaffen sein, um beim Decodieren der empfangenen Daten die Daten nicht zu beachten, die relativ kleineren Gruppierungen der Elemente entsprechen, die empfangen wurden, nachdem die Datenverfälschung aufgetreten ist, wo eine einfachere Wiedergabe des Bildes basierend auf den vor dem Auftreten der Datenverfälschung empfangenen Daten annehmbar ist.
- In einer weiteren alternativen Ausführungsform des Systems 1 kann die Bildelement-Codierungsfunktion 28 beschaffen sein, um ein Bild, wie es durch die Bildpunkte Qi,j dargestellt wird, in Zonen zu verarbeiten, das Bild wird nämlich in Zonen unterteilt, die typischerweise verschiedene Mengen von Bildinformationen bezüglich zueinander umfassen. Wenn die Codierungsfunktion 28 die Bildpunkte Qi,j codiert, können die Grenzen Mu, Ml, Ru und Rl variabel gemacht werden, abhängig davon, welcher Zone die Bildpunkte BQi,j,r, die zu codieren sind, zugeordnet sind. Dies schafft den Vorteil, daß Zonen, die kritische Informationen enthalten, dadurch im Vergleich zu den Zonen, die relativ unwichtige Informationen enthalten, mit einer relativ höheren Auflösung codiert werden können. Die zonengestützte Codierung verbessert die Datenkomprimierung für Zonen, die relativ unwichtige Bildinformationen umfassen, wobei die kritischen Informationen in anderen Zonen befördert werden. Ein Randbereich des Bildes, der relativ wenig Informationen enthält, kann z. B. grob codiert werden, wobei Ml und Rl auf die Werte 10 bzw. 5 gesetzt sind, wohingegen ein Mittenbereich des Bildes codiert werden kann, wenn Ml und Rl auf die Werte 3 bzw. 1 gesetzt sind.
- In einer weiteren alternativen Ausführungsform des Systems 1 führt die Codierungsfunktion 26 eine Cluster-Bitcodierungsroutine aus, die eine alternative Abbildungsbeziehung zu der in der Tabelle 1 bereitgestellten Entropiebeziehung für die Verwendung erzeugt, wenn jeder Bildpunkt Qi,j auf die entsprechenden Bildpunkte in den vier Bitebenenanordnungen BQi,j,r abgebildet wird. Die Cluster-Routine schafft den Vorteil, daß größere Gruppierungen benachbarter freigegebener Bildpunkte BQf,g,r mit Wert eins erzeugt werden, die, wenn sie durch die Extraktionsroutine für quadratischen Elemente und die Lauflängen-Extraktionsroutinen identifiziert werden, eine vergrößerte Datenkomprimierung von etwa 15% in den resultierenden Daten B im Vergleich zu den Daten B schaffen, die durch das Abbilden der Bildpunkte Qi,j unter Verwendung der Entropiebeziehung in der Tabelle 1 erzeugt werden.
- Die Cluster-Codierungsroutine führt eine zweidimensionale Anordnung benachbarter Farben der Elemente Ne,f ein, wobei die Indizes e und f in einem Bereich von 1 bis 16 liegen und numerisch den in den Bildpunkten Qi,j aufgezeichneten Farbwerten entsprechen. Die Elemente Ne,f sind auf einen Wert null voreingestellt. Die Routine tastet dann durch die gesamte Anordnung der Bildpunkte Qi,j ab. Für jeden Bildpunkt Qi,j setzt die Routine den Index e gleich einem numerischen Wert, der in dem Bildpunkt Qi,j befördert wird. Die Routine untersucht dann die Werte in acht zu Qi,j benachbarten Bildpunkten, nämlich den Bildpunkten Qi-1,j, Qi+1,j, Qi-1,j-1, Qi,j-1, Qi+1,j-1, Qi-1,j+1, Qi,j+1 und Qi+1,j+1. Für jeden dieser benachbarten Bildpunkte setzt die Routine einen darin beförderten numerischen Wert auf den Index f, wobei sie dann das dadurch indexierte Element Ne,f inkrementiert. Folglich stellt die Routine die Informationen in den Elementen Ne,f zusammen, die sich auf die Häufigkeit beziehen, mit der die Bild punkte Qi,j mit verschiedenen Farbwerten innerhalb der Anordnung der Bildpunkte Qi,j aneinander grenzen.
- Die Routine erzeugt dann eine Abbildungsbeziehung für das Abbilden der in den Bildpunkten Qi,j beförderten Daten auf die entsprechenden Bildpunkte in den vier Bitebenenanordnungen BQi,j,r. Die Abbildung ist beschaffen, um die Bildpunkte Qi,j, die einen Farbwert besitzen, der am häufigsten in dem Bild auftritt, in den entsprechenden Bildpunkten BQi,j,r in den Bitebenenanordnungen wie für die Entropiecodierung als logische Werte 0 zu codieren. Wenn die Abbildung erzeugt wird, untersucht die Routine die Anordnung der Elemente Ne,f, um daraus Paare von Farben zu bestimmen, die am häufigsten zusammen in dem Bild auftreten; diese werden als Farbpaare bezeichnet. Die Routine stellt dann die Paare in einer Folge in der Reihenfolge abnehmender Häufigkeit des Auftretens des Farbpaares im Bild zusammen. Dann konfiguriert sie die Abbildung für jedes Farbpaar, beginnend mit dem am häufigsten auftretenden Farbpaar, so daß die Bildpunkte Qi,j die die Farbwerte dieses Farbpaares besitzen, durch das zunehmende Setzen von mehr entsprechenden Bitebenen-Bildpunkten BQi,j,r von der logischen 0 zur logischen 1 codiert werden, wie die Häufigkeit des Auftretens des Farbpaares abnimmt. Außerdem ist die Abbildung konfiguriert, um beim Codieren der Bildpunkte Qi,j, die die Farbwerte eines Farbpaares besitzen, ihre entsprechenden Bitebenen-Bildpunkte BQi,j,r zu setzen, damit sie sich um so wenig Bitänderungen wie möglich voneinander unterscheiden, wobei dadurch größere Gruppierungen benachbarter Bildpunkte geschaffen werden, die durch Quadrat- und Lauflängenroutinen identifizierbar sind. Das Auftreten der Bildpunkte Qi,j, die einen Farbwert besitzen, der am häufigsten an die Bildpunkte Qi,j des gleichen Farbwertes grenzt, wird nicht als Farb paare betrachtet, wenn die Abbildungsbeziehung erzeugt wird. Die Routine wendet dann die Abbildungsbeziehung auf die Bildpunkte Qi,j an, um die entsprechenden Bitebenen-Bildpunkte BQi,j,r zu erzeugen.
- Die Routine erzeugt außerdem eine alternative Folge von Farbenübereinstimmungen in der Anordnung der Elemente Gz, die in den Bildkopfinformationen übertragen wird.
- Nun wird ein Beispiel angegeben, um den Betrieb der Cluster-Codierungsroutine zu veranschaulichen. In einem Bild entspricht eine am häufigsten auftretende Farbe einem numerischen Wert 9. Die Bildpunkte Qi,j mit diesem Farbwert werden in die entsprechenden Bildpunkte in den Bitebenenanordnungen BQi,j,r codiert, indem sie auf einen logischen Wert 0 gesetzt werden. Außerdem sind Paare von Farben, die in dem Bild aneinander grenzen, in der Tabelle 4 in absteigender Reihenfolge der Häufigkeit des Aneinandergrenzens bereitgestellt: Tabelle 4
- Die Routine erzeugt in diesem Beispiel eine Abbildungsbeziehung, wie sie in der Tabelle 5 bereitgestellt ist. In der Tabelle sind die Farbpaare zusammen gezeigt, um die Werte der Bildpunkte BQi,j,r zu veranschaulichen, die jede der Farben unterscheiden. Tabelle 5
- Die Bildpunkte Qi,j, die einen Farbwert 9 besitzen, treten am häufigsten auf, wobei sie folglich als eine vorgegebene Farbe aufgezeichnet werden, indem die entsprechenden Bitebenen-Bildpunkte BQi,j,r auf einen Wert 0 gesetzt werden. Die Bildpunkte Qi,j, die einen Farbwert 4 besitzen, treten am häufigsten angrenzend an die Bildpunkte Qi,j auf, die einen Farbwert 5 besitzen, folglich werden die Bildpunkte Qi,j, die einen Farbwert 4 besitzen, durch nur eine Änderung des Wertes der Bitebenen in den entsprechenden Bitebenen-Bildpunkten BQi,j,r im Vergleich zu denjenigen der Bildpunkte Qi,j dargestellt, die einen Farbwert 5 besitzen; mit anderen Worten, die Bildpunkte Qi,j, die einen Farbwert 9 besitzen, werden durch die Bildpunkte BQi,j,1 = 0, BQi,j,2 = 0, BQi,j,3 BQi,j,4 = 0 dargestellt, die Bildpunkte Qi,j, die einen Farbwert 4 besitzen, werden durch die Bildpunkte BQi,j,1 = 0, BQi,j,2 = 0, BQi,j,3 = 0 und BQi,j,4 = 1 dargestellt, während die Bildpunkte Qi,j die einen Farbwert 5 besitzen, durch diejenigen des Farbwerts 4 dargestellt werden, mit Ausnahme, daß der Bildpunkt BQi,j,3 = 1 ist. Folglich stellt die Abbildung benachbarte Bildpunkte Qi,j, deren Farbwerte häufig zusammen auftreten, durch sowenig Änderungen in den entsprechenden Werten der Bitebenen- Bildpunkte BQi,j,r wie möglich dar, um dadurch größere Gruppierungen benachbarter Bildpunkte für die Identifizierung durch die quadratischen Extraktionsroutinen und diese Lauflängen-Extraktionsroutinen zu erzeugen und folglich den Wirkungsgrad der Datenkomprimierung des Systems 1 zu verbessern.
- Die Farbwerte in einer zweiten Spalte der Tabelle 4 sind in der Anordnung der Elemente Gz für die Verwendung aufgezeichnet, wenn die Daten später decodiert werden, um das Bild zu rekonstruieren.
- In den obenbeschriebenen Ausführungsformen der Erfindung codiert das System 1 die Bilder als einer Folge quadratischer Elemente und Lauflängenelemente in den Daten B. Diese Elemente sind wegen der entsprechenden Bildpunktgruppierungen, die derartige Formen darstellen, als Quadrat- und Längsformen visualisierbar, wenn die Bildpunktanordnungen BQi,j,r und RQi,j,r als zweidimensionale Ebenen betrachtet werden, in denen die Bildpunkte regelmäßig verteilt sind; die Formen werden außerdem als Ziffernverteilungen bezeichnet. Rechteckig geformte Elemente schaffen im Vergleich zu anderen Typen der Elementformen bessere Tesselierungseigenschaften. In einer weiteren alternativen Ausführungsform des Systems 1 werden durch die Codierungsfunktion 28 dreieckige, sechseckige, trapezförmige und andere geometrisch geformte Gruppierungen benachbarter Bildpunkte BQi,j,r mit dem logischen Wert 1 identifiziert und als Bildelemente in den Daten B aufgezeichnet. In dieser Ausführungsform können die Bilder in Zonen partitioniert werden, die unter Verwendung im voraus gewählter Typen geometrischer Formen der Gruppierung codiert werden, die für jede der Zonen geeignet sind. Außerdem kann eine Kombination verschiedener geometrischer Formen der Gruppierungen im voraus gewählt werden, um eine besonders effiziente Datenkomprimierung zu erreichen. Außerdem kann die Kombination der geometrischen Form der Gruppierungen automatisch als Antwort auf den Informationsinhalt des Bildes gewählt werden, nachdem es in diese Ausführungsform eingegeben worden ist. In der Ausführungsform schafft die Verwendung rechtwinkliger dreieckiger Elementgruppierungen den Vorteil, daß sie durch drei Parameter effizient beschrieben werden können, nämlich ihre Position, Größe und Orientierung.
- Das obenbeschriebene System 1 überträgt ein Bild in sechzehn Farben von Schwarz zu Weiß, z. B. unter Verwendung der Farben Rot, Grün, Blau und Gelb. In einer anderen alternativen Ausführungsform des Systems 1 können die Graumerkmale der Bilder außerdem übertragen werden. Dies wird in der Ausführungsform erreicht, indem die Größen der Anordnungen Fy und Gz vergrößert werden und ein Bereich der Werte in den Bildpunkten Pi,j zugeordnet wird, der den Grauschattierungen in dem Bild entspricht. Außerdem kann die Anzahl der Bitebenenanordnungen vergrößert werden, der Index r kann nämlich größer als ein Wert vier sein, wobei die Entropiecodierung, wie sie in der Tabelle 1 vorgesehen ist, neu definiert wird, um eine größere Anzahl von Schattierungen und Farben aufzunehmen. Eine derartige Farbwiedergabe ist in den Stand der Technik nicht aufgenommen, die SEA-RL-Codierung des Standes der Technik unterstützt z. B. nur die Schwarzweiß-Bildübertragung.
- In einer weiteren Ausführungsform des Systems 1 können die Anordnungen Fy und Gz beschaffen sein, um Bilder zu codieren, so daß nur Schwarz, Weiß und Grautönungs-Merkmale in den Bitebenenanordnungen BQi,j,r codiert werden. Wenn das System 1 für die Bildübertragung von Bildern konfiguriert ist, die nur Schwarzweißmerkmale enthalten, kann es vereinfacht werden, um eine einzelne Bitebenenanordnung zu enthalten, aus der die Gruppierungen benachbarter Bildpunkte durch Routinen für quadratische Elemente und Lauflängenelemente identifiziert werden, um die codierten Ausgangsdaten zu schaffen.
- In einer weiteren alternativen Ausführungsform des Systems 1 sind Codierer- und Decodierer-Schätzroutinen (PEST-Routinen) in der Bildelement-Codierungsfunktion 28 bzw. in der Decodierungsfunktion 44 enthalten. Die Codierer-Schätzroutine ist beschaffen, um in einer Stufe nach dem Abschluß der Routine für quadratische Bildelemente und vor der Ausführung der Lauflängen-Extraktionsroutine zu arbeiten, die oben beschrieben sind. In der Stufe entsprechen die freigegebenen Bildpunkte BQi,j,r einem restlichen Bild, das eine Anzahl isolierter Bildpunkte enthält, die sich an Orten befinden, die den Ecken der Merkmale in dem durch die Bildpunkte Qi,j dargestellten Bild zugeordnet sind. Die Codierung dieser isolierten Elemente ist ineffizient. Die PEST-Routine ist beschaffen, um das Auftreten der Bildpunkte an inneren Ecken zwischen angrenzenden quadratischen Elementgruppierungen, die aus den Anordnungen der Bildpunkte BQi,j,r, die wiederum für jeden Wert des Index r durch die Elemente Xn,r, Yn,r, Sn,r beschrieben werden, extrahiert worden sind, zu schätzen, und dies mit den restlichen Bildern zu korrelieren, die in den Anordnungen der Bildpunkte BQi,j,r verbleiben, um einen Schätzparameter zu erzeugen. Die Decodierer-Schätzroutine ist beschaffen, um basierend auf dem Schätzparameter freigegebene Bildpunkte an den inneren Ecken der Merkmale einzufügen, die in den Anordnungen der Bildpunkte RQi,j,r aufgezeichnet sind. Der durch die Codierer-Schätzroutine erzeugte Parameter wird in den Daten B durch die Rahmensymbole 160 bis 179 befördert, wie in der Tabelle 2 vorgesehen ist. Die Schätzroutine schafft den Vorteil der vergrößerten Datenkomprimierung in den Daten B, indem die Redundanz in dem Bild ausgenutzt wird, die durch den Schätzparameter effizient befördert wird.
- Es werden zwei Bildpunktegruppierungen als aneinander angrenzend definiert, wobei sie außerdem als einander benachbart bezeichnet werden, wenn wenigstens ein Bildpunkt in einer der Gruppierungen Indizes i, j besitzt, die sich von denjenigen eines Bildpunkts in der anderen Gruppierung nur um einen Zählwert in irgendeinem oder beiden der Indizes i, j unterscheiden.
- Die Codierer-Schätzroutine wirkt wiederum für jeden Wert des Index r auf die Anordnungen der Elemente Xn,r, Yn,r und Sn,r. Die Routine identifiziert, wo die Gruppierungen der Bildpunkte BQi,j,r aneinander grenzen, um die Merkmale der inneren Ecken zu bilden, wobei sie dann die Bildpunkte entsprechend eines im voraus gewählten Schätzparameters schätzt, die wahrscheinlich an diesen Merkmalen vorhanden sind. Der Schätzparameter bezieht sich auf den Grad der Rundung, der auf diese Merkmale angewendet ist. Dann führt die Codierer-Schätzroutine eine Korrelation mit den restlichen Bildern, die in den Anordnungen der Bildpunkte BQi,j,r nach dem Abschluß der obenbeschriebenen Extraktionsroutine für quadratische Bildelemente verbleiben, aus, um den Grad der Genauigkeit zu bestimmen, mit der die geschätzten Bildpunkte mit den restlichen Bildpunkten korreliert sind. Falls die Korrelation größer als eine im voraus gewählte Schwelle ist, wird die Routine beendet, indem der Schätzpa rameter in die Bildkopfinformationen in den Daten B aufgenommen wird, und indem diejenigen Bildpunkte modifiziert werden, die in den Anordnungen der Bildpunkte BQi,j,r verbleiben, die aus dem Schätzparameter durch das Umschalten ihres logischen Wertes schätzbar sind.
- Wenn die Schätzung kleiner als die Schwelle ist, wird der Schätzparameter vergrößert, um mehr Rundung zu schaffen, wobei die Routine dann wiederholt wird, bis eine beste Schätzung erhalten wird. Wenn die beste Schätzung erhalten wird, wird die Routine beendet, indem der Schätzparameter in die Bildkopfinformationen in den Daten B aufgenommen wird und diejenigen Bildpunkte modifiziert werden, die in den Anordnungen der Bildpunkte BQi,j,r verbleiben, die aus dem Schätzparameter durch das Umschalten ihres logischen Wertes schätzbar sind. Falls alle Korrelationen kleiner als die Schwelle sind, wird die Schätzung aufgegeben, wobei der Schätzparameter nicht in die Daten B aufgenommen wird. Die Schwelle bezieht sich darauf, ob im Vergleich zum Codieren des Bildes nur durch das Ausführen der Extraktionsroutinen für quadratische Elemente und der Lauflängen-Extraktionsroutinen eine vergrößerte Datenkomprimierung in den Daten B erreichbar ist, indem das Bild durch das Ausführen der quadratischen Extraktionsroutine und der Lauflängen-Extraktionsroutinen in Verbindung mit dem Einbeziehen des Schätzparameters und dem Umschalten der logischen Werte der unter Verwendung des Schätzparameters schätzbaren Bildpunkte codiert wird.
- Die Decodierer-Schätzroutine ist beschaffen, um den in den Bildkopfinformationen beförderten Schätzparameter zu empfangen und in einer völlig gleichen Weise zur Codierer-Schätzroutine die Bild punkte für die Merkmale der inneren Ecken zu erzeugen. Sie fügt diese dann zu den Bildpunkten RQi,j,r hinzu, die anschließend decodiert und verwendet werden, wenn das Bild rekonstruiert wird. Die aus dem Schätzparameter erzeugten Bildpunkte werden zu den Bildpunkten RQi,j,r hinzugefügt, indem eine logische Exklusiv-ODER- Addition von ihnen ausgeführt wird. Es ist in der Praxis festgestellt worden, daß durch die Aufnahme der PEST in das System 1 im Vergleich zu dem System 1, das ohne PEST arbeitet, eine vergrößerte Datenkomprimierung geschaffen wird, die sich für einige Typen der Bilder 20% nähert.
- In einer weiteren alternativen Ausführungsform des Systems 1 sind die Scanner 10a, 10b in Fig. 1 durch Kameras für Fernüberwachungszwecke ersetzt.
- Einer weiteren alternativen Ausführungsform des Systems 1 sind die Funk-Sender/Empfänger 8a, 8b durch optische Sender/Empfänger ersetzt, um über ein Glasfasernetz zu kommunizieren, wie es z. B. für das Internet verwendet wird.
- Die Bitebenen-Bildpunkte BQi,j,r, die außerdem für die Zwecke dieser Beschreibung als Ziffern bezeichnet werden können, können so beschaffen sein, daß sie in einer alternativen Ausführungsform der Erfindung andere Werte als die logische 0 und die logische 1 besitzen.
- In einer weiteren alternativen Ausführungsform der Erfindung ist die Decodierungsfunktion 44 beschaffen, um auffällige Fehler in den Bildpunkten RPi,j zu identifizieren, die sich aus der Datenverfälschung ergeben. Derartige Fehler sind als Bildfehler bekannt, weil sie oft z. B. als isolierte rechteckige Gruppierungen benachbarter Bildpunkte RPi,j erscheinen, wenn die Daten einem photographischen Bild entsprechen. In der Praxis enthaltenen photographische Bilder selten senkrecht ausgerichtete gerade Kanten.
- Die Bildfehler ergeben sich, wenn quadratische Adressenelemente oder Lauflängen-Adressenelemente in den Bits D verdreht worden sind, so daß sie anderen Adressenelementen darin ähneln, sie aber trotzdem die richtige verschachtelte Reihenfolge beibehalten und folglich durch die Decodierungsfunktion 44 nicht als doppelt decodiert identifiziert werden; diese Bildfehler sind als schwarze Bildfehler bekannt. Bildfehler ergeben sich außerdem, wenn sich Elementgruppierungen nicht in der richtig verschachtelten Reihenfolge in den Bits D befinden, wobei sie durch die Decodierungsfunktion 44 nicht beachtet werden, wenn die Werte zu den Bildpunkten RQi,j,r zugeordnet werden; diese Bildfehler sind als weiße Bildfehler bekannt. In der Praxis sind die weißen Bildfehler im allgemeinen häufiger als die schwarzen Bildfehler.
- Die schwarzen Bildfehler sind oft in einem aus den Daten C erzeugten, in größere Punkte aufgelösten Bild als quadratische Bildpunktgruppierungen mit einer ersten Farbe erkennbar, die von Bildpunkten mit einer zweiten Farbe umschlossen sind, die unähnlich zur ersten Farbe ist. In der alternativen Ausführungsform enthält die Funktion 44 eine expandierende Kernroutine, die eine systematische Suche von dem Bildpunkt RP2,2 ausführt, indem sie jeden an ihn grenzenden Bildpunkt RPi,j mit einem ersten Farbwert als einen Keimbildpunkt nimmt, um von ihm zu arbeiten. Die umgebenden benachbarten Bildpunkte RPi,j um jeden Keimbildpunkt bilden einen Kern der Bildpunkte. Für jeden Kern der Bildpunkte ist die Routine beschaffen, um die Anzahl der Bildpunkte RPi,j mit dem ersten Farbwert und die Anzahl der Bildpunkte RPi,j mit einem zweiten Farbwert zu zählen. Für einen zu erkennenden schwarzen Bildfehler muß wenigstens ein erster Prozentsatz der Bildpunkte innerhalb des Kerns den ersten Farbwert besitzen, während wenigstens ein zweiter Prozentsatz der Bildpunkte, die den Kern umgeben, den zweiten Farbwert besitzen muß. Wenn für jeden Kern kein schwarzer Bildfehler erkannt wird, wird die Größe des Kerns erweitert. Falls z. B. RPα0,β0 er Keimbildpunkt ist, wobei α0 und β0 Indizes sind, umfaßt ein erster durch die Routine überprüfter Kern die Bildpunkte RPα1,β1, wobei ein Index α1 in einem Bereich von α0 - 1 bis α0 + 1 liegt, während ein Index β1 in einem Bereich von β0 - 1 bis β0 + 1 liegt; ein zweiter überprüfter erweiterter Kern umfaßt die Bildpunkte RPα2,β2, wobei ein Index α2 in einem Bereich von a0 - 2 bis a0 + 2 liegt, während ein Index β2 in einem Bereich von β0 - 2 bis β0 + 2 liegt usw. Die Routine beendet das Erweitern jedes Kerns, der nach schwarzen Bildfehler überprüft wird, wenn die Anzahl der darin enthaltenen Bildpunkte RPi,j mit dem ersten Farbwert kleiner als t(2k - 1)² ist, wobei k die Anzahl ist, wie oft der Kern erweitert worden ist, während t ein Schwellenparameter ist. Ein schwarzer Bildfehler wird durch die Routine erkannt, falls:
- (i) die Anzahl der Bildpunkte RPi,j mit der zweiten Farbe im k-ten Kern größerer als oder gleich 8tk ist; und
- (ii) die Anzahl der Bildpunkte mit der ersten Farbe größer als oder gleich t(2k - 1)² ist.
- Wenn durch die Routine ein schwarzer Bildfehler identifiziert wird, werden sein entsprechendes Größenelement und seine entsprechenden Adressenelemente in einer Anordnung Ja aufgezeichnet, so daß er nicht zu der Erzeugung des Ausgangsbildes beiträgt.
- Die Routine kann für verschiedene erste und zweite Farben wiederholt werden, wie sie z. B. durch einen Benutzer des Systems 1 spezifiziert werden; die ersten und zweiten Farben, auf die oben Bezug genommen wurde, sind für die Verwendung durch die Routine z. B. Schwarz bzw. Weiß. Außerdem können erste und zweite Prozentsätze durch den Benutzer abhängig vom Bildinhalt auswählbar sein; in der Praxis sind der erste und zweite Prozentsatz normalerweise auf 85% gesetzt.
- Der Parameter t ist einstellbar, um einen besten Kompromiß zwischen der Beseitigung der Bildfehler und der falschen Erkennung von unverfälschten Merkmalen, die den Bildpunkten RPi,j enthalten sind, zu erhalten.
- In einer weiteren alternativen Ausführungsform der Erfindung enthält die Decodierungsfunktion 44 eine Identifikationsroutine für weiße Bildfehler, die beschaffen ist, um die Anordnung der Bildpunkte RPi,j zu durchsuchen, um zu identifizieren, wo die Grenzen zwischen benachbarten Bildpunkten mit voneinander verschiedenem Farbwert darin auftreten; die durch die Routine durchsuchten Grenzen sind zu regelmäßigen geometrischen Formen in einem aus den Bildpunkten RPi,j erzeugten Bild äquivalent. In der Praxis enthalten viele Bilder keine Merkmale, die regelmäßige geometrische Formen besitzen, z. B. besitzt ein Bild eines menschlichen Gesicht normalerweise kontinuierlich gekrümmte Merkmale. Wenn ein aus den Bildpunkten RPi,j erzeugtes Bild Merkmale mit 90º-Winkel enthält, zeigen diese Merkmale weiße Bildfehler potentiell an.
- Die Routine ist beschaffen, um eine oder mehrere Schablonen aus benachbarten Bildpunktwerten mit den Anordnungen der Bildpunkte RPi,j zu korrelieren; die Schablonen enthalten z. B. eine Auswahl von Eckmerkmalen in einer Vielzahl von verschiedenen Winkelorientierungen. Wenn die Korrelation von wenigstens einer der Schablonen mit einer ausgewählten Gruppierung von Bildpunkten RPi,j auftritt, zeichnet die Routine dieses als einen potentiellen weißen Bildfehler anzeigend auf. Die Routine durchsucht dann die umgebenden Bildpunkte RPi,j in der Nähe der Bildpunkte, wo die Korrelation aufgetreten ist, um zu untersuchen, ob die Korrelation von anderen Schablonen mit den umgebenden Bildpunkten erreichbar ist oder nicht. Wenn die Anzahl der Schablonen, die korreliert sind, eine im voraus definierte Grenze überschreitet, identifiziert die Routine die Bildpunkte, die mit den Schablonen korreliert sind, als einen weißen Bildfehler bildend, wobei sie sie als Bildfehlerdaten in einer Anordnung La aufzeichnet, so daß sie nicht verwendet werden, wenn ein Bild aus den Bildpunkten RPi,j wiedergewonnen wird.
- Die in der Anordnung La verglichenen Bildfehlerdaten können später in der Decodierungsfunktion 44 verwendet werden, um sie mit der Anordnung der Bildpunkte RPi,j zu korrelieren, um die Orte darin zu finden, wo die weißen Bildfehler enthalten sein können, um die sich aus der Datenverfälschung ergebenden Fehler wenigstens teilweise zu korrigieren.
- In einer alternativen Ausführungsform der Erfindung können anstatt der Reed-Muller-Codierung andere Typen der zusätzlichen Codierung verwendet werden, z. B. die Reed-Solomon-Codierung. Außerdem können die Steuerinformationen, die größeren quadratischen Elementen und größeren Lauflängenelementen zugeordnet sind, die in den Daten B codiert sind, häufiger in diese eingefügt sein, um die Robustheit der Daten B gegenüber Datenverfälschung weiter zu vergrößern.
Claims (33)
1. Datencodierungssystem (1), das Codierungsmittel (4), die
Eingangsdaten codieren, enthält, die umfassen:
(a) Analysemittel (26), die die Eingangsdaten analysieren und
entsprechende Ziffern erzeugen und so beschaffen sind, daß sie
Ziffern erzeugen, die sowohl für die Datenverteilungen als auch für
die Häufigkeiten des Auftretens der Daten repräsentativ sind; und
(b) Verarbeitungsmittel (28), die die Ziffern verarbeiten, um
codierte Ausgangsdaten zu schaffen, und so beschaffen sind, daß sie
Gruppierungen von Ziffern für die Verwendung bei der Erzeugung der
Ausgangsdaten auswählen,
wodurch entweder eine Datenkomprimierung in den Ausgangsdaten
und/oder eine Erhöhnung ihrer Robustheit gegenüber
Datenverfälschung geschaffen wird, dadurch gekennzeichnet, daß die
Analysemittel so beschaffen sind, daß sie die Eingangsdaten in einer
Anordnung von Ziffern darzustellen, und die Verarbeitungsmittel so
beschaffen sind, daß sie Gruppierungen von Ziffern mit wechselseitig
ähnlichem Wert in der Anordnung für die Verwendung beim
Erzeugen der codierten Ausgangsdaten identifizieren.
2. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß es Codierungsmittel (4), die die codierten Daten decodieren,
enthält, wobei diese Mittel (4) umfassen:
(a) Umsetzungsmittel (44), die die codierten Daten decodieren, um
Gruppierungen von Ziffern zu schaffen, die die Informationen über
die Datenverteilungen und die Häufigkeiten des Auftretens der
Daten, die in den codierten Daten codiert sind, bewahren;
(b) Interpretationsmittel (44, 46), die die Ziffern entsprechend den
Häufigkeiten des Auftretens interpretieren, um die Daten in
decodierter Form erneut zu erzeugen.
3. Codierungssystem nach Anspruch 2, dadurch gekennzeichnet,
daß die Decodierungsmittel (4) so beschaffen sind, daß sie auf die
Verfälschung der Zifferngruppierungsinformationen in den dort
empfangenen codierten Daten antworten, indem sie die wahlweise
erneute Übertragung der Zifferngruppierungsinformationen
anfordern und diese Informationen mit vorausgehend empfangenen nicht
verfälschten Informationen kombinieren, um die codierten Daten zu
decodieren, um die Daten in decodierter Form erneut zu erzeugen.
4. Codierungssystem nach Anspruch 2, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie die
Gruppierungen der Ziffern in die codierten Ausgangsdaten in einer
verschachtelten Reihenfolge codieren, die den Gruppierungen mit
zunehmend kleinerer Anzahl von Ziffern darin entsprechen, und die
Umsetzungsmittel (44) so beschaffen sind, daß sie überprüfen, daß
die Gruppierungen in einer verschachtelten Reihenfolge in den
codierten Daten codiert sind, um zu identifizieren, daß die
Gruppierungen nicht verfälscht sind.
5. Codierungssystem nach Anspruch 4, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) so beschaffen sind, daß sie die
codierten Daten filtern, um falsch verschachtelte Daten darin zu
identifizieren, und die Interpretationsmittel (44, 46) so beschaffen sind,
daß sie die falsch verschachtelten Daten nicht beachten, wenn die
Daten in codierter Form erneut erzeugt werden.
6. Codierungssystem nach Anspruch 2, dadurch gekennzeichnet,
daß die Analysemittel (26) Ziffernschätzmittel enthalten, die das
Auftreten benachbarter Ziffern schätzen, die in Verbindung mit
Gruppierungen von Ziffern auftreten, die durch die
Verarbeitungsmittel (28) ausgewählt worden sind, die aneinander grenzen, die
Verarbeitungsmittel (28) so beschaffen sind, daß sie in die codierten
Ausgangsdaten Schätzparameter aufnehmen, die die benachbarten
Ziffern anzeigen, und die Decodierungsmittel (4) so beschaffen sind,
daß sie die codierten Daten, die Schätzparameter enthalten,
decodieren und daraus die Anwesenheit benachbarter Ziffern für die
Verwendung bei der erneuten Erzeugung der Daten schätzen.
7. Codierungssystem nach Anspruch 2, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) so beschaffen sind, daß sie die
Gruppierungen der Ziffern zu durchsuchen, um verfälschte
Gruppierungen zu identifizieren, deren entsprechender Wert von demjenigen der
Ziffern verschieden ist, die zu ihnen benachbart sind, und die
Interpretationsmittel so beschaffen sind, daß sie die verfälschten
Gruppierungen nicht beachten, wenn die Daten in decodierter Form erneut
erzeugt werden.
8. Codierungssystem nach Anspruch 7, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) für Vergleichszwecke im voraus
definierte Ziffernverteilungen enthalten, die als Schablonen
bezeichnet werden, und so beschaffen sind, daß sie die Schablonen mit den
Gruppierungen der Ziffern zu korrelieren, um verfälschte
Gruppierungen der Ziffern zu identifizieren, und die Interpretationsmittel (44,
46) so beschaffen sind, daß sie die verfälschten Gruppierungen nicht
beachten, wenn die Daten in decodierter Form erneut erzeugt
werden.
9. Codierungssystem nach Anspruch 7, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) so beschaffen sind, daß sie nach
verfälschten Gruppierungen von Ziffern suchen, die einen
entsprechenden ersten Wert besitzen, indem die Ziffern unter Verwendung
zunehmend größerer Suchkerne gesucht werden, wobei verfälschte
Gruppierungen aus Ziffern identifiziert werden, wenn wenigstens ein
erster Schwellenprozentsatz der in dem Kern enthaltenen Ziffern
einen ersten Wert besitzt und wenigstens ein zweiter
Schwellenprozentsatz der an die Ziffern in dem Kern grenzenden Ziffern einen
zweiten Wert besitzt.
10. Codierungssystem nach Anspruch 9, dadurch gekennzeichnet,
daß die ersten und zweiten Schwellenprozentsätze 85% betragen.
11. Codierungssystem nach Anspruch 2, dadurch gekennzeichnet,
daß die Codierungsmittel (4) so beschaffen sind, daß sie eine am
häufigsten auftretende Datenverteilung in den Eingangsdaten
identifizieren und die Informationen über diese Verteilung in den codierten
Ausgangsdaten weglassen, und die Decodierungsmittel (4) so
beschaffen sind, daß sie die Ausgangsdaten decodieren und die am
häufigsten auftretende Verteilung aus ihrer Abwesenheit in den
Ausgangsdaten ableiten.
12. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie für die
Verwendung bei der Erzeugung der Ausgangsdaten Gruppierungen
von Ziffern identifizieren, die Ziffern umfassen, die in der Anordnung
aneinander grenzen.
13. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie die
Ziffern in jeder Gruppierung durch einen einzelnen entsprechenden
Gruppengrößenparameter in den codierten Ausgangsdaten
darstellen.
14. Codierungssystem nach Anspruch 13, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie
quadratische und lineare Gruppierungen der Ziffern auswählen.
15. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie die durch die
Anordnung der Ziffern dargestellten Eingangsdaten entsprenkeln,
indem isolierte Ziffern in der Anordnung identifiziert werden, deren
zugeordnete Werte zu denjenigen der ihnen benachbarten Ziffern
unähnlich sind, und daß sie die isolierten Ziffernwerte modifizieren,
um die Anzahl der in den Gruppierungen enthaltenen Ziffern zu
vergrößern und/oder die Anzahl der Gruppierungen, die für die
Darstellung der Eingangsdaten in den codierten Ausgangsdaten
erforderlich sind, zu verringern.
16. Codierungssystem nach Anspruch 15, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie die
Eingangsdaten in mehrere Zonen partitionieren und die jeder Zone
entsprechenden Ziffern entsprenkeln, indem ein für diese Zone im voraus
gewählter Entsprenkelungsprozeß verwendet wird.
17. Codierungssystem nach Anspruch 15, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie auf die Ziffern
wenigstens einen Entsprenkelungsprozeß mit einer Betriebsart 1,
einer Betriebsart 2 oder einer Betriebsart 3 anwenden.
18. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie nach
Zifferngruppierungen, die eine Anzahl von Ziffern enthalten, suchen,
wobei die Anzahl in einem im voraus definierten Bereich liegt, und sie
in den Ausgangsdaten codieren.
19. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie jede
Datenverteilung der Eingangsdaten in entsprechenden Ziffern unter
Verwendung der Entropiecodierung darstellen, indem wenigstens einigen
der Verteilungen relativ mehr oder weniger Ziffern mit nicht
vorgegebenen Werten dementsprechend, ob die Häufigkeit des Auftretens der
Verteilung innerhalb der Eingangsdaten im Vergleich zu der anderer
Verteilungen relativ niedriger oder höher ist, abhängig davon
zugewiesen werden, daß jede Datenverteilung durch die
Verarbeitungsmittel, die die Ziffern suchen, in den Ausgangsdaten eindeutig codiert
wird.
20. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie jede
Datenverteilung der Eingangsdaten unter Verwendung der
Cluster-Codierung darstellen, indem wenigstens einigen der Verteilungen relativ
mehr oder weniger Ziffern mit nicht vorgegebenen Werten
dementsprechend, ob die Häufigkeit des Auftretens der Verteilung innerhalb
der Eingangsdaten im Vergleich zu der anderer Verteilungen relativ
niedriger oder höher ist, abhängig davon zugewiesen werden, daß
(a) jede Datenverteilung durch die Verarbeitungsmittel, die die
Ziffern suchen, in den Ausgangsdaten eindeutig codiert wird;
und
(b) jede Datenverteilung durch eine entsprechende
Ziffernkombination dargestellt wird, die sich von der der Datenverteilungen, die
am häufigsten in Verbindung mit ihr auftreten, durch sowenig
Unterschiede des Ziffernwertes wie möglich unterscheidet.
21. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie jede
Datenverteilung in den Eingangsdaten, die am häufigsten auftritt, durch
das Zuordnen eines vorgegebenen Wertes darstellen, und die
Verarbeitungsmittel (28) so beschaffen sind, daß sie:
(i) derartige vorgegebene Werte weglassen, wenn
Zifferngruppierungen ausgewählt werden, die in den Ausgangsdaten zu codieren
sind, um eine verbesserte Datenkomprimierung zu schaffen; und
(ii) Kopfinformationen in die Ausgangsdaten aufnehmen, die die
Datenverteilung definieren, die am häufigsten auftritt;
wobei die Decodierungsmittel (4) so beschaffen sind, daß sie die
Datenverteilung, die am häufigsten auftritt, aus den
Kopfinformationsdaten erneut erzeugen, wenn sie die Ausgangsdaten in
decodierter Form erneut erzeugen.
22. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie eine
zusätzliche Vorwärtsfehlerkorrekturcodierung auf die codierten
Ausgangsdaten anwenden, und die Umsetzungsmittel (44) so
beschaffen sind, daß sie die codierten Daten unter Verwendung der
Maschendecodierungsmittel (50) decodieren.
23. Codierungssystem nach Anspruch 22, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie die
Reed-Muller-Codierung anwenden.
24. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Verarbeitungsmittel (28) so beschaffen sind, daß sie einen
oder mehrere Synchronisationscodes in die codierten Daten
aufnehmen, um die erneute Synchronisation der Umsetzungsmittel (44) mit
den Daten nach dem Verlust oder dem Fehlen der Synchronisation
zu unterstützen.
25. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26) so beschaffen sind, daß sie diejenigen
Eingangsdaten analysieren, die Bildfarbinformationen umfassen, und
die Informationen in die Ziffern aufnehmen, die Verarbeitungsmittel
(28) so beschaffen sind, daß sie Gruppierungen der Ziffern für die
Verwendung auswählen, um codierte Ausgangsdaten zu schaffen, die
die Farbinformationen enthalten, und die Decodierungsmittel (4) so
beschaffen sind, daß sie die codierten Daten, die die
Farbinformationen enthalten, empfangen, decodieren und aus ihnen die
Eingangsdaten erneut erzeugen, die ihre Farbinformationen enthalten.
26. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Analysemittel (26), die Verarbeitungsmittel (28), die
Umsetzungsmittel (44) und die Interpretationsmittel (44, 46) durch
Computer-Software implementiert sind.
27. Codierungssystem nach Anspruch 1, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) so beschaffen sind, daß sie:
(i) Fälle von doppelter Decodierung aus dem mehrfachen Setzen der
decodierten Ziffern erfassen, die die Daten Verfälschung anzeigen;
und
(ii) selektiv Ziffern nicht beachten, die die doppelte Decodierung
verursachen, wenn die codierten Daten in decodierter Form
erneut erzeugt werden.
28. Codierungssystem nach Anspruch 27, dadurch gekennzeichnet,
daß die Umsetzungsmittel (44) so beschaffen sind, daß sie
Zifferngruppierungen, die die doppelte Decodierung veranlassen, mit bereits
erzeugen Ziffern korrelieren, um alternative zuweisbare Ziffern für die
Ersetzung zu identifizieren.
29. Datencodierungssystem nach Anspruch 1, in dem:
(a) die Analysemittel (26) so beschaffen sind, daß sie die
Eingangsdaten als quantisierte Werte in der Anordnung
darstellen, die Häufigkeiten des Auftretens für jeden der Werte
bestimmen und die Anordnung der Werte in eine Anzahl von digitalen
Zahlen umsetzen, die die entsprechenden Häufigkeiten des
Auftretens anzeigen; und
(b) die Verarbeitungsmittel (28) so beschaffen sind, daß sie:
(i) die Anordnung durchsuchen, um entsprechend einer im
voraus angeordneten Folge gleichverteilte Unteranordnungen der
Ziffern der digitalen Zahlen zu identifizieren, denen nicht der
Wert zugeordnet ist, der die größte Häufigkeit des Auftretens
besitzt;
(ii) jeder identifizierten Unteranordnung Positions- und
Größenparameter zuordnen; und
(iii) die codierten Ausgangsdaten in Form der Häufigkeit des
Auftretens der Werte und der Positions- und Größenparameter
der identifizierten Unteranordnungen bereitstellen.
30. Codierungssystem nach Anspruch 28, dadurch gekennzeichnet,
daß es Decodierungsmittel (4), die die codierten Daten decodieren,
enthält, wobei die Mittel (4) umfassen:
(a) Umsetzungsmittel (44), die die Datenwerte bereitstellen, die auf
den Eingangsdatenwert mit der höchsten Häufigkeit des
Auftretens voreingestellt sind; und
(b) Interpretationsmittel (44, 46), die die einzelnen voreingestellten
Werte in Eingangsdatenwerte mit weniger als der höchsten
Häufigkeit des Auftretens in Übereinstimmung mit den Werten und
den Positions- und Größenparametern der identifizierten
Unteranordnungen ändern, um die codierten Daten in decodierter
Form erneut zu erzeugen.
31. Verfahren zum Codieren der Eingangsdaten in einem
Datencodierungssystem (1), um codierte Ausgangsdaten zu schaffen,
wobei das Codierungssystem Analysemittel (26), die die
Eingangsdaten analysieren und sie in Form von Ziffern darstellen, und
Verarbeitungsmittel (28), die die Ziffern verarbeiten, um die
Ausgangsdaten zu erzeugen, umfaßt, wobei das Verfahren die folgenden Schritte
umfaßt:
(a) Ausführen einer Häufigkeitsanalyse an den Eingangsdaten, um
sowohl die Datenverteilungen als auch die Häufigkeiten des
Auftretens der Daten in Form von Ziffern darzustellen, um die
Datenkomprimierung und/oder die vergrößerte Robustheit
gegenüber Verfälschung zu erhalten, und
(b) Verarbeiten der Ziffern, um Gruppierungen von Ziffern für die
Verwendung bei der Erzeugung der Ausgangsdaten
auszuwählen,
dadurch gekennzeichnet, daß der Schritt (a) ausgeführt wird durch
(i) Darstellen der Eingangsdaten als eine Anordnung quantisierter
Werte,
(ii) Bestimmen der Häufigkeit des Auftretens für jeden der Werte,
und
(iii) Umsetzen der Anordnung der Werte in eine Anordnung digitaler
Zahlen, die die entsprechenden Häufigkeiten des Auftretens
anzeigen;
und daß der Schritt (b) ausgeführt wird durch
(i) Durchsuchen der Anordnung, um gleichverteilte
Unteranordnungen der Ziffern der digitalen Zahlen zu identifizieren, denen der
Wert mit der größten Häufigkeit des Auftretens nicht zugeordnet
ist;
(ii) Zuordnen von Positions- und Größenparametern zu jeder
identifizierten Unteranordnung;
(iii) Wiederholen der zwei vorhergehenden Schritte für weitere
gleichverteilte Unteranordnungen, wobei die vorausgehend
identifizierten Unteranordnungen in Übereinstimmung mit einer im
voraus angeordneten Folge weggelassen werden; und
(iv) Bereitstellen der codierten Daten in Form der Häufigkeiten des
Auftretens der Werte und der Positions- und Größenparameter
der identifizierten Unteranordnungen.
32. Verfahren nach Anspruch 31, das ferner den Schritt des
Verarbeitens der codierten Ausgangsdaten umfaßt, um decodierte
Daten zu erzeugen, indem anfangs voreingestellte Datenwerte
bereitgestellt werden, und dann die einzelnen voreingestellten Werte auf
die Eingangsdatenwerte mit weniger als der höchsten Häufigkeit des
Auftretens in Übereinstimmung mit den Werten und den Positions-
und Größenparametern der identifizierten Unteranordnungen
geändert werden.
33. Verfahren nach Anspruch 32, bei dem die voreingestellten Werte
anfangs auf den Eingangsdatenwert gesetzt werden, der die höchste
Häufigkeit des Auftretens besitzt, und dann die voreingestellten
Werte in Eingangsdatenwerte mit weniger als der höchsten Häufigkeit
des Auftretens in Übereinstimmung mit den Werten und den
Position- und Größenparametern der identifizierten Unteranordnungen
geändert werden.
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
GB9714124A GB2327003A (en) | 1997-07-04 | 1997-07-04 | Image data encoding system |
PCT/GB1998/001877 WO1999001981A1 (en) | 1997-07-04 | 1998-06-26 | Data encoding system |
Publications (2)
Publication Number | Publication Date |
---|---|
DE69810070D1 DE69810070D1 (de) | 2003-01-23 |
DE69810070T2 true DE69810070T2 (de) | 2003-09-04 |
Family
ID=10815366
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
DE69810070T Expired - Lifetime DE69810070T2 (de) | 1997-07-04 | 1998-06-26 | Datencodierungssystem |
Country Status (9)
Country | Link |
---|---|
US (1) | US6477277B1 (de) |
EP (1) | EP0929969B1 (de) |
JP (1) | JP4173918B2 (de) |
KR (1) | KR100549976B1 (de) |
AU (1) | AU742625B2 (de) |
CA (1) | CA2264742C (de) |
DE (1) | DE69810070T2 (de) |
GB (2) | GB2327003A (de) |
WO (1) | WO1999001981A1 (de) |
Families Citing this family (18)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP3853115B2 (ja) * | 1999-08-27 | 2006-12-06 | シャープ株式会社 | 画像符号化装置、画像復号化装置、画像符号化方法及び画像復号化方法 |
US8677423B2 (en) | 2000-12-28 | 2014-03-18 | At&T Intellectual Property I, L. P. | Digital residential entertainment system |
US8601519B1 (en) | 2000-12-28 | 2013-12-03 | At&T Intellectual Property I, L.P. | Digital residential entertainment system |
US7698723B2 (en) | 2000-12-28 | 2010-04-13 | At&T Intellectual Property I, L.P. | System and method for multimedia on demand services |
US6934679B2 (en) * | 2002-03-07 | 2005-08-23 | Microsoft Corporation | Error resilient scalable audio coding |
US7082479B2 (en) * | 2002-06-19 | 2006-07-25 | Eastman Kodak Company | System and method for maintaining synchronized data transfer using a plurality of different control words individually indicative of the same single event |
KR100530654B1 (ko) * | 2002-10-26 | 2005-11-22 | 삼성전자주식회사 | 이미지 데이터 압축방법 |
KR100566122B1 (ko) * | 2003-09-15 | 2006-03-30 | (주) 멀티비아 | 모바일 디바이스용 정지영상 압축 방법 |
EP1695559A1 (de) * | 2003-12-15 | 2006-08-30 | Matrixview Limited | Komprimieren von bilddaten |
US8543717B2 (en) * | 2003-12-23 | 2013-09-24 | Eastman Kodak Company | Retaining channel synchronization through use of alternate control characters |
US7675979B1 (en) * | 2004-07-20 | 2010-03-09 | Marvell International Ltd. | Methods, algorithms, software, circuits, architectures, and systems for improved communications over cyclostationary channels |
US20060142419A1 (en) * | 2004-10-14 | 2006-06-29 | Jingjing Xu | Cured compositions containing fine magnetic particles and a process for preparing same and their use |
US7516389B2 (en) * | 2004-11-04 | 2009-04-07 | Agere Systems Inc. | Concatenated iterative and algebraic coding |
EP2035030A2 (de) * | 2006-05-17 | 2009-03-18 | Stryker Corporation | Verwendung löslicher morphogener proteinkomplexe zur behandlung von knorpeldefekten |
US8237731B2 (en) * | 2008-09-23 | 2012-08-07 | Texas Instruments Incorporated | System and method for grouped pixel addressing |
KR101258174B1 (ko) | 2011-06-17 | 2013-04-25 | 한국항공대학교산학협력단 | 자동 인코딩 탐지 시스템 |
JP6668964B2 (ja) * | 2016-06-13 | 2020-03-18 | コニカミノルタ株式会社 | 画像形成システム、画像データ送信部および画像データ伝送方法 |
CN113740066B (zh) * | 2021-11-08 | 2022-02-08 | 中国空气动力研究与发展中心设备设计与测试技术研究所 | 一种压缩机轴承早期故障检测方法 |
Family Cites Families (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
DE1960617A1 (de) * | 1969-07-11 | 1971-01-28 | Zanussi A Spa Industrie | Spannungsstabilisator |
US4682215A (en) * | 1984-05-28 | 1987-07-21 | Ricoh Company, Ltd. | Coding system for image processing apparatus |
US5341440A (en) * | 1991-07-12 | 1994-08-23 | Earl Joseph G | Method and apparatus for increasing information compressibility |
US5471207A (en) * | 1994-02-23 | 1995-11-28 | Ricoh Company Ltd. | Compression of palettized images and binarization for bitwise coding of M-ary alphabets therefor |
US5659631A (en) * | 1995-02-21 | 1997-08-19 | Ricoh Company, Ltd. | Data compression for indexed color image data |
WO1997003516A1 (en) * | 1995-07-11 | 1997-01-30 | Telefonaktiebolaget Lm Ericsson (Publ) | Video coding |
-
1997
- 1997-07-04 GB GB9714124A patent/GB2327003A/en not_active Withdrawn
-
1998
- 1998-06-26 AU AU81228/98A patent/AU742625B2/en not_active Ceased
- 1998-06-26 DE DE69810070T patent/DE69810070T2/de not_active Expired - Lifetime
- 1998-06-26 CA CA002264742A patent/CA2264742C/en not_active Expired - Fee Related
- 1998-06-26 WO PCT/GB1998/001877 patent/WO1999001981A1/en active IP Right Grant
- 1998-06-26 KR KR1019997001840A patent/KR100549976B1/ko not_active IP Right Cessation
- 1998-06-26 GB GB9904338A patent/GB2332330B/en not_active Expired - Fee Related
- 1998-06-26 EP EP98930955A patent/EP0929969B1/de not_active Expired - Lifetime
- 1998-06-26 US US09/254,146 patent/US6477277B1/en not_active Expired - Lifetime
- 1998-06-26 JP JP50662299A patent/JP4173918B2/ja not_active Expired - Lifetime
Also Published As
Publication number | Publication date |
---|---|
JP2001500346A (ja) | 2001-01-09 |
DE69810070D1 (de) | 2003-01-23 |
GB2332330A (en) | 1999-06-16 |
GB2332330B (en) | 2002-01-16 |
AU742625B2 (en) | 2002-01-10 |
AU8122898A (en) | 1999-01-25 |
GB2327003A (en) | 1999-01-06 |
KR100549976B1 (ko) | 2006-02-08 |
JP4173918B2 (ja) | 2008-10-29 |
EP0929969A1 (de) | 1999-07-21 |
WO1999001981A1 (en) | 1999-01-14 |
GB9714124D0 (en) | 1997-09-10 |
CA2264742A1 (en) | 1999-01-14 |
US6477277B1 (en) | 2002-11-05 |
EP0929969B1 (de) | 2002-12-11 |
CA2264742C (en) | 2007-03-27 |
GB9904338D0 (en) | 1999-04-21 |
KR20000068459A (ko) | 2000-11-25 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
DE69810070T2 (de) | Datencodierungssystem | |
DE69222766T2 (de) | System zur adaptiven kompression der blockgrössen eines bildes | |
DE68926876T2 (de) | Vorrichtung zur Vektorquantisierung von Bildern | |
DE3855648T2 (de) | Verfahren und vorrichtung für eine hierarchische kodierung zum wirksamen übertragen von bildfolgen | |
DE3789273T2 (de) | Kodierungssystem zur Reduktion der Redundanz. | |
DE19844752B4 (de) | Ein verbessertes Kompressions- und Dekompressionssystem mit reversiblen Wavelets und verlustbehafteter Rokonstruktion | |
DE69323986T2 (de) | Vorrichtung und Verfahren zur Bildverarbeitung | |
DE69130214T2 (de) | Bilddatenkompression mit adaptiver Blockgrössenauswahl | |
DE69611573T2 (de) | Auflösungserhöhung mit Standardvergleichsmustern | |
DE69227533T2 (de) | Bildverarbeitungsverfahren und -gerät | |
US20030123729A1 (en) | Coder matched layer separation for compression of compound documents | |
DE69031638T2 (de) | System zum Übertragen von Bildinformation | |
DE19506164A1 (de) | Verfahren zum Komprimieren eingegebener Symbole in Codeworte | |
EP0698316B1 (de) | Verfahren zum Übertragen von Bildern mit ungleichem Fehlerschutz | |
DE19534730A1 (de) | Verfahren zum Codieren und Decodieren von Daten | |
DE19739266A1 (de) | Verfahren und Vorrichtung zum Kodieren binärer Formen | |
DE2340230A1 (de) | Verfahren und vorrichtung zur vorhersage des signalpegelwertes eines nachrichtenelementes | |
DE69620932T2 (de) | Verfahren zum Kodieren und Dekodieren von Bewegtbildsignalen | |
EP0981896B1 (de) | Verlustfreie bildkompression mit baumkodierung | |
DE3751684T2 (de) | Musterverarbeitung | |
DE3688919T2 (de) | Verfahren und Vorrichtung zur Bilddatenkompression. | |
DE60200377T2 (de) | Datenkompression | |
WO2022023175A1 (de) | Verfahren und vorrichtung zur auswertung von matrixcodes | |
DE69226307T2 (de) | Digitaler Datendekodierer mit durch Fehlernachricht beeinflusster Übertragungsmodusselektion | |
DE69729433T2 (de) | Kodierte Modulation für Konstellationen, welche weniger Bits pro Symbol haben, als vom Kodierungsschema verlangt wird |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
8364 | No opposition during term of opposition | ||
8327 | Change in the person/name/address of the patent owner |
Owner name: VOCALCOMM GROUP, LLC, WILMINGTON, DEL., US |