Я собрал мозаику из 2025 выстрелов в голову от аватаров лучших пользователей Stack Overflow .
(Нажмите на изображение, чтобы посмотреть его в полном размере.)

Ваша задача - написать алгоритм, который создаст точную фотомозаику другого изображения, используя аватары 48 × 48 пикселей из этой сетки 45 × 45.

Тестовые изображения

Вот тестовые изображения. Первая, конечно же, лампочка!
(Они не являются полноразмерными. Нажмите на изображение, чтобы просмотреть его в полном размере. Половинные версии доступны для Поцелуя , Воскресного полудня ... , Стива Джобса и сфер .)

^{Спасибо Википедии за все, кроме лучевых трасс.}

В полноразмерном виде все эти изображения имеют размеры, кратные 48. Более крупные из них должны были быть в формате JPEG, чтобы они могли быть достаточно сжаты для загрузки.

счет

Это конкурс популярности. За представление с мозаиками, которые наиболее точно изображают исходные изображения, следует проголосовать. Я приму ответ с наибольшим количеством голосов через неделю или две.

правила

• Ваша фотомозаика должна быть полностью составлена ​​из неизмененных аватаров 48 × 48 пикселей, взятых из мозаики выше, расположенных в виде сетки.

• Вы можете повторно использовать аватар в мозаике. (Действительно, для больших тестовых изображений вам придется.)

• Покажите свой вывод, но имейте в виду, что тестовые изображения очень большие, и StackExchange позволяет публиковать изображения размером до 2 МБ . Поэтому сожмите свои изображения или разместите их где-нибудь еще и разместите меньшие версии здесь.

• Для подтверждения победителя вы должны предоставить PNG-версии вашей лампочки или сферической мозаики. Поэтому я могу проверить их (см. Ниже), чтобы убедиться, что вы не добавляете дополнительные цвета в аватары, чтобы мозаика выглядела лучше.

Validator

Этот скрипт Python можно использовать для проверки, действительно ли в законченной мозаике используются неизмененные аватары. Просто установите toValidateи allTiles. Маловероятно, что он будет работать для JPEG или других форматов с потерями, поскольку он сравнивает вещи попиксельно.

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

Удачи всем! Я не могу ждать, чтобы увидеть результаты.

Примечание: я знаю, что алгоритмы фотомозаики легко найти в Интернете, но их еще нет на этом сайте. Я действительно надеюсь, что мы увидим что-то более интересное, чем обычный алгоритм «усреднить каждую плитку и каждое пространство сетки и сопоставить их» .

Ява, среднее расстояние

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

Алгоритм выполняет поиск по всем ячейкам аватара для каждого пространства сетки отдельно. Из-за небольших размеров я не реализовывал сложные структуры данных или алгоритмы поиска, а просто перебор всего пространства.

Этот код не делает никаких модификаций плиток (например, не адаптируется к цветам назначения).

Полученные результаты

Нажмите для просмотра в полном размере.

Влияние радиуса

С помощью radiusвы можете уменьшить повторяемость плиток в результате. Установка radius=0там не влияет. Например, radius=3подавляет одну и ту же плитку в радиусе 3 плиток.

Радиус = 0

Радиус = 3

Влияние коэффициента масштабирования

Используя scalingфактор, мы можем определить, как ищется соответствующий тайл. scaling=1означает поиск совпадения с точностью до пикселя, в то время как scaling=48выполняется поиск средней плитки.

масштабирование = 48

масштабирование = 16

масштабирование = 4

масштабирование = 1

Mathematica, с контролем гранулярности

При этом используются фотографии размером 48 x 48 пикселей. По умолчанию он заменяет эти пиксели на соответствующий квадрат размером 48x48 пикселей с аппроксимируемого изображения.

Тем не менее, размер квадратов назначения может быть меньше 48 x 48, что позволяет повысить точность детализации. (см. примеры ниже).

Предварительная обработка палитры

collage это изображение, содержащее фотографии, которые служат палитрой.

picsColorsсписок отдельных фотографий в сочетании с их средним красным, средним зеленым и синим значениями.

targetColorToPhoto [] `берет средний цвет целевой полосы и находит фотографию из палитры, которая лучше всего ему соответствует.

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

пример

Давайте найдем фотографию, которая лучше всего соответствует RGBColor [0.640, 0.134, 0.249]:

фотомозаику

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 использует исходную картинку, из которой мы сделаем фото-мозаику.

targetPic удалит четвертый параметр (PNG и некоторые JPG), оставив только R, G, B.

dims размеры targetPic .

tiles маленькие квадраты, которые вместе составляют целевую картинку.

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

tileReplacements фотографии, которые соответствуют каждой плитке, в правильном порядке.

gallery является набором замены плиток (фотографий) с правильной размерностью (то есть количеством строк и столбцов, которые соответствуют плиткам).

ImageAssembly объединяет мозаику в непрерывное изображение на выходе.

Примеры

Это заменяет каждый квадрат 12x12 на изображении в воскресенье соответствующей фотографией 48 x 48 пикселей, которая лучше всего соответствует среднему цвету.

photoMosaic[sunday, 12]

Воскресенье (подробно)

photoMosaic[lightbulb, 6]

photoMosaic[stevejobs, 24]

Деталь, стевджобс.

photoMosaic[kiss, 24]

Деталь поцелуя:

photoMosaic[spheres, 24]

JS

То же, что и в предыдущем гольфе: http://jsfiddle.net/eithe/J7jEk/ : D

(на этот раз вызывается с помощью unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}) (не обрабатывайте палитру, чтобы использовать один пиксель один раз, пиксели палитры - образцы 48x48, пиксели формы - образцы 48x48).

В настоящее время он просматривает список аватаров, чтобы найти ближайшее совпадение по массе выбранного алгоритма, однако он не выполняет сопоставления однородности цвета (на что мне нужно взглянуть.

К сожалению, я не могу поиграть с большими изображениями, потому что у меня заканчивается ОЗУ: D Если возможно, я буду признателен за меньшие выходные изображения. Если используется 1/2 размера изображения, вот воскресенье днем:

GLSL

Разница между этим вызовом и вызовом американской готики в палитре Моны Лизы: переставьте пиксели меня заинтересовали, потому что мозаичные плитки можно использовать повторно, а пиксели - нет. Это означает, что можно легко распараллелить алгоритм, поэтому я решил попробовать массивно параллельную версию. Под «массовым использованием» я подразумеваю использование 1344 шейдерных ядер на GTX670 моего рабочего стола одновременно, через GLSL.

метод

Фактическое сопоставление мозаики простое: я вычисляю расстояние RGB между каждым пикселем в целевой области и мозаичной плиткой и выбираю плитку с наименьшей разницей (взвешенной по значениям яркости). Индекс плитки записывается в атрибутах фрагмента красного и зеленого цвета, а затем после того, как все фрагменты были отрисованы, я считываю значения обратно из кадрового буфера и формирую выходное изображение из этих индексов. Реальная реализация довольно взломана; вместо создания FBO я просто открыл окно и отрисовал его, но GLFW не может открывать окна при сколь угодно малых разрешениях, поэтому я создаю окно больше, чем требуется, а затем рисую маленький прямоугольник, который имеет правильный размер, чтобы он имел один фрагмент на плитку, которая отображается на исходное изображение. Полное решение MSVC2013 доступно по адресуhttps://bitbucket.org/Gibgezr/mosaicmaker Для компиляции требуется GLFW / FreeImage / GLEW / GLM и для запуска OpenGL 3.3 или более поздние драйверы / видеокарта.

Источник шейдера фрагмента

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

Полученные результаты

Изображения отображаются почти мгновенно, поэтому распараллеливание прошло успешно. Недостатком является то, что я не могу заставить отдельные фрагменты полагаться на выходные данные любых других фрагментов, поэтому нет никакого способа получить существенное повышение качества, которое вы можете получить, не выбирая одну и ту же плитку дважды в пределах определенного диапазона. Итак, быстрые результаты, но ограниченное качество из-за массовых повторений плиток. В общем, было весело. http://imgur.com/a/M0Db0 для полноразмерных версий.

питон

Здесь идет речь о первом решении Python, используя средний подход. Мы можем развиваться отсюда. Остальные изображения здесь .

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

Еще одно решение Python - на основе среднего (RGB против L a b *)

Результаты (есть небольшие отличия)

Лампа - RGB

полный обзор

Лампа - Лаборатория

полный обзор

Стив - RGB

полный обзор

Стив - Лаб

полный обзор

Сферы - RGB

полный обзор

Сферы - Лаборатория

полный обзор

Воскресенье - RGB

полный обзор

Воскресенье - лаборатория

полный обзор

Поцелуй - RGB

полный обзор

Kiss - Lab

полный обзор

Код

требует python-colormath для лаборатории

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