Last Updated:   Nov / 30 / 2018 Fancy QR Codes via Genetic Algorithms© 2018 Aaron VoseDownload the current version with source code here: QRGA on GitHub Needing a project over the 2018 U.S. Thanksgiving holiday break, I thought it would be fun to see if I could tackle the problem of creating functionally valid QR codes (i.e., 2D bar-codes) which look to human observers to be easily recognizable as personal / company logos or even small works of art. Written in Python, I combine a simple "nonce" search first phase with a second genetic algorithm (GA) phase to search the space of images for a local optima: an image which decodes to the desired website while also looking like a target image. In the first search phase, a harmless random string (perhaps use of the term "nonce" -- think of Bitcoin -- isn't that much of a stretch here) is appended to the target URL / link encoded in the image. That is, a QR code linking to "aaronvose.net" looks just a bit different than one linking to "aaronvose.net?nonce=0x1337" while still directing the user the same site. The goal here is to modify the link encoded in the image in a "harmless" way which also happens to change the QR code image without impinging upon the redundant encoding used to provide resiliency to QR codes. That is, not a single pixel is "corrupted" and the encoded data is still just as valid, yet is encoded in a QR image which is different, and thus might be closer to the target image. It is this combined similarity of link yet difference of image which is exploited in the nonce search phase to find a data string, and thus a QR image, which is as near to the target image as possible. The QR code found in this phase is used as a starting point for the next phase, the GA. In the second phase, a genetic algorithm (GA) utilizing directed mutation starts from the QR code produced in the first phase, and evolves it over time to become more like the desired target image. In this second phase, a population of 100 different QR codes is randomly mutated between two points in multi-dimensional space: the starting valid QR-code as one point and the target image as another. Any population member which is unable to be decoded after mutation is killed. Then the surviving mutated population of QR codes is evaluated for similarity with the target image, and the 10 most fit individual QR codes are allowed to reproduce with crossover to repopulate for the next generation. This GA phase takes advantage of the error correcting code used by the QR format to maximize the similarity to the target (e.g., logo) image while also ensuring that the image is in fact a valid, decipherable QR code. The first and second stages work together in a synergistic way, as starting from as similar a QR code as possible (from the first phase) requires less pixels to be mutated / corrupted to achieve the same level of visual similarity. I hope to support color in the future; there are a lot of fun tricks one might play there! |