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.

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