# 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!

Thank you very much in advance for your help!

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.