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

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

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

Pages:   || 2 |

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

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

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

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

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

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

Защита диссертации состоится 15 ноября 2007 г. в 14.00 часов на заседании диссертационного совета Д212.246.01 Северо – Кавказского Ордена Дружбы Народов Горно – Металлургического Института (Государственном технологическом университете) по адресу : 362021, РСО – Алания, г. Владикавказ, ул. Николаева 44, СКГМИ (ГТУ).

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

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

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

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

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

д.т.н., доцент Алексеев В.П.

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

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

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

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



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

  1. Разработаны алгоритмы компрессии симметричных изображений
  2. Разработан математический аппарат, позволяющий a priori оценить границы эффективности предложенных алгоритмов компрессии симметричных изображений.
  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 градусов. Фрагмент представляет собой обыкновенную двумерную матрицу, где значения ячеек являются значениями цветов.

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

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

где

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

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

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

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

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





Введем следующие обозначения:

x- Размер фрагмента

Q(x) – величина выигрыша

P(x) – вероятность выигрыша Q(x).

Тогда =

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

Полагая, что переменная х непрерывно меняется на заданном интервале, в нашем случае: .

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

Решение задачи дает результат: . (1)

Из (1) следует, что величина выигрыша не зависит от размера фрагмента x. Таким образом, в ходе реализации алгоритма нужно сравнить значения всех полученных выигрышей при различных размерах фрагментов. Существует только одно исключение, когда P(x)=0, которая возникает в том случае, когда размер фрагмента больше половины размера изображения. В этом случае значение Q(x) считается худшим. Если при всех значениях Х величина выигрыша принимает Q(x) плохое значение, то файл изображения не сжимается, а остается старый. В таких случаях рекомендуется поменять степень сжатия.
Компрессия статических изображений вариабельными фрагментами (smart). Модель, о которой говорилось ранее, является достаточно мощной в плане компрессии, но не оптимальной. Фактически она сводит поиск базового подмножества фрагментов, двигаясь от первого, к поиску на соседних планах. Однако такой подход не дает глобально-оптимального решения, так как не предусмотрен выбор другого стартового сегмента, отличного от первого. В этом разделе раскрывается более мощный и оптимальный математический аппарат для компрессии изображений базирующийся на элементах теории графов, использующий оптимальную стратегию при выборе “похожих” сегментов.
Описание метода

Изображение состоит из P числа пикселей, а его область разбита на n-е количество сегментов, количество пикселей в каждом сегменте соответственно равно ; Сегменты считаются “похожими”, если число не совпадающих точек у них не превысит значение “”. Соответствующие пиксели у сравниваемых сегментов являются «похожими», если разница в их цветовой величине не превышает “2”. После компрессии, файл содержащий данные об изображении должен содержать только “непохожие” опорные сегменты и информацию об их размещении в матрице изображения. Отсюда следует утверждение, чем меньше количество опорных сегментов в файле в котором хранится сжатое изображение, тем больше степень сжатия этого изображения.

Фактически формируются две задачи, которые позволят “сжать” изображение с лучшими характеристиками:

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

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

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

  • Подмножество X1 содержит только вершины - эталоны, для любой пары этих вершин, не существует соединений ребрами в наборе U, т.е. справедливо: ;
  • для любой вершины xj принадлежащий подмножеству X2 =X\X1, есть по крайней мере одно соединение c вершиной подмножества X1;
  • |X| min.

Формальная постановка задачи совпадает с задачей о покрытии вершин графа: на графе G(X,U) требуется выделить суграф G(X,U’), X= X1+X2, такой, что:

(2)

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

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

Рис.2. Представление ряда кадров как одно изображение

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

Введем следующие обозначения:

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

F – степень сжатия; характеризуется суммой параметров ;



Pages:   || 2 |
 

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







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

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