Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Pagurek van Mossel, Dave
Master of Science - MSc
University of British Columbia
When creating freeform drawings, artists routinely employ clusters of overdrawn strokes to convey intended, aggregate curves. The ability to algorithmically fit these intended curves to their corresponding clusters is central to many applications that use artist drawings as inputs. However, while human observers effortlessly envision the intended curves given stroke clusters as input, existing fitting algorithms lack robustness and frequently fail when presented with input stroke clusters with non-trivial geometry or topology. We present StrokeStrip, a new and robust method for fitting intended curves to vector-format stroke clusters. Our method generates fitting outputs consistent with viewer expectations across a vast range of input stroke cluster configurations. We observe that viewers perceive stroke clusters as continuous, varying-width strips whose paths are described by the intended curves. An arc length parameterization of these strips defines a natural mapping from a strip to its path. We recast the curve fitting problem as one of parameterizing the cluster strokes using a joint 1D parameterization that is the restriction of the natural arc length parameterization of this strip to the strokes in the cluster. We simultaneously compute the joint cluster parameterization and implicitly reconstruct the a priori unknown strip geometry by solving a variational problem using a discrete-continuous optimization framework. We use this parameterization to compute parametric aggregate curves whose shape reflects the geometric properties of the cluster strokes at the corresponding isovalues. We demonstrate StrokeStrip outputs to be significantly better aligned with observer preferences compared to those of prior art; in a perceptual study, viewers preferred our fitting outputs by a factor of 12:1 compared to alternatives. We further validate our algorithmic choices via a range of ablation studies; extend our framework to raster data; and illustrate applications that benefit from the parameterizations produced.
StrokeStrip: Joint Parameterization and Fitting of Stroke ClustersbyDave Pagurek van MosselB. Software Engineering, University of Waterloo, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)April 2021c© Dave Pagurek van Mossel, 2021The following individuals certify that they have read, and recommend to the Faculty of Graduate and Post-doctoral Studies for acceptance, the thesis entitled:StrokeStrip: Joint Parameterization and Fitting of Stroke Clusterssubmitted by Dave Pagurek van Mossel in partial fulfillment of the requirements for the degree of Masterof Science in Computer Science.Examining Committee:Alla Sheffer, Professor, Computer Science, UBCSupervisorLeonid Sigal, Associate Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractWhen creating freeform drawings, artists routinely employ clusters of overdrawn strokes to convey intended,aggregate curves. The ability to algorithmically fit these intended curves to their corresponding clusters iscentral to many applications that use artist drawings as inputs. However, while human observers effortlesslyenvision the intended curves given stroke clusters as input, existing fitting algorithms lack robustness andfrequently fail when presented with input stroke clusters with non-trivial geometry or topology. We presentStrokeStrip, a new and robust method for fitting intended curves to vector-format stroke clusters. Our methodgenerates fitting outputs consistent with viewer expectations across a vast range of input stroke clusterconfigurations. We observe that viewers perceive stroke clusters as continuous, varying-width strips whosepaths are described by the intended curves. An arc length parameterization of these strips defines a naturalmapping from a strip to its path. We recast the curve fitting problem as one of parameterizing the clusterstrokes using a joint 1D parameterization that is the restriction of the natural arc length parameterizationof this strip to the strokes in the cluster. We simultaneously compute the joint cluster parameterization andimplicitly reconstruct the a priori unknown strip geometry by solving a variational problem using a discrete-continuous optimization framework. We use this parameterization to compute parametric aggregate curveswhose shape reflects the geometric properties of the cluster strokes at the corresponding isovalues. Wedemonstrate StrokeStrip outputs to be significantly better aligned with observer preferences compared tothose of prior art; in a perceptual study, viewers preferred our fitting outputs by a factor of 12:1 comparedto alternatives. We further validate our algorithmic choices via a range of ablation studies; extend ourframework to raster data; and illustrate applications that benefit from the parameterizations produced.iiiLay SummaryWhen sketching, artists routinely depict intended curves using multiple overdrawn strokes. While a humancan easily envision these intended curves, current algorithms for extracting them are prone to failure. Wepresent a novel algorithm that overcomes these difficulties by calculating which points on the input strokesrepresent the same point on the intended curve. Using these connections and the order they come in, wereconstruct the intended curve. We validate the effectiveness of this algorithm by running comparativestudies against state-of-the-art algorithms and against manually drawn reconstructions.ivPrefaceAll the work presented in this thesis is a product of a working relationship between Dave Pagurek vanMossel, Chenxi Liu, Nicholas Vining, Mikhail Bessmeltsev, and Alla Sheffer.Unless otherwise specified, all implementation was done by Dave Pagurek van Mossel. Chenxi Liucreated tools used in this paper for processing and visualizing inputs and outputs, as well as for the generationof study questionnaires. Nicholas Vining assisted in editing of text, mathematical formulations, and theirproofs. Mikhail Bessmeltsev was integral to the creation of the continuous formulation of the algorithm.Help with figure creation was graciously provided by Jerry Yin and Enrique Rosales. Dave Pagurek vanMossel was provided with thoughtful guidance and editing through the entirety of the project by Alla Shefferand Mikhail Bessmeltsev.The user study in Chapter 6 was conducted with the approval of the University of British Columbia(UBC BREB Number H16-02320.)vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.1 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Solution Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Gradient Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1 Optimal Pairwise Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Global Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.1 Pairwise Impact Scores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Arc Length Cluster Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.1 Stroke-Orthogonal Cross-Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 Relaxed Joint Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Final Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4 Periodic Parameterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21vi5 Aggregate Curve Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Results and Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256.1 Comparison to Prior Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.2 Comparison to Manual Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.3 Ablation Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.4 Stress Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.5 Implementaton and Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.6 Extensions and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326.6.1 Raster Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326.6.2 Parameterization-Guided Cluster Manipulation . . . . . . . . . . . . . . . . . . . . 326.6.3 Aggregate Stroke Width . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.7 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37A Supporting Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41A.1 Study of Cluster Perception: Clusters as Strips . . . . . . . . . . . . . . . . . . . . . . . . . 41A.2 Strip Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41A.3 Comparative Study Setup Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42A.4 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42viiList of FiguresFigure 1.1 Freehand sketches use clusters of strokes (a, each cluster colorized in different color)to depict intended aggregate curves. Existing methods that aim to fit aggregate curvesto vector stroke clusters (b,c) frequently produce outputs inconsistent with artist intentand viewer expectations (e.g. nose , mouth, left eyebrow (b,c)); insets show the pointorderings they generate and use to compute fits, visualized using a red to blue colorscheme. StrokeStrip jointly arc length parameterizes each cluster (d, red to blue colorscheme), facilitating aggregate curve fitting consistent with viewer expectations (e) andintuitive cluster level editing operations (f; we deform the hair strands and the lips). . . . 1Figure 1.2 Viewers perceive stroke clusters (a) as depictions of aggregate, varying width strips,(b) whose paths (b, black) depict the intended aggregate curves and follow the averagedirection of the drawn strokes. The natural arclength parameterization of each strip (c,blue to red) induces a joint parameterization of both the clusterâs strokes (d) and theaggregate curve (e). The isolines of the parameterizations (c, d) are orthogonal to thiscurve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Figure 1.3 Viewers distinguish between pairs of stroke points that they perceive as adjacent withinthe aggregate strip (green), and those they see as far apart within it (red), despite similarpairwise Euclidean space distances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Figure 1.4 Given points densely sampled on input cluster strokes (a), methods for spline curvefitting [40] (b), 2D shape reconstruction [14] (c), and MLS based fitting [36] (d) fail tocorrectly recover the geometry (b) or topology (c,d) of the intended aggregate curves.Our method correctly recovers these intended curves (e). . . . . . . . . . . . . . . . . . 4Figure 1.5 StrokeStrip (d) successfully parameterizes (parameter values visualized using a blue tored color scheme) and fits complex stroke clusters (a) on which prior methods ([47] (b)and [38] (c)) fail to compute correct stroke point orderings (visualized using a blue tored scheme) resulting in poor output fit quality. The ordering computed by Liu et al.[38] fails to include the points colored in gray. . . . . . . . . . . . . . . . . . . . . . . . 6viiiFigure 2.1 Overview: StrokeStrip first computes compatible parameterization gradient directions(c) for all cluster strokes (a) by formulating direction choice as a binary labeling problemon a graph (b) whose nodes correspond to strokes, and whose positive and negative edgescores reflect the degree of affinity between them. It then jointly parameterizes the clus-ter using a variational framework (d-f); starting with a initial set of stroke-orthogonalcross-sections (d) it gradually obtains both a relaxed parameterization and pairwise like-lihoods (green to red) for side-by-side points on these cross-sections of being within-strip adjacent. It uses this relaxed parameterization as a starting point to compute ourfinal arc length parameterization (f), used to compute our fitted curves (g). . . . . . . . . 9Figure 2.2 Gradient orientations along individual strokes drastically impact the properties of the re-sulting parameterization: Forcing the parameterization gradients to align with arbitraryinput stroke orientations (indicated by arrows) (a) leads to parameterizations with dis-tinctly different u values at points viewers perceive as adjacent within the strip (b) , andleads to fitting outcomes inconsistent with viewer expectations (c). Our joint orientationmethod consistently orients strokes perceived as next to one another within the strip (d),leading to better parameterization (e) and fits (f). . . . . . . . . . . . . . . . . . . . . . 12Figure 3.1 Stroke pair configurations with preferred (right) and sub-optimal (left) orientation choices(arrows show orientation). Coloring visualizes the joint parameterization imposed byeach order. (a) the preferred orientation results in a parameterization that is tangentcompatible and better satisfies isoline span; (b) the preferred orientation induces a morenarrow strip; (c) the preferred orientation results in a tangent compatible parameterization. 14Figure 4.1 Arc Length Cluster Parameterization: (a) Initial stroke-orthogonal cross-sections (green),sub-sampled for visual clarity; red and orange cross-sections filtered out due to violatingtangent similarity and inter-stroke spacing respectively; (b) relaxed parameterizationsand pairwise within strip adjacency likelihoods (red low, green high) across solutioniterations; (c) final isolines and parameterization. . . . . . . . . . . . . . . . . . . . . . 17Figure 4.2 Starting with a near-optimal parameterization, (a) we minimize Earc reducing arc lengthdistortion and producing straight, gradient orthogonal isolines (c), leading to improvedfitting outcomes (b,d). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Figure 4.3 (a) Initial non-periodic parameterizations of closed-curve clusters; (b) fitting using theseparameterizations; (c) periodic parameterizations; (d) fitting using periodic parameteri-zations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Figure 5.1 Fitting alternatives: accounting for curvature, positions and tangents (d) produces fitsmore consistent with viewer expectations than when accounting for only positions (b)or positions and tangents (c). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24ixFigure 6.1 Our method successfully fits aggregate curves (d,h) to inputs (a,e) that prior methodsof Orbay and Kara [47] (b,f) and Liu et al. [38] (c,g) fail on. Input clusters highlightedin insets (a,e); visibly differently fitted clusters and curves highlighted in orange. . . . . 25Figure 6.2 Additional comparisons on complete drawings against Liu et al. [38] (top) and Orbayand Kara [47] (bottom). Insets show ordered points for prior work and cluster parame-terization for ours rendered using a rainbow color pallet. . . . . . . . . . . . . . . . . . 26Figure 6.3 While the method of Orbay and Kara [47] fails to produce a correct order (b) on theinput clusters (a) resulting in poorly fitted curves (c), our framework parameterizes (d)and fits (e) these clusters consistently with viewer expectations. . . . . . . . . . . . . . 27Figure 6.4 While the method of Liu et al. [38] fails to produce a correct order (b) on the inputclusters (a) resulting in poor fitted curves (c), our framework parameterizes (d) and fits(e) these clusters consistently with viewer expectations. . . . . . . . . . . . . . . . . . . 28Figure 6.5 Summary of comparative preferences in our perceptual study. Participants strongly pre-ferred our results over algorithmic alternatives. . . . . . . . . . . . . . . . . . . . . . . 28Figure 6.6 Parameterization and fitting output generated by (a) skipping the initial cross-sectionfiltering step (Section 4.1), (b) using the stroke-orthogonal cross-sections (Section 4.1)to initialize our final solve (Section 4.3), and (c) our method. These results demonstratethe necessity of the core steps of our method. . . . . . . . . . . . . . . . . . . . . . . . 29Figure 6.7 Impact of changing fitting weights λC (left) and λT (right). In each example the centralresult is generated with the default values and the left and right are lower and higherrespectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figure 6.8 (Top) Overdrawn letters of the alphabet and single clusters with multiple self-intersections,(bottom) correctly fitted by our method. . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figure 6.9 Our outputs on clusters with complex branching structures. . . . . . . . . . . . . . . . . 31Figure 6.10 Both vectorization [1] (b) and joint vectorization and simplification [20] (c) methodsfrequently fail to generate clean curves when presented with single raster stroke clusters(a). Using the basic vectorizations in (b) as input, we successfully fit single intendedcurves to this data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31Figure 6.11 Our parameterization (a) enables cluster level stroke manipulation tasks such as colorinterpolation (b), width scaling (c), and deformation (d). . . . . . . . . . . . . . . . . . 32Figure 6.12 In addition to curves, widths can be fitted to input stroke clusters (a) using either Dirich-let (b) or Neumann (c) boundary conditions to achieve different styles at curve endpoints. 34Figure 6.13 Our method produces meaningful results on ambiguous inputs, but these may divergefrom viewer expected ones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Figure A.1 Top: stroke clusters, bottom: Overlay of aggregate strokes, or strips, participants tracedfor each cluster in our cluster perception study. Participants demonstrated consistencyacross all inputs, confirming our hypothesis. . . . . . . . . . . . . . . . . . . . . . . . . 42Figure A.2 Question layout in our comparative study. . . . . . . . . . . . . . . . . . . . . . . . . . 43Figure A.3 To create inputs for our algorithm, strokes can be clustered using our labeling tool. . . . 44xAcknowledgmentsI would like to thank my supervisor, Alla Sheffer, without whose regular help and guidance in these uncertaintimes this project would not have been possible. Thanks as well to Mikhail Bessmeltsev, whose patientexplanations helped get this project off the ground.Thanks to Chenxi, Jerry, Enrique, and Nicholas for their help getting this project across the finish line,especially leading up to conference deadlines.Finally, I would like to thank my parents, Steve and Cheryl, and my sister, Sari, for their support.xiChapter 1Introduction(a) Input (b) [Orbay and Kara 2011] (c) [Liu et al. 2018] (d) Our ParametrizationL0(e) Our Fit (f) Cluster DeformationFigure 1.1: Freehand sketches use clusters of strokes (a, each cluster colorized in different color) to de-pict intended aggregate curves. Existing methods that aim to fit aggregate curves to vector strokeclusters (b,c) frequently produce outputs inconsistent with artist intent and viewer expectations(e.g. nose , mouth, left eyebrow (b,c)); insets show the point orderings they generate and use tocompute fits, visualized using a red to blue color scheme. StrokeStrip jointly arc length param-eterizes each cluster (d, red to blue color scheme), facilitating aggregate curve fitting consistentwith viewer expectations (e) and intuitive cluster level editing operations (f; we deform the hairstrands and the lips).1.1 MotivationWhen creating freehand sketches, artists ubiquitously employ clusters of nearby, roughly parallel strokes tocommunicate individual intended, or aggregate, curves (Figure 1.1a). They form such clusters by repeatedlyoverdrawing strokes to refine the shape of the curves they aim to convey, to emphasize or thicken thesecurves, or to add interest and texture to the drawn content [2, 18]. When presented with overdrawn strokeclusters, human observers effortlessly imagine the artistâs intended aggregate curves [38, 62]. To facilitatedownstream digital processing, artists increasingly use drawing tools that store the created raw sketches invector form. Most sketch processing applications target clean, overdrawing-free, vector drawings whereeach stroke is assumed to depict an intended meaningful curve (Figure 1.1e, Section 1.2). To process rawfreehand vector sketches, these applications rely on sketch consolidation methods which cluster strokesthat jointly depict individual intended curves, and then fit aggregate curves to each cluster [38, 39, 47].1Figure 1.2: Viewers perceive stroke clusters (a) as depictions of aggregate, varying width strips, (b)whose paths (b, black) depict the intended aggregate curves and follow the average direction ofthe drawn strokes. The natural arclength parameterization of each strip (c, blue to red) induces ajoint parameterization of both the clusterâs strokes (d) and the aggregate curve (e). The isolinesof the parameterizations (c, d) are orthogonal to this curve.Previous fitting methods successfully process clusters that depict relatively simple, low-curvature curves,but often fail to produce results consistent with human expectations on more complex inputs (Section 1.2,Figure 1.1bc). We introduce StrokeStrip, a new method for fitting intended curves to vector stroke clusterscapable of robustly generating aggregate curves consistent with human expectations on arbitrarily complexinputs (Figure 1.1e).We achieve this goal by leveraging insights about human perception of stroke clusters and aggregatecurves (Figure 1.2). We observe that viewers see stroke clusters as narrow, varying-width aggregate strokes,or strips, whose paths define the intended aggregate curves (Figure 1.2b). Human observers mentally delin-eate the outlines of the strips depicted by each cluster (Section A.1), distinguishing between points on thestrokes that are next to one another within the strip, and those adjacent only in Euclidean space (Figure 1.3).Manually traced aggregate curve data [38, 62] indicates that viewers expect aggregate curves to follow thedirection of the raw strokes, and to smoothly average the geometric properties of strokes that viewers per-ceive as being next to one another within the strip. The main algorithmic challenge in computing such curvesis therefore to identify the sets of stroke points whose shape properties jointly define the geometry of eachpoint along the fitted aggregate curve. This problem can naturally be cast as a computation of a 1D clusterparameterization whose isolines define these sets of points (Figure 1.2cd). Specifically, the parameterizationwe look for is a restriction of the natural arc length parameterization of the perceived strip (Figure 1.2c) tothe strokes in the cluster (Figure 1.2d). Given this joint parameterization of the strokes in the cluster, we candirectly compute a parametric fitted curve whose shape at each parameter value u is reflective of the averageshape (positions, tangents, and curvatures) of the cluster strokes at u (Figure 1.2e, Chapter 5).To produce fitted curves aligned with human perception, the joint cluster parameterization must satisfyseveral requirements that follow from the properties of the strip parameterizations we seek (Section 2.1).To accurately capture the geometry of the cluster strokes, we aim to compute arc length parameterizedaggregate curves; we thus aim to produce arc length preserving strip and cluster parameterizations. Theparameterizations must be continuous, and therefore isovalues at stroke points adjacent within, or inside, thestrip should be similar. Aggregate curve tangents, and consequently the gradients of the parameterizations2ââââââFigure 1.3: Viewers distinguish between pairs of stroke points that they perceive as adjacent withinthe aggregate strip (green), and those they see as far apart within it (red), despite similar pairwiseEuclidean space distances.that define them, should be aligned with the stroke tangents; in other words, parameterization isolines needto be approximately orthogonal to the strokes. The isolines should cross the clusters forming cross-sectionsthat extend from one side of the strip to the other (Figure 1.2d). Finally, since the arc length parameterizationof a strip along the gradient direction is strictly monotonic, the restriction to the strokes must be strictlymonotonic as well: parameter values along each stroke must strictly increase or decrease from one strokeendpoint to the other.The core challenge in computing a parameterization that satisfies these requirements is that we do not apriori know the strip geometry; in other words, we do not know which points on different strokes that areadjacent in Euclidean space are perceived as adjacent within the strip. Purely local analysis of point neigh-borhoods is insufficient to distinguish between points which are adjacent within the strip and ones adjacentonly in Euclidean space (Figure 1.3). Thus, while human observers can easily envision the aggregate stripsand curves corresponding to each cluster, and hence the isoline cross-sections orthogonal to these curves(Figure 1.2cd), our algorithm needs to compute these cross-sections given only the raw strokes as input. Weconsequently face two interconnected challenges: we must compute optimal isovalues along each clustercross-section while simultaneously computing the cross-sections themselves.We robustly address both challenges at once by casting the computation of the parameterization and theunderlying isoline cross-sections as a constrained variational problem (Section 2.2). We then solve this prob-lem using a combined discrete-continuous optimization framework (Section 2.3). We first determine the op-timal orientations of parameterization gradients along each stroke, converting monotonicity constraints intomore tractable inequality ones (Chapter 3). We then jointly solve for cluster cross-sections and parametervalues along them using a variational optimization framework (Chapter 4). Our method starts with an initialset of cross-sections that is expected to approximate the final one, but that might contain outliers. It narrowsthis set down using an iterated algorithm that solves for a joint cluster parameterization whose isolines areclosely aligned with a subset of these initial cross-sections, and which satisfies a relaxed variant of the prop-erties above. Finally, it uses this relaxed parameterization as a close initial guess for computing our desiredarc length cluster parameterization. The resulting method robustly handles complex cluster configurations,including self-adjacent and self-intersecting clusters (e.g. the nose, cheek, and left eyebrow in Figure 1.1).We extensively validate our design choices (Chapter 6). We compare our parameterizations and fitted3(a) Input (b) [Liu et al. 2005](c) [De Goes etal. 2011] (d) [Levin 2004] (e) OursFigure 1.4: Given points densely sampled on input cluster strokes (a), methods for spline curve fitting[40] (b), 2D shape reconstruction [14] (c), and MLS based fitting [36] (d) fail to correctly re-cover the geometry (b) or topology (c,d) of the intended aggregate curves. Our method correctlyrecovers these intended curves (e).curves to those produced by previous methods, highlighting our methodâs robustness in handling challenginginputs which cause prior methods to produce severely distorted results. We conduct a perceptual study whichshows that observers prefer curves fitted by our method over those produced by the closest competitor60.6% of the time, judge them as on par 34.6% of the time, and prefer the alternative just 4.8% of thetime. We showcase our methodâs robustness by extending it to handle raster inputs (Section 6.6.1) andto automatically detect and process clusters that depict closed curves (e.g. pupil outlines in Figure 1.1,Section 4.4). We validate our algorithmic choices via a range of ablation studies, and demonstrate theversatility of our parameterizations by showcasing their suitability for a range of other applications.These advancements are made possible by our novel approach to cluster parameterization, which lever-ages observations about human perception of such clusters and converts those into an actionable joint clusterparameterization method.1.2 Related WorkSketch Processing. User demand has led to the emergence of numerous methods and tools for processing ofvector-format artist-drawn sketches, including colorization [1, 48], shading [21, 52], style transfer [22], andediting [31], and has lead to increased use of free-hand vector sketches as inputs for high-level tasks such as3D modeling [9, 28, 37, 61]. These methods typically target clean drawings where each stroke correspondsto a complete meaningful geometric curve and cannot be applied as-is to typical raw artist drawings whichdepict such curves using clusters of overdrawn strokes [38, 39, 62]; thus processing overdrawn sketchesrequires consolidating them first.4Vector Sketch Simplification and Consolidation Vector sketch simplification methods, e.g. [24, 44], reducevisual clutter in detailed drawings by either removing or combining strokes. Vector sketch consolidationmethods identify clusters of strokes that jointly correspond to meaningful intended curves and replace eachcluster with its corresponding curve [6, 13, 38, 39, 45, 47, 51, 53]. Recent research has made significantadvances in detecting clusters that jointly depict intended curves. Once the strokes are clustered, thesemethods use either generic point-based or dedicated stroke-based fitting methods, discussed below, to fitaggregate curves to each cluster. StrokeStrip provides an alternative to these existing fitting methods. Itmakes no assumptions on the structure or other properties of the input clusters provided, and can be usedin conjunction with any stroke clustering method. We discuss how inputs were collected for this paper inSection A.4.Vectorization and Raster-Space Consolidation Raster space consolidation methods (e.g. [54, 55]) generateconsolidated raster outputs from raster overdrawn images, and require a separate vectorization step to pro-duce outputs suitable for downstream processing. Most vectorization methods convert raster inputs into vec-tor form [4, 8, 11, 16, 17, 43, 46, 50] with no attempt to simplify output topology. Recent works [7, 20, 56]aim to simultaneously consolidate and vectorize overdrawn raster sketches; however even when given in-dividual clusters as input they frequently produce complex vector graph outputs (Section 6.6). While ourmethod is designed for vector data, it can be extended to fit single curves to vectorized raster stroke clusters(Section 6.6).1D Parameterization and Curve Fitting to Points Fitting curves to ordered or 1D parameterized points is awell understood problem [19] amenable to many established methods (e.g. [5, 42]). Our problem is distinctlydifferent from this setting, as our input is only partially ordered. Specifically, while we can trivially order or1D parameterize points sampled along an individual stroke, we have no predefined ordering between pointssampled on different strokes. The isovalues of our joint 1D cluster parameterization define a completeordering of points across all strokes, allowing for subsequent use of methods that operate on ordered orparameterized points (Chapter 6). Existing research on point ordering or 1D parameterization does so in thecontext of curve fitting, discussed below.Multiple methods aim to reconstruct 2D shapes given unordered points, which are assumed to lie on ornear these shapes (Figure 1.4,b-d). Traditional fitting methods deform initial 1D curves [19], representedexplicitly [40, 60] or implicitly [63], to best approximate the input points. The output of these methodsis highly dependent on the degree of similarity between the initial and intended curves. Computing suit-able initial curves for fitting points sampled from highly bent or self-intersecting shapes remains an openproblem [60]. Thus, as noted by Orbay and Kara [47], while these methods can be applied for fittingpoints sampled from simple low-curvature stroke clusters, they fail on inputs with high curvature or self-intersections (Figure 1.4b). Classical 2D or 3D reconstruction methods ([14, 15, 23, 33â36, 49, 59]) donot constrain output topology; when presented with points sampled from our inputs, these methods oftenproduce outputs that contain multiple connected components (e.g. Figure 1.4c, bottom) and complex graphconnectivity (Figure 1.4cd). By arc length parameterizing each input cluster in 1D, we successfully and5Figure 1.5: StrokeStrip (d) successfully parameterizes (parameter values visualized using a blue to redcolor scheme) and fits complex stroke clusters (a) on which prior methods ([47] (b) and [38] (c))fail to compute correct stroke point orderings (visualized using a blue to red scheme) resultingin poor output fit quality. The ordering computed by Liu et al. [38] fails to include the pointscolored in gray.fully automatically fit each input, no matter how complex, using a single curve that is consistent with viewerexpectations (Figure 1.4e).[Kara and Shimada2007]Fitting Curves to Stroke Clusters A number of methods specifically target curve fit-ting for stroke clusters. In contexts where live feedback can be provided to artists,fits can be incrementally corrected by adding new strokes [3, 27]; however, in offlinecontexts, this cannot be relied upon. Kara and Shimada [32] and Orbay and Kara [47]first order points sampled along the stroke clusters and use the obtained full orderingto fit polylines or smooth curves to these samples. Kara and Shimada [32] project thepoints to the dominant principal axis of the cluster (computed via PCA) and use the order of these projectionsalong the axis as the point order. This approach fails even on relatively simple inputs (see inset). Orbay andKara [47] use a Laplacian spectral embedding to order the sampled points (Figure 1.1c, Figure 1.5b). Liuet al [38] propose a tangent aware Moving Least Squares (MLS) based approach for fitting curves to strokeclusters. They fit a single curve to the MLS output points by first connecting the points using a directedspanning tree, and then extracting and smoothing the longest path in this tree (Figure 1.1d, Figure 1.5c,points not included in the paths in gray). These methods often produce non-monotonic and counter-intuitivepoint orderings on clusters with sharp turns and narrow bottlenecks, leading to fitting outcomes inconsistentwith viewer expectations (Figure 1.1bc, Figure 1.5bc). Our comparisons (Figure 1.1,Figure 1.5, Chap-ter 6) demonstrate that StrokeStrip robustly computes the desired parameterizations and corresponding fitsin complex scenarios where all prior methods fail.6Chapter 2Algorithm Overview2.1 Problem StatementWe aim to robustly compute the aggregate curves viewers perceive when presented with input vector strokeclusters. Prior literature [38], observations of manually traced curves [38, 62], and our study (Section A.1),suggest that viewers perceive clusters as varying width strips formed by sweeping straight rulings, or cross-sections, along paths that follow these aggregate curves. We speculate that observers mentally envision thegeometry of these curves by interpolating shape properties along such strip cross-sections (Figure 1.2).This observation suggests that our curve-fitting problem can be recast as one of computing a 1D param-eterization of the cluster whose isolines define these cross-sections. Given this desired parameterization, wecan express the shape of the fitted curve at each parameter value u as a function of the shape properties ofthe stroke points along the u-isoline cross-section (Chapter 5). In addition to facilitating fitting, our parame-terizations provide a natural mechanism for jointly manipulating the strokes within the cluster (Figure 1.1f,Chapter 6).To formalize the desired properties of the parameterization we seek, we first formalize the notion of astrip itself. A strip is well-described by its centerline γ(t) â R2, parameterized by its arclength t â [0,L],and width W (t). Reminiscent of ruled surfaces in 3D, the strip is then defined as the set of points swept bya moving line segment of length W (t), centered at and perpendicular to the centerline. The two sides of astrip are then the two curves at the distance of W (t)/2 from the centerline in the normal direction, or moreformally γ(t)± W (t)2 n(t).While this definition addresses non-self-intersecting strips, in general strips can and often do self-intersect. This technical difficulty, however, is easy to overcome by considering the curvilinear strip asan image of a locally injective map of an axis-aligned strip, namely the parameterization domain. We omitthis for brevity; this reasoning, as well as our algorithm, admits self-intersecting strips.u=constThis construction naturally defines the arc length parameterization of a strip as theextension of the arc length parameterization of the centerline to the whole area of thestrip via âextrusionâ in the normal direction (see inset). Simply put, it is a function u(x)defined for all points in the strip, such that straight line segments C(t) = {γ(t)+an(t)|a â7[âW (t)2 , W (t)2 ]} are the parameterizationâs isolines; that is, they share the same parameter value t = u(x),x âC(t).The arc length parameterization of a given a strip defined by its centerline and width can be explicitlycomputed (Section A.2). A trivial, yet important, property of the arc length parameterization of a strip isthat, for any point on the isoline C(t), the parameterization gradient is parallel to the centerline tangent Ï(t).The norm of the gradient, while unit at the centerline, changes depending on the distance from the centerlineand centerline curvature. It is easy to show, however, that the average of parameterization gradients overeach isoline has unit length and thus coincides with the centerline tangent (see Section A.2 for a proof).Returning to the problem of a stroke cluster parameterization, given a set of oriented strokes S = {si, i=1, . . . ,N}, we are looking for a map u(x) : âªisiâ [0;L], where L is unknown; that is, the restriction of thearc length parameterization of the viewer-perceived strip.An important subtlety in parameterizing stroke clusters lies in correct generaliza-tion of the notion of strip centerline. Prior sketch processing research [38, 61] repeat-edly suggests that viewers perceive the tangents of drawn strokes to be more accu-rate than their exact locations. This suggests that viewers do not expect the aggregatecurves, or strip paths, to follow the clusterâs centerline, i.e. to be strictly equidistantfrom the clusterâs outermost side strokes (inset, red), but rather, expect them to align with the stroke tangents(inset, green). Based on these observations, we prioritize tangent alignment over centrality when computingthe strip parameterizations and paths.We are thus looking for a stroke cluster parameterization that is a restriction of the arc length parame-terization of the aggregate strip. While the strip itself is unknown, the observations above suggest that itsrestriction to the strokes in the cluster should satisfy the following properties:Tangent Alignment: The gradient of the arc length parameterization of a strip is parallel to the path tan-gent; the path tangent is, in turn, expected to be closely aligned with the stroke tangents along each isoline.We thus expect all pairs of within-strip adjacent points p, pâ² belonging to different strokes, where p, pâ² isorthogonal to the path tangent, to have the same iso-value u; in other words, we expect the parameterizationisolines to be approximately orthogonal to the stroke tangents at stroke points along the isoline.Arc Length Preservation: As outlined above, the gradient of the arc length parameterization of a strip,averaged over an isoline, has unit norm. We expect the same property from the arc length parameterizationof a cluster.Monotonicity: The arc length parameterization of a strip is, by definition, strictly monotonic along itsgradient direction. We thus expect the parameter values u to strictly monotonically increase (or decrease)along each individual stroke. We note that, combined with tangent alignment, monotonicity implies that thegradients of u at all stroke points along each isoline should have similar directions.Isoline Span: We define pairs of points p, pâ² on different strokes as side-by-side if the line p, pâ² isorthogonal to either Ï(p) or Ï(pâ²). Perception and consolidation research suggest that, absent evidence tothe contrary, viewers perceive side-by-side stroke points with similar stroke tangents as adjacent within thestrip [38]. Combined with tangent alignment, the isoline span property suggests that, absent a conflict withthe properties above, we expect all side-by-side pairs of points to be adjacent within the strip, and thus to8have similar u values in our parameterization.We refer to a cluster parameterization satisfying all these requirements as joint. We formally expressthese requirements as a combination of an objective function and a set of constraints, as described next.(a) Input (e) Relaxed Parameterization (g) Curve Fitting(f) Final Parameterization(b)-111-111(d) Stroke-Othogonal Cross-SectionsGradient Orientation Arc Length ClusterParameterization(c)Figure 2.1: Overview: StrokeStrip first computes compatible parameterization gradient directions (c)for all cluster strokes (a) by formulating direction choice as a binary labeling problem on a graph(b) whose nodes correspond to strokes, and whose positive and negative edge scores reflect thedegree of affinity between them. It then jointly parameterizes the cluster using a variationalframework (d-f); starting with a initial set of stroke-orthogonal cross-sections (d) it graduallyobtains both a relaxed parameterization and pairwise likelihoods (green to red) for side-by-sidepoints on these cross-sections of being within-strip adjacent. It uses this relaxed parameterizationas a starting point to compute our final arc length parameterization (f), used to compute our fittedcurves (g).2.2 FormulationWe formulate our objective using the following derivation. For a non self-intersecting stripS â R2, its arclength parameterization u :S â R is the minimizer of the following variational problem:minuâ« L0â¥â¥â¥â¥ 1W (t)â«C(t)âu(x)dxâ Ï(t)â¥â¥â¥â¥2 dt, (2.1)where the outer integral is with respect to t, the arc length of the strip centerline; the inner integration isover each straight line cross-section C(t) with length W (t), crossing the strip perpendicular to the centerline,as defined in Section 2.1 (see Section A.2 for a proof). However, applying this formulation as-is to strokesis problematic since âu is not clearly defined. We recall that the arc length parameterization satisfies thefollowing properties: its gradient is always parallel to the centerline tangent, and its average over each gra-dient orthogonal cross-section has unit length. Thus instead of minimizing Equation 2.1 we can equivalentlyminimize the projections of the expression inside the norm onto the centerline tangent and normal. Sincefor the arc length strip parameterization â u(x) · n(t) = 0 at every point x and its corresponding centerlineparameter t, and ( 1W (t)â«C(t)âu(x)dxâ Ï) · Ï = 1W (t)â«C(t)âu(x) · Ïdxâ1, the expression for u in Equation 2.1has the same minimizer as the following:â« L0â£â£â£â£ 1W (t)â«C(t)âu(x) · Ï(t)dxâ1â£â£â£â£2 dt+â« L0â«C(t)|âu(x) Â·n(t)|2dxdtThese terms are much more amenable to computation on stroke clusters, since âu(x) · Ï(t) can be well9approximated by the directional derivative of u along each stroke, and âu(x) · n(t) can be approximatedusing samples on different strokes that are within-strip adjacent along the normal direction.This formulation relies on the notion of a path tangent Ï and a normal n, which are unknown. However,if we were given the cross-sections C(t), we could approximate Ï as the averages of stroke tangents Ï alongeach cross-section and replace the normal n with the vector perpendicular to Ï , denoted n. Our formulationthen becomes,Elength =â« L0â£â£â£â£ 1W (t)â«C(t)âu(x) · Ï(t)dxâ1â£â£â£â£2 dt (2.2)Ealign =â« L0â«C(t)|âu(x) Â·n(t)|2dxdt (2.3)minuEarc = minu(Elength+Ealign) (2.4)Here Elength promotes arc length preservation, while Ealign promotes tangent alignment.2.2.1 DiscretizationWe discretize the combined energy function Earc and solve for the parameter values at densely sampledpoints along the cluster strokes that jointly minimize it as follows.Notation: We discretize input strokes as densely-sampled polylines (Section A.4). A sample on an inputstroke s then can be described as {s, i}, where i refers to the sample index. We denote the sample position asps,i, its unit tangent as Ïs,i, and the unknown parameter value as us,i. For brevity, when referring to genericpoint samples, we drop the indexing and use p to describe positions and Ï(p) to describe unit tangents.Finally, we encode a cross-section C(u) as a sequence of point samples C = {a}= {(s, i)}.We convert the integral formulation above into a finite summation by using a finite set of isoline cross-sections C(u), defined for a dense set of parameter values u. We define the cross-section tangent as:Ï(C) :=â(s,i)âC ds,i osÏs,iâ¥â¥â(s,i)âC ds,i osÏs,iâ¥â¥ (2.5)Here os â {1,â1} is a per-stroke direction variable indicating whether the parameterization gradient atstroke s is expected to be ascending (os = 1) or descending (os = â1) with respect to the original strokeorientation. Each tangent in this sum is weighted by the size of the dual cell of the corresponding pointalong the cross-section: If (sâ², iâ²),(s, i),(sâ²â², iâ²â²) are three consecutive points along the cross-section, thends,i = 12(â¥â¥psâ²,iâ²â ps,iâ¥â¥+â¥â¥ps,iâ psâ²â²,iâ²â²â¥â¥).The finite difference discretization of Equation 2.2 then yields:Elength(u) =âC(â(s,i)âCds,iDC(us,iâus,iâ1)Ïs,ils,i· Ï(C)â1)2, (2.6)where we normalize the sum by the length of the cross-section DC = â(s,i)âC ds,i, i.e. a discretization of10W (t), and ls,i is the length of a segment along the polyline: ls,i = âps,iâ ps,iâ1â.The discretization of Equation 2.3 yields:Ealign(u) =12âC âa,bâC(uaâubâ Ï(C) · (paâ pb))2 (2.7)We solve for the u values that minimizeEarc = Elength+Ealign (2.8)subject to monotonicity constraints, expressed as(us,iâus,iâ1)os â¥ ls,i2 âs, i. (2.9)Our choice of a right-hand side value that reflects the local sampling density along each stroke makesthe constraints robust to uneven sampling density, and encourages more uniform velocity.Last but not least, we fix the parameter interval in place, by constraining the parameter value of a singlestroke point u0,0 = 0.2.3 Solution OverviewWe seek the minimizer of the constrained optimization problem above. This requires solving for three setsof variables: the parameter values at all stroke points, the gradient orientations along strokes, and the setsof stroke points on each isoline cross-section. Accounting for the two latter sets of discrete variables whilecomputing the parameterization gives rise to a difficult mixed discrete-continuous optimization problemwhich cannot be addressed using standard optimization strategies. We obtain the desired minimizer byemploying a tailored solution mechanism that leverages the unique properties of our problem.We recall that tangent alignment requires stroke gradient orientations along each isoline to be similar,and that the isoline span property suggests that most side-by-side points on adjacent strokes should havesimilar isovalues. Since stroke tangents are expected to change gradually, these properties suggest that theoriented tangents at most side-by-side points should point in the same direction (Figure 2.1b, Figure 2.2).We use these observations to compute gradient orientations os along all strokes as a first step toward comput-ing the parameterization (Chapter 3, Figure 2.1b). We obtain the orientation choices that optimize directedtangent similarity across all pairs of side-by-side points, and are therefore likely to allow for maximallywide isoline span. We formulate the computation of the desired orientations as a binary graph labeling prob-lem, where the edge weights reflect the likelihood of pairs of strokes to share side-by-side points adjacentwithin the strip. With the orientations computed, our monotonicity constraints (Eq. (2.9)) become simpleinequalities, simplifying the rest of the processing.Our core parameterization step computes the desired arc length cluster parameterization by solving forthe cross-section isolines C(u) and the isovalues along them (Chapter 4). Specifically, we first identifyan initial set of side-by-side points likely to be within-strip adjacent by forming stroke-orthogonal cross-11(a) (b) (c) (d) (e) (f)0LFigure 2.2: Gradient orientations along individual strokes drastically impact the properties of the re-sulting parameterization: Forcing the parameterization gradients to align with arbitrary inputstroke orientations (indicated by arrows) (a) leads to parameterizations with distinctly different uvalues at points viewers perceive as adjacent within the strip (b) , and leads to fitting outcomes in-consistent with viewer expectations (c). Our joint orientation method consistently orients strokesperceived as next to one another within the strip (d), leading to better parameterization (e) andfits (f).sections (Figure 2.1d, Section 4.1). These cross-sections join together points that are largely expected tohave similar isovalues in our target parameterization, but that may not satisfy tangent alignment. We solvefor a relaxed joint parameterization that is arc length preserving and assigns similar values to within-stripadjacent points on these cross-sections, subject to monotonicity constraints (Section 4.2). Specifically, weassociate within-strip adjacency likelihood variables with each pair of points along the cross-sections andsimultaneously solve for parameter values and likelihoods. The minimizers of our relaxed formulationclosely approximate the optimal solutions we seek, and we therefore use them as initial guesses for a localoptimization step that generates our desired final parameterizations (Section 4.3). Finally, and optionally,we evaluate the likelihood that our input clusters depict closed curves, and for clusters that do, we computea periodic parameterization (Section 4.4).12Chapter 3Gradient OrientationThe first stage of our algorithm assigns a gradient orientation oi â {â1,1} to each stroke i in the cluster.Intuitively, we seek orientations that maximize tangent alignment, i.e. result in similar tangent directionsoiÏ(pi) and o jÏ(p j) at side-by-side points pi and p j on strokes i and j that viewers perceive as adjacentwithin the strip (Figure 2.2). While we do not a priori know which side-by-side points are within stripadjacent, we aim to maximize isoline span by maximizing the overall number of side-by-side points withsimilar tangent directions. Maximizing tangent direction similarity at such points increases the likelihoodof these points having similar isovalues in the output parameterization (Figure 2.2, Figure 3.1).We note that any strip allows for two equal quality parameterizations with inversely oriented gradients.We address this degree of freedom by arbitrarily setting o0 = 1. Our problem can now be recast as oneof solving for o1, . . . ,oN that, jointly with o0, best satisfy the requirements above. In the following, wefirst consider the optimal choice of orientations for a cluster consisting of a single stroke pair (Section 3.1,Figure 3.1), then generalize the problem formulation and solution method to clusters with multiple strokes(Section 3.2).3.1 Optimal Pairwise OrientationGiven a pair of strokes si and s j, we keep oi fixed and cast the problem of computing o j as one of findingthe pairwise orientation compatibility oi j â {â1,1} (where 1 indicates similar and -1 indicates opposite)such that the j-th stroke orientation o j = oi joi maximizes the quality of the parameterization of a clusterthat consists of only these two strokes . We choose the optimal solution by evaluating the properties ofthe parameterizations that each of the two choices induces, accounting for the following considerations,illustrated in Figure 3.1:Tangent Compatibility: We consider a parameterization whose isoline cross-sections include points onboth si and s j to be compatible if the angle between the oriented tangents oiÏi(p) and oi joiÏ j(pâ²) along allcross-sections C = (p, pâ²), where p â si and pâ² â s j, is below 90â¦ (Figure 3.1ac). This requirement followsfrom the combination of our monotonicity and tangent alignment properties.13Figure 3.1: Stroke pair configurations with preferred (right) and sub-optimal (left) orientation choices(arrows show orientation). Coloring visualizes the joint parameterization imposed by each order.(a) the preferred orientation results in a parameterization that is tangent compatible and bettersatisfies isoline span; (b) the preferred orientation induces a more narrow strip; (c) the preferredorientation results in a tangent compatible parameterization.Isoline Span: To best satisfy the isoline span property, we prioritize tangent-compatible parameterizationswith isolines that span both strokes over those that do not (Figure 3.1a).Narrowness: Given two tangent compatible parameterizations induced by the twochoices of oi j that include cross-sections that span both strokes (see inset), we prioritizethe parameterization with the shortest cross-section. This preference is motivated by theexpectation that human observers interpret clusters as narrow strips [38]; thus, giventwo alternatives, they prefer a more narrow interpretation (Figure 3.1b).As we prefer parameterizations that satisfy the isoline span requirement, we firstassess if each orientation choice oi j allows for a tangent compatible parameterizationwhose cross-sections span both strokes. If both allow for compatible parameterizations,we choose the orientation that induces more narrow strips (Figure 3.1b). If only oneorientation allows a compatible parameterization that satisfies the isoline span property,we use this orientation choice (Figure 3.1a). If no orientation choice allows for a param-eterization that satisfies both properties, we locate the closest pair of endpoints on thetwo strokes i and j, and compute oi j that minimizes the difference between the orientedtangents at these endpoints (see inset). This choice induces a strip geometry in whichone stroke is the continuation of the other (Figure 3.1c).Proxy Parameterization. A possible approach to evaluate the impact of each choice ofoi j is to directly compute the parameterization it induces (Chapter 4), and then assess the result with respectto the properties above. Such a computation is time consuming, and can be replaced by a much faster proxyparameterization computation that is sufficient for our needs. Specifically, we note that the criteria above arebased only on cross-section width and span, and tangent similarity at cross-section endpoints. Accordingly,instead of computing a full parameterization, we form a set of tentative cross-sections and use them forassessing both properties.For each choice of o j, we first compute tangent compatible, stroke-tangent-aligned cross-sections. Wethen extend the proxy parameterization they induce along the rest of the strokes by introducing additionalwell-spaced cross-sections. Since tangent alignment advocates for cross-sections to be orthogonal to the14strokes, we form our first set of cross-sections by shooting orthogonal left and right rays fromevenly sampled points p on each stroke s â si,s j and recording the intersections pâ² of theserays with the other stroke. We add p, pâ² to the set of cross-sections if the following is satis-fied: (1) the oriented tangents at the two points p and pâ² satisfy tangent compatibility, and (2)the orthogonal to the second stroke at pâ² intersects the stroke s. If this test fails (see inset,p, pâ² in blue), p is not viewed by observers as being next to pâ². If the set of cross-sectionscomputed this way is empty, the assessed orientation does not allow for a tangent-compatibleparameterization.â®â®Given a non-empty set of stroke-orthogonal cross-sections (inset, blue and red) weleverage the expectation that output parameterization should be arc length preserving tointroduce cross-sections through all points p on the two strokes than are not currentlypart of a cross-section (orange and cyan in the inset). For each such point p, we locatethe nearest cross-section endpoint p along its underlying stroke s. We use the cross-section p, pâ² to pair the point p with a point pâ² located at the same signed arclength distance from pâ² as p isfrom p (see inset, green and orange, right). If cross-sections added this way violate tangent compatibility,the assessed orientation does not allow for a compatible parameterization.3.2 Global Solutions1s0s2o0,2=1o1,2=1o0,1=1o1,2=1s0o0,1=1o0,2=-1s1s2A brute force approach for obtaining the orientations resulting in the best parameteriza-tion for larger clusters would be to compute proxy parameterizations for each possibleorientation combination and to select the best combination using similar criteria to onesabove. However, this approach is clearly too computationally expensive. We compute a setof orientations that leads to high quality parameterizations by noting that, given a clusterwith more than two strokes, pairwise preferences, computed independently for each pairof strokes in the cluster, are strongly suggestive of the globally optimal orientation choice.More specifically, when all pairwise preferences are compatible (inset, top), using thesepreferences as-is leads to the desired outcome; however, when the preferences are globally contradictory(inset, bottom), we can still reliably predict which pairwise choices are more likely to impact the globaloutcome by assessing the geometry of each pair as detailed below. These observations motivate our solutionapproach: we first compute compatible orientations for each pair of strokes in the cluster (Section 3.1).We then use these pairwise choices and their predicted impact on the overall parameterization quality tocompute the orientation choices across the entire cluster.FormulationFor each pair of strokes, we compute pairwise orientation compatibilities oi j â {â1,1} as described inSection 3.1. We associate with each pair an impact score wi j, indicating how critical satisfying orientationcompatibility for this pair is for optimizing the quality of the overall output parameterization. Using thesevalues, the optimal set of orientations is given by the solution to the following mixed-integer quadratic15programming (MIQP) problem:minoiâ{â1,1}nâ1âi=1nâj=i+1oi jwi j(oiâo j)2 (3.1)We compute the optimal variables oi using the integer programming solver provided by the Gurobi opti-mization toolbox [29]. For simplicity, instead of keeping track of the per-stroke orientations in the rest ofthe computation, for each stroke with oi =â1, we flip the stroke orientation. In the rest of the computation,we use the directed stroke tangent as-is for all computations and require the gradient of u to be positivealong all strokes.3.2.1 Pairwise Impact ScoresWhen determining the importance of each individual pair satisfying the pairwise orientation relation com-puted in Section 3.1 within the global parameterization, we consider similar factors to those used in consoli-dation literature when assessing how likely strokes are to belong to the same cluster [38]: tangent similarity,distance, and the relative length of their side-by-side sections compared to their overall length. As weaim for a globally tangent-aligned parameterization, we prioritize pairs which demonstrate stronger tangentalignment along shared cross-sections; since we aim for narrow clusters, we prioritize pairs with shortercross-sections; and lastly, we prioritize pairs which have a larger percentage of points on shared cross-sections. Given all cross-sections computed in Section 3.1, which we denote by â¦, we compute the averageangle between cross-section endpoint tangents asÏi j =1|â¦| â(a,b)ââ¦arccos(oi jÏi,a · Ï j,b).We set the alignment score wËi, j as,wËi, j =ï£±ï£´ï£´ï£´ï£²ï£´ï£´ï£´ï£³1, Ï < Î±mineâ(ÏâÎ±min)22Ï2 , αmin â¤ Ï < αmax0, αmax â¤ Ï(3.2)Following perception studies that indicate that observers see lines as parallel when the angle between themis under 20â¦ [30], we set αmin = 10â¦ and αmax = 20â¦, and use the three sigma rule to set Ï = (Î±maxâÎ±min)/3to allow a smooth fall off. If |â¦|= 0, we set wËi, j = 0.We define the impact score wi j aswi j =wËi, j + Îµ1+min(a,b)ââ¦ âaâbâ2max{ |â¦|min(Ni,N j),12}where ε = 10â2 and Ni,N j are the total numbers of samples on the respective strokes used in our parameter-ization computation above.16Chapter 4Arc Length Cluster ParameterizationThe energy function we aim to minimize (Equation 2.8) is non-linear and, in the general case, non-convex.Most importantly, this function is defined via the cross sections which are a priori unknown; consequently,minimizing it â or even assessing it â requires identifying points on different strokes that belong to thesame cross-section. In doing so, we face two chicken and egg problems. First, we expect the cross-sectionsto be orthogonal to the parameterization gradient, but we need a parameterization to compute this gradient.Second, we expect our cross-sections to lie entirely inside the envisioned strips; however, we do not a prioriknow the strip geometry, and thus the strip outlines.We address all these challenges using the following three-step process. We first note that tangent align-ment suggests that stroke tangents can often serve as a plausible proxy for parameterization gradients. Tothis end, we initialize our parameterization computation using stroke-orthogonal cross-sections, rather thangradient orthogonal ones (Section 4.1, Figure 4.1a). When computing these cross-sections, we aim to max-imize isoline span while keeping the cross-sections contained as much as possible within the perceivedstrips. We thus form maximally long cross-sections, absent evidence of them connecting points which arehighly unlikely to be adjacent within the strip (Figure 4.1a). We expect most, if not all, points on theseFigure 4.1: Arc Length Cluster Parameterization: (a) Initial stroke-orthogonal cross-sections (green),sub-sampled for visual clarity; red and orange cross-sections filtered out due to violating tangentsimilarity and inter-stroke spacing respectively; (b) relaxed parameterizations and pairwise withinstrip adjacency likelihoods (red low, green high) across solution iterations; (c) final isolines andparameterization.17cross-sections to be within-strip adjacent, and thus aim for them to have similar isovalues; we do not, how-ever, expect these cross-sections to be strictly gradient orthogonal. Motivated by these observations, weintroduce a relaxed, outlier-robust parameterization formulation that aims to jointly minimize both the arclength distortion along the cluster strokes and a relaxed alignment term, which seeks to assign similar valuesto a maximal subset of point pairs on common cross-sections which are deemed as likely to be within-stripadjacent (Figure 4.1b, Section 4.2). The parameterization that minimizes this relaxed energy serves as a suit-able initial guess for computing our target joint parameterization which strictly satisfies tangent alignment(Section 4.3, Figure 4.1c).We extend the method to detect and parameterize clusters that jointly depict closed curves (Section 4.4).4.1 Stroke-Orthogonal Cross-SectionspTo form stroke-orthogonal cross-sections, we densely sample points p alongeach stroke (black in the inset, gray arrows indicate tangent directions), shootstroke-orthogonal left and right rays from each sampled point, and computethe intersections of these rays with all cluster strokes. Notably, some of theseintersections may not be adjacent to the source point p within the strip. Wefilter such points out using a combination of local and contextual filters.Specifically, we form initial stroke-orthogonal cross-sections C(p) comprised of the sample p and allray-stroke intersections pâ² that satisfy the following three criteria (green in the inset):Tangent Compatibility: Tangent alignment implies that stroke tangent orientations along each cross-section should form angles of under 90â¦. We therefore only include ray-stroke intersections pâ² in C(p)if the angle between the oriented stroke tangents at p and pâ² is smaller than 90â¦ (in the insets, the red inter-sections do not satisfy this property).p'p40°Tangent Similarity: Tangent alignment suggests that stroke tangents at consecutivepoints pâ² and pâ²â² along the rays forming our cross-sections should be similar. Percep-tual literature [30] and consolidation research [38] indicate that human observers areunlikely to see lines as parallel if the angle between them exceeds 20â¦. We thereforeonly include ray-stroke intersections pâ² in C(p) if the angle between the oriented stroketangents at pâ² and pâ²â² is below this threshold (in the inset, the blue intersection does notsatisfy this property).Connectedness: We expect strips and hence cross-sections to be continuous. Thus, given three consecutivepoints a,b,c along the ray, if a and b are not adjacent within the strip, then neither are a and c. We thereforeonly include intersections pâ² in C if all ray-stroke intersections along the segment ppâ² satisfy both alignmentand similarity.18pSpacing: This local filtering resolves the most common scenarios of cross-sectionsextending outside the intended strip, but does not address cases where a ray intersectstwo or more separate similarly oriented sections of an intended strip (see inset). We re-quire a principled way to identify and resolve such configurations. We note that humanobservers are likely to separate parallel stroke groups from one another when the dis-tance between these groups along the stroke orthogonal direction is significantly biggerthan the inter-stroke distances within the groups [38, 58].In our context, this observation argues for separating distinct side-by-side strip sections by assessingdistances between pairs of consecutive intersections {pâ², pâ²â²} along the rays; if the distance dpâ²,pâ²â² = âpâ²â pâ²â²âbetween one pair of points is much larger than the distances between other consecutive pairs in its vicinity,this suggests that the segment pâ², pâ²â² is likely to be outside the strip. We employ a conservative version of thiscriterion, and compare the distance between consecutive ray intersections to the widths of entire adjacentcross-sections. We define the neighborhood of a cross-section C of width W as the set of all cross-sectionswith points at a distance less than W from any c âC. We compute the median cross-section width Wc withinthis neighborhood. For each pair of consecutive intersections {pâ², pâ²}â² in C where pâ² is closer to the rayorigin p, if dpâ²,pâ²â² >Wc(1+Smax) we remove pâ²â² (pink in the inset) from the cross-section (we set Smax = .2).We satisfy connectedness by removing from C all points along the ray that are further away from the originthan pâ²â².4.2 Relaxed Joint ParameterizationOur initial set of stroke-orthogonal cross-sections defines, for each stroke point, a set of side-by-side po-tentially within-strip adjacent points on neighboring strokes. We use these sets to compute a relaxed jointparameterization, which promotes arc length preservation along each strokes and minimizes parameter valuedifferences between side-by-side points on different strokes which are likely to be adjacent. This parame-terization closely approximates our target joint parameterization, and thus serves as a good initial guess forcomputing it (Section 4.3).We formulate the goal of our relaxed joint parameterization u as:minuErelaxed = Elength(u)+Esimilar(u) (4.1)Esimilar(u) =12âC âa,bâCL(a,b)(uaâub)2, (4.2)where Elength is defined by Equation 2.6, L(a,b) measures the likelihood of the points a,b to be within-stripadjacent, and Esimilar(u) promotes assigning similar isovalues to side-by-side points which are likely to beadjacent within the strip.Our formulation of L(a,b) is motivated by the following observations. Since strips allow for a strictly arclength preserving parameterization, we expect the values of both our target and relaxed energies to evaluateto near zero given the optimal parameter values u. Thus, given either the target or relaxed parameterizations,we expect the parameter space distance between nearby within-strip adjacent points to be close to zero; ergo19the farther apart such points are in parameter space, the less likely they are to be adjacent within the strip.Thus, the difference between u values at points along the same stroke-orthogonal cross-section can be usedas a predictor of within-strip adjacency between them. Based on this observation, given a pair of pointsa and b along a common stroke-orthogonal cross-section C, we define the likelihood that these points areadjacent within the strip as:L(xa,xb) = eâ(uaâub)22Ï2 . (4.3)We set Ï = L/30, using the three-sigma rule: we consider points with u values more that 1/10th of theentire parameter space length apart as unlikely to be adjacent.Solution. We compute Ï(C) on the initial cross-sections and keep it fixed throughout the iterations. We thenfind the parameterization u that minimizes Erelaxed by using alternating local-global optimization iterations.Our local step computes the likelihoods L(a,b) for every pair of points (a,b) â C based on the currentparameter values u. Our global step keeps these likelihoods fixed, and uses them to compute the parametervalues u that minimize Erelaxed (Equation 4.1). With Ï(C) and L(a,b) fixed, the energy function minimizedin each global iteration becomes a simple quadratic function, which needs to be minimized subject to linearinequality constraints. We solve the QP problems posed by each iteration using the interior-point methodimplementation in the CVX optimization toolkit [25, 26].The steps are iterated until convergence; specifically, we terminate once the largestchange in parameter values u, across all participating stroke points, drops below 1/2 ofthe strokeâs width. Our method typically takes at most seven iterations to converge. Theaverage per-cross-section energy in each step for the cluster in Figure 4.1b is shown inthe inset.Initialization To obtain an initial outlier-robust guess for u, we minimize Erelaxed using a set of fixed smalllikelihood values L(a,b) = L0 = 10â5, and rewriting Esimilar (Equation 2.7) to use the L1-norm, which isknown to be less sensitive to outliers:Esimilar(u) =12âC âa,bâCL0|uaâub|This formulation strongly prioritizes arc length preservation (Figure 2.1e, Figure 4.1b). Notably since theminimizer of Erelaxed is expected to minimize both Elength and Esimilar independently, we expect the values uaand ub in the output to only diverge in the vicinity of stroke-orthogonal cross-sections that join points whichare not within-strip adjacent.4.3 Final ParameterizationWe use the relaxed joint parameterization computed in the previous step as an initialguess for minimizing Earc (Equation 2.8) subject to monotonicity. At each iteration,we form cross-sections C(u) by evenly sampling the current parameterization u and20InputFinal Parameterization(a) (b) (c) (d)Figure 4.2: Starting with a near-optimal parameterization, (a) we minimize Earc reducing arc lengthdistortion and producing straight, gradient orthogonal isolines (c), leading to improved fittingoutcomes (b,d).Figure 4.3: (a) Initial non-periodic parameterizations of closed-curve clusters; (b) fitting using theseparameterizations; (c) periodic parameterizations; (d) fitting using periodic parameterizations.grouping all stroke points with the corresponding isovalues. We solve the resultingQP problems using the mechanism described in Section 4.2. We require at most two iterations to convergeto a desired solution, using the same convergence criterion as in Section 4.2 (Figure 2.1c, Figure 4.1, Fig-ure 4.2). The average per-cross-section energy for the cluster in Figure 4.1c is shown in the inset, with theresult of Section 4.2 as iteration 0.4.4 Periodic ParameterizationThe framework described so far produces open curve parameterizations, whose parameter extrema are typ-ically located far apart. While individual strokes drawn by artists in standard drawing software are usuallyopen, clusters of strokes can and do frequently depict closed intended curves (e.g. eye pupils in Figure 1.1).We support optional periodic parameterization of such clusters by first identifying them, and then by repa-rameterizing each such closed curve cluster by enforcing periodicity and selectively relaxing monotonicityrequirements. The benefit of such a parameterization for aggregate curve fitting is illustrated in Figure 4.3.21Closed-Curve Clusters In detecting closed-curve clusters, we leverage the observation that, for a directedgraph with closed cycles, one can reach any cycle vertex from any other by following the edge directions.Extending this logic to clusters, if a cluster depicts a closed curve, then once the periodic parameterizationis computed, we expect to be able to reach each stroke point from another by following the parameterizationgradient. In practical terms, this means that given a graph that consists of directed edges connecting pointswith consecutive isovalues along the same stroke, and connecting points on different strokes that share thesame isovalue, a cluster is a closed curve if, and only if, we can compute a directed path in this graph fromeach point sample to another. Notably, given a nonperiodic parameterization, such paths only exist fromsamples with a lower parameter value to those with a higher one.We assess the potential for a parameterized cluster to be a closed-curve cluster by looking for paths ina graph that, in addition to the edges above, contains orthogonal edges: edges that connect immediatelyadjacent points p and pâ² that have similar parameterization gradients but different parameter values andwhere the line p, pâ² is approximately orthogonal to the gradients at both points. We note that this propertyis well satisfied by edges connecting ray seed points on our initial set of cross-sections and their immediateneighbors within these cross-sections (Section 4.1). We thus add these edges to the graph.We classify a cluster as closed-curve if the resulting graph allows for a directed path from a point withthe maximal parameter value to one with the minimal one. Note that once this is the case, this property willhold for all other pairs of points.Periodic Reparameterization If a cluster is deemed closed, we parameterize it once more (Section 4.3)with the following adjustments.We estimate the parameterization period P as the biggest difference in parameter values between theend-points of the computed orthogonal edges. We then recompute a set of isolines such that for each value uthey contain all points with this isovalue modulo P. We locate the isoline with the largest u value, and relaxthe monotonicity constraints between points on this isoline and the consecutive sample points on the strokesthey are on. We then perform one iteration of minimizing Earc (Equation 2.8). All subsequent iterationsproceed as described in Section 4.3.22Chapter 5Aggregate Curve FittingWe aim to fit aggregate curves XË(u), u â [0,L] to input clusters such that the curve shape at a parametervalue u is reflective of the average shape of the clusterâs strokes at the u iso-value. Prior literature [38, 61]suggests that viewers perceive the tangents of artist drawn strokes as more accurate than their exact loca-tion, motivating us to explicitly account for tangents in our framework, and to prioritize tangent alignmentover average position preservation. Our observations further indicate that viewers expect the curvature ofthe fitted curve to be reflective of that of the underlying strokes. In particular, while the average tangentorientation can change abruptly near stroke endpoints (Figure 5.1a), human observers expect the change inthe tangent of the fitted curve (its curvature) to be more gradual when the curvature of these strokes is low(Figure 5.1d).We consequently formulate curve fitting as an optimization balancing three terms: curvature preserva-tion, tangent alignment, and average position preservation (Figure 5.1d). In other words, we seek a curveXË(u) that minimizesXË(u) = argminXËâ« L0(â¥â¥â¥XË(u)â p(u)â¥â¥â¥2+Î»1â¥â¥â¥TË (u)â Ï(u)â¥â¥â¥2+Î»2â¥â¥â¥KË(u)â k(u)â¥â¥â¥2)du (5.1)Here, TË (u) and KË(u) are the unit length tangent and curvature of the curve XË(u) at u, λ1 and λ2 areweights controlling the relative impact of the different terms, Ï(u) is the average of the tangents of strokesamples along the u isoline C(u), computed per Eq. (2.5), p(u) is the average of the positions of strokesamples along the u isoline,p(u) =1|C(u)| â(s,i)âC(u)ps,i,and k(u) is the average of the curvature values at these samples,k(u) =1|C(u)| â(s,i)âC(u)(Ïs,i+1â Ïs,iâ1) · Ïâ¥s,iâps,iâ ps,iâ1â+âps,i+1â ps,iâ23(a) Input (b) Positions (c) + Tangents (d) + CurvaturesFigure 5.1: Fitting alternatives: accounting for curvature, positions and tangents (d) produces fits moreconsistent with viewer expectations than when accounting for only positions (b) or positions andtangents (c).where ps,i are sample positions, and Ïs,i are the unit tangents at these samples.We discretize XË(u) by using a finite set of parameter values u j â [0,L] and represent it as a polyline withedges {XË(u j), XË(u j+1)}:XË(u j) = argminXËâjâ¥â¥â¥XË(u j)â x(u j)â¥â¥â¥2+Î»1â¥â¥â¥TË (u j)â Ï(u j)â¥â¥â¥2+Î»2â¥â¥â¥KË(u j)â k(u j)â¥â¥â¥2 . (5.2)Unit length tangents and curvatures are non-linear functions of point positions, and therefore directlysolving for XË is computationally expensive. We solve for the position XË(u j) by approximating the mini-mization above via two linear solves. Instead of directly computing the positions XË(u j), we first computethe joint tangents ÏË j that balance curvature preservation and tangent alignment. We then use these tangentsto compute the positions.Assuming arc length parameterization of the input strokes, we apply the Frenet-Serret formulas to getÏ â²(u, p) = k(u, p)n(u, px), where n(u, p) is the unit normal and k(u, p) is the curvature at a point, to solvefor tangents at u j:minÏË âjâ¥â¥ÏË jâ Ï(C j)â¥â¥2+Î»Câ¥â¥â¥â¥â¥ ÏË jâ ÏË jâ1â¥â¥Ï(C j) · (p jâ p jâ1)â¥â¥ â k jÏâ¥(C j)â¥â¥â¥â¥â¥2(5.3)We then normalize the computed joint tangents to have unit length, and compute the point positions XË(u j)as the minimizers ofminXË(u j)âj(XË(u) jâ p j)2+Î»Tâ¥â¥â¥â¥â¥ XË(u) jâ XË(u) jâ1â¥â¥Ï(C j) · (p jâ p jâ1)â¥â¥ â ÏË jâ¥â¥â¥â¥â¥2. (5.4)We set λC = 103 and λT = 104, prioritizing curvature preservation over tangent alignment and deemphasiz-ing position preservation.24Chapter 6Results and Validation(a) Input (e) Input(b) [Orbay andKara 2011](f) [Orbay and Kara 2011](c) [Liu et al. 2018] (g) [Liu et al. 2018](d) Ours (h) OursFigure 6.1: Our method successfully fits aggregate curves (d,h) to inputs (a,e) that prior methods ofOrbay and Kara [47] (b,f) and Liu et al. [38] (c,g) fail on. Input clusters highlighted in insets(a,e); visibly differently fitted clusters and curves highlighted in orange.Throughout the paper we demonstrate our fitting and underlying parameterization methods on 9 vectorformat drawings containing 214 clusters, and 31 additional single-cluster inputs. An additional 71 drawingstotaling 1,618 clusters were tested to ensure robustness. In multi-cluster drawings, clusters were labeledsemi-manually using the clustering of [38] as a starting point. These examples include numerous cyclicalclusters whose processing benefits from periodic parameterization (e.g. Figure 4.3, Figure 2.2ab), self-intersecting clusters (e.g. Figure 1.1, Figure 6.8), narrow U-shapes (e.g. Figure 6.3, col 3 and Figure 6.4,right) spirals (e.g. Figure 6.3, right; Figure 2.1), clusters with sudden curvature changes (e.g. eyebrows inFigure 1.1), and ones with large gaps and tangent differences between participating strokes (Figure 6.9). Inall cases we successfully compute arc length parameterizations that satisfy our core criteria (Section 2.1),leading to fitting outputs well aligned with viewer expectations.25(a) Input (b) [Liu et al. 2018] (c) Ours(d) Input (e) [Orbay and Kara 2011] (f) OursFigure 6.2: Additional comparisons on complete drawings against Liu et al. [38] (top) and Orbay andKara [47] (bottom). Insets show ordered points for prior work and cluster parameterization forours rendered using a rainbow color pallet.6.1 Comparison to Prior ArtAs Section 1.2 and Figure 1.4 demonstrate, methods that target fitting to 2D point clouds are poorly suitedfor the task of fitting intended curves to stroke clusters. We thus focus our comparisons on recent approachesspecifically designed for this task [38, 47]. Figure 1.1, Figure 1.5, Figure 6.1-Figure 6.4 compare the fittedcurves produced by StrokeStrip to those produced by these earlier approaches. The comparisons use thefitting output of Liu et al.âs code as-is. Orbay and Kara provided us their point-sample ordering code, butwere unable to locate the original code they used for fitting curves to these ordered samples. To visuallycompare the fits, we therefore fit curves to their output ordered samples using the tangent-aware fitting ofLiu et al., which we expect to provide results on par or superior to the B-spline fitting described in theoriginal Orbay and Kara paper.As these figures demonstrate, prior methods perform well on simple, low-curvature inputs, but frequentlyfail on more complex data. Both methods rely on point ordering as a precursor to fitting, and as the ordering26Figure 6.3: While the method of Orbay and Kara [47] fails to produce a correct order (b) on the inputclusters (a) resulting in poorly fitted curves (c), our framework parameterizes (d) and fits (e) theseclusters consistently with viewer expectations.visualizations in these figures demonstrate, the key reason for their fitting failures is incorrect ordering. Theorderings they produce frequently violate monotonicity and other key properties identified in Section 2.1;our fitting leverages quality parameterizations which avoid these pitfalls.Qualitative Comparison We validate the quality of our results by comparing them to these alternatives via acomparative perceptual study. Study participants were shown input drawings, together with our fitting resultand an alternative fitting result, using the following layout (Section A.3). The input was shown at the topand marked as âAâ, and the two fitting results were placed at the bottom in random order and marked as âBâand âCâ . Participants were then asked: âWhich of the clean drawings below, B or C, more accurately depictsthe rough drawing A on top? If both are equally accurate then select âBothâ. If neither select âNeitherâ â.The answer options were âBâ, âCâ, âBothâ, and âNeitherâ. We included 80 questions comparing our resultsagainst Orbay and Kara [47] and 76 against Liu et al [38]; we collected answers for each query from 6different participants using the protocol described in Section A.3. The study had a total of 36 participants,with each answering at most 32 questions. Participants included 1 artist; 8 familiar with vector drawing;27(a)Input(b)[Liu et al.2018] Ordering(c)[Liu et al.2018] Fit(d)Our Parameterization(e)Our FitFigure 6.4: While the method of Liu et al. [38] fails to produce a correct order (b) on the input clusters(a) resulting in poor fitted curves (c), our framework parameterizes (d) and fits (e) these clustersconsistently with viewer expectations.[Orbay andKara 2011][Liu et al. 2018]Vote Percentage Ours Both Other Neither0% 20% 40% 60% 80% 100%Figure 6.5: Summary of comparative preferences in our perceptual study. Participants strongly pre-ferred our results over algorithmic alternatives.and 27 with no art or graphics experience. Participants had no training of any kind, and were providedPDF questionnaires remotely via email, allowing participants to zoom to see fine details. The front pagestated, âIn this study, we will ask you to compare an original rough drawing against two possible cleaned-upversions. We need your opinion on their accuracy.âFigure 6.5 summarizes the study results. Participants preferred our method over the one of Liu et al [38]77% of the time, and preferred the alternative only 3% of the time. They preferred our method over the28(5.1)Stroke-Orthogonal Cross-SectionsInput(5.2)Relaxed(5.3)Parameterization Fit(a) No Filtering(b) No Relaxed StepN/A(c) Full AlgorithmFigure 6.6: Parameterization and fitting output generated by (a) skipping the initial cross-section fil-tering step (Section 4.1), (b) using the stroke-orthogonal cross-sections (Section 4.1) to initializeour final solve (Section 4.3), and (c) our method. These results demonstrate the necessity of thecore steps of our method.closest alternative [47] 61% of the time, ranked the methods as on par 29% of the time, and preferred thealternative only 5% of the time. Our t-test on the study data indicated that both results are highly significant.This study convincingly demonstrates that the curve fitting outputs we produce are more consistent withviewer expectations than those produced by prior approaches.6.2 Comparison to Manual FittingManually fitting curves to stroke clusters is highly time consuming [38, 62]. We compare the curves fittedby our method to those produced by manual fitting using a comparative qualitative study that follows thesame protocol as above. Specifically, we collected 27 overdrawn sketches with corresponding manuallytraced aggregate strokes (five from the dataset of [38] and the rest from [62]). Participants preferred ourresults 28% of the time, ranked both our and manual results as equally good 35% of the time, and preferredthe manually traced outputs 37% of the time. Overall, these results indicate that observer view our resultsas having comparable quality to manual outputs.6.3 Ablation StudiesWe demonstrate the impact of our design decisions on the output parameterizations and fits throughout thepaper (Figure 2.1,Figure 2.2, Figure 4.1, Figure 4.2, Figure 4.3, and Figure 5.1). Figure 6.6 further demon-29Input λ = 102T λ = 104Tλ = 103Cλ = 101C λ = 105C λ = 106TFigure 6.7: Impact of changing fitting weights λC (left) and λT (right). In each example the centralresult is generated with the default values and the left and right are lower and higher respectively.Figure 6.8: (Top) Overdrawn letters of the alphabet and single clusters with multiple self-intersections,(bottom) correctly fitted by our method.strates the importance and impact of our initial stroke-orthogonal cross-section filtering (Figure 6.6a) andour relaxed parameterization (Figure 6.6a). Skipping either one of those results in poor quality parameteri-zations and fits.Our parameterization method has a total of two empirical parameters: the distance ratio threshold Smax(Section 4.1) and the Ï in Equation 4.3 used to set adjacency likelihoods (Section 4.2). Running our al-gorithm on all the letters in Figure 6.8, we observed no change in fitting output when doubling or halvingeither parameter; the impact on runtime was under 10% in all cases. Our fitting method uses an additionaltwo weight parameters: one for curvature λC and one for tangents λT . Figure 6.7 demonstrates the impactof decreasing or increasing each by a factor of 100 on our fitted outputs; predictably, reducing these weightsmakes the fitted curves more centered with respect to the clusters but less smooth, while increasing themincreases smoothness.30Input Parameterization Fit Input Parameterization FitFigure 6.9: Our outputs on clusters with complex branching structures.6.4 Stress TestsFigure 6.8 and Figure 6.9 show stress-test inputs we tested our method on. Figure 6.8 demonstrates ourability to fit intended curve to highly complex clusters which include multiple intersections and turns. Weexpect our method to be most frequently used on input clusters that viewers perceive as conveying singleintended curves; however, our framework makes no explicit assumptions about the cluster structure and,as demonstrated in Figure 6.9, can be applied as-is to general clusters containing strokes which are neitherproximate nor even roughly parallel. Another such example is included in the supplementary material andthe aforementioned comparative study.6.5 Implementaton and RuntimeWe implemented our parameterization method in both MATLAB and C++. StrokeStrip takes a median timeof 1.6 seconds to fit an aggregate curve per cluster, with the majority of the runtime being spent in CVXand Gurobi performing optimizations. The runtime increases as a function of the number of samples andoverall cluster complexity. The latter impacts the rate of convergence of our iterative topology refinementstep (Section 4.2).Since each cluster can be parameterized independently, for drawings with multiple clusters, our imple-mentation parameterizes all clusters in parallel. The critical path for a drawing consists of the largest clusterin the drawing.Additional implementation details are provided in Section A.4.(a) Raster Input (b) Adobe IllustratorVectorization(c) [Favreau etal. 2016] (d) Our FitFigure 6.10: Both vectorization [1] (b) and joint vectorization and simplification [20] (c) methodsfrequently fail to generate clean curves when presented with single raster stroke clusters (a).Using the basic vectorizations in (b) as input, we successfully fit single intended curves to thisdata.31(b) Colorization(a)(c) Width Scaling (d) DisplacementFigure 6.11: Our parameterization (a) enables cluster level stroke manipulation tasks such as colorinterpolation (b), width scaling (c), and deformation (d).6.6 Extensions and Applications6.6.1 Raster DataOur framework targets artist drawn vector stroke clusters. However, it can typically be successfully ap-plied to vectorized raster stroke clusters (Figure 6.10) with the following minor changes that account forthe differences between the two data sources. Specifically, vectorization methods break strokes at clusterintersections and vectorized raster strokes have more noisy tangents than human-drawn inputs. We accountfor these artifacts as follows. During gradient direction computation (Chapter 3), given pairs of strokes withno common cross-sections we set the alignment score wËi, j to be a function of the angle between the stroketangents at the closest stroke endpoints using Equation 3.2. This change promotes assigning compatible gra-dient orientations for such pairs. Second, when solving for a parameterization, we force the parameter valuesacross such pairs of endpoints to satisfy monotonicity constraints. Finally, during fitting, we compensate forunreliable tangents and curvatures by setting the expected curvature k j to 0 in Equation 5.3.6.6.2 Parameterization-Guided Cluster Manipulationââ[Orbay andâ¨Kara 2011]OursThe benefits of computing joint stroke cluster parameterizations extendbeyond aggregate curve fitting. Our parameterization can be used forjointly manipulating different properties of the individual strokes in thecluster (Figure 6.11, Figure 1.1f). To manipulate the strokes jointly wefirst extend our 1D parameterization to a 2D (u,v) one by arc-length pa-rameterizing each isoline across the interval [âW/2,W/2] where W is theisoline width; we set v = 0 for isolines consisting of a single point. Weuse this parameterization to propagate user specified property values at a sparse set of stroke samples across32all cluster strokes by minimizing either Dirichlet or Laplacian energy (finding harmonic or biharmonic in-terpolating functions respectively) along the u and v parameter intervals. We demonstrate this approach byshading strokes via biharmonic color interpolation starting from fixed user specified colors at selected points(Figure 6.11b). Using our arc length parameterization produces smooth color change along and across theclusters. We use the same framework to modify cluster width - scaling the v isolines by a user given factor(Figure 6.11c). Finally, we use biharmonic interpolation to intuitively deform stroke clusters (Figure 6.11d,Figure 1.1f); we compute per-point displacements as a function of user-specified anchor displacements,and then solve for new point positions consistent with these changes. The same framework can be usedto compute anchor tangent or normal rotations, in line with Poisson deformation schemes. As the insetdemonstrates, the quality of the parameterization is critical to the success of the editing task - using the pa-rameterization induced by the sample ordering of Orbay and Kara [47] (top) leads to visible artifacts duringdeformation.The inset demonstrates the use of our (u,v) parameterization to transfer the style ofan exemplar cluster to a target cluster, generalizing the notion of a decorative brush [41].Here we first map the path of the exemplar cluster to the target curve using arc-lengthparameterization. We then use this path as a deformation handle, to which all otherstrokes are âriggedâ.6.6.3 Aggregate Stroke WidthIn addition to their use in refining positions and tangents, artists may use overdrawn strokes to establish thethickness of implied aggregate curves. In such cases, fixed-width curves fitted to a stroke cluster do not fullycapture artistic intent. We use our parameterization to define width at each parameter value.We define the raw width of a cluster at a given parameter value u to be its isolineâs diameter, i.e. thegreatest distance between any two stroke points with that parameter value. These widths on their own willnot be smooth along the length of the polyline: there will be sharp width changes corresponding to whereinput strokes begin and end. For visually pleasing results, the raw widths must be smoothed. We accomplishthis by solving a multi-objective optimization problem, where we balance the preservation of raw widthswith the reduction of discretized Dirichlet energy of the widths. Using a Laplacian matrix L and a vector Wof raw widths, we solve for smoothed widths w:minw(12wT Lw+Î»âi(wiâWi)2)(6.1)We support both Dirichlet (w(0) = 0 and w(n) = 0) and Neumann (wâ²(0) = 0 and wâ²(n) = 0) bound-ary conditions. The latter (Figure 6.12c) preserves the width at the cluster end-points, while the former(Figure 6.12b) tapers the width at the endpoints to zero, creating an often appealing artistic effect. A fullexample is shown in Figure 1.1e using Dirichlet boundary conditions and λ = 100.33Figure 6.12: In addition to curves, widths can be fitted to input stroke clusters (a) using either Dirich-let (b) or Neumann (c) boundary conditions to achieve different styles at curve endpoints.6.7 LimitationsAs demonstrated, our framework robustly handles a large and diverse setof inputs. However, given inherently ambiguous inputs (Figure 6.13) itlacks the higher-order reasoning that may guide viewers when interpretingsuch data. In these examples observers may perceive the input on the topas a convoluted spiral, or the one on the bottom as a messy approximationof a low-curvature curve. Instead, our framework chooses interpretations more consistent with tangentalignment and maximal isoline span. Our ability to fit raster inputs is dependent on the topology of theintermediate vector representation; we cannot correct cluster self-intersections incorrectly resolved by thevectorization (see inset). An interesting area for future work would be to either improve this intermediatedata or develop a parameterization method that selectively relaxes monotonicity to overcome such inputimperfections. Finally, our current MATLAB implementation does not allow for real-time parameterization;however we expect performance to be improved once the method is re-implemented using a language gearedtoward real-time performance.34Input Parameterization FitFigure 6.13: Our method produces meaningful results on ambiguous inputs, but these may divergefrom viewer expected ones.35Chapter 7ConclusionWe presented a robust method for fitting and parameterizing stroke clusters, that dramatically outperformsprior art. We achieve this goal by casting stroke cluster parameterization as the computation of the restrictionto the strokes of the natural arclength parameterization of the intended strips these clusters depict.Our method has potential applications outside sketch processing, such as reconstructing road maps fromGPS traces and processing of astronomical data, where image processing techniques extract multiple ap-proximately parallel and nearby paths which need to be jointly fitted by singe curves [10, 12, 57].36Bibliography[1] Adobe. Illustrator, 2020. URL https://www.adobe.com/ca/products/illustrator.html. â pages x, 4, 31[2] R. Arora, I. Darolia, V. P. Namboodiri, K. Singh, and A. Bousseau. Sketchsoup: Exploratory ideationusing design sketches. Computer Graphics Forum, 2017. â page 1[3] S.-H. Bae, R. Balakrishnan, and K. Singh. Ilovesketch: As-natural-as-possible sketching system forcreating 3d curve models. In Proceedings of the 21st Annual ACM Symposium on User InterfaceSoftware and Technology, UIST â08, page 151â160, New York, NY, USA, 2008. Association forComputing Machinery. ISBN 9781595939753. doi:10.1145/1449715.1449740. URLhttps://doi.org/10.1145/1449715.1449740. â page 6[4] B. Bao and H. Fu. Vectorizing line drawings with near-constant line width. In Proc. InternationalConference on Image Processing, pages 805â808, 2012. â page 5[5] I. Baran, J. Lehtinen, and J. Popovic´. Sketching clothoid splines using shortest paths. In ComputerGraphics Forum, volume 29, pages 655â664, 2010. â page 5[6] P. Barla, J. Thollot, and F. Sillion. Geometric clustering for line drawing simplification. In Proc.EGSR, 2005. â page 5[7] A. Bartolo, K. P. Camilleri, S. G. Fabri, J. C. Borg, and P. J. Farrugia. Scribbles to Vectors:Preparation of Scribble Drawings for CAD Interpretation. In Sketch-Based Interfaces and Modeling,2007. â page 5[8] M. Bessmeltsev and J. Solomon. Vectorization of line drawings via polyvector fields. ACM Trans.Graph., 38(1):9:1â9:12, Jan. 2019. â page 5[9] M. Bessmeltsev, N. Vining, and A. Sheffer. Gesture3d: Posing 3d characters via gesture drawings.ACM Trans. Graph., 35(6), 2016. â page 4[10] P. Bo, G. Luo, and K. Wang. A graph-based method for fitting planar b-spline curves withintersections. Journal of Computational Design and Engineering, 3(1):14 â 23, 2016. â page 36[11] P. Bo, G. Luo, and K. Wang. A graph-based method for fitting planar b-spline curves withintersections. Journal of Computational Design and Engineering, 3(1):14â23, 2016. â page 5[12] D. Chai, W. Fo¨rstner, and F. Lafarge. Recovering line-networks in images by junction-pointprocesses. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, pages 1894â1901,2013. â page 36[13] J. Chen, G. Guennebaud, P. Barla, and X. Granier. Non-oriented mls gradient fields. In ComputerGraphics Forum, volume 32, pages 98â109, 2013. â page 537[14] F. De Goes, D. Cohen-Steiner, P. Alliez, and M. Desbrun. An Optimal Transport Approach to RobustReconstruction and Simplification of 2D Shapes. Computer Graphics Forum, 30(5):1593â1602,2011. â pages viii, 4, 5[15] T. Dey, K. Mehlhorn, and E. Ramos. Curve reconstruction: connecting dots with good reason. InSCG â99, 1999. â page 5[16] L. Donati, S. Cesano, and A. Prati. An Accurate System for Fashion Hand-drawn SketchesVectorization. International Conference on Computer Vision (ICCV), 2017. â page 5[17] L. Donati, S. Cesano, and A. Prati. A complete hand-drawn sketch vectorization framework.Multimedia Tools and Applications, pages 1â31, 2019. â page 5[18] K. Eissen and R. Steur. Sketching: Drawing Techniques for Product Designers. Bis Publishers, 2008.â page 1[19] G. Farin. Curves and surfaces for computer-aided geometric design: a practical guide. 2014. âpage 5[20] J.-D. Favreau, F. Lafarge, and A. Bousseau. Fidelity vs. simplicity: a global approach to line drawingvectorization. ACM Trans. Graph., 35(4):120, 2016. â pages x, 5, 31[21] M. Finch, J. Snyder, and H. Hoppe. Freeform vector graphics with controlled thin-plate splines. ACMTrans. Graph., 30(6):166:1â166:10, 2011. â page 4[22] W. T. Freeman, J. B. Tenenbaum, and E. C. Pasztor. Learning style translation for the lines of adrawing. ACM Trans. Graph., 22(1):33â46, 2003. â page 4[23] A. Goshtasby. Grouping and parameterizing irregularly spaced points for curve fitting. ACM Trans.Graph., 19(3):185â203, 2000. â page 5[24] S. Grabli, F. Durand, and F. Sillion. Density measure for line-drawing simplification. In Proc. PacificGraphics, 2004. â page 5[25] M. Grant and S. Boyd. Graph implementations for nonsmooth convex programs. In Recent Advancesin Learning and Control, Lecture Notes in Control and Information Sciences, pages 95â110. 2008. âpage 20[26] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1.http://cvxr.com/cvx, Mar. 2014. â page 20[27] C. Grimm and P. Joshi. Just drawit: A 3d sketching system. In Proceedings of the InternationalSymposium on Sketch-Based Interfaces and Modeling, SBIM â12, page 121â130, Goslar, DEU, 2012.Eurographics Association. ISBN 9783905674422. â page 6[28] Y. Gryaditskaya, F. Ha¨hnlein, C. Liu, A. Sheffer, and A. Bousseau. Lifting freehand concept sketchesinto 3d. ACM Trans. Graph., 39(6), 2020. â page 4[29] L. Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL http://www.gurobi.com. âpage 16[30] R. Hess and D. Field. Integration of contours: new insights. Trends in Cognitive Sciences, 3(12):480â486, 1999. â pages 16, 1838[31] T. Igarashi, T. Moscovich, and J. F. Hughes. As-rigid-as-possible shape manipulation. ACM Trans.Graph., 24(3):1134â1141, 2005. â page 4[32] L. B. Kara and K. Shimada. Sketch-based 3d-shape creation for industrial styling design. IEEEComputer Graphics and Applications, 27(1):60â71, 2007. â page 6[33] M. Kazhdan and H. Hoppe. Screened poisson surface reconstruction. ACM Trans. Graph., 32(3),2013. â page 5[34] R. Kolluri, J. R. Shewchuk, and J. F. OâBrien. Spectral surface reconstruction from noisy pointclouds. In Proc. Symp. on Geometry Processing, page 11â21, 2004.[35] I.-K. Lee. Curve reconstruction from unorganized points. Computer aided geometric design, 17(2):161â177, 2000.[36] D. Levin. Mesh-independent surface interpolation. In Geometric modeling for scientific visualization,pages 37â49. 2004. â pages viii, 4, 5[37] H. Lipson and M. Shpitalni. Optimization-based reconstruction of a 3d object from a single freehandline drawing. Computer-Aided Design, 28(8):651 â 663, 1996. â page 4[38] C. Liu, E. Rosales, and A. Sheffer. StrokeAggregator: consolidating raw sketches into artist-intendedcurve drawings. ACM Trans. Graph., 37(4), 2018. â pagesviii, x, 1, 2, 4, 5, 6, 7, 8, 14, 16, 18, 19, 23, 25, 26, 27, 28, 29, 42, 43[39] X. Liu, T.-T. Wong, and P.-A. Heng. Closure-aware sketch simplification. ACM Trans. Graph., 34(6):168, 2015. â pages 1, 4, 5[40] Y. Liu, H. Yang, and W. Wang. Reconstructing b-spline curves from point cloudsâa tangential flowapproach using least squares minimization. In Proc. Shape Modeling and Applications, pages 4â12,2005. â pages viii, 4, 5[41] J. Lu, C. Barnes, C. Wan, P. Asente, R. Mech, and A. Finkelstein. DecoBrush: Drawing structureddecorative patterns by example. In ACM Transactions on Graphics (Proc. SIGGRAPH), Aug. 2014.â page 33[42] J. McCrae and K. Singh. Sketching piecewise clothoid curves. Computers & Graphics, 33(4):452â461, 2009. â page 5[43] P. Najgebauer and R. Scherer. Inertia-based fast vectorization of line drawings. (Proc. PacificGraphics), 38(7):203â213, 2019. â page 5[44] L. Nan, A. Sharf, K. Xie, T.-T. Wong, O. Deussen, D. Cohen-Or, and B. Chen. Conjoining gestaltrules for abstraction of architectural drawings. ACM Trans. Graph., 30(6), 2011. 185:1-185:10. âpage 5[45] G. Noris, D. Sy`kora, A. Shamir, S. Coros, B. Whited, M. Simmons, A. Hornung, M. Gross, andR. Sumner. Smart scribbles for sketch segmentation. In Computer Graphics Forum, volume 31, pages2516â2527, 2012. â page 5[46] G. Noris, A. Hornung, R. W. Sumner, M. Simmons, and M. Gross. Topology-driven vectorization ofclean line drawings. ACM Trans. Graph., 32(1):4, 2013. â page 539[47] G. Orbay and L. B. Kara. Beautification of design sketches using trainable stroke clustering and curvefitting. IEEE Trans. Vis. Comput. Graph, 17(5):694â708, 2011. â pagesviii, x, 1, 5, 6, 25, 26, 27, 29, 33[48] A. Orzan, A. Bousseau, H. Winnemo¨ller, P. Barla, J. Thollot, and D. Salesin. Diffusion curves: Avector representation for smooth-shaded images. In ACM Trans. Graph., volume 27, 2008. â page 4[49] A. D. Parakkat, S. Methirumangalath, and R. Muthuganapathy. Peeling the longest: A simplegeneralized curve reconstruction algorithm. Computers and Graphics, 74:191 â 201, 2018. â page 5[50] A. D. Parakkat, U. B. Pundarikaksha, and R. Muthuganapathy. A delaunay triangulation basedapproach for cleaning rough sketches. (Proc. SMI), 74:171 â 181, 2018. â page 5[51] P. L. Rosin. Grouping curved lines. In Machine Graphics and Vision 7, pages 625â644, 1994. âpage 5[52] C. Shao, A. Bousseau, A. Sheffer, and K. Singh. Crossshade: Shading concept sketches usingcross-section curves. ACM Trans. Graph., 31(4):45:1â45:11, 2012. â page 4[53] A. Shesh and B. Chen. Efficient and dynamic simplification of line drawings. In Computer GraphicsForum, volume 27, pages 537â545, 2008. â page 5[54] E. Simo-Serra, S. Iizuka, K. Sasaki, and H. Ishikawa. Learning to simplify: Fully convolutionalnetworks for rough sketch cleanup. In ACM Trans. Graph., volume 35, pages 1â11, 2016. â page 5[55] E. Simo-Serra, S. Iizuka, and H. Ishikawa. Mastering sketching: Adversarial augmentation forstructured prediction. ACM Trans. Graph., 37(1), 2018. â page 5[56] T. Stanko, M. Bessmeltsev, D. Bommes, and A. Bousseau. Integer-grid sketch simplification andvectorization. Comput. Graph. Forum, Aug. 2020. â page 5[57] E. Tu¨retken, F. Benmansour, B. Andres, H. Pfister, and P. Fua. Reconstructing loopy curvilinearstructures using integer programming. In Computer Vision and Pattern Recognition, pages1822â1829, 2013. â page 36[58] J. Wagemans, J. H. Elder, M. Kubovy, S. E. Palmer, M. A. Peterson, M. Singh, and R. von der Heydt.A century of gestalt psychology in visual perception: I. perceptual grouping and figureâgroundorganization. Psychological bulletin, 138(6):1172, 2012. â page 19[59] J. Wang, Z. Yu, W. Zhang, M. Wei, C. Tan, N. Dai, and X. Zhang. Robust reconstruction of 2d curvesfrom scattered noisy point data. Computer-Aided Design, 50:27 â 40, 2014. â page 5[60] W. Wang, H. Pottmann, and Y. Liu. Fitting b-spline curves to point clouds by curvature-basedsquared distance minimization. ACM Trans. Graph., 25(2):214â238, 2006. â page 5[61] B. Xu, W. Chang, A. Sheffer, A. Bousseau, J. McCrae, and K. Singh. True2form: 3d curve networksfrom 2d sketches via selective regularization. ACM Trans. Graph., 33(4):131:1â131:13, 2014. âpages 4, 8, 23[62] C. Yan, D. Vanderhaeghe, and Y. Gingold. A benchmark for rough sketch cleanup. ACMTransactions on Graphics (TOG), 39(6), 2020. â pages 1, 2, 4, 7, 29[63] Z. Yang, J. Deng, and F. Chen. Fitting unorganized point clouds with active implicit b-spline curves.The Visual Computer, 21:831â839, 09 2005. â page 540Appendix ASupporting MaterialsA.1 Study of Cluster Perception: Clusters as StripsWe validate our observation that human viewers perceive stroke clusters as varying widths aggregate strokes,or strips, via a small scale perceptual study. Participants were shown individual stroke clusters (Figure A.1,top) and asked to âPlease trace the sides of the stroke that is jointly conveyed by the curves belowâ. Thestudy included 5 participants and 7 representative clusters of varying complexity. As the overlays of thetraced outputs (Figure A.1,bottom) show, participants traced the same sets of sides, which satisfied boththe tangent alignment and the isoline span properties. These findings confirm our key hypotheses: thatviewers are consistent in perceiving stroke clusters as strips, and that the strips they perceive satisfy the keyproperties we identified (Section 2.1).A.2 Strip GeometryWe first note that for a strip with an arc length parameterized centerline γ(t) and variable width W (t), toavoid local self-intersections, the centerlineâs curvature k(t) has an upper bound as a function of strip width(a straightforward computation shows that |k(t)| < 1/W (t)). Here we assume strips do not have local self-intersections.For such a strip, we formally define its arc length parameterization u(x) as coinciding with the arc lengthparameterization at the centerline, and constant along each normal cross-section C(t) = {γ(t)+ an(t)|a â[âW (t)2 , W (t)2 ]}. Hence, for some point x = γ(t)+an(t) at the distance of a from the centerline, the gradientof its arc length parameterization is tangent to Ï(t) = γ â²(t) and is simply âu(x) = (Î³(t)+an(t))â² = Ï(t)(1âak(t)). (Here we used the Frenet-Serret formula nâ²(t) =âk(t)Ï(t)). We now prove:Lemma A.2.1. For a strip as defined above, the average of the arc length parameterization gradients alongeach normal cross-section C(t) is the centerline unit tangent; i.e.:1W (t)â«xâCâu(x)dx = Ï(t).41Figure A.1: Top: stroke clusters, bottom: Overlay of aggregate strokes, or strips, participants tracedfor each cluster in our cluster perception study. Participants demonstrated consistency across allinputs, confirming our hypothesis.Proof. Direct computation shows (denoting W =W (t),C =C(t) for brevity):1Wâ«xâCâu(x)dx =1Wâ« W/2âW/2Ï(t)(1â k(t)a)da= (1/W ) (Ïaâ k(t)Ï(t)a22)â£â£â£â£W/2âW/2= Ï(t).A.3 Comparative Study Setup DetailsThe questions (Chapter 6) comparing our results to prior art and manually consolidated images were ran-domly split into six questionnaires, with the question layout shown in Figure A.2. Each questionnaire con-sisted of at most 32 questions. We collected six answers for each questionnaire. All questions are includedin the supplementary.A.4 Implementation DetailsInput Stroke Clusters As input, our algorithm accepts a set of vector strokes that have been determinedto jointly represent a single, aggregate curve, agnostic to the source of these clusters. While they are moretime consuming to produce than automatic clusters, manual clusters are of a higher quality. For this paper,inputs were manually clustered using a labeling tool we created to facilitate this process. Starting fromeither an unlabeled drawing or from clusters automatically produced by StrokeAggregator [38], the labelingtool lets users merge strokes into a cluster, break strokes in two so the halves can be clustered separately,and split strokes out from one cluster into a new cluster. This clustering interface, shown in Figure A.3, was42Figure A.2: Question layout in our comparative study.additionally used to collect data for the training and evaluation of a future learned clustering algorithm.Initial Sampling We pre-process all strokes by resampling them using curvature-aware sampling: we addsamples along strokes so that the distance between each pair of consecutive samples is at most one inputstroke width, and the angle difference between the tangents at the sample is at most 4â¦. This process ensuresadequate sampling density next to sharp stroke turns.Disconnected Clusters Our basic formulation implicitly assumes that the processed clusters are connected- namely that connecting strokes using stroke-orthogonal cross-sections produce a fully connected graph.This assumption holds for clusters that viewers perceive as depicting a single intended curve [38]. We43Figure A.3: To create inputs for our algorithm, strokes can be clustered using our labeling tool.generalize our framework to handle disconnected inputs by introducing the following changes in Chapter 4.Once our our initial cross-section computation is complete, we compute the connected components in theproduced stroke graph. If more than one component is detected, we compute the shortest path connectingall components on a directed graph that connects stroke end-points with similarly oriented tangents. Wethen connect each identified stroke end-point pair using a dummy Hermite curve stroke computed using thepositions and tangents at the participating endpoints. We then apply our framework as-is to the stroke clustercontaining both original and dummy strokes.Parameter Space Sampling for Curve Fitting Using evenly sampled isovalues u j in our fitting formulation(Chapter 5) distributes approximation error evenly. In the interior of the cluster this error may be barelynoticeable. However, drift in aggregate curve endpoint locations can change viewer perceived inter-clusterinteraction, either removing perceived intersections or adding new ones, an outcome we wish to avoid. Weminimize drift near aggregate curve endpoints by using higher isovalue sampling density next to them. Withn samples, and parameter values in the range [0,L], the jth sample u j is chosen as follows:u j =ï£±ï£´ï£²ï£´ï£³L2(2 jâ1nâ1)9/4, jâ1nâ1 < 0.5Lâ L2(2â2 jâ1nâ1)9/4, jâ1nâ1 â¥ 0.5(A.1)44
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Graduate
StrokeStrip : joint parameterization and fitting of stroke clusters
Text