# 699 Project Idea: Photo Collage

Here are some notes to help you plan a project. Its just a bunch of
notes (not necessarily well organized)

### The Basic Idea

Given:
+ a set of pictures, each with an important region identified
+ a target rectangle (image size)

Find:
+ an image that places all of the pictures into the target rectangle
  such that they are as big as possible and all of the "important"
  areas are showing

The trick is to find a "good" collage. There are many different
possible definitions of good. You show try a bunch of different ones
(ideas below).

We sometimes call this the *salient collage problem* since the inner
rectangle often comes from a salience detector (something that tries
to decide what the important part of the image is).

### Variants of the problem

There are many different things that you might do in collages, and
many different methods of determining what layout is "best" - you
should try a bunch of different ones.

It would be nice to provide as many options as possible so the user
can adjust the results to their taste.

A Few Thoughts:

+ Having some degree of variety is good. Straight grids are generally
  boring. 

+ One obvious variant is to find the packing that fills as much of the
  collage with important regions as possible. That is, the packing
  that makes the images as big as possible without overlapping. Other
  variants might trade some of the "as big as possible" for other nice
  properties.

+ You may allow different images to be scaled by different
  amounts, or have them scaled the same. If things scale differently
  you may want to control how different the scalings are (so one
  images doesn't dominate) - or maybe you want that kind of variety.

+ You might rotate the images slightly - each by a different random
  amount - to give a more "random" look. (its amazing what a little
  bit does)

+ Other ways of adding randomness (such as shifting the images from
  side to side, mixing up the stacking order so different overlaps
  appear, ...) add interest.

+ Adding borders when you draw the pictures is a nicer add on
  sometimes (I particularly like adding the "old fashioned" scalloped
  picture borders to some of them.

+ You might want to enforce that there are no gaps (that the pictures
  always overlap), or you might want to minimize the gaps, or
  distribute them uniformly, or ...

### Some thoughts on the problem

+ Given some way to measure "best", the problem of laying out the
  collage optimally is a combinatorial optimization problem and is
  probably intractable. It is important to look into this though. Even
  if the exact "best" solution cannot be found, it is possible that
  there are good approximation methods.

+ It is equivalent to think of scaling the images or scaling the
  target size. However, it is important in both cases to preserve the
  aspect ratios. (the images will be distorted if you scale them
  non-uniformly, and the target's aspect ratio is important since the
  final image can always be scaled)

+ Some experimentation as to what looks good will probably be important.

+ We have tons of pictures around the lab if you don't have your
  own. Or you can find zillions on the web.


### Thoughts on how to proceed

+ You should start by just thinking of the pictures as rectangles
  (with a rectangle inside of them). You may want to test your code
  just using solid color rectangles. However, in the end, you will
  want to actually make collages using real pictures.

+ Don't worry about where the inner rectangles come from. Read the
  rectangles from a file. At some point, it might be nice to have a
  program that allowed the user to mark the rectangle, or to integrate
  with Feng's salience code.

+ I recommend picking one variant of the problem, getting it to work,
  and then diversifying.

+ One possible way to break up the team work is to have different
  people try to do different things. 

+ Pick a series of 1 week steps.

+ You might choose to do low-res previews using texture mapping (since
  you can scale and rotate images really fast using the hardware)

### Deliverables

+ You should deliver source code that we can actually use to make
  collages. This means using good image processing (especially for
  scaling and rotating).

+ Your documentation should discuss the different variants you
  considered.