Сегментация (обработка изображений) (Vyibyumgenx (kQjgQkmtg n[kQjg'yunw))

В компьютерном зрении, сегментация — это процесс разделения цифрового изображения на несколько сегментов (множество пикселей, также называемых суперпикселями). Цель сегментации заключается в упрощении и/или изменении представления изображения, чтобы его было проще и легче анализировать.^[1] Сегментация изображений обычно используется для того, чтобы выделить объекты и границы (линии, кривые, и т. д.) на изображениях. Более точно, сегментация изображений — это процесс присвоения меток каждому пикселю изображения так, что пиксели с одинаковыми метками имеют общие визуальные характеристики.

Результатом сегментации изображения является множество сегментов, которые вместе покрывают всё изображение, или множество контуров, выделенных из изображения (см. Выделение границ). Все пиксели в сегменте похожи по некоторой характеристике или вычисленному свойству, например, по цвету, яркости или текстуре. Соседние сегменты значительно отличаются по этой характеристике.^[1]

Применение

Некоторыми практическими применениями сегментации изображений являются:

Медицинские изображения^[2]
- Обнаружение опухолей и других патологий
- Определение объёмов тканей
- Хирургия при помощи компьютера
- Диагностика
- Планирование лечения
- Изучение анатомической структуры
Выделение объектов на спутниковых снимках
Распознавание лиц
Распознавание отпечатков пальцев
Системы управления дорожным движением
Обнаружение стоп-сигналов
Машинное зрение
Распараллеливание информационных потоков при передаче изображений высокого разрешения^[3]

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

Методы, основанные на кластеризации

k-средних — это итеративный метод, который используется, чтобы разделить изображение на K кластеров. Базовый алгоритм приведён ниже:

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

Здесь в качестве расстояния обычно берётся сумма квадратов или абсолютных значений разностей между пикселем и центром кластера. Разность обычно основана на цвете, яркости, текстуре и местоположении пикселя, или на взвешенной сумме этих факторов. K может быть выбрано вручную, случайно или эвристически.

Этот алгоритм гарантированно сходится, но он может не привести к оптимальному решению. Качество решения зависит от начального множества кластеров и значения K.

Методы с использованием гистограммы

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

Улучшение этого метода — рекурсивно применять его к кластерам на изображении для того, чтобы поделить их на более мелкие кластеры. Процесс повторяется со всё меньшими и меньшими кластерами до тех пор, когда перестанут появляться новые кластеры.^[1]^[4]

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

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

Выделение краёв

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

Обнаруженные края часто бывают разорванными. Но чтобы выделить объект на изображении, нужны замкнутые границы области.

Методы разрастания областей

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

Метод разрастания областей из семян требует дополнительного ввода. Результат сегментации зависит от выбора семян. Шум на изображении может вызвать то, что семена плохо размещены. Метод разрастания областей без использования семян — это изменённый алгоритм, который не требует явных семян. Он начинает с одной области $A_{1}$ — пиксель, выбранный здесь, незначительно влияет на конечную сегментацию. На каждой итерации он рассматривает соседние пиксели так же, как метод разрастания областей с использованием семян. Но он отличается тем, что если минимальная $\delta$ меньше, чем заданный порог $T$ , то он добавляется в соответствующую область $A_{j}$ . В противном случае пиксель считается сильно отличающимся от всех текущих областей $A_{i}$ и создаётся новая область $A_{n+1}$ , содержащая этот пиксель.

Один из вариантов этого метода, предложенный Хараликом и Шапиро (1985),^[1] основан на использовании яркости пикселей. Среднее и дисперсия области и яркость пикселя-кандидата используется для построения тестовой статистики. Если тестовая статистика достаточно мала, то пиксель добавляется к области, и среднее и дисперсия области пересчитываются. Иначе пиксель игнорируется и используется для создания новой области.

Методы разреза графа

Методы разреза графа могут быть эффективно применены для сегментации изображений. В этих методах изображение представляется как взвешенный неориентированный граф. Обычно пиксель или группа пикселей ассоциируется вершиной, а веса рёбер определяют (не)похожесть соседних пикселей. Затем граф (изображение) разрезается согласно критерию, созданному для получения «хороших» кластеров. Каждая часть вершин (пикселей), получаемая этими алгоритмами, считается объектом на изображении. Некоторые популярные алгоритмы этой категории — это нормализованные разрезы графов^[5], случайное блуждание^[6], минимальный разрез^[7], изопериметрическое разделение^[8] и сегментация с помощью минимального остовного дерева^[9].

Сегментация методом водораздела

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

Сегментация с помощью модели

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

Многомасштабная сегментация

Сегментация изображений выполняется в разных масштабах в масштабном пространстве и иногда распространяется от мелких масштабов к крупным.

Критерий сегментации может быть произвольно сложным и может принимать во внимание как локальные, так и глобальные критерии. Общее требование — то, что каждая область должна быть связана в некотором смысле.

Одномерная иерархическая сегментация сигналов

Основополагающая работа Виткина^[10]^[11] в масштабном пространстве содержала идею о том, что одномерный сигнал может быть однозначно сегментирован на области, используя всего лишь один параметр, управляющий масштабом сегментации.

Примечания

↑ ¹ ² ³ ⁴ ⁵ Linda G. Shapiro and George C. Stockman (2001): «Computer Vision», pp 279—325, New Jersey, Prentice-Hall, ISBN 0-13-030796-3
↑ Dzung L. Pham, Chenyang Xu, and Jerry L. Prince (2000): «Current Methods in Medical Image Segmentation», Annual Review of Biomedical Engineering, volume 2, pp 315—337
↑ Слюсар, В.И. Методы передачи изображений сверхвысокой четкости. (неопр.) Первая миля. Last mile. – 2019, №2. 46 - 61. (2019). Дата обращения: 8 мая 2019. Архивировано 8 мая 2019 года.
↑ Ron Ohlander, Keith Price, and D. Raj Reddy (1978): «Picture Segmentation Using a Recursive Region Splitting Method», Computer Graphics and Image Processing, volume 8, pp 313—333
↑ Jianbo Shi and Jitendra Malik (2000): «Normalized Cuts and Image Segmentation» Архивная копия от 6 июня 2011 на Wayback Machine, IEEE Transactions on pattern analysis and machine intelligence, pp 888—905, Vol. 22, No. 8
↑ Leo Grady (2006): «Random Walks for Image Segmentation» Архивировано 19 июля 2011 года., IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768—1783, Vol. 28, No. 11
↑ Z. Wu and R. Leahy (1993): «An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation» (недоступная ссылка), IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1101—1113, Vol. 15, No. 11
↑ Leo Grady and Eric L. Schwartz (2006): «Isoperimetric Graph Partitioning for Image Segmentation» Архивировано 19 июля 2011 года., IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 469—475, Vol. 28, No. 3
↑ C. T. Zahn (1971): «Graph-theoretical methods for detecting and describing gestalt clusters» Архивная копия от 18 июня 2010 на Wayback Machine, IEEE Transactions on Computers, pp. 68-86, Vol. 20, No. 1
↑ Witkin, A. P. «Scale-space filtering», Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany,1019—1022, 1983.
↑ A. Witkin, "Scale-space filtering: A new approach to multi-scale description, " in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing (ICASSP), vol. 9, San Diego, CA, Mar. 1984, pp. 150—153.

Литература

Frucci, Maria; Sanniti di Baja, Gabriella. From Segmentation to Binarization of Gray-level Images] (англ.) // Journal of Pattern Recognition Research] : journal. — 2008. — Vol. 3, no. 1. — P. 1—13 [1].

Ссылки

3D Entropy Based Image Segmentation

[computervision-1] ¹ ² ³ ⁴ ⁵ Linda G. Shapiro and George C. Stockman (2001): «Computer Vision», pp 279—325, New Jersey, Prentice-Hall, ISBN 0-13-030796-3

[2] Dzung L. Pham, Chenyang Xu, and Jerry L. Prince (2000): «Current Methods in Medical Image Segmentation», Annual Review of Biomedical Engineering, volume 2, pp 315—337

[slyusar-3] Слюсар, В.И. Методы передачи изображений сверхвысокой четкости. (неопр.) Первая миля. Last mile. – 2019, №2. 46 - 61. (2019). Дата обращения: 8 мая 2019. Архивировано 8 мая 2019 года.

[4] Ron Ohlander, Keith Price, and D. Raj Reddy (1978): «Picture Segmentation Using a Recursive Region Splitting Method», Computer Graphics and Image Processing, volume 8, pp 313—333

[5] Jianbo Shi and Jitendra Malik (2000): «Normalized Cuts and Image Segmentation» Архивная копия от 6 июня 2011 на Wayback Machine, IEEE Transactions on pattern analysis and machine intelligence, pp 888—905, Vol. 22, No. 8

[6] Leo Grady (2006): «Random Walks for Image Segmentation» Архивировано 19 июля 2011 года., IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768—1783, Vol. 28, No. 11

[7] Z. Wu and R. Leahy (1993): «An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation» (недоступная ссылка), IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1101—1113, Vol. 15, No. 11

[8] Leo Grady and Eric L. Schwartz (2006): «Isoperimetric Graph Partitioning for Image Segmentation» Архивировано 19 июля 2011 года., IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 469—475, Vol. 28, No. 3

[9] C. T. Zahn (1971): «Graph-theoretical methods for detecting and describing gestalt clusters» Архивная копия от 18 июня 2010 на Wayback Machine, IEEE Transactions on Computers, pp. 68-86, Vol. 20, No. 1

[10] Witkin, A. P. «Scale-space filtering», Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany,1019—1022, 1983.

[11] A. Witkin, "Scale-space filtering: A new approach to multi-scale description, " in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing (ICASSP), vol. 9, San Diego, CA, Mar. 1984, pp. 150—153.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]