J'ai compilé une mosaïque de 2025 tirs à la tête à partir des avatars des principaux utilisateurs de Stack Overflow .
(Cliquez sur l'image pour la voir en taille réelle.)

Votre tâche consiste à écrire un algorithme permettant de créer une photomosaïque précise d'une autre image à l'aide des avatars de 48 × 48 pixels de cette grille de 45 × 45.

Images d'essai

Voici les images de test. Le premier est, bien sûr, une ampoule!
(Ils ne sont pas en taille réelle ici. Cliquez sur une image pour la voir en taille réelle. Des versions en taille réduite sont disponibles pour The Kiss , Un dimanche après-midi ... , Steve Jobs et les sphères .)

^{Merci à Wikipedia pour toutes les sphères sauf les rayons.}

A leur taille maximale, ces images ont toutes des dimensions divisibles par 48. Les plus grandes doivent être des images JPEG pour pouvoir être suffisamment comprimées pour être téléchargées.

Notation

C'est un concours de popularité. La soumission avec des mosaïques qui représentent le plus fidèlement les images originales doit être votée. J'accepterai la réponse la plus votée dans une semaine ou deux.

Règles

• Vos mosaïques photographiques doivent être entièrement composées d' avatars inaltérés de 48 × 48 pixels extraits de la mosaïque ci-dessus, disposés en grille.

• Vous pouvez réutiliser un avatar dans une mosaïque. (En effet, pour les images de test plus grandes, vous devrez le faire.)

• Montrez votre sortie, mais gardez à l' esprit que les images de test sont très grandes, et StackExchange permet uniquement l' affichage d'images à 2MB . Alors, compressez vos images ou hébergez-les ailleurs et mettez des versions plus petites ici.

• Pour être confirmé gagnant, vous devez fournir les versions PNG de votre mosaïque à ampoule ou sphères. C’est pour que je puisse les valider (voir ci-dessous) afin de vous assurer que vous n’ajoutez pas de couleurs supplémentaires aux avatars pour améliorer l’apparence des mosaïques.

Validateur

Ce script Python peut être utilisé pour vérifier si une mosaïque terminée utilise réellement des avatars non modifiés. Il suffit de mettre toValidateet allTiles. Il est peu probable que cela fonctionne avec les formats JPEG ou autres formats avec pertes, car il compare exactement les choses, pixel par pixel.

from PIL import Image, ImageChops

toValidate = 'test.png' #test.png is the mosaic to validate
allTiles = 'avatars.png' #avatars.png is the grid of 2025 48x48 avatars

def equal(img1, img2):
    return ImageChops.difference(img1, img2).getbbox() is None

def getTiles(mosaic, (w, h)):
    tiles = {}
    for i in range(mosaic.size[0] / w):
        for j in range(mosaic.size[1] / h):
            x, y = i * w, j * h
            tiles[(i, j)] = mosaic.crop((x, y, x + w, y + h))
    return tiles

def validateMosaic(mosaic, allTiles, tileSize):
    w, h = tileSize
    if mosaic.size[0] % w != 0 or mosaic.size[1] % h != 0:
        print 'Tiles do not fit mosaic.'
    elif allTiles.size[0] % w != 0 or allTiles.size[1] % h != 0:
        print 'Tiles do not fit allTiles.'
    else:
        pool = getTiles(allTiles, tileSize)
        tiles = getTiles(mosaic, tileSize)
        matches = lambda tile: equal(tiles[pos], tile)
        success = True
        for pos in tiles:
            if not any(map(matches, pool.values())):
                print 'Tile in row %s, column %s was not found in allTiles.' % (pos[1] + 1, pos[0] + 1)
                success = False
        if success:
            print 'Mosaic is valid.'
            return
    print 'MOSAIC IS INVALID!'

validateMosaic(Image.open(toValidate).convert('RGB'), Image.open(allTiles).convert('RGB'), (48, 48))

Bonne chance à tous! J'ai hâte de voir les résultats.

Note: Je sais que les algorithmes de photomosaïque sont faciles à trouver en ligne, mais ils ne sont pas encore sur ce site. J'espère vraiment que nous verrons quelque chose de plus intéressant que l' algorithme habituel "moyenne de chaque tuile et de chaque espace de grille et les faire correspondre" .

Java, distance moyenne

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++;
            }
        }
    }
}

L'algorithme effectue une recherche dans toutes les tuiles d'avatar pour chaque espace de grille séparément. En raison des petites tailles, je n’ai mis en œuvre aucune structure de données sophistiquée ni aucun algorithme de recherche, mais tout simplement une force brute dans tout l’espace.

Ce code ne modifie pas les mosaïques (par exemple, aucune adaptation aux couleurs de destination).

Résultats

Cliquez pour l'image en taille réelle.

Effet du rayon

En utilisant radiusvous pouvez réduire la répétitivité des carreaux dans le résultat. Définir radius=0il n'y a pas d'effet. Par exemple, radius=3supprime le même carreau dans un rayon de 3 carreaux.

rayon = 0

rayon = 3

Effet du facteur d'échelle

En utilisant le scalingfacteur, nous pouvons déterminer comment la mosaïque correspondante est recherchée. scaling=1signifie rechercher une correspondance parfaite au pixel tout en scaling=48effectuant une recherche moyenne.

mise à l'échelle = 48

mise à l'échelle = 16

mise à l'échelle = 4

mise à l'échelle = 1

Mathematica, avec contrôle de la granularité

Cela utilise les photos 48 x 48 pixels, selon les besoins. Par défaut, ces pixels seront échangés contre un carré correspondant de 48 x 48 pixels de l'image à approximer.

Toutefois, la taille des carrés de destination peut être définie sur une taille inférieure à 48 x 48, ce qui permet une plus grande fidélité des détails. (voir les exemples ci-dessous).

Prétraitement de la palette

collage est l'image contenant les photos pour servir de palette.

picsColorsest une liste de photos individuelles associées à leurs valeurs moyennes rouge, vert moyen et bleu moyen.

targetColorToPhoto [] `prend la couleur moyenne de la bande cible et trouve la photo de la palette qui lui correspond le mieux.

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]]

Exemple

Trouvons la photo qui correspond le mieux à 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 prend en entrée l'image brute dont nous allons faire une mosaïque.

targetPic supprimera un quatrième paramètre (de PNG et de certains JPG), ne laissant que R, G, B.

dimssont les dimensions de targetPic.

tiles sont les petits carrés qui composent l’image cible.

targetSwathSize is the granularity parameter; it defaults at 48 (x48).

tileReplacements sont les photos qui correspondent à chaque carreau, dans le bon ordre.

gallery est l'ensemble des remplacements de mosaïque (photos) avec la dimensionnalité appropriée (c'est-à-dire le nombre de lignes et de colonnes correspondant aux mosaïques).

ImageAssembly associe la mosaïque en une image de sortie continue.

Exemples

Ceci remplace chaque carré 12x12 de l'image, dimanche, par une photo correspondante de 48 x 48 pixels qui lui correspond le mieux pour une couleur moyenne.

photoMosaic[sunday, 12]

Dimanche (détail)

photoMosaic[lightbulb, 6]

photoMosaic[stevejobs, 24]

Détail, stevejobs.

photoMosaic[kiss, 24]

Détail du baiser:

photoMosaic[spheres, 24]

JS

Comme dans le golf précédent: http://jsfiddle.net/eithe/J7jEk/ : D

(cette fois appelée avec unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}) (ne traitez pas la palette pour utiliser un pixel une fois, les pixels de la palette sont 48x48 échantillons, les pixels de forme sont des échantillons 48x48).

Actuellement, il cherche dans la liste des avatars la correspondance la plus proche en fonction du poids de l'algorithme sélectionné. Toutefois, il ne réalise aucune correspondance d'uniformité des couleurs (ce que je dois examiner.

Malheureusement, je ne suis pas capable de jouer avec des images plus grandes, car ma mémoire RAM est épuisée: D Si possible, j'apprécierais des images de sortie plus petites. Si vous utilisez la moitié de la taille de l'image fournie, le dimanche après-midi:

GLSL

La différence entre ce défi et celui de American Gothic dans la palette de Mona Lisa: Réorganiser les pixels m'intéresse, car les mosaïques peuvent être réutilisées, alors que les pixels ne le peuvent pas. Cela signifie qu'il est possible de paralléliser facilement l'algorithme. J'ai donc décidé d'essayer une version massivement parallèle. Par "massivement", j'entends utiliser les 1344 noyaux de shader sur la GTX670 de mon ordinateur de bureau simultanément, via GLSL.

Méthode

La correspondance de mosaïque réelle est simple: je calcule la distance RVB entre chaque pixel d'une zone cible et la zone de mosaïque, puis je sélectionne la mosaïque présentant la différence la plus faible (pondérée par les valeurs de luminosité). L'index de mosaïque est écrit dans les attributs de couleur rouge et vert du fragment, puis après que tous les fragments aient été restitués, je relis les valeurs hors du framebuffer et construit l'image de sortie à partir de ces index. L'implémentation réelle est un sacré bidouillage; au lieu de créer un FBO, je viens d'ouvrir une fenêtre et de la rendre, mais GLFW ne peut pas ouvrir les fenêtres à des résolutions arbitrairement petites. Je crée donc la fenêtre plus grande que nécessaire, puis dessine un petit rectangle de la taille correcte. un fragment par mosaïque qui correspond à l'image source. L’ensemble de la solution MSVC2013 est disponible à l’adresse suivante:https://bitbucket.org/Gibgezr/mosaicmaker GLFW / FreeImage / GLEW / GLM est nécessaire pour la compilation, et OpenGL 3.3 ou une meilleure carte / carte vidéo pour fonctionner.

Fragment Shader Source

#version 330 core

uniform sampler2D sourceTexture;
uniform sampler2D mosaicTexture;

in vec2 v_texcoord;

out vec4 out_Color;

void main(void)
{   
    ivec2 sourceSize = textureSize(sourceTexture, 0);
    ivec2 mosaicSize = textureSize(mosaicTexture, 0);

    float num_pixels = mosaicSize.x/45.f;
    vec4 myTexel;
    float difference = 0.f;

    //initialize smallest difference to a large value
    float smallest_difference = 255.0f*255.0f*255.0f;
    int closest_x = 0, closest_y = 0;

    vec2 pixel_size_src = vec2( 1.0f/sourceSize.x, 1.0f/sourceSize.y);
    vec2 pixel_size_mosaic = vec2( 1.0f/mosaicSize.x , 1.0f/mosaicSize.y);

    vec2 incoming_texcoord;
    //adjust incoming uv to bottom corner of the tile space
    incoming_texcoord.x =  v_texcoord.x - 1.0f/(sourceSize.x / num_pixels * 2.0f);
    incoming_texcoord.y =  v_texcoord.y - 1.0f/(sourceSize.y / num_pixels * 2.0f);

    vec2 texcoord_mosaic;
    vec2 pixelcoord_src, pixelcoord_mosaic;
    vec4 pixel_src, pixel_mosaic;

    //loop over all of the mosaic tiles
    for(int i = 0; i < 45; ++i)
    {
        for(int j = 0; j < 45; ++j)
        {
            difference = 0.f;
            texcoord_mosaic = vec2(j * pixel_size_mosaic.x * num_pixels, i * pixel_size_mosaic.y * num_pixels);

            //loop over all of the pixels in the images, adding to the difference
            for(int y = 0; y < num_pixels; ++y)
            {
                for(int x = 0; x < num_pixels; ++x)
                {
                    pixelcoord_src = vec2(incoming_texcoord.x + x * pixel_size_src.x, incoming_texcoord.y + y * pixel_size_src.y);                  
                    pixelcoord_mosaic = vec2(texcoord_mosaic.x + x * pixel_size_mosaic.x, texcoord_mosaic.y + y * pixel_size_mosaic.y); 
                    pixel_src = texture(sourceTexture, pixelcoord_src);
                    pixel_mosaic = texture(mosaicTexture, pixelcoord_mosaic);

                    pixel_src *= 255.0f;
                    pixel_mosaic *= 255.0f;

                    difference += (pixel_src.x - pixel_mosaic.x) * (pixel_src.x - pixel_mosaic.x) * 0.5f+
                        (pixel_src.y - pixel_mosaic.y) * (pixel_src.y - pixel_mosaic.y) +
                        (pixel_src.z - pixel_mosaic.z) * (pixel_src.z - pixel_mosaic.z) * 0.17f;
                }

            }

            if(difference < smallest_difference)
            {
                smallest_difference = difference;
                closest_x = j;
                closest_y = i;
            }               
        }
    }

    myTexel.x = float(closest_x)/255.f;
    myTexel.y = float(closest_y)/255.f;
    myTexel.z = 0.f;
    myTexel.w = 0.f;    

    out_Color = myTexel;
}

Résultats

Les images sont rendues presque instantanément, la parallélisation a donc été un succès. L'inconvénient est que je ne peux pas faire en sorte que les fragments individuels dépendent de la sortie d'autres fragments. Il est donc impossible d'obtenir une augmentation significative de la qualité en ne sélectionnant pas deux fois la même tuile dans une certaine plage. Donc, des résultats rapides, mais une qualité limitée en raison de répétitions massives de carreaux. Dans l'ensemble, c'était amusant. http://imgur.com/a/M0Db0 pour les versions grandeur nature.

Python

Voici la première solution Python, utilisant une approche moyenne. Nous pouvons évoluer à partir d'ici. Le reste des images sont ici .

from PIL import Image
import numpy as np

def calcmean(b):
    meansum = 0
    for k in range(len(b)):
        meansum = meansum + (k+1)*b[k]
    return meansum/sum(b)    

def gettiles(imageh,w,h):
    k = 0 
    tiles = {}
    for x in range(0,imageh.size[0],w):
        for y in range(0,imageh.size[1],h):
            a=imageh.crop((x, y, x + w, y + h))
            b=a.resize([1,1], Image.ANTIALIAS)
            tiles[k] = [a,x,y,calcmean(b.histogram()[0:256]) \
                             ,calcmean(b.histogram()[256:256*2]) \
                             ,calcmean(b.histogram()[256*2:256*3])]
            k = k + 1
    return tiles

w = 48 
h = 48

srch = Image.open('25745_avatars.png').convert('RGB')
files = ['21104_spheres.png', '45148_sunday.jpg', '47824_steve.jpg', '61555_kiss.jpg', '77388_lightbulb.png']
for f in range(len(files)):
    desh = Image.open(files[f]).convert('RGB')

    srctiles = gettiles(srch,w,h)
    destiles = gettiles(desh,w,h)

    #build proximity matrix 
    pm = np.zeros((len(destiles),len(srctiles)))
    for d in range(len(destiles)):
        for s in range(len(srctiles)):
            pm[d,s] = (srctiles[s][3]-destiles[d][3])**2 + \
                      (srctiles[s][4]-destiles[d][4])**2 + \
                      (srctiles[s][5]-destiles[d][5])**2

    for k in range(len(destiles)):
        j = list(pm[k,:]).index(min(pm[k,:]))
        desh.paste(srctiles[j][0], (destiles[k][1], destiles[k][2]))

    desh.save(files[f].replace('.','_m'+'.'))

Encore une autre solution Python - Moyenne (RVB vs L a b *)

Résultats (il y a quelques légères différences)

Ampoule - RGB

vue complète

Ampoule - Lab

vue complète

Steve - RVB

vue complète

Steve - Lab

vue complète

Sphères - RVB

vue complète

Sphères - Lab

vue complète

Dimanche - RVB

vue complète

Dimanche - Lab

vue complète

Kiss - RGB

vue complète

Kiss - Lab

vue complète

Code

nécessite python-colormath pour le laboratoire

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from PIL import Image
from colormath.color_objects import LabColor,sRGBColor
from colormath.color_conversions import convert_color
from colormath.color_diff import delta_e_cie1976

def build_photomosaic_ils(mosaic_im,target_im,block_width,block_height,colordiff,new_filename):

    mosaic_width=mosaic_im.size[0]              #dimensions of the target image
    mosaic_height=mosaic_im.size[1]

    target_width=target_im.size[0]              #dimensions of the target image
    target_height=target_im.size[1]

    target_grid_width,target_grid_height=get_grid_dimensions(target_width,target_height,block_width,block_height)       #dimensions of the target grid
    mosaic_grid_width,mosaic_grid_height=get_grid_dimensions(mosaic_width,mosaic_height,block_width,block_height)       #dimensions of the mosaic grid

    target_nboxes=target_grid_width*target_grid_height
    mosaic_nboxes=mosaic_grid_width*mosaic_grid_height

    print "Computing the average color of each photo in the mosaic..."
    mosaic_color_averages=compute_block_avg(mosaic_im,block_width,block_height)
    print "Computing the average color of each block in the target photo ..."
    target_color_averages=compute_block_avg(target_im,block_width,block_height)

    print "Computing photomosaic ..."
    photomosaic=[0]*target_nboxes
    for n in xrange(target_nboxes):
        print "%.2f " % (n/float(target_nboxes)*100)+"%"
        for z in xrange(mosaic_nboxes):
            current_diff=colordiff(target_color_averages[n],mosaic_color_averages[photomosaic[n]])
            candidate_diff=colordiff(target_color_averages[n],mosaic_color_averages[z])

            if(candidate_diff<current_diff):
                photomosaic[n]=z

    print "Building final image ..."
    build_final_solution(photomosaic,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename)

def build_initial_solution(target_nboxes,mosaic_nboxes):
    candidate=[0]*target_nboxes

    for n in xrange(target_nboxes):
        candidate[n]=random.randint(0,mosaic_nboxes-1)

    return candidate

def build_final_solution(best,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename):

    for n in xrange(target_nboxes):

        i=(n%target_grid_width)*block_width             #i,j -> upper left point of the target image
        j=(n/target_grid_width)*block_height

        box = (i,j,i+block_width,j+block_height)        

        #get the best photo from the mosaic
        best_photo_im=get_block(mosaic_im,best[n],block_width,block_height)

        #paste the best photo found back into the image
        target_im.paste(best_photo_im,box)

    target_im.save(new_filename);


#get dimensions of the image grid
def get_grid_dimensions(im_width,im_height,block_width,block_height):
    grid_width=im_width/block_width     #dimensions of the target image grid
    grid_height=im_height/block_height
    return grid_width,grid_height

#compute the fitness of given candidate solution
def fitness(candidate,mosaic_color_averages,mosaic_nboxes,target_color_averages,target_nboxes):
    error=0.0
    for i in xrange(target_nboxes):
        error+=colordiff_rgb(mosaic_color_averages[candidate[i]],target_color_averages[i])
    return error

#get a list of color averages, i.e, the average color of each block in the given image
def compute_block_avg(im,block_height,block_width):

    width=im.size[0]
    height=im.size[1]

    grid_width_dim=width/block_width                    #dimension of the grid
    grid_height_dim=height/block_height

    nblocks=grid_width_dim*grid_height_dim              #number of blocks

    avg_colors=[]
    for i in xrange(nblocks):
        avg_colors+=[avg_color(get_block(im,i,block_width,block_height))]
    return avg_colors

#returns the average RGB color of a given image
def avg_color(im):
    avg_r=avg_g=avg_b=0.0
    pixels=im.getdata()
    size=len(pixels)
    for p in pixels:
        avg_r+=p[0]/float(size)
        avg_g+=p[1]/float(size)
        avg_b+=p[2]/float(size)

    return (avg_r,avg_g,avg_b)

#get the nth block of the image
def get_block(im,n,block_width,block_height):

    width=im.size[0]

    grid_width_dim=width/block_width                        #dimension of the grid

    i=(n%grid_width_dim)*block_width                        #i,j -> upper left point of the target block
    j=(n/grid_width_dim)*block_height

    box = (i,j,i+block_width,j+block_height)
    block_im = im.crop(box)
    return block_im


#calculate color difference of two pixels in the RGB space
#less is better
def colordiff_rgb(pixel1,pixel2):

    delta_red=pixel1[0]-pixel2[0]
    delta_green=pixel1[1]-pixel2[1]
    delta_blue=pixel1[2]-pixel2[2]

    fit=delta_red**2+delta_green**2+delta_blue**2
    return fit

#http://python-colormath.readthedocs.org/en/latest/index.html
#calculate color difference of two pixels in the L*ab space
#less is better
def colordiff_lab(pixel1,pixel2):

    #convert rgb values to L*ab values
    rgb_pixel_1=sRGBColor(pixel1[0],pixel1[1],pixel1[2],True)
    lab_1= convert_color(rgb_pixel_1, LabColor)

    rgb_pixel_2=sRGBColor(pixel2[0],pixel2[1],pixel2[2],True)
    lab_2= convert_color(rgb_pixel_2, LabColor)

    #calculate delta e
    delta_e = delta_e_cie1976(lab_1, lab_2)
    return delta_e


if __name__ == '__main__':
    mosaic="images/25745_avatars.png"
    targets=["images/lightbulb.png","images/steve.jpg","images/sunday.jpg","images/spheres.png","images/kiss.jpg"]
    target=targets[0]
    mosaic_im=Image.open(mosaic)
    target_im=Image.open(target)
    new_filename=target.split(".")[0]+"_photomosaic.png"
    colordiff=colordiff_rgb

    build_photomosaic_ils(mosaic_im,target_im,48,48,colordiff,new_filename)