Алгоритм Ллойда - Lloyd's algorithm

Пример алгоритма Ллойда. Показана диаграмма Вороного текущих точек на каждой итерации. Знаки плюс обозначают центроиды ячеек Вороного.

Итерация 1

Итерация 2

Итерация 3

Итерация 15

На последнем изображении точки находятся очень близко к центроидам ячеек Вороного. Обнаружена центроидная мозаика Вороного.

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

Хотя алгоритм может быть применен непосредственно к евклидовой плоскости , аналогичные алгоритмы также могут применяться к пространствам более высокой размерности или к пространствам с другими неевклидовыми метриками. Алгоритм Ллойда можно использовать для построения близких приближений к центроидным мозаикам Вороного входных данных, которые можно использовать для квантования , дизеринга и штриховки . Другие применения алгоритма Ллойда включают сглаживание треугольных сеток в методе конечных элементов .

История

Алгоритм был впервые предложен Стюартом П. Ллойдом из Bell Labs в 1957 году как метод импульсно-кодовой модуляции . Работа Ллойда получила широкое распространение, но оставалась неопубликованной до 1982 года. Подобный алгоритм был независимо разработан Джоэлом Максом и опубликован в 1960 году, поэтому алгоритм иногда называют алгоритмом Ллойда-Макса.

Описание алгоритма

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

Затем он повторно выполняет следующий этап релаксации:

• Диаграмма Вороного из K сайтов вычисляется.
• Каждая ячейка диаграммы Вороного интегрируется, и вычисляется центроид.
• Затем каждый сайт перемещается в центр тяжести своей ячейки Вороного.

Интеграция и вычисление центроида

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

Приближение

Распространенным упрощением является использование подходящей дискретизации пространства, такой как мелкая пиксельная сетка, например, буфер текстуры в графическом оборудовании. Ячейки материализованы как пиксели, помеченные соответствующим идентификатором сайта. Новый центр ячейки аппроксимируется путем усреднения положений всех пикселей, которым присвоены одинаковые метки. В качестве альтернативы можно использовать методы Монте-Карло , в которых случайные точки выборки генерируются согласно некоторому фиксированному базовому распределению вероятностей, назначаются ближайшему участку и усредняются для аппроксимации центроида для каждого участка.

Точное вычисление

Хотя вложения в других пространствах также возможно, эта разработка предполагает евклидово пространство с помощью L ² нормы и рассматриваются два наиболее соответствующие сценарии, которые два, и , соответственно , три измерения.

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

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

Интегрирование ячейки и вычисление ее центроида (центра масс) теперь дается как взвешенная комбинация центроидов ее симплексов (далее называемых ). ${\ textstyle \ mathbf {c} _ {я}}$

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

Для двумерной ячейки с n треугольными симплексами и накопленной площадью (где - площадь симплекса треугольника ) новый центроид ячейки вычисляется как: ${\ textstyle A_ {C} = \ sum _ {i = 0} ^ {n} a_ {i}}$${\ textstyle a_ {i}}$

${\ displaystyle C = {\ frac {1} {A_ {C}}} \ sum _ {i = 0} ^ {n} \ mathbf {c} _ {i} a_ {i}}$

Аналогично, для трехмерной ячейки с объемом (где - объем симплекса тетраэдра ) центроид вычисляется как: ${\ textstyle V_ {C} = \ сумма _ {я = 0} ^ {n} v_ {я}}$${\ textstyle v_ {i}}$

${\ displaystyle C = {\ frac {1} {V_ {C}}} \ sum _ {i = 0} ^ {n} \ mathbf {c} _ {i} v_ {i}}$

Конвергенция

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

Алгоритм сходится медленно или из-за ограничений числовой точности может не сходиться. Таким образом, реальное применение алгоритма Ллойда обычно останавливается, когда распределение «достаточно хорошее». Одним из общих критериев завершения является остановка, когда максимальное расстояние, на которое перемещается любой сайт за итерацию, становится ниже предварительно установленного порога. Сходимость может быть ускорена за счет чрезмерного расслабления точек, что достигается перемещением каждой точки ω, умноженной на расстояние до центра масс, обычно с использованием значения чуть меньше 2 для ω .

Приложения

Метод Ллойда первоначально использовался для скалярного квантования, но очевидно, что этот метод распространяется также и на векторное квантование. Таким образом, он широко используется в методах сжатия данных в теории информации . Метод Ллойда используется в компьютерной графике, потому что результирующее распределение имеет характеристики синего шума (см. Также Цвета шума ), что означает, что существует несколько низкочастотных компонентов, которые можно интерпретировать как артефакты. Он особенно хорошо подходит для выбора позиций сэмпла для дизеринга . Алгоритм Ллойда также используется для создания точечных рисунков в стиле штриховки . В этом приложении центроиды могут быть взвешены на основе эталонного изображения для создания точечных иллюстраций, соответствующих входному изображению.

В методе конечных элементов входная область сложной геометрии разбивается на элементы более простой формы; например, двумерные области (либо подмножества евклидовой плоскости, либо поверхности в трех измерениях) часто разбиваются на треугольники. Для сходимости методов конечных элементов важно, чтобы эти элементы имели правильную форму; в случае треугольников предпочтение отдается элементам, которые почти равносторонние треугольники. Алгоритм Ллойда можно использовать для сглаживания сетки, созданной каким-либо другим алгоритмом, перемещая ее вершины и изменяя схему соединения между ее элементами, чтобы создавать треугольники, которые более точно равносторонние. Эти приложения обычно используют меньшее количество итераций алгоритма Ллойда, останавливая его до сходимости, чтобы сохранить другие особенности сетки, такие как различия в размерах элементов в разных частях сетки. В отличие от другого метода сглаживания, лапласовского сглаживания (при котором вершины сетки перемещаются в среднее положение их соседей), алгоритм Ллойда может изменять топологию сетки, приводя к более близким к равносторонним элементам, а также избегая проблем с запутывание, которое может возникнуть при лапласовском сглаживании. Однако лапласовское сглаживание может применяться в более общем смысле к сеткам с нетреугольными элементами.

Разные расстояния

Алгоритм Ллойда обычно используется в евклидовом пространстве . Евклидово расстояние играет в алгоритме две роли: оно используется для определения ячеек Вороного, но оно также соответствует выбору центроида в качестве репрезентативной точки каждой ячейки, поскольку центроид - это точка, которая минимизирует средний квадрат евклидова расстояния. к точкам в своей ячейке. Вместо этого могут использоваться альтернативные расстояния и альтернативные центральные точки, чем центроид. Например, Хауснер (2001) использовал вариант метрики Манхэттена (с локально изменяющейся ориентацией), чтобы найти мозаичное покрытие изображения приблизительно квадратными плитками, ориентация которых совпадает с особенностями изображения, которые он использовал для моделирования построения мозаики. . В этом приложении, несмотря на изменение метрики, Хауснер продолжал использовать центроиды в качестве репрезентативных точек своих ячеек Вороного. Однако для показателей, которые более существенно отличаются от евклидовых, может оказаться целесообразным выбрать в качестве репрезентативной точки минимизатор среднего квадрата расстояния вместо центроида.

Смотрите также

• Алгоритм Linde-Бузо-серый , обобщение этого алгоритма векторного квантования
• Обход от начала до конца , другой метод создания равномерно распределенных точек в геометрических пространствах
• Средний сдвиг , родственный метод нахождения максимумов функции плотности
• K-означает ++

Рекомендации

внешняя ссылка

• DemoGNG.js Графический симулятор Javascript для алгоритма LBG и других моделей, включает отображение областей Вороного