“Automatic and topology-preserving gradient mesh generation for image vectorization” by Lai, Hu and Martin

Gradient mesh vector graphics representation, used in commercial software, is a regular grid with specified position and color, and their gradients, at each grid point. Gradient meshes can compactly represent smoothly changing data, and are typically used for single objects. This paper advances the state of the art for gradient meshes in several significant ways. Firstly, we introduce a topology-preserving gradient mesh representation which allows an arbitrary number of holes. This is important, as objects in images often have holes, either due to occlusion, or their 3D structure. Secondly, our algorithm uses the concept of image manifolds, adapting surface parameterization and fitting techniques to generate the gradient mesh in a fully automatic manner. Existing gradient-mesh algorithms require manual interaction to guide grid construction, and to cut objects with holes into disk-like regions. Our new algorithm is empirically at least 10 times faster than previous approaches. Furthermore, image segmentation can be used with our new algorithm to provide automatic gradient mesh generation for a whole image. Finally, fitting errors can be simply controlled to balance quality with storage.

1. Barrett, W., and Cheney, A. S. 2002. Object-based image editing. ACM Transactions on Graphics 21, 3, 777–784. Google ScholarDigital Library
2. Demaret, L., Dyn, N., and Iske, A. 2006. Image compression by linear splines over adaptive triangulations. Signal Processing 86, 7, 1604–1616. Google ScholarDigital Library
3. Dori, D., and Liu, W. 1999. Sparse pixel vectorization: an algorithm and its performance evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence 21, 3, 202–215. Google ScholarDigital Library
4. Felzenszwalb, P. F., and Huttenlocher, D. P. 2004. Efficient graph-based image segmentation. International Journal of Computer Vision 59, 2, 167–181. Google ScholarDigital Library
5. Ferguson, J. 1964. Multivariable curve interpolation. Journal of the ACM 11, 2, 221–228. Google ScholarDigital Library
6. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modeling, IV: 157–186.Google ScholarCross Ref
7. Floater, M. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
8. Jarvis, J. F., Judice, C. N., and Ninke, W. H. 1976. A survey of techniques for the display of continuous tone pictures on bilevel displays. Computer Graphics and Image Processing 5, 1, 13–40.Google ScholarCross Ref
9. Kimmel, R., Malladi, R., and Sochen, N. 2000. Image as embedded maps and minimal surfaces: movies, color, texture and volumetric medical images. International Journal of Computer Vision 39, 2, 111–129. Google ScholarDigital Library
10. Lai, Y.-K., Hu, S.-M., and Pottmann, H. 2006. Surface fitting based on a feature sensitive parameterization. Computer-Aided Design 38, 4, 800–807.Google ScholarCross Ref
11. Lecot, G., and Levy, B. 2006. ARDECO: Automatic region detection and conversion. In Proc. Eurographics Symposium on Rendering, 349–360. Google ScholarDigital Library
12. Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 2, 228–242. Google ScholarDigital Library
13. Manay, S., Hong, B.-W., and Yezzi, A. J. 2004. Integral invariant signatures. In Proc. European Conference on Computer Vision, 87–99.Google Scholar
14. Matusik, W., Zwicker, M., and Durand, F. 2005. Texture design using a simplicial complex of morphable textures. ACM Transactions on Graphics 24, 3, 787–794. Google ScholarDigital Library
15. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition-of-unity implicits. ACM Transactions on Graphics 22, 3, 463–470. Google ScholarDigital Library
16. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: a vector representaiton for smooth-shaded images. ACM Transactions on Graphics 27, 3, 92:1–8. Google ScholarDigital Library
17. Price, B., and Barrett, W. 2006. Object-based vectorization for interactive image editing. The Visual Computer 22, 9–11, 661–670. Google ScholarDigital Library
18. Rother, C., Kolmogorov, V., and Blake, A. 2004. “Grab-Cut”: interactive foreground extraction using iterated graph cuts. ACM Transactions on Graphics 23, 3, 309–314. Google ScholarDigital Library
19. Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proc. ACM SIGGRAPH, 409–416. Google ScholarDigital Library
20. Sun, J., Liang, L., Wen, F., and Shum, H.-Y. 2007. Image vectorization using optimized gradient meshes. ACM Transactions on Graphics 26, 3, 11:1–7. Google ScholarDigital Library
21. Swaminarayan, S., and Prasad, L. 2006. Rapid automated polygonal image decomposition. In Proc. Applied Imagery and Pattern Recognition Workshop, 28–33. Google ScholarDigital Library
22. Tumblin, J., and Choudhury, P. 2004. Bixels: Picture samples with sharp embedded boundaries. In Proc. Eurographics Symposium on Rendering, 186–196. Google ScholarDigital Library
23. Wang, Z., Bovik, A. C., Sheikh, H. R., and Simoncelli, E. P. 2004. Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing 13, 4, 600–612. Google ScholarDigital Library
24. Wolberg, G., and Alfy, I. 1999. Monotonic cubic spline interpolation. In Proc. Computer Graphics International, 188–195. Google ScholarDigital Library
25. Yin, X., Dai, J., Yau, S.-T., and Gu, X. 2008. Slit map: conformal parameterization for multiply connected surfaces. In Proc. Geometric Modeling and Processing, 410–422. Google ScholarDigital Library
26. Yoshizawa, S., Belyaev, A., and Seidel, H.-P. 2004. A fast and simple stretch-minimizing mesh parameterization. In Proc. Shape Modeling International, 200–208. Google ScholarDigital Library
27. Zhang, S.-H., Chen, T., Zhang, Y.-F., Hu, S.-M., and Martin, R. R. 2009. Vectorizing cartoon animations. IEEE Transactions on Visualization and Computer Graphics, IEEE computer Society Digital Library, doi:10.1109/TVCG.2009.9. Google ScholarDigital Library
28. Zou, J. J., and Yan, H. 2001. Cartoon image vectorization based on shape subdivision. In Proc. Computer Graphics International, 225–231. Google ScholarDigital Library