Abstract
In this work, we describe an efficient algorithm, with proof of correctness, for finding an optimal binary segmentation of an image such that the indicated object satisfies a novel high-level prior, called the Band constraint (B), which is the extension of a recent shape prior, called Local Band constraint (LB), to its limiting case with radius tending to infinity. Unlike the LB constraint, the new algorithm can be applied directly to the original image graph saving memory. In our theoretical investigations, we discuss the theoretical relationship of the new B constraint with the Boundary Band (BB) constraint, formerly known as Geodesic Band constraint. Finally, we experimentally conduct a template rotation invariance study of the B constraint within the Oriented Image Foresting Transform framework in region adjacency graphs, when applied to natural images with templates by Gielis geometric equation.
Thanks to Conselho Nacional de Desenvolvimento Científico e Tecnológico – CNPq – (Grant 407242/2021-0, 313087/2021-0, 465446/2014-0), CAPES (88887.136422/2017-00) and FAPESP (2014/12236-1, 2014/50937-1).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Min-Max optimizer is a dual equivalent problem.
- 2.
Note that, in Lines 9–10, since s was removed from set Q on Line 9, we can conclude that it previously had \(S(s) = 0\). Therefore, prior to the execution of Lines 9–10, we had \(s \notin \mathcal{O}_1\) and \(s \in \mathcal{O}_2\). During the execution of Lines 9–10, if \(L(s) = 1\) then s is inserted into \(\mathcal{O}_1\), but it was already in \(\mathcal{O}_2\). On the other hand, if \(L(s) = 0\) then s is removed from \(\mathcal{O}_2\), but \(s \notin \mathcal{O}_1\). A pixel t can also be removed from \(\mathcal{O}_2\) on Lines 17–18, but according to Line 16, this pixel t was previously in the set \(Q_x\), which stores unprocessed pixels, so t was not in \(\mathcal{O}_1\). A pixel t can also be inserted into \(\mathcal{O}_1\) on Lines 25–26, but according to Line 24, this pixel t was previously in the set \(Q_x\), which stores unprocessed pixels, so \(t \in \mathcal{O}_2\) since \(t \notin \mathcal {B}^\prime \).
References
de Moraes Braz, C., Miranda, P.A.: Image segmentation by image foresting transform with geodesic band constraints. In: 2014 IEEE International Conference on Image Processing, pp. 4333–4337. IEEE (2014). https://doi.org/10.1109/ICIP.2014.7025880
Ciesielski, K., Udupa, J., Falcão, A., Miranda, P.: A unifying graph-cut image segmentation framework: algorithms it encompasses and equivalences among them. In: Proceedings of SPIE on Medical Imaging: Image Processing, vol. 8314 (2012)
Das, P., Veksler, O.: Semiautomatic segmentation with compact shapre prior. In: The 3rd Canadian Conference on Computer and Robot Vision, pp. 28–28 (2006)
Freedman, D., Zhang, T.: Interactive graph cut based segmentation with shape priors. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR’05, vol. 1, pp. 755–762. IEEE (2005)
Gulshan, V., Rother, C., Criminisi, A., Blake, A., Zisserman, A.: Geodesic star convexity for interactive image segmentation. In: Proceedings of Computer Vision and Pattern Recognition, pp. 3129–3136 (2010)
Isack, H., Veksler, O., Sonka, M., Boykov, Y.: Hedgehog shape priors for multi-object segmentation. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2434–2442 (2016)
Isack, H.N., Boykov, Y., Veksler, O.: A-expansion for multiple “hedgehog” shapes. CoRR abs/1602.01006 (2016), https://arxiv.org/abs/1602.01006
Malcolm, J., Rathi, Y., Tannenbaum, A.: Graph cut segmentation with nonlinear shape priors. In: 2007 IEEE International Conference on Image Processing, vol. 4, pp. IV-365–IV-368 (2007). https://doi.org/10.1109/ICIP.2007.4380030
Miranda, P., Mansilla, L.: Oriented image foresting transform segmentation by seed competition. IEEE Trans. Image Process. 23(1), 389–398 (2014)
de Moraes Braz, C., Miranda, P.A.V., Ciesielski, K.C., Cappabianco, F.A.M.: Optimum cuts in graphs by general fuzzy connectedness with local band constraints. J. Math. Imaging Vis. 62(5), 659–672 (2020). https://doi.org/10.1007/s10851-020-00953-w
Shi, P., Ratkowsky, D.A., Gielis, J.: The generalized Gielis geometric equation and its application. Symmetry 12(4), 645 (2020). https://doi.org/10.3390/sym12040645
Vu, N., Manjunath, B.S.: Shape prior segmentation of multiple objects with graph cuts. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8 (2008)
Zhang, T., Freedman: tracking objects using density matching and shape priors. In: Proceedings Ninth IEEE International Conference on Computer Vision, vol. 2, pp. 1056–1062 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Braz, C.d.M., Santos, L.F.D., Miranda, P.A.V. (2022). Graph-Based Image Segmentation with Shape Priors and Band Constraints. In: Baudrier, É., Naegel, B., Krähenbühl, A., Tajine, M. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2022. Lecture Notes in Computer Science, vol 13493. Springer, Cham. https://doi.org/10.1007/978-3-031-19897-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-031-19897-7_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-19896-0
Online ISBN: 978-3-031-19897-7
eBook Packages: Computer ScienceComputer Science (R0)