ImageSegmentation.jl

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

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

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

Источник

В документации по алгоритму seeded_region_growing указано, что ему требуются два аргумента: сегментируемое изображение и набор начальных точек для каждой области. Начальные точки должны храниться как вектор кортежей (position, label), где position — это CartesianIndex, а label — целое число. Начнем с того, что откроем изображение с помощью ImageView и считаем координаты начальных точек.

Наведите курсор на объекты, которые нужно сегментировать, и прочитайте координаты одной или нескольких точек внутри каждого из них. Мы сохраним начальные точки как вектор кортежей (seed position, label) и используем seeded_region_growing с записанными начальными точками.

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

Мы можем визуализировать каждый сегмент, используя его средний цвет:

Такая форма отображения используется во многих примерах ниже.

Как видите, алгоритм неплохо справился с сегментацией трех объектов. Единственная очевидная ошибка заключается в том, что элементы неба, «обрамленные» лошадью, в итоге оказались сгруппированы с землей. Это связано с тем, что seeded_region_growing всегда возвращает связанные области, а пути, соединяющего эти части неба с остальной частью, нет. Если добавить несколько дополнительных начальных точек в этих областях и присвоить им ту же метку 2, что и остальной части неба, получится более или менее идеальный результат.

Теперь сегментируем это изображение с помощью алгоритма Фельценшвальба. Алгоритму felzenszwalb нужен только один параметр k, который контролирует размер сегментов. Чем больше k, тем больше сегменты. При значениях от k=5 до k=500 обычно получаются хорошие результаты.

При k = 100 получаются лишь два «основных» сегмента. При k = 10 сегменты получаются меньше, но больше шума. felzenzwalb также принимает необязательный аргумент min_size — он удаляет все сегменты размером менее min_size пикселей. (Базовый алгоритм большинства методов не предполагает удаления небольших сегментов. С помощью метода prune_segments можно обработать результат сегментации и удалить мелкие сегменты.)

Все алгоритмы сегментации (кроме алгоритма нечетких C-средних) возвращают на выходе структуру SegmentedImage. SegmentedImage содержит всю необходимую информацию о сегментах. Для получения информации о сегментах можно использовать следующие функции:

Алгоритм выращивания областей от начальных точек сегментирует изображение относительно некоторых определенных пользователем начальных точек. Каждая начальная точка представляет собой кортеж (position, label), где position — это CartesianIndex, а label — положительное целое число. Каждая метка соответствует уникальной части изображения. Алгоритм пытается присвоить эти метки каждой из оставшихся точек. Если у нескольких точек одинаковая метка, они будут относиться к одному сегменту.

Исходное изображение (источник):

Сегментированное изображение, метки которого заменены средними значениями интенсивности:

Этот алгоритм похож на Seeded Region Growing, но не требует предварительной информации о начальных точках. Процесс сегментации начинается с области , содержащей один пиксель изображения. Допустим, что промежуточное состояние алгоритма состоит из множества идентифицированных областей . Пусть  — это множество всех нераспределенных пикселей, которые граничат хотя бы с одной из этих областей. Процесс выращивания предполагает выбор точки и области , где ], таких, что

где |]

Если меньше threshold, то пиксель z добавляется в . В противном случае выбирается наиболее похожая область такая, что

Если меньше threshold, то пиксель z добавляется в . Если ни одно из этих двух условий не выполняется, то пиксель присваивается новой области . После присваивания обновляется статистика соответствующей области. Выполнение алгоритма останавливается, когда все пиксели присвоены какой-либо области.

Для unseeded_region_growing в качестве параметров требуются изображение img и порог threshold.

Этот алгоритм работает на основе графа смежности областей (RAG). Каждый пиксель или область представляет собой узел графа, а смежные пиксели или области соединены ребрами с весом, соответствующим расхождению между этими пикселями или областями. Алгоритм раз за разом объединяет сходные области, пока не получается окончательная сегментация. Он эффективно вычисляет «суперпиксели» с избыточной сегментацией на изображении. Функцию можно вызвать напрямую с изображением (реализация сначала создает граф RAG изображения, а затем продолжает работу).

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

Метод среднего сдвига — это метод кластеризации. Его основные преимущества в том, что он не предполагает изначальной формы кластера (например, гауссиан для k-средних) и не нужно заранее знать количество кластеров. Этот алгоритм плохо масштабируется в зависимости от размера изображения.

Алгоритм быстрого сканирования сегментирует изображение, сканируя его один раз и сравнивая каждый пиксель с соседними пикселями сверху и слева. Алгоритм начинает выполнение с первого пикселя и присваивает его новому сегменту . Количеству меток lc присваивается значение 1. Затем начинается обход изображения по столбцам, и для каждого пикселя вычисляется величина разницы diff_fn между ним и соседним с ним пикселем слева, допустим, , а также соседним с ним пикселем сверху, допустим, . Возможны четыре случая:

Этот алгоритм сегментирует изображение всего за два прохода (один для сегментации, другой для слияния), поэтому он выполняется очень быстро и может применяться в приложениях реального времени.

Временная сложность: , где  — количество пикселей

Исходное изображение:

Сегментированное изображение:

Этот алгоритм следует методологии «разделяй и властвуй». Если входное изображение однородное, то ничего не происходит. В противном случае изображение делится на две части по каждому измерению, и эти части сегментируются рекурсивно. В результате строится дерево областей, на основе которого можно создать сегментированное изображение.

Временная сложность: , где  — количество пикселей

Исходное изображение:

Сегментированное изображение, метки которого заменены средними значениями интенсивности:

Нечеткая кластеризация C-средних широко применяется для неконтролируемой сегментации изображений. Это итеративный алгоритм, который пытается минимизировать функцию стоимости:

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

Временная сложность: , где  — количество пикселей,  — количество кластеров, а  — количество итераций.

Если говорить кратко, r содержит два важных компонента:

Дополнительные сведения см. в документации по Clustering.jl.

Исходное изображение (источник)

Результат с интенсивностью пикселя = интенсивность в центре кластера * принадлежность пикселя к этому классу

Алгоритм морфологических водоразделов рассматривает изображение как топографическую поверхность, где яркие пиксели соответствуют пикам, а темные — впадинам. Алгоритм начинает затопление со впадин (локальных минимумов) этой топографической поверхности, а границы областей формируются при слиянии воды из разных источников. Если изображение зашумлено, такой подход приводит к чрезмерной сегментации. Для предотвращения чрезмерной сегментации применяются маркерные водоразделы: топографическая поверхность затапливается с заранее определенного набора маркеров.

Рассмотрим пример использования водоразделов для сегментации соприкасающихся объектов. Чтобы использовать водораздел, необходимо изменить изображение так, чтобы на новом изображении затопление топографической поверхности от маркеров отделяло каждую монету. Если измененное изображение зашумлено, затопление из локальных минимумов может привести к чрезмерной сегментации, поэтому также требуется способ нахождения положений маркеров. В этом примере требуемую топографическую структуру имеет обратное преобразование distance_transform изображения с определенными порогами (изображение dist) (сведения о том, как это работает, см. на этой странице). Мы можем определить пороги изображения dist, чтобы получить положения маркеров.

Граф смежности областей можно построить непосредственно на основе SegmentedImage с помощью функции region_adjacency_graph. Каждому сегменту соответствует вершина, а между соседними сегментами строятся ребра. Результатом является кортеж объектов SimpleWeightedGraph и словарь Dict(label=>vertex) с весами, присвоенными в соответствии с weight_fn.

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

Дерево областей можно построить на основе изображения с помощью функции region_tree. Если изображение неоднородное, то оно делится пополам по каждому измерению, и функция вызывается рекурсивно для каждой части изображения. Результатом является объект RegionTree.

Дополнительные сведения о RegionTrees см. здесь.

Все ненужные сегменты можно легко удалить из SegmentedImage с помощью функции prune_segments. Она удаляет сегмент, заменяя его соседним сегментом с наименьшим значением diff_fn. Можно передать список сегментов, подлежащих удалению. Можно также передать функцию, которая возвращает true для меток, которые необходимо удалить.

В этом и следующем примерах (в разделе Removing a segment) используется образец изображения SegmentedImage. Его можно сгенерировать следующим образом:

Удалить один сегмент можно с помощью функции rem_segment!. Она удаляет сегмент из SegmentedImage на месте, заменяя его соседним сегментом с наименьшим значением diff_fn.