Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
2000-06-29
2002-09-03
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
C341S051000
Reexamination Certificate
active
06445312
ABSTRACT:
The present invention concerns a method of compression by blocks of digital data used notably in the field of the compression of a still or moving digital image.
It also concerns a compression device adapted to implement the compression method according to the invention.
The technical field of the invention is the compression, with loss, of digital data representing physical quantities, and notably representing the pixel value for a digital image, for applications such as videotelephony on a transmission network in which real-time compression methods are used.
The invention applies particularly to compression systems implemented by software, on an operating system capable of making the computing resources visible. The operating system can form part notably of a generic host computer, with shared resources limited notably with regard to computing resources.
A compression method is particularly considered in which the data to be compressed are first of all partitioned into a set of blocks, each of these blocks being coded by a coding technique chosen amongst a finite set of acceptable coding techniques.
Generally, coding techniques with loss are described on the one hand in terms of distortion, a distortion which becomes less and less corresponding to a finer and finer approximation of the coded digital signal, and on the other hand in terms of rate, that is to say coding cost.
In a conventional fashion, the different coding techniques applicable are chosen according to a rate/distortion compromise. It is a case in particular of best minimising the distortion under the constraint of an allocated rate or, conversely, best minimising the coding rate under the constraint of a given distortion.
However, the complexity of the compression algorithms used conventionally in the coding of digital data, and in particular during the coding of a video signal, is very great and makes real-time compression of a digital signal with reasonable resolution very difficult.
A technique making it possible to take into account this concept of time was disclosed in the document published in the context of the MPEG (Moving Picture Expert Group) standard entitled “Informative annex about the use and implementation of complexity estimation and CGD”, by Marco Mattavelli and Sylvain Brunetton, Document ISO/IECJTC1/SC29NVG11/MPEG98/M3073, February 1998.
This technique, referred to as CGD (the acronym for “Computational Graceful Degradation”) makes it possible to deliver, when a coded digital signal is compressed, a decoded signal of lesser quality when the required quality cannot be obtained in real time with the computing resources available on the operating system implementing the decoding.
However, this technique only makes it possible to adapt the decoder to the calculation resources of the system, as a function mainly of the structure of the bit stream generated by the compression operation used, in this case a compression according to the MPEG4 standard.
The present invention on the other hand relates to a compression method which can adapt to the computing resources of the system implementing it.
The present invention thus concerns a method of compression by blocks of digital data representing physical quantities, comprising a coding configuration step in which, with each block of digital data, there is associated a coding technique coded from amongst the set of coding techniques acceptable according to a criterion.
In accordance with the invention, this choice criterion is a function of optimisation of the rate or distortion characterising the coding configuration under the constraint of a given computational resource.
The compression method according to the invention makes it possible to choose a block coding configuration best using a computational resource, explicitly taking into account a compromise between the computational complexity and the performance in terms of rate/distortion of each available coding technique.
As a general rule, the greater the computational resource, the higher the rate/distortion performance. Thus, for a given computation time resource, it is a case of best consuming it by maximising the rate/distortion performance.
Preferably, this compression method comprises a computing step for each block of digital data and for each coding technique of an elementary consumed computational resource by the coding technique expressed in time of calculation.
Thus each coding technique is characterised in terms of consumed computational complexity, and no longer solely in terms of rate and distortion.
Advantageously, the computational resource incorporates the computing time for obtaining said elementary consumed computational resource and the consumed computational resource for resolving the optimisation function.
Thus a computational resource constraint is used which integrates both the resource consumed for obtaining elementary quantities but also the resource consumed by the optimisation algorithm in order to know the computational resource actually available for achieving the compression of the digital data.
According to different particularly practical embodiments of the invention,
the optimisation function is adapted to minimise a rate associated with the coding configuration for a computational complexity less than a given computational resource; or
the optimisation function is adapted to minimise a mean distortion associated with the coding configuration for a computational complexity less than a given computational resource; or
the optimisation function is adapted to minimise an upper bound distortion associated with the coding configuration for a computational complexity less than a given computational resource.
According to another preferred characteristic of the invention, the compression method comprises a prior step of choosing a criterion amongst a function of optimisation of the rate or of the distortion characterising the coding configuration under the constraint of a given computational resource, a function of optimisation of the rate characterising the coding configuration under the constraint of a given distortion and a function of optimisation of the distortion characterising the coding configuration under the constraint of a given rate.
The compression method thus advantageously makes it possible to effect a normal optimisation of the rate/distortion performance (that is to say a minimisation of the distortion under the constraint of a given rate or a minimisation of a rate under the constraint of a given distortion) when no calculation time constraint is required for compressing the digital signal.
In practice, the said set of acceptable coding techniques comprises inter coding techniques, such as a predictive coding by movement compensation, a coding by time prediction or a coding by multilinear prediction, and intra coding techniques, such as a coding by spectral transformation or a coding by vector quantisation.
The compression method according to the invention thus makes it possible to choose, amongst conventional coding techniques, those which best meet the choice criterion.
According to a preferred characteristic of the invention, which also makes it possible to improve the coding of a set of digital data, the compression method also comprises a step of partitioning into blocks of digital data representing physical quantities, in which the partitioning of blocks is effected by a partitioning under the constraint of a given computational resource.
Thus a partitioning of the digital data is effected which makes it possible to best use the available computational resources of the system implementing the compression.
In practice, the present invention is particularly well suited to a compression method comprising a step of partitioning into blocks of digital data representing a digital image or a digital video signal.
Correlatively, the present invention concerns a device for compressing by blocks of digital data representing physical quantities, comprising coding configuration means adapted to associate, with each block of digital data, a coding technique ch
LandOfFree
Method and device for compression by blocks of digital data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for compression by blocks of digital data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for compression by blocks of digital data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896789