Object segmentation by Oriented Image Foresting Transform with connectivity constraints
Resumo
Global properties, such as connectivity, shape constraints and boundary polarity, are useful high-level priors for image segmentation, allowing its customization for a given target object. In this work, we introduce a new method called Connected Oriented Image Foresting Transform (COIFT), which provides global optimum solutions according to a graph-cut measure, subject to the connectivity constraint in Oriented Image Foresting Transform (OIFT), ensuring the generation of connected objects, as well as allowing the simultaneous control of the boundary polarity. While the use of connectivity constraints in other frameworks, such as in the min-cut/max-flow algorithm, leads to an NP-Hard problem, COIFT conserves the low complexity of the OIFT algorithm. Experiments show that COIFT can considerably improve the segmentation of objects with thin and elongated parts, for the same number of seeds in segmentation based on markers.
Referências
L. Mansilla, “Object segmentation by oriented image foresting transform with connectivity constraints,” Ph.D. dissertation, Department of Computer Science, Institute of Mathematics and Statistics – University of São Paulo (IME-USP), São Paulo, SP, Brazil, Aug 2018, in Portuguese. [Online]. Available: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01102018-120427/en.php
L. Grady, “Random walks for image segmentation,” IEEE Trans. Pattern Anaysis and Machine Intelligence, vol. 28, no. 11, pp. 1768–1783, 2006. https://doi.ieeecomputersociety.org/10.1109/TPAMI.2006.233
Y. Boykov and G. Funka-Lea, “Graph cuts and efficient N-D image segmentation,” Intl. Jrnl. of Comp. Vision, vol. 70, no. 2, pp. 109–131, 2006. https://doi.org/10.1007/s11263-006-7934-5
X. Bai and G. Sapiro, “Distancecut: Interactive segmentation and matting of images and videos,” in Proc. of the IEEE Intl. Conf. on Image Processing, vol. 2, 2007, pp. II – 249–II – 252. https://doi.org/10.1109/ICIP.2007.4379139
K. Ciesielski, J. Udupa, P. Saha, and Y. Zhuge, “Iterative relative fuzzy connectedness for multiple objects with multiple seeds,” Computer Vision and Image Understanding, vol. 107, no. 3, pp. 160–182, 2007. https://doi.org/10.1016/j.cviu.2006.10.005
J. Cousty, G. Bertrand, L. Najman, and M. Couprie, “Watershed cuts: Thinnings, shortest path forests, and topological watersheds,” Trans. on Pattern Analysis and Machine Intelligence, vol. 32, pp. 925–939, 2010. https://doi.org/10.1109/TPAMI.2009.71
K. Ciesielski, J. Udupa, A. Falcão, and P. Miranda, “A unifying graph-cut image segmentation framework: algorithms it encompasses and equivalences among them,” in Proc. of SPIE on Medical Imaging: Image Processing, vol. 8314, 2012. https://doi.org/10.1117/12.911810
C.Couprie, L.Grady, L.Najman, and H.Talbot, “Power watersheds: A unifying graph-based optimization framework,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 99, no. 7, pp. 1384–1399, Jul 2010. https://doi.org/10.1109/TPAMI.2010.200
A. Falcão, J. Stolfi, and R. Lotufo, “The image foresting transform: Theory, algorithms, and applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 1, pp. 19–29, 2004. https://doi.org/10.1109/TPAMI.2004.1261076
S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image segmentation with connectivity priors,” in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conf. on, June 2008, pp. 1–8. https://doi.org/10.1109/CVPR.2008.4587440
Y. Zeng, D. Samaras, W. Chen, and Q. Peng, “Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in nd images,” Computer Vision and Image Understanding, vol. 112, no. 1, pp. 81 – 90, 2008, special Issue on Discrete Optimization in Computer Vision. https://doi.org/10.1016/j.cviu.2008.07.008
S. Nowozin and C. H. Lampert, “Global interactions in random field models: A potential function ensuring connectedness,” SIAM Journal on Imaging Sciences, vol. 3, no. 4, pp. 1048–1074, 2010. [Online]. Available: http://dx.doi.org/10.1137/090752614
O. Lézoray and L. Grady, Image Processing and Analysis with Graphs: Theory and Practice. California, USA: CRC Press, 2012. https://doi.org/10.1201/b12281
K. Ciesielski, A. Falcão, and P. Miranda, “Path-value functions for which dijkstra’s algorithm returns optimal mapping,” Journal of Mathematical Imaging and Vision, Feb 2018. [Online]. Available: https://doi.org/10.1007/s10851-018-0793-1
K. Ciesielski and J. Udupa, “Affinity functions in fuzzy connectedness based image segmentation i: Equivalence of affinities,” Computer Vision and Image Understanding, vol. 114, no. 1, pp. 146–154, Jan 2010. https://doi.org/10.1016/j.cviu.2009.09.006
P. Miranda, A. Falcão, and J. Udupa, “Synergistic arc-weight estimation for interactive image segmentation using graphs,” Computer Vision and Image Understanding, vol. 114, no. 1, pp. 85–99, Jan 2010. https://doi.org/10.1016/j.cviu.2009.08.001
L. Mansilla and P. Miranda, “Image segmentation by oriented image foresting transform: Handling ties and colored images,” in 18th Intl. Conf. on Digital Signal Processing, Greece, Jul 2013, pp. 1–6. https://doi.org/10.1109/ICDSP.2013.6622806
P. Miranda and L. Mansilla, “Oriented image foresting transform segmentation by seed competition,” IEEE Transactions on Image Processing, vol. 23, no. 1, pp. 389–398, Jan 2014. https://doi.org/10.1109/TIP.2013.2288867
L. Mansilla, P. Miranda, and F. Cappabianco, “Oriented image foresting transform segmentation with connectivity constraints,” in Image Processing (ICIP), 2016 23rd IEEE International Conference on, Phoenix, Arizona, USA, Sept 2016, pp. 2554–2558. https://doi.org/10.1109/ICIP.2016.7532820
P. Miranda, A. Falcao, and T. Spina, “Riverbed: A novel user-steered image segmentation method based on optimum boundary tracking,” Image Processing, IEEE Transactions on, vol. 21, no. 6, pp. 3042–3052, June 2012. https://doi.org/10.1109/TIP.2012.2188034
L. Mansilla and P. Miranda, “Oriented image foresting transform segmentation: Connectivity constraints with adjustable width,” in Graphics, Patterns and Images (SIBGRAPI), 2016 29th SIBGRAPI Conference on, São José Dos Campos, SP, Brazil, Oct 2016, pp. 289–296. https://doi.org/10.1109/SIBGRAPI.2016.047
H. H. Bejar and P. A. Miranda, “Oriented relative fuzzy connectedness: Theory, algorithms, and its applications in hybrid image segmentation methods,” EURASIP Journal on Image and Video Processing, vol. 2015, no. 21, Jul 2015. https://doi.org/10.1186/s13640-015-0067-4
K. C. Ciesielski, P. Miranda, A. Falcão, and J. K. Udupa, “Joint graph cut and relative fuzzy connectedness image segmentation algorithm,” Medical Image Analysis (MEDIA), vol. 17, no. 8, pp. 1046–1057, 2013. https://doi.org/10.1016/j.media.2013.06.006
V. Gulshan, C. Rother, A. Criminisi, A. Blake, and A. Zisserman, “Geodesic star convexity for interactive image segmentation,” in Proc. of Computer Vision and Pattern Recognition, 2010, pp. 3129–3136. https://doi.org/10.1109/CVPR.2010.5540073
H. Bejar, L. Mansilla, and P. Miranda, “Efficient unsupervised image segmentation by optimum cuts in graphs,” in 23rd Iberoamerican Congress on Pattern Recognition (CIARP), vol. LNCS 11401, Madrid, Spain, Nov 2018, pp. 359–367. https://doi.org/10.1007/978-3-030-13469-3_42
M. Condori, L. Mansilla, and P. Miranda, “Bandeirantes: A graph-based approach for curve tracing and boundary tracking,” in Mathematical Morphology and Its Applications to Signal and Image Processing, vol. LNCS 10225. Fontainebleau, France: Springer International Publishing, May 2017, pp. 95–106. https://doi.org/10.1007/978-3-319-57240-6_8
L. Grady, “Random walks for image segmentation,” IEEE Trans. Pattern Anaysis and Machine Intelligence, vol. 28, no. 11, pp. 1768–1783, 2006. https://doi.ieeecomputersociety.org/10.1109/TPAMI.2006.233
Y. Boykov and G. Funka-Lea, “Graph cuts and efficient N-D image segmentation,” Intl. Jrnl. of Comp. Vision, vol. 70, no. 2, pp. 109–131, 2006. https://doi.org/10.1007/s11263-006-7934-5
X. Bai and G. Sapiro, “Distancecut: Interactive segmentation and matting of images and videos,” in Proc. of the IEEE Intl. Conf. on Image Processing, vol. 2, 2007, pp. II – 249–II – 252. https://doi.org/10.1109/ICIP.2007.4379139
K. Ciesielski, J. Udupa, P. Saha, and Y. Zhuge, “Iterative relative fuzzy connectedness for multiple objects with multiple seeds,” Computer Vision and Image Understanding, vol. 107, no. 3, pp. 160–182, 2007. https://doi.org/10.1016/j.cviu.2006.10.005
J. Cousty, G. Bertrand, L. Najman, and M. Couprie, “Watershed cuts: Thinnings, shortest path forests, and topological watersheds,” Trans. on Pattern Analysis and Machine Intelligence, vol. 32, pp. 925–939, 2010. https://doi.org/10.1109/TPAMI.2009.71
K. Ciesielski, J. Udupa, A. Falcão, and P. Miranda, “A unifying graph-cut image segmentation framework: algorithms it encompasses and equivalences among them,” in Proc. of SPIE on Medical Imaging: Image Processing, vol. 8314, 2012. https://doi.org/10.1117/12.911810
C.Couprie, L.Grady, L.Najman, and H.Talbot, “Power watersheds: A unifying graph-based optimization framework,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 99, no. 7, pp. 1384–1399, Jul 2010. https://doi.org/10.1109/TPAMI.2010.200
A. Falcão, J. Stolfi, and R. Lotufo, “The image foresting transform: Theory, algorithms, and applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 1, pp. 19–29, 2004. https://doi.org/10.1109/TPAMI.2004.1261076
S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image segmentation with connectivity priors,” in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conf. on, June 2008, pp. 1–8. https://doi.org/10.1109/CVPR.2008.4587440
Y. Zeng, D. Samaras, W. Chen, and Q. Peng, “Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in nd images,” Computer Vision and Image Understanding, vol. 112, no. 1, pp. 81 – 90, 2008, special Issue on Discrete Optimization in Computer Vision. https://doi.org/10.1016/j.cviu.2008.07.008
S. Nowozin and C. H. Lampert, “Global interactions in random field models: A potential function ensuring connectedness,” SIAM Journal on Imaging Sciences, vol. 3, no. 4, pp. 1048–1074, 2010. [Online]. Available: http://dx.doi.org/10.1137/090752614
O. Lézoray and L. Grady, Image Processing and Analysis with Graphs: Theory and Practice. California, USA: CRC Press, 2012. https://doi.org/10.1201/b12281
K. Ciesielski, A. Falcão, and P. Miranda, “Path-value functions for which dijkstra’s algorithm returns optimal mapping,” Journal of Mathematical Imaging and Vision, Feb 2018. [Online]. Available: https://doi.org/10.1007/s10851-018-0793-1
K. Ciesielski and J. Udupa, “Affinity functions in fuzzy connectedness based image segmentation i: Equivalence of affinities,” Computer Vision and Image Understanding, vol. 114, no. 1, pp. 146–154, Jan 2010. https://doi.org/10.1016/j.cviu.2009.09.006
P. Miranda, A. Falcão, and J. Udupa, “Synergistic arc-weight estimation for interactive image segmentation using graphs,” Computer Vision and Image Understanding, vol. 114, no. 1, pp. 85–99, Jan 2010. https://doi.org/10.1016/j.cviu.2009.08.001
L. Mansilla and P. Miranda, “Image segmentation by oriented image foresting transform: Handling ties and colored images,” in 18th Intl. Conf. on Digital Signal Processing, Greece, Jul 2013, pp. 1–6. https://doi.org/10.1109/ICDSP.2013.6622806
P. Miranda and L. Mansilla, “Oriented image foresting transform segmentation by seed competition,” IEEE Transactions on Image Processing, vol. 23, no. 1, pp. 389–398, Jan 2014. https://doi.org/10.1109/TIP.2013.2288867
L. Mansilla, P. Miranda, and F. Cappabianco, “Oriented image foresting transform segmentation with connectivity constraints,” in Image Processing (ICIP), 2016 23rd IEEE International Conference on, Phoenix, Arizona, USA, Sept 2016, pp. 2554–2558. https://doi.org/10.1109/ICIP.2016.7532820
P. Miranda, A. Falcao, and T. Spina, “Riverbed: A novel user-steered image segmentation method based on optimum boundary tracking,” Image Processing, IEEE Transactions on, vol. 21, no. 6, pp. 3042–3052, June 2012. https://doi.org/10.1109/TIP.2012.2188034
L. Mansilla and P. Miranda, “Oriented image foresting transform segmentation: Connectivity constraints with adjustable width,” in Graphics, Patterns and Images (SIBGRAPI), 2016 29th SIBGRAPI Conference on, São José Dos Campos, SP, Brazil, Oct 2016, pp. 289–296. https://doi.org/10.1109/SIBGRAPI.2016.047
H. H. Bejar and P. A. Miranda, “Oriented relative fuzzy connectedness: Theory, algorithms, and its applications in hybrid image segmentation methods,” EURASIP Journal on Image and Video Processing, vol. 2015, no. 21, Jul 2015. https://doi.org/10.1186/s13640-015-0067-4
K. C. Ciesielski, P. Miranda, A. Falcão, and J. K. Udupa, “Joint graph cut and relative fuzzy connectedness image segmentation algorithm,” Medical Image Analysis (MEDIA), vol. 17, no. 8, pp. 1046–1057, 2013. https://doi.org/10.1016/j.media.2013.06.006
V. Gulshan, C. Rother, A. Criminisi, A. Blake, and A. Zisserman, “Geodesic star convexity for interactive image segmentation,” in Proc. of Computer Vision and Pattern Recognition, 2010, pp. 3129–3136. https://doi.org/10.1109/CVPR.2010.5540073
H. Bejar, L. Mansilla, and P. Miranda, “Efficient unsupervised image segmentation by optimum cuts in graphs,” in 23rd Iberoamerican Congress on Pattern Recognition (CIARP), vol. LNCS 11401, Madrid, Spain, Nov 2018, pp. 359–367. https://doi.org/10.1007/978-3-030-13469-3_42
M. Condori, L. Mansilla, and P. Miranda, “Bandeirantes: A graph-based approach for curve tracing and boundary tracking,” in Mathematical Morphology and Its Applications to Signal and Image Processing, vol. LNCS 10225. Fontainebleau, France: Springer International Publishing, May 2017, pp. 95–106. https://doi.org/10.1007/978-3-319-57240-6_8
Publicado
28/10/2019
Como Citar
MANSILLA, Lucy A. C.; MIRANDA, Paulo A. V..
Object segmentation by Oriented Image Foresting Transform with connectivity constraints. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 77-83.
DOI: https://doi.org/10.5753/sibgrapi.est.2019.8305.
