×

Image segmentation with partial convexity shape prior using discrete conformality structures. (English) Zbl 1497.68542

Summary: Image segmentation aims to partition an image into meaningful regions and extract important objects therein. In real applications, the given images may contain multiple overlapping objects with noisy background, creating great challenges to the segmentation task. In these cases, prior information of the target object is essential for an accurate and meaningful segmentation result. In this paper, we present a new convexity shape prior segmentation framework to guarantee the segmented region to be fully or partially convex according to the user’s preference. The basic idea is to incorporate a registration-based segmentation model with a specially designed convexity constraint. The convexity constraint is based on the discrete conformality structures of the image mesh. To solve the segmentation model, we propose an iterative scheme, which smoothly deforms a template object to trace the boundary of the target object. A projection is carried out to enforce the convexity constraint. The target object is then captured by a (fully or partially) convex region. Convexity is the only prior information needed for a (fully) convex shape, whereas the location of partial convexity is needed for a partially convex shape. Experiments have been carried out on both synthetic and real images and the results demonstrate the effectiveness of our proposed framework.

MSC:

68U10 Computing methodologies for image processing
53A31 Differential geometry of submanifolds of Möbius space
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Bae, X.-C. Tai, and W. Zhu, Augmented Lagrangian method for an Euler’s elastica based segmentation model that promotes convex contours, Inverse Probl. Imaging, 11 (2017), pp. 1-23. · Zbl 1416.94013
[2] A. L. Bobenko and B. Springborn, Variational principles for circle patterns and Koebe’s theorem, Trans. Amer. Math. Soc., 356 (2003), pp. 659-689. · Zbl 1044.52009
[3] R. H. Byrd, M. E. Hribar, and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9 (1999), pp. 877-900. · Zbl 0957.65057
[4] R. H. Byrd, J. C. Gilbert, and J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89 (2000), pp. 149-185. · Zbl 1033.90152
[5] H. L. Chan and L. M. Lui, Detection of \(n\)-dimensional shape deformities using \(n\)-dimensional quasi-conformal maps, Geom. Imaging Comput., 1 (2014), pp. 395-415. · Zbl 1327.65120
[6] H.-L. Chan, S. Yan, L.-M. Lui, and X.-C. Tai, Topology-preserving image segmentation by Beltrami representation of shapes, J. Math. Imaging Vision, 60 (2018), pp. 401-421. · Zbl 1437.94011
[7] T. Chan and W. Zhu, Level set based shape prior segmentation, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), Vol. 2, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 1164-1170.
[8] T. F. Chan and L. A. Vese, Active contours without edges, IEEE Trans. Image Process., 10 (2001), pp. 266-277. · Zbl 1039.68779
[9] P. T. Choi, K. C. Lam, and L. M. Lui, FLASH: Fast landmark aligned spherical harmonic parameterization for genus-0 closed brain surfaces, SIAM J. Imaging Sci., 8 (2015), pp. 67-94. · Zbl 1316.65028
[10] C. R. Collins and K. Stephenson, A circle packing algorithm, Comput. Geom., 25 (2003), pp. 233-256. · Zbl 1023.52005
[11] D. Cremers, N. Sochen, and C. Schnörr, Towards recognition-based variational segmentation using shape priors and dynamic labeling, in Scale Space Methods in Computer Vision, L. D. Griffin and M. Lillholm, eds., Springer, Berlin, 2003, pp. 388-400. · Zbl 1067.68727
[12] D. Cremers, F. Tischhäuser, J. Weickert, and C. Schnörr, Diffusion snakes: Introducing statistical shape knowledge into the Mumford-Shah functional, Int. J. Comput. Vis., 50 (2002), pp. 295-313. · Zbl 1012.68785
[13] M. Desbrun, M. Meyer, and P. Alliez, Intrinsic parameterizations of surface meshes, Comput. Graph. Forum, 21 (2002), pp. 209-218.
[14] F. P. Gardiner and N. Lakic, Quasiconformal Teichmuller Theory, American Mathematical Society, Providence, RI, 2000. · Zbl 0949.30002
[15] L. Gorelick, O. Veksler, Y. Boykov, and C. Nieuwenhuis, Convexity shape prior for binary segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 39 (2017), pp. 258-271.
[16] X. Han, C. X. Xu, and J. L. Prince, A topology preserving level set method for geometric deformable models, IEEE Trans. Pattern Anal. Mach. Intell., 25 (2003), pp. 755-768.
[17] A. N. Hirani, Discrete Exterior Calculus, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2003.
[18] M. Ibrahim, K. Chen, and L. Rada, An improved model for joint segmentation and registration based on linear curvature smoother, J. Algorithms Comput. Technol., 10 (2016), pp. 314-324.
[19] M. Jin, X. Gu, Y. He, and Y. Wang, Computer Vision, Springer, Cham, Switzerland, 2018, pp. 103-133.
[20] M. Kass, A. Witkin, and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vis. 1 (1988), pp. 321-331. · Zbl 0646.68105
[21] L. Kharevych, B. Springborn, and P. Schoder, Discrete conformal mappings via circle patterns, ACM Trans. Graph., 25 (2006), pp. 412-438.
[22] K. C. Lam and L. M. Lui, Landmark- and intensity-based registration with large deformations via quasi-conformal maps, SIAM J. Imaging Sci., 7 (2014), pp. 2364-2392. · Zbl 1309.65019
[23] K. C. Lam, T. C. Ng, and L. M. Lui, Multiscale representation of deformations via Beltrami coefficients, Multiscale Model. Simul., 15 (2017), pp. 864-891. · Zbl 1365.65066
[24] C. Le Guyader and L. A. Vese, Self-repelling snakes for topology-preserving segmentation models, IEEE Trans. Image Process., 17 (2008), pp. 767-779.
[25] C. Le Guyader and L. A. Vese, A combined segmentation and registration framework with a nonlinear elasticity smoother, Comput. Vis. Image Underst., 115 (2011), pp. 1689-1709.
[26] Y.-T. Lee, K.-C. Lam, and L.-M. Lui, Large deformation registration via n-dimensional quasi-conformal maps, J. Sci. Comput., 67 (2016), pp. 926-954. · Zbl 1342.30015
[27] G. Leibon, Characterizing the Delaunay decompositions of compact hyperbolic surfaces, Geom. Topol., 6 (2002), pp. 361-391. · Zbl 1028.52014
[28] M. E. Leventon, W. E. L. Grimson, and O. Faugeras, Statistical shape influence in geodesic active contours, in Proceedings IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2000, Vol. 1, IEEE Computer Society, Los Alamitos, CA, 2000, pp. 316-323.
[29] B. Lévy, S. Petitjean, N. Ray, and J. Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Trans. Graph., 21 (2002), pp. 362-371.
[30] L. M. Lui, K. C. Lam, T. W. Wong, and X. Gu, Texture map and video compression using Beltrami representation, SIAM J. Imaging Sci., 6 (2013), pp. 1880-1902. · Zbl 1281.65036
[31] L. M. Lui and C. Wen, Geometric registration of high-genus surfaces, SIAM J. Imaging Sci., 7 (2014), pp. 337-365. · Zbl 1296.65029
[32] L. M. Lui, T. W. Wong, P. Thompson, T. Chan, X. Gu, and S.-T. Yau, Shape-based diffeomorphic registration on hippocampal surfaces using Beltrami holomorphic flow, in Medical Image Computing and Computer-Assisted Intervention – MICCAI 2010, T. Jiang, N. Navab, J. P. W. Pluim, and M. A. Viergever, eds., Springer, Berlin, 2010, pp. 323-330.
[33] S. Luo, X.-C. Tai, L. Huo, Y. Wang, and R. Glowinski, Convex shape prior for multi-object segmentation using a single level set function, in IEEE Computer Society, Los Alamitos, CA, IEEE International Conference on Computer Vision (ICCV), IEEE Computer Society, Los Alamitos, CA, 2017, pp. 613-621.
[34] MathWorks, Constrained Nonlinear Optimization Algorithms, https://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-algorithms.html.
[35] Matlab Optimization Toolbox Release 2016a, The MathWorks, Natick, MA, 2016.
[36] C. Mercat, Discrete Riemann surfaces and the Ising model, Comm. Math. Phys., 218 (2001), pp. 177-216. · Zbl 1043.82005
[37] I. Rivin, Euclidean structures on simplicial surfaces and hyperbolic volume, Ann. of Math. (2), 139 (1994), pp. 553-580. · Zbl 0823.52009
[38] L. A. Royer, D. L. Richmond, C. Rother, B. Andres, and D. Kainmueller, Convexity shape constraints for image segmentation, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, Piscataway, NJ, 2016, pp. 402-410.
[39] M. Sdika, Combining atlas based segmentation and intensity classification with nearest neighbor transform and accuracy weighted vote, Med. Image Anal., 14 (2010), pp. 219-226.
[40] J. R. Shewchuk, Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator, in Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, eds., Springer, Berlin, 1996, pp. 203-222.
[41] B. Springborn, P. Schröder, and U. Pinkall, Conformal equivalence of triangle meshes, ACM Trans. Graph., 27 (2008), 77.
[42] E. Strekalovskiy and D. Cremers, Generalized ordering constraints for multilabel optimization, in Proceedings of the IEEE International Conference on Computer Vision (ICCV), IEEE, Piscataway, NJ, pp. 2619-2626, 2011.
[43] G. Sundaramoorthi and A. Yezzi, Global regularizing flows with topology preservation for active contours and polygons, IEEE Trans. Image Process., 16 (2007), pp. 803-812.
[44] W. Thurston, Geometry and Topology of Three-Manifolds, Princeton University, Princeton, NJ, 1980, http://library.msri.org/books/gt3m/, 1980.
[45] W. Thurston, The finite Riemann mapping theorem. Invited talk, International Symposium at Purdue University on the Occasion of the Proof of the Bieberbach Conjecture, Purdue University, West Lafayette, IN, 1985.
[46] F. A. Valentine, Convex Sets, McGraw-Hill, New York, 1964. · Zbl 0129.37203
[47] R. Waltz, J. Morales, J. Nocedal, and D. Orban, An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math. Program., 107 (2006), pp. 391-408. · Zbl 1134.90053
[48] S. Warfield, A. Robatino, J. Dengler, F. Jolesz, and R. Kikinis, Nonlinear registration and template-driven segmentation, in Brain Warping, W. Toga, ed., Academic Press, San Diego, CA, 1999, pp. 67-84.
[49] S. Yan, X. Tai, J. Liu, and H. Huang, Convexity shape prior for level set based image segmentation method, IEEE Trans. Image Process., 29 (2020), pp. 7141-7152. · Zbl 07586389
[50] A. Yezzi, L. Zölleiy, and T. Kapur, A variational framework for joint segmentation and registration, in Proceedings IEEE Workshop on Mathematical Methods in Biomedical Image Analysis (MMBIA 2001), IEEE Computer Society, Los Alamitos, CA, 2001, pp. 44-51.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.