Сжатие цифровых изображений

УДК 004.932:004.032.26:519.713 
ББК 32.811 

С33 

Р е ц е н з е н т :  доктор физ.-мат. наук, профессор  С. С. Бондарчук 

А в т о р ы :  О. О. Евсютин, А. А. Шелупанов, С. К. Росошек, Р. В. Мещеряков  

С33
Сжатие цифровых изображений. – М.: Горячая линия – Телеком, 
2013. – 124 с.: ил. 

ISBN 978-5-9912-0357-9. 

На основе математического аппарата теории клеточных автоматов для 
решения задач сжатия цифровых изображений изложен подход, основанный на использовании динамики клеточного автомата для построения ортогональных базисов декоррелирующих преобразований, устраняющих 
пространственную избыточность из элементов данных. Представлены математическая модель сжатия цифровых изображений на основе клеточных автоматов более чем первого порядка и эффективные алгоритмы построения 
и выбора базисов декоррелирующих клеточных преобразований. Изложен 
эффективный метод сжатия цифровых изображений и проведено сравнение 
с методами JPEG и JPEG 2000.  
Применение полученных авторами результатов открывает перспективы создания алгоритмов обработки цифровых изображений, столь же эффективных, что и построенные на основе дискретного вейвлетного преобразования, и в то же время столь же быстродействующих, что и основанные на дискретном преобразовании Фурье, за счет замены вещественных 
операций целочисленными.   
Для инженеров и научных работников, аспирантов и студентов вузов 
интересующихся проблемами сжатия цифровых изображений.  
 

ББК 32.811 

Адрес издательства в Интернет WWW.TECHBOOK.RU 

Научное издание 

Евсютин Олег Олегович  

Шелупанов Александр Александрович 

Росошек Семен Константинович 
Мещеряков Роман Валерьевич 

СЖАТИЕ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ  

Монография 

Редактор  Ю. Н. Чернышов 
Компьютерная верстка  Ю. Н. Чернышова 
Обложка художника  О. В. Карповой 
 

Подписано в печать  01.09.2013.  Формат 60×88/16. Уч. изд. л. 7,75.  Тираж 500 экз.  
ООО «Научно-техническое издательство «Горячая линия – Телеком» 
ISBN 978-5-9912-0357-9                                          ©  Коллектив авторов,  2013 
©  Издательство «Горячая линия – Телеком», 2013 

Введение

Сжатие данных является одной из актуальных проблем в области современных информационных технологий. Производительность
вычислительной техники постоянно растет, и несмотря на повышение емкости и доступности носителей информации, а также пропускной способности телекоммуникационных линий, их возможности не
успевают за ростом потоков данных, требующих обработки.
При
этом особую значимость приобретает проблема сжатия цифровых
изображений, представляющих собой один из наиболее распространенных в настоящее время типов данных.
Сжатие цифровых изображений основывается на устранении
присущей им пространственной избыточности, проявляющейся в виде близости друг другу значений соседних пикселей на локальных
участках изображения.
Существуют различные подходы к декорреляции элементов
цифрового изображения, обладающие своими достоинствами и недостатками. Так, например, декорреляция с предсказанием значений пикселей широко используется в методах сжатия без потерь информации, применение которых актуально для отдельных специализированных приложений, но в общем случае малоэффективно [16,
65]. В свою очередь, фрактальное сжатие изображений, основанное
на поиске самоподобных участков, позволяет достичь самых высоких степеней сжатия, но требует чрезмерных вычислительных затрат [12].
В основе наиболее распространенных современных методов сжатия цифровых изображений с потерями лежат ортогональные декоррелирующие преобразования, осуществляющие разделение элементов данных на составляющие, содержащие основную информацию об
изображении и определяющие малозначимые детали. Сжатие происходит за счет удаления составляющих второго типа из преобразованных элементов данных с последующим энтропийным кодированием
оставшихся элементов [10, 65, 81, 84, 100].
К самым известным ортогональным преобразованиям, которые
используются в методах сжатия цифровых изображений, относятся преобразование Карунена–Лоэва [82, 95], преобразование Уолша–
Адамара [31, 69, 75, 77], дискретное косинусное преобразование [65,

Введение

84], являющееся частным случаем дискретного преобразования Фурье, семейство дискретных вейвлетных преобразований [13, 18, 32,
46].
На основе отдельных представителей данного класса преобразований построены такие известные методы сжатия, как JPEG,
JPEG 2000, SPIHT, QTCQ, EZW, ICER, JPEG XR, WebP.
Фундаментальные основы обработки и сжатия цифровых изображений были заложены в работах N. Ahmed, K.R. Rao, I. Daubechies, R.C. Gonzalez, M.W. Marcellin. В России наибольший вклад в
данную область внесли Д.С. Ватолин, И.И. Исмагилов, Н.Н. Пономаренко, С.В. Умняшкин [9, 12, 14, 16, 18, 33–35, 53, 54, 70–73, 99].
Основная проблема, связанная со сжатием цифровых изображений с потерями, заключается в появлении на восстанавливаемых
после сжатия изображениях разного рода искажений — так называемых артефактов сжатия [67]. При этом каждому из известных
методов сжатия присущи свои собственные артефакты, характер которых зависит от используемого математического аппарата.
Поэтому актуальными являются исследования, направленные
как на улучшение существующих методов сжатия цифровых изображений, так и на разработку новых с привлечением не использовавшегося ранее в данной области математического аппарата.
В настоящее время известны работы, в которых для решения
задачи сжатия цифровых изображений был задействован математический аппарат нейронных сетей [40, 66], модифицированное дискретное косинусное преобразование [53, 73], иерархическая сеточная
интерполяция [14].
Большой интерес в этом отношении представляет математический аппарат теории клеточных автоматов.
Создателями данной
теории были J. von Neumann и K. Zuse. На ее дальнейшее развитие значительное влияние оказали работы E.F. Codd, A. Ilachinski,
T. Toffoli, J.L. Schiff, S. Wolfram, а также В.З. Аладьева, В.Б. Кудрявцева, А.С. Подколзина [2, 38, 39, 68, 86, 88, 91, 105]. В частности,
N. Margolus ввел такое расширение классической модели клеточных
автоматов, как блочные клеточные автоматы (клеточные автоматы
на разбиении) [68].
Математический аппарат теории клеточных автоматов ранее использовался для сжатия цифровых изображений, однако его использование ограничивалось решением некоторых частных задач в рамках существующих методов.
C. Shaw, S. Das и B.K. Sikdar предложили основанный на клеточных автоматах способ энтропийного
кодирования элементов цифрового изображения после дискретного
вейвлетного преобразования [102]. O. Lafe разработал метод сжатия,
построенный на основе декоррелирующего преобразования, использующего в качестве базисных векторов состояния развития класси

Введение
5

ческого клеточного автомата первого порядка с окрестностью Мура–
фон Неймана [98]. Здесь под порядком клеточного автомата подразумевается значение ⌈log2 |A|⌉, где A — алфавит внутренних состояний, определяющий множество возможных значений каждой из клеток решетки автомата. Недостатком клеточных автоматов первого
порядка в контексте решаемой задачи является получение малого количества декоррелирующих преобразований, которые не отличаются
разнообразием свойств и, кроме того, являясь частным случаем преобразования Уолша–Адамара, не обладают какими-либо дополнительными свойствами, отсутствующими у известных преобразований.
Поэтому авторами предлагается расширить класс декоррелирующих преобразований, получаемых с помощью динамики клеточного автомата, за счет использования клеточных автоматов более, чем
первого порядка, что открывает перспективы построения аппроксимаций более сложных преобразований.

Г л а в а
1

Анализ методов сжатия цифровых
изображений

1.1. Особенности цифровых изображений как
типа данных
Цифровое изображение представляет собой прямоугольную матрицу, элементы которой, называемые пикселями, принимают значения из некоторого отрезка ряда целых чисел. Изображение, состоящее из m строк и n столбцов, математически можно описать как
A = (aij)m,n
i=1,j=1, aij ∈ {0, 1, ..., L − 1}, i = 1, m, j = 1, n. Указанный
отрезок начинается с нуля, поскольку в общем случае значение пикселя определяет его яркость и отрицательные значения яркости не
рассматриваются. Мощность множества возможных значений пикселя L, т. е. количество различных уровней яркости, для удобства
аппаратной и программной реализации всегда принимается равной
некоторой степени двойки, чтобы каждый пиксель мог быть представлен целым числом битов.
Также изображение можно описать как дискретную функцию
двух переменных f(x, y) с областью определения E = {0, ..., m−1}×
×{0, ..., n−1}, в этом случае называемой пространственной областью,
и областью значений D = {0, 1, ..., L − 1} [10, 16, 57, 87].
В зависимости от значения L, наличия цвета у пикселей, а также особенностей содержимого различают несколько основных типов
цифровых изображений.
Простейшими являются монохромные (бинарные) цифровые
изображения. Каждый пиксель таких изображений кодируется одним битом, что дает только два цвета: черный и белый [76]. Двуцветные изображения в настоящее время распространены не очень
широко и используются, например, в факсимильной связи, а также
в некоторых специальных приложениях [65].
Более распространенными и удобными для восприятия являются полутоновые цифровые изображения, когда все множество возможных значений пикселя воспринимается как переход от черного

Анализ методов сжатия цифровых изображений
7

цвета к белому через некоторое количество промежуточных оттенков
серого (уровней яркости). Чаще всего пиксели таких изображений
кодируются одним байтом, тогда говорят о 8-битовых изображениях
с 256 градациями серого цвета. Также для представления пикселей
используют 4 или 16 битов, что соответствует 16 или 65536 уровням
яркости.
Пиксели изображений указанных типов не обладают цветом как
таковым, а только яркостью, поэтому далее в рассматриваемой классификации стоят цветные цифровые изображения, которые представляются с помощью определенной цветовой модели. Наиболее известной является RGB-модель, когда цвет каждого пикселя определяется тремя независимыми компонентами красного (red), зеленого
(green) и синего (blue) цветов. Также существуют другие модели,
такие, как CMY, HSI, YCbCr и т. д. [97, 103, 104], последняя из которых, применяющаяся в методах сжатия изображений, будет рассмотрена более подробно в разд. 1.4.
Обычно каждая цветовая компонента кодируется одним байтом,
тогда говорят о 24-разрядных цветных изображениях, естественно,
для них задача сжатия является наиболее актуальной.
Дальнейшая классификация относится уже к цветным изображениям, которые делятся на непрерывно-тоновые и дискретно-тоновые. Главными особенностями непрерывно-тоновых изображений
являются плавные цветовые переходы и отсутствие резких границ,
наличие которых, в свою очередь, является особенностью дискретнотоновых изображений. И если к первым относятся, прежде всего,
оцифрованные изображения окружающей действительности, то ко
вторым — компьютерная графика.
В отдельную категорию выделяются изображения, характерные
для мультипликации. Их особенностями является наличие резких
границ между объектами и однотонное заполнение внутри границ.
Однако их можно считать разновидностью дискретно-тоновых изображений.
Данную классификацию цифровых изображений можно продолжить, разбив указанные основные типы на подтипы по тем особенностям, которые являются характерными для той или иной сферы
человеческой деятельности.
Например, своей спецификой обладают рентгеновские снимки, снимки из космоса, изображения, зарегистрированные в инфракрасном диапазоне, и т. д. [3, 52]. Однако
ограничимся базовой классификацией.
Теперь необходимо выделить основные особенности цифровых
изображений, актуальные в контексте задачи сжатия информации,
что лучше сделать в сравнении с произвольными текстовыми данными, под которыми подразумеваются тексты на естественном или ис

Г л а в а 1

кусственном языке, представляющие собой последовательности символов некоторых алфавитов [21, 23, 37, 60, 55, 100].
Возможность сжатия таких данных определяется наличием в
них статистической избыточности, которая заключается в том, что
отдельно взятые символы алфавита могут встречаться в тексте различное число раз, а также могут повторяться последовательности
символов. Соответственно, задачей сжатия является устранение статистической избыточности посредством присвоения кодов меньшей
битовой длины элементам данных.
Подобным образом действуют статистические и словарные методы сжатия, однако они малопригодны для непосредственного сжатия
цифровых изображений, поскольку существует ряд принципиальных
отличий между изображениями и текстовыми данными.
Во-первых, текст воспринимается как одномерная строка символов, а изображение является двумерным.
В том случае, когда
между элементами данных наблюдается корреляция, о чем будет
сказано ниже, вопрос представления данных становится достаточно
существенным.
Во-вторых, символы текста обычно принимают значения из относительно небольшого множества, такого, как таблица ASCII, состоящая из 256 элементов, каждый из которых кодируется одним байтом, в то время как наиболее распространенные непрерывно-тоновые
изображения строятся с использованием 224 цветов. Вследствие этого подсчет частот встречаемости различных цветов или поиск одинаковых последовательностей пикселей не дадут никакого эффекта.
Также важным является тот факт, что практически невозможно
удалить из текста часть информации так, чтобы это осталось незамеченным. Однако из изображения вполне возможно удалить часть
информации, осуществив, например, подвыборку пикселей. До определенного момента человеческое зрение будет неспособно различить
отличия [16, 97].
Наконец, сжатие по сути заключается в компактном представлении данных за счет того, что некоторые их элементы коррелируют
друг с другом. Однако, рассматривая произвольный текст, мы не можем предполагать, что эта корреляция распространяется именно на
соседние элементы. Одинаковые последовательности символов могут встречаться в любых участках текста. Конечно, каждый язык
обладает определенными особенностями, так, например, в русском
языке маловероятно появление буквы «Ъ» после «Ь» и т. д. Но все
эти факторы учесть невозможно, и они являются малозначимыми
по отношению к задаче компрессии. Поэтому методы сжатия текстовых данных опираются на неявное предположение, что соседние
символы текста никак не связаны между собой.

Анализ методов сжатия цифровых изображений
9

Цифровые изображения, напротив, обладают важнейшей с точки зрения сжатия особенностью: с высокой степенью вероятности
соседние пиксели в пределах некоторой локальной области имеют
одинаковые или близкие цвета.
Это достаточно очевидный факт,
и трудно привести пример полезного изображения, у которого все
соседние пиксели будут резко отличаться друг от друга.
Даже у
дискретно-тоновых изображений в пределах границ объектов имеют
место плавные переходы цветов или однородное заполнение.
Избыточность такого типа, присущая лишь изображениям, получила название пространственной. В связи с этим для сжатия изображений был разработан абсолютно новый подход, заключающийся
в устранении из изображения корреляции между пикселями посредством специального преобразования и дальнейшего статистического
кодирования преобразованных данных.

1.2. Математическая модель сжатия цифровых
изображений
Основу данной модели составляет декоррелирующее преобразование, подобное преобразованию Фурье, отображающему дискретную функцию двух переменных, которой является изображение, из
пространственной области в частотную [15, 31, 51]. Исходная функция представляется в виде суммы элементарных функций различных частот, причем низкочастотные составляющие определяют общий вид функции, а высокочастотные — ее поведение на локальных
участках.
Если значения дискретной функции связаны между собой пространственной избыточностью, то для приближенного восстановления исходной функции достаточно нескольких низкочастотных компонент, остальными допустимо пренебречь.
Количество наиболее
информативных низкочастотных компонент определяется видом
преобразуемой функции. В предельном случае, когда все исходные
значения одинаковы, вся информация будет сосредоточена в одной
низкочастотной составляющей.
Применительно к цифровым изображениям низкочастотные составляющие частотного преобразования соответствуют усредненному значению пикселей в заданной области изображения и определяют огрубленное (сглаженное) представление данной области. В свою
очередь, высокочастотные составляющие соответствуют отклонениям от среднего значения и отвечают за резкость рассматриваемой
области, определяя контуры объектов и мелкие детали.
После применения декоррелирующего преобразования элементы изображения оказываются связанными друг с другом лишь статистической избыточностью, что наряду с уменьшением диапазона

Г л а в а 1

значений высокочастотных составляющих позволяет успешно применять статистические методы сжатия.
Математическая модель сжатия цифровых изображений, основанная на описанном выше подходе, выглядит следующим образом.
Прежде всего, изображение подвергается предварительной обработке, которая может заключаться в преобразовании цветовой модели, добавлении некоторого количества строк и столбцов, подвыборке пикселей и т. д. Данный этап трудно формализовать в общем
виде, поскольку здесь может расширяться область определения функции, представляющей изображение, или изменяться область значений, что определяется конкретным алгоритмом сжатия. Однако
необходимо отметить, что данный этап в отличие от последующих
осуществляется в пространственной области.
Затем осуществляется построенное на основе некоторого ортогонального базиса декоррелирующее преобразование, которое независимо от используемого математического аппарата приводит к удалению пространственной избыточности, связывающей элементы исходного изображения (или преобразованного изображения, полученного
после предварительной обработки), и выявлению статистической избыточности. Декоррелирующее преобразование применяется не ко
всему изображению, а к некоторым его участкам равного размера,
называемым блоками. Это обусловлено тем, что пространственная
избыточность, присущая изображениям, является локальной: каждый пиксель коррелирует с ограниченным числом других пикселей
по горизонтали и вертикали. Обычно в качестве локальной области
с существенной пространственной избыточностью принимают блок
изображения размером 8 × 8 пикселей.
Переход из пространственной области f(x, y) в частотную g(u, v)
является отображением из множества целых чисел в множество вещественных чисел:

g(u, v) = T[f(x, y)].
(1.1)

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