Home
Matcha is a simple program for mosaic creation: given a folder of images and some target photo, it composes the final result using the available tiles. It can work with or without replacement of the used tiles, depending on whether the quantity of the tiles is limited.
"Matcha" is both a tea variety and the wrong spelling of the word "matcher". The name is inspired by the first usage of the software: I wanted to turn my collection of tea bags cases into something beautiful, so I coded it. The result was beyond any expections.
Before adventure yourself in extremely generic guide i wrote below, please mind that this is not a stable version, it's not a complete software or even a useful tool. This is something I made in two afternoons, for fun. It could become something better, if I'll ever have the time to improve it - which is a bit unlikely - or if you take my code and use it as a springboard.
Feel free to do it, I'd be happy to see the results.
It works bad (for now). But I was able to obtain some not-so-bad results, so here's a brief explanation of the idea.
- A tile is an image used to compose the final mosaic. In my first real-world application, each one of those tea bag cases I mentioned before was a tile.
- The target image is the photo we want to draw using the tiles. A good mosaic should resemble the target image as much as possible.
- A cell is a portion of the target image. It will be associated to (= graphically represented by) one of the tiles.
The algorithm takes each cell and each tile and extracts some relevant features from them. In the basic version, those features are the average colors of the images of the tiles and the cells. You can imagine the algorithm sampling those images in a NxM grid (default: 3x3).
This process turns every cell/tile into a vector of coordinates in some multi-dimensional space: we describe each image as a limited series of number that can easily be computed and used for some future operations.
Now it's just a game of who gets to the goal first. Each cell has become a point in the space, thus we can compute its distance from the tiles (which are also points now). The nearest tile would be the one that better represents the cell (for how we defined the features), then we simply assign to it the best tile and, having a tile for each cell, we obtain the final mosaic.
However, this solution works optimally in a virtual world, where the tiles are unlimited and we don't have to worry about the scarcity of raw materials. But in the majority of real world applications we could run out of tiles.
This means that - generally speaking - not every cell can be satisfied with its first choice. Imagine the case where two cells have the same nearest tile, but the available quantity of this tile is only 1. Which cell we serve first?
There are a lot of strategies that could help us decide; in order to maintain things easy, *Matcha uses a greedy strategy based on distances: the nearest tile wins.
In my implementation, every cell computes and stores the distance from every tile. The algorithm sorts the cells by their minimum distance, then it satisfies the requests in order. When a tile becomes unavailable is deleted from all the lists, then the queue of unsatisfied cells is sorted again.
As you can see, the whole process is pretty basic. I have in mind some other strategies, but for now this will work (even if it's pretty far from optimal...).
If you have any suggestion, I'd be glad to hear it!
[ Coming soon ]