Сжатие цифровых данных при помощи вейвлет-преобразований и фрактального кодирования информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Филиппов, Тимур Константинович

• Филиппов, Тимур Константинович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Филиппов, Тимур Константинович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 ОБЗОР АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ СЖАТИЯ ЦИФРОВЫХ ДАННЫХ

1 1 Общий критериальный анализ методов сжатия

1 2 Классификация методов сжатия цифровых изображений

1 ЗМетоды сжатия данных без потери информации

1 3 1 Метод группового кодирования (RLE)

1 3 2 Метод Хаффмана

1 3 3 Метод Шеннона-Фано

1 3 4 Словарный метод

1 3 5 Метод сжатия LZW

1 3 6 Метод JBIG

1 3 7 Lossless JPEG

1 4 Алгоритмы сжатия с потерями

1 4 1 Анализ методов сжатия изображений «с потерями»

1 4 2 Алгоритм JPEG

1 4 3 Алгоритм JPEG 2000

1 4 4 Фрактальные методы сжатия

1 4 5 Рекурсивно волновой алгоритм

1 5 Способы улучшения работы алгоритмов сжатия

1 6 Обзор программных средств для сжатия цифровых изображений

1 7 Обзор программного обеспечения для сжатия данных

1 8 Выводы по первой главе

2 ПРИМЕНЕНИЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЙ ПРИ СЖАТИИ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

2 1 Технический анализ экономических данных 51 2 2 Программный комплекс обработки и сжатия цифровых изображений 53 2 2 1 Кодирование и декодирование изображения 53 2 2 2 Преобразование Хаара 55 2 2 3 Преобразование Малла 56 2 2 4 Вейвлетное преобразование цифровых данных 57 2 2 5 Алгоритм реализованного вейвлет-преобразования 62 2 2 6 Результаты сжатия с применением Вейвлет-преобразования 63 2 2 7 Алгоритм JPEG сжатия данных

2 3 Выводы по 2 главе

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

3 1 Фрактальное сжатие изображений 81 3 2 Алгоритм реализованного фрактального сжатия 83 3 3 Результаты сжатия с применением фрактального кодирования

3 4 Выводы по 3 главе

4 ОБРАБОТКА ВЫХОДНЫХ ДАННЫХ ПРОГРАММНОГО КОМПЛЕКСА «TROPICS» НА ОСНОВЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ

4 1 Описание программного комплекса «TROPICS» 93 4 2 Программный продукт WaveRar для сжатия данных 94 4 3 Сравнительный анализ результатов сжатия данных

4 4 Выводы по главе

5 ОЦЕНКА КАЧЕСТВА СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

5 1 Обзор существующих метрик, использующихся для оценки качества сжатых изображений 102 5 1 1 Метрика PSNR 106 5 1 2 Метрика MSE 110 5 1 3 Метрика MSAD 114 5 1 4 Метрика Delta 117 5 1 5 Метрика MSU Blurring Metric 121 5 1 6 Метрика MSU Blocking Metric 124 5 2 Выводы по главе 128 ЗАКЛЮЧЕНИЕ 132 СПИСОК ЛИТЕРАТ> РЫ 134 ПРИЛОЖЕНИЯ

Введение диссертации (часть автореферата) на тему «Сжатие цифровых данных при помощи вейвлет-преобразований и фрактального кодирования информации»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

• научная визуализация (визуализация результатов научных вычислений);

® визуализация программного обеспечения (использование графики для уяснения понятий и эффективной эксплуатации программного обеспечения и спецификации программ в процессе их разработки);

• информационная визуализация (визуальное описание и представление, как правило, абстрактной информации,

получаемой в процессе сбора и обработки данных различного назначения) [3].

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

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

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

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

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

Все методы компрессии подразделяются на два вида: методы сжатия без потерь информации и с потерями. Первые из них позволяют сжимать данные таким образом, чтобы впоследствии их можно было восстановить с абсолютной точностью. Во многих приложениях сжатие без потерь является единственно допустимым способом сокращения объема данных. Одним из таких приложений является архивация медицинских или деловых документов, сжатие с потерями которых обычно запрещено по закону. Другим является обработка спутниковых изображений, где как применение, так и стоимость получения исходных данных делают сжатие нежелательным. Еще одним направлением является цифровая рентгенология, в которой потеря информации может ухудшить точность диагностики [5,6,7].

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

Методы сжатия с потерями обладают одним существенным преимуществом, которое и дало им право на жизнь: они гораздо эффективнее. Коэффициент сжатия - отношение объема исходной информации к объему сжатой - при использовании алгоритмов компрессии с потерями всегда выше, чем при сжатии без потерь [4,7]. Исследования показали, что максимально возможный коэффициент сжатия без потерь равен, примерно, 2:1, а с потерями - 200:1 и выше [5,7]. Поэтому при цифровой записи изображений алгоритмы компрессии с потерями применяются очень широко. Во многих случаях, методы сжатия изображений без потери дают отрицательный результат, т.е. коэффициент сжатия меньше единицы. Практика показала что, для хранения массивов изображений, методы сжатия без потери становятся малоэффективными. Когда необходимо передавать большие изображения по каналу связи, то методы сжатия без потери становятся совсем неудовлетворительными. Потому что, передача по каналу связи больших изображений не только требует очень длительное время, но и занимает трафик канала.

Но при восстановлении сжатых изображений происходит потеря информации и качества изображений[4]. Оно оценивается разными способами и в связи с различными задачами.

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

X А. ± Г

Теоретические основы методов сжатия исследовались зарубежными учёными Барнсли М., Прэттом У. [8,66]. Проблемы применения высокоэффективных

методов сжатия в телекоммуникационных системах решались Ланнэ A.A., Дворковичем В.П., Зубаревым Ю.Б. [30,67].

Оценки коэффициента сжатия для некоторых методов сжатия цифровых изображений были ранее получены В.М. Ефимовым, А.Н. Колесниковым [27].

Исследованию сжатия изображений посвящены работы J1.E. Назарова и З.Т. Назаровой [24], в которых были рассмотрены нейросетевые методы сжатия. В основу их оценок было положено приближенное вычисление объема сжатых данных, при этом в оценках фигурируют параметры методов и не учитываются характеристики изображения.

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

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

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

Задачи, решаемые в диссертационной работе:

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

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

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

• выбор оптимальных параметров при компрессии изображений;

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

• экспериментальное сравнение эффективности алгоритмов сжатия данных с потерями;

Объектом исследования является процесс сжатия цифровых данных с

потерями;

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

Научная новизна работы:

1. Представлено новое применение метода вейвлет-преобразования информации для компрессии больших массивов вещественных данных;

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

3. Проведено сравнение эффективности методов компрессии полутоновых изображений с потерями на примере JPEG и вейвлет-преобразования.

Практическая значимость работы:

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

2. Разработанный программный продукт «WaveRar» (регистрационный номер № №2012614819), используется для сжатия массивов выходных файлов программного комплекса «TROPICS»;

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

Результаты и положения, выносимые на защиту:

1. Методика кодирования растровых изображений с однородными областями;

2. Алгоритм сжатия массивов вещественных данных на основе вейвлет-преобразования информации;

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

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

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

Апробация работы: Результаты диссертационной работы оценивались на всероссийском конкурсе «Инженер года» в 2009, 2010, 2011 г. и получили следующие награды: дипломы победителя первого тура конкурса «Инженерное искусство молодых» в номинации «Нефтяная и газовая промышленность» 2009г.; «Инженерное искусство молодых» в номинации «Информатика, информационные сети, вычислительная техника» 2010,2011г.; результаты работы докладывались на «Международной научно-практической конференции «опыт и перспективы использования информационно-коммуникационных технологий в образовании» («ИТО-Томск-2009»), на Международной научно-практической конференции «Фундаментальные и прикладные исследования: проблемы и результаты» (2013).

По результатам проведенных исследований и разработок, выполненных в процессе работы, опубликовано 7 научных работ[70-75,79].

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

Структура и объем диссертации. Диссертация изложена на 133 страницах и состоит из введения, пяти глав, заключения, списка литературы и приложений. Работа иллюстрирована 158 рисунками и 5 таблицами. Библиографический указатель включает 79 отечественных и иностранных источников.

ГЛАВА 1:

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

1.1. Общий критериальный анализ методов сжатия

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

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

Второе направление разрабатывается для систем, в которых обработка и оценка результирующей информации связана с восприятием человеком, субъективным восприятием различными системами человека (зрительное восприятие, восприятие аудиоинформации и проч.) Основное применение такие методы находят в системах мультимедиа [8].

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

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

1. коэффициент сжатия;

2. скорость работы алгоритма сжатия;

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

Например, для некоторых условий могут быть выдвинуты дополнительные требования [6]:

3. скорость работы алгоритма в прямом направлении (сжатие данных);

4. скорость работы алгоритма в обратном направлении (восстановление данных);

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

6. простота аппаратной реализации;

Формирование показателя качества для методов сжатия мультимедийных данных является еще более сложной задачей, поскольку критерии качества должны учитывать не только специфику области применения, но и специфику восприятия результирующей информации конечным звеном, т.е. человеком. Следовательно, появляются дополнительные критерии (например, при оценке алгоритмов сжатия изображений) [11,12]:

7. качество восстановленного изображения. При этом оценка качества зависит от конкретной области применения и связана со спецификой работы зрительной системы человека;

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

9. устойчивость к ошибкам, обусловленным искажениями в потоках сжатых данных;

10. Отсутствие скопления ошибок преобразований (связанных с применением метода сжатия) при многократных применениях метода;

11. Прочее.

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

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

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

1.2. Классификация методов сжатия цифровых изображений.

Классификацию методов сжатия растровых изображений обычно осуществляют по двум признакам: способ обработки элементов изображения при кодировании[13,14] и точность восстановления информации[15].

По способу обработки элементов растрового изображения выделяют методы кодирования с поэлементной обработкой и методы кодирования с пространственной обработкой. К методам кодирования с поэлементной обработкой относятся: импульсно-кодовая модуляция (ИКМ)[16,17], кодирование серий[18,14], статистическое кодирование[19,20], кодирование с предсказанием[21,22,23], кодирование последовательности одинаковых символов (Г - подобные алгоритмы)[24,25,26]. В этих методах каждый пиксель кодируется отдельно. К методам кодирования с пространственной обработкой относятся: интерполяционное кодирование [27,28], кодирование с преобразованием [29, 30, 31], векторное кодирование (квантование) [32-34], итеративное фрактальное кодирование [35,10,6]. В этих методах кодируется группа пикселей.

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

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

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

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

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

1.3. Методы сжатия данных без потери информации

1.3.1. Метод группового кодирования (RLE)

Групповое кодирование - Run Length Encoding (RLE) - один из самых ранних и самых простых методов архивации графики. Данный алгоритм необычайно прост в реализации. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в методе RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байтов. Замена их на пары "счетчик, значение" в большинстве случаев уменьшает избыточность данных [4,6,16].

В качестве примера предполагается следующая цепочка букв (17 байт), которая будет сжиматься: ABBBBBBBBCDEEEEF.

Используя метод RLE, компрессионный файл занимает 10 байт и имеет следующий вид: A*8BCD*4EF.

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

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

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

Коэффициенты сжатия варьируются от 1/64 до 2/1.

Данный метод применяется в форматах PCX, TIFF, BMP, TGA, PDF.

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

1.3.2. Метод Хаффмана

Данный метод был разработан в 1952 году и используется как составная часть и других схем сжатия, таких как LZW, Дефляция, JPEG. Идея алгоритма Хаффмана заключается в следующем. Если некоторые данные содержат различные числа, представленные в виде битовых цепочек фиксированной длины и частота, с которой различные числа присутствуют в этих данных, существенно различается, то заменив битовые цепочки фиксированной длины на битовые цепочки различной длины, причем так, чтобы более часто встречающимся числам соответствовали бы более короткие цепочки, можно получить уменьшение объема данных.

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

Алгоритм начинается составлением списка символов алфавита в порядке убывания их вероятностей. Затем от корня строится дерево,

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

Список литературы диссертационного исследования кандидат наук Филиппов, Тимур Константинович, 2013 год

СПИСОК ЛИТЕРАТУРЫ

[1] B.J1. Авербух Разработка средств компьютерной визуализации для научных исследований.

[2] Visualization in Scientific Computing, Special Issue, ACM SIGRAPH Computer Graphics, V. 21, N 6, November 1987.

[3] Авербух В.JI. К теории компьютерной визуализации // Вычислительные технологии. Т. 10, N 4, 2005, стр. 21-51.

[4] Сойфера В.А. Методы компьютерной обработки изображений - 2-е изд., испр.-М.: ФИЗМАТЛИТ, 2003. - 784с.

[5] Ватолин Д. Сжатие статических изображений. Открытые системы сегодня. № 8 (29) Апрель 1995.

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

[7] Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. - М.: Найка, 1982.

[8] Претт У. Цифровая обработка изображений. - М.: Мир. T.I, Т.2, 1982.

[9] Красильников Н.Н. Цифровая обработка изображений — М: Вузовская книга, 2001.

[10] Ватолин Д. Алгоритмы сжатия изображений. М.: Диалог-МГУ, 1999.

[11] Попов А.А. Объективные измерения качества изображения // Техника кино и телевидения, 1999, № 4, с. 21-24.

[12] Гласман К.Ф., Букина А.В. и др. Оценка качества изображения при видеокомпрессии // Техника кино и телевидения, 1999, № 8, с. 48-51.

[13] Сван Т. Форматы файлов Windows. - М.: Бином, 1995. - 258с.

[14] Douglas w. jones application of splay trees to data compression // general terms: Algorithms, Performance. Communication of the ACM. 31, 8 (August 1988), 996-1007.

[15] Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. - СПб: ВУС, 1999.-203 с.

[16] Сэломон Д. Сжатие данных, изображений и звука // Техносфера. Серия «Мир программирования», 2004.

[17] Duda R.O. Image Data Extraction (неопубликованные данные), July 1975

[18] Ричардсон Ян Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения (Н.264 and MPEG-4 Video Compression: Video Coding for Next-Generation Multimedia) // Серия «Мир цифровой обработки» // Издательство Техносфера, 2005. - 368 с.

[19] Поспелов В.В., Кислицина М.А. Использование преобразования Хаара для модификации алгоритма JPEG - сжатия изображений. Тезисы доклада III конференции «Распознавание образов и анализ изображений» ч.1. -Н.Новгород: РОАИ, 1997.- с. 210-212.

[20] Linde Y., Buzo A., Gray R. An Algorithm for Vector Quantization Designs //IEEE Transactions on Communications. - COM - 28. - 1980. - January.

[21] Haralik R.M., Shanmugan К., Dinstein I. Texture Featers for Image Classification // IEEE Trans. Systems. Man and Cybernetics. SMC - 3. - 1973. -№11 -pp. 610-621.

[22] Rosenfeld A., Connectivity in Digital Pictures. // J ACM. - 1970. - Vol. 17. -№l.-pp. 146-160.

[23] Kopylov P., Franti P. Context tree compression of multi-component map images // Proceedings Data Compression Conference, Snowbird Utah, March 2003.

[24] Назаров Jl.E., Назарова З.Т. Нейросетевой, фрактальный и JPEG алгоритмы сжатия изображений. // Информационные технологии. - 2001 .№ 1 .-С. 3-10.

[25] Saupe D. The Fatility of Square Isometrics In Fractal Image Compression. // IEEE International Conference of Image Processing. - 1996. - Vol.1. -№3. - pp. 60-67.

[26] Vasudev Bhaskaran Image and Video Compression Standards: Algorithms and Architectures (The Springer International Series in Engineering and Computer Science) // Springer; 2nd ed. edition (June 30, 1997).

[27] Ефимов B.M., Колесников A.H. Эффективность некоторых алгоритмов сжатия информации в двумерных массивах данных без потери точности при их восстановлении. // Автометрия. - 1997.-№6.- с. 93-97.

[28] Теория информации и кодирование / Самсонов Б.Б., Плохов Е.М., Филоненко А.И., Кречет Т.В. - Ростов н/Д, 2002. - 288 с.

[29] Умняшкин СВ., Кочетков М.Е. Анализ эффективности использования дискретных ортогональных преобразований для цифрового кодирования коррелированных данных // Известия вузов. Электроника. - №6. - 1998.-С.79-84.

[30] Цифровая обработка телевизионных и компьютерных изображений. // А.В. Дворкович, В.П. Дворкович, Ю.Б. Зубарев и др. - М.: Радио и связь, 1997.2-12с.

[31] Christiansen В.О., Schauser К.Е. Fast Motion Detection for Thin Client Compression // Proceedings Data Compression Conference, Snowbird Utah, March 2003.

[32] Iain E Richardson H.264 and MPEG-4 Video Compression // John Wiley & Sons, September 2003.

[33] ISO/I EC DIS 10918-1 Information Technology. Digital Compression and Coding Of Continuous tone Still Images: Compliance Testing /Ed. 1, JTSl/sc29, 1994.

[34] ISO/1 EC DIS 10918-1 Information Technology. Digital Compression and Coding Of Continuous tone Still Images: Extensions/Ed. 1, JTS l/sc29, 1994.

[35] Белей А.В. Типы компрессии при сжатии видеоданных // Телевидение в системах физической защиты, 2004.

[36] Фомин А.А. «Основы сжатия информации»//Санкт-Петербургский государственный технический университет; 1998.

[37] Климов A.C. Форматы графических файлов // С.-Петербург, Изд. "ДиаСофт" 1995.

[38] А. М. Яглом, Вероятность и информация.-М.:«Наука», 1973.

[39] Jacob Ziv, Abraham Lempel. A Universal Algorithm for Sequential Data Compression IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.

[40] Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC- М.Унитех, 1992.

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

[42] Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособ., М., Издательство Триумф, 2003.

[43] Salomon D. Data Compression: The Complete Reference, NY, SpringerVerlag, 2000.

[44] Wallace G. K. The JPEG still picture compression standard // Communication of ACM vol. 34, № 4, April 1991.

[45] http://ru.wikipedia.org/wiki/Texничecкий_aнaлиз

[46] http://ru.wikipedia.org

[47] http://grwp.ru/node/251

[48] www.wavelet.org/wavelet/.

[49] Новиков JI.В. «Основы вейвлет-анализа сигналов» // Учебное пособие, СПб. 1999.

[50] Переберин A.B. - «О системе вейвлет преобразований»// «Вычислительные методы и программы» Т.2. 2001.

[51] Астафьева Н.М. «Вейвлет-анализ: основы теории и примеры применения»// «Успехи физических наук» Том 166 №11 Ноябрь 1996.

[52] Дремин И.М., Иванов О.В., Нечитайло В. А. «Вейвлеты и их использование»// «Успехи физических наук» Том 171 №5 Май 2001.

[53]http://rain.ifmo.ru/cat/view.php/theory/datacompression/ipeg2006

[54] http://algolist.manual.ru/compress/image/ipeg.php

[55] Моргун Д.А., Кощеев В.П., Штанов Ю.Н. Численное решение стохастических дифференциальных уравнений движения частиц в плоскостных каналах кристалла // Тезисы докладов XL международной конференции по физике взаимодействия заряженных частиц с кристаллами / Под. ред. проф. А.Ф. Тулинова. ~ М.: Университетская книга, 2010 — 226с.

[56] Кощеев В.П. Ланжевеновский поход в теории каналирования. Сургут: СурГУ, 2001. С. 86.

[57] В.П. Кощеев, Д.А. Моргун, Н.В. Сафин, А.К. Холодов - Компьютерное моделирование траекторий каналированных ионов//Поверхность. Рентгеновские, синхротронные и нейтронные исследования.-2006- с.48-51.

[58] Алберг Дж. Теория сплайнов и ее приложения. М.: Мир, 1972.

[59] http://qt.nokia.com/

[60] http://mathgl.sf.net/

[61] http://maximumcompression.com/

[62] http://www.win-rar.ru/

[63] http://winzip.allsoft.ru/detail.php/

[64] http://www.7-zip.org/

[65] Walter Scandale et al., Phys. Rev. Lett. 101, 164801 (2008).

[66] Barnsley M.F. Fractal Image Compression. // Notices, V.43, No.6, 1996.

[67] Ланнэ A.A.; Матюшкин Б.Д., Улахович Д.А. Основы цифровой обработки сигналов. Учебное пособие, ч.З. - СПб., 1998

[68] Мандельброт Б., Хадсон Р. Л. - (Не)послушные рынки. Фрактальная революция в финансах -2006, Издательство: Вильямс-408с.

[69] http://keygene.narod.ru/l.htm

[70] Филиппов, Т.К. Применение вейвлет - преобразования информации при техническом анализе экономических данных /Т.К.Филиппов// Научно-технические ведомости. - СПбГПУ. -2012. - №5. -С.95-99.

[71] Филиппов, Т.К. Сжатие выходных данных в программном комплексе "TROPICS" на основе алгоритма вейвлет-преобразования информации / Т.К. Филиппов, В.А. Галкин, Д.А. Моргун //Вестник Воронежского государственного технического университета.-2012.-№11.С.4.

[72] Филиппов, Т.К. Применение вейвлет - преобразования информации при техническом анализе экономических данных /Т.К.Филиппов // Развитие инновационной экономики в России: сб. науч. тр. 3-ей Всерос. Заочной науч.-практ. Конф. -МАТИ. - Москва. -2012. -С.547-551.

[73] Филиппов, Т.К. Разработка средств компьютерной визуализации для научных исследований: методы сжатия цифровых данных на основе вейвлет и фрактального анализа/Т.К.Филиппов // Молодой ученый: научный журнал. -2012, №2(37).-С. 71-74.

[74] Филиппов, Т.К. Имитационное моделирование/Т.К. Филиппов//Актуальные проблемы анализа и построения информационных систем и процессов: сб. ст. междунар. Науч.-технич. конф. - Таганрог: Изд-во Технологического ин-та ЮФУ, 2010. -С. 204-206.

[75] Филиппов, Т.К. Применение вейвлет-преобразований и фрактального кодирования при сжатии цифровых данных / Т.К.Филиппов // Фундаментальные и прикладные исследования: проблемы и результаты - сб. мат-лов III Междунар. науч.-практ. конф. - Новосибирск: Изд-во «Сибпринт», 2013.-С. 160-164.

[76] Саутов Е.Ю. Разработка и анализ неэталонных алгоритмов оценки качества сжатых изображений: 2008 г.: Автореф. дис. канд. техн. наук. М., 2008.-4с.;

[77] http ://www. entropyware. info/images .html

[78] http://www.codec.ru/information/psnr_checker.html;

[79] Филиппов Т.К. Сравнительный анализ оценки качества сжатых полутоновых изображений методами вейвлет и jpeg преобразований / Т.К.Филиппов // «Северный регион: наука, образование, культура»: Научный и культурно-просветительский журнал. - 2013. - № 2 (28). -С. 97-102.