Веселые картинки

Weird aka Беренштейн Евгений

Хакер, номер #087, стр. 087-034-2

[алгоритм JPEG]

Что же такое JPEG и с чем его едят? А знаешь ли ты, как работает этот известный алгоритм? На самом же деле не все так просто, как кажется на первый взгляд, когда мы в Adobe Photoshop PSD картинку сохраняем в формате JPEG, тем самым, сжимая ее.

Алгоритм JPEG стандартизован относительно недавно — в 1991 году. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стандарта были ограничены мощностью, существовавшей на тот момент техники. То есть даже на персональном компьютере алгоритм должен был работать меньше минуты на среднем изображении, а его аппаратная реализация должна быть относительно простой и дешевой. Алгоритм должен был быть симметричным (время разархивации примерно равно времени архивации).

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

Этот алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации. В целом алгоритм основан на дискретном косинусоидальном преобразовании, применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

Все вышесказанное будет темным лесом для человека, который никогда с этим не сталкивался, поэтому мы пойдем более простым путем. Самым главным является то, что изображение разбивается на квадратики размером 8х8 пикселей. Сразу возникает вопрос: почему? Ответ оказывается на удивление прост: внутри такой области яркость и цвет меняются весьма плавно, поэтому алгоритм отрезает у частотной составляющей часть, которая несет гораздо меньше информации. За счет несовершенства человеческого глаза и появляется возможность сжатия данных.

Таким образом, основные стадии этого алгоритма следующие. Изображение разбивается на шаблоны 8х8 точек. Для каждого шаблона (матрицы) выполняется дискретное косинусоидальное преобразование (ДКП). Давай разберемся, зачем нам это преобразование нужно. ДКП раскладывает изображение по амплитудам некоторых частот. Далее из получившихся частот, с помощью специальной весовой таблицы отбираются наиболее существенные для визуального восприятия. Эта процедура называется квантованием и является единственным этапом, на котором происходит потеря информации. Далее матрица отобранных частот представляется компактным образом и кодируется.