“Perception-driven semi-structured boundary vectorization” by Hoshyari, Dominici, Sheffer, Carr, Wang, et al. …

  • ©Shayan Hoshyari, Edoardo Alberto Dominici, Alla Sheffer, Nathan Carr, Zhaowen Wang, Duygu Ceylan, and I-Chao Shen



Entry Number: 118

Session Title:

    Decision & Style R&E


    Perception-driven semi-structured boundary vectorization




    Artist-drawn images with distinctly colored, piecewise continuous boundaries, which we refer to as semi-structured imagery, are very common in online raster databases and typically allow for a perceptually unambiguous mental vector interpretation. Yet, perhaps surprisingly, existing vectorization algorithms frequently fail to generate these viewer-expected interpretations on such imagery. In particular, the vectorized region boundaries they produce frequently diverge from those anticipated by viewers. We propose a new approach to region boundary vectorization that targets semi-structured inputs and leverages observations about human perception of shapes to generate vector images consistent with viewer expectations. When viewing raster imagery observers expect the vector output to be an accurate representation of the raster input. However, perception studies suggest that viewers implicitly account for the lossy nature of the rasterization process and mentally smooth and simplify the observed boundaries. Our core algorithmic challenge is to balance these conflicting cues and obtain a piecewise continuous vectorization whose discontinuities, or corners, are aligned with human expectations.Our framework centers around a simultaneous spline fitting and corner detection method that combines a learned metric, that approximates human perception of boundary discontinuities on raster inputs, with perception-driven algorithmic discontinuity analysis. The resulting method balances local cues provided by the learned metric with global cues obtained by balancing simplicity and continuity expectations. Given the finalized set of corners, our framework connects those using simple, continuous curves that capture input regularities. We demonstrate our method on a range of inputs and validate its superiority over existing alternatives via an extensive comparative user study.


    1. Adobe. 2017. Adobe Illustrator 2017: Image Trace, http://www.adobe.com/. (2017).Google Scholar
    2. Hani Altwaijry, Andreas Veit, Sergej Belongie, and Cornell Tech. 2016. Learning to Detect and Match Keypoints with Deep Architectures.. In BMVC.Google Scholar
    3. Fabián Arrebola and Francisco Sandoval. 2005. Corner detection and curve segmentation by multiresolution chain-code linking. Pattern Recognition 38, 10 (2005), 1596–1614. Google ScholarDigital Library
    4. Ilya Baran, Jaakko Lehtinen, and Jovan Popović. 2010. Sketching clothoid splines using shortest paths. In CGF, Vol. 29,2. 655–664.Google ScholarCross Ref
    5. H Lynn Beus and Steven SH Tiu. 1987. An improved corner detection algorithm based on chain-coded plane curves. Pattern Recognition 20, 3 (1987), 291–296. Google ScholarDigital Library
    6. Leo Breiman. 2001. Random forests. Machine learning 45, 1 (2001), 5–32. Google ScholarDigital Library
    7. A Carmona-Poyato, Francisco José Madrid-Cuevas, R Medina-Carnicer, and Rafael Muñoz-Salinas. 2010. Polygonal approximation of digital planar curves through breakpoint suppression. Pattern Recognition 43, 1 (2010), 14–25. Google ScholarDigital Library
    8. Vicent Caselles, Ron Kimmel, and Guillermo Sapiro. 1997. Geodesic Active Contours. IJCV 22, 1 (1997), 61–79. Google ScholarDigital Library
    9. Dmitry Chetverikov and Zsolt Szabo. 2003. A simple and efficient algorithm for detection of high curvature points in planar curves. In CAIP, Vol. 3. Springer, 746–753.Google ScholarCross Ref
    10. Ryan Dahl, Mohammad Norouzi, and Jonathan Shlens. 2017. Pixel Recursive Super Resolution. In IEEE ICCV.Google Scholar
    11. J. R. Diebel. 2008. Bayesian image vectorization: The probabilistic inversion of vector image rasterization. Ph.D. dissertation, Stanford Univ. Google ScholarDigital Library
    12. Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang. 2014. Learning a deep convolutional network for image super-resolution. In ECCV. 184–199.Google Scholar
    13. Eagle. 1997. Eagle. http://everything2.com/index.pl?node_id=1859453. (1997).Google Scholar
    14. Gerald Farin. 2002. Curves and Surfaces for CAGD: A Practical Guide. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
    15. M. Fatemi, A. Amini, L. Baboulaz, and M. Vetterli. 2016. Shapes From Pixels. IEEE TIP 25, 3 (2016), 1193–1206.Google ScholarDigital Library
    16. Raanan Fattal. 2007. Image Upsampling via Imposed Edge Statistics. In ACM SIGGRAPH. Article 95. Google ScholarDigital Library
    17. Jean-Dominique Favreau, Florent Lafarge, and Adrien Bousseau Bousseau. 2017. Photo2ClipArt: Image Abstraction and Vectorization Using Layered Linear Gradients. ACM TOG 36, 6 (2017). https://hal.inria.fr/hal-01581981 Google ScholarDigital Library
    18. M. A. T. Figueiredo, J. LeitÃčo, and A. K. Jain. 2000. Unsupervised contour representation and estimation using B-splines and a minimum description length criterion. IEEE TIP 9, 6 (2000), 1075–187. Google ScholarDigital Library
    19. Shachar Fleishman, Daniel Cohen-Or, and Cláudio T. Silva. 2005. Robust Moving Least-squares Fitting with Sharp Features. ACM TOG 24, 3 (2005), 544–552. Google ScholarDigital Library
    20. Herbert Freeman and Larry S. Davis. 1977. A corner-finding algorithm for chain-coded curves. IEEE Transactions on computers 26, 3 (1977), 297–303. Google ScholarDigital Library
    21. Daniel Glasner, Shai Bagon, and Michal Irani. 2009. Super-Resolution from a Single Image. In IEEE ICCV.Google Scholar
    22. Chris Harris and Mike Stephens. 1988. A combined corner and edge detector.. In Alvey vision conference, Vol. 15. 50.Google Scholar
    23. Robert Hess and David Field. 1999. Integration of contours: new insights. Trends in cognitive sciences 3, 12 (1999), 480–486.Google Scholar
    24. Hsieh Hou and H Andrews. 1978. Cubic splines for image interpolation and digital filtering. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, 6 (1978), 508–517.Google ScholarCross Ref
    25. Xie Jun, Winnemöller Holger, Li Wilmot, and Schiller Stephen. 2017. Interactive Vectorization. In ACM SIGCHI. Google ScholarDigital Library
    26. Michael Kass, Andrew Witkin, and Demetri Terzopoulos. 1988. Snakes: Active contour models. IJCV 1, 4 (1988), 321–331.Google ScholarCross Ref
    27. Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee. 2016. Accurate image super-resolution using very deep convolutional networks. (2016), 1646–1654.Google Scholar
    28. K. Koffka. 1955. Principles of Gestalt Psychology. Routledge & K. Paul.Google Scholar
    29. Johannes Kopf and Dani Lischinski. 2011. Depixelizing Pixel Art. ACM TOG 30, 4 (2011), 99:1–99:8. Google ScholarDigital Library
    30. DJ Langridge. 1982. Curve encoding and the detection of discontinuities. Computer Graphics and Image Processing 20, 1 (1982), 58–71.Google ScholarCross Ref
    31. Gregory Lecot and Bruno Levy. 2006. Ardeco: Automatic Region Detection and Conversion. In EGSR. 349–360. Google ScholarDigital Library
    32. Xin Li and Michael T Orchard. 2001. New edge-directed interpolation. IEEE TIP 10, 10 (2001), 1521–1527. Google ScholarDigital Library
    33. Yangyan Li, Xiaokun Wu, Yiorgos Chrysanthou, Andrei Sharf, Daniel Cohen-Or, and Niloy J. Mitra. 2011. GlobFit: Consistently Fitting Primitives by Discovering Global Relations. ACM TOG 30, 4 (2011), 52:1–52:12. Google ScholarDigital Library
    34. Jyh-Ming Lien and Nancy M. Amato. 2004. Approximate Convex Decomposition of Polygons. In Proc. Symp. Computational Geometry. 17–26. Google ScholarDigital Library
    35. Yang Liu and Wenping Wang. 2008. A Revisit to Least Squares Orthogonal Distance Fitting of Parametric Curves and Surfaces. In Proc. Advances in Geometric Modeling and Processing. 384–397. Google ScholarDigital Library
    36. Zhaoliang Lun, Evangelos Kalogerakis, and Alla Sheffer. 2015. Elements of Style: Learning Perceptual Shape Style Similarity. ACM Trans. Graph. 34, 4 (2015), 84:1–84:14. Google ScholarDigital Library
    37. Andrea Mazzoleni. 2001. Scale2x. http://www.scale2x.it/. (2001).Google Scholar
    38. James McCrae and Karan Singh. 2008. Sketching Piecewise Clothoid Curves. In Proc. Sketch-Based Interfaces and Modeling. Google ScholarDigital Library
    39. James McCrae and Karan Singh. 2011. Neatening Sketched Strokes Using Piecewise French Curves. In Proc. EG Symposium on Sketch-Based Interfaces and Modeling. 141–148. Google ScholarDigital Library
    40. Gerard Medioni and Yoshio Yasumoto. 1986. Corner detection and curve representation using cubic B-splines. In Robotics and Automation. Proceedings. 1986 IEEE International Conference on, Vol. 3. IEEE, 764–769.Google ScholarCross Ref
    41. Ravish Mehra, Qingnan Zhou, Jeremy Long, Alla Sheffer, Amy Gooch, and Niloy J. Mitra. 2009. Abstraction of Man-Made Shapes. ACM TOG 28, 5 (2009), 137:1–137:10. Google ScholarDigital Library
    42. Kamal Nasrollahi and Thomas B. Moeslund. 2014. Super-resolution: A Comprehensive Survey. Mach. Vision Appl. 25, 6 (Aug. 2014), 1423–1468. Google ScholarDigital Library
    43. 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. ACM TOG 27, 3 (2008). Google ScholarDigital Library
    44. 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. Journal of Machine Learning Research 12 (2011), 2825–2830. Google ScholarDigital Library
    45. Edward Rosten, Reid Porter, and Tom Drummond. 2010. Faster and better: A machine learning approach to corner detection. IEEE transactions on pattern analysis and machine intelligence 32, 1 (2010), 105–119. Google ScholarDigital Library
    46. S Rasoul Safavian and David Landgrebe. 1991. A survey of decision tree classifier methodology. IEEE transactions on systems, man, and cybernetics 21, 3 (1991), 660–674.Google Scholar
    47. ScanFont. 2017. Font Lab, http://old.fontlab.eom/font-converter/scanfont//. (2017).Google Scholar
    48. Peter Selinger. 2003. Potrace: a polygon-based tracing algorithm. In http://potrace.sourceforge.net.Google Scholar
    49. Jianbo Shi et al. 1994. Good features to track. In Computer Vision and Pattern Recognition, 1994. IEEE Conference on. IEEE, 593–600.Google Scholar
    50. Maxim Stepin. 2003. Hqx. http://web.archive.org/web/20070717064839/www.hiend3d.com/hq4x.html. (2003).Google Scholar
    51. Jian Sun, Lin Liang, Fang Wen, and Heung-Yeung Shum. 2007. Image Vectorization Using Optimized Gradient Meshes. In ACM SIGGRAPH. Article 11. Google ScholarDigital Library
    52. Daniel Sýkora, Jan Buriánek, and Jiří Žára. 2005. Sketching Cartoons by Example. In Proc. Sketch-Based Interfaces and Modeling. 27–34.Google Scholar
    53. Vector Magic. 2017. Cedar Lake Ventures http://vectormagic.com/. (2017).Google Scholar
    54. 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
    55. C. Wang, J. Zhu, Y. Guo, and W. Wang. 2017. Video Vectorization via Tetrahedral Remeshing. IEEE TIP 26, 4 (April 2017), 1833–1844. Google ScholarDigital Library
    56. Zhaowen Wang, Ding Liu, Jianchao Yang, Wei Han, and Thomas Huang. 2015. Deep networks for image super-resolution with sparse prior. In IEEE ICCV. 370–378. Google ScholarDigital Library
    57. M. Weber and B. Herzog. 2004. Autotrace. http://autotrace.sourceforge.net. (2004).Google Scholar
    58. Tian Xia, Binbin Liao, and Yizhou Yu. 2009. Patch-based Image Vectorization with Automatic Curvilinear Feature Alignment. ACM TOG 28, 5 (2009). Google ScholarDigital Library
    59. Chih-Yuan Yang, Chao Ma, and Ming-Hsuan Yang. 2014. Single-Image Super-Resolution: A Benchmark. In ECCV, David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars (Eds.). Springer International Publishing, 372–386.Google Scholar
    60. M. Yang, H. Chao, C. Zhang, J. Guo, L. Yuan, and J. Sun. 2016. Effective Clipart Image Vectorization through Direct Optimization of Bezigons. IEEE TVCG 22, 2 (2016), 1063–1075. Google ScholarDigital Library
    61. Kwang Moo Yi, Eduard Trulls, Vincent Lepetit, and Pascal Fua. 2016. Lift: Learned invariant feature transform. In European Conference on Computer Vision. Springer. 467–483.Google ScholarCross Ref
    62. Song-Hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, and Ralph R. Martin. 2009. Vectorizing Cartoon Animations. IEEE TVCG 15, 4 (2009), 618–629. Google ScholarDigital Library

ACM Digital Library Publication: