Одной из главных целей компьютерного зрения при обработке изображений является интерпретация содержимого на изображении. Для этого необходимо качественно отделить фон от объектов. Сегментация разделяет изображение на составляющие части или объекты. Она отделяет объект от фона, чтобы можно было легко обрабатывать изображения и идентифицировать его содержимое. В данном случае выделение контуров на изображении является фундаментальным средством для качественной сегментации изображения. В данной статье предпринята попытка изучить производительность часто используемых алгоритмов выделения контуров для дальнейшей сегментации изображения, а также их сравнение при помощи программного средства MATLAB.
Введение
Сегментация изображений — огромный шаг для анализа изображений. Она разделяет изображение на составляющие части или объекты. Уровень детализации разделяемых областей зависит от решаемой задачи. К примеру, когда интересуемые объекты перестают сохранять целостность, разбиваются на более мелкие, составные части, процесс сегментации стоит прекратить. Алгоритмы сегментации изображений чаще всего базируются на разрыве и подобии значений на изображении. Подход разрывов яркости базируется на основе резких изменений значений интенсивности, подобие же — на разделение изображения на области, подобные согласно ряду заранее определенных критериев. Таким образом, выбор алгоритма сегментации изображения напрямую зависит от проблемы, которую необходимо решить. Обнаружение границ является частью сегментации изображений. Следовательно, эффективность решения многих задач обработки изображений и компьютерного зрения зависит от качества выделенных границ. Выделение их на изображении можно причислить к алгоритмам сегментации, которые базируются на разрывах яркости.
Процесс обнаружения точных разрывов яркости на изображении называется процессом выделение границ. Разрывы — это резкие изменения в группе пикселей, которые являются границами объектов. Классический алгоритм обнаружения границ задействует свертку изображения с помощью оператора, который основывается на чувствительности к большим перепадам яркости на изображении, а при проходе однородных участков возвращает нуль. Сейчас доступно огромное количество алгоритмов выделения контуров, но ни один из них не является универсальным. Каждый из существующих алгоритмов решает свой класс задач (т.е. качественно выделяет границы определенного типа). Для определения подходящего алгоритма выделения контуров необходимо учитывать такие параметры, как ориентация и структура контура, а также наличие и тип шума на изображении. Геометрия оператора устанавливает характерное направление, в котором он наиболее чувствителен к границам. Существующие операторы предназначены для поиска вертикальных, горизонтальных или диагональных границ. Выделение границ объектов — сложная задача в случае сильно зашумленного изображения, так как оператор чувствителен к перепадам яркости, и, следовательно, шум также будет считать некоторым объектом на изображении. Есть алгоритмы, позволяющие в значительной мере избавиться от шума, но в свою очередь, они в значительной мере повреждают границы изображения, искажая их. А так как большинство обрабатываемых изображений содержат в себе шум, шумоподавляющие алгоритмы пользуются большой популярностью, но это сказывается на качестве выделенных контуров.
Также при обнаружении контуров объектов существуют такие проблемы, как нахождение ложных контуров, расположение контуров, пропуск истинных контуров, помехи в виде шума, высокие затраты времени на вычисление и др. Следовательно, цель заключается в том, чтобы исследовать и сравнить множество обработанных изображений и проанализировать качество работы алгоритмов в различных условиях.
В данной статье предпринята попытка сделать обзор наиболее популярных алгоритмов выделения контуров для сегментации, а также реализация их в программной среде MATLAB. Второй раздел вводит фундаментальные определения, которые используются в литературе. Третий — предоставляет теоретический и математический и объясняет различные компьютерные подходы к выделению контуров. Раздел четыре предоставляет сравнительный анализ различных алгоритмов, сопровождая его изображениями. Пятый раздел содержит обзор полученных результатов и заключение.
Сегментация изображений
Сегментация изображения — это процесс разделения цифрового изображения на множество областей или наборов пикселей. Фактически, это разделение на различные объекты, которые имеют одинаковую текстуру или цвет. Результатом сегментации является набор областей, покрывающих вместе все изображение, и набор контуров, извлеченных из изображения. Все пиксели из одной области подобны по некоторым характеристикам, таким как цвет, текстура или интенсивность. Смежные области отличаются друг от друга этими же характеристиками. Различные подходы нахождения границ между областями базируются на неоднородностях уровней интенсивности яркости. Таки образом выбор метода сегментации изображения зависит от проблемы, которую необходимо решить.
Методы, основанные на областях, базируются на непрерывности. Данные алгоритмы делят все изображение на подобласти в зависимости от некоторых правил, к примеру, все пиксели данной группы должны иметь определенное значение серого цвета. Эти алгоритмы полагаются на общие шаблоны интенсивности значений в кластерах соседних пикселей.
Пороговая сегментация является простейшим видом сегментации. На ее основе области могут быть классифицированы по базовому диапазону значений, которые зависят от интенсивности пикселей изображения. Пороговая обработка преобразовывает входное изображение в бинарное.
Методы сегментации, основанные на обнаружении областей, находят непосредственно резкие изменения значений интенсивности. Такие методы называются граничными методами. Обнаружение границ — фундаментальная проблема при анализе изображений. Техники выделения границ обычно используются для нахождения неоднородностей на полутоновом изображении. Обнаружение разрывов на полутоном изображении — наиболее важный подход при выделении границ.
Алгоритмы выделение границ
Границы объектов на изображении в значительной степени уменьшают количество данных, которые необходимо обработать, и в то же время сохраняет важную информацию об объектах на изображении, их форму, размер, количество. Главной особенностью техники обнаружения границ является возможность извлечь точную линию с хорошей ориентацией. В литературе описано множество алгоритмов, которые позволяют обнаруживать границы объектов, но нигде нет описания того, как оценивать результаты обработки. Результаты оцениваются сугубо индивидуально и зависят от области их применения.
Обнаружение границ — фундаментальный инструмент для сегментации изображения. Такие алгоритмы преобразуют входное изображение в изображение с контурами объектов, преимущественно в серых тонах. В обработке изображений, особенно в системах компьютерного зрения, с помощью выделения контура рассматривают важные изменения уровня яркости на изображении, физические и геометрические параметры объекта на сцене. Это фундаментальный процесс, который обрисовывает в общих чертах объекты, получая тем самым некоторые знания об изображении. Обнаружение границ является самым популярным подходом для обнаружения значительных неоднородностей.
Граница является местным изменением яркости на изображении. Они, как правило, проходят по краю между двумя областями. С помощью границ можно получить базовые знания об изображении. Функции их получения используются передовыми алгоритмами компьютерного зрения и таких областях, как медицинская обработка изображений, биометрия и тому подобные. Обнаружение границ — активная область исследований, так как он облегчает высокоуровневый анализ изображений. На полутоновых изображениях существует три вида разрывов: точка, линия и граница. Для обнаружения всех трех видов неоднородностей могут быть использованы пространственные маски.
В технической литературе приведено и описано большое количество алгоритмов выделения контуров и границ. В данной работе рассмотрены наиболее популярные методы. К ним относятся: оператор Робертса, Собеля, Превитта, Кирша, Робинсона, алгоритм Канни и LoG-алгоритм.
Оператор Робертса
Оператор выделения границ Робертса введен Лоуренсом Робертсом в 1964 году. Он выполняет простые и быстрые вычисления двумерного пространственного измерения на изображении. Этот метод подчеркивает области высокой пространственной частоты, которые зачастую соответствуют краям. На вход оператора подается полутоновое изображение. Значение пикселей выходного изображения в каждой точке предполагает некую величину пространственного градиента входного изображения в этой же точке.
Оператор Собеля
Оператор Собеля введен Собелем в 1970 году. Данный метод обнаружения границ использует приближение к производной. Это позволяет обнаруживать край в тех местах, где градиент самый высокий. Данный способ обнаруживает количество градиентов на изображении, тем самым выделяя области с высокой пространственной частотой, которые соответствуют границам. В целом это привело к нахождению предполагаемой абсолютной величине градиента в каждой точке входного изображения. Данный оператор состоит из двух матриц, размером 3×3. Вторая матрица отличается от первой только тем, что повернута на 90 градусов. Это очень похоже на оператор Робертса.
Обнаружение границ данным методом вычислительно гораздо проще, чем методом Собеля, но приводит к большей зашумленности результирующего изображения.
Оператор Превитта
Обнаружение границ данным оператором предложено Превиттом в 1970 году. Правильным направлением в данном алгоритме была оценка величины и ориентация границы. Даже при том, что выделение границ является весьма трудоемкой задачей, такой подход дает весьма неплохие результаты. Данный алгоритм базируется на использовании масок размером 3 на 3, которые учитывают 8 возможных направлений, но прямые направления дают наилучшие результаты. Все маски свертки рассчитаны.
Оператор Кирша
Обнаружение границ этим методом было введено Киршем в 1971 году. Алгоритм основан на использовании всего одной маски, которую вращают по восьми главным направлениям: север, северо-запад, запад, юго-запад, юг, юго-восток, восток и северо-восток. Маски имеют следующий вид:
Величина границы определена как максимальное значение, найденное с помощью маски. Определенное маской направление выдает максимальную величину. Например, маска k 0 соответствует вертикальной границе, а маска k 5 — диагональной. Можно также заметить, что последние четыре маски фактически такие же, как и первые, они являются зеркальным отражением относительно центральной оси матрицы.
Оператор Робинсона
Метод Робинсона, введенное в 1977, подобен методу Кирша, но является более простым в реализации в силу использования коэффициентов 0, 1 и 2. Маски данного оператора симметричны относительно центральной оси, заполненной нулями. Достаточно получить результат от обработки первых четырех масок, остальные же можно получить, инвертируя первые.
Максимальное значение, полученное после применения всех четырех масок к пикселю и его окружению считается величиной градиента, а угол градиента можно аппроксимировать как угол линий нулей в маске, которые дают максимальный отклик.
Выделение контура методом Marr-Hildreth
Marr-Hildreth (1980) метод — метод обнаружения границ в цифровых изображениях, который обнаруживает непрерывные кривые везде, где заметны быстрые и резкие изменения яркости группы пикселей. Это довольно простой метод, работает он с помощью свертки изображения с LoG-функцией или как быстрая аппроксимация с DoG. Нули в обработанном результате соответствуют контурам. Алгоритм граничного детектора состоит из следующих шагов:
- размытие изображение методом Гаусса;
- применение оператора Лапласса к размытому изображению (часто первые два шага объединены в один);
- производим цикл вычислений и в полученном результате смотрим на смену знака. Если знак изменился с отрицательного на положительный и значение изменения значения более, чем некоторый заданный порог, то определить эту точку, как границу;
- Для получения лучших результатов шаг с использованием оператора Лапласса можно выполнить через гистерезис так, как это реализовано в алгоритме Канни.
Выделение контура методом LoG
Алгоритм выделения контуров Лаплассиан Гауссиана был предложен в 1982 году. Данный алгоритм является второй производной, определенной как:
Он осуществляется в два шага. На первом шаге он сглаживает изображение, а затем вычисляет функцию Лапласса, что приводит к образованию двойных контуров. Определение контуров сводится к нахождению нулей на пересечении двойных границ. Компьютерная реализация функции Лапласса обычно осуществляется через следующую маску:
Лаплассиан обычно использует нахождение пикселя на темной или светлой стороне границы.
Детектор границ Канни
Детектор границ Канни является одной из самых популярных алгоритмов обнаружения контуров. Впервые он был предложен Джоном Канни в магистерской диссертации в 1983 году, и до сих пор является лучше многих алгоритмов, разработанных позднее. Важным шагом в данном алгоритме является устранение шума на контурах, который в значительной мере может повлиять на результат, при этом необходимо максимально сохранить границы. Для этого необходим тщательный подбор порогового значения при обработке данным методом.
Алгоритм:
- размытие исходного изображения f(r, c) с помощью функции Гаусса f^(r, c). f^(r, c)=f(r,c)*G(r,c,6);
- выполнить поиск градиента. Границы намечаются там, где градиент принимает максимальное значение;
- подавление не-максимумов. Только локальные максимумы отмечаются как границы;
- итоговые границы определяются путем подавления всех краев, не связанных с определенными границами.
В отличии от операторов Робертса и Собеля, алгоритм Канни не очень восприимчив к шуму на изображении.
Экспериментальные результаты
В данном разделе представлены результаты работы описанных ранее алгоритмов обнаружения границ объектов на изображении.
Все описанные алгоритмы были реализованы в программной среде MATLAB R2009a и протестированы на фотографии университета. Цель эксперимента заключается в получении обработанного изображения с идеально выделенными контурами. Оригинальное изображение и результаты его обработки представлены на рисунке 1.
Рисунок 1 — Оригинальное изображение и результат работы различных алгоритмов выдеоения контуров
При анализе полученных результатов были выявлены следующие закономерности: операторы Робертса, Собеля и Превитта дают очень различные результаты. Marr-Hildreth, LoG и Канни практически одинаково обнаружили контуры объекта, Кирш и Робинсон дали такой же результат. Но наблюдая полученные результаты можно сделать вывод, что алгоритм Канни справляется на порядок лучше других.
Выводы
Обработка изображений — быстро развивающаяся область в дисциплине компьютерного зрения. Ее рост основывается на высоких достижениях в цифровой обработке изображений, развитию компьютерных процессоров и устройств хранения информации.
В данной статье была предпринята попытка изучить на практике методы выделения контуров объектов, основанных на разрывах яркости полутонового изображения. Исследование относительной производительности каждого из приведенных в данной статье методов осуществлялся с помощью программного средства MATLAB. Анализ результатов обработки изображения показал, что такие методы, как Marr-Hildreth, LoG и Канни дают практически одинаковые результаты. Но все же при обработке данного тестового изображения наилучшие результаты можно наблюдать после работы алгоритма Канни, хотя при других условиях лучшим может оказаться другой метод.
Даже учитывая тот факт, что вопрос обнаружения границ на изображении достаточно хорошо осветлен в современной технической литературе, он все же до сих пор остается достаточно трудоемкой задачей, так как качественное выделение границ всегда зависит от множества влияющих на результат факторов.
Список использованной литературы
1. Canny J.F. (1983) Finding edges and lines in images, Master"s thesis, MIT. AI Lab. TR-720.
2. Canny J.F. (1986) A computational approach to edge detection , IEEE Transaction on Pattern Analysis and Machine Intelligence, 8. — P. 679-714.
3. Courtney P, Thacker N.A. (2001) Performance Characterization in Computer Vision: The Role of Statistics in Testing and Design , Chapter in: Imaging and Vision Systems: Theory, Assessment and Applications , Jacques Blanc-Talon and Dan Popescu (Eds.), NOVA Science Books.
4. Hanzi Wang (2004) Robust Statistics for Computer Vision: Model Fitting, Image Segmentation and Visual Motion Analysis, Ph.D thesis, Monash University, Australia.
5. Huber P.J. (1981) Robust Statistics, Wiley New York.
6. Kirsch R. (1971) Computer determination of the constituent structure of biological images , Computers and Biomedical Research, 4. — P. 315–328.
7. Lakshmi S, Sankaranarayanan V. (2010) A Study of edge detection techniques for segmentation computing approaches , Computer Aided Soft Computing Techniques for Imaging and Biomedical Applications. — P. 35-41.
8. Lee K., Meer P. (1998) Robust Adaptive Segmentation of Range Images , IEEE Trans. Pattern Analysis and Machine Intelligence, 20(2). — P. 200-205.
9. Marr D, Hildreth E. (1980) Theory of edge detection , Proc. Royal Society of London, B, 207. — P. 187–217.
10. Marr D. (1982) Vision, Freeman Publishers.
11. Marr P., Doron Mintz. (1991) Robust Regression for Computer Vision: A Review , International Journal of Computer Vision, 6(1). — P. 59-70.
12. Orlando J. Tobias, Rui Seara (2002) Image Segmentation by Histogram Thresholding Using Fuzzy Sets , IEEE Transactions on Image Processing, Vol.11, No.12. — P. 1457-1465.
13. Punam Thakare (2011) A Study of Image Segmentation and Edge Detection Techniques , International Journal on Computer Science and Engineering, Vol 3, No.2. — P. 899-904.
14. Rafael C., Gonzalez, Richard E. Woods, Steven L. Eddins (2004) Digital Image Processing Using MATLAB, Pearson Education Ptd. Ltd, Singapore.
15. Ramadevi Y. (2010) Segmentation and object recognition using edge detection techniques , International Journal of Computer Science and Information Technology, Vol 2, No.6. — P. 153-161.
16. Roberts L. (1965) Machine Perception of 3-D Solids , Optical and Electro-optical Information Processing, MIT Press.
17. Robinson G. (1977) Edge detection by compass gradient masks , Computer graphics and image processing, 6. — P. 492-501.
18. Rousseeuw P. J., Leroy A. (1987) Robust Regression and outlier detection, John Wiley & Sons, New York.
19. Senthilkumaran N., Rajesh R. (2009) Edge Detection Techniques for Image Segmentation — A Survey of Soft Computing Approaches , International Journal of Recent Trends in Engineering, Vol. 1, No. 2. — P. 250-254.
20. Sowmya B., Sheelarani B. (2009) Colour Image Segmentation Using Soft Computing Techniques , International Journal of Soft Computing Applications, Issue 4. — P. 69-80.
21. Umesh Sehgal (2011) Edge detection techniques in digital image processing using Fuzzy Logic , International Journal of Research in IT and Management, Vol.1, Issue 3. — P. 61-66.
22. Yu, X, Bui, T.D. & et al. (1994) Robust Estimation for Range Image Segmentation and Reconstruction , IEEE trans. Pattern Analysis and Machine Intelligence, 16 (5). — P. 530-538.
Один из основных и простых способов - это построение сегментации с помощью порога. Порог - это признак (свойство), которое помогает разделить искомый сигнал на классы. Операция порогового разделения заключается в сопоставлении значения яркости каждого пикселя изображения с заданным значением порога.
Бинаризация
Операция порогового разделения, которая в результате дает бинарное изображение, называется бинаризацией. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение, имеющее некое количество уровней яркости, преобразуется в черно-белое изображение, пиксели которого имеют только два значения – 0 и 1
Пороговая обработка изображения может проводиться разными способами.
Бинаризация с нижним порогом
Бинаризация с нижним порогомБинаризация с нижним порогом является наиболее простой операцией, в которой используется только одно значение порога:
Все значения вместо критерия становятся 1, в данном случае 255 (белый) и все значения(амплитуды) пикселей, которые больше порога t - 0 (черный).
Бинаризации с верхним порогом
Иногда можно использовать вариант первого метода, который дает негатив изображения, полученного в процессе бинаризации. Операция бинаризации с верхним порогом:
Бинаризация с двойным ограничением
Для выделения областей, в которых значения яркости пикселей может меняться в известном диапазоне, вводится бинаризация с двойным ограничением (t 1 
Так же возможны другие вариации с порогами, где пропускается только часть данных (средне полосовой фильтр).
Неполная пороговая обработка
Данное преобразование дает изображение, которое может быть проще для дальнейшего анализа, поскольку оно становится лишенным фона со всеми деталями, присутствующими на исходном изображении.
Многоуровневое пороговое преобразование
Данная операция формирует изображение, не являющееся бинарным, но состоящее из сегментов с различной яркостью.
Что касается бинаризации, то по сути все. Хотя можно добавить, что есть глобальная, которая используется для всего изображения и так же существует локальная, которая захватывает часть картинки (изображения).
Локальная пороговая обработка
Метод ОтсаМетод использует гистограмму распределения значений яркости пикселей растрового изображения. Строится гистограмма по значениям p i =n i /N, где N – это общее кол-во пикселей на изображении, n i – это кол-во пикселей с уровнем яркости i. Диапазон яркостей делится на два класса с помощью порогового значения уровня яркости k,k - целое значение от 0 до L. Каждому классу соответствуют относительные частоты ω 0 ω 1:
Средние уровни для каждого из двух классов изображения:
Далее вычисляется максимальное значение оценки качества разделения изображения на две части:
где (σ кл)2=ω 0 ω 1 (μ 1 -μ 0) 2 , – межклассовая дисперсия, а (σ общ) 2 – это общая дисперсия для всего изображения целиком.
Определение порога на основе градиента яркости изображения
Предположим, что анализируемое изображение можно разделить на два класса – объекты и фон. Алгоритм вычисления порогового значения состоит из следующих 2 шагов:
1. Определяется модуль градиента яркости для каждого пикселя
изображения
2. Вычисление порога:
Итого
Что нашел с радостью выложил вам, в дальнейшем, если получится и будет время, постараюсь реализовать часть алгоритмов. Это лишь малая часть всего, что сегодня существует, но я рад поделится и этим.Спасибо за внимание.
Этим летом мне посчастливилось попасть на летнюю стажировку в компанию Itseez
. Мне было предложено исследовать современные методы, которые позволили бы выделить местоположения объектов на изображении. В основном такие методы опираются на сегментацию, поэтому я начала свою работу со знакомства с этой областью компьютерного зрения.
Сегментация изображения
- это разбиение изображения на множество покрывающих его областей. Сегментация применяется во многих областях, например, в производстве для индикации дефектов при сборке деталей, в медицине для первичной обработки снимков, также для составления карт местности по снимкам со спутников. Для тех, кому интересно разобраться, как работают такие алгоритмы, добро пожаловать под кат. Мы рассмотрим несколько методов из библиотеки компьютерного зрения OpenCV
.
Алгоритм сегментации по водоразделам (WaterShed)
Алгоритм работает с изображением как с функцией от двух переменных f=I(x,y) , где x,y – координаты пикселя:
Значением функции может быть интенсивность или модуль градиента. Для наибольшего контраста можно взять градиент от изображения. Если по оси OZ откладывать абсолютное значение градиента, то в местах перепада интенсивности образуются хребты, а в однородных регионах – равнины. После нахождения минимумов функции f , идет процесс заполнения “водой”, который начинается с глобального минимума. Как только уровень воды достигает значения очередного локального минимума, начинается его заполнение водой. Когда два региона начинают сливаться, строится перегородка, чтобы предотвратить объединение областей . Вода продолжит подниматься до тех пор, пока регионы не будут отделяться только искусственно построенными перегородками (рис.1).
Рис.1. Иллюстрация процесса заполнения водой
Такой алгоритм может быть полезным, если на изображении небольшое число локальных минимумов, в случае же их большого количества возникает избыточное разбиение на сегменты. Например, если непосредственно применить алгоритм к рис. 2, получим много мелких деталей рис. 3.
Рис. 2. Исходное изображение
Рис. 3. Изображение после сегментации алгоритмом WaterShed
Как справиться с мелкими деталями?
Чтобы избавиться от избытка мелких деталей, можно задать области, которые будут привязаны к ближайшим минимумам. Перегородка будет строиться только в том случае, если происходит объединение двух регионов с маркерами, в противном случае будет происходить слияние этих сегментов. Такой подход убирает эффект избыточной сегментации, но требует предварительной обработки изображения для выделения маркеров, которые можно обозначить интерактивно на изображении рис. 4, 5.
Рис. 4. Изображение с маркерами
Рис. 5. Изображение после сегментации алгоритмом WaterShed
с использованием маркеров
Если требуется действовать автоматически без вмешательства пользователя, то можно использовать, например, функцию findContours() для выделения маркеров, но тут тоже для лучшей сегментации мелкие контуры следует исключить рис. 6., например, убирая их по порогу по длине контура. Или перед выделением контуров использовать эрозию с дилатацией, чтобы убрать мелкие детали.
Рис. 6. В качестве маркеров использовались контуры, имеющие длину выше определенного порога
В результате работы алгоритма мы получаем маску с сегментированным изображением, где пиксели одного сегмента помечены одинаковой меткой и образуют связную область. Основным недостатком данного алгоритма является использование процедуры предварительной обработки для картинок с большим количеством локальных минимумов (изображения со сложной текстурой и с обилием различных цветов).
Mat image = imread("coins.jpg", CV_LOAD_IMAGE_COLOR);
// выделим контуры
Mat imageGray, imageBin;
cvtColor(image, imageGray, CV_BGR2GRAY);
threshold(imageGray, imageBin, 100, 255, THRESH_BINARY);
std::vector
Алгоритм сегментации MeanShift
MeanShift группирует объекты с близкими признаками. Пиксели со схожими признаками объединяются в один сегмент, на выходе получаем изображение с однородными областями.
Например, в качестве координат в пространстве признаков можно выбрать координаты пикселя (x, y) и компоненты RGB пикселя. Изобразив пиксели в пространстве признаков, можно заметить сгущения в определенных местах.
Рис. 7. (a) Пиксели в двухмерном пространстве признаков. (b) Пиксели, пришедшие в один локальный максимум, окрашены в один цвет. (с) - функция плотности, максимумы соответствуют местам наибольшей концентрации пикселей. Рисунок взят из статьи .
Чтобы легче было описывать сгущения точек, вводится функция плотности
: 
– вектор признаков i
-ого пикселя, d
- количество признаков, N
- число пикселей, h
- параметр, отвечающий за гладкость, - ядро. Максимумы функции расположены в точках сгущения пикселей изображения в пространстве признаков. Пиксели, принадлежащие одному локальному максимуму, объединяются в один сегмент. Получается, чтобы найти к какому из центров сгущения относится пиксель, надо шагать по градиенту для нахождения ближайшего локального максимума.
Оценка градиента от функции плотности
Для оценки градиента функции плотности можно использовать вектор среднего сдвига 
В качестве ядра в OpenCV используется ядро Епанечникова :
- это объем d
-мерной сферы c единичным радиусом.
означает, что сумма идет не по всем пикселям, а только по тем, которые попали в сферу радиусом h
с центром в точке, куда указывает вектор в пространстве признаков . Это вводится специально, чтобы уменьшить количество вычислений. - объем d
-мерной сферы с радиусом h, Можно отдельно задавать радиус для пространственных координат и отдельно радиус в пространстве цветов. - число пикселей, попавших в сферу. Величину 
можно рассматривать как оценку значения в области .
Поэтому, чтобы шагать по градиенту, достаточно вычислить значение - вектора среднего сдвига. Следует помнить, что при выборе другого ядра вектор среднего сдвига будет выглядеть иначе.
При выборе в качестве признаков координат пикселей и интенсивностей по цветам в один сегмент будут объединяться пиксели с близкими цветами и расположенные недалеко друг от друга. Соответственно, если выбрать другой вектор признаков, то объединение пикселей в сегменты уже будет идти по нему. Например, если убрать из признаков координаты, то небо и озеро будут считаться одним сегментом, так как пиксели этих объектов в пространстве признаков попали бы в один локальный максимум.
Если объект, который хотим выделить, состоит из областей, сильно различающихся по цвету, то MeanShift не сможет объединить эти регионы в один, и наш объект будет состоять из нескольких сегментов. Но зато хорошо справиться с однородным по цвету предметом на пестром фоне. Ещё MeanShift используют при реализации алгоритма слежения за движущимися объектами .
Пример кода для запуска алгоритма:
Mat image = imread("strawberry.jpg", CV_LOAD_IMAGE_COLOR);
Mat imageSegment;
int spatialRadius = 35;
int colorRadius = 60;
int pyramidLevels = 3;
pyrMeanShiftFiltering(image, imageSegment, spatialRadius, colorRadius, pyramidLevels);
imshow("MeanShift", imageSegment);
waitKey(0);
Результат:
Рис. 8. Исходное изображение
Рис. 9. После сегментации алгоритмом MeanShift
Алгоритм сегментации FloodFill
С помощью FloodFill (заливка или метод «наводнения») можно выделить однородные по цвету регионы. Для этого нужно выбрать начальный пиксель и задать интервал изменения цвета соседних пикселей относительно исходного. Интервал может быть и несимметричным. Алгоритм будет объединять пиксели в один сегмент (заливая их одним цветом), если они попадают в указанный диапазон. На выходе будет сегмент, залитый определенным цветом, и его площадь в пикселях.Такой алгоритм может быть полезен для заливки области со слабыми перепадами цвета однородным фоном. Одним из вариантов использования FloodFill
может быть выявление поврежденных краев объекта. Например, если, заливая однородные области определенным цветом, алгоритм заполнит и соседние регионы, то значит нарушена целостность границы между этими областями. Ниже на изображении можно заметить, что целостность границ заливаемых областей сохраняется:
Рис. 10, 11. Исходное изображение и результат после заливки нескольких областей
А на следующих картинках показан вариант работы FloodFill в случае повреждения одной из границ в предыдущем изображении.
Рис. 12, 13. Иллюстрация работы FloodFill
при нарушение целостности границы между заливаемыми областями
Пример кода для запуска алгоритма:
Mat image = imread("cherry.jpg", CV_LOAD_IMAGE_COLOR);
Point startPoint;
startPoint.x = image.cols / 2;
startPoint.y = image.rows / 2;
Scalar loDiff(20, 20, 255);
Scalar upDiff(5, 5, 255);
Scalar fillColor(0, 0, 255);
int neighbors = 8;
Rect domain;
int area = floodFill(image, startPoint, fillColor, &domain, loDiff, upDiff, neighbors);
rectangle(image, domain, Scalar(255, 0, 0));
imshow("floodFill segmentation", image);
waitKey(0);
В переменную area
запишется количество “залитых" пикселей.
Результат: 
Алгоритм сегментации GrabCut
Это интерактивный алгоритм выделения объекта, разрабатывался как более удобная альтернатива магнитному лассо (чтобы выделить объект, пользователю требовалось обвести его контур с помощью мыши). Для работы алгоритма достаточно заключить объект вместе с частью фона в прямоугольник (grab). Сегментирование объекта произойдет автоматически (cut).
Могут возникнуть сложности при сегментации, если внутри ограничивающего прямоугольника присутствуют цвета, которые встречаются в большом количестве не только в объекте, но и на фоне. В этом случае можно поставить дополнительные метки объекта (красная линия) и фона (синяя линия).
Рассмотрим идею алгоритма. За основу взят алгоритм интерактивной сегментации GraphCut, где пользователю надо поставить маркеры на фон и на объект. Изображение рассматривается как массив 
. Z
- значения интенсивности пикселей, N
-общее число пикселей. Для отделения объекта от фона алгоритм определяет значения элементов массива прозрачности , причем может принимать два значения, если = 0
, значит пиксель принадлежит фону, если= 1
, то объекту. Внутренний параметр содержит гистограмму распределения интенсивности переднего плана и гистограмму фона:
.
Задача сегментации - найти неизвестные . Рассматривается функция энергии:
Причем минимум энергии соответствует наилучшей сегментации.
V (a, z)
- слагаемое отвечает за связь между пикселями. Сумма идет по всем парам пикселей, которые являются соседями, dis(m,n)
- евклидово расстояние. 
отвечает за участие пар пикселей в сумме, если a n = a m
, то эта пара не будет учитываться. 
- отвечает за качество сегментации, т.е. разделение объекта от фона.
Найдя глобальный минимум функции энергии E , получим массив прозрачности . Для минимизации функции энергии, изображение описывается как граф и ищется минимальный разрез графа. В отличие от GraphCut в алгоритме GrabCut пиксели рассматриваются в RGB пространстве, поэтому для описания цветовой статистики используют смесь гауссиан (Gaussian Mixture Model - GMM). Работу алгоритма GrabCut можно посмотреть, запустив сэмпл OpenCV
обработка изображений: сегментация
Понятие сегментации, данное выше, является обобщенным понятием. Вообще говоря, изображение для наблюдателя часто представлено в виде некоторых однородных участков, отличающихся друг от друга различными характеристиками. Количество таких типов (или же классов) обычно невелико. Все изображение можно разбить на некоторое количество непересекающихся областей, каждая из которых является изображением одного из типов (классов). При анализе таких изображений целью любой системы является определение этих областей и указания их номера типа. Обработка изображения, позволяющая получить такую совокупность сведений о нем, и называется сегментацией . Иными словами, предполагается, что области изображения соответствуют реальным объектам или же их частям.
Однако существуют изображения, в которых вся картина разбита на области, не отличающиеся друг от друга ни по каким характеристикам. Тогда вся информация представляет в данном случае совокупность границ между этими областями. Простой пример: кирпичная или плиточная кладка.
Методы сегментации изображений делятся на два класса:
Автоматические, то есть такие методы, которые не требуют взаимодействия с пользователем;
Интерактивные или же ручные методы, использующие введенные пользовательские данные во время работы.
Задача сегментации изображения, как правило, применяется на некотором этапе обработки изображения, чтобы получить более точные и более удобные представления этого изображения для дальнейшей работы с ним.
Методов сегментации существует великое множество, и разные методы ориентированы на разные свойства разбиения изображения. Поэтому при выборе метода сегментации в той или иной задаче следует руководствоваться тем, какие же свойства разбиения действительно важны и какими свойствами обладает исходное изображение. Также необходимо решить, какая степень детализации, до которой доводится разделение на классы, оказывается приемлемой. Все зависит от каждой конкретной решаемой задачи. Например, при анализе микросхем задачей выделения объектов может быть выделение блоков микросхем и радиодеталей, а может быть обнаружение трещин на этих радиодеталях. Тогда логично, что в первом случае необходимо ограничиться более крупной детализацией.
Алгоритмы сегментации также делятся, как правило, на два класса:
1) основанные на базовом свойстве яркости: разрывности;
2) основанные на базовом свойстве яркости: однородности .
В первом случае изображение разбивается на области на основании некоторого изменения яркости, такого как, например, перепады яркости на изображении. Во втором случае используется разбиение изображение по критериям однородности областей. Примером первой категории может служить пороговая обработка или же пороговая классификация, а второй - выращивание областей, слияние и разбиение областей. О сегментации первого типа, а именно о пороговой обработке, и пойдет дальше речь.
Сегментация в цветовом пространстве RGB
Обычно пороговая сегментация изображений сводится к задаче сегментации полутоновых изображений. Действительно, выбор порога, как правило единственного, и сегментация на его основе и осуществляют переход от изображения в цветовом пространстве RGB к полутоновому, несмотря на то, что непосредственно предобработки перевода цветного изображения в полутоновое нет. Однако, иногда «цветная сегментация» все же применяется.
Предположим, что на RGB изображении необходимо выделить объекты, цвет которых лежит в определенном диапазоне. Задача сегментации в таком случае состоит в том, чтобы классифицировать каждый пиксель изображения в соответствии с тем, попадает ли его цвет в заданный диапазон или нет. Для этого в цветовом пространстве вводится мера сходства, как правило, евклидово расстояние . Евклидово расстояние между точками и определяется выражением
где, - RGB компоненты вектора, а, - вектора.
Идею применения такой обработки можно в общих чертах увидеть в разделе 2.6 пояснительной записки.
В данной работе в основном рассматривались и сегментировались изображения на основе одного порога, то есть осуществлялся переход к полутоновым изображениям. Причиной тому является тот факт, что задачи сегментации в цветовом пространстве RGB являются узконаправленными, и для каждого изображения в таком случае необходимо знать норму расстояния для каждой компоненты R,G и B, определить которые возможно лишь путем долгих экспериментов на конкретной предметной задаче.
Редактирование изображений и создание коллажей было бы весьма захватывающим процессом, если бы не приходилось тратить бо́льшую часть времени на кропотливую разметку объектов. Задача еще усложняется, когда границы объектов размыты или присутствует прозрачность. Инструменты “Photoshop”, такие как «магнитное лассо» и «волшебная палочка», не очень интеллектуальны, поскольку ориентируются лишь на низкоуровневые признаки изображения. Они возвращают жёсткие (Hard) границы, которые затем нужно исправлять вручную. Подход Semantic Soft Segmentation от исследователей Adobe помогают решить эту непростую задачу, разделяя изображение на слои, соответствующие семантически значимым областям, и добавляя плавные переходы на краях.
«Мягкая» сегментация
Группа исследователей из лаборатории CSAIL в MIT и швейцарского университета ETH Zürich, работающая под руководством Ягыза Аксоя, предложила подойти к этой проблеме, основываясь на спектральной сегментацией, добавив к ней современные достижения глубокого обучения. С помощью текстурной и цветовой информации, а также высокоуровневых семантических признаков, извлечённых , по изображению строится граф специального вида. Затем по этому графу строится матрица Кирхгофа (Laplacian matrix). Используя спектральное разложение этой матрицы, алгоритм генерирует мягкие контуры объектов. Полученное с помощью собственных векторов разбиение изображения на слои можно затем использовать для редактирования.
Обзор предложенного подхода
Описание модели
Рассмотрим метод создания семантически значимых слоёв пошагово:
1. Спектральная маска. Предложенный подход продолжает работу Левина и его коллег, которые впервые использовали матрицу Кирхгофа в задаче автоматического построения маски. Они строили матрицу L, которая задаёт попарное сходство между пикселями в некоторой локальной области. С помощью этой матрицы они минимизируют квадратичный функционал αᵀLα с заданными пользователем ограничениями, где α задаёт вектор значений прозрачности для всех пикселей данного слоя. Каждый мягкий контур является линейной комбинацией K собственных векторов, соответствующих наименьшим собственным значениям L, которая максимизирует так называемую разреженность маски.
2. Цветовая близость. Для вычисления признаков нелокальной цветовой близости исследователи генерируют 2500 суперпикселей и оценивают близость между каждым суперпикселем и всеми суперпикселями в окрестности радиусом 20% размера изображения. Использование нелокальной близости гарантирует, что области с очень похожими цветами останутся связными в сложных сценах, подобных изображённой ниже.
Нелокальная цветовая близость
3. Семантическая близость. Эта стадия позволяет выделять семантически связные области изображения. Семантическая близость поощряет объединение пикселей, которые принадлежат одному объекту сцены, и штрафует за объединение пикселей разных объектов. Здесь исследователи используют предыдущие достижения в области распознавания образов и вычисляют для каждого пикселя вектор признаков, коррелирующий с объектом, в который входит данный пиксель. Векторы признаков вычисляются с помощью нейросети, о чём мы поговорим далее более подробно. Семантическая близость, как и цветовая, определяется на суперпикселях. Однако, в отличие от цветовой близости, семантическая близость связывает только ближайшие суперпиксели, поощряя создание связных объектов. Сочетание нелокальной цветовой близости и локальной семантической близости позволяет создать слои, которые покрывают разъединённые в пространстве изображения фрагмента одного семантически связанного объекта (например, растительность, небо, другие типы фона).
Семантическая близость
4. Создание слоёв. На этом шаге с помощью вычисленных ранее близостей строится матрица L. Из этой матрицы извлекаются собственные векторы, соответствующие 100 наименьшим собственным значениям, а затем применяется алгоритм разреживания, который извлекает из них 40 векторов, по которым строятся слои. Затем количество слоёв ещё раз уменьшается с помощью алгоритма кластеризации k-means при k = 5. Это работает лучше, чем простое разреживание 100 собственных векторов до пяти, поскольку такое сильное сокращение размерности делает задачу переопределённой. Исследователи выбрали итоговое число контуров равным 5 и утверждают, что это разумное число для большинства изображений. Тем не менее, это число можно изменить вручную в зависимости от обрабатываемого изображения.
Мягкие контуры до и после группировки 5. Семантические векторы признаков. Для вычисления семантической близости использовались векторы признаков, посчитанные с помощью нейросети. Основой нейросети стала DeepLab-ResNet-101, обученная на задаче предсказания метрики. При обучении поощрялась максимизация L2-расстояния между признаками разных объектов. Таким образом, нейросеть минимизирует расстояние между признаками, соответствующими одному классу, и максимизирует расстояние в другом случае.
Качественное сравнение со схожими методами
Изображения, приведённые ниже, показывают результаты работы предложенного подхода (подписанные как «Our result») в сравнении с результатами наиболее близкого подхода мягкой сегментации - спектрального метода построения маски - и двумя state-of-the-art методами семантической сегментации: методом обработки сцен PSPNet и методом сегментации объектов Mask R-CNN.
Качественные сравнения мягкой семантической сегментации с другими подходами Можно заменить, что PSPNet и Mask R-CNN склонны ошибаться на границах объектов, а мягкие контуры, построенные спектральным методом, часто заходят за границы объектов. При этом описанный метод полностью охватывает объект, не объединяя его с другими, и достигает высокой точности на краях, добавляя мягкие переходы, где это требуется. Однако стоит заметить, что семантические признаки, использованные в данном методе, не различают два разных объекта, принадлежащих к одному классу. В результате множественные объекты представлены на одном слое, что видно на примере изображений жирафов и коров.
Редактирование изображений с помощью мягких семантических контуров
Ниже приведено несколько примеров применения мягких контуров для редактирования изображений и создания коллажей. Мягкие контуры можно использовать для применения конкретных изменений к разным слоям: добавления размытия, изображающего движение поезда (2), раздельной цветовой коррекции для людей и для фона (5, 6), отдельной стилизации для воздушного шара, неба, ландшафта и человека (8). Конечно, то же самое можно сделать с помощью созданных вручную масок или классических алгоритмов выделения контура, но с автоматическим выделением семантически значимых объектов такое редактирование становится значительно проще.
Использование мягкой семантической сегментации для редактирования изображений
Заключение
Данный метод автоматически создаёт мягкие контуры, соответствующие семантически значимым областям изображения, используя смесь высокоуровневой информации от нейронной сети и низкоуровневых признаков. Однако у этого метода есть несколько ограничений. Во-первых, он относительно медленный: время обработки изображения с размерами 640 x 480–3–4 минуты. Во-вторых, этот метод не создаёт отдельные слои для разных объектов одного класса. И в-третьих, как показано ниже, этот метод может ошибиться на начальных этапах обработки в случаях, когда цвета объектов очень похожи (верхний пример), или во время объединения мягких контуров возле больших переходных областей (нижний пример).
Случаи ошибок алгоритма
Тем не менее, мягкие контуры, созданные с помощью описанного метода, дают удобное промежуточное представление изображения, позволяющее тратить меньше времени и сил при редактировании изображений.