# Find a thumbnail in a mosaic

After the last Ludum Dare (LD) game programming contest a friend of mine made a nice mosaic of all the LD game thumbnails: After searching for my own game I quickly gave up and decided to solve it like a real programmer... by writing code that finds my game thumbnail.

This is the thumbnail of my game: More examples can be found by going to the Ludum Dare list of games.

So what is the challenge? Write a program that has the following input:

<filename_mosaic> <amount_of_tiles_x> <amount_of_tiles_y> <filename_target>


For example using the images above:

mosaic.jpg 59 43 target.png


The output should be the index of the target image. For the mosaic and screenshot above the correct index is:

48,18


The following (non-golfed) code provides a working example:

public class MosaicFinder {

public static void main(String[] args)  throws Exception {
String mosaicFilename = args;
int tilesX = Integer.parseInt(args);
int tilesY = Integer.parseInt(args);
String targetFilename = args;

int tileHeight = mosaic.getHeight()/tilesY;
int tileWidth = mosaic.getWidth()/tilesX;

//Translate target.png to correct size:
BufferedImage matchCanvas = new BufferedImage(tileWidth, tileHeight, BufferedImage.TYPE_INT_RGB);
AffineTransform at = AffineTransform.getScaleInstance((tileWidth*1.0)/tofind.getWidth(), (tileHeight*1.0)/tofind.getHeight());
((Graphics2D)matchCanvas.getGraphics()).drawRenderedImage(tofind, at);

int bestIndexX = 0, bestIndexY = 0;
BigInteger lowest = null;
for(int x = 0; x<tilesX;x++) {
for(int y = 0; y<tilesY;y++) {
//For all tiles:
BigInteger error = BigInteger.ZERO;
for(int x1 = 0; x1<tileWidth;x1++) {
for(int y1 = 0; y1<tileHeight;y1++) {
int rgb1 = matchCanvas.getRGB(x1, y1);
int rgb2 = mosaic.getRGB((x*tileWidth)+x1, (y*tileHeight)+y1);
int r1 = (rgb1 >> 16) & 0xFF;
int r2 = (rgb2 >> 16) & 0xFF;

int g1 = (rgb1) & 0xFF;
int g2 = (rgb2) & 0xFF;

int b1 = rgb1 & 0xFF;
int b2 = rgb2 & 0xFF;
}
}
if(lowest == null || lowest.compareTo(error) > 0) {
lowest = error;
bestIndexX = (x+1);
bestIndexY = (y+1);
}
}
}
System.out.println(bestIndexX+","+bestIndexY);
}
}


This is a visual example of the code running: This contest is a code-golf contest, the shortest code wins the challenge.

Update: It seems stackexchange messes up the images a bit, on my blog you can find the source images for the examples in correct resolution. Also: I've fixed the amount of images from 42 to 43

Current best: David Carraher, Mathematica (280)

# Mathematica - 280 247

No need to scale the target to the tile size. The key is to match the average color for the target and for each tile. Closest match wins.
In principle, it would be possible for the routine to choose the wrong match, but the test case suggests that this approach is surprisingly robust. The mean colors of target and selected tile were almost a perfect match: a distance of 0.00296966 away from the target mean color in RGB colorspace "cube" with edges of length 1.

## Ungolfed 364 chars

f[{m_, tilesx_, tilesy_, targ_}] :=
Module[{mosaic = Import[m],target = Import[targ], mDim = ImageDimensions[mosaic],

(* find the average RGB colors for the target *)
meanTargetPixelColor = Mean[Flatten[ImageData[target], 1]], m, t},
m = ImagePartition[mosaic, {mDim[]/tilesx, mDim[]/tilesy}];

(*Find the color distances between target mean rob and each mosaic tile
Select the tile that best matches the average pixel color.*)
t = SortBy[{#, EuclideanDistance[Mean[Flatten[ImageData[#], 1]],
meanTargetPixelColor]} & /@ Flatten[m], Last][[1, 1]];
Reverse[Position[m, t][]]]


Example

Assuming that mosaic and targethold the respective filenames.

f[{mosaic, 59, 43, target}]


{48,18}

## Golfed 247

f@{p_,x_,y_,s_}:=Module[{k=Flatten,i=Import,z=i@p,w,m,t,r},r=ImageDimensions@z;
w=Mean[k[ImageData[i@s],1]];m=ImagePartition[z,{r[]/x,r[]/y}];
Reverse[Position[m,SortBy[{#,EuclideanDistance[Mean[k[ImageData@#,1]],w]}&/@k@m,Last][[1,1]]][]]]

• in principal, the solution in the original post can return the wrong result as well. Even if he used the identical scaling algorithm as the original creator used, 2 different images can scale to the same image (pigeon hole principal). In this case, I guess you'd be unable to discern the difference as a human as well though, so the answer would effectively still be right. – Cruncher Aug 28 '14 at 14:35
• Cruncher, Interesting point. I was wondering about that. – DavidC Aug 28 '14 at 14:45
• I like this approach, and just want to comment generally on using a single average colour. When I was placing the tiles to make the mosaic, I found using MSE greatly improved the patterns. You actually see tiles chosen that match detail within the original image too. There were other ideas I didn't explore, such as lab colour, gamma corrected scaling, SSIM, PSE etc. But per-pixel was, generally, very important. – Will Aug 29 '14 at 5:25

# Python (360)

I seem to have broken PIL somehow, so load PPMs instead. For this reason, I insist that the thumbnail is already scaled correctly to the size of the tile in the mosaic. Its my first ever codegolf submission and I'm unsure the leeway I can expect in this regard.

import sys
I=int
R=range
O=open
M=map
N='\n'
A=ord
S=sum
# parse arguments
_,m,c,r,t=sys.argv
c=I(c)
r=I(r)
w,h=M(I,w.split())
u=w/c
v=h/r
m=M(A,m)
# make a list of the MSE of each tile in the mosaic, sort it, print the best
print sorted((S(S((p-q)**2 for p,q in zip(t[(y*u+x)*3:][:3],
m[((i*v+y)*w+j*u+x)*3:][:3])) for x in R(u) for y in R(v)),
j+1,i+1) for j in R(c) for i in R(r))[1:]


Its really slow because of the m[ofs*3:][:3] to get the channels for each pixel; that's creating a list of the remainder of the pixels, and then slicing just the first three... horrid performance :)

• because you nerd-sniped me, Roy, and you know it ;) – Will Aug 28 '14 at 13:06

# Java (551) (523)

public class F{
public static void main(String[]j)throws Exception{
int x=parseInt(j),a=parseInt(j),
w=m.getWidth()/x,h=m.getHeight()/a,
b=0;
c=new BufferedImage(w,h,1);
for(int d=1<<30,y=x*a,e;--y>0;) {
e=0;
for(int z=w*h;z-->0;)
for(int i=0,l=c.getRGB(z/h,z%h),k=m.getRGB(y/a*w+z/h,y%a*h+z%h);++i<3;l>>=8,k>>=8)
e+=pow((l&255)-(k&255),2);
if(d>e){d=e;b=y;}
}
out.print(b/a+1+","+(b%a+1));
}
}


Whitespace added to make it a bit clearer.

Based on Roy's, but using a MSE, which is I believe a much superior metric. And less characters.

Java is really verbose :/

Imports etc are:

import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import static javax.imageio.ImageIO.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;


# Java (707)

My example code in golfed mode, removing spaces and using small variable names, without the needed imports:

public class F{public static void main(String[]j)throws Exception{BufferedImage m=read(new File(j));int M=0xFF,x=parseInt(j),a=parseInt(j),w=m.getWidth()/x,h=m.getHeight()/a,b=0,n=0;BufferedImage u=read(new File(j)),c=new BufferedImage(w,h,1);((Graphics2D)c.getGraphics()).drawRenderedImage(u,getScaleInstance((w*1.0)/u.getWidth(),(h*1.0)/u.getHeight()));BigInteger d=null;for(;x-->0;)for(int y=a;y-->0;){BigInteger e=ZERO;for(int z=w;z-->0;)for(int v=h;v-->0;){int l=c.getRGB(z,v),k=m.getRGB(x*w+z,y*h+v);e=e.add(valueOf(abs(((l>>16)&M)-((k>>16)&M)))).add(valueOf(abs(((l>>8)&M)-((k>>8)&M)))).add(valueOf(abs((l&M)-(k&M))));}if(d==null||d.compareTo(e)>0){d=e;b=x+1;n=y+1;}}out.print(b+","+n);}}


The imports are:

import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.math.BigInteger;
import static javax.imageio.ImageIO.*;
import static java.awt.geom.AffineTransform.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.math.BigInteger.*;


Java is horrible for code golf, but at least it is below 1000.