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

На правах рукописи

Д АД АЯН Л ЕВ ОН С ЕРГЕБВ ИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ТЕХНОЛОГ ИИ Б ЫСТРОЙ КОМПРЕССИИ ИЗОБ РАЖЕНИЙ ВАРИАБЕЛЬНЫМИ ФРАГМЕНТАМИ

Специальность 05.13.12 -" СИСТЕМЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ (промышленность)'

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

ООЗ173263

Владикавказ -2007

003173263

Работа выполнена на кафедре «Автоматизация и обработка информации» Северо - Кавказского Ордена Дружбы Народов Горно -Металлургического Института (Государственном технологическом университете)

Научный руководитель: дтнпроф ГроппенВ.О.

Официальные оппоненты: д т.н. проф. ХасцаевБ. Д.

к т н Куз нецов С. Н.

Ведущее предприятие: Институт прикладной математики и информатики

Владикавказского научного центра РАН и РСО-А

Защита диссертации состоится ноября 2007 г в часов

на заседании диссертационного совета Д212 246 01 Северо - Кавказского Ордена Дружбы Народов Горно - Металлургического Института (Государственном технологическом университете) по адресу 362021, РСО-Алания,г Владикавказ, ул Николаева 44, СКШИ (ГТУ)

С диссертацией можно ознакомиться в библиотеке СКГМИ (ГТУ)

Отзывы (в двух экземплярах, заверенные печатью) просим направлять по адресу 362021, Россия, PCO - Алания, г Владикавказ, ул. Николаева 44,Ученый Совет СКГМИ (ГТУ)

Автореферат разослан октября 2007 г

Ученый секретарь диссертационного совета д т н, доцент

Алексеев В П

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы обусловлена тем, что практически все существующие методы сжатия ориентированы на компрессию несимметричных и мелкоформатных фотографий и «картинок», в то время как обработка огромного количества изображений выпадает из установленных существующими алгоритмами правил компрессии

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

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

Научная новизна работы заключается в следующем:

1

Разработаны алгоритмы компрессии симметричных изображений

2.

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

3.

Разработана методика компрессии симметричных

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

Практическая значимость работы заключается в программной реализации разработанного алгоритма, позволяющей:

• уменьшить объем и стоимость хранения баз данных, содержащих орнаменты или узорные изображения, путем уменьшения занимаемого ими объема дискового пространства;

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

Разработанные программный комплекс, модели и алгоритмы внедрены на ОАО «Одежда» - экономический эффект составил 360 тысяч рублей в год, в продюсерском центре «Зебра» - эффект 400 тысяч рублей в год и в рекламном агентстве «Переход»- экономический эффект 600 тысяч рублей, для оптимизации и хранения архивов графической информации

Разработоки, касающихся методов сжатия и способов хранения изображений, используются в учебном процессе в рамках дисциплин «Компьютерная графика» и «Мультимедиа системы» Планом научно-исследовательских работ университета на 2008 год предусмотрено дальнейшее развитие этого направления применительно к использованию университетской неоднородной вычислительной сети с выделением на эти цели 1 млн. 400 тыс. рублей

Достоверность результатов подтверждается обоснованными теоретическими исследованиями на базе классических методов математики, а также положительными результатами внедрения в производство разработанного на основе предлагаемых методов программного обеспечения, результатами машинных экспериментов

На защиту выносятся следующие положения:

1. Классификация изображений (симметричные и ассиметричные, статические и динамичные и т.п.)

2. Алгоритмы компрессии симметричных изображений.

3 Математические методы оценки эффективности предложенных алгоритмов компрессии изображений.

4. Программные реализации предложенных алгоритмов компрессии

5. Экспериментальные результаты оценки предложенных алгоритмов и реализующих их программных комплексов

Апробация результатов работы.

Основные положения работы были доложены и обсуждались на региональной научно-практической конференции "СОВРЕМЕННЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ОБРАЗОВАНИИ", (Владикавказ, 2001 г,) международной научно-технической конференции

«Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике», (Владикавказ, 2003г.), ежегодных научно-технгических конференциях СКГМИ (ГТУ), а так же на специализированых заседаниях кафедры «Автоматизированной обработки информации» с непосредственным участием в них ведущих специалистов кафедры. По результатам работы были усовершенствованны базы данных узорных орнаментов отдельных предприятий. Имеются акты внедрения программных пакетов, реализующих компрессию симметричных изображений, разработанную в диссертации. Так же в 2005 году работа была представлена на международном конкурсе, организованном компанией «Samsung», где была отмечена дипломом 2-й степени

По результатам выполненных исследований опубликовано 4 печатных работ

Структура и объем работььДиссертация состоит из введения, четырех глав, заключения и приложений Объем диссертации -111 страниц, в том числе 31 рисунок, 6 таблиц, список литературы содержащий 103 наименования

СОДЕЖАНИЕ РАБОТЫ

В первой главе дан обзор литературы и проведен анализ современных методов компрессии изображений Рассмотрены основные классы изображений, типы алгоритмов компрессии, и проведено сравнение кодеков между собой.

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

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

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

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

Во второй главе рассматриваются формы цветопредставления Описываются отличия основных цветовых моделей Рассмотрена стандартная модель RGB, которая основана на слиянии трех цветов красного, зеленного и синего Обратная ей схема CMYK предназначенная для полиграфии Представлен подход со стороны физических особенностей зрения человека, в частности устройства глаза, где отмечено, что цвета воспринимаются человеком по-разному. Наибольшая чувствительность приходится на синий цвет, а наименьшая на жёлто-зелёный. Подробно описываются альтернативные RGB модели для получения адаптированных или предсказуемых цветов. Такие как LAB, HSB, HSL,YIQ,UVW, а так же способы перехода от одной цветовой модели к другой

Основой для создания цвета в ЭВМ, служит модель RGB, однако применяя ее в компрессии можно не получить ожидаемый результат, так данная модель достаточно контрастна Хотя использование других

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

Третья глава содержит описание алгоритмов комперссии симметричных изображений.

Изображение делится на квадратные фрагменты размером Х*Х, после чего все фрагменты сравниваются друг с другом. В процессе сравнения фрагменты могут поворачиваться на углы 90, 180 и 270 градусов. Фрагмент представляет собой обыкновенную двумерную матрицу, где значения ячеек являются значениями цветов.

Создается массив позиций, в котором хранятся номера совпавших фрагментов, и массив поворотов который хранит значения угла поворота фрагмента в данной позиции После формирования массивов моделируется размер файла если он "лучше" старого (т. е обеспечивает более высокий уровень компрессии), то массивы и участвующие в них фрагменты сохраняются в памяти, а старые уничтожаются, в противном случае в памяти остаются старые массивы и фрагменты Далее размер квадратного фрагмента увеличивается в два раза, и проделываются те же самые действия. После того как перебор всех размерностей квадратных фрагментов Х*Х бывает завершен, (X принимает значения 8,16,32,64), формируется файл, содержащий только лучшие значениях. Технические особенности реализации алгоритма компрессии вариабельными фрагментами. Так как компьютер использует адаптивную цветовую палитру, т е. цвет формируется в результате сложения трех основных цветов красного зеленого и синего, получается 16 миллионов различных оттенков, а точнее 16777216 цветов Таким

образом, получается, что при сравнении фрагментов для компрессии высококачественных изображений вероятность совпадения одноименных точек в изображении достаточно низка. Цветоразброс к-й (к е {К, G, В}) плоскости колеблется в диапазоне от 0 до 255, что значительно увеличивает шанс найти одинаковые точки, а, следовательно, и увеличить степень сжатия. Формально точки А и В считаются совпадающими, если справедливо:

тах {к, - к А2 < с]. где

k<={R,G,B}y Л а) 1

£", - допустимое несовпадение точек

Поэтому алгоритм сжатия вариабельными фрагментами применяется к каждой цветовой плоскости отдельно, (рис.1.)

М-

ZZIII2II :-----

11212ZZ2

ПП! а з1з зз

112~ZZ11

Рис.1. Иллюстрация работы алгоритма компрессии изображений

вариабельными фрагментами

В процессе сравнения фрагменты могут использовать

дополнительные преобразования.(повороты, отражение, фильтрацию)

Определение максимального выигрыша при компрессии изображений. Как было отмечено выше, изображение делится на квадратные фрагменты, размером X * X. Ставится задача определить величину X, при которой степень сжатия будет максимальной Следует отметить, что из-за хаотичности в цветовых палитрах и размерах предложить один универсальный алгоритм компрессии изображений нельзя. В этом случае имеет смысл обратиться к вероятностным подходам. Введем следующие обозначения х- Размер фрагмента Q(x) — величина выигрыша Р(х) — вероятность выигрыша Q(x)

Тогда Д= X?(I)Ö(I)

х

где А- средний выигрыш

Полагая, что переменная х непрерывно меняется на заданном интервале, в нашем случае: А « ^P(X)Q(X)dX

X

задача заключается в максимизации среднего выигрыша, аналитическая постановка задачи имеет вид

—> max

" X

\P{X)dX = 1

Решение задачи дает результат Q(X) - Const (1)

Из (1) следует, что величина выигрыша не зависит от размера фрагмента х. Таким образом, в ходе реализации алгоритма нужно сравнить значения всех полученных выигрышей при различных размерах фрагментов. Существует только одно исключение, когда Р(х)=0, которая

возникает в том случае, когда размер фрагмента больше

половины размера изображения В этом случае значение Q(x) считается худшим Если при всех значениях X величина выигрыша принимает Q(x) плохое значение, то файл изображения не сжимается, а остается старый В таких случаях рекомендуется поменять степень сжатия. Компрессия статических изображений вариабельными фрагментами (smart). Модель, о которой говорилось ранее, является достаточно мощной в плане компрессии, но не оптимальной Фактически она сводит поиск базового подмножества фрагментов, двигаясь от первого, к поиску на соседних планах Однако такой подход не дает глобально-оптимального решения, так как не предусмотрен выбор другого стартового сегмента, отличного от первого. В этом разделе раскрывается более мощный и оптимальный математический аппарат для компрессии изображений базирующийся на элементах теории графов, использующий оптимальную стратегию при выборе "похожих" сегментов. Описание метода

Изображение состоит из Р числа пикселей, а его область разбита на n-е количество сегментов, количество пикселей в каждом сегменте

Р

соответственно равно —; Сегменты считаются "похожими", если число

п

не совпадающих точек у них не превысит значение "s" Соответствующие пиксели у сравниваемых сегментов являются «похожими», если разница в их цветовой величине не превышает "£2". После компрессии, файл содержащий данные об изображении должен содержать только "непохожие" опорные сегменты и информацию об их размещении в матрице изображения. Отсюда следует утверждение, чем меньше количество опорных сегментов в файле в котором хранится сжатое изображение, тем больше степень сжатия этого изображения

Фактически формируются две задачи, которые позволят "сжать"

изображение с лучшими характеристиками:

1 Определение минимального количества опорных фрагментов из которых будет состоять «сжатое» изображение при их фиксированной размерности

2 Определение оптимальной размерности фрагментов, из которых будет состоять изображение

Формальная постановка задачи

Формально можно заменить изображение графом С(Х,и), где его

вершинами будут являться фрагменты, на которые разбито изображение Каждый фрагмент изображения соответствует вершине, принадлежащей неориентированному графу С(Х,и), где X - множество вершин, и -множество ребер Таким образом, если фрагменты похожи, то межу соответствующими им вершинами есть связь — ребро, если нет, то соединения между ними нет. Следовательно, задача сводится к нахождению Х1 минимального количества вершин соответствующего следующим условиям

• Подмножество Х1 содержит только вершины - эталоны, для любой пары этих вершин, не существует соединений ребрами в наборе и, т.е. справедливо

V/ Ф у, Ух, еХ, : (/, у) ё £/,;

• для любой вершины х, принадлежащий подмножеству Х2 =Х\Хь есть по крайней мере одно соединение с вершиной подмножества Хь

• |Х,| —»тт.

Формальная постановка задачи совпадает с задачей о покрытии

вершин графа: на графе G(X,U) требуется выделить суграф G(X,U'), Х= Xi+X2, такой, что:

| Xj | —> min;

•Vx7eX2:| (J(M)|>1; (2)

l

Vjc, g X^VXj g Xx : (г,у) <£ U\

Другими словами для каждого фиксированного значения "п", решение заключается в выборе минимального покрывающего подмножества вершин в графе G(X, U)

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

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

Рис.2. Представление ряда кадров как одно изображение Фактически задача сводится к нахождению максимального выигрыша в статическом изображении, о котором говорилось выше. Определение оптимальных выигрышей при компрессии между сегментами видеоряда. В зависимости от частоты повторения опорного кадра (кадра, относительно которого происходит сжатие внутри принадлежащего ему сегмента) можно получать различные значения степени компрессии изображения Р, а также его качества О- Ставится задача нахождения оптимальных значений вышеуказанных величин. Введем следующие обозначения:

у- скважность (количество опорных кадров, относительно которых происходит сжатие внутри принадлежащего ему сегменту);

Р — степень сжатия; характеризуется суммой параметров ^ а:у';

а.1 - параметр, определяющий степень сжатия между сегментами внутри одного кадра,

ат параметр, определяющий степень сжатия между кадрами; С> - качество изображений; характеризуется суммой параметров-

оо>;го/ "

Ь| - параметр, определяющий несоответствие фрагментов внутри одного кадра;

Ь2- параметр, определяющий несовпадения между кадрами В первом приближении, обозначая Ьх + Ь2 как Ь[, и ограничивая двумя число слагаемых, характеризующих качество изображения, можно сформулировать как задачу оптимизации по Парето'

- ^ а У тах;

оо>1^0

1>/>о/ У

Оптимальная скважность при фиксированном значении качества.

Чтобы избежать минусов, присущих оптимизации по Парето, ниже ставится задача при фиксированном качестве изображения ()ф максимизировать степень сжатия Формально, если число слагаемых в обоих функционалах цели в системе (3) не превышает двух, она преобразуется к виду:

^ = ау + а2у —> шах 1

Решением является у... =шах{1; --—}.

О» ~ЬУ

(5)

Оптимальная скважность при фиксированном значении степени сжатия.

Пусть теперь ставится задача при фиксированном значении степени сжатия максимизировать качество изображений.

{Э = ЬХ +——>тах;

у ил

' ах+а2у>Рб (6)

у>1

Ре ~а\

Т о оптимальная скважность уПо = тах{1,-}. (7)

а2

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

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

В четвертой главе описывается экспериментальная часть исследований, на основе теоретических расчетов, которые проходили по средствам цифрового эмулирования. Результаты были достаточно стабильные. Вероятности использования фрагментов разной размерности были примерно одинаковы, причем размер фрагмента X мог принимать значения: 4;8,16;32;64;128.

Эмуляция подтвердила разработанную модель (1);

Но теоретические расчеты не включали в себя «затраты» на цветоделение изображения и формирование файла.

___

¡ЗШВМ

-ч. '

-.4x4

- 8x8 16x16

~ 32x32 -64x64

- 128x128

126x128 256x256 ЗЮХ240 320x320 512x512 640x460 1024x768

Рис.3. Вероятность использования фрагментов

Цифровой эмулятор представлял собой двухмерную матрицу, элементам которой присваивались значения посредствам использования рандомизированных, симметричных алгоритмов. Это позволяло имитировать орнаменты. Значения элементов колебались в диапазоне от 0 до 255.

Для данного эксперимента было проведено 700 эмуляций, что составило во временном периоде две недели. Из графика на рисунке 3 видно, что при использовании «маленьких» изображений доминируют фрагменты малой размерности, однако с увеличением размеров изображений ситуация выравнивается, и вероятности выбора фрагментов усредняется. Уже при эмуляции стало очевидно, что использование фрагментов X с размерами 128 * 128 не эффективно. Изображение должно быть обязательно кратно размеру фрагмента. Иначе оно автоматически округляется до кратного, отбрасывая «лишние» точки. При использовании X = 128 пикселей, максимальное число отброшенных

точек может составить 126, в среднем, обращая внимание на то,

что в большинстве случаев размеры изображений колеблются в интервале от 128 * 128 до 1600 *1200 точек, это Ул

Рис. 4. Потери при преобразовании часть изображения. Таким образом, получается, что в среднем выбрасывается четверть изображения.

До появления экспериментальной модели программы компрессора накопилось уже достаточное количество опыта. Программа получила название «VGF Компрессор». Написана данная программа в среде Delphi, что дает ей дополнительный «балласт» в плане медленности, но о самой программе будет сказано позже.

100

128 256 320 320

х х х х 128 256 240 320

512 640 1024

XXX 512 480 768

Рис. 5. Вероятность использования фрагментов разной размерности в результате работы программы

После написания этой экспериментальной программы появилась возможность работать с настоящими изображениями. Ниже приведен график вероятности выбора фрагментов.

Сразу заметно, что количество размеров, которые может принимать X, сократилось с 6 до 4. Размерность 128*128 не используется в связи с вышесказанными в теоретической части эксперимента причинами Так же исчезла размерность 4*4. Причиной послужил массив позиций vgf-файла. Для хранения фрагмента 4*4 требуется 48 байтов, а на его описание в массиве уходит 9 байтов. Получается, что при работе с большими изображениями потратится больше памяти для описания массива позиций фрагментов, чем для самих фрагментов

Непосредственно, что касается самих экспериментов, за основной алгоритм с которым проводилось сравнение, был выбран алгоритм компрессии JEPG

Для небольшого ознакомления ниже представлены основные его особенности. Тестирование cvf и jpeg алгоритмов В результате тестирования алгоритмов CVF и JPEG при работе с несимметричными изображениями, была получена следующая зависимость, при работе с мелкими изображениями метод менее эффективен, чем JPEG. Но при работе с изображениями, размер которых достаточно велик (рекламные щиты, большие киноафиши, вывески, плакаты и др ), в плане компрессии CVF превосходит JEPG.

Это все относилось к несимметричным изображениям, но как уже говорилось, лучшие свои результаты метод CVF показывает при работе с узорными изображениями Как уже отмечалось, изначально метод разрабатывался именно для этого. В качестве оппонента при экспериментах с узорными изображениями снова использовался метод JPG. Алгоритм JPG является одним из лучших в мире, при работе с

несимметричными изображениями, но его работа с узорными изображениями оставляет желать лучшего Таким образом, видно, (рис.6.) что при работе с узорными изображениями JPEG остается верен себе, в отличие от метода компрессии изображений вариабельными фрагментами (CVF), который показал свои наилучшие качества Есть еще одно достоинство метода, над реализацией которого ведется сейчас работа Это его приспособленность к работе с различными цифровыми палитрами, формирующими изображение.

Рис 7 Сравнительная эффективность алгоритмов JPG и CVF применительно к симметричным изображениям.

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

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

1 Алгоритмы для компрессии статических изображений, а так же был создан алгоритм для компрессии видео

Алгоритм cvf

Алгоритм jpg

Размер изображения

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

3. Методика компрессии симметричных изображений, при которой реализуется технология SMART- алгоритм автоматически выбирает оптимальную стратегию для сжатия того или иного изображения.

По каждому из направлений исследований были получены высокие результаты:

1. Границы эффективности алгоритмов были существенно расширены. Разработанные алгоритмы доказывают свое преимущество при работе с симметричными изображениями Тестирование алгоритма компрессии на несимметричных образах, показало сопоставимость результатов с результатами мировыми аналогов

2. Разработанная методика компрессии позволяет создавать алгоритмы реализующие различные стратегии компрессии: Быстрая компрессия - в данном алгоритме производилась оптимизация по времени, те основной уклон делался на скорость сжатия картинки. В данной стратегии применяются два метода Детерминированная компрессия- позволяет вбирать определенный режим быстрой компрессии Рандомизированная компрессия - в данном методе выбор режима осуществляется случайно Оптимальная компрессия - основной задачей является обеспечение высокой степени сжатия изображений

3. Алгоритмы компрессии для статических изображений были реализованы в программах для ЭВМ. «VGF compressor» и «VGF compressor-2». Разработанное программное обеспечение внедрено ОАО «Одежда» - экономический эффект составил 360 тысяч рублей в

год, продюсерский центр «Зебра» - эффект 400 тысяч рублей в год, рекламное агентство «Переход» - экономический эффект 600 тысяч рублей.

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

Публикации. По теме диссертации опубликованы работы

1. Дадаян JI.C Технология компрессии изображений переменной размерности (вариабельными фрагментами) // Вестник СевероКавказского государственного технического университета. № 2 2007. - г Ставрополь: Издательство ГОУВПО «Северо-Кавказский государственный технический университет», 2007. С35-39

2. Дадаян J1.C Компрессия вариабельными фрагментами // СКГТУ: сборник статей аспирантов г.Владикавказ- издательство «Терек», 2001. С. 169-172.

3. Дадаян Л С Технология сжатия видеорядов вариабельными фрагментами //Информационные технологии и системы . Материалы международной конференции г.Владикавказ: Издательство ВНЦ, 2002. С 282-286

4 Дадаян Л С. Экспериментальный анализ сравнительной эффективности различных методов компрессии статических изображений //Новые информационные технологии в науке, образовании, экономике: Материалы международной конференции, г Владикавказ. Издательство «Терек», 2002 С 96-97

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР.

1.1 Основные понятия.

1.2 Классы изоБРАЖЕшш.

1.3 Критерии оценки алгоритмов.

Изображение, которое воспринимает человек, может быть представлено набором точек, пикселей. Пиксели могут быть напечатаны на бумаге или других носителях, а также могут быть отображены на мониторе. Каждый пиксель обладает набором характеристик. В различных системах эти наборы могут быть различными, однако есть два наиболее известных - RGB и CMYK. RGB - Red (красный), Green (зеленый), Blue (синий). Эти цвета появляются в люминофорных слоях экрана компьютера при облучении люминофоров электронной пушкой монитора. Они используются для создания на экране аддитивной (слагательной) палитры. При печати изображения принтер использует другой метод - цветные чернила четырех основных цветов используются для получения субстрактивной цветовой палитры на бумаге. Аббревиатура из английских названий этих цветов и дала название другой системы - CMYK, Cyan (голубовато-зеленый), Magenta (пурпурный), Yellow (желтый) и Black (черный).

Для того чтобы, в изображении можно было передать достаточное количество цветов, под каждую составляющую цвета отводится много памяти. Например, при 24-битном представлении цвета на каждый пиксель отводится 24 бита - по 8 бит на красную, зеленую и синюю составляющие. Таким образом, можно передать до 224=16777216 цветов. Это, конечно, хорошо, однако изображения получаются очень большими и требуют для хранения значительных ресурсов ЭВМ. В связи с этим было разработано большое количество методов сжатия (компрессии) изображений. Наиболее распространенными из них являются GIF и JPEG. Они позволяют уменьшить размер изображения (в смысле объем памяти, необходимый для его хранения или пересылки), не существенно теряя при этом его качества. Формат GIF предназначен, в основном, для компрессии изображений, содержащих небольшое количество цветов и не имеющих плавных цветовых переходов. Обычно 7-10 цветов вполне достаточно, чтобы представить такое изображение. Если же нужно показать фотографию, то здесь уменьшение количества цветов нецелесообразно. Когда в изображении встречается плавный (градиентный) переход от одного цвета к другому, лучше всего сохранять изображение в формате JPEG.

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

Целью данной работы является разработка универсального алгоритма компрессии и декомпрессии, адаптирующегося к различного рода симметричным изображениям (например, рис. 1.1), а также разработка на его базе алгоритма компрессии динамических изображений.

Актуальность работы объясняется тем, что практически все существующие методы сжатия ориентированны на компрессию несимметричных и мелкоформатных фотографий и «картинок», в то время как огромное количество изображений выпадает из установленных существующими алгоритмами правил компрессии. Ведь если присмотреться, можно заметить, что весь окружающий мир симметричен, включая самого человека. Прежде всего, это симметричные узорные изображения, использующиеся в легкой промышленности. Симметричные орнаменты и изображения используются в полиграфии, ковровом

Рис. 1.1. Клпппимй ппнямс'нт производстве и т. д. (рис. 1.1). Более того, если речь идет о крупноформатных изображениях, таких как рекламные щиты и афиши (рис. 1.2), то и здесь стандартные методы не оптимальны. Это связанно, прежде всего, с тем, что к данным изображениям требуется совсем другой подход, основанный на внутрикадровом сегментировании с дальнейшей компрессией этих сегментов (фракталов). Однако простое фрактальное сжатие может так же завести в тупик. Все узоры разнообразны и поэтому к каждому изображению нужен "свой" подход, "своя" стратегия компрессии. То же самое можно сказать и о компрессии видео современные видеокодеки делятся на внутрикадровые и межкадровые, все действие которых сводится к машинальным сравнениям кадров и сегментов внутри кадров со строго определенной неизменяемой в процессе компрессии точностью.

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

Рис. 1.2. Рекламный щит

Научная новизна работы заключается в следующих результатах:

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

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

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

Практическая значимость работы заключается в создании алгоритма и его программной реализации, позволяющей:

• уменьшить объем и стоимость хранения баз данных, содержащих орнаменты или узорные изображения путем уменьшения занимаемого ими объема дискового пространства;

• сократить время восстановления симметричных изображений, причем качество хранящихся изображений будет на высоком уровне.

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

В данной работе на защиту выносятся:

1. Классификация изображений (симметричные и ассиметричные, статические и динамичные и т.п.).

2. Алгоритмы компрессии симметричных изображений.

3. Аналитические методы оценки эффективности предложенных процедур компрессии изображений.

4. Программные средства поддержки предложенных алгоритмов.

5. Экспериментальные результаты оценки предложенных алгоритмов и реализующих их программных комплексов.

Апробация результатов работы.

Основные положения работы были доложены и обсуждались на региональной научно-практической конференции "СОВРЕМЕННЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ОБРАЗОВАНИИ", (Владикавказ, 2001 г,) международной научно-технической конференции

Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике», (Владикавказ, 2003г.), ежегодных научно-технических конференциях СКГМИ (ГТУ), а так же на специализированых заседаниях кафедры «Автоматизированной обработки информации» с непосредственным участием в них ведущих специалистов кафедры. По результатам работы были усовершенствованы бры данных узорных орнаментов отдельных предприятий. Имеется акт внедрения программных пакетов, реализующих компрессию симметричных изображений, разработанную в диссертации. Так же в 2005 году работа была представлена на всероссийском конкурсе организованным компанией «Samsung», где заняла второе место в своей номинации и была отмечена дипломом.

По результатам выполненных исследований опубликовано 5 печатных работ. Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и приложений. Объем диссертации 111 страниц, включает 32 рисунка, 6 таблиц, список литературы из 103 наименований.

Выводы по третей главе.

1. Исследованы общие принципы компрессии изображений вариабельными фрагментами для статических и динамических изображений.

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

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

4. Разработанные модели позволяют осуществлять компрессию изображений, как с потерей, так и без потерь качества воспроизводимых изображений.

Глава 4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ МЕТОДОВ И МОДЕЛЕЙ ТЕХНОЛОГИИ КОМПРЕССИИ ИЗОБРАЖЕНИЙ.

4.1 ТЕСТИРОВАНИЕ АЛГОРИТМОВ КОМПРЕССИИ ИЗОБРАЖЕНИЙ.

На основании теоретических расчетов, которые проводились при использовании цифровых эмуляций изображений. Были получены достаточно стабильные результаты. Вероятности использования фрагментов разной размерности были примерно одинаковы, причем размер фрагмента X мог принимать значения: 4;8;16;32;64;128. В прицепе эмуляция подтвердила разработанную модель:

P(X)Q(X)dX ^ max; ]p{X)dX = \. где после решения системы получается, что Q(X) = A Но теоретические расчеты не включали в себя «затраты» на цветоделение изображения и формирование файла.

126*128 К*2Ж 320x340 32U32D 5t2x5G 6в*«0 «Е4*та

Рисунок 4.1. Графики зависимостей вероятностей

НГПАПиППЯИНЯ ЛшЯГМРНТПП ПТ ПДЧНПИ ПЯ1МРПНПГТ11

Цифровой эмулятор представлял собой двухмерную матрицу, элементам которой присваивались значения посредствам использования рендомизированных, симметричных алгоритмов. Это позволяло имитировать орнаменты. Значения элементов колебались в диапазоне от 0 до 255.

Для данного эксперимента было проведено 700 эмуляций, что составило во временном периоде две недели.

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

Уже при эмуляции стало очевидно, что использование фрагментов X равными 128 * 128 точек не эффективно. Изображение должно быть обязательно кратно размеру фрагмента, если это не происходит, то оно автоматически округляется до кратного, отбрасывая «лишние» точки. При использовании X = 128 пикселей, максимальное число отброшенных точек может составить 126, в среднем, обращая внимание на то, что в большинстве случаев размеры изображений колеблются в интервале от 128 * 128 до 1600 * 1200 точек.

После

О:

Рисунок 4.2. Иллюстрация потери при преобразовании

Это 1А часть изображения. Таким образом, получается, что в среднем выбрасывается четверть изображения.

До округления

CD

До появления экспериментальной модели программы компрессора накопилось уже достаточное количество опыта. Программа получила название «VGF Компрессор». Написана данная программа в среде Delphi, что дает ей дополнительный «балласт» в плане медленности, но о самой программе будет сказано позже. После написания этой экспериментальной программы появилась возможность работать с настоящими изображениями. Ниже приведены графики вероятности выбора фрагментов.

Вероятность выбора фрагментов различной размерности

100 80 60 40 20 0

128 256 320 320 512 640 1024

X X X X X X X

128 256 240 320 512 480 768

-♦-8x8 -■-16x16 32 х32 64 х 64

Рисунок 4.3. Вероятности использования фрагментов разной размерности в результате работы программы

Сразу заметно, что количество размеров, которые может принимать X, сократилось с 6 до 4. Размерность 128*128 не используется в связи с вышесказанными в теоретической части эксперимента причинами. Так же исчезла размерность 4*4. Причиной послужил массив позиций vgf-файла. Для хранения фрагмента 4*4 требуется 48 байтов, а на его описание в массиве уходит 9 байтов. Получается, что при работе с большими изображениями потратится больше памяти для описания массива позиций фрагментов, чем для самих фрагментов. Непосредственно, что касается самих экспериментов, то за основной алгоритм, с которым проводилось сравнение, был выбран алгоритм компрессии JEPG. Для небольшого ознакомления ниже представлены основные его особенности.

4.2 ТЕСТИРОВАНИЕ CVF И JPEG АЛГОРИТМОВ

В результате тестирования алгоритмов CVF и JPEG при работе с несимметричными изображениями были получены следующая зависимости:

АЛГОРИТМ CVF

•АЛГОРИТМ JPG

РАЗМЕР ИЗОБРАЖЕНИЯ

Рисунок 4.4. Сравнение эффективности алгоритмов JPG и CVF применительно к несимметричным изображениям.

Из графиков следует, что при работе с мелкими изображениями метод VGF менее эффективен, чем JPEG. Но при работе с изображениями, размер которых достаточно велик (рекламные щиты, большие киноафиши, вывески, плакаты и др.), в плане компрессии CVF превосходит JEPG [103].

Это все относилось к несимметричным изображениям, но как уже говорилось, лучшие свои результаты метод CVF показывает при работе с узорными изображениями. Как уже отмечалось, изначально метод разрабатывался именно для этого. В качестве оппонента при экспериментах с узорными изображениями снова использовался метод JPG. Алгоритм JPG является одним из лучших в мире при работе с несимметричными изображениями, но его работа с узорными изображениями оставляет желать лучшего. Пример изображения приведен на рисунке. ооооооооооооооооосоооосооооозосооооооооо ооооаоооооооооозоооооооооооооооооооооооа оеоооооооооосооооооооосооооовассоэоооооо ооооооооаоэоозосооэоэооэээоооэоооээосооо еСОООЗОООООСОООООСОООССООСОООООООООООООО еооазовоэооооозоооооооооозоооэооооаооаоо ооооммавеоооооосооооооооооооооооаооооо ооооооосзоосоооооооооооозооооооооооооооо оеоэаоооавввооаооооооссооеооэвооеэоооооо

ОООООООООООООООеООООООеООООООООООООООСОО оооэооооооооооэээоэзэоезэсооээзооэоооооо

ООООЗОООООСООООООСЭЭСООООСОСОССОСООООеОЭ ооооооооооооозоооооооооозэооооооооэооооэ оооооооооозсоооэосоосооэзоесозооозоооооо ООООООООООООООООСОЭв000305 0003 00 000 00000 оооооооооооооооооооооооооооооооооооооооо оооооооооооооооооооооооэоооооооаоооооооо оооооооо00ооооооооо00ооооооооооооооооооо

ОООООООООООООООООООО00ООООО0000ОООООО0 0 оооооооооооооооooooooooооооооооооооооооa ооооовоеовоооООООООООООООООООООООО00000о ОООООООООО000000000000000000О0000ООООООо ООООООООООООООООООООООООООООООООООООООО^ ОООООвОООООООООООООООООО0000000000оооооо юооооооооооооооооооооооооооооооооооооооо оооооооооооооооооооооооооооооооооооооооо ооооооооооооооооооооооооооооаооооооооооо ОООООООООООООООООООООООООООООООООООООООо ОООООООО00ООООООООО00000ОООООООООООООООО ОООООООООООООООООООООООООООООООООООООООО оооооооооэоооооооооооооазоооооооооооооао оооооооооооооооооооооооооооооооооооооооо оооооооооооооееоооооооооовооооооооооееав ©оооооооовововвовооооосозооооооовооооооо 0000ОООО00ОOGOOQО00О00ОООООСОООООООООО00 оооооооооооооооооооооооооооооооооооооооо оооооооооооооооооооооооооооооооооооооооо оооооооооооооооооооооооооооооооооооооооо

ООООООООООООО00000ООООООООООООООО0000000

Рисунок 4.5. Пример изображения с лучшими показателями компрессии

Казалось бы, на первый взгляд достаточно простое для компрессии изображение. Его размер составляет 320 * 320 пикселей при глубине цвегга 16777215 цветов. Изначально размер несжатого изображения составил 307256 байт. Компрессор JPG сжал его в свой файл до размера 131451 байт, А компрессор CVF сжал изображение в файл размером 4390 байт. Таким образом, получилось, что CVF сжал изображение в 32 раза сильнее, чем JPEG, при отличном качестве картинки. Здесь ничего странного нет, JPEG изначально работает по своему алгоритму, который абсолютно не адаптирован к работе с орнаментными изображениями.

АЛГОРИТМ CVF

АЛГОРИТМ JPG

РАЗМЕР ИЗОБРАЖЕНИЯ

Рисунок 4.6. Сравнительная эффективность алгоритмов JPG и CVF применительно к симметричным изображениям.

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

4.3 ОСОБЕННОСТИ РЕАЛИЗАЦИИ ПРОГРАММЫ VGF

КОМПРЕССОР

ЗАКЛЮЧЕНИЕ

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

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

2. Новый подход к компрессии симметричных изображений при котором реализуется технология SMART- самостоятельно выбирается оптимальная стратегия для сжатия того или иного изображения.

3. На базе предложенного подхода было создано несколько алгоритмов для компрессии статических изображений, а также был создан алгоритм для компрессии видео.

По каждому из этих направлений исследований были получены следующие результаты.

1. Границы эффективности алгоритмов были существенно расширены; Разработанные алгоритмы доказывают свое преимущество в работе с симметричными изображениями. Более того, после тестирования алгоритма компрессии на не симметричных образах результаты были сопоставимы с мировыми аналогами.

2. Новый подход к компрессии позволил создать ряд алгоритмов реализующих различные стратегии компрессии: «быстрая компрессия» - производящая оптимизацию по времени, т.е. обеспечивающая сжатие картинки с максимальной скоростью. В данной стратегии исследованы два метода. Детерминированная компрессия - позволяющая вбирать определенный режим быстрой компрессии и рандомизированная компрессия - осуществляющая выбор режима случайно. Оптимальная компрессия - производящая компрессию изображений с высокой степенью сжатия изображений.

3. Алгоритмы компрессии для статических изображений были реализованы в программах для ЭВМ: «VGF compressor» и «VGF compressor-2». Данные программы нашли применения в производстве. В частности имеется акт внедрения от ОАО «Одежда». К исследованиям и алгоритмам по компрессии видео проявляет интерес компания Samsung, отметившая эти исследования отмечены дипломом второй степени.

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

1. B.Smith, L.Rowe. "Algorithm for manipulating compressed images", Computer Graphics and applications, September 1993.

2. R.W.McColl, G.R.Martin. "Compression of color image data usinf histogram analysis and clustering techniques". Electronics & communication engineering journal, March / April 1989.

3. Престон К. Сравнение аналоговых и цифровых методов распознавания образов //ТИИЭР. 1972. - Т.60. - №10. - С.141-160.

4. Розенфельд А. Распознавание и обработка изображений с помощью вычислительных машин. М.: Мир, 1972. - С. 16-144.

5. Вапник В.Н., Червоненкис А Я. Теория распознавания образов. М.: Наука, 1974,- С.34-156.

6. Хуан Т., Шрейбер В., Третьяк О. Обработка изображений // ТИИЭР. -1971. Т.59. -№11. - С.59-89.

7. Васильев В., Гуров И. Компьютерная обработка сигналов в приложении к интерферометрическим системам. СПб: БХВ, 1998.

8. Либенсон М.Н., Хесин А.Я., Янсон Б.А. Автоматизация распознавания телевизионных изображений. М.: Энергия, 1975. - С.50-128.

9. Горьян И.С. О распознавании текстур // Вопросы радиоэлектроники. Сер. Т.Т., 1968. Вып.1. - С.82-89.

10. Ю.Гуревич С.Б., Соклов В.К. Оптические методы обработки информации. В кн. Оптические методы обработки информации. Л.: Наука, 1974. -С. 5-25.

11. П.Крупицкий Э.И., Смирнов А.Я., Эмдин B.C. Сравнение эффективности аналоговых оптических процессоров для обработки изображений с ЦВМ // Межведомственный сборник "Повышение эффективности и надежности РЭС" / ЛЭТИ. Л., 1976.- Вып. 4.- С. 69-73.

12. A. Jacquin, "Fractal image coding based on a theory of iterated contractive image transformations", Visual Comm. and Image Processing, v. SPIE-1360, 1990.

13. Julia Neumann Gabriele Steidl "Dual Tree Complex Wavelet Transform in the Frequency Domain and an Application to Signal Classification". Technical Report TR-03-013, Department for Mathematics and Computer Science, University of Mannheim, 2003.

14. H.Miroslav Vrankic, Damir Sersic "Image Denoising Based on Adaptive Quincunx Wavelets". In Proc. of the 2004 IEEE 6th Workshop on Multimedia Signal Processing, (MMSP 2004), Siena, Italy, September 29 -October 01, 2004, pp. 251-254.

15. Vladan Velisavljevic, Baltasar Beferull-Lozanol, Martin Vetterli, Pier Luigi Dragotti "Discrete Multi-Directional Wavelet Bases". Proc. IEEE International Conference of Image Processing (ICIP2003).

16. Felix C. A. Fernandes, Rutger L. van Spaendonck, C. Sidney Burrus "A Directional, Shift-Insensitive, Low-Redundancy, Wavelet Transform". IEEE Proceedings on International Conference on Image Processing (ICIP2001).

17. Daubechies "Ten Lectures on Wavelets", Philadelphia: SIAM, 1992.

18. S. Mallat "A wavelet tour of signal processing", Academic Press, London, 1998.

19. Д. Ватолин, А. Ратушняк, M. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". Диалог-МИФИ, 2002.

20. Generic coding of moving pictures and associated audio information: Video. ISO/IEC 13818-2:2000.

21. Рейнбоу В. Компьютерная графика. Энциклопедия. СПб: Издательский дом "Питер", 2003.

22. Мураховский В.И. Компьютерная графика: Популярная энциклопедия.

23. Дедков В. Adobe Photoshop. Настольная книга мастера. М.: Компьютер-пресс, 2001.

24. Миронов Д. Ф. CorelDRAW 12. Учебный курс. СПб: Издательство Питер, 2004.

25. Базылев Г. В. Photoshop CS. Самоучитель. М.: Вильяме, 2005. Хатсон Ш. Photoshop для Web-дизайна. -М.: КУДИЦ-Образ, 2006.

26. Донни О'Квин. Допечатная подготовка. Руководство дизайнера. М.: Вильяме, 2002.

27. Y. Fisher, "Fractal image compression", Siggraph'92.28."Progressive Bi-level Image Compression, Revision 4.1", ISO/IEC JTC1/SC2/WG9, CD 11544, September 16, 1991.

28. W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, R.B. Arps, "An overview of the basic principles of the Q-coder adaptive binary arithmetic coder", IBM Journal of research and development, Vol.32, No.6, November 1988, pp. 771-726. ?

29. Szymon Graboskwi, Wojciech Bienieck "A two-pass median-like filter for impulse noise removal in multi-channel images". KOSYR 2003, str. 195-200

30. Richard Alan Peters II "A New Algorithm for Image Noise Reduction using Mathematical Morphology". IEEE Transactions on Image Processing, Volume 4, Number 3, pp. 554-568, May 1995.

31. G. de Haan, T. G. Kwaaitaal-Spassova and O.A. Ojo "Automatic 2-D and 3D noise filtering for high-quality television receivers". International Workshop on HDTV'94,4-B-2,1994-10.

32. R. J. Schutten, G. de Haan and A. H. M. van Roermund "Noise filtering for television receivers with reduced memory". Proc. of the Int. Workshop on

33. HDTV and the Evolution of Television, Taipei, Taiwan, Nov. 1995, pp. 6A15--6A22.

34. G. de Haan, T.G. Kwaaitaal-Spassova, M.M. Larragy, O.A. Ojo, and R.J. Schutten "Television noise reduction 1С". Digest of the ICCE'96, June 1996, Chicago, pp. 184-185.

35. Hakan Norell, Bengt Oelmann and Youshi Xu "Spatio-Temporal Noise Reduction ASIC for Real-Time Video Processing". In Proc. IEEE Nordic Signal Processing Symposium, Kolmarden, Sweden, 13-15 June, 2000

36. D.A. Huffman, "A method for the construction of minimum redundancy codes." In processing. IRE vol.40,1962, pp. 1098-1101.

37. Standartization of Group 3 Facsimile apparatus for document transmission, CCITT Recomendations, Fascicle V1I.2, T.4.1980.

38. S.G. Chang, B. Yu, and M. Vetterli, "Spatially adaptive wavelet thresholding with context modeling for image denoising". IEEE Trans. Image Proc., Sept. 2000.

39. Aleksandra Pizurica, Vladimir Zlokolica and Wilfried Philips "Noise Reduction in Video Sequences Using Wavelet-Domain and Temporal Filtering". SPIE Conference on Wavelet Applications in Industrial Processing 27-31 October 2003.

40. Aleksandra Pizurica and Wilfried Philips "Adaptive Probabilistic Wavelet Shrinkage for Image Denoising". IEEE Transactions on Image Processing, July 11,2003.

41. Aleksandra Pizurica, Vladimir Zlokolica and Wilfried Philips "Combined Wavelet Domain and Temporal Video Denoising". IEEE Conference on Advanced Video and Signal Based Surveillance (AVSS'03), July 2003.

42. Lindsay I Smith "A tutorial on Principal Components Analysis". 2002)

43. D. Darian Muresan, Thomas W. Parks "Adaptive principal components and image denoising". IEEE ICIP 2003.

44. Ivan W. Selesnick and Ke Yong Li "Video denoising using 2D and 3D dual-tree complex wavelet transforms". Appl Signal Image Proc. X (Proc. SPIE 5207), Aug 2003.

45. S.W.Golomb. Run-length encodings. IEEE Trans. Inform. Theory, pp. 399401, 1966.

46. Lossless data compression. Recommendation for space data systems standards. CCSDS 121.0-B-l, Issue 1, 1997.

47. R.F. Rice, Some Practical Universal Noiseless Coding Techniques, Jet Propulsion Laboratory, JPL Publication 79-22, Pasadena, California Mar 1979.

48. P.-S. Yeh, W.Serafino, L. Miles, B.Kobler, D.Menasce. Implementation of CCSDS lossless data compression in HDF. Proc. Of NASA ESTO Conf. 2002, Pasadena,CA, June 11-13,2002.

49. Jagger D. 1989. Fast Ziv-Lempel decoding using RISC architecture. Res.Rept.,Dept.of Computer Science, Univ.of Canterbury, New Zealand.

50. Gallager R.G. 1978. Variations on a theme by Huffman. IEEE Trans.Inf.Theory IT-24, 6(Nov.),668-674. Presents an adaptive Huffman coding algorithm, and derives new bound on the redundancy of Huffman codes.

51. Huffman D.A. 1952. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40,9(Sept.),pp. 1098-1101. The classic paper in which Huffman introduced his famous coding method.

52. ISO DIS 11544, Joint Bi-level Image Expert Group (JBIG).

53. ISO DIS 10918-1,2, Joint Photographic Expert Group (JPEG).

54. Формат JPEG "Открытые системы сегодня", #8(29), 1995

55. G.K. Wallace. "The JPEG still picture compression standard". Communication of ACM, Volume 34, Number 4, April 1991.

56. M. Ali, T. G. Clarkson, Fractal image compression, Proc. 1st Seminar on Information Technology and its Applications (ITA'91), Markfield Conf. Centre, Leicester, U.K., 29 Sept., 1991.

57. M. Ali, C. Papadopoulos, T. G. Clarkson, The use of fractal theory in a video compression system, in Proc. IEEE Data Compression Conference (DCC92), 24-27 March, 1992

58. M. Ali, T. G. Clarkson,Using linear fractal interpolation functions to compress video images, Fractals 2,3 (1994) 417-421.

59. Au, О. C., Liou, M. L., Ma, L. K., Fast fractal encoding in frequency domain,in Proc. IEEE ICIP-97, Santa Barbara, Oct. 97.

60. Z. Baharav, D. Malah, E. Karnin, Hierarchical interpretation of fractal image coding and its applications to fast decoding,Intl. Conf. on Digital Signal Processing, Cyprus, 1993 ;

61. N. T. Thao, Local search fractal image compression for fast integrated implementation,in Proc. ISCAS'97 International Symposium on Circuits and Systems,Hong Kong, June. 1997.

62. M. Breazu, G. Toderean, Region-based fractal image compression using deterministic search, IEEE ICIP 98, Chicago, Oct. 1998.

63. Liou Ming. Overview of the px64 kbit/s video coding standart. Communication of ACM. Vol 34. N.4 April 1991.

64. John F. McGowan, AVI Overview, Ph.D. (c) 1996-2004, http://www.jmcgowan.com/.

65. Coding of moving pictures and associated audio. Committee Draft of Standart ISOl 1172: ISO/MPEG 90/176 Dec. 1990.

66. Д. Ватолин, MPEG стандарт ISO на видео в системах мультимедиа, "Открытые системы", #3,1995.

67. MPEG proposal package description. Document ISO/WG8/MPEG 89/128 (July 1989).

68. Coding of moving pictures and associated audio. Committee Draft of Standart ISOl 1172: ISO/MPEG 90/176 Dec. 1990.

69. D.S Wallach, S Kunapalli, M.F Cohen. Accelerated MPEG compression of Dynamic poligonal scenes ACM Jun 1994.

70. Le Gall D.A. MPEG: a video compression standart for multimedia applications. Communication of ACM. Volume 34. Number 4. April 1991

71. Шлихт Г. Ю. Цифровая обработка цветных изображений. — М.: ЭКОМ, 1997.

72. М.Е.Шарыгин Сканеры и цифровые камеры.74.3айцев А. С. Наука о цвете и живопись. М.: Искусство, 1986. - 158 с.

73. Ивенс Р.-М. Введение в теорию цвета. М.: Мир, 1964. - 227 с.

74. Вотяков Е. И. Свет и цвет. Перевод гл. 2 из кн. Eliott S., Miller P. Inside 3D Studio MAX. vol. 1. Indiana: New Riders Pulishing, 1996. '

75. Chui С. K. An introduction to wavelets San Diego, CA, USA: Academic Press Professional, Inc., 1992.

76. CIE. Colorimetiy. official recommendation of the international commission on illumination: Tech. Rep. 15.2 Vienna, Austria: Bureau Central de la CIE, 1986

77. Ярославский JT. П. Введение в цифровую обработку изображений М.: Сов. радио, 1979.

78. Кирант М., «Лекарство от цветового удара», Publish №1 1999 г.

79. Уманский С.Д, , «Полиграфические цветоделители и работа на них», Москва «Книга», 1980 г.

80. Фокин А.О., Заботин Ю.Д. Компьютерная графика с программой ХагаХ. М.: Майор, 2003 - 192 с.

81. Залогова Л.А. Практикум по компьютерной графике. М.: Лаборатория базовых знаний, 2001.

82. Бурлаков М. Эффекты в программах растровой графики. М.:Биная, 2000. - 496с.: ил.

83. У.Прэтт Цифровая обработка изображений.-В 2-х книгах.-М.:"Мир", 1982.

84. Майкл Ласло. "Вычислительная геометрия и компьютерная графика на С++."Пер. с англ. М.: "Издательство БИНОМ", 1997.

85. Васильев В.Н., Гуров И.П. Компьютерная обработка сигналов в приложении к интерферометрическим системам. СПб.: БХВ - Санкт-Петербург, 1998.

86. Цифровая обработка телевизионных и компьютерных изображений / Под ред. Ю.Б.Зубарева и В.П.Дворковича. Международный Центр научной и технической информации, 1997.

87. Птачек М. Цифровое телевидение: Теория и техника / Пер. с чеш. под ред. Л.С.Виленчика. М.: Радио и связь, 1990.

88. Новаковский С.В., Котельников А.В. Новые системы телевидения. Цифровые методы обработки видеосигналов. М.: Радио и связь, 1992

89. Rao K.R, J.J. Hwang Techniques and Standards for Image Video and Audio Coding.//Prentice Hall PTR, 1996.

90. ISO/IEC 11172 Information technology Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s - Part 1: Systems, Part 2: Video, Part 3 Audio.

91. ISO/IEC 13818 Information Technology Generic Coding of Moving Pictures and Associated Audio - Part 1: Systems, Part 2: Video, Part 3 Audio.

92. Дадаян Л.С. «Компрессия вариабельными фрагментами» V/ СКГТУ сборник статей аспирантов г.Владикавказ 2001г. издательство «Терек» с 169-172.

93. Гроппен В.О. « Принципы Оптимизации программного обеспечения» издательство Ростовского университета, Ростов на дону 1993г.

94. Кристофидес Н. Теория графов, алгоритмический подход Мир, 1978.

95. Белявцев В. Г. Адаптивные нелинейные алгоритмы локальной фильтрации векторных сигналов и изображений: Дис. канд. техн. наук:05.13.16.-Новосибирск,2000.-120.

96. Горелик В. А., Кулясов С. М. Локально-несмещенная фильтрация изображений.

97. Белявцев В.Г., Воскобойников Ю.Е. «Алгоритмы фильтрации изображений с адаптацией размеров апертуры» // Автометрия. 1998. -№ 3.- С. 18-25.

98. Павлидис Т. «Алгоритмы машинной графики и обработки изображений». М.: «Радио и связь». - 1986. - 400с.

99. Дадаян J1.C. Технология сжатия видеорядов вариабельными фрагментами. //Информационные технологии и системы : Наука и Практика (материалы международной конференции) г.Владикавказ издательство Владикавказского научного центра 2002г, с 282-286.