Continuous Line Drawings and Designs

Continuous Line Drawings and Designs

Hua Li (Department of Computer Science, University of North Carolina Wilmington, Wilmington, NC, USA & Carleton University, Canada) and David Mould (School of Computer Science, Carleton University, Ottawa, Canada)
DOI: 10.4018/ijcicg.2014070102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Continuous Line Drawing (CLD) is a drawing style where a picture consists of a single closed non-intersecting line. This paper presents an automatic algorithm for constructing CLDs, with tone and structural information obtained from input images. The connectivity of the line is maintained through a tree generated by path finding with consideration of the key features for a given image. A branching tree structure is grown incrementally by selecting pixels by a cost function, relating to both the tone map and an importance map. After labeling each branch, an artificial wall is then constructed through a two-stage labeling propagation process to produce a single boundary, interpreted as the final CLD. The presented CLD method is effective and automatic, and provides some opportunities for variations. The paper also shows how to design CLDs from scratch using three steps: building base structures, forming shapes by thickening, and extracting CLDs by tracing the boundary of the shapes.
Article Preview

1. 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

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing