Article Preview
Top1. Introduction
Continuous line drawing can be described as follows: when drawing a picture, the pen will never leave the paper until the picture is finished. It is sometimes given as a drawing challenge to young children not yet good at holding a pen; even in advanced drawing classes, artists use this technique for sketching practice. This paper considers the problem of creating a final picture that consists of a single non-self-intersecting closed curve. In addition, we want the strokes obtained from the CLD algorithm to present the image content. A CLD abstracted from an input image should preserve the key features of the image, including both tone and edges.
Previously, algorithmic CLD art was created by solving the Traveling Salesman Problem (TSP) (Bosch & Herman, 2004; Kaplan & Bosch, 2005). Given a set of locations, the salesman is required to visit each one, once and only once, before returning to the original location. The graph-theoretic form is, given an undirected graph with weighted edges, find the lowest-cost Hamiltonian cycle: a notorious NP-Complete problem. TSP art involves placing locations over the image plane with density proportional to image darkness, and then finding the Hamiltonian cycle; to improve the appearance of the final image, object boundaries may be selected manually and no nodes placed on the exterior. However, from the view of non-photorealistic rendering (Gooch & Gooch, 2001; Hertzmann, 2010; Strothotte & Schlechtweg, 2002), applying TSP to the CLD produces an overconstrained problem: every TSP tour gives a CLD, but not every CLD is a TSP tour. Some researchers (Pedersen & Singh, 2006; Pullen, 2010; Xu & Kaplan, 2007a, 2007b, in press) created CLDs in the form of mazes, specifically unicursal mazes. Maze creation usually relied on interactive user assistance to have good results.
We argue that TSP-based approaches are too costly and are difficult to modify to effectively demonstrate image features, but we do not want to impose demands on the user and prefer an entirely automatic method. In this paper, we propose a new method for building a CLD in image space by path finding followed by a labeling propagation process. Unlike previous methods that concentrated on tone matching, our method respects the image structure as well. Our approach involves developing a single closed loop from a tree structure; the tree is created by path finding within a structure-aware point distribution. A depth-first traversal of the tree generates a sequence of nodes which we can interpret as a CLD. The awareness of structure is maintained throughout the entire CLD generation process. Figure 1 shows two CLD examples created from images and then rendered as line art (1b) and as Macaroni art (1d).
Figure 1. Abstract CLDs from images: (a) Original image; (b) Continuous line drawing; (c) Original image; (d) Macaroni art
This paper is an extension to an earlier paper about continuous line drawings by Li & Mould (2012). In the new materials of this paper, we also report efforts to design CLDs from scratch without the guide of input images. The new method employs the same procedure: building a tree structure and forming a CLD on the tree. Instead of automatically generating the tree structure and the CLD, the new method relies on user input. It starts by having a user manually construct a branching structure, then automatically dilating the structure, with spatially varying dilation parameters. The final CLD is generated by tracing the boundary of the resulting region. Figure 2 shows a CLD carefully designed to resemble a decorated tree.
Figure 2. Designing CLDs from scratch: (a) Base dendrite; (b) Thickened shape; (c) CLD