Pixel Palettes

An interesting challenge from Codegolf Stack Exchange


Problem Statement

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.

I developed a solution that takes a random pixel and uses a binary search to find a match in the target palette, weighted for the red component. Here are the results for that approach.

Results

Images are links, diagonals are originals.

Gothic original Gothic -> Mona Lisa Gothic -> Scream Gothic -> Spheres Gothic -> Starry Night Gothic -> Stream Mona -> Gothic Mona Lisa original Mona -> Scream Mona -> Spheres Mona -> Starry Night Mona -> Stream Scream -> Gothic Scream -> Mona Lisa Scream original Scream -> Spheres Scream -> Starry Night Scream -> Stream Spheres -> Gothic Spheres -> Mona Lisa Spheres -> Scream Spheres original Spheres -> Starry Night Spheres -> Stream Starry -> Gothic Starry -> Mona Lisa Starry -> Scream Starry -> Spheres Starry Night original Starry -> Stream Stream -> Gothic Stream -> Mona Lisa Stream -> Scream Stream -> Spheres Stream -> Starry Night Stream original

Code

Source

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);