Маркировка подключенных компонентов
Маркировка связанных компонентов ( 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) ниже). Метод определения связанного списка определяет использование в глубину или в ширину поиска . Для этого конкретного приложения нет никакой разницы, какую стратегию использовать. Самый простой вид очереди «последним пришел — первым обслужен» , реализованный в виде односвязного списка, приведет к стратегии поиска в глубину.
Предполагается, что входное изображение представляет собой двоичное изображение , в котором пиксели являются либо фоновым, либо передним планом, и что желательны связанные компоненты в пикселях переднего плана. Шаги алгоритма можно записать так:
- Начните с первого пикселя изображения. Установите текущую метку на 1. Перейдите к (2).
- Если этот пиксель является пикселем переднего плана и он еще не помечен, присвойте ему текущую метку и добавьте его в качестве первого элемента в очереди, затем перейдите к (3). Если это фоновый пиксель или он уже был помечен, повторите (2) для следующего пикселя изображения.
- Извлеките элемент из очереди и посмотрите на его соседей (на основе любого типа подключения). Если сосед является пикселем переднего плана и еще не помечен, присвойте ему текущую метку и добавьте в очередь. Повторяйте (3), пока в очереди не останется элементов.
- Перейдите к (2) для следующего пикселя изображения и увеличьте текущую метку на 1.
Обратите внимание, что пиксели помечаются перед помещением в очередь. В очереди будет храниться только пиксель для проверки его соседей и добавления их в очередь при необходимости. Этот алгоритм должен проверять соседей каждого пикселя переднего плана только один раз и не проверяет соседей пикселей заднего плана.
Псевдокод :
algorithm OneComponentAtATime(data)
input : imageData[xDim][yDim]
initialization : label = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = false, queue1, queue2;
for i = 0 to xDim do
for j = 0 to yDim do
if imageData[i][j] has not been processed do
if imageData[i][j] is a foreground pixel do
check it four neighbors(north, south, east, west) :
if neighbor is not processed do
if neighbor is a foreground pixel do
add it to the queue1
else
update its status as processed
end if
labelArray[i][j] = label (give label)
statusArray[i][j] = true (update status)
While queue1 is not empty do
For each pixel in the queue do :
check it fours neighbors
if neighbor is not processed do
if neighbor is a foreground pixel do
add it to the queue2
else
update its status as processed
end if
give it the current label
update its status as processed
remove the current element from queue1
copy queue2 into queue1
end While
increase the label
end if
else
update its status as processed
end if
end if
end if
end for
end for
Двухпроходной
[ редактировать ]Относительно простой в реализации и понимании двухпроходный алгоритм. [13] (также известный как алгоритм Хошена-Копельмана ) выполняет итерацию по двумерным двоичным данным. Алгоритм выполняет два прохода по изображению: первый проход для присвоения временных меток и записи эквивалентности, а второй проход для замены каждой временной метки наименьшей меткой ее класса эквивалентности.
Входные данные могут быть изменены на месте (что сопряжено с риском повреждения данных ), либо информация маркировки может сохраняться в дополнительной структуре данных.
Проверки связности осуществляются путем проверки меток соседних пикселей (соседние элементы, метки которых еще не назначены, игнорируются), или, скажем, северо-восток, север, северо-запад и запад текущего пикселя (при условии 8- возможность подключения). 4-связность использует только северных и западных соседей текущего пикселя. Следующие условия проверяются для определения значения метки, которая будет присвоена текущему пикселю (предполагается 4-связность)
Условия проверки:
- Имеет ли пиксель слева (запад) то же значение, что и текущий пиксель?
- Да , мы находимся в одном регионе. Присвойте ту же метку текущему пикселю
- Нет – проверьте следующее условие
- Оба пикселя к северу и западу от текущего пикселя имеют то же значение, что и текущий пиксель, но не ту же метку?
- Да . Мы знаем, что северный и западный пиксели принадлежат одному региону и должны быть объединены. Назначьте текущему пикселю минимум меток севера и запада и запишите их отношение эквивалентности.
- Нет – проверьте следующее условие
- Имеет ли пиксель слева (запад) другое значение, а пиксель севернее — то же значение, что и текущий пиксель?
- Да – назначить метку северного пикселя текущему пикселю.
- Нет – проверьте следующее условие
- Имеют ли северные и западные соседи пикселя значения пикселей, отличные от значений текущего пикселя?
- Да – создайте новый идентификатор метки и присвойте его текущему пикселю.
Алгоритм продолжает работать в том же духе и при необходимости создает новые метки регионов. Однако ключом к быстрому алгоритму является то, как осуществляется это слияние. Этот алгоритм использует структуру данных объединения-поиска , которая обеспечивает превосходную производительность для отслеживания отношений эквивалентности. [14] Функция Union-find по сути хранит метки, соответствующие одному и тому же BLOB-объекту, в структуре данных с непересекающимся набором , что позволяет легко запомнить эквивалентность двух меток с помощью метода интерфейса. Например: 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. Окончательный результат окрашен в цвет, чтобы четко видеть две разные области, обнаруженные в массиве.
Псевдокод :
algorithm TwoPass(data) is
linked = []
labels = structure with dimensions of data, initialized with the value of Background
NextLabel = 0
First pass
for row in data do
for column in row do
if data[row][column] is not Background then
neighbors = connected elements with the current element's value
if neighbors is empty then
linked[NextLabel] = set containing NextLabel
labels[row][column] = NextLabel
NextLabel += 1
else
Find the smallest label
L = neighbors labels
labels[row][column] = min(L)
for label in L do
linked[label] = union(linked[label], L)
Second pass
for row in data do
for column in row do
if data[row][column] is not Background then
labels[row][column] = find(labels[row][column])
return labels
Алгоритмы поиска и объединения реализованы, как описано в Union find .
Последовательный алгоритм
[ редактировать ]Создать счетчик региона
Сканируем изображение (в следующем примере предполагается, что сканирование производится слева направо и сверху вниз):
- Для каждого пикселя проверьте северный и западный пиксель (при рассмотрении 4- связности ) или северо-восточный , северный , северо-западный и западный пиксели на 8-связность для данного критерия региона (т. е. значение интенсивности 1 в бинарном изображении или интенсивность, аналогичную связанных пикселей в полутоновом изображении).
- Если ни один из соседей не соответствует критерию, присвойте региону значение счетчика региона. Увеличение счетчика региона.
- Если только один сосед соответствует критерию, назначьте пиксель этой области.
- Если несколько соседей совпадают и все являются членами одного региона, назначьте пиксель их региону.
- Если несколько соседей совпадают и являются членами разных регионов, назначьте пиксель одному из регионов (неважно, какому). Укажите, что все эти области эквивалентны.
- Сканируйте изображение еще раз, присвоив всем эквивалентным регионам одно и то же значение региона.
Другие
[ редактировать ]Некоторые шаги, присутствующие в двухпроходном алгоритме, могут быть объединены для повышения эффективности, что позволяет выполнить один проход по изображению. Также существуют многопроходные алгоритмы, некоторые из которых работают за линейное время относительно количества пикселей изображения. [16]
В начале 1990-х годов существовал значительный интерес к распараллеливанию алгоритмов связанных компонентов в приложениях анализа изображений из-за узких мест, связанных с последовательной обработкой каждого пикселя. [17]
Интерес к алгоритму вновь возникает при широком использовании CUDA.
Псевдокод для покомпонентного алгоритма
[ редактировать ] |
Алгоритм:
- Матрица связных компонентов инициализируется размером матрицы изображения.
- Метка инициализируется и увеличивается для каждого обнаруженного объекта на изображении.
- Счетчик инициализируется для подсчета количества объектов.
- Сканирование по строкам запускается для всего изображения.
- Если пиксель объекта обнаружен, то следующие шаги повторяются, пока (Индекс !=0)
- Установите для соответствующего пикселя значение 0 в изображении.
- Вектор (индекс) обновляется всеми соседними пикселями текущего набора пикселей.
- Уникальные пиксели сохраняются, а повторяющиеся пиксели удаляются.
- Установите пиксели, указанные индексом, для отметки в матрице связанных компонентов.
- Увеличьте маркер для другого объекта на изображении.
One-Component-at-a-Time(image)
[M, N] := size(image)
connected := zeros(M, N)
mark := value
difference := increment
offsets := [-1; M; 1; -M]
index := []
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) := mark
while ~isempty(index) do
image(index) := 0
neighbors := bsxfun(@plus, index, offsets)
neighbors := unique(neighbors(:))
index := neighbors(find(image(neighbors)))
connected(index) := mark
end while
mark := mark + difference
end if
end for
end for
Время работы алгоритма зависит от размера изображения и количества переднего плана. Временная сложность сравнима с двухпроходным алгоритмом, если передний план покрывает значительную часть изображения. В противном случае временная сложность будет ниже. Однако доступ к памяти менее структурирован, чем для двухпроходного алгоритма, что на практике имеет тенденцию увеличивать время выполнения.
Оценка эффективности
[ редактировать ]За последние два десятилетия было предложено множество новых подходов к маркировке связанных компонентов, но почти ни один из них не подвергался сравнительной оценке эффективности с использованием одного и того же набора данных. ЯККЛАБ [18] [19] (аббревиатура от «Еще один эталон маркировки связанных компонентов») — это пример среды C++ с открытым исходным кодом, которая собирает, запускает и тестирует алгоритмы маркировки связанных компонентов.
Аппаратные архитектуры
[ редактировать ]Появление FPGA с достаточной мощностью для выполнения сложных задач по обработке изображений также привело к появлению высокопроизводительных архитектур для маркировки связанных компонентов. [20] [21] В большинстве этих архитектур используется однопроходный вариант этого алгоритма из-за ограниченных ресурсов памяти, доступных на FPGA . Эти типы архитектур маркировки связанных компонентов могут обрабатывать несколько пикселей изображения параллельно, обеспечивая тем самым высокую пропускную способность и низкую задержку обработки.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Самет, Х.; Тамминен, М. (1988). «Эффективная маркировка компонентов изображений произвольной размерности, представленных линейными двоичными деревьями». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 10 (4): 579. дои : 10.1109/34.3918 . S2CID 15911227 .
- ^ Майкл Б. Дилленкур; Ханнан Самет; Маркку Тамминен (1992). «Общий подход к маркировке связных компонентов для произвольных представлений изображений». Журнал АКМ . 39 (2): 253. CiteSeerX 10.1.1.73.8846 . дои : 10.1145/128749.128750 . S2CID 1869184 .
- ^ Вейцзе Чен; Мэриеллен Л. Гигер; Ульрих Бик (2006). «Подход на основе нечетких C-средних (FCM) для компьютерной сегментации образований молочной железы на МР-изображениях с динамическим контрастированием». Академическая радиология . 13 (1): 63–72. дои : 10.1016/j.acra.2005.08.035 . ПМИД 16399033 .
- ^ Кешэн Ву; Венди Кеглер; Жаклин Чен; Арье Шошани (2003). «Использование растрового индекса для интерактивного исследования больших наборов данных» . ССДБМ.
- ^ Р. Фишер; С. Перкинс; А. Уокер; Э. Вольфарт (2003). «Маркировка подключенных компонентов» .
- ^ Розенфельд, Азриэль; Пфальц, Джон Л. (октябрь 1966 г.). «Последовательные операции цифровой обработки изображений». Дж. АКМ . 13 (4): 471–494. дои : 10.1145/321356.321357 . ISSN 0004-5411 . S2CID 7391071 .
- ^ Перейти обратно: а б с Шапиро, Линда Г. (1996). «Маркировка связанных компонентов и построение графа смежности». Топологические алгоритмы цифровой обработки изображений . Машинный интеллект и распознавание образов. Том. 19. стр. 1–30. дои : 10.1016/s0923-0459(96)80011-5 . ISBN 9780444897541 .
- ^ Клайбер, Майкл Дж. (2016). Параллельная и ресурсоэффективная архитектура анализа связанных компонентов с единым поиском для реконфигурируемого оборудования . Университет Штутгарта.
- ^ Перейти обратно: а б Фу, Ю.; Чен, X.; Гао, Х. (декабрь 2009 г.). «Новый алгоритм анализа связанных компонентов на основе Max-Tree». 2009 г. Восьмая международная конференция IEEE по надежным, автономным и безопасным вычислениям . стр. 843–844. дои : 10.1109/DASC.2009.150 . ISBN 978-1-4244-5420-4 . S2CID 6805048 .
- ^ Перейти обратно: а б Грана, К.; Боргесани, Д.; Сантинелли, П.; Куккьяра, Р. (август 2010 г.). «Высокопроизводительная маркировка подключенных компонентов на FPGA». 2010 Семинары по приложениям баз данных и экспертных систем . стр. 221–225. дои : 10.1109/DEXA.2010.57 . ISBN 978-1-4244-8049-4 . S2CID 6905027 .
- ^ Винсент, Люк; Сойль, Пьер (июнь 1991 г.). «Водоразделы в цифровых пространствах: эффективный алгоритм, основанный на моделировании погружения». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 13 (6): 583. дои : 10.1109/34.87344 . S2CID 15436061 .
- ^ Абубакер, А; Кахваджи, Р; Ипсон, С; Салех, М (2007). «Техника маркировки соединенных компонентов за одно сканирование». 2007 Международная конференция IEEE по обработке сигналов и связи . п. 1283. дои : 10.1109/ICSPC.2007.4728561 . ISBN 978-1-4244-1235-8 . S2CID 10710012 .
- ^ Шапиро, Л.; Стокман, Г. (2002). Компьютерное зрение (PDF) . Прентис Холл. стр. 69–73.
- ^ Введение в алгоритмы , [1] , стр. 498.
- ^ Лифэн Хэ; Юян Чао; Сузуки, К. (1 мая 2008 г.). «Алгоритм маркировки с двумя сканированиями на основе прогона». Транзакции IEEE при обработке изображений . 17 (5): 749–756. Бибкод : 2008ITIP...17..749H . дои : 10.1109/TIP.2008.919369 . ПМИД 18390379 .
- ^ Кенджи Сузуки; Исао Хориба; Нобору Суги (2003). «Маркировка связанных компонентов в линейном времени на основе последовательных локальных операций». Компьютерное зрение и понимание изображений . 89 : 1–23. дои : 10.1016/S1077-3142(02)00030-9 .
- ^ Юджи Хан; Роберт А. Вагнер (1990). «Эффективный и быстрый алгоритм параллельно-связных компонентов» . Журнал АКМ . 37 (3): 626. дои : 10.1145/79147.214077 . S2CID 17867876 .
- ^ Грана, К.; Болелли, Ф.; Баральди, Л.; Веццани, Р. (2016). «YACCLAB — еще один эталон маркировки подключенных компонентов» (PDF) . 23-я Международная конференция по распознаванию образов . Канкун.
- ^ «Еще один эталон маркировки подключенных компонентов: Prittt/YACCLAB» . Гитхаб . 18 февраля 2019 г.
- ^ Бейли, генеральный директор; Джонстон, Коннектикут; Ма, Ни (сентябрь 2008 г.). «Анализ связанных компонентов потоковых изображений». Международная конференция 2008 г. по полевой программируемой логике и ее приложениям . стр. 679–682. дои : 10.1109/FPL.2008.4630038 . ISBN 978-1-4244-1960-9 . S2CID 6503327 .
- ^ М.Дж. Клайбер; Д.Г. Бэйли; Ю. Баруд; С. Саймон (2015). «Ресурсоэффективная аппаратная архитектура для анализа связанных компонентов». Транзакции IEEE по схемам и системам видеотехнологий . 26 (7): 1334–1349. дои : 10.1109/TCSVT.2015.2450371 . S2CID 10464417 .
Общий
[ редактировать ]- Хорн, Бертольд КП (1986). Видение робота . МТИ Пресс . стр. 69–71 . ISBN 978-0-262-08159-7 .
- Аль Бовик (2000). Руководство по обработке изображений и видео (PDF) . Академическая пресса . стр. [37–70]. ISBN 0-12-119790-5 .
Внешние ссылки
[ редактировать ]- Реализация на C#
- об извлечении объектов из изображения и алгоритме маркировки прямых связных компонентов
| Базы данных органов управления : Национальные |
|---|
