Сегментация (обработка изображений)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Применение[править | править вики-текст]

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

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

Методы, основанные на кластеризации[править | править вики-текст]

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

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

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

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

Методы с использованием гистограммы[править | править вики-текст]

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

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

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

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

Выделение краёв[править | править вики-текст]

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

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

Методы разрастания областей[править | править вики-текст]

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

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

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

Методы разреза графа[править | править вики-текст]

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

Сегментация методом водораздела[править | править вики-текст]

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

Сегментация с помощью модели[править | править вики-текст]

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

Многомасштабная сегментация[править | править вики-текст]

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

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

Одномерная иерархическая сегментация сигналов[править | править вики-текст]

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

Литература[править | править вики-текст]

  1. 1 2 3 4 5 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
  3. 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
  4. Jianbo Shi and Jitendra Malik (2000): «Normalized Cuts and Image Segmentation», IEEE Transactions on pattern analysis and machine intelligence, pp 888—905, Vol. 22, No. 8
  5. Leo Grady (2006): «Random Walks for Image Segmentation», IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768—1783, Vol. 28, No. 11
  6. 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
  7. Leo Grady and Eric L. Schwartz (2006): «Isoperimetric Graph Partitioning for Image Segmentation», IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 469—475, Vol. 28, No. 3
  8. C. T. Zahn (1971): «Graph-theoretical methods for detecting and describing gestalt clusters», IEEE Transactions on Computers, pp. 68-86, Vol. 20, No. 1
  9. Witkin, A. P. «Scale-space filtering», Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany,1019—1022, 1983.
  10. 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.

Ссылки[править | править вики-текст]

3D Entropy Based Image Segmentation