Методы теории графов

Методы теории графов – одно из наиболее активно развивающеихся направлений в сегментации изображений.

Общая идея методов этой группы следующая. Изображение представляется в виде взвешенного графа, с вершинами в точках изображения. Вес ребра графа отражает сходство точек в некотором смысле (расстояние между точками по некоторой метрике). Разбиение изображения моделируется разрезами графа.

Рис. 4. Пример моделирования изображения взвешенным графом.

Обычно в методах теории графов вводится функционал «стоимости» разреза, отражающий качество полученной сегментации. Так задача разбиения изображения на однородные области сводится к оптимизационной задаче поиска разреза минимальной стоимости на графе. Такой подход позволяет помимо однородности цвета и текстуры сегментов управлять также формой сегментов, их размером, сложностью границ и т. п.

Для поиска разреза минимальной стоимости применяются различные методы: жадные алгоритмы (на каждом шаге выбирается такое ребро, чтобы суммарная стоимость разреза была минимальной), методы динамического программирования (гарантируется, что, выбирая на каждом шаге оптимальное ребро, получим в итоге оптимальный путь), алгоритм Дейкстры, и т. п. Рассмотрим некоторые методы теории графов подробнее.

Метод Normalized Cut предложен J. Shi, J. Malik (1997) [23]. Вводится нормализованный функционал качества разреза так, чтобы одновременно максимизировать различие точек между классами и минимизировать различия точек внутри класса. Оптимизация нормализованного функционала сводится к задаче поиска собственных значений матрицы попарных расстояний между всеми точками изображения. Для сегментации изображения на две части достаточно найти второе по величине собственное значение такой матрицы.

Рис. 5. Пример матрицы попарных расстояний для точечной конфигурации.

Сложность эффективного алгоритма поиска собственных значений разреженной матрицы линейна по числу точек изображения. Однако метод требует хранения матрицы размером n*n, где n – число точек изображения, и потому в исходном виде неприменим к большим изображениям.

Для данного метода предложены модификации [24, 25], позволяющие сократить сложность алгоритма и требования по памяти за счет аппроксимации матрицы расстояний. Такой подход дает выигрыш в скорости работы в 10-20 раз по сравнению с исходным методом.

Рис. 6. Результаты работы метода Normalized cuts

Метод Nested Cuts предложен Olga Veksler (2000) [26]. Основной принцип этого метода состоит в отделении каждой точки изображения от специальной точки за пределами изображения разрезом минимальной стоимости. При таком подходе изображение делится на непересекающиеся сегменты. Показано, что величиной сегментов изображения можно управлять, накладывая ограничения на стоимость разреза. В статье описывается эффективный алгоритм, основанный на свойствах разбиения. Однако этот метод работает крайне медленно.

Рис. 7. Результат работы Nested Cuts

M. Pavan и M. Pelillo (2003) был предложен новый подход, основанный на разрезах графа [27]. Авторы вводят такое определение сегмента, которое позволяет переформулировать задачу поиска разреза на графе как задачу квадратичного программирования. Предложен метод решения полученной задачи, основанный на методах эволюционной теории игр. Этот подход также требует хранения в памяти матрицы попарных расстояний, как и метод Normalized Cuts.

Рис. 8. Результаты работы метода

Метод сегментации SWA (Segmentation by Weighted Aggregation) основан на группировании схожих точек изображения [28, 29, 30] . Основная идея метода состоит в построении пирамиды взвешенных графов, каждый из которых получен из предыдущего путем объединения схожих вершин.

Рис. 9 Построение пирамиды взвешенных графов для изображения.

На каждом шаге веса связей пересчитываются. В процессе построения пирамиды вычисляются различные статистики, характеризующие форму, цвет, текстуру регионов, эти статистики используются для вычисления меры сходства регионов. Затем, следуя идеологии методов теории графов, для полученного графа вводится функционал стоимости разреза и ищется разрез минимальной стоимости. При этом, в отличие от большинства методов теории графов, SWA имеет сложность O(n), где n - число точек изображения, причем число операций для каждой точки составляет всего несколько десятков.

В модификации алгоритма [29] на каждом следующем шаге анализируется и корректируется результат предыдущего агрегирования, а также используется информация о границах полученных сегментов.

Рис. 10. Сравнение результатов работы алгоритма SWA [28], его модификации [29] и Normalized cuts

Качество работы методов теории графов сильно зависит от выбора метрики. Поэтому для выбора оптимальной метрики в [31, 32] применяют машинное обучение. Основные проблемы методов теории графов - это низкая скорость работы и большие затраты памяти. Большинство методов требует хранения в памяти матрицы попарных расстояний между точками изображения, размер которой равен квадрату числа точек. Такие ограничения делают графовые методы практически неприменимыми для больших изображений.