Содержание к диссертации
Введение
ГЛАВА 1. Аналитический обзор 9
1.1 основные понятия 10
1.2 классы изображений 11
1.3 Критерий оценки алгоритмов 13
1.4 Приложения, использующие статическую графику 14
1.5 Особенности алгоритмов для статических изображений 17
1.6 Алгоритмы сжатия без потерь 19
1.6.1 Групповое кодирование 19
1.6.2 Алгоритм LZW. 19
1.6.3 Алгоритм Хаффмапа 20
1.6.4 Алгоритм JBIG 20
1.6.5 Lossless Jpeg 21
1.7 Алгоритмы сжатия с потерями 23
1.7.1 Рекурсивное сжатие 23
1.7.2 Алгоритм JPEG 23
1.7.3 Фрактальное Сжатие 25
1.8 Резюме по известным алгоритмам сжатия 27
1.10 Форматы представления цвета в динамических изображениях 28
1.11 Microsoft четырехсимвольный код (FOURCC) 31
1.12 Описание основных пршщипов кодирования динамических изображений на примере формата MPG 32
Выводы первой главы 36
ГЛАВА 2 Анализ цветоделения и цветопредставления в изображениях 37
2.1 Проблема цветоделения и выбора цветовой модели 37
2.2 Свети цвет 38
2.2.1 Визуальная система человека 39
2.3 Цветовые системы и модели 40
2.3.1 Цветовая модель CMYK 41
2.3.2 Цветовая модель Lab 43
2.3.3 Цветовая модель HSB. 44
2.3.4 Цветовая модель HLS 45
2.3.5 Цветовая модель YIQ 46
2.3.6 Цветовая модель UVW 47
2.3.7Преобразование RGB в YUV. 48
Выводы ВТОРОЙ ГЛАВЫ 51
ГЛАВА 3. Разработка методов и моделей технологии компрессии вариабельными фрагментами 52
3.1 Разработка общих принципов компрессии изображений вариабельными фрагментами 52
3.1.1 Определение максимального выигрыша при компрессии изображений . 53
3.1.3 Исследование особенностей технической реализации алгоритма компрессии вариабельными фрагментами 56
3.1.3 Анализ форматов файлов для хранения изображений 58
3.2 Разработка принципов компрессии статических изображений вариабельными фрагментами на основе (smart) технологий 66
3.2.1 Описание компрессии изображений на основе smart технологий 66
3.2.3 Формальная постановка задачи компрессии изображений. 67
3.2.4 Решение задачи компрессии изображения. 70
3.2.5 Решение задачи компрессии изображения (оптимизация по времени) 72
3.2.6 Дополнительные улучшения при компрессии изображений. 74
3.3 Разработка принципов компрессии динамических изображений вариабельными фрагментами 78
3.3.1 Разработка и анализ алгоритма алгоритма компрессии изображений. 78
3.3.3 Определение оптимального выигрыша при компрессии между сегментами видеоряда. 80
3.3.4 Определение оптимальной скважности при фиксированном значении качества воспроизводимого видеоизображения 81
3.3.5 Определение оптимальной скваоїсности при фиксированном значении степени сжатия 82
ГЛАВА 4. Экспериментальные исследования разработанных методов и моделей технологии компрессии изображений 86
4.1 Тестирование алгоритмов компрессии изображений 86
4.2 Тестирование cvf и jpeg алгоритмов 90
4.3 Особенности реализации программы vgf компрессор 93
4.4 Особенности реализации программы «vgf compessor-2» 95
Заключение '. 97
Литература
- Приложения, использующие статическую графику
- Визуальная система человека
- Определение максимального выигрыша при компрессии изображений
- Тестирование cvf и jpeg алгоритмов
Введение к работе
Изображение, которое воспринимает человек, может быть представлено набором точек, пикселей. Пиксели могут быть напечатаны на бумаге или других носителях, а также могут быть отображены на мониторе. Каждый пиксель обладает набором характеристик. В различных системах эти наборы могут быть различными, однако есть два наиболее известных - RGB и CMYK. RGB - Red (красный), Green (зеленый), Blue (синий). Эти цвета появляются в люминофорных слоях экрана компьютера при облучении люминофоров электронной пушкой монитора. Они используются для создания на экране аддитивной (слагательной) палитры. При печати изображения принтер использует другой метод - цветные чернила четырех основных цветов используются для получения субстрактивной цветовой палитры на бумаге. Аббревиатура из английских названий этих цветов и дала название другой системы - CMYK, Cyan (голубовато-зеленый), Magenta (пурпурный), Yellow (желтый) и Black (черный).
Для того чтобы, в изображении можно было передать достаточное количество цветов, под каждую составляющую цвета отводится много памяти. Например, при 24-битном представлении цвета на каждый пиксель отводится 24 бита - по 8 бит на красную, зеленую и синюю составляющие. Таким образом, можно передать до 2 24=16777216 цветов. Это, конечно, хорошо, однако изображения получаются очень большими и требуют для хранения значительных ресурсов ЭВМ. В связи с этим было разработано большое количество методов сжатия (компрессии) изображений. Наиболее распространенными из них являются GIF и JPEG. Они позволяют уменьшить размер изображения (в смысле объем памяти, необходимый для его хранения или пересылки), не существенно теряя при этом его качества. Формат GIF предназначен, в основном, для компрессии изображений, содержащих небольшое количество цветов и не имеющих плавных цветовых переходов. Обычно 7-Ю цветов вполне достаточно, чтобы представить такое
изображение. Если же нужно показать фотографию, то здесь уменьшение количества цветов нецелесообразно. Когда в изображении встречается плавный (градиентный) переход от одного цвета к другому, лучше всего сохранять изображение в формате JPEG.
Использование описанных выше методов компрессии, сокращая требования, предъявляемые к одному виду ресурсов ЭВМ - памяти, увеличивают требования к другому виду ресурсов - быстродействию процессора. Дело в том, что время декомпрессии (восстановления) сжатых изображений определяется в значительной мере степенью его сжатия и быстродействием процессора. Таким образом, актуальной остается задача поиска эффективных алгоритмов компрессии, адаптированных применительно к различным типам изображений.
Целью данной работы является разработка универсального алгоритма компрессии и декомпрессии, адаптирующегося к различного рода симметричным изображениям (например, рис. 1.1), а также разработка на его базе алгоритма компрессии динамических изображений.
Актуальность работы объясняется тем, что практически все
существующие методы сжатия ориентированны на компрессию несимметричных и мелкоформатных фотографий и «картинок», в то время как огромное количество изображений выпадает из установленных существующими алгоритмами правил компрессии. Ведь если присмотреться, можно заметить, что весь окружающий мир симметричен, включая самого человека. Прежде всего, это симметричные узорные изображения, использующиеся в легкой промышленности. Симметричные орнаменты и изображения используются в полиграфии, ковровом
производстве и т. д. (рис. 1.1). Более того, если речь идет о крупноформатных изображениях, таких как рекламные щиты и афиши (рис. 1.2), то и здесь стандартные методы не оптимальны. Это связанно, прежде всего, с тем, что к данным изображениям требуется совсем другой подход, основанный на внутрикадровом сегментировании с дальнейшей компрессией этих сегментов (фракталов). Однако простое фрактальное сжатие может так же завести в тупик. Все узоры разнообразны и поэтому к каждому изображению нужен "свой" подход, "своя" стратегия компрессии. То же самое можно сказать и о компрессии видео современные видеокодеки делятся на внутрикадровые и межкадровые, все действие которых сводится к машинальным сравнениям кадров и сегментов внутри кадров со строго определенной неизменяемой в процессе компрессии точностью.
Основной идеей диссертации является построение математических
моделей компрессии статических и
динамических изображений,
Рис. 1.2. Рекламный щит
обладающих различного рода симметрией (например, осевой или центральной) и использование этих моделей для создания эффективных алгоритмов компрессии такого рода изображений.
Научная новизна работы заключается в следующих результатах:
Разработан математический аппарат, позволяющий в априори оценить границы эффективности, предложенного алгоритма компрессии симметричных изображений.
Предложен новый подход к компрессии симметричных изображений, при котором алгоритм сам выбирает
оптимальную стратегию для сжатия того или иного изображения.
3. На базе предложенного подхода создан еще один алгоритм для
компрессии изображений, который займет ранее пустовавшую нишу, связанную с компрессией симметричных изображений.
Практическая значимость работы заключается в создании алгоритма и его программной реализации, позволяющей:
уменьшить объем и стоимость хранения баз данных,
содержащих орнаменты или узорные изображения путем
уменьшения занимаемого ими объема дискового пространства;
сократить время восстановления симметричных изображений,
причем качество хранящихся изображений будет на высоком
уровне.
Разработанные модели и алгоритмы не ограничиваются промышленной областью применения. Ряд наработок, касающихся методов сжатия и способов хранения изображений, можно использовать в учебном процессе в рамках дисциплин «Компьютерная графика» и «Мультимедиа системы».
В данной работе на защиту выносятся:
Классификация изображений (симметричные и ассиметричные, статические и динамичные и т.п.).
Алгоритмы компрессии симметричных изображений.
Аналитические методы оценки эффективности предложенных процедур компрессии изображений.
Программные средства поддержки предложенных алгоритмов.
Экспериментальные результаты оценки предложенных алгоритмов и реализующих их программных комплексов.
Апробация результатов работы.
Основные положения работы были доложены и обсуждались на
региональной научно-практической конференции "СОВРЕМЕННЫЕ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ОБРАЗОВАНИИ", (Владикавказ,
2001 г,) международной научно-технической конференции
«Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике», (Владикавказ, 2003 г.), ежегодных научно-технических конференциях СКГМИ (ГТУ), а так же на специализированых заседаниях кафедры «Автоматизированной обработки информации» с непосредственным участием в них ведущих специалистов кафедры. По результатам работы были усовершенствованы бры данных узорных орнаментов отдельных предприятий. Имеется акт внедрения программных пакетов, реализующих компрессию симметричных изображений, разработанную в диссертации. Так же в 2005 году работа была представлена на всероссийском конкурсе организованным компанией «Samsung», где заняла второе место в своей номинации и была отмечена дипломом.
По результатам выполненных исследований опубликовано 5 печатных работ.
Структура и объем работы
Диссертация состоит из введения, четырех глав, заключения и приложений. Объем диссертации 111 страниц, включает 32 рисунка, 6 таблиц, список литературы из 103 наименований.
Приложения, использующие статическую графику
Ниже анализируется, какими бывают приложения, использующие статическую графику и какие требования к алгоритмам компрессии они предъявляют [21-26].
1. Большое распространение сейчас получили издательские системы. Программы верстки типа PageMaker, QuarkXPress, MS WinWord есть на очень многих персональных компьютерах. В подобных системах приходится иметь дело с полноцветными изображениями самого разного размера (от 640x480 до 3000x2000) и с большими двухцветными изображениями. Поскольку иллюстрации занимают львиную долю от общего объема материала в документе, проблема хранения стоит очень остро. Изображение, соответствующее рекламной странице журнала, занимает до 20 Мб. А в номере их, естественно, несколько. Кроме того, немало могут занимать и иллюстрации к самим статьям. В результате средний журнал в 100 страниц может занимать больше 500 Мб. То же самое относится и к хорошо изданным книгам, буклетам, брошюрам...
У Проблемы также создает большая разнородность иллюстраций. Единственное, что можно сказать заранее, это то, что будут преобладать фотореалистичные изображения и деловая графика.
2. Другим примером являются справочники и энциклопедии на CD-ROM. С появлением большого количества компьютеров, оснащенных этим приводом (В США - у 50% машин) достаточно быстро сформировался рынок программ, выпускаемых на лазерных дисках. Несмотря на то, что емкость одного диска довольно велика (примерно 650 Мб), ее, как правило, не хватает. При создании энциклопедий и игр большую часть диска занимают статические изображения и видео. Таким образом, для этого класса приложений актуальность приобретают существенно асимметричные алгоритмы.
3. Похожие требования к алгоритмам архивации выдвигает и быстро развивающаяся система "Всемирная информационная паутина" - World Wide Web (WWW). В этой гипертекстовой системе достаточно активно используются иллюстрации. При оформлении информационных или рекламных страниц хочется сделать их более яркими и красочными. Больше всего при этом страдают пользователи, подключенные к сети с помощью медленных каналов связи. Если страница WWW перенасыщена графикой, то ожидание ее полного появления на экране может затянуться. Поскольку при этом нагрузка на процессор мала, то здесь могут найти применение эффективно сжимающие сложные алгоритмы со сравнительно большим временем разархивации.
4. Свое применение машинная графика находит и в различных информационных системах. Например, уже становится привычным исследовать ультразвуковые и рентгеновские снимки не на бумаге, а на экране монитора. Постепенно в электронный вид переводят и истории болезней. Понятно, что хранить эти материалы логичнее в единой картотеке. При этом без использования специальных алгоритмов большую часть архивов займут фотографии. Поэтому при создании эффективных алгоритмов решения этой задачи нужно учесть специфику рентгеновских снимков -преобладание размытых участков.
5. В геоинформационных системах - при хранении аэрофотоснимков местности - специфическими проблемами являются большой размер изображения и необходимость выборки лишь части изображения по требованию. Кроме того, может потребоваться масштабирование. Это неизбежно накладывает свои ограничения на алгоритм компрессии.
6. В электронных картотеках и досье различных служб для изображений характерно подобие между фотографиями в профиль, и подобие между фотографиями в фас, которое также необходимо учитывать при создании алгоритма архивации. Подобие между фотографиями наблюдается и в любых других специализированных справочниках. В качестве примера можно привести энциклопедии птиц или цветов. Однако там различие между рисунками значительно больше и использовать подобие сложнее.
Визуальная система человека
К наиболее важным структурным элементам на оптическом пути относятся: роговица, радужка, зрачок, хрусталик и сетчатка (ретина).
Сетчатка глаза содержит два принципиально различных типа светочувствительных фоторецепторов: цветочувствительные колбочки, сосредоточенные главным образом в центральной ямке, и расположенные в основном по периферии сетчатки палочки. Палочки не обладают преимущественной чувствительностью к какому-либо спектральному цвету и играют главную роль в создании ахроматических (т.е нецветных) зрительных образов.
Колбочки бывают трёх типов. Они отвечают за чувствительность к длинным, средним и коротким волнам. Три типа колбочек называют либо как В, G и R, либо как S, М и L. Пики их чувствительности приходятся примерно в среднем на 440 нм, 545 нм и 580 нм, причём наибольшая чувствительность приходится на синий цвет (440 нм), а наименьшая - на жёлто-зелёный (545 нм). В каждом глазу 6 млн колбочек и 120 млн палочек (т.е. примерно 250 млн рецепторов на два глаза). График кривой, отвечающей за общую чувствительность глаза к свету, получается в результате суммирования всех трёх кривых графиков чувствительностей для каждого типа колбочек.
В начале главы уже говорилось о стандартной модели кодирования цвета RGB. Помимо нее существует ряд других цветовых моделей. Модель RGB достаточно проста для технического представления, но не оптимальна. Человеческий глаз не способен различать все 256 оттенков красного, зеленого или синего цветов которые используются в данной модели, соответственно нет необходимость в поддержке такого количества цветов в ЭВМ. Более того, если речь идет о печати изображения, то такая схема абсолютно неприменима.
Цветовая модель CMYK в отличие от RGB описывает поглощаемые цвета. Цвета, которые используют белый свет, вычитая из него определённые участки спектра, называются субстрактивными (вычитательными). Именно такие цвета и используются в модели CMYK. Они получаются путём вычитания из белого аддитивных цветов модели RGB [79].
Голубой цвет получается путём вычитания из белого красного цвета, пурпурный - зелёного, жёлтый - синего. Эти соотношения можно представить в виде формулы С =1-R M = l-G Y= 1-В.
На рис.24, приведена схема аналогичная рис.2.2. Из неё видно, какие цвета получаются при смешении базовых в CMYK. Теперь при смешении всех трёх цветов получается чёрный цвет, т.е. сложение цветов в CMYK аддитивно. Графическое представление данной модели изображено на рис.2.5 . Цветовая модель CMYK является основной в полиграфии. В цветных принтерах также применяется данная модель [80,81].
Из неё следует, что для того, чтобы распечатать чёрный цвет, необходимо большое количество краски. Кроме того, смешение всех цветов модели CMYK на самом деле даёт не чёрный, а грязно-коричневый цвет. Поэтому, для усовершенствования модели CMYK, в неё был введён один дополнительный цвет - чёрный. Он является ключевым цветом при печати, поэтому последняя буква в названии модели - К (Key или ВІасК), а не В. Таким образом, модель CMYK является четырёхканальной. В этом заключается ещё одно её отличие от RGB.
Подводя итоги описанию цветовых моделей RGB и CMYK, надо сказать, что они являются аппаратно-зависимыми. Если речь идёт об RGB, то в зависимости от применённого в используемом мониторе люминофора будут разниться значения базовых цветов. Ещё хуже обстоит дело с CMYK. Здесь идёт речь о типографских красках, особенностях печатного процесса и носителя. Таким образом, одинаковое изображение может по-разному выглядеть на разной аппаратуре.
Определение максимального выигрыша при компрессии изображений
Изображение делится на квадратные фрагменты размерностью Х Х, после чего все фрагменты сравниваются друг с другом. В процессе сравнения фрагменты могут поворачиваться на углы 90, 180 и 270 градусов. Фрагмент представляет собой обыкновенную двумерную матрицу, где значения ячеек являются значениями цветов.
Создается массив позиций, в котором хранятся номера совпавших фрагментов, и массив поворотов, который хранит значения угла поворота фрагмента в данной позиции. После формирования массивов моделируется размер файла, если он "лучше" старого (т. е. обеспечивает более высокий уровень компрессии), то массивы и участвующие в них фрагменты сохраняются в памяти, а старые уничтожаются, в противном случае в памяти остаются старые массивы и фрагменты. Далее размер квадратного фрагмента увеличивается в два раза и проделываются те же самые действия. После того как перебор всех размерностей квадратных фрагментов Х Х бывает завершен (X принимает значения 8,16,32,64), формируется файл, содержащий только лучшие значениях[94].
Как было отмечено выше, изображение делится на квадратные фрагменты, размером X X. Ставится задача определить величину X, при которой качество сжатия будет максимальным. Когда речь касается изображений нельзя не отметить то, что в общем случае какого - то определенного алгоритма оптимизации здесь подобрать нельзя из-за полной хаотичности в цветовых палитрах и размерах изображений. В таких случаях имеет смысл обратиться к вероятностным подходам.
Далее для определения максимального выигрыша вводятся следующие обозначения: Q(x) - величина выигрыша, если фрагмент имеет размерность X. Р(Х) - вероятность выигрыша Q(X). Тогда средний выигрыш Д будет равен: P(X)Q(X) или, полагая X переменную X непрерывно меняющейся на заданном интервале, имеем: Д« \P{X)Q{X). (3.1) X
Полагая, что задача сводится к оценке максимального среднего выигрыша, можно для этой цели предложить систему вида: l\P(X)Q(X)dX- max Ус (3 2 [\P{X)dX = l Используя метод множителей Лагранжа, можно заменить решение системы (3.2) поиском экстремума функции [95]: ЦХ,Л) = \P{X)Q(X)dx + Л[\- \P(X)dXl (3.3) причем последнее достигается приравниванием нулю частных производных: — = P(X)Q(X) - Р{Х) Л = P{X)[Q{X) - Л] = 0; (3.4) оХ = \-\P(X)dX = 0 (3.5) Отсюда следует: Q(X) = Л (3.6)
Из (3.6) следует, что величина выигрыша не зависит от размера фрагмента X. Таким образом, в ходе реализации алгоритма нужно сравнить значения всех полученных выигрышей при различных размерах фрагментов. Существует только одно исключение: это ситуация, когда Р(х)=0, которая возникает в том случае, когда размер фрагмента больше половины размера изображения. В этом случае значение Q(x) считается худшим. Если при всех значениях X величина выигрыша Q(x) принимает плохое значение, то файл изображения не сжимается, сохраняет свой размер. В таких случаях рекомендуется поменять степень сжатия.
В начале раздела приводятся обозначения, используемые при пошаговом описании предлагаемого алгоритма, после чего следует описание самой процедуры компрессии вариабельными фрагментами X - размер одной стороны фрагмента в пикселях. Б- приемлемая погрешность при замене одного фрагмента другим.
Mas - массив позиций, содержащий информацию о номерах фрагментов, из которых будет состоять изображение. POV - массив поворотов, который содержит информацию об углах поворота каждого фрагмента в каждой фиксированной позиции.
Тестирование cvf и jpeg алгоритмов
Из графиков следует, что при работе с мелкими изображениями метод VGF менее эффективен, чем JPEG. Но при работе с изображениями, размер которых достаточно велик (рекламные щиты, большие киноафиши, вывески, плакаты и др.), в плане компрессии CVF превосходит JEPG [103].
Это все относилось к несимметричным изображениям, но как уже говорилось, лучшие свои результаты метод CVF показывает при работе с узорными изображениями. Как уже отмечалось, изначально метод разрабатывался именно для этого. В качестве оппонента при экспериментах с узорными изображениями снова использовался метод JPG. Алгоритм JPG является одним из лучших в мире при работе с несимметричными изображениями, но его работа с узорными изображениями оставляет желать лучшего. Пример изображения приведен на рисунке.
Казалось бы, на первый взгляд достаточно простое для компрессии изображение. Его размер составляет 320 320 пикселей при глубине цвета 16777215 цветов. Изначально размер несжатого изображения составил 307256 байт. Компрессор JPG сжал его в свой файл до размера 131451 байт. А компрессор CVF сжал изображение в файл размером 4390 байт. Таким образом, получилось, что CVF сжал изображение в 32 раза сильнее, чем JPEG, при отличном качестве картинки. Здесь ничего странного нет, JPEG изначально работает по своему алгоритму, который абсолютно не адаптирован к работе с орнаментными изображениями.
Таким образом, видно, что при работе с узорными изображениями JPEG остается верен себе, в отличие от метода компрессии изображений вариабельными фрагментами (CVF), который показал свои наилучшие качества. В принципе, при работе со статическими изображениями на этом месте можно было бы поставить точку, но есть и еще одно достоинство метода, над реализацией которого ведется сейчас работа. Это его приспособленность к работе с различными цифровыми палитрами, формирующими изображение. В разделе, посвященном формату файла, уже упоминалось о создании универсального формата, приспособленного для хранения изображений с различной глубиной цвета.
Приложением к работе является демонстрационная версия программы «VGF Компрессор». Эта программа позволяет сжимать стандартные bmp-файлы в файлы типа vgf. Основная цель данной программы, показать работу алгоритма на практике. Программа имеет достаточно простой и интуитивно понятный интерфейс.
Кнопка «открыть» позволяет загружать стандартные bmp-файлы и файлы имеющие расширение vgf (Variable Fragment Graphics). Кнопка «сохранить» осуществляет компрессию изображения. Сначала перед осуществлением компрессии появляется диалоговое окно, в котором нужно будет ввести имя файла, куда будут записываться сохраненные данные. Кнопка «Настройка» предназначена для изменения степени сжатия изображения. Т.е. здесь предлагается задать точность, согласно которой будут сравниваться между собой фрагменты.
Максимальная степень сжатия картинки достигается, когда допустимое отклонение, т.е. число не совпавших точек, равно 10%. При этом качество картинки бывает наихудшим. При допустимом отклонении равном 0, качество картинки остается неизменным. Но степень сжатия значительно уменьшается.
Пока в программе для хранения графических данных на носителях применяется стандартный формат vgf-файла. Скоро закончатся работы над внедрением в программный комплекс универсального vgf-формата. Данная программа является готовым образцом. Она предназначена для демонстрации основных возможностей компрессии изображений вариабельными фрагментами.
Отличие программы "VGF COMPRESSORS" от предшествующей версии заключается в реализации алгоритма многопоточной распределенной компрессии, а также реализации технологии Smart. В данной версии реализована возможность установки параметра "похожести" точек. Так же реализован ряд дополнительных функций, таких как горизонтальное и вертикальное отражение. Появилась возможность задавать набор используемых функций, значительно увеличивающая возможности алгоритма, как в плане скорости, так и в степени сжатия (см. рис.4.8).
