{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:33:26Z","timestamp":1787322806904,"version":"build-2736575974"},"reference-count":112,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100007567","name":"City University of Hong Kong","doi-asserted-by":"publisher","award":["7200779"],"award-info":[{"award-number":["7200779"]}],"id":[{"id":"10.13039\/100007567","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["584960"],"award-info":[{"award-number":["584960"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Image vectorization converts raster images into vector graphics composed of regions separated by curves. Typical vectorization methods first define the regions by grouping similar colored regions by color quantization, then approximate their boundaries by B\u00e9zier curves. In that way, the raster input is converted into an SVG format parameterizing the regions\u2019 colors and the B\u00e9zier control points. This compact representation has many graphical applications thanks to its universality and resolution-independence. In this paper, we remark that image vectorization is nothing but an image segmentation, and that it can be built by fine to coarse region merging. Our analysis of the problem leads us to propose a vectorization method that alternates region merging and curve smoothing. We formalize the method by alternate operations on the dual and primal graph induced by any domain partition. In that way, we address a limitation of current vectorization methods, which separate the update of regional information from curve approximation. We formalize region merging methods by associating them with various gain functionals, including the classic Beaulieu\u2013Goldberg and Mumford\u2013Shah functionals. More generally, we introduce and compare region merging criteria that involve the number of regions, the scale, the area, and the internal standard deviation of each region. We also show that the curve smoothing, implicit in all vectorization methods, can be performed by the shape-preserving affine scale-space. We extend this flow to a network of curves and give a sufficient condition for the topological preservation of the segmentation. The general vectorization method that follows from this analysis shows explainable behaviors, explicitly controlled by a few intuitive parameters. It is experimentally compared to state-of-the-art software and proved to have comparable or superior fidelity and cost efficiency.<\/jats:p>","DOI":"10.1137\/24m1696469","type":"journal-article","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T07:57:02Z","timestamp":1755849422000},"page":"1742-1787","source":"Crossref","is-referenced-by-count":1,"title":["A Formalization of Image Vectorization by Region Merging"],"prefix":"10.1137","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-4690-4007","authenticated-orcid":true,"given":"Roy Y.","family":"He","sequence":"first","affiliation":[{"name":"Department of Mathematics, City University of Hong Kong, Kowloon."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sung Ha","family":"Kang","sequence":"additional","affiliation":[{"name":"School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6108-897X","authenticated-orcid":true,"given":"Jean-Michel","family":"Morel","sequence":"additional","affiliation":[{"name":"Department of Mathematics, City University of Hong Kong, Kowloon."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,8,22]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.117927"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/34.295913"},{"key":"ref3","unstructured":"Adobe, Adobe illustrator, https:\/\/www.adobe.com\/products\/illustrator.html."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2023.3308391"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-004-0628-9"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"L. Alvarez, Corner detection using the affine morphological scale space, in International Conference on Scale Space and Variational Methods in Computer Vision, Springer, 2017, pp. 29\u201340.","DOI":"10.1007\/978-3-319-58771-4_3"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00375127"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007959616598"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/pl00011302"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160430805"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214446558"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-98-00262-8"},{"key":"ref13","first-page":"1027","volume-title":"Soda","volume":"7","author":"Arthur D.","year":"2007"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1037\/h0043921"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-44588-5"},{"key":"ref16","volume-title":"Perception of Pixelated Images","author":"Bachmann T.","year":"2016"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/34.16711"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00158168"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"H. Bezerra, E. Eisemann, D. DeCarlo, and J. Thollot, Diffusion constraints for vector graphics, in Proceedings of the 8th International Symposium on Non-photorealistic Animation and Rendering, 2010, pp. 35\u201342.","DOI":"10.1145\/1809939.1809944"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/83.277898"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(70)90008-1"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1201\/9781420041484-9"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/b10404"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007979827043"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0732085"},{"key":"ref26","first-page":"876","volume-title":"IPCV","author":"Celebi M. E.","year":"2009"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-023-10406-6"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/83.902291"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"T. F. Chan and L. A. Vese, A level set algorithm for minimizing the Mumford-Shah functional in image processing, in Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision, IEEE, 2001, pp. 161\u2013168.","DOI":"10.1109\/VLSM.2001.938895"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2004.836543"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(01)00054-1"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.5201\/ipol.2017.212"},{"key":"ref33","unstructured":"D. Crisp and G. Newsam, A fast, efficient segmentation algorithm based on region merging, in Proc. Image Vision Computing New Zealand 2000, 2000, pp. 180\u2013185."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1088\/0954-898X_5_3_003"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tics.2019.02.004"},{"key":"ref36","unstructured":"M. Dziuba, I. Jarsky, V. Efimova, and A. Filchenkov, Image Vectorization: A Review, preprint, https:\/\/arxiv.org\/abs\/2306.06441, 2023."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142998337533"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008183703117"},{"key":"ref39","first-page":"565","volume-title":"C. R. Acad. Sci. Paris S\u00e9r. I Math.","volume":"317","author":"Faugeras O.","year":"1993"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130888"},{"key":"ref41","unstructured":"J. Ferraiolo, F. Jun, and D. Jackson, Scalable vector graphics (SVG) 1.0 specification, iuniverse Bloomington, 2000."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024200"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214439902"},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"M. Gervautz and W. Purgathofer, A simple method for color quantization: Octree quantization, in New Trends in Computer Graphics: Proceedings of CG International\u201988, Springer, 1988, pp. 219\u2013231.","DOI":"10.1007\/978-3-642-83492-9_20"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/100814731"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214441371"},{"key":"ref47","first-page":"60","volume":"12","author":"Haralick R. M.","year":"1980","journal-title":"Comput. Vision. Graph."},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/83.730380"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.5201\/ipol.2021.296"},{"key":"ref50","doi-asserted-by":"crossref","unstructured":"Y. He, S. H. Kang, and J.M. Morel, Accurate silhouette vectorization by affine scale-space, in 2021 IEEE International Conference on Image Processing (ICIP), IEEE, 2021, pp. 1539\u20131543.","DOI":"10.1109\/ICIP42928.2021.9506518"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-021-01053-z"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"Y. He, S. H. Kang, and J.M. Morel, Vectorizing images of any size, in 2022 IEEE International Conference on Image Processing (ICIP), IEEE, 2022, pp. 816\u2013820.","DOI":"10.1109\/ICIP46576.2022.9897200"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.5201\/ipol.2023.401"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-023-01149-8"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"Y. He, S. H. Kang, and J.M. Morel, Viva: A variational image vectorization algorithm on dual-primal graph pairs, in 2023 IEEE International Conference on Image Processing (ICIP), IEEE, 2023, pp. 1285\u20131289.","DOI":"10.1109\/ICIP49359.2023.10222783"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1145\/965145.801294"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.127"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321956"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214444099"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.4310\/AJM.1998.v2.n1.a2"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01877.x"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1137\/060662708"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1016\/j.na.2012.08.014"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1007\/BF00133570"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/0731015"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1364\/JOSA.61.000001"},{"key":"ref67","unstructured":"G. Lecot and B. Levy, Ardeco: Automatic region detection and conversion, in 17th Eurographics Symposium on Rendering-EGSR\u201906, 2006, pp. 349\u2013360."},{"key":"ref68","volume-title":"Introduction to Algorithms","volume":"3","author":"Leiserson C. E.","year":"994"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17563-8_6"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417763"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1137\/S1540345902410846"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref73","doi-asserted-by":"crossref","unstructured":"X. Ma, Y. Zhou, X. Xu, B. Sun, V. Filev, N. Orlov, Y. Fu, and H. Shi, Towards layer-wise image vectorization, in Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, 2022, pp. 16314\u201316323.","DOI":"10.1109\/CVPR52688.2022.01583"},{"key":"ref74","unstructured":"A. Magni, C. Mantegazza, and M. Novaga, Motion by Curvature of Planar Networks II, preprint, https:\/\/arxiv.org\/abs\/1301.3352, 2013."},{"key":"ref75","first-page":"235","volume":"3","author":"Mantegazza C.","year":"2004","journal-title":"Ann. Sc. Norm. Sup. Pisa"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1994.1105"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1109\/83.661191"},{"key":"ref78","volume-title":"Variational Methods in Image Segmentation: With Seven Image Processing Experiments","volume":"14","author":"Morel J.-M.","year":"2012"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160420503"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1145\/2421636.2421640"},{"key":"ref81","first-page":"339","volume":"319","author":"Olver P. J.","year":"1994","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. I Math."},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1109\/78.107417"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360691"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(88)90002-2"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1167\/jov.23.1.9"},{"key":"ref86","first-page":"360","volume":"1","author":"Pavlidis T.","year":"1972","journal-title":"Comput. Vision. Graph."},{"key":"ref87","doi-asserted-by":"crossref","unstructured":"T. Pock, D. Cremers, H. Bischof, and A. Chambolle, An algorithm for minimizing the Mumford-Shah functional, in 2009 IEEE 12th International Conference on Computer Vision, IEEE, 2009, pp. 1133\u20131140.","DOI":"10.1109\/ICCV.2009.5459348"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.10.014"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.3758\/BF03206147"},{"key":"ref90","doi-asserted-by":"crossref","unstructured":"P. Reddy, M. Gharbi, M. Lukac, and N. J. Mitra, Im2vec: Synthesizing vector graphics without vector supervision, in Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 7342\u20137351.","DOI":"10.1109\/CVPR46437.2021.00726"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican1290-84"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1145\/249204.249205"},{"key":"ref93","unstructured":"J.L. Rose, T. Grenier, C. Revol-Muller, and C. Odet, Unifying variational approach and region growing segmentation, in 2010 18th European Signal Processing Conference, IEEE, 2010, pp. 1781\u20131785."},{"key":"ref94","first-page":"10","volume":"3","author":"Salman N.","year":"2006","journal-title":"Int. Arab J. Inf. Technol."},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2009.2032310"},{"key":"ref96","doi-asserted-by":"crossref","unstructured":"G. Sapiro and D. L. Ringach, Anisotropic diffusion of multivalued images, in ICAOS\u201996: 12th International Conference on Analysis and Optimization of Systems Images, Wavelets and PDEs, 1996, Springer, Paris, 2005, pp. 134\u2013140.","DOI":"10.1007\/3-540-76076-8_126"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1007\/BF01420591"},{"key":"ref98","unstructured":"E. Saraee, M. Jalal, and M. Betke, Savoias: A Diverse, Multi-Category Visual Complexity Dataset, preprint, https:\/\/arxiv.org\/abs\/1810.01771, 2018."},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2020.102949"},{"key":"ref100","unstructured":"P. Selinger, Potrace: A polygon-based tracing algorithm, 2003."},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1137\/S003613999935799X"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276391"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1137\/S0036139994266311"},{"key":"ref104","unstructured":"T. C. Tao and D. J. Crisp, A useful bound for region merging algorithms in a bayesian model, in Proceedings of the 26th Australasian Computer Science Conference-Volume, Vol. 16, 2003, pp. 95\u2013100."},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1137\/100790197"},{"key":"ref106","volume-title":"A survey of smooth vector graphics: Recent advances in representation, creation, rasterization and image vectorization","author":"Tian X.","year":"2022"},{"key":"ref107","doi-asserted-by":"publisher","DOI":"10.1017\/S0952523808080930"},{"key":"ref108","doi-asserted-by":"crossref","unstructured":"Y. Vinker, Y. Alaluf, D. Cohen-Or, and A. Shamir, Clipascene: Scene sketching with different types and levels of abstraction, in Proceedings of the IEEE\/CVF International Conference on Computer Vision, 2023, pp. 4146\u20134156.","DOI":"10.1109\/ICCV51070.2023.00383"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530068"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2018.2839891"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.9"},{"key":"ref112","doi-asserted-by":"publisher","DOI":"10.1109\/34.537343"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1696469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:26:37Z","timestamp":1787318797000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1696469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,22]]},"references-count":112,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1137\/24M1696469"],"URL":"https:\/\/doi.org\/10.1137\/24m1696469","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,22]]}}}