2
$\begingroup$

I've been trying to find a fast 16 point dct2 and dct3 implementation, however I could only find it in literature expressed as mathematical equations, which honestly I couldn't understand.

However I did find a code generator that outputs dft transforms. The main problem I have is the DFT and Inverse DFT don't have the same numbers going in and out.

// Before DFT              // After DFT and IDFT
inputArray[ 0] = 12;       outputArray[ 0] = 184;
inputArray[ 1] = 12;       outputArray[ 1] = 194;   
inputArray[ 2] = 12;       outputArray[ 2] = 178;
inputArray[ 3] = 14;       outputArray[ 3] = 198;
inputArray[ 4] =  8;       outputArray[ 4] = 155;  
inputArray[ 5] = 10;       outputArray[ 5] = 141;
inputArray[ 6] = 12;       outputArray[ 6] = 164;
inputArray[ 7] = 12;       outputArray[ 7] = 149;
inputArray[ 8] = 12;       outputArray[ 8] = 138;
inputArray[ 9] = 12;       outputArray[ 9] = 121; 
inputArray[10] = 12;       outputArray[10] = 107;
inputArray[11] = 12;       outputArray[11] = 90;
inputArray[12] = 12;       outputArray[12] = 74;  
inputArray[13] = 12;       outputArray[13] = 55;
inputArray[14] = 12;       outputArray[14] = 37;
inputArray[15] = 12;       outputArray[15] = 19; 

I realized the first 5 or so indexes do equal the inputs when divided by 16, however this trend doesn't continue as you go down.

Is this the expected behavior? Or is there something else I need to do the get a proper conversion?

Also I did find an 8 point dct that works well and gives the proper results, is there anyway to expand that into a fast 16 point dct?

Edit:

The reason I want to find a fast 16x16 DCT is because I'm working on a javascript video codec that supports transparency.

So after inter frame prediction is finished I'm left with a lot of residue. Because it's in javascript, and it's processing 24 frames a second I need the fastest way possible to compress and decompress this residue.

$\endgroup$
  • $\begingroup$ "IDFT(DFT(input))" doesn't need to be "input"; but it MUST be "input times constant". If that's not the case, your DFT or IDFT is broken. There's nothing to discuss, then, just use an not-broken implementation. $\endgroup$ – Marcus Müller Aug 2 '18 at 17:08
  • $\begingroup$ also, computing a 16-DCT "naively" using the DCT matrix is ... pretty fast on modern computers. For what reasons / applications do you need a faster DCT? $\endgroup$ – Marcus Müller Aug 2 '18 at 17:09
  • $\begingroup$ Thank you for your help! I edited my question to reflect why I need a fast 16x16 dct. I'm not sure what you mean by my must be input "input times constant". Can you explain a little more about that? $\endgroup$ – YAHsaves Aug 2 '18 at 17:20
  • $\begingroup$ The IDFT, is, as the name suggests, the inverse operation to the DFT; but it depends on the specific definition whether IDFT(DFT(input)) == input or input·constant. $\endgroup$ – Marcus Müller Aug 2 '18 at 19:17
  • 1
    $\begingroup$ Are you sure you want to write a video codec in an interpreted language that fully abstracts the memory model away from its data? JavaScript is especially notorious for not having a proper "vector" data type that has constant access time and contiguous memory – you can basically optimize your algorithm as much as you want, but chances are that the most naive implementation in C++ or C or FORTRAN or … would absolutely outperform what you've done, simply because "handling JavaScript to do some math" is so much more work for your computer than the math that you want to do... $\endgroup$ – Marcus Müller Aug 2 '18 at 19:19
3
$\begingroup$

It depends on which DCT (there are more than four of them), the idea is to take your original data and append to it a mirror-reflection copy of that data. Now your data is twice as long, and you perform an FFT on twice the length. but you have some symmetry to it that allows you to toss half of the data in the result of the DFT.

exactly how, depends on if it's DCT I, DCT II, DCT III, DCT IV, or the "MDCT" or whatever is the DCT flavor of the month.

looks like something useful here. it may need further exploration.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So is the fast DCT, that is referred in the literature, actually a DCT computed through DFT / FFT like you described here? Or are there particular, independent, methods to compute DCT flowgraphs faster, like DFT / FFT butterflies? $\endgroup$ – Fat32 Aug 2 '18 at 17:44
  • $\begingroup$ @Fat32 i think they find ways of doing it without explicitly copying and mirroring the data and doing the FFT of size $2N$. the people to ask are the FFTW people. they know everything. $\endgroup$ – robert bristow-johnson Aug 2 '18 at 17:48
  • $\begingroup$ and @Fat32, i think that there is a preprocessing stage and a postprocessing stage, but what goes in between are FFT butterflies. $\endgroup$ – robert bristow-johnson Aug 2 '18 at 17:55
  • 1
    $\begingroup$ hmm an excerpt from FFTW faq: " Question 4.2: Why is FFTW so fast? This is a complex question, and there is no simple answer. In fact, the authors do not fully know the answer, either...." :-)) Anyway yes that could be. In fact I know about Chen's famous 8 x 8, 16 x 16 DCT2 flowgraphs for Image / Video coding, but I don't how he arrives at them ? $\endgroup$ – Fat32 Aug 2 '18 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.