Квантование, Фурье-сжатие, Сжатие без потерь, алгоритм Хаффмана - Один алгоритм сжатия изображения

Рассмотри косинус-пребразование Фурье для кусочно-постоянных функций

В jpeg используется ступенчатые кусочно-постоянные функции : отрезок (0,р) разбивается на части, ; на этих частичных отрезках функция принимает постоянные значения (это числа от 0 до 255, полученные на квадратике 8х8).

Интеграл (2.1.3) принимает вид

=( (2.2.1)

Обозначим значение интегралов, стоящих в круглых скобках (2.2.1), и рассмотрим матрицу (). Рассмотрим также вектор-столбцы = и.

Из (2.2.1) следует, что вектор коэффициентов a определяется умножением матрицы на вектор значений.

Так как матрица вычислена заранее, то это дает быстрое вычисление коэффициентов. При этом феноменология задачи такова, что достаточно вычислять лишь первые 6-10 коэффициентов (квантование).

Сжатие без потерь, алгоритм Хаффмана

Некоторые виды информации должны быть переданы точно, без потерь, например, чертежи, буквенный или числовой текст и т. п. Одним из самых распространенных алгоритмов сжатия без потерь является алгоритм Хаффмана, его можно назвать статистическим алгоритмом; коэффициент сжатия - 8, 1.5, 1 (лучший, средний, худший случаи). В задаче сжатия изображений он применяется как дополнительный. Текстовый документ обычно формируется некоторым алфавитом с буквами постоянной длины в битах. Алгоритм Хаффмана состоит, во-1х, в подсчете частоты появления каждой буквы. Например, если текст состоит из n букв, то вычисляют число повторений в тексте k-ой буквы алфавита и вычисляют частоту pk= (говорят также - вероятность,.

Во-2х, формируется по некоторому алгоритму новый двоичный алфавит с буквами переменной длины, что и обеспечивает сжатие. Буквам исходного алфавита с наибольшими ставятся в соответствие новые с наиболее короткой записью.

Например, пусть текст состоит из 4-х цифр, обозначим их, , , . Для записи в тексте каждой требуется 3 бита. = 0.5, = 0.24, = 0,15, = 0.11, т. е. занимает 11% объема текста. Можно предложить следующий двоичный алфавит - 0, - 10, - 110, - 101, не трудно проверить непротиворечивость этого алфавита, т. е. любая запись читается единственным образом и не может быть прочитана двояко.

Похожие статьи




Квантование, Фурье-сжатие, Сжатие без потерь, алгоритм Хаффмана - Один алгоритм сжатия изображения

Предыдущая | Следующая