fill region with minimum number of rectangles

I have a image/matrix as shown in the attached picture.

My goal is to recreate the white area in the image with rectangles. That is, I want to recreate the image by defining a bunch of rectangles (and keep each rectangle separate). However, I want to automatically determine the fewest number of rectangles as possible, and create those N rectangles.

The image will always be of this type, nothing but right angle transitions, though the pattern will vary.

Any good ideas/tips on where to start? This seems complex to me.

Answer 1

[Walter Roberson]

This is a Multidimensional Constrained Knapsack Problem and it is NP-Complete (that is, in the category of "very hard" problems that get more expensive faster than any fixed polynomial.)

The problem is in proving that any given solution is the minimum number of rectangles. Solutions can be proposed that are "pretty good" and easy to implement, but proving that there is no way that you could do better is the difficult part.