46928 (597308), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.

2. Математические основы фрактального сжатия

Фрактальные методы сжатия позволяют сжать информацию в 10 000 раз. Все известные программы фрактальной компрессии базируются на алгоритме Джеквина – сотрудника Барнсли, который в 1992 году при защите диссертации описал практический алгоритм фрактального сжатия. Несомненным достоинством работы было то, что вмешательство человека в процесс сжатия удалось полностью исключить.

Рассмотрим механизм фрактального сжатия данных. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей. Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли Первое задается тремя, а второе - питью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт. Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.

Итак, рассмотрим математическое обоснование возможности фрактального сжатия.

Есть отображение , где – множество всех возможных изображений. W является объединением отображений w_i:

где R – изображение, а d_i – какие-то (возможно, перекрывающиеся) области изображения D. Каждое преобразование w_i переводит d_i в r_i. Таким образом:

Такие отображения называются сжимающими, и для них справедливо следующее утверждение:

Если к какому-то изображению F₀ мы начнём многократно применять отображение W таким образом, что

то в пределе, при i, стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F₀:

Это конечное изображение F называют аттрактором, или неподвижной точкой отображения W. Также известно, что если преобразования w_i являются сжимающими, то их объединение W тоже является сжимающим.

3. Типовая схема фрактального сжатия

С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки r_i, называемые ранговыми областями. Далее для каждой области r_i находят область d_i и преобразование w_i такие, что выполняются следующие условия:

1. d_i по размерам больше r_i.

2. w_i (r_i) имеет ту же форму, размеры и положение, что и r_i.

3. Коэффициент u преобразования w_i должен быть меньше единицы.

4. Значение должно быть как можно меньше.

Первые три условия означают, что отображение w_i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия» ). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.

Таким образом, для компрессии изображения W нужно:

1. Разбить изображение на ранговые области r_i (непересекающиеся области, покрывающие все изображение).

2. Для каждой ранговой области r_i найти область d_i (называемую доменной), и отображение w_i, с указанными выше свойствами.

3. Запомнить коэффициенты аффинных преобразований W, положения доменных областей d_i, а также разбиение изображения на домены.

Соответственно, для декомпрессии изображения нужно будет:

1. Создать какое-то (любое) начальное изображение R₀.

2. Многократно применить к нему отображение W (объединение w_i).

3. Так как отображение W сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена.

Именно это и позволяет при развертывании увеличивать его в несколько раз. Особенно впечатляют примеры, в которых при увеличении изображений природных объектов проявляются новые детали, действительно этим объектам присущие (например, когда при увеличении фотографии скалы она приобретает новые, более мелкие неровности).

4. Оценка коэффициента сжатия и вычислительных затрат

Размер данных для полного определения ранговой области рассчитывается по формуле:

где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости.

где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:

Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:

где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области.

Для хранения преобразования T необходимо 3 бита.

Для хранения U и V необходимо 9 и 7 бит соответственно.

Для примера возьмём изображение размером 256x256 пикселей, и будем исследовать доменную область с шагом 4 пикселя.

Nd = Md = (256 - 8 + 1) / 4 = 62

Nb = Mb = CEIL (log₂ 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. Каждая работа из проекта имеет номер, уникальный в пределах проекта. Работы в разных проектах могут иметь одинаковые номера.

Начинающий проектировщик будет использовать отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Номер сотрудника, ФИО, номер отдела, телефон, номер проекта, название проекта, номер задания), имеющее сложный ключ).

Характеристики

Список файлов книги