Базы данных и информационные технологии (стр. 9 из 28)
Итак, рассмотрим математическое обоснование возможности фрактального сжатия.
Есть отображение
, где 
– множество всех возможных изображений. W является объединением отображений wi:  | (1) |
где R – изображение, а di – какие-то (возможно, перекрывающиеся) области изображения D. Каждое преобразование wi переводит di в ri. Таким образом:
 | (2) |
Такие отображения называются сжимающими, и для них справедливо следующее утверждение:
Если к какому-то изображению F0 мы начнём многократно применять отображение W таким образом, что
 | (5) |
то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F0:
 | (6) |
Это конечное изображение F называют аттрактором, или неподвижной точкой отображения W. Также известно, что если преобразования wi являются сжимающими, то их объединение W тоже является сжимающим.
3. Типовая схема фрактального сжатия
С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки ri, называемые ранговыми областями. Далее для каждой области ri находят область di и преобразование wi такие, что выполняются следующие условия:
1. di по размерам больше ri.
2. wi (ri) имеет ту же форму, размеры и положение, что и ri.
3. Коэффициент u преобразования wi должен быть меньше единицы.
4. Значение должно быть как можно меньше.
Первые три условия означают, что отображение wi будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия»). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.
Таким образом, для компрессии изображения W нужно:
1. Разбить изображение на ранговые области ri (непересекающиеся области, покрывающие все изображение).
2. Для каждой ранговой области ri найти область di (называемую доменной), и отображение wi, с указанными выше свойствами.
3. Запомнить коэффициенты аффинных преобразований W, положения доменных областей di, а также разбиение изображения на домены.
Соответственно, для декомпрессии изображения нужно будет:
1. Создать какое-то (любое) начальное изображение R0.
2. Многократно применить к нему отображение W (объединение wi).
3. Так как отображение W сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена.
Именно это и позволяет при развертывании увеличивать его в несколько раз. Особенно впечатляют примеры, в которых при увеличении изображений природных объектов проявляются новые детали, действительно этим объектам присущие (например, когда при увеличении фотографии скалы она приобретает новые, более мелкие неровности).
4. Оценка коэффициента сжатия и вычислительных затрат
Размер данных для полного определения ранговой области рассчитывается по формуле:
 | (10) |
где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости.
 | (11) |
где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
 | (12) |
Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
 | (13) |
где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области.
Для хранения преобразования T необходимо 3 бита.
Для хранения U и V необходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером 256x256 пикселей, и будем исследовать доменную область с шагом 4 пикселя.
Nd = Md = (256 - 8 + 1) / 4 = 62
Nb = Mb = CEIL (log2 62) = 6
Х = 12
Z = 12 + 3 + 6 + 6 = 27
Коэффициент сжатия S составляет
S = (8 * 8 * 8) / 27 = 19
Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.
А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области – 1'024 штуки, для каждой – все ранговые – 58'081 штука (при шаге 1), а для каждой из них, в свою очередь, – все 8 преобразований. Итого получается 1'024 х 58'081 х 8 = 475'799'552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.
К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всего 256 х 256 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
Лекция 5. Нормальные формы отношений
В процессе проектирования базы данных возникают вопросы: хорошо ли спроектированы отношения между сущностями? Правильно ли они отражают предметную область?
На стадии физической реализации базы данных отношения преобразуются в таблицы, атрибуты становятся столбцами таблиц, для ключевых атрибутов создаются уникальные индексы, домены преображаются в типы данных, принятые в конкретной СУБД.
При этом также возникают вопросы: хорошо ли спроектированы таблицы? Правильно ли выбраны индексы?
Для ответа на этот вопрос необходимо рассмотреть понятие нормальной формы.
Рассмотрим в качестве примера предметной области некоторую организацию, выполняющую проекты. Модель предметной области опишем следующим неформальным текстом:
1. Сотрудники организации выполняют проекты.
2. Проекты состоят из нескольких заданий.
3. Каждый сотрудник может участвовать в одном или нескольких проектах, или временно не участвовать ни в каких проектах.
4. Над каждым проектом может работать несколько сотрудников, или временно проект может быть приостановлен, тогда над ним не работает ни один сотрудник.
5. Над каждым заданием в проекте работает ровно один сотрудник.
6. Каждый сотрудник числится в одном отделе.
7. Каждый сотрудник имеет телефон, находящийся в отделе сотрудника.
8. О каждом сотруднике необходимо хранить табельный номер и фамилию. Табельный номер является уникальным для каждого сотрудника.
9. Каждый отдел имеет уникальный номер.
10. Каждый проект имеет номер и наименование. Номер проекта является уникальным.
11. Каждая работа из проекта имеет номер, уникальный в пределах проекта. Работы в разных проектах могут иметь одинаковые номера.
Начинающий проектировщик будет использовать отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Номер сотрудника, ФИО, номер отдела, телефон, номер проекта, название проекта, номер задания), имеющее сложный ключ).
Действительно, зачем разбивать данное отношение на несколько более мелких отношений, если оно заключает в себе все данные? А разбивать надо потому, что при использовании универсального отношения возникает несколько проблем:
1. Проблема избыточности. Даже одного взгляда на отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней с большой избыточностью. Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг от друга данные - и данные о сотрудниках, и об отделах, и о проектах, и о работах по проектам. Пока никаких действий с отношением не производится, это не страшно. Но как только состояние предметной области изменяется, то, при попытках соответствующим образом изменить состояние базы данных, возникает большое количество проблем.