CA2151023A1 - Method of coding/decoding of a data stream - Google Patents
Method of coding/decoding of a data streamInfo
- Publication number
- CA2151023A1 CA2151023A1 CA002151023A CA2151023A CA2151023A1 CA 2151023 A1 CA2151023 A1 CA 2151023A1 CA 002151023 A CA002151023 A CA 002151023A CA 2151023 A CA2151023 A CA 2151023A CA 2151023 A1 CA2151023 A1 CA 2151023A1
- Authority
- CA
- Canada
- Prior art keywords
- data
- compression
- frame
- memory
- buffer
- 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.)
- Abandoned
Links
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/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
- H04N19/436—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation using parallelised computational arrangements
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/124—Quantisation
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/132—Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
- H04N19/136—Incoming video signal characteristics or properties
- H04N19/14—Coding unit complexity, e.g. amount of activity or edge presence estimation
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
- H04N19/146—Data rate or code amount at the encoder output
- H04N19/152—Data rate or code amount at the encoder output by measuring the fullness of the transmission buffer
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
- H04N19/17—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object
- H04N19/172—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object the region being a picture, frame or field
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
- H04N19/17—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object
- H04N19/176—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being an image region, e.g. an object the region being a block, e.g. a macroblock
-
- 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/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
- H04N19/423—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation characterised by memory arrangements
-
- 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/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
- H04N19/423—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation characterised by memory arrangements
- H04N19/426—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation characterised by memory arrangements using memory downsizing methods
- H04N19/428—Recompression, e.g. by spatial or temporal decimation
-
- 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/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
-
- 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/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
- H04N19/61—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding in combination with predictive coding
-
- 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/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
-
- 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
- H04N19/91—Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Computing Systems (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Reduction Or Emphasis Of Bandwidth Of Signals (AREA)
- Signal Processing For Digital Recording And Reproducing (AREA)
Abstract
A method of coding/decoding of a data stream which minimizes the memory requirement for the buffer, the necessary memory band width and the data rate to be stored in the buffer. The method comprises storing the data in the buffer after the data has been compressed and decompressing the data after it is read out.
Description
Method for the ro~;n~/deco~;n~ of a data ~tream Coding and decoding methods are used to m;n;m; ze the data rate and hence to transmit as much data as possible using a small number of channels or to be able to store as much data as possible in as little memory as possible.
The methods for coding and decoding video and audio information are defined, for example, in the "Joint Picture Expert Group" (JEPG) and "Motion Picture Expert Group" (MPEG) standards. Devices for carrying out these methods are mostly based on digital signal processors (DSP). Single-chip implementations, too, are already commercially available.
Prior art A data stream consists of a sequence of elements whose data contents can be combined to form various groups. New data contents are allocated to the groups at regular intervals by the data stream. The groups in their entirety form a data record. In the processing of data streams, it is often necessary to buffer data blocks between the individual method steps. In addition, structured data streams often have to be reordered into a different grouping. The memory required for this is dependent on the m~; mllm volume of data which has to be stored in parallel per unit time.
The memory requirement can be reduced by using addressing methods in which, for example, free memory locations are used between data which are stored block by block. Virtual addressing is also possible, in which a logic address which is proportional to the position of the element in the segment is converted into a physical address by means of a transformation function. Never-theless, the resultant memory requirement is too high for large volumes of data, such as occur, for example, in digital image processing. Moreover, the problem remains that the data rate at which the information is stored in the physical memory is just as high.
The problems of buffering and reformatting will now be explained in more detail with regard to the example of digital image processing using the MPEG
method:
Natural frame sequences have three properties which can be utilized for coding. First of all, successive frames of a frame sequence are similar.
Changes from frame to frame can seldom be attributed to new frame contents, instead they can be attributed pre~om;n~ntly to the movement of objects. Furthermore, natural frames consist, to a first approximation, of areas and edges. In this case, the areas take up the majority of the frame. They are characterized by gradual colour and brightness transitions. Therefore, adjacent pixels within a frame are often similar. Finally, not all grey shades occur with equal probability within natural frames. An average tonal value is more likely to occur than black and white.
These three effects describe the similarity of the signal to itself, namely the similarity of successive frames, the similarity of locally adjacent pixels and the similarity of probability distributions of the tonal values of different frames. These redundancies can be utilized for compression by resolving temporal redundancies of successive frames by means of a movement-compensated DPCM loop (Differential Pulse CodeModulation) and by resolving spacial redundancies and irrelevancies within a frame by means of a DCT (Discrete Cosine Transformation) technique and VLC techniques (Variable Length Coding, consisting of run length coding and Huffmann coding). These techniques for video compression are referred to as hybrid coding. They are already adequately known and proven from video conference and remote contribution insertion codecs, the CCITT H.261 and ITU-T CMTT/2 standards, and from the JPEG method.
21~1023 _ - 3 -The data compression is carried out in an MPEG
encoder. In a firæt stage, the digital video data are initially reordered from the line-by-line frame representation into a sequence of 8 x 8 block matrices (frame reordering), since a complete television picture which can be represented in a two-dimensional matrix is transmitted in such a way that the pixels are combined in a line-by-line manner and the lines succeed one another in time. In this case, the pixels correspond to the elements of a data stream, the elements in their entirety in one line correspond to a group, and the frame corresponds to a data record. The block-oriented coding method described in the MPEG st~n~rd envisages that the frames which are normally present after having been organized in a line-by-line manner are reordered, subdivided into blocks and finally processed in groups of blocks, so-called macro blocks. In this case, each of these blocks consists of 8 block lines having 8 pixels each. The groups are converted into a different grouping by splitting a frame which is represented in a line-by-line manner into non-overlapping blocks having a fixed number of columns and lines. In this case, the blocks each represent a frame excerpt. In addition, the temporal succession of the data records - frames - is likewise changed.
A frame store is provided for this reformatting, which store has to be addressed in such a way that it is possible to access the group elements in a specific manner. The groups must therefore have a regular structure. In contrast, the reordering of the data records no longer requires any structure, since access is made to the blocks in their entirety. If the overall available memory size is adequate, the individual block lengths may be variable.
In block-oriented video coding methods, the memory requirement for the line/block reformatting results in n-1 lines for blocks having n lines. In addition to this, there is the memory space for altering the frame order. This memory requirement results from the number of frames b to be buffered and the frame size. An additional factor is that a plurality of memory banks and address generators are necessary in the case of multistage reformatting. In addition, the information has to be read and written many times.
A second stage is used for data compression by means of the hybrid coding methods mentioned. A frame store is required, in which preceding frames are buffered and used for movement compensation of the respectively current frame. The store is normally arranged downstream of the arithmetic units for carrying out a discrete cosine transformation (DCT) and quantization (Q), as well as inverse quantization (Q~l) and inverse DCT (DCT-l). The video data are transformed and inverse-transformed prior to storage, in order that the coding errors in the movement estimation can be compensated for.
Conventionally, uncompressed frames are stored in the two stores of an MPEG encoder. Consequently, the stores have to be designed to be relatively large.
Depending on the standards and frame formats to be processed, the stores for the first and second stages have sizes between about 300 kbytes for 1/4 of a television picture and more than 4 Mbytes for a high-definition television picture (HDTV picture).
The data decompression is carried out in an MPEG
decoder. For this purpose, the video data of a frame which have been reordered and coded according to the MPEG
standard are read in by an MPEG decoder. In a first stage, the fundamental value details and frame parameters are read from the data stream (header detection) and the data which are coded with a variable code word length are decoded in the variable length decoder (VLD). In this case, the video data are reordered via an inverse zig-zag function into a block arrangement again. A first frame store is used for this purpose. The reordered and VLD-decoded data stream is split up into blocks and further decoded in a second stage by means of dequantization (Q~l) and two-dimensional inverse diæcrete cosine transformation (DCT-l). The movement compensation is then reversed. The corresponding stage with a frame store is used for this purpose, which store can also be used as a buffer for the video output.
The first decodable frame of a sequence is a frame (I-picture) which i8 "intra"-coded completely without any movement compensation. This frame is written directly to the store as the result of the DCT-1. From there, it can be used for movement compensation for the next decoded frame, for e~ample a "predictive" frame (P-picture), which is predicted from preceding frames, or a frame (B-picture) which is "bidirectionally predictive"
from preceding and following frames. The decoded P-pictures are likewise buffered for the movement compensation of B-pictures, if the latter occur in the sequence.
In the stage for movement decompensation, the video data, if they are P- or B-pictures, are converted to match the uncompressed video data, located in the store, of a preceding I- or P-picture or of two preceding B-pictures. The I-pictures are directly decompensated without any information from the store. The decompensated data stream corresponds once more to a decoded normal frame having lllmin~nce and chrom;n~nce values according to the CCIR standard.
The frame store in the second stage is normally addressed with the aid of the VLD-decoded movement vectors. In this case, a displacement position of a macro block of the current frame with respect to the position of a macro block from a preceding frame is indicated in a macro block-by-macro block manner by these vectors.
The decoder also ensures that, with regard to the first frame store for reordering and buffering the data stream, access has to be made to the group elements in a specific manner. In addition, there is a large memory requirement for the frame stores of the first and second stages.
For multichannel audio transmission of audio data, the latter are compressed in an MPEG encoder. The channels of the data stream are subband-filtered in a fir~t ~tag~. ~e r~sultan~ frequency band~ are quantizQd and _~tFixed ln order to fonm t~o c~mpatible ~tereo c~ s. The cnA;n~ of t~e data ~treams takes place i~
a s~cond stage. The d~ta ~re sub~quently for~atted in ~ch a way that they can ~e tra~itted ~cquentially as an MPE~ data ~tream on one channel. ~or this purpoee, the data are split into packet~ ~d provlded with control i~fo~mation.
Bu$fer~ are ~e~ to ~mplement the~e co~l ng methods. In cont~a~t ~o the video enc~e~, the ~torage ~roblsm 18 ~ot ~o m~ch the me~ory ~ize a3 th~ m~mory ~dwldth, Sp~ciflcally, the ~itu~t~on may ari~ that the data rats of a ~iaeO data stream ~ too hi~h. The momory acce~e time i~ then exceeded. ~me~l~l action is the~
provided by the cost-intQ~ use of more rapid mcmory chip~ or by r;n~m~slAg the data rate.
The decompre~slon o~ andio data streams ~akQs plac~ in an audio decoder, In this ca~e, the data stream is deformatted in a fi~at Qta~e. Corr~spon~i n~ to th~
20 ~idQo decodiny Bection~ the control data are read f~om ~he he~ of a sequ~nce ~heade~ detection) a~d f~d together with tha coded ~ampl~ value~ to the decod~ n~
~ection. Tho data are convert~d back into ~u~ba~ds o~ce mor~ ~t the Bame time. In a further ~age, the ~h~nnel ~S are recovered by dQmatrixing a~d are sllh~nA-filtered.
The re3ult i~ channel~ of pulse-code-modulated audio dat~
(PC~ data) ~ich Qx$st ln t~ time ~ ; n, Me~nory i~ 3wiB~ required for the deco~npresl3ion and, for rQaso~ of space, it i~ ~orm~lly used joi~tly for the var~ou~ s~g~s. Even h~re th~re are not only pro~lems with regard to th8 ,iy size but also, primarily, conflict~ o~ng to an excesslvely 8m~11 memory idth.
The invent~on 3~ The ~nventio~ 1~ ~a~sd on a method for the coding/decodi~g of a data ~r~am, w~eh m~thod i~cluden the ~thod sta~ of reordering a~ well a~ compre~io~
~nd decompre~ion of ~he data, the data being ~tored $n buf~r for th~ purpona of reorderlng and bei~g read fr~ the buff~r in ~ differant order. The object o~ thu invention in to improve th~ 8 m~thod to the ~xtent that the ~mory r~quir~ment for the buffe~, th~ nece~sa~y S memory ~dwidt~ and the data rat~ to be ~tored i~ the ~uf~er can ~o mi~l~ized, l~ other wor~s the data strea~
ca~ be ~eorde~ed in a ~nner which ~aYe~ rssource~ and optiml~e~ time. T~is obJ~ct i~ ac~ieved according to the inv~tion by the fact that the data are sto~ed in the ~uffer af~er having ~eing co~pre ~ed and are deco~,~s~d agai~ wh~n they are ~ead out.
If it 18 ~ntended, i~ the me~h~d for the codi~gldecodi~g of t~e data ~tream, in the ~tage of compre~eio~ or dcco~pre~lon, ~o ntore data blocke fr~m ths data etF~ in a ~econd ~uffer ~nd to read th~m o~t ~gain, it is cnvi~a~ed in further pursuance of the conc~pt of the inve~tion tha~ the data are stored i~ ~e ~econd ~uffer after having been compre~sed ~nd ars de~o~prossed again when thsy are read out.
~0 ~he volume of da~a to be buf~red i~ ~on~iderably r~duced by me~ns o~ the ~ompression. Thls results 1 si~nificant further ad~antagee. I~ particular, it thu~
ha~ an adva~tageou~ effsct in video procR~sing in that conside~ably ~maller me~or{e~ can now be used~ In the ca~e of audio proce~ing, ~he pr~mary factor i~ that the ~umber o~ memory accessea and ~hus the ~ecessary ~emory b~' idth are reduced. Conslderably faster buf~er~ng of the data streams is achi~ved in a~y ca~e. In ad~ition, the hardware co~t for the memorles i8 considerably less 30 Shan i~ the ~a~t and only a gmall addltio~al gate ~o~t is ~ecessary.
In the reorde~ing of compree~ed data record~, acces~ to the variable ~.0~8 o~ a data record i~
dete~; n~ by the compression method. A compre~ion 3S method in preferrQd in w~ch the ~tructure~ and ~iZQ8 o~
indivldual data group~ a~ well a8 the buffering locat~on ar~ de~ined ind~pende~tly of the dsta ~ont~ntg, and in which tho ~omp~Q~ion factor of individual dat~ group~ 1~
deflned, in other w~d~ individual group~ are comp~essed varied are less suitable for buffering in the stage of reordering, since the reformatting of the grouping then has to take place prior to compression. Direct access to individual groups is then no longer possible without having to store additional address information. The consequence of this is that it is not possible to reduce the memory requirement and the access rate for the reformatting to such a large extent using such compres-sion methods.
Use is preferably made of differential pulse code modulation (DPCM) in the first buffer or in both buffers for compression and decompression. This provides the advantage of lower computational load and a smaller number of necessary gates. In the image processing, it is also possible to employ a two-~;m~ncional predictor, which operates in a block-by-block manner, for the DPCM, with the use of hierarchical addressing, owing to the similarity present in the line structure in blocks and frames. The compression factor and the quality of the transmitted data can be improved thereby.
In a further embodiment, which is particularly suitable for the second buffer, the compression is carried out in such a way that the data are compressed, with the aid of a two-~;men~ional DCT, a quantization stage (Q) and a VLC, to a fixed size independently of the frame complexity. This has the advantage that the required memory to be made available can be predicted. To read out the data, the decompression takes place using the inverse methods.
The quantization factor can be readjusted in a block-by-block manner by controlling the quantization stage by means of a quantization controller (rate control). This means that the frame store is always utilized completely. It is possible to achieve an optimum between picture quality and memory requirement.
Drawinqs Exemplary embodiments of the invention are described with reference to the drawings. In this case, 21~1023 commercially available chips are referred to by their customary abbreviations and all other circuit components are referred to by numerals. In the drawings:
Figure 1 shows an MPEG encoder with frame stores for reordering and movement compensation Figure 2 shows a method for memory m;n;m;zation Figure 3 shows an MPEG decoder with frame stores for reordering and movement compensation Figure 4 shows a special Huffmann encoder for carrying out a VLC
Exemplary embodiments The method can be used in a multiplicity of data processing devices using all conceivable compression algorithms.
The necessary storage capacity is reduced by the fact that the data are compressed prior to storage and decompressed again when they are read out. The resultant storage capacity is calculated as a function of the compression factor k such that: Spk = Spn / k where Spk: Storage capacity for compressed volume of data Spn: Storage capacity for uncompressed volume of data k : Compression factor The compression factor k is dependent on the selected compression method and the desired quality of the data to be stored.
The invention will now be explained in more detail with regard to the example of video data processing using the MPEG method. Figure 1 illustrates the structure of a conventional MPEG decoder. The uncom-prefised data 1 are reordered in an arithmetic unit 2 (frame reordering), a frame store 3 being used for writing 4 and reading 5. The store is controlled by a control unit by means of control signals 6. The following movement estimator 7 accesses the second frame store 8.
The uncompressed data of preceding frames are stored there. Compression by means of DCT and quantization Q
2151~23 then follows. On the one hand, the data are then subjected to variable length coding (VLC), are buffered in a buffer 9 for the purposes of their output and are output as a compressed data stream 10. On the other hand, inverse quantization and inverse DCT are carried out and the data are stored in the frame store 8. The quantization factor can be readjusted in a block-by-block manner by means of a quantization controller 11 (rate control).
The method according to the invention can be inserted into the first stage for reordering and the second stage for movement compensation. The areas of use of the invention in the encoder are illustrated by a broken block 12.
The reordering can be carried out in one step if a fixed compression factor for individual groups is specified independently of the data contents. This can be achieved by the use of suitable source coding methods. A
possible method is DPCM with a fixed code word length, which is subject to losses and is illustrated in Figure 2, or appropriate transformation coding.
Figure 2 illustrates a block 12 for memory m; n; m; zation. Instead of the uncompressed storage of the original video data in the memory, the said data are subjected to DPCM. For this purpose, the data stream 4 is converted with data which are predicted by a predictor 13 and is quantized (Q). The data stream is subsequently coded using a Huffmann method 14 and written to the memory 15. For reading out, the data stream is decoded in a Huffmann decoder 16 and converted with the values predicted by means of the predictor 17.
This method of coding and decoding by means of DPCM has the advantage that the compression factor can be defined and, consequently, access can be made to the data in the memory in a specific manner. In addition, the gate complexity for implementation in a semiconductor chip is quite low.
For separate block line coding/decoding, from experience a compression factor of two can be used for reordering, without substantial impairment to the picture quality occurring. It is possible directly to access any block line by means of hierarchically structured addressing.
This means that all reformatting operations can be carried out in one step, after writing to the memory 15, which should be implemented as RAM with random access, by means of direct addressing of the block lines when they are read out.
Since each group has been compressed without regard to adjacent groups, the signal can subsequently be decompressed again separately.
Another exemplary embodiment of the invention is illustrated in Figure 3. The data stream 4 is subjected to two-dimensional discrete cosine transformation (DCT) and is subsequently quantized by means of a quantization stage (Q).
The quantized date 18 are compressed in a special Huffmann coding section (VLC), which is illustrated in Figure 4. The compressed data stream 19 is then stored in the memory 15. A
quantization controller 20 (rate control) undertakes the control of the quantization. When the compressed data are read out, these steps are then reversed by means of the corresponding inverse operations (VLD, Q~l, DCT-1). In this case, this method, which is similar to the JPEG standard, has the following special features:
a) Frames are only intra-coded.
b) Frames are compressed to a fixed size independently of the frame complexity.
c) The quantization controller 20 operates predictively, that is to say that during the frame compression it also takes account of the volumes of data which are still to be expected from the as yet unprocessed remaining bits.
d) The Huffmann tables are specially adapted as a function of the compression rate, which is determined in turn by the application.
e) If an uncoded block (8 x 8 pixels) contains less data than a coded block, it is stored uncoded.
Any desired architecture can be used for the DCT, , provided that the accuracy requirements in accordance with the underlying standard (for example MPEG or H.261) are met.
The quantization operates essentially in an analogous manner to JPEG and also has the same two-stage structure. The quantization controller 20 readjusts the quantization factor in a block-by-block manner. This is done as a function of the occupancy of the frame store and of the frame complexity to be expected.
A special Huffmann encoder is illustrated in Figure 4. The quantized data are initially read from a first RAM memory 21 using a zig-zag scan. The first value, the DC component (DC) in the frequency range, is written uncoded to the output memory 22. The subsequent AC components (AC values) are coded in an analogous manner to the MPEG standard using the run length method.
The value pairs produced thereby are then transformed by means of a Huffmann table into a bit code of variable length. A Huffmann encoder 23, a multiplexer 24 and a register memory 25 are used for this purpose. It can be discerned at the overflow of the output memory 26 whether the coded block contains more data than the uncoded block. The block is then output after having been DCT-transformed but not, however, compressed.
Therefore, there appears at the output of the VLC
a bit stream having coded and also, partly, uncoded data, which are parallelized by a multiplexer 27 in accordance with the word width of the memory and are stored in the register memory 22. Furthermore, a flag must be set for each block in a further memory, which flag indicates whether the block is uncoded or coded. In addition, the quantization factor associated with the block must be stored.
It can be ensured by means of algorithms which are dependent on the application that the frame store is always utilized completely, with the result that an optimum is established between picture quality and memory requirement. The quantization controller 20 together with the quantization section (Q) and the Huffmann coding section (VLC) determine the compression factor.
The decoding of the frame store data using the inverse method takes place in an analogous manner to the VLC.
In this case, the flag which serves to indicate whether a block is coded or uncoded has to be evaluated.
The dequantization operates in an analogous manner to the quantization. The 12-bit-wide input data for the inverse DCT and produced.
Any hardware can be used for the inverse discrete cosine transformation (DCT-1), provided that the requirements of the respective standard are upheld.
The use of the invention is additionally illustrated in Figure 5 with regard to an MPEG video decoder.
In this case, the method can be used, on the one hand, for the reordering of the data stream after the header detection 28. The buffer 29 which is normally used for this purpose can be replaced by the method 12 according to the invention.
The method for movement compensation can be used advantageously. The video data which have been decoded by means of VLD, Q~1 and DCT-1 are compressed, if they are I- or P-pictures, according to the method shown in Figure 3 and are written to the frame store 30. They are available there for a future P- or B-picture to be decoded. In this way, the last two P-pictures or one I- and one P-picture are always available in the frame store after having been compressed.
The data are decompressed again by means of the inverse method and are fed to the decompensation stage 31. The B-pictures are not buffered but rather forwarded from the decompensation stage 31 directly via a multiplexer 32 to the output unit.
The store 30 is split into two partial areas which each have two banks. The memory addresses are generated by the vectors of the VLD and stored in an address memory 33.
The following unit must be able to receive the video data in blocks and not in lines, as is necessary in the case of monitors.
the case of monitors.
The estimated hardware expenditure with and without memory minimization is given below by way of comparison for an MPEG decoder, for two CCIR 601 standard frames, with a 4:2:0 chroma format:
If a compression factory of k-3 is selected for the frame store data for the highest picture quality, then only 44/3 Mbytes are transmitted averaged over 1/50 s. This corresponds to a bit rate of 14.7 Mbyte/s. The memory size of the frame store required for this is then: 720 frame columns x 288 frame lines x (8 + 4 bits per pixel) x 4 memory banks 2 I- and 2 P-pictures) / k - approximately 10/k Mbits =
approximately 3.3 Mbits.
The start addresses together with the quantization factor and the flag for coded or uncoded data have to be stored for each block in an address memory. Under the conditions stipulated above, the resulting word width of the address for the frame store is 26 bits per block.
The number of required entries in the address memory depends on the number of blocks, the block size and the standard of the frame: 720 frame columns / 8 (horizontal block size) x 288 frame lines / 8 (vertical block size) x 1.5 (luminance and chrominance) = 4860 blocks per memory bank.
There follows from this a total number of 19,440 entries, each of 26 bits, that is to say approximately 505 kbits for the address memory.
An additional expenditure on hardware is necessary for the special driving of the frame store in an MPEG decoder, which hardware comprises a two-dimensional DCT, a quantizer (Q) and a Huffmann encoder (VLC) including an quantization controller 20. For reading from the frame store, an inverse DCT (DCT-1), a dequantizer (Q~l) and a Huffmann decoder (VLD) are required for each partial store.
Hardware to be Memory m;n;m; zation implemented with without 2 DCT-1 (60 MHz) 24,000 gates 0 gates 2 Q~1 10,000 gates 0 gates 2 VLD 10,000 gates 0 gates 1 VLC 8,000 gates 0 gates 1 Q 5,000 gates 0 gates 1 DCT (16 MHz)8,000 gates 0 gates 1 rate control5,000 gates 0 gates Address memory505 kbits 0 bits Frame store3.3 Mbits 10 Mbits TOTAL 70,000 gates 10 Mbits + approximately 3.8 Mbits Overall, therefore, the resulting memory require-ment for the frame store is 3.3 Mbits (data memory) + 0.515 Mbit (address memory) = approximately 3.8 Mbits, compared with 10 Mbits for the uncompressed storage of frames in CCIR 601, 4:2:0.
The hardware expenditure could possibly be reduced further in the event of time-division multiplex operation of individual moduleæ (for example DCTs, Qs) in conjunction with the use of high-speed technologies.
However, this is dependent on the individual application and on the limiting frequency of the technology compared with the standard-dependent volume of data to be pro-cessed.
When the described method for movementcompensation is used, accumulation of the errors produced by the said compression is normally retained and carried over to the next I-picture. If this is not desired, it is possible to limit the error propagation to the successive B-pictures using the following method:
First of all, an I- or P-picture is written uncompressed to the store. The subsequent incoming I- or P-picture is likewise stored uncompressed for the first - 2t~023 64 lines, depending on the maximum length of the movement vector, and iæ decompensated with the uncompressed I-/P-picture. Then, at the same time, the procedures of reading out the I-picture, compressing it and rewriting it to the store at another location are begun.
The compression in the method according to the invention can also be carried out without any transformation. The video data can be compressed in the space domain by means of the Shannon Entropy Theorem without being converted into the frequency domain by means of DCT/DCT-1 or other transformations. For this purpose, an optimum Huffmann table of the data is initially calculated in the space domain, using the probability distribution of the brightness and chrom;n~nce values in the space ~om~;n. In this case, the Huffmann table is either determined online for each frame excerpt or is established definitely by prior calcula-tion. The advantage of this method is less compression complexity. In order to guarantee a fixed output data rate, this method must be extended by a suitable quantization stage.
The methods for coding and decoding video and audio information are defined, for example, in the "Joint Picture Expert Group" (JEPG) and "Motion Picture Expert Group" (MPEG) standards. Devices for carrying out these methods are mostly based on digital signal processors (DSP). Single-chip implementations, too, are already commercially available.
Prior art A data stream consists of a sequence of elements whose data contents can be combined to form various groups. New data contents are allocated to the groups at regular intervals by the data stream. The groups in their entirety form a data record. In the processing of data streams, it is often necessary to buffer data blocks between the individual method steps. In addition, structured data streams often have to be reordered into a different grouping. The memory required for this is dependent on the m~; mllm volume of data which has to be stored in parallel per unit time.
The memory requirement can be reduced by using addressing methods in which, for example, free memory locations are used between data which are stored block by block. Virtual addressing is also possible, in which a logic address which is proportional to the position of the element in the segment is converted into a physical address by means of a transformation function. Never-theless, the resultant memory requirement is too high for large volumes of data, such as occur, for example, in digital image processing. Moreover, the problem remains that the data rate at which the information is stored in the physical memory is just as high.
The problems of buffering and reformatting will now be explained in more detail with regard to the example of digital image processing using the MPEG
method:
Natural frame sequences have three properties which can be utilized for coding. First of all, successive frames of a frame sequence are similar.
Changes from frame to frame can seldom be attributed to new frame contents, instead they can be attributed pre~om;n~ntly to the movement of objects. Furthermore, natural frames consist, to a first approximation, of areas and edges. In this case, the areas take up the majority of the frame. They are characterized by gradual colour and brightness transitions. Therefore, adjacent pixels within a frame are often similar. Finally, not all grey shades occur with equal probability within natural frames. An average tonal value is more likely to occur than black and white.
These three effects describe the similarity of the signal to itself, namely the similarity of successive frames, the similarity of locally adjacent pixels and the similarity of probability distributions of the tonal values of different frames. These redundancies can be utilized for compression by resolving temporal redundancies of successive frames by means of a movement-compensated DPCM loop (Differential Pulse CodeModulation) and by resolving spacial redundancies and irrelevancies within a frame by means of a DCT (Discrete Cosine Transformation) technique and VLC techniques (Variable Length Coding, consisting of run length coding and Huffmann coding). These techniques for video compression are referred to as hybrid coding. They are already adequately known and proven from video conference and remote contribution insertion codecs, the CCITT H.261 and ITU-T CMTT/2 standards, and from the JPEG method.
21~1023 _ - 3 -The data compression is carried out in an MPEG
encoder. In a firæt stage, the digital video data are initially reordered from the line-by-line frame representation into a sequence of 8 x 8 block matrices (frame reordering), since a complete television picture which can be represented in a two-dimensional matrix is transmitted in such a way that the pixels are combined in a line-by-line manner and the lines succeed one another in time. In this case, the pixels correspond to the elements of a data stream, the elements in their entirety in one line correspond to a group, and the frame corresponds to a data record. The block-oriented coding method described in the MPEG st~n~rd envisages that the frames which are normally present after having been organized in a line-by-line manner are reordered, subdivided into blocks and finally processed in groups of blocks, so-called macro blocks. In this case, each of these blocks consists of 8 block lines having 8 pixels each. The groups are converted into a different grouping by splitting a frame which is represented in a line-by-line manner into non-overlapping blocks having a fixed number of columns and lines. In this case, the blocks each represent a frame excerpt. In addition, the temporal succession of the data records - frames - is likewise changed.
A frame store is provided for this reformatting, which store has to be addressed in such a way that it is possible to access the group elements in a specific manner. The groups must therefore have a regular structure. In contrast, the reordering of the data records no longer requires any structure, since access is made to the blocks in their entirety. If the overall available memory size is adequate, the individual block lengths may be variable.
In block-oriented video coding methods, the memory requirement for the line/block reformatting results in n-1 lines for blocks having n lines. In addition to this, there is the memory space for altering the frame order. This memory requirement results from the number of frames b to be buffered and the frame size. An additional factor is that a plurality of memory banks and address generators are necessary in the case of multistage reformatting. In addition, the information has to be read and written many times.
A second stage is used for data compression by means of the hybrid coding methods mentioned. A frame store is required, in which preceding frames are buffered and used for movement compensation of the respectively current frame. The store is normally arranged downstream of the arithmetic units for carrying out a discrete cosine transformation (DCT) and quantization (Q), as well as inverse quantization (Q~l) and inverse DCT (DCT-l). The video data are transformed and inverse-transformed prior to storage, in order that the coding errors in the movement estimation can be compensated for.
Conventionally, uncompressed frames are stored in the two stores of an MPEG encoder. Consequently, the stores have to be designed to be relatively large.
Depending on the standards and frame formats to be processed, the stores for the first and second stages have sizes between about 300 kbytes for 1/4 of a television picture and more than 4 Mbytes for a high-definition television picture (HDTV picture).
The data decompression is carried out in an MPEG
decoder. For this purpose, the video data of a frame which have been reordered and coded according to the MPEG
standard are read in by an MPEG decoder. In a first stage, the fundamental value details and frame parameters are read from the data stream (header detection) and the data which are coded with a variable code word length are decoded in the variable length decoder (VLD). In this case, the video data are reordered via an inverse zig-zag function into a block arrangement again. A first frame store is used for this purpose. The reordered and VLD-decoded data stream is split up into blocks and further decoded in a second stage by means of dequantization (Q~l) and two-dimensional inverse diæcrete cosine transformation (DCT-l). The movement compensation is then reversed. The corresponding stage with a frame store is used for this purpose, which store can also be used as a buffer for the video output.
The first decodable frame of a sequence is a frame (I-picture) which i8 "intra"-coded completely without any movement compensation. This frame is written directly to the store as the result of the DCT-1. From there, it can be used for movement compensation for the next decoded frame, for e~ample a "predictive" frame (P-picture), which is predicted from preceding frames, or a frame (B-picture) which is "bidirectionally predictive"
from preceding and following frames. The decoded P-pictures are likewise buffered for the movement compensation of B-pictures, if the latter occur in the sequence.
In the stage for movement decompensation, the video data, if they are P- or B-pictures, are converted to match the uncompressed video data, located in the store, of a preceding I- or P-picture or of two preceding B-pictures. The I-pictures are directly decompensated without any information from the store. The decompensated data stream corresponds once more to a decoded normal frame having lllmin~nce and chrom;n~nce values according to the CCIR standard.
The frame store in the second stage is normally addressed with the aid of the VLD-decoded movement vectors. In this case, a displacement position of a macro block of the current frame with respect to the position of a macro block from a preceding frame is indicated in a macro block-by-macro block manner by these vectors.
The decoder also ensures that, with regard to the first frame store for reordering and buffering the data stream, access has to be made to the group elements in a specific manner. In addition, there is a large memory requirement for the frame stores of the first and second stages.
For multichannel audio transmission of audio data, the latter are compressed in an MPEG encoder. The channels of the data stream are subband-filtered in a fir~t ~tag~. ~e r~sultan~ frequency band~ are quantizQd and _~tFixed ln order to fonm t~o c~mpatible ~tereo c~ s. The cnA;n~ of t~e data ~treams takes place i~
a s~cond stage. The d~ta ~re sub~quently for~atted in ~ch a way that they can ~e tra~itted ~cquentially as an MPE~ data ~tream on one channel. ~or this purpoee, the data are split into packet~ ~d provlded with control i~fo~mation.
Bu$fer~ are ~e~ to ~mplement the~e co~l ng methods. In cont~a~t ~o the video enc~e~, the ~torage ~roblsm 18 ~ot ~o m~ch the me~ory ~ize a3 th~ m~mory ~dwldth, Sp~ciflcally, the ~itu~t~on may ari~ that the data rats of a ~iaeO data stream ~ too hi~h. The momory acce~e time i~ then exceeded. ~me~l~l action is the~
provided by the cost-intQ~ use of more rapid mcmory chip~ or by r;n~m~slAg the data rate.
The decompre~slon o~ andio data streams ~akQs plac~ in an audio decoder, In this ca~e, the data stream is deformatted in a fi~at Qta~e. Corr~spon~i n~ to th~
20 ~idQo decodiny Bection~ the control data are read f~om ~he he~ of a sequ~nce ~heade~ detection) a~d f~d together with tha coded ~ampl~ value~ to the decod~ n~
~ection. Tho data are convert~d back into ~u~ba~ds o~ce mor~ ~t the Bame time. In a further ~age, the ~h~nnel ~S are recovered by dQmatrixing a~d are sllh~nA-filtered.
The re3ult i~ channel~ of pulse-code-modulated audio dat~
(PC~ data) ~ich Qx$st ln t~ time ~ ; n, Me~nory i~ 3wiB~ required for the deco~npresl3ion and, for rQaso~ of space, it i~ ~orm~lly used joi~tly for the var~ou~ s~g~s. Even h~re th~re are not only pro~lems with regard to th8 ,iy size but also, primarily, conflict~ o~ng to an excesslvely 8m~11 memory idth.
The invent~on 3~ The ~nventio~ 1~ ~a~sd on a method for the coding/decodi~g of a data ~r~am, w~eh m~thod i~cluden the ~thod sta~ of reordering a~ well a~ compre~io~
~nd decompre~ion of ~he data, the data being ~tored $n buf~r for th~ purpona of reorderlng and bei~g read fr~ the buff~r in ~ differant order. The object o~ thu invention in to improve th~ 8 m~thod to the ~xtent that the ~mory r~quir~ment for the buffe~, th~ nece~sa~y S memory ~dwidt~ and the data rat~ to be ~tored i~ the ~uf~er can ~o mi~l~ized, l~ other wor~s the data strea~
ca~ be ~eorde~ed in a ~nner which ~aYe~ rssource~ and optiml~e~ time. T~is obJ~ct i~ ac~ieved according to the inv~tion by the fact that the data are sto~ed in the ~uffer af~er having ~eing co~pre ~ed and are deco~,~s~d agai~ wh~n they are ~ead out.
If it 18 ~ntended, i~ the me~h~d for the codi~gldecodi~g of t~e data ~tream, in the ~tage of compre~eio~ or dcco~pre~lon, ~o ntore data blocke fr~m ths data etF~ in a ~econd ~uffer ~nd to read th~m o~t ~gain, it is cnvi~a~ed in further pursuance of the conc~pt of the inve~tion tha~ the data are stored i~ ~e ~econd ~uffer after having been compre~sed ~nd ars de~o~prossed again when thsy are read out.
~0 ~he volume of da~a to be buf~red i~ ~on~iderably r~duced by me~ns o~ the ~ompression. Thls results 1 si~nificant further ad~antagee. I~ particular, it thu~
ha~ an adva~tageou~ effsct in video procR~sing in that conside~ably ~maller me~or{e~ can now be used~ In the ca~e of audio proce~ing, ~he pr~mary factor i~ that the ~umber o~ memory accessea and ~hus the ~ecessary ~emory b~' idth are reduced. Conslderably faster buf~er~ng of the data streams is achi~ved in a~y ca~e. In ad~ition, the hardware co~t for the memorles i8 considerably less 30 Shan i~ the ~a~t and only a gmall addltio~al gate ~o~t is ~ecessary.
In the reorde~ing of compree~ed data record~, acces~ to the variable ~.0~8 o~ a data record i~
dete~; n~ by the compression method. A compre~ion 3S method in preferrQd in w~ch the ~tructure~ and ~iZQ8 o~
indivldual data group~ a~ well a8 the buffering locat~on ar~ de~ined ind~pende~tly of the dsta ~ont~ntg, and in which tho ~omp~Q~ion factor of individual dat~ group~ 1~
deflned, in other w~d~ individual group~ are comp~essed varied are less suitable for buffering in the stage of reordering, since the reformatting of the grouping then has to take place prior to compression. Direct access to individual groups is then no longer possible without having to store additional address information. The consequence of this is that it is not possible to reduce the memory requirement and the access rate for the reformatting to such a large extent using such compres-sion methods.
Use is preferably made of differential pulse code modulation (DPCM) in the first buffer or in both buffers for compression and decompression. This provides the advantage of lower computational load and a smaller number of necessary gates. In the image processing, it is also possible to employ a two-~;m~ncional predictor, which operates in a block-by-block manner, for the DPCM, with the use of hierarchical addressing, owing to the similarity present in the line structure in blocks and frames. The compression factor and the quality of the transmitted data can be improved thereby.
In a further embodiment, which is particularly suitable for the second buffer, the compression is carried out in such a way that the data are compressed, with the aid of a two-~;men~ional DCT, a quantization stage (Q) and a VLC, to a fixed size independently of the frame complexity. This has the advantage that the required memory to be made available can be predicted. To read out the data, the decompression takes place using the inverse methods.
The quantization factor can be readjusted in a block-by-block manner by controlling the quantization stage by means of a quantization controller (rate control). This means that the frame store is always utilized completely. It is possible to achieve an optimum between picture quality and memory requirement.
Drawinqs Exemplary embodiments of the invention are described with reference to the drawings. In this case, 21~1023 commercially available chips are referred to by their customary abbreviations and all other circuit components are referred to by numerals. In the drawings:
Figure 1 shows an MPEG encoder with frame stores for reordering and movement compensation Figure 2 shows a method for memory m;n;m;zation Figure 3 shows an MPEG decoder with frame stores for reordering and movement compensation Figure 4 shows a special Huffmann encoder for carrying out a VLC
Exemplary embodiments The method can be used in a multiplicity of data processing devices using all conceivable compression algorithms.
The necessary storage capacity is reduced by the fact that the data are compressed prior to storage and decompressed again when they are read out. The resultant storage capacity is calculated as a function of the compression factor k such that: Spk = Spn / k where Spk: Storage capacity for compressed volume of data Spn: Storage capacity for uncompressed volume of data k : Compression factor The compression factor k is dependent on the selected compression method and the desired quality of the data to be stored.
The invention will now be explained in more detail with regard to the example of video data processing using the MPEG method. Figure 1 illustrates the structure of a conventional MPEG decoder. The uncom-prefised data 1 are reordered in an arithmetic unit 2 (frame reordering), a frame store 3 being used for writing 4 and reading 5. The store is controlled by a control unit by means of control signals 6. The following movement estimator 7 accesses the second frame store 8.
The uncompressed data of preceding frames are stored there. Compression by means of DCT and quantization Q
2151~23 then follows. On the one hand, the data are then subjected to variable length coding (VLC), are buffered in a buffer 9 for the purposes of their output and are output as a compressed data stream 10. On the other hand, inverse quantization and inverse DCT are carried out and the data are stored in the frame store 8. The quantization factor can be readjusted in a block-by-block manner by means of a quantization controller 11 (rate control).
The method according to the invention can be inserted into the first stage for reordering and the second stage for movement compensation. The areas of use of the invention in the encoder are illustrated by a broken block 12.
The reordering can be carried out in one step if a fixed compression factor for individual groups is specified independently of the data contents. This can be achieved by the use of suitable source coding methods. A
possible method is DPCM with a fixed code word length, which is subject to losses and is illustrated in Figure 2, or appropriate transformation coding.
Figure 2 illustrates a block 12 for memory m; n; m; zation. Instead of the uncompressed storage of the original video data in the memory, the said data are subjected to DPCM. For this purpose, the data stream 4 is converted with data which are predicted by a predictor 13 and is quantized (Q). The data stream is subsequently coded using a Huffmann method 14 and written to the memory 15. For reading out, the data stream is decoded in a Huffmann decoder 16 and converted with the values predicted by means of the predictor 17.
This method of coding and decoding by means of DPCM has the advantage that the compression factor can be defined and, consequently, access can be made to the data in the memory in a specific manner. In addition, the gate complexity for implementation in a semiconductor chip is quite low.
For separate block line coding/decoding, from experience a compression factor of two can be used for reordering, without substantial impairment to the picture quality occurring. It is possible directly to access any block line by means of hierarchically structured addressing.
This means that all reformatting operations can be carried out in one step, after writing to the memory 15, which should be implemented as RAM with random access, by means of direct addressing of the block lines when they are read out.
Since each group has been compressed without regard to adjacent groups, the signal can subsequently be decompressed again separately.
Another exemplary embodiment of the invention is illustrated in Figure 3. The data stream 4 is subjected to two-dimensional discrete cosine transformation (DCT) and is subsequently quantized by means of a quantization stage (Q).
The quantized date 18 are compressed in a special Huffmann coding section (VLC), which is illustrated in Figure 4. The compressed data stream 19 is then stored in the memory 15. A
quantization controller 20 (rate control) undertakes the control of the quantization. When the compressed data are read out, these steps are then reversed by means of the corresponding inverse operations (VLD, Q~l, DCT-1). In this case, this method, which is similar to the JPEG standard, has the following special features:
a) Frames are only intra-coded.
b) Frames are compressed to a fixed size independently of the frame complexity.
c) The quantization controller 20 operates predictively, that is to say that during the frame compression it also takes account of the volumes of data which are still to be expected from the as yet unprocessed remaining bits.
d) The Huffmann tables are specially adapted as a function of the compression rate, which is determined in turn by the application.
e) If an uncoded block (8 x 8 pixels) contains less data than a coded block, it is stored uncoded.
Any desired architecture can be used for the DCT, , provided that the accuracy requirements in accordance with the underlying standard (for example MPEG or H.261) are met.
The quantization operates essentially in an analogous manner to JPEG and also has the same two-stage structure. The quantization controller 20 readjusts the quantization factor in a block-by-block manner. This is done as a function of the occupancy of the frame store and of the frame complexity to be expected.
A special Huffmann encoder is illustrated in Figure 4. The quantized data are initially read from a first RAM memory 21 using a zig-zag scan. The first value, the DC component (DC) in the frequency range, is written uncoded to the output memory 22. The subsequent AC components (AC values) are coded in an analogous manner to the MPEG standard using the run length method.
The value pairs produced thereby are then transformed by means of a Huffmann table into a bit code of variable length. A Huffmann encoder 23, a multiplexer 24 and a register memory 25 are used for this purpose. It can be discerned at the overflow of the output memory 26 whether the coded block contains more data than the uncoded block. The block is then output after having been DCT-transformed but not, however, compressed.
Therefore, there appears at the output of the VLC
a bit stream having coded and also, partly, uncoded data, which are parallelized by a multiplexer 27 in accordance with the word width of the memory and are stored in the register memory 22. Furthermore, a flag must be set for each block in a further memory, which flag indicates whether the block is uncoded or coded. In addition, the quantization factor associated with the block must be stored.
It can be ensured by means of algorithms which are dependent on the application that the frame store is always utilized completely, with the result that an optimum is established between picture quality and memory requirement. The quantization controller 20 together with the quantization section (Q) and the Huffmann coding section (VLC) determine the compression factor.
The decoding of the frame store data using the inverse method takes place in an analogous manner to the VLC.
In this case, the flag which serves to indicate whether a block is coded or uncoded has to be evaluated.
The dequantization operates in an analogous manner to the quantization. The 12-bit-wide input data for the inverse DCT and produced.
Any hardware can be used for the inverse discrete cosine transformation (DCT-1), provided that the requirements of the respective standard are upheld.
The use of the invention is additionally illustrated in Figure 5 with regard to an MPEG video decoder.
In this case, the method can be used, on the one hand, for the reordering of the data stream after the header detection 28. The buffer 29 which is normally used for this purpose can be replaced by the method 12 according to the invention.
The method for movement compensation can be used advantageously. The video data which have been decoded by means of VLD, Q~1 and DCT-1 are compressed, if they are I- or P-pictures, according to the method shown in Figure 3 and are written to the frame store 30. They are available there for a future P- or B-picture to be decoded. In this way, the last two P-pictures or one I- and one P-picture are always available in the frame store after having been compressed.
The data are decompressed again by means of the inverse method and are fed to the decompensation stage 31. The B-pictures are not buffered but rather forwarded from the decompensation stage 31 directly via a multiplexer 32 to the output unit.
The store 30 is split into two partial areas which each have two banks. The memory addresses are generated by the vectors of the VLD and stored in an address memory 33.
The following unit must be able to receive the video data in blocks and not in lines, as is necessary in the case of monitors.
the case of monitors.
The estimated hardware expenditure with and without memory minimization is given below by way of comparison for an MPEG decoder, for two CCIR 601 standard frames, with a 4:2:0 chroma format:
If a compression factory of k-3 is selected for the frame store data for the highest picture quality, then only 44/3 Mbytes are transmitted averaged over 1/50 s. This corresponds to a bit rate of 14.7 Mbyte/s. The memory size of the frame store required for this is then: 720 frame columns x 288 frame lines x (8 + 4 bits per pixel) x 4 memory banks 2 I- and 2 P-pictures) / k - approximately 10/k Mbits =
approximately 3.3 Mbits.
The start addresses together with the quantization factor and the flag for coded or uncoded data have to be stored for each block in an address memory. Under the conditions stipulated above, the resulting word width of the address for the frame store is 26 bits per block.
The number of required entries in the address memory depends on the number of blocks, the block size and the standard of the frame: 720 frame columns / 8 (horizontal block size) x 288 frame lines / 8 (vertical block size) x 1.5 (luminance and chrominance) = 4860 blocks per memory bank.
There follows from this a total number of 19,440 entries, each of 26 bits, that is to say approximately 505 kbits for the address memory.
An additional expenditure on hardware is necessary for the special driving of the frame store in an MPEG decoder, which hardware comprises a two-dimensional DCT, a quantizer (Q) and a Huffmann encoder (VLC) including an quantization controller 20. For reading from the frame store, an inverse DCT (DCT-1), a dequantizer (Q~l) and a Huffmann decoder (VLD) are required for each partial store.
Hardware to be Memory m;n;m; zation implemented with without 2 DCT-1 (60 MHz) 24,000 gates 0 gates 2 Q~1 10,000 gates 0 gates 2 VLD 10,000 gates 0 gates 1 VLC 8,000 gates 0 gates 1 Q 5,000 gates 0 gates 1 DCT (16 MHz)8,000 gates 0 gates 1 rate control5,000 gates 0 gates Address memory505 kbits 0 bits Frame store3.3 Mbits 10 Mbits TOTAL 70,000 gates 10 Mbits + approximately 3.8 Mbits Overall, therefore, the resulting memory require-ment for the frame store is 3.3 Mbits (data memory) + 0.515 Mbit (address memory) = approximately 3.8 Mbits, compared with 10 Mbits for the uncompressed storage of frames in CCIR 601, 4:2:0.
The hardware expenditure could possibly be reduced further in the event of time-division multiplex operation of individual moduleæ (for example DCTs, Qs) in conjunction with the use of high-speed technologies.
However, this is dependent on the individual application and on the limiting frequency of the technology compared with the standard-dependent volume of data to be pro-cessed.
When the described method for movementcompensation is used, accumulation of the errors produced by the said compression is normally retained and carried over to the next I-picture. If this is not desired, it is possible to limit the error propagation to the successive B-pictures using the following method:
First of all, an I- or P-picture is written uncompressed to the store. The subsequent incoming I- or P-picture is likewise stored uncompressed for the first - 2t~023 64 lines, depending on the maximum length of the movement vector, and iæ decompensated with the uncompressed I-/P-picture. Then, at the same time, the procedures of reading out the I-picture, compressing it and rewriting it to the store at another location are begun.
The compression in the method according to the invention can also be carried out without any transformation. The video data can be compressed in the space domain by means of the Shannon Entropy Theorem without being converted into the frequency domain by means of DCT/DCT-1 or other transformations. For this purpose, an optimum Huffmann table of the data is initially calculated in the space domain, using the probability distribution of the brightness and chrom;n~nce values in the space ~om~;n. In this case, the Huffmann table is either determined online for each frame excerpt or is established definitely by prior calcula-tion. The advantage of this method is less compression complexity. In order to guarantee a fixed output data rate, this method must be extended by a suitable quantization stage.
Claims (9)
1. Method for the coding/decoding of a data stream, including the method stages of reordering as well as compression and decompression of the data, the data being stored in a buffer for the purpose of reordering and being read from the buffer in a different order, charac-terized in that the data are stored in the buffer after having been compressed and are decompressed again when they are read out.
2. Method according to Claim 1, data blocks from the data stream being stored in a second buffer and read out again in the stage of compression and decompression, characterized in that the data are stored in the second buffer after having been compressed and are decompressed again when they are read out.
3. Method according to Claim 1, characterized by a compression method in which the structures and sizes of individual data groups as well as the buffering location are defined independently of the data contents and the compression factor of individual data groups is defined.
4. Method according to Claim 1, 2 or 3, character-ized in that differential pulse code modulation (DPCM) is used for the compression and decompression.
5. Method according to Claim 4, characterized in that the differential pulse code modulation (DPCM) is carried out using two-dimensional predictors (13 and 17) which operate in a block-by-block manner.
6. Method according to one of Claims 4 and 5, characterized in that the memory locations are assigned by means of hierarchically structured addressing.
7. Method according to Claim 2, characterized in that the data are subjected to a two-dimensional discrete cosine transformation (DCT), are then stored in the memory after having been compressed by means of a quantization stage (Q) and a Huffmann coding section (VLC) and are decompressed again when they are read out by means of the corresponding inverse operations (VLD, Q-1, DCT).
8. Method according to Claim 7, characterized in that the quantization stage (Q) is controlled by a predictively operating quantization controller (20).
9. Method according to Claim 1, 2 or 4, characterized in that one-dimensional transformation coding is used for the compression and decompression.
Applications Claiming Priority (4)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
DEP4419678.4 | 1994-06-06 | ||
DE4419678A DE4419678A1 (en) | 1994-06-06 | 1994-06-06 | Storing picture, video and film information in semiconductor memories |
DE4436956A DE4436956C2 (en) | 1994-10-15 | 1994-10-15 | Device and method for reformatting or temporarily storing data streams |
DEP4436956.5 | 1994-10-15 |
Publications (1)
Publication Number | Publication Date |
---|---|
CA2151023A1 true CA2151023A1 (en) | 1995-12-07 |
Family
ID=25937196
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CA002151023A Abandoned CA2151023A1 (en) | 1994-06-06 | 1995-06-05 | Method of coding/decoding of a data stream |
Country Status (4)
Country | Link |
---|---|
EP (1) | EP0687111B1 (en) |
AT (1) | ATE246864T1 (en) |
CA (1) | CA2151023A1 (en) |
DE (1) | DE59510756D1 (en) |
Cited By (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US6377628B1 (en) | 1996-12-18 | 2002-04-23 | Thomson Licensing S.A. | System for maintaining datastream continuity in the presence of disrupted source data |
US6496537B1 (en) | 1996-12-18 | 2002-12-17 | Thomson Licensing S.A. | Video decoder with interleaved data processing |
CN1106117C (en) * | 1995-12-27 | 2003-04-16 | 汤姆森消费电子有限公司 | Image signal processor system and method, and memory management therefor |
US6594315B1 (en) | 1996-12-18 | 2003-07-15 | Thomson Licensing S.A. | Formatting of recompressed data in an MPEG decoder |
US6879631B1 (en) | 1996-12-18 | 2005-04-12 | Thomson Licensing S.A. | Selective compression network in an MPEG compatible decoder |
US8321326B2 (en) | 2009-09-15 | 2012-11-27 | Auerbach Group Llc | Method and system for enhancing the efficiency of a digitally communicated data exchange |
Families Citing this family (32)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
AU712182B2 (en) * | 1994-06-28 | 1999-10-28 | Lynx System Developers, Inc. | Event recording camera system |
JP3992303B2 (en) * | 1995-06-22 | 2007-10-17 | ソニー株式会社 | Signal compression apparatus, signal expansion apparatus, signal compression method, and signal expansion method |
JP3552811B2 (en) * | 1995-09-29 | 2004-08-11 | 三菱電機株式会社 | Digital video signal encoding device and decoding device |
GB2306829A (en) * | 1995-10-20 | 1997-05-07 | Amstrad Plc | Digital video decoding apparatus |
CN1158050A (en) * | 1995-12-27 | 1997-08-27 | 汤姆森消费电子有限公司 | Image data compression system |
CA2185753C (en) * | 1996-03-04 | 2000-09-12 | Hideo Ohira | Digital image decoding apparatus |
US5701158A (en) * | 1996-03-04 | 1997-12-23 | Mitsubishi Denki Kabushiki Kaisha | Digital image decoding apparatus |
JP3575508B2 (en) * | 1996-03-04 | 2004-10-13 | Kddi株式会社 | Encoded video playback device |
JPH09247671A (en) * | 1996-03-04 | 1997-09-19 | Mitsubishi Electric Corp | Digital image decoder |
US6020924A (en) * | 1996-04-12 | 2000-02-01 | Samsung Electronics Co., Ltd. | Reduced memory size set top box which stores frames and associated motion vectors which indicate which block or blocks are to be retrieved from memory |
US5818530A (en) * | 1996-06-19 | 1998-10-06 | Thomson Consumer Electronics, Inc. | MPEG compatible decoder including a dual stage data reduction network |
GB9622725D0 (en) * | 1996-10-31 | 1997-01-08 | Sgs Thomson Microelectronics | A method and circuitry for compressing and decompressing digital data |
US6028635A (en) * | 1996-12-03 | 2000-02-22 | Stmicroelectronics, Inc. | Reducing the memory required for decompression by storing compressed information using DCT based techniques |
US6167086A (en) * | 1996-12-10 | 2000-12-26 | Thomson Licensing S.A. | Overhead data processor in a memory efficient image processing system |
US5844608A (en) * | 1996-12-12 | 1998-12-01 | Thomson Consumer Electronics, Inc. | Picture element processor for a memory management system |
US6256347B1 (en) | 1996-12-17 | 2001-07-03 | Thomson Licensing S.A. | Pixel block compression apparatus in an image processing system |
WO1998027734A1 (en) * | 1996-12-18 | 1998-06-25 | Thomson Consumer Electronics, Inc. | Efficient fixed-length block compression and decompression |
US6970504B1 (en) | 1996-12-18 | 2005-11-29 | Thomson Licensing | Parallel decoding of interleaved data streams within an MPEG decoder |
DE69734386D1 (en) * | 1997-02-06 | 2006-03-02 | St Microelectronics Srl | Method for storage reduction in a video decoder |
US6130911A (en) * | 1997-11-21 | 2000-10-10 | Sharp Laboratories Of America, Inc. | Method and apparatus for compressing reference frames in an interframe video codec |
EP0920204B1 (en) * | 1997-11-24 | 2006-02-15 | STMicroelectronics S.r.l. | MPEG-2 decoder with reduced RAM requisite by recompression using adaptive tree search vector quantization |
EP1078504B1 (en) * | 1998-05-14 | 2004-07-28 | Interval Research Corporation | Video compression with storage reduction, color rotation, combined signal and border filtering |
US7130351B1 (en) | 1998-05-14 | 2006-10-31 | Vulcan Patents Llc | Storage reduction during compression |
US6516030B1 (en) | 1998-05-14 | 2003-02-04 | Interval Research Corporation | Compression of combined black/white and color video signal |
US6229852B1 (en) * | 1998-10-26 | 2001-05-08 | Sony Corporation | Reduced-memory video decoder for compressed high-definition video data |
US6570924B1 (en) | 1998-11-20 | 2003-05-27 | Interval Research Corp | Low cost video compression using fast, modified Z-coding of wavelet pyramids |
KR100300887B1 (en) * | 1999-02-24 | 2001-09-26 | 유수근 | A method for backward decoding an audio data |
US6807311B1 (en) * | 1999-07-08 | 2004-10-19 | Ati International Srl | Method and apparatus for compressing and storing image data |
EP1298937A1 (en) * | 2001-09-26 | 2003-04-02 | Chih-Ta Star Sung | Video encoding or decoding using recompression of reference frames |
JP4359773B2 (en) * | 2004-06-22 | 2009-11-04 | ソニー株式会社 | Image compression processing apparatus, image compression processing method, and image compression processing program |
JP5234241B2 (en) * | 2004-12-28 | 2013-07-10 | 日本電気株式会社 | Moving picture encoding method, apparatus using the same, and computer program |
JP5396711B2 (en) * | 2006-02-09 | 2014-01-22 | 日本電気株式会社 | Moving picture decoding apparatus, moving picture decoding method, and program |
Family Cites Families (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2959773B2 (en) * | 1989-04-20 | 1999-10-06 | オリンパス光学工業株式会社 | Electronic still camera |
US5016107A (en) * | 1989-05-09 | 1991-05-14 | Eastman Kodak Company | Electronic still camera utilizing image compression and digital storage |
US5249053A (en) * | 1991-02-05 | 1993-09-28 | Dycam Inc. | Filmless digital camera with selective image compression |
EP0535272A1 (en) * | 1991-10-02 | 1993-04-07 | Alcatel N.V. | Hybrid encoder arrangement for an image processing system |
JPH05236466A (en) * | 1992-02-25 | 1993-09-10 | Nec Corp | Device and method for inter-frame predictive image encoding for motion compensation |
TW241416B (en) * | 1992-06-29 | 1995-02-21 | Sony Co Ltd |
-
1995
- 1995-06-02 DE DE59510756T patent/DE59510756D1/en not_active Expired - Fee Related
- 1995-06-02 EP EP95108497A patent/EP0687111B1/en not_active Expired - Lifetime
- 1995-06-02 AT AT95108497T patent/ATE246864T1/en not_active IP Right Cessation
- 1995-06-05 CA CA002151023A patent/CA2151023A1/en not_active Abandoned
Cited By (8)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN1106117C (en) * | 1995-12-27 | 2003-04-16 | 汤姆森消费电子有限公司 | Image signal processor system and method, and memory management therefor |
US6377628B1 (en) | 1996-12-18 | 2002-04-23 | Thomson Licensing S.A. | System for maintaining datastream continuity in the presence of disrupted source data |
US6496537B1 (en) | 1996-12-18 | 2002-12-17 | Thomson Licensing S.A. | Video decoder with interleaved data processing |
US6594315B1 (en) | 1996-12-18 | 2003-07-15 | Thomson Licensing S.A. | Formatting of recompressed data in an MPEG decoder |
US6879631B1 (en) | 1996-12-18 | 2005-04-12 | Thomson Licensing S.A. | Selective compression network in an MPEG compatible decoder |
US8321326B2 (en) | 2009-09-15 | 2012-11-27 | Auerbach Group Llc | Method and system for enhancing the efficiency of a digitally communicated data exchange |
US8538861B2 (en) | 2009-09-15 | 2013-09-17 | Auerbach Group Llc | Use of adaptive and/or customized compression to enhance the efficiency of digital financial data exchanges |
US8756149B2 (en) | 2009-09-15 | 2014-06-17 | Auerbach Group Llc | Use of adaptive and/or customized compression to enhance the efficiency of digital data exchanges |
Also Published As
Publication number | Publication date |
---|---|
EP0687111A3 (en) | 1998-12-16 |
EP0687111B1 (en) | 2003-08-06 |
EP0687111A2 (en) | 1995-12-13 |
DE59510756D1 (en) | 2003-09-11 |
ATE246864T1 (en) | 2003-08-15 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CA2151023A1 (en) | Method of coding/decoding of a data stream | |
KR100574415B1 (en) | Multiple standard decompression and / or compression units | |
US5838597A (en) | MPEG-2 decoding with a reduced RAM requisite by ADPCM recompression before storing MPEG-2 decompressed data | |
KR100253931B1 (en) | Approximate mpeg decoder with compressed reference frames | |
KR100781629B1 (en) | A method for reducing the memory required for decompression by storing compressed information using DCT base technology and a decoder for implementing the method | |
US5724446A (en) | Video decoder apparatus using non-reference frame as an additional prediction source and method therefor | |
US6961063B1 (en) | Method and apparatus for improved memory management of video images | |
US6157741A (en) | Image processing apparatus and image processing method | |
US5933195A (en) | Method and apparatus memory requirements for storing reference frames in a video decoder | |
US8811493B2 (en) | Method of decoding a digital video sequence and related apparatus | |
JPH118849A (en) | Picture encoding method and device therefor | |
US20020057739A1 (en) | Method and apparatus for encoding video | |
JPH1084524A (en) | Mpeg decode method compensating reduced remaining capacity of ram due to adpcm re-compression before storing mpeg expansion data and as required after sampling algorithm and its decoder | |
US6999511B1 (en) | Dynamically switching quant matrix tables within an MPEG-2 encoder | |
JPH08116539A (en) | Dynamic image coder and dynamic image coding method | |
JP2898413B2 (en) | Method for decoding and encoding compressed video data streams with reduced memory requirements | |
JP2001145112A (en) | Device and method for composing dynamic image and recording medium | |
EP0858206B1 (en) | Method for memory requirement reduction in a video decoder | |
US20030147468A1 (en) | Image data coding apparatus capable of promptly transmitting image data to external memory | |
US20020159526A1 (en) | Video encoder and video recording apparatus provided with such a video encoder | |
US6452968B2 (en) | Circuitry and apparatus for converting a decoded image with a macroblock/raster scan conversion capability | |
JP2776284B2 (en) | Image coding device | |
US6377627B1 (en) | Method and apparatus for decoding MPEG video data | |
US5774590A (en) | Image data reproducing apparatus | |
US20060222247A1 (en) | Hardware implementation of inverse scan for a plurality of standards |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
FZDE | Discontinued |