CN1882938A - Process and apparatus for determining transformation elements for a given transformation function, digital signal transformation method and apparatus, and computer readable medium - Google Patents
Process and apparatus for determining transformation elements for a given transformation function, digital signal transformation method and apparatus, and computer readable medium Download PDFInfo
- Publication number
- CN1882938A CN1882938A CN 200480034076 CN200480034076A CN1882938A CN 1882938 A CN1882938 A CN 1882938A CN 200480034076 CN200480034076 CN 200480034076 CN 200480034076 A CN200480034076 A CN 200480034076A CN 1882938 A CN1882938 A CN 1882938A
- Authority
- CN
- China
- Prior art keywords
- mrow
- msub
- mtd
- munder
- mtr
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Complex Calculations (AREA)
Abstract
According to a process for determining a transformation element of a given transformation function, which transformation function comprises a transformation matrix and corresponds to a transformation of a digital signal from the time domain to the frequency domain or from the frequency domain to the time domain, said transformation matrix is decomposed into a rotation matrix (306) and an auxiliary matrix (307), which, when multiplied with itself, is equal to a permutation matrix multiplied with an integer diagonal matrix. Further, each of the rotation matrix (306) and the auxiliary matrix (307) is decomposed into a plurality of lifting matrices (308). Further, the transformation element is determined to include a plurality of lifting stages (309) corresponding to the lifting matrix (308). The present invention also provides a method for transforming a digital signal from the time domain to the frequency domain in accordance with the transformation elements determined by the above process.
Description
Cross Reference to Related Applications
This application claims priority from U.S. provisional application No.60/507,210 filed on 9/29/2003 and U.S. provisional application No.60/507,440 filed on 9/29/2003, the contents of each of which are incorporated herein by reference in their entirety for all purposes.
Further, the following commonly owned applications are filed concurrently herewith and are hereby incorporated by reference in their entirety:
"Method for Forming a Domain Transformation of a digital Signal from the Time Domain in the Frequency Domain and vice Versa", attorney docket No. P100442, and
"Method for Transforming a Digital Signal from the Time Domain to the Frequency Domain and View Versa", attorney docket No. P100444.
Technical Field
The present invention relates to a process and a device for determining a transform element of a given transform function, a method and a device for transforming a digital signal from the time domain to the frequency domain and vice versa, and a computer-readable medium.
Background
Domain transforms, such as the Discrete Cosine Transform (DCT), are widely used in today's signal processing industry. In recent years, the variation of DCT called integer DCT has attracted much research interest because of its important role in lossless coding applications. The term "lossless" means that the decoder can generate an exact copy of the source signal from the encoded bit stream.
The DCT is a real-valued block transform. The output block of the DCT may include non-integer components even if the input block includes only integers. For simplicity, the input block is referred to as an input vector and the output block is referred to as an output vector. If a vector includes only integer components, the vector is referred to as an integer vector. In contrast to the DCT, the integer DCT generates an integer output vector from an integer input vector. For the same integer input vector, the integer output vector of the integer DCT closely approximates the real output vector of the DCT. Thus, the integer DCT retains all the good properties of the DCT when spectrally analyzed.
An important property of the integer DCT is reversibility. Invertibility means that there is an integer Inverse Discrete Cosine Transform (IDCT) such that if the integer DCT produces an output vector y from an input vector x, the integer IDCT can recover the vector x from the vector y. Sometimes integer DCT is also referred to as forward transform and integer IDCT is referred to as inverse transform or inverse transform.
A transform called the integer modified discrete cosine transform (IntMDCT) has been proposed in recent years and is used in ISO/IEC MPEG-4 audio compression. The IntMDCT is derived from its prototype-Modified Discrete Cosine Transform (MDCT). In [1], Malvar gives a method to efficiently implement MDCT by concatenating DCT-IV blocks with multiple Givens rotations. It is well known that Givens rotations can be decomposed into three lifting steps for mapping integers to integers, see example [2 ].
Therefore, the implementation of the IntMDCT relies on an efficient implementation of the integer DCT-IV.
By replacing each Givens rotation with three lifting steps, one can convert directly from a prototype of the integer transform to an integer transform. Since there is one rounding operation in each lifting step, the total number of rounds of the integer transform is 3 times the number of Givens rotations of the prototype transform. For discrete trigonometric transforms, such as the Discrete Fourier Transform (DFT) or the Discrete Cosine Transform (DCT), the number of Givens rotations involved is typically Nlog2Of the order of N, where N is the size of the block, i.e. the amount of data symbols included in each block into which the digital signal is divided. Thus, for the family transforms of the direct-conversion integer transform, the total rounding is total number of timesIs also Nlog2Of the order of N. Due to the rounding, the integer transform only approximates its floating point prototype. The approximation error increases with increasing rounding times.
Disclosure of Invention
The invention solves the problem of determining a transformation element of a given transformation function, which transformation function comprises a transformation matrix and corresponds to a transformation of a digital signal from the time domain into the frequency domain or vice versa, such that the number of rounds comprised by said transformation element is significantly reduced. The invention also provides a method for transforming a digital signal from the time domain to the frequency domain or from the frequency domain to the time domain in accordance with said determined transformation element.
The problem is solved by a process and a device for determining a transform element of a given transform function, a method and a device for transforming a digital signal from the time domain to the frequency domain and vice versa, and a computer-readable medium, with the features according to the independent claims.
According to the present invention, there is provided a process for determining a transform element of a given transform function, the transform function comprising a transform matrix and corresponding to a transformation of a digital signal from a time domain to a frequency domain or from a frequency domain to a time domain, wherein said transform matrix is decomposed into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix, each of said rotation matrix and said auxiliary matrix being decomposed into a plurality of lifting matrices; and the transformation element is determined to include a plurality of lifting stages corresponding to the lifting matrix.
Further, according to the present invention, there is provided an apparatus adapted to perform the above-described process.
Further, according to the present invention, there is provided a method for transforming a digital signal from the time domain to the frequency domain or from the frequency domain to the time domain using a transform element, wherein the transform element corresponds to a given transform function comprising a transform matrix, wherein the transform element is determined by a process comprising decomposing the transform matrix into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix; decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices; and determining that the transformation element comprises a plurality of lifting stages corresponding to the lifting matrix; wherein each lifting stage comprises processing of sub-blocks of the digital signal with an auxiliary transform and a rounding unit.
Furthermore, according to the present invention, there is provided an apparatus adapted to perform the above method.
Further, according to the present invention, there is provided a computer-readable medium having a program recorded thereon, wherein the program is adapted to cause a computer to execute a process for determining a transform element of a given transform function, the transform function including a transform matrix and corresponding to a transform of a digital signal from a time domain to a frequency domain or from a frequency domain to a time domain, wherein the transform matrix is decomposed into a rotation matrix and an auxiliary matrix, which when multiplied by itself is equal to a permutation matrix multiplied by an integer diagonal matrix; each of the rotation matrix and the auxiliary matrix is decomposed into a plurality of lifting matrices; and the transformation element is determined to include a plurality of lifting stages corresponding to the lifting matrix.
Further, according to the present invention, there is provided a computer-readable medium having a program recorded thereon, wherein the program is adapted to make a computer execute a method for transforming a digital signal from a time domain to a frequency domain or from the frequency domain to the time domain using transform elements, wherein the transform elements correspond to a given transform function, the transform function comprising a transform matrix, wherein the transform elements are determined by a process comprising: decomposing the transformation matrix into a rotation matrix and an auxiliary matrix, when the auxiliary matrix is multiplied by itself, the auxiliary matrix is equal to a permutation matrix multiplied by an integer diagonal matrix, and decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices; and determining that the transformation element comprises a plurality of lifting stages corresponding to the lifting matrix; wherein each lifting stage comprises processing sub-blocks of the digital signal with an auxiliary transform and a rounding unit.
In a preferred embodiment, the present invention provides a process and method for implementing an integer type IV DCT transform. The number of rounding operations required for the process according to the invention is significantly reduced compared to the processes of the prior art. As a result, the approximation error is significantly reduced, in the case of DCT-IV, from the usual Nlog2The magnitude of N is reduced to as low as 2.5N, where N represents the block size of the digital signal. The method according to the invention is low in computational complexity and modular in construction.
The method and device according to the invention can be used for any type of digital signal, such as audio, image or video signals. The digital signal, which is a digitized signal, corresponds to a physically measurable signal, which may be generated by scanning at least one characteristic feature of the respective analog signal (e.g., luminance and chrominance values of a video signal, an amplitude of an analog sound signal from a sensor, or an amplitude of an analog sensing signal). The digital signal includes a plurality of data symbols. The data symbols of the digital signal are grouped into a plurality of blocks, wherein each block has the same predetermined number of data symbols based on the sampling rate of the corresponding analog signal.
The method according to the invention can be used to convert an input digital signal that is an integer value into an output signal that is also an integer value. The transformation method according to the invention is reversible. The output signal may be transformed back to the original input signal by performing a transformation method according to the invention. Such reversibility of the transformation according to the method of the invention can be used in lossless coding where the output signal should be identical to the original input signal.
Such integer transformation of signals according to the invention can be used in many applications and systems, such as MPEG audio, image and video compression, JPEG2000 or spectral analysis (for analyzing infrared, ultraviolet or nuclear magnetic radiation signals). It can be easily implemented in hardware systems such as fixed-point Digital Signal Processors (DSPs) without considering factors such as overflow in case of real-valued signal conversion.
According to the inventive method, the digital signal is transformed into the frequency domain using a transformation element which is determined for a given transformation function according to the inventive procedure.
Preferably, the transformation element comprises a plurality of promotion levels.
The transformation element may be instantiated based on a model of the lifting staircase. The elevated stair model has two side members (pieces), each for receiving one of two sets of data symbols. Two or more cascade-connected upgrade stages are arranged between the two side parts. Each booster stage receives a signal at one end (input end) and outputs a signal at the other end (output end) via an adding unit. The rounding unit is arranged at the output. The lifting stages are arranged between the side members in an alternating manner such that the output (or input) terminals of adjacent lifting stages are connected to different side members.
It should be noted that although the transformation elements are described in the form of a lifting staircase model, only the transformation paths of the transformation elements are illustrated. However, the present invention should not be limited to the staircase model.
The number of lifting stages of said transformation element is defined by the number of lifting matrices, which is determined by the process according to the invention.
Discrete cosine transform, discrete sine transform, discrete fourier transform or discrete W transform are examples of transform functions that may be used as transform functions according to the present invention. The number of lifting levels of the transformation elements of the respective transformation functions may differ depending on the result of the process according to the invention for determining the transformation elements.
Drawings
Exemplary embodiments of the invention are described below with reference to the accompanying drawings, in which:
FIG. 1 shows an architecture of an audio encoder according to an embodiment of the invention;
FIG. 2 shows an architecture of an audio decoder according to an embodiment of the invention, corresponding to the audio encoder shown in FIG. 1;
FIG. 3 illustrates an embodiment of a process according to the present invention, wherein the transform function is a DCT-IV transform function;
FIG. 4 shows a flow chart of an embodiment of a method according to the invention;
fig. 5 illustrates an embodiment of the method according to the invention using DCT-IV as the transform function;
FIG. 6 illustrates an algorithm for inverse transformation according to an embodiment of the method of the present invention illustrated in FIG. 5;
FIG. 7 illustrates an architecture of an image archiving system according to an embodiment of the present invention;
FIG. 8 illustrates an embodiment of the method according to the invention using DWT-IV as a transformation function;
fig. 9 illustrates an algorithm for inverse transformation according to an embodiment of the method of the present invention illustrated in fig. 8.
Detailed Description
Fig. 1 shows a structure of an audio encoder 100 according to an embodiment of the present invention.
The audio encoder 100 comprises a conventional perceptual base layer encoder based on the Modified Discrete Cosine Transform (MDCT) and a lossless enhancement encoder based on the integer modified discrete cosine transform (IntMDCT).
For example, an audio signal 109 provided by a microphone 110 and digitized by an analog-to-digital converter 111 is provided to the audio encoder 100. The audio signal 109 comprises a plurality of data symbols. The audio signal 109 is divided into a plurality of blocks, wherein each block comprises a plurality of data symbols of the digital signal and each block is transformed by a Modified Discrete Cosine Transform (MDCT) device 101. The MDCT coefficients provided by the MDCT device 101 are quantized by a quantizer 103 by means of a perceptual model 102. The perceptual model controls the quantizer 103 in such a way that the sound distortion resulting from quantization errors is low. The output of the quantizer 103 is then encoded by a bitstream encoder 104, which bitstream encoder 104 produces a lossy perceptually encoded output bitstream 112. The bitstream encoder 104 losslessly compresses its input using standard methods such as Huffman coding or Run-Length coding to produce an output having an average bit rate that is lower than the average bit rate of its input. The input audio signal 109 is also fed into the IntMDCT device 105 which generates IntMDCT coefficients. The quantized MDCT coefficients, which are the output of the quantizer 103, are used for predicting the IntMDCT coefficients. The quantized MDCT coefficients are fed to an inverse-quantizer 106, and the output of the inverse-quantizer 106 is fed to a rounding unit 107, which rounds the output of the inverse-quantizer 106 to integer values, and residual IntMDCT coefficients are entropy encoded by an entropy encoder 108 on residual IntMDCT coefficients, which are the difference between the output of the rounding unit 107 and the IntMDCT coefficients. The entropy encoder (similar to the bitstream encoder 104)108 losslessly reduces the average bit rate of its input and produces a lossless enhancement bitstream 113. The lossless enhancement bitstream 113 and the perceptually encoded bitstream 112 together carry the information necessary to accurately reconstruct the input audio signal 109.
Fig. 2 shows an architecture of an audio decoder 200 comprising an embodiment of the invention, which corresponds to the audio encoder 100 shown in fig. 1.
The perceptually encoded bitstream 207 is decoded by a bitstream decoder 201, the bitstream decoder 201 performing the inverse of the operation of the bitstream encoder 104 of fig. 1. The decoded bit stream is provided to an inverse-quantizer 202. At its output, the inverse MDCT is applied by an inverse modified discrete cosine transform device (inverse MDCT) 203. Thus, a reconstructed perceptually encoded audio signal 209 is obtained. The lossless enhancement bitstream 208 is decoded by the entropy decoder 204, and the entropy decoder 204 performs the inverse of the operation of the entropy encoder 108 of fig. 1 to produce corresponding residual IntMDCT coefficients. The output of the inverse-quantizer 202 is rounded by a rounding device 205 and then added to the residual IntMDCT coefficients, thereby generating the IntMDCT coefficients. Finally, the inverse integer modified discrete cosine transform of the IntMDCT coefficients is performed by the inverse integer modified discrete cosine transform device 206 to generate the reconstructed lossless encoded audio signal 210.
As mentioned above, the core of the IntMDCT, which plays an important role in lossless audio coding and is used in the embodiments of the present invention illustrated in fig. 1 and 2, is shown in [2] as integer DCT-IV.
Fig. 3 illustrates a flow diagram of an embodiment of a process according to the present invention, wherein the transform function is a DCT-IV transform function.
In the following, an embodiment of the inventive procedure for determining the transform elements of a DCT-IV transform function is explained. The determined transformation elements are used in the encoder shown in fig. 1 to implement the IntMDCT, while the corresponding inverse transformation elements are used in the decoder shown in fig. 2 to implement the inverse IntMDCT. See [2] for a description of how to implement IntMDCT and inverse IntMDCT with DCT-IV.
The DCT-IV transform function with an N-point real input sequence x (N) is defined as follows (see [2 ]):
suppose thatIs the transform matrix of the DCT-IV, i.e.,
according to an embodiment of the process of the present invention, a transformation matrix is transformed
Is decomposed into a rotation matrix and another matrix, which is multiplied by itselfIs equal to the multiplication of the permutation matrix by the integer diagonal matrix.
For clarity, N is assumed to be even.
The process starts at step 300.
In step 301, the even index entries are separated from the odd index entries of the transformation function:
therefore, the temperature of the molten metal is controlled,
having therein a component x1(n)＝x(2n)， Is/are as followsx 1Is a vector comprising all x (n) with even indices, but with a component x2(n)＝x(2n+1)， Is/are as followsx 2Is a vector that includes all x (n) with odd indices.
The following two abbreviations are used:
using equations (4) and (5), equation (3) can be written as:
in step 302, the following two cosine addition theorems apply:
cos(αm，n-βm)＝cosαm，n·cosβm+sinαm，n·sinβm (7)
cos(αm，n+βm)＝cosαm，n·cosβm-sinαm，n·sinβm (8)
using equations (7) and (8), equation (6) can be written as
For the simple, two vectors of size N/2x 1' andx 2' is defined to include the following components:
using (10) and (11), equation (9) is simplified to
In step 303, the vector
Is divided into two partsy 0Andy 1wherein
(Vector)y 1Comprises a pressIn reverse order to correspond to slaveIndexing to N-1yThe component (c).
(Vector)y 1Component y of1(m) satisfies the following equation:
in that In the case of (a) in (b),
y1(m)＝y(N-1-m)
note that for
In a step 304, the process is repeated,y 0andy 1each of which is composed of a DCT-IV matrix
And DST-IV matrix
Is expressed as each having a size of
This is achieved as follows:
for the <math> <mrow> <msub> <mi>β</mi> <mi>m</mi> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mi>m</mi> <mo>+</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> <mfrac> <mi>π</mi> <mrow> <mn>2</mn> <mi>N</mi> </mrow> </mfrac> <mo>,</mo> </mrow> </math> The following equation holds true:
in addition to this, the present invention is,
for the <math> <mrow> <msub> <mi>α</mi> <mrow> <mi>m</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow> <mo>(</mo> <mi>m</mi> <mo>+</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mi>n</mi> <mo>+</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> <mfrac> <mi>π</mi> <mrow> <mo>(</mo> <mfrac> <mi>N</mi> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> </mfrac> <mo>,</mo> </mrow> </math> The following equation holds true:
in addition to this, the present invention is,
cosαN-1-m，n＝cos(2πn+π-αm，n)＝cos(π-αm，n)＝-cosαm，n (22)
sinαN-1-m，n＝sin(2πn+π-αm，n)＝sin(π-αm，n)＝sinαm，n (23)
using equations (19), (20), (22), and (23), equation (15) may be written as
Since another equation (12) yields
According to (24) and (25), can be formedy 0Andy 1expression (c):
wherein diag [ a ]m]Representing a diagonal matrix of N/2 XN/2, the m-th row of the matrix being am， Is a transform matrix of DCT-IV transform, and
is a transform matrix of type IV discrete sine transform (DST-IV).
The two equations (26) and (27) can be expressed as a single equation in the following manner:
in the following, use is made ofMatrix array
And
it can be seen that
It can be simplified as
It can also be seen that, with an N x N matrix,R prcan be defined as
The following equation holds true:
equation (34) can be simplified as
Further, assume thatP eoIs an even-odd matrix, i.e., a permutation matrix, which reorders the vectors by separating the components corresponding to even indices from the components corresponding to odd indicesxWherein
So that the following equation holds
Or simply as
By combining equation (28) with equations (31), (34) and (36), it can be concluded
Using the above and following abbreviations
And
equation (38) may be abbreviated
At step 305, utilizeTo representThis is done using the following equation.
Wherein
Is a diagonal matrix of order N/2 as given below
Using equation (42), equation (41) can be written as
At step 306, an N rotation matrix is calculatedR poThe rotation matrix includes the first three matrices in equation (44):
multiplication of the three matrices in equation (45) is performed to obtain
In step 307, an auxiliary matrix is calculated which, when multiplied with itself, is equal to the permutation matrix multiplied with the integer diagonal matrix.
The auxiliary matrix comprises fourth and fifth matrices of equation (44):
attention is paid to
I.e. T multiplied by itself is equal to the permutation matrix multiplied by the integer diagonal matrix.
Using equations (46) and (47), equation (44) can be simplified to
Thus, the transformation matrix
Is decomposed into rotation matricesR poAuxiliary matrixTAnd even-odd matrixP eoWherein when the auxiliary matrixTWhen multiplied by itself, is equal to the permutation matrix multiplied by the integer diagonal matrix.
In a step 308 of the method, the step of the method,R poandTare each factorized into the product of lifting matrices. According to
T is factorized as follows:
wherein
And factoring according to the following equationR po：
Wherein
And
equation (49) may be further written as
In step 309, the lifting matrices are merged together as much as possible. The matrix S is defined as the product of R3 and T1, i.e.
Due to the fact thatSIs also a lifting matrix, so this merging is possible.
From (57) and (58), the final factorization of the obtained DCT-IV matrix is formulated as
Equation (59) indicates that the transform elements of the integer DCT-IV transform according to the present invention include five lifting stages.
Since the final factorization formula is determined, the process stops at step S310.
Fig. 4 shows a flow chart 400 of an embodiment of a method according to the invention using five upgrade stages, a first upgrade stage 401, a second upgrade stage 402, a third upgrade stage 403, a fourth upgrade stage 404 and a fifth upgrade stage 405. This method is preferably used in the IntMDCT device 105 of fig. 1 and the anti-inmdct device 206 of fig. 2 to implement the IntMDCT and the anti-IntMDCT, respectively. In the context of figure 4 of the drawings,x 1andx 2respectively a first and a second block of digital signals,z 1、 z 2andz 3is the intermediate signal(s) of the signal,y 1andy 2respectively, output signals corresponding to the first and second blocks of the digital signal.
Fig. 5 shows a flow chart of an embodiment of the method according to the invention, wherein the transform function is a DCT-IV transform function. The transformation element used in this embodiment corresponds to equation (59), i.e. it is the transformation element determined by the embodiment of the process illustrated in fig. 3.
The transformation elements include five lifting stages corresponding to the five lifting matrices of equation (59).
Further, the transformation element includes a permutation matrixP eoCorresponding data reassembly (shuffling) stage.
In fig. 5, the inputs of the first upgrade stages are two blocks of a digital signalx 1Andx 2， z 1、 z 2andz 3is the intermediate signal(s) of the signal,y 1andy 2respectively, output signals corresponding to the first and second blocks of the digital signal.
Input of the transformation elementxAnd two input blocks of a first lifting stage of said transformation elementx 1Andx 2satisfy the equation
(in accordance with equation (37)).
In the following, a first lifting stage 501 is explained, which is a lifting matrixT 3A corresponding boost level. Suppose that <math> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <munder> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo>‾</mo> </munder> </mtd> </mtr> <mtr> <mtd> <munder> <msub> <mi>v</mi> <mn>2</mn> </msub> <mo>‾</mo> </munder> </mtd> </mtr> </mtable> </mfenced> </math> Is the first when not rounded to an integer valueBy raising the output vector of the stage, i.e.
Using the equation provided by equation (50)T 3Can be rewritten as in equation (61)
Since in this embodiment, which provides a reversible algorithm for the integer DCT-IV, a rounding to an integer value is included. Thus, according to equation (62), in a first step 506 of the first upgrade stage 501,x 1andK 3multiplication. In step 507, the result of this multiplication is rounded to an integer value. At step 508, the rounded value is then added tox 2. Thus, intermediate signalsz 1Satisfies the equation:
z 1＝_ K 3· x 1_+ x 2
where _ denotes a rounding operation.
Since the transformation elements illustrated in FIG. 5 correspond to matrices, respectivelyT 2、 S、 R 2AndR 1the remaining four upgrade stages 502, 503, 504, and 505 have the same structure as the first upgrade stage 501, and thus the description thereof is omitted. It should be noted only that in the adding step 509 of the second upgrade stage 502, the process is based onT 2In the definition of (a) is,x 1and-D N/2Multiplication.
In the following, the upgrade of the inversely transformed transform element is described with reference to fig. 6.
Fig. 6 illustrates a lifting stage of a transform element of an inverse transform of the transform illustrated in fig. 5.
In FIG. 6, the inputs to the first upgrade stage are two blocks of digital signalsy 1Andy 2， z 1、 z 2andz 3is the intermediate signal(s) of the signal,x 1andx 2respectively, output signals corresponding to the first and second blocks of the digital signal.
The last mentioned stage 605 illustrated in fig. 6 is the inverse of the first mentioned stage 501 illustrated in fig. 5. Thus, in the first step 606 of the last mentioned stage 605,x 1andK 3multiplication. In step 607, the result of this multiplication is rounded to an integer value. Then at step 608, fromz 1The value rounded off is subtracted. Thus, the signalx 2Satisfies the equation:
x 2＝ z 1-_ K 3· x 1_ (64)
where _ denotes a rounding operation.
Since the remaining four of the transformation elements illustrated in fig. 6 are the lifting stages 601, 602, 603, and 604, which are the inverses of the lifting stages 505, 504, 503, and 502, respectively, having the same structure as the last lifting stage 605, the description thereof is omitted. It should only be noted that after the addition step 609 of the fourth upgrade stage 604, the result of the addition step 609 is combined with-D N/2Multiply to producex 1。
It can be seen that the stages 605, 604, 603, 602 and 601 in fig. 6 are the inverse of the stages 501 to 505, respectively, in fig. 5. Due to the matrixP eoThe permutation of the corresponding input signal is also reversible and the inverse transform element comprises the corresponding data reconstruction stage, so the provided method is reversible. Thus, if used in the audio encoder 100 and the audio decoder 200 illustrated in fig. 1 and 2, a method and apparatus for lossless audio encoding are obtained.
An analysis of the number of rounds used in this example is given at the end of the description of the invention.
FIG. 7 illustrates an architecture of an image archiving system according to an embodiment of the present invention.
In fig. 7, an image source 701, such as a camera, provides an analog image signal. The image signals are processed by an analog-to-digital converter 702 to provide corresponding digital image signals. The digital image signal is losslessly encoded by a lossless image encoder 703, which includes a transform from the time domain to the frequency domain. In this embodiment, the time domain corresponds to the coordinate space of the image. The lossless encoded image signal is stored in a storage device 704, such as a hard disk or DVD. When the image is needed, the losslessly encoded image signal is fetched from the storage 704 and provided to a lossless image decoder 705, which lossless image decoder 705 decodes the losslessly encoded image signal and reconstructs the original image signal without data loss.
Such lossless archiving of image signals is important, for example, where the image is an error map of a semiconductor wafer and must be stored for later analysis.
In the following, a further embodiment of the method for transforming a digital signal from the time domain to the frequency domain and vice versa according to the invention is explained. This embodiment is preferably used in the lossless image encoder 703 and the lossless image decoder 705 of the image archiving system illustrated in fig. 7.
Fig. 8 illustrates an embodiment of the method according to the invention using DWT-IV as the transformation function.
The DWT-IV of the N-point real input sequence x (N) is defined as follows:
DWT-IV transformation matrixIs given as follows
According to the process of the invention, the DWT-IV matrix is factorized into the following form:
R Nis an N × N rotation matrix defined as:
I N/2is an identity matrix of order N/2 (in accordance with equation (29))。 J N/2Is an inverse identity matrix of order N/2 (consistent with equation (30)).
P NIs a permutation matrix of NxN
TIs an N × N matrix defined as:
whereinIs a DCT-IV matrix of order N/2,
D N/2is a diagonal matrix of order N/2 as given below
In accordance with the process of the present invention,R NandTcan be further factored into the product of lifting matrices:
wherein, <math> <mrow> <munder> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>‾</mo> </munder> <mo>=</mo> <mrow> <mo>(</mo> <msqrt> <mn>2</mn> </msqrt> <munder> <msub> <mi>I</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> </msub> <mo>‾</mo> </munder> <mo>-</mo> <munder> <msubsup> <mi>C</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> <mi>IV</mi> </msubsup> <mo>‾</mo> </munder> <munder> <msub> <mi>D</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> </msub> <mo>‾</mo> </munder> <mo>)</mo> </mrow> <munder> <msubsup> <mi>C</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> <mi>IV</mi> </msubsup> <mo>‾</mo> </munder> <mo>,</mo> <munder> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo>‾</mo> </munder> <mo>=</mo> <mfrac> <mrow> <mo>-</mo> <munder> <msubsup> <mi>C</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> <mi>IV</mi> </msubsup> <mo>‾</mo> </munder> </mrow> <msqrt> <mn>2</mn> </msqrt> </mfrac> <mo>,</mo> <munder> <msub> <mi>K</mi> <mn>3</mn> </msub> <mo>‾</mo> </munder> <mo>=</mo> <msqrt> <mn>2</mn> </msqrt> <munder> <msubsup> <mi>C</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> <mi>IV</mi> </msubsup> <mo>‾</mo> </munder> <munder> <msub> <mi>D</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> </msub> <mo>‾</mo> </munder> <mo>-</mo> <munder> <msub> <mi>I</mi> <mrow> <mi>N</mi> <mo>/</mo> <mn>2</mn> </mrow> </msub> <mo>‾</mo> </munder> </mrow> </math>
and
wherein
And
therefore, equation (67) can be written as follows
According to the process of the invention, the lifting steps are merged as much as possible.
In this embodiment, the lifting matrixR 3AndT 1can be merged into a lifting matrixS：
From (77) and (78), the following factorization formula for the DWT-IV matrix can be obtained:
equation (79) indicates that the transform elements of the integer DWT-IV transform according to the present invention include five promotion stages.
Further, the transformation element includes a permutation matrixP NCorresponding data reconstruction stage. The data re-organization stage rearranges the order of the components in each input data block. According toP NThe input data vector is rearranged as follows: the first half of the vector remains unchanged and the second half of the vector is turned upside down, i.e. the
In FIG. 8, the inputs to the first upgrade stage are two blocks of digital signalsx 1Andx 2， z 1、 z 2andz 3is the intermediate signal(s) of the signal,y 1andy 2respectively, output signals corresponding to the first and second blocks of the digital signal.
Input x of the transformation element and two input blocks of a first lifting stage of the transformation elementx 1Andx 2satisfy the equation
In the following, a first lifting stage 801 is explained, which is a lifting matrixT 3A corresponding boost level. Suppose that <math> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <munder> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo>‾</mo> </munder> </mtd> </mtr> <mtr> <mtd> <munder> <msub> <mi>v</mi> <mn>2</mn> </msub> <mo>‾</mo> </munder> </mtd> </mtr> </mtable> </mfenced> </math> Is the output vector of the first lifting stage when not rounded to an integer value, i.e.
Using a signal provided by equation (73)T 3Can be rewritten as
Since in the reversible algorithm for integer DCT-IV provided in this embodiment, inclusion into integer values is madeIs rounded off. Therefore, according to equation (83), in a first step 806 of the first upgrade stage 801,x 1andK 3multiplication. In step 807, the result of this multiplication is rounded to an integer value. At step 808, the rounded value is then added tox 2. Thus, intermediate signalsz 1Satisfies the equation:
z 1＝_ K 3· x 1_+ x 2 (84)
where _ denotes a rounding operation.
Since the remaining four promotion levels 802, 803, 804, and 805 of the transformation element illustrated in fig. 8 correspond to matrices, respectivelyT 2、 S、 R 2AndR 1it has the same structure as the first upgrade stage 801, so its description is omitted. It should be noted only that in the adding step 809 of the second upgrade stage 802, the process is carried out according toT 2In the definition of (a) is,x 1andD N/2multiplication.
In the following, the upgrade of the inversely transformed transform element is described with reference to fig. 9.
Fig. 9 illustrates a lifting stage of a transform element of an inverse transform of the transform illustrated in fig. 8.
In FIG. 9, the inputs to the first upgrade stage are two blocks of digital signalsy 1Andy 2， z 1、 z 2andz 3is the intermediate signal(s) of the signal,x 1andx 2respectively, output signals corresponding to the first and second blocks of the digital signal.
Example in FIG. 9The last upgrade 905 is shown inverted from the first upgrade 801 illustrated in FIG. 8. Thus, in the first step 906 of the last mentioned stage 905,x 1andK 3multiplication. In step 907, the result of this multiplication is rounded to an integer value. Then at step 908, fromz 1The value rounded off is subtracted. Thus, the signalx 2Satisfies the equation:
x2＝z1-_K3·x1_ (85)
where _ denotes a rounding operation.
Since the remaining four of the transformation elements illustrated in fig. 9 are the lifting stages 901, 902, 903, and 904, which are the inverses of the lifting stages 805, 804, 803, and 802, respectively, have the same structure as the last lifting stage 905, the description thereof is omitted. It should be noted only that after the addition step 909 of the fourth upgrade stage 904, the result of the addition step 909 is summed withD N/2Multiply to producex 1。
It can be seen that the stages 905, 904, 903, 902 and 901 in fig. 9 are the inverse of the stages 801 to 805 in fig. 8, respectively. Due to the matrixP NThe permutation of the corresponding input signal is also reversible and the inverse transform element comprises the corresponding data reconstruction stage, so the provided method is reversible. Accordingly, if used in the lossless image encoder 703 and the lossless image decoder 705 illustrated in fig. 7, a method and apparatus for lossless image encoding are obtained.
Although in the described embodiments the method of DCT-IV according to the invention is used for audio coding and the method of DWT-IV according to the invention is used for image coding, the method of DCT-IV according to the invention is equally applicable for image coding and the method of DWT-IV according to the invention is equally applicable for audio coding, and both methods can be used for coding of other digital signals, such as video signals.
Considering equations (63) and (64), it can be seen that there is a rounding of N/2 times in each of the proposed stages. Thus, considering equation (59), it can be seen that the total rounding times of the transform elements of the DCT-IV algorithm according to the invention are five times N/2, i.e. 2.5N, which is significantly lower than the Nlog according to the prior art2N。
Considering equation (59) again, it can be seen that when N is a large value, e.g., N is 1024, the main amount of computation is used in correspondence with NFour N/2 point DCT-IV subroutines of multiplication. Since the floating point DCT-IV can be calculated using the two half-length DCT-IV plus the pre-rotation and the post-rotation according to equations (47) and (49), the algorithmic complexity of the proposed integer DCT-IV can be roughly estimated to be twice the algorithmic complexity of the floating point DCT-IV.
Similar conclusions can be drawn for the integer DWT-IV transform function.
In the following, a further embodiment using discrete fourier transformation is explained.
Transform matrix as transform matrix for N-order normalized FFTF NGiven as follows:
m，n＝0，1，…，N-1
where transform size N is an even number.
Following the radix-2 (radix-2) time decimation FFT algorithm, decomposition can be done in the following mannerF N：
Wherein, as described above,P eois an even-odd matrix, i.e., a permutation matrix, which reorders the vectors by separating the components corresponding to even indices from the components corresponding to odd indicesxWherein
So that
Suppose thatF N/2Is the transform matrix of the normalized FFT of order N/2.
Suppose thatWIs a diagonal matrix given below
Wherein WN＝e-j2π/N。
As described above, in the above-described embodiments,I N/2representing an identity matrix of order N/2.
In equation (87), the first matrix on the left is the even-odd matrixP eoIt simply reorders the components in the input vector.
In equation (87), the second matrix on the left may be factored into three lifting matrices in the following manner:
where Q is a permutation matrix of order N/2 as given below
AndJ N/2-lis an inverse index matrix of order N/2-1.
In equation (87), the third matrix on the left is an anti-diagonal matrix that multiplies only half of the components in the input vector by the complex number on the unit circle.
This is interpreted as a rotation in the complex plane.
Let x be xr+jxrIs such a component in the input vector.
In addition, suppose <math> <mrow> <msub> <msup> <munder> <mi>W</mi> <mo>‾</mo> </munder> <mi>k</mi> </msup> <mi>N</mi> </msub> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mi>j</mi> <mn>2</mn> <mi>π</mi> <mo>/</mo> <mi>N</mi> </mrow> </msup> <mo>=</mo> <mi>cos</mi> <mrow> <mo>(</mo> <mn>2</mn> <mi>kπ</mi> <mo>/</mo> <mi>N</mi> <mo>)</mo> </mrow> <mo>-</mo> <mi>j</mi> <mi>sin</mi> <mrow> <mo>(</mo> <mn>2</mn> <mi>kπ</mi> <mo>/</mo> <mi>N</mi> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>c</mi> <mi>k</mi> </msub> <mo>-</mo> <mi>j</mi> <msub> <mi>s</mi> <mi>k</mi> </msub> </mrow> </math> Is a plurality, i.e.WWhen the input vector has been multiplied by the right first matrix and the second matrix in equation (87)WWhen the two signals are multiplied by each other,W N kmultiplied by x.
The result is This is equivalent to x rotating counterclockwise in the complex plane by 2k pi/N radians. This rotation can be factored into three lifting steps as follows:
in equation (87), the fourth matrix on the right is factorized into three lifting matrices as follows:
the radix-2 frequency decimation FFT algorithm is simply the transpose of the radix-2 time decimation FFT algorithm in equation (87).
Thus, the above process can also be applied to factorize the FFT matrix in a frequency decimation mannerF N。
The transformation elements are determined in the lifting matrices using the right-hand factorization in equation (87) by generating a lifting level corresponding to each lifting matrix.
Since a detailed description of how the promotion level is generated based on the promotion matrix has been made above, and in this embodiment, the contents in this respect are similar to those described above. Therefore, the description is omitted here.
The following documents are incorporated herein by reference in the present specification:
H.S.Malvar，“Signal Processing With Lapped Transforms”ArtechHouse，1992；
R.Geiger，T.Sporer，J.Koller，K.Brandenburg，“Audio Coding basedon Integer Transforms”AES 111th Convention，New York，USA，Sept.2001.
Claims (11)
1. A process for determining a transformation element of a given transformation function, the transformation function comprising a transformation matrix and corresponding to a transformation of a digital signal from the time domain into the frequency domain or vice versa, wherein
-said transformation matrix is decomposed into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to the permutation matrix multiplied with the integer diagonal matrix;
-each of the rotation matrix and the auxiliary matrix is decomposed into a plurality of lifting matrices;
-the transformation element is determined to comprise a plurality of lifting stages corresponding to the lifting matrix.
2. The process of claim 1, wherein the transform function is a DCT-I transform function, a DCT-IV transform function, a DST-I transform function, a DST-IV transform function, a DFT-I transform function, a DFT-IV transform function, a DWT-I transform function, or a DWT-IV transform function.
3. The process of claim 1 or 2, wherein each of the lifting matrices is a block triangular matrix with two invertible integer matrices on one diagonal.
4. The process of claim 3, wherein the invertible integer matrices in each lifting matrix are identity matrices or negative identity matrices.
5. The process of any one of claims 1 to 4, wherein the transformation element comprises five promotion levels.
6. The process of any one of claims 1 to 5, wherein an audio signal or a video signal is used as the digital signal.
7. An apparatus for determining transform elements of a given transform function, the transform function comprising a transform matrix and corresponding to a transformation of a digital signal from a time domain to a frequency domain or from a frequency domain to a time domain, the apparatus comprising:
-a first decomposition unit for decomposing the transformation matrix into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix;
-a second decomposition unit for decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices;
-a determination unit for determining the transformation element as comprising a plurality of lifting stages corresponding to the lifting matrix.
8. A method for transforming a digital signal from the time domain to the frequency domain or vice versa using a transformation element, wherein:
said transformation elements corresponding to a given transformation function comprising a transformation matrix, wherein said transformation elements are determined by a process comprising
-decomposing said transformation matrix into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix;
-decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices;
-determining that the transformation element comprises a plurality of lifting stages corresponding to the lifting matrix;
-each lifting stage comprises processing sub-blocks of the digital signal with an auxiliary transform and a rounding unit.
9. Device for transforming a digital signal from the time domain into the frequency domain or vice versa, comprising a transformation unit for transforming the digital signal with a transformation element, wherein
-said transformation elements correspond to a given transformation function comprising a transformation matrix, wherein said transformation elements are determined by a process comprising
-decomposing the transformation matrix into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix,
-decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices;
-determining that the transformation element comprises a plurality of lifting stages corresponding to the lifting matrix;
-the device comprises, for each proposed stage, an auxiliary transform unit for processing sub-blocks of said digital signal, and a rounding unit for processing sub-blocks of said digital signal.
10. A computer-readable medium having a program recorded thereon, wherein the program is adapted to make a computer execute a procedure for determining a transform element of a given transform function, the transform function comprising a transform matrix and corresponding to a transformation of a digital signal from a time domain to a frequency domain or vice versa, wherein
-said transformation matrix is decomposed into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to the permutation matrix multiplied with the integer diagonal matrix;
-each of the rotation matrix and the auxiliary matrix is decomposed into a plurality of lifting matrices;
-the transformation element is determined to comprise a plurality of lifting stages corresponding to the lifting matrix.
11. A computer-readable medium having a program recorded thereon, wherein the program is adapted to make a computer execute a method for transforming a digital signal from a time domain to a frequency domain or vice versa using transform elements, wherein
-said transformation elements correspond to a given transformation function comprising a transformation matrix, wherein said transformation elements are determined by a process comprising
-decomposing the transformation matrix into a rotation matrix and an auxiliary matrix, which when multiplied with itself is equal to a permutation matrix multiplied with an integer diagonal matrix,
-decomposing each of the rotation matrix and the auxiliary matrix into a plurality of lifting matrices;
-determining that the transformation element comprises a plurality of lifting stages corresponding to the lifting matrix;
-each lifting stage comprises processing sub-blocks of the digital signal with an auxiliary transform and a rounding unit.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US50744003P | 2003-09-29 | 2003-09-29 | |
| US60/507,210 | 2003-09-29 | ||
| US60/507,440 | 2003-09-29 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1882938A true CN1882938A (en) | 2006-12-20 |
| CN100520765C CN100520765C (en) | 2009-07-29 |
Family
ID=37520233
Family Applications (3)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB2004800350103A Expired - Fee Related CN100570597C (en) | 2003-09-29 | 2004-05-06 | Method for Transforming Digital Signals from Time Domain to Frequency Domain and Its Inverse Transformation |
| CNB2004800350550A Expired - Fee Related CN100517298C (en) | 2003-09-29 | 2004-05-06 | Method for transforming digital signal from time domain to frequency domain and inverse transformation thereof |
| CNB2004800340760A Expired - Fee Related CN100520765C (en) | 2003-09-29 | 2004-05-06 | Process and device for determining a transforming element for a given transformation function, method and device for transforming a digital signal and computer readable medium |
Family Applications Before (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB2004800350103A Expired - Fee Related CN100570597C (en) | 2003-09-29 | 2004-05-06 | Method for Transforming Digital Signals from Time Domain to Frequency Domain and Its Inverse Transformation |
| CNB2004800350550A Expired - Fee Related CN100517298C (en) | 2003-09-29 | 2004-05-06 | Method for transforming digital signal from time domain to frequency domain and inverse transformation thereof |
Country Status (1)
| Country | Link |
|---|---|
| CN (3) | CN100570597C (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102725609A (en) * | 2009-12-14 | 2012-10-10 | 通腾德国股份有限公司 | Method and system for cross-referencing and deduplicating objects in multiple map building blocks |
| CN105163130A (en) * | 2015-08-25 | 2015-12-16 | 重庆邮电大学 | Image lossless compression method based on discrete Tchebichef orthogonal polynomial |
| CN104318926B (en) * | 2014-09-29 | 2018-08-31 | 四川九洲电器集团有限责任公司 | Lossless audio coding method based on IntMDCT, coding/decoding method |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2009035613A1 (en) * | 2007-09-12 | 2009-03-19 | Dolby Laboratories Licensing Corporation | Speech enhancement with noise level estimation adjustment |
| US8631060B2 (en) | 2007-12-13 | 2014-01-14 | Qualcomm Incorporated | Fast algorithms for computation of 5-point DCT-II, DCT-IV, and DST-IV, and architectures |
| US9501182B2 (en) | 2011-09-30 | 2016-11-22 | Intel Corporation | Mechanism for interpreting touches to a pad cover over a sensor pad at a computing device |
| CN107911122A (en) * | 2017-11-13 | 2018-04-13 | 南京大学 | Lossless compression method for distributed optical fiber vibration sensing data based on decomposition and compression |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5523847A (en) * | 1992-10-09 | 1996-06-04 | International Business Machines Corporation | Digital image processor for color image compression |
| US5999656A (en) * | 1997-01-17 | 1999-12-07 | Ricoh Co., Ltd. | Overlapped reversible transforms for unified lossless/lossy compression |
| US5987005A (en) * | 1997-07-02 | 1999-11-16 | Telefonaktiebolaget Lm Ericsson | Method and apparatus for efficient computation of discrete fourier transform (DFT) and inverse discrete fourier transform |
| WO2000055757A1 (en) * | 1999-03-17 | 2000-09-21 | The Johns Hopkins University | A fast multiplierless transform |
| US6681052B2 (en) * | 2000-01-15 | 2004-01-20 | Sony Corporation | Methods and systems for performing inverse quantization and inverse weighting of DV video |
| US6934676B2 (en) * | 2001-05-11 | 2005-08-23 | Nokia Mobile Phones Ltd. | Method and system for inter-channel signal redundancy removal in perceptual audio coding |
-
2004
- 2004-05-06 CN CNB2004800350103A patent/CN100570597C/en not_active Expired - Fee Related
- 2004-05-06 CN CNB2004800350550A patent/CN100517298C/en not_active Expired - Fee Related
- 2004-05-06 CN CNB2004800340760A patent/CN100520765C/en not_active Expired - Fee Related
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102725609A (en) * | 2009-12-14 | 2012-10-10 | 通腾德国股份有限公司 | Method and system for cross-referencing and deduplicating objects in multiple map building blocks |
| US8918413B2 (en) | 2009-12-14 | 2014-12-23 | Tomtom Germany Gmbh & Co. Kg | Method and system for cross-referencing and deduplicating objects in multiple map building blocks |
| CN102725609B (en) * | 2009-12-14 | 2015-07-29 | 通腾德国股份有限公司 | Method and system for cross-referencing and deduplicating objects in multiple map building blocks |
| US9176983B2 (en) | 2009-12-14 | 2015-11-03 | Tomtom Germany Gmbh & Co. Kg | Method and system for cross-referencing and deduplicating objects in multiple map building blocks |
| CN104318926B (en) * | 2014-09-29 | 2018-08-31 | 四川九洲电器集团有限责任公司 | Lossless audio coding method based on IntMDCT, coding/decoding method |
| CN105163130A (en) * | 2015-08-25 | 2015-12-16 | 重庆邮电大学 | Image lossless compression method based on discrete Tchebichef orthogonal polynomial |
| CN105163130B (en) * | 2015-08-25 | 2019-05-31 | 重庆邮电大学 | A kind of Lossless Image Compression Algorithm method based on discrete Tchebichef orthogonal polynomial |
Also Published As
| Publication number | Publication date |
|---|---|
| CN100517298C (en) | 2009-07-22 |
| CN100570597C (en) | 2009-12-16 |
| CN1886737A (en) | 2006-12-27 |
| CN100520765C (en) | 2009-07-29 |
| CN1918562A (en) | 2007-02-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN1640142A (en) | Method and device for encoding wavelet transform coefficients | |
| CN1171459C (en) | Image encoding device and image decoding device | |
| CN1379366A (en) | Image processing apparatus and method | |
| CN1268135C (en) | Method, device and recording medium for encoding, and method, device and recording medium for decoding | |
| CN101069354A (en) | Information compression-coding device, its decoding device, method thereof, program thereof and recording medium storing the program | |
| CN1860795A (en) | Method and apparatus for transcoding input video based on first transformation kernel to output viedo based on second transformation kernel | |
| CN1685369A (en) | Low complexity and unified transforms for video coding | |
| CN1438613A (en) | Device and medium for encoding and decoding coordinate interpolator keyword data and key value data | |
| CN1855227A (en) | Apparatus and method for separating audio signals | |
| CN1339915A (en) | Image coding device, image decoding device, image decoding method, image decoding method and medium | |
| CN1918633A (en) | Improved coding techniques using estimated spectral magnitude and phase derived from mdct coefficients | |
| CN1200571C (en) | Orthogonal transformation, inverse orthogonal transformation method and device, and encoding and decoding method and device | |
| CN1864158A (en) | Device and method for processing at least two input values | |
| CN101036113A (en) | Information encoding method, decoding method, common multiplier estimation method, apparatus, program, and recording medium using these methods | |
| CN1838724A (en) | Decoding apparatus, dequantizing method, distribution determining method, and program thereof | |
| CN1898724A (en) | Speech/tone coding device and speech/tone coding method | |
| CN1669071A (en) | Method and device for code conversion between audio encoding/decoding methods and storage medium thereof | |
| CN1882938A (en) | Process and apparatus for determining transformation elements for a given transformation function, digital signal transformation method and apparatus, and computer readable medium | |
| CN1238969C (en) | Adaptive state space signal separation, discrimination and recovery architectures and their adaptations for use in dynamic environments | |
| CN1835548A (en) | Decoding apparatus, decoding method and program product therefor | |
| CN101061534A (en) | Audio signal encoding apparatus and method | |
| CN1585970A (en) | Code conversion method, apparatus, program, and storage medium | |
| CN1893607A (en) | Encoding apparatus and method, decoding apparatus and method, image processing system and method, and recording medium | |
| CN1741392A (en) | The method and apparatus that data are encoded and deciphered | |
| CN1269314C (en) | Data processing apparatus |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| C17 | Cessation of patent right | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20090729 Termination date: 20110506 |