BubbleMe was our first android application, we encounter many difficulties during it’s development.
Most of them related to memory leaks, image processing and the garbage collector. To find those memory leaks we had to use the Eclipse Memory Analizer and had to understand the inner of memory management in Android. This google IO conference was indispensable to achieve this goal. It may seem long (1 hour), but is worth it.
Image processing in android isn’t a pain in itself, but handling the images in a limited memory is. If you are careless you will crash your app.
The algorithm
In Bubble Me we have one goal: simulate the effect of being nude through a pattern made of circles that only let us see the naked parts of a person. Here we have an example with Olivia Wilde:
Studying the effect on internet images we set some objectives to our algorithm:
- Hide all the clothes.
- The face must appear in the picture.
- The circles will never intersect; it will break the pattern.
- Maximize the area of the circles and it’s own size.
First approximation
The only points we had clear when we started were points 1 and 2. The other we will discover through time and many tries.
We need the user to provide where are the clothes. So we ask him to paint over.
We also need to know where are the faces so, again, we ask the user for that information. We tried to use facial recognition, but not always work.
Once we have this information we throw a big number of random points and check if it’s painted or not. If it isn’t painted we create a circle as big as possible in that location.
Later we arrange the obtained circles by size, and add the circles to the image being carefully that they don’t intersect.
Looking backwards it seem a little crazy and a waste of resources, but we need a start point.
Quadtree approximation
Quadtree analysis of a line
After some improvements on the previous algorithm we decided to try another approach. We decided to use QuadTrees.
Quadtrees are often use in 2D collisions (or 3D collisions if we are talking about 3D collisions), and are known for their great performance. So we supposed that would improve the generation time of the pattern. Also we discovered that the quadtree provided us very useful information to our purposes. The bigger areas were where we should place our circles.
To increase even more the cover area we slightly (and iteratively) moved the circles to maximize the occupied space.
The performance improvement was great, and we decided to stick to this algorithm.
Other algorithm: Delaunay triangulation and Voronoi cells
Delaunay and Voronoi
Beside of using quadtrees for the algorithm we think there are event faster ways of creating the pattern. Using Delanuay and Voronoi (they are correlated).
Finding the Delaunay triangulation it’s even faster than calculate the quadtree for the image. And the points of the triangulation would be the center of our circles in the pattern.
There are several implementations in the net of this algorithms, so that wouldn’t be a problem. Maybe the hardest part would be to represent the clothes as unwanted zones, and for that we keep the quadtree implementation.
Sloth Developers 