Комментарии 22
Программу не возможно загрузить с Вашего сайта! Хотелось бы увидеть результаты и резюме относительно результатов в статье. Еще не плохо рассказать о проблемах алгоритма и случаи, когда его целесообразно применять. Все таки для новичков хотите написать.
Спасибо. Ссылку исправил.
Алгоритма меток:
+ Не только подсчитываем объекты, но и отделяем их друг от друга (т.е. сегментируем изображение).
+ Простота и интуитивность алгоритма
— Медленный
— Тяжело реализуется на ПЛИС
Алгоритм углов:
+ Очень быстрый
+ Легко реализуется на ПЛИС
— Объекты не должны содержать внутренних отверстий
Т.о. смысл использовать метки есть только тогда, когда нам необходимо не просто подсчитать количество объектов, но и выделить их. Алгоритм углов используется только дл быстрого подсчёте количества объектов.
Алгоритма меток:
+ Не только подсчитываем объекты, но и отделяем их друг от друга (т.е. сегментируем изображение).
+ Простота и интуитивность алгоритма
— Медленный
— Тяжело реализуется на ПЛИС
Алгоритм углов:
+ Очень быстрый
+ Легко реализуется на ПЛИС
— Объекты не должны содержать внутренних отверстий
Т.о. смысл использовать метки есть только тогда, когда нам необходимо не просто подсчитать количество объектов, но и выделить их. Алгоритм углов используется только дл быстрого подсчёте количества объектов.
Нетрудно заметить, что этот алгоритм использует рекурсию, а значит, у нас возникает две потенциальных проблемы. Во-первых, скорость работы алгоритма может быть недостаточной для обработки данных в реальном времени, во-вторых, потенциально нам может не хватать размера стека, особенно, если мы говорим о реализации этого алгоритма в железе (ПЛИС).Достаточно заменить поиск в глубину поиском в ширину и можно обойтись без рекурсии.
Время работы от этого не уменьшится, и нам всё равно придётся где-то хранить список связных точек. Но идея хороша. Спасибо.
Не совсем так. Конечно очередь нам все равно нужна, но памяти она будет занимать намного меньше чем стек в случае рекурсии. Например в крайнем случае, когда вся картинка размером NxM будет залита одним цветом, в случае поиска в глубину нам понадобится стек глубиной N*M, тогда как максимальный размер очереди в поиске в ширину в этом случае будет чуть больше чем min(N, M). Реализовать очередь, зная, что в ней никогда не будет больше чем определенное количество элементов, очень просто, например с помощью циклического буфера в памяти.
По времени — поиск это тоже один проход по изображению, поэтому я не понимаю почему углы будут быстрее. По памяти, да у них есть небольшое преимущество. Зато у поиска есть другое преимущество: можно сразу выделить связанные области и пометить их разными «цветами», попутно еще и определив размер каждой области.
По времени — поиск это тоже один проход по изображению, поэтому я не понимаю почему углы будут быстрее. По памяти, да у них есть небольшое преимущество. Зато у поиска есть другое преимущество: можно сразу выделить связанные области и пометить их разными «цветами», попутно еще и определив размер каждой области.
Пометка и определение размера — очень важные достоинства. Согласен, но мы говорим только о подсчёте количества объектов. А выигрыш вот в чём. Пусть у нас есть изображение N*M, залитое одним цветом, используя алгоритм меток нам потребуется дважды пройтись по нему: первый раз при пометке, начатой в пикселе [1;1], а второй раз при проверке всех остальных пикселей. В некоторых задачах двукратный выигрыш в скорости обхода может быть существенным. И ещё одно, это аппаратная реализация. Если мы используем метки, то для кодирования каждого пиксела нужно log2(<максимальное количество объектов>) бит, а в методе углов можно пользоваться простым правилом: 1 пиксел — 1 бит.
— Ещё раз спасибо за замечания. Потом попробую реализовать поиск в ширину и сравню производительность.
— Ещё раз спасибо за замечания. Потом попробую реализовать поиск в ширину и сравню производительность.
Для использования алгоритма углов обязательно, чтобы все углы объектов были прямыми?
Второй алгоритм не работает когда все поле представляет собой один объект:)
Что в принципе довольно ожидаемо. Должен существовать фон, шириной хотя бы в 1 пиксел.
+1 необходима какая-то детекция фона, тогда можно было бы задуматься о корректности определения и «дырчатых» объектов.
Для подсчета количества объектов можно еще использовать алгоритм заливки (почти как метод марок, только нерекурсивный). Наткнулись на непомеченный пиксель — увеличиваем счетчик и заливаем всю область, что объект занимает, фоновым цветом.
Не совсем понимаю этот метод. А как мы узнаём границы объекта, когда он состоит более чем из одного пиксела?
Вот реализованный мной несколько лет назад алгоритм заливки (он тут как вспомогательный)
Основное его предназначение — вычисление центра масс всех найденных объектов на изображении. Для обработки я всё изображение переводил в ч/б массив (массив булеанов), а затем выделял в нем объекты. Под цветное изображение труда не будет переделать.
Прошу прощения за делфи. Ну суть понятна, я думаю, комментарии есть. Что-то непонятно — обращайтесь, распишу
Основное его предназначение — вычисление центра масс всех найденных объектов на изображении. Для обработки я всё изображение переводил в ч/б массив (массив булеанов), а затем выделял в нем объекты. Под цветное изображение труда не будет переделать.
procedure TRgbBmp.CalcMassCentre4(var BoolArr: TBoolArray);
var
// ...
begin
// ... инициализации
// Алгоритм заполнения произвольной области с затравкой
// Преобразован для нахождения центра масс -
// Координаты всех "залитых" точек суммируются и делятся на площадь
for i := 1 to FHeightMinus1 - 1 do
for j := 1 to FWidthMinus1 - 1 do
// Как только натыкаемся на непомеченный пиксель - запускаем алгоритм заливки
if TmpBoolArr[i, j] then
begin
SumX := 0;
SumY := 0;
N := 0;
Top := 0;
// Добавляем в стек текущие координаты
Stack[Top] := ToCoord(i, j);
// пока стек не пуст
while Top <> -1 do
begin
// извлекаем из стека координаты
Curr := Stack[Top];
Dec(Top);
// помечаем текущую точку
if TmpBoolArr[Curr.y, Curr.x] then
begin
TmpBoolArr[Curr.y, Curr.x] := False;
CoordAdd(Curr.y, Curr.x, SumY, SumX, N);
end;
// заливаем все пиксели слева
xl := Curr.x - 1;
while TmpBoolArr[Curr.y, xl] do
begin
TmpBoolArr[Curr.y, xl] := False;
CoordAdd(Curr.y, xl, SumY, SumX, N);
Dec(xl);
end;
// заливаем все пиксели справа
xr := Curr.x + 1;
while TmpBoolArr[Curr.y, xr] do
begin
TmpBoolArr[Curr.y, xr] := False;
CoordAdd(Curr.y, xr, SumY, SumX, N);
Inc(xr);
end;
Dec(xr);
// идем вниз и вверх
k := 1;
repeat
y := Curr.y + k;
x := xl + 1;
// добавляем еще одну строчку для следующей итерации
while x < xr do
begin
x0 := x;
while (TmpBoolArr[y, x]) and (x < xr) do
Inc(x);
if x0 <> x then
begin
Inc(Top);
Stack[Top] := ToCoord(y, x);
end;
while (not TmpBoolArr[y, x]) and (x < xr) do
Inc(x);
end;
// для верхней строки
k := k - 2;
until
k < -1;
end;
// Если объект маленький (3 и меньше пикселей), то его не учитываем
if N > 3 then
begin
MassCentre.Y := Trunc(SumY / N);
MassCentre.X := Trunc(SumX / N);
MasscentreArr[MassCentre.y, MassCentre.x] := True;
end;
end;
// ...
end;
Прошу прощения за делфи. Ну суть понятна, я думаю, комментарии есть. Что-то непонятно — обращайтесь, распишу
Один из алгоритмов заливки — «заливка с затравкой». Возьмет любой объект (хоть бублик), а не только прямоугольный. А границы мы узнаем, когда зальем — алгоритм изначально под это не приспособлен, но можно подправить. В итоге получается тоже самое, что и метод марок, только эффективние и без рекурсии.
Вот его реализация на java — с более-менее подробными комментариями, готовый к компилированию код:
pastebin.com/WaLgEEzr
pastebin.com/WaLgEEzr
Помнится один знакомый, чтоб от него отстали требовал алгоритм распознавания зебры… Как быть, если объект высококонтрастный?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Подсчёт объектов на изображении