Jpeg Хаффман кодирования - PullRequest
       39

Jpeg Хаффман кодирования

3 голосов
/ 02 февраля 2012

Таблица Хаффмана в стандарте JPEG создается из набора статистических данных в два этапа.Одним из шагов является реализация функции / метода, заданного этим изображением: (Это изображение дано в Приложении K стандарта JPEG): Function

Проблема здесь.Ранее в стандарте (Приложение C) говорится это предложение:

Таблицы Хаффмана указаны в виде 16-байтового списка (БИТОВ), в котором указано количество кодов для каждой длины кода от 1 до 16. Этосопровождается списком 8-битных значений символов (HUFFVAL), каждому из которых назначается код Хаффмана.

Очевидно, BITS - это список из 16 элементов.Но на картинке выше, i сначала установлен на 32 (i=32), затем мы хотим получить доступ к BITS[i].Возможно, я что-то неправильно понял, поэтому, пожалуйста, позвольте мне дать ответ.

Вот стандартное описание изображения в формате JPEG: На рисунке K.3 приведена процедура настройки списка BITS так,что ни один код не длиннее 16 бит.Поскольку символы соединяются для самого длинного кода Хаффмана, символы удаляются из этой категории длины по два за раз.Префикс для пары (которая на один бит короче) назначается одной из пары;затем (пропуская запись BITS для этой длины префикса) кодовое слово из следующей кратчайшей ненулевой записи BITS преобразуется в префикс для двух кодовых слов на один бит длиннее.После того, как список BITS уменьшен до максимальной длины кода 16 битов, последний шаг удаляет зарезервированную кодовую точку из счетчика длины кода.

Вот код для рисунка выше:

void adjustBitLengthTo16Bits(vector<char>&BITS){
    int i=32,j=0;
    while(1){
        if(BITS[i]>0){
            j=i-1;
            j--;
            while(BITS[j]<=0)
                j--;
            BITS[i]=BITS[i]-2;
            BITS[i-1]=BITS[i-1]+1;
            BITS[j+1]=BITS[j+1]+2;
            BITS[j]=BITS[j]-1;
            continue;
        }
        else{
            i--;
            if(i!=16)
                continue;

            while(BITS[i]==0)
                i--;
            BITS[i]--;
            return;
        }
    }
}

1 Ответ

3 голосов
/ 02 февраля 2012

Этот код предназначен только для кодировщиков, которые хотят создавать свои собственные таблицы Хаффмана. Большинство кодеров JPEG просто используют фиксированные таблицы, которые являются разумным приближением статистики большинства изображений. В этом конкретном случае первый шаг в создании таблицы Хаффмана для коэффициентов переменного тока создает таблицу длиной до 32 записей (битов). Поскольку существует только 256 уникальных символов для кодирования (пары пропуска / длины), никогда не должно быть больше 32 бит, необходимых для указания всех кодов Хаффмана. После того, как первый проход произведет набор кодов (длиной до 32 бит), второй проход берет наименее частые (самые длинные) коды и «перемещает» их в интервалы с более короткой длиной, так что максимальная длина кода составляет 16 бит , В идеальной таблице Хаффмана частотные распределения соответствуют длинам кода. В этом случае таблица подстраивается под сжатие самых длинных кодов в слоты, зарезервированные для более коротких кодов. Это можно сделать, потому что коды Хаффмана длиной 14/15/16 битов имеют «пространство» для большего количества перестановок битов и могут «вмещать» в них более длинные коды.

Обновление: Преимущество «оптимизации» таблиц Хаффмана в JPEG ограничено. Большая часть сжатия происходит из-за квантования и преобразования DCT пикселей. Переключение на арифметическое кодирование дает ощутимое преимущество (уменьшение размера ~ 10%), но в то же время ограничивает аудиторию, поскольку большинство декодеров JPEG не поддерживают арифметическое кодирование из-за прошлых проблем с патентами.

...