Ich habe ein Mosaik von 2025 Headshots aus den Avataren der Top-Stack Overflow-Benutzer zusammengestellt .
(Klicken Sie auf das Bild, um es in voller Größe anzuzeigen.)

Ihre Aufgabe ist es, einen Algorithmus zu schreiben, der aus den 48 × 48 Pixel-Avataren dieses 45 × 45-Rasters ein genaues Fotomosaik eines anderen Bildes erstellt.

Bilder testen

Hier sind die Testbilder. Das erste ist natürlich eine Glühbirne!
(Sie sind hier nicht in voller Größe. Klicken Sie auf ein Bild, um es in voller Größe anzuzeigen. Für The Kiss , A Sunday Afternoon ... , Steve Jobs und die Sphären sind Versionen in halber Größe verfügbar .)

^{Vielen Dank an Wikipedia für alle außer den Raytracing-Sphären.}

In voller Größe haben diese Bilder alle Abmessungen, die durch 48 teilbar sind. Die größeren Bilder mussten JPEGs sein, damit sie zum Hochladen komprimiert werden konnten.

Wertung

Dies ist ein Beliebtheitswettbewerb. Die Einreichung mit Mosaiken, die die Originalbilder am genauesten wiedergeben, sollte positiv bewertet werden. Ich werde die Antwort mit den meisten Stimmen in ein oder zwei Wochen annehmen.

Regeln

• Ihre Fotomosaiken müssen vollständig aus unveränderten 48 × 48-Pixel-Avataren bestehen, die aus dem obigen Mosaik stammen und in einem Raster angeordnet sind.

• Sie können einen Avatar in einem Mosaik wiederverwenden. (In der Tat müssen Sie für die größeren Testbilder.)

• Zeigen Sie Ihre Ausgabe, aber denken Sie daran, dass die Testbilder sehr groß sind und StackExchange nur das Posten von Bildern mit bis zu 2 MB zulässt . Komprimieren Sie also Ihre Bilder oder hosten Sie sie woanders und fügen Sie hier kleinere Versionen ein.

• Um als Gewinner bestätigt zu werden, müssen Sie PNG-Versionen Ihrer Glühbirnen- oder Kugelmosaike bereitstellen. Auf diese Weise kann ich sie überprüfen (siehe unten), um sicherzustellen, dass Sie den Avataren keine zusätzlichen Farben hinzufügen, damit die Mosaike besser aussehen.

Validator

Mit diesem Python-Skript können Sie überprüfen, ob ein fertiges Mosaik wirklich unveränderte Avatare verwendet. Einfach einstellen toValidateund allTiles. Es ist unwahrscheinlich, dass es für JPEGs oder andere verlustbehaftete Formate funktioniert, da es die Dinge Pixel für Pixel genau vergleicht.

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

Viel Glück euch allen! Ich kann es kaum erwarten, die Ergebnisse zu sehen.

Hinweis: Ich weiß, dass Fotomosaik-Algorithmen online leicht zu finden sind, aber noch nicht auf dieser Website. Ich hoffe wirklich, dass wir etwas interessanteres sehen als den üblichen Algorithmus "Durchschnitt für jede Kachel und jeden Rasterplatz und Abgleich" .

Java, durchschnittliche Entfernung

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

Der Algorithmus durchsucht alle Avatar-Kacheln für jeden Rasterplatz separat. Aufgrund der geringen Größe habe ich keine ausgeklügelten Datenstrukturen oder Suchalgorithmen implementiert, sondern einfach den gesamten Raum brachialisiert.

Dieser Code nimmt keine Änderungen an den Kacheln vor (z. B. keine Anpassung an die Zielfarben).

Ergebnisse

Klicken Sie hier für ein größeres Bild.

Auswirkung des Radius

Mit können radiusSie die Wiederholbarkeit der Kacheln im Ergebnis reduzieren. Die Einstellung radius=0hat keine Auswirkung. ZB radius=3unterdrückt das gleiche Plättchen in einem Radius von 3 Plättchen.

Radius = 0

Radius = 3

Auswirkung des Skalierungsfaktors

Anhand des scalingFaktors können wir bestimmen, wie die passende Kachel gesucht wird. scaling=1bedeutet, nach einer pixelgenauen Übereinstimmung zu suchen, während eine Suche nach scaling=48durchschnittlichen Kacheln durchgeführt wird.

Skalierung = 48

Skalierung = 16

Skalierung = 4

Skalierung = 1

Mathematica mit Kontrolle der Granularität

Hierbei werden nach Bedarf die Fotos mit 48 x 48 Pixeln verwendet. Standardmäßig werden diese Pixel gegen ein entsprechendes 48 x 48 Pixel großes Quadrat aus dem zu approximierenden Bild ausgetauscht.

Die Größe der Zielquadrate kann jedoch kleiner als 48 x 48 eingestellt werden, um eine höhere Detailtreue zu ermöglichen. (siehe die Beispiele unten).

Vorverarbeitung der Palette

collage ist das Bild, das die Fotos enthält, die als Palette dienen sollen.

picsColorsist eine Liste der einzelnen Fotos, gepaart mit ihren Durchschnittswerten für Rot, Grün und Blau.

targetColorToPhoto [] `verwendet die durchschnittliche Farbe des Zielstreifens und sucht das Foto aus der Palette, das am besten zu ihm passt.

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

Beispiel

Lassen Sie uns das Foto finden, das am besten zu RGBColor [0.640, 0.134, 0.249] passt:

Fotomosaik

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 verwendet als Eingabe das Rohbild, aus dem wir ein Fotomosaik erstellen.

targetPic entfernt einen vierten Parameter (von PNGs und einigen JPGs) und lässt nur R, G, B.

dimssind die Dimensionen von targetPic.

tiles sind die kleinen Quadrate, die zusammen das Zielbild bilden.

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

tileReplacements sind die Fotos, die zu jeder Kachel passen, in der richtigen Reihenfolge.

gallery ist die Menge der Kachelersetzungen (Fotos) mit der richtigen Dimension (dh der Anzahl der Zeilen und Spalten, die mit den Kacheln übereinstimmen).

ImageAssembly Verbindet das Mosaik zu einem fortlaufenden Ausgabebild.

Beispiele

Dies ersetzt jedes 12 x 12 Quadrat aus dem Bild am Sonntag durch ein entsprechendes 48 x 48 Pixel großes Foto, das für die durchschnittliche Farbe am besten geeignet ist.

photoMosaic[sunday, 12]

Sonntag (Detail)

photoMosaic[lightbulb, 6]

photoMosaic[stevejobs, 24]

Detail, Stevejobs.

photoMosaic[kiss, 24]

Detail des Kusses:

photoMosaic[spheres, 24]

JS

Gleich wie beim vorherigen Golf: http://jsfiddle.net/eithe/J7jEk/ : D

(Diesmal mit aufgerufen unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}) (Behandeln Sie die Palette nicht so, dass nur ein Pixel verwendet wird. Palettenpixel sind 48x48-Farbfelder, Formpixel sind 48x48-Farbfelder.)

Derzeit durchsucht es die Avatare-Liste, um die nächstgelegene Übereinstimmung nach Gewicht des ausgewählten Algorithmus zu finden, führt jedoch keine Farbgleichmäßigkeitsanpassung durch (etwas, das ich mir ansehen muss).

Leider kann ich nicht mit größeren Bildern herumspielen, da mir der Arbeitsspeicher ausgeht: D Wenn möglich, würde ich kleinere Ausgabebilder begrüßen. Wenn Sie die Hälfte der angegebenen Bildgröße verwenden, ist hier der Sonntagnachmittag:

GLSL

Der Unterschied zwischen dieser Herausforderung und der bei American Gothic in der Palette von Mona Lisa: Die Pixel neu anordnen interessiert mich, weil die Mosaikfliesen wiederverwendet werden können, während die Pixel nicht können. Das bedeutet, dass es leicht möglich ist, den Algorithmus zu parallelisieren. Ich habe mich daher für eine massiv parallele Version entschieden. Mit "massiv" meine ich, die 1344-Shader-Kerne auf der GTX670 meines Desktops gleichzeitig über GLSL zu verwenden.

Methode

Die tatsächliche Kachelanpassung ist einfach: Ich berechne den RGB-Abstand zwischen jedem Pixel in einem Zielbereich und dem Mosaikkachelbereich und wähle die Kachel mit der geringsten Differenz (gewichtet mit Helligkeitswerten). Der Kachelindex wird in den roten und grünen Farbattributen des Fragments ausgegeben. Nachdem alle Fragmente gerendert wurden, lese ich die Werte aus dem Framebuffer zurück und erstelle das Ausgabebild aus diesen Indizes. Die tatsächliche Implementierung ist ein ziemlicher Hack. Anstatt ein FBO zu erstellen, habe ich nur ein Fenster geöffnet und darin gerendert, aber GLFW kann keine Fenster mit willkürlich kleinen Auflösungen öffnen. Daher erstelle ich das Fenster größer als erforderlich und zeichne dann ein kleines Rechteck, das die richtige Größe hat Ein Fragment pro Kachel, das dem Quellbild zugeordnet ist. Die gesamte MSVC2013-Lösung ist unter verfügbarhttps://bitbucket.org/Gibgezr/mosaicmaker Zum Kompilieren sind GLFW / FreeImage / GLEW / GLM und OpenGL 3.3 oder bessere Treiber / Grafikkarten erforderlich.

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

Ergebnisse

Die Bilder werden fast sofort gerendert, sodass die Parallelisierung ein Erfolg war. Der Nachteil ist, dass ich die einzelnen Fragmente nicht von der Ausgabe anderer Fragmente abhängig machen kann. Daher gibt es keine Möglichkeit, die signifikante Qualitätssteigerung zu erzielen, die Sie erzielen, wenn Sie nicht zweimal innerhalb eines bestimmten Bereichs dasselbe Plättchen auswählen. Schnelle Ergebnisse, aber eingeschränkte Qualität aufgrund massiver Fliesenwiederholungen. Alles in allem hat es Spaß gemacht. http://imgur.com/a/M0Db0 für Vollversionen.

Python

Hier geht es um die erste Python-Lösung, die einen mittleren Ansatz verwendet. Wir können uns von hier aus weiterentwickeln. Der Rest der Bilder ist hier .

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'+'.'))

Noch eine andere Python-Lösung - auf Durchschnittsbasis (RGB vs L a b *)

Ergebnisse (Es gibt einige geringfügige Unterschiede)

Birne - RGB

Vollansicht

Bulb - Lab

Vollansicht

Steve - RGB

Vollansicht

Steve - Lab

Vollansicht

Kugeln - RGB

Vollansicht

Kugeln - Lab

Vollansicht

Sonntag - RGB

Vollansicht

Sonntag - Labor

Vollansicht

Kuss - RGB

Vollansicht

Kiss-Lab

Vollansicht

Code

benötigt python-colormath für Lab

#!/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)