Разработка алгоритма для кодирования изображений с использованием функций Уолша
ВВЕДЕНИЕ
В современном мире человечество располагает богатыми возможностями для создания, хранения и передачи информации. Понятие, виды, свойства информации и объем информационных ресурсов в любой области деятельности человека растет огромными темпами. Массивы передаваемой информации увеличиваются непрерывно: начиная от бытовых разговоров, заканчивая информационным потоком в интернете. Рост объема информации обусловлен усложнением всех сфер жизнедеятельности современного общества, определяющим фактором является развитие технологий и научный прогресс.
Одним из основных видов передаваемой информации являются изображения. Они используются во всех сферах жизни, начиная от сельского хозяйства и заканчивая ядерными исследованиями. Однако, передача и хранение графического материала в несжатом виде требует больших затрат. Поэтому необходимы алгоритмы, которые, без существенных потерь данных, позволяют хранить и передавать сжатые изображения.
Алгоритмы сжатия изображения с потерями по
СОДЕРЖАНИЕ
Введение……………………………………………………………………... 6
1 Обзор методов кодирования изображений……………….…………….. 7
2 Функции Уолша в различных системах упорядочения……………....... 11
3 Использование вейвлетов для сжатия изображений...………………..... 16
4 Использование функций Уолша для сжатия графической информации……... 20
4.1 Разработка алгоритма кодирования изображений…………………. 20
4.2 Моделирование в интерактивной среде MATLAB...……….………. 25
4.3 Программная реализация кодирования на языке Python………….. 27
4.4 Разработка интерфейса взаимодействия с пользователем……….... 29
4.5 Расчёт коэффициента сжатия……………………………………….. 31
5 Разработка структуры кодера...………………………………………….. 35
6 Исследовательская часть…………………………….…………………… 37
7 Экономическое обоснование научно-исследовательской работы...…... 42
Заключение…………………………………………………………………... 54
Список использованных источников………………………………………. 56
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
[1] Сэломон, Д. Сжатие данных изображений и звука / Д. Сэломон, пер. с англ./ В. В. Чепыжова. М.: Техносфера, 2004. – 368 с.
[2] Лосев, В. В. Поиск и декодирование сложных дискретных сигналов / В. В. Лосев, Е. Б. Бродская, В. И. Коржик. М.: Радио и связь, 1988. – 346 с.
[3] Касами, Т. Теория кодирования / Т. Касами, пер. с япон. А.В. Кузнецова. М.: Мир, 2006. – 571 с.
[4] Билинский И. Я. Стохастическая цифровая обработка сигналов / И. Я. Билинский, Рига : Зинатне, 1983. – 292 с.
[5] Харкевич, А. А. Спектры и анализ / А. А. Харкевич. М.: Физмат, 1962. – 241 с.
[6] Конопелько, В. Теория прикладного кодирования: учеб. пособие. В 2 т. / В. К. Конопелько, В. А. Липницкий, В. Д. Дворников– Мн. : БГУИР, 2004. – Т. 2. – 398 с.
[7] Кларк, Дж. Кодирование с исправлением ошибок в системах цифровой связи: пер. с англ. / Дж. Кларк. М. : Радио и связь, 1987. – 392 с.
[8] Терёхин, В. Моделирование в системе MATLAB: учеб. пособ. / В. В. Терёхин. – Кемеровский государственный университет. Новокузнецк. : Кузбассвузиздат, 2004. – 376 с.
[9] Техническая документация Django [Электронный ресурс]. – Режим доступа : https://www.djangoproject.com/.
[10] Никитин, Г. Свёрточные коды: учеб. пособ. / Г. Никитин. – СПбГУАП. СПб. : 2001. 80 с.
[11] Патентно-информационные ресурсы Российской Федерции [Электронный ресурс]. – Режим доступа : http://www1.fips.ru/wps/wcm/connect/content_ru/ru.
[12] Информационно-справочный портал WIPO GOLD [Электронный ресурс]. – Режим доступа : http://patentscope.wipo.int/search/ru/search.jsf.
[13] Евразийская патентная информационная система [Электронный ресурс]. – Режим доступа : http://eapatis.com/ru.
[14] Патентное ведомство Япония [Электронный ресурс]. – Режим доступа : www.jpo.go.jp.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.
Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому потомку соответствует нулю в коде, а к правому – единице. Если пометить листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Алгоритм построения дерева Хаффмана и получения кодов Хаффмана:
1 Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа.
2 Выбираются два свободных узла дерева с наименьшими весами.
3 Создается их родитель с весом, равным их суммарному весу.
4 Родитель добавляется в список свободных узлов, а двое его потомков удаляются из этого списка.
5 Одной дуге, выходящей из родителя, ставится в соответствие еди-ничный бит, другой — нулевой.
6 Шаги, начиная со второго, повторяются