Optimum-Path Forest: A Novel and Powerful Framework for Supervised Graph-based Pattern Recognition Techniques
Resumo
We present here a novel framework for graph-based pattern recognition techniques called Optimum-Path Forest (OPF), which has been demonstrated to be superior than traditional supervised pattern recognition techniques, such as Artificial Neural Networks using Multilayer Perceptrons and Support Vector Machines, in terms of both accuracy and execution times. The OPF-based classifiers model the problem of the pattern recognition as a computation of an optimum-path forest in a graph induced by the dataset samples, achieving very good results in complex situations, i.e., in which we have a large amount of overlapped regions. Results in several real and synthetic datasets show the robustness of the OPF-based classifiers against the above ones.Referências
Boser, B., Guyon, I., and Vapnik, V. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the 5th Workshop on Computational Learning Theory, pages 144–152, New York, NY, USA. ACM Press.
Cappabianco, F., Falcão, A., and Rocha, L. (2008). Clustering by optimum path forest and its application to automatic gm/wm classification in mr-t1 images of the brain. In ISBI, pages 428–431.
Chiachia, G., Marana, A., Papa, J., and Falcão, A. (2009). Infrared face recogniton by optimum-path forrest. In Proc. of the 16th Intl. Conf. on Systems, Signals, and Image Processing. Santorini, Greece (accepted).
Duda, R., Hart, P., and Stork, D. (2000). Pattern Classification. Wiley-Interscience.
Falcão, A., Stolfi, J., and Lotufo, R. (2004). The image foresting transform: Theory, algorithms, and applications. IEEE Trans. on PAMI, 26(1):19–29.
Falcão, A., Suzuki, C., Gomes, J., Candido, L., Shimizu, S., and Papa, J. (2008). Sistema para diagnóstico de parasitos intestinais por análise computadorizada de imagens e uso de referido sistema. Protocol number PI018080046387.
Falcão, A., Suzuki, C., Gomes, J., Papa, J., Candido, L., and Shimizu, S. (2006). Sistema para diagnóstico de parasitos intestinais por análise computadorizada de imagens. INPI Protocol-PI0605465-0.
Falcão, A., Suzuki, C., Gomes, J., Papa, J., Candido, L., and Shimizu, S. (2007). A system for diagnosing intestinal parasites by computerized image analysis. PCT Protocol - PCT/BR2007/000272.
Freitas, G., Ávila, A., Pinto, H., Papa, J., and Falcão, A. (2009). Optimum-path forest-based models for rainfall estimation. In Proceedings of the 16th International Conference on Digital Signal Processing. Santorini, Greece (accepted).
Freitas, G. M., Ávila, A. M. H., Pinto, H. S., and Papa, J. P. (2007). Classifiers evaluation for agricultural areas monitoring. In Proceedings of the XV Brazilian Congress on Agrometeorology, volume 1, pages 25–29. Aracaju, Brazil.
Haykin, S. (1994). Neural networks: a comprehensive foundation. Prentice Hall.
Iliev, A., Scordilis, M., Papa, J., and Falcão, A. (2009). Spoken emotion recognition through optimum-path forest classification using glottal features. Computer, Speech, and Language. accepted for publication.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2007). Rotation-invariant texture recognition. In 3rd International Symposium on Visual Computing, volume Part II, LNCS 4842, pages 193–204, Lake Tahoe, Nevada, CA, USA. Springer.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2008a). Learning how to extract rotation-invariant and scale-invariant features from texture images. EURASIP Journal on Advances in Signal Processing, 2008:1–16.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2008b). Novel approaches for exclusive and continuous fingerprint classification. In Proc. of the 3rd Pacific Rim Symposium on Advances in Image and Video Technology, pages 386–397, Berlin, Heidelberg. Springer-Verlag.
Papa, J. (2008). Supervised pattern classification using optimum-path forest. PhD. Thesis - Institute of Computing, University of Campinas, available at [link].
Papa, J., Falcão, A., Levada, A., Corrêa, D., Salvadeo, D., and Mascarenhas, N. (2009a). Fast and accurate holystic face recognition through optimum-path forest. In 16th International Conference on Digital Signal Processing. Santorini, Greece (accepted).
Papa, J., Falcão, A., Suzuki, C., and Mascarenhas, N. (2008a). A discrete approach for supervised pattern recognition. In 12th International Workshop on Combinatorial Image Analysis, volume 4958, pages 136–147. LNCS Springer Berlin/Heidelberg.
Papa, J., Freitas, G., Falcão, A., and Ávila, A. (2009b). Robust training patterns pruning for optimum-path forest and its application for satellite-based rainfall estimation. IEEE Geoscience and Remote Sensing Letters. (accepted for publication).
Papa, J., Spadotto, A., ao, A. F., and Pereira, J. (2008b). Optimum path forest classifier applied to laryngeal pathology detection. In Proc. of the 15th Intl. Conf. on Systems, Signals, and Image Processing, volume 1, pages 249–252, Bratislava, Slovakia. IEEE.
Papa, J., Spadotto, A., Falcão, A., Guido, R., and Pereira, J. (2009c). Robust biomedical signal recognition though optimum-path forest. Artificial Intelligence in Medicine. submitted.
Papa, J. P. and Falcão, A. X. (2008). A new variant of the optimum-path forest classifier. In ISVC ’08: Proceedings of the 4th International Symposium on Advances in Visual Computing, pages 935–944, Berlin, Heidelberg. Springer-Verlag.
Papa, J. P. and Falcão, A. X. (2009a). A learning algorithm for the optimum-path forest classifier. In 7th IAPR Workshop on Graph-based Representations in Pattern Recognition, volume 5534, pages 195–204, Berlin, Heidelberg. Springer-Verlag.
Papa, J. P. and Falcão, A. X. (2009b). On the training patterns pruning for optimum-path forest. In 15th Intl. Conf. on Image Analysis and Processing. Salerno, Italy (accepted).
Papa, J. P., Falcão, A. X., Miranda, P. A. V., Suzuki, C. T. N., and Mascarenhas, N. D. A. (2007). Design of robust pattern classifiers based on optimum-path forests. In Mathematical Morphology and its Applications to Image and Signal Processing (ISMM’07), pages 337–348. MCT/INPE.
Papa, J. P., Falcão, A. X., and Suzuki, C. T. N. (2009d). Supervised pattern classification based on optimum-path forest. International Journal of Imaging Systems and Technology, 19:120–131.
Pisani, R., Papa, J., Zimback, C., Falcão, A., and Barbosa, A. (2009). Land use classification using optimum-path forest. In Proceedings of the 14th Brazilian Symposium on Remote Sensing, pages 7063–7070. MCT-INPE.
Spadotto, A., Pereira, J., Guido, R., Papa, J., Falcão, A., Gatto, A., Cola, P., and Schelp, A. (2008). Oropharyngeal dysphagia identification using wavelets and optimum path forest. In Proc. of the 3rd IEEE Intl. Symp. on Communications, Control and Signal Processing, pages 735–740.
Tang, B. and Mazzoni, D. (2006). Multiclass reduced-set support vector machines. In Proceedings of the 23th International Conference on Machine learning, pages 921–928. ACM Press.
Cappabianco, F., Falcão, A., and Rocha, L. (2008). Clustering by optimum path forest and its application to automatic gm/wm classification in mr-t1 images of the brain. In ISBI, pages 428–431.
Chiachia, G., Marana, A., Papa, J., and Falcão, A. (2009). Infrared face recogniton by optimum-path forrest. In Proc. of the 16th Intl. Conf. on Systems, Signals, and Image Processing. Santorini, Greece (accepted).
Duda, R., Hart, P., and Stork, D. (2000). Pattern Classification. Wiley-Interscience.
Falcão, A., Stolfi, J., and Lotufo, R. (2004). The image foresting transform: Theory, algorithms, and applications. IEEE Trans. on PAMI, 26(1):19–29.
Falcão, A., Suzuki, C., Gomes, J., Candido, L., Shimizu, S., and Papa, J. (2008). Sistema para diagnóstico de parasitos intestinais por análise computadorizada de imagens e uso de referido sistema. Protocol number PI018080046387.
Falcão, A., Suzuki, C., Gomes, J., Papa, J., Candido, L., and Shimizu, S. (2006). Sistema para diagnóstico de parasitos intestinais por análise computadorizada de imagens. INPI Protocol-PI0605465-0.
Falcão, A., Suzuki, C., Gomes, J., Papa, J., Candido, L., and Shimizu, S. (2007). A system for diagnosing intestinal parasites by computerized image analysis. PCT Protocol - PCT/BR2007/000272.
Freitas, G., Ávila, A., Pinto, H., Papa, J., and Falcão, A. (2009). Optimum-path forest-based models for rainfall estimation. In Proceedings of the 16th International Conference on Digital Signal Processing. Santorini, Greece (accepted).
Freitas, G. M., Ávila, A. M. H., Pinto, H. S., and Papa, J. P. (2007). Classifiers evaluation for agricultural areas monitoring. In Proceedings of the XV Brazilian Congress on Agrometeorology, volume 1, pages 25–29. Aracaju, Brazil.
Haykin, S. (1994). Neural networks: a comprehensive foundation. Prentice Hall.
Iliev, A., Scordilis, M., Papa, J., and Falcão, A. (2009). Spoken emotion recognition through optimum-path forest classification using glottal features. Computer, Speech, and Language. accepted for publication.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2007). Rotation-invariant texture recognition. In 3rd International Symposium on Visual Computing, volume Part II, LNCS 4842, pages 193–204, Lake Tahoe, Nevada, CA, USA. Springer.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2008a). Learning how to extract rotation-invariant and scale-invariant features from texture images. EURASIP Journal on Advances in Signal Processing, 2008:1–16.
Montoya-Zegarra, J., Papa, J., Leite, N., Torres, R., and Falcão, A. (2008b). Novel approaches for exclusive and continuous fingerprint classification. In Proc. of the 3rd Pacific Rim Symposium on Advances in Image and Video Technology, pages 386–397, Berlin, Heidelberg. Springer-Verlag.
Papa, J. (2008). Supervised pattern classification using optimum-path forest. PhD. Thesis - Institute of Computing, University of Campinas, available at [link].
Papa, J., Falcão, A., Levada, A., Corrêa, D., Salvadeo, D., and Mascarenhas, N. (2009a). Fast and accurate holystic face recognition through optimum-path forest. In 16th International Conference on Digital Signal Processing. Santorini, Greece (accepted).
Papa, J., Falcão, A., Suzuki, C., and Mascarenhas, N. (2008a). A discrete approach for supervised pattern recognition. In 12th International Workshop on Combinatorial Image Analysis, volume 4958, pages 136–147. LNCS Springer Berlin/Heidelberg.
Papa, J., Freitas, G., Falcão, A., and Ávila, A. (2009b). Robust training patterns pruning for optimum-path forest and its application for satellite-based rainfall estimation. IEEE Geoscience and Remote Sensing Letters. (accepted for publication).
Papa, J., Spadotto, A., ao, A. F., and Pereira, J. (2008b). Optimum path forest classifier applied to laryngeal pathology detection. In Proc. of the 15th Intl. Conf. on Systems, Signals, and Image Processing, volume 1, pages 249–252, Bratislava, Slovakia. IEEE.
Papa, J., Spadotto, A., Falcão, A., Guido, R., and Pereira, J. (2009c). Robust biomedical signal recognition though optimum-path forest. Artificial Intelligence in Medicine. submitted.
Papa, J. P. and Falcão, A. X. (2008). A new variant of the optimum-path forest classifier. In ISVC ’08: Proceedings of the 4th International Symposium on Advances in Visual Computing, pages 935–944, Berlin, Heidelberg. Springer-Verlag.
Papa, J. P. and Falcão, A. X. (2009a). A learning algorithm for the optimum-path forest classifier. In 7th IAPR Workshop on Graph-based Representations in Pattern Recognition, volume 5534, pages 195–204, Berlin, Heidelberg. Springer-Verlag.
Papa, J. P. and Falcão, A. X. (2009b). On the training patterns pruning for optimum-path forest. In 15th Intl. Conf. on Image Analysis and Processing. Salerno, Italy (accepted).
Papa, J. P., Falcão, A. X., Miranda, P. A. V., Suzuki, C. T. N., and Mascarenhas, N. D. A. (2007). Design of robust pattern classifiers based on optimum-path forests. In Mathematical Morphology and its Applications to Image and Signal Processing (ISMM’07), pages 337–348. MCT/INPE.
Papa, J. P., Falcão, A. X., and Suzuki, C. T. N. (2009d). Supervised pattern classification based on optimum-path forest. International Journal of Imaging Systems and Technology, 19:120–131.
Pisani, R., Papa, J., Zimback, C., Falcão, A., and Barbosa, A. (2009). Land use classification using optimum-path forest. In Proceedings of the 14th Brazilian Symposium on Remote Sensing, pages 7063–7070. MCT-INPE.
Spadotto, A., Pereira, J., Guido, R., Papa, J., Falcão, A., Gatto, A., Cola, P., and Schelp, A. (2008). Oropharyngeal dysphagia identification using wavelets and optimum path forest. In Proc. of the 3rd IEEE Intl. Symp. on Communications, Control and Signal Processing, pages 735–740.
Tang, B. and Mazzoni, D. (2006). Multiclass reduced-set support vector machines. In Proceedings of the 23th International Conference on Machine learning, pages 921–928. ACM Press.
Publicado
20/07/2009
Como Citar
PAPA, João Paulo; FALCÃO, Alexandre Xavier.
Optimum-Path Forest: A Novel and Powerful Framework for Supervised Graph-based Pattern Recognition Techniques. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 22. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 41-48.
ISSN 2763-8820.
