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

<p>The reduction is straightforward from: <a href="https://www.sciencedirect.com/science/article/pii/092577219400015N" rel="nofollow noreferrer">Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson: Tiling Figures of the Plane with Two Bars. Comput. Geom. 5: 1-25 (1995)</a> </p>

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

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

CC BY-SA 4.0
2019-07-01T15:08:16.533Z
Thank you very much for the reference!
f10w
CC BY-SA 4.0
2019-06-28T07:55:48.617Z
2019-06-30T09:56:31.453Z
2019-06-30T09:56:31.453Z
Marzio De Biasi
<p>I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.</p>

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

<ul>
<li>Each bounding box has a color taken from <code>C</code>.</li>
<li>Every bounding box of color <code>c</code> has width <code>w_c</code> and height <code>h_c</code>.</li>
</ul>

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

<p>Any suggestions on how to solve this problem would be very much appreciated!</p>

<p>Thank you very much in advance for your help!</p>

<ds.algorithms><co.combinatorics>
Placing color boxes on a colored image such that color consistency is maximized
f10w
# Placing color boxes on a colored image such that color consistency is maximized

(Asked by: username_0 on 2019-06-26)

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!

**Tags:** ds.algorithms, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2019-06-28. Score: 3

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)](https://www.sciencedirect.com/science/article/pii/092577219400015N)

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.

> **Comments:**
> **username_0**: Thank you very much for the reference!  

---

