# MS Paint is underrated

MS Paint was always a great time waster, but it was shunned by most graphic designers. Perhaps people lost interest because of the jarring color palette, or because of limited undo levels. Regardless, it's still possible to generate beautiful images with just the standard brush and default color palette.

## Challenge

Using only the default brush (a 4x4 square with no corners) and the default color palette (the 28 colors below), attempt to replicate a source image using a technique based on stochastic hill climbing.

## Algorithm

Every answer must follow the same basic algorithm (stochastic hillclimb). Details can be tweaked within each step. A movement is considered to be a stroke of the brush (ie. clicking in paint).

1. Guess next movement(s). Make a guess (of coordinates and colors) for the next movement(s) however you'd like. However the guess must not reference the source image.
2. Apply the guess. Apply the brush to the painting to make the movement(s).
3. Measure the benefit of movement(s). By referencing the source image, determine whether the movement(s) benefited the painting (ie. the painting more closely resembles the source image). If it is beneficial, keep the movement(s), otherwise discard the movement(s).
4. Repeat until convergence. Go to Step 1 and try the next guess until the algorithm has converged sufficiently. The painting should heavily resemble the source image at this point.

If your program does not match these four steps, it is probably not a stochastic hillclimb. I have tagged this as a popularity contest because the goal is to produce interesting painting algorithms based on the limited color palette and brush.

## Contraints

• The algorithm should be stochastic in some way.
• The next guess should not be influenced by the source image. You are guessing each new movement, and then checking to see if it helped or not. For example, you are not allowed to determine where to place the brush based on the source image colors (that is similar to dithering the source image, which is not the goal).

• You are allowed to influence the placement by tweaking the steps of the algorithm however you'd like. For example, you could start your guesses at the edges and move inwards, drag the brush to create lines for each guess, or decide to paint dark colors first. You are allowed to reference previous iteration images (but not the source image) in order to calculate the next desired movement. These can be restrictive as you'd like (ie. only make guesses within the top-left quadrant for the current iteration).

• The measure of "difference" between the source image and the current iteration can be measured however you'd like, as long as it does not calculate other potential movements to determine whether this movement is considered to be the "best". It shouldn't know whether the current movement is the "best", only whether it fits within the tolerance of the acceptance criteria. For example, it can be as simple as abs(src.R - current.R) + abs(src.G - current.G) + abs(src.B - current.B) for each affected pixel, or any of the well-known color difference techniques.

## Palette

You can download the palette as a 28x1 image or create it directly in the code.

## Brush

The brush is a 4x4 square without corners. This is a scaled version of it:

(Your code must use the 4x4 version)

## Example

Input:

Output:

You can see how the basic algorithm progresses in a short video I made (each frame is 500 iterations): The Starry Night. The initial stages are interesting to watch:

• @vihan1086: The source image does not have transparency. The current image can depend on the previous iteration (like my example, in which new points are added on top of the previous) if that's what you mean. Commented Jul 12, 2015 at 23:41
• I don't see what the stochastic hill climbing adds at all... considering that you can make guesses however you want and discard them if they're not good, that's effectively the same as just going through a bunch of guesses while checking and picking the best one. Commented Jul 13, 2015 at 9:18
• @Sp3000: The point is that you don't know the "best" movement until it a potential movement has been made, at which point you can choose to accept it if it fits inside your own acceptance criteria (ie. it's "close enough"). The acceptance criteria shouldn't have knowledge of all possible moves (I may need to clarify this further). Essentially you shouldn't be able to determine the "best" movement ahead of time, instead you should be incrementally improving the image. Commented Jul 13, 2015 at 13:41
• With this brush shape, is it impossible to paint the corner pixels (from your example I get this impression), or can the brush be placed partially outside the image boundaries? Commented Jul 13, 2015 at 14:52
• Here's the palette in a usable format: 000000 808080 800000 808000 008000 008080 000080 800080 808040 004040 0080FF 004080 8000FF 804000 FFFFFF C0C0C0 FF0000 FFFF00 00FF00 00FFFF 0000FF FF00FF FFFF80 00FF80 80FFFF 8080FF FF0080 FF8040 Commented Mar 10, 2018 at 17:13

# JavaScript

This solution uses the HTML5 canvas element to extract the image data, but without the need to use HTML, that means it can be run in your console. It access the color palette image as an array; I stored all the colors from the palette image in an array). It outputs to the console (after it finishes) and also stores the result in a variable.

The most updated version of the code is in the fiddle. The fiddle also uses a better algorithm to reduce noise in the pictures. The improvement in the algorithm is mostly fixing a function (max to min) which caused the inverse color to be chosen.

Code in the shape of the MS Paint Icon! (formatted code in fiddle or Stack Snippet)

eval(                                                   function
Paint(t){fun
ction n(t){va
r n=t.toString(
16);return 1==n.
length?"0"+n:n}fu
nction e(t){return
"#"+n(t[0])+n(t[1]
)+n(t[2])}var a=ne
w Image,i=document.
createElement("canv
as"),h=null,o=docum
ent.createElement(
"canvas"),r=          o.getContext("2d
")     ,l=[],u=this,c      =[[0,0,0],[255
,2       55,255],[ 192,192,   192],[128,12
8     ,128],[126,3,8],[252,13,27] ,[255,25
3,    56],[128,127,23],[15,127,18],[ 41,253
,    46],[45,255,254],[17,128,127],[2 ,12,1
2    6],[ 11,36,2 51],[252,40,252],[12 7,15,1
2    6],[  128,127 ,68],[255,253,136],[4 2,253,
1   33],   [4,64,64],[23 ,131,251],[133,255,254],
[    129   ,132,252],[6,6 6,126],[127,37,2 51],[127,
6   4,1    3],[253,128,73],[252,22,129]];a.crossOrigin
=   "",   a.src=t,this.done=this.done||function(){},a.o
n   load=function(){function t(t){var n=0,e=0,a=0;return
t  .forEach(function(t){n+=t[0],e+=t[1],a+=t[2]}),[n/t.leng
t  h,e /t.length,a/t.length]}function n(t){for(var n=[],e=0;e
<  t.l  ength;e+=1)n.push(t[e]);return n}function g(t,n){retur
n  (Ma  th.abs(t[0]-n[0])/255+Math.abs(t[1]-n[1])/255+Math.abs(t
[  2]- n[2])/255)/3}function f(t,n){for(var e=Math.floor(Math.ran
do m()*n.length),a=n[e],i=(g(t,a),1-.8),h=56,o=[];o.length<=h&
&g (t,a)>i;)if(o.push(a),a=n[Math.floor(Math.random()*n.length)]
,  o.length==h){var r=o.map(function(n){return g(t,n)});a=o[r.indexO
f(Math.max.apply(Math,r))],o.push(a)}return a}function s(t,n){for(
v  ar e=[];t.length>0;)e.push(t.splice(0,n).slice(0,-1));return e}i.w
i  dth=a.width,i.height=2*a.height,h=i.getContext("2d"),h.drawImage(a,0
,0,a.width,a.height);for(var d=(function(t){reduce=t.map(function(t){re
turn(t[ 0]+t[1]+t[2])/3})}(c),0),m=0,v=i.width*i.height/4,p=0;v>p;p+=1)d
>2*Mat h.ceil(a.width/2)&&(d=0,m+=1),l.push(f(t(s(n(h.getImageData(2*d,2
*m,4,4).data),4)),c)),d+=1;o.width=i.width,o.height=i.height;for(var d=0
,m=0,v=i.width*i.height/4,p=0;v>p;p+=1)d>2*Math.ceil(a.width/2)&&(d=0,m+=
1),console.log("Filling point ("+d+", "+m+") : "+e(l[p])),r.fillStyle=e(l
[p]),r.fillRect(2*d+1,2*m,2,1)  ,r.fillRect(2*d,2*m+1,4,2),r.fillRect(2*d
+1,2*m+3,2,1),d+=1;u.result=o      .toDataURL("image/png"),u.resultCanvas
=o,u.imageCanvas=i,u.image=a       ,u.done(),console.log(u.result)},a.one
rror=function(t){console.log       ("The image failed to load. "+t)}}/*..
............................       ......................................
. ..........................       .....................................
............................      ......................................
.............................    .......................................
.......................................................................
.......................................................................
..................  ..................................................
................     .................................................
..............       ................................................
.............       ................................................
...........        .................................................
.........         ................................................
.......          ................................................
....           ................................................
................................................
...............................................
...............................................
..............................................
.............................................
............................................
..........................................
.......................................
.....................................
.................................
.............................
......................
.....
.....
.....
....
*/
.replace(/\n/g,''))


Usage:

Paint('DATA URI');


# Fiddle.

The fiddle uses crossorigin.me so you don't need to worry about cross-origin-resource-sharing.

I've also updated the fiddle so you can adjust some values to produce the best-looking painting. Some pictures' colors might be off, to avoid this, adjust the accept_rate to adjust the algorithm. A lower number means better gradients, a higher number will result in sharper colors.

Here's the fiddle as a Stack-Snippet (NOT updated, in case the fiddle doesn't work):

/* Options */

var accept_rate = 82,  // 0 (low) - 100 (high)
attempts    = 16, // Attemps before giving up
edge_multi  = 2;   // Contrast, 2-4

function Paint(image_url) {
var image = new Image(), canvas = document.createElement('canvas'), context = null, result = document.createElement('canvas'), resultContext = result.getContext('2d'), final_colors = [], self = this, color_choices = [
[0,0,0],
[255,255,255],
[192,192,192],
[128,128,128],
[126,3,8],
[252,13,27],
[255,253,56],
[128,127,23],
[15,127,18],
[41,253,46],
[45,255,254],
[17,128,127],
[2,12,126],
[11,36,251],
[252,40,252],
[127,15,126],
[128,127,68],
[255,253,136],
[42,253,133],
[4,64,64],
[23,131,251],
[133,255,254],
[129,132,252],
[6,66,126],
[127,37,251],
[127,64,13],
[253,128,73],
[252,22,129]
];
image.crossOrigin = "";
image.src = image_url;

this.done = this.done || function () {};

function hex(c) {
var res = c.toString(16);
return res.length == 1 ? "0" + res : res;
}

function colorHex(r) {
return '#' + hex(r[0]) + hex(r[1]) + hex(r[2]);
}

image.onload = function () {
canvas.width = image.width; canvas.height = image.height * 2;
context = canvas.getContext('2d');
context.drawImage(image, 0, 0, image.width, image.height);

function averageColors(colors_ar) {
var av_r = 0,
av_g = 0,
av_b = 0;

colors_ar.forEach(function (color) {
av_r += color[0];
av_g += color[1];
av_b += color[2];
});

return [av_r / colors_ar.length,
av_g / colors_ar.length,
av_b / colors_ar.length];
}

function arrayFrom(ar) {
var newar = [];
for (var i = 0; i < ar.length; i += 1) {
newar.push(ar[i]);
}
return newar;
}

function colorDif(c1,c2) {
// Get's distance between two colors 0.0 - 1.0
return (Math.abs(c1[0] - c2[0]) / 255 +
Math.abs(c1[1] - c2[1]) / 255 +
Math.abs(c1[2] - c2[2]) / 255) / 3;
}

var furthest = (function (cc) {
// Determines furthest color

// Reduces RGB into a "single value"
reduce = cc.map(function(color) {
return ( color[0] + color [1] + color [2] ) / 3;
});

}(color_choices));

function intDif(i1,i2,t) {
return Math.abs(i1 - i2) / t
}

function arrayIs(ar, int,d) {
return intDif(ar[0],int,255) <= d &&
intDif(ar[1],int,255) <= d &&
intDif(ar[2],int,255) <= d
}

function colorLoop(c1,c2) {
var edgeCap =  edge_multi * ((accept_rate / 100) / 50), values = c2.map(function (i) {
return colorDif(c1,i);
});

return arrayIs(c1,255,edgeCap)?[255,255,255]:
arrayIs(c1,0,edgeCap)  ?[0,0,0]:
c2[values.indexOf(Math.min.apply(Math, values))];
}

function colorFilter(c1, c2) {
// Does the color stuff
var rand  = Math.floor( Math.random() * c2.length ), // Random number
color = c2[rand], // Random color
randdif = colorDif(c1, color),
threshhold = 1 - accept_rate / 100, // If the color passes a threshhold
maxTries   = attempts, // To avoid infinite looping, 56 is the maximum tries to reach the threshold
tries      = [];

// Repeat until max iterations have been reached or color is close enough

while ( tries.length <= maxTries && colorDif( c1, color ) > threshhold ) {
tries.push(color);
color = c2[Math.floor(Math.random() * c2.length)]; // Tries again

if (tries.length == maxTries) {
// Used to hold color and location
var refLayer = tries.map(function(guess) {
return colorDif(c1, guess);
});

color = tries[refLayer.indexOf(Math.min.apply(Math, refLayer))];
tries.push(color);
}

}

var edgeCap =  edge_multi * ((accept_rate / 100) / 50), loop = colorLoop(c1, c2);

return arrayIs(c1,255,edgeCap)?[255,255,255]:
arrayIs(c1,0,edgeCap)  ?[0,0,0]:
colorDif(c1,color)<accept_rate?color:
loop;
}

function chunk(ar, len) {
var arrays = [];

while (ar.length > 0)
arrays.push(ar.splice(0, len).slice(0, -1));

return arrays;
}

var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;

for (var i = 0; i < total; i += 1) {
if (x > (Math.ceil(image.width / 2) * 2)) {
x = 0;
y += 1;
}

final_colors.push( colorFilter( averageColors( chunk( arrayFrom(context.getImageData(x * 2, y * 2, 4, 4).data), 4 ) ), color_choices) );

x += 1;
}

// Paint Image
result.width = canvas.width;
result.height = canvas.height;
var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
for (var i = 0; i < total; i += 1) {
if (x > (Math.ceil(image.width / 2) * 2)) {
x = 0;
y += 1;
}

console.log("Filling point (" + x + ", " + y + ") : " + colorHex(final_colors[i]));

resultContext.fillStyle = colorHex(final_colors[i]);
resultContext.fillRect(x*2 + 1, y * 2, 2 , 1); // Top
resultContext.fillRect(x * 2, y * 2 + 1, 4, 2); // Middle
resultContext.fillRect(x * 2 + 1, y * 2 + 3, 2, 1); // Bottom

x += 1;
}

self.result = result.toDataURL("image/png");
self.resultCanvas = result;
self.imageCanvas = canvas;
self.image = image;
self.done();

console.log(self.result);

};

image.onerror = function(error) {
console.log("The image failed to load. " + error);
}

}

// Demo

document.getElementById('go').onclick = function () {
var url = document.getElementById('image').value;
if (!url.indexOf('data:') == 0) {
url = 'http://crossorigin.me/' + url;
}
var example = new Paint(url);

example.done = function () {
document.getElementById('result').src = example.result;
document.getElementById('result').width = example.resultCanvas.width;
document.getElementById('result').height = example.resultCanvas.height;
window.paint = example;
};
};
<!--This might take a while-->
Enter the image data URI or a URL, I've used crossorigin.me so it can  perform CORS requests to the image. If you're inputting a URL, be sure to include the http(s)
<input id="image" placeholder="Image URI or URL"><button id="go">Go</button>
<hr/>
You can get the image URI from a website like <a href="http://jpillora.com/base64-encoder/">this one</a>
<hr/>

Result:
<img id="result">
<span id="error"></span><hr/>
Check your console for any errors. After a second, you should see the colors that are being generated / printed getting outputted to the console.

To commemorate New Horizon's flyby of Pluto, I've inputted an image of Pluto:

For the following I've set it to make them resemble the original as close as possible:

I ran this with OS X Yosemite's default wallpaper. After leaving it run for a bit, the results are absolutely stunning. The original file was huge (26 MB) so I resized and compressed it:

The starry night (I've used a higher resolution image for better results)

A picture I found on google:

# JavaScript + HTML

Random Point

### Random Aligned:

Subdivides the canvas into 4x4 squares, and chooses a point randomly inside one of the squares. Offsets will move the grid, so you can fill in the little gaps.

### Loop:

Creates a grid and Loops through all the points. Offsets moves the grid. Spacing determine the size of each cell. (They will start to overlap)

### Color difference:

• RGB
• HSL
• HSV

var draw = document.getElementById("canvas").getContext("2d");
var data = document.getElementById("data").getContext("2d");
colors = [
[0, 0, 0],
[255, 255, 255],
[192, 192, 192],
[128, 128, 128],
[126, 3, 8],
[252, 13, 27],
[255, 253, 56],
[128, 127, 23],
[15, 127, 18],
[41, 253, 46],
[45, 255, 254],
[17, 128, 127],
[2, 12, 126],
[11, 36, 251],
[252, 40, 252],
[127, 15, 126],
[128, 127, 68],
[255, 253, 136],
[42, 253, 133],
[4, 64, 64],
[23, 131, 251],
[133, 255, 254],
[129, 132, 252],
[6, 66, 126],
[127, 37, 251],
[127, 64, 13],
[253, 128, 73],
[252, 22, 129]
];
iteration = 0;
fails = 0;
success = 0;
x = 0;
y = 0;
//Init when the Go! button is pressed
document.getElementById("file").onchange = function (event) {
document.getElementById("img").src = URL.createObjectURL(event.target.files[0]);
filename = document.getElementById("file").value;
/*if (getCookie("orginal") == filename) {
}*/
};

var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i];
while (c.charAt(0) == ' ') c = c.substring(1);
if (c.indexOf(name) == 0) return c.substring(name.length, c.length);
}
return "";
}*/

//Run when the image has been loaded into memory
document.getElementById("img").onload = function () {
document.getElementById("file").disable = "true";
document.getElementById("canvas").hidden = "";
document.getElementById("canvas").height = document.getElementById("img").height;
document.getElementById("data").height = document.getElementById("img").height;
document.getElementById("canvas").width = document.getElementById("img").width;
document.getElementById("data").width = document.getElementById("img").width;

var imgData = draw.createImageData(document.getElementById("img").width, document.getElementById("img").height);
for (var i = 0; i < imgData.data.length; i += 4) {
imgData.data[i + 0] = 0;
imgData.data[i + 1] = 0;
imgData.data[i + 2] = 0;
imgData.data[i + 3] = 255;
}
draw.putImageData(imgData, 0, 0);
data.putImageData(imgData, 0, 0);
if (reload == true) {
}
data.drawImage(document.getElementById("img"), 0, 0);
setInterval(function () {
for (var u = 0; u < document.getElementById("selectColor").value; u++) {
doThing();
}
}, 0);
};

//The core function. Every time this function is called, is checks/adds a dot.
function doThing() {
getCoords();
paintBucket();
console.count("Iteration");
if (compare(x, y)) {
draw.putImageData(imgData, x, y);
}
}

function getCoords() {
switch (document.getElementById("selectCord").value) {
case "1":
x = Math.floor(Math.random() * (document.getElementById("img").width + 4));
y = Math.floor(Math.random() * (document.getElementById("img").height + 4));
break;
case "2":
x = Math.floor(Math.random() * ((document.getElementById("img").width + 4) / 4)) * 4;
console.log(x);
x += parseInt(document.getElementById("allignX").value);
console.log(x);
y = Math.floor(Math.random() * ((document.getElementById("img").height + 4) / 4)) * 4;
y += parseInt(document.getElementById("allignY").value);
break;
case "3":
x += parseInt(document.getElementById("loopX").value);
if (x > document.getElementById("img").width + 5) {
x = parseInt(document.getElementById("allignX").value);
y += parseInt(document.getElementById("loopY").value);
}
if (y > document.getElementById("img").height + 5) {
y = parseInt(document.getElementById("allignY").value);
}
}
}

function compare(arg1, arg2) {
var arg3 = arg1 + 4;
var arg4 = arg2 + 4;
imgData2 = data.getImageData(arg1, arg2, 4, 4);
imgData3 = draw.getImageData(arg1, arg2, 4, 4);
N = 0;
O = 0;
i = 4;
i += 4;
for (l = 0; l < 8; l++) {
}
i += 4;
i += 4;
//console.log("New Score: " + N + " Old Score: " + O);
iteration++;
/*if(iteration>=1000){

}*/
if (N < O) {
return true;
} else {
return false;
}
}

if (document.getElementById("colorDif").value == "HSL") {
HSLCompare();
i += 4;
return;
}
if (document.getElementById("colorDif").value == "HSV") {
HSVCompare();
i += 4;
return;
}
N += Math.abs(imgData.data[i] - imgData2.data[i]);
N += Math.abs(imgData.data[i + 1] - imgData2.data[i + 1]);
N += Math.abs(imgData.data[i + 2] - imgData2.data[i + 2]);
O += Math.abs(imgData3.data[i] - imgData2.data[i]);
O += Math.abs(imgData3.data[i + 1] - imgData2.data[i + 1]);
O += Math.abs(imgData3.data[i + 2] - imgData2.data[i + 2]);
i += 4;
}

function HSVCompare() {
var NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[0];
var PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[0];
var OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[0];

var NScore = [Math.abs(NewHue - PicHue), ((NewHue < PicHue) ? NewHue + (1 - PicHue) : PicHue + (1 - NewHue))];
var OScore = [Math.abs(OldHue - PicHue), ((OldHue < PicHue) ? OldHue + (1 - PicHue) : PicHue + (1 - OldHue))];

NScore = Math.min(NScore[0], NScore[1]);
OScore = Math.min(OScore[0], OScore[1]);

NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[1];
PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[1];
OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[1];

NScore += Math.abs(NewHue-PicHue);
OScore += Math.abs(OldHue-PicHue);

NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[2];
PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[2];
OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[2];

N += Math.abs(NewHue-PicHue) + NScore;
O += Math.abs(OldHue-PicHue) + OScore;
}

function rgbToHsv(r, g, b){
r = r/255, g = g/255, b = b/255;
var max = Math.max(r, g, b), min = Math.min(r, g, b);
var h, s, v = max;

var d = max - min;
s = max == 0 ? 0 : d / max;

if(max == min){
h = 0; // achromatic
}else{
switch(max){
case r: h = (g - b) / d + (g < b ? 6 : 0); break;
case g: h = (b - r) / d + 2; break;
case b: h = (r - g) / d + 4; break;
}
h /= 6;
}

return [h, s, v];
}

function HSLCompare() {
var result = 0;
rgb = false;

var NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[0];
var PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[0];
var OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[0];
if (rgb == true) {
N += Math.abs(imgData.data[i] - imgData2.data[i]);
N += Math.abs(imgData.data[i + 1] - imgData2.data[i + 1]);
N += Math.abs(imgData.data[i + 2] - imgData2.data[i + 2]);
O += Math.abs(imgData3.data[i] - imgData2.data[i]);
O += Math.abs(imgData3.data[i + 1] - imgData2.data[i + 1]);
O += Math.abs(imgData3.data[i + 2] - imgData2.data[i + 2]);
return;
}
var NScore = [Math.abs(NewHue - PicHue), ((NewHue < PicHue) ? NewHue + (1 - PicHue) : PicHue + (1 - NewHue))];
var OScore = [Math.abs(OldHue - PicHue), ((OldHue < PicHue) ? OldHue + (1 - PicHue) : PicHue + (1 - OldHue))];

NScore = Math.min(NScore[0], NScore[1]);
OScore = Math.min(OScore[0], OScore[1]);

NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[1];
PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[1];
OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[1];

NScore += Math.abs(NewHue-PicHue);
OScore += Math.abs(OldHue-PicHue);

NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[2];
PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[2];
OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[2];

N += Math.abs(NewHue-PicHue) + NScore;
O += Math.abs(OldHue-PicHue) + OScore;
}

function rgbToHue(r, g, b) {
if (Math.max(r, g, b) - Math.min(r, g, b) < 50) {
rgb = true
}
r /= 255, g /= 255, b /= 255;
var max = Math.max(r, g, b),
min = Math.min(r, g, b);
var h, s, l = (max + min) / 2;

if (max == min) {
h = s = 0; // achromatic
} else {
var d = max - min;
s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
switch (max) {
case r:
h = (g - b) / d + (g < b ? 6 : 0);
break;
case g:
h = (b - r) / d + 2;
break;
case b:
h = (r - g) / d + 4;
break;
}
h /= 6;
}
return [h,s,l];
}

//Create a 4x4 ImageData object, random color selected from the colors var, transparent corners.
function paintBucket() {
color = Math.floor(Math.random() * 28);
imgData = draw.createImageData(4, 4);
imgData2 = draw.getImageData(x, y, 4, 4);
i = 0;
createCorn();
createColor();
createColor();
createCorn();
for (l = 0; l < 8; l++) {
createColor();
}
createCorn();
createColor();
createColor();
createCorn();
}

function createCorn() {
imgData.data[i] = imgData2.data[i];
imgData.data[i + 1] = imgData2.data[i + 1];
imgData.data[i + 2] = imgData2.data[i + 2];
imgData.data[i + 3] = 255;
i += 4;
}

function createColor() {
imgData.data[i] = colors[color][0];
imgData.data[i + 1] = colors[color][1];
imgData.data[i + 2] = colors[color][2];
imgData.data[i + 3] = 255;
i += 4;
}
<canvas id="canvas" hidden></canvas>
<br>
<canvas id="data" hidden></canvas>
<br>
<input type="file" id="file"></input>
<br>
<img id="img">
<p>Algorithms:</p>
<select id="selectCord">
<option value="1">Random</option>
<option value="2">Random Alligned</option>
<option value="3" selected>Loop</option>
</select>
<select id="selectColor">
<option value="2000">Super Speedy</option>
<option value="1000">Very Speedy</option>
<option value="500" selected>Speedy</option>
<option value="1">Visual</option>
</select>
<select id="colorDif">
<option value="RGB" selected>RGB</option>
<option value="HSL">HSL</option>
<option value="HSV">HSV</option>
</select>
<p>Algorithm Options:
<br>
</p>
<p>X Offset:
<input id="allignX" type="range" min="0" max="3" value="0"></input>
</p>
<p>Y Offset:
<input id="allignY" type="range" min="0" max="3" value="0"></input>
</p>
<p>Spacing X:
<input id="loopX" type="range" min="1" max="4" value="2"></input>
</p>
<p>Spacing Y:
<input id="loopY" type="range" min="1" max="4" value="2"></input>
</p>

RGB:
HSL:
HSV:

• Very cool. The "Run code snippet" breaks for me when it tries to set document.cookie (after 1000 iterations) because the document is sandboxed. Is the cookie necessary? Commented Jul 14, 2015 at 5:17
• No, once upon a time I ran the program for a few hours, but then my browser crashed. So I baked the cookie as a backup thing. But I'll remove it because it seems stack exchange dislikes cookies. Commented Jul 14, 2015 at 12:33
• Looking at your code, I think it might benefit from the same speedup I suggested on wolfhammer's answer, except applied to doThing instead of loop. You might find the speed increase worth the extra line... Commented Jul 14, 2015 at 22:53
• @trichoplax Thanks alot, Not only did your fix increase the speed of my program, while fixing I found and fixed a math error I made, and my program no longer generates those tiny black dots. Commented Jul 15, 2015 at 1:17
• That's great! The new output image looks much better. Commented Jul 15, 2015 at 1:56

## C# (reference implementation)

This is the code used to generate the images in the question. I thought it would be useful to give some people a reference for organizing their algorithm. A completely random coordinate and color are selected each movement. It performs surprisingly well considering the limitations imposed by the brush size/acceptance criteria.

I use the CIEDE2000 algorithm for measuring color differences, from the open source library ColorMine. This should give closer color matches (from a human perspective) but it doesn't seem to be a noticeable difference when used with this palette.

using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using ColorMine.ColorSpaces;
using ColorMine.ColorSpaces.Comparisons;

namespace Painter
{
public class Painter
{
private readonly Bitmap _source;
private readonly Bitmap _painting;
private readonly int _width;
private readonly int _height;
private readonly CieDe2000Comparison _comparison = new CieDe2000Comparison();
private const int BRUSHSIZE = 4;
private readonly Random _random = new Random();
private readonly ColorPalette _palette;

private static readonly int[][] BRUSH = {
new[] {1, 0}, new[] {2, 0},
new[] {0, 1}, new[] {1, 1}, new[] {2, 1}, new[] {3, 1},
new[] {0, 2}, new[] {1, 2}, new[] {2, 2}, new[] {3, 2},
new[] {1, 3}, new[] {2, 3}
};

public Painter(string sourceFilename, string paletteFilename)
{
_source = (Bitmap)Image.FromFile(sourceFilename);
_width = _source.Width;
_height = _source.Height;

_palette = Image.FromFile(paletteFilename).Palette;
_painting = new Bitmap(_width, _height, PixelFormat.Format8bppIndexed) {Palette = _palette};

// search for black in the color palette
for (int i = 0; i < _painting.Palette.Entries.Length; i++)
{
Color color = _painting.Palette.Entries[i];
if (color.R != 0 || color.G != 0 || color.B != 0) continue;
SetBackground((byte)i);
}
}

public void Paint()
{
// pick a color from the palette
int brushIndex = _random.Next(0, _palette.Entries.Length);
Color brushColor = _palette.Entries[brushIndex];

// choose coordinate
int x = _random.Next(0, _width - BRUSHSIZE + 1);
int y = _random.Next(0, _height - BRUSHSIZE + 1);

// determine whether to accept/reject brush
if (GetBrushAcceptance(brushColor, x, y))
{
BitmapData data = _painting.LockBits(new Rectangle(0, y, _width, BRUSHSIZE), ImageLockMode.ReadWrite, PixelFormat.Format8bppIndexed);
byte[] bytes = new byte[data.Height * data.Stride];
Marshal.Copy(data.Scan0, bytes, 0, bytes.Length);

// apply 4x4 brush without corners
foreach (int[] offset in BRUSH)
{
bytes[offset[1] * data.Stride + offset[0] + x] = (byte)brushIndex;
}
Marshal.Copy(bytes, 0, data.Scan0, bytes.Length);
_painting.UnlockBits(data);
}
}

public void Save(string filename)
{
_painting.Save(filename, ImageFormat.Png);
}

private void SetBackground(byte index)
{
BitmapData data = _painting.LockBits(new Rectangle(0, 0, _width, _height), ImageLockMode.WriteOnly, PixelFormat.Format8bppIndexed);
byte[] bytes = new byte[data.Height * data.Stride];
for (int i = 0; i < data.Height; i++)
{
for (int j = 0; j < data.Stride; j++)
{
bytes[i*data.Stride + j] = index;
}
}
Marshal.Copy(bytes, 0, data.Scan0, bytes.Length);
_painting.UnlockBits(data);
}

private bool GetBrushAcceptance(Color brushColor, int x, int y)
{
double currentDifference = 0.0;
double brushDifference = 0.0;
foreach (int[] offset in BRUSH)
{
Color sourceColor = _source.GetPixel(x + offset[0], y + offset[1]);
Rgb sourceRgb = new Rgb {R = sourceColor.R, G = sourceColor.G, B = sourceColor.B};
Color currentColor = _painting.GetPixel(x + offset[0], y + offset[1]);

currentDifference += sourceRgb.Compare(new Rgb {R = currentColor.R, G = currentColor.G, B = currentColor.B}, _comparison);
brushDifference += sourceRgb.Compare(new Rgb {R = brushColor.R, G = brushColor.G, B = brushColor.B}, _comparison);
}
return brushDifference < currentDifference;
}
}
}


Then you can generate series of images (like my video) by calling an instance in a way similar to the code below (tweak based on number of iterations/frames/name desired). The first argument is the file path to the source image, the second argument is the file path to the palette (linked in the question), and the third argument is the file path for output images.

namespace Painter
{
class Program
{
private static void Main(string[] args)
{
int i = 0;
int counter = 1;
Painter painter = new Painter(args[0], args[1]);
while (true)
{
painter.Paint();
if (i%500000 == 0)
{
counter++;
painter.Save(string.Format("{0}{1:D7}.png", args[2], counter));
}
i++;
}
}
}
}


I searched for some colorful canvas paintings online and came across the images below, which seem to be great (complicated) test images. All copyrights belong to their respective owners.

Source

Source

• This is how I know I don't know anything about anything. Nice solution Commented Jul 14, 2015 at 18:29

# JavaScript Canvas

Update

Excellent suggestions in the comments. It's now faster and doesn't slow down the ui!

function previewFile() {
var srcImage = document.getElementById('srcImage');
var file = document.querySelector('input[type=file]').files[0];

}

if (file) {
} else {
srcImage.src = "";
}
}

var buckets = []; // buckets / iterations
var iter_per_focus = 5000;

var pal = "00FFFF,0000FF,00FF00,FFFF00,\
C0C0C0,FF0000,FF00FF,FFFF78,\
FF0078,FF7848,7878FF,78FFFF,\
00FF78,784800,007800,\
007878,787800,780000,787878,\
000078,780078,004878,7800FF,\
0078FF,004848,787848,000000,FFFFFF".split(",");
var pLen = pal.length;
var p = 0;
var _R = 0;
var _G = 1;
var _B = 2;
var _CAN = 3;

// Create fast access palette with r,g,b values and
// brush image for color.
function initPal() {

for (var i = 0; i < pal.length; i++) {
var r = parseInt(pal[i].substr(0, 2), 16);
var g = parseInt(pal[i].substr(2, 2), 16);
var b = parseInt(pal[i].substr(4, 2), 16);
var pcan = document.createElement('canvas');
pcan.width = 4;
pcan.height = 4;
var pctx = pcan.getContext('2d');
pctx.fillStyle = '#' + pal[i];
pctx.beginPath();
pctx.rect(1, 0, 2, 4);
pctx.rect(0, 1, 4, 2);
pctx.fill();

pal[i] = [r,g,b,pcan];

}
}
initPal();

var score = [];
var can = document.getElementById("canB");
var ctx = can.getContext('2d');
var mainDiv = document.getElementById("main");
var bCan = document.createElement('canvas');
bCan.width = can.width;
bCan.height = can.height;
var bCtx = bCan.getContext('2d');

var canA = document.getElementById("canA");
can.width = can.height = canA.width = canA.height = 200;
var ctxA = canA.getContext('2d');
var imageData;
var data;

function getSrcImage() {
var img = document.getElementById('srcImage');
can.width = canA.width = img.width;
can.height = canA.height = img.height;
ctxA.drawImage(img, 0, 0);
imageData = ctxA.getImageData(0, 0, img.width, img.height);
data = imageData.data;

// adjust for brush offset
var w = can.width - 2;
var h = can.height - 2;

var n = Math.floor((w * h) / iter_per_focus);
buckets = [];
for (var i = 0; i < n; i++) {
var bucket = [];
bucket.r = Math.floor(Math.random() * pLen);
buckets.push(bucket);
}
var b = 0;
var pt = 0;
for (var y = 0; y < h; y++) {
for (var x = 0; x < w; x++, pt+=4) {
var r = Math.floor((Math.random() * n));
buckets[r].push([x,y,pt,256 * 12,Math.floor(Math.random()*pLen)]);
b %= n;
}
pt += 8; // move past brush offset.
}

}

var loopTimeout = null;

function loopInit() {
var r, y, x, pt, c, s;
var row = can.width * 4;

var b = 0;

function loop() {
clearTimeout(loopTimeout);
var bucket = buckets[b++];
var len = bucket.length;
// Stepping color
//c = pal[p];
// Pulsing color;
//c = pal[Math.floor(Math.random()*pLen)]
// Pulsting step
c = pal[bucket.r++];
bucket.r%=pLen;
b %= buckets.length;
if (b === 0) {
p++;
p%=pLen;
}

for (var i = 0; i < len; i++) {

var x = bucket[i][0]
var y = bucket[i][1];
var pt = bucket[i][2];
// Random color
//c = pal[bucket[i][4]++];
//bucket[i][4]%=pLen;

s = Math.abs(data[pt] - c[_R]) +
Math.abs(data[pt + 1] - c[_G]) +
Math.abs(data[pt + 2] - c[_B]) +
Math.abs(data[pt + 4] - c[_R]) +
Math.abs(data[pt + 5] - c[_G]) +
Math.abs(data[pt + 6] - c[_B]) +
Math.abs(data[pt + row] - c[_R]) +
Math.abs(data[pt + row + 1] - c[_G]) +
Math.abs(data[pt + row + 2] - c[_B]) +
Math.abs(data[pt + row + 4] - c[_R]) +
Math.abs(data[pt + row + 5] - c[_G]) +
Math.abs(data[pt + row + 6] - c[_B]);
if (bucket[i][3] > s) {
bucket[i][3] = s;
bCtx.drawImage(c[_CAN], x - 1, y - 1);
}

}
loopTimeout = setTimeout(loop, 0);
}

loop();
}

// Draw function is separate from rendering. We render
// to a backing canvas first.
function draw() {
ctx.drawImage(bCan, 0, 0);
setTimeout(draw, 100);
}

function start() {

getSrcImage();
imageData = ctxA.getImageData(0, 0, can.width, can.height);
data = imageData.data;
bCan.width = can.width;
bCan.height = can.height;
bCtx.fillStyle = "black";
bCtx.fillRect(0, 0, can.width, can.height);
loopInit();

draw();
}
body {
background-color: #444444;
color: #DDDDEE;
}
#srcImage {
display: none;
}
#testBtn {
display: none;
}
#canA {
display:none;
}
<input type="file" onchange="previewFile()">
<br>
<img src="" height="200" alt="Upload Image for MS Painting">

<button onclick="genImage()" id="testBtn">Generate Image</button>

<div id="main">
<img id="srcImage" src="" onload="start()">
<canvas id="canA"></canvas>
<canvas id="canB"></canvas>
</div>

• @trichoplax I was having some cross site issues with loading the image. I'll see if I can figure something out. Commented Jul 13, 2015 at 20:23
• @trichoplax No the dark wasn't intentional. It was a bug with the transparency in the generated image. The comparing code thought transparent should be black. Commented Jul 13, 2015 at 20:28
• @trichoplax I've changed it to only compare a random color. Commented Jul 14, 2015 at 19:07
• I copied your code into a jsfiddle and tried an experiment. It made the convergence somewhat faster. You might like to try it... All I did was surround the contents of the loop function with a for loop to repeat the contents 1000 times. This means mouse and keyboard events are only checked for every 1000 iterations instead of every iteration. Your loop is fast enough that every 1000 iterations still leaves the mouse and keyboard responsive, and it saves waiting hours for convergence :) Commented Jul 14, 2015 at 22:49
• @tricholplax Wow those suggestions made things a lot faster. I think s /= 4 is needed, I don't get the cool color animation with it. Commented Jul 15, 2015 at 6:31

## Mathematica

It's not really all that fast though, but at least it makes vaguely recognisable images, so I'm happy.

img = Import["https://i.sstatic.net/P7X6g.jpg"]
squigglesize = 20;
squiggleterb = 35;
colist = Table[RGBColor[PixelValue[colors, {x, 1}]], {x, 28}];
imgdim0 = ImageDimensions[img];
curimg = Image[ConstantArray[0, Reverse[imgdim0]]];

rp := RandomInteger[squigglesize, 2] - squigglesize/2;
i = 0; j = 0;
Module[{imgdim = imgdim0, randimg, points, randcol, squigmid, st,
randist, curdist = curdist0, i = 0, j = 0},

While[j < 10,
squigmid = {RandomInteger[imgdim[[1]]], RandomInteger[imgdim[[1]]]};
While[i < 20,
randcol = RandomChoice[colist];
st = RandomInteger[squiggleterb, 2] - squiggleterb/2;
points = {rp + squigmid + st, rp + squigmid + st, rp + squigmid + st, rp + squigmid + st};

randimg =
Rasterize[
Style[Graphics[{Inset[curimg, Center, Center, imgdim],
{randcol, BezierCurve[Table[{-1, 0}, {4}] + points]},
{randcol, BezierCurve[Table[{-1, 1}, {4}] + points]},
{randcol, BezierCurve[Table[{0, -1}, {4}] + points]},
{randcol, BezierCurve[points]},
{randcol, BezierCurve[Table[{0, 1}, {4}] + points]},
{randcol, BezierCurve[Table[{0, 2}, {4}] + points]},
{randcol, BezierCurve[Table[{1, -1}, {4}] + points]},
{randcol, BezierCurve[Table[{1, 0}, {4}] + points]},
{randcol, BezierCurve[Table[{1, 1}, {4}] + points]},
{randcol, BezierCurve[Table[{1, 2}, {4}] + points]},
{randcol, BezierCurve[Table[{2, 0}, {4}] + points]},
{randcol, BezierCurve[Table[{2, 1}, {4}] + points]}
}, ImageSize -> imgdim, PlotRange -> {{0, imgdim[[1]]}, {0, imgdim[[2]]}}],
Antialiasing -> False], RasterSize -> imgdim];
randist = ImageDistance[img, randimg];
If[randist < curdist, curimg = randimg; curdist = randist; i = 0;
j = 0;];
i += 1;
]; j += 1; i = 0;];
Print[curimg]]


Output:

Output could probably be a bit better with more iterations, and there's still a lot that I can try to speed it up/improve convergence, but for now this seems good enough.

# Java + Processing

I saw this challenge and immediately had to try it.

My algorithm isn't too well optimized, so the output is a bit choppy.

color[] palette={#000000,#FFFFFF,#C0C0C0,#808080,#7E0308,#FC0D1B,#FFFD38,#807F17,#0F7F12,#29FD2E,#2DFFFE,#11807F,#020C7E,#0B24FB,#FC28FC,#7F0F7E,#807F44,#FFFD88,#2AFD85,#044040,#1783FB,#85FFFE,#8184FC,#06427E,#7F25FB,#7F400D,#FD8049,#FC1681};
PImage p;
int currTime;
int sTime=0;
int yPix;
void settings() {
yPix = 0;

size(p.width,p.height);
}
void setup() {
frameRate(p.width);
noStroke();
rectMode(CENTER);
//image(p,0,0);
//for(int i=0; i<palette.length;i++) {
//  fill(palette[i]);
//  square(i*20,0, 20);
//}
}

void draw() {

int x =  int(random(p.width));
int y = int(random(p.height));
color randPix = p.get(x,y);
float[] d = new float[palette.length];
for(int k=0;k<palette.length;k++) {
d[k]=abs(red(randPix)-red(palette[k]))+abs(blue(randPix)-blue(palette[k]))+abs(green(randPix)-green(palette[k]));
}int b=0;
for(int l=0;l<palette.length;l++){
if(d[l]<=d[b]){
b=l;
}
}
fill(palette[b]);
rect(x,y,2,4);
rect(x,y,4,2);

}
void mouseClicked() {
noLoop();
save("c.png");
}


# SmileBASIC

OPTION STRICT
OPTION DEFINT

DEF MSPAINT(IMAGE,WIDTH,HEIGHT,STEPS)
DIM COLORS[28]
COPY COLORS%,@COLORS
@COLORS
DATA &H000000,&H808080,&H800000
DATA &H808000,&H008000,&H008080
DATA &H000080,&H800080,&H808040
DATA &H004040,&H0080FF,&H004080
DATA &H8000FF,&H804000,&HFFFFFF
DATA &HC0C0C0,&HFF0000,&HFFFF00
DATA &H00FF00,&H00FFFF,&H0000FF
DATA &HFF00FF,&HFFFF80,&H00FF80
DATA &H80FFFF,&H8080FF,&HFF0080
DATA &HFF8040

'create output array and fill with white
DIM OUTPUT[WIDTH,HEIGHT]
FILL OUTPUT,&HFFFFFFFF

VAR K
FOR K=1 TO STEPS
'Pick random position/color
VAR X=RND(WIDTH -3)
VAR Y=RND(HEIGHT-3)
VAR COLOR=COLORS[RND(28)]

'Extract average (really the sum) color in a 4x4 area.
'this is less detailed than checking the difference of every pixel
'but it's better in some ways...
'corners are included so it will do SOME dithering
'R1/G1/B1 = average color in original image
'R2/G2/B2 = average color in current drawing
'R3/G3/B3 = average color if brush is used
VAR R1=0,G1=0,B1=0,R2=0,G2=0,B2=0,R3=0,G3=0,B3=0
VAR R,G,B
VAR I,J
FOR J=0 TO 3
FOR I=0 TO 3
'original image average
RGBREAD IMAGE[Y+J,X+I] OUT R,G,B
INC R1,R
INC G1,G
INC B1,B
'current drawing average
RGBREAD OUTPUT[Y+J,X+I] OUT R,G,B
INC R2,R
INC G2,G
INC B2,B
'add the old color to the brush average if we're in a corner
IF (J==0||J==3)&&(I==0||I==3) THEN
INC R3,R
INC G3,G
INC B3,B
ENDIF
NEXT
NEXT
'brush covers 12 pixels
RGBREAD COLOR OUT R,G,B
INC R3,R*12
INC G3,G*12
INC B3,B*12

'Compare
BEFORE=ABS(R1-R2)+ABS(G1-G2)+ABS(B1-B2)
AFTER =ABS(R1-R3)+ABS(G1-G3)+ABS(B1-B3)

'Draw if better
IF AFTER<BEFORE THEN
FILL OUTPUT,COLOR, Y   *WIDTH+X+1,2 ' ##
FILL OUTPUT,COLOR,(Y+1)*WIDTH+X  ,4 '####
FILL OUTPUT,COLOR,(Y+2)*WIDTH+X  ,4 '####
FILL OUTPUT,COLOR,(Y+3)*WIDTH+X+1,2 ' ##
ENDIF
NEXT

RETURN OUTPUT
END


MSPAINT image%[] , width% , height% , steps% OUT output%[]

• image% - 2D [y,x] integer array with the image data (32 bit ARGB format (alpha is ignored))
• width% - image width
• height% - image height
• steps% - number of iterations
• output% - output array, same as image%.

• can you add some examples? Commented Mar 10, 2018 at 17:31
• Yeah, I'll add some soon (It's a lot of work to transfer images though, so I'll have to just take pictures of the screen for now) Commented Mar 10, 2018 at 17:56