November  2016, 10(4): 1149-1180. doi: 10.3934/ipi.2016036

A minimal surface criterion for graph partitioning

1. 

Montana State University, Department of Mathematical Sciences, 2-214 Wilson Hall, Box 172400, Bozeman, MT 59717-2400, United States

2. 

University of Utah, Salt Lake City, Department of Mathematics, 155 S. 1400 E, Rm 233, Salt Lake City, UT 84112, United States

Received  July 2015 Revised  May 2016 Published  October 2016

We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. Since the Beltrami energy interpolates between the Total Variation and Dirichlet energies, various results for optimal partitions for these two energies can be recovered. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective. The method is applied to several clustering problems on graphs constructed from manifold discretizations, synthetic data, the MNIST handwritten digit dataset, and image segmentation. The model has a semisupervised extension and provides a natural representative for the clusters as well.
Citation: Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
References:
[1]

K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming,, Cambridge Univ. Press, (1958). Google Scholar

[2]

I. Babuska, The finite element method with penalty,, Mathematics of Computation, 27 (1973), 221. doi: 10.1090/S0025-5718-1973-0351118-5. Google Scholar

[3]

D. A. Bader, H. Meyerhenke, P. Sanders and D. Wagner (eds.), Graph Partitioning and Graph Clustering,, American Mathematical Society, (2013). doi: 10.1090/conm/588. Google Scholar

[4]

D. Barash, Fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 844. doi: 10.1109/TPAMI.2002.1008390. Google Scholar

[5]

B. Bogosel, Shape Optimization and Spectral Problems,, Ph.D. thesis, (2015). Google Scholar

[6]

B. Bogosel, Partitions minimizing an anisotropic length,, 2016., (). Google Scholar

[7]

V. Bonnaillie-Noël and B. Helffer, Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions,, Experimental Mathematics, 20 (2011), 304. doi: 10.1080/10586458.2011.565240. Google Scholar

[8]

V. Bonnaillie-Noël, B. Helffer and G. Vial, Numerical simulations for nodal domains and spectral minimal partitions,, ESAIM: Control, 16 (2010), 221. doi: 10.1051/cocv:2008074. Google Scholar

[9]

V. Bonnaillie-Noël and C. Léna, Spectral minimal partitions for a family of tori,, URL , (). Google Scholar

[10]

B. Bourdin, D. Bucur and É. Oudet, Optimal partitions for eigenvalues,, SIAM Journal on Scientific Computing, 31 (2010), 4100. doi: 10.1137/090747087. Google Scholar

[11]

T. Brox and D. Cremers, On local region models and a statistical interpretation of the piecewise smooth Mumford-Shah functional,, International Journal of Computer Vision, 84 (2009), 184. doi: 10.1007/s11263-008-0153-5. Google Scholar

[12]

D. Bucur, G. Butazzo and A. Henrot, Existence results for some optimal partition problems,, Adv. Math. Sci. Appl., 8 (1998), 571. Google Scholar

[13]

D. Bucur and G. Butazzo, Variational Methods in Shape Optimization Problems, vol. 65 of Progress in Nonlinear Differential Equations and Their Applications,, Birkhäuser Boston, (2005). Google Scholar

[14]

D. Bucur and B. Velichkov, Multiphase shape optimization problems,, SIAM Journal on Control and Optimization, 52 (2014), 3556. doi: 10.1137/130917272. Google Scholar

[15]

L. A. Cafferelli and F. H. Lin, An optimal partition problem for eigenvalues,, Journal of Scientific Computing, 31 (2007), 5. doi: 10.1007/s10915-006-9114-8. Google Scholar

[16]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging,, Journal of Mathematical Imaging and Vision, 40 (2011), 120. doi: 10.1007/s10851-010-0251-1. Google Scholar

[17]

T. F. Chan and L. A. Vese, Active contours without edges,, IEEE Transactions on Image Processing, 10 (2001), 266. doi: 10.1109/83.902291. Google Scholar

[18]

H. Cohn and A. Kumar, Universally optimal distribution of points on spheres,, Journal of the American Mathematical Society, 20 (2007), 99. doi: 10.1090/S0894-0347-06-00546-7. Google Scholar

[19]

O. Cybulski, V. Babin and R. Holyst, Minimization of the Renyi entropy production in the space-partitioning process,, Physical Review E, 71 (2005). doi: 10.1103/PhysRevE.71.046130. Google Scholar

[20]

O. Cybulski and R. Holyst, Three-dimensional space partition based on the first Laplacian eigenvalues in cells,, Physical Review E, 77 (2008). doi: 10.1103/PhysRevE.77.056101. Google Scholar

[21]

L. Dascal, G. Rosman and R. Kimmel, Efficient Beltrami filtering of color images via vector extrapolation,, in SSVM'07: Proceedings of the 1st international conference on Scale space and variational methods in computer vision, 4485 (2007), 92. doi: 10.1007/978-3-540-72823-8_9. Google Scholar

[22]

A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm,, Journal of the Royal Statistical Society. Series B (Methodological), 39 (1977), 1. Google Scholar

[23]

J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions,, in Proceedings of the 25th international conference on Machine learning - ICML '08, (2008), 272. Google Scholar

[24]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems,, North-Holland Publishing Company, (1976). Google Scholar

[25]

S. Esedoglu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions,, Communications on Pure and Applied Mathematics, 68 (2015), 808. doi: 10.1002/cpa.21527. Google Scholar

[26]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science,, SIAM Journal on Imaging Sciences, 3 (2010), 1015. doi: 10.1137/09076934X. Google Scholar

[27]

M. Feigin and N. Sochen, Anisotropic regularization for inverse problems with application to the Wiener filter with Gaussian and impulse noise,, in Scale Space and Variational Methods in Computer Vision, (5567), 319. doi: 10.1007/978-3-642-02256-2_27. Google Scholar

[28]

R. Gabbrielli, A new counter-example to Kelvin's conjecture on minimal surfaces,, Philosophical Magazine Letters, 89 (2009), 483. doi: 10.1080/09500830903022651. Google Scholar

[29]

C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus, Multiclass data segmentation using diffuse interface methods on graphs,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (2014), 1600. doi: 10.1109/TPAMI.2014.2300478. Google Scholar

[30]

E. Giusti, Minimal Surfaces and Functions of Bounded Variation,, Springer Science & Business Media, (1984). doi: 10.1007/978-1-4684-9486-0. Google Scholar

[31]

T. C. Hales, The honeycomb conjecture,, Discrete & Computational Geometry, 25 (2001), 1. doi: 10.1007/s004540010071. Google Scholar

[32]

B. Helffer, On spectral minimal partitions: A survey,, Milan J. Math., 78 (2010), 575. doi: 10.1007/s00032-010-0129-0. Google Scholar

[33]

B. Helffer and T. Hoffmann-Ostenhof, Remarks on two notions of spectral minimal partitions,, Adv. Math. Sci. Appl., 20 (2010), 249. Google Scholar

[34]

B. Helffer, T. Hoffmann-Ostenhof and S. Terracini, On spectral minimal partitions: The case of the sphere, 2010,, Around the research of Vladimir Maz'ya. III, 13 (2010), 153. doi: 10.1007/978-1-4419-1345-6_6. Google Scholar

[35]

C. Herring, Some theorems on the free energies of crystal surfaces,, Physical Review, 82 (1951), 87. doi: 10.1103/PhysRev.82.87. Google Scholar

[36]

R. Kaftory, N. A. Sochen and Y. Y. Zeevi, Variational blind deconvolution of multi-channel images,, Int. J. Imaging Syst. Technol., 15 (2005), 56. doi: 10.1002/ima.20038. Google Scholar

[37]

R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images,, Int. J. Comput. Vis., 39 (2000), 111. Google Scholar

[38]

C. Li, C.-Y. Kao, J. C. Gore and Z. Ding, Minimization of region-scalable fitting energy for image segmentation,, IEEE Transactions on Image Processing, 17 (2008), 1940. doi: 10.1109/TIP.2008.2002304. Google Scholar

[39]

Z. Liang and Y. Li, Beltrami flow in Hilbert space with applications to image denoising,, Journal of Electronic Imaging, 21 (2012), 1. doi: 10.1117/1.JEI.21.4.043019. Google Scholar

[40]

S. Lloyd, Least squares quantization in PCM,, IEEE Transactions on Information Theory, 28 (1982), 129. doi: 10.1109/TIT.1982.1056489. Google Scholar

[41]

L. Lopez-Perez, R. Deriche and N. Sochen, The Beltrami flow over triangulated manifolds,, in CVAMIA and MMBIA Workshop at ECCV 2004, 3117 (2004), 135. doi: 10.1007/978-3-540-27816-0_12. Google Scholar

[42]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for segmentation and image processing,, SIAM J. Imaging Sciences, 6 (2013), 1903. doi: 10.1137/120886935. Google Scholar

[43]

B. Merriman, J. K. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature,, Technical report, (1992), 92. Google Scholar

[44]

B. Merriman, J. K. Bence and S. Osher, Diffusion generated motion by mean curvature,, AMS Selected Letters, (): 73. Google Scholar

[45]

B. Osting and C. D. White, Nonnegative matrix factorization of transition matrices via eigenvalue optimization,, in NIPS OPT, (2013). Google Scholar

[46]

B. Osting, C. D. White and É. Oudet, Minimal Dirichlet energy partitions for graphs,, SIAM Journal on Scientific Computing, 36 (2014). doi: 10.1137/130934568. Google Scholar

[47]

É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture,, Experimental Mathematics, 20 (2011), 260. doi: 10.1080/10586458.2011.565233. Google Scholar

[48]

J. Plateau, Statique Expérimentale et Théorique des Liquides Soumis Aux Seules Forces Moléculaires,, Gauthier-Villars, (1873). Google Scholar

[49]

G. Pólya and G. Szegő, Isoperimetric inequalities in mathematical physics,, Princeton University Press, (1951). Google Scholar

[50]

G. Rosman, X.-C. Tai, L. Dascal and R. Kimmel, Polyakov action for efficient color image processing,, Trends and Topics in Computer Vision, 6554 (2010), 50. doi: 10.1007/978-3-642-35740-4_5. Google Scholar

[51]

A. Roussos and P. Maragos, Tensor-based image diffusions derived from generalizations of the total variation and Beltrami functionals,, in 2010 IEEE International Conference on Image Processing, (2010), 4141. doi: 10.1109/ICIP.2010.5653241. Google Scholar

[52]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[53]

C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Gabor feature space diffusion via the minimal weighted area method,, in Energy Minimization Methods in Computer Vision and Pattern Recognition, 2134 (2001), 621. doi: 10.1007/3-540-44745-8_41. Google Scholar

[54]

H. Schaeffer and L. Vese, Variational dynamics of free triple junctions,, Journal of Scientific Computing, 59 (2014), 386. doi: 10.1007/s10915-013-9767-z. Google Scholar

[55]

H. A. Schwarz, Gesammelte mathematische Abhandlungen,, Springer Berlin Heidelberg, (1890). doi: 10.1007/978-3-642-50665-9. Google Scholar

[56]

W. Sir Thomson, On the division of space with minimum partitional area,, Acta Mathematica, 11 (1887), 121. doi: 10.1007/BF02612322. Google Scholar

[57]

N. Sochen, R. Deriche and L. Lopez-Perez, The Beltrami flow over implicit manifolds,, in 9th IEEE ICCV, (2003), 832. doi: 10.1109/ICCV.2003.1238434. Google Scholar

[58]

N. Sochen, R. Kimmel and R. Malladi, A general framework for low level vision,, IEEE Transactions on Image Processing, 7 (1998), 310. doi: 10.1109/83.661181. Google Scholar

[59]

N. A. Sochen, Stochastic processes in vision: From Langevin to Beltrami,, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 1 (2001), 288. doi: 10.1109/ICCV.2001.937531. Google Scholar

[60]

A. Spira, R. Kimmel and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds,, IEEE Transactions on Image Processing, 16 (2007), 1628. doi: 10.1109/TIP.2007.894253. Google Scholar

[61]

M. van den Berg and D. Bucur, On the torsion function with Robin or Dirichlet boundary conditions,, Journal of Functional Analysis, 266 (2014), 1647. doi: 10.1016/j.jfa.2013.07.007. Google Scholar

[62]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs,, Milan Journal of Mathematics, 82 (2014), 3. doi: 10.1007/s00032-014-0216-8. Google Scholar

[63]

A. Wetzler and R. Kimmel, Efficient Beltrami flow in patch-space,, in Scale Space and Variational Methods in Computer Vision 2011 (eds. A. M. Bruckstein, (2011), 134. doi: 10.1007/978-3-642-24785-9_12. Google Scholar

[64]

Z. Yang, T. Hao, O. Dikmen, X. Chen and E. Oja, Clustering by nonnegative matrix factorization using graph random walk,, in Advances in Neural Information Processing Systems 25, (2012), 1079. Google Scholar

[65]

M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration,, Technical report, (2008), 08. Google Scholar

[66]

M. Zhu, S. J. Wright and T. F. Chan, Duality-based algorithms for total-variation-regularized image restoration,, Computational Optimization and Applications, 47 (2010), 377. doi: 10.1007/s10589-008-9225-2. Google Scholar

[67]

D. Zosso, J. An, J. Stevick, N. Takaki, M. Weiss, L. S. Slaughter, H. H. Cao, P. S. Weiss and A. L. Bertozzi, Image segmentation with dynamic artifacts detection and bias correction,, submitted to: AIMS J. Inverse Problems and Imaging, (). Google Scholar

[68]

D. Zosso and A. Bustin, A Primal-Dual Projected Gradient Algorithm for Efficient Beltrami Regularization,, Technical report, (2014), 14. Google Scholar

show all references

References:
[1]

K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming,, Cambridge Univ. Press, (1958). Google Scholar

[2]

I. Babuska, The finite element method with penalty,, Mathematics of Computation, 27 (1973), 221. doi: 10.1090/S0025-5718-1973-0351118-5. Google Scholar

[3]

D. A. Bader, H. Meyerhenke, P. Sanders and D. Wagner (eds.), Graph Partitioning and Graph Clustering,, American Mathematical Society, (2013). doi: 10.1090/conm/588. Google Scholar

[4]

D. Barash, Fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 844. doi: 10.1109/TPAMI.2002.1008390. Google Scholar

[5]

B. Bogosel, Shape Optimization and Spectral Problems,, Ph.D. thesis, (2015). Google Scholar

[6]

B. Bogosel, Partitions minimizing an anisotropic length,, 2016., (). Google Scholar

[7]

V. Bonnaillie-Noël and B. Helffer, Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions,, Experimental Mathematics, 20 (2011), 304. doi: 10.1080/10586458.2011.565240. Google Scholar

[8]

V. Bonnaillie-Noël, B. Helffer and G. Vial, Numerical simulations for nodal domains and spectral minimal partitions,, ESAIM: Control, 16 (2010), 221. doi: 10.1051/cocv:2008074. Google Scholar

[9]

V. Bonnaillie-Noël and C. Léna, Spectral minimal partitions for a family of tori,, URL , (). Google Scholar

[10]

B. Bourdin, D. Bucur and É. Oudet, Optimal partitions for eigenvalues,, SIAM Journal on Scientific Computing, 31 (2010), 4100. doi: 10.1137/090747087. Google Scholar

[11]

T. Brox and D. Cremers, On local region models and a statistical interpretation of the piecewise smooth Mumford-Shah functional,, International Journal of Computer Vision, 84 (2009), 184. doi: 10.1007/s11263-008-0153-5. Google Scholar

[12]

D. Bucur, G. Butazzo and A. Henrot, Existence results for some optimal partition problems,, Adv. Math. Sci. Appl., 8 (1998), 571. Google Scholar

[13]

D. Bucur and G. Butazzo, Variational Methods in Shape Optimization Problems, vol. 65 of Progress in Nonlinear Differential Equations and Their Applications,, Birkhäuser Boston, (2005). Google Scholar

[14]

D. Bucur and B. Velichkov, Multiphase shape optimization problems,, SIAM Journal on Control and Optimization, 52 (2014), 3556. doi: 10.1137/130917272. Google Scholar

[15]

L. A. Cafferelli and F. H. Lin, An optimal partition problem for eigenvalues,, Journal of Scientific Computing, 31 (2007), 5. doi: 10.1007/s10915-006-9114-8. Google Scholar

[16]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging,, Journal of Mathematical Imaging and Vision, 40 (2011), 120. doi: 10.1007/s10851-010-0251-1. Google Scholar

[17]

T. F. Chan and L. A. Vese, Active contours without edges,, IEEE Transactions on Image Processing, 10 (2001), 266. doi: 10.1109/83.902291. Google Scholar

[18]

H. Cohn and A. Kumar, Universally optimal distribution of points on spheres,, Journal of the American Mathematical Society, 20 (2007), 99. doi: 10.1090/S0894-0347-06-00546-7. Google Scholar

[19]

O. Cybulski, V. Babin and R. Holyst, Minimization of the Renyi entropy production in the space-partitioning process,, Physical Review E, 71 (2005). doi: 10.1103/PhysRevE.71.046130. Google Scholar

[20]

O. Cybulski and R. Holyst, Three-dimensional space partition based on the first Laplacian eigenvalues in cells,, Physical Review E, 77 (2008). doi: 10.1103/PhysRevE.77.056101. Google Scholar

[21]

L. Dascal, G. Rosman and R. Kimmel, Efficient Beltrami filtering of color images via vector extrapolation,, in SSVM'07: Proceedings of the 1st international conference on Scale space and variational methods in computer vision, 4485 (2007), 92. doi: 10.1007/978-3-540-72823-8_9. Google Scholar

[22]

A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm,, Journal of the Royal Statistical Society. Series B (Methodological), 39 (1977), 1. Google Scholar

[23]

J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions,, in Proceedings of the 25th international conference on Machine learning - ICML '08, (2008), 272. Google Scholar

[24]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems,, North-Holland Publishing Company, (1976). Google Scholar

[25]

S. Esedoglu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions,, Communications on Pure and Applied Mathematics, 68 (2015), 808. doi: 10.1002/cpa.21527. Google Scholar

[26]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science,, SIAM Journal on Imaging Sciences, 3 (2010), 1015. doi: 10.1137/09076934X. Google Scholar

[27]

M. Feigin and N. Sochen, Anisotropic regularization for inverse problems with application to the Wiener filter with Gaussian and impulse noise,, in Scale Space and Variational Methods in Computer Vision, (5567), 319. doi: 10.1007/978-3-642-02256-2_27. Google Scholar

[28]

R. Gabbrielli, A new counter-example to Kelvin's conjecture on minimal surfaces,, Philosophical Magazine Letters, 89 (2009), 483. doi: 10.1080/09500830903022651. Google Scholar

[29]

C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus, Multiclass data segmentation using diffuse interface methods on graphs,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (2014), 1600. doi: 10.1109/TPAMI.2014.2300478. Google Scholar

[30]

E. Giusti, Minimal Surfaces and Functions of Bounded Variation,, Springer Science & Business Media, (1984). doi: 10.1007/978-1-4684-9486-0. Google Scholar

[31]

T. C. Hales, The honeycomb conjecture,, Discrete & Computational Geometry, 25 (2001), 1. doi: 10.1007/s004540010071. Google Scholar

[32]

B. Helffer, On spectral minimal partitions: A survey,, Milan J. Math., 78 (2010), 575. doi: 10.1007/s00032-010-0129-0. Google Scholar

[33]

B. Helffer and T. Hoffmann-Ostenhof, Remarks on two notions of spectral minimal partitions,, Adv. Math. Sci. Appl., 20 (2010), 249. Google Scholar

[34]

B. Helffer, T. Hoffmann-Ostenhof and S. Terracini, On spectral minimal partitions: The case of the sphere, 2010,, Around the research of Vladimir Maz'ya. III, 13 (2010), 153. doi: 10.1007/978-1-4419-1345-6_6. Google Scholar

[35]

C. Herring, Some theorems on the free energies of crystal surfaces,, Physical Review, 82 (1951), 87. doi: 10.1103/PhysRev.82.87. Google Scholar

[36]

R. Kaftory, N. A. Sochen and Y. Y. Zeevi, Variational blind deconvolution of multi-channel images,, Int. J. Imaging Syst. Technol., 15 (2005), 56. doi: 10.1002/ima.20038. Google Scholar

[37]

R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images,, Int. J. Comput. Vis., 39 (2000), 111. Google Scholar

[38]

C. Li, C.-Y. Kao, J. C. Gore and Z. Ding, Minimization of region-scalable fitting energy for image segmentation,, IEEE Transactions on Image Processing, 17 (2008), 1940. doi: 10.1109/TIP.2008.2002304. Google Scholar

[39]

Z. Liang and Y. Li, Beltrami flow in Hilbert space with applications to image denoising,, Journal of Electronic Imaging, 21 (2012), 1. doi: 10.1117/1.JEI.21.4.043019. Google Scholar

[40]

S. Lloyd, Least squares quantization in PCM,, IEEE Transactions on Information Theory, 28 (1982), 129. doi: 10.1109/TIT.1982.1056489. Google Scholar

[41]

L. Lopez-Perez, R. Deriche and N. Sochen, The Beltrami flow over triangulated manifolds,, in CVAMIA and MMBIA Workshop at ECCV 2004, 3117 (2004), 135. doi: 10.1007/978-3-540-27816-0_12. Google Scholar

[42]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for segmentation and image processing,, SIAM J. Imaging Sciences, 6 (2013), 1903. doi: 10.1137/120886935. Google Scholar

[43]

B. Merriman, J. K. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature,, Technical report, (1992), 92. Google Scholar

[44]

B. Merriman, J. K. Bence and S. Osher, Diffusion generated motion by mean curvature,, AMS Selected Letters, (): 73. Google Scholar

[45]

B. Osting and C. D. White, Nonnegative matrix factorization of transition matrices via eigenvalue optimization,, in NIPS OPT, (2013). Google Scholar

[46]

B. Osting, C. D. White and É. Oudet, Minimal Dirichlet energy partitions for graphs,, SIAM Journal on Scientific Computing, 36 (2014). doi: 10.1137/130934568. Google Scholar

[47]

É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture,, Experimental Mathematics, 20 (2011), 260. doi: 10.1080/10586458.2011.565233. Google Scholar

[48]

J. Plateau, Statique Expérimentale et Théorique des Liquides Soumis Aux Seules Forces Moléculaires,, Gauthier-Villars, (1873). Google Scholar

[49]

G. Pólya and G. Szegő, Isoperimetric inequalities in mathematical physics,, Princeton University Press, (1951). Google Scholar

[50]

G. Rosman, X.-C. Tai, L. Dascal and R. Kimmel, Polyakov action for efficient color image processing,, Trends and Topics in Computer Vision, 6554 (2010), 50. doi: 10.1007/978-3-642-35740-4_5. Google Scholar

[51]

A. Roussos and P. Maragos, Tensor-based image diffusions derived from generalizations of the total variation and Beltrami functionals,, in 2010 IEEE International Conference on Image Processing, (2010), 4141. doi: 10.1109/ICIP.2010.5653241. Google Scholar

[52]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[53]

C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Gabor feature space diffusion via the minimal weighted area method,, in Energy Minimization Methods in Computer Vision and Pattern Recognition, 2134 (2001), 621. doi: 10.1007/3-540-44745-8_41. Google Scholar

[54]

H. Schaeffer and L. Vese, Variational dynamics of free triple junctions,, Journal of Scientific Computing, 59 (2014), 386. doi: 10.1007/s10915-013-9767-z. Google Scholar

[55]

H. A. Schwarz, Gesammelte mathematische Abhandlungen,, Springer Berlin Heidelberg, (1890). doi: 10.1007/978-3-642-50665-9. Google Scholar

[56]

W. Sir Thomson, On the division of space with minimum partitional area,, Acta Mathematica, 11 (1887), 121. doi: 10.1007/BF02612322. Google Scholar

[57]

N. Sochen, R. Deriche and L. Lopez-Perez, The Beltrami flow over implicit manifolds,, in 9th IEEE ICCV, (2003), 832. doi: 10.1109/ICCV.2003.1238434. Google Scholar

[58]

N. Sochen, R. Kimmel and R. Malladi, A general framework for low level vision,, IEEE Transactions on Image Processing, 7 (1998), 310. doi: 10.1109/83.661181. Google Scholar

[59]

N. A. Sochen, Stochastic processes in vision: From Langevin to Beltrami,, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 1 (2001), 288. doi: 10.1109/ICCV.2001.937531. Google Scholar

[60]

A. Spira, R. Kimmel and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds,, IEEE Transactions on Image Processing, 16 (2007), 1628. doi: 10.1109/TIP.2007.894253. Google Scholar

[61]

M. van den Berg and D. Bucur, On the torsion function with Robin or Dirichlet boundary conditions,, Journal of Functional Analysis, 266 (2014), 1647. doi: 10.1016/j.jfa.2013.07.007. Google Scholar

[62]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs,, Milan Journal of Mathematics, 82 (2014), 3. doi: 10.1007/s00032-014-0216-8. Google Scholar

[63]

A. Wetzler and R. Kimmel, Efficient Beltrami flow in patch-space,, in Scale Space and Variational Methods in Computer Vision 2011 (eds. A. M. Bruckstein, (2011), 134. doi: 10.1007/978-3-642-24785-9_12. Google Scholar

[64]

Z. Yang, T. Hao, O. Dikmen, X. Chen and E. Oja, Clustering by nonnegative matrix factorization using graph random walk,, in Advances in Neural Information Processing Systems 25, (2012), 1079. Google Scholar

[65]

M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration,, Technical report, (2008), 08. Google Scholar

[66]

M. Zhu, S. J. Wright and T. F. Chan, Duality-based algorithms for total-variation-regularized image restoration,, Computational Optimization and Applications, 47 (2010), 377. doi: 10.1007/s10589-008-9225-2. Google Scholar

[67]

D. Zosso, J. An, J. Stevick, N. Takaki, M. Weiss, L. S. Slaughter, H. H. Cao, P. S. Weiss and A. L. Bertozzi, Image segmentation with dynamic artifacts detection and bias correction,, submitted to: AIMS J. Inverse Problems and Imaging, (). Google Scholar

[68]

D. Zosso and A. Bustin, A Primal-Dual Projected Gradient Algorithm for Efficient Beltrami Regularization,, Technical report, (2014), 14. Google Scholar

[1]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[2]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[3]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[4]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[5]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[6]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[7]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[8]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[9]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[10]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[11]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017

[12]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[13]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[14]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190

[15]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092

[16]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

[17]

Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang. A clustering based mate selection for evolutionary optimization. Big Data & Information Analytics, 2017, 2 (1) : 77-85. doi: 10.3934/bdia.2017010

[18]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

[19]

Mohamed A. Tawhid, Kevin B. Dsouza. Hybrid binary dragonfly enhanced particle swarm optimization algorithm for solving feature selection problems. Mathematical Foundations of Computing, 2018, 1 (2) : 181-200. doi: 10.3934/mfc.2018009

[20]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (17)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]