Сегментацией изображения называется разбиение изображения на непохожие по некоторому признаку области. Предполагается, что области соответствуют реальным объектам, или их частям, а границы областей соответствуют границам объектов. Сегментация играет важную роль в задачах обработки изображений и компьютерного зрения.

Введение

Методы сегментации можно разделить на два класса: автоматические – не требующие взаимодействия с пользователем и интерактивные – использующие пользовательский ввод непосредственно в процессе работы. В данной статье рассматриваются только автоматические методы.

Задачи автоматической сегментации делятся на два класса:

• выделение областей изображения с известными свойствами
• разбиение изображения на однородные области

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

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

Автоматические методы

Сегментация как разбиение изображения на однородные области

Вначале рассмотрим постановку задачи сегментации, как разбиения изображения на однородные области. Такая постановка возникла раньше, чем задача выделения областей изображения с известными свойствами, и методы этой группы на данный момент хорошо разработаны.

Ясно, что задача разбиения изображения на однородные области поставлена некорректно. Внизу приведены четыре варианта сегментации одного и того же изображения из Berkeley Segmentation Dataset, выполненные разными людьми. Как видно, среди участников эксперимента нет единства в выборе разбиения изображения. Далеко не всегда для изображения есть единственно «правильная» сегментация, и далеко не всегда задача сегментации имеет единственное решение. По той же причине нет и объективного критерия оценки качества разбиения изображения.

Рис. 1. Варианты сегментации изображения

Оценка качества работы методов сегментации

Поскольку сегментация обычно используется не самостоятельно, а как часть некоторой системы (например, системы машинного зрения), то с практической точки зрения, качество работы метода оценивается исходя из работы системы в целом. Поэтому один и тот же метод сегментации может оказаться хорошим для одной задачи и плохим для другой.

Для грубой оценки качества метода в конкретной задаче обычно фиксируют несколько свойств, которыми должна обладать хорошая сегментация. Качество работы метода оценивается в зависимости от того, насколько полученная сегментация обладает этими свойствами. Наиболее часто используются следующие свойства [1]:

• однородность регионов (однородность цвета или текстуры)
• непохожесть соседних регионов
• гладкость границы региона
• маленькое количество мелких «дырок» внутри региона
• и т. д.

Разные методы сегментации ориентированы на разные свойства разбиения. Поэтому при выборе метода сегментации для решения конкретной задачи, следует определиться, какие свойства разбиения действительно важны. В некоторых прикладных задачах достаточно того, чтобы разбиение обладало лишь первыми двумя из перечисленных свойств.

Более общий подход к оценке качества работы метода, не учитывающий конкретного приложения, состоит в тестировании методов на общей базе изображений, для которых известна «правильная» сегментация. Например, Berkeley Segmentation Dataset (http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench), насчитывает более 1000 изображений, отсегментированных вручную 30 разными людьми. В [18] приводится описание базы изображений и предлагается численная мера соответствия полученной сегментации «правильной».

Кластеризация цветового пространства

В постановке задачи сегментации прослеживается аналогия с задачей кластеризации (или обучения без учителя). Для того чтобы свести задачу сегментации к задаче кластеризации, достаточно задать отображение точек изображения в некоторое пространство признаков и ввести метрику (меру близости) на этом пространстве признаков.

В качестве признаков точки изображения можно использовать представление ее цвета в некотором цветовом пространстве, примером метрики (меры близости) может быть евклидово расстояние между векторами в пространстве признаков. Тогда результатом кластеризации будет квантование цвета для изображения. Задав отображение в пространство признаков, можно воспользоваться любыми методами кластерного анализа. Наиболее популярные методы кластеризации, используемые для сегментации изображений – к-средних [35] (обобщенный метод Ллойда), EM алгоритм[5].

Основная проблема методов кластеризации, состоит в том, что пространственное расположение точек либо не учитывается совсем, либо учитывается косвенно (например, используя координаты точки как один из признаков). Поэтому обычно после кластеризации точек изображения проводят процедуру выделения связных компонент.

Методы кластеризации плохо работают на зашумленных изображениях: часто теряют отдельные точек регионов, образуется много мелких регионов, и. т. п.

Выращивание регионов, дробление-слияние

Методы этой группы учитывают пространственное расположение точек напрямую.

Методы выращивания регионов основаны на следующей идее. Сначала по некоторому правилу выбираются центры регионов (seeds), к которым поэтапно присоединяются соседние точки, удовлетворяющих некоторому критерию. Процесс выращивания регионов (region growing) останавливается, когда ни одна точка изображения не может быть присоединена ни к одному региону.

Применяются разные критерии, на основании которых точка присоединяется или не присоединяется к региону: близость (в некотором смысле) точки к центру региона; близость к соседней точке, присоединенной к региону на предыдущем шаге; близость по некоторой статистике региона; стоимость кратчайшего пути от точки до центра региона, и т. п.

В основном процедура выращивания региона используется для получения отдельных регионов, однако, применяя эту процедуру последовательно или одновременно для нескольких регионов, можно получить разбиение всего изображения. Существуют различные стратегии выбора зерен (seeds) и выращивания регионов [14, 15, 16, 17].

Методы дробления-слияния состоят из двух основных этапов: дробления и слияния.[4, 6] Дробление начинается с некоторого разбиения изображения, не обязательно на однородные области. Процесс дробления областей происходит до тех пор, пока не будет получено разбиение изображения (пересегментация), удовлетворяющее свойству однородности сегментов. Затем происходит объединение схожих соседних сегментов до тех пор, пока не будет получено разбиение изображения на однородные области максимального размера.

Конкретные методы различаются алгоритмами, используемыми на этапах дробления и слияния. Для получения пересегментации изображения используются алгоритмы k-средних [10], watershed [9, 12], fuzzy expert systems [13], на втором этапе используются алгоритмы k-средних [10], самоорганизующиеся карты Кохонена [11,6], fuzzy expert systems [16], и т. д. На этапе слияния регионов используются relaxation process[3], k-средних [10], SIDE-уравнения [14], самоорганизующиеся карты Кохонена [9],и т. д.

Моделирование изображения Марковским полем

Хорошей моделью изображения служит Марковское случайное поле [7, 8]. Данная модель основана на предположении, что цвет каждой точки изображения зависит от цветов некоторого множества соседних точек. Предложено также обобщение модели изображения также можно обобщить на текстурную сегментацию [7]. Данный подход является достаточно сложным в реализации, однако может являться наиболее адекватным в случае важности учёта текстуры при сегментации. Подробнее о Марковских полях можно прочитать в [7, 8].

Методы, основанные на операторах выделения краев

При данном подходе задача сегментации формулируется как задача поиска границ регионов. Методы поиска границ хорошо разработаны для полутоновых изображений. Полутоновое изображение рассматривается как функция двух переменных (x и y), и предполагается, что границы регионов соответствуют максимумам градиента этой функции. Для их поиска применяется аппарат дифференциальной геометрии (в простейшем случае это фильтры Roberts, Kirsch, Prewitt, Sobel).

Для повышения устойчивости к шуму, перед применением фильтрации изображение обычно размывают. Благодаря коммутативности оператора Лапласа и Гауссова фильтра, можно одновременно осуществлять размытие и поиск границ. В методе Canny комбинируются результаты поиска границ при разной степени размытия.

Рис. 2. Результат применения фильтра Canny

Другой подход основан на применении steerable filters [19], которые осуществляют дифференцирование по направлению. Для таких фильтров можно выбрать базис, через который выражается дифференцирование по любому направлению. Для поиска границ комбинируются результаты применения базисных фильтров.

Исходное изображение 1ый порядок 3ий порядок 5ый порядок

Рис. 3. Результат работы steerable filters с разными параметрами

В [22] предлагается комбинированный подход, использующий steerable filters и cellular neural networks.

Ясно, что выбор критерия для граничных точек определяет качество работы краевых методов. В [33] для выбора оптимального критерия граничных точек применяется машинное обучение.

Основной проблемой методов поиска границ является неустойчивость к шуму. Кроме того, поскольку понятие границы свое для каждой задачи, каждый раз при применении методов поиска границ требуется дополнительно выбирать метод доработки результатов фильтрации (edge linking, edge relaxation).

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

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

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

Рис. 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] применяют машинное обучение. Основные проблемы методов теории графов - это низкая скорость работы и большие затраты памяти. Большинство методов требует хранения в памяти матрицы попарных расстояний между точками изображения, размер которой равен квадрату числа точек. Такие ограничения делают графовые методы практически неприменимыми для больших изображений.

Оптимизационный подход

Задачу разбиения изображения на однородные области можно свести к задаче оптимизации. Для этого задачу сегментации формулируют как задачу поиска разбиения изображения, обладающего определенными свойствами, и затем вводится функционал, который отражает степень соответствия полученной сегментации предъявляемым требованиям. .Например, в графовых методах оптимизируется функционал стоимости разреза.

Примером оптимизационного метода являетя алгоритм JSEG [17]. Вводится функционал качества сегментации, использующий распределение цветов на изображении.

Рис. 11. Примеры разных цветовых карт (+, 0, * - различные цвета). Значения функционала: 1) J=1.72, 2) J=0, 3) J=0.855, 4) J=0.05, 5) J=0

Однако оптимизация этого функционала напрямую – очень трудоемкая задача. В методе JSEG используется жадный алгоритм оптимизации введенного функционала качества сегментации. Значение функционала качества вычисляется для окрестности каждой точки. Большие значения функционала качества соответствуют границам однородных областей, маленькие значения соответствуют центрам регионов. Затем применяется выращивание регионов, в качестве зерен используются точки с минимальными значениями функционала. На последнем этапе проводится слияние мелких регионов.

На рисунке внизу приведены результаты работы алгоритма JSEG на разных картинках и приведены значения функционала качества для исходной картинки и для полученного разбиения.

Рис. 12. Результаты работы JSEG.

Настройка параметров

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

В основе настройки параметров при помощи машинного обучения лежит следующий принцип: сначала производится настройка параметров метода сегментации на некоторой базе отсегментированных вручную изображений, и затем новые изображения сегментируются при помощи уже настроенного метода.

Например, в [20] предлагается метод настройки порога для бинаризации фотографий рукописных текстов. Метод обучается на наборе изображений, для каждого из которых вручную выбраны оптимальные значения порога.

Рис. 13 Изображение рукописного текста, бинаризованное изображение, полученное методом Бернсена и бинаризованное изображение, полученное описанным методом

Во многих работах при помощи машинного обучения настраиваются параметры метрики для графовых методов. В [31, 34] авторы графового метода Normalized Cut предложили вариант Normalized Cut с настраиваемой метрикой.

По набору размеченных фотографий (Berkley Segmentation dataset) составляется обучающая выборка для настройки метрики. В обучающую выборку входят пары точек с известной классификацией. К первому классу относятся пары точек, лежащие в одном регионе, второй класс составляют пары точек, лежащие в разных регионах. Причем, две точки изображения считаются лежащими в одном и том же регионе только, если они оказались в одном и том же регионе во всех вариантах сегментации данного изображения.

Затем, в соответствии с идеологией машинного обучения, задача сегментации изображения формулируется как задача построения классификатора по данной обучающей выборке. Далее для каждой пары точек из обучающей выборки вычисляется вектор признаков. В [31] в качестве признаков используются несколько простых метрик: текстурный градиент, энергия по направлению, градиент яркости, градиент цвета по прямой, соединяющей пару точек. Также используются метрики, учитывающие различия в распределении цвета и текстурных элементов в небольших окрестностях этих точек.

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

Оптимальная метрика строится по обучающей выборке как некоторая функция от простых метрик. В результате экспериментов с разными методами обучения оказалось, что результат практически не зависит от выбора метода [31], и определяется в основном выбором простых метрик.

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

Литература

1. R. M. Haralick, L. G. Shapiro, “Image Segmentation Techniques,” Computer Vision, Graphics, and Image Processing, Vol 29, No 1, 1985
2. K. S. Fu and J. k. Mui, “A Survey on Image Segmentation,” Pattern Recognition, Vol. 13, 1981
3. N. R. Pal and S. K. Pal, “A Review on Image Segmentation Techniques,” Pattern Recognition, Vol. 26, No 9, 1993
4. R. Jain, R. Kasturi, and B. G. Schunck, Machine Vision, 1995
5. L. Lucchese and S.K. Mitra “Color Image Segmentation: A State-of-the-Art Survey”, 2001
6. S.-T. Bow, Pattern Recognition and Image Preprocessing, Marcel Dekker, Inc., New York, NY, 1992.
7. G. R. Cross and A. K. Jain, “Markov Random Field Texture Models,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 1983
8. S. German and D. German, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 1984
9. H. Digabel and С. Lantujoul, “Iterative Algorithms,” Proc. of the 2nd European Symp. on Quantitative Analysis of Microstructures in Material Science, Biology and Medicine, 1977
10. M. Celenk, “Hierarchical Color Clustering for Segmentation of Textured Images,” Proc. of the 29th Southeastern Symposium on system Theory, 1997
11. S. Ji and H. W. Park, “Image Segmentation of Color Image Based on Region Coherency,” Proc. of ICIP’98
12. L. Shafarenko, M. Petrov, and J. Kittler, “Automatic Watershed segmentation of Randomly Textured Color Images,” IEEE Trans. on Image Processing, 1997
13. M. Barni, S. Rossi, and A. Mecocci, “A Fuzzy Expert System for Low Level Image Segmentation,” EUSIPCO-96
14. A. Tremeau and n. Borel, “A Region growing and Merging Algorithm to color segmentation,” Pattern Recognition, 1997
15. Y. Kanai, “Image Segmentation Using Intensity and Color Information,” SPIE –Visual Communications and Image Processing’98
16. B. Cramariuc, M. Gabbouj, and J. Astola, “Clustering Based Region Growing Algorithm for Color Imag Segmentation,” Int. Conf. on Digital signal Processing, 1997
17. Y. Deng, B. S. Manjunath, and H, Shin, “Color Image Segmentation”, CVPR 1999
18. A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics David Martin Charless Fowlkes Doron Tal Jitendra Malik Department of Electrical Engineering and Computer Sciences
19. M. Jacob, M. Unser, "Design of Steerable Filters for Feature Detection Using Canny-Like Criteria," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 1007-1019
20. Image Segmentation By Learning Approach Horacio Andrés Legal-Ayala, Jacques Facon, 2003
21. Bayesian learning, global competition and unsupervised image Segmentation Guodong Guo and Songde Ma
22. Edge Detection Using steerable Filters and CNN, Atilla Ozmen and Emir Tufan Akman, 2002
23. Normalized Cuts and Image Segmentation - J. Shi, J. Malik (1997) University of California at Berkeley
24. Efficient Spatiotemporal Grouping Using the Nystrom Method (CVPR 2001) -Charless Fowlkes , Serge Belongie, Jitendra Malik
25. Efficient Graph Cuts for Unsupervised Image Segmentation using Probabilistic Sampling and SVD-based Approximation (ICCV 2003) - J. Keuchel, C.Schnorr, University of Mannheim, Germany
26. Image Segmentation by Nested Cuts (2000) - Olga Veksler, NEC Research Institute
27. A New Graph-Theoretic Approach to Clustering and Segmentation (CVPR03)
28. Fast Multiscale Image Segmentation (CVPR 2000) - Eitan Sharon, Achi Brandt Ronen Basriy, Dept. of Applied MathThe Weizmann Inst. of Science, Israel
29. Segmentation and Boundary Detection Using Multiscale Intensity Measurements (CVPR 2001) - Eitan Sharon, Achi Brandt_, Ronen Basri
30. Texture Segmentation by Multiscale Aggregation of Filter Responses and Shape Elements (ICCV 2003) - Meirav Galun, Eitan Sharon, Ronen Basri, Achi Brandt
31. Learning Affinity Functions for Image Segmentation: Combining Patch-based and Gradient-based Approaches, Charless Fowlkes, David Martin, Jitendra Malik, 2003
32. Boosting Margin Based Distance Functions for Clustering, Tomer Hertz, Aharon Bar-Hillel , 2004
33. Learning to Detect Natural Image Boundaries Using Brightness and Texture, Charless Fowlkes, David Martin, Jitendra Malik, 2003
34. How Much Does Globalization Help Segmentation, Charless Fowlkes and Jitendra Malik, 2003
35. Bishop, C. M. Neural Networks for Pattern Recognition. Oxford, England: Oxford University Press, 1995