Reduced Error Processing of Transformed digital Data

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
8Forward
Citations 
0
Petitions 
0
Assignments
First Claim
0 Assignments
0 Petitions
Accused Products
Abstract
This invention solves problems due to employing error degraded data in digital processing. It particularly solves multigeneration problems wherein transform data degrade during each inverse transform and forward transform cycle even without any processing due to the rounding and clipping errors. It provides methods, systems and devices for reducederror processing of transformcoded data. After inverse transformation of transform data, highprecision numbers are manipulated. The converting to integers and clipping to an allowed range steps are executed at any stage in the manipulation to obtain integer representation of the inverse transformed data such as for displaying of the data. However, further processing including forward transforming back to the transform domain is executed on the highprecision numbers. Thus, the rounding and clipping errors are not present in the processed data. Although advantageous to many applications employing digital transformed data, the invention is particularly advantageous for use in digital studios during editing of MPEGcoded, JPEGcoded and waveletcoded video and audio data.
12 Citations
View as Search Results
METHOD AND DEVICE FOR AVOIDING ROUNDING ERRORS AFTER PERFORMING AN INVERSE DISCRETE ORTHOGONAL TRANSFORMATION  
Patent #
US 20100208807A1
Filed 02/16/2010

Current Assignee
SONNHALDENSTRASSE 7, EcoDisc Technology AG

Sponsoring Entity
SONNHALDENSTRASSE 7, EcoDisc Technology AG

INVERSE QUANTIZATION CIRCUIT, INVERSE QUANTIZATION METHOD AND IMAGE REPRODUCING APPARATUS  
Patent #
US 20100014582A1
Filed 02/26/2008

Current Assignee
Sovereign Peak Ventures LLC

Sponsoring Entity
Panasonic Corporation

DISPERSED DATA STORAGE SYSTEM DATA DECODING AND DECRYPTION  
Patent #
US 20100269008A1
Filed 08/31/2009

Current Assignee
Pure Storage Inc.

Sponsoring Entity
Pure Storage Inc.

METHODS AND APPARATUS FOR SPATIALLY VARYING RESIDUE CODING  
Patent #
US 20120099642A1
Filed 07/01/2010

Current Assignee
Interdigital Vc Holdings Inc.

Sponsoring Entity
Thomson Licensing

VIDEO DECODER WITH REDUCED DYNAMIC RANGE TRANSFORM WITH QUANTIZATION MATRICIES  
Patent #
US 20120230395A1
Filed 03/11/2011

Current Assignee
Sharp Electronics Corporation

Sponsoring Entity
Sharp Electronics Corporation

Inverse quantization circuit, inverse quantization method and image reproducing apparatus  
Patent #
US 8,401,073 B2
Filed 02/26/2008

Current Assignee
Sovereign Peak Ventures LLC

Sponsoring Entity
Panasonic Corporation

Methods and apparatus for spatially varying residue coding  
Patent #
US 9,736,500 B2
Filed 07/01/2010

Current Assignee
Interdigital Vc Holdings Inc.

Sponsoring Entity
Thomson Licensing

Dispersed data storage system data decoding and decryption  
Patent #
US 10,447,474 B2
Filed 08/31/2009

Current Assignee
Pure Storage Inc.

Sponsoring Entity
Pure Storage Inc.

Video postfiltering with motioncompensated temporal filtering and/or spatialadaptive filtering  
Patent #
US 6,178,205 B1
Filed 12/12/1997

Current Assignee
Cisco Technology Incorporated

Sponsoring Entity
Vtel Corporation

Picture signal encoding method and apparatus, picture signal transmitting method, picture signal decoding method and apparatus and recording medium  
Patent #
US 6,256,349 B1
Filed 12/24/1996

Current Assignee
Sony Corporation

Sponsoring Entity
Sony Corporation

Array processing with fused multiply/add instruction  
Patent #
US 5,719,964 A
Filed 10/10/1995

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Decompression of standard ADCTcompressed images  
Patent #
US 5,379,122 A
Filed 10/02/1992

Current Assignee
Xerox Corporation

Sponsoring Entity
Xerox Corporation

0 Claims
1 Specification
The present application is related to the following applications even dated herewith: Attorney docket number Y0998372, entitled, “Transformdomain correction of realdomain errors,” by inventors J. Mitchell et al., and Attorney docket number Y0998373, entitled, “Error reduction in transformed digital data,” by inventors M. Bright et al., which are incorporated herein in entirety by reference.
This invention relates to transform coding of digital data, specifically to real domain processing of transform data. More particularly, this invention relates to reducederror digital processing of inverse transformed data.
Transform coding is the name given to a wide family of techniques for data coding, in which each block of data to be coded is transformed by some mathematical function prior to further processing. A block of data may be a part of a data object being coded, or may be the entire object. The data generally represent some phenomenon, which may be for example a spectral or spectrum analysis, an image, an audio clip, a video clip, etc. The transform function is usually chosen to reflect some quality of the phenomenon being coded; for example, in coding of audio, still images and motion pictures, the Fourier transform or Discrete Cosine Transform (DCT) can be used to analyze the data into frequency terms or coefficients. Given the phenomenon being coded, there is generally a concentration of the information into a few frequency coefficients. Therefore, the transformed data can often be more economically encoded or compressed than the original data. This means that transform coding can be used to compress certain types of data to minimize storage space or transmission time over a communication link.
An example of transform coding in use is found in the Joint Photographic Experts Group (JPEG) international standard for still image compression, as defined by ITUT Rec. T.81 (1992)ISO/IEC 109181:1994, Information technology—Digital compression and coding of continuoustone still images, Part 1: Requirements and Guidelines. Another example is the Moving Pictures Experts Group (MPEG) international standard for motion picture compression, defined by ISO/IEC 11172:1993, Information Technology—Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbits/s. This MPEG1 standard defines systems for both video compression (Part 2 of the standard) and audio compression (Part 3). A more recent MPEG video standard (MPEG2) is defined by ITUT Rec. H.262ISO/IEC 138182: 1996 Information Technology Generic Coding of moving pictures and associated audio—Part 2: video. A newer audio standard is ISO/IEC 138183: 1996 Information Technology—Generic Coding of moving pictures and associated audio—Part 3: audio. All three image international data compression standards use the DCT on 8x8 blocks of samples to achieve image compression. DCT compression of images is used herein to give illustrations of the general concepts put forward below; a complete explanation can be found in Chapter 4 “The Discrete Cosine Transform (DCT)” in W. B. Pennebaker and J. L. Mitchell, JPEG: Still Image Data Compression Standard, Van Nostrand Reinhold: N.Y., (1993).
Wavelet coding is another form of transform coding. Special localized basis functions allow wavelet coding to preserve edges and small details. For compression the transformed data is usually quantized. Wavelet coding is used for fingerprint identification by the FBI. Wavelet coding is a subset of the more general subband coding technique. Subband coding uses filter banks to decompose the data into particular bands. Compression is achieved by quantizing the lower frequency bands more finely than the higher frequency bands while sampling the lower frequency bands more coarsely than the higher frequency bands. A summary of wavelet, DCT, and other transform coding is given in Chapter 5 “Compression Algorithms for Diffuse Data” in Roy Hoffman, Data Compression in Digital Systems, Chapman and Hall: New York, (1997).
In any technology and for any phenomenon represented by digital data, the data before a transformation is performed are referred to as being “in the real domain”. After a transformation is performed, the new data are often called “transform data” or “transform coefficients”, and referred to as being “in the transform domain”. The function used to take data from the real domain to the transform domain is called the “forward transform”. The mathematical inverse of the forward transform, which takes data from the transform domain to the real domain, is called the respective “inverse transform”.
In general, the forward transform will produce realvalued data, not necessarily integers. To achieve data compression, the transform coefficients are converted to integers by the process of quantization. Suppose that (λ_{i}) is a set of realvalued transform coefficients resulting from the forward transform of one unit of data. Note that one unit of data may be a onedimensional or twodimensional block of data samples or even the entire data. The “quantization values” (q_{i}) are parameters to the encoding process. The “quantized transform coefficients” or “transformcoded data” are the sequence of values (α_{i}) defined by the quantization function Q:
where └x┘ means the greatest integer less than or equal to x. The resulting integers are then passed on for possible further encoding or compression before being stored or transmitted. To decode the data, the quantized coefficients are multiplied by the quantization values to give new “dequantized coefficients” (λ_{i}′) given by
λ_{i}′=q_{i}α_{i}. (2)
The process of quantization followed by dequantization (also called inverse quantization) can thus be described as “rounding to the nearest multiple of q_{i}”. The quantization values are chosen so that the loss of information in the quantization step is within some specified bound. For example, for audio or image data, one quantization level is usually the smallest change in data that can be perceived. It is quantization that allows transform coding to achieve good data compression ratios. A good choice of transform allows quantization values to be chosen which will significantly cut down the amount of data to be encoded. For example, the DCT is chosen for image compression because the frequency components which result produce almost independent responses from the human visual system. This means that the coefficients relating to those components to which the visual system is less sensitive, namely the highfrequency components, may be quantized using large quantization values without perceptible loss of image quality. Coefficients relating to components to which the visual system is more sensitive, namely the lowfrequency components, are quantized using smaller quantization values.
The inverse transform also generally produces noninteger data. Usually the decoded data are required to be in integer form. For example, systems for the playback of audio data or the display of image data generally accept input in the form of integers. For this reason, a transform decoder generally includes a step that converts the noninteger data from the inverse transform to integer data, either by truncation or by rounding to the nearest integer. There is also often a limit on the range of the integer data output from the decoding process in order that the data may be stored in a given number of bits. For this reason the decoder also often includes a “clipping” stage that ensures that the output data are in an acceptable range. If the acceptable range is [a,b], then all values less than a are changed to a, and all values greater than b are changed to b.
These rounding and clipping processes are often considered an integral part of the decoder, and it is these which are the cause of inaccuracies in decoded data and in particular when decoded data are reencoded. For example, the JPEG standard (Part 1) specifies that a source image sample is defined as an integer with precision P bits, with any value in the range 0 to 2**P−1. The decoder is expected to reconstruct the output from the inverse discrete cosine transform (IDCT) to the specified precision. For the baseline JPEG coding P is defined to be 8; for other DCTbased coding P can be 8 or 12. The MPEG2 video standard states in Annex A (Discrete cosine transform) “The input to the forward transform and the output from the inverse transform is represented with 9 bits.”
For JPEG the compliance test data for the encoder source image test data and the decoder reference test data are 8 bit/sample integers. Even though rounding to integers is typical, some programming languages convert from floating point to integers by truncation. Implementations in software that accept this conversion to integers by truncation introduce larger errors into the realdomain integer output from the inverse transform.
The term “highprecision” is used herein to refer to numerical values which are stored to a precision more accurate than the precision used when storing the values as integers. Examples of highprecision numbers are floatingpoint or fixedpoint representations of numbers.
In light of the problems described above regarding inaccuracies caused by digital processing techniques and by such things as rounding and clipping after the inverse transform of transform data, one aspect of this invention provides a method for processing transform data in the real domain. This method reduces the undesired errors in the data produced by such things as rounding to integers and clipping to an allowed range after the inverse transform. In an embodiment, this method includes: performing the inverse transform of the transform data such that the realdomain data produced are in the form of highprecision numbers; processing these highprecision numbers; and converting the processed highprecision numbers to integers and clipping to an allowed range only after the processing stage is complete.
It is another aspect of this invention to provide a method for processing transformcoded data in the real domain which reduces the undesired errors in the data produced by the converting to integers and clipping to an allowed range after the inverse transform. In an embodiment, the method includes: performing the inverse quantization of the transformcoded data; performing the inverse transform of the transform data thus produced, such that the realdomain data produced are in the form of highprecision numbers; processing these highprecision numbers; and converting the processed highprecision numbers to integers and clipping to an allowed range only after the processing stage is complete.
Still another aspect of the present invention is to provide a method for processing transformcoded data in the real domain to produce new transformcoded data, which reduces the error produced by converting to integers and clipping to an allowed range after the inverse transform. In an embodiment, this method includes: performing the inverse quantization of the transformcoded data; performing the inverse transform of the transform data thus produced, such that the realdomain data produced are in the form of highprecision numbers; processing these highprecision numbers; performing the forward transform on the processed highprecision numbers; and performing quantization on the new transform data. If the errors in the forward and inverse transforms and in the processing are sufficiently small, there will be no undesirable errors produced in the new quantized transformdomain data.
There is no requirement that the input data to the methods described herein need come from a single data source. Thus, this invention is not restricted to the realdomain processing of data from a single source, but also applies to realdomain processing of data from multiple sources, such as the merging of images or audio data.
The quantization described in the background is the linear quantization used in international image data compression standards such as JPEG and MPEG. There is no requirement that the quantization be linear. Any mapping that reduces the number of transform data levels in a deterministic way can be used with this invention. The quantization step has been described mathematically with a division in Equation (1). Actual embodiments may use a lookup table or a sequence of comparisons to achieve similar results.
It is a further aspect of the invention to provide apparatus, a computer product and an article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to perform the methods of the present invention.
These and other objects, features, and advantages of the present invention will become apparent upon further consideration of the following detailed description of the invention when read in conjunction with the drawing figures, in which:
This invention provides methods, systems, and computer products which reduce or eliminate errors introduced by the processing of digital data. Firstly, the source of the error is analyzed and described. This is followed by a presentation of the invention concepts for error reduction and elimination. It is particularly noted that data manipulation and/or processing as employed heretobefore used digital techniques contaminated by the continued introducing of errors by the respective implementation of digital processing. These techniques employed for years are responsible for an inability to maintain original data precision and the continued deterioration of the data representing the phenomenon as more processing is performed. This is particularly detrimental when a process is performed on data which contain errors imparted on the data by previous processes. This results in the continued impairment of the data which thereby becomes less and less useful as more and more processes are performed thereupon.
The seriousness of the problem as realized by the inventors of the present invention is described forthwith. It is noted that in the figures presented herein, optional steps are often shown with dashed lines and/or boxes.
It is noted that the concepts of the present invention are useful in almost any digital processing technology. However, the subsequent description is mostly related to image data. This is because of the general availability and continued usage of image data compression standards which are employed worldwide. These standards require the introduction into the digital data of the errors to be described and the continued employment and processing of the error contaminated data. These standards basically teach away from the present invention. Thus image technology is a good example for describing the present invention.
One aspect of the present invention is concerned with the manipulation of both transform data and transformcoded data. The words “manipulation” and “processing” are used interchangeably herein. Manipulation may be employed in order to achieve many different results. For example, image data must often be processed before printing by scaling and/or rotation. Data from two sources can be merged as is performed in chromakeying of images or mixing of audio data. Manual manipulation of data is often needed for editing or color correction. Such manipulation of transform data are often performed on the integer realdomain data which results from the transform decoding of
A process for manipulation of transform data 300 is shown in
It is noted that there is no requirement in the data manipulation processes described above, for the input data to come entirely from one source. For example, many types of data manipulation involve the merging of data from two or more sources. This includes manipulations such as mixing of audio data or merging of images. The processes illustrated in the figures and described generally apply equally well to such types of manipulation. Thus the “input data” used for any of the processes described may in practice come from more than one input source.
It is often the case that data after manipulation are to be reencoded to the transform domain. It is desirable that the process of decoding and reencoding, when no manipulation is performed on the realdomain data, should be lossless. That is, the data, when the forward transform operation uses the same transform type operation as the inverse transform type of transform operation, should result in exactly the same transformdomain data as was present initially. However, errors are introduced by the converting to integers and clipping to the allowed range as is illustrated in
The multigeneration problem is also illustrated for transformcoded data in
Q(λ_{i}+ε)=Q(λ_{i}) if ε<0.5_{i } (3)
where
ε is the error produced in this transform coefficient. This is because each of the λ_{i }is already a multiple of the quantization value, since they have been produced by dequantization as in Equation (2). Thus it is advantageous to control the errors so that they are sufficiently small. When the errors are sufficiently small, the new transformcoded data will be exactly the same as the original transformcoded data. The maximum possible error introduced by the conversion to integers by rounding is half the error introduced by truncating during the conversion.
An example of a method which embodies the process shown in
If it is necessary to show the data before manipulation, for example when the image manipulation is an interactive process, the image can optionally be sent to a display device 758. The image is then manipulated 762 to produce some desired change. If the result of the manipulation is noninteger data then the image data may be converted to integers and clipped to the range e.g. [0,255] 768. In this way the image data 772 may again be displayed 758. The new realdomain image data 772 are passed to the forward DCT 776 and the resulting DCT coefficients are quantized 780 to produce new quantized DCT coefficients 784. These coefficients 784 are then entropy encoded 788 to produce new coded data ‘Cl’ 792 which are different from the original coded data ‘C’ 710. Now the new coded data ‘Cl‘792 incorporates not only the desired changes made to the image by the image manipulation 762, but also the errors resulting from the converting and clipping stages 750 and 768. It would be advantageous to eliminate or reduce these errors.
An example of a system which embodies the process shown in
If it is necessary to show the data before manipulation, for example when the image manipulation is an interactive process, the image can optionally be sent to a display 763. The image is operated on by a manipulator 767 to produce some desired change. If the result of the manipulation is noninteger data then the image data may be passed to another integer converter and clipper 773. In this way the image data 777 may again be displayed 763. The new realdomain image data 777 are passed to the forward DCTer 781 and the resulting DCT coefficients are input to the quantizer 785 to produce new quantized DCT coefficients 789. These coefficients 789 are then input to the entropy encoder 793 to produce new coded data ‘C1’ 797 which are different from the original coded data ‘C’ 715. Now the new coded data ‘C1’ 797 incorporates not only the desired changes made to the image by the image manipulator 767, but also the errors resulting from the integer converter and clippers 755 and 773.
The maximum possible error from truncating is just under 1 for each sample. This almost doubles the error in the unquantized forward transform coefficients. For the quantization matrix in
A numerical example showing the multigeneration problem is given in
This example also applies to transformcoded data if the DC quantization value is set to 1, 2, or 4. Then the transform coefficients 822 would be produced from transformcoded values of 4, 2, or 1 respectively. The quantization of the new transform coefficients 828 would change the resulting DC quantization values to 2, 4, or 8 respectively.
Another numerical example showing the multigeneration problem is given in
Having demonstrated the errors caused by realdomain rounding or truncating when converting to integers, we now show how realdomain clipping can cause errors.
Bar chart 862 shows the data produced from that in chart 858 after realdomain clipping. Those negative parts of the real data have been changed to 0. This results in the DC coefficient of the data increasing and hence leads to error being introduced. Because the quantization value for the DC coefficient is generally small, the error is large enough to cause a change in the quantized data as given in Equation (3).
To further illustrate the possibility of error introduced by realdomain clipping, a numerical example 870 is shown in FIGS. 8(f) and 8(g). This example employs the system illustrated in
In many situations, the process of decoding, manipulation and reencoding of data needs to be done multiple times. In these situations each iteration of this process is referred to as a “generation”. The errors described above, caused by converting to integers and clipping to an allowed range in the real domain, accumulate as multiple iterations are performed and may result in significant degradation of the data. It is realized that the foregoing are only representative examples of errors introduced by rounding (or truncating) and/or clipping. Other examples having more or less error developed are possible.
The problem is usually even worse following multiple generations of decoding and reencoding as shown in
A case showing the problem significantly worsened due to multiple generations of realdomain manipulation of transformcoded data is shown in
An example embodiment of a method for processing transform data with reduced error 1100 is illustrated in
An example embodiment of a system for processing transform data with reduced error 1105 in accordance with the present invention is illustrated in
An example of an embodiment of the present invention employing a method for performing inverse transform followed by forward transform steps 1200 is illustrated in
An example of an embodiment of the present invention employing a system with an inverse transformer followed by forward transformer 1205 is illustrated in
A method for performing realdomain manipulation of transformcoded data with reduced error is illustrated in
A system for performing realdomain manipulation of transformcoded data with reduced error is illustrated in
An example embodiment of a method for realdomain conversion of transformcoded data 1500 is shown in
The conversion between quantization matrices may be for coarser or finer quantization. For converting data from the JPEG international standard to the MPEG international standard, the quantization is likely to be coarser. The higher quality JPEG independent images are needed during the editing process. The coarser, more compressible, MPEG images are used to achieve the desired bandwidth objectives. On the other hand, in recompressing JPEG images after significant hand editing, the quantization is likely to be finer in order to preserve the changes.
An example embodiment of a system for realdomain conversion of transformcoded data 1505 in accordance with the present invention is shown in
A method for performing realdomain manipulation of transformcoded data with reduced error 1600 is formed by extending the method 1400 described in
A system for performing realdomain manipulation of transformcoded data with reduced error 1605 is formed by extending the method 1405 described in
An example embodiment of a method for realdomain manipulation of transformcoded data with reduced error 1700 is shown in
An example invention embodiment of a system for realdomain manipulation of transformcoded data with reduced error 1705 is shown in
A method for performing realdomain manipulations of transformcoded data with reduced error in multiple steps 1800, alternating the manipulation steps with forward transforming and quantizing steps and inverse transform and quantizing steps, is illustrated in
As shown in
An example invention embodiment of a system for performing realdomain manipulations of transformcoded data with reduced error in multiple stages 1805, alternating the operation of a manipulator with the operation of a forward transformer and quantizer and the operation of an inverse quantizer and inverse transformer, is illustrated in
A numerical example showing how the present invention solves one aspect of the multigeneration problem is given in
Another numerical example showing how the present invention solves another aspect of the multigeneration problem is given in
Having demonstrated how using the highprecision numbers removes the errors caused by realdomain rounding or truncating, we now show how realdomain clipping errors are also avoided. The same numerical starting point and first three steps used in
Examples of the manipulation between generations include merging two or more transformcoded data sets. For transformcoded image data sets, the merging may be needed because multiple small images need to be collected into one bigger picture. Fanfolded advertising brochures typically are composed of multiple individual pictures. Today'"'"'s highest end laser printers print more than one page at a time. In such cases, the images generally do not overlap, but may not have the same quantization, positioning relative to the reference grid such as the 8×8 block structure for JPEG DCTs, or orientation. By composing the final picture in the real domain, standard processes can be used for each subimage. Then the composite image can be recompressed for eventual decompression for onthefly printing.
Similarly, digital editing can include many special effects requiring several independent manipulations performed serially. Digital movies often use the fadein/fadeout special effect to perform a smooth transition between two key scenes. Such special effects may follow independent processing of each scene. Thus, multiple generations of decompression and recompression are often needed in the editing to produce the composite of the special effects.
Chromakeying involves two independent video data streams. In one video stream the background has been captured. In the other video stream the foreground, often composed of action involving live actors, has been filmed against a blank single color such as a deep blue or black background. Then the blank pixels in the foreground image are replaced with pixels from the background video. Since the pixels are being mixed at a singlepixel level, the images need to be combined in the real domain. The errors introduced by converting to integers and clipping are highly undesirable for such digital studio applications. These errors are reduced or eliminated by implementing the present invention.
Another application example for use of the present invention is in the highend digital graphics market which uses digital images with sometimes more than 100 megapixels. Glossy advertising brochures and the large photographic trade show booth backdrops are just two examples of the use of such high quality digital imagery. Highquality lossy JPEG compression are sometimes used to keep the transmission and storage costs down. As such images are decompressed and recompressed to allow changes and modifications such as adding highlights, correcting colors, adding or changing text and image cropping, unintentional changes are a problem that is solved with the use of the concepts of the present invention.
The above examples for the concepts of the present invention are usual for image and video transform data. The wide use of the Internet has shown the value of JPEG and MPEG compressed image data. When JPEG images are to be printed, then manipulations such as a change of scale or a change of orientation may be required. In addition, a transformation to another color space followed by recompression will allow the printready versions of the image to be stored. Use of the present invention overcomes the problem inherent in propagating the errors from the rounding and clipping.
Audio coded data also needs to be decompressed, mixed with special sound effects, merged with other audio data, edited and processed in the real domain with reduced errors. Similar implementations are performed for other industrial, commercial, and military applications of digital processing employing a transform and an inverse transform of data representing a phenomenon when the data is stored in the transform domain. These are thus other representative applications wherein use of the present invention is highly advantageous.
It is further noted that this invention may also be provided as an apparatus or a computer product. For example, it may be implemented as an article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to perform the methods of the present invention.
It is noted that although the description of the invention is made for particular arrangements of steps, the intent and concept of the present invention are suitable and applicable to other arrangements. It will be clear to those skilled in the art that other modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention.