Discrete Cosine Transform DCT implementation C
Im trying to implement a forward and inverse Discrete Cosine Transform (DCT) in C. The code is to transorm a single input block of pixels to the transformation matrix via the dct() function and then back to the original pixel values via the idct() function. Please see the attached code. My output form the idct are consecutive values of 244, 116, 244, 116 etc. From the look of the idct values, it doesnt look like my program is working.. Could someone help me out and give me an idea of what results i should be expecting after each function? Obviously after the idct, i should be getting prety close to the original input Matrix.
Thanks
# include <stdio.h>
# define PI 3.14
void dct(float [][]); // Function prototypes
void idct(float [][]); // Function prototypes
void dct(float inMatrix[8][8]){
double dct,
Cu,
sum,
Cv;
int i,
j,
u,
h = 0,
v;
FILE * fp = fopen("mydata.csv", "w");
float dctMatrix[8][8],
greyLevel;
for (u = 0; u < 8; ++u) {
for (v = 0; v < 8; ++v) {
if (u == 0) {
Cu = 1.0 / sqrt(2.0);
} else {
Cu = 1.0;
}
if (v == 0) {
Cv = 1.0 / sqrt(2.0);
} else {
Cu = (1.0);
}
sum = 0.0;
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
// Level around 0
greyLevel = inMatrix[i][j];
dct = greyLevel * cos((2 * i + 1) * u * PI / 16.0) *
cos((2 * j + 1) * v * PI / 16.0);
sum += dct;
}
}
dctMatrix[u][v] = 0.25 * Cu * Cv * sum;
fprintf(fp, "\n %f", dctMatrix[u][v]);
}
fprintf(fp, "\n");
}
idct(dctMatrix);
}
void idct(float dctMatrix[8][8]){
double idct,
Cu,
sum,
Cv;
int i,
j,
u,
v;
float idctMatrix[8][8],
greyLevel;
FILE * fp = fopen("mydata.csv", "a");
fprintf(fp, "\n Inverse DCT");
for (i = 0; i < 8; ++i) {
for (j = 0; j < 8; ++j) {
sum = 0.0;
for (u = 0; u < 8; u++) {
for (v = 0; v < 8; v++) {
if (u == 0) {
Cu = 1.0 / sqrt(2.0);
} else {
Cu = 1.0;
}
if (v == 0) {
Cv = 1.0 / sqrt(2.0);
} else {
Cu = (1.0);
}
// Level around 0
greyLevel = dctMatrix[u][v];
idct = (greyLevel * cos((2 * i + 1) * u * PI / 16.0) *
cos((2 * j + 1) * v * PI / 16.0));
sum += idct;
}
}
idctMatrix[i][j] = 0.25 * Cu * Cv * sum;
fprintf(fp, "\n %f", idctMatrix[i][j]);
}
fprintf(fp, "\n");
}
}
int main() {
float
testBlockA[8][8] = { {255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255} },
testBlockB[8][8] = {{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255} };
dct(testBlockB);
}
Answer
There are at least two typos in the Cv constant assignment at the if statements:
if (v == 0) {
Cv = 1.0 / sqrt(2.0);
} else {
Cu = (1.0); // << this should be Cv = 1.0
}
Didn't check too properly though. Using the german wikipedia about cosine transform, following code works... I didn't want to spent time on figuring out how you defined what conversion constant. I guess you need to make sure that you use the correct constants and inverse functions:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
void dct(float **DCTMatrix, float **Matrix, int N, int M);
void write_mat(FILE *fp, float **testRes, int N, int M);
void idct(float **Matrix, float **DCTMatrix, int N, int M);
float **calloc_mat(int dimX, int dimY);
void free_mat(float **p);
float **calloc_mat(int dimX, int dimY){
float **m = calloc(dimX, sizeof(float*));
float *p = calloc(dimX*dimY, sizeof(float));
int i;
for(i=0; i <dimX;i++){
m[i] = &p[i*dimY];
}
return m;
}
void free_mat(float **m){
free(m[0]);
free(m);
}
void write_mat(FILE *fp, float **m, int N, int M){
int i, j;
for(i =0; i< N; i++){
fprintf(fp, "%f", m[i][0]);
for(j = 1; j < M; j++){
fprintf(fp, "\t%f", m[i][j]);
}
fprintf(fp, "\n");
}
fprintf(fp, "\n");
}
void dct(float **DCTMatrix, float **Matrix, int N, int M){
int i, j, u, v;
for (u = 0; u < N; ++u) {
for (v = 0; v < M; ++v) {
DCTMatrix[u][v] = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
DCTMatrix[u][v] += Matrix[i][j] * cos(M_PI/((float)N)*(i+1./2.)*u)*cos(M_PI/((float)M)*(j+1./2.)*v);
}
}
}
}
}
void idct(float **Matrix, float **DCTMatrix, int N, int M){
int i, j, u, v;
for (u = 0; u < N; ++u) {
for (v = 0; v < M; ++v) {
Matrix[u][v] = 1/4.*DCTMatrix[0][0];
for(i = 1; i < N; i++){
Matrix[u][v] += 1/2.*DCTMatrix[i][0];
}
for(j = 1; j < M; j++){
Matrix[u][v] += 1/2.*DCTMatrix[0][j];
}
for (i = 1; i < N; i++) {
for (j = 1; j < M; j++) {
Matrix[u][v] += DCTMatrix[i][j] * cos(M_PI/((float)N)*(u+1./2.)*i)*cos(M_PI/((float)M)*(v+1./2.)*j);
}
}
Matrix[u][v] *= 2./((float)N)*2./((float)M);
}
}
}
int main() {
float
testBlockA[8][8] = { {255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255} },
testBlockB[8][8] = {{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255},
{255, 0, 255, 0, 255, 0, 255, 0},
{0, 255, 0, 255, 0, 255, 0, 255} };
FILE * fp = fopen("mydata.csv", "w");
int dimX = 8, dimY = 8;
int i, j;
float **testBlock = calloc_mat(dimX, dimY);
float **testDCT = calloc_mat(dimX, dimY);
float **testiDCT = calloc_mat(dimX, dimY);
for(i = 0; i<dimX; i++){
for(j = 0; j<dimY; j++){
testBlock[i][j] = testBlockB[i][j];
}
}
dct(testDCT, testBlock, dimX, dimY);
write_mat(fp, testDCT, dimX, dimY);
idct(testiDCT, testDCT, dimX, dimY);
write_mat(fp, testiDCT, dimX, dimY);
fclose(fp);
free_mat(testBlock);
free_mat(testDCT);
free_mat(testiDCT);
return 0;
}
Edit the dct is based on the crossproduct of formula DCT-II in the wiki. the idct is based on the crossproduct of formula DCT-III with the normalization factor 2/N per dimension (since this is the inverse to DCT-II as mentioned in the text). Edit I am pretty sure that the factor in the inverse dct should sqrt(2) and not 1/sqrt(2) in your version.