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

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!

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 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.