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
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.