Распечатать запись Распечатать запись

Кривые Гильберта

Кривые Гильберта названы в честь немецкого математика Давида Гильберта. Впервые они были описаны в 1891 году.

Кривая Гильберта — это непрерывная кривая, заполняющая пространство. Эти кривые также являются фракталами, они самоподобны; если вы увеличите масштаб и внимательно посмотрите на часть кривой более высокого порядка, то вы увидите, что она выглядит так же, как сама кривая.

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




Не разрешается, чтобы веревка пересекала сама себя.

Есть много способов сделать это, однако кривые Гильберта имеют некоторые дополнительные интересные свойства. Чтобы понять эти свойства, мы должны внимательнее посмотреть на то, как они строятся рекурсивно.




Кривая Гильберта, которая построена для сетки 8 \times 8, показана слева.


Рекурсия


Основным элементом кривой Гильберта является П-образный элемент. Посмотрите на рисунок слева.



Здесь у нас квадратная сетка 2 \times 2. Начнем с левого верхнего угла и проведем веревку через другие три квадрата сетки, закончив в правом верхнем углу.

Теперь представьте, что мы удваиваем размер сетки, получая сетку 4 \times 4.

Мы можем представить эту сетку 4 \times 4 в виде набора 4=2\times2 сеток, каждая из которых имеет размер 2 \times 2 (как набор матрешек).

Мы хотим пересечь сетку более высокого уровня в таком порядке 0 \to 1 \to 2 \to 3 (это показано большими желтыми стрелками), а затем внутри этой сетки используем все тот же П-образный шаблон обхода для каждой из сеток меньшего уровня.




Результат этого показан слева.

Эта запутанная и извилистая кривая проходит через каждый квадрат сетки.




Если вы вернетесь назад, к кривой на сетке 8 \times 8, приведенной выше, то увидите, что она построена из кривых для четырех сеток 4 \times 4, размещенных по П-образному образцу…


Вот некоторые кривые Гильберта по возрастанию порядка:

От 1D к 2D


Здесь все становится немного интереснее. Вместо того чтобы использовать веревку, представим, что мы по сетке располагаем измерительную ленту.

Поскольку лента извивается и разворачивается в противоположном направлении вокруг сетки, получается интересное свойство. Если сопоставить расстоянию d, отмеренному лентой, пару координат (x,y) точек на исходной сетке, то получится, что другие отметки на ленте (близкие к d) соответствуют координатам, близким к (x,y).

Мы получили полезную функцию перехода от размерности 1 к двум измерениям, она сохраняет свойство локальности (примеч. Проекция, сохраняющая свойство локальности — линейное проективное отображение, которое оптимально сохраняет структуру окрестности точки из области определения).

Близкие значения d соответствуют близким значениям (x, y).

Замечание. Обратное не всегда верно (что неизбежно при отображении двух измерений на одно измерение). Обязательно будут случаи, когда точки с геометрически близкими координатами (x,y) будут соответствовать сильно отличающимся значениям на ленте d. Тем не менее, за исключением этих случаев, кривые Гильберта также неплохо работают и на обратных отображениях.

Справа вы можете увидеть квадрат, раскрашенный с использованием кривой Гильберта. Цвета, близкие друг к другу на спектре, имеют близкие координаты (x,y).

(Близкие координаты (x,y) не всегда соответствуют близким цветовым оттенкам цвета по причине, описанной выше, хотя часто это так. Отсутствие непрерывности наиболее заметно вдоль двух границ. Некоторые интересные обходы этого ограничения были придуманы, больше об этом — позже).


Более внимательный взгляд

Ниже приведен график, на котором показаны расстояния между всеми клетками кривой Гильберта 16\times16 и исходной точкой (отмеченной красной линией). По оси x изображено одномерное расстояние d, измеренное лентой. По оси y показано расстояние между точкой, отмеченной на оси x, и исходной точкой (отмеченной красной линией).

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

В приведенном выше примере выбранная нами исходная точка соответствует 51 единице на ленте по шкале 0–255, где нуль — начало ленты, а 255 — конец ленты.

Ниже еще один пример, на этот раз исходная точка соответствует 138 единицам на ленте. Как и прежде, чем дальше от исходной точки, тем больше становится расстояние между парами координат (x,y). И, как и раньше, значения d для точек, близких к исходной, соответствуют координатам, которые близки к координатам (x,y) исходной точки.

Вот тепловая карта для расстояний между всеми парами значений d. Чем ярче цвет, тем больше расстояние. Верхний левый угол сетки представляет собой расстояние между точками d = 0, d = 0. Каждый пиксель, сдвинутый на n вправо соответствует d=n, и каждый пиксель, сдвинутый на m вниз, соответствует d=m. Цвет каждого пикселя соответствует расстоянию между двумя точками d=m,d=n на плоскости.

(Приведенные выше графики эквивалентны горизонтальным разрезам этой сетки, так что оттенки цвета соответствуют высоте графика).

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

Более высокие размерности

Построение кривых Гильберта может быть сделано и для более чем двух измерений. Одномерная линия может быть закручена в стольких измерениях, сколько вы можете себе представить.

Вариант трехмерной кривой показан слева. В этом случае точки на кривой, численно близкие друг к другу, также близки в трехмерном пространстве.

Легко увидеть, как это может быть распространено на более высокие измерения.


Практическое применение

Кривые Гильберта не просто красивы, они являются очень полезными конструкциями.

Функции Гильберта могут помочь в индексировании пространственных баз данных; при поиске записи, близкой по географическому положению они дают возможность определить приоритет для поиска.

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

В более высоких размерностях они могут быть использованы для планирования задач в компьютерных программах с параллельной обработкой данных, преобразования многомерного распределения задач в одномерное и привязки близких задач к точкам размещения с более высоким уровнем близости.

Исследования

Ранее уже говорилось, что не все в кривых Гильберта идеально. (Точки с близкими значениями d имеют схожие значения (x,y), но обратное не всегда верно).

Это свойство было бы невероятно полезно, например, при осуществлении эффективного доступа к данным. Давайте представим, что у вас есть некоторые данные, хранящиеся в цифровом виде (точки их размещения с очень большим временем доступа), и требуется их индексация и доступ к ним эффективным образом, что нужно сделать географически. Как известно, преобразование координат (x,y) в значения d не может гарантировать, что близкие значения d расположены в непосредственной близости. Большую часть времени да, но время от времени нет.

Чтобы избежать этого, вместо простого индексирования данных на одной кривой Гильберта, данные переводятся на множество гильбертовых кривых (как правило, полученных вращением и горизонтальными/вертикальными сдвигами одной кривой). Таким образом, с помощью объединения результатов сглаживаются любые неудачные значения в окрестности 2^n границ.

Источник: http://www.datagenetics.com/blog/march22013/index.html

Оставьте свой отзыв

Добавить изображение