Содержание к диссертации
Введение
1. Анализ методов сжатия графической информации 21
1.1 Обоснование целесообразности разработки нового методасжатия графической информации 1.2 Анализ существующих методов сжатия графической
1.3 Выбор критериев для оценки эффективности методов сжатия 41
1.4 Анализ и определение требований к методу фрактального 44
1.5 Анализ существующих стеганографических методов и обоснование целесообразности их применения в разрабатываемом методесжатия графической информации 49
1.6 Постановка задачи разработки метода фрактального сжатияграфической информации с возможностью реализациистеганографических функций
1.7 Выводы
2. Разработка моделей описания и обработки графической информации
2.1 Исследование концептуальных основ возможности представления графической информации с использованием ее фрактальных свойств 64
2.2 Разработка метода реализации стеганографической вместимо- 76
2.3 Разработка метода математического описания процессов, обладающих фрактальными и мультифрактальными свойствами
2.3.1 Разработка модели описания шумовой составляющей графической информации
2.3.2 Разработка метода математического описания процессов,обладающих фрактальными и мультифрактальными свойствами 2.4 Разработка модели описания и обработки графической инфор- з
2.5 Выводы 101
3. Разработка метода фрактального сжатия графической информации с реализацией стеганографи-ческих функций 103
ЗЛ Разработка обобщенного алгоритма метода фрактального сжатия графической информации 103
3.2 Разработка блок-схемы алгоритма подготовки сигнала для обработки ПО
3.3 Разработка алгоритма формирования библиотеки доменов 117
3.4 Обоснование рационального количества разбиений для методафрактального сжатия 122
3.5 Разработка блок-схемы алгоритма поиска пары «домен - ранго- 127
3.6 Разработка блок-схемы алгоритма формирования архива 133
3.7 Разработка блок-схемы алгоритма применения систем итерируемых функций 144
3.8 Разработка блок-схемы алгоритма формирования графическойинформации при ее восстановлении 147
3.9 Разработка блок-схемы алгоритма селекции носителя для внедрения файла-контейнера 147
3.10 Разработка блок-схемы алгоритма внедрения цифровой метки. 154
3.11 Разработка блок-схемы алгоритма фильтрации цифровой мет- 155
3.12 Выводы 156
4. Оценка эффективности разработанного методафрактального сжатия графической информации иразработка практических предложений по его применению 158
4.1 Разработка модели, оценки эффективности методов сжатияграфической информации 158
4.2 Оценка корректности алгоритмов разработанного метода 167
4.3 Оценка сложности разработанного метода фрактального сжатия 171
4.4 Оценка качества разработанного метода фрактального сжатия 173
4.5 Оценка симметричности разработанного метода сжатия 174
4.6 Оценка коэффициента сжатия и степени зашумленности вносимой в обрабатываемую графическую информацию 175
4.7 Оценка эффективности реализации стеганографических функ- 180
4.8 Предложения по практическому применению разработанногометода фрактального сжатия графической информации 183
4.9 Выводы 187
Заключение 189
Список использованных источников 192
- Выбор критериев для оценки эффективности методов сжатия
- Разработка метода математического описания процессов, обладающих фрактальными и мультифрактальными свойствами
- Разработка блок-схемы алгоритма подготовки сигнала для обработки
- Оценка симметричности разработанного метода сжатия
Введение к работе
Актуальность темы. Проблема передачи и хранения информации, представленной в цифровом виде, является одной из самых важных в областях, где используется вычислительная техника. Для получения компактного представления данных используются различные технологии сжатия. Их применение позволяет получить значительный выигрыш в ресурсах при эксплуатации носителей информации и повысить эффективность передачи данных по каналам связи.
Алгоритмы сжатия занимают значительное место в теории цифровой обработки изображений. Связано это с тем, что изображения, представленные в цифровой форме, требуют для хранения довольно большого объема памяти, а для передачи их по каналам связи необходимо значительное время. Так, для хранения изображения с Full HD разрешением 1920x1080 пикселей и 24 битами на отсчет требуется 5,93 Мбайта памяти. Чтобы передать его по типовому телекоммуникационному каналу со скоростью 1 Мбит/с, понадобится около 40 секунд. Современные исследования показывают, что такое время передачи не соответствует предъявляемым требованиям.
Актуальность диссертационных исследований определяется недостаточной степенью сжатия графической информации при требуемом качестве ее восстановления существующими на сегодняшний день методами сжатия. Эти методы также не позволяют выполнить требования по подтверждению целостности управляющей информации, внедряемой в файл сжатого изображения.
В настоящее время не исследован ряд вопросов, основным из которых является отсутствие моделей и методов:
- учитывающих мультифрактальные свойства шумовой составляющей графической информации, возникающей при ее обработке;
- реализации стеганографической вместимости, позволяющей передавать любую управляющую информацию совместно со сжатым файлом изображения, не увеличивая его объема и не влияя на качество восстановления;
- методики оценки эффективности обработки графической информации методами сжатия. Поэтому объектом исследований является процесс обработки графической информации различных классов, циркулирующей в системах обработки данных (СОД).
Актуальность темы диссертационной работы определяется необходимостью решения задач обусловленных тем, что существующие методы обработки графической информации не обеспечивают выполнения требований по степени ее сжатия и возможности одновременной передачи управляющей информации для заданного качества восстановления. Это приводит к невозможности улучшения характеристик ее обработки на базе использования известных методов сжатия в силу следующих их недостатков:
- невозможность достичь заданной степени сжатия графической информации при одновременном обеспечении требуемого качества ее восстановления, определяемого как соотношение сигнал/шум (Кс/ш). При требовании Кс/ш=30дБ коэффициент сжатия С должен составлять С150 - известные методы (JPEG, JPEG 2000) обеспечивают значение С=75. При требовании Кс/ш=35дБ коэффициент сжатия должен составлять С70 - известные методы обеспечивают значение С=25;
- отсутствие метода математического описания процессов на основе вэйвлет-преобразований, применяемого при обработке графической информации, обладающей фрактальными и мультифрактальными свойствами;
- отсутствие модели описания, учитывающей фрактальные свойства графической информации;
- отсутствие научно-методического аппарата, адекватно описывающего внедрение в обрабатываемую графическую информацию файла-контейнера с управляющей информацией, обеспечивающей реализацию стеганографических функций и методики оценки эффективности разработанного метода фрактального сжатия.
Выявленные противоречия при обработке графической информации в СОД пытаются разрешить на данный момент различными методами. Но они не обеспечивают комплексного решения задачи сжатия, подтверждения целостности передаваемых файлов графической информации и качества ее восстановления.
Предметом диссертационных исследований является научно-методический аппарат решения задач системного анализа, направленного на исследование процесса разработки нового фрактального метода сжатия графической информации в СОД. Обработка графической информации рассматривается как сложная система с изменяющимися во времени значениями входных данных. К их числу относятся: класс графической информации, ее объем, требуемая степень сжатия, ее шумовые характеристики и заданные требованиях по качеству восстановления.
Целью диссертационных исследований является повышение эффективности обработки графической информации за счет разработки метода фрактального сжатия, использования ее фрактальных свойств и возможности внедрения файла-контейнера без снижения качества ее восстановления.
Научной задачей исследований является разработка метода фрактального сжатия графической информации с возможностью реализации стеганографических функций. Этот метод обеспечивает более эффективную ее обработку по сравнению с существующими методами сжатия. Разработка методики оценки эффективности методов сжатия графической информации.
Для решения общей научной задачи ее целесообразно декомпозировать на пять частных научных задач:
1. Разработка метода реализации стеганографической вместимости файла-контейнера при заданных показателях качества восстановления графической информации.
2. Разработка метода математического описания процесса обработки графической информации, обладающей фрактальными и мультифрактальными свойствами.
3. Разработка модели описания обработки графической информации на основе систем итерируемых функций.
4. Разработка метода фрактального сжатия графической информации с реализацией стеганографических функций.
5. Разработка методики оценки эффективности методов сжатия графической информации.
Методы исследования: научно-методический аппарат системного анализа; математический аппарат теории фракталов, вэйвлет-преобразований, систем итерируемых функций, цифровой обработки сигналов и теории вероятностей.
Достоверность и обоснованность полученных результатов подтверждаются:
- обоснованностью вводимых допущений и ограничений;
- корректным выбором апробированного научно-математического аппарата системного анализа, теории фракталов, систем итерируемых функций, теории вероятности, а также использованием известных исходных данных о характеристиках существующих методов сжатия графической информации и систем обработки данных;
- ясной физической трактовкой используемых показателей;
- результатами оценки выбранных показателей качества разработанных и существующих методов сжатия графической информации, полученных с помощью предложенной методики оценки их эффективности.
Справедливость выводов эффективности разработанного метода подтверждена результатами оценки выбранных показателей качества и существующих методов сжатия графической информации.
Научная новизна полученных результатов заключается в том, что впервые:
- разработан метод математического описания процессов обработки графической информации, учитывающий ее фрактальные свойства и мультифрактальные свойства ее шумовой составляющей и позволяющий сохранить ее массу и стохастичность;
- разработан математический метод расчета стеганографической вместимости графической информации, рассматривающий ее как динамическую систему;
- разработана модель обработки графической информации, позволяющая реализовать заданный набор стеганографических функций;
- разработан метод фрактального сжатия графической информации, отличающийся от известных тем, что в нем реализована возможность внедрения в обрабатываемую информацию файла-контейнера, при выполнении заданных ограничений;
- разработана методика оценки эффективности методов сжатия графической информации.
Практическая значимость исследований заключается в возможности использования разработанных моделей, методов и полученных на их основе результатов и предложений при проектировании и эксплуатации современных и перспективных систем управления и принятия решений, в которых используется обработка графической информации.
На защиту выносятся следующие научные положения:
1. Метод математического расчета стеганографической вместимости обрабатываемой в СОД графической информации.
2. Метод математического описания процессов обработки графической информации.
3. Модель описания процесса обработки графической информации на основе использования систем итерируемых функций с реализацией набора стеганографических функций.
4. Метод фрактального сжатия графической информации с возможностью внедрения файла-контейнера.
5. Методика оценки эффективности методов сжатия графической информации, представленная впервые.
Апробация работы: основные результаты работы докладывались и обсуждались на 11-й НТК «Вузовская наука – Северо-Кавказскому региону» в СевКавГТУ в 2007г., (г. Ставрополь); на 3-й Международной НПК в СтГАУ в 2007г. (г. Ставрополь); на НТК «Инфоком-3» в СевКавГТУ в 2007г. (г. Ставрополь); на 4-й Международной НПК в СтГАУ в 2008г. (г. Ставрополь).
Публикации. Полученные автором результаты изложены в 8 печатных трудах, из них 4 опубликованы в журналах, входящих в перечень ВАК: «Теория и техника радиосвязи», «Информационные системы и технологии», «Вестник СевКавГТУ». Получены 2 свидетельства о государственной регистрации программ для ЭВМ.
Реализация результатов исследования. Основные результаты исследований внедрены, что подтверждено соответствующими актами:
- в учебном процессе при проведении занятий по дисциплине «Пилотажно-навигационные комплексы летательных аппаратов», в ВУНЦ ВВС, ВВА имени профессора Н. Е. Жуковского и Ю. А. Гагарина (акт о внедрении от 25. 04. 2011 года);
- в Воронежском НИИ «Вега» в ходе проведения ОКР «Кизил 9ЦМ-2» при разработке базового устройства обработки информации нового поколения системы связи «Кавказ-4» (акт о внедрении, приказ № 36 от 13.04.2011 года);
- при выполнении НИР: «Разработка предложений по повышению качества функционирования сетевых распределенных систем» (рег. № 432/4/1/652 от 10.06.2010 г.); «Исследование информационных аспектов внутрисетевой организации и управления современными сетями связи» (рег. № 143-Н от 16.02. 2009г.); «Разработка нового способа определения параметров трафика сети на основе вэйвлетов Хаара и имитационных моделей оптимизации топологических структур сетей связи» » (рег. № 432/4/1/653 от 10.06.2010 г.); и 2 ОКР «Исследование фрактальных свойств трафика в мультисервисных сетях» » (рег. № 267-Н от 23.11.2009 г.), «Кизил 9ЦМ-2» - при разработке базового устройства обработки информации нового поколения системы связи «Кавказ-4» (рег. № 36 от 13.04.2011 г.).
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, 7 приложений и заключения. Ее основное содержание изложено на 192 страницах основного текста, проиллюстрировано 75 рисунками и 15 таблицами. Библиографический список содержит 139 наименований.
Личный вклад автора. Результаты исследования автором получены единолично. В совместных публикациях автору принадлежит теоретическое обоснование возможности прогнозирования поведения сетевого трафика с применением методов вэйвлет-анализа, а также разработка математических соотношений для решения этих задач; разработка математических соотношений для определения нормированного размаха сетевого трафика на основе фактора Фано, сформированного различными источниками.
Выбор критериев для оценки эффективности методов сжатия
Задачи эффективной обработки графической информации в настоящее время являются ключевыми в процессах управления и принятия решения, требующих ее использования. Источниками графической информации являются различные объекты, такие, как системы видеонаблюдения, технического зрения, терминального управления и другие, используемые в различных областях при принятии управленческих решений [6].
Несмотря на существенные различия условий, в которых осуществляется применение источников графической информации и типов, обрабатываемых в них данных, они имеют много общего. Это обусловлено тем, что они используют общий набор методов и алгоритмов обработки для решения похожих задач. Проведенные оценки показали, что имеющейся опыт разработки систем преобразования графической информации, способствует расширению их применения в различных системах управления [6, 57].
Развитие вычислительной техники, позволяющей осуществлять обработку больших массивов информации в режиме реального времени, создает предпосылки для существенного расширения возможностей практического использования эффективных методов обработки графической информации [3, 57]. Например, в задачах управления движением используется метод распознавания, который сводится к распознанию отдельных объектов, элементов, ориентиров. Степень надежности такого распознавания существенно увеличится при использовании информации о трехмерной структуре наблюдаемых объектов. Она может быть получена от систем технического зрения, но это потребует значительного увеличения объема передаваемых данных [25, 26].
В течение последних 10 лет в рамках теории обработки графической информации бурно развивается совершенно новая область, объектом исследования которой являются методы ее сжатия. Появление этой области обусловлено специфическими особенностями изображений графической информации [8, 52].
Графическая информация требует намного больше памяти в СОД при ее хранении, чем текст. Так, например, изображение размером 500x800 пикселей, занимает 1,2 Мбайт - столько же, сколько 400 страниц текста (60 знаков в строке, 42 строки на странице). Данная ситуация приводит к необходимости выделения большого количества ресурсов СОД при работе с графической информацией. Указанная особенность графической информации определяет целесообразность разработки и применения новых, более эффективных, чем существующие, методов ее обработки [9].
Второй особенностью графической информации является то, что человек при ее анализе оперирует контурами, общим переходом цветов и сравнительно нечувствительно к малым изменениям. Таким образом, можно создать эффективные методы сжатия графической информации, в которых при восстановлении она не будет совпадать с оригиналом, однако человек этого не заметит. Данная особенность позволяет повысить эффективность методов сжатия графической информации при ее обработке в СОД [26].
Графическая информация обладает избыточностью в двух измерениях, обусловленной тем, что соседние точки по горизонтали и по вертикали близки по цвету. Кроме того, можно использовать подобие между цветовыми плоскостями R, G и В при сжатии, что дает возможность создать еще более эффективные методы обработки [61, 106]. Таким образом, при создании новых методов сжатия графической информации можно эффективно использовать особенности ее структуры.
Для эффективного использования всех особенностей графической информации при ее обработке необходимо более подробно рассмотреть ее структуру в СОД с точки зрения системного подхода. Для выявления особенностей системы обработки графической информации и определения требований к ней был использован методологический аппарат системного анализа. Он позволяет получить выходные характеристики, рассматриваемой системы, с учетом входных воздействий, управляющих воздействий и воздействий внешней среды. При этом выделяется три основных компонента системы - элементы, связи и операции [2]. Модель системы обработки графической информации представлена на рисунке 1.1.
Система обработки графической информации может быть представлена в виде совокупности трех подсистем, подсистемы сжатия, подсистемы восстановления и подсистемы передачи данных. К системе обработки графической информации приложены управляющие воздействия со стороны внешней среды и входные воздействия, которые определяют класс, обрабатываемой графической информации и ее объем. Представленная на рисунке 1.1 модель системы обработки графической информации в общем виде отражает процесс ее обработки с точки зрения системного подхода.
Рассмотрение функционирования системы обработки графической информации должно проводиться с учетом некоторых ограничений [2]. Следовательно, управляющее воздействие на подсистему сжатия осуществляется через выбранную систему ограничений, показатели которой определяются качеством восстановления в зависимости от предъявляемых требований.
Большие объемы графической информации, поступающие на обработку в СОД, определяют все более высокие требования к аппаратному обеспечению и размеру дискового пространства для ее хранения. Данное обстоятельство является определяющим в обосновании необходимости разработки нового метода фрактального сжатия графической информации, обеспечивающего более высокую степень ее сжатия.
Разработка метода математического описания процессов, обладающих фрактальными и мультифрактальными свойствами
Исследование фрактальных свойств графической информации позволяет использовать их для решения вопросов, связанных с ее сжатием.
В начале 80-х годов прошлого века была выдвинута гипотеза о возможности получения заранее заданной графической информации, как аттрактора хаотического процесса [4, 21, 71]. Гипотеза, основанная на исследованиях обнаруживших, что хаотические системы способны создавать ее различные формы такие, как странные аттракторы. Данная гипотеза явилась основой в направлении решения обратной задачи - при заданном классе графической информации построить хаотическую систему, для которой она является странным аттрактором. При этом использовалась специальная система отображений, названная в последствии системой итерируемых функций. Хотя СИФ в своей исходной форме не являются основой современных подходов к фрактальному сжатию графической информации, однако, они являются отправной точкой развития фрактальных методов ее сжатия [40, 82-84].
Термин фрактал был впервые введен Б. Мандельбротом [101]. Ключевое свойство, характеризующее фракталы - самоподобие. Фрактальный объект представляет собой некоторый набор элементов, который остается одним и тем же независимо от масштаба, то есть фрактал можно приближать до бесконечности. Второе свойство, характеризующее фракталы это его дробная размерность. Подробное изложение математической теории, лежащей в основе фрактального сжатия графической информации, приведено в [5, 28, 58, 83, 136]. В работе [73] приведено понятие дробной размерности, которая рассмотрена на основе обычной евклидовой размерности (где размерность линии равна единице, размерность поверхности равна двум, а размерность объема - трем) и расширена для тех понятий, дробная размерность которых имеет смысл.
Понятие расстояния можно расширить до более общего понятия метрики и ввести представление об объектах, как о точках в пространстве. Это позволит рассматривать графическую информацию в пространствах особого вида, называемых метрическими пространствами, и измерять расстояния между ее изображениями. Такой подход позволяет изложить алгоритм генерации заранее заданной фрактальной графической информации.
Известно [58], что в евклидовом пространстве R расстояние d2(x,y) между точками х = (xi,x2) и у - {ух,у2) определяется следующим образом: d2(x,y) = ((X]-yl)2+(x2-y2)2)l/2. (2.1) Однако, это не единственный способ измерения расстояний в пространстве R2. Другая функция расстояния dx(x,y) имеет вид [58]: d\ (х, у) = \хх - у11 + \х2 - у21. (2.2) Эти две функции по-разному определяют расстояние между двумя точками. Однако обе являются его мерами. При этом учитывается следующее: - не имеет значения, измеряется ли расстояние от точки х до точки у или отточки до точки х, (d(x,y) = d(y,x)); - расстояние от точки до нее самой равно нулю, то есть (d(x,x) -0); - кратчайшее расстояние между двумя точками - это расстояние по прямой линии между ними (d(x, у) d(x, z) + d(z, у)); - функция расстояния является вещественной, конечной и положительной для двух различных точек х а у (0 d(x,y) оо).
Функция расстояния, удовлетворяющая этим свойствам, является метрикой, а множество точек X вместе с метрикой d, определенной на множестве X - метрическим пространством (X,d). Графическую информацию можно рассмотреть как множество точек в пространстве R , опираясь на базовые определения, касающиеся метрического пространства (X,d), представленного следующиим рассуждениями [93]: 1. Последовательность точек [хп} называется сходящейся к точке х& X, если: для любого сколь угодно малого є О, существует множество N 0, такое что d{xn,х) є для всякого п N. При этом точка х называется пределом последовательности {хп}, то есть хп -» х. 2. Последовательность \хп} называется последовательностью Коши, если точки хп и хт становятся сколь угодно близкими друг к другу для достаточно больших пит. Следовательно, для любого сколь угодно малого є О существует N О, такое что d(xn, хт) є для всех т,п N. 3. Метрическое пространство, в котором каждая последовательность Коши сходится к точке этого пространства, называется полным метрическим пространством, следовательно, (R2,d2) -полное метрическое пространство. 4. Точка х называется предельной точкой, если существует последовательность точек, такая что х„ — х (за исключением точки х). 5. Множество А в метрическом пространстве (X,d) называется замкнутым, если оно содержит все свои предельные точки. Множество А вместе со всеми его предельными точками называется замыканием множества А и обозначается А. 6. Множество В в метрическом пространстве (X,d) ограничено, если существует точка х0 є X и конечное значение R, 0 R оо, такое что для каждого х є В выполняется условие:
Разработка блок-схемы алгоритма подготовки сигнала для обработки
Случайные каскады соответствуют физическим моделям турбулентности [67], однако они не сохраняют исходную массу, а детерминированные каскады обладают свойством сохранения массы, однако не учитывают стохастический характер процесса.
Таким образом, описание шумовой составляющей, появляющейся в результате обработки графической информации, требует компромисса между гибкими случайными и жесткими детерминированными каскадами. Для того, что бы решить обе задачи, то есть сохранить массу (детерминированного каскада) и стохастичность (случайного каскада), используется полуслучайное (или консервативное) правило. В соответствии, с которым присваиваем массу W интервалу /(о) и массу (l-W)-M интервалу /(і), где W- генератор консервативного каскада, являющийся случайной переменной, симметричной относительно своего среднего значения, равного 1/2. Таким образом, формируется по 88 следовательность случайных переменных W(jx,...,j„) для п \ со структурной зависимостью, определяемой как [59]: W(J\ ,...,Л-. Л) = 1 - W(Jx,.., Іп-х, 0), (2.34) где случайные переменные W(jx,...,jn_x,0),W(jx,...,jri_x,l) распределяются, так же как и W. Таким образом, формируются консервативный каскад, и совокупность мер /л„. Для всех п \ мера интервала I{jx,...,jn) определяется с помощью следующего выражения: »Mh,---Jn)) = M0-W{jx)-W{jx,j2)-..,W{jx,...Jn), (2.35) и вследствие этой мультипликативной структуры jun(j(jx,...,jn)) распределяется приблизительно по логонормальному закону [28, 58]. Причем в данном случае для всех п 1 мы имеем ju„ (/) = М . Основное отличие консервативного каскада от случайного заключается в том, как исходная масса, сосредоточенная в интервале «родителя», распределяется между левым и правым субинтервалами «детьми» на каждой ступени процесса конструирования. Построение консервативного каскада приводит к тому, что предельная мера jUx является не вырожденной, и существуют моменты //да = М . Учитывая выше изложенное в качестве основы для построения модели, учитывающей мультифрактальный характер шумовой составляющей графической информации, целесообразно использовать структуру консервативного каскада. Однако, данное утверждение требует проверки соответствия структурных свойств измеренного ряда значений основной конструкции консервативного каскада. В связи с этим осуществим разработку инверсного каскада, который позволяет установить, совпадает ли консервативное правило перераспределения массы в двух субинтервалах с основным интервалом. Если исследуемые данные обладают данным свойством, то статистические свойства генератора W основного консервативного каскада постоянны.
На рисунках 2.5 - 2.8 представлены результаты применения процедуры инверсного каскада к исследуемому процессу. Графики показывают эмпириче 89 ские функции плотности вероятностей отношений ребенок/родитель для ряда выбранных ступеней (1,9, 12) в конструкции инверсного каскада. На рисунках 2.5, 2.6 представлены графики эмпирических функций автокорреляции для соответствующих отношений (для 4 и 12 ступеней инверсного каскада). Рисунок 2.6 показывает эмпирическое среднеквадратическое отклонение как функцию ступени п в инверсной процедуре. Эти графики дают эмпирическое доказательство того, что в основе измеренного ряда лежит конструкция консервативного каскада. Фактически на различных ступенях в инверсной конструкции, эмпирически наблюдаемые свойства отношений дают генератор W, который соответствует нормальному распределению на интервале [0;lj со средним значением равным 1/2, т.е. он является симметричным и независимым на любой фиксированной ступени, что демонстрируют графики автокорреляционных функций. Рисунок 2.5 иллюстрирует то, что изменчивость генератора W происходит практически монотонно как функция ступени в инверсной конструкции с меньшим затуханием на грубых масштабах (на последних ступенях) по сравнению с масштабами с высокой разрешающей способностью (начальные ступени). Другими словами, генератор не фиксируется, и на каждом уровне наблюдается его изменчивость. Таким образом, наблюдаемая последовательность данных соответствует конструкции консервативного каскада.
Кроме того, проведем анализ масштабирования каскадов. Для этого сначала рассмотрим детерминированный каскад. Универсальным средством для проведения масштабно-временного анализа является вэйвлет-преобразование, что показано в [40].
В качестве базиса вэйвлетов выберем наиболее простой базис вэйвлетов Хаара, использование которого позволяет осуществить ортогональное вэйвлет-преобразование, причем материнский вэйвлет ц(х) имеет один исчезающий момент [78, 79, 87], т.е. \xri//(x)dx - 0 при г — 1.
Оценка симметричности разработанного метода сжатия
Зависимость времени обработки графической информации от минимального числа разбиений Зависимость времени обработки графической информации от минимального числа разбиений и порогового значения расстояния между блоками показана на рисунке 3.10. Из него видно, что при изменении аргумента в диапазоне значений от 1 до 5 при фиксированном пороговом расстоянии между блоками время обработки графической информации практически не изменяется. Значительный рост времени обработки наблюдается при изменении аргумента в диапазоне от 5 до 7. Таким образом, уменьшение значения минимального числа разбиений увеличивает коэффициент сжатия, улучшает качество восстановления, практически не оказывает влияния на время обработки. Следовательно, целесообразно установить значение минимального числа разбиений равным единице.
Блок поиска пары «домен - ранговая область» является наиболее ресурсоёмким в методе сжатия и от его реализации во многом зависит его вычислительная сложность. Это обусловлено большим числом процедур сравнения ранговых областей с элементами библиотеки доменов.
Поскольку производится поиск двух блоков графической информации связанных некоторым аффинным преобразованием, а одним из параметров аффинного преобразования является угол поворота одного блока относительно другого, то при сравнении должны учитываться все возможные варианты поворота [122]. Это приводит к необходимости ограничить область допустимых значений угла поворота.
При разработке метода фрактального сжатия графической информации принято допущение о том, что блок может быть повернут на п — градусов, где п = 0,...,3. Также к блоку может быть применена операция зеркального отображения относительно вертикальной оси. При этом число перебираемых положений ранговой области при сравнении с доменом сокращено до восьми.
Для реализации процедуры поиска необходимо выбрать правило для формирования таблицы расстояний, на основании которой можно было бы утверждать, что г -ый домен подобену -ой ранговой области, т.к. расстояние между ними в данной таблице не превышает порогового значения. Правило должно соответствовать следующим условиям [122]: 1. d(a, b) О, для любых a, b є X; 2. d(a,b) = 0, тогда и только тогда, когда а = Ъдля любых а,ЬєХ; 3. d(a,b) = d(b,a), для любых а,Ь Є.Х; 4. d(a,с) d(a,b) + d(b,с), для любых a,b,c s X. 128 В качестве альтернатив применяют три метрики, для вычисления расстояния между двумя блоками графической информации А = {а1,г = \..п) и B = {b;,i = \..n} [65]: 1. За расстояние принимается абсолютное значение математического ожидания разности между соответствующими элементами сравниваемых массивов, т.е: с/, (3.26) 2. За расстояние принимается максимальная разность между соответствую щими элементами сравниваемых массивов, т.е: d2 - max(a, - bi), i-\..n /3 27) 3. За расстояние принимается среднеквадратичное отклонение между эле ментами сравниваемых массивов, т.е. Ч, , ,2 3=,- 2 /- ) (3.28) V" ы Недостаток первой метрики заключается в том, что при расчете расстояния между блоками рассматривается разность между элементами, которая может принимать как положительные, так и отрицательные значения. Это может привести к тому, что два совершенно разных блока будут приняты за подобные. В то же время, если значения элементов одного массива больше элементов другого на некоторую величину d и d t, где t - пороговое значение расстояния, то соответствующие блоки не будут считаться подобными, даже если блоки имеют схожую структуру.
Использование второй метрики приводит к тому, что, если два блока графической информации отличаются значением уровня яркости одного пикселя при полном совпадении уровней яркости остальных, расстояние между ними в данной метрике будет большим, хотя глаз человека не способен заметить подобное отличие.
В разрабатываемом методе сжатия графической информации для решения задачи сравнения ее блоков использована третья метрика. Выбор обусловлен тем, что в данной метрике рассматриваются квадраты разностей между элементами массивов. Это приводит к тому, что, во-первых, не происходит компенсации положительных отклонений значений элементов отрицательными отклонениями, во-вторых, метрика чувствительна к большим отклонениям между элементами.
Похожие диссертации на Разработка метода фрактального сжатия графической информации в системах обработки данных
