### Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Sun, 12 Dec 2010 13:10:57 GMT

Hello,
I have this idea to try and describe the area of a bitmap with
boxes/rectangles.
Like covering a bitmap with boxes/rectangles.
The only catch is that only pixels that are not transparent/black should be
covered.
So only the pixels which actually consists out of colors should be covered.
Furthermore the mission is to try and describe the bitmap with as little
boxes/rectangles as possible.
So this is an optimization problem.
I can imagine that different solutions might exist... some might be better
than others.
Some questions about this:
1. To what category does this problem belong ? (Covering ? Packing ?)
2. Is there already an algorithm which does this ?
If not what can you think of ? ;)
I am not really looking for a "solver model" an algorithm will do just
fine... even heuristics which give sub optimal might be fine...
It reminds me a bit of the "bin packing" problem for texture mapping.
Except this time some parts of the texture map are already taken and thus
some areas remain free to pack.
So in other words... the black/transparent colors are already taken in
area... for those parts it probably doesn't matter how they are taking away
from the remaining solution space.
Hmmm...
Bye,
Skybuck.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Sun, 12 Dec 2010 13:26:23 GMT

Hmm..
Ok... I think I have a nice algorithm in my little big heady... but for now
I will keep it secret LALALALAL LOL.
But I am curious what you can come up with if you willing to share that is
?! Unlike me ?! I am so {*filter*} LOL.
But if it's already know then you can share can't you ?! ;) :)
If it turns out that my algo sux then I will get back to you...
Maybe I will turn it into a competition.
It would work as follows:
1. I give you a bitmap and you must turn it into rectangles/boxes with your
algorithm.
Then we simply count boxes and compare the results.
That way we don't have to reveal our algorithms and we can simply compare
the results instead... to see which algorithm is actually better...
That would be cool ! ;) =D
I like this idea a lot !
I am going to make a website for it and turn it into a little programming
contest !
JAWHOLE ! :) =D LOL.
Bye,
Bye,
Skybuck.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **A.L.** » Sun, 12 Dec 2010 14:05:29 GMT

On Sat, 11 Dec 2010 05:26:23 +0100, "Skybuck Flying"
What about reinventing the wheel? Or light bulb?
A.L.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Sun, 12 Dec 2010 14:14:00 GMT

Hihihihihihihi.
Big words you speak of ! (Yoda says) ;) :)
You self-pro-claimed-jedi will get your chance to prove yourself in combat
soon enough ! ;) :)
See the next/new posting for contest details ! ;) :)
(Subject: "Programming Contest: BoxifyMe" )
I shall keep a close eye on you ! ;) =D
Bye,
Skybuck ;) =D

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Uffe Kousgaard** » Sun, 12 Dec 2010 17:08:27 GMT

>
I'll put a small rectangle around every single bit on your bitmap.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Sun, 12 Dec 2010 18:30:05 GMT

Hmm ok you do that... then your entry will be 100x100 = 10000 boxes.
I already completed my first algoritm idea... and it only produces 306
boxes.
So you are already defeated by me by a big margin ! ;) :)
The results/outputs still need to be verified... but so far it's looking
pretty good/reliable/correctly...
See here and be jealous hahahahahahahahaha:
http://www.**--****.com/
Me pointing a big colorized pictured gun at you and asking you the following
question:
"Can you do better punk ?" ;) :)
Bye,
Skybuck ;) =D

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **A.L.** » Mon, 13 Dec 2010 00:37:18 GMT

On Sat, 11 Dec 2010 06:14:00 +0100, "Skybuck Flying"
Somehow you were not in my kill file...
A.L.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Paul** » Mon, 13 Dec 2010 01:06:41 GMT

I trust that's now been corrected?
/Paul

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Jamie** » Mon, 13 Dec 2010 06:22:50 GMT

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Tue, 14 Dec 2010 12:10:54 GMT

LOL, If you can't even straighten out your killfile... then what possible
hope could you have for this contest ?! ;) =D
Be seeing you ! LOL.
Bye,
Skybuck ;) =D

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Jongware** » Tue, 14 Dec 2010 23:46:19 GMT

That's a good start.
Next: join rects of "equal" color (with some formula to compare two
slightly different colors -- the parameters for that are not given).
Since you are talking about *boxes*, you must next check how much each
single rectangle can grow in either or both x and y direction. All you
have to do is to keep track of the largest area -- for when an increase
in y means a decrease in x and a net smaller rectangle area.
Since you want "as little boxes as possible", you could add a fuzziness
parameter: how much would you gain by covering one single lousy pixel of
a 'bad' color? How much by covering two? Three? Eigh{*filter*}? This can
probably given a rational score by comparing the number of 'false'
coverings to the total number of pixels covered in the entire rectangle.
That way, a 10x10 rectangle that covers one wrong pixel is worse than a
100x100 rectangle that covers 10 wrong pixels.
After that, you'd probably have millions of possible box arrangements;
picking the optimal solution could be done with some kind of network
optimizer (the name of which escapes me for the mo').
[Jw]

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Wed, 15 Dec 2010 01:22:08 GMT

Thanks great idea. (I think you mean a bigger rectangle area here but ok)
The mission is not to create "very little boxes" but the opposite to create
"as few boxes as possible" so an implementation will want to make big boxes
because they describe more and reduce the number of needed boxes, probably
;)
Your idea of doing an "area" calculation for grow direction possibilities is
nice.
I might give this area heuristi (growth decision moment) an implementation
try in the near future.
Therefore if I do implement it... I will call that version: "area".
Perhaps even "edge+area" ;) :)
Bye,
Skybuck =D

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Thu, 16 Dec 2010 12:09:21 GMT

Perhaps you were correct and smallest box should be found first by greedy
algorithm...
I think I might give that idea a try to see if you on to something ;) :)
Bye,
Skybuck.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **ngry** » Fri, 17 Dec 2010 06:40:52 GMT

Hi, maybe mu suggestion will help you.
I suppose you're able to create bitonal mask (pixmap) for pixels of
interest.
Then you should perform seed fill on this mask, identifying connected
components.
(This process also called morphological reconstruction, see
http://www.**--****.com/ )
When filling, you are maintaining a stack of pixels, say pairs of
integers {x,y}.
For solution I propose you to maintain additional array of {x,y}
pairs.
Sorting this array by x than by y, and removing adjacent pixels will
produce
a vertical run-length representation of your raster spot (changing
order comparing y first
will give you horizontal run-length representation). With run-length
representation
I understand array of triples {x,y,run} where x,y are seed point
coordinates and
run is the length of single-pixel line. This triples can be converted
to rectangles
with width (height if horizontal) equal to 1.
Having this array of runs you can find adjacent runs with same run
length, producing
single rectangle instead of few thin ones (sorting trick is applicable
too!).
Some notes on implementation:
1. Sorting can be done very fast by using counting sort
(lsd-radix sort), 2 bytes for each coordinate (or 4 bytes for pair
{x,y}) are enough
in most of applications.
2. It is not necessary to compute pixmap to perform seed filling, see
link above, for
grayscale seed-fill.
3. You can find contours of yours objects of interests, convert them
into chain code, etc
and turn your problem into "optimal rectilinear polygon partition by
rectangles", which
is NP-hard. My suggestion is a one of heuristics.
Cheers.

### Re: Covering a bitmap with (minimal) boxes/rectangles.

by **Skybuck Flying** » Fri, 17 Dec 2010 14:12:06 GMT

Yes, ok.
Anything is possible yes.
I can maintain anything but ok.
Why sort ?
In other words, largest height per pixel.
In other words, largest width per pixel.
How ? Only pixels next to it might have same length etc but ok.
I guess this is simply trying to grow the rectangle.
Again what does sorting have to do with it ?
I am not interested in sorting algorithms, just keep the description of the
algorihm basic ;)
I also don't need details about bytes and such... just keep it simple...
I'll figure out the rest.
What you call pixmap... I call a 2D array of boolean indicating if pixel is
on or off.
mPixelEnabled[vX,vY] := true or false;
Counters ok, what is chain code ? you mean growing them ?
Ok, I'll google this and read up on it... if I can make any sense of it and
have any questions I'll get back to you assuming you know it ?
Bye,
Skybuck.

### Similar Threads:

1.Covering a bitmap with (minimal) boxes/rectangles.

Hello,
I have this idea to try and describe the area of a bitmap with
boxes/rectangles.
Like covering a bitmap with boxes/rectangles.
The only catch is that only pixels that are not transparent/black should be
covered.
So only the pixels which actually consists out of colors should be covered.
Furthermore the mission is to try and describe the bitmap with as little
boxes/rectangles as possible.
So this is an optimization problem.
I can imagine that different solutions might exist... some might be better
than others.
Some questions about this:
1. To what category does this problem belong ? (Covering ? Packing ?)
2. Is there already an algorithm which does this ?
If not what can you think of ? ;)
I am not really looking for a "solver model" an algorithm will do just
fine... even heuristics which give sub optimal might be fine...
It reminds me a bit of the "bin packing" problem for texture mapping.
Except this time some parts of the texture map are already taken and thus
some areas remain free to pack.
So in other words... the black/transparent colors are already taken in
area... for those parts it probably doesn't matter how they are taking away
from the remaining solution space.
Hmmm...
Bye,
Skybuck.

2.Covering rectangles in 2D

3.2D covering rectangles

Hi,
I have a problem and I hope somebody can put some light on it. Suppose
there is a big rectangle, 'A', and suppose that I put several smaller
rectangles over 'A'. The small rectangles can be overlapped, but they
are all inside 'A'. The question is, is it possible to know whether
'A' is totally covered? In other words, it is possible to know if all
points inside 'A' are also inside of, at least, one small rectangle?
Example:
'A' is the rectangle with coordinates (down-left corner and upper-
right corner) <0, 0> <100, 200>
There are two smaller rectangles: '1' is <0, 0> <50, 100>; '2' is <50,
100> <200, 200>.
In this case, 'A' is not totally covered because, for example, point
<70, 20> is not in any of the smaller rectangles.
Does this problem is solvable?
Thanks

4.covering points by a rectangle

Given n points in the plane and a fixed rectangle r. How can one find a
translation of r that covers as many of these n points as possible?
This translation clearly can be found in O(n^2) by trying all reasonable
locations for r. Is there any faster algorithm known?

5.Help - white covering box - not

Using PM 6.5 I've got a multipage document with header in master
page. I don't want to print header on first 2 pages. In the past, I've
drawn a box around header using no line and paper fill. That's not
working this time. Any suggestions?
Leo aka Charlie
Yahoo is spam trap XXXX@XXXXX.COM is real

6. Repaint TImage bitmap rectangle?

7. First rectangle in bitmap renders as transparent if white or nearly white (vb.net)

8. Cut rectangle out of Bitmap?