Abstract
Label ordering, the specification of subset–superset relationships for segmentation labels, has been of increasing interest in image segmentation as they allow for complex regions to be represented as a collection of simple parts. Recent advances in continuous max-flow segmentation have widely expanded the possible label orderings from binary background/foreground problems to extendable frameworks in which the label ordering can be specified. This article presents Directed Acyclic Graph Max-Flow image segmentation which is flexible enough to incorporate any label ordering without constraints. This framework uses augmented Lagrangian multipliers and primal–dual optimization to develop a highly parallelized solver implemented using GPGPU. This framework is validated on synthetic, natural, and medical images illustrating its general applicability.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bae, E., Tai, X. C., & Yuan, J. (2015). Maximizing flows with message-passing: Computing spatially continuous min-cuts. In International workshop on energy minimization methods in computer vision and pattern recognition (pp. 15–28). Springer International Publishing.
Bae, E., Yuan, J., Tai, X. C., & Boykov, Y. (2014). A fast continuous max-flow approach to non-convex multi-labeling problems. In Efficient algorithms for global optimization methods in computer vision (pp. 134–154). Springer Berlin Heidelberg.
Baxter, J. S., Rajchl, M., Yuan, J., & Peters, T. M. (2014). A continuous max-flow approach to general hierarchical multi-labeling problems. arXiv preprint arXiv:1404.0336.
Baxter, J. S., Yuan, J., Drangova, M., Peters, T. M., & Inoue, J. (2016). Shape complexes in continuous max-flow segmentation. In SPIE medical imaging (978434 pp.). International Society for Optics and Photonics.
Bertsekas, D. P. (1999). Nonlinear programming (pp. 1–60). Belmont: Athena scientific.
Billionnet, A., & Minoux, M. (1985). Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Applied Mathematics, 12(1), 1–11.
Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1), 155–225.
Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(9), 1124–1137.
Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 23(11), 1222–1239.
Censor, Y., & Zenios, S. A. (1992). Proximal minimization algorithm with d-functions. Journal of Optimization Theory and Applications, 73(3), 451–464.
Chambolle, A. (2004). An algorithm for total variation minimization and applications. Journal of Mathematical imaging and vision, 20(1–2), 89–97.
Chambolle, A., & Pock, T. (2011). A first-order primal–dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1), 120–145.
Chen, G., & Teboulle, M. (1993). Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3), 538–543.
Cocosco, C. A., Kollokian, V., Kwan, R. K. S., Pike, G. B., & Evans, A. C. (1997). Brainweb: Online interface to a 3D MRI simulated brain database. In NeuroImage.
Delage, E., Lee, H., & Ng, A. Y. (2006). A dynamic bayesian network model for autonomous 3d reconstruction from a single indoor image. In 2006 IEEE computer society conference on computer vision and pattern recognition (CVPR’06) (Vol. 2, pp. 2418–2428). IEEE.
Delong, A., & Boykov, Y. (2009). Globally optimal segmentation of multi-region objects. In International conference on computer vision (ICCV) (pp. 285–292). IEEE.
Delong, A., Gorelick, L., Veksler, O., & Boykov, Y. (2012). Minimizing energies with hierarchical costs. International journal of computer vision, 100(1), 38–58.
Denk, C., & Rauscher, A. (2010). Susceptibility weighted imaging with multiple echoes. Journal of Magnetic Resonance Imaging, 31(1), 185–191.
Ekeland, I., & Temam, R. (1999). Convex analysis and variational problems.Society for Industrial and Applied Mathematics.
Giusti, E. (1984). Minimal surfaces and functions of bounded variation. Springer.
Gulshan, V., Rother, C., Criminisi, A., Blake, A., & Zisserman, A. (2010). Geodesic star convexity for interactive image segmentation. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 3129–3136). IEEE.
Guo, F., Yuan, J., Rajchl, M., Svenningsen, S., Capaldi, D. P., Sheikh, K., et al. (2015). Globally optimal co-segmentation of three-dimensional pulmonary 1 h and hyperpolarized 3 he mri with spatial consistence prior. Medical Image Analysis, 23(1), 43–55.
Haacke, E. M., Xu, Y., Cheng, Y. C. N., & Reichenbach, J. R. (2004). Susceptibility weighted imaging (swi). Magnetic Resonance in Medicine, 52(3), 612–618.
Hoiem, D., Efros, A. A., & Hebert, M. (2007). Recovering surface layout from an image. International Journal of Computer Vision, 75(1), 151–172.
Hong, M., & Luo, Z. Q. (2012). On the linear convergence of the alternating direction method of multipliers. arXiv preprint arXiv:1208.3922.
Ishikawa, H. (2003). Exact optimization for markov random fields with convex priors. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 25(10), 1333–1336.
Ivănescu, P. L. (1965). Some network flow problems solved with pseudo-boolean programming. Operations Research, 13(3), 388–399.
Jang, J., Kim, H. W., & Kim, Y. S. (2014). Co-segmentation of inter-subject brain magnetic resonance images. In IEEE international conference on ubiquitous robots and ambient intelligence (URAI) (pp. 80–84). IEEE.
Koch, L. M., Rajchl, M., Tong, T., Passerat-Palmbach, J., Aljabar, P., & Rueckert, D. (2015). Multi-atlas segmentation as a graph labelling problem: Application to partially annotated atlas data. In Information processing in medical imaging (pp. 221–232). Springer.
Kolmogorov, V., & Zabin, R. (2004). What energy functions can be minimized via graph cuts? Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(2), 147–159.
Pock, T., Chambolle, A., Cremers, D., & Bischof, H. (2009). A convex relaxation approach for computing minimal partitions. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 810–817). IEEE.
Potts, R. B. (1952). Some generalized order-disorder transformations. In Mathematical proceedings of the Cambridge Philosophical Society (Vol. 48, pp. 106–109). Cambridge Univ Press.
Rajchl, M., Baxter, J. S., McLeod, A. J., Yuan, J., Qiu, W., Peters, T. M., & Khan, A. R. (2016). Hierarchical max-flow segmentation framework for multi-atlas segmentation with Kohonen self-organizing map based Gaussian mixture modeling. Medical Image Analysis, 27, 45–56.
Rajchl, M., Yuan, J., White, J., Ukwatta, E., Stirrat, J., Nambakhsh, C., et al. (2014). Interactive hierarchical-flow segmentation of scar tissue from late-enhancement cardiac mr images. Medical Imaging, IEEE Transactions on, 33(1), 159–172.
Rockafellar, R. T. (1976). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5), 877–898.
Schlesinger, D., & Flach, B. (2006). Transforming an arbitrary minsum problem into a binary one. TU: Fak. Informatik.
Su, X., & Chen, W. (2004). Reliability-guided phase unwrapping algorithm: A review. Optics and Lasers in Engineering, 42(3), 245–261.
Thomas, B., Somasundaram, S., Thamburaj, K., Kesavadas, C., Gupta, A. K., Bodhey, N. K., et al. (2008). Clinical applications of susceptibility weighted mr imaging of the brain-a pictorial review. Neuroradiology, 50(2), 105–116.
van der Lijn, F., den Heijer, T., Breteler, M. M., & Niessen, W. J. (2008). Hippocampus segmentation in mr images using atlas registration, voxel classification, and graph cuts. Neuroimage, 43(4), 708–720.
Veksler, O. (2008). Star shape prior for graph-cut image segmentation. In Computer vision—ECCV 2008 (pp. 454–467). Springer.
Yuan, J., Bae, E., & Tai, X. C. (2010). A study on continuous max-flow and min-cut approaches. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 2217–2224). IEEE.
Yuan, J., Bae, E., Tai, X. C., & Boykov, Y. (2010). A continuous max-flow approach to Potts model. In Computer vision—ECCV 2010 (pp. 379–392). Springer.
Yuan, J., Qiu, W., Ukwatta, E., Rajchl, M., Sun, Y., & Fenster, A. (2012). An efficient convex optimization approach to 3D prostate MRI segmentation with generic star shape prior. Prostate MR Image Segmentation Challenge, MICCAI, 7512, 82–89.
Acknowledgements
The authors would like to acknowledge Zahra Hosseini, Maria Drangova, and Ravi Menon’s laboratory at the Robarts Research Institute Imaging Laboratories for their assistance in collecting and processing MRI phase data. John S.H. Baxter and A. Jonathan McLeod were funded through the Natural Sciences and Engineering Research Council of Canada.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Julien Mairal.
Rights and permissions
About this article
Cite this article
Baxter, J.S.H., Rajchl, M., McLeod, A.J. et al. Directed Acyclic Graph Continuous Max-Flow Image Segmentation for Unconstrained Label Orderings. Int J Comput Vis 123, 415–434 (2017). https://doi.org/10.1007/s11263-017-0994-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-017-0994-x