stringtranslate.com

Маркировка связанных компонентов

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

Маркировка связанных компонентов используется в компьютерном зрении для обнаружения связанных областей в бинарных цифровых изображениях , хотя цветные изображения и данные с более высокой размерностью также могут быть обработаны. [1] [2] При интеграции в систему распознавания изображений или интерфейс взаимодействия человек-компьютер маркировка связанных компонентов может работать с различной информацией. [3] [4] Извлечение пятен обычно выполняется на полученном бинарном изображении с этапа пороговой обработки, но оно может быть применимо также к изображениям в оттенках серого и цветным изображениям. Пятна можно подсчитывать, фильтровать и отслеживать.

Извлечение пятен связано с обнаружением пятен, но отличается от него .

Обзор

4-связность
8-связность

Граф, содержащий вершины и соединяющие ребра , строится из соответствующих входных данных. Вершины содержат информацию, требуемую эвристикой сравнения, в то время как ребра указывают на связанных «соседей». Алгоритм проходит по графу, маркируя вершины на основе связности и относительных значений их соседей. Связность определяется средой; графы изображений, например, могут быть 4-связными окрестностями или 8-связными окрестностями . [5]

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

Определение

Использование термина «маркировка связанных компонентов» (CCL) и его определение в академической литературе довольно единообразны, тогда как анализ связанных компонентов (CCA) различается как с точки зрения терминологии, так и определения проблемы.

Розенфельд и др. [6] определяют маркировку связанных компонентов как «[с]оздание маркированного изображения, в котором позиции, связанные с одним и тем же связанным компонентом двоичного входного изображения, имеют уникальную метку». Шапиро и др. [7] определяют CCL как оператор, «входом которого является двоичное изображение, а [...] выходом является символическое изображение, в котором метка, назначенная каждому пикселю, является целым числом, однозначно идентифицирующим связанный компонент, к которому принадлежит этот пиксель». [8]

В академической литературе нет единого мнения об определении CCA. Его часто используют как взаимозаменяемый термин с CCL. [9] [10] Более обширное определение дано Шапиро и др.: [7] «Анализ связанных компонентов состоит из маркировки связанных компонентов черных пикселей с последующим измерением свойств областей компонентов и принятием решений». Представленное здесь определение анализа связанных компонентов является более общим и учитывает мысли, высказанные в [ 7] [9] [10] .

Алгоритмы

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

Один компонент за раз

Это быстрый и очень простой в реализации и понимании метод. Он основан на методах обхода графа в теории графов. Короче говоря, как только найден первый пиксель связанного компонента, все связанные пиксели этого связанного компонента маркируются перед переходом к следующему пикселю на изображении. Этот алгоритм является частью алгоритма сегментации водораздела Винсента и Сойля , [11] существуют и другие реализации. [12]

Для этого формируется связанный список , который будет хранить индексы пикселей, связанных друг с другом, шаги (2) и (3) ниже. Метод определения связанного списка определяет использование поиска в глубину или в ширину . Для этого конкретного приложения нет разницы, какую стратегию использовать. Простейший вид очереди «последний пришел — первый вышел» , реализованный как односвязный список, приведет к стратегии поиска в глубину.

Предполагается, что входное изображение является бинарным изображением , в котором пиксели являются либо фоном, либо передним планом, и что нужны связанные компоненты в пикселях переднего плана. Шаги алгоритма можно записать как:

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

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

Псевдокод : ​

 алгоритм 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-связность):

Условия для проверки:

  1. Имеет ли пиксель слева (на западе) то же значение, что и текущий пиксель?
    1. Да – Мы в одном регионе. Назначить ту же метку текущему пикселю
    2. Нет – Проверьте следующее условие
  2. Имеют ли оба пикселя к северу и западу от текущего пикселя то же значение, что и текущий пиксель, но не ту же метку?
    1. Да – Мы знаем, что северный и западный пиксели принадлежат к одному региону и должны быть объединены. Назначьте текущему пикселю минимум из меток севера и запада и запишите их отношение эквивалентности
    2. Нет – Проверьте следующее условие
  3. Имеет ли пиксель слева (на западе) другое значение, а пиксель севернее — то же значение, что и текущий пиксель?
    1. Да — назначить метку северного пикселя текущему пикселю
    2. Нет – Проверьте следующее условие
  4. Имеют ли северные и западные соседи пикселя другие значения пикселей, чем текущий пиксель?
    1. Да — создайте новый идентификатор метки и назначьте его текущему пикселю.

Алгоритм продолжает работать таким образом и создает новые метки регионов по мере необходимости. Однако ключ к быстрому алгоритму заключается в том, как выполняется это слияние. Этот алгоритм использует структуру данных union-find , которая обеспечивает превосходную производительность для отслеживания отношений эквивалентности. [14] Union-find по сути хранит метки, которые соответствуют одному и тому же блобу, в структуре данных disjoint-set , что упрощает запоминание эквивалентности двух меток с помощью метода интерфейса, например: findSet(l). findSet(l) возвращает минимальное значение метки, которое эквивалентно аргументу функции 'l'.

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

Ниже представлен более быстрый алгоритм сканирования для извлечения связанных областей. [15]

При первом проходе:

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

На втором проходе:

  1. Пройтись по каждому элементу данных по столбцу, затем по строке.
  2. Если элемент не является фоном
    1. Переименуйте элемент, указав наименьшую эквивалентную метку.

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

Графический пример двухпроходного алгоритма

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.

Псевдокод для алгоритма «по одному компоненту за раз»

Алгоритм:

  1. Матрица связанных компонентов инициализируется размером матрицы изображения.
  2. Метка инициализируется и увеличивается для каждого обнаруженного объекта на изображении.
  3. Инициализируется счетчик для подсчета количества объектов.
  4. Начинается сканирование по строкам всего изображения.
  5. Если обнаружен пиксель объекта, то следующие шаги повторяются, пока (Индекс !=0)
    1. Установите соответствующий пиксель на 0 в изображении.
    2. Вектор (индекс) обновляется всеми соседними пикселями текущего набора пикселей.
    3. Уникальные пиксели сохраняются, а повторяющиеся пиксели удаляются.
    4. Установите пиксели, указанные индексом, для маркировки в матрице связанных компонентов.
  6. Увеличьте маркер для другого объекта на изображении.
По одному компоненту за раз ( изображение ) [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] Большинство этих архитектур используют однопроходный вариант этого алгоритма из-за ограниченных ресурсов памяти, доступных на ПЛИС . Эти типы архитектур маркировки связанных компонентов могут обрабатывать несколько пикселей изображения параллельно, тем самым достигая высокой пропускной способности и низкой задержки обработки.

Смотрите также

Ссылки

  1. ^ Samet, H.; Tamminen, M. (1988). «Эффективная маркировка компонентов изображений произвольной размерности, представленных линейными двоичными деревьями». Труды IEEE по анализу образов и машинному интеллекту . 10 (4): 579. doi :10.1109/34.3918. S2CID  15911227.
  2. ^ Майкл Б. Дилленкурт; Ханнан Самет; Маркку Тамминен (1992). «Общий подход к маркировке связанных компонентов для произвольных представлений изображений». Журнал ACM . 39 (2): 253. CiteSeerX 10.1.1.73.8846 . doi :10.1145/128749.128750. S2CID  1869184. 
  3. ^ Weijie Chen; Maryellen L. Giger; Ulrich Bick (2006). «Подход на основе нечетких C-средних (FCM) для компьютерной сегментации поражений молочной железы на динамических контрастных МР-изображениях». Academic Radiology . 13 (1): 63–72. doi :10.1016/j.acra.2005.08.035. PMID  16399033.
  4. ^ Кешенг Ву; Венди Кеглер; Жаклин Чен; Ари Шошани (2003). «Использование индекса Bitmap для интерактивного исследования больших наборов данных». SSDBM.
  5. ^ Р. Фишер; С. Перкинс; А. Уокер; Э. Вольфарт (2003). «Маркировка связанных компонентов».
  6. ^ Розенфельд, Азриэль; Пфальц, Джон Л. (октябрь 1966 г.). «Последовательные операции в цифровой обработке изображений». J. ACM . 13 (4): 471–494. doi :10.1145/321356.321357. ISSN  0004-5411. S2CID  7391071.
  7. ^ abc Шапиро, Линда Г. (1996). «Маркировка связанных компонентов и построение графа смежности». Топологические алгоритмы цифровой обработки изображений . Машинный интеллект и распознавание образов. Том 19. С. 1–30. doi :10.1016/s0923-0459(96)80011-5. ISBN 9780444897541.
  8. ^ Клайбер, Майкл Дж. (2016). Параллельная и ресурсоэффективная архитектура анализа связанных компонентов с единым поиском для реконфигурируемого оборудования . Штутгартский университет.
  9. ^ ab Fu, Y.; Chen, X.; Gao, H. (декабрь 2009 г.). "Новый алгоритм анализа связанных компонентов на основе Max-Tree". Восьмая международная конференция IEEE по надежным, автономным и безопасным вычислениям 2009 г. стр. 843–844. doi :10.1109/DASC.2009.150. ISBN 978-1-4244-5420-4. S2CID  6805048.
  10. ^ ab Grana, C.; Borghesani, D.; Santinelli, P.; Cucchiara, R. (август 2010 г.). «Высокопроизводительная маркировка связанных компонентов на ПЛИС». Практикумы 2010 г. по приложениям баз данных и экспертных систем . стр. 221–225. doi :10.1109/DEXA.2010.57. ISBN 978-1-4244-8049-4. S2CID  6905027.
  11. ^ Винсент, Люк; Сойль, Пьер (июнь 1991 г.). «Водоразделы в цифровых пространствах: эффективный алгоритм, основанный на имитационном моделировании погружения». Труды IEEE по анализу шаблонов и машинному интеллекту . 13 (6): 583. doi :10.1109/34.87344. S2CID  15436061.
  12. ^ Абубакер, А.; Кахваджи, Р.; Ипсон, С.; Салех, М. (2007). «Метод маркировки подключенных компонентов одним сканированием». Международная конференция IEEE по обработке сигналов и коммуникациям 2007 г. стр. 1283. doi :10.1109/ICSPC.2007.4728561. ISBN 978-1-4244-1235-8. S2CID  10710012.
  13. ^ Шапиро, Л.; Стокман, Г. (2002). Компьютерное зрение (PDF) . Prentice Hall. стр. 69–73.
  14. ^ Введение в алгоритмы , [1], стр. 498
  15. ^ Lifeng He; Yuyan Chao; Suzuki, K. (1 мая 2008 г.). «Алгоритм двухскановой маркировки на основе прогона». Труды IEEE по обработке изображений . 17 (5): 749–756. Bibcode : 2008ITIP...17..749H. doi : 10.1109/TIP.2008.919369. PMID  18390379.
  16. ^ Кэндзи Судзуки; Исао Хориба; Нобору Суги (2003). «Линейная маркировка связанных компонентов на основе последовательных локальных операций». Компьютерное зрение и понимание изображений . 89 : 1–23. doi :10.1016/S1077-3142(02)00030-9.
  17. ^ Юйцзе Хан; Роберт А. Вагнер (1990). «Эффективный и быстрый алгоритм параллельно соединенных компонентов». Журнал ACM . 37 (3): 626. doi : 10.1145/79147.214077 . S2CID  17867876.
  18. ^ Грана, К.; Болелли, Ф.; Баральди, Л.; Веццани, Р. (2016). "YACCLAB - еще один эталон маркировки связанных компонентов" (PDF) . 23-я Международная конференция по распознаванию образов . Канкун.
  19. ^ «Еще один тест маркировки подключенных компонентов: Prittt/YACCLAB». GitHub . 2019-02-18.
  20. ^ Бейли, Д.Г.; Джонстон, КТ; Ма, Ни (сентябрь 2008 г.). «Анализ связанных компонентов потоковых изображений». Международная конференция по программируемой логике и приложениям 2008 г. . стр. 679–682. doi :10.1109/FPL.2008.4630038. ISBN 978-1-4244-1960-9. S2CID  6503327.
  21. ^ MJ Klaiber; DG Bailey; Y. Baroud; S. Simon (2015). «Ресурсоэффективная аппаратная архитектура для анализа связанных компонентов». Труды IEEE по схемам и системам для видеотехнологий . 26 (7): 1334–1349. doi :10.1109/TCSVT.2015.2450371. S2CID  10464417.

Общий

Внешние ссылки