The visual arts have undergone a series of gradual changes since their humble beginnings as simple wall drawings and carvings left by the prehistoric humans. Through the course of thousands of years, these primitive forms of art have evolved into the many masterpieces that we know Today, and they keep evolving even now, giving birth to new varieties of artistic styles. Over the last century in particular, there has been an explosion of different artistic styles that are defined by some type of limiting constraint in them, such as employing a reduced subset of colors, the use of characters or shapes arranged in certain patterns, among others. Regardless of whether these works have a deeper meaning to them or not, they possess a unique charm that captures the hearts of those who see them.

This thesis attempts to explore the nature of these types of uniquely constrained artistic styles from a scientific point of view, and to develop image abstraction models that are suitable for reproducing them. Research of this type is important because it allows us to obtain a better understanding of the techniques involved in the creation of a particular style, allowing us to synthesize works that closely resemble them, create new artistic styles by combining ideas and concepts from other ones, improve existing visualization techniques in order to convey visual information in an effective manner, among others.

As the world of artistic drawing styles is very diverse, we focus primarily on the generation of continuous line illustration styles in this thesis. Continuous line illustration is a subcategory of artistic drawing in which art pieces give the illusion of being composed of a single continuous line traced along the canvas, while often portraying complex objects or scenes. These drawings can be occasionally found in many art galleries, and are also frequently seen in the media in the form of advertisements and company logos. Aside from artistic expression purposes, continuous line illustrations also have many real-world applications, such as the creation of quilting designs, steel-wire sculptures, labyrinth patterns, maze design, and connect-the-dots puzzles just to name a few.

Even though such illustrations are based on the simple concept of tracing a single line, the amount of style variations found in these works is surprisingly vast. Depending on the preferences of the artist, continuous line illustrations can vary in expressive nature (the portrayal of the scene through its contours or by approximating its shading) and planarity constraints (the presence of self-intersections or no intersections at all along the line). The portrayal of these properties often involves careful planning of the overall design of the illustration beforehand, in order to preserve the continuous line constraint, while still managing to effectively convey the objects in the drawing.

Previous works in the computer graphics literature focused on the generation of continuous line illustrations that were non-intersecting and shading-based in nature. Although illustrations with high visual quality are achieved through these approaches, the overall strategies employed in these works do not take the edges of the image into account, often resulting in line illustrations whose orientation seems to be mostly random in nature.

In this work, we first explore a series of algorithms for constructing graph structures based on the features of an input image. We are able to compute graphs that are based on either the contours of an input image, as well as grid graphs that are derived from the overall illumination or shading of the image.

Next, we describe methods for computing paths that traverse all over a graph structure while being influenced by the orientation of edges in the image. Our research explores the computation of orientation-aware Eulerian and Hamiltonian-like paths. Paths of the former type traverse through all edges of the graph while considering the orientation of edges adjacent to each graph vertex. Prior to computing the path, a series of edge operations are performed on the graph in order to fulfill the conditions that would allow for such a path to exist, while attempting to avoid the unnecessary retracing of edges and abrupt changes in curvature. The latter type of paths are obtained by means of merging a series of cycles that are grown over a set of specified vertices in a graph, while mostly following a predetermined orientation. We also provide strategies for specifying arbitrary endpoints to the paths obtained with both of these approaches.

The above mentioned techniques are then employed for image abstraction purposes, by modeling the expressive nature of a continuous line illustration as an image-derived graph, and its planarity constraint as a graph traversing path with orientational bias. Our research examines the generation of contour-based self-intersecting continuous line illustrations, as well as the non-intersecting shading-based case, which are arguably the two most commonly found variations of these styles.

We model a contour-based self-intersecting illustration as an orientation-aware Eulerian path computed over a graph derived from a set of image contours. In this way, we can generate line drawings that follow the image edges and whose self-intersections correspond to edge crossings in the image. Moreover, we can control the amount of detail portrayed in the final illustrations by classifying the edges that compose the continuous line into several levels of detail, while still preserving the coherence of the illustration across different levels. On the other hand, a shading-based non-intersecting illustration is modeled as Hamiltonian-like path with orientational bias, which covers a set of specified cells in a precomputed grid graph derived from the overall shading and orientation of edges present in the input image. Several post-processing steps are then applied to the paths in order to improve the quality of the illustration and remove visual artifacts that might be contained within them.

This research attempts to improve the quality of continuous line illustrations produced with the described approaches by providing frameworks for designing these illustrations from a top level perspective. We provide a hierarchical approach for designing contour-based illustrations by assigning a series of child graphs to another graph specified as a parent, and perform a piecewise computation of the illustration per hierarchy level, all the while attempting to preserve the overall coherence of the line drawing across the different levels of the hierarchy. A region-based approach for designing shading-based illustrations is also discussed in this thesis. Users segment an input image into several regions and assign a region type to each of them, directly manipulating the orientation, spacing, and other properties of the illustration on a per-region basis. A variety of visual effects can be applied to illustrations produced by both design methodologies in order to improve their visualization.

Extensions of the proposed techniques for synthesizing other types of abstract art styles are also discussed throughout this thesis.

近年、入力写真を画家の作風に似せたCG作品に変換するノンフォトリアリスティックレンダリングと呼ばれる分野が、広く研究されてきている。本論文は、このノンフォトリアリスティックレンダリングの一種である入力画像から一筆描き線画を生成する手法を開発したもので、「IMAGE ABSTRACTION FOR REPRODUCING ARTISTIC STYLES WITH CONTINUOUS LINE CONSTRAINTS (一筆描き制約を用いた芸術表現再構成のための画像抽象化手法)」と題し、7章からなり、英文で書かれている。

第1章は、「Introduction(序論)」と題され、研究の目的、寄与、本論文の主題である一筆描きの定義、論文の構成などを述べている。

第2章は、「Image-derived Graphs(画像から生成されたグラフ)」と題し、入力画像からの特徴を抽出し、この特徴をベースに、画像処理の技術や計算幾何のアルゴリズムを利用して、グラフ構造を生成する手法を述べている。これらの手法により、輪郭にもとづくグラフ、明るさ情報にもとづく格子グラフが得られる。

第3章は、「Eulerian and Hamiltonian Paths with Directional Bias(方向依存性のあるオイラー経路とハミルトン経路)」と題し、入力グラフからこの上をくまなく通るオイラー経路やハミルトン経路などを得る手法の提案や得られるグラフの分析を記述している。

第4章は、「Automatic Generation of Continuous Line Illustrations Oriented According to Image Features(画像特徴に基づく一筆描き線画の自動生成)」と題し、2章と3章で確立されたアルゴリズムを利用して、画像から実際に、一筆描きスケッチを得られることを示している。また、他の一筆描き手法との比較をユーザースタディも含めて行っている。

第5章は、「Strategies for User-Guided CLI Design Strategies(ユーザーガイドに基づく一筆描き線画生成戦略)」と題し、ユーザーが大まかな構造を与えた上で、この構造を満たすように一筆描きスケッチを得る手法を提案している。

第6章は、「CLI-based Applications and Extensions into Other Artistic Styles(一筆描き線画の応用並びに他の画風への拡張)」は、前章までで得られた一筆描きをもちいてパズルや迷路の設計といった他の分野への応用や一筆描きの領域内を色付けしたり、二値画像化することで異なった作風の絵画を得る手法へと拡張している。

第7章は、「Conclusions(結論)」は、まとめや今後の研究方向について述べている。

以上これを要するに、本論文は、ノンフォトリアリスティックレンダリングの一種である一筆描き線画アルゴリズムに関して、入力画像からをオイラー経路やハミルトン経路を得るアルゴリズム、画像から一筆描き線画を得るアルゴリズム、一筆描き線画に大局的な構造を与えるアルゴリズム、一筆描き線画に色付けを行うアルゴリズムなどを提案したもので、コンピュータ科学、特にコンピュータグラフィックスの分野への寄与が大きい。よって、本論文は、博士(情報理工学)の学位請求論文として合格と認められる。