Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

After the last Ludum Dare (LD) game programming contest a friend of mine made a nice mosaic of all the LD game thumbnails:

mosaic of Ludum Dare games

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:

screenshot of 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: enter image description here

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)

share|improve this question

4 Answers 4

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]]]]
share|improve this answer
    
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 at 14:35
    
Cruncher, Interesting point. I was wondering about that. –  David Carraher Aug 28 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 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)
# 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 :)

share|improve this answer
2  
because you nerd-sniped me, Roy, and you know it ;) –  Will Aug 28 at 13:06

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.

share|improve this answer

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;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.