Merging image regions (bboxes) in linear time

Question

I have a set of regions (bounding boxes) for some image, example python code:

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

What I would like to do is to merge regions which overlap or the distance between bbox edges is less than X. Naive approach would be checking distances between all regions, which has O(n²) complexity. I can write something smarter but I have impression that this kind of algorithm already exists and I don't want to reinvent the wheel. Any help is appreciated.

Answer 1

Is this your question "There is n boxes (not necessarily // to x-y axis), and you want to find all overlapping boxes and merge them if they exist?"

I cannot think of a linear algorithm yet but I have a rough idea faster than O(n^2), maybe O(n lg n) describes as follow:

1. Give each box an id, also for each edge, mark it's belonging box
2. Use sweeping line algorithm to find all intersections
3. In the sweeping line algorithm, once an intersection is reported, you know which 2 boxes are overlapping, use something like disjoint-set to group them.
4. Lastly linearly scan the disjoint-set, for each set, keep updating the leftmost, rightmost, topmost, bottommost point for making a larger box to bound them all (merging done here, note that if a box has no overlapping with others, the set will only contain itself)

I hope this method will work and it should be faster than O(n^2), but even if it does works, it still have some problems at step 4, where the larger merged box must be // to x-y axis, which is not a must.

Edit: Sorry I just go through OP again, and understand the above solution does not solve the "merge boxes with distance < x", it even only solves partly of the overlapping boxes problem.

Moreover, the merging box procedure is not a 1-pass job, it is kind of recursive, for example a box A and box B merged become box C, then box C may overlap / distance < x with box D..and so on.

To solve this task in linear time is quite impossible for me, as pre-computing the distance between all pair-wise box is already hardly be done in O(n)...