Photographic Mosaics
COSC450 Assignment 1
Due: 3rd September 2014, 5pm
This assignment is worth 20% of your final grade.
1
Overview
Photographic mosaics (also called Photomosaics, but that term is a trademark)
is the process of making a large image out of small tiles which are themselves
other images. An original image is divided into small square or rectangular
regions, and then each region is replaced by another image, which is scaled
down in size and chosen to best represent the original patch. As an example,
Figure 1 shows an original image of Barack Obama and three mosaics. Each
mosaic replaces square regions of the original image with another face. These
face images are taken from a collection called ‘labeled faces in the wild’, which
is available for you to use in your experiments. The three mosaic images differ
in how many images are used to create the mosaic effect.
Figure 1: An image of Barack Obama in front of a portrait of Abraham Lincoln
(left) made using a mosaic of (from left to right) 672 32 × 32 patches, 2,688
16 × 16 patches, and 10,752 8 × 8 patches. Each patch is itself an image of a
face.
The process of creating a photographic mosaic is, in principle, quite simple
and is described in Algorithm 1. The key to making a good mosaic is choosing
a good function to describe an image or a patch as a vector of numbers. An
1
average value of the pixels in a patch can give good results, and in colour images
this average is a vector of values (red, green, and blue), rather than a simple
scalar value.
Data: An input image, I, of size w × h; a tile size, s; and a set of n patch
images, P = {P1 , P2 , . . . , Pn }
Result: A version of I where each s × s tile is a copy of some Pi
x ← 1;
y ← 1;
for x ← 1, s, 2s, . . . , w − s do
for y ← 1, s, 2s, . . . , h − s do
d = describe(I(x . . . x + s, y . . . y + s));
i = min ||d − describe(Pi )||;
Pi ∈P
I(x . . . x + s, y . . . y + s) ← resize(Pi , s × s);
end
end
Algorithm 1: Basic photographic mosaic algorithm
For large collections of patch images, there are also issues of computational
efficiency. Computing the descriptor for every patch inside the nested loops is
wasteful – it is much better to compute each patch’s descriptor once, and to
store these values for future reference, as shown in Algorithm 2. Further issues
arise when searching for the best descriptor to match a given tile. Searching the
full list of patch descriptors takes O(n) time, which can be quite time consuming
for large n. Faster results can be obtained by using tree-based index structures,
meaning that each search takes O(log n) time.
Data: An input image, I, of size w × h; a tile size, s; and a set of n patch
images, P = {P1 , P2 , . . . , Pn }
Result: A version of I where each s × s tile is a copy of some Pi
x ← 1;
y ← 1;
for i ← 1 . . . n do
di = describe(Pi );
end
for x ← 1, s, 2s, . . . , w − s do
for y ← 1, s, 2s, . . . , h − s do
d = describe(I(x . . . x + s, y . . . y + s));
i = min ||d − di ||;
i∈{1...n}
I(x . . . x + s, y . . . y + s) ← resize(Pi , s × s);
end
end
Algorithm 2: Photographic mosaic algorithm with pre-computed descriptors
2
Other refinements to the algorithm can improve the appearance of the final
mosaic. Areas of uniform colour tend to lead to repeated use of the same patch
image, which creates a very regular appearance. In these situations, randomly
selecting from a few good matches often looks better than always using the best
match. Descriptors that capture more information about the structure within
a patch can also help improve the appearance of the final mosaic. For example,
the three patches shown in Figure 2 all have the same average colour, but look
very different. Descriptors which compute information about sub-patches (such
as the average colour in each quadrant of the tile), or which use information
about the variance as well as the average colour, can help in these cases.
Figure 2: These three patches all have the same average colour, but look quite
different.
2
Assignment Requirements
For this assignment you need to write a program which creates photographic
mosaics using a choice of at least two descriptor functions, and write a report
on the results. Your program should also include some randomisation to reduce
the effects of repeated patches in uniform areas of the image.
Your program should take as input (on the command line) at least the following options:
• The original input image to be made into a mosaic
• A text file listing (one to a line) the images to use as patches
• The size (in pixels) of the patches
• A parameter indicating what method to use to describe the images
• The filename of the image to be written as output
For example, your program might be run using the average red-green-blue values
like this:
mosaic input.png listOfImages.txt 16 averageRGB output.png
If your program has other parameters that can be adjusted then these should
be included as command line parameters.
Your report should include:
3
• Clear directions for building and running your program, including any
command line parameters that are required.
• A discussion of the descriptors you have chosen to implement, including
the reasons why you chose them.
• A comparison of the results of the different methods, including a discussion
of the effects of parameters (such as patch size) on the results. You should
compare the visual quality of the results as well as the computational
requirements (time, memory use) of your methods.
3
Extensions
Up to 80% of the marks for this assignment can be achieved by completing the
basic requirements above. The remaining 20% come from some extension to the
basic mosaicing program. Possible extensions include:
• Using an efficient index structure to speed up the process of selecting the
best image for each patch.
• Implementing an adaptive division of the image into tiles. For example,
if an image is found that represents a 32 × 32 patch well, it might be
accepted, but if no good image is found, that patch might be divided into
four 16 × 16 patches and so on.
• Ensuring that no adjacent tiles (or, more generally, no tiles within some
fixed distance of each other) use the same image. Note that a random
element in the selection process doesn’t necessarily guarantee this.
4
Skeleton Code
Skeleton code for this assignment is provided in ∼steven/Public/COSC450/
PhotographiMosaic/skeleton.zip. This code uses the OpenCV library, which
will be discussed in the lectures. The code provides an abstract base class,
PatchDatabase, which provides a template for methods to select images for
each patch. Classes derived from PatchDatabase must implement the methods
add and find. The add method puts a potential patch into the database, and
the find method returns an appropriate patch given a target image.
Animplementation of PatchDatabase is given, called RandomPatchDatabase.
In this implementation, the add method simply puts the patches into a vector,
and the find method selects a random element from that vector. A more intelligent implementation would compute a descriptor for each patch, and store
this as well as the patch itself when add is called. The find method would
then compute the descriptor for the target image, and then find a patch with a
similar descriptor.
The skeleton code also contains two sample files listing patch images. These
are lfw.txt and lfw100.txt, and use faces from the Labeled Faces in the Wild
4
dataset (http://vis-www.cs.umass.edu/lfw/). There are about 5700 people
in the dataset, and lfw.txt uses one image of each. Since this is a fairly large
dataset to load when testing, lfw100.txt lists just the first 100 people.
5
Deliverables
You should send a report (PDF format preferred) and your source code (C++
code and headers, Makefile, etc.) to [email protected]. You should include
everything that is needed to build and run your program, apart from the libraries that are provided. You may find it convenient to archive your files as
a .tar or .zip, but be aware that archives sent from outside of the department
often get caught in the University’s spam filters. This can be easily circumvented by renaming your files to remove the archive extension. If your code is
zipped up as mycode.zip, just rename it to mycode.txt or something (but not
mycode.exe!) and tell me in the body of your email what you’ve done. I will
reply to acknowledge receipt of your assignment in any case.
The marks for this assignment will be allocated as follows:
• 30% of the marks from your code
• 50% of the marks from the report
• 20% of the marks for extension (code + report)
Clarity and correctness are the main concerns with your code, and comments,
layout, variable names, etc. contribute to that. While efficient methods are
preferred, you should worry primarily about making sure that your code does
what it should, and that this is clear to someone else reading your code. The
complexity and appropriateness of the techniques that you have implemented
will also be a factor.
Your report will be marked based on clarity of expression, and how well it
fulfils the requirements listed above. I will be looking to see how you tested
your code, and how convincing any experiments and results you give are. It is
expected that reports should be about 4-5 pages long, although large numbers
of pictures could extend this. Any extensions you have made should also be
discussed
Late assignment submissions will be penalised at the rate of 10% per working day. Extensions to the deadline may be granted where appropriate, and will
require evidence of work done to date. The usual university regulations relating to plagiarism (http://www.otago.ac.nz/study/plagiarism/index.html)
apply, and any work you submit for assessment must be your own.
5
© Copyright 2024 ExpyDoc
