“StrokeStrip: joint parameterization and fitting of stroke clusters” by Van Mossel, Liu, Vining, Bessmeltsev and Sheffer

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.

1. Adobe. 2020. Illustrator. https://www.adobe.com/ca/products/illustrator.htmlGoogle Scholar
2. Rahul Arora, Ishan Darolia, Vinay P. Namboodiri, Karan Singh, and Adrien Bousseau. 2017. SketchSoup: Exploratory Ideation Using Design Sketches. Computer Graphics Forums (2017).Google Scholar
3. Seok-Hyung Bae, Ravin Balakrishnan, and Karan Singh. 2008. ILoveSketch: As-Natural-as-Possible Sketching System for Creating 3d Curve Models. In Proc. UIST. 151–160.Google ScholarDigital Library
4. Bin Bao and Hongbo Fu. 2012. Vectorizing line drawings with near-constant line width. In Proc. International Conference on Image Processing. 805–808.Google ScholarCross Ref
5. Ilya Baran, Jaakko Lehtinen, and Jovan Popović. 2010. Sketching clothoid splines using shortest paths. In Computer Graphics Forum, Vol. 29. 655–664.Google ScholarCross Ref
6. Pascal Barla, Joëlle Thollot, and François Sillion. 2005. Geometric Clustering for Line Drawing Simplification. In Proc. EGSR.Google ScholarDigital Library
7. A. Bartolo, K. P. Camilleri, S. G. Fabri, J. C. Borg, and P. J. Farrugia. 2007. Scribbles to Vectors: Preparation of Scribble Drawings for CAD Interpretation. In Proc. SBIM.Google Scholar
8. Mikhail Bessmeltsev and Justin Solomon. 2019. Vectorization of Line Drawings via Polyvector Fields. ACM Trans. Graph. 38, 1, Article 9 (Jan. 2019), 12 pages.Google ScholarDigital Library
9. Mikhail Bessmeltsev, Nicholas Vining, and Alla Sheffer. 2016. Gesture3D: Posing 3D Characters via Gesture Drawings. ACM Trans. Graph. 35, 6 (2016).Google ScholarDigital Library
10. Blender. 2021. Grease Pencil. https://www.blender.org/features/grease-pencil/.Google Scholar
11. Pengbo Bo, Gongning Luo, and Kuanquan Wang. 2016. A graph-based method for fitting planar B-spline curves with intersections. Journal of Computational Design and Engineering 3, 1 (2016), 14 — 23.Google ScholarCross Ref
12. Dengfeng Chai, Wolfgang Förstner, and Florent Lafarge. 2013. Recovering Line-Networks in Images by Junction-Point Processes. In Proc. CVPR. 1894–1901.Google ScholarDigital Library
13. Jiazhou Chen, Gael Guennebaud, Pascal Barla, and Xavier Granier. 2013. Non-Oriented MLS Gradient Fields. In Computer Graphics Forum, Vol. 32. 98–109.Google ScholarCross Ref
14. Fernando De Goes, David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2011. An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes. Computer Graphics Forum 30, 5 (2011), 1593–1602.Google ScholarCross Ref
15. T. Dey, K. Mehlhorn, and E. Ramos. 1999. Curve reconstruction: connecting dots with good reason. In SCG ’99.Google Scholar
16. Luca Donati, Simone Cesano, and Andrea Prati. 2017. An Accurate System for Fashion Hand-drawn Sketches Vectorization. Proc. ICCV (2017).Google ScholarCross Ref
17. Luca Donati, Simone Cesano, and Andrea Prati. 2019. A complete hand-drawn sketch vectorization framework. Multimedia Tools and Applications (2019), 1–31.Google Scholar
18. Koos Eissen and Roselien Steur. 2008. Sketching: Drawing Techniques for Product Designers. Bis Publishers.Google Scholar
19. Gerald Farin. 2014. Curves and surfaces for computer-aided geometric design: a practical guide.Google Scholar
20. Jean-Dominique Favreau, Florent Lafarge, and Adrien Bousseau. 2016. Fidelity vs. simplicity: a global approach to line drawing vectorization. ACM Trans. Graph. 35, 4 (2016), 120.Google ScholarDigital Library
21. Mark Finch, John Snyder, and Hugues Hoppe. 2011. Freeform Vector Graphics with Controlled Thin-plate Splines. ACM Trans. Graph. 30, 6 (2011), 166:1–166:10.Google ScholarDigital Library
22. William T Freeman, Joshua B Tenenbaum, and Egon C Pasztor. 2003. Learning style translation for the lines of a drawing. ACM Trans. Graph. 22, 1 (2003), 33–46.Google ScholarDigital Library
23. A. Goshtasby. 2000. Grouping and Parameterizing Irregularly Spaced Points for Curve Fitting. ACM Trans. Graph. 19, 3 (2000), 185–203.Google ScholarDigital Library
24. Stéphane Grabli, Frédo Durand, and François Sillion. 2004. Density Measure for Line-Drawing Simplification. In Proc. Pacific Graphics.Google ScholarDigital Library
25. Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control. 95–110.Google Scholar
26. Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx.Google Scholar
27. Cindy Grimm and Pushkar Joshi. 2012. Just DrawIt: A 3D Sketching System. In Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling (SBIM ’12). Eurographics Association, Goslar, DEU, 121–130.Google ScholarDigital Library
28. Yulia Gryaditskaya, Felix Hähnlein, Chenxi Liu, Alla Sheffer, and Adrien Bousseau. 2020. Lifting Freehand Concept Sketches into 3D. ACM Trans. Graph. 39, 6, Article 167 (2020).Google ScholarDigital Library
29. LLC Gurobi Optimization. 2020. Gurobi Optimizer Reference Manual. http://www.gurobi.comGoogle Scholar
30. Robert Hess and David Field. 1999. Integration of contours: new insights. Trends in Cognitive Sciences 3, 12 (1999), 480–486.Google ScholarCross Ref
31. Takeo Igarashi, Tomer Moscovich, and John F. Hughes. 2005. As-rigid-as-possible Shape Manipulation. ACM Trans. Graph. 24, 3 (2005), 1134–1141.Google ScholarDigital Library
32. L. B. Kara and K. Shimada. 2007. Sketch-Based 3D-Shape Creation for Industrial Styling Design. IEEE Computer Graphics and Applications 27, 1 (2007), 60–71.Google ScholarDigital Library
33. Michael Kazhdan and Hugues Hoppe. 2013. Screened Poisson Surface Reconstruction. ACM Trans. Graph. 32, 3, Article 29 (2013).Google ScholarDigital Library
34. Ravikrishna Kolluri, Jonathan Richard Shewchuk, and James F. O’Brien. 2004. Spectral Surface Reconstruction from Noisy Point Clouds. In Proc. SGP. 11–21.Google Scholar
35. In-Kwon Lee. 2000. Curve reconstruction from unorganized points. Computer aided geometric design 17, 2 (2000), 161–177.Google Scholar
36. David Levin. 2004. Mesh-independent surface interpolation. In Geometric modeling for scientific visualization. 37–49.Google Scholar
37. H Lipson and M Shpitalni. 1996. Optimization-based reconstruction of a 3D object from a single freehand line drawing. Computer-Aided Design 28, 8 (1996), 651 — 663.Google ScholarCross Ref
38. Chenxi Liu, Enrique Rosales, and Alla Sheffer. 2018. StrokeAggregator: consolidating raw sketches into artist-intended curve drawings. ACM Trans. Graph. 37, 4, Article 97 (2018).Google ScholarDigital Library
39. Xueting Liu, Tien-Tsin Wong, and Pheng-Ann Heng. 2015. Closure-aware sketch simplification. ACM Trans. Graph. 34, 6 (2015), 168.Google ScholarDigital Library
40. Y. Liu, H. Yang, and W. Wang. 2005. Reconstructing B-spline Curves from Point Clouds-A Tangential Flow Approach Using Least Squares Minimization. In Proc. Shape Modeling and Applications. 4–12.Google Scholar
41. Jingwan Lu, Connelly Barnes, Connie Wan, Paul Asente, Radomir Mech, and Adam Finkelstein. 2014. DecoBrush: Drawing Structured Decorative Patterns by Example. In ACM Trans. Graph (Proc. SIGGRAPH).Google Scholar
42. James McCrae and Karan Singh. 2009. Sketching piecewise clothoid curves. Computers & Graphics 33, 4 (2009), 452–461.Google ScholarDigital Library
43. Patryk Najgebauer and Rafał Scherer. 2019. Inertia-based Fast Vectorization of Line Drawings. (Proc. Pacific Graphics) 38, 7 (2019), 203–213.Google Scholar
44. Liangliang Nan, Andrei Sharf, Ke Xie, Tien-Tsin Wong, Oliver Deussen, Daniel Cohen-Or, and Baoquan Chen. 2011. Conjoining Gestalt Rules for Abstraction of Architectural Drawings. ACM Trans. Graph. 30, 6 (2011). 185:1–185:10.Google ScholarDigital Library
45. Gioacchino Noris, Alexander Hornung, Robert W Sumner, Maryann Simmons, and Markus Gross. 2013. Topology-driven vectorization of clean line drawings. ACM Trans. Graph. 32, 1 (2013), 4.Google ScholarDigital Library
46. Gioacchino Noris, Daniel Sỳkora, A Shamir, Stelian Coros, Brian Whited, Maryann Simmons, Alexander Hornung, M Gross, and R Sumner. 2012. Smart scribbles for sketch segmentation. In Computer Graphics Forum, Vol. 31. 2516–2527.Google ScholarDigital Library
47. Gunay Orbay and Levent Burak Kara. 2011. Beautification of design sketches using trainable stroke clustering and curve fitting. IEEE TVCG 17, 5 (2011), 694–708.Google Scholar
48. Alexandrina Orzan, Adrien Bousseau, Holger Winnemöller, Pascal Barla, Joëlle Thollot, and David Salesin. 2008. Diffusion Curves: A Vector Representation for Smooth-Shaded Images. In ACM Trans. Graph., Vol. 27.Google ScholarDigital Library
49. Amal Dev Parakkat, Subhasree Methirumangalath, and Ramanathan Muthuganapathy. 2018a. Peeling the longest: A simple generalized curve reconstruction algorithm. Computers and Graphics 74 (2018), 191 — 201.Google ScholarCross Ref
50. Amal Dev Parakkat, Uday Bondi Pundarikaksha, and Ramanathan Muthuganapathy. 2018b. A Delaunay triangulation based approach for cleaning rough sketches. (Proc. SMI) 74 (2018), 171 — 181.Google Scholar
51. Richard Pusch, Faramarz Samavati, Ahmad Nasri, and Brian Wyvill. 2007. Improving the Sketch-Based Interface: Forming Curves from Many Small Strokes. Vis. Comput. 23, 9 (Aug. 2007), 955–962. Google ScholarDigital Library
52. Paul L. Rosin. 1994. Grouping Curved Lines. In Machine Graphics and Vision 7. 625–644.Google Scholar
53. Cloud Shao, Adrien Bousseau, Alla Sheffer, and Karan Singh. 2012. CrossShade: Shading Concept Sketches Using Cross-section Curves. ACM Trans. Graph. 31, 4 (2012), 45.Google ScholarDigital Library
54. Amit Shesh and Baoquan Chen. 2008. Efficient and dynamic simplification of line drawings. In Computer Graphics Forum, Vol. 27. 537–545.Google ScholarCross Ref
55. Edgar Simo-Serra, Satoshi Iizuka, and Hiroshi Ishikawa. 2018. Mastering sketching: Adversarial augmentation for structured prediction. ACM Trans. Graph. 37, 1 (2018).Google ScholarDigital Library
56. Edgar Simo-Serra, Satoshi Iizuka, Kazuma Sasaki, and Hiroshi Ishikawa. 2016. Learning to simplify: Fully convolutional networks for rough sketch cleanup. In ACM Trans. Graph., Vol. 35. 1–11.Google ScholarDigital Library
57. T. Stanko, M. Bessmeltsev, D. Bommes, and A. Bousseau. 2020. Integer-Grid Sketch Simplification and Vectorization. Comput. Graph. Forum (Aug. 2020).Google Scholar
58. Engin Türetken, Fethallah Benmansour, Bjoern Andres, Hanspeter Pfister, and Pascal Fua. 2013. Reconstructing Loopy Curvilinear Structures Using Integer Programming. In Proc. CVPR. 1822–1829.Google ScholarDigital Library
59. Johan Wagemans, James H Elder, Michael Kubovy, Stephen E Palmer, Mary A Peterson, Manish Singh, and Rüdiger von der Heydt. 2012. A century of Gestalt psychology in visual perception: I. Perceptual grouping and figure-ground organization. Psychological bulletin 138, 6 (2012), 1172.Google Scholar
60. Jun Wang, Zeyun Yu, Weizhong Zhang, Mingqiang Wei, Changbai Tan, Ning Dai, and Xi Zhang. 2014. Robust reconstruction of 2D curves from scattered noisy point data. Computer-Aided Design 50 (2014), 27 — 40.Google ScholarDigital Library
61. Wenping Wang, Helmut Pottmann, and Yang Liu. 2006. Fitting B-Spline Curves to Point Clouds by Curvature-Based Squared Distance Minimization. ACM Trans. Graph. 25, 2 (2006), 214–238.Google ScholarDigital Library
62. Baoxuan Xu, William Chang, Alla Sheffer, Adrien Bousseau, James McCrae, and Karan Singh. 2014. True2Form: 3D Curve Networks from 2D Sketches via Selective Regularization. ACM Trans. Graph. 33, 4 (2014), 131:1–131:13.Google ScholarDigital Library
63. Chuan Yan, David Vanderhaeghe, and Yotam Gingold. 2020. A Benchmark for Rough Sketch Cleanup. ACM Transactions on Graphics (TOG) 39, 6 (2020).Google ScholarDigital Library
64. Zhouwang Yang, Jiansong Deng, and Falai Chen. 2005. Fitting unorganized point clouds with active implicit B-spline curves. The Visual Computer 21 (09 2005), 831–839.Google Scholar