1.3. Округление
Следующим этапом, на котором и происходит основная потеря информации, является округление или квантование. Как видно, ДКП не выполняет какого-либо сжатия или кодирования. Основной его задачей является преобразование исходного изображения к виду, удобному для последующих операций над ним.
Округлением называется процесс уменьшения объема информации, необходимого для хранения матрицы ДКП, с частичной потерей точности. По стандарту JPEG для этого используется матрица округления (МО). Каждому элементу исходной матрицы ДКП соответствует элемент МО. Результирующая матрица получается делением исходной матрица на МО. При этом низкочастотным значениям в матрице ДКП соответствуют меньшие коэффициенты МО, что позволяет оставлять более значимую, низкочастотную информацию и отбрасывать менее важную высокочастотную. В связи с тем, что низкочастотные компоненты сосредоточены в левом верхнем углу матрицы ДКП, значения МО растут слева направо и сверху вниз.
Результаты округления и качества восстановленного изображения напрямую зависят от выбранной матрицы округления. Стандарт JPEG позволяет использовать любую МО, однако ISO в ходе долгих экспериментальных тестирований разработала набор матриц, позволяющих добиться оптимальных результатов.
1.4. Сжатие
Последний этап работы алгоритма кодирования JPEG — это сжатие. После обработки матрицы ДКП с помощью МО, в результирующей матрице появляется большое количество нулей, особенно в высокочастотной области (правый нижний угол).
Первым шагом значение в левом верхнем углу результирующей матрицы заменяется на относительное. Так как соседние блоки изображения похожи друг на друга, то кодирование очередного элемента (0,0) через разницу с предыдущим будет более эффективным. Вторым шагом является непосредственно применение алгоритма кодирования повторов (LZW), для обработки большого количества подряд идущих нулей. Экспериментальные тестирования показали, что наилучших результатов можно добиться, если обходить матрицу зигзагом, как показано на рисунке 1.
Рисунок — 1 Порядок обхода матрицы зигзагом
Наконец, на третьем и заключительном шаге полученный результат сжимается, как обычные данные с помощью алгоритма Хаффмана или арифметического кодирования в зависимости от реализации. Этот этап носит название «кодирование энтропии» (в терминологии JPEG).
1.5. Кодирование энтропии
Энтропийное кодирование – кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности.
Предполагается, что до кодирования отдельные элементы последовательности имеют различную вероятность появления. После кодирования в результирующей последовательности вероятности появления отдельных символов практически одинаковы (энтропия на символ максимальна).
Различают несколько вариантов кодов:
1) Сопоставление каждому элементу исходной последовательности различного числа элементов результирующей последовательности. Чем больше вероятность появления исходного элемента, тем короче соответствующая результирующая последовательность. Примером могут служить код Шеннона — Фано, код Хаффмана.
2) Сопоставление нескольким элементам исходной последовательности фиксированного числа элементов конечной последовательности. Примером является код Танстола.
3) Другие структурные коды, основанные на операциях с последовательностью символов. Примером является кодирование длин серий.
4) Если приблизительные характеристики энтропии потока данных предварительно известны, может быть полезен более простой статический код, такой как унарное кодирование, гамма-код Элиаса, код Фибоначчи, код Голомба или кодирование Райса.
Согласно теореме Шеннона, существует предел сжатия без потерь, зависящий от энтропии источника. Чем более предсказуемы получаемые данные, тем лучше их можно сжать. Случайная независимая равновероятная последовательность сжатию без потерь не поддаётся.