Here is an example

dots representing coordinates of pixels

enter image description here

added more representative example

enter image description here

added real example

added real example

added main problem

main problem

  • $\begingroup$ I see two figures consisting of rectangles, both congruent, one in grayscale and one in colors. What would you like to cluster here? $\endgroup$ – Stephan Kolassa Sep 19 '19 at 12:13
  • $\begingroup$ gray is an image which is I should to process somehow to get second, colored image $\endgroup$ – Oleg Sep 19 '19 at 12:16
  • $\begingroup$ Ah. It sounds like you actually don't want to cluster shapes, but to cut them into the smallest possible number of rectangles, correct? $\endgroup$ – Stephan Kolassa Sep 19 '19 at 12:24
  • $\begingroup$ yeah, split them, and get coordinates of it $\endgroup$ – Oleg Sep 19 '19 at 12:26
  • $\begingroup$ got it, thank you Stephan! $\endgroup$ – Oleg Sep 19 '19 at 13:41

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:

base image wall thickness decomposition

Step 1 Find all the uninterrupted horizontal and vertical lines in the image.

all horizontal uninterrupted linesall vertical uninterrupted lines

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
           if pixel:
               if not on_a_line:
                   on_a_line = True
                   line = (coord, coord)
                   counts[line] = 1
                   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:

from line to rectangle for wall thickness decomposition algorithm from line to rectangle for wall thickness decomposition algorithm from line to rectangle for wall thickness decomposition algorithm from line to rectangle for wall thickness decomposition algorithm etc.

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:

overlapping rectangles overlapping rectangles

The result would then be:

split rectangles algorithm

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:

edge case wall splitting edge case wall splittinge edge case wall splitting edge case wall splitting

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:

result wall thickness decomposition algorithm

  • $\begingroup$ Nice solution mate! but as for me — I needed a 100% robust & 0 maintenance way, so I ended up with plain simple template matching, categorized by wall thickness. But thank you anyway! Hope it would be helpful for someone. $\endgroup$ – Oleg Oct 26 '19 at 15:35

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.

  • $\begingroup$ imagine bw floor plan with different wall thickness, so thickness can vary in different directions $\endgroup$ – Oleg Sep 20 '19 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.