Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Shape Partitioning via \({L}_{p}\) Compressed Modes

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

The eigenfunctions of the Laplace–Beltrami operator (manifold harmonics) define a function basis that can be used in spectral analysis on manifolds. In Ozoli et al. (Proc Nat Acad Sci 110(46):18368–18373, 2013) the authors recast the problem as an orthogonality constrained optimization problem and pioneer the use of an \(L_1\) penalty term to obtain sparse (localized) solutions. In this context, the notion corresponding to sparsity is compact support which entails spatially localized solutions. We propose to enforce such a compact support structure by a variational optimization formulation with an \(L_p\) penalization term, with \(0<p<1\). The challenging solution of the orthogonality constrained non-convex minimization problem is obtained by applying splitting strategies and an ADMM-based iterative algorithm. The effectiveness of the novel compact support basis is demonstrated in the solution of the 2-manifold decomposition problem which plays an important role in shape geometry processing where the boundary of a 3D object is well represented by a polygonal mesh. We propose an algorithm for mesh segmentation and patch-based partitioning (where a genus-0 surface patching is required). Experiments on shape partitioning are conducted to validate the performance of the proposed compact support basis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

References

  1. Agathos, A., Pratikakis, I., Perantonis, S., Sapidis, N., Azariadis, P.: 3D mesh segmentation methodologies for CAD applications. Comput. Aided Des. Appl. 4(6), 827–841 (2007)

    Article  Google Scholar 

  2. Attene, M., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A.: Mesh segmentation—a comparative study. In: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06). IEEE Computer Society, Washington (2006)

  3. Barekat, F.: On the consistency of compressed modes for variational problems associated with the Schrödinger operator. SIAM J. Math. Anal. 46(5), 3568–3577 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  4. Barekat, F., Caflish, R., Osher, S.: On the support of compressed modes. CAM reports (2014)

  5. Benhabiles, H., Lavoué, G., Vandeborre, J.-P., Daoudi, M.: Learning boundary edges for 3D-mesh segmentation. Comput. Graph. Forum 30(8), 2170–2182 (2011)

    Article  Google Scholar 

  6. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)

    Article  MATH  Google Scholar 

  7. Chahhou, M., Moumoun, L., El Far, M., Gadi, T.: Segmentation of 3D meshes using p-spectral clustering. IEEE Trans. Pattern Anal. Mach. Intell. 36(8), 1687–1693 (2014)

    Article  Google Scholar 

  8. Chen, X., Golovinskiy, A., Funkhouser, T.: A benchmark for 3D mesh segmentation. ACM Trans. Graph 28(3), 73:1–73:12 (2009)

    Article  Google Scholar 

  9. Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Dodgson, N.A., Floater, M.S., Sabin, M.A. (eds.) Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pp. 157–186. Springer, Berlin (2005)

    Chapter  Google Scholar 

  10. Gao, Y., Menon, P.G., Zhang, Y.: 3D shape comparison of cardiac geometries using a Laplace spectral-shape-matching approach. CMBBE Imaging Vis. 4, 86–97 (2016)

    Google Scholar 

  11. Gower, J.C., Dijksterhuis, G.B.: Procrustes Problems. Oxford University Press, Oxford (2004)

    Book  MATH  Google Scholar 

  12. Huska, M., Morigi, S.: Sparsity-inducing variational shape partitioning. Electron. Trans. Numer. Anal. 46, 36–54 (2017)

    MathSciNet  MATH  Google Scholar 

  13. Kalogerakis, E., Hertzmann, A., Singh, K.: Learning 3D mesh segmentation and labeling. ACM Trans. Graph. 29(4), 102:1–102:12 (2010)

    Article  Google Scholar 

  14. Lai, R., Osher, S.: A splitting method for orthogonality constrained problems. J. Sci. Comput. 58(2), 431–449 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lanza, A., Morigi, S., Sgallari, F.: Constrained TVp-L2 model for image restoration. J. Sci. Comput. (JOMP) 68(1), 64–91 (2016)

    Article  MATH  Google Scholar 

  16. Lévy, B., Zhang, H.R.: Spectral mesh processing. In: ACM SIGGRAPH 2010 courses (SIGGRAPH ’10). ACM, New York (2010)

  17. Lin, H., Chen, W., Bao, H.: Adaptive patch-based mesh fitting for reverse engineering. Comput. Aided Des. 39(12), 1134–1142 (2007)

    Article  Google Scholar 

  18. Liu, R., Zhang, H.: Segmentation of 3D meshes through spectral clustering. In: Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (Oct 2004), PG 2004, pp. 298–305 (2004)

  19. Mejia, D., Ruiz-Salguero, O., Cadavid, C.A.: Spectral-based mesh segmentation. Int. J. Interact. Des. Manuf. (IJIDeM):1955–2505 11(3), 503–514 (2017)

  20. Neumann, T., Varanasi, K., Theobalt, C., Magnor, M., Wacker, M.: Compressed manifold modes for mesh processing, computer graphics forum. In: Proceedings of the Symposium on Geometry Processing (SGP), vol. 33, issue 5. Eurographics Association, pp. 35–44 (2014)

  21. Ozoli, V., Lai, R., Caflisch, R., Osher, S.: Compressed modes for variational problems in mathematics and physics. Proc. Nat. Acad. Sci. 110(46), 18368–18373 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Patanè, G., Spagnuolo, M., Falcidieno, B.: Families of cut-graphs for bordered meshes with arbitrary genus. Graph. Models 69(2), 119–138 (2007)

    Article  Google Scholar 

  23. Patanè, G., Spagnuolo, M., Falcidieno, B.: Para-graph: graph-based parameterization of triangle meshes with arbitrary genus. Comput. Graph. Forum 23(4), 783–797 (2004)

    Article  Google Scholar 

  24. Pinkall, U., Polthier, K.: Computing discrete minimal surfaces and their conjugates. Exp. Math. 2, 15–36 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  25. Reuter, M., Wolter, F.-E., Peinecke, N.: Laplace-spectra as fingerprints for shape matching. In: Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling (SPM ’05), pp. 101–106. ACM, New York (2005)

  26. Schonemann, P.H.: On the formal differentiation of traces and determinants. Multivar. Behav. Res. 20(2), 113–139 (1985)

    Article  Google Scholar 

  27. Shamir, A.: A survey on mesh segmentation techniques. Comput. Graph. Forum 27(6), 1539–1556 (2008)

    Article  MATH  Google Scholar 

  28. Song, R., Liu, Y., Martin, R.R., Rosin, P.L.: Mesh saliency via spectral processing. ACM Trans. Graph. 33(1), 6:1–6:17 (2014)

    Article  MATH  Google Scholar 

  29. Steiner, D., Fischer, A.: Cutting 3D freeform objects with genus-n into single boundary surfaces using topological graphs. In: Symposium on Solid Modeling and Applications, pp. 336–343 (2002)

  30. Theologou, P., Pratikakis, I., Theoharis, T.: A comprehensive overview of methodologies and performance evaluation frameworks in 3D mesh segmentation. Comput. Vis. Image Underst. 135, 49–82 (2015)

    Article  Google Scholar 

  31. Theologou, P., Pratikakis, I., Theoharis, T.: Unsupervised spectral mesh segmentation driven by heterogeneous graphs. IEEE Trans. Pattern Anal. Mach. Intell. 39(2), 397–410 (2017)

    Article  Google Scholar 

  32. Vallet, B., Lévy, B.: Spectral geometry processing with manifold harmonics. Comput. Graph. Forum 27(2), 251–260 (2008)

    Article  Google Scholar 

  33. Varady, T.: Automatic procedures to create CAD models from measured data. Comput. Aided Des. Appl. 5(5), 577–588 (2013)

    Article  Google Scholar 

  34. Wang, H., Lu, T., Au, O.K.-C., Tai, C.-L.: Spectral 3D mesh segmentation with a novel single segmentation field. Graph. Models 76(5), 440–456 (2014)

    Article  Google Scholar 

  35. Yan, D.-M., Wang, W., Liuc, Y., Yang, Z.: Variational mesh segmentation via quadric surface fitting. Comput. Aided Des. 44(11), 1072–1082 (2012)

    Article  Google Scholar 

  36. Yin, K., Osher, S.: On the completeness of the compressed modes in the eigenspace. UCLA CAM report, pp. 13–62 (2013)

  37. Zhang, J., Zheng, J., Wu, C., Cai, J.: Variational mesh decomposition. ACM Trans. Graph. 31(3), 21:1–21:14 (2012)

    Article  Google Scholar 

  38. Zuo, W., Meng, D., Zhang, L., Feng, X., Zhang, D.: A generalized iterated shrinkage algorithm for non-convex sparse coding. International Conference of Computer Vision (ICCV), pp. 217–224 (2013)

Download references

Acknowledgements

We would like to thank the referees for comments that lead to improvements in the presentation. Research was supported in part by the National Group for Scientific Computation (GNCS-INDAM), Research Projects 2018.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Bologna, Bologna, Italy

    Martin Huska, Damiana Lazzaro & Serena Morigi

Authors
  1. Martin Huska
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Damiana Lazzaro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Serena Morigi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Serena Morigi.

Appendix

Appendix

Proof of Theorem 1.

Proof

The proof is decomposed in four steps.

Step 1 We first derived the Euler–Lagrange equations for (3.2). For any function u, let s(u) denote an element of subdifferential of \(\left| u \right| ^p\), that is:

$$\begin{aligned} s(u)=\hbox {sign}(u)\cdot p \cdot \left| u \right| ^{p-1}. \; \end{aligned}$$
(9.1)

The solutions of (3.2) are weak solutions of the following system of nonlinear boundary value problem:

$$\begin{aligned}&\frac{1}{\mu } s(\psi _i)-2\lambda _{ii} \psi _i-\varDelta \psi _i\nonumber \\&\quad - \sum _{j \ne i} \lambda _{ij}\psi _j=0, \quad i=1,..,N \; \text{ on } \quad \varOmega \end{aligned}$$
(9.2)

where \(\lambda _{ij}\), with \(\lambda _{ij}=\lambda _{ji}\) are Lagrange multipliers corresponding to orthonormality constraints:

$$\begin{aligned} \int _\varOmega {\psi _i^2 \mathrm{d}x}= & {} 1 \quad \text{ and } \quad \int _\varOmega {\psi _i \psi _j \mathrm{d}x}=0,\nonumber \\ \text{ for }~i,j= & {} 1,\ldots ,N, \; j\ne i. \end{aligned}$$
(9.3)

Step 2 Upper bounds for \(\lambda _{ii}\), \(\Vert \psi _i \Vert _p^p\) and \(\Vert \nabla \psi _i \Vert _2\)

For each i multiply both sides of Eq. (9.2) by \(\psi _i(x)\) and integrate over domain \(\varOmega \):

$$\begin{aligned}&\int _\varOmega {\frac{1}{\mu } s(\psi _i) \psi _i \mathrm{d}x}-2\lambda _{ii} \int _\varOmega {\psi _i\psi _i \mathrm{d}x}\nonumber \\&\quad - \int _\varOmega {\varDelta \psi _i \psi _i \mathrm{d}x} - \sum _{j \ne i} \lambda _{ij}\int _\varOmega {\psi _i \psi _j \mathrm{d}x}=0 . \end{aligned}$$
(9.4)

By using orthonormality conditions (9.3), we can rewrite the above equation as:

$$\begin{aligned} \int _\varOmega {\frac{1}{\mu } s(\psi _i) \psi _i \mathrm{d}x}-2\lambda _{ii} - \int _\varOmega {\varDelta \psi _i \psi _i \mathrm{d}x}=0 \end{aligned}$$
(9.5)

that, using integration by parts and zero boundary conditions on \(\varOmega \), implies that

$$\begin{aligned} \int _\varOmega {\frac{1}{\mu } s(\psi _i)\psi _i \mathrm{d}x}-2\lambda _{ii} + \int _\varOmega {\left| \nabla \psi _i \right| ^2 \mathrm{d}x}=0 \end{aligned}$$
(9.6)

and then

$$\begin{aligned} \lambda _{ii}= \frac{1}{2\mu } \int _\varOmega {s(\psi _i)\psi _i \mathrm{d}x}+ \frac{1}{2} \int _\varOmega {\left| \nabla \psi _i \right| ^2 \mathrm{d}x}. \end{aligned}$$
(9.7)

By using definition (9.1), relation (9.7) can be reformulated as:

$$\begin{aligned} \lambda _{ii}= \frac{1}{2\mu } \int _\varOmega {p \left| \psi _i \right| ^p \mathrm{d}x}+ \frac{1}{2}\int _\varOmega {\left| \nabla \psi _i \right| ^2 \mathrm{d}x} \end{aligned}$$
(9.8)

From Proposition 1, we know that the first compressed mode \(\psi \) has support whose volume satisfy (3.3). It follows that for \(\mu \) sufficiently small and \(0<p < 1\), the N disjoint copies (i.e., translates) of \(\psi \) can be placed in \(\varOmega \), and these N functions are a solution for problem (3.2). Therefore, in view of Proposition 1, there exist \(\mu _0\) (depending on values of p, N, and d) such that for \(\mu < \mu _0\):

$$\begin{aligned}&\sum _{i=1}^N \int _\varOmega { \frac{1}{\mu }\left| {\psi _i}\right| ^p \mathrm{d}x}+\sum _{i=1}^N \frac{1}{2}\int _\varOmega {\left| \nabla {\psi _i} \right| ^2 \mathrm{d}x}\nonumber \\&\quad \le m(\varOmega )^{\frac{1}{p}-1} C_1 N \mu ^{-\frac{4}{4+d}}. \end{aligned}$$
(9.9)

Because each of the summands in the left-hand side of above inequality is positive, there exist constant \(C_2\) (depending on d and N) such that for \(\mu < \mu _0\),

$$\begin{aligned} \int _\varOmega { \frac{1}{\mu }\left| {\psi _i}\right| ^p \mathrm{d}x}\le & {} m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}} \quad \text{ and }\nonumber \\ \int _\varOmega {\left| \nabla {\psi _i} \right| ^2 \mathrm{d}x}\le & {} m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}}. \end{aligned}$$
(9.10)

Moreover, replacing the above inequalities into (9.8), it follows that there exist a constant \(C_3\) (depending on d, N and p), such that for \(\mu <\mu _0\)

$$\begin{aligned} \left| \lambda _{ii}\right|< & {} p \frac{C_2}{2} \mu ^{-\frac{4}{4+d}}m(\varOmega )^{\frac{1}{p}-1}+ p \frac{C_2}{2} \mu ^{-\frac{4}{4+d}} m(\varOmega )^{\frac{1}{p}-1}\nonumber \\< & {} C_3 \mu ^{-\frac{4}{4+d}} m(\varOmega )^{\frac{1}{p}-1}. \end{aligned}$$
(9.11)

Step 3 Upper bounds for \(\lambda _{ij}'s\).

Fix i. For \(k \ne i\), multiply both sides of Eq. (9.2) by \(\psi _k(x)\) and integrate over \(\varOmega \):

(9.12)

which, using orthonormality condition (9.3) and integration by parts, implies that:

$$\begin{aligned} \frac{1}{\mu } \int _\varOmega {s(\psi _i)\psi _k \mathrm{d}x}+ \int _\varOmega {(\nabla \psi _i) (\nabla \psi _k) \mathrm{d}x} -\lambda _{ik}=0. \end{aligned}$$
(9.13)

Therefore

$$\begin{aligned} \lambda _{ik}=\frac{1}{\mu } \int _\varOmega {s(\psi _i)\psi _k \mathrm{d}x}+ \int _\varOmega {(\nabla \psi _i) (\nabla \psi _k) \mathrm{d}x}. \end{aligned}$$
(9.14)

By using relation (9.1), we have

$$\begin{aligned} \left| \frac{1}{\mu } \int _\varOmega {s(\psi _i) \psi _k \mathrm{d}x} \right|\le & {} \frac{1}{\mu } \int _\varOmega {\left| s(\psi _i)\psi _k \right| \mathrm{d}x}\nonumber \\= & {} \frac{p}{\mu } \int _\varOmega {\left| \psi _i \right| ^{p-1}\left| \psi _k\right| \mathrm{d}x}\nonumber \\= & {} \frac{p}{\mu } \int _\varOmega {\left| \psi _i \right| ^{p} \frac{\left| \psi _k\right| }{\left| \psi _i\right| } \mathrm{d}x}. \end{aligned}$$
(9.15)

Since \(\left| \psi _i\right| ^{p}\) does not change sign on \(\varOmega \), by the First Mean Value Theorem for Integrals, there exists \(\xi \in \varOmega \), with \(\psi _i(\xi ) \ne 0\), such that, if we set \(M=\frac{\left| \psi _k(\xi )\right| }{\left| \psi _i(\xi )\right| }\), it follows that

$$\begin{aligned} \frac{p}{\mu } \int _\varOmega { \left| \psi _i \right| ^{p} \frac{\left| \psi _k\right| }{\left| \psi _i\right| } \mathrm{d}x}=M \frac{p}{\mu } \int _\varOmega { \left| \psi _i \right| ^{p} \mathrm{d}x}. \end{aligned}$$

Making use of (9.10), we conclude that

$$\begin{aligned} \left| \frac{1}{\mu } \int _\varOmega {s(\psi _i)\psi _k \mathrm{d}x} \right| \le p M m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}}. \end{aligned}$$
(9.16)

Finally, using Cauchy–Schwarz and equation (9.10),

$$\begin{aligned}&\left| \int _\varOmega {(\nabla \psi _i) (\nabla \psi _k) \mathrm{d}x} \right| \le \left( \int _\varOmega {\left| \nabla \psi _i \right| ^2 \mathrm{d}x} \right) ^{\frac{1}{2}} \left( \int _\varOmega {\left| \nabla \psi _k \right| ^2 \mathrm{d}x} \right) ^{\frac{1}{2}} \nonumber \\&\quad <(m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}})^{\frac{1}{2}} (m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}})^{\frac{1}{2}}\nonumber \\&\quad = m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}}. \end{aligned}$$
(9.17)

Substituting the two upper bounds given in (9.16) and (9.17) into Eq. (9.14), we have for \(\mu < \mu _0\)

$$\begin{aligned} \left| \lambda _{ik} \right|< & {} p M m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}} +\,\, m(\varOmega )^{\frac{1}{\tilde{p}}-1} C_2\mu ^{-\frac{4}{4+d}}\nonumber \\= & {} m(\varOmega )^{\frac{1}{p}-1} C_2 \mu ^{-\frac{4}{4+d}}(p M+1)\nonumber \\< & {} C_4 m(\varOmega )^{\frac{1}{\tilde{p}}-1} \mu ^{-\frac{4}{4+d}} \end{aligned}$$
(9.18)

where \(C_4\) depends on N, M, p and \(\mu \).

Step 4 Bounding the volume of the support \(\psi _i\)’s

For each i multiply both sides of Eq. (9.2) by \(\frac{1}{p} \hbox {sign}(\psi _i) \left| \psi _i \right| ^{1-p}\) and integrate over domain \(\varOmega \):

$$\begin{aligned}&\frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right| -\frac{2}{p}\lambda _{ii} \int _\varOmega {\left| \psi _i \right| ^{2-p}\mathrm{d}x}\nonumber \\&\quad - \frac{1}{p}\int _\varOmega {\varDelta \psi _i \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}\nonumber \\&\quad -\frac{1}{p}\sum _{j\ne i} \lambda _{ij} \int _\varOmega {\psi _j \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}=0, \end{aligned}$$
(9.19)

namely,

$$\begin{aligned}&\frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right| \nonumber \\&\quad =\left| \frac{2}{p}\lambda _{ii} \int _\varOmega {\left| \psi _i \right| ^{2-p}\mathrm{d}x}+ \frac{1}{p}\int _\varOmega {\varDelta \psi _i \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}\right. \nonumber \\&\left. \qquad +\,\, \frac{1}{p}\sum _{j\ne i} \lambda _{ij} \int _\varOmega {\psi _j \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}\right| \nonumber \\&\quad \le \left| \frac{2}{p}\lambda _{ii} \int _\varOmega {\left| \psi _i \right| ^{2-p}\mathrm{d}x}+ \frac{1}{p}\int _\varOmega {\varDelta \psi _i \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}\right| \nonumber \\&\qquad +\,\, \left| \frac{1}{p}\sum _{j\ne i} \lambda _{ij} \int _\varOmega {\psi _j \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}\right| . \end{aligned}$$
(9.20)

Define

$$\begin{aligned} \varOmega ^+=\left\{ x \in \varOmega : \psi _i(x)>0\right\} \end{aligned}$$

and

$$\begin{aligned} \varOmega ^-=\left\{ x \in \varOmega : \psi _i(x)<0\right\} . \end{aligned}$$

According to Green’s formula

$$\begin{aligned} \int _{\varOmega ^+}{\varDelta \psi _i \mathrm{d}x}=\int _{\partial \varOmega ^+}{\frac{\partial \psi _i}{\partial \nu } \mathrm{d}S} \le 0, \end{aligned}$$

where \(\nu \) is outward pointing unit normal vector along \(\partial \varOmega ^+\). Since \(\psi \) is positive in \(\varOmega ^+\) and becomes zero on \(\partial \varOmega ^+\), the right-hand side of the above expression is not positive.

With a similar argument, we have that

$$\begin{aligned} \int _{\varOmega ^-}{\varDelta \psi _i \mathrm{d}x}=\int _{\partial \varOmega ^-}{\frac{\partial \psi _i}{\partial \nu } \mathrm{d}S} \ge 0. \end{aligned}$$

Hence, since \(\left| \psi _i\right| ^{1-p} \ge 0\) \(\forall i\), it follows that:

$$\begin{aligned} \int _\varOmega {\varDelta \psi _i \hbox {sign}(\psi _i) \left| \psi _i\right| ^{1-p}\mathrm{d}x}= & {} \int _{\varOmega ^+}{\varDelta \psi _i \left| \psi _i\right| ^{1-p}\mathrm{d}x}\nonumber \\&-\int _{\varOmega ^-}{\varDelta \psi _i \left| \psi _i\right| ^{1-p}\mathrm{d}x}\le 0.\nonumber \\ \end{aligned}$$
(9.21)

Using inequality (9.21), (9.20) can be rewritten as:

$$\begin{aligned}&\frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right| \nonumber \\&\quad \le \left| \frac{2}{p}\lambda _{ii} \int _\varOmega {\left| \psi _i \right| ^{2-p}\mathrm{d}x}\right| + \left| \frac{1}{p}\sum _{j\ne i} \lambda _{ij} \int _\varOmega {\left| \psi _j \right| \left| \psi _i\right| ^{1-p}\mathrm{d}x}\right| \nonumber \\&\quad \le \frac{2}{p}|\lambda _{ii}| \int _\varOmega {\left| \psi _i \right| ^{2-p}\mathrm{d}x}+ \frac{1}{p}\sum _{j\ne i} |\lambda _{ij}| \int _\varOmega {\left| \psi _j \right| \left| \psi _i\right| ^{1-p}\mathrm{d}x} \nonumber \\&\quad \le \frac{2}{p} |\lambda _{ii}| \int _\varOmega {\left| \psi _i \right| \left| \psi _i \right| ^{1-p}\mathrm{d}x}+\frac{1}{p}\sum _{j\ne i} |\lambda _{ij}| \int _\varOmega {\left| \psi _j \right| \left| \psi _i\right| ^{1-p}\mathrm{d}x}.\nonumber \\ \end{aligned}$$
(9.22)

We set \(\tilde{p}=1-p\), \(0<\tilde{p}<1\) , for \(0<p<1\).

$$\begin{aligned} \frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right|\le & {} \frac{2}{p} |\lambda _{ii}| \int _\varOmega {\left| \psi _i \right| \left| \psi _i \right| ^{\tilde{p}}\mathrm{d}x}\nonumber \\&+ \frac{1}{p}\sum _{j\ne i} |\lambda _{ij}| \int _\varOmega {\left| \psi _j \right| \left| \psi _i\right| ^{\tilde{p}}\mathrm{d}x}. \end{aligned}$$
(9.23)

Since \(\left| \psi _i\right| ^{\tilde{p}}\) does not change sign on \(\varOmega \), by the first mean value theorem for integrals, there exist \(\xi , \eta \in \varOmega \) such that, if we set \(\bar{M}=\left| \psi _i(\xi )\right| \) and \(\tilde{M}=\left| \psi _j(\eta )\right| \), relation (9.23) can be rewritten as:

$$\begin{aligned} \frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right|\le & {} \frac{2}{p} \bar{M} |\lambda _{ii}| \int _\varOmega { \left| \psi _i \right| ^{\tilde{p}}\mathrm{d}x}\nonumber \\&+\,\, \frac{1}{p}\sum _{j\ne i} \tilde{M} |\lambda _{ij}| \int _\varOmega {\left| \psi _i\right| ^{\tilde{p}}\mathrm{d}x}. \end{aligned}$$
(9.24)

By using (9.10), (9.11),(9.18), then (9.24) becomes:

$$\begin{aligned}&\frac{1}{\mu } \left| \hbox {supp}(\psi _i) \right| \nonumber \\&\quad \le \frac{2}{p} \bar{M} C_3 m(\varOmega )^{\frac{1}{p}-1} \mu ^{-\frac{4}{4+d}} m(\varOmega )^{\frac{1}{1-p}-1}C_2 \mu ^{-\frac{4}{4+d}+1} \nonumber \\&\qquad +\,\, \frac{1}{p} (N-1) \tilde{M} C_4 m(\varOmega )^{\frac{1}{p}-1}\mu ^{-\frac{4}{4+d}} m(\varOmega )^{\frac{1}{1-p}-1}C_2 \mu ^{-\frac{4}{4+d}+1}\nonumber \\&\quad \le C_5 \mu ^{-\frac{8}{4+d}+1} m(\varOmega ) ^{\frac{1}{p(1-p)}-2} \end{aligned}$$
(9.25)

where \(C_5\) depends on N and p. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huska, M., Lazzaro, D. & Morigi, S. Shape Partitioning via \({L}_{p}\) Compressed Modes. J Math Imaging Vis 60, 1111–1131 (2018). https://doi.org/10.1007/s10851-018-0799-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-018-0799-8

Keywords

Search

Navigation