Зважений Вороний Штиплер

Антон Лопирєв - січень 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), тому терміни не дуже вражають.

Це зображення футуристичного автомобіля, яке ви вже бачили вище, було відтворено в 7000 лінійках приблизно за 20 хвилин з важливою вибіркою на.
Оригінальне зображення було захоплено з: http://blog.silive.com/sinotebook/2008/12/have_the_big_3_automakers_come.html
Завантажте SVG

6.0 Розширення

6.1 Важливість вибірки

Підхід до вибірки моєї важливості, представлений у розділі 4.2, можна описати за допомогою кількох простих кроків:

Крок 1
Створіть гістограму інтенсивності вихідного зображення. Розглянемо інтенсивність як ціле число від 0 до 255, що представляє колір пікселя на зображенні (0 - чорний, а 255 - білий). Отже, наша гістограма матиме 256 бункерів. Однак, враховуючи те, що ми хочемо ігнорувати регіони з високою інтенсивністю, ми зменшимо кількість бункерів до 250 та ігноруємо всі пікселі з інтенсивністю більше 250. Ось зразок гістограми зображення "прототипу автомобіля":

Крок 2
Тепер, коли пікселі зображення розподілені між контейнерами, щоб сформувати випадкову точку, ми могли спершу сформувати випадкове число кошика, а потім вибрати випадкову точку в цьому кошику. Однак насправді ми хочемо частіше вибирати темні контейнери, тому кожному контейнеру ми призначаємо вагу. Якщо заборгованість смітника становить Я, тоді вага становить 255 - Я.

Крок 3
Ми відображаємо зважену гістограму до лінійної функції випадкової величини X. Для цього для кожного смітника ми обчислюємо нижню та верхню межу X значення:
Для кошика 0:
нижня межа = 0
верхня межа = кількість пікселів у цьому кошику * 255
Для bin i:
нижня межа = верхня межа попереднього (i - 1) контейнера + 1
верхня межа = кількість пікселів у цьому кошику * вага смітника

Крок 4
Тепер для генерації випадкової точки на зображенні:

генерувати випадкове число X в діапазоні [0, верхня межа смітника 250],
використовуйте двійковий пошук, щоб знайти, до якого кошика також належить це число,
вибрати випадковий піксель [х, у] в тому смітнику,
виберіть випадкову плаваючу крапку всередині комірки цього пікселя [x, y] - (x + 1, y + 1).

Результати вибірки
Наведені нижче зображення демонструють різницю між загальною випадковою вибіркою (2-е зображення) та наближенням вибірки важливості (3-е зображення). Зверніть увагу, що обидва зображення мають однакову кількість 7000 фішок і були створені за той самий проміжок часу - 20 хвилин. Очевидно, що останнє зображення набагато краще переносить тон вихідного зображення.

6.2 Розміри штрихов

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

Моє продовження намагається покращити стосунки, застосувавши простий факт, викладений Deussen et al. у своєму документі з плаваючими точками. Спостереження Деуссена показують, що на справжніх малюнках з тонкими малюнками найбільші крапки максимум удвічі більші за найменші.

Я використовую цей факт і функцію щільності зображення, щоб лінійно масштабувати штрихи. В областях вхідного зображення, де функція щільності дорівнює 1, радіус смужок дорівнює Р.. Коли функція щільності дорівнює нулю, радіус щілин дорівнює R/2.

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

6.3 Кольорове мелірування

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

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

Зробіть смужки частково прозорими та врахуйте перекриття, щоб краще зобразити кольори в тих регіонах зображення, де є багато смужок.
Виберіть обмежену кількість базових кольорів (3 або більше) і створіть кілька шарів частково прозорих смужок на основі різних функцій щільності, отриманих при розгляді кольорових компонентів вихідного зображення окремо.
Зробіть колір і розмір паличок спільними, щоб краще відображати зміни тембру. Наприклад, маленька темна смужка повинна мати подібний ефект, як велика світла смужка.

Нижче наведені деякі мої остаточні результати:

Це кольорова версія зображення старого, відтворена з використанням 15000 незмінних розмірів з незмінною вибіркою.
Завантажити чорно-біле SVG Завантажити кольорове SVG