“Detecting viewer-perceived intended vector sketch connectivity”

Many sketch processing applications target precise vector drawings with accurately specified stroke intersections, yet free-form artist drawn sketches are typically inexact: strokes that are intended to intersect often stop short of doing so. While human observers easily perceive the artist intended stroke connectivity, manually, or even semi-manually, correcting drawings to generate correctly connected outputs is tedious and highly time consuming. We propose a novel, robust algorithm that extracts viewer-perceived stroke connectivity from inexact free-form vector drawings by leveraging observations about local and global factors that impact human perception of inter-stroke connectivity. We employ the identified local cues to train classifiers that assess the likelihood that pairs of strokes are perceived as forming end-to-end or T- junctions based on local context. We then use these classifiers within an incremental framework that combines classifier provided likelihoods with a more global, contextual and closure-based, analysis. We demonstrate our method on over 95 diversely sourced inputs, and validate it via a series of perceptual studies; participants prefer our outputs over the closest alternative by a factor of 9 to 1.

1. Adobe Inc. 2021. Adobe Illustrator. https://adobe.com/products/illustratorGoogle Scholar
2. Paul Asente, Mike Schuster, and Teri Pettit. 2007. Dynamic Planar Map Illustration. ACM Trans. Graph. 26, 3 (2007), 10 pages.Google ScholarDigital Library
3. Ilya Baran, Jaakko Lehtinen, and Jovan Popović. 2010. Sketching Clothoid Splines Using Shortest Paths. Comput. Graph. Forum 29, 2 (2010), 655–664.Google ScholarCross Ref
4. Pascal Barla, Joëlle Thollot, and François X. Sillion. 2005. Geometric Clustering for Line Drawing Simplification. In ACM SIGGRAPH 2005 Sketches (SIGGRAPH ’05). Association for Computing Machinery, 96–es.Google Scholar
5. Mikhail Bessmeltsev and Justin Solomon. 2019. Vectorization of Line Drawings via Polyvector Fields. ACM Trans. Graph. 38, 1 (Jan. 2019), 9:1–9:12.Google ScholarDigital Library
6. Blender. 2021. Blender Cloud. https://cloud.blender.org/p/gallery/5b642e25bf419c1042056fc6Google Scholar
7. Blender. 2022. Grease Pencil. https://www.blender.org/features/grease-pencil/Google Scholar
8. Salman Cheema, Sumit Gulwani, and Joseph LaViola. 2012. QuickDraw: Improving Drawing Experience for Geometric Diagrams. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’12). Association for Computing Machinery, 1037–1064.Google ScholarDigital Library
9. Jiazhou Chen, Mengqi Du, Xujia Qin, and Yongwei Miao. 2018. An Improved Topology Extraction Approach for Vectorization of Sketchy Line Drawings. Vis Comput 34, 12 (Dec. 2018), 1633–1644.Google ScholarCross Ref
10. JiaZhou Chen, Qi Lei, YongWei Miao, and QunSheng Peng. 2015. Vectorization of Line Drawing Image Based on Junction Analysis. Sci. China Inf. Sci. 58, 7 (July 2015), 1–14.Google ScholarCross Ref
11. Pedro Company, Raquel Plumed, Peter A. C. Varley, and Jorge D. Camba. 2019. Algorithmic Perception of Vertices in Sketched Drawings of Polyhedral Shapes. ACM Trans. Appl. Percept. 16, 3 (Aug. 2019), 18:1–18:19.Google ScholarDigital Library
12. Tamal K Dey. 2006. Curve and surface reconstruction: algorithms with mathematical analysis. Vol. 23. Cambridge University Press.Google ScholarDigital Library
13. Luca Donati, Simone Cesano, and Andrea Prati. 2019. A Complete Hand-Drawn Sketch Vectorization Framework. Multimed Tools Appl 78, 14 (July 2019), 19083–19113.Google ScholarDigital Library
14. Mathias Eitz, James Hays, and Marc Alexa. 2012. How Do Humans Sketch Objects? ACM Trans. Graph. 31, 4 (July 2012), 44:1–44:10.Google ScholarDigital Library
15. Jean-Dominique Favreau, Florent Lafarge, and Adrien Bousseau. 2016. Fidelity vs. Simplicity: A Global Approach to Line Drawing Vectorization. ACM Trans. Graph. 35, 4 (July 2016), 120:1–120:10.Google ScholarDigital Library
16. Jakub Fišer, Paul Asente, Stephen Schiller, and Daniel Sýkora. 2016. Advanced Drawing Beautification with ShipShape. Computers & Graphics 56 (May 2016), 46–58.Google Scholar
17. Sébastien Fourey, David Tschumperlé, and David Revoy. 2018. A Fast and Efficient Semi-Guided Algorithm for Flat Coloring Line-Arts. The Eurographics Association.Google Scholar
18. Michel Gangnet, Jean-Manuel Thong, and Jean-Daniel Fekete. 1994. Automatic Gap Closing for Freehand Drawing. In ACM SIGGRAPH 94 Technical Sketch.Google Scholar
19. Songwei Ge, Vedanuj Goswami, Larry Zitnick, and Devi Parikh. 2020. Creative Sketch Generation. In International Conference on Learning Representations.Google Scholar
20. Yulia Gryaditskaya, Felix Hähnlein, Chenxi Liu, Alla Sheffer, and Adrien Bousseau. 2020. Lifting Freehand Concept Sketches into 3D. ACM Trans. Graph. 39, 6 (Nov. 2020), 167:1–167:16.Google ScholarDigital Library
21. Yulia Gryaditskaya, Mark Sypesteyn, Jan Willem Hoftijzer, Sylvia Pont, Frédo Durand, and Adrien Bousseau. 2019. OpenSketch: A Richly-Annotated Dataset of Product Design Sketches. ACM Trans. Graph. 38, 6 (Nov. 2019), 232:1–232:16.Google ScholarDigital Library
22. Yi Guo, Zhuming Zhang, Chu Han, Wenbo Hu, Chengze Li, and Tien-Tsin Wong. 2019. Deep Line Drawing Vectorization via Line Subdivision and Topology Reconstruction. Computer Graphics Forum 38, 7 (Oct. 2019), 81–90.Google ScholarCross Ref
23. David Ha and Douglas Eck. 2018. A Neural Representation of Sketch Drawings. In International Conference on Learning Representations. https://openreview.net/forum?id=Hy6GHpkCWGoogle Scholar
24. Takeo Igarashi, Satoshi Matsuoka, Sachiko Kawachiya, and Hidehiko Tanaka. 1997. Interactive Beautification: A Technique for Rapid Geometric Design. In Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology (UIST ’97). Association for Computing Machinery, 105–114.Google ScholarDigital Library
25. Jie Jiang, Hock Soon Seah, and Hong Ze Liew. 2021. Handling Gaps for Vector Graphics Coloring. Vis Comput 37, 9 (Sept. 2021), 2473–2484.Google ScholarDigital Library
26. Jie Jiang, Hock Soon Seah, Hong Ze Liew, and Quan Chen. 2020. Challenges in Designing and Implementing a Vector-Based 2D Animation System. In The Digital Gaming Handbook. CRC Press.Google Scholar
27. Gabe Johnson, Mark D. Gross, Jason Hong, and Ellen Yi-Luen Do. 2009. Computational Support for Sketching in Design: A Review. Found. Trends Hum.-Comput. Interact. 2, 1 (2009), 1–93.Google ScholarDigital Library
28. Gaetano Kanizsa. 1979. Organization in Vision: Essays on Gestalt Perception. Praeger.Google Scholar
29. Byungsoo Kim, Oliver Wang, A. Cengiz Öztireli, and Markus Gross. 2018. Semantic Segmentation for Line Drawing Vectorization Using Neural Networks. Comput. Graph. Forum 37, 2 (2018), 329–338.Google ScholarCross Ref
30. K. Koffka. 1955. Principles of Gestalt Psychology. Routledge & K. Paul.Google Scholar
31. Krita. 2021. Krita. https://krita.org/Google Scholar
32. Chenxi Liu, Enrique Rosales, and Alla Sheffer. 2018. StrokeAggregator: Consolidating Raw Sketches into Artist-Intended Curve Drawings. ACM Trans. Graph. 37, 4 (July 2018), 97:1–97:15.Google ScholarDigital Library
33. Xueting Liu, Tien-Tsin Wong, and Pheng-Ann Heng. 2015. Closure-Aware Sketch Simplification. ACM Trans. Graph. 34, 6 (Oct. 2015), 168:1–168:10.Google ScholarDigital Library
34. Haoran Mo, Edgar Simo-Serra, Chengying Gao, Changqing Zou, and Ruomei Wang. 2021. General Virtual Sketching Framework for Vector Line Art. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2021) 40, 4 (2021), 51:1–51:14.Google Scholar
35. S. Murugappan, S. Sellamani, and K. Ramani. 2009. Towards Beautification of Freehand Sketches Using Suggestions. In Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling (SBIM ’09). Association for Computing Machinery, 69–76.Google Scholar
36. 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 (Feb. 2013), 4:1–4:11.Google ScholarDigital Library
37. G. Noris, D. Sýkora, A. Shamir, S. Coros, B. Whited, M. Simmons, A. Hornung, M. Gross, and R. Sumner. 2012. Smart Scribbles for Sketch Segmentation. Comput. Graph. Forum 31, 8 (Dec. 2012), 2516–2527.Google ScholarDigital Library
38. G. Orbay and L. B. Kara. 2011. Beautification of Design Sketches Using Trainable Stroke Clustering and Curve Fitting. IEEE Trans. Vis. Comput. Graph. 17, 5 (May 2011), 694–708.Google ScholarDigital Library
39. Amal Dev Parakkat, Marie-Paule Cani, and Karan Singh. 2021. Color by Numbers: Interactive Structuring and Vectorization of Sketch Imagery. In CHI ’21: Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems.Google ScholarDigital Library
40. Amal Dev Parakkat, Prudhviraj Madipally, Hari Hara Gowtham, and Marie-Paule Cani. 2020. Interactive Flat Coloring of Minimalist Neat Sketches. The Eurographics Association.Google Scholar
41. Theo Pavlidis and Christopher J. Van Wyk. 1985. An Automatic Beautifier for Drawings and Illustrations. SIGGRAPH Comput. Graph. 19, 3 (July 1985), 225–234.Google ScholarDigital Library
42. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-Learn: Machine Learning in Python. J. Mach. Learn. Res. 12 (2011), 2825–2830.Google ScholarDigital Library
43. Ivan Puhachov, William Neveu, Edward Chien, and Mikhail Bessmeltsev. 2021. Keypoint-Driven Line Drawing Vectorization via PolyVector Flow. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 40, 6 (Dec. 2021).Google Scholar
44. Anran Qi, Yulia Gryaditskaya, Jifei Song, Yongxin Yang, Yonggang Qi, Timothy M. Hospedales, Tao Xiang, and Yi-Zhe Song. 2021. Toward Fine-Grained Sketch-Based 3D Shape Retrieval. IEEE Trans. Image Process. 30 (2021), 8595–8606.Google ScholarDigital Library
45. Yingge Qu, Tien-Tsin Wong, and Pheng-Ann Heng. 2006. Manga Colorization. ACM Trans. Graph. 25, 3 (July 2006), 1214–1220.Google ScholarDigital Library
46. Bardia Sadri and Karan Singh. 2014. Flow-Complex-Based Shape Reconstruction from 3D Curves. ACM Trans. Graph. 33, 2, Article 20 (apr 2014), 15 pages.Google ScholarDigital Library
47. Patsorn Sangkloy, Nathan Burnell, Cusuh Ham, and James Hays. 2016. The Sketchy Database: Learning to Retrieve Badly Drawn Bunnies. ACM Trans. Graph. 35, 4 (July 2016), 119:1–119:12.Google ScholarDigital Library
48. Kazuma Sasaki, Satoshi Iizuka, Edgar Simo-Serra, and Hiroshi Ishikawa. 2017. Joint Gap Detection and Inpainting of Line Drawings. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 5768–5776.Google Scholar
49. 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:1–45:11.Google ScholarDigital Library
50. Edgar Simo-Serra, Satoshi Iizuka, and Hiroshi Ishikawa. 2018a. Mastering Sketching: Adversarial Augmentation for Structured Prediction. ACM Trans. Graph. 37, 1 (Jan. 2018), 11:1–11:13.Google ScholarDigital Library
51. Edgar Simo-Serra, Satoshi Iizuka, and Hiroshi Ishikawa. 2018b. Real-Time Data-Driven Interactive Rough Sketch Inking. ACM Trans. Graph. 37, 4 (July 2018), 98:1–98:14. Google ScholarDigital Library
52. Edgar Simo-Serra, Satoshi Iizuka, Kazuma Sasaki, and Hiroshi Ishikawa. 2016. Learning to Simplify: Fully Convolutional Networks for Rough Sketch Cleanup. ACM Trans. Graph. 35, 4 (July 2016), 121:1–121:11.Google ScholarDigital Library
53. Tibor Stanko, Mikhail Bessmeltsev, David Bommes, and Adrien Bousseau. 2020. Integer-Grid Sketch Simplification and Vectorization. Computer Graphics Forum (Proc. SGP) 39, 5 (7 2020).Google Scholar
54. Daniel Sýkora, John Dingliana, and Steven Collins. 2009. LazyBrush: Flexible Painting Tool for Hand-Drawn Cartoons. Comput. Graph. Forum 28, 2 (2009), 599–608.Google ScholarCross Ref
55. Dave Pagurek Van Mossel, Chenxi Liu, Nicholas Vining, Mikhail Bessmeltsev, and Alla Sheffer. 2021. StrokeStrip: Joint Parameterization and Fitting of Stroke Clusters. ACM Trans. Graph. 40, 4 (July 2021), 50:1–50:18.Google ScholarDigital Library
56. J. Wagemans, J. H. Elder, M. Kubovy, S. E. Palmer, M. A. Peterson, M. Singh, and R 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–1217.Google ScholarCross Ref
57. Shuxia Wang and Sui-huai Yu. 2009. Endpoint fusing of freehand 3D object sketch with Hidden-part-draw. 2009 IEEE 10th International Conference on Computer-Aided Industrial Design & Conceptual Design (2009), 586–590.Google Scholar
58. Shuxia Wang, Qian Zhang, Shouxia Wang, Xiaoke Jing, and Mantun Gao. 2020. Endpoint Fusing Method of Online Freehand-Sketched Polyhedrons. Vis Comput 36, 2 (Feb. 2020), 291–303.Google ScholarDigital Library
59. Baoxuan Xu, William Chang, Alla Sheffer, Adrien Bousseau, James McCrae, and Karan Singh. 2014. True2Form: 3D Curve Networks from 2D Sketches via Selective Regularization. Transactions on Graphics (Proc. SIGGRAPH 2014) 33, 4 (2014).Google ScholarDigital Library
60. Chuan Yan, David Vanderhaeghe, and Yotam Gingold. 2020. A Benchmark for Rough Sketch Cleanup. ACM Trans. Graph. 39, 6 (Nov. 2020).Google ScholarDigital Library
61. Wenwu Yang, Hock-Soon Seah, Quan Chen, Hong-Ze Liew, and Daniel Sýkora. 2018. FTP-SC: Fuzzy Topology Preserving Stroke Correspondence. Comput. Graph. Forum 37, 8 (2018), 125–135.Google ScholarCross Ref
62. Song-Hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, and Ralph R. Martin. 2009. Vectorizing Cartoon Animations. IEEE Trans. Vis. Comput. Graph. 15, 4 (July 2009), 618–629.Google Scholar