Remove an unobstructed rectangle 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 2563 - 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.
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&lt;
V{H{BI=J=_2$=
0R{&quot;I&gt;! I+V&lt;J&gt;! J+H&lt;&quot;4/+4/z{~~}%:&amp;1$*\)}%);2$-|t
}fJ}fI
[P,{_La#\1$0t1$f-}*;;]
{:TR=2/~\~V\-,&gt;\f{\_3$=@~H\-,&gt;{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.