Источник: http://en.wikipedia.org/wiki/Segmentation_(image_processing)

Перевод отрывка статьи с английского выполнен Суровой Анной

СЕГМЕНТАЦИЯ

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

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

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

• Медицинские изображения
• Поиск опухолей и других патологий
• Измерение объема тканей
• Компьютерная хирургия
• Диагностика
• Планирование лечения
• Изучение анатомической структуры
• Поиск объектов спутниковых изображений (дороги, леса и т.д.)
• Распознавание лиц
• Распознавание отпечатков
• Автоматические системы контроля движения
• Машинное зрение

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

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

Алгоритм K-средних – это итеративный метод, который используется для разделения изображения на K кластеров. Основной алгоритм состоит в следующем: Выберем К центров кластеров, будь то случайно или на основе некоторых эвристик. Назначим каждый пиксель изображения кластеру, чтобы свести к минимуму разницу между пикселем и центром кластера. Пересчитаем центры кластера путем усреднения всех точек в кластере. Повторяем шаги 2 и 3 до тех пор, пока достигнем сонвергенции (например, нет пикселей, изменяющих кластера) В этом случае разница будет в квадрате или абсолютная разницей между пикселем и центром кластера. Разница, как правило, основана на цвет пикселя, интенсивности, текстуре, и расположении, или взвешенной комбинации этих факторов. K могут быть выбраны вручную, случайно или эвристически. Этот алгоритм гарантированно сходится, но он может не дать оптимальное решение. Качество решения зависит от исходного набора кластеров и значение К.

Гистограммные методы

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

Методы обнаружения границ

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

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

Первым методом наращивания областей был метод наращивания областей севом. В этом методе используется множество семян в качестве входных параметров совместно с изображением. Семена отмечают каждый из объектов сегментирования. Области итеративно наращиваются путем сравнения всех свободных соседних пикселей с характеристиками областей. Разница между значением интенсивности пикселей и значением в области, δ, используется в качестве меры сходства. Пиксель с наименьшим различием, измеренным таким образом, причисляется к соответствующей области. Этот процесс продолжается до тех пор, пока все пиксели не будут причислены к областям. Метод наращивания севом требует дополнительных затрат. Результаты сегментации зависят от выбора семян. Шум на изображении может далеко рассеять семена. Наращивание областей без семян представляет собой модифицированный алгоритм, который не требует явного применения семян. Она начинается с одной области A1 – пиксели, выбранные здесь, существенно не влияют на окончательную сегментацию. На каждой итерации он рассматривает соседние пиксели таким же образом, как в методе наращивания севом. Он отличается от метода наращивания области тем, что если минимальная δ меньше заданного порогового T, то она добавляется к соответствующей области Аj. Если нет, то пиксель считается существенно отличным от всех нынешних областей Ai и новая область An+1 создается этим пикселем. Вариант этого метода, предложенный Хараликом и Шапиро (1985), основан на интенсивности пикселей. Среднее и разброс по области и интенсивность кандидата-пикселя используется для расчета тестовой статистики. Если тестовая статисктика достаточно небольшая, пиксели добавляется к области, и в среднее и рассеяние области пересчитываются. В противном случае пиксель будет исключен, и используется для формирования новой области.

Поуровневые методы

Кривая распределения является популярным методом анализа изображения для извлечения объекта, отслеживания объекта, стерео реконструкции и т.д. Центральная идея такого подхода заключается в том, чтобы провести кривую в направлении самого низкого потенциала стоимостной функции, когда ее определение отражает ее предназначение и налагает определенные ограничения на гладкость. Методы Лагранжа основаны на параметризации контура по некоторым стратегиям отбора проб, а затем выводить каждый элемент в соответствии с изображением и внутренними условиями. Хотя такой метод может быть очень эффективным, он страдает от различных ограничений, таких как принятие решения о стратегии отбора проб, оценки внутренних геометрических свойств этой кривой, изменений ее топологии, решение проблем в сфере более высокого разрешения и т.д.

Поуровневй метод был первоначально предложен для отслеживания движущихся интерфейсов Osher и Sethian в 1988 году и распространился в различных областях обработки изображений в конце девяностых. Он может использоваться для эффективного решения проблемы кривой/поверхности/и т.д. распространения соответствующим образом. Основная идея заключается в выделении контура с использованием знаковой функции, где ее нулевой уровень соответствует нужному контуру. Затем, в соответствии с уравнением движения в контуре, можно легко получить аналогичную плавную для неявной поверхности, которая, при применении к нулевому уровню будет отражать распространение контура. Поуровневый метод кодирует множество преимуществ: это неявность, безпараметричность, обеспечение прямого пути для оценки геометрических свойств выделенной структуры, возможность изменять топологию и внутренние свойства. Кроме того, они могут быть использованы для определения каркаса оптимизации, предложенные Чжао, Merriman и Osher в 1996 году. Таким образом, можно заключить, что это очень удобная среда разработки для создания многочисленных приложений компьютерного зрения и анализа медицинских изображений.

Методы графической разметки

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

Трансформация водоразделом

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

Сегментация, основанная на моделях

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

(I) регистрацию учебных примеров общего вида,

(II) вероятностное представлении множества зарегистрированных образцов

(III)статистическое соответствие модели и изображения.

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

Вверх