Global minimization for continuous multiphase partitioning problems using a dual approach.

*(English)*Zbl 1235.68244Summary: This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding duality-based approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality.

##### MSC:

68T45 | Machine vision and scene understanding |

94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |

##### Software:

MAXFLOW
PDF
BibTeX
XML
Cite

\textit{E. Bae} et al., Int. J. Comput. Vis. 92, No. 1, 112--129 (2011; Zbl 1235.68244)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Bae, E., & Tai, X. C. (2009a). Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In Scale space and variational methods in computer vision (pp. 1–13). Berlin: Springer. · Zbl 1296.94023 |

[2] | Bae, E., & Tai, X.-C. (2009b). Efficient global minimization for the multiphase Chan-Vese model of image segmentation. In Energy minimization methods in computer vision and pattern recognition (EMMCVPR) (pp. 28–41). |

[3] | Banerjee, S., Merugu, I., Dhillon, J., & Ghosh, J. (2004). Clustering with Bregman divergences. Journal of Machine Learning Research, 234–245. · Zbl 1190.62117 |

[4] | Boykov, Y., & Kolmogorov, V. (2001). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 359–374. · Zbl 1005.68964 |

[5] | Boykov, Y., & Kolmogorov, V. (2003). Computing geodesics and minimal surfaces via graph cuts. In ICCV ’03: proceedings of the ninth IEEE international conference on computer vision (pp. 26–33). Washington: IEEE Computer Society. |

[6] | Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1222–1239. |

[7] | Boykov, Y., Kolmogorov, V., Cremers, D., & Delong, A. (2006). An integral solution to surface evolution pdes via geo-cuts. In ECCV (pp. 409–422). |

[8] | Bresson, X., Esedoglu, S., Vandergheynst, P., Thiran, J. P., & Osher, S. (2007). Fast global minimization of the active contour/snake model. Journal of Mathematical Imaging and Vision, 28(2), 151–167. · Zbl 05193728 |

[9] | Brown, E. S., Chan, T. F., & Bresson, X. (2009). Convex formulation and exact global solutions for multi-phase piecewise constant mumford-shah image segmentation (CAM-report-09-66). UCLA, Applied Mathematics, July 2009. |

[10] | Brown, E. S., Chan, T. F., & Bresson, X. (2010). A convex relaxation method for a class of vector-valued minimization problems with applications to mumford-shah segmentation (CAM-report-10-43). UCLA, Applied Mathematics, July 2010. |

[11] | Chambolle, A. (2004). An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision, 20(1), 89–97. · Zbl 1366.94056 |

[12] | Chan, T. F., & Esedoglu, S. (2005). Aspects of total variation regularized l[sup 1] function approximation. SIAM Journal of Applied Mathematics, 65(5), 1817–1837. · Zbl 1096.94004 |

[13] | Chan, T., & Vese, L. A. (2001). Active contours without edges. IEEE Transactions on Image Processing, 10, 266–277. · Zbl 1039.68779 |

[14] | Combettes, P. L., & Wajs, V. R. (2005). Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, 4(4), 1168–1200. · Zbl 1179.94031 |

[15] | Ekeland, I., & Téman, R. (1999). Convex analysis and variational problems. Philadelphia: Society for Industrial and Applied Mathematics. |

[16] | Fan, K. (1953). Minimax theorems. Proceedings of the National Academy of Sciences of the United States of America, 39, 42–47. · Zbl 0050.06501 |

[17] | Goldstein, T., Bresson, X., & Osher, S. (2009). Geometric applications of the split Bregman method: segmentation and surface reconstruction (UCLA CAM Report 09-06). · Zbl 1203.65044 |

[18] | 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, 271–279. |

[19] | Hyman, J. M., & Shashkov, M. J. (1997a). Adjoint operators for the natural discretizations of the divergence, gradient and curl on logically rectangular grids. Applied Numerical Mathematics, 25(4), 413–442. · Zbl 1005.65024 |

[20] | Hyman, J. M., & Shashkov, M. J. (1997b). Natural discretizations for the divergence, gradient, and curl on logically rectangular grids. Computer Mathematics and Its Applications, 33(4), 81–104. · Zbl 0868.65006 |

[21] | Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 1333–1336. · Zbl 05112455 |

[22] | Kass, M., Witkin, A., & Terzopoulos, D. (1988). Snakes: active contour models. International Journal of Computer Vision, 1(4), 321–331. · Zbl 0646.68105 |

[23] | Kiwiel, K. C. (1995). Proximal minimization methods with generalized Bregman functions. SIAM Journal on Control and Optimization, 35, 1142–1168. · Zbl 0890.65061 |

[24] | Klodt, M., Schoenemann, T., Kolev, K., Schikora, M., & Cremers, D. (2008). An experimental comparison of discrete and continuous shape optimization methods. In ECCV ’08: proceedings of the 10th European conference on computer vision (pp. 332–345). Berlin: Springer. |

[25] | Kohli, P., Pawan Kumar, M., & Torr, P. H. S. (2009). p 3 and beyond: move making algorithms for solving higher order functions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(9), 1645–1656. |

[26] | Kolmogorov, V. (2005). What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In ICCV (pp. 564–571). |

[27] | Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568–1583. · Zbl 05340984 |

[28] | Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 65–81. · Zbl 1039.68666 |

[29] | Komodakis, N., & Tziritas, G. (2007). Approximate labeling via graph-cuts based on linear programming. Pattern Analysis and Machine Intelligence, 1436–1453. |

[30] | Lellmann, J., Kappes, J., Yuan, J., Becker, F., & Schnörr, C. (2009). Convex multi-class image labeling by simplex-constrained total variation. In SSVM ’09: proceedings of the second international conference on scale space and variational methods in computer vision (pp. 150–162). Berlin: Springer. |

[31] | Lellmann, J., Breitenreicher, D., & Schnörr, C. (2010). Fast and exact primal-dual iterations for variational problems in computer vision. In European conference on computer vision (ECCV). · Zbl 1278.90307 |

[32] | Li, S. Z. (2001). Markov random field modeling in image analysis. New York: Springer. · Zbl 0978.68130 |

[33] | Li, H., & Tai, X. C. (2007). Piecewise constant level set methods for multiphase motion. International Journal of Numerical Analysis and Modeling, 4, 274–293. · Zbl 1113.49044 |

[34] | Lie, J., Lysaker, M., & Tai, X.-C. (2006a). A variant of the level set method and applications to image segmentation. Mathematics of Computation, 75(255), 1155–1174. · Zbl 1096.35034 |

[35] | Lie, J., Lysaker, M., & Tai, X. C. (2006b). A binary level set model and some applications to Mumford-Shah image segmentation. IEEE Transactions on Image Processing, 15(5), 1171–1181. · Zbl 1286.94018 |

[36] | Meyer, Y. (2001). University lecture series: Vol. 22. Oscillating patterns in image processing and nonlinear evolution equations. Providence: American Mathematical Society. The fifteenth Dean Jacqueline B. Lewis memorial lectures. |

[37] | Mumford, D., & Shah, J. (1989). Optimal approximation by piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics, 42, 577–685. · Zbl 0691.49036 |

[38] | Nikolova, M., Esedoglu, S., & Chan, T. F. (2006). Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics, 66(5), 1632–1648. · Zbl 1117.94002 |

[39] | Osher, S., & Sethian, J. A. (1988). Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics, 79(1), 12–49. · Zbl 0659.65132 |

[40] | Paragios, N., Chen, Y., & Faugeras, O. (2005). Handbook of mathematical models in computer vision. New York: Springer. · Zbl 1083.68500 |

[41] | Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008a). A convex formulation of continuous multi-label problems. In European conference on computer vision (ECCV), Marseille, France, October 2008. |

[42] | Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008b). A convex formulation of continuous multi-label problems. In ECCV ’08: proceedings of the 10th European conference on computer vision (pp. 792–805). Berlin: Springer. |

[43] | Pock, T., Chambolle, A., Bischof, H., & Cremers, D. (2009). A convex relaxation approach for computing minimal partitions. In IEEE conference on computer vision and pattern recognition (CVPR), Miami, FL. · Zbl 1202.49031 |

[44] | Potts, R. B. (1952). Some generalized order-disorder transformations. Proceedings of the Cambridge Philosophical Society, 48, 106–109. · Zbl 0048.45601 |

[45] | Rockafellar, R. T. (1970). Princeton mathematical series: Vol. 28. Convex analysis. Princeton: Princeton University Press. · Zbl 0193.18401 |

[46] | Rose, K. (1998). Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. In Proceedings of the IEEE (pp. 2210–2239). |

[47] | Strang, G. (1983). Maximal flow through a domain. Mathematical Programming, 26, 123–143. · Zbl 0513.90026 |

[48] | Tao, W., & Tai, X. (2009). Multiple piecewise constant active contours for image segmentation using graph cuts optimization (UCLA cam-report 09-13). |

[49] | Teboulle, M. (2007). A unified continuous optimization framework for center-based clustering methods. Journal of Machine Learning Research, 8, 65–102. · Zbl 1222.68318 |

[50] | Velasco, F. R. D. (1980). Thresholding using the ISODATA clustering algorithm. IEEE Transactions on Systems, Man, and Cybernetics, 10(11), 771–774. |

[51] | Vese, L. A., & Chan, T. F. (2002). A new multiphase level set framework for image segmentation via the mumford and shah model. International Journal of Computer Vision, 50, 271–293. · Zbl 1012.68782 |

[52] | Wainwright, M., Jaakkola, T., & Willsky, A. (2002). Map estimation via agreement on (hyper)trees: message-passing and linear programming approaches. IEEE Transactions on Information Theory, 51, 3697–3717. · Zbl 1318.94025 |

[53] | Yuan, J., Bae, E., Tai, X.-C., & Boykov, Y. (2010). A continuous max-flow approach to Potts model. In ECCV 2010: proceedings of the 11th European conference on computer vision (pp. 332–345). Berlin: Springer. |

[54] | Zach, C., Gallup, D., Frahm, J.-M., & Niethammer, M. (2008). Fast global labeling for real-time stereo using multiple plane sweeps. In Vision, modeling and visualization workshop (VMV). |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.