UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Digital micrography Maharik, Ron Israel 2011

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


ubc_2012_spring_maharik_ron.pdf [ 108.02MB ]
JSON: 1.0052114.json
JSON-LD: 1.0052114+ld.json
RDF/XML (Pretty): 1.0052114.xml
RDF/JSON: 1.0052114+rdf.json
Turtle: 1.0052114+rdf-turtle.txt
N-Triples: 1.0052114+rdf-ntriples.txt
Original Record: 1.0052114 +original-record.json
Full Text

Full Text

Digital Micrography by Ron Israel Maharik B.Sc., Technion { Israel Institute of Technology, 2004 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Computer Science) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) November 2011 c Ron Israel Maharik 2011Abstract This work is concerned with computer-assisted generation of text art. Specif- ically, we consider an artistic style known as micrography, in which complex images are constructed from lines of tiny, readable text. Traditionally cre- ated by trained scribes and requiring immense amounts of e ort, microgra- phy has in recent years crossed over into the digital domain, with modern artists adapting the style in various ways and using it to convey their own message. Unfortunately, creating micrography with standard digital graphic design techniques remains a tedious and frustrating exercise. The method proposed here is capable of automating the work-intensive aspects of micrography, while still keeping the designer in control of the overall look and feel of the result. For artists, this means they can now rapidly experiment with di erent designs in a way that would be infeasible using traditional digital techniques. We begin with an analysis of the aesthetic properties of text  ow that make for a visually appealing micrography. Observing that some of these requirements are shared with well-studied problems in computer graphics such as parameterization and quadrangulation, we base our solution on the popular framework of smooth  elds, augmenting it with a novel approach to boundary constraint design for planar shapes. The result is a system that lets artists generate beautiful micrography in a matter of minutes, automat- ically optimizing for aesthetic appeal and readability while also allowing for intuitive manual intervention. iiPreface The method presented in this thesis was described in the following research paper:  R. Maharik, M. Bessmeltsev, A. She er, A. Shamir, N. Carr. Digital Micrography. In ACM Transactions on Graphics (Proc. SIGGRAPH 2011), July 2011 [28] Figures and text from the publication are copyrighted by ACM (2011) and reused in this thesis by permission. Chapter 8 describes an algorithm developed by Mikhail Bessmeltsev and Prof. Alla She er. The text of the chapter appears in the publication above, and is reproduced here for the sake of completeness. The algorithm in Section 6.3 was developed by Mikhail Bessmeltsev, Alla She er and myself in collaboration. Other ideas in this thesis were  eshed out in discussions with Alla She er, Ariel Shamir at the Interdisciplinary Center Herzliya, and Nathan Carr at Adobe Systems. I carried out most of the background literature survey and all experiments and development. iiiTable of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Text Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Layout Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Smooth Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Text Layout Design . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Aesthetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Alignment . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.2 Shading and Spacing . . . . . . . . . . . . . . . . . . 16 3.1.3 Bounded Curvature . . . . . . . . . . . . . . . . . . . 17 3.1.4 Distinction . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Readability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 Curvature . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 Line Length and Word Breakup . . . . . . . . . . . . 20 3.2.3 Coherence and Line Ordering . . . . . . . . . . . . . 20 3.2.4 Line Spacing . . . . . . . . . . . . . . . . . . . . . . . 21 ivTable of Contents 4 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.1.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.1.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . 22 4.1.3 Smooth Field Design . . . . . . . . . . . . . . . . . . 22 4.1.4 Streamline Tracing and Ordering . . . . . . . . . . . 24 4.1.5 Text Placement . . . . . . . . . . . . . . . . . . . . . 24 4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.1 Con guration File . . . . . . . . . . . . . . . . . . . . 25 4.2.2 Dependencies . . . . . . . . . . . . . . . . . . . . . . 26 4.2.3 Performance . . . . . . . . . . . . . . . . . . . . . . . 26 5 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1 Image Preprocessing . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Text Preprocessing . . . . . . . . . . . . . . . . . . . . . . . 30 6 Smooth Field Design . . . . . . . . . . . . . . . . . . . . . . . . 32 6.1 Field Design Primer . . . . . . . . . . . . . . . . . . . . . . . 32 6.2 Field Design for Text Layout . . . . . . . . . . . . . . . . . . 35 6.3 Boundary Condition Design . . . . . . . . . . . . . . . . . . 39 6.3.1 Pairwise Preference Weights . . . . . . . . . . . . . . 42 6.3.2 Individual Preference Weights . . . . . . . . . . . . . 43 6.3.3 Completing the Formulation . . . . . . . . . . . . . . 44 6.3.4 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4 Computing the Field . . . . . . . . . . . . . . . . . . . . . . 47 6.5 User Control . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.6 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7 Line Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.1 Goals and Requirements . . . . . . . . . . . . . . . . . . . . 52 7.2 Tracing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 53 7.3 Deviations from the Field . . . . . . . . . . . . . . . . . . . . 55 7.4 Spacing and Enrichment . . . . . . . . . . . . . . . . . . . . 56 8 Line Orientation and Ordering . . . . . . . . . . . . . . . . . 59 8.1 Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 8.2 Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 vTable of Contents 9 Rendering Text . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 9.1 Typesetting . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 9.2 Text Warping . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 10.1 Running Times . . . . . . . . . . . . . . . . . . . . . . . . . . 75 11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 12 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 viList of Tables 10.1 Run time breakdown . . . . . . . . . . . . . . . . . . . . . . . 80 viiList of Figures 1.1 Hand-drawn micrography (1) . . . . . . . . . . . . . . . . . 2 1.2 Hand-drawn micrography (2) . . . . . . . . . . . . . . . . . 3 2.1 Path-based text art . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Grid-aligned digital text art . . . . . . . . . . . . . . . . . . 8 2.3 Other digital text art . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Flow visualization using streamlines . . . . . . . . . . . . . 11 2.5 Field-guided mosaic pattern . . . . . . . . . . . . . . . . . . 13 3.1 Boundary-aligned vs. unaligned layout . . . . . . . . . . . . 16 3.2 Region distinction . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Region distinction: hand-drawn example . . . . . . . . . . . 19 3.4 Coherent vs. incoherent layout . . . . . . . . . . . . . . . . 21 4.1 Algorithm overview . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 User interface . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.1 Planar map . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Image preprocessing . . . . . . . . . . . . . . . . . . . . . . 29 6.1 Smooth  eld types . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Singularities and text layout . . . . . . . . . . . . . . . . . . 34 6.3 Full boundary alignment . . . . . . . . . . . . . . . . . . . . 36 6.4 Narrow regions . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Partial boundary alignment . . . . . . . . . . . . . . . . . . 38 6.6 Pairwise alignment preferences . . . . . . . . . . . . . . . . 40 6.7 Narrow features . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.8 Boundary condition formulation . . . . . . . . . . . . . . . . 41 6.9 Feature size estimation . . . . . . . . . . . . . . . . . . . . . 43 6.10 Boundary condition solution . . . . . . . . . . . . . . . . . . 45 6.11 Boundary solver procedure . . . . . . . . . . . . . . . . . . . 46 6.12 Alignment/coherence trade-o . . . . . . . . . . . . . . . . . 49 viiiList of Figures 6.13 Forcing symmetry . . . . . . . . . . . . . . . . . . . . . . . . 51 7.1 Greedy tracing algorithm . . . . . . . . . . . . . . . . . . . 54 7.2 Elements of our tracing method . . . . . . . . . . . . . . . . 57 8.1 Orientation and ordering formulation . . . . . . . . . . . . . 60 9.1 Text warping example . . . . . . . . . . . . . . . . . . . . . 64 9.2 Line end warping . . . . . . . . . . . . . . . . . . . . . . . . 66 10.1 Microgram: \Motif" . . . . . . . . . . . . . . . . . . . . . . 68 10.2 Microgram: \Summer Girl" . . . . . . . . . . . . . . . . . . 70 10.3 Microgram: \In Flanders Fields" . . . . . . . . . . . . . . . 71 10.4 Microgram: \Mona Lisa" . . . . . . . . . . . . . . . . . . . 72 10.5 Microgram: \Light and Shadow" . . . . . . . . . . . . . . . 73 10.6 Microgram: \Fedora" . . . . . . . . . . . . . . . . . . . . . . 74 10.7 Microgram: \Dark Eyes" . . . . . . . . . . . . . . . . . . . . 75 10.8 Two cats: comparison with Li et al. . . . . . . . . . . . . . 76 10.9 Variations: text length . . . . . . . . . . . . . . . . . . . . . 77 10.10 Variations: typeface and colour . . . . . . . . . . . . . . . . 78 10.11 Field design with user constraints . . . . . . . . . . . . . . . 79 ixAcknowledgements I owe a debt of gratitude to my supervisor, Prof. Alla She er, for teaching me how to look critically at images and how to undertake research work in computer graphics. Her drive, and her endless  ow of ideas, helped shape this work at every turn. I am further grateful to the rest of the project team: Prof. Ariel Shamir, Nathan Carr, and Mikhail Bessmeltsev, all of whom were deeply involved and invested in this work and helped make it what it is. Many thanks also to my second reader Prof. Tamara Munzner for her valuable feedback on this manuscript. I am indebted to everyone at Adobe’s Advanced Technology Labs for hosting me in San Jose, for their enthusiasm about this work and for pro- viding the resources and know-how that made it possible. It was an honor to be part of your team. Thanks also to the Canadian agencies that funded my work: the Natural Sciences and Engineering Research Council of Canada, GRAND NCE, and MITACS/Mprime Network. Many thanks to all the artists whose creations are used here, either as source material or as a source of inspiration. I am ever grateful to my parents and grandparents, my siblings, and the extended family in Israel for their love and support, and to Dana, my partner in this adventure and all others. Finally, I am thankful to everyone who shared their wisdom and ex- perience with me over the past two years, o ered words of encouragement and kindness, and provided some much-needed balance: my colleagues and friends in Imager, CS department faculty and sta , the CSGSA, and all my friends in Vancouver. Thank you for being part of this amazing experience. Ron Maharik The University of British Columbia November 2011 xChapter 1 Introduction This work is concerned with text art. The idea of using the form and ar- rangement of letters and words to convey an artistic message is perhaps as old as written language itself. Calligraphy, literally \beautiful writing", has been in practice in Asia for thousands of years [52]. According to British book designer Thomas James Cobden-Sanderson, \The whole duty of Ty- pography, as of Calligraphy, is to communicate to the imagination, without loss by the way, the thought or image intended to be communicated by the Author". A calligram is a speci c form of text art whereby words or letters are arranged so as to create a visual image. Calligrams enjoy a rich tradition and come in a wide variety of styles, limited only by the artist’s imagina- tion. In this work we focus on a genre of calligram known alternatively as micrography or microcalligraphy. Practised by Jewish artists since the Middle Ages [7], micrography utilizes minute letters to provide a unique in- terplay between textual content and image { presenting a story or poem at the small scale, while forming an image when viewed as a whole. This gap in scale between lettering and image is a de ning characteristic of micrographic works, or micrograms, distinguishing them from other types of calligram. Despite the small scale of the lettering, micrography places much empha- sis on readability. Not only should individual letters be neat and legible, but the text as a whole must be arranged in a way that allows readers to easily follow its progression. Thus a close correspondence is established between the microgram and its source text { a correspondence that plays a crucial part in the artistic appeal of the work, even for observers who would not follow the text from start to  nish. This is especially true when the text is a recognizable piece such as scripture or a popular poem. Di erent styles exist in traditional micrography, ranging from simple ornamentation to fully painted scenes with colour and shading e ects. A common theme in all styles is the treatment of individual text lines as brush or pencil strokes. Hence, classic illustration techniques such as line-art or hatching can be applied in the creation of micrography, and aesthetic con- ventions that govern illustration apply to micrograms as well. First and 1Chapter 1. Introduction Figure 1.1: Examples of hand-drawn micrography, by (clockwise from top left) G. Apollinaire, G. Klopstock (gilklop.co.il/apage/35286.php), and J. Sibal (jonsibal.com). Used with permission. 2Chapter 1. Introduction Figure 1.2: Modern example of hand-drawn micrography. Even this rel- atively rough design required three hours of work to complete. Image by lovelymetalhead.deviantart.com. Used with permission. foremost among these is the practice of aligning strokes with boundaries and other salient features. The three hand-drawn examples in Figure 1.1 demon- strate e ective use of text lines as strokes to convey shape and structure. Wonderful examples of micrography have been created by artists over the centuries ([3, 7]), and contemporary artists are continuing this tradi- tion today ([50]). However, the popularity of micrography has always been limited by the sheer amount of e ort required to create a single work. Tra- ditional artists, working without the bene t of digital tools, must legibly scribe every letter at the desired minuscule resolution { a process that can take weeks to complete and leaves little room for error or for experimen- tation with di erent designs. An artist will generally use a combination of rough underlying sketch and guiding lines to design the layout, then  ll in the lettering. With the advent of digital creative software, the barriers for practitioners of micrography are lower than in the past. Digital artists have in recent years adopted the form and are rapidly expanding its frontier { developing new 3Chapter 1. Introduction styles, importing nontraditional source material, and using the medium to promote commercial products or political movements [50]. However, even with digital graphic design tools, microgram creation remains a very tedious process. To produce an appealing design the artist must manually lay out and stylize individual sentences, words, even speci c letters. As a result, many designs are either limited in size or rely on very simple text  ow patterns, such as all-horizontal layout (Figure 3.1 left). In this work we present a method for creating digital micrograms starting from a given text and an appropriate vector-graphics image. Our goal is to automate the highly technical and time-consuming aspects of microgram creation, while providing high level tools for user control. This frees the artist to e ciently experiment with multiple designs and settings to achieve the intended result. The micrograms created using our system are easy to read, e ectively convey the input image, and are visually appealing. Not every image is suitable for creating micrography. Micrograms usu- ally consist of several contiguous regions of text conveying large image com- ponents, as well as individual text lines representing isolated line art. Some works also contain non-textual elements (Figure 1.1, top right) enhancing the visual appeal of the image. Hence, the natural input to our system is vector graphics images, where such regions and lines are well-de ned. More com- plex images can be simpli ed and converted to vector representation using standard tools, e.g. Adobe Illustrator [1]. In this work we deal exclusively with vector representations, which are practically resolution independent. Reproducing such vector art on physical media is a separate topic with its own literature [25, 33, 41]. In approaching the problem, we begin by observing that the primary challenge of micrography lies in designing a suitable text layout { an ar- rangement of paths along which the text will be placed. We examine the criteria for a good layout, taking into account aesthetic and readability re- quirements. Next, we show how to construct text layouts over a set of closed regions using smooth  elds, a mathematical tool that has been applied ex- tensively and successfully in recent years to a variety of related problems. Given a suitable  eld per region, we use a custom algorithm to trace streamlines through the regions and obtain a set of paths for text placement. We then compute an ordering of these streamlines, optimizing for natural line-to-line progression. Finally, we render text along the ordered set of streamlines, adaptively scaling and warping as necessary to form clearly delineated, evenly shaded regions. Our system can provide a fully automatic solution for a given input text and vector image. For greater expressiveness, it also provides a user interface 4Chapter 1. Introduction giving artists more control over the layout. This includes local directional preferences, font face and size customization, and additional controls over various artistic e ects. By implementing the system as a plug-in for Adobe Illustrator we provide artists with a full-featured graphic design tool for creating intricate, appealing digital micrography. 5Chapter 2 Related Work 2.1 Text Art The visual appeal of artistic expression using text, as well as its labour- intensive nature, are widely recognized. Technologies for placing text along user-speci ed trajectories have been well explored and are a key component of several commercial design tools such as Adobe Illustrator [1]. These packages usually deal with text on a line-by-line basis: The user speci es the text to be placed, designs a path for the text to follow, and may include additional deformation attributes. Illustrator implements a modi ed version of the Skeletal Strokes ap- proach proposed by Hsu et al. [21]. A skeletal stroke is an image de ned in relation to a reference line (the skeleton) and a reference width. When the skeleton is deformed, the image deforms accordingly in an intuitive man- ner. The original method supports a variety of deformation options, which Illustrator augments with locally-de ned width pro les and folding avoid- ance [6]. Text Sculpting [44, 47] provides a further degree of freedom in deforma- tion by replacing the skeleton with a parametric surface S(u; v), construct- ing the layout as a symbolic combination of this surface and the given text string, which is represented as a set of B ezier curves. Text sculpting also adds explicit support for animation. Example designs using skeletal strokes and text sculpting are shown in Figure 2.1. While our method uses skeletal strokes as a building block, single-line text placement alone is not su cient for creating sophisticated micrography. Specifying dozens and often hundreds of lines to convey a complex image would still be a daunting task, and exploration of the design space essentially requires repeating the entire exercise from scratch. Another group of text art methods focuses on generating speci c forms of text art on a larger scale. Xu et al. [59] show how to create structure- based ASCII art by optimizing a specially designed shape similarity metric. ASCII art aims to approximate a given shape using a limited set of symbols under rigid rules for alignment and position, but it does not attempt to 62.1. Text Art Figure 2.1: Path-based text art. Top: adaptive width pro les using Adobe Illustrator CS5. Bottom: adaptive deformation with SculpText. place meaningful text in a legible form. The calligraphic packing work of Xu and Kaplan [56] packs and warps a word or short phrase to  t a given shape. The resulting macroscopic calligrams are certainly engaging, but the technique relies heavily on individual letter arrangement by the user, and therefore does not scale well to the case of micrography. A number of software packages such as Textorizer [16] and Textaizer [4] produce readable text in the form of grid-aligned text-mosaics (Figure 2.2). This approach lacks an explicit notion of shape, relying only on local colour and shading to depict the given image. In contrast, micrography draws from a much broader artistic palette, using shape at both the macro image-level and the micro font-level. Our system aims at delivering this greater degree of freedom. Textorizer can also generate images using a stippling technique with a given set of words as brush strokes (Figure 2.3), but this method does not produce readable text passages. Finally, tag clouds such as those generated by Wordle ([14], Figure 2.3) 72.1. Text Art Figure 2.2: Examples of grid-aligned digital text art tools. Top: Textorizer mode 2. Bottom: Textaizer. 82.1. Text Art Figure 2.3: Examples of digital text art tools. Top: Textorizer mode 1. Bottom: Wordle. 92.2. Layout Tasks are mosaic structures created from a given list of words, with the font size of a word often determined by some measure of importance. There is no coherent sentence structure, and typically these images do not adhere to any recognizable shape { hence the cloud metaphor. 2.2 Layout Tasks Our goal of placing text inside a set of regions is related to a number of well- studied problems that can be loosely grouped as layout tasks. These include space- lling curves,  eld visualization using streamlines, maze generation, ornamental patterns, and hatching. The criteria for designing ornamental patterns, as described by Wong et al. [55], are quite similar to those for laying out text. A given shape boundary must be adhered to, and there is often the expectation of a deeper interplay between the  ll and the boundary, such as tracking a medial representation of the shape. The given space should be  lled in a balanced manner with uniform density, while also preserving the aesthetic qualities and topologi- cal characteristics of the pattern used for the  ll. Wong et al. propose a greedy layout method that  nds large regions of empty space and  lls them  rst, then gradually expands to  ll gaps of diminishing size. Although this approach can successfully mimic natural plant growth patterns in certain cases, its applicability to other pattern types is limited. Their work also lacks support for a global layout strategy, as they point out in their future work section. Our work introduces such a global strategy in the context of text layout. Computer generated mazes and labyrinths pack evenly-spaced paths into a given region. Pedersen and Singh [35] evolve their \organic" mazes from basic user-de ned curves using a biologically inspired iterative algorithm. Xu and Kaplan [57] combine the organic approach with other maze types such as spiral and directional mazes. Both methods segment the underlying input into regions and use di erences in pattern to make these regions dis- tinct. Our system achieves a similar distinction e ect through the use of text directions and font characteristics. A key di erence in design goal between maze art and micrography is that maze generators actually encourage the resulting paths to wind and bend to increase the complexity of the maze. In contrast we are interested in generating coherent, readable  ows, and work to minimize path curvature where possible. Hatching and other non-photorealistic rendering methods use strokes to convey the shape of an input model, typically a manifold surface in 3D. 102.2. Layout Tasks Figure 2.4: Example of  ow visualization with evenly-spaced streamlines. Original image by Crowsnest at en.wikipedia. Praun et al. [36] support arbitrary hatching styles in real time by pre- rendering a set of textures corresponding to di erent shades. To orient the strokes they rely on either a surface parameterization, a user-guided direc- tion  eld, or principal curvature directions. Surazhsky and Elber [45] take this idea a step closer to our goal by replacing hatching strokes with lines of text. Speci cally, they generalize the Text Sculpting method (Section 2.1) to B-spline surfaces in 3D space and multiple text lines. The result, while quite appealing, is not equivalent to 2D micrography and does not ful ll the readability requirement. From any single point of view some areas will con- tain easily readable text, but other portions are either  ipped, excessively sheared, or occluded entirely. Their result is also highly dependent on sur- face parameterization, whose de nition is external to their layout algorithm. A  nal technique in this discussion is  ow visualization with evenly- spaced streamlines. A streamline is a curve that is tangential to an un- derlying  ow  eld at every point. Streamlines provide a natural way to visualize  ow patterns in two or three dimensions. As an example, Fig- ure 2.4 demonstrates the use of streamlines to visualize air  ow around the wing of an aircraft. Two primary considerations in 2D streamline visualiza- tion are: avoidance of short lines where possible, and maintaining relatively uniform line density throughout the region of interest (equivalently, main- tain roughly even spacing between adjacent lines) [30]. Note the similarities to our goal of  lling a region with lines of text { this motivates our use of streamline placement as a proxy during the text layout process. Turk and Banks [49] proposed an image-guided technique that produces pleasing streamline patterns, but their iterative optimization approach was not fast 112.3. Smooth Fields enough for many applications. Jobard and Lefer [23] introduced an e - cient greedy streamline-tracing method with comparable results. Mebarki et al. [31] developed an alternative greedy strategy that generates longer lines on average while maintaining uniform spacing. Our system builds on the method of Jobard and Lefer, adapting it in several ways to optimize the results for text placement. 2.3 Smooth Fields The use of smooth  elds as a design tool has exploded in recent years, thanks to improved computational methods and a number of novel applications. A brief introduction to  elds in the context of geometry processing is given in Section 6.1. Xu et al. [58] use a vector  eld to synthesize anisotropic textures on manifolds in a manner that respects feature lines and user constraints. They argue that aligning with salient features causes the texture to reinforce the underlying structure, rather than being at odds with it. The same ar- gument motivates our approach to  eld-guided layout of text. Li et al. [26] successfully combine vector or tensor  elds with shape grammars to syn- thesize geometry on manifolds. They also demonstrate anisotropic mosaic generation in 2D, guided by a tensor  eld which they align with manually selected directions approximating an image gradient (Figure 2.5). Two closely related applications that often rely on smooth  elds are uv parameterization and quadrangulation. Ray et al. [37] use two orthogonal vector  elds, typically derived from principal curvature directions, to con- struct globally smooth parameterizations of triangle meshes. Bommes et al. [8] compute a parameterization based on a smooth feature-aligned cross-  eld. They employ a mixed-integer solver to constrain all singular points to lie at integer locations, which allows for straightforward conversion of the resulting parameterization into a coarse all-quad mesh. The maze-art method of Xu and Kaplan [57] and hatching algorithm of Praun et al. [36], both of which were discussed in Section 2.2, also use smooth  elds to guide  ow and improve alignment with region boundaries or feature lines. Field design is the process of constructing a smooth  eld suitable for a particular application. A number of design schemes have been proposed, most of which fall into one of two categories: topological or geometric [38]. Topological methods are concerned primarily with singular points in the  eld { where to place them, what types are allowed, and how to reduce their occurrence, since singularities almost always give rise to undesirable 122.3. Smooth Fields Figure 2.5: Field-guided mosaic pattern by Li et al. [26]. The  eld is man- ually aligned with salient edges in the image. Reprinted with permission of IEEE. artifacts. Geometric methods, on the other hand, focus on relating the  eld to the shape over which it is de ned. Ray et al. [39] and Crane et al. [12] take the topological route, con- structing smooth direction  elds given a user-de ned set of singularities. This approach can generate  elds with the absolute minimum number of singularities, but often at the cost of increased  eld curvature. In contrast, Fisher et al. [15] and Bommes et al. [8] start with a set of user-de ned local directional constraints, and let the singularities arise auto- matically. Fisher et al. use weighted least squares to minimize a quadratic energy function that accounts for smoothness as well as user constraints, while Bommes et al. develop a mixed integer problem that interpolates user-de ned directions while maximizing smoothness. Finally, Ray et al. [38] propose a geometric method based on a novel direction  eld formulation that lets the user adjust the trade-o between curvature (smoothness) and singularity count. The fact that curvature, singularities, and feature alignment are at odds with each other, and must be balanced according to the needs of the application, will be at the heart of our discussion of  eld design in Chapter 6. 132.3. Smooth Fields An aspect of these works that is of particular interest to us is their treat- ment of boundaries. Three popular approaches for incorporating boundaries into the  eld design process are to leave them unconstrained (free), treat them as feature lines, or manually assign directions along the boundary according to some external criterion. In applications that focus on manifold surfaces in 3D, boundaries in non-closed manifolds have both topological and geometric implications. The topological method of Crane et al. accounts for boundaries by modifying the algorithm to produce a free-boundary e ect, which they refer to as \natural boundary behaviour". An alternative solution is mentioned which increases the turning number of the  eld along the boundary, but that approach is not motivated or demonstrated. Ray et al. [39] rely heavily on boundaries in their topological analysis of N-symmetry direction  elds: they analyze the behaviour at singular points by modelling them as in nitesimal \holes" surrounded by boundaries. Actual boundaries in open manifolds are han- dled by temporarily patching the holes and constraining the turning number along the boundary similarly to Crane, with similar results. The method of Fisher et al. supports either free boundaries or arbitrary user-de ned directions. All of the above also applies in the special case of planar shapes in 2D. Yet here boundaries play a key role, whereas in many 3D applications they are almost an afterthought. This is because boundaries in 2D are often the most prominent or even sole existing type of salient feature. One consequence is that default approaches to dealing with boundaries { treat all as feature lines or leave all unconstrained { often fail to achieve the desired result, forcing users to intervene manually in boundary condition design. In this thesis we present a principled approach to boundary design for smooth  elds in 2D. While our method is carefully optimized for the purpose of text layout, the underlying principles can be generalized to other anisotropic layout scenarios, enabling automatic generation of results that would otherwise require signi cant manual e ort. 14Chapter 3 Text Layout Design In this chapter we establish the characteristics of e ective text layout for micrography. Layout is the primary device for conveying the structure and aesthetics of the source image in works of micrography [7]. This is especially true for works rendered in black-and-white { a common practice in traditional as well as modern pieces { but holds true in the presence of colour or tone as well. In micrographic depiction of a given image, text lines are used in the manner of brush strokes, hatching strokes, or lines in sketching or painting. In Section 2.1 we discussed text-art styles in which layout plays no part in image depiction, but such works are normally not considered examples of micrography. In addition to its contribution to image depiction, layout plays a key role in making a microgram readable. Although some readability choices are independent of layout (e.g. font face), a readable microgram cannot be produced given a bad layout. We therefore see text layout as the main challenge in computer-generated micrography. The dual nature of micrograms dictates that our layout must satisfy aesthetic and image recognition requirements on the one hand, and text readability on the other. This set of requirements can often be contra- dictory, and consists of global as well as local considerations. The remainder of this chapter investigates each requirement in more detail. 3.1 Aesthetics 3.1.1 Alignment To properly depict boundaries and other salient curves in the given image, text  ow should align with these curves when possible. That is, the text line immediately adjacent to the curve should ideally run parallel to the curve at every point. This is an almost universal convention in sketching and paint- ing, and is consistent with the manner in which the human visual system perceives edges in a scene [10]. Figure 3.1 compares a simple all-horizontal 153.1. Aesthetics L O R E M   I P S U M   D O L O R   S I T   A M E T ,  C O N S E C T E T U R   A D I P I S I C I N G   E L I T ,  S E D   D O   E I U S M O D   T E M P O R   I N C I D I D U N T   U T   L A B O R E   E T   D O L O R E   M A G N A   A L I Q U A .   U T   E N I M   A D   M I N I M   V E N I A M ,  Q U I S   N O S T R U D   E X E R C I T A T I O N   U L L A M C O   L A B O R I S   N I S I   U T   A L I Q U I P   E X   E A   C O M M O D O   C O N S E Q U A T .   D U I S   A U T E   I R U R E   D O L O R   I N   R E P R E H E N D E R I T   I N   V O L U P T A T E   V E L I T   E S S E   C I L L U M   D O L O R E   E U   F U G I A T   N U L L A   P A R I A T U R .   E X C E P T E U R   S I N T   O C C A E C A T   C U P I D A T A T   N O N   P R O I D E N T ,  S U N T   I N   C U L P A   Q U I   O F F I C I A   D E S E R U N T   M O L L I T   A N I M   I D   E S T   L A B O R U M .   S E D   U T   P E R S P I C I A T I S   U N D E   O M N I S   I S T E   N A T U S   E R R O R   S I T   V O L U P T A T E M   A C C U S A N T I U M   D O L O R E M Q U E   L A U D A N T I U M ,  T O T A M   R E M   A P E R I A M ,  E A Q U E   I P S A   Q U A E   A B   I L L O   I N V E N T O R E   V E R I T A T I S   E T   Q U A S I   A R C H I T E C T O   B E A T A E   V I T A E   D I C T A   S U N T   E X P L I C A B O .   N E M O   E N I M   I P S A M   V O L U P T A T E M   Q U I A   V O L U P T A S   S I T   A S P E R N A T U R   A U T   O D I T   A U T   F U G I T ,  S E D   Q U I A   C O N S E Q U U N T U R   M A G N I   D O L O R E S   E O S   Q U I   R A T I O N E   V O L U P T A T E M   S E Q U I   N E S C I U N T .   N E Q U E   P O R R O   Q U I S Q U A M   E S T ,  Q U I   D O L O R E M   I P S U M   Q U I A   D O L O R   S I T   A M E T ,  C O N S E C T E T U R ,  A D I P I S C I   V E L I T ,  S E D   Q U I A   N O N   N U M Q U A M   E I U S   M O D I   T E M P O R A   I N C I D U N T   U T   L A B O R E   E T   D O L O R E   M A G N A M   A L I Q U A M   Q U A E R A T   V O L U P T A T E M .   U T   E N I M   A D   M I N I M A   V E N I A M ,  Q U I S   N O S T R U M   E X E R C I T A T I O N E M   U L L A M   C O R P O R I S   S U S C I P I T   L A B O R I O S A M ,  N I S I   U T   A L I Q U I D   E X   E A   C O M M O D I   C O N S E Q U A T U R ?   Q U I S   A U T E M   V E L   E U M   I U R E   R E P R E H E N D E R I T   Q U I   I N   E A   V O L U P T A T E   V E L I T   E S S E   Q U A M   N I H I L   M O L E S T I A E   C O N S E Q U A T U R ,  V E L   I L L U M   Q U I   D O L O R E M   E U M   F U G I A T   Q U O   V O L U P T A S   N U L L A   P A R I A T U R ?  Figure 3.1: The all-horizontal con guration on the left does not depict the shape well, su ers from jagged aliasing artifacts, and creates very short lines in thin features. the layout on the left is aligned with shape boundaries and better conveys the shape, also avoiding short lines and aliasing. Reprinted with permission of ACM. layout, which does not follow the convention (left), with a layout that does (right). The former su ers from jagged aliasing artifacts, and is at odds with the natural  ow directions of the shape. The latter produces a more appealing, natural-looking microgram. If we focus on the all-horizontal re- sult on the left, we can make another observation: from a shape depiction point of view, text  ow perpendicular to the curve is an adequate substi- tute for aligned  ow. Aliasing artifacts are most evident when the angle between boundary and text is small, and they gradually diminish as the angle approaches 90 degrees. 3.1.2 Shading and Spacing Evenly shaded regions are common in source images used in micrography (Chapter 1). Text layout in uences how such regions will be perceived by an observer. The simplest and most common method for even shading with text is to generate text lines at roughly even baseline-to-baseline spacing, then use a constant font size throughout the region (perhaps with minor local adaptations) to achieve a uniform look. The font size is generally set so that 163.2. Readability leftover space between lines is kept to a minimum, although retaining a bit of space can improve readability [54]. In modern works artists sometimes add an element of texture by varying the text size within a region. This approach was used to great e ect for rendering the hair in Figure 1.1 (bottom). 3.1.3 Bounded Curvature Aesthetic as well as readability considerations dictate that excessive bending along any given text line should be avoided. On the aesthetic side, humans are not accustomed to viewing sharply curving text lines, and may  nd such designs uncomfortable or distracting. Another consideration is visual compatibility with brush strokes and hatching strokes, both of which rarely exhibit high curvature. 3.1.4 Distinction A boundary between adjacent regions presents a potential problem when constructing images from lines of text. Proper image depiction requires that the boundary be easily discernible in the resulting microgram. However, if we follow the alignment convention discussed in Section 3.1.1 then the text would  ow in the same direction on either side of the boundary, obscuring the boundary (Figure 3.2 middle). Variations in colour or tone between the two regions will solve the problem, as will di erences in font face, size or density. Another approach, popular in micrography, is to create distinction using text directions: rather than aligning with the boundary, the text  ow on one side is designed to approach the boundary at an angle (Figure 3.2 bottom). This layout-based solution for region distinction can be seen in the handcrafted image in Figure 3.3, which also demonstrates another similar technique: trace one or two text lines along the boundary, and have the text  ow toward the boundary at an angle on either side. 3.2 Readability 3.2.1 Curvature Human observers are accustomed to reading text laid out in straight lines { be they left-to-right, right-to-left, or top-to-bottom depending on language. Although creators of text art are allowed to deviate from this principle, excessive bending (high curvature) makes the text di cult to follow, and the problem is exacerbated in extreme cases by deformation of the individual 173.2. Readability Figure 3.2: Two regions separated by a thin boundary (top). If the text is aligned on both sides, the boundary may be di cult to distinguish (mid- dle). Distinction is improved by enforcing di ering text directions across the boundary (bottom). 183.2. Readability Figure 3.3: In this work, region distinction is achieved via a combination of techniques: di erences in orientation, varying text density, and explicit demarcation using isolated lines. Portrait by L. Rotblat, 1897 193.2. Readability letters [6, 44]. Lines that wind and bend steeply are also di cult to assemble into coherent text passages (Section 3.2.3). Note that when discussing the curvature of text lines, we should scale our measurements by the font size in use. A path suitable for rendering tiny 6-point text may be completely inadequate for 36-point headlines. 3.2.2 Line Length and Word Breakup Passages constructed from short fragments of text are di cult to read, since the reader is forced to skip frequently between di erent parts of the page. We therefore seek to eliminate short fragments. Beyond that, there is no requirement to maximize line lengths. As in general typography, breaking up a word across multiple lines is undesirable but not necessarily forbidden. Di erent artists take di erent approaches to this matter. Note that extremely short lines might not be able to contain even a single word, which is another reason to avoid them in our layout. 3.2.3 Coherence and Line Ordering While curvature and line length characterize individual text lines, the con- cept of coherence applies to the arrangement of multiple lines that forms the complete image. Readers must be able to follow text progression in a smooth and natural manner, and to facilitate this an ideal layout would again adhere to standard typographic convention: regions of evenly-spaced lines, with roughly aligned start and end points within each region. This ideal is often not achievable in micrography, but some layouts approximate it better than others. In  gure 3.4, the layout on the left is highly inco- herent, while the one on the right is not far removed from typical creative graphic designs (e.g. printed advertisements). The other piece needed for natural text progression is a full ordering of lines within a given region, and also between di erent regions, in a manner that matches reader expectations. The reader should be able to accurately predict, given the location of one text line, where to search for the next line in the chain. In the absence of coherent layout this is generally impossible to achieve (Figure 3.4 left), but even with coherent layout the ordering may be ambiguous (Figure 3.4 right). 203.2. Readability Figure 3.4: Given an incoherent layout (left), it is usually impossible to follow the text in a natural progression. Even with coherent layout (right), determining a natural full ordering among text lines can be far from trivial. Our layout (right) selectively relaxes the alignment requirement to provide both a readable text and a visually appealing representation of the input image. Reprinted with permission of ACM. 3.2.4 Line Spacing As mentioned in Section 3.1.2, interline spacing in micrography is generally kept to a minimum, but some spacing often remains in the interest of read- ability. At the very least, overlaps between adjacent lines must be carefully avoided. When using Latin script this task is complicated by variability in the vertical span of letters due to the presence of ascenders and descenders. We have observed that many artists circumvent this issue by designing their art using all caps (Figure 1.1 bottom). One could argue that line spacing is unrelated to layout, since letters could always be scaled uniformly and/or vertically to alter the amount of leftover space. However, vertical scaling introduces distortion, and uniform scaling changes the amount of text that will  t in a given region and in the image as a whole. Line spacing therefore becomes a factor in the complex planning task that is text layout for micrography. 21Chapter 4 System Overview 4.1 Algorithm 4.1.1 Input The input to the algorithm consists of a vector graphics image, the text from which the microgram is to be constructed, and optional con guration infor- mation. The input image contains some combination of three component types: regions to be  lled with text, individual strokes to be used directly as text paths (see Figure 10.6), and additional graphical elements which are left untouched by the system (Figure 10.2). Con guration data consists of global settings, adjustments to region-speci c properties such as font face and size, and/or local alignment preferences enabling the user to in uence the resulting text layout. 4.1.2 Preprocessing Since the input is a vector image, very limited processing is needed to ex- tract regions and curves. Region boundaries are uniformly sampled, approx- imated by a polygon, and then triangulated, in preparation for smooth  eld computation in the following stage. An estimated font size per region is also computed at this time based on region areas, length of the input text, and user preferences. See Chapter 5 for details. 4.1.3 Smooth Field Design Our primary machinery for designing text layouts is a smooth  eld computed per region. The  eld is constrained to align locally with parts of the region boundary. This partial alignment is carefully designed to balance align- ment requirements against other aesthetic and readability considerations including smoothness, coherence, and text line length. To determine which parts of the boundary should be aligned we could make use of outlier-robust optimization techniques, which allow one to balance a set of constraints, se- lectively relaxing ones that are hard to satisfy. However, such methods are 224.1. Algorithm (a) (b) (c) (d) (e) Figure 4.1: Overview of our text layout method. Given the input image (a), we  rst compute suitable boundary conditions for a desired smooth  eld, ex- pressed via region boundary alignment constraints (b), where green denotes an requirement for alignment and red denotes a free boundary. We then calculate a smooth  eld (c) satisfying these boundary conditions. Next, we trace a set of streamlines, orient and order them, with blue-to-red colouring visualizing line order inside each region (d). Finally, we render a line of text along each streamline (e). Reprinted with permission of ACM. 234.2. Implementation typically numerically expensive and would require solving a large non-linear system throughout each region. Instead, we separate the problem into two phases:  rst, we partition the sampled boundary into aligned and unaligned portions. This is done by modelling the problem as a graph-cut and solving using a stochastic quadratic programming search algorithm (Section 6.3). We then construct a smooth 2-rotational symmetry  eld (Section 6.4) per region given these boundary conditions. The  elds are de ned over the vertices of the triangulation computed in the preprocessing stage. 4.1.4 Streamline Tracing and Ordering To construct the layout, we trace a set of streamlines through the smooth  eld using a custom tracing mechanism which aims to avoid short lines, op- timize interline spacing, and place endpoints coherently (Chapter 7). The streamlines are smoothed in a post-processing step to further improve spac- ing and coherence. In order for readers to easily follow the text’s progression, we determine a consistent orientation among the set of streamlines and com- pute a traversal order conforming to typographic conventions (Chapter 8). Finding the optimal ordering is equivalent to solving a shortest Hamiltonian path problem, which is known to be NP-Hard, but by relying on coherence of the traced streamlines we can obtain a suitable ordering e ciently. 4.1.5 Text Placement Given the set of oriented and ordered streamlines, the text is partitioned into fragments of appropriate size. To a large extent we are able to rely in this step on the Adobe Text Engine , which is designed for text handling in traditional publishing tasks. However, some challenges speci c to microgra- phy must be addressed by our method. These include choosing the optimal font size per region, and ensuring su cient text  ll for shorter streamlines. Finally, each text fragment is rendered on its corresponding streamline, using font and colour information supplied by the user. The text may be subtly warped to ensure a good  t, both at the individual streamline level and over the image as a whole. 4.2 Implementation Our system is implemented in C++ as a plug-in for Adobe Illustrator CS5 [1]. An industry standard vector-based graphic design suite, Illustrator 244.2. Implementation Figure 4.2: Adobe Illustrator CS5 user interface provides services such as loading and storing of vector images, a comprehen- sive library for modelling curves and regions, advanced text processing, a user interface for editing and compositing, etc. Figure 4.2 presents a snap- shot of Illustrator’s user interface. 4.2.1 Con guration File We found that associating custom properties (e.g. font face and size) with speci c regions using the Illustrator interface would represent a signi cant engineering e ort. We therefore opt to use a human-readable con guration  le instead. An example con guration  le is shown in Program 4.1. 254.2. Implementation Program 4.1 Typical con guration  le from our system. The  rst four lines contain font settings for speci c regions. The remaining lines adjust global parameter values. 0 1.15 AGaramondPro-Regular 0.1 0 1 1 1 1.5 HamburgerHeavenNF 0.3 0 1 1 2 1.0 AGaramondPro-Regular 0.1 0 1 1 3 0.36 Greetings 0.05 0 1 1 config SAMPLE_DIST_FACTOR 100.0 config LINE_HEIGHT_STRETCH_FACTOR 0.8 config MAX_WARP 0.6 config MIN_STRAIGHT_PATH_LENGTH 3.7 4.2.2 Dependencies Like many geometry processing applications, we rely on standard software components for services such as meshing, numerics and optimization. The system’s dependency list includes:  Triangle [42] and CML [46] for discrete geometry  TAUCS [48] linear solver  Ipopt [51] and MATLAB [29] for quadratic programming 4.2.3 Performance The system described here is a full-featured proof of concept. It was not en- gineered for optimal performance. Although the dependencies we use are in general mature software packages, with performance comparable to indus- try standards, there is room for improvement in our own implementation, integration, and data structures. Section 10.1 presents performance  gures for the system as currently implemented. 26Chapter 5 Preprocessing The input to our system consists of a vector graphics image, a given text, and optional con guration. Preliminary processing of the vector image is described in Section 5.1. An estimated font size per region is also computed at this time, explained in Section 5.2. 5.1 Image Preprocessing The given vector image is  rst converted to a planar map [5]. This rep- resentation, which consists of disjoint regions and non-intersecting curves, is well suited to micrography since it resolves ambiguities in region bound- aries, removes overlaps or layers, and establishes clear adjacency relation- ships between regions. The user can further edit the planar map by split- ting/merging regions and by adding new strokes (Figure 5.1). The repre- sentation is constructed using Illustrator’s built-in support for planar map conversion and editing. The input image is also scaled uniformly to a stan- dard size, allowing us to process all inputs in a scale-invariant manner. Be- cause of the resolution-independent nature of vector graphics, this is a safe, information-preserving transformation, with none of the adverse e ects as- sociated with scaling in raster images. Figure 5.1: Planar map editing. Left: a vector image consisting of two overlapping elliptical regions. Centre: the input is converted to a planar map with  ve non-overlapping regions. Right: the user can further edit the map, e.g. by merging adjacent regions as done in this case. To maximize the richness and expressiveness of our results, each element in the planar map can be handled in one of three ways: 275.1. Image Preprocessing  As a region to be  lled with text. A region is described using one closed, piecewise-smooth boundary path and a possibly empty set of closed paths representing holes (Figure 5.2).  As an isolated stroke used directly for placing a line of text (e.g. the contours of the face in Figure 10.6). Each stroke is speci ed by an open, piecewise-smooth path.  As an additional graphical element to be left untouched by the method (e.g. the eyes and eyebrows in Figure 10.2) Elements of the latter type are copied to the output and removed from consideration. The paths representing the remaining elements are sampled uniformly using arc-length parameterization, and each path is approximated by a polyline. Closed regions are then tessellated using constrained Delaunay triangulation [42]. The vertices generated by the triangulation process will be used to de ne a smooth  eld over the region (Chapter 6). There is a close correspondence between path sampling rates, path fea- ture size, font size, and complexity of the smooth  eld. The principal guide- line here is that image details in micrography cannot be smaller than in- dividual letters, therefore we can use an estimate of the font size in each region (Section 5.2) to derive the minimum feature size and su cient sam- pling density. Our smooth  elds will also be designed in a way that avoids  ne details, so they too do not require very  ne sampling. We found that setting the sampling distance to equal the estimated font size is a suitable choice in every case. Note that this approach may well lead to loss of image details that are deemed necessary by the user. Such issues can be resolved by increasing the amount of available text, either in the microgram as a whole or within the speci c region, as described in the next section. Fill-colour information from the input image is stored in a database and eventually applied to the resulting microgram. This provides a simple and intuitive way for the user to handle colouring. Although only uniform colour per region is supported directly, integration with Illustrator makes it simple matter to use our output as the starting point for further processing, such as applying colour gradients or bitmap image data (Figure 10.8). Figure 5.2 presents an overview of the system’s image preprocessing work ow. 285.1. Image Preprocessing Figure 5.2: Image preprocessing work ow. Top: input image. Middle: paths are sampled and approximated by polylines. Bottom: triangulation of closed regions. 295.2. Text Preprocessing 5.2 Text Preprocessing The method is designed to  t the given text into the image exactly once. Clearly this implies a strong link between the amount of text available, the area covered by the input image, and the font size to use. In our setup the former two are given and the latter is determined by the system as explained below. As an additional degree of freedom, we would like to provide user control over font sizing in di erent regions within the image. The approach we adopt is to let the user specify font sizes in relative terms, as multipliers of some common base size which is not known a priori. Unfortunately, it is not possible to compute exact font sizes at this point in the algorithm, due to variability in the amount of text that can  t in a given region using a given font size. One source of variability is the fact that text lines can seldom be packed to  ll a region with perfectly even spacing. Another is the need to  t complete words into each line (see Chapter 9). The base font size computed at this time is therefore a working estimate, to be adjusted later as part of the text placement stage. Why do we need font size estimates at this point in the process? One reason is path sampling rates, as discussed in the previous section. Another important reason is the close link between font size and inter-streamline spacing. Typographers measure the size of a font in western languages as the distance from the top of an ascender to the bottom of a descender (e.g. the vertical dimension of the bounding box of the word \boy"). This means that two text lines whose baselines are spaced font-size apart are guaranteed not to overlap. The base font size F is estimated using a simple quadratic model. Let Ar be the area of region r, and let Mr be the user-speci ed font size multi- plier for that region. Then the number of characters used to  ll the region is roughly proportional to Ar(FMr)2 . Recall that in addition to  lled regions, the given image may contain isolated strokes representing individual text lines. Assuming a common font size for all such strokes, the total number of characters to be placed along them is proportional to LlaFMla , where Lla is the total length of isolated strokes and Mla is the font size multiplier for iso- lated strokes. Incorporating the normalization constants, and denoting the number of characters in the given text by N , we get the following condition for exact  tting of the text to the image: NF 2 =  1 K1 X r Ar M2r ! +  1 K2 Lla F Mla  (5.1) The constants K1 and K2 were set by experimentation to 0.2 and 0.4 re- 305.2. Text Preprocessing spectively. We solve this quadratic equation in F and apply the multipliers to obtain an estimate of the font size for each region. 31Chapter 6 Smooth Field Design Smooth  elds are at the core of many recent geometry processing methods. The mathematical theory behind them as well as their application domain are rapidly evolving. Since  eld-guided methods have already been applied successfully to a host of layout problems, they present a natural choice for tackling text layout design. We begin this chapter with a brief overview of  eld terminology and characterization, then describe a method for  eld- guided text layout. 6.1 Field Design Primer A  eld is an assignment of a value to each point in a subset of Euclidean space. If the assigned value is a scalar, this is called a scalar  eld. If it is a vector, a vector  eld. In discrete contexts a  eld is typically de ned at a  nite set of points in space (e.g. on a regular grid, at the vertices of a polygon mesh, or on the faces of a triangle mesh), and an interpolation scheme is used to evaluate its values elsewhere. Most  elds of practical interest are smooth in the sense that their value changes gradually as one moves in space, i.e. if the  eld is de ned at two points whose spatial distance is small then the two  eld values are highly correlated. This also motivates the use of interpolation to determine  eld values at intermediate locations. In what follows we focus on the two-dimensional case, which is of interest in the context of this work. The general theory is of course richer and more complex. A number of di erent  eld formulations (Figure 6.1) can be used to guide layout. General 2D vector  elds de ne both a magnitude and a direction at every point. A direction  eld is a scalar  eld whose value is interpreted as a rotation angle with respect to some reference frame. The angle is not necessarily constrained to the range [0; 2 ). An orientation  eld di ers from a direction  eld in that the angles are de ned up to an integer multiple of  , inducing a two-way symmetry. To complete the picture, N-rotational symmetry (N-RoSy)  elds have both magnitude and direction, where the 326.1. Field Design Primer Figure 6.1: Di erent types of smooth  eld. Clockwise from top left: a general vector  eld, direction  eld, orientation  eld, 2-rotational symmetry  eld. Highlighted regions indicate the location of singularities. 336.1. Field Design Primer Figure 6.2: E ect of singularities on text layout. The presence of a trisector singularity in the middle of this image precludes the de nition of a coherent ordering or orientation of text lines in its vicinity. direction is de ned up to an integer multiple of 2 N . An orientation  eld can therefore be thought of as a 2-RoSy  eld with unit magnitude everywhere. A singularity (also known as singular point or isolated zero) is a point at which the  eld vanishes (Figure 6.1 left) or becomes degenerate (Fig- ure 6.1 right). Singularities are interesting from a theoretical point of view since they de ne the topological nature of a smooth  eld. They are also important in the context of  eld-guided layout since they are almost al- ways associated with undesirable artifacts { distortion, irregular vertices, increased computational complexity, and so forth depending on the appli- cation. In our method, singularities corresponds to text line con gurations that cannot be ordered coherently, and { depending on the type of singular- ity { may be impossible to orient coherently either (Figure 6.2). We would therefore like to identify the conditions under which singularities occur and avoid them where possible. Theoretical results from di erential topology show that singularities can- not always be avoided. The well-known hairy ball theorem guarantees that a smooth  eld de ned over a topological sphere will have at least one sin- gularity. The more general Poincar e-Hopf theorem [32] extends this result to other surfaces, including the one most pertinent to our work { 2D topo- logical disks. According to the theorem, if the  eld points in the outward direction everywhere along the boundary, then at least one singular point must occur inside the disk. It is easy to see that forcing alignment of the 346.2. Field Design for Text Layout  eld everywhere along the boundary would lead to the same result. This is a  rst indication that  eld-guided layout methods may want to avoid full alignment along boundaries. Beyond these topological considerations, singularities also arise naturally in methods that minimize curvature. Field curvature is estimated by the angle deviation of the  eld between adjacent vertices or faces. Curvature is the opposite of smoothness { a smooth  eld is one whose curvature is low. Ray et al. [38] show that while it is always possible to reduce the number of singularities to the theoretical minimum, the curvature of the resulting  eld may be quite high when compared to a  eld with additional singularities strategically placed at geometric feature points. Their work then proceeds to analyze this trade-o in manifold meshes and proposes a method for controlling it. We conclude this introduction to  eld design with a discussion of user constraints. By far the most commonplace and practical type of user inter- vention in  eld design is local directional constraints, i.e. having the user specify the direction of a  eld at a single point, along a path, or within a region. Although such constraints are geometric by nature, they can be sup- ported in topological design frameworks as well [12]. The exact de nition of a directional constraint corresponds to the  eld formulation: in a general vector  eld directional constraints would be vectors, in a direction  eld they are angles, and so on. When applied in the context of curvature-minimizing methods, direc- tional constraints will generally cause an increase in curvature. This takes us back to boundary alignment, presenting another reason why full align- ment should be avoided: a  eld constrained to align with a high-curvature boundary will by necessity have areas of high curvature (Figure 6.3). 6.2 Field Design for Text Layout Since we aim to use the streamlines of a smooth  eld for placing lines of text, the  eld should facilitate the formation of streamlines that a priori satisfy the aesthetic and readability requirements discussed in Chapter 3. While the line spacing criterion (Section 3.1.2) is only relevant for streamline tracing and subsequent steps, all others (boundary alignment, curvature, coherence, minimal length and distinction) can be taken into account during  eld design. Here is how to reformulate these requirements using smooth  eld terminology: 356.2. Field Design for Text Layout Figure 6.3: Forcing the  eld to fully align with region boundaries often leads to high  eld curvature, which in turn produces sharply bending streamline patterns (highlighted in orange) with multiple singularities (shown as purple dots).  Boundary alignment is a directional constraint enforced along bound- aries, specifying that the  eld’s orientation should be locally tangent to the boundary.  Similarly, distinction is a directional constraint applied along the mu- tual boundary of two regions, enforcing distinct  ow directions on either side.  Low curvature of text lines translates directly as low curvature of the  eld.  Coherence in  eld design is largely a matter of avoiding singularities, since there is no way to coherently order lines of text around a singular point. Other coherence considerations are discussed in later chapters.  Finally, avoidance of short lines is a directional constraint enforced at narrow parts of the region, specifying that the text should  ow through the narrow part rather than across it (Figure 6.4). Lines of text have a  ow direction rather than just an orientation, i.e. each line has a well-de ned starting point. One might therefore presume that the  elds we design should also be directional. However, this poses 366.2. Field Design for Text Layout Figure 6.4: Orienting the  eld to  ow across narrow regions (top) leads to short text lines. These can be avoided by routing the  eld through narrow regions instead (bottom). a problem: how to initialize the  ow direction along boundaries? Various criteria could be used (e.g. always choose a left-to-right  ow), but ulti- mately these are better applied to a resulting set of streamlines than as an a priori constraint on the  eld { since any added constraint only serves to degrade the smoothness of the generated  eld. We therefore use an undi- rected formulation for the  eld (Section 6.4) and resolve text  ow directions in a separate step (Section 8.1). Various techniques exist for computing  elds that satisfy conditions such as alignment or distinction. However, such  elds are not necessarily coher- ent (singularity-free) or have low curvature. As we saw in Section 6.1, fully boundary-aligned  elds will in general contain high-curvature regions and multiple singularities. Fortunately, full alignment is not necessary for proper shape depiction { as Figure 3.4 shows, equally good or even better shape depiction can be achieved by selectively relaxing the alignment constraint, or boundary conditions, so that the  eld is no longer required to aligned with certain parts of the boundary. Using a suitable set of boundary condi- tions we can avoid singularities, eliminate high curvature, and still maintain a pleasing text-art representation of the input shape. By designing these 376.2. Field Design for Text Layout Figure 6.5: Partial alignment with boundaries can provide the correct bal- ance between shape depiction, smoothness and coherence. Reprinted with permission of ACM. boundary conditions for an ensemble of adjoining regions simultaneously, distinction requirements can be included in the formulation explicitly. Figure 6.5 demonstrates the bene ts of partial alignment. In the puzzle piece on the right, alignment is only enforced along the more horizontal boundaries of the piece. On the left, the alignment constraint is relaxed at the two rounded tips. The question we must now answer is how to control the boundary con- ditions to achieve the right balance between alignment and smoothness. One appealing approach is to integrate the decision into  eld computation by using a robust error term such as Cauchy’s function [22] or Geman- McClure [17]. Such a method would automatically treat boundary con- straints that cannot be met as outliers. There are two problems though:  rst, the discretization of the problem in complex regions may be quite large, making these methods computationally expensive. Second, incorpo- rating user control into this framework is a di cult challenge. Another approach involves an iterative reweighting scheme, somewhat similar to the curve orientation method proposed by Xu et al. [58], whereby pieces of the boundary are iteratively relaxed (or constrained) based on an optimality measure. While this method is better able to accommodate user constraints, it requires successive computations of the  eld, and in most cases will not  nd a globally optimal solution without extensive backtracking. Instead, we observe that in our setup the behaviour of the  eld can be predicted based on the shape of the boundary alone, without computing the 386.3. Boundary Condition Design  eld at all. We can therefore break the process into two steps:  rst compute a suitable set of boundary conditions, then use a simple linear solver to obtain the  eld throughout. Each step provides a global, one-step solution to the problem it addresses. 6.3 Boundary Condition Design The only type of boundary constraint in our  eld design task is alignment with region boundaries. To design the conditions we therefore only need to decide for each point on the boundary: should the text be aligned to the boundary at that point, or not? We use the sampled boundary from Section 5.1 to discretize the problem, and aim to assign a boolean value per sample: 1 for alignment, 0 for relaxation (free boundary). We formulate this assignment as a global labelling problem for all points along region boundaries. The resulting labelling should satisfy two imperatives. First, the bound- ary conditions it induces should cause the  eld’s direction to change slowly as we move in space. Slow change takes care of the low-curvature require- ment, and also precludes singularities, since at singular points the direction changes in a discontinuous manner. Applied to boundary points, the slow- change requirement de nes a preference relation between pairs of nearby points, based on the similarity or dissimilarity of their tangent directions. Figure 6.6 illustrates this idea: if two nearby points have similar tangents, we want to avoid a situation where the  eld is forced to align with one of them but not the other, since having the  eld follow the boundary and then suddenly veer away would be damaging from a shape-depiction point of view. Conversely, if two nearby points have dissimilar tangents, we want to avoid aligning the  eld with both of them since high curvature would result. As Figure 6.6 shows, dissimilarity is most evident near sharp corners but can also occur in smooth high-curvature sections of the boundary. The second requirement that the labelling must ful ll is to maximize the proportion of the boundary that remains aligned, in the interest of shape depiction. This is an individual, pointwise preference. By default, every point on the boundary prefers to be assigned the \aligned" label, with the exception of points at sharp corners where no meaningful tangent direc- tion is available. However, the strength (or weight) of this preference can vary based on global considerations and speci cally the impact of alignment choice on the length of traced streamlines, and consequently text lines (see Section 3.2.2). While it is hard to predict the length of a streamline aligned 396.3. Boundary Condition Design Figure 6.6: To ensure that the  eld’s direction changes slowly, pairs of boundary point should have similar alignment labels if their tangent di- rections are similar (bottom and right), and di ering labels if their tangents are dissimilar (top and left). Figure 6.7: By forcing boundary alignment at points where the feature diameter is small (marked red), the  eld is constrained to  ow through the narrow feature rather than across it. 406.3. Boundary Condition Design with a boundary at any given point, a good estimate of the length of a non-aligned, or orthogonal, streamline is the feature diameter at that point. Hence, since we aim to reduce the number of short streamlines, the pref- erence for alignment should have an inverse relationship to the diameter. This ensures that at very narrow features the  eld would  ow through the feature rather than across it (Figure 6.7). Labelling problems such as this one are often formulated as a graph- cut. Each point is represented as a node in the graph, and the pairwise preferences are weighted edges between nodes. We construct such a graph, adding an edge from each point to all points that are visible from it, i.e. the line between the two points does not intersect region boundaries (see Figure 6.8 right). Figure 6.8: The graph constructed for the jigsaw example in Figure 4.1. Left: strength of individual preference for alignment for each boundary point, vi- sualized by a red to green range (green represents maximal preference). Right: visualization of the weighted-edges graph from one boundary point (shown in yellow) to its neighbourhood; node and edge colour represent pair- wise weights, with negative weights in red, positive in green. The full graph consists of such edges from all boundary points. Reprinted with permission of ACM. 416.3. Boundary Condition Design 6.3.1 Pairwise Preference Weights Edge weights in our labelling problem re ect the expected degree of similar- ity or dissimilarity between node labels. This requirement can be encoded as a positive or negative weight assignment wij to the edge between nodes i and j, with positive weights indicating a preference for similar labels and negative weights signifying a preference for dissimilar labels. The angle aij between the two tangent directions controls the sign as well as the strength of the preference. Since our rationale for pairwise preferences applies to boundary points that are near one another, the distance dij between the two points also  gures into the weight assignment. The exact de nition of distance for this purpose requires some care: we distinguish between point pairs that are mutually visible inside the region (i.e. the line segment connecting them is contained within the region) and points that are visible outside. Euclidean distance can be used as an indicator of mutual in uence in the former case, but is often misleading in the latter { for example, the two \tips" at the bottom of the jigsaw piece in Figure 6.5 are close to each other in Euclidean space, but their local  eld orientations are largely independent. On the other hand, if we exclude \outside-pairs" from the formulation entirely we lose valuable information. Case in point: without them, no dissimilarity weights would be generated at a concave corner. Our approach to outside- pairs is to measure their distance dij by the length of the boundary section connecting them. Geodesic distance would be another suitable alternative for this purpose. The boundary distance is then multiplied by c = 3 to further attenuate the in uence of outside-pairs compared to the more critical inside-pairs. The  nal weighting formula for a single edge is wij = Fa(aij)Fd(dij) (6.1) where the angle factor Fa is a sigmoid function that varies smoothly from -1 to 1. Speci cally, we use the hyperbolic tangent function tanh as follows: Fa(aij) = tanh(j  2  aij j   4 ) (6.2) With appropriate scaling this results in a smooth transition from a weight of 1 for perfectly aligned tangents to -1 for orthogonal ones. For the distance factor Fd we use Gaussian fallo , causing the preference to decay rapidly as distance increases: Fd(dij) = e  d2ij= 2 d (6.3) 426.3. Boundary Condition Design with  d set to 20% of the diagonal length of the region’s bounding box. This scale-invariant fallo achieves good balance between coherence on the one hand and individual alignment preferences on the other. If the input contains multiple adjoining regions, we may want to distin- guish them visually using text directions (see Section 3.1.4). To do this the user can invoke an algorithm variant that incorporates this constraint into the labelling problem: we duplicate the nodes of boundary points located on shared boundaries and associate a copy of the node with each adjacent re- gion. We then introduce an edge with the maximal negative weight wij =  1 between the two copies. This approach was used in producing the jigsaw image in Figure 4.1. The shared-boundary distinction constraint is shown as a red line connecting the two jigsaw pieces in Figure 6.8 (right). Note that in the absence of distinction constraints our labelling problem can be solved per region in isolation. Our system takes advantage of this, solving per region when possible, and only constructing and solving a uni ed problem if the user has indeed requested distinction constraints. 6.3.2 Individual Preference Weights We want to relate the individual preference strength at each boundary point to its feature diameter. One way to measure the diameter is to use the local feature size [2] and the degree to which the boundary tangent is aligned with Figure 6.9: Local feature size estimation. A bundle of rays around the inward normal direction is used to obtain a robust estimate for the distance and orientation of the \opposite" boundary. 436.3. Boundary Condition Design the local feature skeleton. However, robustly computing the local feature size and skeleton and matching the boundary to the skeleton are nontrivial tasks. Instead, similar to Shapira et al. [40], we use an approximate \diameter" measure by evaluating the distance and degree of alignment between the normal at each point and the normal at the \opposite" boundary of the region (Figure 6.9). For node i representing boundary point vi, we de ne the opposite bound- ary point as the closest intersection of the boundary with a ray emanating from vi in the inward normal direction. The distance to the intersection ap- proximates twice the local feature size, while the angle between the normals (or tangents) at vi and its opposite point re ects the degree of alignment with the local skeleton. To avoid inaccuracies due to slight variations in a normal we consider a cone of rays around the inward normal of vi rather than just a single ray. We trim the resulting set of opposite points to remove outliers in terms of distance and normals, and use an averaged distance di and average normal direction ai to compute the individual preference weight  i for node i (Figure 6.8 left):  i = F + a (ai)Fd(di) (6.4) This formulation is similar to the pairwise weight function in Equation 6.1 except that we clamp negative values of the angle factor Fa to zero to pro- duce F+a , ensuring that the individual preference weights obtained are non- negative. 6.3.3 Completing the Formulation We now have a classical labelling problem based on graph cut, where the optimal solution is found by minimizing a quadratic functional: min X ij wij(li  lj) 2 + ! X i  i(1 li) (6.5) subj. to 0  li  1 The left-hand term is the aggregate of all pairwise preferences. The right- hand term corresponds to individual preferences. The coe cient ! controls the trade-o between the two, and has a default setting of ! = 8.There is however a scaling issue to resolve: there are as many individual-preference terms as there are boundary points, but the number of pairwise preferences is quadratic in the number of boundary points. As a result, the relative in u- ence of the two terms is dependent on sampling density along the boundaries. 446.3. Boundary Condition Design To remove this dependence, we scale the individual preference weights  i by kWk=k k where W is the symmetric weight matrix and  the vector of individual preference weights. 6.3.4 Solving If all weights wij were positive, Equation 6.5 would be a standard convex problem. However, with negative weights the problem becomes much harder. In fact, if we ignore the individual preference component, then by  ipping the negative and positive weights the graph-cut problem becomes one of  nding a maximal cut { one of the 21 classical NP-complete problems [24]. A combinatorial approach would therefore be prohibitively expensive. Another approach that may seem appealing is graph partitioning. Ap- proximation methods such as normalized cut [43] and isoperimetric parti- tioning [19] can handle negative edge weights e ciently. However, these methods are designed to partition a graph into subsets of roughly equal size (or \volume" according to various metrics). They can be adapted to par- tition a graph into unequal size sets, but the sizes must be speci ed ahead of time. In our case, there is no reason to aim for balanced partitioning of the boundary into aligned and unaligned points, or to aim for any other size ratio de ned in advance. Instead, the solution should be driven only by Figure 6.10: Two candidate solutions encountered during the stochastic search. One of the local minima appears on the left. The best labelling found is shown on the right. Reprinted with permission of ACM. 456.3. Boundary Condition Design the pairwise dissimilarity preferences, with the number of unaligned points minimized subject to these preferences. In lieu of these general graph-cut techniques we develop a search proce- dure tailored to this case. The weight settings in our formulation impose a special structure on the problem: optimal solutions tend to have chains of consecutive boundary points with similar labels, with only a small number of discontinuities where the label changes (see Figure 6.10). Consequently, we can to use a custom stochastic search approach to compute a satisfactory solution. We generate a series of randomized initial guesses, then search locally for the best solution near each guess. For the local search we use a quadratic programming approach [18], which is well suited for this type of problem. The  rst initial guess is a neutral setting of li = 0:5 for all i. Intuitively, given this setting the method is most likely to move the labels according to individual preference weights, keeping chains of boundary points together when they are similar and separating them when they are not. We proceed with a local randomization strategy whereby each new initial guess is gen- erated either from the best global solution so far, or from the most recent solution. To generate a new initial guess from a given solution, we randomly select consecutive portions of the region boundary and invert their labels. start label ip optimized Figure 6.11: A single iteration of the boundary solver. Aligned points are shown in red, unaligned in blue. Left: labelling from a previous iteration. Centre: new initial guess produced by  ipping the labels along a portion of the boundary. Right: new optimized labelling computed by the quadratic programming solver. 466.4. Computing the Field The location of the inverted portion and its length are selected randomly with uniform probability, with at least one third of boundary points in- verted in each iteration (Figure 6.11). Ten to twenty iterations are typically su cient to arrive at the desired result. Since the procedure above computes real-valued labels, a rounding mech- anism is required to de ne the  nal partition. Thanks to the nature of our pairwise preference weighting, the number of labels whose value is neither 0 nor 1 is typically very small. Our implementation uses a permissive round- ing threshold of Tr = 0:9, labelling nodes as unaligned if their real-valued label is less than the threshold. In practice, the in uence of the threshold on the  nal result is minimal. 6.4 Computing the Field Once the boundary conditions are computed, we solve for a smooth  eld within each region. As previously discussed, many methods have been pro- posed for tackling this problem. However, since the boundary conditions were carefully designed to produce simple, slowly changing  elds with no singularities, the choice of  eld formulation is less crucial { any reasonable approach will produce the  eld we want. In order to decouple the question of text-line orientation from  eld computation (see Section 6.2) we use a two-way symmetric formulation. Speci cally, we follow the method of Pala- cios and Zhang [34] by solving for 2-rotational symmetry (2-RoSy)  elds. This formulation o ers a high degree of smoothness and is very e cient to compute. The  eld is de ned over the vertices of the triangulation from Section 5.1. It is computed individually inside each region. As in the work of Palacios and Zhang, the 2-RoSy  eld is derived by solving for its corresponding rep- resentation vector  eld R: Ri =  cos2 i sin2 i ! where  i 2 [0;  ) is the angle of the 2-RoSy  eld at vertex i of the triangula- tion. The solution itself is a standard least squares minimization problem. For each boundary point l labelled \aligned" by the boundary constraint de- sign algorithm, the representation R0l of the tangent at that point is added to the system as a soft constraint on the corresponding variable Rl. We thus have: min X ij kRi  Rjk 2 + X l kRl  R 0 lk 2 476.5. User Control The solution is computed using the TAUCS linear solver [48]. We found that the  elds generated using our two-step approach are in general singularity free and low-curvature whenever a solution exists that does not violate other critical requirements such as user constraints or very thin features. If no such solution is available, the resulting  eld may still contain a few singularities or areas of higher curvature. Advanced  eld design schemes such as those of Ray et al. [38] or Fisher et al. [15] may handle such cases better than the 2-Rosy approach. On the other hand, methods that avoid singularities at all costs [12] are less suitable for our needs as they tend to compensate with an undesirable increase in curvature. An example of a singularity generated due to user-imposed alignment constraints is shown in Figure 10.11 (bottom), where the artist required that the text be aligned with both the top and the sides of the head. Fig- ure 10.1 contains a few regions where coherence and low curvature could not be satis ed without including some very short lines. Consequently, higher curvature or one or two singularities were introduced automatically to allow for longer streamlines. 6.5 User Control A key advantage of  eld-guided methods is that users can interact with the process in an e cient and intuitive manner, imposing their requirements in the form of sparse constraints. This is helpful since layout tasks in general do not have a single \correct" solution, and artists may have additional considerations that are not part of our framework. We considered a number of mechanisms for users to control the design of boundary conditions and consequently the smooth  eld. These included a direct editing interface for algorithm parameters, a post-process  eld editor as described by Palacios and Zhang [34], and selection among di erent local minima of the quadratic programming solver. We found that the most intuitive approach is a direct visual interface for specifying preferred (or undesirable) alignment constraints. In our system, users are able to control the  eld in two di erent ways:  Directly sketching preferred directions as strokes inside the relevant region. These strokes take precedence over boundary alignment con- siderations and are used in rare circumstances, e.g. the background of the poppy in Figure 10.3.  Marking portions of the boundary as ones that should (or should not) 486.5. User Control be aligned with the  eld. These preferences are added as strong indi- vidual preference weights to the boundary formulation. User interaction is most often an interactive process. In the  rst phase the system is invoked without constraints, generating boundary conditions, smooth  elds and a visualization using the default settings. The user then applies a set of preferences and runs the algorithm again, producing a new layout design and visualization. The process repeats until the desired result is obtained. Figure 10.11 presents two micrograms generated from the same image and text { one produced automatically, the other with the inclusion of user- de ned boundary constraints. Another interaction paradigm involves the trade-o weight ! in Equa- tion 6.5, which controls the balance between alignment and coherence. By modifying its value and regenerating the boundary conditions, the user can raise the proportion of boundary points that are aligned at the cost of in- creased curvature, or vice versa. See Figure 6.12 for an example of the e ect of this parameter. In addition, variants of the boundary labelling formulation supporting Figure 6.12: E ect of the trade-o parameter !. When set very low (left), boundary condition design is dominated by coherence, resulting in a very smooth  eld but also producing large unaligned sections and many short lines. A balanced setting (top centre) improves alignment at the cost of some increase in curvature. Very high settings (left) result in a  eld that is almost fully aligned. 496.6. Symmetry distinction constraints (Section 6.3.1) and symmetry (Section 6.6) can be enabled or disabled by the user as global switches. 6.6 Symmetry Figure 6.13 presents a shape with a high degree of symmetry, which raises the question of whether we can (or should) design text layouts that re ect symmetry in the input. By default, our boundary condition formulation prefers to maximize smoothness and coherence even at the cost of broken symmetry (Figure 6.13 a,b). The user can however choose to override this behaviour. To account for symmetry we use a modi cation of the boundary la- belling formulation (Equation 6.5) similar to the one used to create region distinction in Section 6.3.1. Speci cally, we add strong pairwise similar- ity constraints between points that are equivalent under symmetry. The equivalence relationships, computed by hand or by a symmetry analysis al- gorithm [27], must be provided as auxiliary input. The resulting layout, shown in Figure 6.13 c, respects the shape’s symmetry, but the added con- straints produced a few singularities and areas of high curvature. 506.6. Symmetry (a) (b) (c) Figure 6.13: Forcing symmetry: (a) default asymmetric  eld generated by our method. (b) corresponding text layout (c) alternative text layout gen- erated by adding pairwise symmetry weights to the boundary formulation. Text: Lorem ipsum. Reprinted with permission of ACM. 51Chapter 7 Line Tracing The next task after  eld design is to trace a set of streamlines through each region. These lines will then serve as skeletons for individual lines of text in the  nal microgram. Since our  elds were carefully designed to satisfy shape depiction and coherence requirements a priori, we can use a fairly simple approach when tracing streamlines through them. Still, there are gains to be made by analyzing and optimizing the tracing process for the purpose of micrography. 7.1 Goals and Requirements By default, the set of lines we trace should be as evenly spaced as possible, so that text can be rendered on them without overlaps or gaps with only minimal deformation of individual letters. An exception to this rule is when the artist chooses to vary the font size within a given region to increase visual interest. The system supports this feature, with certain restrictions { see Section 7.4. Traced lines should of course avoid abrupt curves to prevent excessive deformation of text placed along them. Much of our focus in  eld design has been on ensuring that the smooth  eld does not exhibit high curvature, but we also designed the  eld to allow for the existence of singularities in certain situations. The curvature of a traced streamline as it approaches a singular point is unbounded. The tracing method must therefore take special measures near singular points. Short lines are another artifact that we would like to avoid. The  eld design process eliminates the \inevitable" short lines that would result from  eld  ow across narrow features, so the tracing step need only avoid spurious short lines in other places. As it turns out, this goal is shared with standard techniques for  eld visualization. We can therefore adopt existing solutions for our purpose. A requirement that sets us apart from other streamline-tracing methods is that we aim to mimic, as much as possible, the reading  ow of standard rectangular layouts that readers are accustomed to. In a rectangular layout, 527.2. Tracing Algorithm lines extend all the way to the margin on either end, and line endpoints are aligned with each other along the direction orthogonal to the text  ow (i.e. the direction that corresponds to \up" and \down" in most written languages). In micrography these properties cannot be guaranteed, but maintaining them wherever possible can contribute signi cantly to coherence (Figure 7.2). An important point to keep in mind is that unlike standard streamline visualization scenarios, in our system the streamlines and underlying  eld are tools rather than goals in and of themselves. It is therefore permissible to deviate slightly from the  eld in the interest of the goals presented here. 7.2 Tracing Algorithm Our method is based on the greedy tracing algorithm of Jobard and Lefer [23]. Their approach is appealing because of its simplicity and amenability to modi cations that stress various design goals, as exempli ed in the street modelling method of Chen et al. [11]. Starting from an initial seed point, a streamline is grown by tracing the  eld in both directions using numerical integration. At each integration step, new seed candidates are produced near the current position at a  xed distance in the direction orthogonal to the  eld (i.e. \above" and \below" the line currently being traced), and inserted into a queue. The  xed distance re ects to ideal spacing between adjacent streamlines, which in our case depends on the font size. Once the current line has been traced to its termination on both ends, a new candi- date is selected from the queue and used as the seed for the next streamline. The process ends when the candidate queue becomes empty. Figure 7.1 illustrates the tracing method. The original Jobard and Lefer algorithm used a simple FIFO queue to store candidate seeds. Chen et al. introduced a priority queue for smarter selection of the next seed point, and our system does the same. Our priority function is designed to encourage streamlines that extend to the boundary of the region and have their endpoints aligned with adjacent streamlines. A good heuristic for both objectives is to begin tracing new lines close to the endpoint of an existing line. Hence, seeds are given a higher priority the closer they are to an existing endpoint. To improve approximation of the region’s boundary, the process is initial- ized by  lling the queue with points near the region’s boundaries, speci cally points at an o set of half the text height inward from the boundary. Higher priority is given to points where the  eld direction is well aligned with the 537.2. Tracing Algorithm Figure 7.1: Illustration of the greedy streamline tracing algorithm. Top: the queue of seed candidates is initialized from the boundaries. Here seeds are coloured according to how well the  eld aligns with the boundary at that location (red for perfectly aligned, blue for orthogonal). Centre: An initial seed (in green) is selected and a streamline traced from it in both directions. Bottom: A new seed is selected near the previous streamline, and a new streamline is traced. Note that the new seed is not one of the initial seeds shown at the top. 547.3. Deviations from the Field boundary. To prevent these initial seeds from interfering with the rest of the tracing logic, their priorities are set lower than any of the candidates generated during tracing. This means that in most circumstances, only one initial seed will ever be used in any given region. The exception is regions containing very narrow features, for example the two \hooks" of the large orange-coloured region in Figure 10.1. Streamlines generated elsewhere in the region usually cannot penetrate into such narrow spots. In that case, initial seeds placed inside the feature will ensure that at lease one streamline is generated within it. When it is time to start tracing a new streamline, the highest-priority candidate is removed from the queue and tested to see if it is su ciently distant from the boundaries and from all existing streamlines. If so, it is used to trace a new streamline. Otherwise it is discarded and the next candidate is extracted from the queue. In our implementation the actual tracing is performed using the midpoint integration rule [20], which balances out errors and provides an excellent degree of accuracy (given that abrupt direction changes are largely absent from the  eld). Lines are terminated when they reach the boundary, come too close to another streamline, or make a sharp turn. The latter can only indicate the presence of a nearby singularity. The strategy of terminating streamlines that approach a singularity has performed well in streamline visualization methods, and is a workable solution in our case as well (see Figure 10.11 bottom). 7.3 Deviations from the Field Since exact visualization of the underlying  eld is not our goal, we may de- viate from the strict \streamline" de nition in the interest of coherence and shape depiction. This comes into play when a streamline follows a trajectory almost parallel to an existing feature { either another streamline or a bound- ary { with the distance to the feature gradually decreasing. At some point the distance will drop below a preset threshold, causing the new streamline to be terminated. If the streamline was following a boundary, terminating it at this point produces an aliasing artifact. If it was following another streamline, this represents a streamline that stopped midway through the region. Both e ects are undesirable, and can often be avoided by letting the streamline continue to run in parallel until it hits a boundary \head- on". To support this behaviour robustly we augment the primary smooth  eld with a weak  eld around each feature that repels new streamlines away 557.4. Spacing and Enrichment from it. This repelling  eld decays exponentially with distance, and is weak enough to only a ect the trajectory of streamlines that are almost parallel. To witness the e ect of the repelling  eld, compare images (b) and (c) in Figure 7.2. Several streamlines that were cut short in the version without repelling  elds (b) extend much further when these  elds are introduced (c), in many cases all the way to the opposite boundary. Once tracing has completed we abandon the  eld-guided paradigm, work- ing directly with the set of generated streamline curves. A number of cleanup operations are performed at this time:  rst, lines that are near-continuations of one another are stitched together. The tracing method is designed to min- imize such cases, but if they do occur we have more freedom in our scenario to patch them, whereas in pure streamline-based visualization this would not be allowed. Very short lines, if generated, are simply discarded. Lines that were terminated before reaching the boundary can sometimes be extended to the boundary. The idea behind these transformations is to remove visual artifacts that are damaging in the context of micrography, trading them for increased variability in interline spacing, which is more easily handled. The progression from basic Jobard and Lefer tracing to our  nal algo- rithm is presented in Figure 7.2. 7.4 Spacing and Enrichment The  nal step in our layout design is a readjustment of the spacing between adjacent lines. The user may prefer the spacing between streamlines in a speci c region be uniform, or not: uniform spacing produces even shading, as seen for example in Figures 10.9 and 10.11, while non-uniform spacing can add richness to the output, as in Figures 10.2 and 10.10. In the uniform case, although the tracing algorithm aims to produce evenly-spaced streamlines, we can still improve on its results after the fact. This is due to a number of reasons:  rst, the greedy algorithm makes no guarantee of global optimality. Second, during tracing we constrained our- selves to follow an underlying smooth  eld, but small deviations from the  eld are perfectly acceptable in our setup. Compare for example images (c) and (d) in Figure 7.2, which show the result before and after post-process adjustment. Notice that in (d), whenever a line terminates before reaching the boundary, the lines on either side of it bend toward each other to  ll the resulting gap. Such behaviour would be di cult to integrate into the tracing process, but is easy to implement once tracing has completed. A  nal reason for post-process adjustment is compensation for the e ect of 567.4. Spacing and Enrichment (a) (b) (c) (d) Figure 7.2: Elements of our tracing algorithm: (a) The basic tracing mech- anism of Jobard and Lefer creates an unorganized layout with numerous short lines. (b) Our seed selection strategy encourages streamlines that are  ush with the boundary. (c) Repelling  elds help prevent lines breaks inside the shape. (d) After post-process smoothing, the layout is ready for text rendering. Reprinted with permission of ACM. 577.4. Spacing and Enrichment cleanup operations such as short line removal. Spacing adjustment is performed by iteratively moving streamline ver- tices (i.e. the points computed via numerical integration) along the orthog- onal axis to the local tangent direction. For each vertex, the intersection of this axis with the two adjacent streamlines (or borders, as the case may be) is computed. If uniform spacing is desired, the vertex is moved to the average of the two intersections. For non-uniform spacing we use a weighted average, with weights per vertex determined at random ahead of time. The random weighting approach has a number of limitations, but it still illustrates the added richness that non-uniform spacing can provide. Some tracing methods support non-uniform streamline tracing by introducing a spatial density function [31]. In micrography, it is often desirable to use non- uniform sizing to emphasize a speci c word or phrase, regardless of where exactly it is located. Our system does not support these options however. 58Chapter 8 Line Orientation and Ordering Laying out text along a set of arbitrarily oriented streamlines requires se- lecting a text orientation along each line and computing a line ordering1. 8.1 Orientation A basic requirement for intuitive line orientation within each region is that adjacent parallel lines have the same orientation. Depending on the cur- vature of the lines, this requirement may not always be satis able. For instance, consider one line that bends around another as on the skull fore- head in Figure 10.11 (bottom). Our method aims to  nd a consistent global orientation that is similar on adjacent lines, when possible. We de ne a weighted graph where each node corresponds to a streamline and directed edges connect each pair of adjacent parallel streamlines. The weight associated with each edge from one streamline to another is set to be the percentage of the length of the  rst streamline where the two lines are adjacent. Note that two adjacent streamlines will have two directed edges, but these edges may have di erent weights (Figure 8.1a). The orientation within each region is de ned using a prioritized breadth-  rst traversal on this graph. To initialize the traversal we select a line that has a clear orientation preference, i.e. it is largely horizontal, and has su cient length (at or above the average line length in the region). The initial line is oriented left-to-right and this orientation is propagated through the graph using a breadth traversal order based on the edge weights. If no line has a strong left-right preference, e.g. if all streamlines are vertical, we use a bottom-up orientation instead, consistent with a left-right line order. 1This chapter was written by Mikhail Bessmeltsev and Prof. Alla She er, and de- scribes an algorithm developed by them. The text of this chapter was published previously as detailed in the preface, and is reproduced here for the sake of completeness. 598.1. Orientation (a) (b) (c) Figure 8.1: Orientation and ordering demonstrated on a subset of stream- lines: (a) initial adjacency graph, with edge colour representing weights (b) spanning forest of oriented lines, with connection edges highlighted in black (c)  nal order of lines (blue to red). Reprinted with permission of ACM. 608.2. Ordering 8.2 Ordering The requirement for intuitive ordering involves both region ordering and line ordering within each region. Inside a region, for any two adjacent par- allel lines, the lower one with respect to the determined orientation should, whenever possible, come after the upper one. This requirement de nes a partial, rather than full, order inside the region, as a streamline can have more then one adjacent line above or below it. Moreover, this partial or- der can contain loops when lines have high curvature, potentially wrapping around other lines, as is the case in the previously mentioned skull example. To de ne ordering we must convert this partial order to a full order. In the general case, solving this problem with respect to some metric is equivalent to  nding a shortest Hamiltonian path, and is NP-Hard. The algorithm we use is targeted at  nding an intuitive, readable order when the partial order is consistent, and a plausible one when loops are present. To  nd the ordering we use a subset of the streamline graph de ned for orientation, discarding edges from lower streamlines to the streamlines above them. Next, we compute an optimum branching [13], which de nes a spanning forest of the graph (Figure 8.1b). To create a full order we need to connect the forest into a single graph. We traverse the nodes of all trees to locate the shortest edge connecting two trees and add it to the graph. This process is repeated until all the trees are joined together or no edges linking trees are found. In the latter case we treat each sub-graph as a separate region for text layout. To traverse and order the combined graph, we pick as a root the left- most orphan node (i.e. one with no incoming edges) with respect to the frame de ned by the line orientation. We traverse the graph starting from the root. Each time we encounter a node with more than one parent, we traverse all branches above this node in a left-to-right order and only then traverse the node itself. At each branching point with multiple children we use the same left-to-right order to traverse those (Figure 8.1c). To order the regions themselves, we use a similar process, but on a region graph instead of a lines graph. The order here is more vague as we have no clear notion of adjacency or parallelism. Instead region nodes are connected by edges based on global adjacency computed using a Voronoi diagram, and edge weights are set to be inversely proportional to the distance between the regions, and directly proportional to the dot product of the transition direction between regions and the preference direction. The preference can follow a lexicographic left-right, top-bottom order, or some mix of the two directions set by specifying an arbitrary direction vector such as (1; 1). We 618.2. Ordering then use a similar graph traversal mechanism where the local frame is set based on the average of the line orientations in adjacent regions. To order individual strokes (text lines not included in a region) we can treat each as a stand-alone region, or we can treat them all as a single region. While we cannot claim that the ordering computed is necessarily globally optimal, we found that our results agree, in general, with manual ordering both inside and in between regions. 62Chapter 9 Rendering Text We now have a set of ordered curves on which to render the text of the microgram. Placing of text is a typesetting problem, albeit a highly unusual one: lines in general are not straight, their lengths can vary dramatically, and there are good reasons to vary the font size locally, as we shall see. 9.1 Typesetting A dedicated typesetting engine for micrography, while useful, is beyond the scope of this work. Instead we use the Adobe Text Engine (ATE) package included with Adobe Illustrator. The ATE takes care of two major tasks: partitioning the given text into fragments that can  t onto the curves, and rendering fragments with user-speci ed font face, size and colour. These fragments are then transferred onto the target curves using the skeletal strokes method (Section 2.1). Remember that our goal is to  t the given text onto the microgram exactly once. An approximate base font size for achieving this was derived in Section 5.2, but the precise size may di er somewhat. We therefore perform a simple search procedure to  nd the optimal base size, repeatedly rendering the text at di erent sizes to determine the largest font that does not cause any over ow. We con gure ATE to prevent breaking up individual words over multiple lines. As with any typesetting system, the text to be rendered on a line may not cover the available space exactly { this is normally handled either by \ ush left", i.e. aligning the text with the start of the line while leaving some white-space at the end, or by \full justi cation", which increases the spacing between words so that the text aligns with both start and end. In our case,  ush left is clearly unsuitable due to shape-depiction requirements. Full justi cation is better, but large chunks of white-space within a line can become a noticeable shading artifact. Instead, we render the text in  ush-left mode and stretch the result to the desired length. As long as the stretch factor is limited, the e ect remains largely invisible and produces more uniform shading than full justi cation. 639.2. Text Warping Short lines present a special challenge. Since word breakups are avoided, the  tting of text to a short line in the presence of long words may fail, leaving the line partially or even entirely blank. We found that blank lines in the microgram { even short ones { immediately draw the observer’s eye and greatly diminish the work’s aesthetic appeal. To prevent this we use a version of the stretching idea above: when fragmenting the text, lines shorter than some minimal threshold (.e.g. 4 times the font size) are clamped up to the threshold. Once the fragments are determined, if the size of a fragment exceeds the actual length of its curve, the text is rescaled to  t in the available space. This introduces some distortion but is less damaging than blank space. The bear images in Figure 10.9 demonstrate the e ect of our typesetting approach. Most of the bear’s body, constructed of long text lines, is very uniform in both shading and text size. More variation in size and shading is found in those legs of the bear that, in the interest of coherence, were laid out using shorter lines. This variation is due to stretching of shorter words and contraction of longer phrases to  t a particular line length. 9.2 Text Warping At this point the microgram is essentially complete, but a more aesthetically pleasing result is obtained by subtly warping the text in two ways. First, Figure 9.1: E ect of adaptive text height and boundary warping: a single petal from Figure 10.3 without text warping (left) and with warping (right). Reprinted with permission of ACM. 649.2. Text Warping we account for local variations in spacing between neighbouring lines. Al- though our  eld design and tracing algorithm reduce such variations to a bare minimum, perfect spacing is impossible in any nontrivial layout task. To avoid visual gaps in the image we adaptively warp the height of the text to  ll the space more uniformly. We measure the distance from each curve to its neighbours at regular intervals along the curve and construct smoothly varying height pro les, which are then applied to the rendered text. Next, the beginning and end of each text line are adjusted to better match the region boundary. Whenever a text line is neither aligned nor orthogonal to the boundary, some jagged aliasing artifacts may result. Here too our careful  eld design and streamline tracing methods minimize this e ect, but it can still occur as we balance other considerations as well. To reduce the e ect further we apply a cage deformation [53] as illustrated in Figure 9.2. We  rst render the text horizontally and de ne an initial cage coinciding with the text’s bounding box. This rectangular cage is then deformed into a trapezoid by rotating its vertical edges, with the amount of rotation de ned by the angle between streamline and boundary at the corresponding endpoint of the streamline. For endpoints that do not occur at a boundary, no deformation is applied. The resulting warped text is then rendered along the streamline. Figure 9.1 demonstrates the e ect of text warping on the  nal result. 659.2. Text Warping Figure 9.2: Warping the endpoints of text lines to improve boundary align- ment. Top: results with no warping. Bottom: with warping. The cage- warped horizontal text is shown in the bottom left corner. The cage itself is visualized for the last four text lines. 66Chapter 10 Results This chapter presents a diverse selection of micrograms created with our system, from graphics and text available freely online. Part of the artistry of micrography lies in selecting source graphics that have the right amount of detail, along with the correct amount of text. If the image is very detailed or the font too large then individual letters begin to play a crucial role; we thus leave the realm of micrography for that of general calligraphy, which is outside the scope of this work. In our system, the choice of sources remains entirely up to the user. Except where stated otherwise, the layouts for all results were computed automatically based on the input graphics and text. This allowed us to rapidly experiment with di erent fonts and texts to achieve a pleasing result. We consider this capacity for iterative microgram design a key advantage of our system over established digital art software for artists working in this  eld. The microgram \Motif" (Figure 10.1) was created using text from Lewis Carroll’s Alice in Wonderland. Font size multipliers were used to vary the size of the text in the various regions, adding to the visual complexity of the result. By traditional standards this is only a medium-sized microgram, but even so determining the hundreds of lines it is comprised of would be di - cult as well as tedious if done by hand. This example also demonstrates the challenge of balancing readability and image depiction requirements. Given the complicated nature of the abstract input shapes, maintaining coher- ence in some of them is far from trivial. For most regions a singularity-free solution exists which naturally aligns with narrow features. However, the orange-coloured region at top-right has six narrow areas in various orienta- tions which are very hard to reconcile. Consequently, a few high-curvature areas are produced within the region to obtain what is deemed an acceptable trade-o between coherence and alignment. The \Summer Girl" image is combined with words from the Song of Songs. The hair consists of two highly intricate regions, with smooth random variation in size used to create the visual e ect of hair strands. The large size and high complexity of these regions make for a particularly challenging 67Chapter 10. Results Figure 10.1: \Motif". Image source: allfreevectors.com. Text: excerpt from Alice in Wonderland. Input image inset. Reprinted with permission of ACM. Please zoom into the  gures in this chapter using the digital version to read the  ne text. 68Chapter 10. Results boundary condition problem. Here we are able to produce a pleasing result at reduced computational cost by using a local reweighting approach, which is based on individual alignment preferences (Section 6.3.2). This approach enforces boundary alignment at narrow areas while allowing some relaxation in places where the feature diameter is large. Figure 10.3 adopts the text of the poem In Flanders Fields, placing one full copy of the poem on each petal, as well as in the centre and in the background. The size of the text is automatically adjusted according to the area of each region. Randomized line thickness is applied inside the petals for enhanced visual e ect. The Mona Lisa image in Figure 10.4 and the portrait in Figure 10.5 exemplify black and white classic style micrography. Both of them use text from T. S. Eliot’s Portrait of a Lady. Note the use of text  ow directions to achieve visual distinction between di erent regions. In Figure 10.6, lines of text are used to  ll regions as well as depict outlines, creating an interesting visual interplay between the two. Figure 10.7 combines graphical content with a translation of the well- known Russian poem Dark Eyes, generating a compelling black and white image where font properties are used to visually separate image regions. In Figure 10.8 we compare the results of using two di erent smooth  elds to guide text layout over the same input image, speci cally the cat picture from Figure 2.5. On the left is the original  eld used by Li et al. [26] to generate their mosaic pattern { a single  eld computed over the entire region of interest and fully aligned with the feature lines (in this case, the cat’s eyes and the outline of its face). On the right is our  eld, computed over a segmented version of the same input. Mosaic and text layouts share some similarities { both aim to  ll a given region using anisotropic texture elements while conforming to feature lines. But while the approach of Li et al. was successful in the case of the mosaic, it generates an incoherent layout when used for text. In contrast, our result is more coherent. It also allows for clearer separation of the elements of the image, by varying the font size and text direction between regions. The di erences become more pronounced in the black-and-white version (bottom). Figure 10.9 shows two results created from the same input using di er- ent amounts of text, highlighting the  exibility o ered to artists using our system. In this example, a very simple input is converted into a visually appealing, intricate design by overlaying the microgram with a colour layer speci ed by the user. Such e ects are very easy to apply since our outputs are naturally presented as vector graphics. Figure 10.10 presents variations on a theme in colour and typeface, as 69Chapter 10. Results Figure 10.2: \Summer Girl". Image source: vector.net. Text: Song of Songs. Input image inset. Reprinted with permission of ACM. 70Chapter 10. Results Figure 10.3: \In Flanders Fields". Image source: Wikimedia Commons. Text: In Flanders Fields by John McCrae. Input image inset. Reprinted with permission of ACM. 71Chapter 10. Results Figure 10.4: \Mona Lisa". Image source: spraypaintstencils.com. Text: Portrait of a Lady by T. S. Eliot. Input image inset. Reprinted with per- mission of ACM. 72Chapter 10. Results Figure 10.5: \Light and Shadow". Image source by Ruby Mawira. Text: Portrait of a Lady by T. S. Eliot. Input image inset. 73Chapter 10. Results Figure 10.6: \Fedora". Text and image source: Wikipedia. Input image inset. Reprinted with permission of ACM. 7410.1. Running Times Figure 10.7: \Dark Eyes". A black and white microgram where region distinction is achieved through variation in font size and type. Image source: vector4free.com. Text: Dark Eyes (translated by Katya from russmus. net). Reprinted with permission of ACM. well as the visual interest that stems from variable text height. Figure 10.11 demonstrates our support for user preferences in the form of local boundary alignment constraints. The automatically generated result (top), with largely vertical text  ow inside the main part of the skull, is superior in terms of the coherence and curvature. The user-guided solution (bottom) was constrained to align with the top and sides of the skull. This result appears more natural to many observers, despite the singularity that must appear in order to reconcile the user’s constraint with other alignment requirements. 10.1 Running Times The primary cost in our implementation involves the boundary condition computation, which requires solving a quadratic programming (QP) opti- mization problem. This step was initially implemented in MATLAB using the built-in active-set based QP solver [9]. A more e cient C++ implemen- tation was later developed based on the Interior-Point Optimization (Ipopt) package [51], resulting in a sixfold performance improvement on average. The two other computationally demanding steps are text rendering using the Adobe Text Engine, and the spacing adjustment step performed after streamline tracing. The latter relies on a large number of ray-intersection queries, and its cost can be reduced signi cantly by using techniques from 7510.1. Running Times Figure 10.8: Top left: layout guided by the fully-aligned  eld of Li et al. Top right: Layout created by our method. Bottom: the di erences between the two layouts become more evident in the absence of colour. Original image courtesy of Li et al. Text: The Cat Came Back, adapted from Harry S. Miller. Reprinted with permission of ACM. 7610.1. Running Times Figure 10.9: In this example, di erent lengths of input text produce di erent results from an otherwise identical input. Text: Wikipedia. Reprinted with permission of ACM. 7710.1. Running Times Figure 10.10: Endless variations on a topic can be produced by modifying the typeface, colour scheme, etc. Text: Genesis 1 (King James Version) and On the Origin of Species by Charles Darwin. Reprinted with permission of ACM. 7810.1. Running Times Figure 10.11: Field design with user-de ned constraints: the Jolly Roger  ag at the top was created with automatic boundary constraints. It has long text lines and no singularities. With user preference for text alignment around the top and sides of the skull (shown in green), the  eld becomes less coherent (containing a singularity on the forehead), but the overall e ect is arguably more appealing. Image source: Wikipedia. Text: Derelict by Young E. Allison. Reprinted with permission of ACM. 7910.1. Running Times Microgram Boundary Spacing Text Other Total MATLAB C++ Fedora 102 27 19 13 2 61 Dark Eyes 284 38 11 18 12 79 Jolly Roger 215 56 12 28 13 109 Mona Lisa 189 37 51 23 11 122 In Flanders Fields 418 45 21 30 9 105 Beetle 340 83 36 13 10 142 Light and Shadow 706 104 65 25 15 209 Cat 403 68 36 83 44 231 California Republic 568 82 146 50 36 314 Summer Girl 130 23 271 93 94 481 Motif 4619 738 25 92 61 916 Table 10.1: Run time breakdown: boundary condition solvers; spacing ad- justment; text rendering; rest of the algorithm; total running time when using the C++ boundary solver. All times are given in seconds. Note: in the Summer Girl image, the boundary solver was only invoked for the smaller regions. real-time rendering and global illumination. The rest of the algorithm requires a few seconds for simpler images and up to about a minute for the largest examples. Table 10.1 lists running times for the results presented in this chapter. All runs were executed on a dual-core Intel workstation equipped with the E6400 CPU running at 2.4 GHz. 80Chapter 11 Summary This thesis described an automated method for generating micrography, an appealing and intricate form of text art. Traditional hand-drawn mi- crography has been practised by artists for many centuries, but designing micrograms remains a highly technical, time-consuming task requiring sig- ni cant expertise. In contrast, by using the digital design tool implemented as part of this work, such designs can be created from standard vector art in a matter of minutes. To the best of our knowledge this is the  rst attempt by the computer graphics community to tackle micrographic design. The proposed method takes in a vector graphics image and text and produces a richly detailed, visually appealing and easily readable microgram. A range of artistic controls are provided to the user, including font styling and local directional constraints. The  exibility and applicability of the system are demonstrated in Chapter 10 using a wide variety of  nished designs, ranging from classic style black and white imagery to composite works that take full advantage of the digital platform. Our main technical contribution is an algorithm that uses smooth  elds to generate text layouts inside a closed planar shape. Field-guided methods are by now well-established in related applications, e.g. parameterization, quadrangulation and texture synthesis, and we extend the paradigm to cover text line patterns as well. However, this work goes beyond standard  eld- guided techniques by presenting a principled approach to boundary condition design for smooth  elds in 2D. Through careful analysis and speci cation of boundary conditions, we are able to shift much of the complexity away from  eld computation and into a separate preprocessing step, which is smaller in scale and better suited to the kind of reasoning we want to apply. In the case of micrography this approach helps produce  elds that balance aesthetic and readability requirements, aligning with the boundary where possible while remaining largely free of singularities and high curvature. The same ideas can potentially transfer to other applications that use smooth  elds as a design tool, such as anisotropic texturing and meshing. 81Chapter 12 Future Work This work presents opportunities for further development in two primary areas: text art, and boundary condition design. On the text art front, it would be interesting to map and expand the range of styles supported by the proposed framework. While most micro- grams can be generated using piecewise smooth  elds as done in our system, there are examples where this approach requires an unintuitive partition of the image into regions. Modern creations in particular sometimes include elements such as partial text overlap, pseudo-3D e ects, or interleaving of di erent text  ow directions, none of which  t well into the existing algo- rithm. It would also be instructive to work closely with designers of mi- crography { hand-drawn as well as digital { to observe what kinds of control mechanisms are most helpful to them in expressing and producing the result they are after. There is clearly room for improvement in the text placement and ren- dering mechanism of our system. In the method presented, local properties of the text only come into play during the very last step { an approach that has bene ts as well as disadvantages. On the one hand, a key goal of our system is to let artists focus on high-level design rather than devote their attention to individual words and letters. On the other hand, ignoring text details until later in the process means that these details cannot inform the layout process. Better text placement { leveraging knowledge about the shape of individual words and letters { could help reduce artifacts, achieve more uniform density, and improve readability. A performance boost is needed if our implementation is to mature into a practical, user-friendly tool. Ideally we would like to provide artists with real-time responses to changes in their design. This requires a combina- tion of engineering e orts and a revisit of some of the core algorithmics. In particular, the boundary formulation is a non-convex search problem. Although our method performs the search quite e ciently, an alternative convex formulation for the boundary condition problem would be an impor- tant contribution. Beyond text art, a number of applications could bene t from the bound- 82Chapter 12. Future Work ary condition design paradigm proposed in this work. Quadrangulation and uv-parameterization methods typically aim to follow feature lines, minimize curvature, and avoid singularities. In the 2D case our boundary formulation could probably be applied to these problems as it is. The broader concept, whereby parts of the boundary are aligned and others relaxed according to a set of custom criteria, is applicable to a host of other planar layout tasks, and could perhaps be extended to feature-aligned designs in 3D as well. 83Bibliography [1] Adobe Systems Inc. Illustrator CS5 [computer software], 2010. www. adobe.com/products/illustrator. [2] Nina Amenta and Marshall Bern. Surface reconstruction by voronoi  ltering. In Proc. Symp. Computational Geometry, pages 39{48. ACM Press, 1998. [3] Guillaume Apollinaire and Anne H. Greet. Calligrammes : Poems of Peace and War (1913-1916): A Bilingual Edition. University of Cali- fornia Press, 1980. [4] APP Helmond. Textaizer [computer software], 2010. www.mosaizer. com/Textaizer. [5] Paul Asente, Mike Schuster, and Teri Pettit. Dynamic planar map illustration. ACM Trans. Graphics (Proc. SIGGRAPH), pages 30:1{ 30:10, 2007. [6] Paul J. Asente. Folding avoidance in skeletal strokes. In Proc. Sketch- Based Interfaces and Modeling Symp. (SBIM), pages 33{40. Eurograph- ics, 2010. [7] Leila Avrin. Hebrew Micrography: One Thousand Years of Art in Script. Israel Museum, Jerusalem, 1981. [8] David Bommes, Henrik Zimmer, and Leif Kobbelt. Mixed-integer quad- rangulation. ACM Trans. Graphics (Proc. SIGGRAPH), pages 77:1{ 77:10, 2009. [9] Mary Ann Branch and Andy Grace. Optimization Toolbox User’s Guide, Version 2, 2002. [10] John Canny. A computational approach to edge detection. IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679{698, 1986. 84Bibliography [11] Guoning Chen, Gregory Esch, Peter Wonka, Pascal Muller, and Eugene Zhang. Interactive procedural street modeling. ACM Trans. Graphics (Proc. SIGGRAPH), pages 103:1{103:10, 2008. [12] Keenan Crane, Mathieu Desbrun, and Peter Schr oder. Trivial connec- tions on discrete surfaces. Computer Graphics Forum (Proc. SGP), pages 1525{1533, 2010. [13] Jack Edmonds. Optimum branchings. J. Research National Bureau Standards, 71B:233{240, 1967. [14] Jonathan Feinberg. Wordle [computer software], 2009. www.wordle. net. [15] Matthew Fisher, Peter Schr oder, Mathieu Desbrun, and Hugues Hoppe. Design of tangent vector  elds. ACM Trans. Graphics (Proc. SIG- GRAPH), pages 56:1{56:9, 2007. [16] Max Froumentin. Textorizer [computer software], 2010. lapin-bleu. net/software/textorizer. [17] Stuart Geman, Donald E. McClure, and Donald Geman. A nonlin- ear  lter for  lm restoration and other problems in image processing. CVGIP: Graphical Models and Image Processing, 54:281{289, 1992. [18] Philip E. Gill, Walter Murray, and Margaret H. Wright. Practical Op- timization, chapter 5. Academic Press, 1981. [19] Leo Grady and Eric L. Schwartz. Isoperimetric partitioning: a new algorithm for graph partitioning. SIAM J. Scienti c Computing, 27(6):1844{1866, 2006. [20] Denwood V. Gri ths and Ian M. Smith. Numerical methods for engi- neers: a programming approach. CRC Press, 1991. [21] Siu Chi Hsu, Irene H. H. Lee, and Neil E. Wiseman. Skeletal strokes. In Proc. ACM Symp. User Interface Software and Technology, pages 197{206, 1993. [22] Peter J. Huber. Robust statistics, page 71. Wiley-Interscience, 2004. [23] Bruno Jobard and Wilfrid Lefer. Creating evenly-spaced streamlines of arbitrary density. In Eurographics Workshop Visualization in Scienti c Computing, pages 43{56, 1997. 85Bibliography [24] Richard M. Karp. Reducibility among combinatorial problems. In Com- plexity of Computer Computations, pages 85{103. Plenum Press, 1972. [25] Donald E. Knuth. Digital Typography. Cambridge University Press, 1997. [26] Yuanyuan Li, Fan Bao, Eugene Zhang, Yoshihiro Kobayashi, and Peter Wonka. Geometry synthesis on surfaces using  eld-guided shape gram- mars. IEEE Trans. Visualization and Computer Graphics, 17:231{243, 2011. [27] Yaron Lipman, Xiaobai Chen, Ingrid Daubechies, and Thomas Funkhouser. Symmetry factored embedding and distance. ACM Trans. Graphics (Proc. SIGGRAPH), pages 103:1{103:12, 2010. [28] Ron Maharik, Mikhail Bessmeltsev, Alla She er, Ariel Shamir, and Nathan Carr. Digital micrography. ACM Trans. Graphics (Proc. SIG- GRAPH), pages 100:1{100:12, 2011. [29] The MathWorks Inc. MATLAB [computer software], 2010. version 7.11.0 (R2010b). [30] Tony McLoughlin, Robert S. Laramee, Ronald Peikert, Frits H. Post, and Min Chen. Over two decades of integration-based, geometric  ow visualization. Computer Graphics Forum, 29(6):1807{1829, 2010. [31] Abdelkrim Mebarki, Pierre Alliez, and Olivier Devillers. Farthest point seeding for e cient placement of streamlines. In IEEE Visualization, pages 479{486, 2005. [32] John W. Milnor. Topology from the di erentiable viewpoint, page 35. University Press of Virginia, 1965. [33] Victor Ostromoukhov and Roger D. Hersch. Multi-color and artistic dithering. In Proc. SIGGRAPH, pages 425{432. ACM, 1999. [34] Jonathan Palacios and Eugene Zhang. Rotational symmetry  eld design on surfaces. ACM Trans. Graphics (Proc. SIGGRAPH), pages 55:1{ 55:10, 2007. [35] Hans Pedersen and Karan Singh. Organic labyrinths and mazes. In Proc. Non-Photorealistic Animation and Rendering (NPAR), pages 79{ 86. ACM, 2006. 86Bibliography [36] Emil Praun, Hugues Hoppe, Matthew Webb, and Adam Finkelstein. Real-time hatching. In Proc. SIGGRAPH, pages 581{586. ACM, 2001. [37] Nicolas Ray, Wan Chiu Li, Bruno L evy, Alla She er, and Pierre Alliez. Periodic global parameterization. ACM Trans. Graphics, 25:1460{1485, 2006. [38] Nicolas Ray, Bruno Vallet, Laurent Alonso, and Bruno L evy. Geometry aware direction  eld processing. ACM Trans. Graphics, 29:1:1{1:11, 2009. [39] Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno L evy. N-symmetry direction  eld design. ACM Trans. Graphics, 27:10:1{10:13, 2008. [40] Lior Shapira, Ariel Shamir, and Daniel Cohen-Or. Consistent mesh partitioning and skeletonization using the shape diameter function. The Visual Computer, 24(4):249{259, 2008. [41] Gaurav Sharma. Digital Color Imaging Handbook. CRC Press, 2002. [42] Jonathan R. Shewchuk. Triangle: Engineering a 2D quality mesh gen- erator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, pages 203{222. Springer-Verlag, 1996. [43] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmenta- tion. IEEE Trans. Pattern Analysis and Machine Intelligence, 22:888{ 905, 1997. [44] Tatiana Surazhsky and Gershon Elber. Arbitrary precise orientation speci cation for layout of text. In Proc. Paci c Conf. Computer Graph- ics and Applications, pages 80{86. IEEE Computer Society, 2000. [45] Tatiana Surazhsky and Gershon Elber. Artistic surface rendering using layout of text. Computer Graphics Forum, 21(2):99{110, 2002. [46] Vitaly Surazhsky. CML { a mesh processing library [computer soft- ware], 2002. [47] Technion { Israel Institute of Technology. SculpText [computer soft- ware], 2008. www.cs.technion.ac.il/textsculpt. [48] Sivan Toledo. TAUCS { a library of sparse linear solvers, 2003. www. tau.ac.il/~stoledo/taucs. 87Bibliography [49] Greg Turk and David Banks. Image-guided streamline placement. In Proc. SIGGRAPH, pages 453{460. ACM, 1996. [50] Vahe. Micrography: Text art and typography, 2009. www.gawno.com/ 2009/05/micrography-text-art-and-typography. [51] Andreas W achter and Lorenz T. Biegler. On the implementation of an interior-point  lter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106:25{57, 2006. [52] Youfen Wang, Zhongshi Ouyang, Wen C. Fong, Baolin Cao, Wenjun Cong, Dun Huang, Jingxian Wang, Shizheng Wang, Yuchi Wang, Peigui Ye, Junjie Zhou, Guantian Zhu, Qianshen Bai, Uta Lauer, and Craig Shaw. Chinese Calligraphy. Yale University Press, 2008. [53] O r Weber, Mirela Ben-Chen, and Craig Gotsman. Complex barycen- tric coordinates with applications to planar shape deformation. Com- puter Graphics Forum (Proc. Eurographics), pages 587{597, 2009. [54] A. J. Wilkins and M. I. Nimmo-Smith. The clarity and comfort of printed text. Ergonomics, 30(12):1705{1720, 1987. [55] Michael T. Wong, Douglas E. Zongker, and David H. Salesin. Computer-generated  oral ornament. In Proc. SIGGRAPH, pages 423{ 434. ACM, 1998. [56] Jie Xu and Craig S. Kaplan. Calligraphic packing. In Proc. Graphics Interface, pages 43{50. ACM, 2007. [57] Jie Xu and Craig S. Kaplan. Image-guided maze construction. ACM Trans. Graphics (Proc. SIGGRAPH), pages 29:1{29:9, 2007. [58] Kai Xu, Daniel Cohen-Or, Tao Ju, Ligang Liu, Hao Zhang, Shizhe Zhou, and Yueshan Xiong. Feature-aligned shape texturing. ACM Trans. Graphics (Proc. SIGGRAPH Asia), pages 108:1{108:7, 2009. [59] Xuemiao Xu, Linling Zhang, and Tien-Tsin Wong. Structure-based ASCII art. ACM Trans. Graphics (Proc. SIGGRAPH), pages 52:1{ 52:10, 2010. 88


Citation Scheme:


Usage Statistics

Country Views Downloads
United States 9 0
Romania 2 0
Australia 1 0
United Kingdom 1 0
Russia 1 0
City Views Downloads
Ashburn 6 0
Unknown 2 0
San Francisco 2 0
Suceava 2 0
Adelaide 1 0
Sunnyvale 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items