Image meshing via hierarchical optimization

Abstract

Vector graphic, as a kind of geometric representation of raster images, has many advantages, e.g., definition independence and editing facility. A popular way to convert raster images into vector graphics is image meshing, the aim of which is to find a mesh to represent an image as faithfully as possible. For traditional meshing algorithms, the crux of the problem resides mainly in the high non-linearity and non-smoothness of the objective, which makes it difficult to find a desirable optimal solution. To ameliorate this situation, we present a hierarchical optimization algorithm solving the problem from coarser levels to finer ones, providing initialization for each level with its coarser ascent. To further simplify the problem, the original non-convex problem is converted to a linear least squares one, and thus becomes convex, which makes the problem much easier to solve. A dictionary learning framework is used to combine geometry and topology elegantly. Then an alternating scheme is employed to solve both parts. Experiments show that our algorithm runs fast and achieves better results than existing ones for most images.

Keywords

Image meshing / Hierarchical optimization / Convexification

References

[1] Adams, M.D., 2011. A flexible content-adaptive mesh-generation strategy for image representation. IEEE Trans. Image Process., 20(9):2414–2427. http://dx.doi.org/10.1109/TIP.2011.2128336

[2] Demaret, L., Iske, A., 2004. Advances in digital image compressionbyadaptive thinning. Ann. MCFA, 3:105–109.

[3] Demaret, L., Dyn, N., Iske, A., 2006. Image compression by linear splines over adaptive triangulations. Signal Process., 86(7):1604–1616. http://dx.doi.org/10.1016/j.sigpro.2005.09.003

[4] Hu, S.M., Zhang, F.L., Wang, M., et al., 2013. PatchNet: a patch-basedimage representationforinteractivelibrary-driven image editing. ACM Trans. Graph., 32(6):196. http://dx.doi.org/10.1145/2508363.2508381

[5] Huynh-Thu, Q., Ghanbari, M., 2008. Scope of validity of PSNR in image/video quality assessment. . Electron. Lett., 44(13):800–801. http://dx.doi.org/10.1049/el:20080522

[6] Lai, Y.K., Hu, S.M., Martin, R.R., 2009. Automatic and topology-preserving gradient mesh generation for image vectorization. ACM Trans. Graph., 28(3):85. http://dx.doi.org/10.1145/1531326.1531391

[7] Lecot, G., Levy, B., 2006. Ardeco: automatic region detection and conversion. 17th Eurographics Symp. on Rendering, p.349–360. http://dx.doi.org/10.2312/EGWR/EGSR06/349-360

[8] Liao, Z.C., Hoppe, H., Forsyth, D., et al., 2012. A subdivision-based representation for vector image editing. IEEE Trans. Vis. Comput. Graph., 18(11):1858–1867. http://dx.doi.org/10.1109/TVCG.2012.76

[9] Liu, D.C., Nocedal, J., 1989. On the limited memory BFGS method for large-scale optimization. Math. Program., 45(3):503–528. http://dx.doi.org/10.1007/BF01589116

[10] Sieger, D., Botsch, M., 2012. Design, implementation, and evaluation of the surface_mesh data structure. Proc. 20th Int. Meshing Roundtable, p.533–550. http://dx.doi.org/10.1007/978-3-642-24734-7_29

[11] Sun, J.,Liang, L.,Wen, F., et al., 2007. Image vectorization using optimizedgradient meshes. ACMTrans. Graph., 26(3):11. http://dx.doi.org/10.1145/1239451.1239462

[12] Swaminarayan, S., Prasad, L., 2006. Rapid automated polygonal image decomposition. 35th IEEE Applied Imagery and Pattern Recognition Workshop, p.28–33. http://dx.doi.org/10.1109/AIPR.2006.30

[13] Xia, T., Liao, B.B., Yu, Y.Z., 2009. Patch-based image vectorization with automatic curvilinearfeature alignment. ACM Trans. Graph., 28(5):115. http://dx.doi.org/10.1145/1618452.1618461

[14] Xie, H., Tong, R.F., Zhang, Y., 2014. Image meshing via alternative optimization. J. Comput. Inform. Syst., 10(19):8209–8217. http://dx.doi.org/10.12733/jcis11723

[15] Xiong, S.Y., Zhang, J.Y., Zheng, J.M., et al., 2014. Robust surface reconstruction via dictionary learning. ACM Trans. Graph., 33(6). http://dx.doi.org/10.1145/2661229.2661263

[16] Xu, L., Lu, C.W., Xu, Y., et al., 2011. Image smoothing via L0 gradient minimization. ACM Trans. Graph., 30(6):174. http://dx.doi.org/10.1145/2024156.2024208

[17] Yang, Y.Y.,Wernick, M.N.,Brankov, J.G., 2003. Afast approach for accurate content-adaptive mesh generation. IEEE Trans. Image Process., 12(8):866–881. http://dx.doi.org/10.1109/TIP.2003.812757