Create mosaic from photograph

I am building a tool in VB.Net to generate a photograph mosaic. The main image is 7000px X 7000px.

The individual tile sizes are 30px X 30px

I need help with the following:

1) The mosaic generation code should check for each tile color and decide the best place to put it on the main image. Presently, my code is just randomly placing images on the main picture

2) It should suitable shade the tile to match the back color of the spot it is placed on - my code is doing that but not very well

3) It should generate a TRUE mosaic. Not an overlay of the main image with transparent looking tiles on top - there should be no 'ghost' image peeping out from the tiles

Please help in showing me third party tools that can achieve this or help me with the code. The project is in VB.Net
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

some questions:
The individual tile sizes are 30px X 30px
7000 is not a multiple of 30. you may use 6990 or 7020 pixels instead or define the tiles 35x35.

The mosaic generation code should check for each tile color

Open in new window

can you make a sample - say with 3x3 tiles and a picture of 90x90?

it is unclear where the tiles come from and which color out of 900 pixels is the one you want? are the tiles unicolored?

 ... and decide the best place to put it on the main image

Open in new window

can you tell which criteria should be used for that. the picture may have 900 different colors for a spot (worst case) or may be black-and-white (another extreme case).

It should suitable shade the tile to match the back color of the spot it is placed on

Open in new window

can you define what you mean with that?

RTKHOTAuthor Commented:
Thanks for your interest. Here are some replies:

1) I approximated it. But 6990 x 6990 is fine using 30 x 30 tiles

2) The main image will be a photograph that contains head and neck. it will be on a dark background

3) the tiles will also be photographs of people. The will be of multiple colors, shades and backgrounds. they may be indoor, outdoor, full photo, just face... anything. They will be a complete mixture of photos of people

4) Ideally, a light tile should be placed on a light area of the photo. IT should be an approximate placement. Similarly, a dark tile on a dark area of the photo. A tile that has more red should be around a red area of the photo. This is an ideal situation. I realise it may not be possible.

5) When a tile is being placed on the main image, and suppose tile is grey and it is being placed on a red area of main image. Then the tile should become slightly red so it gets properly camouflaged. The tiles should get a hue that matches where they are being placed.

Hope this answers everything! :)
thanks. yes, i now have a good idea what you want to do.

two more questions:

- how many tile photos are available?
  i assume they are more than 230x230, or do you want to use some of them a multiple?

- you told it is project. are you interested in c++ code nevertheless? or are you interested in algorithms only?

generally, you would define a measure for all tiles (mosaic or background). for example the measure could compute a 3d-point in a 10x10x10 grid where the dimensions are brightness index (from light to dark), color index (white to black), and diversity (count of neighbored pixels which have same color index) of all 900 pixels of a tile (for example the measure { 2, 5, 9 } could mean light-grey-homogeny, while { 8, 0, 1} is a mostly white picture with many scattered colored pixels on it). you may define a simple distance function between two points by calculating the Euclidean distance. the measure allows to  find a suitable tile for a given background very quickly by using dictionaries. for the shading you would use smaller tiles - say 3x3 - which you compare with the background. then "correct" the colors of the overlay by an appropriate algorithm (for example by calculating the difference between two colors for all 9 pixels of a mini tile and use the standard deviation to correct all colors into same direction; two neighbored mini tiles should not be corrected into different directions).  

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

RTKHOTAuthor Commented:
we will have a very large collection of tiles. but its ok if some repeat. we will have approx 1000 tiles.

code would help. vb or C is ok. if not, then algorithm would be second choice.

ok. first the algorithm. if it is ok, I can help with code as well.    

to be able to compare rgb colors, you would divide the rgb space by 4 for each color, thus getting 64 "color cubes" from 000 to 333 (base 4 numbers, or 0 to 63 decimal). for example the cube where red is in [192, 255] range and green in [128,191] range and blue in [0, 63] range could be named "dark yellow" for all its points. the reference for each cube color is the middle point of each cube, for the example it is rgb(223, 95, 31). put all cubes into an array of 64 elements.

then, define an array of colors (color groups) where each cube can be assigned to, for example { black, dark, red, green, blue, grey, yellow, orange, beige, brown, olive, pink, violet, cyan, lite, white }.  

for each of the 64 cubes you would determine the key (for example 0 to 63), optionally a name (for example "dark yellow", "lite blue green", ...), the color group index and the reference point and put all that into a structure (class). for each color group, you would make a list of all color cubes which belong to the group.  

for each color group, you would determine the "neighbored" color groups, for example red is neighbored to { orange, pink }. you would do that on a visual resemblance rather than based on rgb values.

for each of your tiles and each of the 900 pixels of a tile you determine the cube(s) where it belongs to. count the pixels for each for color cube and for each color group. sort both the counter lists and eliminate counts less than 30 for the cube counts and less than 90 for the color counts. for cube count list determine the cube with maximum pixels. triple the number and add all counts of cubes neighbored to the maximum cube. if the total is more than 600 points, you would add the tile index plus total points to a list associated to the cube. repeat the computation for the second maximum cube, until the total pixels in the cube is less than 45 (or any other threshold you want to define) or points are less than 450.

for the color count list you would do similar. start with the color that has the majority of colors assigned and where the initial count is greater 90.  triple the count and add counts of colors which are neighbored to the majority color. if total points greater 600 you would add the tile index plus points to a list associated to the color group. repeat that for next maximum while total points are greater than the half of the maximum points.

for example if you have (dark:50, brown:80, beige:120, orange:150, pink:150, red:350) you would add the tile to list of red with 1350 points (3*350 +150+150) and to orange with 880 points  (3*150 + 350 + 80) and pink with 850 points (2*150 + 350)  but not to brown which has only 560 points which is less than the half of the red points.

as a pair of tile index and points is added to the lists, we would be able to sort the lists by points and use the tile with the maximum points if there are multiple choices. all tiles which could not associated to a cube were added to one of four lists of "scattered" tiles. for that you would compute  average + standard deviation of the sum of the rgb values for each pixel. use both values to determine whether a tile belongs to dark-thinly-dispersed, dark-highly-dispersed, lite-highly-dispersed or lite-thinly-dispersed.

to determine which tile to use for a given spot of the picture compute the cubes and colors for each spot same way as you did it for the tiles. check the lists of tiles whether there are exact matches. if there are multiple matches use a random algorithm to make a choice where the probability for matches with higher points should give an advantage. increment a counter for each tile used for mosaic  such that you could prevent the same tile to be used too often. if no tiles would fit or tiles were used too much use the "scattered" lists.

RTKHOTAuthor Commented:
thanks for the above. if you have code, please send that as well
I am a c++ programmer and the collections mentioned in the algorithm would be standard collections (arrays, lists, sets, maps or dictionaries).

are you familiar with c++ collections and standard libraries?

if not, I would prefer to use pseudo code which easily could be elaborated to VB or C# code.

I could not give full working code as it would be too much work. I can make a design and help with code, though.

RTKHOTAuthor Commented:
Either would be fine. Whatever is convenient to you and requires least of your effort.

Thank you kindly and appreciate it much.
to be able to compare rgb colors, you would divide the rgb space by 4 for each color, thus getting 64 "color cubes" from 000 to 333
#include <string>
#include <vector>
#include <algorithm>

typedef unsigned long COLORREF;

#ifndef RGB
#define RGB(r,g,b)          ((COLORREF)(((BYTE)(r)|((WORD)((BYTE)(g))<<8))|(((DWORD)(BYTE)(b))<<16)))

// names for color cubes
// the reference color is in the middle of each cube, [123] -> red 31, green 95, blue 159
enum EColorCube {
      black_000               = 0,
      dark_blue_001,      // = 1
      blue_002,                // = 2
      lite_blue_003,         // = 3
      dark_green_010,    // = 4
      dark_cyan_011,      // = 5
      sea_blue_012,        // = 6
      //...                                             // please add a name for each color cube
      lite_cyan_233,         // = 62
      white_333,              // = 63
      MAX_CUBE             //  = 64

// used for readability 
const char * szCubeColors[MAX_CUBE] = { "black", "dark blue", "blue", "lite blue", /*..., */ "lite cyan", "white" }; 

Open in new window

define an array of colors (color groups) where each cube can be assigned to

// colors from 0 (black) to 15 (white)
enum EColorGroup
     { empty = 0, black, dark, red, green, blue, grey, yellow, orange, 
       beige, brown, olive, pink, violet, cyan, lite, white, MAX_COLOR};

const char * szColors[MAX_COLOR] = 
     "", "black", "dark", "red", "green", "blue", "grey", "yellow", "orange", 
          "beige", "brown", "olive", "pink", "violet", "cyan", "lite", "white", 

const int MAX_NEIGHBOR = 5;

const int colorNeighbors[MAX_COLOR][1 + MAX_NEIGHBOR] =
     {  black, dark, },                     // black
     {  dark,  black, brown }, 
     {  red,    orange, pink },
      //...                                         // please add neighbor relations for all colors

struct ColorCube
      int index;
      const char * szcolor;
      COLORREF refColor;
      int color;

const ColorCube cubeDefs[MAX_CUBE] = 
      { black_000,               szCubeColors[black_000],          RGB(31, 31, 31),         black, },
      { dark_blue_001,           szCubeColors[dark_blue_001],      RGB(31, 31, 95),         dark,  },
      { white_333,               szCubeColors[white_333],          RGB(223, 223, 223),      white, },

Open in new window

for each color group, you would make a list of all color cubes which belong to the group.

class ColorGroup
     int              index;
     std::string      color;
     std::vector<int> neighbors;
     std::vector<int> cubes;
     ColorGroup(int idx) 
            , neighbors(&colorNeighbors[idx][1], &colorNeighbors[idx][MAX_NEIGHBOR+1])
            std::vector<int>::iterator last = std::find(neighbors.begin(), neighbors.end(), 0); 
            if (last != neighbors.end()) neighbors.resize(last-neighbors.begin());
            // list of assigned cubes
            for (int n = 0; n < MAX_CUBE; ++n)
                  if (cubeDefs[n].color == idx)

class ColorGroups
       std::vector<ColorGroup> colors;
             for (int c = black; c <= white; ++c)

Open in new window

the above compiles in vc++ (unmanaged c++).

you may add the missing definitions and/or port the above to your preferred language.

to be continued ...


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Visual Basic.NET

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.