Сжатие движущихся изображений

Алгоритмы архивации изображений без потери информации. Классический алгоритм Хаффмана. LZ и LZW компрессия.

Алгоритмы архивации изображений с регулируемой потерей информации. Алгоритм JPEG.

Понятие фрактала. Основные идеи фрактальных алгоритмов сжатия.

Сжатие движущихся изображений

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

Как и многое в технике, идея сжатия визуальной информации давно уже реализована матушкой природой в живых существах, населяющих Землю, в том числе и в нас с вами. Ресурсы нашего мозга были бы очень быстро исчерпаны, если бы мы воспринимали изображения просто как совокупность импульсов от сетчатки глаза. Например, глядя на лес, мы не запоминаем очертания каждого дерева однако впоследствии можем узнать конкретный лес или подробно описать его знакомым. Лес состоит из деревьев, на каждом из которых есть листья. Зная как выглядят «среднестатистическое» дерево и «среднестатистический» лист, мы строим в своем сознании соответствующую модель «среднестатистического» леса В качестве информации об определённом лесном массиве мы запоминаем различия между усредненной моделью в нашем представлении и реально наблюдаемым лесом там листва рано пожелтела, там дерево согнулось, а там необычно высокое дерево При необходимости по этим данным можно даже по памяти нарисовать картину. Вот это и есть один из видов сжатия графической информации.

Способы представления изображений в компьютере, используемые на практике сегодня, делятся на два основных типа: векторные и растровые.

При векторном представлении изображение передается в виде ин­формации о наборе геометрических фигур, их цвете и взаимном располо­жении. Прямо как в стишке: «Ручки, ножки, огуречик — вот и вышел чело­вечек». Описание векторной графики, как правило, очень компактно, но, увы, далеко не каждое изображение можно представить набором геометрических фигур. Если вы создаете рисунок в графическом редакторе, то компьютер «запоминает», из каких геометрических фигур вы конструируете изображение. Однако если вы, например, пытаетесь имитировать изменение давления карандаша или кисти, записать это в векторной форме очень сложно, подчас невозможно. Тем более невозможно представление в векторной форме фотографии с плавными цветовыми переходами. Поэтому фотографии, а также рисунки с нечёткими границами объектов представляют в растровом виде, когда изображение равномерно делится на точки — растр. Каждой точке в зависимости от её цветового оттенка ставится в соответствие элемент двумерного числового массива. Недостатком растрового представления является большой объём запи­сываемой информации — здесь-то и требуются высокоэффективные методы сжатия. На практике часто используется комбинированный вариант — растровое изображение входит в состав векторного как один из эле­ментов (т.е. как фигура типа «набор точек»).

Точность представления изображения в растровой форме определяется тремя параметрами: числом точек по вертикали, числом точек по горизонтали и глубиной цвета, то есть числом бит, отведённым для отображения одной точки. Для чёрно-белых изображений вполне достаточно глубины цвета 8 бит, поскольку наш глаз различает не более 256 оттенков серого. Если говорить обо всех цветовых оттенках, которые мы воспринимаем, то их примерно 16 миллионов, следовательно, для фотографического изображения нужна глубина цвета 24 бита.

Однако на каждом конкретном изображении оказываются задейст­вованными далеко не все цветовые оттенки, которые мы можем различить. Вот и первый резерв уменьшения размера файла — нужно описать палитру, т.е. перечислить и пронумеровать цветовые оттенки, которые используются в изображении, а потом указать в каждом из элементов массива номер цвета в палитре. Поскольку число цветов в палитре значительно меньше, чем число различаемых нами оттенков, то в итоге на описание каждой точки изобра­жения уйдет меньшее число бит.

В персональных компьютерах основным форматом без сжатия является BMP (Bitmap), причем существует две его версии: OS/2 Bitmap и Windows Bitmap. Для хранения несжатых изображений в таких областях, как компьютерная графика, издательское дело и цифровая фотография, используется один из вариантов формата TIFF (опция «без сжатия»), который наряду с набором чисел, поставленных в соответствие пикселам, содержит дополнительную информацию, необходимую при работе с изображением.

Методы сжатия информации, в том числе и графической, делятся на два класса: с потерями и без потерь.

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

Во втором случае исходные данные можно восстановить в неизменном виде (среди таких методов — алгоритм RLE, серия алгоритмов LZ).