Новый взгляд на мир. Фрактальная геометрия - [22]
Блестящий немецкий математик Давид Гильберт.
На рисунке показано, как на каждом шаге части кривой соединяются тремя отрезками, которые непрерывно уменьшаются в размерах. Именно так описал построение этой кривой сам Гильберт в 1891 г. в короткой статье всего на двух страницах. Существует стандартное построение этой же кривой, в основе которого лежит несколько иная фигура. Оставим поиски этого построения заинтересованному читателю. Отличие кривой Гильберта от кривой Пеано в том, что в первой на каждом шаге построения длины отрезков и квадратов уменьшаются в два раза, а в кривой Пеано — в три раза.
Существуют интересные вариации кривой Гильберта: в одной из них в качестве исходной фигуры используется перевернутая буква V, в другой, за авторством Карла Хансена, исходной фигурой является буква Н (очевидно, по первой букве фамилии Гильберта — Hilbert). Кривая Гильберта обладает еще одной любопытной особенностью: ее можно видоизменить так, что она будет покрывать объемную фигуру, как показано на рисунке:
Эта трехмерная версия кривой Гильберта имеет большое значение в устройствах передачи данных, в особенности там, где для выявления ошибок используется так называемый код Грея — вариация двоичного кода. В традиционном двоичном коде числа от 0 до 7 записываются так: 000, 001, 010, 011, 100, 101, 110, 111. Затем каждое число этой последовательности располагается в одной из вершин куба так, чтобы двоичные разряды соответствовали координатам этой вершины. Например, число 001 нужно расположить в точке с координатами (0, 0, 1). После этого числа нужно упорядочить, следуя вдоль кривой Гильберта, как показано на рисунке ниже.
Эта последовательность двоичных чисел является кодом Грея, который обладает особым свойством. При внимательном рассмотрении заметно, что соседние значения различаются только в одном разряде (одним битом информации), что не выполняется для традиционной последовательности чисел, где, например, за 001 следует 010 (эти числа отличаются двумя разрядами). Говоря техническим языком, расстояние Хэмминга между двумя соседними 3-битными числами равно 1. Если нам нужно закодировать не первые восемь натуральных чисел, а больше, то понадобится следующая итерация кривой Гильберта, с помощью которой мы закодируем числа от 0 до 31. Код Грея позволяет существенно снизить количество ошибок при передаче информации. В частности, он широко применяется в наземных сетях цифрового телевидения.
Кривая Гильберта также используется при цифровой обработке изображений. Если мы хотим распечатать изображение в градациях серого на лазерном принтере первого поколения, то нам понадобится приближенная бинарная модель изображения, так как принтер «понимает» только значение 0 или 1 (тонер/нет тонера). Для этого применяется так называемый дизеринг. Эта техника имитирует широкую палитру цветов, хотя в действительности используется крайне ограниченное число оттенков. Она также применяется при моделировании множества оттенков серого в двоичном коде.
На рисунке слева — исходное изображение в 256 оттенках серого (именно эта конкретная фотография обычно приводится в качестве примера в научных статьях, посвященных обработке изображений). На втором рисунке слева — увеличенное изображение с примененным эффектом дизеринга, который позволяет имитировать 256 оттенков серого, когда реальное число градаций серого меньше 256. Далее приведено еще два увеличенных изображения. Для генерации последнего использовалась кривая Гильберта.
Как правило, этот процесс обычно выглядит так: для преобразования изображения в 256 градаций серого используется проход по линиям или блокам пикселей. Каждому пикселю присваивается оттенок серого из сокращенной палитры цветов в зависимости от оттенков соседних пикселей таким образом, чтобы снизить общую ошибку. Как видно на втором рисунке, после применения дизеринга на изображении возникают характерные мелкие дефекты. Чтобы избавиться от них, вместо прохода вдоль горизонтальных линий используется обход вдоль кривой Гильберта, проходящей через все пиксели изображения. Преимущество этого метода заключается в том, что в этом случае отсутствуют ярко выраженные дефекты, которые нетрудно заметить при других способах обхода изображения.
После публикаций Пеано и Гильберта многие другие математики стали предлагать похожие примеры. Среди них были Хельге фон Кох, Поль Леви и Эрнесто Чезаро, Вацлав Серпинский и Исаак Шёнберг. Швейцарский математик Хельге фон Кох в 1904 г. опубликовал статью «Об одной непрерывной кривой, не имеющей касательных, построенной с помощью методов элементарной геометрии». Под этим пугающим названием скрывалось нечто очень простое и столь же удивительное. Рассмотрим отрезок горизонтальной прямой, имеющий единичную длину. Заменим исходный отрезок четырьмя отрезками длиной 1/3 и получим первую кривую для итеративного построения, которое показано на рисунке ниже:
Если построить три копии кривой Коха на сторонах равностороннего треугольника, получится так называемая снежинка Коха. Эта кривая обладает удивительным свойством: ее длина бесконечна, а площадь закрашенной области — нет.
