Problems with DCT and IDCT algorithm in java

Question

Here I have my DCT algorithm class with "applyDCT" and "applyIDCT" methods. Technically after doing a forward DCT (discrete cosine transform) on a 2x2 table of random integers between 0 and 255, and then immediately doing a reverse DCT on these numbers, we should come back to the original integer numbers we had in the first place. In my case, this is not so. What am I doing wrong here?

public class DCT {
    private static final int N = 2;
    private double[] c = new double[N];

    public DCT() {
          this.initializeCoefficients();
    }

    private void initializeCoefficients() {
        for (int i=1;i<N;i++) {
            c[i]=1;
        }
        c[0]=1/Math.sqrt(2.0);
    }

    public double[][] applyDCT(double[][] f) {
        double[][] F = new double[N][N];
        for (int u=0;u<N;u++) {
          for (int v=0;v<N;v++) {
            double sum = 0.0;
            for (int i=0;i<N;i++) {
              for (int j=0;j<N;j++) {
                sum+=Math.cos(((2*i+1)/(2.0*N))*u*Math.PI)*Math.cos(((2*j+1)/(2.0*N))*v*Math.PI)*f[i][j];
              }
            }
            sum*=((c[u]*c[v])/4.0);
            F[u][v]=sum;
          }
        }
        return F;
    }

    public double[][] applyIDCT(double[][] F) {
        double[][] f = new double[N][N];
        for (int u=0;u<N;u++) {
          for (int v=0;v<N;v++) {
            double sum = 0.0;
            for (int i=0;i<N;i++) {
              for (int j=0;j<N;j++) {
                sum+=((c[u]*c[v]))*Math.cos(((2*i+1)/(2.0*N))*u*Math.PI)*Math.cos(((2*j+1)/(2.0*N))*v*Math.PI)*F[i][j];
              }
            }
            sum/=4.0;
            //sum*=((c[u]*c[v])/4.0);
            f[u][v]=sum;
          }
        }
        return f;
    }
}

And here is the main class that goes with it:

public class Main {
    private static final int N = 2;
    private static double[][] f = new double[N][N];
    private static Random generator = new Random();

    public static void main(String[] args) {
        // Generate random integers between 0 and 255
        int value;
        for (int x=0;x<N;x++) {
            for (int y=0;y<N;y++) {
              value = generator.nextInt(255);
              f[x][y] = value;
              System.out.println(f[x][y]+" => f["+x+"]["+y+"]");
            }
        }

        DCT dctApplied = new DCT();
        double[][] F = dctApplied.applyDCT(f);
        System.out.println("From f to F");
        System.out.println("-----------");
        for (int x=0;x<N;x++) {
            for (int y=0;y<N;y++) {
             try {
                 System.out.println(F[x][y]+" => F["+x+"]["+y+"]");
                 } catch (Exception e) {
                    System.out.println(e);
                 }
            }
        }

        double f[][] = dctApplied.applyIDCT(F);
        System.out.println("Back to f");
        System.out.println("---------");
        for (int y=0;y<N;y++) {
            for (int z=0;z<N;z++) {
              System.out.println(f[y][z]+" => f["+y+"]["+z+"]");
            }
        }
    }
}

Here are example of results:

149.0 => f[0][0]
237.0 => f[0][1]
122.0 => f[1][0]
147.0 => f[1][1] 

From f to F
-----------
81.87499999999999 => F[0][0]
-14.124999999999993 => F[0][1]
14.62500000000001 => F[1][0]
-7.875 => F[1][1] 

Back to f
---------
9.3125 => f[0][0]
14.812499999999998 => f[0][1]
7.624999999999999 => f[1][0]
9.187499999999998 => f[1][1]

As shown above, "Back to f" does not show the same values contained in f initially...

What was the input case, what was the expected result, and what the actual result? Did you try running each of your routines on trivial input cases (e.g. [1 0; 0 0]) to find out which one was incorrect? — Oliver Charlesworth, Nov 21 '10 at 21:35
What results do you get when you say you don't get your original integers back? Some floating point rounding errors can be introduced. — rsp, Nov 21 '10 at 21:35
DCT itself is lossy. You need modified DCT (lossless DCT) to get lossless (reversible) operation. — osgx, Nov 21 '10 at 21:52
@osgx: The DCT is not lossy (unless you're talking about rounding errors). — Oliver Charlesworth, Nov 21 '10 at 21:58
@Oli Charlesworth, DCT is considered lossy in real application (jpeg, video). there is always a information loss in sin, cos functions, written(stored) in some finite format, isnt it? — osgx, Nov 21 '10 at 23:23
@osgx: Then you may as well as call the DFT "lossy"! The MDCT is no less "lossy"; it just has slightly different basis functions. There are DCT variants with integer coefficients that can be used in certain situations (H.264 springs to mind), but they have different mathematical characteristics, which may not be suitable for the OP. — Oliver Charlesworth, Nov 21 '10 at 23:28
@osgx, I don't think that DCT is lossy. By applying DCT once you're supposed to obtain the "transform", and applying the inverse DCT, you would obtain the original values. If you are refering to the jpeg applications, the "lossy" part of this is the quantification and should not come from the DCT. — Jean-François Beaulieu, Nov 22 '10 at 02:15

Jean-François Beaulieu · Accepted Answer · 2010-11-22T17:03:33.887

I have resolved this problem, I am sorry if my question was unclear but here is what was not right: The IDCT method had to have the coefficient inside the i and j for loops :

public double[][] applyIDCT(double[][] F) {
        double[][] f = new double[N][N];
        for (int i=0;i<N;i++) {
          for (int j=0;j<N;j++) {
            double sum = 0.0;
            for (int u=0;u<N;u++) {
              for (int v=0;v<N;v++) {
                sum+=(c[u]*c[v])/4.0*Math.cos(((2*i+1)/(2.0*N))*u*Math.PI)*Math.cos(((2*j+1)/(2.0*N))*v*Math.PI)*F[u][v];
              }
            }
            f[i][j]=Math.round(sum);
          }
        }
        return f;
    }

This only works for a 8x8 bloc of data, or else you would have to change this:

(c[u]*c[v])/4.0)

into something like this:

(2*c[u]*c[v])/Math.sqrt(M*N)

Where M and N are the dimentions of the table...

Here are the results with a 2x2 block of data:

Original values
---------------
54.0 => f[0][0]
35.0 => f[0][1]
128.0 => f[1][0]
185.0 => f[1][1]

From f to F
-----------
200.99999999999994 => F[0][0]
-18.99999999999997 => F[0][1]
-111.99999999999997 => F[1][0]
37.99999999999999 => F[1][1]

Back to f
---------
54.0 => f[0][0]
35.0 => f[0][1]
128.0 => f[1][0]
185.0 => f[1][1]

Problems with DCT and IDCT algorithm in java

1 Answers1

Linked