Source: http://www.google.com/patents/US7194138?dq=5,758,352
Timestamp: 2016-07-25 19:02:45
Document Index: 694563010

Matched Legal Cases: ['art.\n10', 'art.\n23', 'art 1', 'art 2', 'art 3', 'art 2', 'art 3', 'art 854', 'art 858']

Patent US7194138 - Reduced-error processing of transformed digital data - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThis invention solves problems due to employing error degraded data in digital processing. It particularly solves multi-generation 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...http://www.google.com/patents/US7194138?utm_source=gb-gplus-sharePatent US7194138 - Reduced-error processing of transformed digital dataAdvanced Patent SearchPublication numberUS7194138 B1Publication typeGrantApplication numberUS 09/186,247Publication dateMar 20, 2007Filing dateNov 4, 1998Priority dateNov 4, 1998Fee statusLapsedAlso published asCN1253339A, CN100339852C, US7724976, US20070160146Publication number09186247, 186247, US 7194138 B1, US 7194138B1, US-B1-7194138, US7194138 B1, US7194138B1InventorsMartin James Bright, Joan LaVerne MitchellOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (17), Referenced by (20), Classifications (17), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetReduced-error processing of transformed digital data
US 7194138 B1Abstract
1. A processing method comprising digitally processing integer transform data representing a phenomenon,
said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip,
said integer transform data having an original precision as real domain data input for forward transformation and quantization in forming said integer transform data, the step of digitally processing comprising:
employing only said integer transform data while performing an inverse transform of said integer transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision; and
maintaining said greater precision while manipulating said high-precision numbers to produce an effect in said one of: spectral analysis, spectrum analysis, image, audio clip, or video clip.
2. A method as recited in claim 1, wherein said step of manipulating results in manipulated high precision numbers, and further comprising converting said manipulated high-precision numbers to integers and clipping the integers to an allowed range forming converted data.
4. A method as recited in claim 1, wherein said effect is the chroma-key merging of two data sets.
5. A method as recited in claim 1, wherein said effect is the color correction of image data.
6. A method as recited in claim 3, wherein said effect is a 90 degree rotation of the image.
7. A method as recited in claim 1, wherein said high-precision numbers are floating point numbers.
8. A method as recited in claim 1, wherein said high-precision numbers are fixed precision numbers including a fractional part.
10. A method as recited in claim 1, wherein the step of performing employs an inverse discrete wavelet transform.
11. A method as recited in claim 1, wherein the step of performing employs an inverse discrete Fourier transform.
12. A method as recited in claim 1, further comprising implementing an inverse quantization of transform-coded data forming the integer transform data.
13. A method as recited in claim 12, further comprising converting said high-precision numbers to integers and clipping the integers to an allowed range forming converted data.
14. A method as recited in claim 12, further comprising entropy decoding coded data to form the transform-coded data.
15. A method as recited in claim 14, wherein said coded data are coded image data.
16. A method as recited in claim 14, wherein said coded data are coded video data.
19. A method as recited in claim 12, wherein the step of performing employs an inverse discrete cosine transform.
20. A method as recited in claim 12, wherein the step of performing employs an inverse discrete wavelet transform.
21. A method as recited in claim 12, wherein the step of performing employs an inverse discrete Fourier transform.
22. A method as recited in claim 12, wherein said high-precision numbers are fixed precision numbers that include a fractional part.
23. A system for digitally processing integer transform data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said integer transform data having an original precision as real domain data input for forward transformation and quantization in forming said integer transform data, the system comprising:
an inverse transformer to perform an inverse transform of the integer transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision employing only said inverse transform; and
a manipulator to manipulate the high-precision numbers to produce an effect in said one of: spectral analysis, spectrum analysis, image, audio clip, or video clip, while maintaining said greater precision.
24. A system as recited in claim 23, wherein said manipulator forms manipulated high precision numbers, and further comprising a converter to convert said manipulated high-precision numbers to integers, and a clipper to clip the integers to an allowed range.
25. A system for digitally processing transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, the system comprising:
an inverse quantizer to perform an inverse quantization of said transform-coded data to form integer transform data;
an inverse transformer to perform an inverse transform of said integer transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision employing only said integer transform data; and
a manipulator for manipulating the high-precision numbers to produce an effect in said one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, while maintaining said greater precision.
26. A system as recited in claim 25, further comprising a converter to convert said high-precision numbers to integers, and a clipper to clip the integers to an allowed range.
27. A method as recited in claim 2, further comprising providing said converted data for use by an output device.
28. A method as recited in claim 27, wherein the output device is a display monitor.
29. A method as recited in claim 27, wherein the output device is a raster display monitor.
30. A method as recited in claim 1, wherein the integer transform data includes information of a spectral analysis.
31. An article of manufacture comprising a computer readable medium having computer readable program code means embodied therein for digitally processing integer transform data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said integer transform data having an original precision as real domain data input for forward transformation and quantization in forming said integer transform data, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:
maintaining said greater precision while manipulating said high-precision numbers to produce an effect in said one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip.
32. An article of manufacture as recited in claim 31, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect converting said high-precision numbers to integers and clipping the integers to an allowed range forming converted data.
33. An article of manufacture as recited in claim 31, wherein the phenomenon is an image.
34. A program storage device readable by computer tangibly embodying a program of instructions executable by the computer to perform method steps for digitally processing transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, said method steps comprising:
performing an inverse quantization of said transform-coded data forming integer transform data;
35. A computer program as recited in claim 34, wherein the step of manipulating results in manipulated high-precision numbers, the computer readable program code means in said computer program further comprising converting said manipulated high-precision numbers to integers and clipping the integers to an allowed range forming converted data.
36. A method as recited in claim 14, wherein said coded data are coded audio data.
37. A processing method comprising digitally processing transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, the step of digitally processing comprising:
implementing an inverse quantization of the transform-coded data forming transform data;
employing only integer transform data while perform an inverse transform of said transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision; and
38. A method as recited in claim 37, wherein the step of manipulating results in manipulated high-precision numbers, and further comprising converting said manipulated high-precision numbers to integers and clipping the integers to an allowed range forming converted data.
39. A program storage device readable by computer, tangibly embodying a program of instructions executable by the computer to perform method steps for digitally processing transform-coded data representing a phenomenon, said method steps comprising the steps of claim 37.
40. A system for digitally processing transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, the system comprising:
a first inverse quantizer to generate an inverse quantization of the transform-coded data forming transform data;
a first inverse transformer to produce an inverse transform of integer transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision employing only said integer transform data; and
41. An article of manufacture comprising a computer readable medium having computer readable program code means embodied therein for causing digitally processing of transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of:
employing only said integer transform data while performing an inverse transform of said transform data to the real domain directly forming high-precision numbers having a precision greater than said original precision; and
maintaining said greater precision while manipulating said high-precision numbers to produce an effect.
42. A computer program product comprising a computer readable medium having computer readable program code means embodied therein for causing digital processing of transform-coded data representing a phenomenon, said phenomenon comprising one of: a spectral analysis, a spectrum analysis, an image, an audio clip, or a video clip, said transform coded data having an original precision as real domain data input for forward transformation and quantization in forming said transform coded transform data, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of:
a fast inverse quantizer to generate an inverse quantization of the transform-coded data forming transform data;
a manipulator for manipulating the high-precision numbers to produce an effect in said one of: spectral analysis, spectrum analysis, image, audio clip, or video clip, while maintaining said greater precision.
The present application is related to the following applications even dated herewith: Ser. No. 09/186,245, entitled, “Transform-domain correction of real-domain errors,” by inventors J. Mitchell et al., and Ser. No. 09/186,249, entitled, “Error reduction in transformed digital data,” by inventors M. Bright et al., which are incorporated herein in entirety by reference.
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 ITU-T Rec. T.81 (1992) ISO/IEC 10918-1:1994, Information technology—Digital compression and coding of continuous-tone 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 MPEG-1 standard defines systems for both video compression (Part 2 of the standard) and audio compression (Part 3). A more recent MPEG video standard (MPEG-2) is defined by ITU-T Rec. H.262 ISO/IEC 13818-2: 1996 Information Technology—Generic Coding of moving pictures and associated audio—Part 2: video. A newer audio standard is ISO/IEC 13818-3: 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 8�8 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: New York, (1993).
In general, the forward transform will produce real-valued 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 real-valued transform coefficients resulting from the forward transform of one unit of data. Note that one unit of data may be a one-dimensional or two-dimensional block of data samples or even the entire data. The “quantization values” (qi) are parameters to the encoding process. The “quantized transform coefficients” or “transform-coded data” are the sequence of values (ai) defined by the quantization function Q:
a i = Q ( λ i ) = ⌊ λ i q i + 0.5 ⌋ ( 1 ) 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 a i. (2)
FIG. 1( a) is a block diagram showing a method for performing an inverse transform;
FIG. 1( b) is a block diagram showing a system for performing an inverse transform;
FIG. 2( a) is a block diagram showing a method for decoding transform-coded data;
FIG. 2( b) is a block diagram showing a system for decoding transform-coded data;
FIG. 7( a) is a block diagram showing a method for performing real-domain processing of JPEG DCT-coded image data, which exhibits the multi-generation problem;
FIG. 7( b) is a block diagram showing a system for performing real-domain processing of JPEG DCT-coded image data, which exhibits the multi-generation problem;
FIG. 8( a) gives the JPEG example luminance quantization matrix;
FIG. 8( b) gives the JPEG example chrominance quantization matrix;
FIG. 8( c) is a numerical example of how real-domain rounding can cause significant errors in 8�8 block DCT coded data;
FIG. 8( d) is a numerical example of how real-domain truncation can cause significant errors in 8�8 block DCT coded data;
FIG. 8( e) is a series of graphs illustrating how real-domain clipping can cause errors in one-dimensional discrete cosine transform-coded data;
FIG. 8( f) and FIG. 8( g) are a numerical example of how real-domain clipping can cause significant errors in 8�8 block DCT coded data;
FIG. 11( a) is a block diagram showing an example of a method for reduced-error processing of transform data in accordance with the present invention;
FIG. 11( b) is a block diagram showing an example of a system for reduced-error processing of transform data in accordance with the present invention;
FIG. 12( a) is a block diagram showing an example of a method for performing an inverse transform followed by a forward transform, such that this process is lossless in accordance with the present invention;
FIG. 12( b) is a block diagram showing an example of a system for performing an inverse transform followed by a forward transform, such that this process is lossless in accordance with the present invention;
FIG. 13( a) is a block diagram showing an example of a method for performing real-domain manipulation of transform data with reduced error followed by a forward transform in accordance with the present invention;
FIG. 13( b) is a block diagram showing an example of a system for performing real-domain manipulation of transform data with reduced error followed by a forward transform in accordance with the present invention;
FIG. 14( a) is a block diagram showing an example of a method for reduced-error processing of transform-coded data in accordance with the present invention;
FIG. 14( b) is a block diagram showing an example of a system for reduced-error processing of transform-coded data in accordance with the present invention;
FIG. 15( a) is a block diagram showing an example of a method for decoding and re-encoding transform-coded data such that this process is lossless in accordance with the present invention;
FIG. 15( b) is a block diagram showing an example of a system for decoding and re-encoding transform-coded data such that this process is lossless in accordance with the present invention;
FIG. 16( a) is a block diagram showing an example of a method for performing real-domain manipulation of transform-coded data with reduced error in accordance with the present invention;
FIG. 16( b) is a block diagram showing an example of a system for performing real-domain manipulation of transform-coded data with reduced error in accordance with the present invention;
FIG. 17( a) is a block diagram showing an example embodiment of a method for performing real-domain processing of JPEG-coded image data, such that undesired errors in the new transform-coded data are reduced or eliminated in accordance with the present invention;
FIG. 17( b) is a block diagram showing an example embodiment of a system for performing real-domain processing of JPEG-coded image data, such that undesired errors in the new transform-coded data are reduced or eliminated in accordance with the present invention;
FIG. 18( a) is a block diagram showing an example of a method for performing multiple iterations of the real-domain manipulation of transform-coded data with reduced error, where each iteration is as described in FIG. 16( a) in accordance with the present invention;
FIG. 18( b) is a block diagram showing an example of a system for performing multiple iterations of the real-domain manipulation of transform-coded data with reduced error, where each iteration is as described in FIG. 16( b) in accordance with the present invention;
FIG. 19( a) shows the same 8�8 block numerical starting point of FIG. 8( c) using the high-precision numbers as input to the forward transform instead of the rounded numbers;
FIG. 19( b) shows the same 8�8 block numerical starting point of FIG. 8( d) using the high-precision numbers as input to the forward transform instead of the truncated numbers;
FIG. 19( c) shows the same 8�8 block numerical steps as FIG. 8( f); and
FIG. 19( d) shows the numerical results when the output of the inverse DCT with rounding, but before clipping, is input to the forward transform followed by quantization.
FIG. 1( a) shows an inverse transform method 100. Transform-domain data ‘A’ 110 are acted on by the inverse transform 120, which produces high-precision real-valued data 130. The high-precision data 130 are converted to integers and clipped 140 to produce integer real-domain data 150. In some cases, the integer-valued data are optionally sent to an output device 160.
FIG. 1( b) shows an inverse transform system 105. Transform-domain data ‘A’ 115 are acted on by the inverse transformer 125, which produces high-precision real-valued data 135. The high-precision data 135 are input to the integer converter and clipper 145 to produce integer real-domain data 155. In some cases, the integer-valued data are optionally input to an output device 165 such as a display monitor, a television set, or an audio player.
FIG. 2( a) shows a method 200 for decoding transform-coded (i.e. quantized) data. The integer transform-coded data ‘B’ 210 are inverse quantized 220 (i.e. dequantized) with quantization values as in Equation (2) above. The result of the dequantizing step may then be passed as input to the inverse transform 120, and decoding proceeds as in FIG. 1( a).
FIG. 2( b) shows a system 205 for decoding transform-coded (i.e. quantized) data. The integer transform-coded data ‘B’ 215 are input to the inverse quantizer 225 with quantization values as in Equation (2) above. The result of the dequantizing step is passed as input to the inverse transformer 125, and decoding proceeds as in FIG. 1( b).
One aspect of the present invention is concerned with the manipulation of both transform data and transform-coded 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 chroma-keying 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 real-domain data which results from the transform decoding of FIG. 1( a) and/or FIG. 2( a).
An example of a method which embodies the process shown in FIG. 6, is shown in FIG. 7( a). The method 700 illustrated performs real-domain manipulation on coded data such as JPEG-coded image data. The coded data ‘C’ 710 are entropy decoded 720, which is defined for JPEG-coded data in the JPEG standard. The entropy decode step 720 decompresses the data into quantized DCT coefficients. These quantized coefficients are inverse quantized 730 and passed to the inverse transform, which in this system is the two-dimensional 8�8 inverse DCT 740. The resulting real-valued image data are rounded to integers and clipped 750 to the allowed range (e.g. [0,255]) to produce integer-valued image data 754 in the allowed range.
An example of a system which embodies the process shown in FIG. 6, is shown in FIG. 7( b). The system 705 performs real-domain manipulation on coded data. The coded data ‘C’ 715 are input to the entropy decoder 725, which is defined for JPEG-coded data in the JPEG standard. The entropy decoder 725 decompresses the data into quantized DCT coefficients. These quantized coefficients are input to the inverse quantizer 735 and the output passed to the inverse transformer, which in this system is the two-dimensional 8�8 inverse DCT-er 745. The resulting real-valued image data are rounded to integers and clipped 755 (e.g. to the range [0,255]) to produce integer-valued image data 759 in the allowed range.
FIG. 8( a) shows the JPEG example luminance quantization matrix 804 for 8�8 DCT luminance blocks. FIG. 8( b) gives the JPEG example chrominance quantization matrix 814 for 8�8 DCT chrominance blocks. The smallest quantization value in FIG. 8( a) is 10. The smallest quantization value in FIG. 8( b) is 17. Since the maximum possible error from rounding is 0.5 for each of 64 samples, the largest error in the unquantized forward transform coefficients from conversion to integers by rounding is 4 (shown in FIG. 8( c)) for JPEG. For the quantization matrices shown in FIGS. 8( a) and 8(b) this size error is less than half of all of the values and will disappear during quantization. However, for high quality applications such as high end printing or digital studio editing, the quantization matrix values are much smaller. In some cases, the DC (upper left corner) term is as small as 1 to preserve maximum quality. Then the rounding errors are significant.
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 FIG. 8( a) eight quantization values are small enough for this error to potentially change the transform-coded data.
A numerical example showing the multi-generation problem is given in FIG. 8( c). In this example the transform used is the 8�8 DCT as used in the JPEG still is image compression standard. A set of transform-domain coefficients 822, of which only one (the constant, or DC, term) is non-zero, are operated on by the inverse transform to produce an block of real-domain data 824. In this case the data consist of 64 values which are all equal to 128.5. Note that the JPEG level shift of 128 for 8 bit data has been applied. The real-domain data are rounded to the nearest integers 826, which in this case means that each value is rounded up to 129. The forward transform is then applied to produce new transform-domain coefficients 828. It can be seen that the resulting new transform coefficients 828 are significantly different from the initial transform coefficients 822. This is a highly undesirable result.
Another numerical example showing the multi-generation problem is given in FIG. 8( d). Again the transform used is the 8�8 DCT as used in the JPEG still image compression standard. A set of transform-domain coefficients 832, of which only one (the constant, or DC, term) is non-zero, are operated on by the inverse transform to produce a block of real-domain data 834. In this case the data consist of 64 values which are all equal to 128.875. Note that the JPEG level shift of 128 for 8 bit data has been applied. The real-domain data are truncated to the nearest integers 836, which in this case means that each value is reduced to 128. The forward transform is then applied to produce new transform-domain coefficients 838. It can be seen that the resulting new transform coefficients 838 are significantly different from the initial transform coefficients 832. This is a highly undesirable result.
Having demonstrated the errors caused by real-domain rounding or truncating when converting to integers, we now show how real-domain clipping can cause errors. FIG. 8( e) shows an example of real-domain clipping 850. This example uses the one-dimensional DCT to illustrate the problem. FIG. 8( d) shows a bar chart 854 displaying one block of data consisting of eight samples. The data displayed has only two frequency components: a constant, or DC, component which is indicated by the dotted line; and an alternating, or AC, component which gives an alternating wave pattern symmetrical about the dotted line. The magnitudes of these components, namely the respective DCT coefficients, are high-precision numbers. When quantization is performed, these DCT coefficients are rounded to the nearest quantization level. The data after transform-domain quantization are shown in the bar chart 858. In the example shown, the DC coefficient has a small quantization value and so quantization does not change the DC level significantly. The AC coefficient shown has a large quantization value and so is changed significantly by quantization. This example shows the AC component almost doubling in magnitude due to quantization. These quantization values reflect, for example, those used when compressing chrominance image data. Thus the data represented after quantization have parts which have negative values. This shows how transform-domain data which, after inverse transforming, give real-domain negative values can be produced by original real-domain data which do not contain negative values.
To further illustrate the possibility of error introduced by real-domain clipping, a numerical example 870 is shown in FIGS. 8( f) and 8(g). This example employs the system illustrated in FIG. 5. This example uses the two-dimensional 8�8 DCT as used for transform coding of images to illustrate the problem described above. The initial quantized DCT coefficients are shown in matrix 874. All but two of the coefficients are 0; the two non-zero coefficients are the DC coefficient and one high-frequency coefficient. The coefficients, after dequantizing using the quantization matrix shown in FIG. 8( a), are shown in matrix 878. When the inverse DCT is performed on these transform data and the level shift of 128 added, real data are produced as shown in matrix 882. The data shown in matrix 882 have already been rounded to integers but have not been clipped to an allowed range. It can be seen that these real data include several negative values. After clipping, the real data 882 produce clipped real data as shown in matrix 886. These data are identical to 882 except that each negative value has been replaced by 0. The forward DCT is then applied to the real-domain data to give new rounded transform data 890. It can be seen that the new transform data are significantly different from the previous transform data 878. When quantization is performed using the quantization matrix shown in FIG. 8( a), new transform-coded data 894 are produced. The resulting changes in the transform data are large enough to produce changes in the transform-coded data after quantization. This is a highly undesirable result.
An example embodiment of a method for processing transform data with reduced error 1100 is illustrated in FIG. 11( a). Transform data ‘A’ 110 are passed through an inverse transform 120 to produce high-precision real-domain data 130, as in FIG. 1( a). If it is necessary to pass the real-domain data to an output device 160 which takes integer-valued input, or to generate integer-valued data before manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 140 is done before manipulation without affecting the high-precision real-domain data. The desired manipulation 1110 of the real-domain data is performed using a method which accepts high-precision data as input and produces high-precision data 1120 as output. This manipulation method 1110 performs conceptually the same processing on the data as the manipulation on integers 310 described above in FIG. 3, but operates instead on high-precision data. If it is necessary to pass the manipulated real-domain data to an output device 160 which takes integer-valued input, or to generate integer-valued data after manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 140 are done after manipulation without affecting the high precision of the processed data.
An example embodiment of a system for processing transform data with reduced error 1105 in accordance with the present invention is illustrated in FIG. 11( b). Transform data ‘A’ 115 are passed through an inverse transformer 125 to produce high-precision real-domain data 135, as in FIG. 1( b). If it is necessary to pass the real-domain data to an output device 165 which takes integer-valued input, or to generate integer-valued data before manipulation for any other reason, the integer converter and clipper 145 operates before manipulation without affecting the high-precision real-domain data. The manipulator 1115 operates on the real-domain data accepting high-precision data as input and producing high-precision data 1125 as output. This manipulator 1115 performs conceptually the same processing on the data as the manipulation on integers 310 described above in FIG. 3, but operates instead on high-precision data. If it is necessary to pass the manipulated real-domain data to an output device 165 which takes integer-valued input, or to generate integer-valued data after manipulation for any other reason, the integer converter and clipper 145 operates after manipulation without affecting the high precision of the processed data.
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 FIG. 12( a). Transform data ‘A’ 110 are passed through an inverse transform 120 to produce high-precision real-domain data 130, as in FIG. 1( a). If it is necessary to pass the real-domain data to an output device 160 which takes integer-valued input, or to generate integer-valued data for any other reason, the steps of converting to integers and clipping to an allowed range 140 are done without affecting the high-precision real-domain data. The high-precision data 130 are used as input to the forward transform 1210, which accepts real-valued data as input. The resulting transform data ‘A3’ 1220 are identical to the original transform data ‘A’ 110 which were the input to the inverse transform 120 if the forward transform 1210 is the inverse of the inverse transform since the errors from rounding and clipping are not present in the transform data ‘A3’. The forward transform 1210 will produce different transform data ‘A3’ 1220 when a different forward transform is used. This allows conversion between transforms without the errors from rounding and clipping being present in the forward transform input.
An example of an embodiment of the present invention employing a system with an inverse transformer followed by forward transformer 1205 is illustrated in FIG. 12( b). Transform data ‘A’ 115 are passed through an inverse transformer 125 to produce high-precision real-domain data 135, as in FIG. 1( b). If it is necessary to pass the real-domain data to an output device 165 which takes integer-valued input, or to generate integer-valued data for any other reason, the integer converter and clipper 145 operates without affecting the high-precision real-domain data 135. The high-precision data 135 are used as input to the forward transform 1215, which accepts real-valued data as input. The resulting transform data ‘A3’ 1225 are identical to the original transform data ‘A’ 115 which were the input to the inverse transformer 125 if the forward transformer 1215 implements the inverse of the inverse transform since the errors from rounding and clipping are not present in the transform data ‘A3’. The forward transformer 1215 will produce different transform data ‘A3’ 1225 when a different forward transformer is used.
FIG. 13( a) shows a method for performing real-domain manipulation of transform data with reduced error 1300. This method is formed by extending the method 1100 described in FIG. 11( a). In this case, the high-precision data 1120 are passed as input to a forward transform 1210 which accepts high-precision data as input, to produce new transform data ‘A4’ 1310 without rounding and/or clipping errors.
FIG. 13( b) shows a system for performing real-domain manipulation of transform data with reduced error 1305. This method is formed by extending the system 1105 described in FIG. 11( b). In this case, the high-precision data 1125 are passed as input to a forward transformer 1215 which accepts high-precision data as input, to produce new transform data ‘A4’ 1315 without rounding and/or clipping errors.
A method for performing real-domain manipulation of transform-coded data with reduced error is illustrated in FIG. 14( a). FIG. 14( a) shows integer transform-coded data ‘B’ 210 are dequantized 220 and the output passed through an inverse transform 120 to produce high-precision real-domain data 130, as in FIG. 2( a). If it is necessary to pass the real-domain data 130 to an output device 160 which takes integer-valued input, or to generate integer-valued data 150 before manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 140 are done before manipulation without affecting the high-precision real-domain data 130. The desired manipulation 1110 of the real-domain data is then performed using a method which accepts high-precision data as input and produces high-precision data 1410 as output. This manipulation 1110 performs conceptually the same processing on the data as the manipulation on integers 310 described above in FIG. 3, but operates instead on high-precision data. If it is necessary to pass the manipulated real-domain data to an output device 160 which takes integer-valued input, or to generate integer-valued data after manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 140 are done after manipulation 1110 without affecting the high precision of the processed data 1410.
A system for performing real-domain manipulation of transform-coded data with reduced error is illustrated in FIG. 14( b). FIG. 14( b) shows integer transform-coded data ‘B’ 215 input to an inverse quantizer 225 and passed through an inverse transformer 125 to produce high-precision real-domain data 135, as in FIG. 2( b). If it is necessary to pass the real-domain data 135 to an output device 165 which takes integer-valued input, or to generate integer-valued data 155 before manipulation for any other reason, the integer converter and clipper 145 operates on the data before manipulation without affecting the high-precision real-domain data 135. The desired manipulation of the real-domain data is then performed using a manipulator 1115 which accepts high-precision data as input and produces high-precision data 1415 as output. This manipulator 1115 performs conceptually the same processing on the data as the manipulation on integers 310 described above in FIG. 3, but operates instead on high-precision data. If it is necessary to pass the manipulated real-domain data to an output device 165 which takes integer-valued input, or to generate integer-valued data after manipulation for any other reason, the integer converter and clipper 145 operates on the non-integer data 1415 after manipulation 1115 without affecting the high precision of the processed data 1415.
An example embodiment of a method for real-domain conversion of transform-coded data 1500 is shown in FIG. 15( a). The high-precision data 130 are used as input to the forward transform 1210, which accepts real-valued data as input. The output of the forward transform 1210 is quantized 1510. Depending upon the desired system implementation, the forward transform operation 1210 may employ a different transform than that used in the inverse transform operation 120. For example, the inverse transform 120 may use the inverse DCT transform whereas the forward transform 1210 may use the Fourier transform. The resulting integer transform-coded data ‘B2’ 1520 are identical to the original integer transform-coded data ‘B’ 210 which were the input to the inverse quantize step 220 if the forward transform operation 1210 is the inverse of the inverse transform operation 120 and the quantization values used in the inverse quantization step 220 and the quantization step 1510 are identical. It is noted that the forward transform 1210 will produce different integer transform-coded data ‘B2’ when a different forward transform is used. Similarly, use of different quantization values in the inverse quantization 220 and quantization 1510 also produces different integer transform-coded data 1520. This method thus allows conversion between transforms and quantization matrices without the errors from rounding and clipping being present in the forward transform 1210 input 130.
An example embodiment of a system for real-domain conversion of transform-coded data 1505 in accordance with the present invention is shown in FIG. 15( b). The high-precision data 135 are used as input to the forward transformer 1215, which accepts real-valued data as input. The output of the forward transformer 1215 is input to the quantizer 1515. Depending upon the desired system implementation, the forward transformer 1215 may produce a different transform than that used in the inverse transformer 125. For example, the inverse transformer 125 may use the inverse DCT transform whereas the forward transformer 1215 may use the Fourier transform. The resulting integer transform-coded data ‘B2’ 1525 are identical to the original integer transform-coded data ‘B’ 215 which was the input to the inverse quantizer 225 if the forward transformer 1215 produces the inverse of the inverse transformer 125 and the quantization-values used in the inverse quantizer 225 and the quantizer 1515 are identical. It is noted that the forward transformer 1215 will produce different integer transform-coded data ‘B2’ when a different forward transform is produced. Similarly, use of different quantization values in the inverse quantizer 225 and quantizer 1515 also produces different integer transform-coded data 1525. This system thus allows conversion between transforms and quantization matrices without the errors from rounding and clipping being present in the forward transformer 1215 input 135.
A method for performing real-domain manipulation of transform-coded data with reduced error 1600 is formed by extending the method 1400 described in FIG. 14( a) as is illustrated in FIG. 16( a). The high-precision data 1410 are passed as input to a forward transform 1210 which accepts high-precision data as input. The output values from the forward transform are quantized 1510 to produce new transform-coded data ‘B3’ 1610.
A system for performing real-domain manipulation of transform-coded data with reduced error 1605 is formed by extending the method 1405 described in FIG. 14( b) as is illustrated in FIG. 16( b). The high-precision data 1415 are passed as input to a forward transformer 1215 which accepts high-precision data as input. The output values from the forward transformer are input to the quantizer 1515 to produce new transform-coded data ‘B3’ 1615.
An example embodiment of a method for real-domain manipulation of transform-coded data with reduced error 1700 is shown in FIG. 17( a). The chosen embodiment is a method for real-domain manipulation of coded images, which are transform-coded using the DCT. Coded data ‘C’ 710 are decoded by a lossless entropy decode step 720 to produce quantized DCT coefficients. These coefficients are dequantized 730 and passed through an inverse DCT 740 to produce high-precision real-domain data 1710. If it is necessary to pass the image before manipulation to a display device 758 which takes integer-valued input, or to produce integer-valued data 754 before manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 750 are performed before manipulation 1720 without affecting the high-precision real-domain image data 1710. The desired manipulation 1720 of the image is then performed using a method which accepts high-precision data as input and produces high-precision data 1730 as output. If it is necessary to pass the manipulated image data to a display 758 which takes integer-valued input, or to generate integer-valued image data 1750 after manipulation for any other reason, the steps of converting to integers and clipping to an allowed range 1740 are performed after manipulation 1720 without affecting the high precision of the processed image data 1730. The high-precision image data 1730 are passed as input to a forward DCT 1760 which accepts high-precision data as input. The output values from the forward transform 1760 are quantized 780 to produce new integer DCT coefficients 1770. These coefficients 1770 are encoded by a lossless entropy encode step 788 to produce new coded data ‘C2’ 1780. If the forward and inverse transforms and the manipulation system are sufficiently accurate so that the error they introduce is less than half a quantization step, as described in Equation (3) given above, no error at all is introduced to the DCT coefficients.
An example invention embodiment of a system for real-domain manipulation of transform-coded data with reduced error 1705 is shown in FIG. 17( b). The chosen embodiment is to implement a method for real-domain manipulation of coded images such as JPEG-coded images, which are transform-coded using the DCT. Coded data ‘C’ 715 are decoded by a lossless entropy decoder 725 to produce quantized DCT coefficients. These coefficients are sent to a inverse quantizer 735 and then passed through an inverse DCT-er 745 to produce high-precision real-domain data 1715. If it is necessary to pass the image before manipulation to a display device 763 which takes integer-valued input, or to produce integer-valued data 759 before manipulation for any other reason, the integer converter and clipper 755 produces integer-valued data in the allowed range before manipulation 1725 without affecting the high-precision real-domain image data 1715. The manipulator 1725 which performs the desired manipulation of the image accepts high-precision data as input and produces high-precision data 1735 as output. If it is necessary to pass the manipulated image data to a display 763 which takes integer-valued input, or to generate integer-valued image data 1755 after manipulation for any other reason, the optional integer converter and clipper 1745 produces integer-valued data 1755 after the operation of the manipulator 1725 without affecting the high precision of the processed image data 1735. The high-precision image data 1735 are passed as input to a forward DCT-er 1765 which accepts high-precision data as input. The output values from the forward DCT-er 1765 are sent to the quantizer 785 to produce new integer DCT coefficients 1775. These coefficients 1775 are encoded by a lossless entropy encoder 793 to produce new coded data ‘C2’ 1785. If the forward and inverse transforms and the manipulation system are sufficiently accurate so that the error they introduce for each coefficient is less than half a quantization step, as described in Equation (3) given above, no additional error is introduced to the DCT coefficients.
A method for performing real-domain manipulations of transform-coded 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 FIG. 18( a). In general each manipulation may perform another operation on the data. For example for digital studio editing, the first manipulation might color correct the image. The second manipulation might merge the color corrected image with a background using the chroma-keying method. The third manipulation might add highlights to the image. The fourth manipulation might crop the image to convert from the 16:9 width to height aspect ratio of movies to the 4:3 aspect ratio of television. For the printing of images the first manipulation might rotate the image 90 degrees to orient the image with the printing direction. The second manipulation might merge several independent images into one composite image. A third manipulation might do a color conversion.
As shown in FIG. 18( a) transform-coded data ‘D0’ 910 are dequantized and passed through an inverse transform 920 to produce high-precision real-domain data 1810. If it is necessary to produce integer-valued data for any reason, the high-precision data 1810 may be converted to integers and clipped to an allowed range 1820 without affecting the high precision of the real-domain data 1810. The desired manipulation 1110 of the real-domain data is then performed using a method which accepts high-precision data 1810 as input and produces high-precision data 1840 as output. If it is desired to produce an integer-valued of this output data, the high-precision data 1810 may be converted to integers and clipped to an allowed range 1830 without affecting the high precision of the output data. The high-precision output data are passed as input to a forward transformer and quantizer 1850 to produce new transform-coded data ‘F1’ 1860. The process of inverse quantizing and inverse transforming, manipulation and forward transforming and quantizing may be repeated multiple times with the manipulation 1870 being different upon each iteration. After multiple steps, final transform-coded data ‘Fn’ 1880 are produced with rounding and/or clipping errors reduced or eliminated. Outputs resulting from any of the convert to integer and clip steps may be sent to an output device 1890 with or without a multiplexor.
An example invention embodiment of a system for performing real-domain manipulations of transform-coded 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 FIG. 18( b). Transform-coded data ‘D0’ 1815 are fed to an inverse quantizer and inverse transformer 1819 to produce high-precision real-domain data 1823. If it is necessary to produce integer-valued data for any reason, the high-precision data 1823 may be operated on by the integer converter and clipper 1827 without affecting the high precision of the real-domain data 1823. The manipulator 1115 then operates on the real-domain data 1823 to produce the desired manipulation and produces high-precision data 1845 as output. If it is desired to produce integer-values of this output data, the high-precision data 1845 may be input to an integer converter and clipper 1835 without affecting the high precision of the output data. The high-precision output data are passed as input to a forward transformer and quantizer 1855 to produce new transform-coded data ‘F1’ 1865. The steps of inverse quantizing and inverse transforming, manipulation and forward transforming and quantizing may be repeated multiple times with the manipulator 1875 being different upon each iteration. After multiple iterations, final transform-coded data ‘Fn’ 1885 are produced with real-domain rounding and/or clipping errors reduced or eliminated. In a particular embodiment the output from any or all of the integer converter and clipper modules is fed to the output device 1895. For coded image data the output device may be a display or television set. For coded audio data the output device may be a player and/or recorder.
A numerical example showing how the present invention solves one aspect of the multi-generation problem is given in FIG. 19( a). A set of transform-domain coefficients 822, of which only one (the constant, or DC, term) is non-zero, are operated on by the inverse transform to produce an block of real-domain data 824. In this case the data consist of 64 values which are all equal to 128.5. Note that the JPEG level shift of 128 for 8 bit data has been applied. The forward transform is then applied to produce new transform-domain coefficients 1910. It can be seen that the new transform coefficients 1910 are identical to the initial transform coefficients 822. This is due to the rounding error not being present in the data sent to the forward DCT.
Another numerical example showing how the present invention solves another aspect of the multi-generation problem is given in FIG. 19( b). A set of transform-domain coefficients 832, of which only one (the constant, or DC, term) is non-zero, are operated on by the inverse transform to produce an block of real-domain data 834. In this case the data consist of 64 values which are all equal to 128.875. Note that the JPEG level shift of 128 for 8 bit data has been applied. The forward transform is then applied to produce new transform-domain coefficients 1938. It can be seen that the new transform coefficients 1938 are identical to the initial transform coefficients 832. This is due to the truncation error not being present in the data sent to the forward DCT.
Having demonstrated how using the high-precision numbers removes the errors caused by real-domain rounding or truncating, we now show how real-domain clipping errors are also avoided. The same numerical starting point and first three steps used in FIG. 8( f) are shown in FIG. 19( c). The initial quantized DCT coefficients are shown in matrix 874. All but two of the coefficients are 0; the two non-zero coefficients are the DC coefficient and one high-frequency coefficient. The coefficients after dequantizing are shown in matrix 878. The quantization matrix used is shown in FIG. 8( a). When the inverse DCT is performed on these transform data, real data are produced as shown in matrix 882. The data shown in matrix 882 have already been rounded to integers but have not been clipped to an allowed range.
FIG. 19( d) shows the results of the forward DCT applied to the real-domain data to give new rounded transform data 1944. When quantization is performed, new transform-coded data 1948 are produced. In this example, the changes in the transform data are not large enough to produce changes in the transform-coded data after quantization.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5495292 *Sep 3, 1993Feb 27, 1996Gte Laboratories IncorporatedInter-frame wavelet transform coder for color video compressionUS5544266 *Jul 19, 1994Aug 6, 1996Koninklijke Ptt Nederland N.V.Transcoding deviceUS5675666Mar 2, 1995Oct 7, 1997Sony CorportionImage data compression method and apparatus with pre-processing to compensate for the blocky effectUS5999957 *Dec 29, 1997Dec 7, 1999Nec CorporationLossless transform coding system for digital signalsUS6064435 *Jun 1, 1995May 16, 2000Sony CorporationMotion picture signal compressing apparatus which encodes the motion vector of the block of a motion picture signal picture as a motion vector differenceUS6134350 *Feb 18, 1998Oct 17, 2000Dome Imaging Systems, Inc.Method of producing wavelets and compressing digital images and of restoring the digital imagesUS6151361 *Dec 29, 1997Nov 21, 2000Thomson Licensing S.A.System and method for reducing multipass signal degradationUS6178205 *Dec 12, 1997Jan 23, 2001Vtel CorporationVideo postfiltering with motion-compensated temporal filtering and/or spatial-adaptive filteringUS6243728 *Jul 12, 1999Jun 5, 2001Sony Corporation Of JapanPartitioned shift right logic circuit having rounding supportUS6256349 *Dec 24, 1996Jul 3, 2001Sony CorporationPicture signal encoding method and apparatus, picture signal transmitting method, picture signal decoding method and apparatus and recording mediumUS6256422 *Nov 4, 1998Jul 3, 2001International Business Machines CorporationTransform-domain correction of real-domain errorsEP0849736A1Dec 19, 1997Jun 24, 1998Sony CorporationMethod and apparatus for converting video field sequencesEP0849936A2Dec 11, 1997Jun 24, 1998Xerox CorporationColor correction of a compressed imageGB2318472A Title not availableJPH02227770A Title not availableJPH07123009A Title not availableWO1996027262A1Nov 30, 1995Sep 6, 1996Sony Electronics, Inc.Image data compression method and apparatus with pre-processing to compensate for the blocky effect* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7433529 *Feb 5, 2004Oct 7, 2008International Business Machines CorporationFaster transforms using early aborts and precision refinementsUS7489826 *Oct 7, 2004Feb 10, 2009Infoprint Solutions Company, LlcCompensating for errors in performance sensitive transformationsUS7526136 *Jul 18, 2008Apr 28, 2009International Business Machines CorporationFaster transforms using early aborts and precision refinementsUS7689052 *Jun 9, 2006Mar 30, 2010Microsoft CorporationMultimedia signal processing using fixed-point approximations of linear transformsUS7773671Aug 10, 2010Microsoft CorporationBlock transform and quantization for image and video codingUS7839928Apr 12, 2005Nov 23, 2010Microsoft CorporationBlock transform and quantization for image and video codingUS7881371Feb 1, 2011Microsoft CorporationBlock transform and quantization for image and video codingUS8000394 *Mar 8, 2004Aug 16, 2011Mitsubishi Denki Kabushiki KaishaProgram, method, and apparatus for decoding coded dataUS8942289Jun 29, 2007Jan 27, 2015Microsoft CorporationComputational complexity and precision control in transform-based digital media codecUS8971405Jan 19, 2011Mar 3, 2015Microsoft Technology Licensing, LlcBlock transform and quantization for image and video codingUS20040156553 *Feb 5, 2004Aug 12, 2004International Business Machines CorporationFaster transforms using early aborts and precision refinementsUS20050141609 *Feb 25, 2005Jun 30, 2005Microsoft CorporationBlock transform and quantization for image and video codingUS20050180503 *Apr 12, 2005Aug 18, 2005Microsoft CorporationBlock transform and quantization for image and video codingUS20050213659 *Apr 12, 2005Sep 29, 2005Microsoft CorporationBlock transform and quantization for image and video codingUS20060080373 *Oct 7, 2004Apr 13, 2006International Business Machines CorporationCompensating for errors in performance sensitive transformationsUS20070081734 *Jun 9, 2006Apr 12, 2007Microsoft CorporationMultimedia signal processing using fixed-point approximations of linear transformsUS20070122044 *Mar 8, 2004May 31, 2007Mitsubishi Denki Kabushiki KaishaProgram, method, and apparatus for decoding coded dataUS20080198935 *Jun 29, 2007Aug 21, 2008Microsoft CorporationComputational complexity and precision control in transform-based digital media codecUS20080273808 *Jul 18, 2008Nov 6, 2008International Business Machines CorporationFaster transforms using early aborts and precision refinementsUS20110116543 *May 19, 2011Microsoft CorporationBlock transform and quantization for image and video coding* Cited by examinerClassifications U.S. Classification382/248, 375/E07.028, 375/E07.226International ClassificationG06T9/00, H04N7/32, G06K9/46, H03M7/30, H04N1/41, H04N7/26, H04N7/30, H04N7/50Cooperative ClassificationH04N19/60, H04N19/61, H04N19/45, H04N19/63European ClassificationH04N7/26D2, H04N7/30Legal EventsDateCodeEventDescriptionJan 25, 1999ASAssignmentOwner name: IBM CORPORATION, NEW YORKFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BRIGHT, MARTIN J.;MITCHELL, JOAN L.;REEL/FRAME:009729/0797;SIGNING DATES FROM 19981125 TO 19990115Jul 16, 2010FPAYFee paymentYear of fee payment: 4Oct 31, 2014REMIMaintenance fee reminder mailedMar 20, 2015LAPSLapse for failure to pay maintenance feesMay 12, 2015FPExpired due to failure to pay maintenance feeEffective date: 20150320RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services