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!

I'm impressed that apparently people seem to find TinyEye a good service (good as in a producer of relevant results given a query). I expect the kind of recipe described in the last link to produce many false positives, and it doesn't seem to particularly care about the reasoning behind each step mentioned. Why would you want to intentionally such bad results ? I would drop the mention about image comparison together with the link pointed out, leaving only the question about the correctness of your implementation. Now, to compare your implementation simply check against a known implementation. — mmgp, Jan 01 '13 at 00:50
JPEG uses DCTs to compress the image, if you want to have a look to the source code http://www.ijg.org/ — Déjà vu, Jan 16 '13 at 16:19

score 1 · Accepted Answer · edited Dec 01 '16 at 08:30

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.

I assume `dct1D(array(8, 7, 6, 5, 4, 3, 2, 1))` will have something like `array(12.7279, 6.4423, 0, 0.6735, 0, 0.2009, 0, 0.0507)` but index 1 and upwards are too small. — Roy, Apr 26 '13 at 15:47
I updated the dct 1 function i made un mistake. It's not $in[$k] but $in[$n] and not 2*$n +1 but $n + 0.5 — JEY, Apr 29 '13 at 12:09

score 0 · Answer 2 · answered Jan 17 '13 at 09:20

0

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

answered Jan 17 '13 at 09:20

JEY

6,973
1
36
51

That's the problem. I only know javascript, and php. Do you know of any implementations in those languages? As far as optimization goes I need specific code pointers because I'm not a Mathematics professor. So is table size equivalent to the image size? And resampling the image in this case will change the table size? Also, am I applying my coefficients correctly? – skibulk Jan 17 '13 at 13:28
No you don't apply the coefficients correctly because if $x2 and $y2 are both equal to 0 you have to multiply twice by 1/sqrt(2). Furthermore you start your sum equal to 1. I'll post you a code later – JEY Jan 17 '13 at 16:11

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

2 Answers2