Маркировка связанных компонентов ( CCL ), анализ связанных компонентов ( CCA ), выделение blob , маркировка областей , обнаружение blob или выделение области - это алгоритмическое приложение теории графов , где подмножества связанных компонентов однозначно помечаются на основе заданной эвристики . Маркировку подключенных компонентов не следует путать с сегментацией .
Маркировка связанных компонентов используется в компьютерном зрении для обнаружения связанных областей в двоичных цифровых изображениях , хотя цветные изображения и данные с более высокой размерностью также могут обрабатываться. [1] [2] При интеграции в систему распознавания изображений или интерфейс взаимодействия человека с компьютером , маркировка подключенных компонентов может работать с различной информацией. [3] [4] Извлечение BLOB-объектов обычно выполняется на результирующем двоичном изображении на этапе установления порога, но оно также может быть применимо к полутоновым и цветным изображениям. BLOB-объекты можно подсчитывать, фильтровать и отслеживать.
Извлечение blob связано с обнаружением blob, но отличается от него .
Обзор
Граф, содержащий вершины и соединяющие ребра , строится из соответствующих входных данных. Вершины содержат информацию, требуемую эвристикой сравнения, а ребра указывают на связанных «соседей». Алгоритм проходит по графу, маркируя вершины на основе связности и относительных значений их соседей. Связь определяется средой; Графы изображений, например, могут быть 4-связными окрестностями или 8-связными окрестностями . [5]
После этапа разметки граф может быть разбит на подмножества, после чего исходная информация может быть восстановлена и обработана.
Определение
Использование термина «разметка связанных компонентов» (CCL) и его определение в академической литературе вполне согласовано, тогда как анализ связанных компонентов (CCA) варьируется как с точки зрения терминологии, так и с точки зрения определения проблемы.
Розенфельд и др. [6] определяют маркировку связанных компонентов как «[c] создание помеченного изображения, в котором позиции, связанные с одним и тем же связным компонентом двоичного входного изображения, имеют уникальную метку». Шапиро и др. [7] определяют CCL как оператор, «вход которого представляет собой двоичное изображение, а выход [...] представляет собой символическое изображение, в котором метка, присвоенная каждому пикселю, является целым числом, однозначно идентифицирующим подключенный компонент, которому принадлежит этот пиксель». [8]
В академической литературе нет единого мнения по поводу определения ОСО. Часто используется как синоним CCL. [9] [10] Более подробное определение дано Шапиро и др.: [7] «Анализ связанных компонентов состоит из маркировки связанных компонентов черных пикселей с последующим измерением свойств областей компонентов и принятием решений». Представленное здесь определение связно-компонентного анализа является более общим, принимая во внимание мысли, высказанные в [9] [10] [7] .
Алгоритмы
Обсуждаемые алгоритмы могут быть обобщены на произвольные измерения, хотя и с повышенной временной и пространственной сложностью.
По одному компоненту за раз
Это быстрый и очень простой метод для реализации и понимания. Он основан на методах обхода графов в теории графов. Короче говоря, как только первый пиксель подключенного компонента найден, все подключенные пиксели этого подключенного компонента помечаются перед переходом к следующему пикселю изображения. Этот алгоритм является частью алгоритма сегментации водораздела Винсента и Сойля [11], также существуют другие реализации. [12]
Для этого формируется связанный список, в котором будут храниться индексы пикселей, которые связаны друг с другом, шаги (2) и (3) ниже. Метод определения связанного списка определяет использование поиска в глубину или в ширину . Для этого конкретного приложения нет разницы, какую стратегию использовать. Простейший вид очереди « последний пришел, первый ушел», реализованный как односвязный список, приведет к стратегии поиска в глубину.
Предполагается, что входное изображение является двоичным изображением с пикселями, являющимися фоном или передним планом, и что желательны соединенные компоненты в пикселях переднего плана. Шаги алгоритма можно записать как:
- Начните с первого пикселя изображения. Установите текущую метку на 1. Перейдите к (2).
- Если этот пиксель является пикселем переднего плана и он еще не помечен, присвойте ему текущую метку и добавьте его в качестве первого элемента в очереди, затем перейдите к (3). Если это фоновый пиксель или он уже был помечен, повторите (2) для следующего пикселя изображения.
- Вытащите элемент из очереди и посмотрите на его соседей (на основе любого типа связи). Если сосед является пикселем переднего плана и еще не помечен, присвойте ему текущую метку и добавьте его в очередь. Повторяйте (3), пока в очереди не останется элементов.
- Перейдите к (2) для следующего пикселя изображения и увеличьте текущую метку на 1.
Обратите внимание, что пиксели маркируются перед помещением в очередь. Очередь будет хранить только пиксель для проверки своих соседей и добавления их в очередь при необходимости. Этот алгоритм должен проверять только соседей каждого пикселя переднего плана один раз и не проверяет соседей пикселей фона.
Двухходовой
Относительно простой в реализации и понимании, двухпроходный алгоритм [13] (также известный как алгоритм Хошена – Копельмана ) выполняет итерацию по двумерным двоичным данным. Алгоритм делает два прохода по изображению. Первый проход предназначен для присвоения временных меток и эквивалентностей записей, а второй - для замены каждой временной метки наименьшей меткой из ее класса эквивалентности.
Входные данные могут быть изменены на месте (что сопряжено с риском повреждения данных ), или маркировочная информация может сохраняться в дополнительной структуре данных.
Проверки связности выполняются путем проверки меток соседних пикселей (соседние элементы, чьи метки еще не назначены, игнорируются) или, скажем, северо-восток, север, северо-запад и запад от текущего пикселя (при условии 8- возможность подключения). 4-связность использует только северных и западных соседей текущего пикселя. Следующие условия проверяются, чтобы определить значение метки, которая будет назначена текущему пикселю (предполагается 4-связность)
Условия для проверки:
- Имеет ли пиксель слева (запад) то же значение, что и текущий пиксель?
- Да, мы находимся в одном регионе. Назначьте ту же метку текущему пикселю
- Нет - проверьте следующее условие
- Оба пикселя к северу и западу от текущего пикселя имеют то же значение, что и текущий пиксель, но не одинаковую метку?
- Да. Мы знаем, что северный и западный пиксели принадлежат одному региону и должны быть объединены. Присвойте текущему пикселю минимум меток «Север» и «Запад» и запишите их отношение эквивалентности.
- Нет - проверьте следующее условие
- Пиксель слева (запад) имеет другое значение, а пиксель к северу - то же значение, что и текущий пиксель?
- Да - присвоить метку северного пикселя текущему пикселю
- Нет - проверьте следующее условие
- У северных и западных соседей пикселя значения пикселей отличаются от текущего?
- Да - создать новый идентификатор метки и назначить его текущему пикселю
Алгоритм продолжает этот путь и при необходимости создает новые метки регионов. Однако ключом к быстрому алгоритму является то, как выполняется это слияние. Этот алгоритм использует структуру данных объединение-поиск, которая обеспечивает отличную производительность для отслеживания отношений эквивалентности. [14] Union-find по существу хранит метки, которые соответствуют одному и тому же blob-объекту в непересекающейся структуре данных , что позволяет легко запомнить эквивалентность двух меток с помощью метода интерфейса Eg: findSet (l). findSet (l) возвращает минимальное значение метки, эквивалентное аргументу функции 'l'.
Как только начальная маркировка и запись эквивалентности завершены, второй проход просто заменяет каждую метку пикселя ее эквивалентным репрезентативным элементом непересекающегося множества.
Алгоритм более быстрого сканирования для выделения связанных областей представлен ниже. [15]
На первом проходе:
- Итерировать каждый элемент данных по столбцу, затем по строке (растровое сканирование)
- Если элемент не является фоном
- Получить соседние элементы текущего элемента
- Если нет соседей, однозначно пометьте текущий элемент и продолжите
- В противном случае найдите соседа с наименьшей меткой и назначьте его текущему элементу
- Сохраните эквивалентность между соседними этикетками
На втором проходе:
- Перебирать каждый элемент данных по столбцу, затем по строке
- Если элемент не является фоном
- Изменить метку элемента с наименьшей эквивалентной меткой
Здесь фон представляет собой классификацию, специфичную для данных, используемую для отделения основных элементов от переднего плана . Если переменная фона не указана, то двухпроходный алгоритм будет рассматривать фон как другую область.
Графический пример двухпроходного алгоритма
1. Массив, из которого должны быть извлечены связанные регионы, приведен ниже (на основе 8-связности).
Сначала мы присваиваем различные двоичные значения элементам на графике. Значения «0 ~ 1» в центре каждого из элементов на следующем графике являются значениями элементов, тогда как значения «1,2, ..., 7» на следующих двух графиках являются метками элементов. Эти два понятия не следует путать.
2. После первого прохода генерируются следующие метки:
Всего создается 7 меток в соответствии с условиями, выделенными выше.
Сгенерированные отношения эквивалентности меток:
Установить идентификатор | Эквивалентные ярлыки |
---|---|
1 | 1,2 |
2 | 1,2 |
3 | 3,4,5,6,7 |
4 | 3,4,5,6,7 |
5 | 3,4,5,6,7 |
6 | 3,4,5,6,7 |
7 | 3,4,5,6,7 |
3. Массив, сформированный после объединения меток. Здесь значение метки, которое было наименьшим для данного региона, «разливается» по всей подключенной области и дает две различные метки и, следовательно, две разные метки.
4. Конечный результат в цвете, чтобы четко видеть две разные области, которые были обнаружены в массиве.
Псевдокод является:
Алгоритм TWOPASS (данные) является connected = [] label = структура с размерами данных, инициализированная значением Background NextLabel = 0 Первый проход для строки в данных делать для столбца в строке делать, если данные [строка] [столбец] не являются фоновыми, тогда соседи = связанные элементы с текущим значением элемента если соседи будет пусто , то связаны [NextLabel] = набор , содержащий NextLabel метки [строка] [столбец] = NextLabel NextLabel + = 1 еще Найдите самую маленькую этикетку L = метки соседей этикетки [строка] [столбец] = мин (L) , для этикетки в L действительно связан [этикетка] = объединение (связанная [этикетка], L) Второй проход для строки в данных делать для столбца в строке делать, если данные [строка] [столбец] не являются фоновыми, тогда метки [строка] [столбец] = найти (метки [строка] [столбец]) вернуть этикетки
В находят и союзные алгоритмы реализованы , как описано в непересекающихся .
Последовательный алгоритм
Создать счетчик региона
Отсканируйте изображение (в следующем примере предполагается, что сканирование выполняется слева направо и сверху вниз):
- Для каждого пикселя проверьте северный и западный пиксели (при рассмотрении 4- связности ) или северо-восточный , северный , северо-западный и западный пиксели на наличие 8-связности для данного критерия региона (т.е. значение интенсивности 1 в двоичном изображении или аналогичную интенсивность для подключенных пикселей в полутоновом изображении).
- Если ни один из соседей не соответствует критерию, присвойте региону значение счетчика регионов. Счетчик региона приращения.
- Если только один сосед соответствует критерию, назначьте пиксель этой области.
- Если несколько соседей совпадают и все являются членами одного региона, назначьте пиксель их региону.
- Если несколько соседей совпадают и являются членами разных регионов, назначьте пиксель одной из областей (не имеет значения, какой из них). Укажите, что все эти регионы эквивалентны.
- Отсканируйте изображение еще раз, присвоив всем эквивалентным регионам одно и то же значение региона.
Другие
Некоторые шаги, представленные в двухпроходном алгоритме, можно объединить для повышения эффективности, что позволяет выполнять одно сканирование изображения. Также существуют многопроходные алгоритмы, некоторые из которых работают в линейном времени относительно количества пикселей изображения. [16]
В начале 1990-х годов был значительный интерес к распараллеливанию алгоритмов связанных компонентов в приложениях для анализа изображений из-за узкого места, связанного с последовательной обработкой каждого пикселя. [17]
Интерес к алгоритму снова возникает при широком использовании CUDA.
Псевдокод для покомпонентного алгоритма
Алгоритм:
- Матрица связанных компонентов инициализируется размером матрицы изображения.
- Метка инициализируется и увеличивается для каждого обнаруженного объекта на изображении.
- Инициализируется счетчик для подсчета количества объектов.
- Начнется сканирование всего изображения по строкам.
- Если пиксель объекта обнаружен, следующие шаги повторяются, пока (Индекс! = 0)
- Установите для соответствующего пикселя значение 0 в Image.
- Вектор (индекс) обновляется со всеми соседними пикселями текущих установленных пикселей.
- Уникальные пиксели сохраняются, а повторяющиеся пиксели удаляются.
- Установите пиксели, обозначенные индексом, для отметки в матрице связанных компонентов.
- Увеличьте маркер для другого объекта на изображении.
По одному компоненту ( изображение ) [M, N]: = размер ( изображение ) соединенных : = нули (M, N) знак : = разница значений : = смещения приращения : = [-1; M; 1; -M] индекс : = [] no_of_objects : = 0 for i: 1: M do for j: 1: N do if ( image (i, j) == 1) then no_of_objects : = no_of_objects + 1 index : = [((j-1) × M + i)] connected ( index ): = отметить, в то время как ~ isempty ( index ) do image ( index ): = 0 соседи : = bsxfun (@plus, index , смещения ) соседи : = уникальный ( соседи (:)) индекс : = соседи (найти ( изображение ( соседи ))) connected ( index ): = mark end while mark : = mark + difference end if end for end для
Время выполнения алгоритма зависит от размера изображения и количества переднего плана. Временная сложность сопоставима с двухпроходным алгоритмом, если передний план покрывает значительную часть изображения. В противном случае временная сложность ниже. Однако доступ к памяти менее структурирован, чем для двухпроходного алгоритма, что на практике приводит к увеличению времени выполнения.
Оценка эффективности
За последние два десятилетия было предложено много новых подходов к маркировке связанных компонентов, и почти ни один из них не сравнивался на одних и тех же данных. YACCLAB [18] [19] (аббревиатура от Another Connected Components Labeling Benchmark) является примером платформы C ++ с открытым исходным кодом, которая собирает, запускает и тестирует алгоритмы маркировки связанных компонентов.
Аппаратные архитектуры
Появление ПЛИС с достаточной емкостью для выполнения сложных задач обработки изображений также привело к появлению высокопроизводительных архитектур для маркировки подключенных компонентов. [20] [21] В большинстве этих архитектур используется однопроходный вариант этого алгоритма из-за ограниченных ресурсов памяти, доступных на ПЛИС . Эти типы архитектур маркировки подключенных компонентов могут обрабатывать несколько пикселей изображения параллельно, тем самым обеспечивая высокую пропускную способность при низкой задержке обработки.
Смотрите также
- Извлечение признаков
- Заливка
Рекомендации
- ^ Самет, H .; Тамминен, М. (1988). «Эффективная маркировка компонентов изображений произвольной размерности, представленных линейными двойными деревьями». IEEE Transactions по анализу шаблонов и машинному анализу . 10 (4): 579. DOI : 10,1109 / 34,3918 .
- ^ Майкл Б. Дилленкур; Ханнан Самет; Маркку Тамминен (1992). «Общий подход к маркировке связанных компонентов для произвольных представлений изображений». Журнал ACM . 39 (2): 253. CiteSeerX 10.1.1.73.8846 . DOI : 10.1145 / 128749.128750 .
- ^ Вэйцзе Чен; Мэриеллен Л. Гигер; Ульрих Бик (2006). «Подход на основе нечетких C-средних (FCM) для компьютерной сегментации поражений груди в МР-изображениях с динамическим контрастом». Академическая радиология . 13 (1): 63–72. DOI : 10.1016 / j.acra.2005.08.035 . PMID 16399033 .
- ^ Кешенг Ву; Венди Кеглер; Жаклин Чен; Арье Шошани (2003). «Использование индекса Bitmap для интерактивного исследования больших наборов данных» . SSDBM.
- ^ Р. Фишер; С. Перкинс; А. Уокер; Э. Вольфарт (2003). «Маркировка подключенных компонентов» .
- ^ Розенфельд, Азриэль; Пфальц, Джон Л. (октябрь 1966 г.). «Последовательные операции в обработке цифровых изображений». J. ACM . 13 (4): 471–494. DOI : 10.1145 / 321356.321357 . ISSN 0004-5411 .
- ^ а б в Шапиро, Линда Г. (1996). «Маркировка связанных компонентов и построение графа смежности». Топологические алгоритмы обработки цифровых изображений . Машинный интеллект и распознавание образов. 19 . С. 1–30. DOI : 10.1016 / s0923-0459 (96) 80011-5 . ISBN 9780444897541.
- ^ Клайбер, Майкл Дж. (2016). Параллельная и ресурсоэффективная архитектура анализа подключенных компонентов с единым поиском для реконфигурируемого оборудования . Штутгартский университет.
- ^ а б Fu, Y .; Чен, X .; Гао, Х. (декабрь 2009 г.). Новый алгоритм анализа связанных компонентов, основанный на Max-Tree . 2009 Восьмая международная конференция IEEE по надежным, автономным и безопасным вычислениям . С. 843–844. DOI : 10,1109 / DASC.2009.150 . ISBN 978-1-4244-5420-4.
- ^ а б Grana, C .; Borghesani, D .; Santinelli, P .; Куккьяра Р. (август 2010 г.). Маркировка высокопроизводительных подключаемых компонентов на ПЛИС . 2010 Семинары по приложениям баз данных и экспертных систем . С. 221–225. DOI : 10.1109 / DEXA.2010.57 . ISBN 978-1-4244-8049-4.
- ^ Винсент, Люк; Сойль, Пьер (июнь 1991 г.). «Водоразделы в цифровых пространствах: эффективный алгоритм на основе иммерсионного моделирования». IEEE Transactions по анализу шаблонов и машинному анализу . 13 (6): 583. DOI : 10,1109 / 34,87344 .
- ^ Абубакер, А; Qahwaji, R; Ипсон, S; Салех, М (2007). Методика маркировки подключенных компонентов за одно сканирование . Обработка сигналов и связь, 2007. ICSPC 2007. Международная конференция IEEE . п. 1283. DOI : 10,1109 / ICSPC.2007.4728561 . ISBN 978-1-4244-1235-8.
- ^ Шапиро, Л .; Штокман, Г. (2002). Компьютерное зрение (PDF) . Прентис Холл. С. 69–73.
- ^ Введение в алгоритмы , [1] , pp498
- ^ Lifeng He; Юян Чао; Судзуки, К. (1 мая 2008 г.). «Алгоритм маркировки с двумя сканированиями на основе прогона». IEEE Transactions по обработке изображений . 17 (5): 749–756. Bibcode : 2008ITIP ... 17..749H . DOI : 10.1109 / TIP.2008.919369 . PMID 18390379 .
- ^ Кенджи Судзуки; Исао Хориба; Нобору Суги (2003). «Маркировка связных компонентов в линейном времени на основе последовательных локальных операций». Компьютерное зрение и понимание изображений . 89 : 1–23. DOI : 10.1016 / S1077-3142 (02) 00030-9 .
- ^ Yujie Han; Роберт А. Вагнер (1990). «Эффективный и быстрый компонентный алгоритм с параллельным подключением». Журнал ACM . 37 (3): 626. DOI : 10,1145 / +79147,214077 .
- ^ Grana, C .; Болелли, Ф .; Baraldi, L .; Веццани, Р. (2016). «YACCLAB - еще один тест для маркировки подключенных компонентов» (PDF) . 23-я Международная конференция по распознаванию образов . Канкун.
- ^ «Еще один тест для маркировки подключенных компонентов: Prittt / YACCLAB» . 2019-02-18.
- ^ Бейли, генеральный директор; Джонстон, Коннектикут; Ма, Ни (сентябрь 2008 г.). Анализ связанных компонентов потоковых изображений . 2008 Международная конференция по программируемой логике и приложениям . С. 679–682. DOI : 10.1109 / FPL.2008.4630038 . ISBN 978-1-4244-1960-9.
- ^ MJ Klaiber; Д. Г. Бейли; Ю. Баруд; С. Саймон (2015). «Ресурсоэффективная аппаратная архитектура для анализа подключенных компонентов». IEEE Transactions on Circuits and Systems for Video Technology . 26 (7): 1334–1349. DOI : 10.1109 / TCSVT.2015.2450371 .
Общий
- Хорн, Бертольд КП (1986). Зрение робота . MIT Press . С. 69–71 . ISBN 978-0-262-08159-7.
Внешние ссылки
- Реализация на C #
- об извлечении объектов из изображения и алгоритме маркировки компонентов с прямым подключением