Відновлення Ллойда: Комбінування Хаосу у Везику

Почніть із діаграми Вороної

Розсіюйте набір точок у площині та запитайте для кожної локації, який пункт найближчий – відповідь розділяє площину на області, звані клітинами Вороної, одна на пункт, і весь розподіл є діаграмою Вороної. Випадкові точки дають діаграму Вороної з нерівномірними клітинами: деякі маленькі та щільні, інші великі та порожні, оскільки ніщо у випадковому розміщенні не віддає переваги скупченню. Стюарт Ллойд, працюючи в Bell Labs у 1957 році над проблемою квантизації сигналу, знайшов напрочуд простий метод, який перетворює цей нерівномірний безлад на щось близьке до рівномірного.

Крок розслаблення: перехід до центрумаси

Алгоритм Ллойда чергує дві операції. По-перше, будується діаграма Вороної для поточних точок. По-друге, кожна точка замінюється центром мас свого власного комірки, а не її початковим положенням. Повторюйте. Кожен прохід змушує кожну точку наближатися до центру регіону, який вона контролює – точка в комірці, яка випирає вбік, тягнеться до цього вигину, що зменшує дисбаланс для наступного разу.

repeat for N iterations:
  V = VoronoiDiagram(points)              // one cell per point
  for each point p, with cell C in V:
    p ← centroid(C)                        // area-weighted centre of mass

energy being minimised:
  E = Σ over cells ∫∫_C |x − centroid(C)|² dA

Чому енергія падає на кожному кроці

Цей процес можна розуміти як градієнтне спустошення (gradient descent) по певній кількості: сума, для кожної комірки, квадратів відстаней від кожного пункту всередині комірки до власного центру маси цієї комірки. Переміщення генеричного пункту комірки в її центр маси є доведеним вибором, який мінімізує внесок цієї комірки у загальну енергію, зберігаючи межі комірок незмінними — отже, кожен крок Ллойда може зменшувати або стабілізувати загальну енергію, але ніколи її не збільшувати. Ця монотонна зменшення гарантує, що процес затихає, а не коливається чи розходиться, хоча він не має уявлення про розмір кроку або швидкість навчання, як це зазвичай робить градієнтне спустошення.

Стаціонарна точка: центроїдна Вороної тесатура

Процес зупиняється, коли кожна точка вже знаходиться точно у своєму клітинному центроїді – повторне переміщення туди ж не має наслідків. Ця конфігурація називається центроїдною Вороною тесатурою (ЦВТ), і це є фіксована точка, до якої збігається алгоритм Ллойда. Ідеальна шестигранна сітка є відомим прикладом ЦВТ з однаковими клітинами, і не дивно, що розслаблені набори точок схиляються до вигляду шестигранного внутрішнього розподілу, подалі від будь-якого краю: регулярний шестигранник є доведеним найефективнішим способом поділити площину на рівновеликі області з однаковою площею, мінімізуючи саме такий тип енергії, що зменшує алгоритм Ллойда.

Де то використовується фактично розслаблена точка

Розслаблення Ллойда з’являється будь-де, де потрібно рівномірно розподілити набір вибіркових точок без очевидної сітчастої структури. Метод генерації сіток для моделювання кінцечних елементів використовує його, щоб уникнути довгих, вузьких, чисельно нестабільних трикутників, які виникають при нерозслабленому випадковому зразкуванні. Алгоритми точки-крапки та джитлінгу використовують його для розміщення точок так, щоб локальна щільність відповідала сірого значення зображення, уникаючи візуально відволікаючої кластерної та порожньої випадковості - ця техніка лежить в основі популярного методу «зваженого Voronoi точки-крапки» для створення ілюстрацій з фотографій. Генерація шумового сигналу синього кольору для рендерингу та розміщення процедурних текстур спирається на ту ж ідею: розслаблені точки все ще виглядають органічно та нерегулярно, але без кластерних артефактів, які загрожують чистому випадковому розміщенню.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Lloyd's Relaxation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.