Bottle cap art via clustering and optimal color assignments

We present a new methodology for the problem of approximating an input image with a given set of plastic bottle caps. The first step of our method adaptively discretizes the image into a grid where the caps are going to be placed. The next step reduces the number of colors in this discrete image using K-means color clustering. The last step calculates color assignments performing a minimization that aims to approximate colors and color differences between clustered regions while respecting the given cap colors and quantities. A collection of results showcases the potential of our method to tackle this very constrained problem at a much lower cost than the current state of the art.