Я только что закончил тратить ~ 4 часа на отладку проблемы, возникшей у меня с более крупной программой, и даже после ее устранения я все еще не могу понять, почему она вызывает проблему.
РЕДАКТИРОВАТЬ:
ОСНОВНЫЕ РАЗЛИЧИЯ между двумя версиями.
Версия 1 (неверно):
for (int u=0;u<8;u++){
for (int v=0;v<8;v++){
temp += input_data[u][v] * fcosine[x/8][u] * fcosine[x%8][v];
if (!u){
temp /= (double) sqrt(2);
}
if (!v){
temp /= (double) sqrt(2);
}
}
}
//Produces wrong result
out[x/8][x%8] = temp/4;
ПРАВИЛЬНЫЙ ВЫХОД:
for (int u=0;u<8;u++){
for (int v=0;v<8;v++){
temp = input[u][v] * fcosine[x/8][u] * fcosine[x%8][v];
if (!u){
temp /= (double) sqrt(2);
}
if (!v){
temp /= (double) sqrt(2);
}
sum +=temp;
}
}
out[x/8][x%8] = (sum/4);
Вот мини-версия кода:
#include <cstdlib>
#include<iostream>
#include <math.h>
#define PI 3.1415926535897932384626433832795 // the value of PI
void calculate_idct(double input_data[8][8], double out[8][8], double fcosine[8][8]){
double temp;
for (int x=0;x<=64;x++){
temp = 0.0;
for (int u=0;u<8;u++){
for (int v=0;v<8;v++){
temp += input_data[u][v] * fcosine[x/8][u] * fcosine[x%8][v];
if (!u){
temp /= (double) sqrt(2);
}
if (!v){
temp /= (double) sqrt(2);
}
}
}
//Produces wrong result
out[x/8][x%8] = temp/4;
}
}
void calculate_idct2(double input[8][8], double out[8][8], double fcosine[8][8]){
double temp, sum;
for (int x =0;x<=64;x++){
sum = 0;
for (int u=0;u<8;u++){
for (int v=0;v<8;v++){
temp = input[u][v] * fcosine[x/8][u] * fcosine[x%8][v];
if (!u){
temp /= (double) sqrt(2);
}
if (!v){
temp /= (double) sqrt(2);
}
sum +=temp;
}
}
out[x/8][x%8] = (sum/4);
}
}
void calculate_dct(double input_data[8][8], double out64[8][8], double fcosine[8][8]) {
unsigned char u, v, x, y;
double temp;
// do forward discrete cosine transform
for (u = 0; u < 8; u++)
for (v = 0; v < 8; v++) {
temp = 0.0;
for (x = 0; x < 8; x++)
for (y = 0; y < 8; y++)
temp += input_data[x][y] * fcosine[x][u] * fcosine[y][v];
if ((u == 0) && (v == 0))
temp /= 8.0;
else if (((u == 0) && (v != 0)) || ((u != 0) && (v == 0)))
temp /= (4.0*sqrt(2.0));
else
temp /= 4.0;
out64[u][v] = temp;
}
}void make_cosine_tbl(double cosine[8][8]) {
// calculate the cosine table as defined in the formula
for (unsigned char i = 0; i < 8; i++)
for (unsigned char j = 0; j < 8; j++)
cosine[i][j] = cos((((2*i)+1)*j*PI)/16);
}
using namespace std;
int main(int argc, char** argv) {
double cosine[8][8];
make_cosine_tbl(cosine);
double input_data[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} };
double out64[8][8];
calculate_dct(input_data, out64, cosine);
double out5[8][8];
cout << "Input" << endl;
for (int i = 0;i<8;i++){
for (int j=0;j<8;j++){
cout << input_data[i][j] << " ";
}
cout << endl;
}
cout << "\n Version 1 \n " << endl;
calculate_idct(out64,out5,cosine);
for (int i = 0;i<8;i++){
for (int j=0;j<8;j++){
cout << out5[i][j] << " ";
}
cout << endl;
}cout << "\n Version 2 \n " << endl;
calculate_idct2(out64,out5,cosine);
for (int i = 0;i<8;i++){
for (int j=0;j<8;j++){
cout << out5[i][j] << " ";
}
cout << endl;
}}
Вот вывод:
Version 1
60.7617 -58.7695 60.7617 -58.7695 60.7617 -58.7695 60.7617 -58.7695
-116.404 118.396 -116.404 118.396 -116.404 118.396 -116.404 118.396
135.3 -133.308 135.3 -133.308 135.3 -133.308 135.3 -133.308
-139.93 141.922 -139.93 141.922 -139.93 141.922 -139.93 141.922
141.922 -139.93 141.922 -139.93 141.922 -139.93 141.922 -139.93
-133.308 135.3 -133.308 135.3 -133.308 135.3 -133.308 135.3
118.396 -116.404 118.396 -116.404 118.396 -116.404 118.396 -116.404
-58.7695 60.7617 -58.7695 60.7617 -58.7695 60.7617 -58.7695 60.7617
Version 2
255 -1.42109e-14 255 -7.10543e-15 255 2.13163e-14 255 -7.10543e-14
3.55271e-15 255 -1.13687e-13 255 -9.9476e-14 255 1.7053e-13 255
255 -5.68434e-14 255 0 255 -2.84217e-14 255 -1.91847e-13
6.39488e-14 255 0 255 -5.68434e-14 255 1.56319e-13 255
255 -5.68434e-14 255 -5.68434e-14 255 -2.84217e-14 255 -1.27898e-13
7.10543e-15 255 0 255 0 255 2.13163e-13 255
255 2.98428e-13 255 2.55795e-13 255 2.13163e-13 255 1.52767e-13
3.55271e-15 255 -4.9738e-14 255 -2.84217e-14 255 1.74083e-13 255
Версия 2 верна, но Версия 1 далеко не верна.
Я запустил программу, но мне любопытно, почему была такая большая разница.
temp = input[u][v] * fcosine[x][u] * fcosine[y][v]; //I don't get it at all, but making the above line a // += gives the wrong result
Упрощенная:
temp = 0;
for (i = 1; i < 3; i++) {
temp = 1;
}
// temp is 1
temp = 0;
for (i = 1; i < 3; i++) {
temp += 1;
}
// temp is 2
Почему вы ожидаете, что код будет работать так же с +
а также +=
?
Кроме того, вы (должны быть) подводят итоги temp
затем разделить его перед добавлением в sum
; но если вы не опустошите temp
между ними ваше деление применяется несколько раз к ранее x
а также y
Результаты:
100 / 4 + 100 / 4
отличается от
(100 / 4 + 100) / 4
Других решений пока нет …