“Keypoint-driven line drawing vectorization via PolyVector flow” by Puhachov, Neveu, Chien and Bessmeltsev
Conference:
Type(s):
Title:
- Keypoint-driven line drawing vectorization via PolyVector flow
Session/Category Title: Curves and Surfaces
Presenter(s)/Author(s):
Abstract:
Line drawing vectorization is a daily task in graphic design, computer animation, and engineering, necessary to convert raster images to a set of curves for editing and geometry processing. Despite recent progress in the area, automatic vectorization tools often produce spurious branches or incorrect connectivity around curve junctions; or smooth out sharp corners. These issues detract from the use of such vectorization tools, both from an aesthetic viewpoint and for feasibility of downstream applications (e.g., automatic coloring or inbetweening). We address these problems by introducing a novel line drawing vectorization algorithm that splits the task into three components: (1) finding keypoints, i.e., curve endpoints, junctions, and sharp corners; (2) extracting drawing topology, i.e., finding connections between keypoints; and (3) computing the geometry of those connections. We compute the optimal geometry of the connecting curves via a novel geometric flow — PolyVector Flow — that aligns the curves to the drawing, disambiguating directions around Y-, X-, and T-junctions. We show that our system robustly infers both the geometry and topology of detailed complex drawings. We validate our system both quantitatively and qualitatively, demonstrating that our method visually outperforms previous work.
References:
1. Amin AliAbdi, Ali Mohades, and Mansoor Davoodi Monfared. 2019. Constrained shortest path problems in bi-colored graphs: a label-setting approach. GeoInformatica (12 2019), 1–19.
2. Bin Bao and Hongbo Fu. 2012. Vectorizing line drawings with near-constant line width. In IEEE Int. Conf. on Image Processing. 805–808.
3. Alexandra Bartolo, Kenneth P. Camilleri, Simon G. Fabri, Jonathan C. Borg, and Philip J. Farrugia. 2007. Scribbles to Vectors: Preparation of Scribble Drawings for CAD Interpretation. Proceedings of the 4th Eurographics Workshop on Sketch-based Interfaces and Modeling (SBIM ’07) (2007), 123–130.
4. Mikhail Bessmeltsev and Justin Solomon. 2019. Vectorization of line drawings via polyvector fields. ACM Transactions on Graphics 38, 1 (2019). arXiv:1801.01922
5. 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.
6. Alexander I. Bobenko and Peter Schröder. 2005. Discrete Willmore Flow. In Proceedings of the Third Eurographics Symposium on Geometry Processing (Vienna, Austria) (SGP ’05). Eurographics Association, Goslar, DEU, 101–es.
7. Alexandre Carlier, Martin Danelljan, Alexandre Alahi, and Radu Timofte. 2020. DeepSVG: A Hierarchical Generative Network for Vector Graphics Animation. arXiv:2007.11301 [cs.CV]
8. V. Caselles, R. Kimmel, and G. Sapiro. 1995. Geodesic active contours. In Proceedings of IEEE International Conference on Computer Vision. 694–699.
9. Dengfeng Chai, Wolfgang Förstner, and Florent Lafarge. 2013. Recovering Line-Networks in Images by Junction-Point Processes. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. 1894–1901.
10. Jiazhou Chen, Mengqi Du, Xujia Qin, and Yongwei Miao. 2018. An improved topology extraction approach for vectorization of sketchy line drawings. Visual Computer 34, 12 (2018), 1633–1644.
11. Jiazhou Chen, Gaël Guennebaud, Pascal Barla, and Xavier Granier. 2013. Non-Oriented MLS Gradient Fields. Computer Graphics Forum 32, 8 (2013), 98–109.
12. JiaZhou Chen, Qi Lei, YongWei Miao, and QunSheng Peng. 2015. Vectorization of line drawing image based on junction analysis. Science China Information Sciences 58, 7 (2015), 1–14.
13. U. Clarenz, U. Diewald, G. Dziuk, M. Rumpf, and R. Rusu. 2004. A Finite Element Method for Surface Restoration with Smooth Boundary Conditions. Comput. Aided Geom. Des. 21, 5 (May 2004), 427–445.
14. Ulrich Clarenz, Gerhard Dziuk, and Martin Rumpf. 2003. On generalized mean curvature flow in surface processing. In Geometric Analysis and Nonlinear Partial Differential Equations. Springer.
15. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Robust Fairing via Conformal Curvature Flow. 32, 4, Article 61 (July 2013), 10 pages.
16. Ayan Das, Yongxin Yang, Timothy Hospedales, Tao Xiang, and Yi-Zhe Song. 2021. Cloud2Curve: Generation and Vectorization of Parametric Sketches. i (2021). arXiv:2103.15536
17. Fernando de Goes, Siome Goldenstein, and Luiz Velho. 2008. A simple and flexible framework to adapt dynamic meshes. Computers & Graphics 32, 2 (2008), 141 — 148. http://www.sciencedirect.com/science/article/pii/S0097849308000174
18. Klaus Deckelnick, Gerhard Dziuk, and Charles M. Elliott. 2005. Computation of geometric partial differential equations and mean curvature flow. Acta Numerica 14 (2005), 139–232.
19. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr. 1999. Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., USA, 317–324.
20. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable PolyVector Fields. ACM Trans. Graph. 34, 4, Article 38 (July 2015), 12 pages.
21. Edoardo Alberto Dominici, Nico Schertler, Jonathan Griffin, Shayan Hoshyari, Leonid Sigal, and Alla Sheffer. 2020. PolyFit: Perception-aligned Vectorization of Raster Clip-art via Intermediate Polygonal Fitting. ACM Transaction on Graphics 39, 4 (2020).
22. Luca Donati, Simone Cesano, and Andrea Prati. 2017. An Accurate System for Fashion Hand-Drawn Sketches Vectorization. In The IEEE International Conference on Computer Vision (ICCV). 2280–2286.
23. Luca Donati, Simone Cesano, and Andrea Prati. 2019. A complete hand-drawn sketch vectorization framework. Multimedia Tools and Applications 78, 14 (2019), 19083–19113.
24. Gerhard Dziuk. 1999. Discrete Anisotropic Curve Shortening Flow. SIAM J. Numer. Anal. 36, 6 (1999), 1808–1830.
25. Gerhard Dziuk and Charles M. Elliott. 2013. Finite element methods for surface PDEs. Acta Numerica 22 (2013), 289–396.
26. Vage Egiazarian, Oleg Voynov, Alexey Artemov, Denis Volkhonskiy, Aleksandr Safin, Maria Taktasheva, Denis Zorin, and Evgeny Burnaev. 2020. Deep Vectorization of Technical Drawings. Lecture Notes in Computer Science (2020), 582–598.
27. Jean-Dominique Favreau, Florent Lafarge, and Adrien Bousseau. 2016. Fidelity vs. Simplicity: a Global Approach to Line Drawing Vectorization. ACM Transactions on Graphics (SIGGRAPH Conference Proceedings) 35, 4, Article 120 (July 2016), 10 pages.
28. Jun Gao, Chengcheng Tang, Vignesh Ganapathi-Subramanian, Jiahui Huang, Hao Su, and Leonidas J. Guibas. 2019. DeepSpline: Data-Driven Reconstruction of Parametric Curves and Surfaces. CoRR abs/1901.03781 (2019). arXiv:1901.03781
29. Songwei Ge, Vedanuj Goswami, C. Lawrence Zitnick, and Devi Parikh. 2021. Creative Sketch Generation. arXiv:2011.10039 [cs.CV]
30. 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 (July 2011), 1593–1602.
31. Anthony Gruber and Eugenio Aulisa. 2020. Computational P-Willmore Flow with Conformal Penalty. ACM Trans. Graph. 39, 5, Article 161 (Aug. 2020), 16 pages.
32. Yulia Gryaditskaya, Felix Hahnlein, Chenxi Liu, Alla Sheffer, and Adrien Bousseau. 2020. Lifting Freehand Concept Sketches into 3D. ACM Transactions on Graphics (Proc. SIGGRAPH Asia) 39 (12 2020).
33. 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. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 81–90.
34. LLC Gurobi Optimization. 2021. Gurobi Optimizer Reference Manual. http://www.gurobi.com
35. Igor Guskov, Wim Sweldens, and Peter Schröder. 1999. Multiresolution Signal Processing for Meshes. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., USA, 325–334.
36. David Ha and Douglas Eck. 2017. A Neural Representation of Sketch Drawings. ArXiv e-prints (April 2017). arXiv:1704.03477 [cs.NE]
37. Xavier Hilaire and Karl Tombre. 2006. Robust and accurate vectorization of line drawings. IEEE Transactions on Pattern Analysis and Machine Intelligence 28, 6 (June 2006), 890–904.
38. Shayan Hoshyari, Edoardo Alberto Dominici, Alla Sheffer, Nathan Carr, Duygu Ceylan, Zhaowen Wang, and I-Chao Shen. 2018. Perception-Driven Semi-Structured Boundary Vectorization. ACM Transaction on Graphics 37, 4 (2018).
39. Sadashige Ishida, Masafumi Yamamoto, Ryoichi Ando, and Toshiya Hachisuka. 2017. A Hyperbolic Geometric Flow for Evolving Films and Foams. ACM Trans. Graph. 36, 6, Article 199 (Nov. 2017), 11 pages.
40. Xie Jun, Winnemöller Holger, Li Wilmot, and Schiller Stephen. 2017. Interactive Vectorization. In ACM SIGCHI. 6695–6705.
41. Henry Kang, Seungyong Lee, and Charles K. Chui. 2007. Coherent Line Drawing. In Proceedings of the 5th International Symposium on Non-photorealistic Animation and Rendering (San Diego, California) (NPAR ’07). ACM, New York, NY, USA, 43–50.
42. S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum, and A. Yezzi. 1995. Gradient flows and geometric active contour models. In Proceedings of IEEE International Conference on Computer Vision. 810–815.
43. Byungsoo Kim, Oliver Wang, A. Cengiz Öztireli, and Markus Gross. 2018. Semantic Segmentation for Line Drawing Vectorization Using Neural Networks. Computer Graphics Forum (Proc. Eurographics) 37, 2 (2018), 329–338.
44. Leif Kobbelt. 2000. Discrete fairing and variational subdivision for freeform surface design. The Visual Computer 16 (2000).
45. Leif Kobbelt, Swen Campagna, Jens Vorsatz, and Hans-Peter Seidel. 1998. Interactive Multi-Resolution Modeling on Arbitrary Meshes. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’98). Association for Computing Machinery, New York, NY, USA, 105–114.
46. L. Kou, G. Markowsky, and L. Berman. 1981. A Fast Algorithm for Steiner Trees. Acta Inf. 15, 2 (June 1981), 141–145.
47. Gregory Lecot and Bruno Lévy. 2006. Ardeco: Automatic Region Detection and Conversion. In Proceedings of the 17th Eurographics Conference on Rendering Techniques (Nicosia, Cyprus) (EGSR ’06). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 349–360.
48. Juelin Leng, Yongjie Zhang, and Guoliang Xu. 2013. A Novel Geometric Flow Approach for Quality Improvement of Multi-Component Tetrahedral Meshes. Comput. Aided Des. 45, 10 (Oct. 2013), 1182–1197.
49. Tzu-Mao Li, Michal Lukáč, Gharbi Michaël, and Jonathan Ragan-Kelley. 2020. Differentiable Vector Graphics Rasterization for Editing and Learning. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 193:1–193:15.
50. Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie. 2017. Feature Pyramid Networks for Object Detection. arXiv:1612.03144 [cs.CV]
51. 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.
52. Chenxi Liu, Enrique Rosales, and Alla Sheffer. 2018. StrokeAggregator: consolidating raw sketches into artist-intended curve drawings. ACM Transactions on Graphics (TOG) 37, 4 (2018), 97.
53. Chen Liu, Jiajun Wu, Pushmeet Kohli, and Yasutaka Furukawa. 2017. Raster-to-Vector: Revisiting Floorplan Transformation. In 2017 IEEE International Conference on Computer Vision (ICCV). 2214–2222.
54. Raphael Gontijo Lopes, David Ha, Douglas Eck, and Jonathon Shlens. 2019. A Learned Representation for Scalable Vector Graphics. In Proceedings of the IEEE International Conference on Computer Vision (ICCV).
55. M. K. Misztal, K. Erleben, A. Bargteil, J. Fursund, B. Bunch Christensen, J. A. Bærentzen, and R. Bridson. 2012. Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Lausanne, Switzerland) (SCA ’12). Eurographics Association, Goslar, DEU, 97–106.
56. 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.
57. Patryk Najgebauer and Rafał Scherer. 2019. Inertia-based Fast Vectorization of Line Drawings. Computer Graphics Forum (Proc. Pacific Graphics) 38, 7 (2019), 203–213.
58. Alejandro Newell, Kaiyu Yang, and Jia Deng. 2016. Stacked Hourglass Networks for Human Pose Estimation, Vol. 9912. 483–499.
59. 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, Article 4 (Feb. 2013), 11 pages.
60. Alexandrina Orzan, Adrien Bousseau, Pascal Barla, Holger Winnemöller, Joëlle Thollot, and David Salesin. 2013. Diffusion Curves: A Vector Representation for Smooth-shaded Images. Commun. ACM 56, 7 (July 2013), 101–108.
61. Amal Dev Parakkat, Uday Bondi Pundarikaksha, and Ramanathan Muthuganapathy. 2018. A Delaunay triangulation based approach for cleaning rough sketches. Computers & Graphics 74 (2018), 171 — 181.
62. Pradyumna Reddy, Michael Gharbi, Michal Lukac, and Niloy J. Mitra. 2021. Im2Vec: Synthesizing Vector Graphics without Vector Supervision. arXiv:2102.02798 [cs.CV]
63. Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. 2016. You Only Look Once: Unified, Real-Time Object Detection. arXiv:1506.02640 [cs.CV]
64. Robert Schneider and Leif Kobbelt. 2001. Geometric fairing of irregular meshes for free-form surface design. Computer Aided Geometric Design 18, 4 (2001), 359 — 379.
65. Edgar Simo-Serra, Satoshi Iizuka, and Hiroshi Ishikawa. 2018. Mastering Sketching: Adversarial Augmentation for Structured Prediction. ACM Transactions on Graphics (TOG) 37, 1 (2018).
66. Edgar Simo-Serra, Satoshi Iizuka, Kazuma Sasaki, and Hiroshi Ishikawa. 2016. Learning to Simplify: Fully Convolutional Networks for Rough Sketch Cleanup. ACM Transactions on Graphics (SIGGRAPH) 35, 4 (2016).
67. Tibor Stanko, Mikhail Bessmeltsev, David Bommes, and Adrien Bousseau. 2020. Integer-Grid Sketch Simplification and Vectorization. Computer Graphics Forum (Proceedings of the Eurographics Symposium on Geometry Processing) 39, 5 (jul 2020), 149–161. http://www-sop.inria.fr/reves/Basilic/2020/SBBB20
68. Gabriel Taubin. 1995. A Signal Processing Approach to Fair Surface Design. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’95). Association for Computing Machinery, New York, NY, USA, 351–358.
69. Nils Thürey, Chris Wojtan, Markus Gross, and Greg Turk. 2010. A Multiscale Approach to Mesh-Based Surface Tension Flows. In ACM SIGGRAPH 2010 Papers (Los Angeles, California) (SIGGRAPH ’10). Association for Computing Machinery, New York, NY, USA, Article 48, 10 pages.
70. Engin Türetken, Fethallah Benmansour, Bjoern Andres, Hanspeter Pfister, and Pascal Fua. 2013. Reconstructing Loopy Curvilinear Structures Using Integer Programming. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. 1822–1829.
71. Saining Xie and Zhuowen Tu. 2017. Holistically-Nested Edge Detection. Int. J. Comput. Vision 125, 1–3 (Dec. 2017), 3–18.
72. Xuemiao Xu, Minshan Xie, Peiqi Miao, Wei Qu, Wenpeng Xiao, Huaidong Zhang, Xueting Liu, and Tien-Tsin Wong. 2019. Perceptual-aware Sketch Simplification Based on Integrated VGG Layers. IEEE Transactions on Visualization and Computer Graphics (2019).
73. Chuan Yan, David Vanderhaeghe, and Yotam Gingold. 2020. A Benchmark for Rough Sketch Cleanup. ACM Transactions on Graphics 39, 6 (Nov. 2020). To be presented at SIGGRAPH Asia 2020.
74. Song-Hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, and Ralph R. Martin. 2009. Vectorizing Cartoon Animations. IEEE Transactions on Visualization and Computer Graphics 15, 4 (July 2009), 618–629.
75. Yizhong Zhang, Huamin Wang, Shuai Wang, Yiying Tong, and Kun Zhou. 2012. A Deformable Surface Model for Real-Time Water Drop Animation. IEEE Transactions on Visualization and Computer Graphics 18, 8 (Aug. 2012), 1281–1289.
76. Xingyi Zhou, Dequan Wang, and Philipp Krähenbühl. 2019b. Objects as Points. In arXiv preprint arXiv:1904.07850.
77. Yichao Zhou, Haozhi Qi, and Yi Ma. 2019a. End-to-end wireframe parsing. Proceedings of the IEEE International Conference on Computer Vision 2019-October (2019), 962–971. arXiv:1905.03246
