Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
Это все нам не подходит.
почему?
почему?
Когда мне это когда-то давно нужно было решить такую задачу на курсовой, я решил её за 5 минут путём заполнения (у вас это Fill). А вам почему-то не подходит. Почему?
Я не знаю, как можно реализовать подсчет периметра в рекурсивной версии, когда в сканирующей версии это делается очень просто вместе с остальными геометрическими характеристиками — тема второй части.
В первом приближении можно использовать периметр bounding box бинарного объекта :)
Кстати, а ваш метод с масками работает для объектов, содержащих внутренние незаполненные области?
Кстати, а ваш метод с масками работает для объектов, содержащих внутренние незаполненные области?
bounding box — тогда отличить квадрат от круга не получится, а фактор формы с точно вычисленным периметром и площадью — это позволит сделать. но об этом позже.
Да конечно, если внутри есть незаполненная область — то все так же будет работать. Для уверенности — перепроверил сейчас. Тут и число Эйлера можно вычислить вроде.
Да конечно, если внутри есть незаполненная область — то все так же будет работать. Для уверенности — перепроверил сейчас. Тут и число Эйлера можно вычислить вроде.
Разметка связных областей делается с помощью bwlabel (есть и для Scilab).
Вычисление характеристик (длина, площадь) с помощью встроенных функций (если есть) или в матричном виде, аккумулируя результаты с помощью vl_binsum, histc или подобных.
Всяко будет красивее и быстрее, чем писать циклы в Matlab/Scilab.
Вот например на днях нужно было посчитать длину общей границы между всеми парами областей: (чуть более сложная задача, чем посчитать длины границ объектов):
Не понадобился ни один цикл.
Вычисление характеристик (длина, площадь) с помощью встроенных функций (если есть) или в матричном виде, аккумулируя результаты с помощью vl_binsum, histc или подобных.
Всяко будет красивее и быстрее, чем писать циклы в Matlab/Scilab.
Вот например на днях нужно было посчитать длину общей границы между всеми парами областей: (чуть более сложная задача, чем посчитать длины границ объектов):
function adj = pairwiseBoundaryLengths(map)
% map содержит разметку изображения по областям
h = size(map, 1);
w = size(map, 2);
n = max(map(:));
% вертикальные и горизонтальные границы
% фокус - записываем для каждой границы номера граничащих областей
% но разворачиваем пару чисел в одномерный индекс, чтобы проще было потом суммировать
vertical = (map(1 : h - 1, :) - 1) * n + map(2 : h, :);
horizontal = (map(:, 1 : w - 1) - 1) * n + map(:, 2 : w);
adj = zeros(n);
adj(:) = vl_binsum(adj(:), 1, vertical(:));
adj(:) = vl_binsum(adj(:), 1, horizontal(:));
adj = adj + adj';
adj = adj .* (ones(n) - eye(n));
end
Не понадобился ни один цикл.
А ещё, у вас операция слияния областей «Image(Image == C) = B;» может оказаться дороговатой.
Проходиться при каждом слиянии по всему изображению, заменяя метки? Не дольше ли это окажется обычного dfs/bfs, который, по крайней мере, работает за линейное время? Можно использовать для быстрого объединения непересекающиеся множества, но всё равно будет долго, неподходящий язык выбран для такой задачи.
Потому и предоставляется готовая функция bwlabel, написанная на C.
Проходиться при каждом слиянии по всему изображению, заменяя метки? Не дольше ли это окажется обычного dfs/bfs, который, по крайней мере, работает за линейное время? Можно использовать для быстрого объединения непересекающиеся множества, но всё равно будет долго, неподходящий язык выбран для такой задачи.
Потому и предоставляется готовая функция bwlabel, написанная на C.
В пункте 5-ом, описания позиции маски, говорится как раз о перенумерации Image(Image == C) = B. При реальной рализации это эфективно делать с использованием указатлей — см. задачку в самом конце статьи.
> матрица указателей на специальную структуру
«специальная структура» — это система непересекающихся множеств, или что-то другое?
«специальная структура» — это система непересекающихся множеств, или что-то другое?
У меня получилось сделать однопроходный алгоритм (C++) без использования структур/множеств. Храню массив int* вместо int, и в случае, когда текущий пиксель объединяет 2 объекта (последний else у вас в коде), делаю так:
т.е. изменяю значение указателя с бОльим номером объекта на значение объекта с меньшим номером, с которым происходит объединение. Таким образом остается один (общий) объект с меньшим номером. int* в качестве ячейки позволяет изменить номер объекта для всех пикселей этого объекта без дополнительного прохода по массиву рисунка.
Конечно, для такой реализации необходимо иметь матрицу указателей, но в моем случае массив рисунка для этих нужд я использовать не мог.
int **m_labels;
...
} else {
if (*m_labels[bIndex] <= *m_labels[cIndex])
*m_labels[cIndex] = *m_labels[bIndex];
else
*m_labels[bIndex] = *m_labels[cIndex];
m_labels[index] = m_labels[bIndex];
}
т.е. изменяю значение указателя с бОльим номером объекта на значение объекта с меньшим номером, с которым происходит объединение. Таким образом остается один (общий) объект с меньшим номером. int* в качестве ячейки позволяет изменить номер объекта для всех пикселей этого объекта без дополнительного прохода по массиву рисунка.
Конечно, для такой реализации необходимо иметь матрицу указателей, но в моем случае массив рисунка для этих нужд я использовать не мог.
Пока еще не понял будет ли это работать для всех коллизий, однако идея очень интересная.
Вот к примеру пусть разметка такова, что возникают последовательно эквивалентности:
2 эквивалентно 3, затем: 3 эквивалентно 5.
1. По адресу в указателе на 2 ставится 3.
2. По адресу указывающему на на 3 ставится 5.
Таким образом коллизия не разрешена и перенумерация выполнена не полностью: осталось и 3 и 5. Когда должно остаться только 5.
Или я где-то заблуждаюсь?
Вот к примеру пусть разметка такова, что возникают последовательно эквивалентности:
2 эквивалентно 3, затем: 3 эквивалентно 5.
1. По адресу в указателе на 2 ставится 3.
2. По адресу указывающему на на 3 ставится 5.
Таким образом коллизия не разрешена и перенумерация выполнена не полностью: осталось и 3 и 5. Когда должно остаться только 5.
Или я где-то заблуждаюсь?
1. Соединяются объекты 2 и 3. Объект 3 станет объектом 2.
2. Соединяются объекты 3 и 5. Объект 5 станет объектом 2, т.к. объект 3 — уже имеет номер 2 (переименован в предыдущем шаге)
Код работает, я сейчас использую этот подход в реальном проекте (кстати, спасибо вам за отличную статью, очень своевременно для меня).
Ксати, что характерно, если не делать проверку
а делать просто
то выйдет криво (будет куча объектов вместо одного).
2. Соединяются объекты 3 и 5. Объект 5 станет объектом 2, т.к. объект 3 — уже имеет номер 2 (переименован в предыдущем шаге)
Код работает, я сейчас использую этот подход в реальном проекте (кстати, спасибо вам за отличную статью, очень своевременно для меня).
Ксати, что характерно, если не делать проверку
} else {
if (*m_labels[bIndex] <= *m_labels[cIndex])
*m_labels[cIndex] = *m_labels[bIndex];
else
*m_labels[bIndex] = *m_labels[cIndex];
m_labels[index] = m_labels[bIndex];
}
а делать просто
} else {
*m_labels[cIndex] = *m_labels[bIndex];
m_labels[index] = m_labels[bIndex];
}
то выйдет криво (будет куча объектов вместо одного).
Хм, действительно, сейчас подумал — все верно. Только не как доказать это не могу для себя. У вас есть какие-то рассуждения? Поделитесь?
А если эквивалентность вида: 2 эквивалентно 3, а 3 эквивалентно 1?
1. Соединяются объекты 2 и 3. Объект 3 станет объектом 2. Теперь указателей на тройку нет вообще.
2. Соединяются объекты 3 и 1. Объект 3 станет объектом 1. А так как указатели на тройку уже потеряны, то эта эквивалентность не обработается получается?
1. Соединяются объекты 2 и 3. Объект 3 станет объектом 2. Теперь указателей на тройку нет вообще.
2. Соединяются объекты 3 и 1. Объект 3 станет объектом 1. А так как указатели на тройку уже потеряны, то эта эквивалентность не обработается получается?
Да, вы правы. На новых рисунках отчетливо видны необъединенные объекты. Видимо, придется делать двухпроходным алгоритмом со списком множеств эквивалентных объектов
Можете это поподробнее объяснить (или картинку добавить если не очень сложно)? Никак понять не могу.
Я сейчас как раз делаю так же с матрицей указателей. Ошибка возникает, а причина до конца неясна.
Я сейчас как раз делаю так же с матрицей указателей. Ошибка возникает, а причина до конца неясна.
Пусть изображение представляется матрицей, где в каждой ячейке — указатель на номер объекта, которому принадлежит эта ячейка.
Все номера хранятся в отдельном массиве — выделенном предварительно и с некоторым запасом, так как неизвестно сколько объектов на картинке.
Самое простое и нормально работающее:
Возникла коллизия 2 эквивалентно 3, мы не трогаем указатели в матрице, мы в массиве номеров, на втором месте вместо двойки ставим 3.
Возникла коллизия 3 эквивалентно 1, мы просматриваем массив номеров — и везде, где в нем стоит 3, ставим 1.
То есть обобщая эти два тезиса имеем:
При возникновении эквивалентности C1 эквивалентно C2 мы проходим весь массив номеров и там где C1 ставим C2.
Массив номеров часто имеет малый размер в сравнении с изображением, и это сильно ускоряет перенумерацию. Уже этот способ дает реал-тайм, я реализовывал для iPhone.
В эти выходные я опубликую вторую часть статьи, с которой уже порядком затянул — обстоятельства. Там расскажу про улучшение этого способа, но оно на поверхности.
Все номера хранятся в отдельном массиве — выделенном предварительно и с некоторым запасом, так как неизвестно сколько объектов на картинке.
Самое простое и нормально работающее:
Возникла коллизия 2 эквивалентно 3, мы не трогаем указатели в матрице, мы в массиве номеров, на втором месте вместо двойки ставим 3.
Возникла коллизия 3 эквивалентно 1, мы просматриваем массив номеров — и везде, где в нем стоит 3, ставим 1.
То есть обобщая эти два тезиса имеем:
При возникновении эквивалентности C1 эквивалентно C2 мы проходим весь массив номеров и там где C1 ставим C2.
Массив номеров часто имеет малый размер в сравнении с изображением, и это сильно ускоряет перенумерацию. Уже этот способ дает реал-тайм, я реализовывал для iPhone.
В эти выходные я опубликую вторую часть статьи, с которой уже порядком затянул — обстоятельства. Там расскажу про улучшение этого способа, но оно на поверхности.
Да. Так и делаю, скорость действительно высокая.
А разве возможен случай, когда две эквивалентности (это ведь позиция 4?) ещё и с разными метками возникает подряд?
Подскажите пожалуйста литературу(англ/русс) где описаны эти алгоритмы.
А разве возможен случай, когда две эквивалентности (это ведь позиция 4?) ещё и с разными метками возникает подряд?
Подскажите пожалуйста литературу(англ/русс) где описаны эти алгоритмы.
На самом деле возможно все что угодно, тут теорию делать сложно. я встречал и более замороченные коллизии. В начале, пытался честным образом строить граф эквивалентностей, разбирая получающиеся тразитивности по завершению алгоритма — но отказался от этой затеи, так как она привела к задаче поиска путей в графе и ужаснула меня.
Литературу — ну про этот алгоритм есть ссылка в вики (приводилась в комментариях). Там же есть хороший список литературы, но я с ним еще не знаком, как и с этой статьей.
Про этот алгоритм я узнал из лекций на 4-ом курсе.
Литературу — ну про этот алгоритм есть ссылка в вики (приводилась в комментариях). Там же есть хороший список литературы, но я с ним еще не знаком, как и с этой статьей.
Про этот алгоритм я узнал из лекций на 4-ом курсе.
Пришел к аналогичной идее после комментария skb7 с методом присвоения ссылок.
Большое спасибо автору и skb7 за идеи и направления.
Большое спасибо автору и skb7 за идеи и направления.
" длину общей границы между всеми парами областей" — у меня взорвался мозг, если две области не связанные как между ними есть общая граница? Расскажите подробнее пожалуйста.
Ну у меня просто разбиение было не на черное/белое, а по цветам (связная красная область, связная синяя область и т.п.), то есть разные области могли соприкасаться и не было т.н. фона (т.е. клеток, не принадлежащих никакой области). Это более общий случай. Тогда у каждой пары областей можно рассматривать длину общей границы. Если области не связаны, то длина общей границы равна нулю.
А в данном случае, когда есть несвязанные области и фон — посчитать матрично периметр всех областей ещё проще.
А в данном случае, когда есть несвязанные области и фон — посчитать матрично периметр всех областей ещё проще.
На всякий случай поясню что будет в вашем случае:
* найти площади областей — напрямую использовать vl_binsum/histc
* найти периметры — обнулить все внутренние пиксели области, после чего задача сведется к нахождению площадей.
Матрично (без циклов) удалить внутренние пиксели области несложно.
* найти площади областей — напрямую использовать vl_binsum/histc
* найти периметры — обнулить все внутренние пиксели области, после чего задача сведется к нахождению площадей.
Матрично (без циклов) удалить внутренние пиксели области несложно.
Действительно, но что-то не соображу, как без циклов удалить внутренние пиксели, мне сразу представился последовательный проход и маска.
Пусть map содержит 0 — там где фон, и числа больше 0, таи где области. Пусть также на границах массива не будет областей (если это не так, то можно дописать к нему нулевые строки/столбцы).
Тогда:
Тут всё делалось на низком уровне вручную, использовалась лишь мощь матричных операций.
Для конкретных задач можно использовать функции erode или сразу bwperim.
Тогда:
[h, w] = size(map);
% логический массив, содержащий 1 для внутренних элементов
inner = map(2:h-1, 3:w)~=0 & map(2:h-1,1:w-2)~=0 & map(3:h, 2:w-1)~=0 & map(1:h-2, 2:w-1)~=0;
map = map(2:h-1, 2:w-1);
map(inner) = 0;
Тут всё делалось на низком уровне вручную, использовалась лишь мощь матричных операций.
Для конкретных задач можно использовать функции erode или сразу bwperim.
данную задачу можно решить существенно быстрее и сильно сэкономив память.
сначала обходим объект по внешнему контуру (можно сделать за время порядка количества внешних точек, что обычно не больше 4*X*Y, если интересно, могу написать как делается), а потом заполняем соответствующим индексом все внутренние точки (если это нужно).
остается только уметь находить начальные точки для обхода, без предварительного квадратичного (X*Y) прохода по изображению это сделать сложно, но можно совместить этот процесс с считыванием изображения.
сначала обходим объект по внешнему контуру (можно сделать за время порядка количества внешних точек, что обычно не больше 4*X*Y, если интересно, могу написать как делается), а потом заполняем соответствующим индексом все внутренние точки (если это нужно).
остается только уметь находить начальные точки для обхода, без предварительного квадратичного (X*Y) прохода по изображению это сделать сложно, но можно совместить этот процесс с считыванием изображения.
Нет, это не так. О какой памяти вообще говорится ?, дополнительной памяти не требуется, и экономить ее не получится, тем более существенно.
«уметь находить начальные точки для обхода» — в этом проблема.
Более того, после того как контур найден, его нужно убрать с изображения, чтобы снова не найти — дополнительные расходы.
И еще, ваш вариант совершенно не подходит если изображение поступает последовательно, придется дождаться полного получения картинки, в моем варианте — достаточно получить две строки.
«уметь находить начальные точки для обхода» — в этом проблема.
Более того, после того как контур найден, его нужно убрать с изображения, чтобы снова не найти — дополнительные расходы.
И еще, ваш вариант совершенно не подходит если изображение поступает последовательно, придется дождаться полного получения картинки, в моем варианте — достаточно получить две строки.
мой комментарий имеет смысл в предположении, что картинка в памяти доступна только для чтения.
собственно если это честный набор бит Ч/Б, то ее эффективнее представлять как набор бит, а если нет — то после работы алгоритма она не должна портиться.
контуры не надо убирать с изображения, достаточно просто списка пропусков точек для каждого столбца.
и да, если картинка поступает последовательно с построением контуров будут сложности.
собственно если это честный набор бит Ч/Б, то ее эффективнее представлять как набор бит, а если нет — то после работы алгоритма она не должна портиться.
контуры не надо убирать с изображения, достаточно просто списка пропусков точек для каждого столбца.
и да, если картинка поступает последовательно с построением контуров будут сложности.
и + скорость. мы когда занимались подобной задачей пользовали подобный (или в точности такой? уже не припомню) метод, время работы на картинках 3200x2400 измерялась в секундах. с внешними контурами — десятые доли секунды (реально сильно зависело от картинки, от 5 миллисекунд до секунды).
Я пробовал реализовывать описанный вами алгоритм и отказался от него.
Этапы: Поиск стартовой позиции, трассировка контуров, определение внутренних точек.
Самый затратный этап был у меня — определение принадлежности точки к полигону — он сделал строго по алгоритму из книги Кормена.
У меня получилось медленнее чем в предлагаемом в статье варианте.
И я не верю, что что можно сделать существенно быстрее.
Хотя все имеет место в своих приложениях.
Этапы: Поиск стартовой позиции, трассировка контуров, определение внутренних точек.
Самый затратный этап был у меня — определение принадлежности точки к полигону — он сделал строго по алгоритму из книги Кормена.
У меня получилось медленнее чем в предлагаемом в статье варианте.
И я не верю, что что можно сделать существенно быстрее.
Хотя все имеет место в своих приложениях.
завтра попробую написать топик про то как мы это делали, и в частности проблема принадлежности точки к контуру была решена.
хотя, ради справедливости, в финальном релизе мы плюнули на оба варианта и реализовали «самый тупой» (алгоритм заливки) на CUDA. со скоростью обработки в 20Гбайт/с результирующее время даже не мерили.
хотя, ради справедливости, в финальном релизе мы плюнули на оба варианта и реализовали «самый тупой» (алгоритм заливки) на CUDA. со скоростью обработки в 20Гбайт/с результирующее время даже не мерили.
Спустя 5 лет все-таки задам вопрос, вы говорите, что алгоритм однопроходный и может работать, когда изображение поступает последовательно пиксель за пикселем (надо две строчки). А как в этом случае реализовавать операцию слияния двух объектов, если B != 0, С != 0 и B != C.
Image(Image == C) = B?
Мне приходит в голову только опять обойти изображени только теперь снизу вверх, но также справа налево.
Image(Image == C) = B?
Мне приходит в голову только опять обойти изображени только теперь снизу вверх, но также справа налево.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Подсчет объектов на бинарном изображении. Часть 1