- •Межрегиональный открытый социальный институт
- •Содержание
- •Примечание! 108
- •2. Цели и задачи дисциплины, ее место в учебном процессе
- •1.1. Цели и задачи дисциплины
- •1.2. Место дисциплины в учебном процессе
- •1.3. Итоговый контроль знаний по курсу
- •3. Содержание дисциплины
- •План занятий
- •3. Содержание дисциплины
- •План занятий
- •Наименование и краткое содержание лекций
- •Тема 2. Администрация базы данных.
- •Тема 3. Взаимодействие компонентов системы Баз данных.
- •Тема 4. Классификация субд.
- •Тема 5. Модели данных.
- •Тема 6. Уровни моделирования предметной области.
- •Тема 7. Концептуальное проектирование баз данных
- •Тема 9. Требования к распределенным базам данных
- •Тема 10. Транзакции.
- •Конспект лекций
- •Тема 2. Администрация базы данных
- •Тема 3. Взаимодействие компонентов системы баз данных
- •Тема 4. Классификация субд
- •Тема 5. Модели данных
- •5.1. Основные понятия реляционной модели данных
- •5.2. Целостность реляционных данных
- •5.3. Операции над отношениями
- •5.4. Нормализация баз данных
- •Тема 6. Уровни моделирования предметной области
- •Тема 7. Концептуальное проектирование баз данных
- •7.1.Даталогическое проектирование
- •7.2. Физические модели
- •Тема 8. Case-средства разработки баз данных
- •8.1. Пример нотации er-модели – метод idef1x
- •Тема 9. Требования к распределенным базам данных
- •9.1. Базовые архитектуры распределенной обработки
- •Сервер бд
- •Тема 10. Транзакции
- •Тема 11. Проблема сжатия больших информационных массивов.
- •Тема 11. Фракталы и Фрактальные методы архивации
- •2. Математические основы фрактального сжатия
- •3. Типовая схема фрактального сжатия
- •Методические рекомендации для выполнения лабораторных работ
- •Создание таблицы в режиме таблицы и определение свойств для полей таблицы
- •Импорт таблиц. Работа с мастером подстановок
- •Создание связей между таблицами
- •Ввод и просмотр данных в режиме таблицы
- •Заполните таблицу Продажи товаров, рис. 5.11
- •Создание формы базы данных с помощью мастера
- •Работа с конструктором форм. Элементы управления
- •Создание подчиненной формы
- •Оформление формы
- •Создание простого запроса на выборку
- •Задание нескольких условий отбора в запросе
- •Создание вычисляемого поля в запросе
- •Групповые расчеты в запросе
- •Создание запроса на удаление
- •Создание запроса на обновление
- •Создание запроса на создание таблицы
- •Создание отчета базы данных с помощью мастера
- •Просмотр и печать отчета
- •Создание макроса
- •Тестовая база
- •Ответы:
- •Глоссарий
2. Математические основы фрактального сжатия
Итак, рассмотрим математическое обоснование возможности фрактального сжатия.
Есть отображение ,
где – множество всех возможных изображений.является объединением отображений:
где – изображение,
– какие-то (возможно, перекрывающиеся) области изображения.
Каждое преобразование переводитв. Таким образом:
Будет логично представить изображение в виде функции двух переменных . На множестве всех таких функций введём метрику (расстояние между изображениями), например, таким образом:
Согласно теореме Банаха, существует определённый класс отображений, для которых существует константатакая, что для любых изображенийивыполняется неравенство
Такие отображения называются сжимающими, и для них справедливо следующее утверждение:
Если к какому-то изображению F0 мы начнём многократно применять отображение W таким образом, что
то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве :
Это конечное изображение называютаттрактором, илинеподвижной точкой отображения . Также известно, что если преобразованияявляются сжимающими, то их объединениетоже является сжимающим.
3. Типовая схема фрактального сжатия
С учётом вышесказанного, схема компрессии выглядит так: изображение разбивают на кусочки, называемыеранговыми областями. Далее для каждой области, находят областьи преобразованиетакие, что выполняются следующие условия:
по размерам больше,.
имеет ту же форму, размеры и положение, что и,
Коэффициент преобразованиядолжен быть меньше единицы.
Значение должно быть как можно меньше.
Первые три условия означают, что отображение будет сжимающим. А в силу четвёртого условия кодируемое изображениеи его образбудут похожи друг на друга. В идеале. А это означает, что наше изображениеи будет являться неподвижной точкой. Именно здесь используется подобие различных частей изображения (отсюда и название –«фрактальная компрессия»). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.
Таким образом, для компрессии изображения нужно:
Разбить изображение на ранговые области , (непересекающиеся области, покрывающие все изображение).
Для каждой ранговой области , найти область(называемуюдоменной), и отображение, с указанными выше свойствами.
Запомнить коэффициенты аффинных преобразований , положения доменных областей, а также разбиение изображения на домены.
Соответственно, для декомпрессии изображения нужно будет:
Создать какое-то (любое) начальное изображение .
Многократно применить к нему отображение (объединениеwi).
Так как отображение сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена.
Пусть дано изображение точек (гдеикратны 8), 256 градаций серого. Ранговые и доменные области будем брать квадратными. Исходное изображение разобьём на ранговые области размеромточек. Доменные области будем искать размеромточек путём перебора всех возможных положений. Существует всего 8 аффинных преобразований, переводящих квадрат в квадрат (повороты на, зеркальные отражения относительно центральной горизонтали, центральной вертикали, от главной и побочной диагоналей). Осталось найти только коэффициенты для преобразования цвета. Но значенияи(контрастности и яркости) можно легко найти аналитически.
Если есть две последовательности значений цвета пикселов (доменной области) и(ранговой области), то можно минимизировать среднеквадратичное отклонение цвета пикселов, представляющее собой вариант метрики различия изображений:
Для этого достаточно приравнять частные производные пои пок нулю, и решить уравнение относительнои. Получатся такие выражения:
при этом, если
то
Итак, какие же данные необходимо хранить в результате. Сетка разбиения на ранговые области постоянная для всех изображений, её хранить не надо. Остаётся положение ранговых областей (верхнего левого угла), номер преобразования и коэффициенты яркости и контрастности.
4. Оценка коэффициента сжатия и вычислительных затрат
Размер данных для полного определения ранговой области рассчитывается по формуле:
,
где – количество бит, необходимых для хранения координат нижнего левого угла домена
– количество бит, необходимых для хранения типа аффинного преобразования
и– для хранения коэффициентов контраста и яркости.
где и– количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
,
где – функция округления до максимального целого
и– количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
где и– вертикальный и горизонтальный размеры изображения
– размер доменного блока,– шаг поиска доменной области.
Для хранения преобразования необходимо 3 бита.
Для хранения инеобходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером пикселей, и будем исследовать доменную область с шагом 4 пикселя.
Коэффициент сжатия составляет
Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.
А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области – 1'024 штуки, для каждой – все ранговые – 58'081 штука (при шаге 1), а для каждой из них, в свою очередь, – все 8 преобразований. Итого получается действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.
К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всегопикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
5. Оптимизация алгоритма компрессии
Алгоритм нуждается в оптимизации по нескольким направлениям: по скорости, по качеству получаемого изображения, по степени компрессии.
Для снижения вычислительных затрат можно предпринять следующие меры:
Исследовать доменную область не полностью, а с некоторым шагом. Это также позволит увеличить степень сжатия, но скажется на качестве изображения.
Искать не лучшую доменную область, а удовлетворяющую некоторому . Хотя это может значительно увеличить скорость сжатия, но такой приём так же может значительно снизить качество результирующего изображения. В данном случае качество в значительной степени зависит от адекватности метрики различия между изображениями.
При поиске доменной области подвергать преобразованию не доменную область, а ранговую. Для этого удобно хранить 8 вариантов ранговых областей с различными преобразованиями. При этом в результирующий файл нужно записать обратное преобразование. Для всех преобразований, кроме двух, обратным является само это преобразование. Для поворота на инеобходимо записать поворот наисоответственно. Это значительно сократит вычислительные затраты, но также значительно увеличатся затраты оперативной памяти.
Для поиска доменной области можно использовать не перебор, а какой-либо из алгоритмов условной нелинейной глобальной оптимизации, такой, как алгоритм моделирования отжига или генетический алгоритм. В этом случае будет всего три варьируемых параметра (координаты доменной области и номер аффинного преобразования), а целевой функцией – среднеквадратичное отклонение доменной области от ранговой.
Для улучшения качества: в случае необнаружения доменной области, удовлетворяющей заданному , ранговую область можно разбить на 4 подобласти и произвести поиск домена для каждой из них. Это можно делать и дальше рекурсивно, до достижения некоторого минимального размера либо единичного пикселя. Но это увеличит вычислительные затраты и снизит коэффициент сжатия.
Для увеличения коэффициента компрессии можно идентифицировать однотонные блоки. Однотонным блокомбудем называть ранговую область, у которой среднеквадратичное отклонение от собственного среднего значения не превышает некоторого. При этом в выходной файл будет записана только средняя яркость точки, за счёт чего будет достигнуто сжатие 1 к 64 (для ранговых областей размером 8).