August  2011, 5(3): 645-657. doi: 10.3934/ipi.2011.5.645

A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation

1. 

Department of Applied Mathematics, Nanjing University of Science and Technology, Nanjing, Jiangsu 210094, China, China

2. 

Department of Mathematics, University of Florida, Gainesville, FL 32611

Received  November 2010 Revised  April 2011 Published  August 2011

This paper presents a novel variational model for ultrasound image segmentation that uses a maximum likelihood estimator based on Fisher-Tippett distribution of the intensities of ultrasound images. A convex relaxation method is applied to get a convex model of the subproblem with fixed distribution parameters. The relaxed subproblem, which is convex, can be fast solved by using a primal-dual hybrid gradient algorithm. The experimental results on simulated and real ultrasound images indicate the effectiveness of the method presented.
Citation: Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
References:
[1]

V. Caselles, R. Kimmel and G. Sapiro, On geodesic active contours,, Int. J. Comput. Vis., 22 (1997), 61. doi: 10.1023/A:1007979827043.

[2]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Commun. Pure Appl. Math, 42 (1989), 577. doi: 10.1002/cpa.3160420503.

[3]

S. C. Zhu and A. Yuille, Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation,, IEEE PAMI, 18 (1996), 884. doi: 10.1109/34.537343.

[4]

N. Paragios and R. Deriche, Geodesic active regions and level set methods for supervised texture segmentation,, Int. J. Computer Vision, 46 (2002), 223. doi: 10.1023/A:1014080923068.

[5]

T. F. Chan and L. A. Vese, Active contoure without edges,, IEEE Trans. Image Processing, 10 (2001), 266. doi: 10.1109/83.902291.

[6]

I. B. Ayed, C. Vazquez, A. Mitiche and Z. Belhadj, SAR image segmentation with active contours and level sets,, Proceedings of IEEE Intl. Conf. Image Process (ICIP), 4 (2004), 2717.

[7]

Zhong Tao and H. D. Tagare, Evaluation of four probability distribution models for speckle in clinical cardic ultrasound images,, IEEE Trans. Medical Imaging, 25 (2006), 1483. doi: 10.1109/TMI.2006.881376.

[8]

A. Sarti, C. Corsi and E. Mazzini, Maximum likelihood segmentation of ultrasound images with Rayleigh distribution,, IEEE Trans. Ultrasonics Ferroelectrics and Frequency Control, 52 (2005), 947. doi: 10.1109/TUFFC.2005.1504017.

[9]

J. M. Thijssen, Ultrasonic speckle formation, analysis and processing applied to tissue characterization,, Pattern Recognition Letters, 24 (2003), 659. doi: 10.1016/S0167-8655(02)00173-3.

[10]

S. Osher, J. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations,, J. Comput. Phys., 79 (1988), 12. doi: 10.1016/0021-9991(88)90002-2.

[11]

T. F. Chan, S. Esedoḡlu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models,, SIAM J. Appl. Math, 66 (2006), 1632. doi: 10.1137/040615286.

[12]

X. Bresson, S. Esedoḡlu, P. Vandergheynst, J.-P. Thiran and S. Osher, Fast global minimization of the active contour/snake model,, J. Math Imaging Vis., 28 (2007), 151. doi: 10.1007/s10851-007-0002-0.

[13]

T. Goldstein, X. Bresson and S. Osher, Geometric application of the split Bregman method: Segmentation and surface reconstruction,, Journal of Scientific Computing, 45 (2010), 272.

[14]

J. Yuan, E. Bae and Xue-Cheng Tai, A study on continuous max-flow and min-cut approaches,, 2010 IEEE Conference on Computer Vision and Pattern Recognition, (2010), 2217.

[15]

E. S. Brown, T. F. Chan and X. Bresson, "Globally Convex Chan-Vese Image Segmentation,", CAM Report, (2010), 10.

[16]

E. Bae, J. Yuan and Xue-Cheng Tai, Global minimization for continuous multiphase partitioning problems using a dual approach,, Int. J. Comput. Vis., 92 (2011), 112. doi: 10.1007/s11263-010-0406-y.

[17]

Mingqiang Zhu and T. F. Chan, "An Efficient Primal-Dual Hybrid Gradient Algorithm for TV Image Restoration,", CAM Report, (2008), 8.

[18]

C. B. Burckhardt, Speckle in ultrasound B-mode scans,, IEEE Transaction on Sonics and Ultrasonics, 25 (1978), 1.

[19]

R. F. Wanger, S. W. Smith and J. M. Sandrik, Statistics of speckle in ultrasound B-scans,, IEEE Transaction on Sonics and Ultrasonics, 30 (1983), 156. doi: 10.1109/T-SU.1983.31404.

[20]

V. Dutt and J. Greenleaf, Statistics of the log-compression envelope,, Journal of Acoustical Society of America, 99 (1996), 3817.

[21]

J. M. Thijssen, B. J. Oosterveld and R. F. Wanger, Gray level transforms and lesion detectabivity in echographic images,, Utrason. Imag, 10 (1988), 171.

[22]

E. Esser, Xiaoqun Zhang and T. F. Chan, "A General Framework for a Class of First Order Primal-Dual Algorithms for TV Minimization,", CAM Report, (2009), 9.

[23]

Zhang Xu, A unified primal-dual algorithm based on l1 and Bregman iteration,, private communication, (2009).

[24]

J. A. Jensen, Field: A program for simulating ultrasound systems,, Biological Engineering and Computing, 34 (1996), 351.

[25]

J. A. Jensen and N. B. Svendsen, Calculation of pressure fields from arbitrarily shaped, apodized, and excited ultrasound transducers,, IEEE Trans. Ultrason., 39 (1992), 262.

show all references

References:
[1]

V. Caselles, R. Kimmel and G. Sapiro, On geodesic active contours,, Int. J. Comput. Vis., 22 (1997), 61. doi: 10.1023/A:1007979827043.

[2]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Commun. Pure Appl. Math, 42 (1989), 577. doi: 10.1002/cpa.3160420503.

[3]

S. C. Zhu and A. Yuille, Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation,, IEEE PAMI, 18 (1996), 884. doi: 10.1109/34.537343.

[4]

N. Paragios and R. Deriche, Geodesic active regions and level set methods for supervised texture segmentation,, Int. J. Computer Vision, 46 (2002), 223. doi: 10.1023/A:1014080923068.

[5]

T. F. Chan and L. A. Vese, Active contoure without edges,, IEEE Trans. Image Processing, 10 (2001), 266. doi: 10.1109/83.902291.

[6]

I. B. Ayed, C. Vazquez, A. Mitiche and Z. Belhadj, SAR image segmentation with active contours and level sets,, Proceedings of IEEE Intl. Conf. Image Process (ICIP), 4 (2004), 2717.

[7]

Zhong Tao and H. D. Tagare, Evaluation of four probability distribution models for speckle in clinical cardic ultrasound images,, IEEE Trans. Medical Imaging, 25 (2006), 1483. doi: 10.1109/TMI.2006.881376.

[8]

A. Sarti, C. Corsi and E. Mazzini, Maximum likelihood segmentation of ultrasound images with Rayleigh distribution,, IEEE Trans. Ultrasonics Ferroelectrics and Frequency Control, 52 (2005), 947. doi: 10.1109/TUFFC.2005.1504017.

[9]

J. M. Thijssen, Ultrasonic speckle formation, analysis and processing applied to tissue characterization,, Pattern Recognition Letters, 24 (2003), 659. doi: 10.1016/S0167-8655(02)00173-3.

[10]

S. Osher, J. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations,, J. Comput. Phys., 79 (1988), 12. doi: 10.1016/0021-9991(88)90002-2.

[11]

T. F. Chan, S. Esedoḡlu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models,, SIAM J. Appl. Math, 66 (2006), 1632. doi: 10.1137/040615286.

[12]

X. Bresson, S. Esedoḡlu, P. Vandergheynst, J.-P. Thiran and S. Osher, Fast global minimization of the active contour/snake model,, J. Math Imaging Vis., 28 (2007), 151. doi: 10.1007/s10851-007-0002-0.

[13]

T. Goldstein, X. Bresson and S. Osher, Geometric application of the split Bregman method: Segmentation and surface reconstruction,, Journal of Scientific Computing, 45 (2010), 272.

[14]

J. Yuan, E. Bae and Xue-Cheng Tai, A study on continuous max-flow and min-cut approaches,, 2010 IEEE Conference on Computer Vision and Pattern Recognition, (2010), 2217.

[15]

E. S. Brown, T. F. Chan and X. Bresson, "Globally Convex Chan-Vese Image Segmentation,", CAM Report, (2010), 10.

[16]

E. Bae, J. Yuan and Xue-Cheng Tai, Global minimization for continuous multiphase partitioning problems using a dual approach,, Int. J. Comput. Vis., 92 (2011), 112. doi: 10.1007/s11263-010-0406-y.

[17]

Mingqiang Zhu and T. F. Chan, "An Efficient Primal-Dual Hybrid Gradient Algorithm for TV Image Restoration,", CAM Report, (2008), 8.

[18]

C. B. Burckhardt, Speckle in ultrasound B-mode scans,, IEEE Transaction on Sonics and Ultrasonics, 25 (1978), 1.

[19]

R. F. Wanger, S. W. Smith and J. M. Sandrik, Statistics of speckle in ultrasound B-scans,, IEEE Transaction on Sonics and Ultrasonics, 30 (1983), 156. doi: 10.1109/T-SU.1983.31404.

[20]

V. Dutt and J. Greenleaf, Statistics of the log-compression envelope,, Journal of Acoustical Society of America, 99 (1996), 3817.

[21]

J. M. Thijssen, B. J. Oosterveld and R. F. Wanger, Gray level transforms and lesion detectabivity in echographic images,, Utrason. Imag, 10 (1988), 171.

[22]

E. Esser, Xiaoqun Zhang and T. F. Chan, "A General Framework for a Class of First Order Primal-Dual Algorithms for TV Minimization,", CAM Report, (2009), 9.

[23]

Zhang Xu, A unified primal-dual algorithm based on l1 and Bregman iteration,, private communication, (2009).

[24]

J. A. Jensen, Field: A program for simulating ultrasound systems,, Biological Engineering and Computing, 34 (1996), 351.

[25]

J. A. Jensen and N. B. Svendsen, Calculation of pressure fields from arbitrarily shaped, apodized, and excited ultrasound transducers,, IEEE Trans. Ultrason., 39 (1992), 262.

[1]

Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030

[2]

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

[3]

Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455

[4]

Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925

[5]

Dominique Zosso, Jing An, James Stevick, Nicholas Takaki, Morgan Weiss, Liane S. Slaughter, Huan H. Cao, Paul S. Weiss, Andrea L. Bertozzi. Image segmentation with dynamic artifacts detection and bias correction. Inverse Problems & Imaging, 2017, 11 (3) : 577-600. doi: 10.3934/ipi.2017027

[6]

Matthew S. Keegan, Berta Sandberg, Tony F. Chan. A multiphase logic framework for multichannel image segmentation. Inverse Problems & Imaging, 2012, 6 (1) : 95-110. doi: 10.3934/ipi.2012.6.95

[7]

Ye Yuan, Yan Ren, Xiaodong Liu, Jing Wang. Approach to image segmentation based on interval neutrosophic set. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019028

[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]

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

[10]

Burak Ordin. The modified cutting angle method for global minimization of increasing positively homogeneous functions over the unit simplex. Journal of Industrial & Management Optimization, 2009, 5 (4) : 825-834. doi: 10.3934/jimo.2009.5.825

[11]

Jianping Zhang, Ke Chen, Bo Yu, Derek A. Gould. A local information based variational model for selective image segmentation. Inverse Problems & Imaging, 2014, 8 (1) : 293-320. doi: 10.3934/ipi.2014.8.293

[12]

Ruiliang Zhang, Xavier Bresson, Tony F. Chan, Xue-Cheng Tai. Four color theorem and convex relaxation for image segmentation with any number of regions. Inverse Problems & Imaging, 2013, 7 (3) : 1099-1113. doi: 10.3934/ipi.2013.7.1099

[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]

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

[15]

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

[16]

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

[17]

Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691

[18]

Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022

[19]

Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037

[20]

Zhi-Feng Pang, Yu-Fei Yang. Semismooth Newton method for minimization of the LLT model. Inverse Problems & Imaging, 2009, 3 (4) : 677-691. doi: 10.3934/ipi.2009.3.677

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]