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. 

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. 

On Sat, 11 Dec 2010 05:26:23 +0100, "Skybuck Flying"





What about reinventing the wheel? Or light bulb?

A.L.

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 

>

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

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 

On Sat, 11 Dec 2010 06:14:00 +0100, "Skybuck Flying"








Somehow you were not in my kill file...

A.L.

I trust that's now been corrected?

/Paul

Shame on you..

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 

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]

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 

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. 

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.

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.