Как работает эта реализация 1D IDCT? - PullRequest
Новая
       53

Как работает эта реализация 1D IDCT?

4 голосов
/ 04 января 2012

У меня есть реализация обратного дискретного косинусного преобразования, и я пытаюсь выяснить, как они попали в этот код.До сих пор я выяснил, что это, вероятно, оптимизированная реализация Cooley-Tukey radix-2 Decimation-in-time для DCT вместо DFT (дискретного преобразования Фурье).

Тем не менее, я все еще не знаю, что именно происходит на каждом этапе.Я подумал, что Wx-константы, вероятно, являются твидл-факторами.

Кто-нибудь может дать ссылку на объяснение или дать какое-то объяснение этому коду?

//Twiddle factors
#define W1 2841 /* 2048*sqrt(2)*cos(1*pi/16) */
#define W2 2676 /* 2048*sqrt(2)*cos(2*pi/16) */
#define W3 2408 /* 2048*sqrt(2)*cos(3*pi/16) */
#define W5 1609 /* 2048*sqrt(2)*cos(5*pi/16) */
#define W6 1108 /* 2048*sqrt(2)*cos(6*pi/16) */
#define W7 565 /* 2048*sqrt(2)*cos(7*pi/16) */

//Discrete Cosine Transform on a row of 8 DCT coefficients.
NJ_INLINE void njRowIDCT(int* blk) {
    int x0, x1, x2, x3, x4, x5, x6, x7, x8;
    int t;
    if (!((x1 = blk[4] << 11)
        | (x2 = blk[6])
        | (x3 = blk[2])
        | (x4 = blk[1])
        | (x5 = blk[7])
        | (x6 = blk[5])
        | (x7 = blk[3])))
    {
        blk[0] = blk[1] = blk[2] = blk[3] = blk[4] = blk[5] = blk[6] = blk[7] = blk[0] << 3;
        return;
    }
    x0 = (blk[0] << 11) + 128;  //For rounding at fourth stage

    //First stage
    /*What exactly are we doing here? Do the x values have a meaning?*/
    x8 = W7 * (x4 + x5);
    x4 = x8 + (W1 - W7) * x4;
    x5 = x8 - (W1 + W7) * x5;
    x8 = W3 * (x6 + x7);
    x6 = x8 - (W3 - W5) * x6;
    x7 = x8 - (W3 + W5) * x7;

    //Second stage
    x8 = x0 + x1;
    x0 -= x1;
    x1 = W6 * (x3 + x2);
    x2 = x1 - (W2 + W6) * x2;
    x3 = x1 + (W2 - W6) * x3;
    x1 = x4 + x6;
    x4 -= x6;
    x6 = x5 + x7;
    x5 -= x7;

    //Third stage
    x7 = x8 + x3;
    x8 -= x3;
    x3 = x0 + x2;
    x0 -= x2;
    x2 = (181 * (x4 + x5) + 128) >> 8;
    x4 = (181 * (x4 - x5) + 128) >> 8;

    //Fourth stage
    blk[0] = (x7 + x1) >> 8;  //bit shift is to emulate 8 bit fixed point precision
    blk[1] = (x3 + x2) >> 8;
    blk[2] = (x0 + x4) >> 8;
    blk[3] = (x8 + x6) >> 8;
    blk[4] = (x8 - x6) >> 8;
    blk[5] = (x0 - x4) >> 8;
    blk[6] = (x3 - x2) >> 8;
    blk[7] = (x7 - x1) >> 8;

}

Ответы [ 2 ]

4 голосов
/ 05 января 2012

Я не эксперт в DCT, но я написал несколько FFT-реализаций в свое время, поэтому я попытаюсь ответить на этот вопрос. Пожалуйста, возьмите следующее с щепоткой соли. 

void njRowIDCT(int* blk)

Вы правильно говорите, что алгоритм представляет собой DCT Radix-2 длиной 8, который использует арифметику с фиксированной точкой с точностью 24: 8. Я предполагаю точность, потому что последняя ступень справа сдвигается на 8, чтобы получить желаемое (это и комментарий рассказывающего рассказа;)

Поскольку его длина 8, его мощность равна 3 (2 ^ 3 = 8), что означает, что в DCT есть 3 ступени. Пока что все это очень похоже на БПФ. «Четвертая стадия» - это просто масштабирование для восстановления исходной точности после арифметики с фиксированной точкой.

Насколько я вижу, входной каскад представляет собой обращение битов от входного массива blk к локальным переменным x0-x7. х8 кажется временной переменной. Извините, я не могу быть более наглядным, чем это.

Стадия обращения бит

Bit Reversal of input

Обновление

Взгляните на DSP для ученых и инженеров . Это дает четкое и точное объяснение тем обработки сигналов. Эта глава посвящена DCT (перейдите к p497).

Wn (множители) соответствуют базисным функциям в этой главе, хотя обратите внимание, что это описание DCT 8x8 (2D).

В отношении трех этапов, которые я упомянул, сравните с описанием 8-точечного БПФ:

8ptFFTGraph

БПФ выполняет бабочек на обращенном к битам входном массиве (которые по сути являются сложными многократными сложениями), умножая один путь на Wn или коэффициент твида. БПФ выполняется поэтапно. Я до сих пор не выяснил, что делает ваш код DCT, но разложение на такую ​​диаграмму может помочь.

Тот или кто-то, кто знает, о чем они говорят, подойдут; -)

Я вернусь на эту страницу и отредактирую по мере расшифровки кода

1 голос
/ 05 января 2012

Как DFT, так и DCT являются просто линейными преобразованиями, которые могут быть представлены в виде одного сложного матричного умножения (иногда обрезанного для строго реального ввода).Таким образом, вы можете просто объединить приведенные выше уравнения, чтобы получить формулу для каждого последнего члена, которая должна в конечном итоге быть эквивалентной одной строке матрицы линейного преобразования (игнорируя проблемы округления).Затем посмотрите, как вышеприведенная кодовая последовательность вручную выполняет общую оптимизацию подвыражения или рефакторинг между и / или в вычислениях строк.

...