consider an image like this:

by grouping pixels by color into distinct rectangles, different configurations might be achieved, for 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?

p.s. I'm not seeking recommendations for books, tools, software libraries, and more.

CodePudding user response：

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.