\documentclass[11pt,oneside]{fithesis} \usepackage[plainpages=false, pdfpagelabels, colorlinks, hyperindex, breaklinks, linktocpage, draft]{hyperref} \usepackage{czech} \usepackage{a4wide} \usepackage{graphicx} \usepackage{subfigure} \usepackage{amssymb,amsmath} \usepackage{url} \usepackage{wrapfig} \usepackage{epsfig} \usepackage{listings} \thesistitle{Tvorba ilustrací pomocí rychlé distribuce kreslicích primitiv} \thesissubtitle{Bakalářská práce} \thesisstudent{Josef Sedlačík} \thesiswoman{false} \thesisfaculty{fi} \thesisyear{jaro 2008} \thesisadvisor{doc. Ing. Jiří Sochor, CSc.} \thesislang{cs} \begin{document} \FrontMatter \ThesisTitlePage \begin{ThesisDeclaration} \DeclarationText \AdvisorName \end{ThesisDeclaration} \begin{ThesisThanks} Rád bych poděkoval vedoucímu práce doc. Ing. Jiřímu Sochorovi za cenné rady a pomoc při~řešení práce. \end{ThesisThanks} \begin{ThesisAbstract} Cílem práce bylo nastudovat metodu nefotorealistického vykreslování a porovnat ji s jinými podobnými přístupy. V praktické části pak implementovat jednoduchou aplikaci, která by umožnila vytvářet ilustrace popsanou metodou.\\ V první části práce je popis několika metod pro nefotorealistické zobrazování a jejich srovnání. V druhé části práce je popsán realizovaný program. \end{ThesisAbstract} \begin{ThesisKeyWords} grafická primitiva, hustota pravděpodobnosti, distribuční funkce, histogram \end{ThesisKeyWords} \MainMatter \tableofcontents \chapter{Úvod do problematiky} \section{Co je nefotorealistické zobrazování} Metody v počítačové grafice, které se snaží vytvářet fotorealistický obraz virtuální trojrozměrné scény, se označují jako \uv{fotorealistické}. Myslí se tím míra podobnosti obrazu virtuální scény s fotografií. Nefotorealistické zobrazování (angl. non-photorealistic rendering, zkratka NPR) je pak oblastí počítačové grafiky, která se o fotorealismus nesnaží. NPR je inspirováno uměleckými styly jako malba, kresba, technická ilustrace... Fotorealismus je pro některé scény nevhodný, scény jsou zbytečně složité a těžko se v nich orientuje. Proto je vhodnější použít nefotorealistické zobrazení. NPR zobrazí jen důležité části a nepotřebné části zanedbá. Např. u manuálu k sestavení nějakého přístroje není zapotřebí mít do podrobna vykreslenou každou součástku, ale stačí zobrazit jen základní tvary součástek. Současné NPR metody lze rozdělit do několika oblastí. Každá z těchto oblastí řeší odlišný okruh problémů -- simulace tradičních malířských technik, simulace kreseb a rytin, metody pro názornější zobrazení scény... \section{Ilustrace se vzhledem perokresby} Metody snažící se napodobit vzhled perokresby, můžeme rozdělit do dvou kategorií: image-space a object-space metody. Někdy odkazované v literatuře jako image precision a object precision. Metoda object-space provádí výpočty na jednotlivých objektech scény, porovnává jednotlivé objekty mezi sebou. Metoda image-space bere v úvahu viditelnost jednotlivých pixelů každého objektu v~scéně. Problémem je tvorba animací kreseb. Pokud jsou grafická primitiva umístňována náhodně, při animování scény vzniká šum. Je tedy nutné zaručit koherenci umístění primitiv. Jednou možností je držet primitiva na místě relativně k obrazu. Je tak zaručena určitá koherence, ale tyto animace trpí tzv. \uv{shower-door} efektem -- animace působí dojmem, že se odehrává za nepohyblivým reliéfním sklem. Pod pojmem grafická primitiva jsou považovány základní dvourozměrné objekty (úsečky,lomené čáry, kružnice, mnohoúhelníky, křivky...) Většinu z nich nalezneme jako základní útvary pro práci v kreslících programech. Lepší dojem zanechávají techniky, které se snaží držet primitiva na místě relativně k~jednotlivým objektům scény. \chapter{NPR metody} V této kapitole uvádím přehled několika NPR metod a jemný nástin na způsob, jakým přistupují ke zpracování obrazové informace. U každé z těchto metod jsem se snažil zobrazit ukázky ilustrující postupné zpracování jednotlivými metodami. \section{Image-space ilustrace se vzhledem perokresby pro textury}\label{textury} Systém se dělí dle formátu vstupu na 2 rozsáhlé kategorie: geometry-based systém, který má na vstupu informace ze 3D scény, a image-space systém -- vstupem obraz v úrovních šedi.\\ \begin{figure}[h] \begin{center} \label{fig:orient} \includegraphics[scale=1.0]{obr/salisbury} \caption{Jednotlivé vrstvy zleva stín, směr a množina vzorků. Vpravo výsledná ilustrace získáná složením komponent. (Přejato z \cite{textures})} \end{center} \end{figure} Podle druhu vstupu se v této metodě zpracovává signál jiným způsobem. U 2D vstupu se výsledný produkt složí kombinací tří komponent. Šedotónní obraz -- definuje stíny pro~ilustraci. Směr -- definuje orientaci textury v bodech. A množina vzorků, kterými se vykreslí konečná podoba ilustrace. Ukázka na obrázku \ref{fig:orient}. Uživatel si ale musí nadefinovat jednotlivé komponenty ručně. Narozdíl od 3D scény zvládá tato metoda u 2D vstupu ilustrovat i složitejší modely jako srst zvířat či lidský obličej. Podrobněji v \cite{textures}. Pro vstup lze použít jak 3D model tak i 2D obraz. Barevný obraz na vstupu můžeme použít jen za předpokladu, že bychom jej ještě před přímým zpracováním touto metodou převedli na šedotónní obraz. Pro výsledné zpracování potřebujeme nadefinovat tři \uv{obrazy}. Do tvorby těchto částí ale musí zasáhnout uživatel. Je to jediný systém, kde musí během vytváření ilustrace zasahovat uživatel. Všechny ostatní metody zde popsané generují ilustrace bez vnějšího zásahu. Kromě toho zde potřebujeme dva stejně velké buffery jako originální obraz a jeden menší, do kterých bychom mohli uložit jednotlivé vrstvy, z kterých se pak složí výsledná ilustrace. \section{Ilustrace stromů se vzhledem perokresby}\label{stromy} \begin{figure} \begin{center} \subfigure[Model stromu]{\includegraphics[scale=0.5]{obr/treeColor}}% \qquad \subfigure[Ilustrace kmene]{\includegraphics[scale=0.5]{obr/treetrunk}}% \qquad \subfigure[Ilustrace s prahováním 1000]{\includegraphics[scale=0.5]{obr/treebw1}}% \qquad \subfigure[S prahováním 2000]{\includegraphics[scale=0.5]{obr/treebw2}}% \caption{Ukázka ilustrace metodou \ref{stromy} (Přejato z \cite{trees})} \end{center} \end{figure} Tato metoda byla navrhnutá pro ilustraci stromů. Ke zpracování potřebuje model stromu, vytvořeného např. systémem Xfrog\cite{xfrog}. Konečný model z tohoto systému je předzpracován a jsou vytvořeny dva soubory. V prvním je uložena geometrie kostry stromu. Ve druhém souboru jsou uloženy informace o listech -- pozice a normálové vektory. V původním modelu stromu se většinou nachází velké množství listů, které je třeba zredukovat kvůli složitosti výpočtu. Kmen a větve jsou jsou v ilustraci vykresleny známými NPR technikami. Mohli bychom proto použít i algoritmus z~kapitoly \ref{algoritmus}. Jelikož se listí výrazně liší od zbývajících povrchů, musí být zpracováno odděleně od zbytku scény. Každý list je vykreslen grafickými primitivy. Seřazením primitiv podle hloubky ve scéně se pak určí, které se ve výsledku vykreslí. Pro zjištění hloubky umístění primitiv je používán hloubkový buffer. Pro každý pixel se spočítá rozdíl se všemi okolními pixely. Jako výsledek se bere největší pozitivní rozdíl. Tato hodnota určuje, jak daleko před okolními pixely je daný pixel. Pro konečné vykreslení se pak použije prahování\cite{treshold}. Všechny pixely, které mají rozdíl hloubky větší než daný práh, jsou použity k záverečnému vykreslení. Okolní vegetace může být vykreslena stejným způsobem. Podrobnější popis této metody je popsán v \cite{trees}. Pro tvorbu ilustrací touto metodou je jediným možným vstupem 3D model. Což je podle mě celkem nevýhoda. Buď potřebujeme mít k~dispozici soubory s~3D modely stromů nebo si je musíme vytvořit pomocí nějakého programu pro tvorbu rostlin. Nevýhodou je podle mého názoru způsob zpracování listí, který celý algoritmus nejspíše hodně zpomaluje. I když se podaří množství listů zredukovat, jsou všechny zbývající listy vykresleny jako nějaký polygon. V takto vzniklém obraze pak navíc porovnávám každý pixel se všemi okolními pixely. U modelu s mnoha listy to může celý postup zpracování zpomalit. \section{Perokresba pro parametrické povrchy}\label{par_pov} Metoda pro automatické generování ilustrace se vhledem perokresby pro mnohostěnné modely. Moc se neliší od tradičních fotorealistických metod. Vstupem je 3D model, jedno nebo více světel a nastavení kamery. Výpočet se zahájí zjištěním viditelných povrchů a polygonů se stínem použitím 3D BSP stromu. Podrobnější informace o BSP stromech jsou v \cite{mod_graf}. Výsledkem tohoto procesu je množina konvexních polygonů seřazených podle hloubky. Ty jsou pak použity k sestavení 2D BSP stromu a rovinné mapy prezentující viditelné povrchy scény. Poté se můžou vykreslit jednotlivé oblasti rovinné mapy použitím textury tvořené čarami. Jediným možným vstupem pro tuto metodu je 3D model. Pro 2D vstup by se tato metoda upravit nedala, protože bychom tak přišli o důležité informace, pomocí kterých se počítá výsledná ilustrace. Zjištění viditelných částí je řešeno jednoduchým způsobem za pomoci BSP stromu. Pokud modelem nemanipulujeme, je třídění pomocí BSP stromu rychlé. Tuto metodu bych označil jako za nejsložitější ze všech, které v této práci zmiňuji. Složitostí bych ji nejspíše mohl srovnávat s tradičními fotorealistickými metodami. \begin{figure}[h] \begin{center} \includegraphics[scale=0.5]{obr/surface}% \caption{Ukázka ilustrace metodou \ref{par_pov} (Přejato z \cite{surfaces})} \end{center} \end{figure} \section{Automatické NPR odstraněním měkkých stínů}\label{softrem} \begin{wrapfigure}{r}{0.5\textwidth} \begin{center} \includegraphics[scale=0.5]{obr/soft_shading2} \label{fig:softexmaple} \caption{Originální obrázek a obrázek upravený metodou \ref{softrem}} \end{center} \end{wrapfigure} Tato metoda narozdíl od~ostatních zmiňovaných v~této práci negeneruje binární obraz, ale barevný. Odstraňuje měkké stíny a přidává černé kontury podél objektů. První část zaměřená na~odstranění stínů je založena na~rozdělení původního obrazu. Na~obraz s~jasovou složku a dva barevné obrazy, které odpovídají barevným kanálům červená-zelená (RG) a modrá-žlutá(BY). Původní RGB obraz se převede na~LMS prostor (kde $ L, M, S $ jsou dlouhé, střední a krátké vlnové délky). Pomocí LMS prostoru se původní barevný obraz převede na~dané tři obrazy. Dále jsou nalezeny hrany v~RG a BY obrazech a provedena jejich kombinace pomocí logického součtu. V~dalším kroku se odvodí obraz klasifikovaný podle hran nalezených v~předcházejícím kroku. Následuje vrácení barev do~obrazu, ale už s~odstraněnými měkkými stíny. Jako poslední krok se k~tomuto obrazu přidají kontury objektů. Výsledný efekt je lépe vidět na~obrázku \ref{fig:softexmaple}. Je to jediná metoda v této práci, která generuje barevný obraz. Ke zpracování používá 2D obraz, ale mohli bychom použít i 3D model a vyrenderovat z~něj 2D obraz. Jelikož se jedná o NPR metodu pro generování barevného obrazu, tak oproti všem zde zmiňovaným přístupům používá všechny barevné kanály. Vzdáleně bych ji mohl přirovnat k~metodě z~kapitoly \ref{textury}, která výsledný obraz také skládá z několika rozdílných vrstev získaných z~původní předlohy. Metoda je podrobněji popsána v \cite{soft_shading} \section{Ilustrace pomocí rychlé distribuce kreslících primitiv} Jednou z NPR metod je i metoda ilustrace pomocí rychlé distribuce kreslících primitiv, kterou jsem měl v rámci této práce nastudovat a vytvořit podle ní jednoduchou funkční aplikaci. Základní popis metody je převzat z \cite{heidrich} a je doplněn textem, který podrobněji popisuje způsob, jak algoritmus funguje. \subsection{Odvození algoritmu pro vytváření ilustrace} Kreslící proces by měl vytvořit binární obraz, kde pravděpodobnost, že pixel $ x_i $ je vykreslen, je identická k intensitě odpovídajícímu pixelu v originálním obraze, tj. $ p(x_i = 1) = I(x_i) $. Navíc bychom chtěli nezávisle umístit vzorky pro generování tohoto binárního obrazu. Potřebujeme najít PDF (hustotu pravděpodobnosti - v angl. probability density function) $ q(x) $, která by mohla být použita algoritmem z podkapitoly \ref{algoritmus}.\cite{heidrich} Po umístění $ N $ vzorků podle PDF $ q(x) $ je pravděpodobnost, že pixel $ x_i $ není vykreslen,\\ $ (1-q(x_i))^N $. Využijeme ale opačného jevu, kdy pixel $ x_i $ vykreslen je. \begin{align} (1-q(x_i))^N&=p(x_i=1)\notag \\ q(x_i)&=1-\sqrt[N]{1-p(x_i=1)}\tag{1}\label{eq:1} \end{align} pro všechna $ i = 1...n $, kde $ n $ je počet pixelů v obraze.\\ Potřebujeme, abychom integrací $ q(x_i) $ získali jedničku a dodrželi tak definici CDF (distribuční funkce - v angl. cumulative density function). Kombinací těchto omezení a předchozí rovnice získáme \begin{align} \sum_{i=1}^n q(x_i) = 1 \Leftrightarrow ... \Leftrightarrow \sum_{i=1}^n \sqrt[N]{1 - p(x_i=1)} = n - 1\tag{2}\label{eq:2} \end{align} Pro obecné obrazy nemůže být tento systém rovnic řešen přímo, ale je zapotřebí použít nějakou numerickou metodu, např. binární hledání. Binární hledání nemusí být počítáno přes celou sumu. Každý term v sumě závisí pouze na pravděpodobnosti $ p(x_i = 1) $ každého pixelu, která závisí na intensitě $ I(x_i) $ vstupního obrazu, která je obvykle kvantifikována, např. pro 256 odstínů šedé. Jestliže označíme kvantifikované odstíny jako $ I_j, j = 1...K $ a histogram vstupního obrazu jako $ H(I_j) $, můžeme rovnice \ref{eq:1} a \ref{eq:2} přepsat jako \begin{align} q(I_j) = 1 - \sqrt[N]{1 - I_j}\tag{3}\label{eq:3} \end{align} a \begin{align} \sum_{j=1}^K H(I_j) \sqrt[N]{1 - I_j} = n - 1\tag{4}\label{eq:4} \end{align} které zahrnují sumu jen přes $ K $ odstínů a nikoliv přes $ n $ pixelů.\cite{heidrich}\\ Výsledný program můžeme použitím histogramu zrychlit v řádu několika sekund. \subsection{Generování náhodných bodů} \subsubsection{Pomocí 1D PDF} Je dána jednodimenzionální PDF $ p(x), x \in [0,1] $ a množina rovnoměrně distribuovaných náhodných vzorků $ {x_i} $ nad $ [0,1] $. Vzorky můžeme rozdistribuovat podle $ p(x) $. Ukázka 1D PDF je na obrázku \ref{fig:PDF}.\cite{heidrich} Spočítáme distribuční funkci \begin{align} C(x) = \int\limits_0^x{p(t)dt}\notag \end{align} jak ukazuje obrázek \ref{fig:CDF}. Poté můžeme $ C(x) $ invertovat a transformovat jednotlivé vzorky $ x_i $ na $ x_i^{\prime} = C^{-1}(x_i) $. Graficky je to znázorněno na obrázku \ref{fig:iCDF} jako mapování množiny vzorků na ose $ y $ na osu $ x $. Množina $ {x_i} $ znázorněná jako kolečka na ose $ x $ na obrázku \ref{fig:iCDF} jsou distribuovány podle původní PDF $ p(x) $. \begin{figure}[!h] \label{fig:zeroInverse} \begin{center} \subfigure[PDF]{\includegraphics[scale=0.5]{obr/pdf1zero}}% \qquad \subfigure[CDF\label{fig:zeroCDF}]{\includegraphics[scale=0.5]{obr/pdf2zero}}% \qquad \subfigure[Inverse \ref{fig:zeroCDF}\label{fig:zero}]{\includegraphics[scale=0.5]{obr/pdf3zero}}% \caption{Ukázka transformace s nulovými oblastmi v PDF. Obr. \ref{fig:zero} není funkce. (Přejato z \cite{secord})} \end{center} \end{figure} Počítání inverze CDF není úplně přímé, jsou-li totiž v PDF místa s nulovou pravděpodobností, integrují se v CDF na stejnou hodnotu. Obrázek \ref{fig:zeroInverse} ukazuje daný problém. V této části pak neexistuje inverze. Daná funkce se může rozložit na několik částí, u nichž inverze neporušují podmínky pro funkce. Jednotlivé části se pak vyřeší samostatně. Další možností je daný úsek vynechat, ale v takovém případě se ve výsledném obraze nemusí daný řádek(sloupec) vůbec vykreslit.\cite{heidrich} \begin{figure} \begin{center} \label{fig:redistribuce} \subfigure[1D PDF\label{fig:PDF}]{\includegraphics[scale=0.15]{obr/PDF}}% \subfigure[1D CDF\label{fig:CDF}]{\includegraphics[scale=0.15]{obr/CDF}}% \subfigure[1D CDF a její vzorkování\label{fig:iCDF}]{\includegraphics[scale=0.15]{obr/CDFi}}% \caption{Ukázka redistribuce bodů podle 1D PDF.} \end{center} \end{figure} \subsubsection{Pomocí 2D PDF} Je dána dvoudimenzionální PDF $ p(x), x \in [0,1]^2 $ a množina rovnoměrně distribuovaných náhodných bodů $ p_i $ nad $ [0,1]^2 $. Body můžeme rozdistribuovat podle $ p(x) $ užitím transformační metody.\cite{heidrich} K nalezení y-souřadnice $ q_i^y $ redistribuovaného bodu $ q_i $ spočítáme distribuční funkci \begin{eqnarray} \nonumber M(y)=\int\limits_0^y{m(t)dt}\text{, kde }m(y)=\int\limits_0^1{p(x)dx} \end{eqnarray} a získáme $ q_i=M^{-1}(p_i^y) $. Funkce $ M(y) $ je monotónní, ale ne striktně monotónní, jestliže některé řádky mají nulovou intenzitu. $ M^{-1}(y) $ tedy existuje téměř vždy až na místa isolovaných bodů.\cite{heidrich} Máme-li spočteno $ q_i^y $, můžeme určit x-ové souřadnice $ q_i^x $ podle PDF, respektivě podle řádky. Matematicky můžeme daný vztah vyjádřit jako podmíněnou PDF \begin{align} c(x|q_{i,y}) = \frac{p(x,q_{i,y})}{m(q_{i,y})}\notag \end{align} a její CDF \begin{align} C(x|q_{i,y}) = \int\limits_0^x{c(s|q_{i,y})ds}\notag \end{align} Stejně jako předtím, x-ová souřadnice nového bodu je dána inverzní funkcí $ q_i^x = C^{-1}(p_i^x|q_{i,y}) $. Pro diskrétní PDF $ q(x) $, stejně jako při odvození z obrazu, můžeme $ M(y) $ a $ C(x|y) $ jednoduše předpočítat jako 1D a 2D pole. Jednoduchým hledáním v poli pak můžeme najít hledané souřadnice. \begin{figure} \begin{center} \label{fig:2D_PDF} \includegraphics[scale=0.5]{obr/marginal} \caption{2D PDF a pravděpodobnost pro jednotlivé řádky (vpravo) a 1D PDF řádku (nahoře) (Přejato z \cite{secord})} \end{center} \end{figure} Obrázek \ref{fig:2D_PDF} ukazuje 2D PDF, kde tmavé oblasti jsou mapovány na nízké pravděpodobnosti a světlé oblasti na vysoké pravděpodobnosti. Vpravo je marginalní funkce $ m(y) $ získaná integrací jednotlivých řádků. Nahoře je jedna z mnoha řádkových PDF, $ c(x|y) $ pro nějaké $ y $ znázorněné černou čarou v obrázku.\cite{heidrich} \subsection{Algoritmus}\label{algoritmus} Shrnutím předchozí teorie můžeme přepsat algoritmus do 7 základních kroků. \begin{enumerate} \item Načtení vstupního obrazu. \item Vytvoření histogramu intezit obrazu. \item Nalezení $ N $, počtu primitiv, které se budou vykreslovat, použitím rovnice \ref{eq:4}.\\ Pro spočtení $ N $ je zapotřebí použít některou z numerických metod (půlení intervalu, metoda sečen...) \item Spočtení PDF $ q(I_{j}), j = 1...K $ , kde $ K $ je počet úrovní intenzit, použitím rovnice \ref{eq:3}.\\ Za $ N $ se dosadí hodnota spočtená v předcházejícím kroku. \item Integrace řádků a invertování na formu $ M^{-1} $.\\ \item Integrace a invertování na formu $ C^{-1} $.\\ \item Distribuce $ N $ primitiv podle $ M^{-1} $ a $ C^{-1} $.\\ Primitiva jsou distribuovány podle původní PDF. Pro umístění primitiv podle PDF se použije zamítací metoda \cite{numerical_rec} popsaná dále. \end{enumerate} \subsection{Zamítací metoda}\label{rej_method} Po invertování na $ M^{-1} $ a $ C^{-1} $ je potřeba dané body redistribuovat podle původní PDF. K~tomu nám dobře poslouží zamítací metoda (v angl. rejection method). \begin{figure}[!h] \begin{center} \label{fig:rejection} \includegraphics[scale=0.5]{obr/rejection} \caption{Zamítací metoda pro generování náhodné proměnné $ x $ ze známé PDF $ p(x) $, která je menší než nějaká funkce $ f(x) $. Nejdříve se najde nová hodnota $ x_0 $. Ve druhém kroku pro $ x_0 $ vygeneruju náhodnou hodnotu $ l: l < f(x_0) $. Pokud $ l < p(x_0) $, dané $ x_0 $ akceptuji, jinak ho zamítnu.} \end{center} \end{figure} Mějme novou funkci $ f(x) $ takovou, že $ p(x) \leq R.f(x) $ pro konstantu $ R $. Pro použití v~algoritmu zvolíme $ R = max(p(x)) $. Pro $ x $ najdeme pomocí inverze $ x_0 $. Pro redistibuovaný bod $ x_0 $ náhodně vybereme číslo $ l: l \in [0, R] $. Pokud $ p(x_0) < l $ bod můžeme vykreslit, v~opačném případě bod zahodíme. Princip metody je lépe vidět na obrázku 2.8. \subsection{Kreslící styly} Tento algoritmus může být použitý k rozdílným kreslícím stylům. V základním návrhu potřebuje algoritmus na vstupu jen šedotónní obraz, aby se vygenerovalo PDF.\\ Pokud se použije místo obrazu na vstupu 3D model, můžeme do obrazu zakódovat dodatečné informace a využít je potom k rozdílným kreslícím stylům.\\ Následující tři popsané styly se dají aplikovat i na 2D obraz. \subsubsection{Tečkování - v angl. point stippling} Je to základní styl na renderování ilustrace popsanou metodou, který nepotřebuje z obrazu získávat žádné dodatečné informace.\\ Ilustraci vykreslenou tímto stylem získáme následujícím způsobem: \begin{enumerate} \item Načtení vstupního obrazu. \item Sestavení histogramu vstupního obrazu. \item Spočtení $ N $. Pro rychlejší výpočet se bere v potaz váha jednotlivých intenzit z histogramu.\\ $ N $ nejde z rovnice \ref{eq:4} vyjádřit, proto je potřeba použít některou z numerických metod na~jeho spočtení, např. metodu půlení intervalu. \item Spočtení PDF $ q(I_j), j = 1..K $, kde $ K $ je počet odstínů šedé ve vstupním obraze pomocí rovnice \ref{eq:3}. Za $ N $ se dosadí hodnota získaná v předcházejícím kroce. \item Vypočtení marginálních funkcí pro jednotlivé řádky - $ \int_0^1 p(x)dx $. Budou potřeba v následujících krocích. \item Spočítání distribuční funkce $ M(y)=\int\limits_0^y{m(t)dt} $, kde $ m(y) $ jsou hodnoty marginálních funkcí z předchozího kroku. \item Spočítání podmíněné distribuční funkce $ C(x|q_{i,y}) = \int\limits_0^x{c(s|q_{i,y})ds} $. PDF daného bodu se dělí hodnotou marginální funkce pro řádek, na kterém se daný bod nachází. \item Distribuce primitiv podle původní PDF $ q(x) $.\\ Pro každý bod v původním obraze nalezneme jeho nové souřadnice pomocí inverze $ M^{-1} $ a $ C^{-1} $. Nové souřadnice nalezneme jako $ y_0 = M^{-1}(y) $ a $ x_0 = C^{-1}(x|y_0) $, kde $ x $ a $ y $ jsou převedeny na interval $ [0, 1] $.\\ Nejdříve se zjistí nová souřadnice $ y_0 $ a teprve potom můžeme vypočítat i novou souřadnici $ x_0 $.\\ Jakmile máme vypočteny nové souřadnice, musíme podle původní PDF rozhodnout, jestli se daný bod vykreslí nebo ne. K tomu se použije zamítací metoda popsaná výše. \end{enumerate} \begin{figure}[!h] \begin{center} \label{fig:point_stippling} \subfigure[\label{fig:2}]{\includegraphics[scale=0.4]{obr/example/original/2}}% \qquad \subfigure[\label{fig:2_point}]{\includegraphics[scale=0.4]{obr/example/2_point}} \qquad% \subfigure[\label{fig:5}]{\includegraphics[scale=0.46]{obr/example/original/5}}% \qquad \subfigure[\label{fig:5_point}]{\includegraphics[scale=0.33]{obr/example/5_point}}% \caption{Ukázka po aplikování algoritmu.} \end{center} \end{figure} \subsubsection{Šrafování - v angl. hatching} U tohoto stylu se používají čáry rozdílné tloušťky a délky. Orientace čar se volí konstantně.\\ Postup pro získání obrazu vykresleného tímto stylem je stejný jako u tečkování s jediným rozdílem, místo bodů se používají čáry se středem $ x_0, y_0 $. \begin{figure}[!h] \begin{center} \label{fig:point_stippling_2} \subfigure[\label{fig:2_hatching}]{\includegraphics[scale=0.5]{obr/example/2_hatching}}% \qquad \subfigure[\label{fig:1_hatching}]{\includegraphics[scale=0.4]{obr/example/1_hatching}} \caption{Ukázka po aplikování algoritmu - šrafování.} \end{center} \end{figure} \subsubsection{Šrafování s různou orientací čar - v angl. cross hatching} Tento styl je velice podobný předchozímu. Pouze u čar není pevně dána orientace, ta se spočítá pro každou vykreslovanou čáru zvlásť z původního obrazu.\\ Pro zjištění orientace můžeme použít sobelův operátor \cite{sobel}. Spočítáme gradient ve směru $ x $ a ve~směru $ y $.\\ \[ G_x = \left| \begin{array}{ccc} +1 & 0 & -1 \\ +2 & 0 & -2 \\ +1 & 0 & -1 \end{array} \right| * A \text{ a } G_y = \left| \begin{array}{ccc} +1 & +2 & +1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{array} \right| * A.\] Úhel $ \alpha $ spočítám jako $ \alpha = \frac{\pi}{2} - \arctan{\frac{G_y}{G_x}} $. Jednotlivé čáry se potom v obraze vykreslí natočené podle tohoto úhlu. \begin{figure}[!h] \begin{center} \label{fig:point_stippling_3} \subfigure[\label{fig:3_cross}]{\includegraphics[scale=0.4]{obr/example/3_cross}}% \qquad \subfigure[\label{fig:5_cross}]{\includegraphics[scale=0.4]{obr/example/5_cross}} \caption{Ukázka po aplikování algoritmu - šrafování s rozdílnou orientací čar.} \end{center} \end{figure} \subsection{Korekce tónů} Při používání primitiv větších než pixel může docházet k překrývání jednotlivých bodů v~generovaném obraze. Například při použití bodů o poloměru 3 pixelů ztrácíme velkou část obrazové informace. \begin{figure} \begin{center} \label{fig:overlap} \includegraphics[scale=0.5]{obr/lena_overlap} \caption{Tečkování při nastavení poloměru 2} \end{center} \end{figure} Aby se uchoval správný tón výstupního obrazu, musíme již vzít v~úvahu vztahy mezi pixely. Převedeme původní postup do 2D. Místo $ p(x_i) $ budeme používat $ p(x_{i,j}) $.\\ Po této úpravě můžeme přepsat pravděpodobnost na \begin{align} p(x_{i,j}=1) = 1 - \left(1 - \sum_{k=1}^{n_x}\sum_{l=1}^{n_y}q(x_{k,l})s(x_{k-i,l-j})\right)^N \tag{5}\label{eq:5} \end{align} kde $ i = 1...n_x, j = 1...n_y $ a $ s(x_{k-i,l-j}) $ je binární obraz získaný původním algoritmem. Hodnota $ s(x) $ je tedy rovna jedné nebo nule. Dále je potřeba upravit rovnici \ref{eq:2}, získáme \begin{align} \sum_{k=1}^{n_x}\sum_{l=1}^{n_y}q(x_{k,l}) = 1. \tag{6}\label{eq:6} \end{align} Stejně jako v původním případě, musí být tyto dvě rovnice řešeny souběžně, abychom získali $ q(x_{i,j}) $ a $ N $. Tento systém rovnic ale nemá řešení, pokud se ve vstupním obraze vyskytují místa, která jsou užší než použitá primitiva.\\ Přidáním podmínky $ q(x_{k,l}) \geq 0 $ lze docílit minimálních rozdílu mezi jednotlivými stranami rovnice \ref{eq:5}. Rovnici \ref{eq:5} můžeme ještě aproximovat a získáme tak \begin{align} p(x_{i,j}=1) &= 1 - \left(1-\sum_{k=1}^{n_x}\sum_{l=1}^{n_y}q(x_{k,l})s(x_{k-i,l-j})\right)^N \tag{7}\label{eq:8}\\ &\approx 1 - \left(1-q(x_{k,l})\sum_{k=1}^{n_x}\sum_{l=1}^{n_y}s(x_{k-i,l-j})\right)^N \tag{8}\label{eq:9}\\ &= 1 - \left(1-q(x_{k,l})s_{i,j}\right)^N \tag{9}\label{eq:10} \end{align} kde $ s_{i,j} \equiv \sum\limits_{k=1}^{n_x}\sum\limits_{l=1}^{n_y}s(x_{k-i,l-j}) $. $ s_{i,j} $ představuje počet pixelů $ (x_k,y_l) $, které mohou způsobit, že se díky nim vykreslí i pixel $ (x_{i,j}) $.\cite{heidrich}\\ \begin{figure} \begin{center} \label{fig:tone} \subfigure[\label{fig:1_cross_tone}]{\includegraphics[scale=0.4]{obr/example/1_cross_tone}}% \qquad \subfigure[\label{fig:2_cross_tone}]{\includegraphics[scale=0.4]{obr/example/2_cross_tone}} \qquad% \subfigure[\label{fig:4_cross_tone}]{\includegraphics[scale=0.35]{obr/example/4_cross_tone}} \caption{Ukázka při použítí korekce tónů.} \end{center} \end{figure} Pro aplikování korekce tónů je zapotřebí nejprve provést původní algoritmus. Místo vykreslování obrazu budeme ale počítat $ s_{i,j} $. Jakmile známe $ s_{i,j} $, můžeme jej použít k vypočtení nového $ N $ - počet primitiv k vykreslení. \begin{align} \sum\limits_{k=1}^{n_x}\sum\limits_{l=1}^{n_y}\frac{1-\sqrt[N]{1 - I_{i,j}}}{s_{i,j}} = 1 \tag{10}\label{eq:11} \end{align} $ N $ stejně jako v původním algoritmu nejde vypočítat přímo, ale je opět nutné použít numerickou metodu, např. metodu půlení intervalu. Poté dosadíme nově spočtené $ N $ do rovnice \ref{eq:10} a spočítáme z ní $ q_{k,l} $. Další postup se shoduje s původním algoritmem. Spočítání marginální funkce, distribuční funkce... s jediným rozdílem, místo $ q(I_j) $ se použije $ q(x_{k,l}) $. \subsection{Srovnání metod} V následující tabulce je shrnutí a porovnání předchozích metod.\\ \begin{tabular}{p{4.5cm}||ccc}\label{srovnani} \bfseries \bfseries Metoda & \bfseries Druh vstupu & \bfseries Zásah uživatele & \bfseries Druh výstupu\\[2mm] \hline \hline Image-space ilustrace se vzhledem perokresby pro textury & 2D, 3D & ano & bin. obraz\\\hline Ilustrace stromů se vzhledem perokresby & 3D model stromu & ne & bin. obraz \\\hline Perokresba pro parametrické povrchy & 3D & ne & bin. obraz \\\hline Automatické NPR odstraněním měkkých stínů & 2D & ne & RGB obraz \\\hline Ilustrace pomocí rychlé distribuce kreslících primitiv & 2D, 3D & ne & bin. obraz \\\hline \end{tabular}\\ Z tabulky je vidět, že pro vstup se mohou používat 2D obrazy i 3D modely. Většina metod pak funguje bez zásahu uživatele a generuje pouze binární obrazy. \chapter{Realizovaný program} Důležitou částí aplikace je okno pro nastavení stylů \ref{fig:aplikace_5} a \ref{fig:aplikace_6}. Horní polovina slouží pro nastavení jednotlivých primitiv, pro bod se nastavuje poloměr. Velikost 0 zde znamená, že se jedná o pouhý pixel.\\ U čáry(úsečky) se nastavuje její šířka a délka.\\ V dolní části okna nastavení je možnost si vybrat jeden ze tří stylů vykreslování(tečkování, šrafování a šrafování s různou orientací úseček). Pod přehledem stylů je možnost zašktrnout použití korekce tónů, která slouží k přepočítání výsledné ilustrace, pokud se primitiva v obraze překrývají a v ilustraci nelze řádně rozeznat původní obrázek. Tato volba ale zpracování vstupu zpomaluje.\\ Pokud chceme pro danou ilustraci změnit styl kreslení a nechceme přenastavovat celou aplikaci přes Tools/Options, použijeme Change style z Toolbaru. Aplikace znovu vykreslí ilustraci podle daného stylu pro aktivní okno. \begin{figure}[h] \begin{center} \label{fig:aplikace_4} \includegraphics[scale=0.3]{obr/aplikace_4} \caption{Aplikace s hotovou ilustrací.} \end{center} \end{figure} \begin{figure} \begin{center} \label{fig:app} \subfigure[\label{fig:aplikace_0}]{\includegraphics[scale=0.25]{obr/aplikace_0}}% \qquad \subfigure[\label{fig:aplikace_1}]{\includegraphics[scale=0.25]{obr/aplikace_1}} \qquad% \subfigure[\label{fig:aplikace_2}]{\includegraphics[scale=0.25]{obr/aplikace_2}} \qquad \subfigure[\label{fig:aplikace_3}]{\includegraphics[scale=0.25]{obr/aplikace_3}}% \qquad \subfigure[\label{fig:aplikace_5}]{\includegraphics[scale=0.25]{obr/aplikace_5}} \qquad% \subfigure[\label{fig:aplikace_6}]{\includegraphics[scale=0.25]{obr/aplikace_6}} \caption{Ukázka aplikace.} \end{center} \end{figure} Aplikace pro vstup používá pouze obrázky typu png, jpeg, gif a bmp. Na výstup jsou použity formáty png a gif. Formát jpeg jsem nepoužil kvůli ztrátové kompresi.\\ Pro kvalitnější výstupní obraz doporučuji používat obrázky větších rozměrů(s menší velikostí obrázku klesá kvalita výstupu) a velikost primitiv nevolit příliš velikou. \chapter{Závěr} Při zpracovávání této práce jsem zíslal základní znalosti o jedné z mnoha metod pro nefotorealistické zobrazování, na jejichž základě jsem byl schopen vytvořit jednoduchou aplikaci pro tvorbu ilustrací.\\ Při zpracování jsem se naučil i další metody z počítačové grafiky, např. vykreslování kružnice pomocí Bresenhamova algoritmu, vzplňování ohraničeného prostoru...\\ Dále jsem měl v rámci práce příležitost porovnat tuto metodu s několika dalšími. Zadaná metoda se mi na rozdíl od ostatních metod zmiňovaných v této práci, zdála asi jako nejjednodušší. Některé z NRP metod bych mohl složitostí přirovnat i k fotorealistickým metodám zobrazování.\\ Ukázky výstupu z aplikace jsou na přiloženém CD ve složce samples. \pagestyle{plain} \begin{thebibliography}{99} \bibitem{textures}{\em Salisbury M. P., Wong M. T., Hughes J. F., Salesin D. H.}, Orientable Textures for Image-Based Pen-and-Ink Illustration\\ University of Washington, 1997\\ Dokument dostupný na http://www.cs.brown.edu/courses/cs224/papers/orient.pdf (leden 2008) \bibitem{trees}{\em Deussen O., Strothotte T.}, Computer-Generated Pen-and-Ink Illustration of Trees\\ Faculty of Computer Science, University of Magdeburg, 2000 \bibitem{xfrog}{\em Greenworks GbR.}, Domovská stránka systému xfrog http://www.greenworks.de \bibitem{treshold} http://cs.wikipedia.org/wiki/Prahování (leden 2008) \bibitem{mod_graf}{\em Žára J., Beneš B., Sochor J., Felkel P.}, Moderní počítačová grafika (2. vydání)\\ Computer Press, Brno, 2004 \bibitem{surfaces}{\em Winkenbach G., Salesin D. H.}, Rendering Parametric Surfaces in Pen and Ink, Department of Computer Science \& Engineering\\ University of Washington, Seattle, 1996 \bibitem{soft_shading}{\em Olmos A., Kingdom F. A. A.}, Automatic non-photorealistic rendering through soft-shading removal: a colour-vision approach\\ 2nd International Conference on Vision, Video and Graphics (VVG '05), pp. 203--208, Edinburgh, 2005\\ Dokument dostupný na http://www.eg.org/EG/DL/PE/VVG/VVG05/203-207.pdf.abstract.pdf (leden 2008) \bibitem{heidrich}{\em Secord A., Heidrich W., Streit L.}, Fast Primitive Distribution for Illustration\\ Department of Computer Science, The University of British Columbia, Vancouver, 2002\\ Dokument dostupný na http://www.cs.ubc.ca/~heidrich/Papers/RW.02.pdf (leden 2008) \bibitem{secord}{\em Secord A. J.}, Random Marks on Paper Non-Photorealistic Rendering with Small Primitives\\ B.Math., University of Waterloo, 2000 \bibitem{sobel} http://en.wikipedia.org/wiki/Sobel\_operator (leden 2008) \bibitem{numerical_rec}{\em Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P.}, Numerical Recipes in C. The Art of Scientific Computing, Second Edition\\ Press Syndicate of the University of Cambridge, 1993 \end{thebibliography} \appendix \chapter{Obsah přiloženého CD} \begin{itemize} \item{Zdrojový kód bakalářské práce ve formátu pro \LaTeX a samotná práce ve formátu pdf} \item{Zdrojové kódy aplikace pro Visual C++ 2005} \item{Ukázkový výstup aplikace} \item{Zkompilovaná verze aplikace} \end{itemize} \newpage \section{Zdrojový kód} \lstset{ breaklines=true, % line wrapping on language=C++, commentstyle=\color{green}, flexiblecolumns=true, breakautoindent=false } \begin{lstlisting} //Zakladni funkce volana pro redistribuci primitiv. Bitmap^ redistribute(System::Drawing::Bitmap^ bmp) { Thread^ oThread = gcnew Thread( gcnew ParameterizedThreadStart( &Thread_wait_form::ThreadProc ) ); oThread->Start(); this->setBitmap(bmp); this->setHistogram(); this->setN(false); this->setQij(); this->setMy(false); this->setCxy(false); oThread->Abort(); return this->draw_into_array(); } /** * spocita pocet primitiv na redistribuci * pocet omezen intervalem 20%-100% vsech pixelu */ void setN(bool correction) { int n; int min = 0; int max; if(correction) { //pri korekci tonu max = this->N; // max. pocet primitiv na zobrazeni, maximalne jako puvodni N n = 1; } else { n = this->bitmap->Width * this->bitmap->Height - 1; // pocet pixelu - 1 max = n; // max. pocet primitiv na zobrazeni int min = (int)Math::Round(n*0.2f); // min. pocet primitiv na zobrazeni int max = min; } int mid; while(min < max) { double sum = 0; mid = (min+max)/2; if(correction) { // spocitam nove N - pro korekci tonu for(int x = 0; x < this->bitmap->Width; x++) { for(int y = 0; y < this->bitmap->Height; y++) { if(this->Sij[x, y] > 0) { double intensity = (double)(this->getIntensity(x, y))/(K-1); double root = Math::Pow(1.0 - intensity, 1.0 / (double)mid); sum += (1.0 - root)/this->Sij[x, y]; } } } } else { for(int i = 0; i < K; i++) { sum += this->histogram[i] * Math::Pow(1-(double)i/(K-1), 1.0/(double)mid); } } if(correction) { if(sum < n) { max = mid - 1; } else { min = mid + 1; } } else { if(sum < n) { min = mid + 1; } else { max = mid - 1; } } } this->N = mid; } /** * spocita PDF */ void setQij() { double base; this->Qij = gcnew array(K); for(int i = 0; i < K; i++) { base = 1.0 - ((double)i / (K-1)); this->Qij[i] = 1 - Math::Pow(base,1.0/(double)this->N); } } /** * spocita CDF pro redistribuci primitiv na ose Y * soucasne spocita i marginal f. -> usetreni jednoho pruchodu pres vysku obrazku */ void setMy(bool correction) { this->marginal = gcnew array(this->bitmap->Height); // init pole this->marginal_max = 0.0; // init max. hodnoty this->My = gcnew array(this->bitmap->Height); // init pole //init pro prvni radek this->marginal[0] = 0; for(int x = 0; x < this->bitmap->Width; x++) { if(correction) { this->marginal[0] += this->CQij[x, 0]; } else { this->marginal[0] += this->Qij[this->getIntensity(x, 0)]; } this->marginal_max = this->marginal[0]; } this->My[0] = this->marginal[0]; // konec prvni radek for(int y = 1; y < this->bitmap->Height; y++) { this->marginal[y] = 0; for(int x = 0; x < this->bitmap->Width; x++) { if(correction) { this->marginal[y] += this->CQij[x, y]; } else { this->marginal[y] += this->Qij[this->getIntensity(x, y)]; } } // najde max. hodnotu if(this->marginal[y] > this->marginal_max) { this->marginal_max = this->marginal[y]; } //spocitam CDF this->My[y] = this->My[y-1]+this->marginal[y]; } } /** * spocita cumulative density function */ void setCxy(bool correction) { this->Cxy = gcnew array(this->bitmap->Width, this->bitmap->Height); // init pole this->max_Cxy = gcnew array(this->bitmap->Height); // init prvniho sloupce for(int y = 0; y < this->bitmap->Height; y++) { if(this->marginal[y]>0) { if(correction) { this->Cxy[0, y] = this->CQij[0, y]/this->marginal[y]; } else { this->Cxy[0, y] = this->Qij[this->getIntensity(0, y)]/this->marginal[y]; } } else { this->Cxy[0, y] = 0; } // init pro zjisteni max. hodnot cond. pdf na radcich this->max_Cxy[y] = 0; } for(int y = 0; y < this->bitmap->Height; y++) { for(int x = 1; x < this->bitmap->Width; x++) { this->Sij[x, y] = 0; // vunuluju puvodni obraz if(this->marginal[y]>0) { double cond_px = 0.0; if(correction) { cond_px = this->CQij[x, y]/this->marginal[y]; } else { cond_px = this->Qij[this->getIntensity(x, y)]/this->marginal[y]; } if(cond_px > this->max_Cxy[y]) { this->max_Cxy[y] = cond_px; } this->Cxy[x, y] = this->Cxy[x - 1, y] + cond_px; } else { this->Cxy[x, y] = this->Cxy[x - 1, y]; } } } } // zakladni vykresleni se provede vzdy for(int y = 0; y < this->bitmap->Height; y++) { for(int x = 0; x < this->bitmap->Width; x++) { new_y = this->searchRedistribution((double)y/(this->bitmap->Height - 1)); if(!this->rejection_method(new_y)) { continue; } new_x = this->searchRedistribution((double)x/(this->bitmap->Width - 1), new_y); if(this->rejection_method(new_x, new_y)) { this->draw(new_x, new_y); } } } \end{lstlisting} \end{document}