4

Given an image with a fixed palette (e.g. 256 colors)

Create an algorithm to divide that image into rectangular regions, each of which consists of the pixels of the same color. Regions can overlap, the order of them also matters (the last region will be drawn on top of others). The number of regions should be as small as possible.

Alternative formulation of the problem: draw an image using the smallest number of fill instructions.

I'm pretty sure that this problem is NP-complete, so a faster solution would be better than an exact one taking forever to run.

The simplest approach would be scanning the image line-by-line and producing rectangles with height of 1. But that is not very effective.

I were also thinking about creating a quadtree and then merging adjacent regions (merging would require some sort of heuristics to choose the best pair to merge).

The two above algorithms don't consider that the regions may overlap. We can draw a huge region, then drawing details above it.

Any ideas?

LeshaInc
  • 101
  • 1
  • 2
  • 1
    Do we get sample images? – Mark Setchell Oct 19 '18 at 16:28
  • The algorithm should be able to handle any image. – LeshaInc Oct 19 '18 at 16:37
  • Only related post I found: https://stackoverflow.com/questions/14315104/optimising-the-drawing-of-overlapping-rectangles – juvian Oct 19 '18 at 16:53
  • https://stackoverflow.com/questions/5919298/ – MBo Oct 19 '18 at 16:54
  • Are you concerned about reducing the total number of pixels that need to be drawn in the case over overlapping fills? Or just the total number of fills? i.e. should you minimize overdraw? – samgak Oct 19 '18 at 20:15
  • @samgak, no, I have to minimize the number of fills. – LeshaInc Oct 20 '18 at 11:06
  • Do you allow some kind of intensity margin, where you could merge pixels with a similar intensity (e.g for complex images) or do you need to have specifically 1 component per non-connected field? – T A Oct 22 '18 at 07:34
  • No, after subdividing the result should look the same as the input image. Input images have a fixed palette of 256 colors (not so complex). – LeshaInc Oct 22 '18 at 13:41
  • If you want to make claims about NP-completeness, you need to state it as a decision problem. – wildturtle Mar 04 '19 at 22:53

0 Answers0