American Gothic in the palette of Mona Lisa: Rearrange the pixels You are given two true color images, the Source and the Palette. They do not necessarily have the same dimensions but it is guaranteed that their areas are the same, i.e. they have the same number of pixels.

Your task is to create an algorithm that makes the most accurate looking copy of the Source by only using the pixels in the Palette. Each pixel in the Palette must be used exactly once in a unique position in this copy. The copy must have the same dimensions as the Source.

This Python script can be used ensure these constraints are met:

from PIL import Image
def check(palette, copy):
    palette = sorted(Image.open(palette).convert('RGB').getdata())
    copy = sorted(Image.open(copy).convert('RGB').getdata())
    print 'Success' if copy == palette else 'Failed'

check('palette.png', 'copy.png')


Here are several pictures for testing. They all have the same area. Your algorithm should work for any two images with equal areas, not just American Gothic and the Mona Lisa. You should of course show your output.








Thanks to Wikipedia for the images of famous paintings.

Scoring

This is a popularity contest so the highest voted answer wins. But I'm sure there's lots of ways to be creative with this!

Animation

millinon had the idea that it would be cool to see the pixels rearrange themselves. I thought so too so I wrote this Python script that takes two images made of the same colors and draws the intermediate images between them. Update: I just revised it so each pixel moves the minimum amount it has to. It is no longer random.

First is the Mona Lisa turning into aditsu's American Gothic. Next is bitpwner's American Gothic (from Mona Lisa) turning into aditsu's. It's amazing that the two versions share the exact same color palette.




The results are really quite astounding. Here is aditsu's rainbow Mona Lisa (slowed to show detail).



This last animation is not necessarily related to the contest. It shows what happens when my script is used to rotate an image 90 degrees.
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(&quot;serial&quot;)
public class CopyColors extends JFrame {
    private static final String SOURCE = &quot;spheres&quot;;
    private static final String PALETTE = &quot;mona&quot;;
    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(&quot;CopyColors by aditsu&quot;);
        source = ImageIO.read(new File(sourceName + &quot;.png&quot;));
        final BufferedImage palette = ImageIO.read(new File(paletteName + &quot;.png&quot;));
        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 &lt; sh; ++i) {
            for (int j = 0; j &lt; 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(&quot;Save&quot;);
        add(b, BorderLayout.SOUTH);
        b.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(final ActionEvent e) {
                try {
                    ImageIO.write(dest, &quot;png&quot;, new File(sourceName + &quot;-&quot; + paletteName + &quot;.png&quot;));
                } 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 &lt; 3; ++i) {
            final double xi = ((x &gt;&gt; (i * 8)) &amp; 255) * F[i];
            final double yi = ((y &gt;&gt; (i * 8)) &amp; 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) &gt; 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 &lt; 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. &quot;Closer&quot; 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.