American Gothic in the palette of Mona Lisa: Rearrange the pixels
Java - GUI with progressive randomized transformation
I tried a LOT of things, some of them very complicated, then I finally came back to this relatively-simple code:
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.Timer;
@SuppressWarnings("serial")
public class CopyColors extends JFrame {
private static final String SOURCE = "spheres";
private static final String PALETTE = "mona";
private static final int COUNT = 10000;
private static final int DELAY = 20;
private static final int LUM_WEIGHT = 10;
private static final double[] F = {0.114, 0.587, 0.299};
private final BufferedImage source;
protected final BufferedImage dest;
private final int sw;
private final int sh;
private final int n;
private final Random r = new Random();
private final JLabel l;
public CopyColors(final String sourceName, final String paletteName) throws IOException {
super("CopyColors by aditsu");
source = ImageIO.read(new File(sourceName + ".png"));
final BufferedImage palette = ImageIO.read(new File(paletteName + ".png"));
sw = source.getWidth();
sh = source.getHeight();
final int pw = palette.getWidth();
final int ph = palette.getHeight();
n = sw * sh;
if (n != pw * ph) {
throw new RuntimeException();
}
dest = new BufferedImage(sw, sh, BufferedImage.TYPE_INT_RGB);
for (int i = 0; i < sh; ++i) {
for (int j = 0; j < sw; ++j) {
final int x = i * sw + j;
dest.setRGB(j, i, palette.getRGB(x % pw, x / pw));
}
}
l = new JLabel(new ImageIcon(dest));
add(l);
final JButton b = new JButton("Save");
add(b, BorderLayout.SOUTH);
b.addActionListener(new ActionListener() {
@Override
public void actionPerformed(final ActionEvent e) {
try {
ImageIO.write(dest, "png", new File(sourceName + "-" + paletteName + ".png"));
} catch (IOException ex) {
ex.printStackTrace();
}
}
});
}
protected double dist(final int x, final int y) {
double t = 0;
double lx = 0;
double ly = 0;
for (int i = 0; i < 3; ++i) {
final double xi = ((x >> (i * 8)) & 255) * F[i];
final double yi = ((y >> (i * 8)) & 255) * F[i];
final double d = xi - yi;
t += d * d;
lx += xi;
ly += yi;
}
double l = lx - ly;
return t + l * l * LUM_WEIGHT;
}
public void improve() {
final int x = r.nextInt(n);
final int y = r.nextInt(n);
final int sx = source.getRGB(x % sw, x / sw);
final int sy = source.getRGB(y % sw, y / sw);
final int dx = dest.getRGB(x % sw, x / sw);
final int dy = dest.getRGB(y % sw, y / sw);
if (dist(sx, dx) + dist(sy, dy) > dist(sx, dy) + dist(sy, dx)) {
dest.setRGB(x % sw, x / sw, dy);
dest.setRGB(y % sw, y / sw, dx);
}
}
public void update() {
l.repaint();
}
public static void main(final String... args) throws IOException {
final CopyColors x = new CopyColors(SOURCE, PALETTE);
x.setSize(800, 600);
x.setLocationRelativeTo(null);
x.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
x.setVisible(true);
new Timer(DELAY, new ActionListener() {
@Override
public void actionPerformed(final ActionEvent e) {
for (int i = 0; i < COUNT; ++i) {
x.improve();
}
x.update();
}
}).start();
}
}
All the relevant parameters are defined as constants at the beginning of the class.
The program first copies the palette image into the source dimensions, then repeatedly chooses 2 random pixels and swaps them if that would get them closer to the source image. "Closer" is defined using a color distance function that calculates the difference between the r, g, b components (luma-weighted) together with the total luma difference, with a greater weight for luma.
It takes just a few seconds for the shapes to form, but a while longer for the colors to come together. You can save the current image at any time. I usually waited about 1-3 minutes before saving.
Results:
Unlike some other answers, these images were all generated using the exact same parameters (other than the file names).
American Gothic palette
Mona Lisa palette
Starry Night palette
The Scream palette
Spheres palette
I think this is the toughest test and everybody should post their results with this palette:
Sorry, I didn't find the river image very interesting so I haven't included it.
I also added a video at https://www.youtube.com/watch?v=_-w3cKL5teM , it shows what the program does (not exactly in real-time but similar) then it shows the gradual pixel movement using Calvin's python script. Unfortunately the video quality is significantly damaged by youtube's encoding/compression.
Java
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import javax.imageio.ImageIO;
/**
*
* @author Quincunx
*/
public class PixelRearranger {
public static void main(String[] args) throws IOException {
BufferedImage source = ImageIO.read(resource("American Gothic.png"));
BufferedImage palette = ImageIO.read(resource("Mona Lisa.png"));
BufferedImage result = rearrange(source, palette);
ImageIO.write(result, "png", resource("result.png"));
validate(palette, result);
}
public static class MInteger {
int val;
public MInteger(int i) {
val = i;
}
}
public static BufferedImage rearrange(BufferedImage source, BufferedImage palette) {
BufferedImage result = new BufferedImage(source.getWidth(),
source.getHeight(), BufferedImage.TYPE_INT_RGB);
//This creates a list of points in the Source image.
//Then, we shuffle it and will draw points in that order.
List<Point> samples = getPoints(source.getWidth(), source.getHeight());
System.out.println("gotPoints");
//Create a list of colors in the palette.
rgbList = getColors(palette);
Collections.sort(rgbList, rgb);
rbgList = new ArrayList<>(rgbList);
Collections.sort(rbgList, rbg);
grbList = new ArrayList<>(rgbList);
Collections.sort(grbList, grb);
gbrList = new ArrayList<>(rgbList);
Collections.sort(gbrList, gbr);
brgList = new ArrayList<>(rgbList);
Collections.sort(brgList, brg);
bgrList = new ArrayList<>(rgbList);
Collections.sort(bgrList, bgr);
while (!samples.isEmpty()) {
Point currentPoint = samples.remove(0);
int sourceAtPoint = source.getRGB(currentPoint.x, currentPoint.y);
int bestColor = search(new MInteger(sourceAtPoint));
result.setRGB(currentPoint.x, currentPoint.y, bestColor);
}
return result;
}
public static List<Point> getPoints(int width, int height) {
HashSet<Point> points = new HashSet<>(width * height);
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
points.add(new Point(x, y));
}
}
List<Point> newList = new ArrayList<>();
List<Point> corner1 = new LinkedList<>();
List<Point> corner2 = new LinkedList<>();
List<Point> corner3 = new LinkedList<>();
List<Point> corner4 = new LinkedList<>();
Point p1 = new Point(width / 3, height / 3);
Point p2 = new Point(width * 2 / 3, height / 3);
Point p3 = new Point(width / 3, height * 2 / 3);
Point p4 = new Point(width * 2 / 3, height * 2 / 3);
newList.add(p1);
newList.add(p2);
newList.add(p3);
newList.add(p4);
corner1.add(p1);
corner2.add(p2);
corner3.add(p3);
corner4.add(p4);
points.remove(p1);
points.remove(p2);
points.remove(p3);
points.remove(p4);
long seed = System.currentTimeMillis();
Random c1Random = new Random(seed += 179426549); //The prime number pushes the first numbers apart
Random c2Random = new Random(seed += 179426549); //Or at least I think it does.
Random c3Random = new Random(seed += 179426549);
Random c4Random = new Random(seed += 179426549);
Dir NW = Dir.NW;
Dir N = Dir.N;
Dir NE = Dir.NE;
Dir W = Dir.W;
Dir E = Dir.E;
Dir SW = Dir.SW;
Dir S = Dir.S;
Dir SE = Dir.SE;
while (!points.isEmpty()) {
putPoints(newList, corner1, c1Random, points, NW, N, NE, W, E, SW, S, SE);
putPoints(newList, corner2, c2Random, points, NE, N, NW, E, W, SE, S, SW);
putPoints(newList, corner3, c3Random, points, SW, S, SE, W, E, NW, N, NE);
putPoints(newList, corner4, c4Random, points, SE, S, SW, E, W, NE, N, NW);
}
return newList;
}
public static enum Dir {
NW(-1, -1), N(0, -1), NE(1, -1), W(-1, 0), E(1, 0), SW(-1, 1), S(0, 1), SE(1, 1);
final int dx, dy;
private Dir(int dx, int dy) {
this.dx = dx;
this.dy = dy;
}
public Point add(Point p) {
return new Point(p.x + dx, p.y + dy);
}
}
public static void putPoints(List<Point> newList, List<Point> listToAddTo, Random rand,
HashSet<Point> points, Dir... adj) {
List<Point> newPoints = new LinkedList<>();
for (Iterator<Point> iter = listToAddTo.iterator(); iter.hasNext();) {
Point p = iter.next();
Point pul = adj[0].add(p);
Point pu = adj[1].add(p);
Point pur = adj[2].add(p);
Point pl = adj[3].add(p);
Point pr = adj[4].add(p);
Point pbl = adj[5].add(p);
Point pb = adj[6].add(p);
Point pbr = adj[7].add(p);
int allChosen = 0;
if (points.contains(pul)) {
if (rand.nextInt(5) == 0) {
allChosen++;
newPoints.add(pul);
newList.add(pul);
points.remove(pul);
}
} else {
allChosen++;
}
if (points.contains(pu)) {
if (rand.nextInt(5) == 0) {
allChosen++;
newPoints.add(pu);
newList.add(pu);
points.remove(pu);
}
} else {
allChosen++;
}
if (points.contains(pur)) {
if (rand.nextInt(3) == 0) {
allChosen++;
newPoints.add(pur);
newList.add(pur);
points.remove(pur);
}
} else {
allChosen++;
}
if (points.contains(pl)) {
if (rand.nextInt(5) == 0) {
allChosen++;
newPoints.add(pl);
newList.add(pl);
points.remove(pl);
}
} else {
allChosen++;
}
if (points.contains(pr)) {
if (rand.nextInt(2) == 0) {
allChosen++;
newPoints.add(pr);
newList.add(pr);
points.remove(pr);
}
} else {
allChosen++;
}
if (points.contains(pbl)) {
if (rand.nextInt(5) == 0) {
allChosen++;
newPoints.add(pbl);
newList.add(pbl);
points.remove(pbl);
}
} else {
allChosen++;
}
if (points.contains(pb)) {
if (rand.nextInt(3) == 0) {
allChosen++;
newPoints.add(pb);
newList.add(pb);
points.remove(pb);
}
} else {
allChosen++;
}
if (points.contains(pbr)) {
newPoints.add(pbr);
newList.add(pbr);
points.remove(pbr);
}
if (allChosen == 7) {
iter.remove();
}
}
listToAddTo.addAll(newPoints);
}
public static List<MInteger> getColors(BufferedImage img) {
int width = img.getWidth();
int height = img.getHeight();
List<MInteger> colors = new ArrayList<>(width * height);
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
colors.add(new MInteger(img.getRGB(x, y)));
}
}
return colors;
}
public static int search(MInteger color) {
int rgbIndex = binarySearch(rgbList, color, rgb);
int rbgIndex = binarySearch(rbgList, color, rbg);
int grbIndex = binarySearch(grbList, color, grb);
int gbrIndex = binarySearch(gbrList, color, gbr);
int brgIndex = binarySearch(brgList, color, brg);
int bgrIndex = binarySearch(bgrList, color, bgr);
double distRgb = dist(rgbList.get(rgbIndex), color);
double distRbg = dist(rbgList.get(rbgIndex), color);
double distGrb = dist(grbList.get(grbIndex), color);
double distGbr = dist(gbrList.get(gbrIndex), color);
double distBrg = dist(brgList.get(brgIndex), color);
double distBgr = dist(bgrList.get(bgrIndex), color);
double minDist = Math.min(Math.min(Math.min(Math.min(Math.min(
distRgb, distRbg), distGrb), distGbr), distBrg), distBgr);
MInteger ans;
if (minDist == distRgb) {
ans = rgbList.get(rgbIndex);
} else if (minDist == distRbg) {
ans = rbgList.get(rbgIndex);
} else if (minDist == distGrb) {
ans = grbList.get(grbIndex);
} else if (minDist == distGbr) {
ans = grbList.get(grbIndex);
} else if (minDist == distBrg) {
ans = grbList.get(rgbIndex);
} else {
ans = grbList.get(grbIndex);
}
rgbList.remove(ans);
rbgList.remove(ans);
grbList.remove(ans);
gbrList.remove(ans);
brgList.remove(ans);
bgrList.remove(ans);
return ans.val;
}
public static int binarySearch(List<MInteger> list, MInteger val, Comparator<MInteger> cmp){
int index = Collections.binarySearch(list, val, cmp);
if (index < 0) {
index = ~index;
if (index >= list.size()) {
index = list.size() - 1;
}
}
return index;
}
public static double dist(MInteger color1, MInteger color2) {
int c1 = color1.val;
int r1 = (c1 & 0xFF0000) >> 16;
int g1 = (c1 & 0x00FF00) >> 8;
int b1 = (c1 & 0x0000FF);
int c2 = color2.val;
int r2 = (c2 & 0xFF0000) >> 16;
int g2 = (c2 & 0x00FF00) >> 8;
int b2 = (c2 & 0x0000FF);
int dr = r1 - r2;
int dg = g1 - g2;
int db = b1 - b2;
return Math.sqrt(dr * dr + dg * dg + db * db);
}
//This method is here solely for my ease of use (I put the files under <Project Name>/Resources/ )
public static File resource(String fileName) {
return new File(System.getProperty("user.dir") + "/Resources/" + fileName);
}
static List<MInteger> rgbList;
static List<MInteger> rbgList;
static List<MInteger> grbList;
static List<MInteger> gbrList;
static List<MInteger> brgList;
static List<MInteger> bgrList;
static Comparator<MInteger> rgb = (color1, color2) -> color1.val - color2.val;
static Comparator<MInteger> rbg = (color1, color2) -> {
int c1 = color1.val;
int c2 = color2.val;
c1 = ((c1 & 0xFF0000)) | ((c1 & 0x00FF00) >> 8) | ((c1 & 0x0000FF) << 8);
c2 = ((c2 & 0xFF0000)) | ((c2 & 0x00FF00) >> 8) | ((c2 & 0x0000FF) << 8);
return c1 - c2;
};
static Comparator<MInteger> grb = (color1, color2) -> {
int c1 = color1.val;
int c2 = color2.val;
c1 = ((c1 & 0xFF0000) >> 8) | ((c1 & 0x00FF00) << 8) | ((c1 & 0x0000FF));
c2 = ((c2 & 0xFF0000) >> 8) | ((c2 & 0x00FF00) << 8) | ((c2 & 0x0000FF));
return c1 - c2;
};
static Comparator<MInteger> gbr = (color1, color2) -> {
int c1 = color1.val;
int c2 = color2.val;
c1 = ((c1 & 0xFF0000) >> 16) | ((c1 & 0x00FF00) << 8) | ((c1 & 0x0000FF) << 8);
c2 = ((c2 & 0xFF0000) >> 16) | ((c2 & 0x00FF00) << 8) | ((c2 & 0x0000FF) << 8);
return c1 - c2;
};
static Comparator<MInteger> brg = (color1, color2) -> {
int c1 = color1.val;
int c2 = color2.val;
c1 = ((c1 & 0xFF0000) >> 8) | ((c1 & 0x00FF00) >> 8) | ((c1 & 0x0000FF) << 16);
c2 = ((c2 & 0xFF0000) >> 8) | ((c2 & 0x00FF00) >> 8) | ((c2 & 0x0000FF) << 16);
return c1 - c2;
};
static Comparator<MInteger> bgr = (color1, color2) -> {
int c1 = color1.val;
int c2 = color2.val;
c1 = ((c1 & 0xFF0000) >> 16) | ((c1 & 0x00FF00)) | ((c1 & 0x0000FF) << 16);
c2 = ((c2 & 0xFF0000) >> 16) | ((c2 & 0x00FF00)) | ((c2 & 0x0000FF) << 16);
return c1 - c2;
};
public static void validate(BufferedImage palette, BufferedImage result) {
List<Integer> paletteColors = getTrueColors(palette);
List<Integer> resultColors = getTrueColors(result);
Collections.sort(paletteColors);
Collections.sort(resultColors);
System.out.println(paletteColors.equals(resultColors));
}
public static List<Integer> getTrueColors(BufferedImage img) {
int width = img.getWidth();
int height = img.getHeight();
List<Integer> colors = new ArrayList<>(width * height);
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
colors.add(img.getRGB(x, y));
}
}
Collections.sort(colors);
return colors;
}
}
My approach works by finding the closest color to each pixel (well, likely the closest), in 3-space, since colors are 3D.
This works by creating a list of all the points we need to fill and a list of all the possible colors we can use. We randomize the list of points (so the image will turn out better), then we go through each point and get the color of the source image.
Update: I used to simply binary search, so red matched better than green which matched better than blue. I now changed it to do six binary searches (all of the possible permutations), then choose the closest color. It only takes ~6 times as long (ie 1 minute). While the pictures are still grainy, the colors match better.
Update 2: I no longer randomize the list. Instead, I choose 4 points following the rule of thirds, then randomly arrange the points, with preference to filling out the center.
Note: See the revision history for the old pictures.
Mona Lisa -> River:
Mona Lisa -> American Gothic:
Mona Lisa -> Raytraced Spheres:
Starry Night -> Mona Lisa:
Here's an animated Gif showing how the image was constructed:
And showing the pixels being taken from the Mona Lisa:
Perl, with Lab color space and dithering
Note: Now I have a C solution too.
Uses a similar approach to aditsu's, (choose two random positions, and swap the pixels at those positions if it would make the image more like the target image), with two major improvements:
- Uses the CIE Lab* color space to compare colors — the Euclidean metric on this space is a very good approximation to the perceptual difference between two colors, so the color mappings should be more accurate than RGB or even HSV/HSL.
- After an initial pass putting pixels in the best possible single position, it does an additional pass with a random dither. Instead of comparing the pixel values at the two swap positions, it computes the average pixel value of a 3x3 neighborhood centered at the swap positions. If a swap improves the average colors of the neighborhoods it's allowed, even if it makes individual pixels less accurate. For some image pairs this has a dubious effect on the quality (and makes the palette effect less striking), but for some (like spheres -> anything) it helps quite a bit. The "detail" factor emphasizes the central pixel to a variable degree. Increasing it decreases the overall amount of dither, but retains more fine detail from the target image. The dithered optimization is slower, which is why we run it on the output of the non-dithered optimization as a starting point.
Averaging Lab values, like the dither does, isn't really justified (they should be converted to XYZ, averaged, and converted back) but it works just fine for these purposes.
These images have termination limits of 100 and 200 (end the first phase when less than 1 in 5000 swaps is accepted, and the second phase at 1 in 2500), and a dithering detail factor of 12 (a little tighter dither than the previous set). At this super high quality setting, the images take a long time to generate, but with parallelization the whole job still finishes within an hour on my 6-core box. Bumping the values up to 500 or so finishes images within a few minutes, they just look a little less polished. I wanted to show off the algorithm to the best here.
Code is not by any means pretty:
#!/usr/bin/perl
use strict;
use warnings;
use Image::Magick;
use Graphics::ColorObject 'RGB_to_Lab';
use List::Util qw(sum max);
my $source = Image::Magick->new;
$source->Read($ARGV[0]);
my $target = Image::Magick->new;
$target->Read($ARGV[1]);
my ($limit1, $limit2, $detail) = @ARGV[2,3,4];
my ($width, $height) = ($target->Get('width'), $target->Get('height'));
# Transfer the pixels of the $source onto a new canvas with the diemnsions of $target
$source->Set(magick => 'RGB');
my $img = Image::Magick->new(size => "${width}x${height}", magick => 'RGB', depth => 8);
$img->BlobToImage($source->ImageToBlob);
my ($made, $rejected) = (0,0);
system("rm anim/*.png");
my (@img_lab, @target_lab);
for my $x (0 .. $width) {
for my $y (0 .. $height) {
$img_lab[$x][$y] = RGB_to_Lab([$img->getPixel(x => $x, y => $y)], 'sRGB');
$target_lab[$x][$y] = RGB_to_Lab([$target->getPixel(x => $x, y => $y)], 'sRGB');
}
}
my $n = 0;
my $frame = 0;
my $mode = 1;
while (1) {
$n++;
my $swap = 0;
my ($x1, $x2, $y1, $y2) = (int rand $width, int rand $width, int rand $height, int rand $height);
my ($dist, $dist_swapped);
if ($mode == 1) {
$dist = (sum map { ($img_lab[$x1][$y1][$_] - $target_lab[$x1][$y1][$_])**2 } 0..2)
+ (sum map { ($img_lab[$x2][$y2][$_] - $target_lab[$x2][$y2][$_])**2 } 0..2);
$dist_swapped = (sum map { ($img_lab[$x2][$y2][$_] - $target_lab[$x1][$y1][$_])**2 } 0..2)
+ (sum map { ($img_lab[$x1][$y1][$_] - $target_lab[$x2][$y2][$_])**2 } 0..2);
} else { # dither mode
my $xoffmin = ($x1 == 0 || $x2 == 0 ? 0 : -1);
my $xoffmax = ($x1 == $width - 1 || $x2 == $width - 1 ? 0 : 1);
my $yoffmin = ($y1 == 0 || $y2 == 0 ? 0 : -1);
my $yoffmax = ($y1 == $height - 1 || $y2 == $height - 1 ? 0 : 1);
my (@img1, @img2, @target1, @target2, $points);
for my $xoff ($xoffmin .. $xoffmax) {
for my $yoff ($yoffmin .. $yoffmax) {
$points++;
for my $chan (0 .. 2) {
$img1[$chan] += $img_lab[$x1+$xoff][$y1+$yoff][$chan];
$img2[$chan] += $img_lab[$x2+$xoff][$y2+$yoff][$chan];
$target1[$chan] += $target_lab[$x1+$xoff][$y1+$yoff][$chan];
$target2[$chan] += $target_lab[$x2+$xoff][$y2+$yoff][$chan];
}
}
}
my @img1s = @img1;
my @img2s = @img2;
for my $chan (0 .. 2) {
$img1[$chan] += $img_lab[$x1][$y1][$chan] * ($detail - 1);
$img2[$chan] += $img_lab[$x2][$y2][$chan] * ($detail - 1);
$target1[$chan] += $target_lab[$x1][$y1][$chan] * ($detail - 1);
$target2[$chan] += $target_lab[$x2][$y2][$chan] * ($detail - 1);
$img1s[$chan] += $img_lab[$x2][$y2][$chan] * $detail - $img_lab[$x1][$y1][$chan];
$img2s[$chan] += $img_lab[$x1][$y1][$chan] * $detail - $img_lab[$x2][$y2][$chan];
}
$dist = (sum map { ($img1[$_] - $target1[$_])**2 } 0..2)
+ (sum map { ($img2[$_] - $target2[$_])**2 } 0..2);
$dist_swapped = (sum map { ($img1s[$_] - $target1[$_])**2 } 0..2)
+ (sum map { ($img2s[$_] - $target2[$_])**2 } 0..2);
}
if ($dist_swapped < $dist) {
my @pix1 = $img->GetPixel(x => $x1, y => $y1);
my @pix2 = $img->GetPixel(x => $x2, y => $y2);
$img->SetPixel(x => $x1, y => $y1, color => \@pix2);
$img->SetPixel(x => $x2, y => $y2, color => \@pix1);
($img_lab[$x1][$y1], $img_lab[$x2][$y2]) = ($img_lab[$x2][$y2], $img_lab[$x1][$y1]);
$made ++;
} else {
$rejected ++;
}
if ($n % 50000 == 0) {
# print "Made: $made Rejected: $rejected\n";
$img->Write('png:out.png');
system("cp", "out.png", sprintf("anim/frame%05d.png", $frame++));
if ($mode == 1 and $made < $limit1) {
$mode = 2;
system("cp", "out.png", "nodither.png");
} elsif ($mode == 2 and $made < $limit2) {
last;
}
($made, $rejected) = (0, 0);
}
}
Results
American Gothic palette
Little difference here with dithering or not.
Mona Lisa palette
Dithering reduces the banding on the spheres, but isn't especially pretty.
Starry Night palette
Mona Lisa retains a bit more detail with dithering. Spheres is about the same situation as last time.
Scream palette
Starry Night without dithering is the most awesome thing ever. Dithering makes it more photo-accurate, but far less interesting.
Spheres palette
As aditsu says, the true test. I think I pass.
Dithering helps immensely with American Gothic and Mona Lisa, mixing some grays and other colors in with the more intense pixels to produce semi-accurate skin tones instead of horrible blotches. The Scream is affected far less.
Camaro - Mustang
Source images from flawr's post.
Camaro: 
Mustang: 
Camaro palette
Looks pretty good without dither.
A "tight" dither (same detail factor as above) doesn't change much, just adds a little detail in the highlights on the hood and roof.
A "loose" dither (detail factor dropped to 6) really smooths out the tonality, and a lot more detail is visible through the windshield, but ditherng patterns are more obvious everywhere.
Mustang palette
Parts of the car look great, but the gray pixels look glitchy. What's worse, all the darker yellow pixels got distributed over the red Camaro body, and the non-dithering algorithm can't find anything to do with the lighter ones (moving them into the car would make the match worse, and moving them to another spot on the background makes no net difference), so there's a ghost-Mustang in the background.
Dithering is able to spread those extra yellow pixels around so they don't touch, scattering them more-or-less evenly over the background in the process. The highlights and shadows on the car look a little better.
Again, the loose dither has the evenest tonality, reveals more detail on the headlights and windshield. The car almost looks red again. background is clumpier for some reason. Not sure if I like it.
Video
(HQ Link)