Remove an unobstructed rectangle

Question

This image was made by overlaying 7 differently colored rectangles on top of each other:

The black and maroon rectangles are unobstructed, that is, no other rectangles are above them.

Write a program that takes in an image such as this and remove any single unobstructed rectangle, outputting the resulting image.

Example

If you ran your program on the image above and kept re-running it on the output, it might progress like this.

Run 1 - Black removed (could have been maroon):

Run 2 - Maroon removed (only choice):

Run 3 - Yellow removed (only choice):

Run 4 - Blue removed (could have been green):

Run 5 - Green removed (only choice):

Run 6 - Brown removed (only choice):

Run 7 - Red removed (only choice):

Any additional runs should produce the same white image.

^{Hopefully Stack Exchange has not lossily compressed any of these images.}

The image will always have a white background and each rectangle will be a unique RGB color that isn't white.

You can assume that the image can always be interpreted as a set of overlapping rectangles. Specifically, you can assume that, for a particular color, the pixel with that color closest to the top of the image is part of the top edge of that color's rectangle. The same holds for the bottom, left, and right edges.

So, for example, in this image, the top edge of the red rectangle would be just below the bottom edge of the yellow rectangle, as the the orange rectangle covered the old red top edge:

In this image, the red rectangle could be removed first (along with black/maroon/orange/gray):

When the order of the lower rectangles is ambiguous, you can give them any order.

For example, the left image here could become the middle or the right:

The output should not have paradoxical overlaps (so making it with the painter's algorithm should be possible). So in this image (thanks user23013), it would have to be green under the orange rectangle:

Additional Details

• The image and rectangles may have any dimensions.
• The rectangles may touch the image border.
• There may be up to 256³ - 1 rectangles.
• If the input is entirely white, the output should be as well.
• You may use image libraries.
• The input should be the image file name or the raw image data. It can come from stdin or the command line.
• The output can be written to the same or another image file, spewed raw to stdout, or simply displayed.
• Any common lossless truecolor image file format is allowed.

The submission with the fewest bytes wins.

Answer 1

CJam, 241 bytes

(with newlines removed.)

rri:Hri:Vri:Q[q~]3/_Qa3*a+_|$W%:Pf{\a#}:AH/:B0ff*
P,,[AHAW%HBz:+_W%V\V]2/
ff{~@@f=/::|1#}0Ua4*t:R;
P0f<
V{H{BI=J=_2$=
0R{"I>! I+V<J>! J+H<"4/+4/z{~~}%:&1$*\)}%);2$-|t
}fJ}fI
[P,{_La#\1$0t1$f-}*;;]
{:TR=2/~\~V\-,>\f{\_3$=@~H\-,>{Tt}/t}~}/
:~Pf=:~
~]S*N

It uses the ppm file format. Example usage (using ImageMagick):

convert IVYvE.png -compress none ppm:-| (time /path/to/cjam-0.6.4.jar 1.cjam) |display

Well, it is too long and too slow... Runs about a minute for the example.

I resized the test cases (and added some others) to make testing easier.

It seems the color space informations are lost so the colors are slightly different.

Answer 2

Python, 690 651 610 606 594 569 bytes

The script reads the image name from stdin.

It detects the edges of every rectangles, sort them by the number of different colors they contain (the unobstructed rectangles contains only 1 color, and then appear at the end of the list)

This list is used to redraw an image. The redraw order is decided by choosing the permutation of the list that would generate an output image that have the least pixel difference with the input.

from PIL import Image as l,ImageDraw as D;from itertools import*;O,R,I,Z,k=[],range,l.open(raw_input()),{},lambda x:-x[1];(W,H),Q=I.size,I.load()
for i,j in product(R(W),R(H)):
 c=Q[i,j]
 if c in Z:x,y,X,Y=Z[c];Z[c]=[x,y,max(X,i),max(Y,j)]
 else:Z[c]=[i,j,0,0]
for n in permutations(sorted([(c,len({Q[g] for g in product(R(x,X),R(y,Y))})) for c,(x,y,X,Y) in Z.items()],key=k)[1:-1]):o=l.new(I.mode,I.size,0xFFFFFF);[D.Draw(o).rectangle(Z[c],fill=c) for c,_ in n];O+=[(o,sum(abs(a-b) for t,T in zip(I.getdata(), o.getdata()) for a,b in zip(t,T)))]
max(O,key=k)[0].show()

Answer 3

Java - 1483 bytes

I'm not a great code golfer, let that be clear; so the verbosity is not entirely Java's fault ;-) Nevertheless, this seemed like a really fun challenge. I've solved it in a way that - I think - is a bit boring and verbose, but hey. It works, it's (relatively) fast and, especially, it was fun!

The idea is as follows: Check each pixel from starting at the top left corner all the way to bottom right. Is it a white pixel? Ignore. Is it coloured? Cool, let's keep track of it and try to determine its boundaries (top left, top right, bottom left, bottom right).

Once that's done, check each rectangle's area. Does it contain a different colour than the rectangle's colour? Then find out what rectangle belongs to that colour and update that overlapping rectangle's z-index by 1.

And finally, draw all rectangles while taking the z-indices into account. It works actually like a z-index you know from CSS and other 3D stuff. The rectangles with the lowest z-index are drawn first, the highest z-index last.

import java.awt.*;import java.awt.image.*;import java.io.File;import java.util.*;import java.util.List;import javax.imageio.*;class A{class R{public Color k=new Color(-1);public int z;public Point a;public Point b;public Point c;public Point d;}public static void main(String[]w)throws Exception{BufferedImage i=ImageIO.read(new File(w[0]));List<R>r=new Vector<R>();for(int y=0;y<i.getHeight();y++){for(int x=0;x<i.getWidth();x++){Color c=new Color(i.getRGB(x,y));if(c.getRGB()==-1){continue;}R t=null;for(R s:r){if(s.k.equals(c)){t=s;}}if(t==null){t=new A().new R();r.add(t);}if(t.a==null){t.a=new Point(x, y);t.b=new Point(x, y);t.c=new Point(x, y);t.d=new Point(x, y);t.k=new Color(c.getRGB());}if(x<t.a.x){t.a.x=x;t.c.x=x;}if(x>t.b.x){t.b.x=x;t.d.x=x;}t.c.y=y;t.d.y=y;}}for(R s:r){List<Color>b=new Vector<Color>();for(int y=s.a.y;y<=s.c.y;y++){for(int x = s.a.x;x<=s.b.x;x++){if(i.getRGB(x, y)!=s.k.getRGB()){Color a=new Color(i.getRGB(x,y));boolean q=false;for(Color l:b){if(l.equals(a)){q=true;}}if(!q){b.add(a);} else {continue;}R f=null;for(R k:r){if(k.k.equals(a)){f=k;}}f.z=s.z+1;}}}}Collections.sort(r,new Comparator<R>(){public int compare(R a, R b){return a.z>b.z?1:(a.z==b.z?0:-1);}});for(int ii=r.size();ii>0;ii--){BufferedImage d=new BufferedImage(i.getWidth(),i.getHeight(),2);Graphics2D g=(Graphics2D)d.getGraphics();for(R s : r.subList(0, ii)){g.setColor(s.k);g.fillRect(s.a.x,s.a.y,s.b.x-s.a.x,s.c.y-s.a.y);}ImageIO.write(d,"png",new File(r.size()-ii+".png"));}}}

The complete code which is a bit - and that's an understatement ;-) - written more clearly, can be found here: http://pastebin.com/UjxUUXRp

Also, now that I see dieter's submission, I could have made some parts easier. It's not really necessary to find the rectangle whose colour is overlapping another rectangle. I could indeed just count the number of 'invading' colours.