A tiled picture (or PhotoMosaic® as originally created by Robert Silvers) is a collection of small pictures organized in a way to create a larger picture. It's like a puzzle except your not actually using the original picture to create the pieces. Instead, your attempting to use other pictures to reconstruct a picture which resembles the original picture.
If you tried to build a tiled picture manually, you might begin by organizing each of the smaller pictures into different color groups. Next, you might break the original picture into pieces which are the same size as the smaller pictures. Finally, you would take each piece from the original picture and try to match it up with one of the smaller pictures. Since, you organized the smaller pictures into color groups, you can work faster because each piece from the original picture can also be mapped to a color group. You just need to pick a picture from the color group to replace the piece from the original picture.
Now, if a piece from the original has several colors in it (maybe there is an edge between two objects), you might attempt to find a smaller picture which has a similar color difference. This way the smaller pictures will better represent the orginal picture and reduce some of the pixelization which will occur when just replacing blocks with solid color. However, if there are not enough pictures to choose from, you may not have alot of choice about which picture to insert in a given location. Having a good pool of pictures is key to making a good mosaic. This needs to be balanced, of course, since too many will make searching for a picture take a long time.
Ok, so that's the basic approach - now how do you make a computer do it? First, we need to build a palette of colors to which we will map each image and piece of the original picture. Our palette will consist of 512 colors generated by rotating through the RGB color space in steps of 36. This will give us a fairly good gradiant of colors to work with.
// Generate palette. Index
// RGB values which will be used
// to match pictures
for ($x=0;$x<=7;$x++)
{
for ($y=0;$y<=7;$y++)
{
for ($z=0;$z<=7;$z++)
{
$r = $x * 36;
$g = $y * 36;
$b = $z * 36;
$_PALETTE[64 * $x + 8 * $y + $z] = array("color" => array("r" => $r, "g" => $g, "b" => $b),
"images" => array(),
"pieces" => array());
}
}
}
Next, we need to categorize all of the replacement images and pieces from the original picture. The picture will be broken down into 30x30 pixel squares. The replacement pictures are the same size so they can be swapped into the picture to create the mosaic. This is done by calculating the average color of an image and then finding the closest color in our palette.
function find_image_averages($img, $sz_x, $sz_y, $sz_w, $sz_h)
{
// Randomly sample 10% of the pixels to calculate
// an average color for the whole picture and
// each of the quadrants.
$mid_x = (int) ($sz_w / 2);
$mid_y = (int) ($sz_h / 2);
$cur_loc = 0;
$tcnt = 0;
$q1cnt = 0;
$q2cnt = 0;
$q3cnt = 0;
$q4cnt = 0;
$avg = array("t_avg_color" => array("r" => 0, "g" => 0, "b" => 0),
"q1_avg_color" => array("r" => 0, "g" => 0, "b" => 0),
"q2_avg_color" => array("r" => 0, "g" => 0, "b" => 0),
"q3_avg_color" => array("r" => 0, "g" => 0, "b" => 0),
"q4_avg_color" => array("r" => 0, "g" => 0, "b" => 0));
while ($cur_loc < $sz_w * $sz_h)
{
$cur_loc += rand(5, 15);
$cur_x = $cur_loc % $sz_h;
$cur_y = ceil($cur_loc / $sz_w);
$tcnt++;
$rgb = imagecolorat($img, $sz_x + $cur_x, $sz_y + $cur_y);
$r = ($rgb >> 16) & 0xFF;
$g = ($rgb >> 8) & 0xFF;
$b = $rgb & 0xFF;
$avg["t_avg_color"]["r"] += $r;
$avg["t_avg_color"]["g"] += $g;
$avg["t_avg_color"]["b"] += $b;
if ($cur_x <= $mid_x && $cur_y <= $mid_y)
{
$avg["q1_avg_color"]["r"] += $r;
$avg["q1_avg_color"]["g"] += $g;
$avg["q1_avg_color"]["b"] += $b;
$q1cnt++;
}
else if ($cur_x > $mid_x && $cur_y <= $mid_y)
{
$avg["q2_avg_color"]["r"] += $r;
$avg["q2_avg_color"]["g"] += $g;
$avg["q2_avg_color"]["b"] += $b;
$q2cnt++;
}
else if ($cur_x > $mid_x && $cur_y > $mid_y)
{
$avg["q3_avg_color"]["r"] += $r;
$avg["q3_avg_color"]["g"] += $g;
$avg["q3_avg_color"]["b"] += $b;
$q3cnt++;
}
else if ($cur_x <= $mid_x && $cur_y > $mid_y)
{
$avg["q4_avg_color"]["r"] += $r;
$avg["q4_avg_color"]["g"] += $g;
$avg["q4_avg_color"]["b"] += $b;
$q4cnt++;
}
}
$avg["t_avg_color"]["r"] = (int) ($avg["t_avg_color"]["r"] / $tcnt);
$avg["t_avg_color"]["g"] = (int) ($avg["t_avg_color"]["g"] / $tcnt);
$avg["t_avg_color"]["b"] = (int) ($avg["t_avg_color"]["b"] / $tcnt);
$avg["q1_avg_color"]["r"] = (int) ($avg["q1_avg_color"]["r"] / $q1cnt);
$avg["q1_avg_color"]["g"] = (int) ($avg["q1_avg_color"]["g"] / $q1cnt);
$avg["q1_avg_color"]["b"] = (int) ($avg["q1_avg_color"]["b"] / $q1cnt);
$avg["q2_avg_color"]["r"] = (int) ($avg["q2_avg_color"]["r"] / $q2cnt);
$avg["q2_avg_color"]["g"] = (int) ($avg["q2_avg_color"]["g"] / $q2cnt);
$avg["q2_avg_color"]["b"] = (int) ($avg["q2_avg_color"]["b"] / $q2cnt);
$avg["q3_avg_color"]["r"] = (int) ($avg["q3_avg_color"]["r"] / $q3cnt);
$avg["q3_avg_color"]["g"] = (int) ($avg["q3_avg_color"]["g"] / $q3cnt);
$avg["q3_avg_color"]["b"] = (int) ($avg["q3_avg_color"]["b"] / $q3cnt);
$avg["q4_avg_color"]["r"] = (int) ($avg["q4_avg_color"]["r"] / $q4cnt);
$avg["q4_avg_color"]["g"] = (int) ($avg["q4_avg_color"]["g"] / $q4cnt);
$avg["q4_avg_color"]["b"] = (int) ($avg["q4_avg_color"]["b"] / $q4cnt);
return $avg;
}
function findclosestcolor($rgb, $tbl)
{
$cur = 0;
$prv = 99999999;
$fnd = 0;
$idx = 0;
$r1 = $rgb["r"];
$g1 = $rgb["g"];
$b1 = $rgb["b"];
// $tbl is the palette of colors
while ($idx <= count($tbl))
{
$r2 = $tbl[$idx]["color"]["r"];
$g2 = $tbl[$idx]["color"]["g"];
$b2 = $tbl[$idx]["color"]["b"];
$dr = $r1 - $r2;
$dg = $g1 - $g2;
$db = $b1 - $b2;
$rb = ($r1 + $r2) / 2;
// Calculate the distance between the two colors
// the weights adjust how the eye perceives of the
// different colors.
$cur = 0.5 * ($dr * $dr) + ($dg * $dg) + 0.25 * ($db * $db);
if ($cur < $prv)
{
$fnd = $idx;
$prv = $cur;
}
$idx++;
}
return $fnd;
}
You might wonder why we calculate five different averages. As outlined in the manual process, we want to attempt to accomidate variations in color in an image. There is one average for each quadrant of the image such that if there is a major difference in color, we can attempt to find the best match. Also, we don't really need to average each pixel in the image. Instead, we'll randomly sample about 10% of the pixels in the image to calcluate the averages. Finding the closest color is a simple task of minimizing the distance between the average color of an image to a color in the palette.
Now that we have everything categorized, we can start to build our mosaic. Since we've already organized all our pieces, we just loop through all of them and pick one of the images in the same color category to replace it. However, we have several things we need to deal with in order for the resulting mosaic to look good.
First, we have to deal with situations when there is not an image in the color category the current piece is in. We can handle this by looking at the nearest color categories to the one the piece is in and use an image from that category. The further we have to look, the more the color will differ from the original piece.
Second, we don't want to select the same replacement image over and over again - especially in the same location in the picture. So as we build the mosaic, we must try to maximize the distance between the same image by using different images from the same color category. Sometimes this is not always possible since a color category may only have a few images and that color occurs frequently in the picture.
Third, we want to attempt to find a best fitting image when a piece has a significant difference in color between one of the quadrant averages and the overall color average. So we must minimize the difference between all five average colors of the image and the piece being replaced. However, we need to balance this with maximizing the distance between the same piece. In areas where the color does not vary, the same image will probably fit the best. Other images would probably be fairly close too and we want to use these as well. Places where there is a large difference in color, there might be only one piece which fits the best. If that image was recently used, we don't want to skip it when it will best define the area being replaced. So how do we ensure we use the best piece when there is a large variance in color and still maximize the distance between the same image when there is little variation? The approach used in the mosaic algorithm is to reduce how much the distance between the same piece can affect the decision to use a given image by the amount of variation in the piece being replaced. So the more variation in color, the less the distance between the last use of the image will contribute to the decision to use it.
The following equation is used to calculate the "fitness factor" for an image. This needs to be minimized over all possible image choices: rt = tcd + qcdsum + pdist / (pqmax - pqmin) tcd = distance in color between overall average for the piece and image qcdsum = sum of the color distance between each quadrant of the piece and image pdist = distance between the current position in the picture and the last place the image was used pqmax = the maximum color distance between the overall image color average and each quadrant pqmin = the minimum color distance between the overall image color average and each quadrant
Each component of the equation can be multiplied by a constant to increase or decrease the importance of the component.
What are the results? Well, try it your self. Click here to upload a picture and create a mosaic. We've included several tools for showing you how the program decomposed the image and chose the replacement images.