Content deleted Content added
→Multidimensional DCTs: some stuff Tag: Reverted |
Undid revision 1243797329 by 167.103.7.80 (talk) unexplained changes |
||
Line 345:
Like for the [[discrete Fourier transform|DFT]], the normalization factor in front of these transform definitions is merely a convention and differs between treatments. For example, some authors multiply the transforms by <math display="inline">\sqrt{2/N}</math> so that the inverse does not require any additional multiplicative factor. Combined with appropriate factors of {{sqrt|2}} (see above), this can be used to make the transform matrix [[orthogonal matrix|orthogonal]].
== Multidimensional DCTs ==
Multidimensional variants of the various DCT types follow straightforwardly from the one-dimensional definitions: they are simply a separable product (equivalently, a composition) of DCTs along each dimension.
=== M-D DCT-II ===
For example, a two-dimensional DCT-II of an image or a matrix is simply the one-dimensional DCT-II, from above, performed along the rows and then along the columns (or vice versa). That is, the 2D DCT-II is given by the formula (omitting normalization and other scale factors, as above):
:<math>
\begin{align}
X_{k_1,k_2} &=
\sum_{n_1=0}^{N_1-1}
\left( \sum_{n_2=0}^{N_2-1}
x_{n_1,n_2}
\cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right]\right)
\cos \left[\frac{\pi}{N_1} \left(n_1+\frac{1}{2}\right) k_1 \right]\\
&= \sum_{n_1=0}^{N_1-1}
\sum_{n_2=0}^{N_2-1}
x_{n_1,n_2}
\cos \left[\frac{\pi}{N_1} \left(n_1+\frac{1}{2}\right) k_1 \right]
\cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right] .
\end{align}
</math>
:The inverse of a multi-dimensional DCT is just a separable product of the inverses of the corresponding one-dimensional DCTs (see above), e.g. the one-dimensional inverses applied along one dimension at a time in a row-column algorithm.
The ''3-D DCT-II'' is only the extension of ''2-D DCT-II'' in three dimensional space and mathematically can be calculated by the formula
:<math>
X_{k_1,k_2,k_3} =
\sum_{n_1=0}^{N_1-1}
\sum_{n_2=0}^{N_2-1}
\sum_{n_3=0}^{N_3-1}
x_{n_1,n_2,n_3}
\cos \left[\frac{\pi}{N_1} \left(n_1+\frac{1}{2}\right) k_1 \right]
\cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right]
\cos \left[\frac{\pi}{N_3} \left(n_3+\frac{1}{2}\right) k_3 \right],\quad
\text{for } k_i = 0,1,2,\dots,N_i-1.
</math>
The inverse of '''3-D DCT-II''' is '''3-D DCT-III''' and can be computed from the formula given by
:<math>
x_{n_1,n_2,n_3} =
\sum_{k_1=0}^{N_1-1}
\sum_{k_2=0}^{N_2-1}
\sum_{k_3=0}^{N_3-1}
X_{k_1,k_2,k_3}
\cos \left[\frac{\pi}{N_1} \left(n_1+\frac{1}{2}\right) k_1 \right]
\cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right]
\cos \left[\frac{\pi}{N_3} \left(n_3+\frac{1}{2}\right) k_3 \right],\quad
\text{for } n_i=0,1,2,\dots,N_i-1.
</math>
Technically, computing a two-, three- (or -multi) dimensional DCT by sequences of one-dimensional DCTs along each dimension is known as a ''row-column'' algorithm. As with [[fast Fourier transform#Multidimensional FFTs|multidimensional FFT algorithms]], however, there exist other methods to compute the same thing while performing the computations in a different order (i.e. interleaving/combining the algorithms for the different dimensions). Owing to the rapid growth in the applications based on the 3-D DCT, several fast algorithms are developed for the computation of 3-D DCT-II. Vector-Radix algorithms are applied for computing M-D DCT to reduce the computational complexity and to increase the computational speed. To compute 3-D DCT-II efficiently, a fast algorithm, Vector-Radix Decimation in Frequency (VR DIF) algorithm was developed.
====3-D DCT-II VR DIF====
In order to apply the VR DIF algorithm the input data is to be formulated and rearranged as follows.<ref>{{cite journal|doi=10.1049/ip-f-2.1990.0063|title=Direct methods for computing discrete sinusoidal transforms|year=1990|last1=Chan|first1=S.C.|last2=Ho|first2=K.L.|journal=IEE Proceedings F - Radar and Signal Processing|volume=137|issue=6|page=433}}</ref><ref name=":0">{{cite journal|first1=O.|last1=Alshibami|first2=S.|last2=Boussakta|title=Three-dimensional algorithm for the 3-D DCT-III|journal=Proc. Sixth Int. Symp. Commun., Theory Applications|date=July 2001|pages=104–107}}</ref> The transform size ''N × N × N'' is assumed to be 2.
[[File:Stages of the 3-D DCT-II VR DIF algorithm.jpg|thumb|The four basic stages of computing 3-D DCT-II using VR DIF Algorithm.|336x336px]]
:<math>
\begin{array}{lcl}\tilde{x}(n_1,n_2,n_3) =x(2n_1,2n_2,2n_3)\\
\tilde{x}(n_1,n_2,N-n_3-1)=x(2n_1,2n_2,2n_3+1)\\
\tilde{x}(n_1,N-n_2-1,n_3)=x(2n_1,2n_2+1,2n_3)\\
\tilde{x}(n_1,N-n_2-1,N-n_3-1)=x(2n_1,2n_2+1,2n_3+1)\\
\tilde{x}(N-n_1-1,n_2,n_3)=x(2n_1+1,2n_2,2n_3)\\
\tilde{x}(N-n_1-1,n_2,N-n_3-1)=x(2n_1+1,2n_2,2n_3+1)\\
\tilde{x}(N-n_1-1,N-n_2-1,n_3)=x(2n_1+1,2n_2+1,2n_3)\\
\tilde{x}(N-n_1-1,N-n_2-1,N-n_3-1)=x(2n_1+1,2n_2+1,2n_3+1)\\
\end{array}
</math>
:where <math>0\leq n_1,n_2,n_3 \leq \frac{N}{2} -1</math>
The figure to the adjacent shows the four stages that are involved in calculating 3-D DCT-II using VR DIF algorithm. The first stage is the 3-D reordering using the index mapping illustrated by the above equations. The second stage is the butterfly calculation. Each butterfly calculates eight points together as shown in the figure just below, where <math>c(\varphi_i)=\cos(\varphi_i)</math>.
The original 3-D DCT-II now can be written as
:<math>X(k_1,k_2,k_3)=\sum_{n_1=1}^{N-1}\sum_{n_2=1}^{N-1}\sum_{n_3=1}^{N-1}\tilde{x}(n_1,n_2,n_3) \cos(\varphi k_1)\cos(\varphi k_2)\cos(\varphi k_3)
</math>
where <math>\varphi_i= \frac{\pi}{2N}(4N_i+1),\text{ and } i= 1,2,3.</math>
If the even and the odd parts of <math>k_1,k_2</math> and <math>k_3</math> and are considered, the general formula for the calculation of the 3-D DCT-II can be expressed as [[File:Single butterfly of the 3-D DCT-II VR DIF algorithm.jpg|thumb|The single butterfly stage of VR DIF algorithm.|310x310px]]
:<math>X(k_1,k_2,k_3)=\sum_{n_1=1}^{\tfrac N 2 -1}\sum_{n_2=1}^{\tfrac N 2 -1}\sum_{n_1=1}^{\tfrac N 2 -1}\tilde{x}_{ijl}(n_1,n_2,n_3) \cos(\varphi (2k_1+i)\cos(\varphi (2k_2+j)
\cos(\varphi (2k_3+l))</math>
where
: <math>\tilde{x}_{ijl}(n_1,n_2,n_3)=\tilde{x}(n_1,n_2,n_3)+(-1)^l\tilde{x}\left(n_1,n_2,n_3+\frac{n}{2}\right) </math>
: <math>+(-1)^j\tilde{x}\left(n_1,n_2+\frac{n}{2},n_3\right)+(-1)^{j+l}\tilde{x}\left(n_1,n_2+\frac{n}{2},n_3+\frac{n}{2}\right) </math>
: <math>+(-1)^i\tilde{x}\left(n_1+\frac{n}{2},n_2,n_3\right)+(-1)^{i+j}\tilde{x}\left(n_1+\frac{n}{2}+\frac{n}{2},n_2,n_3\right) </math>
: <math>+(-1)^{i+l}\tilde{x}\left(n_1+\frac{n}{2},n_2,n_3+\frac{n}{3}\right)</math>
: <math>+(-1)^{i+j+l}\tilde{x}\left(n_1+\frac{n}{2},n_2+\frac{n}{2},n_3+\frac{n}{2}\right) \text{ where } i,j,l= 0 \text{ or } 1.</math>
===== Arithmetic complexity =====
The whole 3-D DCT calculation needs <math>~ [\log_2 N] ~</math> stages, and each stage involves <math>~ \tfrac{1}{8}\ N^3 ~</math> butterflies. The whole 3-D DCT requires <math>~ \left[ \tfrac{1}{8}\ N^3 \log_2 N \right] ~</math> butterflies to be computed. Each butterfly requires seven real multiplications (including trivial multiplications) and 24 real additions (including trivial additions). Therefore, the total number of real multiplications needed for this stage is <math>~ \left[ \tfrac{7}{8}\ N^3\ \log_2 N \right] ~,</math> and the total number of real additions i.e. including the post-additions (recursive additions) which can be calculated directly after the butterfly stage or after the bit-reverse stage are given by<ref name=":0" /> <math>~ \underbrace{\left[\frac{3}{2}N^3 \log_2N\right]}_\text{Real}+\underbrace{\left[\frac{3}{2}N^3 \log_2N-3N^3+3N^2\right]}_\text{Recursive} = \left[\frac{9}{2}N^3 \log_2N-3N^3+3N^2\right] ~.</math>
The conventional method to calculate MD-DCT-II is using a Row-Column-Frame (RCF) approach which is computationally complex and less productive on most advanced recent hardware platforms. The number of multiplications required to compute VR DIF Algorithm when compared to RCF algorithm are quite a few in number. The number of Multiplications and additions involved in RCF approach are given by <math>~\left[\frac{3}{2}N^3 \log_2 N \right]~</math> and <math>~ \left[\frac{9}{2}N^3 \log_2 N - 3N^3 + 3N^2 \right] ~,</math> respectively. From Table 1, it can be seen that the total number
{| class="wikitable sortable"
|+TABLE 1
Comparison of VR DIF & RCF Algorithms for computing 3D-DCT-II
!Transform Size
!3D VR Mults
!RCF Mults
!3D VR Adds
!RCF Adds
|-
|8 × 8 × 8
|2.625
|4.5
|10.875
|10.875
|-
|16 × 16 × 16
|3.5
|6
|15.188
|15.188
|-
|32 × 32 × 32
|4.375
|7.5
|19.594
|19.594
|-
|64 × 64 × 64
|5.25
|9
|24.047
|24.047
|}
of multiplications associated with the 3-D DCT VR algorithm is less than that associated with the RCF approach by more than 40%. In addition, the RCF approach involves matrix transpose and more indexing and data swapping than the new VR algorithm. This makes the 3-D DCT VR algorithm more efficient and better suited for 3-D applications that involve the 3-D DCT-II such as video compression and other 3-D image processing applications.
The main consideration in choosing a fast algorithm is to avoid computational and structural complexities. As the technology of computers and DSPs advances, the execution time of arithmetic operations (multiplications and additions) is becoming very fast, and regular computational structure becomes the most important factor.<ref>{{cite journal |doi=10.1109/78.827550 |title=On the computation of two-dimensional DCT |year=2000 |last1=Guoan Bi |last2=Gang Li |last3=Kai-Kuang Ma |last4=Tan |first4=T.C. |journal=IEEE Transactions on Signal Processing |volume=48 |issue=4 |pages=1171–1183 |bibcode=2000ITSP...48.1171B}}</ref> Therefore, although the above proposed 3-D VR algorithm does not achieve the theoretical lower bound on the number of multiplications,<ref>{{cite journal |doi=10.1109/18.144722 |title=On the multiplicative complexity of discrete cosine transforms |date=July 1992a |last1=Feig |first1=E. |last2=Winograd |first2=S. |journal=IEEE Transactions on Information Theory |volume=38 |issue=4 |pages=1387–1391}}</ref> it has a simpler computational structure as compared to other 3-D DCT algorithms. It can be implemented in place using a single butterfly and possesses the properties of the [[Cooley–Tukey FFT algorithm]] in 3-D. Hence, the 3-D VR presents a good choice for reducing arithmetic operations in the calculation of the 3-D DCT-II, while keeping the simple structure that characterize butterfly-style [[Cooley–Tukey FFT algorithm]]s.
[[File:DCT-8x8.png|thumb|250px|Two-dimensional DCT frequencies from the [[JPEG#Discrete cosine transform|JPEG DCT]]]]
The image to the right shows a combination of horizontal and vertical frequencies for an {{nobr| 8 × 8 }} <math>(~ N_1 = N_2 = 8 ~)</math> two-dimensional DCT. Each step from left to right and top to bottom is an increase in frequency by 1/2 cycle.
For example, moving right one from the top-left square yields a half-cycle increase in the horizontal frequency. Another move to the right yields two half-cycles. A move down yields two half-cycles horizontally and a half-cycle vertically. The source data {{nobr|( 8×8 )}} is transformed to a [[linear combination]] of these 64 frequency squares.
=== MD-DCT-IV ===
The M-D DCT-IV is just an extension of 1-D DCT-IV on to {{mvar|M}} dimensional ___domain. The 2-D DCT-IV of a matrix or an image is given by
:<math> X_{k,\ell} =
\sum_{n=0}^{N-1} \; \sum_{m=0}^{M-1} \ x_{n,m} \cos\left(\ \frac{\,( 2 m + 1 )( 2 k + 1 )\ \pi \,}{4N} \ \right) \cos\left(\ \frac{\, ( 2n + 1 )( 2 \ell + 1 )\ \pi \,}{4M} \ \right) ~,</math>
: for <math>~~ k = 0,\ 1,\ 2\ \ldots\ N-1 ~~</math> and <math>~~ \ell= 0,\ 1,\ 2,\ \ldots\ M-1 ~.</math>
We can compute the MD DCT-IV using the regular row-column method or we can use the polynomial transform method<ref>{{cite book |last=Nussbaumer |first=H.J. |title=Fast Fourier transform and convolution algorithms |publisher=Springer-Verlag |___location=New York |date=1981 |edition=1st }}</ref> for the fast and efficient computation. The main idea of this algorithm is to use the Polynomial Transform to convert the multidimensional DCT into a series of 1-D DCTs directly. MD DCT-IV also has several applications in various fields.
== Computation ==
| |||