Кодирование коэффициентов ДКП
Следующим шагом после квантования коэффициентов ДКП является преобразование матрицы этих коэффициентов в одномерную последовательность. Именно здесь окончательно реализуется процесс устранения избыточности, подготовка к которому проводилась на рассмотренных выше этапах ДКП и взвешенного квантования. Данное преобразование предусматривает объединение коэффициентов матрицы в определенные группы и применение затем так называемого энтропийного кодирования.
Алгоритм группирования (упорядочивания) коэффициентов ДКП существенно влияет на эффективность компрессии: в процессе сканирования преобразуемой во временной последовательность чисел матрицы нулевые коэффициенты объединяются в максимально длинные серии. Тогда их описание может сводиться к лаконичной записи длины серии и ее местоположения в матрице. Одним из вариантов такого алгоритма группирования является зигзагообразное сканирование, при котором преобразование начинается с левого верхнего угла матрицы и заканчивается в ее правом нижнем углу (рисунок 5.5).
Рис.5.5 — Зигзаг-сканирование коэффициентов ДКП
Поскольку именно в правом нижнем углу сосредоточено большинство нулевых коэффициентов, такой порядок сканирования обеспечивает формирование наиболее длинных серий нулей, а, следовательно, и самую компактную форму их передачи.
Полученная в результате сканирования последовательность чисел подвергается упомянутому выше энтропийному кодированию или кодированию с переменной длиной слова. Наиболее употребимым из энтропийных кодов является код Хаффмана. Он основывается на том, что коды символов, обладающих большей вероятностью, описываются меньшим числом бит, чем коды символов с меньшей вероятностью. Как было показано, после взвешенного квантования матрицы ДКП в последней преобладают числа с малыми амплитудами, и их целесообразно кодировать короткими словами. Большие амплитуды, характерные для левого верхнего угла матрицы, по сравнению с другими значениями коэффициентов встречаются реже, и им можно приписать символы с большим числом разрядов.
Эффективность энтропийного кода Хаффмана повышается также за счет того, что не требуется разделителей между символами. И хотя последние имеют различную битовую длину, они декодируются единственным образом.
Рассмотрим следующий простой пример. Пусть имеется алфавит из четырех символов А1, А2, А3, А4 . Вероятности появления этих символов в сообщениях приведены во втором столбце таблицы 5.1.
Табл.5.1
| Символ | Вероятность Символа | Обычное кодирование | Код Хаффмена |
| А1 | 0,5 | ||
| А2 | 0,25 | ||
| А3 | 0,125 | ||
| А4 | 0,125 |
При обычном кодировании алфавита из четырех символов на каждый символ требуется 2 бита, как это показано в третьем столбце таблицы. Код Хаффмена использует от 1 до 3 бит на символ. Проанализировав различные последовательности кодовых слов, можно убедиться, что непрерывный поток бит однозначно разделяется на кодовые слова.
Для оценки эффективности данного кодирования необходимо сопоставить среднее количество бит на символ в сообщении при обоих методах кодирования. Эта величина определяется соотношением
niPi,
i=1
где ni – длина кодового слова при передаче i–го символа: Pi– вероятность появления данного символа в сообщении. Легко видеть, что при обычном кодировании с постоянной длиной кодового слова среднее количество бит на символ равно 2, а при применении кода Хаффмена среднее количество бит на символ равно 1,75. Если, как в случае кодирования последовательностей пар чисел при передаче коэффициентов ДКП, алфавит содержит большое количество символов, вероятности появления которых существенно различаются, выигрыш в среднем количестве бит на символ при применении кодов с переменной длиной кодового слова оказывается существенно больше. Кодирование по Хаффмену обеспечивает наименьшую среднюю длину кодового слова среди всех возможных методов кодирования. Изложенные методы внутрикадрового кодирования явились основой принятого Международной организацией стандартизации ISO стандарта JPEG (JointPhotographicExpertsGroup). Данный стандарт определяет методику кодирования неподвижных изображений или отдельных кадров телевизионного сигнала. Методика включает разбиение изображения на блоки 8×8 пикселов, выполнение ДКП в каждом блоке, пороговую обработку и квантование полученных коэффициентов ДКП, считывание обработанных коэффициентов ДКП каждого блока изображения в зигзагообразном порядке, преобразование полученной последовательности коэффициентов ДКП в последовательность пар чисел, кодирование последовательности пар чисел с переменной длиной кодового слова. Изменением порога и шага квантования коэффициентов ДКП обеспечивается изменения качества воспроизводимого изображения в обмен на скорость передачи двоичных символов.
Методы JPEG используются при записи неподвижных изображений для экономии объема ЗУ. Для большинства изображений эти методы позволяют уменьшить объем информации в 5 – 10 раз без заметного ухудшения визуально воспринимаемого качества. В телевидении внутрикадровое кодирование является составной частью арсенала методов кодирования. Для еще большего сжатия информации применяется межкадровое кодирование, принципы которого рассматриваются в следующем разделе.