Here is an example
dots representing coordinates of pixels
added more representative example
added real example
added main problem
Here is an example
dots representing coordinates of pixels
added more representative example
added real example
added main problem
I would write an algorithm where you would iteratively fill lines into rectangles and create a rectangle merging and splitting procedure based on area and thickness. I will use the following image as an example image for the algorithm:
Step 1 Find all the uninterrupted horizontal and vertical lines in the image.
In python you would do something like this:
def horizontal_longest_lines(im):
counts = {}
on_a_line = False
line = None
for row_index, row in enumerate(im):
for col_index, pixel in enumerate(row):
coord = (row_index, col_index)
if not pixel:
on_a_line = False
line = None
continue
if pixel:
if not on_a_line:
on_a_line = True
line = (coord, coord)
counts[line] = 1
else:
current = counts[line]
del counts[line]
line = (line[0], coord)
counts[line] = current + 1
return counts
def vertical_longest_lines(im):
counts = horizontal_longest_lines(im.transpose())
new_counts = {}
for key in counts:
new_counts[(key[0][::-1], key[1][::-1])] = counts[key]
return new_counts
Step 2 fill the area around the lines to create rectangles from the lines:
For a more efficient algorithm, you could improve this step by trying to merge existing lines into rectangles. But that would probably a bit more complicated to write.
Step 3 Since some lines will create the same rectangle, these duplicate rectangles need to be removed.
Step 4 Find overlapping rectangles, give preferences to rectangles that have a bigger area. Cut off the overlapping part from the smaller rectangle. For these two rectangles:
The result would then be:
Step 5 Some edge cases can happen, where the resulting cut-off does not result in a new rectangle. For these cases, split the resulting shape in new rectangles. For instance in this case:
Do note, there are two possibilities here in splitting up the resulting shape. You would need to fine-tune this process.
Step 6 Merge rectangles that have exactly the same width as the other rectangle's height and are touching each other.
All the resulting rectangles are now the decomposed walls by thickness:
It is a bad idea to try to abuse clustering algorithms for this. In particular k-means will not cut vertically, nor consider rectangles.
What you need to do is a trivial axis-aligned corner detection.it does not get much simpler than that!
You begin on the left, and whenever the location of the topmost pixel changes, a rectangle is complete.