(UPDATE 12/10/2015 I have enhanced the PolyMatch algorithm which resulted in more accurate matching. The images in this writeup have been updated to highlight the improvement.)
As a proof of concept to investigate the capabilities of AI-Based Genetic Algorithms on mobile processors, I developed the PolyMatch image processing filter. PolyMatch is an iOS app that attempts to recreate a camera or photo library image using only 10-200 semitransparent colored triangles. One or two hundred seems like a small number of triangle to reproduce complex images, but surprisingly realistic recreations can be made if the proper combination of triangles, colors, transparency, and geometry can be found. However, finding this combination is not an easy task for conventional knowledge-based search techniques (and near-impossible for humans!), hence I used genetic algorithms.
Genetic algorithms (GAs) are a search technique used to rapidly search a large solution space. Based on the concept of evolution, GAs rely on a “population” of possible solutions. Initially the population is random, and each member of the population tries to solve the problem at hand (in the case of PolyMatch, this would be image matching). Some members of the population will perform better than others. The better performers are saved, while the weaker performers are discarded. Then, the better performers are mixed and possibly mutated, creating a newer population (i.e. a new ‘generation’). The solve-evaluate-mix loop is repeated continuously, and each successful generation will become better at solving the problem. After a certain number of generations (50,000 to 200,000 generations in the case of PolyMatch) the best solution is selected and the algorithm ends.
Since 10,000,000’s of triangles & 100,000’s of images need to be evaluated as the PolyMatch algorithm runs, performance is critical. I employed the OpenGL ES library and hardware image pipeline to rapidly render and compare images against the target solution.
While this application is fun and toy-like, my insights into AI and rendering performance have influenced how I build mobile web applications.
Key skills I used for the project: Genetic Algorithm design and implementation, iOS application development, OpenGL ES graphics programming, performance research.
Additional examples follow: