Антон Лопирєв - Зважений Вороний Стиплер

Антон Лопирєв - січень 2010 року

Застереження

Більшість зображень, що використовуються для тестування цього завдання, які відображаються на цій сторінці, були витягнуті з суспільного надбання. Однак, якщо ви залишаєте за собою будь-які права на будь-яке із зображень і хотіли б, щоб я їх зняв, повідомте про це електронною поштою: anton на адресу lopyrev dot com. Я спробую якнайшвидше задовольнити ваш запит. Заздалегідь перепрошую за несанкціоноване використання будь-якого захищеного авторським правом матеріалу.

Якщо ви зацікавлені в отриманні вихідного коду, ви можете взяти його тут.

1.0 Зміст

2.0 Вступ

Це підготовка до завдання 1 курсу нефореалістичного візуалізації CS 791, який я проходив взимку 2010 року. Повні технічні характеристики завдання див. Тут.

Підводячи підсумок, завдання передбачало реалізацію базового алгоритму стиплінгу з статті Адріана Секорда «Зважений Вороной Стиплінг». Стиплінг - це техніка моделювання різного ступеня затінення та тону за допомогою ряду маленьких крапок. Точки потенційно можуть відрізнятися за розміром, кольором та формою. У зваженому штрихованні Вороного використовуються цетроїдні діаграми Вороного та зважена варіація ітеративного методу Ллойда для розподілу точок відповідно до тону зображення.

Моя реалізація алгоритму використовує цікаву техніку вибірки, щоб розмістити початковий набір куточків. Це також передбачає обробку вихідного зображення високою роздільною здатністю та ефективне обчислення центроїдів, щоб досягти кращих результатів за коротший час. Обидва ці прийоми описані в оригінальній роботі.

3.0 Використані інструменти

4.0 Деталі реалізації

4.1 Інтерфейс користувача

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

лопирєв

Як бачите, інтерфейс дозволяє користувачеві відкрити новий файл (Файл -> Відкрити), вибрати відповідну кількість стипплів і запустити стиплер. Після того, як алгоритми збиваються, користувач може зберегти результат у файл SVG (Файл -> Зберегти).
Також є 3 додаткові опції, які користувач може вказати:

  • Показати вороной регіони: цей параметр дозволяє користувачеві бачити регіони Вороного навколо куточків під час роботи алгоритму.
  • Використовуйте незмінні розміри ліній: цей параметр дозволяє користувачеві змінювати розмір паличок з постійного на один залежно від інтенсивності кольору. Детальніше про розділ 6.2.
  • Використовуйте вибірку важливості: цю опцію можна ввімкнути до того, як стиплер застосовуватиметься до вихідного зображення. Це забезпечує вибірку важливості, яка детально обговорюється в розділі 6.1.
  • Використовуйте кольорові смужки: цей параметр дозволяє користувачеві змінити колір смужок з чорного на той, що залежить від інтенсивності кольору. Детальніше про розділ 6.3.

4.2 Початкова техніка відбору проб

4.3 Дозвіл обчислення Вороного

Щоб зменшити наслідки відносної похибки розрахункових місць розташування центроїдів, я використав техніку обробки плитки, згадану в роботі. Я розділив вихідне зображення на 16 плиток, а потім відтворив кожну плитку з повною роздільною здатністю зображення, таким чином, ефективно збільшивши віртуальну роздільну здатність діаграми Вороного в 16 разів.

Це допомогло набагато краще зобразити темні тони та градієнти, особливо для зображень із 5000+ фігурами.

4.4 Ефективне обчислення Centroid

5.0 Результати

Всі результати були показані на моєму ноутбуці (2,53 ГГц Intel Core 2 Duo), тому терміни не дуже вражають.