### 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 Imagedef 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.

Must the process be entirely unguided, or is it permitted to give the program hints about the parts of the image which are most important (e.g. Lisa's face)?

@Quincunx I do know that only one is a png, but I just made sure that my script only considers the RGB values in each image. The strings 'palette.png' and 'copy.png' were just placeholders since PIL will load most image types. If it helps anyone I could put all the images in the same format, say bmp.

@PeterTaylor I'd say that you should not have to manually tell the program what parts of the image to put more detail into. That goes against the idea of your algorithm working in the general case just given two images. You may definitely do this programmatically though. (I'd still love to see your output even if you stick with manual detailing!)

To increase the hits on your question you may wish to consider entitling it, "American Gothic in the palette of Mona Lisa: Rearrange the pixels"

Hi, I just want to congratulate you on this original challenge! Very refreshing and interesting.

Thanks for the support @bolov. I just added a couple more images for some more variety.

@Calvin'sHobbies I would definitely do this challenge, if I knew how to work with images :P

@qwr It is not that difficult - can you tell me a language you know? I am pretty sure you can easily edit images in most languages - and its great fun=) PS: Calvin'sHobbies you are making sure you keep us busy by adding new images, eh!

@flawr I mostly do python. The reason I was hesitant to do this problem is that I wasn't sure that simple luminance matching would work; I wanted maybe edge detection but that's a hard task.

@qwr have a look at the codes here, they did similar things (but I do not know how easy/difficult): https://codegolf.stackexchange.com/questions/11141/encode-images-into-tweets-extreme-image-compression-edition

I'm glad this isn't a [code-golf].

Love the animation! :D

Fantastic job with the gif!

The bitpwner's AG -> aditsu's is bizarre one. Can't believe that they indeed share the same colours. I guess aditsu's approach, in case of sorting takes into account surrounding pixels as well? Will take a look at that when I've got a moment

For the record, the optimal solution can be computed in O(N^3) using the Hungarian algorithm. Of course, it's not very practical for N = 295 x 357 However, if you enforce a constraint that a point only be sent to one of its 10 closest neighbors, it starts to become tractable.

@Ben I just included a shorter version of the validity checker but the animation script is quite long and is somewhat of an afterthought on an question that's already getting too long.

So how long would it take to brute force all combinations of the pixels, and choose the picture with the shortest averaged pixel distance?

http://gif-explode.com/?explode=http://i.stack.imgur.com/GEeS4.gif how come the frames look wrong? I was interested about the rotating image example. But the last frame when decomposing it is simply incorrect.

@Cruncher I know. The original images aren't like that, it's just a gif artifact. I may make an hd video of these animations soon so they can be viewed properly.

@Calvin'sHobbies http://jsfiddle.net/eithe/J7jEk/31/ - boredom got to me :D

@eithedog Very nice! If you want I actually scaled down my tree, the original is at http://i.stack.imgur.com/PjUCP.png.

@Calvin'sHobbies - cheers! now with the originals I'll have to figure out why the hell is red moving :D (at least black stays in place)

While doing the 90° turn with the tree, the borders should remain mainly untouched. So you are not using the travel distance optimized version, do you?

• # 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).

### 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.

Eww. You're extending JFrame! Nice pictures by the way.

@Quincunx And I'm not calling invokeLater either, shoot me :p Also, thanks :)

After some more testing, it looks like it converges faster to similar results if I use a lower LUM_WEIGHT. Oh well...

When in doubt, brute force it? Seems like an excellent solution, I'd love to see an animation for this, maybe even a video instead of a gif.

wow, random magic wins

@aditsu Would it be alright if I used some of your images in a YouTube video to showcase my animation script?

You could extend the algorithm a bit to a full simulated annealing for a small improvement. What you're doing is already very close (but it's greedy). Finding the permutation that minimizes the distance seems like a hard optimization problem, so this kind of heuristic is fitting. @Lilienthal this is not brute forcing, it's actually close to commonly used optimization techniques.

This algorithm has the best results by far. And it is so simple. This makes it a clear winner for me.

Can you provide a precompiled version of your code? I think I have a compiler, but not everyone does / knows how to. A JAR will do.

@JanDvorak I guess I could, but I'd have to change it because the paths are hardcoded, figure out where to host it, etc

Well done, needless to say you have my vote :)

I modified this to stop itself when it doesn't swap pixels 5000 times in a row. It takes 13 seconds to do that on spheres palette mona lisa. http://pastebin.com/qm2DfnTv

Very interesting algorithm, definitely deserves the winner imo. Unless there is any conversion done that I cannot see in your initial image setup, it should be a lot faster if you copy the whole array at once: `int[] rdbData = source.getRGB(0, 0, source.getWidth(), source.getHeight(), (int[]) null, 0, source.getWidth());` then `dest.setRGB(0, 0, dest.getWidth(), dest.getHeight(), rdbData , 0, dest.getWidth());`

I made a fastest-algorithm challenge for your idea as this seems to be very popular. See here