Слияние областей изображения (bbox) за линейное время

У меня есть набор регионов (ограничивающих прямоугольников) для некоторого изображения, например код Python:

im = Image.open("single.png")
pix = np.array(im)
gray = rgb2grey(pix)
thresh = threshold_otsu(gray)
bw = closing(gray > thresh, square(1))

cleared = bw.copy()
clear_border(cleared)
borders = np.logical_xor(bw, cleared)
label_image = label(borders)

for region in regionprops(label_image, ['Area', 'BoundingBox']):
    #now i have bounding boxes in hand

Что я хотел бы сделать, так это объединить области, которые перекрываются или расстояние между краями bbox меньше X. Наивным подходом будет проверка расстояний между всеми областями, что имеет сложность O(n2). Я могу написать что-нибудь умнее, но у меня сложилось впечатление, что такой алгоритм уже существует, и я не хочу изобретать велосипед. Любая помощь приветствуется.


python algorithm image-processing bounding-box scikits
person mnowotka    schedule 04.01.2014    source источник
comment
Как вы измеряете расстояние между ограничивающими прямоугольниками? Вы имеете в виду, что каждое ребро в ограничивающей рамке находится не более чем на расстоянии X или общее расстояние между ребрами равно X? Кроме того, как именно вы хотите объединить их вместе? Есть разные способы сделать это, но некоторые из них могут вызвать каскадный эффект, когда после слияния двух блоков новый блок затем должен быть объединен с третьим.   -  person templatetypedef    schedule 04.01.2014
comment
@templatetypedef Расстояние определяется как кратчайшее расстояние между любыми двумя краями двух разных блоков. Слияние — это создание рамки вокруг ограничивающих рамок, которые необходимо объединить.   -  person mnowotka    schedule 04.01.2014
comment
Проблема расстояния намного проще, если вы просто увеличиваете все поля на (расстояние/2). Это, по крайней мере, уменьшает проблему перекрытия блоков.   -  person kazagistar    schedule 05.01.2014

Ответы (1)


arrow_upward
0
arrow_downward

Это ваш вопрос: «Есть n блоков (не обязательно // по оси x-y), и вы хотите найти все перекрывающиеся блоки и объединить их, если они существуют?»

Я пока не могу придумать линейный алгоритм, но у меня есть приблизительное представление быстрее, чем O (n ^ 2), возможно, O (n lg n) описывает следующее:

  1. Дайте каждому ящику идентификатор, а также для каждого края отметьте его принадлежность
  2. Используйте алгоритм плавной линии чтобы найти все пересечения
  3. В алгоритме скользящей линии, как только сообщается о пересечении, вы знаете, какие 2 прямоугольника перекрываются, используйте что-то вроде disjoint-set, чтобы сгруппировать их.
  4. Наконец, линейно сканируйте непересекающийся набор, для каждого набора продолжайте обновлять крайнюю левую, крайнюю правую, самую верхнюю и самую нижнюю точку, чтобы сделать большую рамку, чтобы связать их все (объединение выполнено здесь, обратите внимание, что если коробка не перекрывается с другими, набор будет содержать только себя)

Я надеюсь, что этот метод будет работать, и он должен быть быстрее, чем O (n ^ 2), но даже если он работает, у него все еще есть некоторые проблемы на шаге 4, где больший объединенный блок должен быть // на оси xy, которая не обязательно.

Редактировать: извините, я просто снова просматриваю OP и понимаю, что приведенное выше решение не решает «объединить блоки с расстоянием ‹ x», оно даже частично решает проблему перекрывающихся блоков.

Кроме того, процедура слияния блоков не является однопроходной задачей, она является своего рода рекурсивной, например, блок A и блок B, объединенные в блок C, затем блок C может перекрываться / расстояние ‹ x с блоком D и т. д. .

Решить эту задачу за линейное время для меня совершенно невозможно, так как предварительное вычисление расстояния между всеми парными ящиками уже вряд ли можно сделать за O (n)...

person shole    schedule 21.02.2014