Связанная компонентная маркировка ( CCL ), связанный компонентный анализ ( CCA ), извлечение блобов , маркировка регионов , обнаружение блобов или извлечение регионов — это алгоритмическое применение теории графов , где подмножества связанных компонентов уникально маркируются на основе заданной эвристики . Связанную компонентную маркировку не следует путать с сегментацией .
Маркировка связанных компонентов используется в компьютерном зрении для обнаружения связанных областей в бинарных цифровых изображениях , хотя цветные изображения и данные с более высокой размерностью также могут быть обработаны. [1] [2] При интеграции в систему распознавания изображений или интерфейс взаимодействия человек-компьютер маркировка связанных компонентов может работать с различной информацией. [3] [4] Извлечение пятен обычно выполняется на полученном бинарном изображении с этапа пороговой обработки, но оно может быть применимо также к изображениям в оттенках серого и цветным изображениям. Пятна можно подсчитывать, фильтровать и отслеживать.
Извлечение пятен связано с обнаружением пятен, но отличается от него .
Граф, содержащий вершины и соединяющие ребра , строится из соответствующих входных данных. Вершины содержат информацию, требуемую эвристикой сравнения, в то время как ребра указывают на связанных «соседей». Алгоритм проходит по графу, маркируя вершины на основе связности и относительных значений их соседей. Связность определяется средой; графы изображений, например, могут быть 4-связными окрестностями или 8-связными окрестностями . [5]
После этапа маркировки граф может быть разделен на подмножества, после чего исходная информация может быть восстановлена и обработана.
Использование термина «маркировка связанных компонентов» (CCL) и его определение в академической литературе довольно единообразны, тогда как анализ связанных компонентов (CCA) различается как с точки зрения терминологии, так и определения проблемы.
Розенфельд и др. [6] определяют маркировку связанных компонентов как «[с]оздание маркированного изображения, в котором позиции, связанные с одним и тем же связанным компонентом двоичного входного изображения, имеют уникальную метку». Шапиро и др. [7] определяют CCL как оператор, «входом которого является двоичное изображение, а [...] выходом является символическое изображение, в котором метка, назначенная каждому пикселю, является целым числом, однозначно идентифицирующим связанный компонент, к которому принадлежит этот пиксель». [8]
В академической литературе нет единого мнения об определении CCA. Его часто используют как взаимозаменяемый термин с CCL. [9] [10] Более обширное определение дано Шапиро и др.: [7] «Анализ связанных компонентов состоит из маркировки связанных компонентов черных пикселей с последующим измерением свойств областей компонентов и принятием решений». Представленное здесь определение анализа связанных компонентов является более общим и учитывает мысли, высказанные в [ 7] [9] [10] .
Обсуждаемые алгоритмы можно обобщить на произвольные измерения, хотя и с увеличением временной и пространственной сложности.
Это быстрый и очень простой в реализации и понимании метод. Он основан на методах обхода графа в теории графов. Короче говоря, как только найден первый пиксель связанного компонента, все связанные пиксели этого связанного компонента маркируются перед переходом к следующему пикселю на изображении. Этот алгоритм является частью алгоритма сегментации водораздела Винсента и Сойля , [11] существуют и другие реализации. [12]
Для этого формируется связанный список , который будет хранить индексы пикселей, связанных друг с другом, шаги (2) и (3) ниже. Метод определения связанного списка определяет использование поиска в глубину или в ширину . Для этого конкретного приложения нет разницы, какую стратегию использовать. Простейший вид очереди «последний пришел — первый вышел» , реализованный как односвязный список, приведет к стратегии поиска в глубину.
Предполагается, что входное изображение является бинарным изображением , в котором пиксели являются либо фоном, либо передним планом, и что нужны связанные компоненты в пикселях переднего плана. Шаги алгоритма можно записать как:
Обратите внимание, что пиксели маркируются перед помещением в очередь. Очередь сохранит только пиксель для проверки его соседей и добавления их в очередь при необходимости. Этот алгоритм должен проверить соседей каждого пикселя переднего плана только один раз и не проверяет соседей пикселей фона.
Псевдокод :
алгоритм OneComponentAtATime(data) ввод : imageData[xDim][yDim] инициализация : label = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = false, queue1, queue2; для i = 0 до xDim сделать для j = 0 до yDim сделать если imageData[i][j] не был обработан сделать если imageData[i][j] является пикселем переднего плана сделать проверьте четырех соседей (север, юг, восток, запад): если сосед не обрабатывается, сделать , если сосед является пикселем переднего плана, сделать добавить его в очередь1 еще обновить свой статус как обработанный конец, если labelArray[i][j] = метка (дать метку) statusArray[i][j] = true (обновить статус) Пока очередь1 не пуста, делаем Для каждого пикселя в очереди выполните: проверьте это четверо соседей если сосед не обрабатывается, сделать , если сосед является пикселем переднего плана, сделать добавить его в очередь2 еще обновить свой статус как обработанный конец, если дайте ему текущую метку обновить свой статус как обработанный удалить текущий элемент из queue1 копировать очередь2 в очередь1 конец Пока увеличить этикетку конец если иначе обновить свой статус как обработанный конец если конец если конец если конец для конец для
Относительно простой для реализации и понимания двухпроходный алгоритм [13] (также известный как алгоритм Хошена–Копельмана ) выполняет итерации по двумерным двоичным данным. Алгоритм выполняет два прохода по изображению: первый проход для назначения временных меток и записи эквивалентностей, а второй проход для замены каждой временной метки наименьшей меткой ее класса эквивалентности.
Входные данные могут быть изменены на месте (что несет риск повреждения данных ), или информация о маркировке может храниться в дополнительной структуре данных.
Проверки связности выполняются путем проверки меток соседних пикселей (соседние элементы, метки которых еще не назначены, игнорируются), или, скажем, северо-восток, север, северо-запад и запад текущего пикселя (предполагается 8-связность). 4-связность использует только северных и западных соседей текущего пикселя. Следующие условия проверяются для определения значения метки, которая будет назначена текущему пикселю (предполагается 4-связность):
Условия для проверки:
Алгоритм продолжает работать таким образом и создает новые метки регионов по мере необходимости. Однако ключ к быстрому алгоритму заключается в том, как выполняется это слияние. Этот алгоритм использует структуру данных union-find , которая обеспечивает превосходную производительность для отслеживания отношений эквивалентности. [14] Union-find по сути хранит метки, которые соответствуют одному и тому же блобу, в структуре данных disjoint-set , что упрощает запоминание эквивалентности двух меток с помощью метода интерфейса, например: findSet(l). findSet(l) возвращает минимальное значение метки, которое эквивалентно аргументу функции 'l'.
После завершения первоначальной маркировки и записи эквивалентности второй проход просто заменяет каждую метку пикселя ее эквивалентным репрезентативным элементом непересекающегося множества.
Ниже представлен более быстрый алгоритм сканирования для извлечения связанных областей. [15]
При первом проходе:
На втором проходе:
Здесь фон — это классификация, специфичная для данных, используемая для различения заметных элементов от переднего плана . Если переменная фона опущена, то двухпроходный алгоритм будет рассматривать фон как другую область.
1. Массив, из которого необходимо извлечь связанные регионы, приведен ниже (на основе 8-связности).
Сначала мы присваиваем различные двоичные значения элементам в графе. Значения "0~1" в центре каждого из элементов в следующем графе являются значениями элементов, тогда как значения "1,2,...,7" в следующих двух графах являются метками элементов. Эти два понятия не следует путать.
2. После первого прохода генерируются следующие метки:
Всего генерируется 7 этикеток в соответствии с указанными выше условиями.
Сгенерированные отношения эквивалентности меток следующие:
3. Массив, сформированный после слияния меток, выполняется. Здесь наименьшее значение метки для данного региона «разливается» по всему связанному региону и дает две различные метки, а значит, и две различные метки.
4. Окончательный результат в цвете, чтобы четко видеть две разные области, обнаруженные в массиве.
Псевдокод :
алгоритм TwoPass(data) — это связанный = [] метки = структура с размерами данных, инициализированная значением Background Следующая метка = 0 Первый проход для строки в данных сделать для столбца в строке сделать если данные[строка][столбец] не является фоновым тогда соседи = связанные элементы со значением текущего элемента если neighbors пусто , то linked[NextLabel] = набор , содержащий NextLabel метки[строка][столбец] = СледующаяМетка Следующая метка += 1 еще Найдите самую маленькую этикетку L = метки соседей labels[row][column] = min (L) для label в L do linked[label] = union (linked[label], L) Второй проход для строки в данных сделать для столбца в строке сделать если данные[строка][столбец] не Фон , то метки[строка][столбец] = найти (метки[строка][столбец]) этикетки возврата
Алгоритмы поиска и объединения реализованы так, как описано в union find .
Создать региональный счетчик
Сканируйте изображение (в следующем примере предполагается, что сканирование выполняется слева направо и сверху вниз):
Некоторые из шагов, присутствующих в двухпроходном алгоритме, могут быть объединены для эффективности, позволяя выполнить один проход по изображению. Существуют также многопроходные алгоритмы, некоторые из которых работают за линейное время относительно количества пикселей изображения. [16]
В начале 1990-х годов существовал значительный интерес к распараллеливанию алгоритмов связанных компонентов в приложениях анализа изображений из-за узкого места последовательной обработки каждого пикселя. [17]
Интерес к алгоритму вновь возникает в связи с широким использованием CUDA.
Алгоритм:
По одному компоненту за раз ( изображение ) [M, N] := размер( изображение ) связано := нули(M, N) отметка := разница значений := приращение смещения := [-1; M; 1; -M] индекс := [] нет_объектов := 0 для i: 1:M сделать для j: 1:N сделать если ( изображение (i, j) == 1) тогда нет_объектов := нет_объектов + 1 индекс := [((j-1) × M + i)] связано ( индекс ) := пометить пока ~isempty( индекс ) сделать изображение ( индекс ) := 0 соседи := bsxfun(@plus, index , offsets ) соседи := уникальный( соседи (:)) индекс := соседи (найти( изображение ( соседи ))) связано ( индекс ) := пометить конец пока отметка := отметка + разница конец если конец для конец для
Время выполнения алгоритма зависит от размера изображения и объема переднего плана. Временная сложность сопоставима с двухпроходным алгоритмом, если передний план покрывает значительную часть изображения. В противном случае временная сложность ниже. Однако доступ к памяти менее структурирован, чем для двухпроходного алгоритма, что на практике приводит к увеличению времени выполнения.
За последние два десятилетия было предложено много новых подходов к маркировке связанных компонентов, но почти ни один из них не подвергался сравнительной оценке производительности с использованием одного и того же набора данных. YACCLAB [18] [19] (аббревиатура от Yet Another Connected Components Labeling Benchmark) — это пример фреймворка с открытым исходным кодом на C++ , который собирает, запускает и тестирует алгоритмы маркировки связанных компонентов.
Появление ПЛИС с достаточной емкостью для выполнения сложных задач обработки изображений также привело к появлению высокопроизводительных архитектур для маркировки связанных компонентов. [20] [21] Большинство этих архитектур используют однопроходный вариант этого алгоритма из-за ограниченных ресурсов памяти, доступных на ПЛИС . Эти типы архитектур маркировки связанных компонентов могут обрабатывать несколько пикселей изображения параллельно, тем самым достигая высокой пропускной способности и низкой задержки обработки.