skibulk skibulk - 8 days ago 6
PHP Question

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

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!

JEY JEY
Answer

This is how i performed my DCT what i'm doing here is to perform a 1 dimention 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.