How to calculate Discrete Cosine Transform (DCT) in PHP?

Question

What I'd like here is a working, optimized version of my current code. While my function does return an array with actual results, I don't know if they are correct (I'm not a mathematics guru and I don't know Java code to compare my results against known implementations). Secondly, I'd like the function to be able to accept custom table sizes, but I don't know how to do that. Is table size equivalent to resampling the image? Am I applying the coefficients correctly?

// a lot of processing is required for large images
$image = imagecreatetruecolor(21, 21);
$black = imagecolorallocate($image, 0, 0, 0);
$white = imagecolorallocate($image, 255, 255, 255);
imagefilledellipse($image, 10, 10, 15, 15, $white);

print_r(imgDTC($image));

function imgDTC($img, $tableSize){
    // m1 = Matrix1, an associative array with pixel data from the image
    // m2 = Matrix2, an associative array with DCT Frequencies
    // x1, y1 = coordinates in matrix1
    // x2, y2 = coordinates in matrix2
    $m1 = array();
    $m2 = array();

    // iw = image width
    // ih = image height
    $iw = imagesx($img);
    $ih = imagesy($img);

    // populate matrix1
    for ($x1=0; $x1<$iw; $x1++) {
        for ($y1=0; $y1<$ih; $y1++) {
            $m1[$x1][$y1] = imagecolorat($img, $x1, $y1) & 0xff;
        }
    }

    // populate matrix2
    // for each coordinate in matrix2
    for ($x2=0;$x2<$iw;$x2++) {
        for ($y2=0;$y2<$ih;$y2++) {

        // for each coordinate in matrix1
            $sum = 1;
            for ($x1=0;$x1<$iw;$x1++) {
                for ($y1=0;$y1<$ih;$y1++) {
                    $sum += 
                        cos(((2*$x1+1)/(2*$iw))*$x2*pi()) * 
                        cos(((2*$y1+1)/(2*$ih))*$y2*pi()) * 
                        $m1[$x1][$y1]
                    ;
                }
            }

            // apply coefficients
            $sum *= .25;
            if ($x2 == 0 || $y2 == 0) {
                $sum *= 1/sqrt(2);
            }

            $m2[$x2][$y2] = $sum;
        }
    }
    return $m2;
}

My PHP function is a derivitive from this post in Java: Problems with DCT and IDCT algorithm in java. I have rewritten the code for php and readability. Ultimately, I am working on a script which will enable me to compare images and find similarities. The technique is outlined here: http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html.

Thanks!

Answer 1

This is how I performed my DCT what I'm doing here is to perform a 1 dimension DCT on each row. Then I took the result an perform the DTC on each column it's faster.

function dct1D($in) {
    $results = array();
    $N = count($in);
    for ($k = 0; $k < $N; $k++) {
        $sum = 0;
        for ($n = 0; $n < $N; $n++) {
             $sum += $in[$n] * cos($k * pi() * ($n + 0.5) / ($N));
        }
        $sum *= sqrt(2 / $N);
        if ($k == 0) {
            $sum *= 1 / sqrt(2);
        }
        $results[$k] = $sum;
    }
    return $results;
}

function optimizedImgDTC($img) {
    $results = array();

    $N1 = imagesx($img);
    $N2 = imagesy($img);

    $rows = array();
    $row = array();
    for ($j = 0; $j < $N2; $j++) {
        for ($i = 0; $i < $N1; $i++)
            $row[$i] = imagecolorat($img, $i, $j);
        $rows[$j] = dct1D($row);
    }

    for ($i = 0; $i < $N1; $i++) {
        for ($j = 0; $j < $N2; $j++)
            $col[$j] = $rows[$j][$i];
        $results[$i] = dct1D($col);
    }
    return $results;
}

Most algorithm I found on internet assume that the input matrix is 8x8. That's why you multiplyed by 0.25. In general you should multiply by sqrt(2 / N) a 1D matrix and here we are in 2D so sqrt(2/N1) * sqrt(2/N2). If you do this for N1 = 8 and N2 = 8: sqrt(2/8)^2 = 2/8 = 1/4 = 0.25

The other thing was to multiply by 1/sqrt(2) X0 it's for 1D matrix here we are in 2D so you multiply when k1 = 0 or k2 = 0. When k1 = 0 and k2 = 0 you have to do it twice.

Answer 2

First you need to test your function so find any working implementation. And compare results from your implementation with the results of the working implementation (with the same input).

If you whant your code to be faster you can look at this paper http://infoscience.epfl.ch/record/34246/files/Vetterli85.pdf (the first 2 parts).

In your case you can't use a custom table size because it should match the image size (can be wrong).