Введение к работе
Актуальность темы. Сжатие данных - одна из самых важных компонент современных систем обработки информации на ЭВМ. Это связано с совершенствованием цифровой измерительной аппаратуры, возможностью и удобством использования компьютеров для обработки, передачи и хранения поступающих данных. При этом объем хранимой и передаваемой информации обычно весьма велик. Возникает проблема эффективного сжатия данных без потерь либо с допустимым уровнем таких потерь.
В настоящее время разработаны эффективные методы архивации данных. Эти алгоритмы кодируют данные без потери информации. Они основаны на замене часто повторяющихся последовательностей короткими кодами (кодирование по алгоритму Хаффмана или Лемпеля-Зива). Эти методы, хорошо применимые при сжатии текстов и монохромных изображений, неэффективны при сжатии вещественных данных (упаковке вещественных таблиц, сжатии экспериментальных данных), а также при сжатии полутоновых и цветных изображений.
По этой причине для сжатия экспериментальных данных, вещественных таблиц, а также полутоновых и цветных изображений используются вычислительные алгоритмы, в которых допускается определенный уровень потери информации. Широко известны алгоритмы интерполирования и экстраполяции, алгоритмы импульсно-кодовой модуляции (ИКМ), алгоритмы с предсказанием (ДИКМ), алгоритмы посредством преобразований (Карунена-Лоэва, Фурье), гибридные схемы (JPEG).
Одним из эффективных вычислительных методов сжатия вещественных данных, являющихся функциональными
зависимостями от двух переменных, может быть алгоритм ЕП-приближения. Этот алгоритм позволяет сжимать данные с желаемым уровнем точности. При этом процесс восстановления данных, в отличии от многих алгоритмов, выполняется достаточно быстро.
При сжатии цветных изображений довольно важную роль играет разложение изображения на полутоновые составляющие (факторы). Обычно в применяемых алгоритмах сжатия цветных изображений, например, в алгоритме JPEG, используются универсальные разложения для всех изображений (стандарты PAL, SECAM, NTSC). При этом не учитываются особенности конкретного сжимаемого цветного изображения. Использование факторного анализа для получения таких разложений часто позволяет получать более удобные разложения с точки зрения сжатия.
Пели работы состоят:
-
В разработке эффективных вычислительных схем и алгоритмов для решения задач сжатия непрерывных и дискретных функциональных зависимостей от двух переменных, в частности, полутоновых изображений.
-
В разработке методов факторного анализа цветных изображений; в создании на их основе экспериментального программного обеспечения по сжатию данных и проведении сравнительных численных экспериментов.
Научная новизна и практическая ценность работы.
1. Для сжатия экспериментальных данных разработаны конкретные вычислительные схемы сжатия с требуемой степенью точности на основе алгоритма ЕП-
аппроксимации с применением непрерывных и дискретных сплайнов. Алгоритм П-аппроксимации сформулирован на основе общего подхода, что позволяет значительно расширить класс функциональных зависимостей и типы оценок для получения требуемых точностей.
-
Для сжатия цветных изображений предложены новые методы разложения на полутоновые компоненты на основе факторного анализа изображений. Разложения строятся в новых системах координат, зависящих от конкретного изображения. <
-
Предложен новый алгоритм округления цветов до заданной палитры на основе метода октодеревьев. Данный метод позволяет строить рекурсивные структуры по принципу оглавления в книге, что обеспечивает быстрый поиск "ближайшего" цвета.
-
Создано программное обеспечение по сжатию функциональных зависимостей от двух переменных, факторному анализу цветных изображений, сжатию таких изображений. '- "
Апробация работы. Основные результаты работы докладывались на Международном симпозиуме по численному анализу - ISNA-92 (Прага, 1992), на XXIV Региональной Математической молодежной школы-конференции (Екатеринбург, 1993), на XX Дальневосточной математической школе-семинаре им. академика Е.В. Золотова по проблемам математического моделирования и численного анализа (Находка, 1992), на VII Всесибирской школе по методам вычислительной математики (Красноярск, 1991), на VIII Всесибирской
школе по методам вычислительной математики (Шушенское, 1993), на III Региональной конференции по теории аппроксимации и задачам вычислительной математики (Новосибирск, 1991), на объединенном семинаре отдела математического обеспечения обработки изображений и отдела автоматизации проектирования и машинной графики ВЦ СО РАН под руководством профессора В.П. Пяткина (1993), на семинаре по пакетам прикладных программ ВЦ СО РАН под руководством профессора В.П.Ильина (1993).
Публикации. По теме диссертации опубликованы 4 работы.
Объем работы. Диссертационная работа состоит из введения, двух глав, заключения, списка литературы и трех приложений. Основной текст диссертации содержит 88 страниц, 26 рисунков и 3 таблицы. Список литературы включает 64 наименования. В приложениях (на компьютерной дискете) содержится 50 цветных иллюстраций.
Похожие диссертации на Экспериментальное программное обеспечение по сжатию функциональных зависимостей и цветных изображений
