Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников




Скачать 297.16 Kb.
НазваниеКобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников
страница4/5
Дата20.09.2012
Размер297.16 Kb.
ТипДокументы
1   2   3   4   5

Модифицированный ФРАКТАЛЬНыЙ АЛГОРИТМ СЖАТИЯ СТАТИЧЕСКИХ ИЗОБРАЖЕНИЙ

Зараменский Д.А., Хрящев В.В.

Ярославский государственный университет имени П.Г. Демидова

150000, Россия, Ярославль, ул. Советская 14. Тел. (4852) 797775, e-mail: connect@piclab.ru

Проблема сжатия изображений подробно исследовалась на протяжении последних трех десятилетий [1]. Несмотря на то, что сейчас стандартом сжатия цветных цифровых изображений де-факто является алгоритм JPEG, существуют и другие методы, которые не используют понятие избыточности информации для ее сжатия [2]. Главным недостатком JPEG является неустойчивость кода к помехам и предопределенная граница коэффициента сжатия. Изменение единственного байта кода может привести к тому, что изображение декодировать не удастся [3]. Фрактальные алгоритмы кодирования не используют понятие избыточности информации, а непосредственно представляют ее в компактном виде [4]. Это выгодно отличает их от других алгоритмов сжатия с потерями в плане помехоустойчивости кода. Суть любого фрактального алгоритма заключается в нахождении сжимающего оператора F, действующего на пространстве изображений такого, что его неподвижная точка близка в смысле некоторой метрики к исходному изображению. В этом случае вся информация об изображении содержится в операторе F, и если для хранения оператора F требуется меньшее количество памяти, чем для хранения исходного изображения, значит, мы добились сжатия исходного изображения.

Г

лавным недостатком подобных алгоритмов является их вычислительная сложность [5]. На практике существует несколько способов построения данного оператора, однако все они используют большое число вычислений расстояний между отдельными частями изображения, что и приводит к существенному увеличению времени работы алгоритма. Наиболее популярным является метод доменно-рангового сопоставления, согласно которому, все изображение разбивается на 2 семейства блоков – доменных и ранговых. Алгоритм находит для каждого рангового блока доменный блок такой, что расстояние между ними после оптимального преобразования w будет меньше заранее заданного допуска. Для разбиения используются 2 основных метода – равномерное разбиение и адаптивное разбиение (рис 1).


Рис 1. Разбиение изображения Lenna на ранговые блоки


Первый метод дает лучший результат с точки зрения качества изображения, т.к. зачастую используется очень мелкое разбиение на ранговые блоки, второй – дает более высокую степень сжатия, за счет разбиения на блоки разной величины. Для программной реализации фрактального алгоритма было использовано адаптивное разбиение методом квадродерева [6]. В качестве преобразования w было использовано сжатие простым усреднением по строкам и столбцам. Традиционно к сжатию добавляют еще всевозможные повороты на 900 и отражения. Анализ научно-технических источников [6] показывает, что от них можно отказаться без ущерба для качества изображения, а освободившуюся память использовать под более тщательное доменное разбиение.

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

Первое направление заключается в ведении оценки, по которой можно сказать стоит ли производить сопоставление данного доменного блока с ранговым или нет. Для этого можно использовать вероятностные характеристики и их аналоги, учитывая специфику доменно-рангового сопоставления. Для матрицы Anxm=[aij] нами было отобрано 6 характеристик: , где , , , ,

, .

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

Таблица 1 Сравнение базового и оптимизированного фрактальных алгоритмов

Тип алгоритма

Изображение

Кол-во доменов

Глубина квадродерева

Время работы

Базовый алгоритм

Lenna 256x256х24

1186

6

135 c.

Оптимизированный алгоритм

Lenna 256x256х24

1186

6

57 с.

Итак, мы получили метод быстрого сравнения доменного блока с ранговым, однако перебор доменов до сих пор осуществлялся в порядке следования их индексов в разбиении. На основании анализа кода изображений можно сделать вывод, что чаще всего в соответствии ранговым блокам ставятся доменные блоки, коэффициенты матрицы которых почти одинаковы. В работе [7] такие блоки были названы «регулярными». Такой блок можно сопоставить ранговому блоку при достаточно большой глубине квадродерева. На основании этого можно рассмотреть следующую систему перебора доменов. Перед началом работы алгоритма присвоим каждому доменному блоку вес, равный 0. В процессе работы алгоритма, когда очередному ранговому блоку ставится в соответствие доменный блок, вес этого домена увеличивается на 1 и становится равным количеству ранговых блоков, которым соответствует данный доменный блок. Таким образом, все доменные блоки после каждого шага алгоритма можно упорядочить по их весам. На практике это можно делать в процессе присваивания весов для экономии времени. На следующем шаге перебор доменных блоков следует проводить в соответствии с их весами, начиная с домена с наибольшим весом. При использовании такого способа перебора доменов мы получаем выигрыш во времени порядка 15% - 20%. Сравнительный анализ результатов моделирования приведен в таблице 2.

Таблица 2. Сравнение алгоритмов при использовании упорядоченного обхода

Тип алгоритма

Изображение

Кол-во доменов

Глубина квадродерева

Время работы

Оптимизированный алгоритм

Flower 512х384х24

99902

7

49.13 мин

Оптимизированный алгоритм с упорядоченным перебором доменов

Flower 512х384х24

99902

7

39.40 мин

Следует отметить, что в качестве метрики была использована Евклидова метрика для матриц, а все расчеты проводились на 1-ядерном процессоре с тактовой частотой 1.7 ГГц. Все исследования проводились для цветных изображений в формате RGB. В данном случае для каждого блока изображения мы имели 3 вектора характеристик. Однако была реализована модификация, в которой сравнение векторов характеристик производилось только по 1 каналу, например, по зеленому. Доменно-ранговое сопоставление проводилось же по всем 3 каналам. Тем не менее, эта модификация не дала прироста быстродействия, так как время, сэкономленное при вычислении и сравнении характеристик, компенсировалось увеличением числа доменно-ранговых сопоставлений из-за пропуска «плохих» доменов при сравнении векторов характеристик.

Примеры обработки тестовых изображений «Lenna» и «Flowers» с помощью описанных выше фрактальных процедур приведены на рис.2. Используя различные методы повышения эффективности алгоритма фрактального кодирования можно уменьшить время работы алгоритма в 2–2.5 раза. В работе [7] была предложена реализация алгоритма с использованием генетического алгоритма для поиска предоптимальных доменных блоков. Данная реализация также снизила время работы алгоритма примерно в 2-3 раза. Фрактальный алгоритм не имеет предела для коэффициента сжатия, что позволяет использовать его в задачах, где требуется большая степень сжатия и не существенны артефакты блочности.





а)

б)





в)

г)

Рис 2. Обработка изображений фрактальным алгоритмом: а) оригинальное изображение «Lenna»; б) декодированное изображение после 1 итерации (коэффициент сжатия 8.6); в) оригинальное изображение «Flowers»; г) декодированное изображение после 7 итерации (коэффициент сжатия 9.1)

Литература

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

  2. Гонсалес Р., Вудс Р. Цифровая обработка изображений. – М.: Техносфера, 2005.

  3. Сэломон Д. Сжатие данных, изображений и звука. – М.: Техносфера, 2004.

  4. Кроновер Р. Фракталы и хаос в динамических системах. – М.: Постмаркет, 2000.

  5. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. – М.: Триумф, 2003.

  6. Fisher. Y. Fractal Image Compression. Springer-Verlag, 1998.

  7. Mitra S., Murthy C. Technique for fractal image compression using genetic algorithm // IEEE Transactions on Image Processing. 1998. V. 4, № 2. P. 586-593.




MODIFIED FRACTAL IMAGE COMPRESSION ALGORITHM

Zaramensky D., Khryashchev V.

Yaroslavl State University
14 Sovetskaya st., Yaroslavl, Russia 150000. Phone: (4852) 797775. E-mail: connect@piclab.ru

The problem of image compression has been studied in details during last 30 years. Despite the fact that nowadays JPEG algorithm is the standard of color image compression there are algorithms that do not use information redundancy for compression [1]. The main disadvantage of JPEG is noise instability: changing 1 byte of a code can cause decompression failure [2]. Fractal image coding algorithm do not drop redundant information but try to directly present information in a compact way. This is their advantage in comparison with others. The essential of any fractal image coding algorithm is to find suitable contractive operator F on the space of digital images, so that its fixed point approximates original image. In that case all information about original image is stored in operator F, and if F requires less memory to store then we have compressed the image.

The main disadvantage of such algorithms is their resource consumption. There are several ways to construct the fractal operator, but all of them use a lot of distance calculations between different subimages, which cause a long time operations. The most common method is method of domain and range blocks, when the whole image is partitioned into 2 sets of blocks – domain and range blocks. For each range block algorithm tries to find a suitable domain block of bigger size, which being transformed by some w transformation approximates given range block.

In described algorithm this is domain to range comparison that results in big calculation costs. Because of huge amount of domain the time of compression causes algorithm to be is unsuitable for further researching. But at the same time there are 2 clear ways of optimization – the first is to introduce some domain to range comparison forecasting method, not to compare useless domains, and the second is to organize domain selection.

The first way was developed as a special estimation, based on statistical characteristics and their analogues. This estimation shows is it reasonable to compare domain and range blocks.

The second one is based on the analysis of the fractal code, generated by the algorithm. It was found that domain blocks with special statistic characteristics are more frequently conformed to range blocks.

This fact led to the adaptive system of domain selecting.

We must mention that we used Euclid metric for matrixes and all calculations were made on 1-core 1.7 GHz processor. All researches used RGB images.

Therefore using a combination of increasing efficiency methods we reduced calculation time of the algorithm in 2.5 times. Fractal algorithm don’t have compression limit and can be used in applications were good compression is more important than “blocking artifacts”.

References

  1. Gonzalez Rafael C., Woods Richard E. Digital Image Processing. – Pearson Education Inc. 2002

  2. Crownover Richard M. Introduction to Fractal and Chaos. – Jones and Bartlett Publishers Inc. 1999




КРАТНОМАСШТАБНЫЙ АНАЛИЗ В ЗАДАЧЕ ЦИФРОВОЙ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ

Моисеев А.А., Волохов В.А.

Ярославский государственный университет им. П.Г. Демидова
150000, Россия, Ярославль, ул. Советская, 14. Тел. (4852) 79-77-75. E-mail: dcslab@uniyar.ac.ru

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

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



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

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

Идея работы блока восстановления (рис. 1) достаточно проста и представляет собой совокупность трех основных этапов:

  • вычисление прямого преобразования изображения (вейвлет-преобразования [2], риджлет-преобразования [3], курвлет-преобразования [3] или их аналогов);

  • изменение полученных коэффициентов преобразования по определенному правилу;

  • вычисление соответствующего обратного преобразования от области измененных коэффициентов.

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

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

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

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

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

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



Рис. 2. Схема курвлет-преобразования

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

В работе рассматривались два варианта реализации схем, представленных на рис. 3:

  • Вариант 1 состоит в использовании на всех уровнях разложения одних и тех же вейвлет-фильтров разложения и восстановления.

  • Вариант 2 состоит в использовании на различных уровнях разложения вейвлет-фильтров, импульсные характеристики которых построены на основе импульсных характеристик вейвлет-фильтров, применяемых на первом уровне разложения и восстановления, путем добавления 2j-1-1 нулевых значений между каждыми двумя их смежными отсчетами. Здесь j определяет уровень разложения, поэтому если j=1 нулевые отсчеты не добавляются, что соответствует первому уровню разложения.









а)

б)

Рис. 3. Инвариантные к сдвигу субполосные схемы разложения: а) двухполосная схема;

б) трехполосная схема
1   2   3   4   5

Похожие:

Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconУчебное пособие Издательство
Учебное пособие предназначено для бакалавров направления 230700 «Прикладная информатика» по дисциплине «Теория вероятностей и математическая...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма вступительного экзамена по специальности научных работников 01. 01. 05 «Теория вероятности и математическая статистика»
Аксиомы теории вероятностей. Вероятность и ее свойства. Распределение, функция распределения, плотность распределения. Их свойства....
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма по дисциплине «Теория вероятностей и математическая статистика»
«Теория вероятностей и математическая статистика» разработана в соответствии с Государственным стандартом образования РФ (ЕН. Общие...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины человеческое развитие для направления 080100. 62 «Экономика» подготовки бакалавров Автор: Е. Н. Кобзарь ()
«Экономика» по специализации «Прикладная экономика». Студенты, приступающие к изучению курса, должны иметь базовые знания в области...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины "Теория вероятностей и математическая статистика для менеджеров "
...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconТехнические науки
Анализ данных. Статистические и вычислительные методы для научных работников и инженеров
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconПрограмма дисциплины теория вероятностей и математическая статистика Цикл ен. Ф. Специальность : 013800 Радиофизика и электроника
Рабочая программа дисциплины "Теория вероятностей и математическая статистика" предназначена для студентов 2 курса
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconТочные науки: математика, физика, химия
Анализ данных. Статистические и вычислительные методы для научных работников и инженеров
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconАннотация рабочей программы
Теория вероятностей и математическая статистика» является вариативной частью Профессионального цикла дисциплин подготовки студентов...
Кобзарь А. И. Прикладная математическая статистика. Для инженеров и научных работников iconМетодические рекомендации к практическим занятиям и самостоятельной работе по дисциплине «Прикладная математическая статистика»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница