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

Алгоритм, используемый для точек в евклидовом пространстве

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

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

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

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

История

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

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

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

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

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

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

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

Приближение

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

Точный расчет

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

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

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

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

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

Для двумерной ячейки с 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}=\sum _{i=0}^{n}v_{i}}$ ${\textstyle v_{i}}$

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

Внешние ссылки

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