Convex cardinal shape composition. (English) Zbl 1352.68260
Summary: We propose a new shape-based modeling technique for applications in imaging problems. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right dictionary elements and geometrically composing them through basic set operations to characterize desired regions in an image. This is a combinatorial problem solving which requires an exhaustive search among a large number of possibilities. We propose a convex relaxation to the problem to make it computationally tractable. We take some major steps towards the analysis of the proposed convex program and characterizing its minimizers. Applications vary from shape-based characterization, object tracking, optical character recognition, and shape recovery in occlusion to other disciplines such as the geometric packing problem.
MSC:
| 68T45 | Machine vision and scene understanding |
| 49Q20 | Variational problems in a geometric measure-theoretic setting |
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
| 68T10 | Pattern recognition, speech recognition |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
| 90C25 | Convex programming |
Keywords:
image segmentation; Chan-Vese model; Mumford-Shah functional; shape-based modeling; compressive sensing; sparse recovery; optical character recognition; geometric packingSoftware:
CVXReferences:
| [1] | A. Aghasi, M. Kilmer, and E.L. Miller, {\it Parametric level set methods for inverse problems}, SIAM J. Imaging Sci., 4 (2011), pp. 618-650. · Zbl 1219.65053 |
| [2] | A. Aghasi, I. Mendoza-Sanchez, E.L. Miller, C.A. Ramsburg, and L.M. Abriola, {\it A geometric approach to joint inversion with applications to contaminant source zone characterization}, Inverse Problems, 29 (2013), 115014. · Zbl 1284.86006 |
| [3] | A. Aghasi and J. Romberg, {\it Sparse shape reconstruction}, SIAM J. Imaging Sci., 6 (2013), pp. 2075-2108. · Zbl 1281.65026 |
| [4] | Y.I. Alber, A.N. Iusem, and M.V. Solodov, {\it On the projected subgradient method for nonsmooth convex optimization in a Hilbert space}, Math. Programming, 81 (1998), pp. 23-35. · Zbl 0919.90122 |
| [5] | G. Aubert and P. Kornprobst, {\it Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations}, Appl. Math. Sci. 147, Springer, New York, 2006. · Zbl 1110.35001 |
| [6] | S. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049 |
| [7] | E.S. Brown, T.F. Chan, and X. Bresson, {\it Completely convex formulation of the Chan-Vese image segmentation model}, Int. J. Comput. Vis., 98 (2012), pp. 103-121. · Zbl 1254.68271 |
| [8] | E. Candès and B. Recht, {\it Simple bounds for recovering low-complexity models}, Math. Program., 141 (2013), pp. 577-589. · Zbl 1278.15038 |
| [9] | E.J. Candès, J. Romberg, and T. Tao, {\it Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information}, IEEE Trans. Inform. Theory, 52 (2006), pp. 489-509. · Zbl 1231.94017 |
| [10] | A. Chambolle, D. Cremers, and T. Pock, {\it A convex approach to minimal partitions}, SIAM J. Imaging Sci., 5 (2012), pp. 1113-1158. · Zbl 1256.49040 |
| [11] | T.F. Chan, S. Esedoḡlu, and M. Nikolova, {\it Algorithms for finding global minimizers of image segmentation and denoising models}, SIAM J. Appl. Math., 66 (2006), pp. 1632-1648. · Zbl 1117.94002 |
| [12] | T.F. Chan, J. Shen, and L. Vese, {\it Variational PDE models in image processing}, Notices Amer. Math. Soc., 50 (2003), pp. 14-26. · Zbl 1168.94315 |
| [13] | T.F. Chan and L.A. Vese, {\it Active contours without edges}, IEEE Trans. Image Process., 10 (2001), pp. 266-277. · Zbl 1039.68779 |
| [14] | Y. Chen, H.D. Tagare, S. Thiruvenkadam, F. Huang, D. Wilson, K.S. Gopinath, R.W. Briggs, and E.A. Geiser, {\it Using prior shapes in geometric active contours in a variational framework}, Int. J. Comput. Vis., 50 (2002), pp. 315-328. · Zbl 1012.68787 |
| [15] | D. Cremers, M. Rousson, and R. Deriche, {\it A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape}, Int. J. Comput. Vis., 72 (2007), pp. 195-215. |
| [16] | D. Cremers, N. Sochen, and C. Schnörr, {\it A multiphase dynamic labeling model for variational recognition-driven image segmentation}, Int. J. Comput. Vis., 66 (2006), pp. 67-81. · Zbl 1286.94013 |
| [17] | K.A. Dowsland and W.B. Dowsland, {\it Packing problems}, European J. Oper. Res., 56 (1992), pp. 2-14. · Zbl 0825.90355 |
| [18] | S. Foucart and H. Rauhut, {\it A Mathematical Introduction to Compressive Sensing}, Birkhäuser/Springer, New York, 2013. · Zbl 1315.94002 |
| [19] | R.J. Fowler, M.S. Paterson, and S.L. Tanimoto, {\it Optimal packing and covering in the plane are np-complete}, Inform. Process. Lett., 12 (1981), pp. 133-137. · Zbl 0469.68053 |
| [20] | M. Grant and S. Boyd, {\it CVX: Matlab Software for Disciplined Convex Programming, Version 2.1}, http://cvxr.com/cvx (2014). |
| [21] | E. Hopper and B.C.H. Turton, {\it A review of the application of meta-heuristic algorithms to 2d strip packing problems}, Artif. Intell. Rev., 16 (2001), pp. 257-300. · Zbl 1032.68721 |
| [22] | M.E. Leventon, W.E.L. Grimson, and O. Faugeras, {\it Statistical shape influence in geodesic active contours}, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Vol. 1, 2000, pp. 316-323. |
| [23] | O.L. Mangasarian, {\it Uniqueness of solution in linear programming}, Linear Algebra Appl., 25 (1979), pp. 151-162. · Zbl 0399.90053 |
| [24] | D. Mumford and J. Shah, {\it Optimal approximations by piecewise smooth functions and associated variational problems}, Comm. Pure Appl. Math., 42 (1989), pp. 577-685. · Zbl 0691.49036 |
| [25] | S. Osher and R.P. Fedkiw, {\it Level set methods: An overview and some recent results}, J. Comput. Phys., 169 (2001), pp. 463-502. · Zbl 0988.65093 |
| [26] | S. Osher and N. Paragios, {\it Geometric Level Set Methods in Imaging, Vision, and Graphics}, Springer, New York, 2003. · Zbl 1027.68137 |
| [27] | N.R. Pal and S.K. Pal, {\it A review on image segmentation techniques}, Pattern Recogn., 26 (1993), pp. 1277-1294. |
| [28] | Q. Song, J. Bai, M.K. Garvin, M. Sonka, J.M. Buatti, and X. Wu, {\it Optimal multiple surface segmentation with shape and context priors}, IEEE Trans. Med. Imag., 32 (2013), pp. 376-386. |
| [29] | A. Tsai, A. Yezzi, Jr., W. Wells, C. Tempany, D. Tucker, A. Fan, W.E. Grimson, and A.S. Willsky, {\it A shape-based approach to the segmentation of medical imagery using level sets}, IEEE Trans. Med. Imag., 22 (2003), pp. 137-154. |
| [30] | A. Tsai, A. Yezzi, Jr., and A.S. Willsky, {\it Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification}, IEEE Trans. Image Process., 10 (2001), pp. 1169-1186. · Zbl 1062.68595 |
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.
