Алгоритм Ллойда - Lloyds algorithm

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

Итерация 1

Итерация 2

Итерация 3

Итерация 15

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

В Информатика и электротехника, Алгоритм Ллойда, также известный как Итерация Вороного или релаксация, это алгоритм, названный в честь Стюарта П. Ллойда для поиска равномерно распределенных наборов точек в подмножествах Евклидовы пространства и разделение этих подмножеств на выпуклые ячейки правильной формы и одинакового размера.^[1] Как и тесно связанный k-средства кластеризации алгоритм, он неоднократно находит центроид каждого набора в разделе, а затем повторно разбивает входные данные в соответствии с тем, какой из этих центроидов является ближайшим. В этой настройке средняя операция является интегралом по области пространства, а операция ближайшего центроида приводит к Диаграммы Вороного.

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

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

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

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

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

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

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

Приближение

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

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

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

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

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

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

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

Для 2D-ячейки с п треугольные симплексы и накопленная площадь ${\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}=\sum _{i=0}^{n}v_{i}}$ (куда ${\textstyle v_{i}}$ это объем тетраэдра симплекс), центроид вычисляется как:

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

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

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

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

Приложения

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

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

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

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

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

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

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

1. Ллойд, Стюарт П. (1982), «Квантование методом наименьших квадратов в PCM» (PDF), IEEE Transactions по теории информации, 28 (2): 129–137, Дои:10.1109 / TIT.1982.1056489.
2. Ду, Цян; Фабер, Вэнс; Гинцбургер, Макс (1999), "Центроидальные мозаики Вороного: приложения и алгоритмы", SIAM Обзор, 41 (4): 637–676, Bibcode:1999SIAMR..41..637D, Дои:10.1137 / S0036144599352836.
3. Ду, Цян; Емельяненко Мария; Джу, Лили (2006), "Сходимость алгоритма Ллойда для вычисления центроидных мозаик Вороного", Журнал SIAM по численному анализу, 44: 102–119, CiteSeerX  10.1.1.591.9903, Дои:10.1137/040617364.
4. Сабин, М. Дж .; Грей, Р. М. (1986), "Глобальная сходимость и эмпирическая согласованность обобщенного алгоритма Ллойда", IEEE Transactions по теории информации, 32 (2): 148–155, Дои:10.1109 / TIT.1986.1057168.
5. Емельяненко Мария; Джу, Лили; Рэнд, Александр (2009), "Невырожденность и слабая глобальная сходимость алгоритма Ллойда в р^d", Журнал SIAM по численному анализу, 46: 1423–1441, Дои:10.1137/070691334.
6. Сяо, Сяо. «Метод Ллойда с избыточной релаксацией для вычисления центроидных мозаик Вороного». (2010).
7. Деуссен, Оливер; Хиллер, Стефан; ван Овервельд, Корнелиус; Стрототт, Томас (2000), «Плавающие точки: метод расчета штриховых рисунков», Форум компьютерной графики, 19 (3): 41–50, Дои:10.1111/1467-8659.00396, Труды Еврография.
8. Секорд, Адриан (2002), "Взвешенная штриховка Вороного", Материалы симпозиума по нефотореалистичной анимации и рендерингу (NPAR), ACM SIGGRAPH, стр. 37–43, Дои:10.1145/508530.508537.
9. Ду, Цян; Гинцбургер, Макс (2002), "Создание и оптимизация сетки на основе центроидных мозаик Вороного", Прикладная математика и вычисления, 133 (2–3): 591–607, CiteSeerX  10.1.1.324.5020, Дои:10.1016 / S0096-3003 (01) 00260-0.
10. Хауснер, Алехо (2001), "Моделирование декоративной мозаики", Материалы 28-й ежегодной конференции по компьютерной графике и интерактивным техникам., ACM SIGGRAPH, стр. 573–580, Дои:10.1145/383259.383327.
11. Дикерсон, Мэтью Т.; Эппштейн, Дэвид; Вортман, Кевин А. (2010), "Планарные диаграммы Вороного для сумм выпуклых функций, сглаженного расстояния и растяжения", Proc. 7-й Международный симпозиум по диаграммам Вороного в науке и технике (ISVD 2010), стр. 13–22, arXiv:0812.0607, Дои:10.1109 / ISVD.2010.12.

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

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