Более быстрый алгоритм AAN для вычисления дискретного косинусного преобразования

От: Из: Общие

Я реализовал алгоритм AAN для вычисления двумерного дискретного косинусного преобразования на массиве 8 * 8. Я использую как прямой, так и обратный алгоритм AAN.

Мой код чрезвычайно быстр по сравнению с наивным алгоритмом DCT, но я чувствую, что моя реализация могла бы быть быстрее. Как я могу улучшить производительность моих преобразований?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#ifndef M_PI
#    define M_PI 3.14159265358979323846
#endif
/*
File: dct.c
Summary: 2D AAN implementation of Discrete Cosine transform
     Code for Forward and Inverse DCT using AAN method
Sources: Forward DCT inspired by // https://unix4lyfe.org/dct-1d/
     Inverse DCT inspired by (Everything you need to know about jpeg Youtube Playlist) https://www.youtube.com/watch?v=sb8CQ9knDgI&list=PLpsTn9TA_Q8VMDyOPrDKmSJYt1DLgDZU4

Input : float array of 64 elements representing 8 * 8 block
*Note I use a 1-dimensional array to represent 2d data   
*/


//Compute forward dct
void ForwardDCTComponent(float *component)
{
/*Forward DCT constants*/
const float a1 = 0.707;
const float a2 = 0.541;
const float a3 = 0.707;
const float a4 = 1.307;
const float a5 = 0.383;

const float s0 = 0.353553;
const float s1 = 0.254898;
const float s2 = 0.270598;
const float s3 = 0.300672;
const float s4 = s0;
const float s5 = 0.449988;
const float s6 = 0.653281;
const float s7 = 1.281458;
/*Forward DCT constants*/


    for(int i = 0; i < 8; i++)
    {
        const float b0 = component[0*8 + i] + component[7*8 + i];
        const float b1 = component[1*8 + i] + component[6*8 + i];
        const float b2 = component[2*8 + i] + component[5*8 + i];
        const float b3 = component[3*8 + i] + component[4*8 + i];
        const float b4 =-component[4*8 + i] + component[3*8 + i];
        const float b5 =-component[5*8 + i] + component[2*8 + i];
        const float b6 =-component[6*8 + i] + component[1*8 + i];
        const float b7 =-component[7*8 + i] + component[0*8 + i];
        
        const float c0 = b0 + b3;
        const float c1 = b1 + b2;
        const float c2 =-b2 + b1;
        const float c3 =-b3 + b0;
        const float c4 =-b4 - b5;
        const float c5 = b5 + b6;
        const float c6 = b6 + b7;
        const float c7 = b7;
        
        const float d0 = c0 + c1;
        const float d1 =-c1 + c0;
        const float d2 = c2 + c3;
        const float d3 = c3;
        const float d4 = c4;
        const float d5 = c5;
        const float d6 = c6;
        const float d7 = c7;
        const float d8 = (d4+d6) * a5;
        
        const float e0 = d0;
        const float e1 = d1;
        const float e2 = d2 * a1;
        const float e3 = d3;
        const float e4 = -d4 * a2 - d8;
        const float e5 = d5 * a3;
        const float e6 = d6 * a4 - d8;
        const float e7 = d7;
        
        const float f0 = e0;
        const float f1 = e1;
        const float f2 = e2 + e3;
        const float f3 = e3 - e2;
        const float f4 = e4;
        const float f5 = e5 + e7;
        const float f6 = e6;
        const float f7 = e7 - e5;
        
        const float g0 = f0;
        const float g1 = f1;
        const float g2 = f2;
        const float g3 = f3;
        const float g4 = f4 + f7;
        const float g5 = f5 + f6;
        const float g6 = -f6 + f5;
        const float g7 = f7 - f4;   
        
        component[0*8 + i] = g0 * s0;
        component[4*8 + i] = g1 * s4;
        component[2*8 + i] = g2 * s2;
        component[6*8 + i] = g3 * s6;
        component[5*8 + i] = g4 * s5;
        component[1*8 + i] = g5 * s1;
        component[7*8 + i] = g6 * s7;
        component[3*8 + i] = g7 * s3;       
    }
    for(int i = 0; i < 8; i++)
    {
        const float b0 = component[i*8 + 0]  + component[i*8 + 7];
        const float b1 = component[i*8 + 1]  + component[i*8 + 6];
        const float b2 = component[i*8 + 2]  + component[i*8 + 5];
        const float b3 = component[i*8 + 3]  + component[i*8 + 4];
        const float b4 =-component[i*8 + 4]  + component[i*8 + 3];
        const float b5 =-component[i*8 + 5]  + component[i*8 + 2];
        const float b6 =-component[i*8 + 6]  + component[i*8 + 1];
        const float b7 =-component[i*8 + 7]  + component[i*8 + 0] ;
        
        const float c0 = b0 + b3;
        const float c1 = b1 + b2;
        const float c2 =-b2 + b1;
        const float c3 =-b3 + b0;
        const float c4 =-b4 - b5;
        const float c5 = b5 + b6;
        const float c6 = b6 + b7;
        const float c7 = b7;
        
        const float d0 = c0 + c1;
        const float d1 =-c1 + c0;
        const float d2 = c2 + c3;
        const float d3 = c3;
        const float d4 = c4;
        const float d5 = c5;
        const float d6 = c6;
        const float d7 = c7;
        const float d8 = (d4+d6) * a5;
        
        const float e0 = d0;
        const float e1 = d1;
        const float e2 = d2 * a1;
        const float e3 = d3;
        const float e4 = -d4 * a2 - d8;
        const float e5 = d5 * a3;
        const float e6 = d6 * a4 - d8;
        const float e7 = d7;
        
        const float f0 = e0;
        const float f1 = e1;
        const float f2 = e2 + e3;
        const float f3 = e3 - e2;
        const float f4 = e4;
        const float f5 = e5 + e7;
        const float f6 = e6;
        const float f7 = e7 - e5;
        
        const float g0 = f0;
        const float g1 = f1;
        const float g2 = f2;
        const float g3 = f3;
        const float g4 = f4 + f7;
        const float g5 = f5 + f6;
        const float g6 = -f6 + f5;
        const float g7 = f7 - f4;   
        
        component[i*8 + 0] = g0 * s0;
        component[i*8 + 4] = g1 * s4;
        component[i*8 + 2] = g2 * s2;
        component[i*8 + 6] = g3 * s6;
        component[i*8 + 5] = g4 * s5;
        component[i*8 + 1] = g5 * s1;
        component[i*8 + 7] = g6 * s7;
        component[i*8 + 3] = g7 * s3;   
    }
}

void InverseDCTComponent(float *component)
{
const float m0 = 2.0 * cos(1.0/16.0 * 2.0 * M_PI);
const float m1 = 2.0 * cos(2.0/16.0 * 2.0 * M_PI);
const float m3 = 2.0 * cos(2.0/16.0 * 2.0 * M_PI);
const float m5 = 2.0 * cos(3.0/16.0 * 2.0 * M_PI);
const float m2 = m0-m5;
const float m4 = m0+m5;

const float s0 = cos(0.0/16.0 *M_PI)/sqrt(8);
const float s1 = cos(1.0/16.0 *M_PI)/2.0;
const float s2 = cos(2.0/16.0 *M_PI)/2.0;
const float s3 = cos(3.0/16.0 *M_PI)/2.0;
const float s4 = cos(4.0/16.0 *M_PI)/2.0;
const float s5 = cos(5.0/16.0 *M_PI)/2.0;
const float s6 = cos(6.0/16.0 *M_PI)/2.0;
const float s7 = cos(7.0/16.0 *M_PI)/2.0;

    for(int i = 0; i < 8; i++)
    {
        const float g0 = component[0*8 + i] * s0;
        const float g1 = component[4*8 + i] * s4;
        const float g2 = component[2*8 + i] * s2;
        const float g3 = component[6*8 + i] * s6;
        const float g4 = component[5*8 + i] * s5;
        const float g5 = component[1*8 + i] * s1;
        const float g6 = component[7*8 + i] * s7;
        const float g7 = component[3*8 + i] * s3;
        
        const float f0 = g0;
        const float f1 = g1;
        const float f2 = g2;
        const float f3 = g3;
        const float f4 = g4 - g7;
        const float f5 = g5 + g6;
        const float f6 = g5 - g6;
        const float f7 = g4 + g7;
        
        const float e0 = f0;
        const float e1 = f1;
        const float e2 = f2 - f3;
        const float e3 = f2 + f3;
        const float e4 = f4;
        const float e5 = f5 - f7;
        const float e6 = f6;
        const float e7 = f5 + f7;
        const float e8 = f4 + f6;
        
        const float d0 = e0;
        const float d1 = e1;
        const float d2 = e2 * m1;
        const float d3 = e3;
        const float d4 = e4 * m2;
        const float d5 = e5 * m3;
        const float d6 = e6 * m4;
        const float d7 = e7;
        const float d8 = e8 * m5;
        
        const float c0 = d0 + d1;
        const float c1 = d0 - d1;
        const float c2 = d2 - d3;
        const float c3 = d3;
        const float c4 = d4 + d8;
        const float c5 = d5 + d7;
        const float c6 = d6 - d8;
        const float c7 = d7;
        const float c8 = c5 - c6;
        
        const float b0 = c0 + c3;
        const float b1 = c1 + c2;
        const float b2 = c1 - c2;
        const float b3 = c0 - c3;
        const float b4 = c4 - c8;
        const float b5 = c8;
        const float b6 = c6 - c7;
        const float b7 = c7;
        
        component[0 * 8 + i] = b0 + b7;
        component[1 * 8 + i] = b1 + b6;
        component[2 * 8 + i] = b2 + b5;
        component[3 * 8 + i] = b3 + b4;
        component[4 * 8 + i] = b3 - b4;
        component[5 * 8 + i] = b2 - b5;
        component[6 * 8 + i] = b1 - b6;
        component[7 * 8 + i] = b0 - b7; 
    }
    
    for(int i = 0 ; i < 8; i++)
    {
        const float g0 = component[i*8 + 0] * s0;
        const float g1 = component[i*8 + 4] * s4;
        const float g2 = component[i*8 + 2] * s2;
        const float g3 = component[i*8 + 6] * s6;
        const float g4 = component[i*8 + 5] * s5;
        const float g5 = component[i*8 + 1] * s1;
        const float g6 = component[i*8 + 7] * s7;
        const float g7 = component[i*8 + 3] * s3;
        
        const float f0 = g0;
        const float f1 = g1;
        const float f2 = g2;
        const float f3 = g3;
        const float f4 = g4 - g7;
        const float f5 = g5 + g6;
        const float f6 = g5 - g6;
        const float f7 = g4 + g7;
        
        const float e0 = f0;
        const float e1 = f1;
        const float e2 = f2 - f3;
        const float e3 = f2 + f3;
        const float e4 = f4;
        const float e5 = f5 - f7;
        const float e6 = f6;
        const float e7 = f5 + f7;
        const float e8 = f4 + f6;
        
        const float d0 = e0;
        const float d1 = e1;
        const float d2 = e2 * m1;
        const float d3 = e3;
        const float d4 = e4 * m2;
        const float d5 = e5 * m3;
        const float d6 = e6 * m4;
        const float d7 = e7;
        const float d8 = e8 * m5;
        
        const float c0 = d0 + d1;
        const float c1 = d0 - d1;
        const float c2 = d2 - d3;
        const float c3 = d3;
        const float c4 = d4 + d8;
        const float c5 = d5 + d7;
        const float c6 = d6 - d8;
        const float c7 = d7;
        const float c8 = c5 - c6;
        
        const float b0 = c0 + c3;
        const float b1 = c1 + c2;
        const float b2 = c1 - c2;
        const float b3 = c0 - c3;
        const float b4 = c4 - c8;
        const float b5 = c8;
        const float b6 = c6 - c7;
        const float b7 = c7;
        
        component[i * 8 + 0] = b0 + b7;
        component[i * 8 + 1] = b1 + b6;
        component[i * 8 + 2] = b2 + b5;
        component[i * 8 + 3] = b3 + b4;
        component[i * 8 + 4] = b3 - b4;
        component[i * 8 + 5] = b2 - b5;
        component[i * 8 + 6] = b1 - b6;
        component[i * 8 + 7] = b0 - b7;
    }
}

void Print(float *array, int length)
{
    for(int i = 0; i < 64; i++)
    {
        if(i > 0 && i % 8 == 0)
        {
            putchar('n');
        }
        printf("%.1f ", array[i]);  
    }
    putchar('n');
}




int main()
{
    //Create Sample Array 
    float *component = malloc(64 * sizeof(int));
    for(int i = 0; i < 64; i++)
    {
        component[i] = 255;
    }
    //Print Sample Array
    Print(component,64);
    
    //Perform forward DCT
    ForwardDCTComponent(component);
    putchar('n');
    //Print results of forward dct
    Print(component,64);
    
    //Perform inverse DCT
    InverseDCTComponent(component);
    putchar('n');
    //Print results of inverse dct
    Print(component,64);
    free(component);
    
    
    return 0;
}

1 ответ
1

Представление

Как я могу улучшить производительность моих преобразований?

Пока только небольшие идеи.

float против. double математика

Не вызывайте время выполнения double функции и константы для float математика. Много времени можно потратить на преобразование вверх и вниз.

// const float s1 = cos(1.0/16.0 * M_PI)/2.0;
define M_PIf 3.14159265f
const float s1 = cosf(1.0f/16.0f * M_PIf)/2.0f;

С другой стороны, еще лучше предварительно рассчитать с высокой точностью, а потом …

Использовать константы

Некоторые компиляторы будут формировать значения констант времени компиляции, используя уравнения констант с хорошо известными функциями во время компиляции, другие вычисляют во время выполнения. Простое кодирование значения — самое быстрое. Некоторые вопросы касаются количества цифр в коде. Я рекомендую как минимум 9 для float и ОК, если есть еще много чего. Педантический код будет использовать 17+ в случае, если float имеет ту же точность, что и double. Ваш звонок.

// const float s0 = cos(0.0/16.0 *M_PI)/sqrt(8);
const float s0 = 0.353553391f // cos(0.0/16.0 *M_PI)/sqrt(8);

static

В зависимости от компилятора const объект может быть повторно загружен в функции.

static обязательно предотвратит это.

// const float s0 = 0.353553391f // cos(0.0/16.0 *M_PI)/sqrt(8);
static const float s0 = 0.353553391f // cos(0.0/16.0 *M_PI)/sqrt(8);

Микрооптимизация

Может сэкономить галочку или два

 //for(int i = 0 ; i < 8; i++)
 //  ...  i*8 ...
 //  ...  i*8 ...
 for(int i = 0 ; i < 64; i+=8)
   ...  i ...
   ...  i ...

Экономьте время на кодирование

Это экономия вашего драгоценного времени на кодирование.

void Print(float *array, int length) не использует length. С хорошо включенным компилятором это вызвало бы предупреждение. Тем не менее, поскольку он есть, это означает, что все предупреждения не были включены.

Сэкономьте время, включите все предупреждения, которые помогут вам улучшить код.

Правильность

Кодирование float против. double константы

// const float s0 = 0.353553;
const float s0 = 0.353553f;

Видеть Когда добавление ‘f’ изменяет значение плавающей константы при присвоении ей float?

Подозрительные ценности

Для a1, a2, ..., почему константы только 3 значащие цифры? Возможно float a1 = 0.707106781f; лучше?

Оценка

Чтобы судить о правильности float, избегать использования "%.1f" поскольку это занимает плавающий вне числа с плавающей запятой. Wee ценности все 0.0 а большие значения содержат чрезмерное количество цифр.

// printf("%.1f ", array[i]);
printf("%.*g ", FLT_DECIMAL_DIG, array[i]);

Скрытая ошибка

float и int не указано, что они имеют одинаковый размер.

Избегайте ошибок в размере. Размер по отношению к объекту, на который указывает ссылка, а не по типу. Легче правильно кодировать, проверять и поддерживать.

// float *component = malloc(64 * sizeof(int)); // int ???
float *component = malloc(sizeof *component * 64);

    Похожие записи:

    1. Оценка покерных рук (оптимизация скорости)
    2. C ++ 20: я — матрица, вещание, np.dot () и np.matmul ()
    3. Реализация параллельного трехмерного дискретного косинусного преобразования в Matlab
    4. Программа расчета небоскребов для размера NxN, версия 2 (с использованием функции отслеживания с возвратом)
    5. Функция batch_recursive_count_if с уровнем распаковки для произвольной вложенной итерируемой реализации произвольного типа в C ++

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *