авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

Повышение эффективности компрессии статичных изображений

-- [ Страница 1 ] --

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

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

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ КОМПРЕССИИ

СТАТИЧНЫХ ИЗОБРАЖЕНИЙ

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

АВТОРЕФЕРАТ

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

кандидата технических наук

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

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

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

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

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

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

канд. физ.-мат. наук

Цопанов Игорь Дзастемирович

Ведущее предприятие: «Институт прикладной математики и информатики Владикавказского научного центра РАН и правительства РСО Алания»

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

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

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

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

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

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

Д 212.246.01, к.т.н., доцент Аликов А.Ю.

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

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

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R(i,j) – интенсивность красного цвета i-го пикселя j-го фраг­мента изображения;

G(i,j) – интенсивность зеленого цвета i-го пикселя j-го фраг­мента изображения;

B(i,j) – интенсивность голубого цвета i-го пикселя j-го фраг­мента изображения;

G(X,U) – ориентированный граф, вершины которого соответствуют фрагментам изображения и существует дуга (i,j) множества U, если i-й фрагмент можно с помощью заданного множества процедур преобразовать в j-й с заданной точностью ;

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

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

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

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

- h-й путь на G(X,U), идущий из в

;

– допустимое отклонение в цветопередаче одного пикселя: если i-й пиксель j-го фрагмента и p-й пиксель k-го фрагмента изо­бражения;

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

k1 – объем памяти для хранения одного пикселя;

k2 – объем памяти для хранения одной дуги;

t1 – время компрессии изображения;

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

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

Алгоритм 1.

Шаг 1.Величине V присваивается бесконечно большое значе­ние.

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

Шаг 3. Изображение делится на квадратные фрагменты, размер которых определен на предыдущем шаге, после чего все фрагменты сравниваются друг с другом, причем в ходе сравнения один из фрагментов, “базовый”, подвергается различным преобразованиям, определяемым множеством . Если в ходе сравнений некоторый j-й фрагмент с заданной точностью совпадает с одной из модифика­ций k-го базового фрагмента, т.е. то это означает, что он может быть заменен соответствующей модификацией базового фрагмента.

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

  • из них достижимы все остальные вершины множества \ по дугам множества U, т.е. справедливо условие:
  • Учитывая, что для любого конкретного графа G(X,U) мощ­ность формальная постановка этой задачи как экстре­мальной задачи с булевыми переменными имеет вид:

(1)

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

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

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

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

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

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

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

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

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

(2)

Связь между системами (1) и (2) определяется теоремой 1:

Теорема 1. .

Доказательство теоремы 1.

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

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

(3)

=0. (4)

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



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.