skibulk - 1 year ago 109
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!

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download