Divide a 2D depth image into non-overlapping rectangular areas of similar values

Question

I am trying to segment a 2D depth image into non-overlapping rectangular areas of similar values as shown in the example:

In this example, the depth image is segmented into four rectangles: 4by3by6 yellow, 2by4by15 green, 4by2by8 orange, and 2by2by3 blue. Note that there is a min length and width limit to the rectangles, in this case, 2, so that the lower right corner is segmented into one area instead of two.

This is a simple example, the depth map can be a lot more complex than this. This is quite a challenging problem I don't expect it to be solved to optimality, but any solution more optimized than a grid of fixed resolution is appreciated.

I imagine this to be solved by some RANSAC process, similar to plane fitting, but I haven't figured out exactly how to do that. The problem also resembles image segmentation, where each segment is rectangular in shape and does not overlap.

Answer 1

Idea of an algorithm to solve this (not optimally ofc):

1. examine vertical neighbours for each element that could be grouped. Rule of grouping needs to be determined by you after some "trial and error". Single-element groups are also possible. Every element must be added to one and only one group.

2. iterate through groups and check whether horizontal neighbours of those are "close enough", if yes, then merge groups.

3. iterate through groups and check whether vertical neighbours of those are "close enough", if yes, then merge groups.

4. Continue steps 2 and 3 and finish when there was no single group merging during those

5. Finally, remove those groups that do not fulfill width/height requirements