Новый взгляд на мир [Фрактальная геометрия] (Мир математики. т.10.) - страница 28

Кривая Гильберта также используется при цифровой обработке изображений. Если мы хотим распечатать изображение в градациях серого на лазерном принтере первого поколения, то нам понадобится приближенная бинарная модель изображения, так как принтер «понимает» только значение 0 или 1 (тонер/нет тонера). Для этого применяется так называемый дизеринг. Эта техника имитирует широкую палитру цветов, хотя в действительности используется крайне ограниченное число оттенков. Она также применяется при моделировании множества оттенков серого в двоичном коде.

На рисунке слева — исходное изображение в 256 оттенках серого (именно эта конкретная фотография обычно приводится в качестве примера в научных статьях, посвященных обработке изображений). На втором рисунке слева — увеличенное изображение с примененным эффектом дизеринга, который позволяет имитировать 256 оттенков серого, когда реальное число градаций серого меньше 256. Далее приведено еще два увеличенных изображения. Для генерации последнего использовалась кривая Гильберта.

Как правило, этот процесс обычно выглядит так: для преобразования изображения в 256 градаций серого используется проход по линиям или блокам пикселей. Каждому пикселю присваивается оттенок серого из сокращенной палитры цветов в зависимости от оттенков соседних пикселей таким образом, чтобы снизить общую ошибку. Как видно на втором рисунке, после применения дизеринга на изображении возникают характерные мелкие дефекты. Чтобы избавиться от них, вместо прохода вдоль горизонтальных линий используется обход вдоль кривой Гильберта, проходящей через все пиксели изображения. Преимущество этого метода заключается в том, что в этом случае отсутствуют ярко выраженные дефекты, которые нетрудно заметить при других способах обхода изображения.

После публикаций Пеано и Гильберта многие другие математики стали предлагать похожие примеры. Среди них были Хельге фон Кох, Поль Леви и Эрнесто Чезаро, Вацлав Серпинский и Исаак Шёнберг. Швейцарский математик Хельге фон Кох в 1904 г. опубликовал статью «Об одной непрерывной кривой, не имеющей касательных, построенной с помощью методов элементарной геометрии». Под этим пугающим названием скрывалось нечто очень простое и столь же удивительное. Рассмотрим отрезок горизонтальной прямой, имеющий единичную длину. Заменим исходный отрезок четырьмя отрезками длиной 1/3 и получим первую кривую для итеративного построения, которое показано на рисунке ниже:

Если построить три копии кривой Коха на сторонах равностороннего треугольника, получится так называемая снежинка Коха. Эта кривая обладает удивительным свойством: ее длина бесконечна, а площадь закрашенной области — нет.

Мы уже определили понятие размерности для любых объектов и увидели, что существуют кривые, подобные кривым Гильберта и Пеано, которые имеют размерность 1, но покрывают область размерностью 2. Возникает необходимость дать понятию размерности другое определение, которое согласовывалось бы с результатами наших наблюдений. Кривая Коха будет идеальным примером, который проиллюстрирует наши рассуждения. Новая размерность, о которой мы поговорим далее, называется фрактальной размерностью. Затем мы продемонстрируем фрактальную размерность для фигур, не обладающих свойством самоподобия.

Понятие самоподобия более подробно обсуждается в следующей главе. Здесь же мы укажем лишь его некоторые основные свойства. Объект обладает самоподобием, если имеет ту же форму, что и его части. Части самоподобного объекта могут быть получены путем преобразований этого объекта, которые называются преобразованиями подобия. Например, если мы возьмем кривую Коха, уменьшим ее в три раза и сделаем три копии новой, уменьшенной кривой, то сможем соединить их так, что получится новая кривая Коха. Мы последовательно расположим копии кривой так, что первая будет располагаться горизонтально, вторая — с поворотом на 60°, третья — с поворотом на —60°, четвертая — вновь горизонтально.

Этим свойством обладают и другие, даже самые простые объекты: например, можно уменьшить отрезок в два раза, соединить между собой две его уменьшенные копии и снова получить исходный отрезок. Нечто подобное можно сделать с квадратом: его можно уменьшить в четыре раза, затем соединить четыре уменьшенные копии и снова получить исходный квадрат. Во всех структурах, обладающих свойством самоподобия, существует взаимосвязь между коэффициентом уменьшения