Divide an image by grouping similar pixels into rectangles

user_19433653 0
Viewed 107

consider an image like this:

original image

by grouping pixels by color into distinct rectangles, different configurations might be achieved, for example:

dissected image example

the goal is to find one of the best configurations, i.e. a configuration which has the least possible number of rectangles (rectangles sizes are not important).

any idea on how to design an efficient algorithm which is able to solve this problem?

EDIT: i think the best answer is the one by @dshin, as they proved that this problem is a NP-HARD one so there probably isn't any efficient solution that is able to guarantee an optimal result. other answers provide reasonable compromises to get an acceptable solution, but that won't always be the optimal one.

image-processing geometry algorithm
3 Answers

Each connected colored region is a rectilinear polygon that can be considered independently, and so your problem amounts to solving the minimum rectangle covering for rectilinear polygons. This is a well-studied problem that finds applications in some fields, like VLSI.

For convex rectilinear polygons, there is an algorithm that finds the optimal solution in polynomial time, described in this 1984 thesis.

The non-convex case is NP-hard (reference), so an efficient optimal solution likely does not exist. But there are several algorithms which produce good empirical results. This 1990 publication describes three separate algorithms, each of which are guaranteed to use at most twice as many rectangles as the optimal solution. This 2016 publication describes an algorithm that uses the common IP + LP relaxation technique, which apparently produces better results in real-life problem instances, although lacking in theoretical guarantees. Unfortunately, both publications are behind paywalls, and I haven't been able to find free resources that describe the algorithms.

If you are just looking for something reasonable, and your problem instances are not pathological in nature, then the algorithms described in other answers are probably good enough.

user_5439130

I don't have a proof but my feeling is a greedy approach should solve this problem:

  1. Start on the upper left (or in whichever corner)
  2. Expand rectangle 1px to the right as long as colors match
  3. Expand rectangle 1px to the bottom as long as all colors in that row match
  4. Line by line and column by column, find the next pixel that is not already part of a square (maybe keep track of visited pixels in a second array) and repeat 2 and 3.

You can switch lines and columns and go up and left or whatever instead and end up with different configurations, but from playing this through in my mind I think the number of rectangles should always be the same.

user_104810330

The idea here is based on the following links: Link 1 and Link 2.

In both the cases, the largest possible rectangle is computed within a given polygon/shape. Check both the above links for details.

We can extend the idea above to the problem at hand.

Steps:

  1. Filter the image by color (say red)
  2. Find the largest possible rectangle in the red region. After doing so mask it.
  3. Repeat to find the next biggest rectangle until all the portions in red have been covered.
  4. Repeat the above for every unique color.

Overview:

enter image description here

user_68859020
Related