AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (2.1 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Unsupervised random forest for affinity estimation

Key Laboratory of Machine Perception (MOE), Department of Machine Intelligence, Peking University, Beijing 100871, China
Department of Electrical and Electronic Engineering, Imperial College London, London, UK
School of Stomatology, Stomatology Hospital, PekingUniversity, Beijing 100081, China
Show Author Information

Graphical Abstract

Abstract

This paper presents an unsupervised cluste-ring random-forest-based metric for affinity estimation in large and high-dimensional data. The criterion usedfor node splitting during forest construction can handle rank-deficiency when measuring cluster compactness. The binary forest-based metric is extended to continuous metrics by exploiting both the common traversal path and the smallest shared parent node.

The proposed forest-based metric efficiently estimates affinity by passing down data pairs in the forest using a limited number of decision trees. A pseudo-leaf-splitting (PLS) algorithm is introduced to account for spatial relationships, which regularizes affinity measures and overcomes inconsistent leaf assign-ments. The random-forest-based metric with PLS facilitates the establishment of consistent and point-wise correspondences. The proposed method has been applied to automatic phrase recognition using color and depth videos and point-wise correspondence. Extensive experiments demonstrate the effectiveness of the proposed method in affinity estimation in a comparison with the state-of-the-art.

Keywords

affinity estimationforest-based metricunsupervised clustering forestpseudo-leaf-splitting (PLS)

References

[1]
Rao, S.; Tron, R.; Vidal, R.; Ma, Y. Motion segmen-tation in the presence of outlying, incomplete, or corrupted trajectories. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 32, No. 10, 1832-1845, 2010.
Crossref Google Scholar
[2]
Brox, T.; Malik, J. Object segmentation by long term analysis of point trajectories. In: Computer Vision-ECCV 2010. Lecture Notes in Computer Science, Vol. 6315. Daniilidis, K.; Maragos, P.; Paragios, N. Eds. Springer Berlin Heidelberg, 282-295, 2010.
Crossref
[3]
Vrigkas, M.; Karavasilis, V.; Nikou, C.; Kakadiaris, I. A. Matching mixtures of curves for human action recognition. Computer Vision and Image Understanding Vol. 119, 27-40, 2014.
Crossref Google Scholar
[4]
Pei, Y. R.; Kim, T. K.; Zha, H. B. Unsupervised random forest manifold alignment for lipreading. In: Proceedings of the IEEE International Conference on Computer Vision, 129-136, 2013.
Crossref
[5]
Boscaini, D.; Masci, J.; Rodolà, E.; Bronstein, M. M.; Cremers, D. Anisotropic diffusion descriptors. Computer Graphics Forum Vol. 35, No. 2, 431-441, 2016.
Crossref Google Scholar
[6]
Ovsjanikov, M.; Ben-Chen, M.; Solomon, J.; Butscher, A.; Guibas, L. Functional maps. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 30, 2012.
Crossref Google Scholar
[7]
Kim, V. G.; Lipman, Y.; Funkhouser, T. Blended intrinsic maps. ACM Transactions on Graphics Vol. 30, No. 4, Article No. 79, 2011.
Crossref Google Scholar
[8]
Sahillioglu, Y.; Yemez, Y. Coarse-to-fine combinatorial matching for dense isometric shape correspondence. Computer Graphics Forum Vol. 30, No. 5, 1461-1470, 2011.
Crossref Google Scholar
[9]
Rodolà, E.; Bulò, S.; Windheuser, T.; Vestner, M.; Cremers, D. Dense non-rigid shape correspondence using random forests. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 4177-4184, 2014.
Crossref
[10]
Boyer, D. M.; Lipman, Y.; St. Clair, E.; Puente, J.; Patel, B. A.; Funkhouser, T.; Jernvall, J.; Daubechies, I. Algorithms to automatically quantify the geometric similarity of anatomical surfaces. Proceedings of the National Academy of Sciences Vol. 108, No. 45, 18221-18226, 2011.
Crossref Google Scholar
[11]
Pei, Y. R.; Kou, L.; Zha, H. B. Anatomical structure similarity estimation by random forest. In: Proceedings of the IEEE International Conference on Image Processing, 2941-2945, 2016.
Crossref
[12]
Criminisi, A.; Shotton, J. Decision Forests for Computer Vision and Medical Image Analysis. London: Springer London, 2013.
Crossref
[13]
Moosmann, F.; Triggs, B.; Jurie, F. Fast discriminative visual codebooks using randomized clustering forests. In: Proceedings of the Conference on Neural Infor-mation Processing Systems, 985-992, 2006.
[14]
Shotton, J.; Fitzgibbon, A.; Cook, M.; Sharp, T.; Finocchio, M.; Moore, R.; Kipman, A.; Blake, A. Real-time human pose recognition in parts from single depth images. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1297-1304, 2011.
Crossref
[15]
Gall, J.; Yao, A.; Razavi, N.; Van Gool, L.; Lempitsky, V. Hough forests for object detection, tracking, and action recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 11, 2188-2202, 2011.
Crossref Google Scholar
[16]
Hengl, T.; Nussbaum, M.; Wright, M. N.; Heuvelink, G. B. M.; Gräler, B. Random forest as a generic framework for predictive modeling of spatial and spatio-temporal variables. PeerJ Vol. 6, e5518, 2018.
Crossref Google Scholar
[17]
Jeung, M.; Baek, S.; Beom, J.; Cho, K. H.; Her, Y.; Yoon, K. Evaluation of random forest and regression tree methods for estimation of mass first flush ratio in urban catchments. Journal of Hydrology Vol. 575, 1099-1110, 2019.
Crossref Google Scholar
[18]
Yeşilkanat, C. M. Spatio-temporal estimation of the daily cases of COVID-19 in worldwide using random forest machine learning algorithm. Chaos, Solitons & Fractals Vol. 140, 110210, 2020.
Crossref Google Scholar
[19]
Breiman, L. Random forests. Machine Learning Vol. 45, No. 1, 5-32, 2001.
Crossref Google Scholar
[20]
Criminisi, A. Decision forests: A unified framework for classification, regression, density estimation, manifold learning and semi-supervised learning. Foundations and Trends®  in Computer Graphics and Vision Vol. 7, Nos. 2-3, 81-227, 2011.
Crossref Google Scholar
[21]
Liu, B.; Xia, Y. Y.; Yu, P. S. Clustering through decision tree construction. In: Proceedings of the 9th International Conference on Information and Knowledge Management, 20-29, 2000.
Crossref
[22]
Shi, T.; Horvath, S. Unsupervised learning with random forest predictors. Journal of Computational and Graphical Statistics Vol. 15, No. 1, 118-138, 2006.
Crossref Google Scholar
[23]
Yu, G.; Yuan, J. S.; Liu, Z. C. Unsupervised random forest indexing for fast action search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 865-872, 2011.
Crossref
[24]
Zhu, X. T.; Loy, C. C.; Gong, S. G. Video synopsis by heterogeneous multi-source correlation. In: Proceedings of the IEEE International Conference on Computer Vision, 81-88, 2013.
Crossref
[25]
Zhu, X. T.; Loy, C. C.; Gong, S. G. Constructing robust affinity graphs for spectral clustering. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1450-1457, 2014.
Crossref
[26]
Alzubaidi, L.; Arkah, Z. M.; Hasan, R. I. Using random forest algorithm for clustering. Journal of Engineering and Applied Sciences Vol. 13, No. 21, 9189-9193, 2018.
Google Scholar
[27]
Pei, Y. R.; Yi, Y. N.; Chen, G.; Xu, T. M.; Zha, H. B.; Ma, G. Y. Voxel-wise correspondence of cone-beam computed tomography images by cascaded randomized forest. In: Proceedings of the IEEE 14th International Symposium on Biomedical Imaging, 481-484, 2017.
Crossref
[28]
Pei, Y. R.; Yi, Y. N.; Ma, G. Y.; Guo, Y. K.; Chen, G.; Xu, T. M.; Zha, H. Mixed metric random forest for dense correspondence of cone-beam computed tomography images. In: Medical Image Computing and Computer Assisted Intervention-MICCAI 2017. Lecture Notes in Computer Science, Vol. 10433. Descoteaux, M.; Maier-Hein, L.; Franz, A.; Jannin, P.; Collins, D.; Duchesne, S. Eds. Springer Cham, 283-290, 2017.
Crossref
[29]
Sun, D.; Pei, Y.; Guo, Y.; Ma, G.; Xu, T.; Zha, H. Dense correspondence of cone-beam computed tomography images using oblique clustering forest. In: Proceedings of the British Machine Vision Conference, 2018.
[30]
Pei, Y. R.; Yi, Y. N.; Ma, G. Y.; Kim, T. K.; Guo, Y. K.; Xu, T. M.; Zha, H. Spatially consistent supervoxel correspondences of cone-beam computed tomography images. IEEE Transactions on Medical Imaging Vol. 37, No. 10, 2310-2321, 2018.
Crossref Google Scholar
[31]
Li, Z. H.; Nie, F. P.; Chang, X. J.; Yang, Y.; Zhang, C. Q.; Sebe, N. Dynamic affinity graph construction for spectral clustering using multiple features. IEEE Transactions on Neural Networks and Learning Systems Vol. 29, No. 12, 6323-6332, 2018.
Crossref Google Scholar
[32]
Ganapathi-Subramanian, V.; Diamanti, O.; Guibas, L. J. Modular latent spaces for shape correspondences. Computer Graphics Forum Vol. 37, No. 5, 199-210, 2018.
Crossref Google Scholar
[33]
Aflalo, Y.; Dubrovina, A.; Kimmel, R. Spectral generalized multi-dimensional scaling. International Journal of Computer Vision Vol. 118, No. 3, 380-392, 2016.
Crossref Google Scholar
[34]
Huang, Q. X.; Guibas, L. Consistent shape maps via semidefinite programming. Computer Graphics Forum Vol. 32, No. 5, 177-186, 2013.
Crossref Google Scholar
[35]
Huang, Q. X.; Wang, F.; Guibas, L. Functional map networks for analyzing and exploring large shape collections. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 36, 2014.
Crossref Google Scholar
[36]
Nguyen, A.; Ben-Chen, M.; Welnicka, K.; Ye, Y. Y.; Guibas, L. An optimization approach to improving collections of shape maps. Computer Graphics Forum Vol. 30, No. 5, 1481-1491, 2011.
Crossref Google Scholar
[37]
Litany, O.; Remez, T.; Rodolà, E.; Bronstein, A.; Bronstein, M. Deep functional maps: Structured prediction for dense shape correspondence. In: Proceedings of the IEEE International Conference on Computer Vision, 5659-5667, 2017.
Crossref
[38]
Groueix, T.; Fisher, M.; Kim, V. G.; Russell, B. C.; Aubry, M. 3D-CODED: 3D correspondences by deep deformation. In: Computer Vision-ECCV 2018. Lecture Notes in Computer Science, Vol. 11206. Ferrari, V.; Hebert, M.; Sminchisescu, C.; Weiss, Y. Eds. Springer Cham, 235-251, 2018.
Crossref
[39]
Wang, W. Y.; Ceylan, D.; Mech, R.; Neumann, U. 3DN: 3D deformation network. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1038-1046, 2019.
Crossref
[40]
Dice, L. Measures of the amount of ecologic association between species. Ecology Vol. 26, No. 3, 297-302, 1945.
Crossref Google Scholar
[41]
Comaniciu, D.; Meer, P. Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 24, No. 5, 603-619, 2002.
Crossref Google Scholar
[42]
Zhao, G. Y.; Barnard, M.; Pietikainen, M. Lipreading with local spatiotemporal descriptors. IEEE Transactions on Multimedia Vol. 11, No. 7, 1254-1265, 2009.
Crossref Google Scholar
[43]
Anina, I.; Zhou, Z. H.; Zhao, G. Y.; Pietikäinen, M. OuluVS2: A multi-view audiovisual database for non-rigid mouth motion analysis. In: Proceedings of the 11th IEEE International Conference and Workshops on Automatic Face and Gesture Recognition, 1-5, 2015.
Crossref
[44]
Cootes, T. F.; Edwards, G. J.; Taylor, C. J. Active appearance models. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 23, No. 6, 681-685, 2001.
Crossref Google Scholar
[45]
Bronstein, A.; Bronstein, M.; Kimmel, R. Numerical Geometry of Non-Rigid Shapes. New York: Springer New York, 2008.
Crossref
[46]
Anguelov, D.; Srinivasan, P.; Koller, D.; Thrun, S.; Rodgers, J.; Davis, J. Scape. ACM Transactions on Graphics Vol. 24, No. 3, 408-416, 2005.
Crossref Google Scholar
[47]
Bogo, F.; Romero, J.; Loper, M.; Black, M. FAUST: Dataset and evaluation for 3D mesh registration. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3794-3801, 2014.
Crossref
[48]
Aubry, M.; Schlickewei, U.; Cremers, D. The wave kernel signature: A quantum mechanical approach to shape analysis. In: Proceedings of the IEEE International Conference on Computer Vision Workshops, 1626-1633, 2011.
Crossref
[49]
Vlasic, D.; Baran, I.; Matusik, W.; Popović, J.Articulated mesh animation from multi-viewsilhouettes. ACM Transactions on Graphics Vol. 27, No. 3, Article No. 97, 2008.
Crossref Google Scholar
[50]
Wang, F.; Huang, Q. X.; Guibas, L. J. Image co-segmentation via consistent functional maps. In: Proceedings of the IEEE International Conference on Computer Vision, 849-856, 2013.
Crossref
[51]
Chen, Q. F.; Koltun, V. Robust nonrigid registration by convex optimization. In: Proceedings of the IEEE International Conference on Computer Vision, 2039-2047, 2015.
Crossref
[52]
Wei, L. Y.; Huang, Q. X.; Ceylan, D.; Vouga, E.; Li, H. Dense human body correspondences using convolutional networks. arXiv preprint arXiv:1511.05904, 2015.
Crossref Google Scholar
[53]
Kim, V. G.; Li, W.; Mitra, N. J.; Chaudhuri, S.; DiVerdi, S.; Funkhouser, T. Learning part-based templates from large collections of 3D shapes. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 70, 2013.
Crossref Google Scholar
[54]
Zhou, Z. H.; Hong, X. P.; Zhao, G. Y.; Pietikäinen, M. A compact representation of visual speech data using latent variables. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 36, No. 1, 1-1, 2014.
Crossref Google Scholar
[55]
Lee, D.; Lee, J.; Kim, K.-E. Multi-view automatic lip-reading using neural network. In: Computer Vision-ACCV 2016 Workshops. Lecture Notes in Computer Science, Vol.10117. Chen, C. S.; Lu, J.; Ma, K. K. Eds. Springer Cham, 290-302, 2017.
Crossref
[56]
Chung, J. S.; Zisserman, A. Out of time: Automated lip sync in the wild. In: Computer Vision-ACCV 2016 Workshops. Lecture Notes in Computer Science, Vol.10117. Chen, C. S.; Lu, J.; Ma, K. K. Eds. Springer Cham, 251-263, 2017.
Crossref
[57]
Chung, J. S.; Zisserman, A. Lip reading in the wild. In: Computer Vision-ACCV 2016. Lecture Notes in Computer Science, Vol. 10112. Lai, S. H.; Lepetit, V.; Nishino, K.; Sato, Y. Eds. Springer Cham, 87-103, 2017.
Crossref
[58]
Kanavati, F.; Tong, T.; Misawa, K.; Fujiwara, M.; Mori, K.; Rueckert, D.; Glocker, B. Supervoxel classification forests for estimating pairwise image correspondences. Pattern Recognition Vol. 63, 561-569, 2017.
Crossref Google Scholar
Computational Visual Media
Volume 8 Issue 2,
June 2022
Pages 257-272
DOI: 10.1007/s41095-021-0241-9
Cite this article:
Yi Y, Sun D, Li P, et al. Unsupervised random forest for affinity estimation. Computational Visual Media, 2022, 8(2): 257-272. https://doi.org/10.1007/s41095-021-0241-9

562

Views

12

Downloads

9

Crossref

7

Web of Science

8

Scopus

0

CSCD

Altmetrics
Received: 29 March 2021
Accepted: 26 May 2021
Published: 06 December 2021
© The Author(s) 2021.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.
Return