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

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

СОКОЛОВА ЕКАТЕРИНА АНДРЕЕВНА

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ КОМПРЕССИИ СТАТИЧНЫХ ИЗОБРАЖЕНИЙ

Специальность 05.13.12 - «Системы автоматизации проектирования (промышленность) по техническим наукам»

АВТОРЕФЕРАТ

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

003452778

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

003452778

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

Научный руководитель: д-р техн. наук, проф.

Гроппен Виталий Оскарович

Официальные оппопенты: д-р техн. наук, проф.

Мустафаев Гасан Абакарович

канд. физ.-мат. наук Цопанов Игорь Дзастемирович

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

информатики Владикавказского

научного центра РАН и правительства PCO - Алания»

Защита диссертации состоится 5 декабря в 15:00 часов на заседании диссертационного совета Д 212.246.01 при Северо - Кавказском Горно - Металлургическом Институте (Государственном технологическом университете) по адресу: 362021, PCO - Алания, г. Владикавказ, ул. Николаева 44, СКГМИ (ГТУ). Факс: (8672) 407-203, E-mail: skgtu@skgtu.ru

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

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

Автореферат разослан «3» ноября 2008 г.

Ученый секретарь

диссертационного совета

Д 212.246.01, к.т.н., доцент (^jß^^T Аликов А.Ю.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

- бортовые системы фотографирования поверхности Земли;

- спутниковые системы получения метеоснимков;

-медицинские базы данных, хранящие диагностические снимки;

- фотографии;

- результаты томографических исследований;

-охранные системы видеоиаблгадения с возможностью видеорегистрации.

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

Работа проведена в соответствии с планом научно-исследовательских работ Северо-Кавказского горнометаллургического института (государственного технологического университета).

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Произвести анализ современных требований к алгоритмам сжатия с потерями и без потерь. Для этого необходимо:

- выполнить обзор теории представления графической информации в цифровом виде и алгоритмов ее компрессии;

- изучить требования к алгоритмам сжатия графической информации;

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

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

- оптимизировать выбор минимального подмножества фрагментов при компрессии изображений с поиском глобально-оптимального решения, применяя полный перебор в графе;

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

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

3. Экспериментально доказать, что результаты компрессии разработанного автором алгоритма сжатия SCI превосходят результаты сжатия алгоритмами JPEG и TIFF;

Для этого необходимо:

- произвести сравнительный анализ экспериментальных исследований, применения алгоритма сжатия sei при компрессии двуцветных, 16-ти цветных и полноцветных типов изображений;

- произвести исследование и систематизировать результаты критериального анализа компрессии при применении алгоритмов сжатия без потерь;

- произвести исследование и систематизировать результаты критериального анализа компрессии при применении алгоритмов сжатия с потерями.

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

Применялись лабораторные и экспериментальные исследования, обработка и систематизация данных с использованием ЭВМ.

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

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

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

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

4. Предложена и реализована оригинальная методика декомпрессии алгоритма сжатия SCI, которая позволяет сократить время декомпрессии, и не зависит от размеров открываемого файла.

Научная новизна подтверждается получением патента РФ №2007129867/09(032526) и двух свидетельств официальной регистрации программы для ЭВМ №2007610600, №2007613948.

Практическое значение работы. Разработанные и предложенные способы и методики алгоритмов компрессии и декомпрессии статичных изображений обеспечивают получение стабильных результатов, позволяют повысить эффективность сжатия по сравнению с известными программными продуктами для хранения и передачи изображений. Применение полученных алгоритмов сжатия изображений возможно для широкого класса систем хранения и передачи визуальной информации, прежде всего, в мультимедийных и сетевых компьютерных приложениях. Разработанные алгоритмы обладают высокими характеристиками по скорости, качеству обработки и сжатия данных, которые соответствуют современному мировому уровню. Практическая ценность работы заключается во внедрении программного продукта в пакетах программ графических баз и данных УГМК Холдинг на ОАО «Электроцинк». Технико-экономическая эффективность предложенных методик и рекомендаций заключается в сокращении объема информационных файлов при их передаче и хранении, благодаря увеличенной эффективности алгоритма компресс™. В частности, сокращение среднегодовых затрат на приобретение цифровых носителей, расходование средств на оплату услуг связи при передаче и хранении информации сокращается на 11%, вследствие увеличения эффективности компрессии изображений.

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

Основные научные положения, которые выносятся на защиту:

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

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

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

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

5.Применение алгоритма сжатия sei, эффективного при компрессии двуцветных , 16-ти цветных и полноцветных типов изображений.

6. Определение классов изображений, для которых результаты компрессии разработанного автором алгоритма сжатия SCI превосходят результаты сжатия алгоритмами JPEG и TIFF.

Апробация исследований. Основные результаты работы обсуждались на X Международном конгрессе (г. Нальчик , КБГУ), Всероссийских конференциях в г. Нальчик «Перспектива» в 2004 и 2006г. и Международной научно - технической конференции, г. Владикавказ, 2008 г.

Публикации. Основные положения диссертации опубликованы в 13 работах, в том числе две статьи в рецензируемых журналах из перечня ВАК, один патент РФ и два свидетельства об официальной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, 3 глав, заключения, библиографического списка из 125 наименований, 13 приложений, содержит 118 стр. машинописного текста, 43 рисунка и 31 таблицу.

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

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

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

Также рассмотрен ряд вопросов, посвященных современному состоянию проблемы компрессии изображений в российской и зарубежной науке. В этой области известны работы Y. Fisher, D.A. Huffman, Д.Ватолина и др.

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

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

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

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

Используются следующие обозначения и допущения:

V/ - число пикселей, принадлежащих каждому квадратному фрагменту изображения, на которые можно его разделить;

Ъ - общее число фрагментов изображения;

Б - время оперативного сравнения мощности текущего сочетания вершин графа,

О - время проверки на достижимость всех вершин графа;

11(10) ~ интенсивность красного цвета ¡-го пикселя ]-го фрагмента изображения;

С(д) - интенсивность зеленого цвета 1-го пикселя _|-го фрагмента изображения;

В(у) - интенсивность голубого цвета ¡-го пикселя ]-го фрагмента изображения;

й(Х,и) - ориентированный граф, вершины которого соответствуют фрагментам изображения и существует дуга (у) множества и, если ¡-й фрагмент можно с помощью заданного множества процедур преобразовать в _]-й с заданной точностью е;

Хх € X - подмножество вершин множества X, соответствующих тем фрагментам изображения, на основании которых могут быть восстановлены другие фрагменты, которым отвечают вершины подмножества Х\Х1;

Хх <= Хх - подмножество вершин множества, соответствующих тем фрагментам изображения, которые выбраны для восстановления всех фрагментов, отвечающих вершинам подмножест-

шХ\(Х\\}Х\)-,

Х2 6 X - подмножество терминальных вершин множества X, соответствующих тем фрагментам изображения, на основании которых не могут быть восстановлены никакие фрагменты;

Х2 £ X2 — подмножество вершин множества Х2, в которые не

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

-й путь на С(Х,и), идущий из х(. е Х\Х2 в

хкеХ\Х'2;

(.1 - допустимое отклонение в цветопередаче одного пикселя: если ¡-й пиксель .¡-го фрагмента и р-й пиксель к-го фрагмента изображения;

У(],к) - множество несовпадающих одноименных пикселей ]-го и к-го фрагментов изображения;

к1- объем памяти для хранения одного пикселя; к2~ объем памяти для хранения одной дуги; I, - время компрессии изображения;

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

\уим

ведливо неравенство: 1 —-I < е Ж

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

Шаг 1 .Величине V присваивается бесконечно большое значение. Шаг 2.Выбирается новый, ранее не рассматривавшийся размер квадратного фрагмента, на которые можно разделить изображение. Если таковых нет, то перейти к шагу 11, иначе - к шагу 3.

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

ляемым множеством ф. Если в ходе сравнений некоторый .¡-й фрагмент с заданной точностью е совпадает с одной из модификаций к-го базового фрагмента, т.е. ^ < £ то это означает, что он может быть IV

заменен соответствующей модификацией базового фрагмента.

Шаг 4. Решается оптимизационная задача, которая в графовой интерпретации называется задачей о минимальном покрытии: на множестве вершин X графа С(Х,11) соседства фрагментов изображения требуется выделить минимальное подмножество покрывающих вершин

Х1 € А', таких, что:

в из них достижимы все остальные вершины множества

Х^^и^г) по ДУгам множества и, т.е. справедливо условие:

е X1 (Х\ и б Х\: (1,]) е Ц;

» х[и х'2\-> пип.

Учитывая, что для любого конкретного графа С(Х,11) мощность X, = СОГШ, формальная постановка этой задачи как экстремальной задачи с булевыми переменными имеет вид:

р1 = Х'2 + £ £ z(j,k), ^ шш;

\/хкеХ\(Х;их'2): £ г(у'Д)>1; У2(уД)€С/:г(/,/) = I.

На множестве вершин графа выбирается ранее не просмотренное сочетание вершин, перейти к шагу 5. При отсутствии таковых перейти к шагу 2.

Шаг. 5. Производится проверка мощности текущего сочетания вершин графа. Если текущая мощность больше существующей, перейти к следующему шагу, иначе перейти к шагу 4.

Шаг 6. Проверяется возможность достижения всех вершин графа. При достижении всех вершин графа перейти к шагу 7, иначе к шагу 4.

Шаг 7. Создается массив позиций, в котором хранятся номера совпавших фрагментов, и массив функций, являвшихся компонентами множества ср, использовавшихся при модификации каждого выбранного базового фрагмента. Суммарный объем памяти, требуемой для хранения минимального подмножества базовых фрагментов, массива позиций и массива функций обозначается 0.

Шаг 8. Если С? < V, то перейти к следующему шагу, в противном случае - к шагу 2.

Шаг 9. Величине V присвоить значение, равное

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

Шаг 11. Конец алгоритма.

Можно увеличить степень компрессии изображения, заменив модель оптимизации, использующую систему (1), следующей:

рг=Х'г + X 52п £ ^(Л к), Рг шш;

У20\к)еи-.2(и) = 1.

Связь между системами (1) и (2) определяется теоремой 1: Теорема 1. Р1>Е2. Доказательство теоремы 1.

Поскольку целевые функции систем (1) и (2) совпадают, для доказательства теоремы достаточно показать, что оптимальное решение (1) является допустимым решением системы (2).

Допустим, что это не так, т.е. существует хотя бы одна вершина

хк е X \ fX¡ U X-,) такая, что справедливо:

1; (3)

1 IZ П z(P'd)- 0. №

j^Vj h (p,d)eLh(j,k)

Рисунок 1 - Блок-схема алгоритма

Очевидна противоречивость полученной системы (3)-(4): неравенство свидетельствует о наличии не менее одной выбранной дуги, идущей из одной из вершин подмножества Хх е Х^ в вершину хк е X \ (Х1 и Х2), в то время как равенство говорит об отсутствии пути, состоящего из выбранных дуг, ведущего из одной из вершин подмножестваХ1 в вершину хк е X \ (Х1[] Х2). Но любая дуга,

удовлетворяющая (3), является путем такого рода, следовательно сделанное допущение неверно.

Теорема доказана.

Для учета возможных погрешностей при сравнении пикселей и фрагментов вводятся:

ц - допустимое отклонение в цветопередаче одного пикселя: если ¡-й пиксель .¡-го фрагмента и р-й пиксель к-го фрагмента изображения;

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

\УиМ

ведливо неравенство: 1———1 < Е, (5)

Формальная постановка задачи с учетом погрешностей имеет следующий вид:

I ,58п I , -(¡,к)->т\п;

х хкеХ\(Х\Ш'г>

^хк^х\(х[\}х2),\У0.Щ: II П Ф.Ф>\;

х И (р.Ф^'Ом

У/еВД: (6)

14т^т)г+[сеч>-о(ик)г+№№№г >и 100 , У0,к)еи:2(ч)=\.

Для расчета верхней границы времени работы алгоритма до пустим, что результат будет достигнут лишь на последней итерации, тогда максимальное время работы алгоритма V считается по формуле(7):

F. =(IC>iö = i2'iiö=(2VIo = iß

1 = 0 1 = 1 1 = 0 1 = 1 ( = 1 1=1 ^У)

Нижняя граница времени работы алгоритма при полном переборе

на графе будет в случае, если первое сочетание вершин на графе ока-

жется глобально-оптимальным решением (8).

На основе предложенной методики сжатия и последующего построения изображения, которая позволяет учитывать возможные погрешности при сравнении фрагментов изображений, автором разработана и предложена программа компрессии изображений вариабельными фрагментами (свидетельство об официальной регистрации программы для ЭВМ №2007610600).

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

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

1) двуцветные изображения;

2) 16-цветные изображения;

3) полноцветные изображения.

размер файла, Мб 250

-JPEG

-BMP

.SCI

двуцветные \ 16-тицветныЬ полноцветные

Рисунок 2 - Изменение эффективности сжатия двуцветных, 16-ти цветных и полноцветных изображений.

Кроме того, была предложена градация изображений в зависимости от их симметричности и степени заполнения:

а) симметричные изображения с центральной либо осевой симметрией (орнаменты, мозаика и т.д.);

б) несимметричные изображения (фотографии, цветные картинки);

в) фоновые изображения со сравнительно маленьким рисунком.

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

Для проведения эксперимента были взяты изображения формата bmp размером 256*256 пикселей.

С использованием программы сжатия изображений SCI производилась компрессия изображений для получения файла формата sei.

Для проведения сравнительного анализа были взяты также изображения, сжатые форматами jpeg и tiff.

Эксперимент проводился на ЭВМ, обладающей следующими ха-рактеристиками:1ВМ РС-совмест. ПК. Р4 2,00 , 512 Mb, 40Gb.

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

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

Оптимальным решением будет являться такая размерность фрагмента, при которой максимально число совпадений при минимальном объеме фрагментов, хранящихся в памяти. Кривая z показывает обратную зависимость размерности от занимаемого фрагментом объема. Кривая w иллюстрирует прямую зависимость размерности фрагмента от количества совпадений. Точка пересечения кривой г и кривой w будет являться оптимальной величиной размерности.

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

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

Количество

Рисунок 3 - График поиска оптимального размера фрагмента

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

Рисунок 4 - Зависимость времени компрессии от размера фрагмента

Как видно из рисунков 3 и 4, качество сжатого изображения и степень сжатия зависят от выбора размерности вариабельного фрагмента, которая будет оптимальной как по времени (скорость) компрессии, так и по размеру сжатого изображения.

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

Результаты сравнительного анализа алгоритмов сжатия изображений приведены в таблице 1.

Таблица 1-Сравнительный анализ алгоритмов сжатия.

Алгоритм Коэффициенты сжатия Симметричность по времени На что ориентирован Потери качества

Групповое кодирование 1/32 1/2 2/1 1 3,4 битные Нет

LZW 1/100 1/4 7/5 1.2-3 1-8 битные Нет

Хаффмана 1/8 2/3 1/1 1-1.5 1-битные Нет

JB1G 1.5 раза -1 1-битные Нет

Lossless JPEG 2 раза ~1 24-битн. сер. Нет

Рекурсивное сжатие 2-20 раз 1.5 Серые Да

JPEG 2-200 раз ~1 24-битн. сер. Да

Фрактальный 2-2000 раз 1000-10000 24-битн. сер. Да

SCI 0.9-60 раз 1-1.5 24-битн. Да

ЗАКЛЮЧЕНИЕ

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

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

По итогам работы сделаны следующие выводы и даны рекомендации:

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

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

3) разработана и предложена программа компрессии изображений вариабельными фрагментами;

4) проведено исследование и систематизация результатов критериального анализа компрессии при применении алгоритмов сжатия без потерь и с потерями;

5) экспериментально доказано, что применение алгоритма сжатия SCI эффективно при компрессии двуцветных, 16-ти цветных и полноцветных типов изображений и не имеет существенных различий;

6) определены классы изображений, для которых результаты компрессии разработанного автором алгоритма сжатия SCI превосходят результаты сжатия алгоритмами JPEG и TIFF;

7) произведено внедрение программного продукта в пакетах программ графических баз и данных УГМК Холдинг на ОАО «Электроцинк».

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

1. Соколова Е.А. К проблеме повышения эффективности компрессии изображений. Безопасность информационных технологий, Министерство образования и науки РФ, МИФИ, ВНИИПТИ, 2008, № 2 , с.57-60.

2. Соколова Е.А., Компрессия изображения вариабельными фрагментами: модель, алгоритм, интерфейс, эксперимент. Вестник компьютерных и информационных технологий, №10, с.31-34.

3. Соколова Е.А. Эффективная оценка компрессии изображений вариабельными фрагментами. Перспектива - 2007: Материалы международного конгресса студентов аспирантов и молодых ученых.- Нальчик: Каб.- Балк. ун.-т, 2007 ,с. 200-201.

4. Гроппен В.О., Проскурин А.Е., Соколова Е.А. Способ компрессии и декомпрессии статических изображений и видеоинформации в цифровой форме. Патент РФ №2007129867/09(032526)

5. Гроппен В.О., Соколова Е.А. Разработка сжатия изображения методом вариабельных фрагментов, Научный потенциал студенчества - будущему России / Материалы Всероссийской научной студенческой конференции. Ставрополь: СевКавГТУ, 2006. с. 212

6. Проскурин А.Е., Соколова Е.А. Поиск оптимального решения при использовании метода вариабельных фрагментов. Перспектива -2006: Материалы Всероссийской научной конференции студентов аспирантов и молодых ученых.- Нальчик: Каб.- Балк. ун.-т, 2006 с. 260261.

7. Гроппен В.О., Проскурин А.Е., Соколова Е.А. Программа компрессии изображений (SCI - Smart compression of images)\\ Свид-во об офиц. регистрации программы для ЭВМ № 2007610600 РФ/Роспатент.- №2006614251;заявл. 11.12.06; зарег в Реестре программ для ЭВМ 07.02.07.

8. Соколова Е.А. Анализ алгоритмов сжатия и оценка их эффективности. Материалы 6-ой международной конференции "Инноваци-

онные технологии для устойчивого развития горных терригорий".-Владикавказ,28-30 мая 2007, с.710-711,

9. Гроппен В.О., Проскурин А.Е., Соколова Е.А. Программа компрессии видеоизображений (SCIV - Smart compression of video) Свид-во об офиц. регистрации программы для ЭВМ № 2007613948 РФ/Роспатент.- № 2007613109;заявл. 26.07.07; зарег в Реестре программ для ЭВМ 14.09.07.

10. Мамонтов Д.В.,Соколова Е.А Алгоритм поиска пути в двумерном и трехмерном массивах. Перспектива - 2004: Материалы Всероссийской научной конференции студентов аспирантов и молодых ученых.- Нальчик: Каб.- Балк. ун.-т, 2004,с.210-212.

11. Соколова Е.А., Определение параметров быстродействия алгоритма компрессии статичных изображений. Перспектива - 2008: Материалы международной научной конференции молодых ученых, аспирантов и студентов,- Нальчик: Каб.- Балк. ун.-т, 2008,с. 143-147.

12. Соколова Е.А., Математическая модель компрессии статичных изображений вариабельными фрагментами с учетом погрешностей. Деп. в ВИНИТИ 19.07.07. № 748-В2007, указатель № 9, 12 с

13. Соколова Е.А., Гречаный C.B., Компрессия динамических изображений вариабельными фрагментами: модель, алгоритм, интерфейс, эксперимент. Материалы международной научно - технической конференции ИТ - технологии: Развитие и предложения./Сев. - кавказский горно- металлургии, ин-т (гос. техн. ун-т). СКГМИ (ГТУ); Инт теоретической и прикладной информатики (ИТПИ) - Владикавказ, с. 64-73.

Сдано в набор 23.10.08г., подписано в печать 29.10.08г. Гарнитура Тайме. Печать трафаретная. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ №210.

Типография ООО НПКП «МАВР», Лицензия Серия ПД №01107, 362040, г. Владикавказ, ул. Августовских событий, 8, тел. 44-19-31

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИТИЧЕСКИЙ ОБЗОР ТЕОРИИ ПРЕДСТАВЛЕНИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ И ПРОЦЕССОВ ЕЕ КОМПРЕССИИ.

1.1.Введени е.

1.2.Цветовая модель, как способ представления графической информации

1.2.1. Аддитивная цветовая модель RGB.

1.2.2. Субтрактивные цветовые модели (CMY и CMYK).

1.2.3. Перцепционная цветовая модель HSB.

1.2.4. Колориметрические цветовые модели Lab и другие.

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

1.4.Анализ существующих требований к алгоритмам сжатия

1.5. Аналитический обзор алгоритмов сжатия без потерь.

1.5.1.Групповое кодирование.

1.5.2. Алгоритм LZW.

1.5.3. Алгоритм Хаффмана.

1.5.4.Алгоритм JBIG.

1.5.5.LOSSLESSJPE G.

1.6.Аналитический обзор алгоритмов сжатия с потерями.

1.6.1 Рекурсивное сжатие.

1.6.2 Алгоритм JPEG.

1.6.3 Фрактальное сжатие.

1.7.Исследованпе и критериальный анализ результатов компрессии при применении . алгоритмов сжатия без потерь.

1.8.Исследование и критериальный анализ результатов компрессии при применении алгоритмов сжатия с потерями.

1.9.ВЫВОДЫ.

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

2.1. Обозначения, определения и допущения.

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

2.2.1. Математическая модель для учета погрешностей в цветовой гамме фрагментов.

2.2.2. Функции, используемые для преобразования фрагментов.

2.3. Пример компрессии изображений вариабельными фрагментами.

2.4. Расчет оценки быстродействия алгоритма.

2.5.ВЫВОДЫ.

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

3.1 Постановка эксперимента.

3.1. Архивация двуцветных изображений.

3.1.2.Архивация 16-цветного изображений.

3.1.3. Архивация полноцветных изображений.

ЗЛЛОбщая характеристика тестируемых форматов.

3.1.5. Орнаменты, мозаика, рисунки на коврах.

3.1.6. Различные рамки.

3.1.7. Узоры на тканях, полотнах.

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

3.1.9.Графики, тексты.

3.1.10. Фоновые изображения для мобильных телефонов.

3.1.11. Симметричные изображения.

3.2. Поиск оптимальной размерности фрагмента на основе анализа проведенных экспериментов.

3.3.ВЫВОД Ы.

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

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

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

В частности, в работах Дадаяна JI.C. [1,2] приводится описание методики компрессии статичных изображений вариабельными фрагментами, сравнение пикселов в которой осуществляется посредством анализа структуры их цветовой гаммы и разделения на 3 цветовых спектра с использованием цветовой модели RGB. Результаты компрессии изображений, полученных по методикам на основе вышеупомянутой теории по коэффициенту компрессионного сжатия, выгодно отличаются от аналогичных наработок с использованием вариабельных фрагментов, разработанных в СОЦНИТ, однако, методика разделения цвета на спектры не позволяет производить объективное сравнение пикселов, а выбор минимального базового подмножества фрагментов не дает глобально -оптимального решения.

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

Актуальность проблемы. С появлением новых технических средств растровые цифровые изображения в различных отраслях науки и техники, все чаще используются в качестве данных об обрабатываемых и исследуемых объектах в системах, созданных на базе ЭВМ; информационных комплексов и компьютерных сетей. Представление цифровых статических изображений в виде двумерных матриц требует больших объемов данных и предъявляет высокие требования к сетевому оборудованию при передаче их по каналам связи, а также к емкости внешних носителей при хранении информационной базы. В частности, книжная иллюстрация на обложке размером приблизительно 510 х 820 точек занимает емкость на цифровом носителе около 1.23 Мб — т.е. примерно столько же, сколько художественная книга объемом в 350 страниц (около 60 знаков в строке и примерно 40 строк на странице) [6]. Таким образом, актуальность вопросов повышения эффективности сжатия статичных изображений не вызывает сомнения. Ярким примером острой необходимости скорейшего усовершенствования процессов компрессии изображений являются системы, в которых необходимо обеспечить хранение большого количества изображений в автономном режиме:

- бортовые системы фотографирования поверхности Земли;

- спутниковые системы получения метеоснимков;

-медицинские базы данных, хранящие диагностические снимки;

- фотографии;

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

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

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

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

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

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

Работа проведена в соответствии с планом научно-исследовательских работ Северо-Кавказского горно-металлургического института (государственного технологического университета)

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Произвести анализ современных мировых требований к методологии алгоритмов сжатия с потерями и без потерь. Для этого необходимо:

- выполнить обзор теории представления графической информации в цифровом виде и алгоритмов ее компрессии;

- изучить требования к алгоритмам сжатия графической информации;

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

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

- оптимизировать выбор минимального подмножества фрагментов при компрессии изображений с поиском глобально — оптимального базового подмножества фрагментов;

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

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

3. Экспериментально доказать, что результаты компрессии разработанного автором алгоритма сжатия SCI превосходят результаты сжатия алгоритмами JPEG и TIFF.

Для этого необходимо:

- произвести сравнительный анализ экспериментальных исследований применения алгоритма сжатия sci при компрессии двуцветных, 16-ти цветных и полноцветных типов изображений; произвести исследование и систематизировать результаты критериального анализа компрессии при применении алгоритмов сжатия без потерь; произвести исследование и систематизировать результаты критериального анализа компрессии при применении алгоритмов сжатия с потерями;

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

Применялись лабораторные и экспериментальные исследования, обработка и систематизация данных с использованием ЭВМ.

Основные научные положения, которые выносятся на защиту:

1. Результаты систематизация требований к методологии алгоритмов сжатия с потерями и без потерь;

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

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

4. Разработанный автором алгоритм сжатия SCI;

5. Предложенный способ применения алгоритма сжатия sci, при котором коэффициент сжатия эффективен в случае компрессии двуцветных, 16-ти цветных и полноцветных типов.

Научная новизна работы подтверждается:

1. Разработкой методики выбора базового подмножества фрагментов изображений в процессе сжатия;

2. Разработкой способа сравнения фрагментов статичных изображений в процессе компрессии;

3. Построением математической модели для учета выбора степени погрешности пользователем и ее применения при работе с алгоритмом SCI.

4. Предложенной и реализованной автором оригинальной методикой декомпрессии алгоритма сжатия SCI, которая позволяет сократить время декомпрессии и не зависит от размеров открываемого файла.

5. Получением двух свидетельств официальной регистрации программы для ЭВМ №2007610600, №2007613948, патента РФ №2007129867/09(032526).

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

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

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

Апробация и реализация работы. Основные результаты работы обсуждались на X Международном конгрессе (г. Нальчик , КБГУ), Всероссийских конференциях в г. Нальчик «Перспектива» в 2004 и 2006г. и

Всероссийской научной студенческой конференции, г. Ставрополь, СевКавГТУ, 2006г.

Публикации. Основные положения диссертации опубликованы в 13 работах, в том числе получены два свидетельства об официальной регистрации программы для ЭВМ №2007610600, №2007613948 и патент РФ №2007129867/09(032526).

Структура и объем работы. Диссертация состоит го введения, 3 глав, заключения, библиографического списка из 125 наименований, 10 приложений, содержит 118 стр. машинописного текста, 44 рисунков и 32 таблиц.

Основные результаты работы обсуждались на X Международном конгрессе (г. Нальчик , КБГУ), Всероссийских конференциях в г. Нальчик «Перспектива» в 2004 и 2006г. и Всероссийской научной студенческой конференции, г. Ставрополь, СевКавГТУ, 2006г. По результатам исследований выдано свидетельство об официальной регистрации программы для ЭВМ №2007610600, №2007613948, патента РФ №2007129867/09(03256).

Некоторые научные положения работы используются при изучении профильных дисциплин на кафедрах «Автоматизированной обработки информации», «Информационные системы в экономике», «Системах автоматизированного управления» Северо-Кавказского горнометаллургического института (государственного технологического университета).

1. Дадаян JI.C. Компрессия изображений вариабельными фграгментами. Сборник статей аспир анто в .Владикавказ, 2001 г.

2. Дадаян JI.C. Экспериментальный анализ сравнительной эффективности различных методов компрессии статических изображений. Материалы международной конференции "Новые информационные технологии в науке, образовании, экономике". Владикавказ,2002 г.

3. Мельниченко В.В., Легейда В.В. Настоящий самоучитель компьютерной графики К.: Век+, СПб.: КОРОНАпринт, К.:НТИ, 2005. -560 с.

4. Информатика. Базовый курс. 2-е издание / Под ред. С.В. Симоновича. -СПб.: Питер, 2005 640 е.: ил.

5. Пономаренко С.И. Пиксел и вектор. Принципы цифровой графики. — СПб.: БХВ Петербург, 2002. - 496 е.: ил.

6. Коцюбинский А.О., Грошев С.В.Компыотерная графика.: Практ. Пособ. — М.:»ТЕХНОЛОДЖИ-3000», 2001 752 е.: ил.

7. Гроппен B.O., Принципы оптимизации комбинаторных процедур. Изд-во РУ,1988.200 с.

8. Гроппен В.О., Модели и алгоритмы комбинаторного программирования. Изд-во РУД 983.

9. Кирсанов Д., Веб-дизайн, издательство: Символ-Плюс,2001,367 с.

10. Ю.Сик Д., Ли Л., Ламсдэйн Э., С++ Boost Graph Library. Библиотекапрограммиста. Изд-во Питер,2005.

11. П.Якушев Д., "Философия" программирования на языке С++, издательство: Новый издательский дом, 2006, 320 с.

12. Софиева Ю.Н., Цирлин А.М., Условная оптимизация. Методы и задачи, издательство: УРСС,2003 ,140 с.

13. С. И. Бирюков, Оптимизация. Элементы теории. Численные методы, издательство: МЗ-Пресс, 2003, 246 с.

14. М. Петров, Компьютерная графика. Учебник для вузов. 2-е издание, издательство: Питер, 2004, 812 с.

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

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

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

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

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

20. 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.

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

22. Standartization of Group 3 Facsimile apparatus for document transmission, CCITT Recomendations, Fascicle V1I.2, T.4. 1980. 10. Д. Ватолин, MPEG стандарт ISO на видео в системах мультимедиа, "Открытые системы", #3,1995.

23. L. R. Foulds Graph Theory Applications, Springer; 2 edition (December 2, 2004), 403 p.

24. Vitaly O. Groppen. New Solution Principles of Multi-Criteria Problems Based on Comparison Standards. www.aixiv.Qrg/ltp/iTiadi/papg^0501/0501357.pdf. 2004.

25. Гроппен В.О. Принципы принятия решений с помощью эталонов. Изд. РАН, ж. Автоматика и телемеханика, № 4, 2006, стр. 167-184.

26. Прэтт У. Цифровая обработка изображений. М.,«Мир», 1982, т.1, 310 с. , т.2, 790 с.

27. Ярославский Л.П. Введение в цифровую обработку изображений. М. «Советское радио», 1979, 311 с.

28. Патрик Э. Основы теории распознавания образов. М., «Советское радио», 1980, 408 с.

29. Ту Дж., Гонсалес Р. Принципы распознавания образов. М., «Мир», 1978,411 с.

30. Горелик А.Л., Скрипкин В.А. Методы распознавания. М., «Высшая школа», 1984, 208 с.

31. Корн Г, Корн Т., Справочник по математике (для научных работников и инженеров), М., «Наука», 1973,832 с.

32. Бард Й. Нелинейное оценивание параметров. М., «Статистика», 1979, 350 с.

33. Крамер Г. Математические методы статистики. М., «Мир», 1975, 648 с.

34. Космическое землеведение: информационно-математические основы / Под ред. акад.РАН В.А. Садовничего. М.: Изд-во Моск. ун-та, 1998, 571с.

35. 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 .

36. 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.

37. 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 HDTV and the Evolution of Television, Taipei, Taiwan, Nov. 1995, pp. 6A15—6A22.

38. 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.

39. 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 .

40. Detlev Marpe, Hans L. Cycon, Gunther Zander, Kai-Uwe Barthel "Context-based Denoising of Images Using Iterative Wavelet Thresholding". Proc. SPIE, Vol. 4671, pp. 907-914, Jan. 2002.

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

42. 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.

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

44. Aleksandra Pizurica, Wilfried Philips, Ignace Lemahieu, and Marc Acheroy "A Versatile Wavelet Domain Noise Filtration Technique for Medical Imaging". IEEE Trans Med Imaging. 2003 Mar;22(3):323-31.

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

46. Lindsay I Smith "A tutorial on Principal Components Analysis". 2002 nittpy/www.cs.otago.ac.rc7crac453 companents.pdf)

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

48. Интернет-ресурс: http://taco.polv.edu/WaveletSoftware/.50.1van 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

49. 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 .

50. 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.

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

52. 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), pp.37-40.

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

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

55. Интернет-ресурс: http://astronomv.swin.edu.au/~pbourke/analvsis/.

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

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

58. G. de Haan "Progress in motion estimation for video format conversion". IEEE Transactions on Consumer Electronics Vol 46 No 3 Aug 2000 pp 449450.

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

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

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

62. Интернет- ресурс- http://graphics.cs.msu.su/librarv/fractals/index.htni

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

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

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

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

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

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

69. Крупицкий Э.И., Кундин А.И., Эмдин B.C. Некоторые пути реализации аналоговых оптико -электронных линейных обучаемых классификаторов изображений // Межведомственный научный сборник

70. Способы записи информации на бессерябряных носителях". (Киев). -1975. -Вып. 6. -С.58-68.

71. Блок А.С., Зюзин O.M., Крупицкий Э.И., Фридман Г.Х. Гибридные оптико-электронные системы распознавания изображений // Автометрия. АН СССР-СО. 1974. - №1. - С.36-46.

72. Крупицкий Э.И., Кундин А.И., Эмдин B.C. Аппаратурная оценка параметров случайных полей оптическим методом // VII Всесоюзный симпозиум "Методы представления и аппаратурный анализ случайных процессов и полей": докл.- Таганрог, 1974. С. 143-147.

73. Крупицкий Э.И., Фридман Г.Х. Применение когерентной оптики и голографии в системах распознавания изображений. В кн. Оптические методы обработки информации. Л.: Наука, 1974. - С.78-93.

74. Харкевич А.А. О выборе признаков в машинном опознании // Техническая кибернетика. Изв. АН СССР. Наука, 1963. - №2. - С.3-9.

75. Левин М. Методы выделения признаков // ТИИЭР. 1969. - Т.58. - №8.-С.51-69.

76. Холмс В. Автоматическая фотоинтерпретация снимков и обнаружения целей // ТИИЭР. 1966. - Т.54. - №12. - С.56-65.

77. Фу К. Последовательные методы в распознавании образов и обучения машин. -М.: Наука, 1971. С.40-46, 165-184.

78. Стуйг В.А., Тимофеев А.В. Опознание фотоизображений с помощью оптических фильтров // Изв. вузов: Приборостроение. ЛИТМО, 1970. -№11. С. 102-105.

79. Эльман Р.И. О синтезе структуры анализатора изображений // Изв. АН СССР: Техническая кибернетика, 1968. №1. - С. 135-150.

80. Лэндрис Д., Стенли Г. Метод дискретизации дифракционных картин для распознавания образов // ТИИЭР. 1970. - Т.58. - №2. - С.22-40.

81. Крупицкий Э.И., Кундин А.И., Эмдин B.C. Некоторые методы когерентно-оптической аналоговой обработки двумерных случайныхполей // В сб. "Иконика новое направление в изучении изображений" // Труды ГОИ. -1979. - Т. 44. - Вып. 178. - С. 117-121.

82. Блок А.С., Эмдин B.C. Оптико-телевизионный анализатор изображений. Межвузовский сборник "Повышение эффективности и надежности РЭС / ЛЭТИ. Л.- 1979. - Вып. 9. - С. 112-118.

83. Пугачев B.C. Теория случайных функций и ее изменение в задачах автоматического управления. Физматгиз. 1962. - С.203-245.

84. Слуцкий Е.Е. Сложение случайных величин как источник случайных процессов. Избранные труды АН СССР. М. - 1960. - С.99-132.

85. Эмдин B.C. Определение параметров бинарных случайных масок в оптико-электронных классификаторах изображений // Тематический сборник "Оптические и оптико-электронные методы обработки изображений и сигналов" / АН СССР. Л., 1982. - С. 192-196.

86. Силинг М.М., Эмдин B.C. Формирование признаков для классификации текстур с помощью масок бинарных случайных функций // Техника средств связи. Сер. ТТ. 1983. - Вып. 2.- С. 51-55.

87. А.С. 409585. Голографический коррелятор / Э.И.Крупицкий, Л .П.Карпов//БИ. -2001 .-№20.

88. Гибин И.С., Нежевенко Е.С. и др. Когерентно-оптические устройства для обобщенного спектрального анализа изображений // Автометрия. АН СССР-СО. 1972. - №5. - С.3-9.

89. A.C. 470214. Устройство контроля записи голографических согласованных фильтров / Л.П.Карпов, Э.И.Крупицкий, В.С.Эмдин и др.//БИ.-2001 .-№20.

90. A.C. 498629. Оптико-механическое сканирующее устройство / Л.П.Карпов, В.С.Эмдин и др. // БИ. 1976. - №1.

91. Эмдин B.C. Двухкоординатное устройство отклонения светового луча// ОМП. -1983. -№6. С.58-59.

92. Интернет- ресурс -http://www.mathsoft.com/wavelets .

93. Нежевенко Е.С., Салов Г.И. и др. Линейный обучаемый классификатор оптических изображений // Автометрия. АН СССР-СО. 1971. - №3. -С.82-84.

94. А.С. 278229. Оптико-электронная обучаемая система / О.М.Зюзин, Л.П.Карпов, Э.И.Крупицкий //Б.И. 1970. - № 25.

95. А.с. 417810. Устройство для распознавания образов / Э.И. Крупицкий,

96. A.И.Кундин, В.С.Эмдин //Б.И. 1974. - №8.

97. А.С. 511810. Устройство для распознавания образов / В.С.Эмдин,

98. B.Н.Яковлев.//БИ.-2001.-№20.

99. Блок А.С., Эмдин B.C., Оптико-телевизионный анализатор изображений. Межвузовский сборник "Повышение эффективности и надежностиРЭС/ЛЭТИ. Л. - 1979. -Вып. 9. -С. 112-118.

100. Кругер М.Я. и др. Справочник конструктора оптико-механических приборов. Л.: Машиностроение, 1968. - С.50.

101. Интернет- ресурс httpy/vvww.hakiiec.ac.ip/-^ links.html.

102. А.с. 530571. Устройство распознавания образов / Э.И. Крупицкий, В.С.Эмдин и др.//БИ.-1978.-№42.

103. Надь Д. Цифровая обработка изображений, полученных при дистанционном исследовании природных ресурсов // ТИИЭР. 1972. -Т.60. -№Ю. -С.90-122.

104. Блок А.С., Зюзин О.М., Крупицкий Э.И., Эмдин B.C. Опыт разработки многоканального когерентно-оптического анализатора для гибридной системы распознавания изображений // П Всесоюзная конференция по голографии: докл.- Киев, 1975. - 4.1. - С. 21-23.

105. Интернет- ресурс http://www.rasip.etf.hr/research/compress/index.html.

106. Интернет- ресурс httoy/aaphics.csjnsu.su.

107. Интернет- ресурс httpy/g^hics.cs.m^

108. Интернет- ресурс -hltpTfelay.ustiLru^t^'cnTt/inf techn/slovarAitemOKl .htm.

109. Интернет- ресурс -hUp://vvmv.iTmsfo.marLm:808^^111. Интернет- ресурс

110. Интернет- ресурс -httpy/wvw-bufld^ewm

111. Мамонтов Д.В., Соколова Е.А., Алгоритм поиска пути в двумерном и трехмерном массивах. Перспектива 2004: Материалы Всероссийской научной конференции студентов аспирантов и молодых ученых,- Нальчик: Каб.- Балк. ун.-т, 2004,с.210-212.

112. Гроппен В.О., Соколова Е.А., Разработка сжатия изображения методом вариабельных фрагментов, Научный потенциал студенчества -будущему России / Материалы Всероссийской научной студенческой конференции. Ставрополь: СевКавГТУ, 2006. с. 212 .

113. Гроппен В.О., Проскурин А.Е., Соколова Е.А.Официальная регистрация ПрЭВМ Программа компрессии изображений (SCI — Smart compression of images) № 2007610600 от 07.02.2007г.

114. Соколова Е.А. Эффективная оценка компрессии изображений вариабельными фрагментами. Перспектива — 2007: Материалы международного конгресса студентов аспирантов и молодых ученых.- Нальчик: Каб,- Балк. ун.-т, 2007 ,с. 200-201.

115. Соколова Е.А. Анализ алгоритмов сжатия и оценка их эффективности. Материалы 6-ой международной конференции "Инновационные технологии для устойчивого развития горных территорий".-Владикавказ,28-30 мая 2007, с.710-711.

116. Гроппен В.О., Проскурин А.Е., Соколова Е.А.Официальная регистрация ПрЭВМ Программа компрессии видеоизображений (SCIV Smart compression of video) № 2007613948 от 26.07.07 г.

117. Соколова Е.А., Математическая модель компрессии статичных изображений вариабельными фрагментами с учетом погрешностей. Деп. в ВИНИТИ 19.07.07. № 748-В2007, указатель № 9, 12 с.

118. Соколова Е.А., Определение параметров быстродействия алгоритма компрессии статичных изображений. Перспектива — 2008: Материалы международной научной конференции молодых ученых, аспирантов и студентов.- Нальчик: Каб,- Балк. ун.-т, 2008,с. 143-147.

119. Гроппен В.О., Проскурин А.Е., Соколова Е.А. Способ компрессии и декомпрессии статических изображений и видеоинформации в цифровой форме. Патент РФ №2007129867/09(032526).

120. Соколова Е.А. К проблеме повышения эффективности компрессии изображений. Безопасность информационных технологий, Министерство образования и науки РФ, МИФИ, ВНИИПТИ, 2008, № 2 , с.57-60.

121. Соколова Е.А., Компрессия изображения вариабельными фрагментами: модель, алгоритм, интерфейс, эксперимент. Вестник компьютерных и информационных технологий, №10, 2008, с.31-34.

122. Поворот на 90 градусов относительно оси ок:for (int i = 0; i < s; i++)for (int j = 0; j < s; j++)

123. D.SetPixel(i, j, BG.GetPixelG, s i - 1));

124. Поворот на 180 градусов относительно оси ок for (int i = 0; i < s; i++) for (int j = 0; j < s; j++)

125. D.SetPixel(i, j, BG.GetPixel(s i - 1, s - j - 1));

126. Поворот на 270 градусов относительно оси окfor (int i = 0; i < s; i++)for (intj = 0;j <s;j++)

127. D.SetPixel(i, j, BG.GetPixel(s j - 1, i));

128. Зеркальное отображение на 90 градусов относительно оси ок for (int i = 0; i < s; i++) for (int j = 0;j <s;j++)

129. D.SetPixel(i, j, BG.GetPixel(s j -1, s - i - 1));

130. Зеркальное отображение на 180 градусов относительно оси ок for (int i = 0; i < s; i++) for (int j =0;j <s;j++) D.SetPixel(i, j, BG.GetPixel(j, i));

131. Зеркальное отображение на 270 градусов относительно оси окfor (int i = 0; i < s; i++)for (intj =0;j <s;j++)

132. D.SetPixel(i, j, BG.GetPixel(i, s j - 1));

133. Зеркальное отображение на 360 градусов относительно оси окfor (int i = 0; i < s; i++)for (intj = 0; j <s;j++)

134. D.SetPixel(i, j, BG.GetPixel(s i - 1, j));1. Изображение1. VWf1. ЛШЙ (ГЙ? ь1. Размер256*256256*256

135. И 256*256 26 7,3 130 1,4 192 1 6 321. Изображениек и я1. Размер, пике.

136. Li:;:- 1 256*256 36,8 5,2 40 4,8 192 1 15,3 123 1 r 1 1 Г 1 ж a it ! j} i ' r i i r t 256*256 56,7 3,3 115 1,6 192 1 5,35 35

137. КЛ V B.Jf v.* MM M 51.1 >"!i V"S «Я V-Щ' ДО. & 31 Ц* fc-sn» U # IS и И (■■J »л f-Г ОЛ И-*; tuf P." 256*256 61 3,1 121 1,6 192 1 7,27 265 во 4fp U«I U»! |N' •NP ufl * , * * . к . , . 256*256 102 1,8 154 1,2 192 1 38 5

138. M ы м ы ы u ш u IF» ■ ■ 1 ■ ' VV, Г Л Ц . jg № Ы. i * ~ ■ ■I : ■ (Ш si V; кшшвшвш i -! "j" Ы a 11 ^'f 256*256 59 3,2 117 1,6 192 1 6,59 297 256*256 J 63 3 119,5 1,6 192 1 5,73 331. Изображение1. Размер

139. Размер изображения в формате с погрешностью 0%, Кб Коэффициент компрессии1. TIFF1. JPEG1. BMP256*25612