2d DCT program not working

Question

I have to do this 2d DCT of an image for my project. I translated the formula right to code. It all seems fine logically but it doesn't give the required result. I've tallied it with matlab function to check the results for a 3x3 matrix but they are incorrect.

Also, what and how I've coded gives a huge number of loops such that an actual image operation takes hours to compute.

Any suggestion to reduce the loops and pointing of program error would be great. Thanks.

This is my code.

    double alpha_p, alpha_q;
    double pi = Math.atan(1.0) * 4.0;
    //dct begins
    System.out.println("it begins");
    for (int p = 0; p < M; p++) {
        for (int q = 0; q < N; q++) {
            if (p == 0)
                alpha_p = 1 / sqrt(M);
            else
                alpha_p = sqrt(2 / M);
            if (q == 0)
                alpha_q = 1 / sqrt(N);
            else
                alpha_q = sqrt(2 / N);
            double toreturn = 0;
            for (int m = 0; m < M; m++) {
                for (int n = 0; n < N; n++) {
                    toreturn = toreturn + img[m][n]
                            * cos(((2 * m + 1) * p * pi) / 2 * M)
                            * cos(((2 * n + 1) * q * pi) / 2 * N);
                }
            }
            dctimg[p][q] = alpha_p * alpha_q * toreturn;
            System.out.println("euta");
        }
    }
    // dct over
    System.out.println("its over");

    //inverse dct begins
    for (int m = 0; m < M; m++) {
        for (int n = 0; n < N; n++) {
            double toreturn = 0;
            for (int p = 0; p < M; p++) {
                for (int q = 0; q < N; q++) {
                    if (p == 0)
                        alpha_p = 1 / sqrt(M);
                    else
                        alpha_p = sqrt(2 / M);
                    if (q == 0)
                        alpha_q = 1 / sqrt(N);
                    else
                        alpha_q = sqrt(2 / N);
                    toreturn = toreturn + alpha_p * alpha_q * dctimg[p][q]
                                          * cos(((2 * m + 1) * p * pi) / 2 * M)
                                          * cos(((2 * n + 1) * q * pi) / 2 * N);
                }
            }
            finalimg[m][n] = toreturn;
        }
    }
    //inverse dct over

`double pi=Math.atan(1.0) * 4.0` .. or you could use `Math.PI` — harold, Jul 15 '17 at 14:48
see [compute DFCT using DFFT](https://stackoverflow.com/a/22779268/2521214) and [How to compute DFT/DFFT](https://stackoverflow.com/a/26355569/2521214). Make sure you are using compatible DCTs ... If my memory serves well there are 4 of them... — Spektre, Jul 16 '17 at 08:04

score 1 · Accepted Answer · answered Jul 15 '17 at 14:37

1

First of all, in the formula of DCT the denominator of cos is 2 * M. It is a typical mistake. 4 / 2 * 2 = 4 not 1

cos(((2 * m + 1) * p * pi) / 2 * M) should be cos(((2 * m + 1) * p * pi) / (2 * M))

Parentheses are required in all four cases.

Another moment that I want to mention is sqrt(2 / M). If M has an integer type (it is not clear by your code) and it is greater than 2, then the expression 2 / M is equal to 0. Because both operands have integer types and / gives only integer part. To fix it, add a floating point like that sqrt(2.0 / M).

As you have already noticed, there is a lot of loops, in other words, the complexity of the 2D DCT II is O(n^4).

In real life nobody applies DCT to the whole actual image. The image is split into blocks of size 8x8 and each block is processed by DCT. This approach allows to keep n low and the complexity becomes acceptable.

To decrease the algorithmic complexity, I want to link here, where methods of using 1D DCT and FFT are good explained.

answered Jul 15 '17 at 14:37

Enegue

50
1
7

Thank you sir Enege for your well explained reply. I realised the mistakes. I'll try reducing the complexity stuff as well by applying to 8x8 blocks. One good thing is that now I'm getting the original pixel values after successive DCT and IDCT. But, the DCT coefficients are not in a match to that of a matlab test result. I tried a 3x3 matrix for this test. Will have to sort that out. Do you know what block size does matlab use as a standard? – user8311562 Jul 15 '17 at 15:52
@user8311562, I [implemented](https://gist.github.com/Ka6aSH/7594671a4d60aef7a12b0077e002d6a1) from the scratch the DST2 described [here](https://www.mathworks.com/help/images/ref/dct2.html) and tested it on the same input with MathLab online `J = dct2([11 12 13; 14 15 16; 17 18 19]);`. Result is the same, maybe we miss another error. I'm not sure, but I think the function dst2 do not use blocks, it is a pure transformation. Another question is why it is so fast? The answer is that MathLab is highly optimized for matrix operations and it is quite hard to reach such performance. – Enegue Jul 15 '17 at 21:46
Thank you Enegue. All sorted out. – user8311562 Jul 16 '17 at 15:23

2d DCT program not working

1 Answers1