American Gothic in the palette of Mona Lisa: Rearrange the pixels

Question

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.

Answer 1

C++, version 2.1

UPDATED code and images to account for an error I noticed on the river images: FreeImage stores bitmap bytes on scanline boundaries aligned to 32 bits. I needed to account for the pitch in some cases, like river.

Slower than my first answer, taking approximately 15 seconds per image on my machine now, but I prefer most of the results. Adding this as a second answer, because it generates vastly different results in all cases.

This program is a two-pass algorithm; pass 1 is like before, an extremely quick algorithm that makes two lists of pixels sorted by a weighted brightness, and matches up the pairs by index values, copying the results to the destination bitmap.

Pass 2 is a version of aditsu's "random swap" concept. I run random swaps on two pixels in the destination bitmap if the swap would reduce the 'error measurement' in the destination, and terminate this after a threshold of 10000 sequential misses. Increasing the threshold would increase quality, but at the expense of time.

Code

/* Inputs: 2 image files of same area
Outputs: image1 made from pixels of image2*/
#include <iostream>
#include <stdlib.h>
#include "FreeImage.h"
#include <vector>
#include <algorithm>

class pixel
{
public:
    int x, y;
    BYTE r, g, b;
    float val;  //color value; weighted 'brightness'
};

bool sortByColorVal(const pixel &lhs, const pixel &rhs) { return lhs.val > rhs.val; }

FIBITMAP* GenericLoader(const char* lpszPathName, int flag) 
{
    FREE_IMAGE_FORMAT fif = FIF_UNKNOWN;

    // check the file signature and deduce its format
    // (the second argument is currently not used by FreeImage)
    fif = FreeImage_GetFileType(lpszPathName, 0);
    if (fif == FIF_UNKNOWN) 
    {
        // no signature ?
        // try to guess the file format from the file extension
        fif = FreeImage_GetFIFFromFilename(lpszPathName);
    }
    // check that the plugin has reading capabilities ...
    if ((fif != FIF_UNKNOWN) && FreeImage_FIFSupportsReading(fif)) 
    {
        // ok, let's load the file
        FIBITMAP *dib = FreeImage_Load(fif, lpszPathName, flag);
        // unless a bad file format, we are done !
        return dib;
    }
    return NULL;
}

bool GenericWriter(FIBITMAP* dib, const char* lpszPathName, int flag) 
{
    FREE_IMAGE_FORMAT fif = FIF_UNKNOWN;
    BOOL bSuccess = FALSE;

    if (dib) 
    {
        // try to guess the file format from the file extension
        fif = FreeImage_GetFIFFromFilename(lpszPathName);
        if (fif != FIF_UNKNOWN) 
        {
            // check that the plugin has sufficient writing and export capabilities ...
            WORD bpp = FreeImage_GetBPP(dib);
            if (FreeImage_FIFSupportsWriting(fif) && FreeImage_FIFSupportsExportBPP(fif, bpp)) 
            {
                // ok, we can save the file
                bSuccess = FreeImage_Save(fif, dib, lpszPathName, flag);
                // unless an abnormal bug, we are done !
            }
        }
    }
    return (bSuccess == TRUE) ? true : false;
}

void FreeImageErrorHandler(FREE_IMAGE_FORMAT fif, const char *message) 
{
    std::cout << std::endl << "*** ";
    if (fif != FIF_UNKNOWN) 
    {
        std::cout << "ERROR: " << FreeImage_GetFormatFromFIF(fif) << " Format" << std::endl;
    }
    std::cout << message;
    std::cout << " ***" << std::endl;
}

FIBITMAP* Convert24BPP(FIBITMAP* dib)
{
    if (FreeImage_GetBPP(dib) == 24) return dib;

    FIBITMAP *dib2 = FreeImage_ConvertTo24Bits(dib);
    FreeImage_Unload(dib);
    return dib2;
}
// ----------------------------------------------------------

int main(int argc, char **argv)
{
    // call this ONLY when linking with FreeImage as a static library
#ifdef FREEIMAGE_LIB
    FreeImage_Initialise();
#endif

    FIBITMAP *src = NULL, *pal = NULL;
    int result = EXIT_FAILURE;

    // initialize my own FreeImage error handler
    FreeImage_SetOutputMessage(FreeImageErrorHandler);

    // print version
    std::cout << "FreeImage version : " << FreeImage_GetVersion() << std::endl;

    if (argc != 4) 
    {
        std::cout << "USAGE : Pic2Pic <source image> <palette image> <output file name>" << std::endl;
        return EXIT_FAILURE;
    }

    // Load the src image
    src = GenericLoader(argv[1], 0);
    if (src) 
    {
        // load the palette image
        pal = GenericLoader(argv[2], 0);

        if (pal) 
        {
            //first make sure everything is 24 bit:
            src = Convert24BPP(src);
            pal = Convert24BPP(pal);

            //compare areas
            // if(!samearea) return EXIT_FAILURE;
            unsigned int width_src = FreeImage_GetWidth(src);
            unsigned int height_src = FreeImage_GetHeight(src);
            unsigned int width_pal = FreeImage_GetWidth(pal);
            unsigned int height_pal = FreeImage_GetHeight(pal);

            //strides! FreeImage stores bitmap scanlines on 32-bit boundaries...old-school shit I haven't had to deal with in a while ;)
            unsigned int pitch_src = FreeImage_GetPitch(src);
            unsigned int pitch_pal = FreeImage_GetPitch(pal);

            if (width_src * height_src != width_pal * height_pal)
            {
                std::cout << "ERROR: source and palette images do not have the same pixel area." << std::endl;
                result = EXIT_FAILURE;
            }
            else
            {
                //go to work!               

                //retrieve the image data
                BYTE *bits_src = FreeImage_GetBits(src);
                BYTE *bits_pal = FreeImage_GetBits(pal);

                //make destination image
                FIBITMAP *dst = FreeImage_ConvertTo24Bits(src);
                BYTE *bits_dst = FreeImage_GetBits(dst);

                //probably same as src, but eh...
                unsigned int pitch_dst = FreeImage_GetPitch(dst);

                //make a vector of all the src pixels that we can sort by color value
                std::vector<pixel> src_pixels;
                for (unsigned int y = 0; y < height_src; ++y)
                {
                    for (unsigned int x = 0; x < width_src; ++x)
                    {
                        pixel p;
                        p.x = x;
                        p.y = y;

                        p.b = bits_src[y*pitch_src + x * 3];
                        p.g = bits_src[y*pitch_src + x * 3 + 1];
                        p.r = bits_src[y*pitch_src + x * 3 + 2];

                        //calculate color value using a weighted brightness for each channel
                        //p.val = 0.2126f * p.r + 0.7152f * p.g + 0.0722f * p.b; //from http://www.poynton.com/notes/colour_and_gamma/ColorFAQ.html
                        p.val = 0.5f * p.r + p.g + 0.1f * p.b;                      

                        src_pixels.push_back(p);
                    }
                }

                //sort by color value
                std::sort(src_pixels.begin(), src_pixels.end(), sortByColorVal);

                //make a vector of all palette pixels we can use
                std::vector<pixel> pal_pixels;

                for (unsigned int y = 0; y < height_pal; ++y)
                {
                    for (unsigned int x = 0; x < width_pal; ++x)
                    {
                        pixel p;

                        p.b = bits_pal[y*pitch_pal + x * 3];
                        p.g = bits_pal[y*pitch_pal + x * 3 + 1];
                        p.r = bits_pal[y*pitch_pal + x * 3 + 2];

                        p.val = 0.5f * p.r + p.g + 0.1f * p.b;

                        pal_pixels.push_back(p);
                    }
                }

                //sort by color value
                std::sort(pal_pixels.begin(), pal_pixels.end(), sortByColorVal);

                //for each src pixel, match it with same index palette pixel and copy to destination
                for (unsigned int i = 0; i < width_src * height_src; ++i)
                {
                    bits_dst[src_pixels[i].y * pitch_src + src_pixels[i].x * 3] = pal_pixels[i].b;
                    bits_dst[src_pixels[i].y * pitch_src + src_pixels[i].x * 3 + 1] = pal_pixels[i].g;
                    bits_dst[src_pixels[i].y * pitch_src + src_pixels[i].x * 3 + 2] = pal_pixels[i].r;
                }

                //improve the destination via random swaps until we miss threshold swaps in a row
                unsigned int threshold = 10000;
                unsigned int missed = 0;
                unsigned int index1, index2, index1_dst, index2_dst;
                unsigned int distance_squared_current, distance_squared_swapped;
                BYTE tr, tg, tb;
                unsigned int x1, x2, y1, y2;

                srand(42); //for good luck!...and, er, repeatable results. Should maybe re-seed periodically if threshold is high.
                for (;;)
                {
                    //not assuming pitch_src == pitch_dst, for now

                    x1 = rand() % width_src;
                    x2 = rand() % width_src;
                    y1 = rand() % height_src;
                    y2 = rand() % height_src;
                    index1 = (x1) * 3 + (y1) * pitch_src;
                    index2 = (x2) * 3 + (y2) * pitch_src;
                    index1_dst = (x1)* 3 + (y1)* pitch_dst;
                    index2_dst = (x2)* 3 + (y2)* pitch_dst;

                    distance_squared_current = 
                        ((bits_src[index1 + 2] - bits_dst[index1_dst + 2]) * (bits_src[index1 + 2] - bits_dst[index1_dst + 2]) >> 3) +
                        (bits_src[index1 + 1] - bits_dst[index1_dst + 1]) * (bits_src[index1 + 1] - bits_dst[index1_dst + 1]) +
                        ((bits_src[index1] - bits_dst[index1_dst]) * (bits_src[index1] - bits_dst[index1_dst]) >> 1 )+
                        ((bits_src[index2 + 2] - bits_dst[index2_dst + 2]) * (bits_src[index2 + 2] - bits_dst[index2_dst + 2]) >> 3) +
                        (bits_src[index2 + 1] - bits_dst[index2_dst + 1]) * (bits_src[index2 + 1] - bits_dst[index2_dst + 1]) +
                        ((bits_src[index2] - bits_dst[index2_dst]) * (bits_src[index2] - bits_dst[index2_dst]) >> 1);

                    distance_squared_swapped = 
                        ((bits_src[index1 + 2] - bits_dst[index2_dst + 2]) * (bits_src[index1 + 2] - bits_dst[index2_dst + 2]) >> 3) +
                        (bits_src[index1 + 1] - bits_dst[index2_dst + 1]) * (bits_src[index1 + 1] - bits_dst[index2_dst + 1]) +
                        ((bits_src[index1] - bits_dst[index2_dst]) * (bits_src[index1] - bits_dst[index2_dst]) >> 1)+
                        ((bits_src[index2 + 2] - bits_dst[index1_dst + 2]) * (bits_src[index2 + 2] - bits_dst[index1_dst + 2]) >> 3) +
                        (bits_src[index2 + 1] - bits_dst[index1_dst + 1]) * (bits_src[index2 + 1] - bits_dst[index1_dst + 1]) +
                        ((bits_src[index2] - bits_dst[index1_dst]) * (bits_src[index2] - bits_dst[index1_dst]) >> 1);

                    if (distance_squared_swapped < distance_squared_current)
                    {
                        missed = 0;

                        tb = bits_dst[index1_dst];
                        tg = bits_dst[index1_dst + 1];
                        tr = bits_dst[index1_dst + 2];

                        bits_dst[index1_dst] = bits_dst[index2_dst];                        
                        bits_dst[index1_dst + 1] = bits_dst[index2_dst + 1];
                        bits_dst[index1_dst + 2] = bits_dst[index2_dst + 2];

                        bits_dst[index2_dst] = tb;                      
                        bits_dst[index2_dst + 1] = tg;
                        bits_dst[index2_dst + 2] = tr;
                    }

                    missed += 1;
                    if (missed > threshold) break; //done improvements
                }

                // Save the destination image
                bool bSuccess = GenericWriter(dst, argv[3], 0);
                if (!bSuccess)
                {
                    std::cout << "ERROR: unable to save " << argv[3] << std::endl;
                    std::cout << "This format does not support 24-bit images" << std::endl;
                    result = EXIT_FAILURE;
                }
                else result = EXIT_SUCCESS;

                FreeImage_Unload(dst);
            }

            // Free pal
            FreeImage_Unload(pal);
        }

        // Free src
        FreeImage_Unload(src);
    }

#ifdef FREEIMAGE_LIB
    FreeImage_DeInitialise();
#endif

    if (result == EXIT_SUCCESS) std::cout << "SUCCESS!" << std::endl;
    else std::cout << "FAILURE!" << std::endl;
    return result;
}

Results

American Gothic palette

Mona Lisa palette

Rainbow palette (toughy for this program!)

River palette

Scream palette

Starry Night palette

and for fun: Mustang in the Camaro palette

Sorry for the length of this post, but I loved this puzzle; it kept me thinking and tinkering, off and on all day.

Answer 2

Found this question a bit late, but better than never - here's a solution in

Javascript (Node)

Highlights:

• Uses RGB color space
• Runs on my laptop in between 20-70 seconds (node pixels after npm install)
• 215 lines (including Javadoc-style function comments)
• Uses a binary search tree through sorted pixels
• Randomizes source pixel selection to ensure "even" distribution
• Currently weights pixels on RED component, so my results may be red-biased. For example, the ones from the "Scream" palette give the best results.

---

var startTime = new Date().getTime();

var fs = require("fs");
var pngjs = require("pngjs").PNG;

/**
 *
 */
var Pixels = function() {};

/**
 *
 */
Pixels.prototype = {
    source: null,
    confirm: null,
    target: null,
    result: {},
};

/**
 * Heavy lifting done here.
 */
Pixels.prototype.repalettize = function() {
    // Indices is count from 0 to LxW, used to reference pixels in the tgtPalette, which are 8? bits wide.
    var indices = [];
    for (var y = 0; y < P.target.height; y++) {
        for (var x = 0; x < P.target.width; x++) {
            indices.push((P.target.width * y + x) << 2);
        }
    }

    var len = indices.length;
    P.result.asBuffer = new Buffer(P.target.height * P.target.width * 4);
    P.result.asArray = [];

    var i, ii;

    while (len) {
        i = Math.floor(Math.random() * len);
        ii = indices[i];

        // Find RGB in source, no need for alpha channel.
        matchIndex = P.findMatch(
            zeropad(P.target.asBuffer[ii], 3) +
            zeropad(P.target.asBuffer[ii + 1], 3) +
            zeropad(P.target.asBuffer[ii + 2], 3)
        );

        matchRgb = P.source.asArray[matchIndex];

        P.result.asArray.push(matchRgb);

        P.result.asBuffer[ii] = matchRgb.substr(0, 3) * 1;
        P.result.asBuffer[ii + 1] = matchRgb.substr(3, 3) * 1;
        P.result.asBuffer[ii + 2] = matchRgb.substr(6, 3) * 1;
        P.result.asBuffer[ii + 3] = 255;

        indices.splice(i, 1);
        P.source.asArray.splice(matchIndex, 1);
        len = indices.length;
    }

    var resultImg = new pngjs({
        filterType: 4
    });

    resultImg.data = P.result.asBuffer;
    resultImg.width = P.target.width;
    resultImg.height = P.target.height;
    resultImg.pack().pipe(fs.createWriteStream('result.png'));

    var endTime = new Date().getTime();
    console.log((endTime - startTime) / 1000 + " seconds, confirming");

    P.doConfirm(P.confirm.asArray, P.result.asArray) ?
        console.log('OK - Source array and result array match.') :
        console.log('ERROR! Source array and result array do not match!');
};

/**
 * Slightly modified binary search tree.
 */
Pixels.prototype.findMatch = function(rgb0) {
    var start = 0;
    var end = P.source.asArray.length;
    var mid;

    while (start + 1 < end) {
        mid = Math.floor((end - start) / 2 + start);
        if (P.source.asArray[mid] < rgb0) {
            start = mid;
        }
        else {
            end = mid;
        }
    }

    return start;
};

/**
 *
 */
Pixels.prototype.doConfirm = function(arr1, arr2) {
    var len1 = arr1.length;
    var len2 = arr2.length;

    if (len1 !== len2) {
        return false;
    }

    arr1.sort();
    arr2.sort();

    for (var i = 0; i < len1; i++) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }

    return true;
};

/**
 * Reads an image from a path, generates required information, and passes information to callback.
 */
Pixels.prototype.read = function(path0, callback0) {
    var width = 0;
    var height = 0;
    var asBuffer = null;
    var asArray = null;

    fs.createReadStream(path0).pipe(new pngjs({ filterType: 4 }))
    .on('metadata', function(meta0) {
        width = meta0.width;
        height = meta0.height;
    })
    .on('parsed', function(buffer0) {
        var x, y, i;
        var arr = [];
        for (y = 0; y < height; y++) {
            for (x = 0; x < width; x++) {
                i = y * width + x << 2;

                arr.push(zeropad(buffer0[i], 3) + zeropad(buffer0[i + 1], 3) + zeropad(buffer0[i + 2], 3));
            }
        }

        callback0({
            width: width,
            height: height,
            asBuffer: buffer0,
            asArray: arr,
        });
    });
};

/**
 * sprintf implementation to ensure 9-digit pixels for sorting.
 */
var zeropad = function(str0, len0) {
    str0 = str0.toString();
    while (str0.length < len0) {
        str0 = "0" + str0;
    }
    return str0;
};

/**
 * Ansynchronous file reads will execute and call this function. After they're all finished, the processing can begin.
 */
var filesRead = 0;
var thenContinue = function(data0) {
    filesRead++;

    if (filesRead === 3) {
        P.source.asArray.sort();
        P.repalettize();
    }
}

/**
 * Information for the source image, where the pixels are taken from.
 */
var thenSaveSource = function(obj0) {
    P.source = obj0;
    thenContinue();
}

/**
 * A copy of the source data used after processing to ensure source pixels match result pixels.
 */
var thenSaveConfirm = function(obj0) {
    P.confirm = obj0;
    thenContinue();
}

/**
 * Information for the target images, which the pixels are matched to.
 */
var thenSaveTarget = function(obj0) {
    P.target = obj0;
    thenContinue();
}

//===== Entry point
var P = new Pixels();
P.read('scream.png', thenSaveSource);
P.read('scream.png', thenSaveConfirm);
P.read('starry.png', thenSaveTarget);

---

Click on any image to see it larger size. Source images are on the diagonal.

Answer 3

C#

This sorts the pixels for both images by luminosity and then grabs the x and y from the source and the color from the palette in order from darkest to brightest and adds it to a new list which is used to create the new image.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PictureConverter
{
   using System.Drawing;

   class Program
   {
      struct Pixel
      {
         public int x;
         public int y;
         public Color color;
         public Pixel(int x, int y, Color color)
         {
            this.x = x;
            this.y = y;
            this.color = color;
         }
      }

      static List<Pixel> sourcePixels = new List<Pixel>();
      static List<Pixel> palettePixels = new List<Pixel>();
      static List<Pixel> newPixels = new List<Pixel>();

      static Pixel BaselineColor = new Pixel(0, 0, Color.FromArgb(0, 0, 0, 0));

      static int width;
      static int height;
      static int currentPixel = 0;

      static void Main(string[] args)
      {
         string sourceDirectory = "pic" + args[0] + ".png";
         string paletteDirectory = "pic" + args[1] + ".png";

         using (Bitmap source = Bitmap.FromFile(sourceDirectory) as Bitmap)
         {
            width = source.Width;
            height = source.Height;
            for (int x = 0; x < source.Width; x++)
            {
               for (int y = 0; y < source.Height; y++)
               {
                  sourcePixels.Add(new Pixel(x, y, source.GetPixel(x, y)));
               }
            }

            using (Bitmap palette = Bitmap.FromFile(paletteDirectory) as Bitmap)
            {
               // ReSharper disable once PossibleNullReferenceException
               for (int x = 0; x < palette.Width; x++)
               {
                  for (int y = 0; y < palette.Height; y++)
                  {
                     palettePixels.Add(new Pixel(x, y, palette.GetPixel(x, y)));
                  }
               }
            }

            if (palettePixels.Count != sourcePixels.Count)
            {
               throw new Exception("OH NO!!!!!!!!");
            }

            sourcePixels.Sort((x, y) => GetProx(x, BaselineColor) - GetProx(y, BaselineColor));
            palettePixels.Sort((x, y) => GetProx(x, BaselineColor) - GetProx(y, BaselineColor));

            foreach (Pixel p in sourcePixels)
            {
               Pixel newPixel = GetClosestColor(p);
               newPixels.Add(newPixel);
               //Console.WriteLine(p.x + " " + p.y);
            }

            foreach (var p in newPixels)
            {
               source.SetPixel(p.x, p.y, p.color);
            }
            source.Save("Out" + args[0] + "to" + args[1] + ".png");
         }
      }

      private static Pixel GetClosestColor(Pixel p)
      {
         Pixel ret = palettePixels[currentPixel++];
         return new Pixel(p.x, p.y, ret.color);
      }

      private static int GetProx(Pixel a, Pixel p)
      {
         int red = (a.color.R - p.color.R) * (a.color.R - p.color.R);
         int green = (a.color.G - p.color.G) * (a.color.G - p.color.G);
         int blue = (a.color.B - p.color.B) * (a.color.B - p.color.B);
         return red + blue + green;
      }
   }
}

With the palette list sorted from brightest to darkest instead:

Change this:

palettePixels.Sort((x, y) => GetProx(x, BaselineColor) - GetProx(y, BaselineColor));

to this:

palettePixels.Sort((x, y) => GetProx(y, BaselineColor) - GetProx(x, BaselineColor));

Answer 4

This is my first post here, so here we go...

Python 3.4.3

from PIL import Image
import time
from random import randint
from random import shuffle
t0=time.time()
# p1 with palette of p2
im=Image.open('0.png')
a=im.getdata()
x1=im.size[0]
y1=im.size[1]
im.close()
im=Image.open('4.png')
b=list(im.getdata())
im.close()
red=[]
green=[]
blue=[]
c=[]
t=[]
#b.sort()
shuffle(b)
rr=1
gr=2
br=1
ra=0
ga=0
ba=0
rb=0
gb=0
bb=0
rg=0
gg=0
bg=0
for x in range(0,len(b)):
    t=[b[x][0],b[x][1],b[x][2]]
    c.append(t)
    rb+=b[x][0]
    gb+=b[x][1]
    bb+=b[x][2]
rb/=len(b)
gb/=len(b)
bb/=len(b)
g=[]
for x in range(0,len(b)):
    t=[a[x][0],a[x][1],a[x][2]]
    g.append(t)
    rg+=a[x][0]
    gg+=a[x][1]
    bg+=a[x][2]
rg/=len(b)
gg/=len(b)
bg/=len(b)
temp=[]
e=0
ro=rb-rg
go=gb-gg
bo=bb-bg
for x in range(0,len(b)):
    g[x][0]+=ro
    g[x][1]+=go
    g[x][2]+=bo
for One_Republic in range(0,10):
    #'''
    e=0
    f=0
    te=0
    tf=0
    rr=[]
    ts=[]
    for x in range(0,10**5):
        e=randint(0,len(b)-1)
        f=randint(0,len(b)-1)
        te=(c[e][0]-g[e][0])**2+(c[e][1]-g[e][1])**2+(c[e][2]-g[e][2])**2
        tf=(c[f][0]-g[e][0])**2+(c[f][1]-g[e][1])**2+(c[f][2]-g[e][2])**2
        ts=[te,tf]
        if(tf==min(ts)):
            rr=list(c[f])
            c[f]=list(c[e])
            c[e]=list(rr)
    #'''
    e=0
    f=0
    te=0
    tf=0
    rr=[]
    ts=[]
    for Adele in range(0,3):
        for x in range(0,len(b)-2):
            e=x
            f=x+1
            te=(c[e][0]-g[e][0])**2+(c[e][1]-g[e][1])**2+(c[e][2]-g[e][2])**2
            tf=(c[f][0]-g[e][0])**2+(c[f][1]-g[e][1])**2+(c[f][2]-g[e][2])**2
            ts=[te,tf]
            if(tf==min(ts)):
                rr=list(c[f])
                c[f]=list(c[e])
                c[e]=list(rr)
    #'''
b=[]
for x in range(0,len(c)):
    t=(c[x][0],c[x][1],c[x][2])
    b.append(t)
im=Image.new('RGB',(x1,y1),'black')
im.putdata(b)
im.save('pic.png')
print(time.time()-t0)

The code tries to shuffle pixels randomly, then locally, to match another input painting. What it does first is tint the painting that the code is trying to mimic, to make a higher-def picture. The code does have a timer. It now auto-accepts the dimensions of the output file. In my folder,

0 is Starry Night

1 is The Scream

2 is Mona Lisa

3 is American Gothic

4 is Spheres

5 is The River

So the results:

Obligatory Mona Lisas

My other experiments

Answer 5

C#

Sorts pixels by Gray Scale and then paints pixels.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;

namespace ImageSwap
{
    public class Pixel : IEquatable<Pixel>, IComparable<Pixel>
    {
        public int x, y;
        public Color rgb;
        public int grayScale;
        public Pixel() { }

        public int CompareTo(Pixel other)
        {
            if (this.grayScale < other.grayScale)
                return 1;
            else if (this.grayScale == other.grayScale)
                return 0;
            else
                return -1;
        }

        public bool Equals(Pixel other)
        {
            return this.grayScale == other.grayScale;
        }

        public override string ToString()
        {
            string s = string.Format("x:{0},y:{1}:gray:{2}", this.x, this.y, this.grayScale);
            return s;
        }
    }

    class PalleteCopy
    {
        private Image src, palette;

        PalleteCopy(Image s, Image p)
        {
            this.src = s;
            this.palette = p;
        }

        public List<Pixel> Analyse(Image img)
        {
            List<Pixel> pxList = new List<Pixel>();
            Bitmap b = (Bitmap)img;
            int w = b.Width;
            int h = b.Height;
            float gray = 0;
            for (int i = 0; i < w; i++)
            {               
                for (int j = 0; j < h; j++)
                {
                    Pixel px = new Pixel();
                    px.x = i;
                    px.y = j;
                    px.rgb = b.GetPixel(i, j);
                    gray = (px.rgb.B + px.rgb.G + px.rgb.R) / 3;
                    px.grayScale = (int)(gray);
                    pxList.Add(px);
                }

            }

            return pxList;
        }

        public void ToFile(List<Pixel> px)
        {
            StreamWriter w = null;
            try
            {
                w = new StreamWriter("C:/pics/pics.log", true);
                foreach (Pixel p in px)
                {
                    w.WriteLine(p.ToString());
                }
            }
            catch (Exception) { }
            finally { if (w != null) w.Close(); }
        }

        public List<Pixel> SortByGray(List<Pixel> pxList)
        {
            List<Pixel> pL = new List<Pixel>();
            foreach(Pixel p in pxList)
            {
                pL.Add(p);
            }
            pL.Sort();
            return pL;
        }

        public Image CreateCopy()
        {
            List<Pixel> pxSrc = this.Analyse(this.src);
            //ToFile(pxSrc);
            //this.Print(this.FromPixels(pxSrc), "C:/pics/p1.png");

            List<Pixel> pxPal = this.Analyse(this.palette);
            //ToFile(pxPal);
            //this.Print(this.FromPixels(pxPal), "C:/pics/p2.png");

            List<Pixel> sortSrc = this.SortByGray(pxSrc);
            //ToFile(sortSrc);
            //this.Print(this.FromPixels(sortSrc), "C:/pics/p3.png");

            List<Pixel> sortPal = this.SortByGray(pxPal);
            //ToFile(sortPal);
            //this.Print(this.FromPixels(sortPal), "C:/pics/p4.png");

            int w = this.src.Width;
            int h = this.src.Height;
            Bitmap copy = new Bitmap(w, h);
            int n = sortPal.Count;
            for(int i=0; i<n; i++)
            {
                copy.SetPixel(sortSrc[i].x, sortSrc[i].y, sortPal[i].rgb);
            }
            return copy;
        }

        public Image FromPixels(List<Pixel> px)
        {
            Bitmap copy = new Bitmap(this.src.Width, this.src.Height);
            int n = px.Count;
            for (int i = 0; i < n; i++)
            {
                copy.SetPixel(px[i].x, px[i].y, px[i].rgb);
            }
            return copy;
        }

        public void Print(Image img, string filename)
        {
            Bitmap b = (Bitmap)img;
            try
            {
                b.Save(filename);
            }
            catch (Exception) { }
        }

        static void Main(string[] args)
        {
            string src = @"C:\pics\source.png";
            string pal = @"C:\pics\palette.png";
            try
            {
                Image s = Image.FromFile(src);
                Image p = Image.FromFile(pal);
                PalleteCopy pc = new PalleteCopy(s, p);
                Image c = pc.CreateCopy();
                pc.Print(c, @"C:\pics\copy.png");

                Console.WriteLine("Success");
            }
            catch (Exception ex) 
            {
                Console.WriteLine("Failed: " + ex.Message);
            }
        }
    }
}

Result image:

Answer 6

Squeak Smalltalk

This is pretty crude, it just scans through the pixels from the top and lets them get the best matches using the built-in Color >> diff:, which sums the differences in RGB and normalizes to 1.

Usage:

1. Create a PixelArranger object.
2. #loadSrcImageFile: and #loadDestImageFile:.
3. #rearrangeLinear. Transcript shows status (number of pixels).
4. Convert arrangedForm to a Morph with #asMorph and then #openInWorld.

Mona Lisa in the palette of ray-traced balls

Here is the fileout:

'From Squeak4.4 of 11 September 2013 [latest update: #12337] on 13 July 2014 at 1:32:08 pm'!
Object subclass: #PixelArranger
    instanceVariableNames: 'srcForm srcImageFile palette destForm destImageFile arrangedForm'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'PixelArranger'!

!PixelArranger methodsFor: 'image loading' stamp: 'pnr 7/12/2014 18:55'!
loadDest: aForm
    destForm := aForm.

    arrangedForm := Form extent: (aForm extent) depth: (aForm depth).
! !

!PixelArranger methodsFor: 'image loading' stamp: 'pnr 7/12/2014 18:52'!
loadDestImageFile: aFilename
    self loadDest:(Form fromFileNamed: aFilename).
    destImageFile := aFilename.! !

!PixelArranger methodsFor: 'image loading' stamp: 'pnr 7/12/2014 23:49'!
loadSrc: aForm
    srcForm := aForm.

    self buildPalette.! !

!PixelArranger methodsFor: 'image loading' stamp: 'pnr 7/12/2014 18:47'!
loadSrcImageFile: aFilename
    self loadSrc:(Form fromFileNamed: aFilename).
    srcImageFile := aFilename.! !


!PixelArranger methodsFor: 'processing' stamp: 'pnr 7/13/2014 11:41'!
buildPalette
    "We scrape one pixel at a time off the source image and deposit it on to the palette."
    palette removeAll. "clean it first!!"

    srcForm bits do: [:each |
        palette add: (Color colorFromPixelValue: each depth: 32).
        ]! !

!PixelArranger methodsFor: 'processing' stamp: 'pnr 7/13/2014 11:17'!
pickClosestColor: aColor from: aColorCollection
    "Answer the closest color from the available source pixels"
    |  closest minDiff |
    minDiff := 1.0.
    closest := Color black.

    aColorCollection asSet do: [:each | | diff |
        diff := aColor diff: each.
        (diff = 0.0) ifTrue: [ ^each ].
        (diff < minDiff) ifTrue: [ 
            minDiff := diff.
            closest := each.
            ]
        ].

    ^closest.! !

!PixelArranger methodsFor: 'processing' stamp: 'pnr 7/12/2014 23:49'!
rearrangeLinear
    | count arrangedBits |
    count := 0.

    self buildPalette.

    arrangedBits := destForm bits collect:[:each | | closest target |
        target := Color colorFromPixelValue: each depth: 32.
        closest := self pickClosestColor: target from: palette.
        palette remove: closest ifAbsent:[].    
        (count \\ 100 = 0) ifTrue: [Transcript show: 'rearrangeLinear: ', count ; cr].
        count := count + 1 .
        closest pixelValue32.
        ].

    arrangedForm bits: arrangedBits.
! !


!PixelArranger methodsFor: 'initialize-release' stamp: 'pnr 7/12/2014 23:47'!
initialize
    super initialize.
    palette := Bag new.! !