[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Topology- and Perception-Aware Image Vectorization

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

We propose a new color image vectorization method converting raster images to resolution-independent scalable vector graphics. Starting from a quantized raster image, the method builds a hierarchical structure to represent its discontinuity set. The lowest level elements, called curve-elements, separate exactly two colors and end at T-junctions or X-junctions. The middle-level objects, called curvebases, are concatenations of curve-elements following perceptual rules and representing the apparent contours of objects. On the highest level, the jump set coincides with the discontinuity set of the quantized image input. A geometric filtering method removes pixelization effects by affine shortening of the curvebases while resolving the induced topological changes. All junctions are preserved, thus maintaining the highest level of perceptual fidelity even on tiny pixel art images. A single parameter controls the simplification of curves between two junctions. Theoretical bounds are given to guarantee the method’s topological consistency. This allows the method to be iterated such that it yields a smoothing semigroup. In both qualitative and quantitative experiments, our method compares favorably to multiple state-of-the-art algorithms and software.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25

Similar content being viewed by others

Data Availability

The datasets analyzed for vectorizing photographic images are available in the IPOL demo https://ipolcore.ipol.im/demo/clientApp/demo.html?id=5555531082036. The datasets analyzed for vectorizing pixel art are available in the published articles [10, 24].

Notes

  1. When presenting the results by [19], since the available program only vectorizes the boundaries without correctly rendering the colors, we manually filled in the corresponding colors.

References

  1. Adobe Illustrator. https://www.adobe.com/products/illustrator.html

  2. Álvarez, L., Guichard, F., Lions, P.-L., Morel, J.-M.: Axiomes et équations fondamentales du traitement d’images.(Analyse multiéchelle et edp). Comptes rendus de l’Académie des sciences. Série 1, Mathématique 315, 2, 135–138 (1992)

  3. Angenent, S., Sapiro, G., Tannenbaum, A.: On the affine heat equation for non-convex curves. J. Am. Math. Soc. 11(3), 601–634 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bowler, J., Brown, C., Capsimalis, M., Cohn, R., Deweese Cole, L., et al.: Scalable vector graphics (svg) 1.0 specification. World Wide Web Consortium (2001)

  5. Caselles, V., Coll, B., Morel, J.-M.: Scale space versus topographic map for natural images. In International conference on scale-space theories in computer vision. Springer, 29–49 (1997)

  6. Caselles, V., Coll, B., Morel, J.-M.: Topographic maps and local contrast changes in natural images. Int. J. Comput. Vis. 33(1), 5–27 (1999)

    Article  Google Scholar 

  7. Celebi, M.E.: Improving the performance of k-means for color quantization. Image Vis. Comput. 29(4), 260–271 (2011)

    Article  Google Scholar 

  8. Charles, D., Davies, E.R.: Properties of the mode filter when applied to colour images (2003)

  9. Ciomaga, A., Monasse, P., Morel, J.-M.: The image curvature microscope: accurate curvature computation at subpixel resolution. Image Process. Line 7(2017), 197–217 (2017)

    Article  MathSciNet  Google Scholar 

  10. Dominici, E.A., Schertler, N., Griffin, J., Hoshyari, S., Sigal, L., Sheffer, A.: PolyFit: perception-aligned vectorization of raster clip-art via intermediate polygonal fitting. ACM TOG 39(4), 77–1 (2020)

    Article  Google Scholar 

  11. Egiazarian, V., Voynov, O., Artemov, A., Volkhonskiy, D., Safin, A., Taktasheva, M., Zorin, D., Burnaev, E.: Deep vectorization of technical drawings. In: European conference on computer vision. Springer, 582–598, (2020)

  12. Freire, A.: Mean curvature motion of triple junctions of graphs in two dimensions. Comm. Partial Differ. Equ. 35(2), 302–327 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fuchs, W.: Experimentelle Untersuchungen uber das simultane Hintereinandersehen auf derselben Sehrichtung. Z. Psychol. 91(1923), 145–235 (1923)

    Google Scholar 

  14. Garcke, H., Nestler, B., Stoth, B.: A multiphase field concept: numerical simulations of moving phase boundaries and multiple junctions. SIAM J. Appl. Math. 60(1), 295–315 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gervautz, M., Purgathofer, W.: A simple method for color quantization: octree quantization. In: New trends in computer graphics. Springer, 219–231 (1988)

  16. Gibson, L., Lucas, D.: Vectorization of raster images using hierarchical methods. Comput. Graph. 20(1), 82–89 (1982)

    Google Scholar 

  17. He, Y., Kang, S.H., Morel, J.-M.: Silhouette Vectorization by Affine Scale-Space. J. Math. Imag. Vis. 2021, 1–16 (2021)

    MATH  Google Scholar 

  18. He, Y., Kang, S. H., Morel, J.-M.: Vectorizing images of any size. In: IEEE International conference on image processing (ICIP). IEEE (2022)

  19. Hoshyari, S., Dominici, E.A., Sheffer, A., Carr, N., Wang, Z., Ceylan, D., Shen, I.-C.: Perception-driven semi-structured boundary vectorization. ACM TOG 37(4), 1–14 (2018)

    Article  Google Scholar 

  20. Inkscape. https://inkscape.org

  21. Jimenez, J., Navalon, J.L.: Some experiments in image vectorization. IBM J. Res. Dev. 26(6), 724–734 (1982)

    Article  Google Scholar 

  22. Kanizsa, G.: Organization in Vision: Essays on Gestalt Perception. Praeger Publishers (1979)

    Google Scholar 

  23. Kanizsa, G.: Seeing and thinking. Acta Physiol. 59(1), 23–33 (1985)

    Google Scholar 

  24. Kopf, J.: Depixelizing pixel art. SIGGRAPH 30, 99:1-99:8 (2011)

    Google Scholar 

  25. Kopf, J., Lischinski, D.: Depixelizing pixel art. In ACM SIGGRAPH. 1–8 (2011b)

  26. Lai, Y.-K., Shi-Min, H., Martin, R.R.: Automatic and topology-preserving gradient mesh generation for image vectorization. ACM TOG 28(3), 1–8 (2009)

    Article  Google Scholar 

  27. Leclerc, Y.G., Zucker, S.W.: The local structure of image discontinuities in one dimension. IEEE PAMI 3(1987), 341–355 (1987)

    Article  Google Scholar 

  28. Lecot, G., Levy, B.: ARDECO: Automatic region detection and conversion. In EGSR. 349–360 (2006)

  29. Lindeberg, T.: Junction detection with automatic selection of detection scales and localization scales. In: Proceedings of 1st international conference on image processing, 1. IEEE, 924–928 (1994)

  30. Liu, C., Wu, J., Kohli, P., Furukawa, Y.: Raster-to-vector: Revisiting floorplan transformation. In ICIP. 2195–2203 (2017)

  31. Mantegazza, C., Novaga, M., Pluda, A.: Motion by curvature of networks with two triple junctions. Geom. Flows 2(1), 18–48 (2016)

    MathSciNet  MATH  Google Scholar 

  32. Merriman, B., Bence, J.K., Osher, S.J.: Motion of multiple junctions: a level set approach. J. Comput. Phys. 112(2), 334–363 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  33. Moisan, L.: Affine plane curve evolution: a fully consistent scheme. IEEE Trans. Image Process. 7(3), 411–420 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  34. Montero, A.S., Lang, J.: Skeleton pruning by contour approximation and the integer medial axis transform. Comput. Graph. 36(5), 477–487 (2012)

    Article  Google Scholar 

  35. Nitzberg, M., Mumford, D. B.: (1990). The 2.1-D sketch. IEEE Computer Society Press

  36. Nitzberg, M., Mumford, D., Shiota, T., Mumford, D.: Filtering, segmentation and depth. Lecture Notes in Computer Science 662 (1993)

  37. Noble, J.A.: Finding half boundaries and junctions in images. Image Vis. Comput. 10(4), 219–232 (1992)

    Article  Google Scholar 

  38. Olsen, S., Gooch, B.: x Image simplification and vectorization. In ACM SIGGRAPH. 65–74 (2008)

  39. Orchard, M.T., Bouman, C.A., et al.: Color quantization of images. IEEE Trans. Signal Process. 39(12), 2677–2690 (1991)

    Article  Google Scholar 

  40. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., Salesin, D.: Diffusion curves: a vector representation for smooth-shaded images. ACM TOG 27(3), 1–8 (2008)

    Article  Google Scholar 

  41. Owen, C. B., Makedon, F.: High quality alias free image rotation. In: Conference record of the thirtieth asilomar conference on signals, systems and computers. Vol. 1. IEEE, 115–119 (1996)

  42. Park, W., Leibon, G., Rockmore, D.N., Chirikjian, G.S.: Accurate image rotation using Hermite expansions. IEEE Trans. Image Process. 18(9), 1988–2003 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  43. Price, B., Barrett, W.: Object-based vectorization for interactive image editing. Vis. Comput. 22(9), 661–670 (2006)

    Article  Google Scholar 

  44. Quint, A.: Scalable vector graphics. IEEE Multimedia 10(3), 99–102 (2003)

    Article  Google Scholar 

  45. Sapiro, G., Tannenbaum, A.: Affine invariant scale-space. Int. J. Comput. Vis. 11(1), 25–44 (1993)

    Article  MATH  Google Scholar 

  46. Selinger, P.: Potrace: a polygon-based tracing algorithm. Potrace (online), http://potrace.sourceforge.net/potrace.pdf (2009-07-01) 2 (2003)

  47. Sloan, K.R., Tanimoto, S.L.: Progressive refinement of raster images. IEEE Trans. Comput. 28(11), 871–874 (1979)

    Article  Google Scholar 

  48. Sun, J., Liang, L., Wen, F., Shum, H.-Y.: Image vectorization using optimized gradient meshes. ACM TOG 26, 11-es (2007)

    Article  Google Scholar 

  49. Swaminarayan, S., Prasad, L.: Rapid automated polygonal image decomposition. In AIPR. IEEE, 28–28 (2006)

  50. Taylor, J.E.: Motion of curves by crystalline curvature, including triple junctions and boundary points. Proc. Symp. Pure Math. 54, 417–438 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  51. Tombre K., Tabbone, S.: Vectorization in graphics recognition: to thin or not to thin. In ICPR. 2, 91–96 (2000)

  52. Vector Magic. https://vectormagic.com

  53. Weiman, C.F.R.: Continuous anti-aliased rotation and zoom of raster images. In: Proceedings of the 7th annual conference on Computer graphics and interactive techniques. 286–293 (1980)

  54. Xia, T., Liao, B., Yizhou, Yu.: Patch-based image vectorization with automatic curvilinear feature alignment. ACM TOG 28(5), 1–10 (2009)

    Article  Google Scholar 

  55. Xumin, L., Xue, Y.: Research on vectorization of weather radar image. Proc. Eng. 15(2011), 1298–1302 (2011)

    Article  Google Scholar 

  56. Yang, H.-M., Lu, J.-J., Lee, H.-J.: A Bezier curve-based approach to shape description for Chinese calligraphy characters. In ICDAR. IEEE, 276–280 (2001)

  57. Zhao, H.-K., Chan, T., Merriman, B., Osher, S.: A variational level set approach to multiphase motion. J. Comput. Phys. 127(1), 179–195 (1996)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai, China

    Yuchen He

  2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA

    Sung Ha Kang

  3. Centre Borelli, École Normale Supérieure Paris-Saclay, Paris, France

    Jean-Michel Morel

Authors
  1. Yuchen He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sung Ha Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jean-Michel Morel
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors jointly wrote the main manuscript text. Yuchen He implemented the algorithm, produced the experiments, and prepared the figures. All authors reviewed the manuscript.

Corresponding author

Correspondence to Yuchen He.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An online demo of the method is available here: https://ipolcore.ipol.im/demo/clientApp/demo.html?id=5555531082036.

Appendix A Intersection Test for Two Line Segments

Appendix A Intersection Test for Two Line Segments

This technique is classical in computational geometry, and we state the details for completeness and reproducibility. Suppose we have two line segments \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\), the task is to determine whether they intersect, and if they do, whether they intersect at the segment’s interior or boundary, i.e., the end points. The key quantities for such decisions are

$$\begin{aligned}&q_0=\text {sign}\left( (P_1-P_0)\times (Q_0-P_0)\right) ,\\&q_1=\text {sign}\left( (P_1-P_0)\times (Q_1-P_0)\right) ,\\&p_0=\text {sign}\left( (Q_1-Q_0)\times (P_0-Q_0)\right) , \\&p_1=\text {sign}\left( (Q_1-Q_0)\times (P_1-Q_0)\right) . \end{aligned}$$

These signs indicate relative positions of the involved points. For example, \(q_0\) indicates by \(-1\), \(+1\), and 0, respectively, whether \(Q_0\) lies one the right-hand side of, or left-hand side of, or on the line passing through \(P_1\) and \(P_0\). We have the following cases:

  1. 1.

    \(q_0q_1<0\) and \(p_0p_1<0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(T^*\) that lies in the interior of both lines.

  2. 2.

    \(q_0q_1<0\), \(p_0=0\), and \(p_1\ne 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_0\), which is in the interior of \(\overline{Q_0Q_1}\).

  3. 3.

    \(q_0q_1<0\), \(p_0\ne 0\), and \(p_1= 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_1\), which is in the interior of \(\overline{Q_0Q_1}\).

  4. 4.

    \(p_0p_1<0\), \(q_0\ne 0\), \(q_1= 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(Q_1\), which is in the interior of \(\overline{P_0P_1}\).

  5. 5.

    \(p_0p_1 <0\), \(q_0= 0\), \(q_1\ne 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(Q_0\), which is in the interior of \(\overline{P_0P_1}\).

  6. 6.

    \(p_0=0\), \(p_1\ne 0\) \(q_0= 0\), \(q_1\ne 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_0=Q_0\).

  7. 7.

    \(p_0\ne 0\), \(p_1= 0\) \(q_0= 0\), \(q_1\ne 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_1=Q_0\).

  8. 8.

    \(p_0=0\), \(p_1\ne 0\) \(q_0\ne 0\), \(q_1= 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_0=Q_1\).

  9. 9.

    \(p_0\ne 0\), \(p_1= 0\) \(q_0\ne 0\), \(q_1= 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) intersect at \(P_1=Q_1\).

  10. 10.

    \(p_0=0\), \(p_1= 0\) \(q_0= 0\), \(q_1= 0\). \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) have infinitely many intersection points. This is practically impossible due to numerical perturbation.

  11. 11.

    Otherwise, \(\overline{P_0P_1}\) and \(\overline{Q_0Q_1}\) do not intersect.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

He, Y., Kang, S.H. & Morel, JM. Topology- and Perception-Aware Image Vectorization. J Math Imaging Vis 65, 874–893 (2023). https://doi.org/10.1007/s10851-023-01149-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-023-01149-8

Keywords

Search

Navigation