zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Geometric applications of the split Bregman method: segmentation and surface reconstruction. (English) Zbl 1203.65044
Summary: Variational models for image segmentation have many applications, but can be slow to compute. Recently, globally convex segmentation models have been introduced which are very reliable, but contain TV-regularizers, making them difficult to compute. The previously introduced split Bregman method is a technique for fast minimization of L 1 regularized functionals, and has been applied to denoising and compressed sensing problems. By applying the split Bregman concept to image segmentation problems, we build fast solvers which can out-perform more conventional schemes, such as duality based methods and graph-cuts. The convex segmentation schemes also substantially outperform conventional level set methods, such as the Chan-Vese level set-based segmentation algorithm. We also consider the related problem of surface reconstruction from unorganized data points, which is used for constructing level set representations in 3 dimensions. The primary purpose of this paper is to examine the effectiveness of “split Bregman” techniques for solving these problems, and to compare this scheme with more conventional methods.
MSC:
65D18Computer graphics, image analysis, and computational geometry
65D19Computational issues in computer and robotic vision
68U10Image processing (computing aspects)
References:
[1]Adalsteinsson, D., Sethian, J.: A fast level set method for propagating interfaces. J. Comput. Phys. 118, 269–277 (1995) · Zbl 0823.65137 · doi:10.1006/jcph.1995.1098
[2]Almgren, F., Taylor, J.E., Wang, L.: Curvature-driven flows: a variational approach. SIAM J. Control Optim. 31(2), 387–438 (1993) · Zbl 0783.35002 · doi:10.1137/0331020
[3]Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. In: SCG’98: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pp. 39–48. ACM, New York (1998)
[4]Amenta, N., Bern, M., Kamvysselis, M.: A new Voronoi-based surface reconstruction algorithm. In: SIGGRAPH’98: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pp. 415–421. ACM, New York (1998)
[5]Aujol, J.-F., Chambolle, A.: Dual norms and image decomposition models. Int. J. Comput. Vision 63(1), 85–104 (2005) · Zbl 02244103 · doi:10.1007/s11263-005-4948-3
[6]Bertsekas, D.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, San Diego (1996)
[7]Boissonnat, J.-D.: Geometric structures for three-dimensional shape representation. ACM Trans. Graph. 3(4), 266–286 (1984) · doi:10.1145/357346.357349
[8]Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222–1239 (2001) · Zbl 05112621 · doi:10.1109/34.969114
[9]Bregman, L.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex optimization. USSR Comput. Math. Math. Phys. 7, 200–217 (1967) · doi:10.1016/0041-5553(67)90040-7
[10]Bresson, X., Chan, T.: Active contours based on chambolle’s mean curvature motion. In: IEEE International Conference on Image Processing, pp. 33–36 (2007)
[11]Bresson, X., Esedoglu, S., Vandergheynst, P., Thiran, J.-P., Osher, S.: Fast global minimization of the active contour/snake model. J. Math. Imaging Vis. 28, 151–167 (2007) · Zbl 05193728 · doi:10.1007/s10851-007-0002-0
[12]Burger, M., Hintermuller, M.: Projected gradient flows for bv/level set relaxation. UCLA CAM technical report, 05-40 (2005)
[13]Carson, C., Belongie, S., Greenspan, H., Malik, J.: Blobworld: Image segmentation using expectation-maximization and its application to image querying. IEEE Trans. Pattern Anal. Mach. Intell. 24, 1026–1038 (1999) · Zbl 05111981 · doi:10.1109/TPAMI.2002.1023800
[14]Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. In: IEEE International Conference on Computer Vision, p. 694 (1995)
[15]Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1–2), 89–97 (2004) · Zbl 02060335 · doi:10.1023/B:JMIV.0000011320.81911.38
[16]Chambolle, A.: An algorithm for mean curvature motion. Interfaces Free Bound. 6(2), 195–218 (2004) · Zbl 1061.35147 · doi:10.4171/IFB/97
[17]Chambolle, A., Darbon, J.: On total variation minimization and surface evolution using parametric maximum flows. UCLA CAM report 08-19 (2008)
[18]Chan, T.F., Vese, L.: Active contours without edges. IEEE Trans. Image Process. 10, 266–277 (2001) · Zbl 1039.68779 · doi:10.1109/83.902291
[19]Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1999) · Zbl 0929.68118 · doi:10.1137/S1064827596299767
[20]Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66, 1932–1648 (2006)
[21]Darbon, J., Sigelle, M.: A fast and exact algorithm for total variation minimization. IbPRIA 2005 3522(1), 351–359 (2005)
[22]Donoho, D.L., Johnstone, I.M.: Adapting to unknown smoothness via wavelet shrinkage J. Am. Stat. Assoc. 90(432), 1200–1224 (1995) · Zbl 0869.62024 · doi:10.2307/2291512
[23]Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. UCLA CAM technical report, 09-31 (2009)
[24]Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient graph-based image segmentation. Int. J. Comput. Vis. 59(2), 167–181 (2004) · doi:10.1023/B:VISI.0000022288.19776.77
[25]Goldfarb, D., Yin, W.: Parametric maximum flow algorithms for fast total variation minimization. CAAM technical report, TR07-09 (2008)
[26]Goldstein, T., Osher, S.: The split Bregman method for l1 regularized problems. UCLA CAM report 08-29 (2008)
[27]He, L., Chang, T.-C., Osher, S.: Mr image reconstruction from sparse radial samples by using iterative refinement procedures. In: Proceedings of the 13th Annual Meeting of ISMRM, p. 696 (2006)
[28]Hoppe, H., Derose, T., Duchamp, T., Mcdonald, J., Stuetzle, W.: Surface reconstruction from unorganized points. Comput. Graph. 26(2), 71–78 (1992) · doi:10.1145/142920.134011
[29]Jonasson, L., Bresson, X., Hagmann, P., Cuisenaire, O., Meuli, R., Thiran, J.-P.: White matter fiber tract segmentation in dt-mri using geometric flows. Med. Image Anal. 9(9), 223–236 (2005) · doi:10.1016/j.media.2004.07.004
[30]Kass, W., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. Int. J. Comput. Vis. 1(4), 312–331 (2004)
[31]Kimmel, R., Bruckstein, A.M.: Regularized Laplacian zero crossings as optimal edge integrators. Int. J. Comput. Vis. 53, 225–243 (2001) · Zbl 01963239 · doi:10.1023/A:1023030907417
[32]Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell., pp. 147–159 (2004)
[33]Malladi, R., Kimmel, R., Adalsteinsson, D., Sapiro, G., Caselles, V., Sethian, J.A.: A geometric approach to segmentation and analysis of 3d medical images. In: MMBIA’96: Proceedings of the 1996 Workshop on Mathematical Methods in Biomedical Image Analysis (MMBIA’96), Washington, DC, USA, p. 244. IEEE Comput. Soc., Los Alamitos (1996)
[34]Mumford, D., Shah, J.: Optimal approximation by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42, 577–685 (1989) · Zbl 0691.49036 · doi:10.1002/cpa.3160420503
[35]Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Springer, Berlin (2003)
[36]Osher, S., Fedkiw, R.P.: Level set methods. Technical report, in Imaging, Vision and Graphics (2003)
[37]Osher, S., Sethian, J.A.: Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 12–49 (1988) · Zbl 0659.65132 · doi:10.1016/0021-9991(88)90002-2
[38]Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. MMS 4, 460–489 (2005)
[39]Rogers, D.F.: An Introduction to NURBS: With Historical Perspective. Morgan Kaufmann, San Mateo (2001)
[40]Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[41]Sethian, J.A.: Level set methods and fast marching methods: Evolving. In: Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge (1999)
[42]Setzer, S.: Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage. In: Proceedings of the Second International Conference on Scale Space Methods and Variational Methods in Computer Vision (2009)
[43]Sussman, M., Smereka, P., Osher, S.: A level set approach for computing solutions to incompressible two-phase flow. J. Comput. Phys. 114(1), 146–159 (1994) · Zbl 0808.76077 · doi:10.1006/jcph.1994.1155
[44]Tschirren, J., Hoffman, E.A., McLennan, G., Sonka, M.: Intrathoracic airway trees: segmentation and airway morphology analysis from low-dose ct scans. IEEE Trans. Med. Imag. 24, 1529–1539 (2005) · doi:10.1109/TMI.2005.857654
[45]Wang, Y., Yin, W., Zhang, Y.: A fast algorithm for image deblurring with total variation regularization. CAAM technical reports (2007)
[46]Yezzi, A., Kichenassamy, S., Kumar, A., Olver, P., Tannenbaum, A.: A geometric snake model for segmentation of medical imagery. IEEE Trans. Med. Imag. 16(2), 199–209 (1997) · doi:10.1109/42.563665
[47]Yin, W.: Analysis and generalizations of the linearized Bregman method. UCLA CAM technical report, 09-42 (2009)
[48]Yin, W.: Pgc: A preflow-push based graph-cut solver. Version 2.32
[49]Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for l1-minimization with applications to compressed sensing. SIAM J. Imag. Sci. 1, 142–168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983
[50]Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imag. Sci. 1(3), 248–272 (2008) · Zbl 1187.68665 · doi:10.1137/080724265
[51]Zhao, H.-K., Osher, S., Merriman, B., Kang, M.: Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method. Comput. Vis. Image Underst. 80(3), 295–314 (2000) · Zbl 1011.68538 · doi:10.1006/cviu.2000.0875
[52]Zhao, H.-K., Osher, S., Fedkiw, R.: Fast surface reconstruction using the level set method. In: VLSM’01: Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM’01), Washington, DC, USA, p. 194. IEEE Comput. Soc., Los Alamitos (2001)