Placing color boxes on a colored image such that color consistency is maximized

Question

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.

Given an image with black background that contains blobs whose colors are taken from a set C (that does not contain black). Suppose that we have an infinite number of rectangular bounding boxes such that:

• Each bounding box has a color taken from C.
• Every bounding box of color c has width w_c and height h_c.

Question: How to place these bounding boxes on the image such that there is no overlap between any two boxes, and that n_good - n_bad is maximized, where n_good is the total number of pixels that are inside a box of the same color (as the pixel's color), and n_bad is the total number of pixels that are inside a box of a different color?

Any suggestions on how to solve this problem would be very much appreciated!

Thank you very much in advance for your help!

Answer 1

Just an extended note to show that the decision version of your problem ("Is there a placement of the bounding boxes such that $n_{good} - n_{bad} \geq k$?" ) is NP-complete even for two colors $C = \{c_1, c_2\}$ and two bounding boxes $B_1 \equiv \langle col=c_1, w=3, h=1 \rangle$, $B_2 \equiv \langle col=c_2, w=1, h=1 \rangle$.

The reduction is straightforward from: Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson: Tiling Figures of the Plane with Two Bars. Comput. Geom. 5: 1-25 (1995)

They prove that tiling a figure on the plane grid with two horizontal/vertical bars with length at least 3 is NP-complete.

The reduction to your problem is simple: just color the "pixels" of the figure with color $c_1$ and fill the remaining background pixels of the $N+1\times N+1$ square region around it with color $c_2$. You can place the bounding boxes $B_1, B_2$ with $n_{good} - n_{bad} = (N+1)^2$ if and only if the original figure is tileable with $3 \times 1$ horizontal/vertical bars.