Метод Хаффмана.
Первоначально он был разработан для кодирования текстовых файлов. Для изображений, которые имеют большую долю основного цвета также бывает очень эффективным.
Основан он на использовании некоторых предварительно вычисленных статистических данных. Предварительно вычисляется статистическая информация для данных и такая же для устойчивых сочетаний у данных. Пусть у нас есть последовательность:
abbbcccddeeeeeeeee f
1 3 3 2 9 1
На основе этой последовательности строится граф. Его начинают строить с тех данных, которые встречаются в последовательности реже всего.
1
0 0 1
1
0
1
Те данные, которые встречаются чаще всего будут иметь короткие коды:
е.: 1
b: 010
c: 011
d: 001
a: 0000
f: 0001
Таким образом, мы заменяем данные некоторым двоичным кодом, который тем короче, чем чаще встречаются данные. Эффективность метода зависит от ряда причин:
Опирается на предварительную статистику.
Степень сжатия зависит от правильного определения статистики.
Следует строить граф для определения кодировки. Так как граф можно построить несколькими методами, то минимизация будет разной, то есть сам граф влияет на коды.
Эффективность от вида текста зависит крайне существенно. Существует ограниченный набор задач, где мы получаем нужный эффект. Одна из областей применения – это криптография. Оказывается, что в каждом языке, вероятность, что попадётся данная буква строго фиксируется, и если мы имеем кусок шифрованного текста, то можно вычислить вероятность каждого знака и по таблице расшифровать его.
Алгоритм сжатия jpeg.
Он работает только с растровыми изображениями. В настоящее время формат JPG поддерживается почти всеми пакетами, которые работают с растровой графикой. Предыдущие методы обеспечивали сжатие без потерь качества, а этот является алгоритмом сжатия с потерями. На изображениях типа фотографий, картин есть слишком много оттенков или градаций яркости. Человеческий глаз их просто не воспринимает. Таким образом, можно заменить целый ряд оттенков одним цветом. При этом при том же для глаза «качестве» картинки степень сжатия может достигать до 95%.
Суть. Берётся матрица (обычно размером 9х9 пикселей). Сравнивается две соседние матрицы и запоминается не две матрицы, а разница между ними. Затем берётся следующая матрица и так далее. Реализуется как программно, так и аппаратно. Если это делается аппаратно, то это делает графический сопроцессор. На первом шаге разница между соседними матрицами. Изменение некоторых частот по яркости. Характеризуется, как быстро меняется цвет и яркость. Диапазон частот разбивается на поддиапазоны, в каждом из которых находится число частот усреднения. Они далее и используются, которыми фактически и заменяются значения в исходном изображении. Сами средние частоты сжимаются по методу Хаффмана. Математика здесь очень сложная.
По особому алгоритму образуется плавающая шкала относительной важности.
Вычисляются частоты по дискретному косинусному преобразованию.
Размеры файлов получаются очень маленькие. С точки зрения пользователя при восстановлении изображения из JPEG резкие линии становятся размытыми. Ранее однотипный цвет может получить переливы. Поэтому не следует применять JPEG к изображениям с малым количеством цветов.
В то же время на фото при сохранении в JPEG и последующим восстановлении может пропасть зернистость, смягчиться контрастность. Чисто внешне изображение может быть субъективно качественнее.