Современные проблемы дистанционного зондирования Земли из космоса. 2015. Т. 12. № 1. С. 131-144
Распознавание текстур на цифровых изображениях методами вычислительной топологии
Н.Г. Макаренко
1,2 , Ф.А. Уртьев
1 , И.С. Князева
1 , Д.Б. Малкова
3 , И.Т. Пак
2 , Л.М. Каримова
2 1 Главная астрономическая обсерватория РАН, Санкт-Петербург, Россия
2 Институт информационных и вычислительных технологий МOН РК, Алматы, Казахстан
3 Ярославский государственный университет им. П.Г. Демидова, Ярославль, Россия
В работе обсуждается распознавание текстур на цифровых изображениях методами вычислительной топологии. Основная идея заключается в использовании логики признаков, основанной на топологической фильтрации. Упорядоченные по фотометрической мере - уровню серого, пиксели изображения сканируются по высоте. Каждый локальный минимум порождает компоненту связности. Она исчезает, если в ее локальной окрестности появляется близкий по величине максимум. При увеличении уровня кластеры, порожденные первичными компонентами, сливаются. Процесс заканчивается, когда получается один глобальный кластер. Число компонент связности измеряется топологическим инвариантом – числом Бетти-нуль. Продолжительность жизни компоненты, или ее персистентность, измеряется разностью двух уровней. Первый маркирует ее появление, второй – слияние с соседним кластером. Слияние отдельных компонент сопровождается появлением «дыр» внутри комплекса кластеров. Их количество измеряется числом Бетти-1, а персистентность – разностью уровней исчезновения и появления дыры. Мы показываем, как распределения персистентных чисел Бетти можно использовать для распознавания текстур на цифровых изображениях.
Ключевые слова: сегментация изображений, топологическая фильтрация, комплекс Чеха, персистентные числа Бетти, распознавание образов
Полный текстСписок литературы:
- Борхес Х.Л. Аналитический язык Джона Уилкинса. // Борхес Х. Л. Собрание сочинений. СПб.: Амфора, 2005. Т.2. C. 416-420.
- Винклер Г. Анализ изображений, случайные поля и динамические методы Монте-Карло. Математические основы: Пер. с англ. Новосибирск: СО РАН, филиал Тео, 2002. 343 с.
- Гренандер У. Лекции по теории образов. 3 Регулярные структуры. М.: Мир, 1983. 432 c.
- Макаренко Н.Г., Круглун О.А., Макаренко И.Н., Каримова Л.М. Мультифрактальная сегментация данных дистанционного зондирования // Исследование Земли из космоса. 2008. № 3. C. 18-26.
- Макаренко Н.Г., Каримова Л.М., Круглун О.А. Скейлинговые свойства цифровых изображений земных ландшафтов // Современные проблемы дистанционного зондирования Земли из космоса. 2014. Т. 11. № 2. С. 26-37.
- Макаренко Н.Г., Малкова Д.Б., Мячин М.Л., Князева И.С., Макаренко И.Н. Диагностика магнитной динамики активных областей Солнца методами вычислительной топологии // Фундаментальная и прикладная математика. 2013. Т. 18. № 2. С. 79-93.
- Фуко М. Слова и вещи. Археология гуманитарных наук: Пер. с фр. СПб.: А-cad, 1994. 408 с.
- Цопф Г. Отношение и контекст // Принципы самоорганизации. Пер.с англ. М.: Мир, 1966. C. 399-427.
- Bubenik P. Statistical topological data analysis using persistence landscapes // 2014, arXiv:1207.6437 [math.AT].
- Carlsson G. Topology and data // Bull. of the Amer. Mathem. Soc. 2009. Vol. 46(2), P. 255-308.
- Carlsson E., Carlsson G., Silva Vin De. An algebraic topological method for feature identification // Intern. J. of Computational Geometry & Applications 2006. Vol. 16 (04), P. 291-314.
- Edelsbrunner H., Harer J., Computational Topology, An Introduction. American Mathematical Society. 2009. 241 p.
- Edelsbrunner H., Morozov. D. Persistent Homology: Theory and Practice // European Congress of Mathematics, Krakow, 2-7 July, 2012, Europ. Math. Soc. 2012. P. 31-50.
- Ester M., Kriegel H-P., Sander J., Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise // KDD-96 Proceedings. 1996. P.226-231.
- Geman S., Geman D. Stochastic relaxation, Gibbs distributions, and Bayesian restoration of images // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. PAMI-6.1984. No. 6. Р. 721-741.
- Ghrist R. Barcodes: The persistent topology of data // Bull. Amer. Math. Soc. 2008. Vol. 45(1) P. 61-75.
- Kaczynski T., Mischaikow K., Mrozek M. Computational Homology. Springer 2004. 482 p.
- Luxburg U. Von. A tutorial on spectral clustering // Stat. Comput. 2007. Vol. 17. P. 395–416.
- Li Stan Z. Markov Random Field Modeling in Image Analysis. Springer. 2009. 357 p.
- Mumford D., Shah J. Optimal approximation by piecewise smooth functions and associated variational problems // Comm. Pure Appl. Math. 1989. No. 42. P. 577–685.
- Robins V., Abernethy J., Rooney N., Bradley E. Topology and Intelligent Data Analysis // Journ. Intelligent Data Analysis. 2004. Vol.8. No 5. P. 505 - 515
- Rui Xu R., Wunsch II D. Survey of Clustering Algorithms. // IEEE Trans. on Neural Networks. 2005. Vol.16. No. 3. P. 645-678.
- Shen J. A Stochastic -variational model for soft Munford –Shah segmentation // Intern. J. of Biomedical Imaging. 2006. Vol. 2006. Article ID 92329. P. 1–14.
- Selfridge O.G. Pandemonium: A Paradigm for Learning // Mechanisation of Thought Processes. National Phys. Labor. Symp. No. 10. London: Her Majestry’s Stationery office. 1959. P.513-530.
- Serra J. Image Analysis and Mathematical Morphology. New-York: Academic Press. 1982. 610 p.
- Zomorodian A.J. Topology for computing. Cambridge Univ. Press. 2005. 243 p.