SCIENCE CHINA Information Sciences, Volume 60, Issue 3: 032104(2017) https://doi.org/10.1007/s11432-016-0130-4

Patch-based variational image approximation

More info
  • ReceivedFeb 24, 2016
  • AcceptedApr 22, 2016
  • PublishedOct 13, 2016


Vector graphic gives us a new solution to the representation of raster images. Among many types of vectorized representations, the most popular is mesh representation, which inherits the benefits of vector graphics. Inspired by mesh, we propose a novel patch-based representation for raster images, in which pixels are partitioned into regions, and pixels belonging to the same region are converted into a 3D point cloud and approximated by a 3D planar patch with proper boundaries in a variational way. The resulting patches are then encoded via a half-edge structure for storage. The key point is that the vertices of boundaries are not located on the very positions of sample points, i.e. converted pixels, but dependent on the optimal position of the patch, which theoretically reduces the fitting errors. Experiments show that our algorithm produces better results.

Funded by

National High Technology Research and Development Program of China(2013AA013903)



This work was supported by National High Technology Research and Development Program of China (Grant No. 2013AA013903).


[1] Cohen-Steiner D, Alliez P, Desbrun M. {Variational shape approximation}. ACM Trans Graphics, 2004, 23: 905-914 CrossRef Google Scholar

[2] Adams M D. {A flexible content-adaptive mesh-generation strategy for image representation}. IEEE Trans Image Process, {2011}, 20: 2414-2427 CrossRef Google Scholar

[3] Demaret L, Dyn N, Iske A. {Image compression by linear splines over adaptive triangulations}. Signal Process, {2006}, 86: 1604-1616 CrossRef Google Scholar

[4] Demaret L, Iske A, Mathematik Z, et al. {Advances in digital image compression by adaptive thinning}. Ann MCFA, 2004, 3: 105-109 Google Scholar

[5] Li P, Adams M D. {A tuned mesh-generation strategy for image representation based on data-dependent triangulation}. IEEE Trans Image Process, {2013}, {22}: 2004-2018 Google Scholar

[6] Yang Y Y, Wernick M N, Brankov J G. {A fast approach for accurate content-adaptive mesh generation}. IEEE Trans Image Process, {2003}, 12: 866-881 CrossRef Google Scholar

[7] Xia T, Liao B B, Yu Y Z. {Patch-based image vectorization with automatic curvilinear feature alignment}. ACM Trans Graphics, {2009}, 28: 115-881 Google Scholar

[8] Lai Y-K, Hu S-M, Martin R R. {Automatic and topology-preserving gradient mesh generation for image vectorization}. ACM Trans Graphics, {2009}, 28: 85-881 Google Scholar

[9] Sun J, Liang L, Wen F, et al. {Image vectorization using optimized gradient meshes}. ACM Trans Graphics, {2007}, 26: 11-881 Google Scholar

[10] Jeschke S, Cline D, Wonka P. {Estimating color and texture parameters for vector graphics}. Comput Graphics Forum, {2011}, 30: 523-532 CrossRef Google Scholar

[11] Orzan A, Bousseau A, Barla P, et al. {Diffusion curves: a vector representation for smooth-shaded images}. Commun ACM, {2013}, {56}: 101-108 Google Scholar

[12] Orzan A, Bousseau A, Winnemoeller H, et al. {Diffusion curves: a vector representation for smooth-shaded images}. ACM Trans Graphics, {2008}, 27: 101-108 Google Scholar

[13] Nagai Y, Ohtake Y, Yokota H, et al. {Boundary-representable partition of unity for image magnification}. Sci China Inf Sci, {2013}, 56: 112106-108 Google Scholar

[14] Wang M, Lai Y-K, Liang Y, et al. {BiggerPicture: data-driven image extrapolation using graph matching}. ACM Trans Graphics, {2014}, 33: 173-108 Google Scholar

[15] Hu S-M, Zhang F-L, Wang M, et al. {PatchNet: a patch-based image representation for interactive library-driven image editing}. ACM Trans Graphics, {2013}, 32: 196-108 Google Scholar

[16] Li H, Wu W, Wu E H. Robust interactive image segmentation via graph-based manifold ranking. Comput Visual Media, 2015, 1: 183-195 CrossRef Google Scholar

[17] Chen X W, Zhou B, Guo Y, et al. {Structure guided texture inpainting through multi-scale patches and global optimization for image completion}. Sci China Inf Sci, {2014}, 57: 012102-195 Google Scholar

[18] Lai Y-K, Martin R R. {Vertex location optimisation for improved remeshing}. Graphical Models, {2012}, {74}: 233-243 Google Scholar

[19] Douglas D H, Peucker T K. {Algorithms for the reduction of the number of points required to represent a digitized line or its caricature}. Int J Geogr Inf Geovisualization, 1973, 10: 112-122 CrossRef Google Scholar

[20] Zhang M, Yan W, Yuan C M, et al. {Curve fitting and optimal interpolation on CNC machines based on quadratic B-splines}. Sci China Inf Sci, {2011}, {54}: 1407-1418 Google Scholar

[21] Huynh-Thu Q, Ghanbari M. {Scope of validity of PSNR in image/video quality assessment}. Electron Lett, {2008}, 44: 800-835 CrossRef Google Scholar

[22] Wang Z, Bovik A C, Sheikh H R, et al. {Image quality assessment: from error visibility to structural similarity}. IEEE Trans Image Process, {2004}, 13: 600-612 CrossRef Google Scholar

[23] Sieger D, Botsch M. {Design, implementation, and evaluation of the surface\_mesh data structure}. In: Proceedings of the 20th International Meshing Roundtable, Paris, 2012. 533--550. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号