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
- Every bounding box of color
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!