Photomosaics or: How Many Programmers Does it Take to Replace a Light Bulb?
Mathematica, with control for granularity
This uses the 48 x 48 pixel photos, as required. By default, it will swap those pixels for a corresponding 48x48 pixel square from the image to be approximated.
However, the size of the destination squares can be set to be smaller than 48 x 48, allowing for greater fidelity to detail. (see the examples below).
Preprocessing the palette
collage is the image containing the photos to serve as the palette.
picsColorsis a list of individual photos paired with their mean red, mean green, and mean blue values.
targetColorToPhoto[]` takes the average color of the target swath and finds the photo from the palette that best matches it.
parts=Flatten[ImagePartition[collage,48],1];
picsColors={#,c=Mean[Flatten[ImageData[#],1]]}&/@parts;
nf=Nearest[picsColors[[All,2]]];
targetColorToPhoto[p_]:=Cases[picsColors,{pic_,nf[p,1][[1]]}:>pic][[1]]
Example
Let's find the photo that best matches RGBColor[0.640, 0.134, 0.249]:
photoMosaic
photoMosaic[rawPic_, targetSwathSize_: 48] :=
Module[{targetPic, data, dims, tiles, tileReplacements, gallery},
targetPic = Image[data = ImageData[rawPic] /. {r_, g_, b_, _} :> {r, g, b}];
dims = Dimensions[data];
tiles = ImagePartition[targetPic, targetSwathSize];
tileReplacements = targetColorToPhoto /@ (Mean[Flatten[ImageData[#], 1]] & /@Flatten[tiles, 1]);
gallery = ArrayReshape[tileReplacements, {dims[[1]]/targetSwathSize,dims[[2]]/targetSwathSize}];
ImageAssemble[gallery]]
`photoMosaic takes as input the raw picture we will make a photo mosaic of.
targetPic will remove a fourth parameter (of PNGs and some JPGs), leaving only R, G, B.
dims are the dimensions of targetPic.
tiles are the little squares that together comprise the target picture.
targetSwathSize is the granularity parameter; it defaults at 48 (x48).
tileReplacements are the photos that match each tile, in proper order.
gallery is the set of tile-replacements (photos) with the proper dimensionality (i.e. the number of rows and columns that match the tiles).
ImageAssembly joins up the mosaic into a continuous output image.
Examples
This replaces each 12x12 square from the image, Sunday, with a corresponding 48 x 48 pixel photograph that best matches it for average color.
photoMosaic[sunday, 12]
Sunday (detail)
photoMosaic[lightbulb, 6]
photoMosaic[stevejobs, 24]
Detail, stevejobs.
photoMosaic[kiss, 24]
Detail of the Kiss:
photoMosaic[spheres, 24]
Java, average distance
package photomosaic;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import javax.imageio.ImageIO;
public class MainClass {
static final String FILE_IMAGE = "45148_sunday.jpg";
static final String FILE_AVATARS = "25745_avatars.png";
static final String FILE_RESULT = "mosaic.png";
static final int BLOCKSIZE = 48;
static final int SCALING = 4;
static final int RADIUS = 3;
public static void main(String[] args) throws IOException {
BufferedImage imageAvatars = ImageIO.read(new File(FILE_AVATARS));
int[] avatars = deBlock(imageAvatars, BLOCKSIZE);
BufferedImage image = ImageIO.read(new File(FILE_IMAGE));
int[] data = deBlock(image, BLOCKSIZE);
// perform the mosaic search on a downscaled version
int[] avatarsScaled = scaleDown(avatars, BLOCKSIZE, SCALING);
int[] dataScaled = scaleDown(data, BLOCKSIZE, SCALING);
int[] bests = mosaicize(dataScaled, avatarsScaled, (BLOCKSIZE / SCALING) * (BLOCKSIZE / SCALING), image.getWidth() / BLOCKSIZE);
// rebuild the image from the mosaic tiles
reBuild(bests, data, avatars, BLOCKSIZE);
reBlock(image, data, BLOCKSIZE);
ImageIO.write(image, "png", new File(FILE_RESULT));
}
// a simple downscale function using simple averaging
private static int[] scaleDown(int[] data, int size, int scale) {
int newsize = size / scale;
int newpixels = newsize * newsize;
int[] result = new int[data.length / scale / scale];
for (int r = 0; r < result.length; r += newpixels) {
for (int y = 0; y < newsize; y++) {
for (int x = 0; x < newsize; x++) {
int avgR = 0;
int avgG = 0;
int avgB = 0;
for (int sy = 0; sy < scale; sy++) {
for (int sx = 0; sx < scale; sx++) {
int dt = data[r * scale * scale + (y * scale + sy) * size + (x * scale + sx)];
avgR += (dt & 0xFF0000) >> 16;
avgG += (dt & 0xFF00) >> 8;
avgB += (dt & 0xFF) >> 0;
}
}
avgR /= scale * scale;
avgG /= scale * scale;
avgB /= scale * scale;
result[r + y * newsize + x] = 0xFF000000 + (avgR << 16) + (avgG << 8) + (avgB << 0);
}
}
}
return result;
}
// the mosaicize algorithm: take the avatar with least pixel-wise distance
private static int[] mosaicize(int[] data, int[] avatars, int pixels, int tilesPerLine) {
int tiles = data.length / pixels;
// use random order for tile search
List<Integer> ts = new ArrayList<Integer>();
for (int t = 0; t < tiles; t++) {
ts.add(t);
}
Collections.shuffle(ts);
// result array
int[] bests = new int[tiles];
Arrays.fill(bests, -1);
// make list of offsets to be ignored
List<Integer> ignores = new ArrayList<Integer>();
for (int sy = -RADIUS; sy <= RADIUS; sy++) {
for (int sx = -RADIUS; sx <= RADIUS; sx++) {
if (sx * sx + sy * sy <= RADIUS * RADIUS) {
ignores.add(sy * tilesPerLine + sx);
}
}
}
for (int t : ts) {
int b = t * pixels;
int bestsum = Integer.MAX_VALUE;
for (int at = 0; at < avatars.length / pixels; at++) {
int a = at * pixels;
int sum = 0;
for (int i = 0; i < pixels; i++) {
int r1 = (avatars[a + i] & 0xFF0000) >> 16;
int g1 = (avatars[a + i] & 0xFF00) >> 8;
int b1 = (avatars[a + i] & 0xFF) >> 0;
int r2 = (data[b + i] & 0xFF0000) >> 16;
int g2 = (data[b + i] & 0xFF00) >> 8;
int b2 = (data[b + i] & 0xFF) >> 0;
int dr = (r1 - r2) * 30;
int dg = (g1 - g2) * 59;
int db = (b1 - b2) * 11;
sum += Math.sqrt(dr * dr + dg * dg + db * db);
}
if (sum < bestsum) {
boolean ignore = false;
for (int io : ignores) {
if (t + io >= 0 && t + io < bests.length && bests[t + io] == at) {
ignore = true;
break;
}
}
if (!ignore) {
bestsum = sum;
bests[t] = at;
}
}
}
}
return bests;
}
// build image from avatar tiles
private static void reBuild(int[] bests, int[] data, int[] avatars, int size) {
for (int r = 0; r < bests.length; r++) {
System.arraycopy(avatars, bests[r] * size * size, data, r * size * size, size * size);
}
}
// splits the image into blocks and concatenates all the blocks
private static int[] deBlock(BufferedImage image, int size) {
int[] result = new int[image.getWidth() * image.getHeight()];
int r = 0;
for (int fy = 0; fy < image.getHeight(); fy += size) {
for (int fx = 0; fx < image.getWidth(); fx += size) {
for (int l = 0; l < size; l++) {
image.getRGB(fx, fy + l, size, 1, result, r * size * size + l * size, size);
}
r++;
}
}
return result;
}
// unsplits the block version into the original image format
private static void reBlock(BufferedImage image, int[] data, int size) {
int r = 0;
for (int fy = 0; fy < image.getHeight(); fy += size) {
for (int fx = 0; fx < image.getWidth(); fx += size) {
for (int l = 0; l < size; l++) {
image.setRGB(fx, fy + l, size, 1, data, r * size * size + l * size, size);
}
r++;
}
}
}
}
The algorithm performs a search through all avatar tiles for each grid space separately. Due to the small sizes I didn't implement any sophisticated data structurs or search algorithms but simply brute-force the whole space.
This code does not do any modifications to the tiles (e.g. no adaption to destination colors).
Results
Click for full-size image.
Effect of radius
Using radius you can reduce the repetitiveness of the tiles in the result. Setting radius=0 there is no effect. E.g. radius=3 supresses the same tile within a radius of 3 tiles.
radius=0
radius=3
Effect of scaling factor
Using the scaling factor we can determine how the matching tile is searched. scaling=1 means searching for a pixel-perfect match while scaling=48 does a average-tile search.
scaling=48
scaling=16
scaling=4
scaling=1
JS
Same as in previous golf: http://jsfiddle.net/eithe/J7jEk/ :D
(this time called with unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}) (don't treat palette to use one pixel once, palette pixels are 48x48 swatches, shape pixels are 48x48 swatches).
Currently it searches through the avatars list to find the nearest matching by weight of selected algorithm, however it doesn't perform any color uniformity matching (something I need to take a look at.
Unfortunately I'm not able to play around with larger images, because my RAM runs out :D If possible I'd appreciate smaller output images. If using 1/2 of image size provided, here's Sunday Afternoon:
