Find a thumbnail in a mosaic

Question

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 {

    //Start with java MosaicFinder mosaic.jpg  59 43 target.png
    public static void main(String[] args)  throws Exception {
        String mosaicFilename = args[0]; 
        int tilesX = Integer.parseInt(args[1]);
        int tilesY = Integer.parseInt(args[2]);
        String targetFilename = args[3];

        BufferedImage mosaic = ImageIO.read(new File(mosaicFilename));
        int tileHeight = mosaic.getHeight()/tilesY;
        int tileWidth = mosaic.getWidth()/tilesX;

        BufferedImage tofind = ImageIO.read(new File(targetFilename));

        //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;
                        error = error.add(BigInteger.valueOf(Math.abs(r1-r2)));

                        int g1 = (rgb1) & 0xFF;
                        int g2 = (rgb2) & 0xFF;
                        error = error.add(BigInteger.valueOf(Math.abs(g1-g2)));

                        int b1 = rgb1 & 0xFF;
                        int b2 = rgb2 & 0xFF;
                        error = error.add(BigInteger.valueOf(Math.abs(b1-b2)));
                    }
                }
                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)

Answer 1

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[[1]]/tilesx, mDim[[2]]/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][[1]]]]

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[[1]]/x,r[[2]]/y}];
Reverse[Position[m,SortBy[{#,EuclideanDistance[Mean[k[ImageData@#,1]],w]}&/@k@m,Last][[1,1]]][[1]]]]

Answer 2

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)
# load mosaic ppm
_,w,_,m=O(m).read().split(N,3)
w,h=M(I,w.split())
u=w/c
v=h/r
m=M(A,m)
# load thumbnail ppm
t=M(A,O(t).read().split(N,3)[3])
# 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))[0][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 :)

Answer 3

Java (551) (523)

public class F{
    public static void main(String[]j)throws Exception{
        BufferedImage m=read(new File(j[0])),c;
        int x=parseInt(j[1]),a=parseInt(j[2]),
        w=m.getWidth()/x,h=m.getHeight()/a,
        b=0;
        c=new BufferedImage(w,h,1);
        c.getGraphics().drawImage(read(new File(j[3])).getScaledInstance(w,h,Image.SCALE_SMOOTH),0,0,null);
        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;

Answer 4

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[0]));int M=0xFF,x=parseInt(j[1]),a=parseInt(j[2]),w=m.getWidth()/x,h=m.getHeight()/a,b=0,n=0;BufferedImage u=read(new File(j[3])),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.