Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
  • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
  • H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Definitions

• the present invention relates to a method and a device for compression by conditional coding of digital images without loss of information.
• French patent application 83 18132 discloses a method of compressing digital information representative of the pixels of a digitized image. This process makes it possible to obtain a good compression rate, without loss of information, whereas the previous processes only made it possible to obtain interesting compression rates with a certain degradation of the image, therefore with loss of information, which is unacceptable when it comes to radiographic medical images.
• the present invention relates to a method for compressing digital information making it possible to obtain a high compression ratio, without loss of information, and it also relates to a device for implementing this method, a device which is simple. and inexpensive to make.
• the method of the present invention consists in performing a conditional coding for each pixel of the digitized image by assigning to each current pixel a variable length code counts given its value and the values of at least two neighboring pixels, and according to an advantageous aspect of the invention, the different codes are grouped into a smaller number of coding classes all having substantially the same probability of occurrence and groups together under the same prefix several values of unlikely codes that are distinguished by a suffix.
• the device for implementing the invention essentially comprises a random access memory memorizing the values of successive pixels of an image analyzed in number at least equal to the number of pixels contained in a line of this image, this random access memory being connected to a converter device supplying, as a function of the respective values of the pixels neighboring the current pixel, the numbers of coding classes, this converter device being connected to a coding device supplying, as a function of the above-mentioned class numbers, corresponding variable length codes.
• the device of the invention comprises a concatenation forming device essentially composed of a register with parallel inputs whose serial output is connected to a serial input of another register of the same capacity with parallel outputs, the inputs of the first of these registers being connected to said coding device and the outputs of the second to a mass storage device, said coding device comprising a variable-length code length output connected by a controller to a clock itself connected to the clock signal inputs of the two registers and to a counter whose number of counting states and equal to the capacity of each of the two registers, the output of this counter, activated at arrival at the last counting state, being linked to the command to validate the outputs of the aforementioned second register.
• FIG. 1 is a block diagram of an encoder conforming to the invention.
• FIG. 2 is a block diagram of a decoder according to the invention.
• variable length codes such as HUFFMAN codes (which can range from 1 to 16 binary elements for example) would make it possible to reach the value of compression ratio mentioned above, but would require, in the current state of technology, a prohibitive number of memory circuits.
• the present invention makes it possible, as explained below, to considerably reduce the number of circuits necessary for the implementation of such coding.
• the present invention proposes, first, to distribute all the pairs of values (Y, Z) into a smaller number of coding classes, and then to group several values under a single prefix, distinguished by a suffix.
• the compression ratio could be further increased by taking into account a larger number of pixels, but this would require, in the context of the invention, an increase in the capacity of the coding memory generally too high having regard to the relatively small increase in compression ratio.
• the coder shown in FIG. 1 receives, on a terminal 1, from a digitizing device (not shown), a succession of binary data, coded on eight binary elements in the present case, resulting from the analysis, line by line , an angiography image, and then the digitization of the values obtained.
• a digitizing device not shown
• X the value of the current pixel (the one being coded)
• Y the value of the previous pixel
• Z the value of the one having the same rank as pixel X in the previous line.
• other pixels could be chosen from among the neighboring pixels of the current pixel, whether in the current image or in the previous images of the sequence.
• Terminal 1 of the encoder is connected to the input of a memory 2, advantageously consisting of a random access memory, making it possible to store a number of pixel values equal to the number of pixels of an image line analyzed.
• the memory 2 has two outputs 3, 4 on which the current values Y and Z appear respectively for an incident current value X, this by means of addressing the memory 2 which is obvious for those skilled in the art.
• the output 3 is connected to the addition input of an adder 5 whose subtraction input is connected to the output 4.
• the output 4 is also connected to the input of a memory 6, which can be a read only memory, but preferably random access memory, and which, depending on the value of Y, provides part of the code number on three binary elements (in fact, one of the eight lines in the table above).
• the output of the adder 5 (on which the value YZ is collected) is connected to the input of a memory 7, which can be, like memory 6, a read only memory, but preferably a random access memory.
• This memory 7 provides, as a function of the eight classes of values of (YZ), the other three binary elements of the code number.
• the input l is, moreover, connected to an input of a multiplexer 8, and to the addition input of an adder 9, the subtraction input of which is connected to the output 3.
• the output of the the adder 9 is connected to the addition input of another adder 10 the other addition input of which is connected to the output of the adder 5 with shift of one row towards the least significant binary elements, so as to draw half of the output value of the latter, i.e. (YZ) / 2.
• the output of the adder 10 is connected to another input of the multiplexer 8.
• the outputs of memories 6 and 7 are connected on the one hand to a memory 11 the output of which is connected to the control input of the multiplexer 8, and on the other hand, jointly with the output of the multiplexer 8, to the input a code memory 12.
• the output of the adder 5 is defined on nine binary elements (the sign is taken into account), like that of the multiplexer 8, and the memory 12 is therefore addressed on fifteen elements binaries.
• the memory 11 controls the choice, by the multiplexer 8, of the value X (of terminal 1) or else of the value X - from adder 10, according to the respective coding classes (0, 5, 6, 7) or (4 and 8 to 63).
• the memory 12 which is also preferably a random access memory, supplies information C on an output 13 which represents either the variable length code or a prefix to which the value X of the current pixel will be added in suffix (at the level of the register 16).
• the information C has, in the present case, a length L of fifteen binary elements at most, and this information L (determined on four binary elements) is presented on an output 14 of the memory 12.
• information P indicating, on a binary element, whether information C is a variable length code or a prefix.
• the outputs 13 and 15 of the memory 12, as well as the terminal 1, are connected to the parallel inputs of a register 16 whose serial output is connected to the serial input of another register 17.
• the parallel outputs (sixteen in the present case) of the register 17 are connected via a buffer register 18 to a mass memory 19 which can be, for example a flexible disk unit.
• the connection between the buffer 18 and the memory 19 can be done on eight or sixteen binary elements.
• the outputs 14 and 15 of the memory 12 are connected to a controller 20, which can for example be a down counter, itself connected to the control input of a clock 21.
• the output of the clock 21 is connected to the input of clock signals from registers 16 and 17 and to a counter 22 mounted as a counter by 16, the output of which is connected to the input LD for controlling the loading of register 18.
• the formatting circuit connected downstream of the memory 12 operates as follows. At the first incident value of X, register 16 is loaded from memory 12 either with a prefix and the value of X via input 1, or with the corresponding variable length code.
• the controller 20 causes the clock 21 to send a number of pulses equal to the length L1 of the information loaded into the register 16, so that this first information is transferred to the first L1 cells of the register 17 (those the closer to the serial input).
• the counter 22 does not reach its release value, and the register 17 contains (16-L1) binary elements of any value, and L1 binary code elements.
• the register 16 is loaded with the corresponding information of length L2, and the controller 20 causes the clock 21 to transmit L2 pulses.
• L2 is greater than (16-L1), as soon as the clock 21 has emitted (16-L1) pulses, the counter 22 arrives at 16 and emits at its output a signal which commands the sending by the register 17 of its contained on its parallel outputs.
• This content consists of the L1 bits of information corresponding to the first pixel analyzed and the (16-L1) first bits of information corresponding to the second pixel analyzed. These first 16 bits are then loaded into the mass memory 19.
• L2 is less than (16-L1), the counter 22 does not fire, and the register 17 waits for the loading of other information coming from from the register 16.
• a third piece of information of length L3 is loaded into the register 16 and transferred in series to the register 17, and if the latter receives at least sixteen bits of information, i.e. if (L1 + L2 + L3 - 16) is greater than or equal to 16, the content of register 17 is transferred to memory 19, otherwise register 17 waits for the arrival of one or more other following pieces of information, until this condition is fulfilled .
• FIG. 2 shows the block diagram of a decoder circuit making it possible to restore from the information stored in the mass memory 19 the original image.
• the decoder circuit described below takes up all the constituent elements of the circuit of FIG. 1, but with certain connection differences.
• a person skilled in the art can easily realize the two circuits using a single set of constituent elements, and switch them appropriately according to whether he wants to obtain an encoder or a decoder.
• these two circuits are described here separately.
• the mass memory 19 is connected by a buffer 23 to the parallel input of a register 24, the serial output of which is connected to the serial input of another register 25.
• the connection between the memory 19 and the buffer 23 can be done on eight or sixteen binary elements, and that between the buffer and the register 24 is done on sixteen binary elements, the two registers 24 and 25 each having sixteen cells.
• the parallel output of register 25 is connected to the input of a decoder 26 consisting of a read-only memory, or, preferably, of a random access memory.
• the decoder 26 has an output 27 which emanates the decoded word (which is either X or X -), on nine binary elements in the present case (value on eight binary elements and the sign), and an output 28 on which there is information concerning the length of the decoded word.
• This output 28 is connected to a controller 29, which comprises for example a down-counter, and the output of which is connected to the control input of a clock 30.
• the output of the clock 30 is connected to the signal inputs clock of registers 24 and 25, as well as at the input of a counter 31 mounted as a counter by 16.
• the output, activated on arrival at state 16, of counter 31 is connected to the signal input buffer 23.
• the output 27 (without the sign) of the decoder 26 is connected to an input of a multiplexer 32 as well as to the addition input of an adder 33 (with the sign) whose output is connected to the input of another adder 34, the output of the latter being connected to another input of the multiplexer 32.
• the output of the multiplexer 32 is connected to a terminal 35, on which we collect, for subsequent processing, the digitized values of the pixels X (on 8 binary elements in this case), as well as the input of a memory 36 which has the same characteristics as the memory 2.
• the output "Y" of the memory 36 is connected to the input of a memory 37 as well as to the input d 'an adder 38.
• the subtraction input of the adder 38 is connected to the output "Z" of memory 36, and its output is connected to the input of a memory 39.
• the outputs of memories 37 and 39 are connected to the input of the decoder 26, as well as to the input of a memory 40 whose output is connected to the control input of the multiplexer 32.
• the characteristics of the memories 37, 39 and 40 are the same as those of memories 6, 7 and 11 respectively.
• the output "Y" of the memory 36 is connected to another input of the adder 33, and the output of the adder 38 is connected, with shift of a weight towards the least significant (division by 2), with l subtraction input of the adder 34.
• the values of the successive pixels of an image we read, in the order in which they were stored there, slices of 8 or 16 binary elements which are loaded into the buffer 23.
• a control device (not shown) sends it a clock pulse, and its content is transferred to the register 24.
• the controller 29 causes clock 30 to send to registers 24 and 25 a number of pulses corresponding to the length of the code previously presented at the input of decoder 26 to evacuate it as soon as the decoder has supplied at its output 27 the value decoded X or X -.
• the first coded value present in the register 24 corresponds to the value X of the first pixel, and in this case, the controller 29 sends 16 pulses by the clock 30, to transfer it to the register 25.
• the decoder memory 26, which is preferably a random access memory , receives on its addressing inputs, on the one hand the 6 binary elements corresponding to the class of the code associated with the pair (Y, Z), on the other hand the first 8 bits of the content of register 25.

Landscapes

• Engineering & Computer Science (AREA)
• Multimedia (AREA)
• Signal Processing (AREA)
• Image Processing (AREA)
• Compression, Expansion, Code Conversion, And Decoders (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=9325440

Family Applications (1)

Country Status (4)

Families Citing this family (12)

Family Cites Families (11)

• 1985
  • 1985-12-04 FR FR8517949A patent/FR2591050B1/fr not_active Expired - Lifetime
• 1986
  • 1986-12-02 WO PCT/FR1986/000413 patent/WO1987003769A1/fr not_active Ceased
  • 1986-12-02 EP EP86906864A patent/EP0249607A1/de not_active Withdrawn
  • 1986-12-02 US US07/080,532 patent/US4916544A/en not_active Expired - Fee Related

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events