×

On total variation minimization and surface evolution using parametric maximum flows. (English) Zbl 1371.94073

Summary: In a recent paper Y. Boykov et al. [Lect. Notes Comput. Sci.. 3953, 409–422 (2006)] proposed an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Y. Boykov and V. Kolmogorov [“Computing geodesics and minimal surfaces via graph cuts”. In: International conference on computer vision, pp. 26–33 (2003)]. We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by F. Almgren et al. [SIAM J. Control Optim. 31, No. 2, 387–438 (1993; Zbl 0783.35002)] and S. Luckhaus and T. Sturzenhecker [Calc. Var. Partial Differ. Equ. 3, No. 2, 253–271 (1995; Zbl 0821.35003)], and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
53C44 Geometric evolution equations (mean curvature flow, Ricci flow, etc.) (MSC2010)
35A15 Variational methods applied to PDEs
49Q20 Variational problems in a geometric measure-theoretic setting

Software:

MAXFLOW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows. Theory, algorithms, and applications. Englewood Cliffs: Prentice-Hall. · Zbl 1201.90001
[2] Allard, W. K. (2007). Total variation regularization for image denoising, I. Geometric theory. SIAM Journal on Mathematical Analysis, 39(4), 1150–1190. · Zbl 1185.49047 · doi:10.1137/060662617
[3] Almgren, R. (1993). Variational algorithms and pattern formation in dendritic solidification. Journal of Computational Physics, 106(2), 337–354. · Zbl 0787.65095
[4] Almgren, F., Taylor, J. E., & Wang, L.-H. (1993). Curvature-driven flows: a variational approach. SIAM Journal on Control and Optimization, 31(2), 387–438. · Zbl 0783.35002 · doi:10.1137/0331020
[5] Alter, F., Caselles, V., & Chambolle, A. (2005). A characterization of convex calibrable sets in \(\mathbb{R}\) N . Mathematische Annalen, 332(2), 329–366. · Zbl 1108.35073 · doi:10.1007/s00208-004-0628-9
[6] Babenko, M. A., Derryberry, J., Goldberg, A. V., Tarjan, R. E., & Zhou, Y. (2007). Experimental evaluation of parametric max-flow algorithms. In Lecture notes in computer science (Vol. 4252, pp. 256–269). Berlin: Springer.
[7] Beck, A., & Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1), 183–202. · Zbl 1175.94009 · doi:10.1137/080716542
[8] Bellettini, G., & Paolini, M. (1996). Anisotropic motion by mean curvature in the context of Finsler geometry. Hokkaido Mathematical Journal, 25(3), 537–566. · Zbl 0873.53011
[9] Bellettini, G., Novaga, M., & Paolini, M. (1999). Facet-breaking for three-dimensional crystals evolving by mean curvature. Interfaces and Free Boundaries, 1(1), 39–55. · Zbl 0934.49023 · doi:10.4171/IFB/3
[10] Bellettini, G., Caselles, V., Chambolle, A., & Novaga, M. (2006). Crystalline mean curvature flow of convex sets. Archive for Rational Mechanics and Analysis, 179(1), 109–152. · Zbl 1148.53049 · doi:10.1007/s00205-005-0387-0
[11] Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225. · Zbl 1076.90032 · doi:10.1016/S0166-218X(01)00341-9
[12] Bouchitté, G. (1998). Recent convexity arguments in the calculus of variations. In Lecture notes from the 3rd int. summer school on the calculus of variations, Pisa.
[13] Boykov, Y., & Kolmogorov, V. (2003). Computing geodesics and minimal surfaces via graph cuts. In International conference on computer vision, pp. 26–33.
[14] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9), 1124–1137. · Zbl 05112231 · doi:10.1109/TPAMI.2004.60
[15] Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11), 1222–1239. · Zbl 05112621 · doi:10.1109/34.969114
[16] Boykov, Y., Kolmogorov, V., Cremers, D., & Delong, A. (2006). An integral solution to surface evolution PDEs via Geo-Cuts. In A. Leonardis, H. Bischof, & A. Pinz (Eds.), Lecture notes in computer science : Vol. 3953. European conference on computer vision (ECCV) (pp. 409–422). Graz, Austria, May 2006. Berlin: Springer.
[17] Caselles, V., & Chambolle, A. (2006). Anisotropic curvature-driven flow of convex sets. Nonlinear Analysis, 65(8), 1547–1577. · Zbl 1107.35069 · doi:10.1016/j.na.2005.10.029
[18] Caselles, V., Chambolle, A., & Novaga, M. (2007). The discontinuity set of solutions of the TV denoising problem and some extensions. Multiscale Modeling and Simulation, 6(3), 879–894. · Zbl 1145.49024 · doi:10.1137/070683003
[19] Chambolle, A. (2004). An algorithm for mean curvature motion. Interfaces and Free Boundaries, 6(2), 195–218. · Zbl 1061.35147 · doi:10.4171/IFB/97
[20] Chambolle, A. (2005). Total variation minimization and a class of binary MRF models. In Lecture notes in computer science. Energy minimization methods in computer vision and pattern recognition (pp. 136–152). Berlin: Springer.
[21] Chambolle, A., & Novaga, M. (2007). Approximation of the anisotropic mean curvature flow. Mathematical Models and Methods in the Applied Sciences, 17(6), 833–844. · Zbl 1120.35054 · doi:10.1142/S0218202507002121
[22] Chambolle, A., & Novaga, M. (2008). Implicit time discretization of the mean curvature flow with a discontinuous forcing term. Interfaces and Free Boundaries, 10(3), 283–300. · Zbl 1170.65054
[23] Chan, T. F., & Esedoglu, S. (2005). Aspects of total variation regularized L 1 function approximation. SIAM Journal on Applied Mathematics, 65(5), 1817–1837 (electronic). · Zbl 1096.94004 · doi:10.1137/040604297
[24] Cohen, L. D. (1991). On active contour models and balloons. CVGIP: Image Understanding, 53(2), 211–218. · Zbl 0774.68111 · doi:10.1016/1049-9660(91)90028-N
[25] Combettes, P. L., & Wajs, V. R. (2005). Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation, 4(4), 1168–1200 (electronic). · Zbl 1179.94031 · doi:10.1137/050626090
[26] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms. Cambridge: MIT Press. · Zbl 1047.68161
[27] Cunningham, W. H. (1985). On submodular function minimization. Combinatoria, 5, 185–192. · Zbl 0647.05018 · doi:10.1007/BF02579361
[28] Darbon, J. (2005) Total variation minimization with L 1 data fidelity as a contrast invariant filter. In Proceedings of the 4th international symposium on image and signal processing and analysis (ISPA 2005), Zagreb, Croatia, September 2005.
[29] Darbon, J., & Sigelle, M. (2006). Image restoration with discrete constrained total variation part i: fast and exact optimization. Journal of Mathematical Imaging and Vision, 26(3), 261–276. · Zbl 1478.94026 · doi:10.1007/s10851-006-8803-0
[30] Eisner, M. J., & Severance, D. G. (1976). Mathematical techniques for efficient record segmentation in large shared databases. Journal of the ACM, 23(4), 619–635. · Zbl 0333.68020 · doi:10.1145/321978.321982
[31] Ekeland, I., & Témam, R. (1999). Classics in applied mathematics : Vol. 28. Convex analysis and variational problems. Philadelphia: SIAM. (English ed., translated from the French). · Zbl 0939.49002
[32] Federer, H. (1969). Geometric measure theory. New York: Springer. · Zbl 0176.00801
[33] Freedman, D., & Drineas, P. (2005). Energy minimization via graph cuts: settling what is possible. In IEEE computer society conference on computer vision and pattern recognition (CVPR) (pp. 939–946).
[34] Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989). A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1), 30–55. · Zbl 0679.68080 · doi:10.1137/0218003
[35] Giusti, E. (1984). Monographs in mathematics : Vol. 80. Minimal surfaces and functions of bounded variation. Basel: Birkhäuser. · Zbl 0545.49018
[36] Goldberg, A. V., & Tarjan, R. E. (1986). A new approach to the maximum flow problem. In STOC’86: proceedings of the eighteenth annual ACM symposium on theory of computing (pp. 136–146). New York: ACM Press.
[37] Goldfarb, D., & Yin, Y. (2007). Parametric maximum flow algorithms for fast total variation minimization. Technical report, Rice University (2007). · Zbl 1198.49040
[38] Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989). Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society Series B, 51, 271–279.
[39] Grötschel, M., Lovász, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatoria, 1, 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[40] Hochbaum, D. S. (2001). An efficient algorithm for image segmentation, Markov random fields and related problems. Journal of the ACM, 48(4), 686–701 (electronic). · Zbl 1127.68474 · doi:10.1145/502090.502093
[41] Hochbaum, D. S. (2005). Complexity and algorithms for convex network optimization and other nonlinear problems. A Quarterly Journal of Operations Research, 3(3), 171–216. · Zbl 1099.90059
[42] Iwata, S., Fleischer, L., & Fujishige, S. (2000). A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. In STOC’00: Proceedings of the thirty-second annual ACM symposium on theory of computing (pp. 97–106). New York: ACM. · Zbl 1296.90104
[43] Juan, O., & Boykov, Y. (2006). Active graph cuts. In Proceedings of the IEEE Computer Society conference on computer vision and pattern recognition (CVPR), (pp. 1023–1029).
[44] Kholi, P., & Torr, P. (2005). Efficient solving dynamic Markov random fields using graph cuts. In Proceedings of the 10th international conference on computer vision (pp. 922–929).
[45] Kolmogorov, V., & Zabih, R. (2002). What energy functions can be minimized via graph cuts? In European conference on computer vision (Vol. 3, pp. 65–81), May 2002. · Zbl 1039.68666
[46] Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 2(26), 147–159. · Zbl 05110619 · doi:10.1109/TPAMI.2004.1262177
[47] Kolmogorov, V., Boykov, Y., & Rother, C. (2007). Applications of parametric maxflow in computer vision. In Proceedings of the IEEE 11th international conference on computer vision (ICCV 2007) (pp. 1–8).
[48] Lee, J. (2004). A first course in combinatorial optimization. Cambridge: Cambridge University Press. · Zbl 1089.90044
[49] Lovász, L. (1983). Submodular functions and convexity. In Mathematical programming: the state of the art (pp. 235–257). Bonn, 1982. Berlin: Springer.
[50] Luckhaus, S., & Sturzenhecker, T. (1995). Implicit time discretization for the mean curvature flow equation. Calculus of Variations and Partial Differential Equations, 3(2), 253–271. · Zbl 0821.35003 · doi:10.1007/BF01205007
[51] McCormick, S. T. (1996) Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. In Proceedings of the twenty-eighth annual ACM symposium on theory of computing (pp. 319–328). · Zbl 0936.68013
[52] Murota, K. (2003). SIAM monographs on discrete mathematics and applications. Discrete convex analysis. Philadelphia: SIAM.
[53] Nesterov, Y. (2004). Introductory lectures on convex optimization: a basic course. Dordrecht: Kluwer. · Zbl 1086.90045
[54] Nesterov, Y. (2007) Gradient methods for minimizing composite objective function. Technical report, CORE discussion paper 2007/76, Catholic University of Louvain (2007).
[55] Paolini, M., & Pasquarelli, F. (2000). Numerical simulation of crystalline curvature flow in 3D by interface diffusion. In GAKUTO international series. Mathematical sciences and applications : Vol. 14. Free boundary problems: theory and applications, II (pp. 376–389). Chiba, 1999. Tokyo: Gakkōtosho. · Zbl 0979.53076
[56] Picard, J. C., & Ratliff, H. D. (1975). Minimum cuts and related problems. Networks, 5(4), 357–370. · Zbl 0325.90047 · doi:10.1002/net.3230050405
[57] Rockafellar, R. T. (1997). Princeton landmarks in mathematics. Convex analysis. Princeton: Princeton University Press (Reprint of the 1970 original Princeton paperbacks).
[58] Rouy, E., & Tourin, A. (1992). A viscosity solutions approach to shape-from-shading. SIAM Journal on Numerical Analysis, 29(3), 867–884. · Zbl 0754.65069 · doi:10.1137/0729053
[59] Schrijver, A. (2000). A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory (B), 80, 436–355. · Zbl 1052.90067 · doi:10.1006/jctb.2000.1989
[60] Sethian, J. A. (1999). Fast marching methods. SIAM Review, 41(2), 199–235 (electronic). · Zbl 0926.65106 · doi:10.1137/S0036144598347059
[61] Tsitsiklis, J. N. (1995). Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control, 40(9), 1528–1538. · Zbl 0831.93028 · doi:10.1109/9.412624
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.