Anton Lopyrev - ianuarie 2010

Declinare de responsabilitate

Majoritatea imaginilor utilizate pentru testarea acestei misiuni care sunt afișate pe această pagină au fost extrase din domeniul public. Cu toate acestea, dacă vă rezervați drepturi pentru oricare dintre imagini și doriți să le dau jos, vă rugăm să ne anunțați prin e-mail: anton at lopyrev dot com. Voi încerca să vă răspund cererii cât mai repede posibil. Îmi cer scuze în avans pentru utilizarea neautorizată a oricărui material protejat prin drepturi de autor.

Dacă sunteți interesat să obțineți codul sursă, îl puteți lua aici.

1.0 Conținut

2.0 Introducere

Aceasta este o înregistrare pentru misiunea 1 a cursului de redare non-fotorealistă CS 791 pe care am urmat-o în iarna anului 2010. Vedeți specificațiile complete ale sarcinii aici.

În rezumat, misiunea a implicat implementarea unui algoritm de bază de stippling din lucrarea lui Adrian Secord Weighted Voronoi Stippling. Stippling este o tehnică de simulare a diferitelor grade de umbrire și ton folosind un număr de puncte mici. Punctele pot varia în mărime, culoare și formă. Punctarea ponderată a Voronoi utilizează diagrame cetoreale Voronoi și o variație ponderată a metodei iterative Lloyd pentru a distribui punctele în funcție de tonul imaginii.

Implementarea algoritmului meu utilizează o tehnică de eșantionare de importanță interesantă pentru a plasa setul inițial de capse. De asemenea, implică plasarea imaginii sursă la o rezoluție mai mare și un calcul eficient al centroizilor pentru a obține rezultate mai bune într-un timp mai scurt. Ambele tehnici sunt descrise în lucrarea originală.

3.0 Instrumente utilizate

4.0 Detalii de implementare

4.1 Interfața utilizatorului

Pentru ca implementarea mea să fie mai utilizabilă, am ales să proiectez o interfață de utilizator simplă pentru programul meu în loc să îl fac un instrument bazat pe linia de comandă pură. Acest lucru m-a ajutat, de asemenea, să vizualizez iterațiile algoritmului Lloyd pe măsură ce mergeau și, astfel, depanarea oricăror probleme a fost destul de nedureroasă. Interfața de bază a utilizatorului este prezentată în imaginea de mai jos:

lopyrev

După cum puteți vedea, interfața permite utilizatorului să deschidă un fișier nou (Fișier -> Deschidere), să aleagă un număr adecvat de stipples și să ruleze stippler-ul. Odată ce algoritmii concluzionează, utilizatorul poate salva rezultatul într-un fișier SVG (Fișier -> Salvare).
Există, de asemenea, 3 opțiuni suplimentare pe care utilizatorul le poate specifica:

  • Afișați regiunile voronoi: această opțiune permite utilizatorului să vadă regiunile Voronoi din jurul punctelor în timp ce algoritmul rulează.
  • Utilizați dimensiuni constante de puncte: această opțiune permite utilizatorului să schimbe dimensiunea punctelor de la constantă la una în funcție de intensitatea culorii. Citiți mai multe despre secțiunea 6.2.
  • Folosiți eșantionarea importanței: această opțiune poate fi activată înainte ca stippler-ul să fie aplicat imaginii sursă. Permite importanța eșantionării, care este discutată în detaliu în secțiunea 6.1.
  • Utilizați puncte de culoare: această opțiune permite utilizatorului să schimbe culoarea punctelor de la negru la una în funcție de intensitatea culorii. Citiți mai multe despre secțiunea 6.3.

4.2 Tehnica inițială de eșantionare

4.3 Rezoluția calculului Voronoi

Pentru a reduce efectele erorii relative a localizărilor centrului calculat, am folosit tehnica de placare menționată în lucrare. Am împărțit imaginea sursă în 16 plăci și apoi am redat fiecare placă la rezoluția maximă a imaginii, crescând astfel rezoluția virtuală a diagramei Voronoi de 16 ori.

Acest lucru a ajutat la reprezentarea tonurilor și a gradientelor mai întunecate mult mai bine, în special pentru imaginile cu peste 5000 de puncte.

4.4 Calcul eficient al Centroidului

5.0 Rezultate

Toate rezultatele au fost redate pe laptopul meu (2,53 Ghz Intel Core 2 Duo), deci timpul nu este foarte impresionant.

Această imagine a unei mașini futuriste pe care ați văzut-o deja mai sus a fost redată cu 7000 de puncte în aproximativ 20 de minute, cu eșantionare importantă pe.
Imaginea originală a fost preluată de pe: http://blog.silive.com/sinotebook/2008/12/have_the_big_3_automakers_come.html
Descărcați SVG

6.0 Extensii

6.1 Eșantionarea importanței

Abordarea de eșantionare a importanței mele introdusă în secțiunea 4.2 poate fi descrisă utilizând o serie de pași simpli:

Pasul 1
Generați o histogramă a intensităților imaginii sursă. Luați în considerare intensitatea ca un număr întreg de la 0 la 255 reprezentând culoarea pixelilor din imagine (0 fiind negru și 255 fiind alb). Prin urmare, histograma noastră va avea 256 de coșuri. Cu toate acestea, având în vedere că dorim să ignorăm regiunile cu intensitate mare, vom reduce numărul de coșuri la 250 și vom ignora toți pixelii cu intensitate mai mare de 250. Iată o mostră de histogramă a imaginii „mașină prototip”:

Pasul 2
Acum că pixelii imaginii sunt distribuiți între coșuri, pentru a genera un punct aleatoriu, am putea genera mai întâi un număr aleatoriu de coș și apoi să alegem un punct aleatoriu în coșul respectiv. Cu toate acestea, ceea ce vrem cu adevărat este să alegem coșurile întunecate mai des, așa că atribuim o greutate fiecărui coș. Dacă intesitatea unui coș de gunoi este Eu, atunci greutatea este 255 - Eu.

Pasul 3
Hartăm histograma cântărită la o funcție liniară a unei variabile aleatorii X. Pentru a face acest lucru, pentru fiecare coș calculăm limita inferioară și superioară a X valori:
Pentru coșul 0:
limita inferioară = 0
limită superioară = numărul de pixeli din coșul respectiv * 255
Pentru coșul i:
limita inferioară = limita superioară a coșului anterior (i - 1) + 1
limită superioară = numărul de pixeli din coșul respectiv * greutatea coșului

Pasul 4
Acum, pentru a genera un punct aleatoriu pe imagine:

  1. generează un număr aleatoriu X în intervalul [0, limita superioară a coșului 250],
  2. folosiți căutarea binară pentru a găsi, cărui coș aparține și acel număr,
  3. alege pixel aleatoriu [X y] în coșul respectiv,
  4. alegeți un punct plutitor aleatoriu în celula pixelului respectiv [x, y] - (x + 1, y + 1).
Rezultate de eșantionare
Imaginile de mai jos demonstrează diferența dintre eșantionarea generală aleatorie (a doua imagine) și aproximarea eșantionării de importanță (a 3-a imagine). Rețineți că ambele imagini au un număr egal de 7000 de puncte și au fost generate în aceeași perioadă de timp - 20 de minute. În mod clar, ultima imagine transmite tonul imaginii sursă mult mai bine.

6.2 Dimensiuni Stipple

Potrivit tezei de master a lui Adrian, principalul motiv pentru "neliniaritatea dintre densitatea imaginii de intrare și acoperirea cernelii de ieșire este că orice dimensiune primitivă fixă ​​nu poate reproduce fidel tonurile imaginii de intrare".

Extinderea mea încearcă să îmbunătățească relația prin aplicarea unui fapt simplu afirmat de Deussen și colab. în lucrarea sa cu Puncte Flotante. Observațiile lui Deussen arată că, în desenele cu puncte reale, cele mai mari puncte sunt cel mult de două ori mai mari decât cele mai mici.

Folosesc acest fapt și funcția de densitate a imaginii pentru a scala liniar punctele. În regiunile imaginii de intrare, unde funcția densității este egală cu 1, raza punctelor este R. Când funcția de densitate este zero, raza punctelor este R/2.

Această tehnică simplă nu compensează suprapunerea sau orice alte probleme menționate în teza lui Adrian. Cu toate acestea, produce rezultate interesante și îmbunătățește cu siguranță capacitatea algoritmului de a evidenția detalii complicate. Observați cum puteți distinge acum mai multe detalii pe roți, faruri și interiorul mașinii:

6.3 Punct de culoare

Ca extensie principală, am implementat punctarea culorii. Din cauza lipsei de timp, nu am complicat algoritmul de selecție a culorilor. Abordarea mea asupra punctării culorii poate fi considerată o simplă dovadă a conceptului, care poate fi potențial încântată pentru a obține rezultate mai bune. Cu toate acestea, nu uitați niciodată simplitatea algoritmului meu, cred că rezultatele pe care le vedeți mai jos sunt încă destul de plăcute.

Ideea din spatele algoritmului meu de punctare a culorii este de a selecta pur și simplu culoarea pentru stipples pe baza intensității culorii imaginii sursă. Acest lucru funcționează destul de bine, mai ales cu un număr mare de capse. Există, de asemenea, o serie de idei interesante pe care am vrut să le implementez pentru a-mi încânta imaginile, dar nu am avut timp:

  • Faceți capsulele parțial transparente și țineți cont de suprapunere pentru a reprezenta culorile mai bine în regiunile imaginii, unde există o mulțime de capse.
  • Alegeți un număr limitat de culori de bază (3 sau mai multe) și generați mai multe straturi de capse parțial transparente pe baza funcțiilor de densitate diferite obținute prin examinarea separată a componentelor de culoare ale imaginii sursă.
  • Faceți ca culoarea și dimensiunea știfturilor să funcționeze împreună pentru a reprezenta mai bine schimbările de ton. De exemplu, micul întunecat ar trebui să aibă un efect similar cu cel mare.
Mai jos sunt câteva dintre rezultatele mele finale:

Această versiune color a imaginii omului vechi a fost redată folosind 15000 de capse de dimensiuni constante cu eșantionare imporance.
Descărcați alb-negru SVG Descărcați SVG color