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 widthw_c
and heighth_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!