Shape Collage creates a collage by taking a bunch of photos and moving them around on a page so that they form a shape. When arranging the photos, they should be spread apart as far as possible so that you can see each one. The photos should cover the entire shape.
This sounds easy, but it’s actually a lot harder than it sounds. Figuring out how to perfectly place the photos is an “NP-complete” problem, which is Computer Science lingo for “really, really hard”.
Shape Collage uses a very simple and fast machine learning algorithm to arrange the photos in the collage. It’s not perfect, but it does a pretty good job. The basic idea is to throw a bunch of photos on a page and then one at a time, move each photo away from the other photos, while still staying inside of the shape. Keep doing this until the photos are evenly spaced throughout the shape.
This algorithm is maximum likelihood learning using gradient descent. The function to optimize is based on the distance between each of the photos and optimizing this function maximizes the distance between the photos. The general procedure is as follows:
- Randomly place and rotate the photos inside the collage shape
- One at a time, move each photo away from the other photos by following the gradient, obtained by taking the derivative of the global function with respect to the other photos, making sure to stay inside of the shape when moving the photo
- Repeat until the photos have settled into a local optimum