Автоматизированная система колоризации полутонового изображения
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?седние точки, удовлетворяющие некоторому критерию. Процесс выращивания регионов (regiongrowing) останавливается, когда ни одна точка изображения не может быть присоединена ни к одному региону [5].
Применяются разные критерии, на основании которых точка присоединяется или не присоединяется к региону: близость (в некотором смысле) точки к центру региона; близость к соседней точке, присоединенной к региону на предыдущем шаге; близость по некоторой статистике региона; стоимость кратчайшего пути от точки до центра региона, и т. п.
В основном процедура выращивания региона используется для получения отдельных регионов, однако, применяя эту процедуру последовательно или одновременно для нескольких регионов, можно получить разбиение всего изображения. Существуют различные стратегии выбора зерен (seeds) и выращивания регионов. Методы дробления-слияния состоят из двух основных этапов: дробления и слияния. Дробление начинается с некоторого разбиения изображения, не обязательно на однородные области. Процесс дробления областей происходит до тех пор, пока не будет получено разбиение изображения (пересегментация), удовлетворяющее свойству однородности сегментов. Затем происходит объединение схожих соседних сегментов до тех пор, пока не будет получено разбиение изображения на однородные области максимального размера [5]. Конкретные методы различаются алгоритмами, используемыми на этапах дробления и слияния. Для получения пересегментации изображения используются алгоритмы k-средних, watershed, fuzzy expert systems, на втором этапе используются алгоритмы k-средних, самоорганизующиеся карты Кохонена, fuzzy expert systems, и т. д. На этапе слияния регионов используются relaxation process, k-средних, SIDE-уравнения, самоорганизующиеся карты Кохонена, и т. д. [5].
1.1.6 Методы, основанные на операторах выделения краев
При данном подходе задача сегментации формулируется как задача поиска границ регионов. Методы поиска границ хорошо разработаны для полутоновых изображений. Полутоновое изображение рассматривается как функция двух переменных (x и y), и предполагается, что границы регионов соответствуют максимумам градиента этой функции. Для их поиска применяется аппарат дифференциальной геометрии (в простейшем случае это фильтры Roberts, Kirsch, Prewitt, Sobel) [4].
Для повышения устойчивости к шуму, перед применением фильтрации изображение обычно размывают. Благодаря коммутативности оператора Гаусса (формула 1.1) и Лапласа (формула 1.2) фильтра, можно одновременно осуществлять размытие и поиск границ.
,(1.1)
где r - радиус размытия,
s - коэффициент размытия по Гауссу.
.(1.2)
В методе Canny комбинируются результаты поиска границ при разной степени размытия. Пример метода, основанного на операторах выделения краев, представлен на рисунке 1.2.
Рисунок 1.2 - Результат применения фильтра Canny
1.1.7 Методы теории графов
Методы теории графов - одно из наиболее активно развивающихся направлений в сегментации изображений.
Общая идея методов этой группы следующая. Изображение представляется в виде взвешенного графа, с вершинами в точках изображения. Вес ребра графа отражает сходство точек в некотором смысле (расстояние между точками по некоторой метрике). Разбиение изображения моделируется разрезами графа (рисунок 1.3) [5].
Рисунки 1.3 - Пример моделирования изображения взвешенным графом.
Обычно в методах теории графов вводится функционал стоимости разреза, отражающий качество полученной сегментации. Так задача разбиения изображения на однородные области сводится к оптимизационной задаче поиска разреза минимальной стоимости на графе. Такой подход позволяет помимо однородности цвета и текстуры сегментов управлять также формой сегментов, их размером, сложностью границ и т. п.
Для поиска разреза минимальной стоимости применяются различные методы: жадные алгоритмы (на каждом шаге выбирается такое ребро, чтобы суммарная стоимость разреза была минимальной), методы динамического программирования (гарантируется, что, выбирая на каждом шаге оптимальное ребро, получим в итоге оптимальный путь), алгоритм Дейкстры, и т. п. Рассмотрим некоторые методы теории графов подробнее.
Метод сегментации SWA (Segmentation by Weighted Aggregation) основан на группировании схожих точек изображения. Основная идея метода состоит в построении пирамиды взвешенных графов, каждый из которых получен из предыдущего путем объединения схожих вершин [3].
На каждом шаге веса связей пересчитываются. В процессе построения пирамиды вычисляются различные статистики, характеризующие форму, цвет, текстуру регионов, эти статистики используются для вычисления меры сходства регионов (рисунок 1.4). Затем, следуя идеологии методов теории графов, для полученного графа вводится функционал стоимости разреза и ищется разрез минимальной стоимости. При этом в отличие от большинства методов теории графов, SWA имеет сложность O(n), где n - число точек изображения, причем число операций для каждой точки составляет всего несколько десятков.
Рисунок 1.4 - Построение пирамиды взвешенных графов для изображения
В модификации алгоритма на каждом следующем шаге анализируется и корректируется результат предыдущего агрегирования, а также используется информация о границах полученных сегментов (рисунок 1.5) [5].
Чтобы приблизиться к теме сегментации изображений, описание продолжим в терминологии пикселей изображения и их цвета. Допустим, мы с?/p>