DE2556803B1

DE2556803B1 - Method for data compression of binary coded image signals

Info

Publication number: DE2556803B1
Application number: DE19752556803
Authority: DE
Inventors: Dieter Dipl-Ing Preuss
Original assignee: Dr Ing Rudolf Hell GmbH
Current assignee: Dr Ing Rudolf Hell GmbH
Priority date: 1975-12-17
Filing date: 1975-12-17
Publication date: 1977-03-24

Description

In Fig 1 ist ein Beispiel für ein Prädiktionsmuster dargestellt Die Anordnung der Bildpunkte Xi bis x7 gibt an, in welcher Form das Umfeld des gerade abzutastenden Bildpunktes xo berücksichtigt wird. Im Prinzip handelt es sich um ein bekanntes Prädiktionsmuster, wie es z. B. bei der US-Patentschrift 38 13485 in Fig. 3B vorgeschlagen worden ist. Aus der Informationsverteilung innerhalb des Prädiktionsmusters wird die Vorhersage des gerade abzutastenden Bildpunktes abgeleitet Die Informationswerte der Umfeldbildpunkte xl bis x7 werden gespeichert oder verzögert, und mit Hilfe eines später dargestellten Prädiktors wird der Vorhersagewert bestimmt Anschließend wird der vorhergesagte Wert mit dem tatsächlich bei der Abtastung vorgefundenen Informationswert verglichen.An example of a prediction pattern is shown in FIG Arrangement of the pixels Xi to x7 there in what form that Environment of the pixel xo to be scanned is taken into account. Acts in principle it is a known prediction pattern, as it is e.g. B. in the US patent 38 13485 in Figure 3B. From the information distribution within of the prediction pattern is the prediction of the pixel to be scanned Derived The information values of the surrounding image points xl to x7 are stored or delayed, and with the help of a predictor presented later, the predicted value Then the predicted value is determined with the actual value during the scan found information value compared.

Um eine solche Prädiktion durchführen zu können, muß vorab untersucht werden, wie groß die Wahrscheinlichkeit für die Richtigkeit der Vorhersage für eine repräsentative Vorlage ist Zu diesem Zweck wurde mit einem Prädiktionsmusterschema von vier Bildpunkten Xi bis X4 gemäß Fig.2 die Wahrscheinlichkeit für sechszehn verschiedene Prädiktionsmuster untersucht F i g. 3 zeigt eine Tabelle, wie hoch die Wahrscheinlichkeit für die Aussage des Prädiktionswertes bp im Falle einer Wetterkarte war. Spalte 1 zeigt die Anzahl der Zustände S>, Spalte 2 die jeweiligen Konfigurationen der Prädiktionsmuster, wobei x= 0 ein weißer Bildpunkt und x= 1 ein schwarzer Bildpunkt ist In Spalte 3 ist die jeweilige Wahrscheinlichkeit für Weiß und in Spalte 4 die Wahrscheinlichkeit für Schwarz angegeben. Aus der größeren Wahrscheinlichkeit ergibt sich dann der Prädiktionswert bp, für den auch die logische Funktion Xp = (X1 & X2) V(X2 & X3) V(X3 & V(XI & X4) In F i g. 5 ist ein Prinzipschaltbild zur Erzeugung eines sogenannten Fehlerbildes angegeben. Das Signal des gerade abgetasteten Bildpunktes xo gelangt über eine Leitung 7 zu einem Vergleicher 8, an dessen anderem Eingang der Prädiktionswert bp liegt Der Prädiktionswert bp wurde gemäß F i g. 4 aus den Werten Xi bis Xn gewonnen. Damit die Werte xl bis Xn gleichzeitig an der Prädiktorstufe P anliegen, wurden diese von der Eingangsleitung 7 ankommend auf ein Verzögerungsglied Vgegeben. Wenn die Helligkeitswerte von x0 und bp im Vergleicher 8 übereinstimmen, wird ein binäres Fehlersignal x, auf den Wert logisch Null gesetzt Stimmen xo und xp nicht überein, so wird xf auf logisch 1 gesetzt Das auf diese Weise erzeugte Prädiktionsfehlerbild wird anstelle des ursprünglichen Bildes in codierter Form übertragen. Die Bestimmung des Wertes bp stützt sich auf die statistischen Abhängigkeiten von dem Bildpunkt xo und den Nachbarbildpunkten xl bis xn, die in den Wahrscheinlichkeiten der Spalten 4 und 5 der gelten muß. In order to be able to carry out such a prediction, it must be examined beforehand how big the probability of the prediction being accurate for a To this end, a representative template was used with a prediction pattern scheme of four pixels Xi to X4 according to FIG. 2 the probability for sixteen various prediction patterns examined FIG. 3 shows a table of how high the probability for the statement of the prediction value bp in the case of a weather map was. Column 1 shows the number of states S>, column 2 the respective configurations the prediction pattern, where x = 0 a white pixel and x = 1 a black pixel is In column 3 is the respective probability for white and in column 4 the Probability for black given. Resulting from the greater probability then the prediction value bp, for which the logical function Xp = (X1 & X2) V (X2 & X3) V (X3 & V (XI & X4) In Fig. 5 is a block diagram specified for generating a so-called error pattern. The signal of the one just sampled Image point xo arrives via a line 7 to a comparator 8, at the other one Input of the prediction value bp is The prediction value bp was determined according to FIG. 4th obtained from the values Xi to Xn. So that the values xl to Xn at the same time Predictor level P are present, these were incoming from the input line 7 a delay element V is given. If the brightness values of x0 and bp in the comparator 8 match, a binary error signal x is set to the value logic zero If xo and xp do not match, then xf is set to logical 1, and that on this Manner generated prediction error image is instead of the original image in transmitted in coded form. The determination of the value bp is based on the statistical Dependencies on the pixel xo and the neighboring pixels xl to xn, which are shown in the probabilities of columns 4 and 5 which must apply.

In der F i g. 4 ist ein Schaltungsbeispiel für einen Prädiktor angegeben, der diese logische Verknüpfung erfüllt Die Werte xl bis X4 werden auf UND-Tore 2 bis 5 gegeben, wobei die Werte x2 und X4 in negierter Form an die Tore 3,4 und 5 gelangen. Die Ausgänge der Tore 2 bis 5 sind gemäß der logischen Verknüpfung an ein ODER-Tor 6 geschaltet, an dessen Ausgang der Vorhersagewert erscheint. In FIG. 4 shows a circuit example for a predictor, which fulfills this logical link The values xl to X4 are set to AND gates 2 to 5, with the values x2 and X4 in negated form at gates 3, 4 and 5 reach. The outputs of gates 2 to 5 are on according to the logic connection an OR gate 6 is switched, at the output of which the predicted value appears.

Die eigentliche Codierung wird in zwei Schritten durchgeführt Zunächst wird der gerade abgetastete Bildpunkt xo mit einem Prädiktionswert Xp verglichen, der aus n benachbarten und bereits abgetasteten Bildpunkten xl bis gewonnen wird. Die Punkte xi bis in können sowohl der laufenden Zeile als auch einer oder mehreren vorangegangenen Zeilen entnommen werden. The actual coding is done in two steps. First of all the currently scanned pixel xo is compared with a prediction value Xp, which is obtained from n neighboring and already scanned image points xl bis. The points xi to in can be both the current line and one or more previous lines.

Fig 3 zum Ausdruck kommen. Das Prädiktionsfehlerbild enthält noch die gesamte Information des ursprünglichen Bildes, die jedoch in der Verteilung der Prädiktionsfehler steckt Diese Verteilung ist in F i g. 6 als Folge der Zustände der Lage der Prädiktionsfehler angegeben. Die Pfeile geben an, wo ein Fehler in der Voraussage vorhanden war. Im zweiten Schritt des Codierungsprozesses wird die Lage der Prädiktionsfehler innerhalb der Zeile mittels einer eindimensionalen Lauflängencodierung übertragen. Dies geschieht gemäß der Erfindung dadurch, daß die Abstände aufeinanderfolgender Prädiktionsfehler für die einzelnen Zustände getrennt codiert und übertragen werden. Vom Beginn der Zeile gerechnet, erscheint z. B. in F i g. 6 fünfmal der Zustand »O«, bis der erste Prädiktionsfehler in diesem Zustand auftritt, d. h, es muß die Lauflänge 5 übertragen werden.Fig 3 are expressed. The prediction error image still contains all the information in the original image, but in the distribution the prediction error is stuck This distribution is shown in FIG. 6 as a result of the states the location of the prediction errors. The arrows indicate where there is an error in the prediction was there. In the second step of the coding process, the Location of the prediction errors within the line by means of one-dimensional run length coding transfer. This is done according to the invention in that the distances are consecutive Prediction errors for the individual states are coded and transmitted separately. Calculated from the beginning of the line, z. B. in Fig. 6 five times the state "O" until the first prediction error occurs in this state; h, it has to be Run length 5 are transferred.

Der Zustand »1« erscheint dreimal bis zum ersten Prädiktionsfehler in diesem Zustand, und die zu übertragende Lauflänge beträgt also 3. Die Lauflänge beginnt beim letzten Prädiktionsfehler in dem betrachteten Zustand bzw. am Zeilenanfang und endet beim nächsten Prädiktionsfehler innerhalb desselben Zustandes. Gezählt wird aber nur, wie oft der entsprechende Zustand vorgekommen ist Zur Codierung der Lauflänge kann jeder beliebige Lauflängencode verwendet werden, der auch für eine eindimensionale Lauflängencodierung geeignet ist, z. B. der Code in F i g. 7.The state »1« appears three times up to the first prediction error in this state, and the run length to be transmitted is thus 3. The run length begins with the last prediction error in the observed state or at the beginning of the line and ends with the next prediction error within the same state. Counted but only shows how often the corresponding state has occurred. For coding the Run-length any run-length code can be used that is also applicable to a one-dimensional run length coding is suitable, e.g. B. the code in FIG. 7th

Zweckmäßigerweise wird die elementare Blocklänge n der Codeworte für jeden Zustand so gewählt, daß sie optimal an die Wahrscheinlichkeitsverteilung der Lauflängen angepaßt ist Dann wird die erzielte Einsparung z. B. an Übertragungszeit am größten sein.The elementary block length n of the code words for each state is chosen so that it optimally fits the probability distribution of the Run lengths is adapted. Then the savings achieved are z. B. transmission time be greatest.

F i g. 8 zeigt ein Beispiel für das Übertragungsformat einer Zeile. Hierbei gilt LCWm = Lauflängencodeworte für den Zustand Sn? Der Buchstabe »T« bedeutet ein Trennzeichen und die Bezeichnung Ze das Zeilenende. F i g. 8 shows an example of the transmission format of one line. Here, LCWm = run length code words for the state Sn? The letter "T" means a separator and the term Ze the end of the line.

Als Trennzeichen und Zeilenendezeichen müssen Codeworte gewählt werden, die nicht als Lauflängencodewort vorkommen können. Die Festlegung geeigneter Codeworte für die Lauflängen und für die Sonderzeichen soll nicht Gegenstand dieser Erfindung sein. Es können dafür alle bekannten Lauflängencodes verwendet werden.Code words must be selected as separators and line end characters, which cannot occur as a run length code word. The definition of suitable code words for the run lengths and for the special characters should not be the subject of this invention be. All known run length codes can be used for this.

Das beschriebene Codierungssystem läßt sich hinsichtlich des technischen Aufwandes vereinfachen, wenn bei der Lauflängencodierung der Prädiktionsfehler nicht alle überhaupt möglichen Zustände der Bildpunkte x, bis Xn unterschieden werden, sondern mehrere Zustände zu einem neuen Zustand zusammengefaßt werden. Ein solches vereinfachtes System ist in F i g. 9 dargestellt Hierbei wurden für das Beispiel alle vom Zustand »o« verschiedenen Zustände zu einem neuen Zustand »O« zusammengefaßt Alle ursprünglichen Zustände, die zu dem neuen Zustand gehören, werden beim Abzählen der Lauflängen nicht mehr unterschieden. Mit der Vereinfachung durch Zusammenfassen von Zuständen ist jedoch eine Verringerung des Reduktionsfaktors verbunden. Auf diese Weise kann ein geeigneter Kompromiß zwischen schaltungstechnischem Aufwand und Reduktionsgewinn erzielt werden. Im unteren Teil der F i g. 9 ist die Zusammenfassung der von 0 verschiedenen Zustände als Lauflänge dargestellt In Fig. 10 ist eine vereinfachte Lauflängencodierung der Prädiktionsfehler angegeben. Um die Codierung in mehreren Schieberegisterdurchläufen bzw. die Speicherung aller Lauflänge einer Zeile im Decoder zu vermeiden, kann die in F i g. 10 gezeigte vereinfachte Lauflängencodierung verwendet werden. Dabei wird die Lage der Prädiktionsfehler in der Reihenfolge codiert und gesendet, in der sie in der Zeile auftreten Das Lauflängencodewort gibt sowohl den Zustand an, bei dem der nächste Prädiktionsfehler auftritt als auch die Zahl der Zustände zwischen dem letzten und dem neuen Prädiktionsfehler. Diese Lauflängencodierung kann auch mit der Vereinfachung durch Zusammenfassung von Zuständen gemäß F i g. 9 kombiniert werden, um den Realisierungsaufwand zu vermindern. Ein Codewort ist aus zwei Teilen aufgebaut, dem linken Teil, der die Zustände angibt, bei dem der nächste Prädiktionsfehler auftritt und dem rechten Teil, der die Zahl der Zustände »S« seit dem letzten Prädiktionsfeh ler darstellt Im Beispiel der Fig. 10 hat z B. die linke Lauflänge das Codewort 13/1, d. IL, beim Zustand 13 tritt der nächste Prädiktionsfehler auf, d h nach einem Zustand 13 seit dem letzten Prädiktionsfehler. The coding system described can be in terms of the technical Simplify the effort if the prediction error does not occur in the run length coding all possible states of the image points x until Xn are distinguished, but several states can be combined to form a new state. One such simplified system is shown in FIG. 9 were shown here for the example all states different from the state "o" are combined into a new state "O" All of the original states associated with the new state are counted down the run lengths are no longer differentiated. With the simplification by summarizing of states, however, is associated with a reduction in the reduction factor. on this can be a suitable compromise between the complexity of the circuitry and reduction gain can be achieved. In the lower part of FIG. 9 is the summary of the states different from 0 shown as the run length. FIG. 10 shows a simplified one Run-length coding of the prediction errors specified. To do the coding in several Shift register runs or the storage of all run lengths of a line in the decoder to avoid, the in F i g. 10 shown simplified Run length coding be used. The position of the prediction errors is coded in the sequence and sent in which they occur in the line The run length codeword gives both indicates the state in which the next prediction error occurs as well as the number the states between the last and the new prediction error. This run length coding can also with the simplification by combining states according to FIG. 9 can be combined in order to reduce the implementation effort. A code word is made up of two parts, the left part, which indicates the states in which the next prediction error occurs and the right part, which is the number of states "S" represents since the last prediction error. In the example of FIG B. the left run length the code word 13/1, d. IL, at state 13 the next one occurs Prediction errors on, i.e. after a state 13 since the last prediction error.

Fig. 11 zeigt ein Beispiel eines Huffman-Codes für die Lauflängencodierung Spund LL Da die Codeworte sowohl den Zustand s> bei dem der nächste Prädiktionsfehler auftritt, als auch die Zahl der Zustände Sseit dem letzten Prädiktionsfehler angeben, wären bei einer Zeilenlänge von Z Bildpunkten in dem Beispiel von F i g. 10 insgesamt 16 - Z verschiedene Codeworte möglich Um den Aufwand gering zu halten, ist im Codierer ein Codewortspeicher mit 128 Plätzen zu je 16 Bits vorgesehen, der davon nur die häufigsten Codeworte (S, LL) mit LL < 8 enthält (Fig 11} Bei größeren Lauflängen wird ein Codewort mit der Bedeutung (S, LL 1 8) gesendet und anschließend wird zusätzlich die Lauflänge als 12-Bit-Binãrzahl übertragen. Für die zusätzlich übertragenen Laufgängen kann jedoch auch einer der bekannten Lauflängencodes verwendet werden. Die Codeworte (S, LL < 8) sind nach dem bekannten Prinzip von H u f f m an gebildet, wobei den häufigen Kombinationen (5, LL) kurz Codeworte und den seltenen Kombinationen lange Codeworte zugeordnet sind. Der Huffman-Code ist in »IEEE International Convention Record« von P.D. Fig. 11 shows an example of a Huffman code for run length coding Spund LL Since the code words both have the state s> in which the next prediction error occurs as well as the number of states since the last prediction error, would be with a line length of Z pixels in the example of FIG. 10 in total 16 - Z different code words possible To keep the effort low, is in the coder a code word memory with 128 places of 16 bits each is provided, of which only the contains most frequent code words (S, LL) with LL <8 (Fig. 11} For longer run lengths a code word with the meaning (S, LL 1 8) is sent and then additionally transmit the run length as a 12-bit binary number. For the additionally transferred walkways however, one of the known run length codes can also be used. The code words (S, LL <8) are formed according to the known principle from H u f f m on, where the frequent combinations (5, LL) for short code words and the rare combinations long code words are assigned. The Huffman Code is in "IEEE International Convention Record «by P.D.

Dodd und F.B. Wood, 1963, Seiten 60 bis 93, beschrieben worden. Es kann auch ein modifizierter Huffman-Code angewendet werden, wie er in der DT-AS 2552751 beschriebenist Damit die Codierungsschaltung die Länge eines Codewortes erkennen kann, ist sie in den letzten 4 Bits jedes Speicherplatzes im Codewortspeicher als Binärzahl enthalten. Die ersten 12 Bits enthalten das Codewort selbst (F i g. 11). Die genaue Zuordnung der Codeworte zu den Kombinationen (S, LL)hängt von der Statistik der vorwiegend zu übertragenden Bilder und von der verwendeten Auflösung ab und muß für den jeweiligen Anwendungsfall optimiert werden.Dodd and F.B. Wood, 1963, pp. 60-93. It a modified Huffman code can also be used, as it is in the DT-AS 2552751 is described so that the coding circuit determines the length of a code word can recognize, it is in the last 4 bits of each memory location in the code word memory included as a binary number. The first 12 bits contain the code word itself (F i g. 11). The exact assignment of the code words to the combinations (S, LL) depends on the Statistics of the predominantly transmitted images and the resolution used and must be optimized for the respective application.

Fig. 12 zeigt die Schaltung des Codierers und Fig. 13 das dazugehörige Taktschema Ein Schieberegister SR 1 nimmt das ankommende Bildsignal BS auf und verzögert es um eine Zeile, so daß zu jedem Zeitpunkt die Bildpunkte .... . x4, die den Augenblickszustand Sj bilden, entnommen werden können. Diese vier den Zustand kennzeichnenden Signale werden dem Prädiktor P, (vgL Fig.4) und den Adresseneingängen der Speicher SP1 und SP2 zugeführt Der Speicher SP1 enthält 16 Plätze zu je 12 Bits, in denen für jeden der 16 Zustände gespeichert ist, wie oft der jeweilige Zustand seit dem letzten Prädiktionsfehler aufgetreten ist Der Speicher SP2 enthält 128 Plätze zu je 16 Bits, in denen die Codeworte gespeichert sind (vgL Fig.11} Nachdem mit dem Takt 71 ein neuer Bildpunkt in den Zeilenspeicher eingeschrieben wurde, bildet der Prädiktor F, den Pradiktionswert Xp, aus dem durch Vergleich mit XO das Fehlersignal XF gewonnen wird. Mit dem Takt L, wird der zum Augenblickszustand Si gehörende Lauflängenzahlerstand aus dem Speicher SP1 in den Zähler Z 1 übernommen. Dort wird er mit dem Takt T2 um »1« erhöht und anschließend mit dem Takt Sucht wieder an seinen alten Platz im Speicher SP1 zurAckgeschrieben. Damit ist die Verarbeitung für den Fall, daß kein Prädiktionsfehler aufgetreten ist, abgeschlossen, und die Schaltung wartet auf das Einschreiben des nächsten Bildpunktes in den Zeilenspeicher. Fig. 12 shows the circuit of the encoder and Fig. 13 shows the associated one Clock scheme A shift register SR 1 receives the incoming image signal BS and delays it it by one line, so that at any point in time the pixels ..... x4, which is the instantaneous state Form Sj, can be taken. These four signals characterizing the state are the predictor P, (see Fig. 4) and the address inputs of the memory SP1 and SP2 supplied The memory SP1 contains 16 locations of 12 bits each, in which for each of the 16 states is stored, how often the respective state since the last one A prediction error has occurred The memory SP2 contains 128 locations of 16 bits each, in which the code words are stored (see Fig. 11} After with the clock 71 a new pixel in the Line memory has been written, forms the predictor F, the prediction value Xp, from which the error signal XF is obtained by comparison with XO will. With the cycle L, the run length counter status belonging to the instantaneous state Si becomes taken from the memory SP1 in the counter Z 1. There it is with the clock T2 increased by »1« and then returned to its old place in the Memory SP1 written back. This is the processing in the event that no Prediction error has occurred, completed, and the circuit is waiting for that Writing the next pixel in the line memory.

Wenn das Signal XF einen Prädiktionsfehler anzeigt, werden jedoch auch die weiteren Taktsignale wirksam, die das zur Kombination (S, LL) gehörende Codewort aus dem Speicher SP2 heraussuchen und als Signal CW ausgeben. Zunächst prüft eine ODER-Verknüpfung den Inhalt des Zählers Z1 darauf hin, ob die Lauflänge U ' 8 ist Wenn ja, wird das Flipflop FF gesetzt Dadurch werden die drei niedrigstwertigen Adresseneingänge des Speichers SP2 Null gesetzt, so daß die Kombination(S LL r 8) adressiert ist (vgl. F i g. 11). Ist die Lauflänge LL < 8, so wird der Speicher SP2 durch das Zustandssignal Si und die letzten drei Bits des Zählers Z1 adressiert. Mit dem Taktsignal L2 wird nun das Codewort der adressierten Kombination (S, LL) in das Schieberegister SR 2 und die Länge dieses Codewortes in den Zähler Z2 übernommen. Die Takte T3 schieben das Codewort als Signal CWheraus. Dabei wird gleichzeitig der Zähler Z2 rückwärts gezählt Sobald er auf »Null« steht, ist die Zahl der hinausgeschobenen Bits gleich der Codewortlänge, und der Takteingang des Schieberegisters SR 2 wird gesperrt Die Takte T4 werden nur wirksam, wenn die Lauflänge LL 8 war, wenn also das Flipflop FF gesetzt ist Dann wird im Anschluß an das Codewort (Sj, LL8) 8) die 12-Bit-Lauflãnge aus dem Zähler Z1 zum Ausgang CW hinausgeschoben. Zum Abschluß der Verarbeitung werden schließlich mit dem Rücksetzsignal R, das Flipflop FF und die Zählerstände im Speicher SP1 auf »Null« gesetzt, und die Schaltung wartet auf das Einschreiben des nächsten Bildpunktes in den Zeilenspeicher. If the signal XF indicates a prediction error, however, the other clock signals that belong to the combination (S, LL) are also effective Find the code word from the memory SP2 and output it as a signal CW. First an OR link checks the content of the counter Z1 to determine whether the run length U 'is 8 If so, the flip-flop FF is set. This sets the three least significant Address inputs of memory SP2 set to zero so that the combination (S LL r 8) is addressed (see Fig. 11). If the run length LL <8, the memory SP2 addressed by the status signal Si and the last three bits of the counter Z1. With the clock signal L2, the code word of the addressed combination (S, LL) transferred into the shift register SR 2 and the length of this code word in the counter Z2. The clocks T3 shift out the code word as signal CW. At the same time the counter Z2 counts backwards As soon as it is at "zero", the number of those pushed out is Bits equal to the code word length, and the clock input of the shift register SR 2 becomes blocked The clocks T4 only become effective if the run length LL was 8, i.e. if the flip-flop FF is set. Then, following the code word (Sj, LL8) 8), the 12-bit run length shifted out of counter Z1 to output CW. In conclusion the processing are finally with the reset signal R, the flip-flop FF and the counter readings in the memory SP1 are set to "zero" and the circuit waits the writing of the next pixel in the line memory.

Fig. 14 zeigt die Schaltung des Decodierers und Fig.15 das dazugehörige Taktschema Die seriell ankommenden Codeworte CW werden durch ein Mikroprogrammsteuerwerk, das aus dem Speicher SP3 und dem Register RG 1 besteht, decodiert Der Speicher enthält 256 Plätze zu je 9 Bits. Zu Beginn der Verarbeitung wird das Register RG 1 durch den Takt R1' gelöscht Zur Decodierung eines Codewortes führt das Mikroprogrammsteuerwerk, gesteuert durch den Lesetakt Ll', soviele Schritte aus wie das Codewort lang ist Der Inhalt der Speicherplätze ist in F i g. 16 angegeben. Solange das Codewort noch nicht fertig decodiert ist, was dadurch angezeigt wird, daß das letzte Bit des Speicherplatzes Es 0 ist, werden die ersten sieben Bits zu den Adreßeingängen zurückgeführt Zusammen mit dem nächsten Codewortbild ergeben sich daraus die Adressen von zwei Speicherplätzen, in denen wiederum die ersten sieben Bits einer Speicheradresse stehen, usw. Die Folge der Adressen, die das Mikroprogrammsteuerwerk durchläuft, entspricht der Folge von Verzweigungen, die man im Codebaum des Huffman-Codes durchlaufen muß, um zu dem gewünschten Endpunkt zu komme. Ein solcher Codebaum ist in F i g. 4 der eingangs genannten Literaturstelle »IEEE International Convention Record« von P. D. FIG. 14 shows the circuit of the decoder and FIG. 15 the associated one Clock scheme The serially arriving code words CW are controlled by a microprogram control unit, which consists of the memory SP3 and the register RG 1, decoded. The memory contains 256 places with 9 bits each. At the beginning of the processing, the register RG 1 is through the clock R1 'deleted To decode a code word, the microprogram control unit, controlled by the reading clock Ll ', as many steps as the code word is long The content of the memory locations is shown in FIG. 16 specified. As long as the code word is not completely decoded, which is indicated by the fact that the last bit of the memory location If it is 0, the first seven bits are fed back to the address inputs together with the next codeword image, the addresses of two memory locations result from this, which in turn contain the first seven bits of a memory address, etc. The The sequence of addresses that the microprogram control unit passes through corresponds to the sequence of branches that one has to go through in the code tree of the Huffman code in order to to get to the desired end point. Such a code tree is shown in FIG. 4 of the beginning "IEEE International Convention Record" by P. D.

D o d d und F. B. Wo od, 1963 dargestellt. Nachdem das letzte Bit eines Codewortes verarbeitet ist, trifft das Mikroprogrammsteuerwerk auf einen Speicherplatz, in dem die decodierte Kombination (S, LL) steht (F i g. 16).D o d d and F. B. Wo od, 1963. After the last bit of a code word has been processed, the microprogram control unit encounters a memory location which contains the decoded combination (S, LL) (FIG. 16).

Das Ende eines Codewortes wird daran erkannt, daß das letzte Bit des Speicherplatzes E = 1 gesetzt ist.The end of a code word is recognized by the fact that the last bit of the Storage location E = 1 is set.

Außerdem ist das vorletzte Bit Ü = 1 gesetzt, wenn die zum Zustand S gehörende Lauflänge LL 2 8 ist. In diesem Fall werden die nächsten 12 Codebits durch die Takte T1' in den Zähler Z1 geschrieben. Wenn LL < 8 ist, d. h. Ü= O, wird die 3-Bit-Lauflänge aus dem Speicherplatz des Mikroprogrammsteuerwerks in den Zähler Z1 übernommen. Nach Abschluß dieser Verarbeitung steht im Register RG 1 der Zustand Sund im Zähler Z 1 die Lauflänge Kl, bei der der nächste Prädiktionsfehler auftritt In der zweiten Phase der Decodierung wird das Bildsignal BS erzeugt. Dazu stehen in dem Schieberegister SR3 die Bildpunkte X ... X4 zur Verfügung, aus denen wie beim Codierer durch den Prädiktor P2 der Prädiktionswert Xp gewonnen wird. Der durch X1 . . .... . X4 bestimmte Momentanzustand Si wird mit dem im Register RG 1 gespeicherten Zustand Sverglichen. Sind beide gleich, wird der Zählerstand Z1 durch den Takt T3' um »1« erniedrigt. Wenn der Zählerstand Null geworden ist, wird das Signal XF = 1 gesetzt und für XO wird der invertierte Prädiktionswert Xp eingesetzt Wenn der Momentanzustand Sj mit dem gespeicherten Zustand S nicht übereinstimmt oder wenn beide übereinstimmen und der Zähler Z 1 aber noch nicht Null geworden ist, wird für XO der Prädiktionswert Xp eingesetzt. Nachdem so die Kombination (S, LL) abgearbeitet wurde, wiederholt sich der Vorgang mit der Decodierung des nächsten CodewortesIn addition, the penultimate bit Ü = 1 is set when the status S is the corresponding run length LL 2 8. In this case it will be the next 12 bits of code written into the counter Z1 by the clocks T1 '. If LL <8 i.e. H. Ü = O, the 3-bit run length is transferred from the memory location of the microprogram control unit to the Counter Z1 accepted. After this processing has been completed, the register RG 1 contains the State Sund in counter Z 1 the run length Kl at which the next prediction error occurs in the second phase of decoding the Image signal BS generated. In addition the image points X ... X4 are available in the shift register SR3, from which as in the case of the encoder, the prediction value Xp is obtained by the predictor P2. Of the through X1. . .... X4 determined instantaneous state Si is compared with that in register RG 1 saved state S compared. If both are the same, the counter reading will be Z1 decreased by "1" by measure T3 '. When the count has become zero, will the signal XF = 1 is set and the inverted prediction value Xp is used for XO When the current state Sj does not coincide with the stored state S. or if both match and the counter Z 1 has not yet become zero is, the prediction value Xp is used for XO. After the combination (S, LL) has been processed, the process is repeated with the decoding of the next Code word

Claims

Claims: 1. Method for data compression (redundancy reduction) binary coded image signals obtained by scanning original images, whereby the black-and-white information of the individual pixels is based on several, prediction patterns resulting from the area around the pixel are predicted, compared with the actually found black or white information and at Deviation is recognized and registered as an error and the resulting error image is transmitted using run length coding and decoded again at the receiving location, characterized in that for each prediction pattern that corresponds to a predetermined Black and white state of the environment corresponds to the error according to the prediction subsequent comparison are saved separately that the distances from errors to errors are coded and transmitted separately as run lengths for each state and that the errors of the individual states are stored and decoded at the receiving location will.

2. The method according to claim 1, characterized in that in per se transmit frequently occurring states with smaller code words in a known manner are considered less frequent.

3. The method according to claim 2, characterized in that in per se as is known, the most frequent status is transmitted with the shortest code word.

4. The method according to any one of claims I to 3, characterized in that that several states are combined into one state.

5. The method according to claim 4, characterized in that all of most frequent state deviating states can be summarized as one state.

6. The method according to any one of claims 1 to 5, characterized in, that the position of the prediction errors are coded and ordered in the order, in which they occur in the line, using run-length codewords that include indicate the state in which the next prediction error occurs and the number of these states between the last and the new error.

7. The method according to any one of claims 1 to 6, characterized in, that the distances from error to error are coded for each status according to DT-AS 2552751 and transmitted.

The present invention relates to a method for data compression (Redundancy reduction) Binary coded image signals that are generated by scanning original images can be obtained, the black-and-white information of the individual pixels based on of several prediction patterns resulting from the area around the image point predicted, compared with the actually found black or white information and in the event of a deviation it is recognized and registered as an error and the result that has arisen in this way The error image is transmitted using run length coding and decoded again at the receiving location Data compression is often used to save transmission time or bandwidth worked, whereby it comes to the normally existing redundancy of the to be transmitted Decrease information.

When transmitting binary coded image information of only two Black and white brightness levels, e.g. weather maps, drawings or pages of text, in order not to have to encode each pixel individually, the so-called Proposed run length coding, especially for longer image lines the same information means considerable savings in terms of transmission time or bandwidth brings with it.

This method, in which the length of the black or. White states encoded and transmitted is by that described in US Pat. No. 3,813,485 Method that uses a prediction of the coming image point derived from the environment works, has been improved. Depending on the black and white information distribution of the surroundings, the information of the coming image point is predicted and with compared to the information actually encountered. Any deviation will result in an error recognized and the entirety of the errors registered as an error image.

This error image is then transmitted by run length coding. With this method, however, there still remains a not inconsiderable residual redundancy.

The present invention is based on the object of this method to be further improved in order to achieve an even greater reduction in redundancy. These The object is achieved according to the invention by the features specified in claim 1 Further advantageous refinements of the invention are described in the following Subclaims indicated.

The invention is illustrated below with reference to FIGS. 1 to 16 closer explained. 1 shows an example of the derivation of a prediction pattern with seven pixels from the environment, FIG. 2 shows an example of a prediction pattern with four surrounding image points, FIG. 3 a table for the probabilities and Prediction values of different prediction patterns, FIG. 4 an example of a Circuit for generating the prediction value, F i g. 5 is a block diagram for Generation of the defect image, F i g. 6 an example of the run lengths between the Errors of individual states, F i g. 7 an example of the coding of each Run lengths between the errors of individual states, FIG. 8 an example of a transmission format for one line, F i g. 9 a simplified system for the evaluation of the error pattern, F i g. 10 shows an example of a simplified run-length coding, FIG. 11 a Example of a Huffman code for coding, Fig. 12 is a circuit diagram of an encoder, Egg g. 13 is a timing diagram of the encoder, FIG. 14 an example of a decoder, F i g. 15 shows a clock scheme of the decoder, FIG. 16 shows examples of the content of the memory locations in the decoder.