На Рис. 3.3.5 показан полученный по такой схеме тре^ уровень разбиения и соответствующий ему список индекс Например, заштрихованный блок имеет индекс 3,2,4.

Рис. 3.3.5.

Разбиение метолом квалро-лерева (3 уровня) и соответствующий список инлексов. Заштрихованному блоку соответствует инлекс 3.2.4

Нетрудно себе представить, как быстро увеличивается список индексов при увеличении числа уровней квадродерева и уменьшении допустимой погрешности.

з.з.з. Отображение доменных областей в ранговые

Главный вычислительный шаг во фрактальном кодировании-это сравнение доменной и ранговой области. Для каждого рангового блока алгоритм сравнивает варианты преобразования всех доменов (или хотя бы всех доменов заданного класса, о чем пойдет речь в следующей главе) к этому ранговому блоку. Это аффинные преобразования, такие как описанные в раз-деле 3.2.1, пространственная составляющая которых жестко ограничена параллельным переносом, сжатием и одним из восьми вариантов ориентации. Варианты ориентации вклкЯ^ ют четыре поворота на 90° и зеркальное отражение в каЖДоИ ориентации. В статье [39] автор утверждает, что использование этих восьми ориентации необязательно и столь же хор0* шие результаты могут быть получены при использован^ большего множества доменов без применения поворотов. Пр0* грамма, прилагаемая к книге, позволяет исследовать эту в°3 можность, так как количество вариантов ориентации выбир* ется пользователем и принимает значения от 1 до 8, прич^ единица соответствует тождественному преобразованию.

фрактальное кодирование изображений в градациях серого

87

Поиск соответствия между доменными и ранговой областями (будем называть его доменно-ранговым сопоставлением), реализованный в прилагаемой программе, - это трехшаговый процесс; схема его представлена на Рис. 3.3.6. Во-первых, к выбранному домену применяется один из восьми (или меньше) базовых поворотов/отражений. Во-вторых, вращаемая доменная область сжимается, чтобы соответствовать размеру ранговой области. Заметим, что на практике ранговая область должна быть меньше доменной, для того чтобы суммарное отображение было сжимающим. И, наконец, методом наименьших квадратов вычисляются оптимальные параметры яркости и контрастности.