Learning on graphs and hierarchies
Resumo
Hierarchies, as described in mathematical morphology, represent nested regions of interest that facilitate high-level analysis and provide mechanisms for coherent data organization. Represented as hierarchical trees, they have formalisms intersecting with graph theory and applications that can be conveniently generalized. However, due to the deterministic algorithms, the multiform representations, and the absence of a direct way to evaluate the hierarchical structure, it is hard to insert hierarchical information into a learning framework and benefit from the recent advances in the field. This work aims to create a learning framework that can operate with hierarchical data and is agnostic to the input and the application. The idea is to study ways to transform the data to a regular representation required by most learning models while preserving the rich information in the hierarchical structure. The methods in this study use edgeweighted image graphs and hierarchical trees as input, evaluating different proposals on the edge detection and segmentation tasks. The model of choice is the Random Forest, a fast, inspectable, scalable method. The experiments in this work are an outline of the original study in the related Ph.D. thesis. They demonstrate that it is possible to create a learning framework dependent only on the hierarchical data that performs well in multiple tasks.
Referências
D. Marr, Vision: a computational investigation into the human representation and processing of visual information, M. Acock, Ed. MIT Press, 1982.
R. Kurzweil, How to create a mind: the secret of human thought revealed, B. Giffords and R. Ottewell, Eds. Penguin Books, 2013.
L. Najman and H. Talbot, Mathematical morphology: from theory to applications, 1st ed., L. Najman and H. Talbot, Eds. John Wiley & Sons, Inc., 2013.
J. Serra, “A lattice approach to image segmentation,” vol. 24, pp. 83–130.
P. Bosilj, E. Kijak, and S. Lefèvre, “Partition and inclusion hierarchies of images: a comprehensive survey,” Journal of Imaging, vol. 4, p. 33, 2018.
M. Clément, C. Kurtz, and L. Wendling, “Learning spatial relations and shapes for structural object description and scene recognition,” Pattern Recognition, vol. 84, pp. 197–210, 2018.
T. T. Nguyen, P. Krishnakumari, S. C. Calvert, H. L. Vu, and H. van Lint, “Feature extraction and clustering analysis of highway congestion,” Transportation Research Part C: Emerging Technologies, vol. 100, pp. 238–258, 2019.
K. Nandy, P. R. Gudla, R. Amundsen, K. J. Meaburn, T. Misteli, and S. J. Lockett, “Supervised learning framework for screening nuclei in tissue sections,” in Annual International Conference of the IEEE Engineering in Medicine and Biology Society IEEE. Boston, MA, USA: IEEE, 2011, pp. 5989–5992.
G. Zwettler and W. Backfrieder, “Evolution strategy classification utilizing meta features and domain-specific statistical a priori models for fully-automated and entire segmentation of medical datasets in 3d radiology,” in International Conference on Computing and Communications Technologies. Chennai, India: IEEE, 2015, pp. 12–18.
F. Meyer, “Hierarchies of partitions and morphological segmentation,” in Scale-Space and Morphology in Computer Vision. Springer Berlin Heidelberg, 2001, vol. 2106, pp. 161–182.
L. Breiman, “Random forests,” Machine Learning, vol. 45, pp. 5–32, 2001.
J. Cousty, L. Najman, and B. Perret, “Constructive links between some morphological hierarchies on edge-weighted graphs,” in Mathematical Morphology and Its Applications to Signal and Image Processing. Springer Berlin Heidelberg, pp. 86–97.
L. Guigues, J. P. Cocquerez, and H. L. Men, “Scale-sets image analysis,” vol. 68, pp. 289–317.
R. R. Sokal and J. Rohlf, “The comparison of dendrograms by objective methods,” vol. 11, pp. 33–40, 1962.
J. Cousty, L. Najman, Y. Kenmochi, and S. Guimarães, “Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps,” Journal of Mathematical Imaging and Vision, vol. 60, pp. 479–502, 2018.
S. Beucher, “Watershed, hierarchical segmentation and waterfall algorithm,” in Computational Imaging and Vision. Springer, 1994, vol. 2, pp. 69–76.
C. Xu, S. Whitt, and J. J. Corso, “Flattening supervoxel hierarchies by the uniform entropy slice,” in IEEE International Conference on Computer Vision. IEEE, 2013, pp. 2240–2247.
M. M. Adão, S. J. F. Guimarães, and Z. K. G. P. Jr, “Learning to realign hierarchy for image segmentation,” vol. 133, pp. 287–294.
B. Perret, J. Cousty, S. J. F. Guimarães, Y. Kenmochi, and L. Najman, “Removing non-significant regions in hierarchical clustering and segmentation,” Pattern Recognition Letters, vol. 128, pp. 433–439, 2019.
P. Arbelaez, J. Pont-Tuset, J. Barron, F. Marques, and J. Malik, “Multiscale combinatorial grouping,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2014, pp. 328–335.
E. Scornet, “Random forests and kernel methods,” IEEE Transactions on Information Theory, vol. 62, pp. 1485–1500, 2016.
A. Wyner, M. Olson, J. Bleich, and D. Mease, “Explaining the success of adaboost and random forests as interpolating classifiers,” The Journal of Machine Learning Research, vol. 18, pp. 1558–1590, 2017.
P. Dollar, S. Belongie, and P. Perona, “The fastest pedestrian detector in the west,” in Procedings of the British Machine Vision Conference. British Machine Vision Association, 2010, pp. 68.1–68.11.
D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in Proceedings Eighth IEEE International Conference on Computer Vision. IEEE Comput. Soc, 2001, pp. 416–423.
L. A. C. Mansilla and P. A. V. Miranda, “Oriented image foresting transform segmentation: connectivity constraints with adjustable width,” in Conference on Graphics, Patterns and Images. IEEE, 2016, pp. 289–296.
R. Almeida, E. Kijak, S. Malinowski, Z. K. P. Jr, A. A. Araújo, and S. J. Guimarães, “Graph-based image gradients aggregated with random forests,” Pattern Recognition Letters, 2022.
B. Perret, J. Cousty, S. J. F. Guimaraes, and D. S. Maia, “Evaluation of hierarchical watersheds,” IEEE Transactions on Image Processing, vol. 27, pp. 1676–1688, 2018.
P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “From contours to regions: An empirical evaluation,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009, pp. 2294–2301.
K.-K. Maninis, J. Pont-Tuset, P. Arbelaez, and L. V. Gool, “Convolutional oriented boundaries: from image segmentation to high-level tasks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, pp. 819–833, 2018.
C. J. Taylor, “Towards fast and accurate segmentation,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2013, pp. 1916–1922.
E. Grossiord, H. Talbot, N. Passat, M. Meignan, and L. Najman, “Automated 3d lymphoma lesion segmentation from pet/ct characteristics,” in International Symposium on Biomedical Imaging. IEEE, 2017, pp. 174–178.
Z. Hu, T. Shi, C. Wang, Q. Li, and G. Wu, “Scale-sets image classification with hierarchical sample enriching and automatic scale selection,” International Journal of Applied Earth Observation and Geoinformation, vol. 105, p. 102605, 2021.
F. J. A. Padilla, B. Romaniuk, B. Naegel, S. Servagi-Vernat, D. Morland, D. Papathanassiou, and N. Passat, “Random walkers on morphological trees: a segmentation paradigm,” Pattern Recognition Letters, vol. 141, pp. 16–22, 2021.
R. Almeida, Z. K. G. Patrocínio Jr., A. d. A. Araújo, E. Kijak, S. Malinowski, and S. J. F. Guimarães, “Descriptive image gradient from edge-weighted image graph and random forests,” in 34th Conference on Graphics, Patterns and Images, 2021, pp. 338–345.
R. Kurzweil, How to create a mind: the secret of human thought revealed, B. Giffords and R. Ottewell, Eds. Penguin Books, 2013.
L. Najman and H. Talbot, Mathematical morphology: from theory to applications, 1st ed., L. Najman and H. Talbot, Eds. John Wiley & Sons, Inc., 2013.
J. Serra, “A lattice approach to image segmentation,” vol. 24, pp. 83–130.
P. Bosilj, E. Kijak, and S. Lefèvre, “Partition and inclusion hierarchies of images: a comprehensive survey,” Journal of Imaging, vol. 4, p. 33, 2018.
M. Clément, C. Kurtz, and L. Wendling, “Learning spatial relations and shapes for structural object description and scene recognition,” Pattern Recognition, vol. 84, pp. 197–210, 2018.
T. T. Nguyen, P. Krishnakumari, S. C. Calvert, H. L. Vu, and H. van Lint, “Feature extraction and clustering analysis of highway congestion,” Transportation Research Part C: Emerging Technologies, vol. 100, pp. 238–258, 2019.
K. Nandy, P. R. Gudla, R. Amundsen, K. J. Meaburn, T. Misteli, and S. J. Lockett, “Supervised learning framework for screening nuclei in tissue sections,” in Annual International Conference of the IEEE Engineering in Medicine and Biology Society IEEE. Boston, MA, USA: IEEE, 2011, pp. 5989–5992.
G. Zwettler and W. Backfrieder, “Evolution strategy classification utilizing meta features and domain-specific statistical a priori models for fully-automated and entire segmentation of medical datasets in 3d radiology,” in International Conference on Computing and Communications Technologies. Chennai, India: IEEE, 2015, pp. 12–18.
F. Meyer, “Hierarchies of partitions and morphological segmentation,” in Scale-Space and Morphology in Computer Vision. Springer Berlin Heidelberg, 2001, vol. 2106, pp. 161–182.
L. Breiman, “Random forests,” Machine Learning, vol. 45, pp. 5–32, 2001.
J. Cousty, L. Najman, and B. Perret, “Constructive links between some morphological hierarchies on edge-weighted graphs,” in Mathematical Morphology and Its Applications to Signal and Image Processing. Springer Berlin Heidelberg, pp. 86–97.
L. Guigues, J. P. Cocquerez, and H. L. Men, “Scale-sets image analysis,” vol. 68, pp. 289–317.
R. R. Sokal and J. Rohlf, “The comparison of dendrograms by objective methods,” vol. 11, pp. 33–40, 1962.
J. Cousty, L. Najman, Y. Kenmochi, and S. Guimarães, “Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps,” Journal of Mathematical Imaging and Vision, vol. 60, pp. 479–502, 2018.
S. Beucher, “Watershed, hierarchical segmentation and waterfall algorithm,” in Computational Imaging and Vision. Springer, 1994, vol. 2, pp. 69–76.
C. Xu, S. Whitt, and J. J. Corso, “Flattening supervoxel hierarchies by the uniform entropy slice,” in IEEE International Conference on Computer Vision. IEEE, 2013, pp. 2240–2247.
M. M. Adão, S. J. F. Guimarães, and Z. K. G. P. Jr, “Learning to realign hierarchy for image segmentation,” vol. 133, pp. 287–294.
B. Perret, J. Cousty, S. J. F. Guimarães, Y. Kenmochi, and L. Najman, “Removing non-significant regions in hierarchical clustering and segmentation,” Pattern Recognition Letters, vol. 128, pp. 433–439, 2019.
P. Arbelaez, J. Pont-Tuset, J. Barron, F. Marques, and J. Malik, “Multiscale combinatorial grouping,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2014, pp. 328–335.
E. Scornet, “Random forests and kernel methods,” IEEE Transactions on Information Theory, vol. 62, pp. 1485–1500, 2016.
A. Wyner, M. Olson, J. Bleich, and D. Mease, “Explaining the success of adaboost and random forests as interpolating classifiers,” The Journal of Machine Learning Research, vol. 18, pp. 1558–1590, 2017.
P. Dollar, S. Belongie, and P. Perona, “The fastest pedestrian detector in the west,” in Procedings of the British Machine Vision Conference. British Machine Vision Association, 2010, pp. 68.1–68.11.
D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in Proceedings Eighth IEEE International Conference on Computer Vision. IEEE Comput. Soc, 2001, pp. 416–423.
L. A. C. Mansilla and P. A. V. Miranda, “Oriented image foresting transform segmentation: connectivity constraints with adjustable width,” in Conference on Graphics, Patterns and Images. IEEE, 2016, pp. 289–296.
R. Almeida, E. Kijak, S. Malinowski, Z. K. P. Jr, A. A. Araújo, and S. J. Guimarães, “Graph-based image gradients aggregated with random forests,” Pattern Recognition Letters, 2022.
B. Perret, J. Cousty, S. J. F. Guimaraes, and D. S. Maia, “Evaluation of hierarchical watersheds,” IEEE Transactions on Image Processing, vol. 27, pp. 1676–1688, 2018.
P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “From contours to regions: An empirical evaluation,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009, pp. 2294–2301.
K.-K. Maninis, J. Pont-Tuset, P. Arbelaez, and L. V. Gool, “Convolutional oriented boundaries: from image segmentation to high-level tasks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, pp. 819–833, 2018.
C. J. Taylor, “Towards fast and accurate segmentation,” in IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2013, pp. 1916–1922.
E. Grossiord, H. Talbot, N. Passat, M. Meignan, and L. Najman, “Automated 3d lymphoma lesion segmentation from pet/ct characteristics,” in International Symposium on Biomedical Imaging. IEEE, 2017, pp. 174–178.
Z. Hu, T. Shi, C. Wang, Q. Li, and G. Wu, “Scale-sets image classification with hierarchical sample enriching and automatic scale selection,” International Journal of Applied Earth Observation and Geoinformation, vol. 105, p. 102605, 2021.
F. J. A. Padilla, B. Romaniuk, B. Naegel, S. Servagi-Vernat, D. Morland, D. Papathanassiou, and N. Passat, “Random walkers on morphological trees: a segmentation paradigm,” Pattern Recognition Letters, vol. 141, pp. 16–22, 2021.
R. Almeida, Z. K. G. Patrocínio Jr., A. d. A. Araújo, E. Kijak, S. Malinowski, and S. J. F. Guimarães, “Descriptive image gradient from edge-weighted image graph and random forests,” in 34th Conference on Graphics, Patterns and Images, 2021, pp. 338–345.
Publicado
06/11/2023
Como Citar
ALMEIDA, Raquel; KIJAK, Ewa; MALINOWSKI, Simon; GUIMARÃES, Silvio Jamil F..
Learning on graphs and hierarchies. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 36. , 2023, Rio Grande/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 35-41.
DOI: https://doi.org/10.5753/sibgrapi.est.2023.27449.
