Методы вычислительной топологии для распознавания текстур.

В докладе обсуждается распознавание текстур цифровых изображений методами вычислительной топологии. Идея заключается в использовании логики признаков, основанной на топологической фильтрации. Такая фильтрация возникает согласно цепному правилу соединения точек в пространстве признаков. В простейшем варианте, две точки соединяются ребром, если расстояние между ними, в подходящей метрике, не превышает заданного малого числа. В алгебраической топологии цепная близость приводит к понятию нерва топологического покрытия точечного множества. Ради простоты, рассмотрим дискретный набор точек – признаков на плоскости. Декорируем каждую точку диском с центром в этой точке и переменным радиусом. Будем синхронно увеличивать радиусы дисков. Напомним, что структура состоящая из простейших элементов – вершин, ребер и треугольных граней называется симплициальным комплексом, если его смежные элементы пересекаются в точке, либо имеют общее ребро. Пусть пересечение двух дисков продуцирует ребро и три пересекающихся диска порождают грань. Полученное покрытие облака точек называют комплексом Чеха. Структура комплекса меняется с изменением радиусов диска: возникают и сливаются вместе новые компоненты. Появляются дыры (пустые области, ограниченные циклом из ребер), которые превращаются в грани. Алгебраическая структура комплексов описывается двумя группами гомологий. Ранг первой из них совпадает с числом отдельных компонент связности Бетти-нуль, для второй – числом дыр, Бетти один. Результатом фильтрации будет один связный объект с Бетти-нуль = 1. В процессе эволюции комплекса, время жизни компонент и дыр, измеряют в радиусах дисков, и называют их персистентностью. Тогда, структуру облака точек в пространстве признаков можно описывать используя диаграмму персистентности. Она отображает время жизни элемента комплекса двухмерным графиком, используя в качестве координат момент рождение элемента и его исчезновение, измеренные в радиусах дисков покрытия. Пусть, например, признаками является случайная выборка точек кольца. Тогда диаграмма будет содержать точки вдоль диагонали с малым временем жизни, и точку вдали от диагонали, соответствующую «дыре» в кольце.
Для цифрового изображения, упорядочим по уровню серого, пиксели изображения. Выберем в качестве основы, функцию высоты пиксела. Тогда, при санировании по высоте, каждый локальный минимум порождает компоненту связности. Она исчезает, когда соединится с другой компонентой цепочкой пикселей промежуточного уровня. Таким образом, при увеличении уровня, кластеры, порожденные первичными компонентами сливаются, уменьшая число Бетти-нуль. Ее персистентность, измеряется разностью двух уровней. Первый маркирует ее появление, второй – слияние с соседним кластером. Слияние отдельных компонент сопровождается появлением и исчезновением «дыр» внутри комплекса кластеров. Количество дыр измеряется числом Бетти-1, а их персистентность, разностью уровней исчезновения и появления дыры. Процесс заканчивается, когда получается один глобальный кластер. Мы показываем как распределения персистентных чисел Бетти по высоте можно использовать для распознавания текстур на цифровых изображениях.