Math, Art, and the World
——Watched “OPT Art by Dr. Robert Bosch”
Two years ago, when I first tried to apply Genetic Algorithm to find optimal feature sets for EEG data, I learnt about traveling salesman problem (TSP). I was fascinated by the “Mona Lisa’s Smile” which was created by applying TSP, although I didn’t understand the detailed method. The first time I noticed an image created by solving integer programming (IP) would probably be a year ago. In a corner of a store where I was shopping, I came across a framed picture, with a lot of sub figures splicing together. Since it was right by my foot, I scrutinized those small figures, and found that there were only five or six basic figures, such as portraits, scenery, and animals, repeatedly, creating the whole picture. Some of them were bright and some were dark, I cannot see what it tells, until I walked far away and looked back, I found that the small figures disappeared, and all I could see was a man’s portrait, with the varying colors decently sketching his outlines. I was very curious about how the artist know where to put those small figures, and I guessed that it must be some computer programs that automatically matched the figures with the original portrait.
Until now, after learning Optimization, I understand better the way that these pictures are created through mathematical representation. What makes me more excited and also illustrated by Dr. Bosch in the seminar is that pictures created using the idea of IP seems to be very diversified and beautiful. When using well designed basic patterns, picture can be made simple and in high quality, and the computational time dramatically decreases. This seems happen to indicate that no matter how complex the world is, how confusing the phenomenon is, the truth hiding behind are always supported by simple rules. Using basic and simple logic to present and simplify the complexity, and exhibits artistic beauty; that is the charm of math.
The seminar given by Dr. Bosch discussed how to use optimization methods to create picture portraits and sculptures. He described the detailed steps in creating a domino picture, and used a simple assignment model to demonstrate how integer programming (IP) works and how IP helps with domino arrangement. Then he extended the problem to how to present the same picture differently, instead of dominoes, using other patterns such as tile-based art, triangle shaped, and 3D cubic based art. Finally he showed pictures created by TSP, and mentioned related works done by other artists.
As explained in the lecture, to “dominize” a target picture, we first need to chop it into squares of pixels, and then replace each square with a single “megapixel”, represented with a number between 0 to 9, where 0 means darkest black and 9 means brightest white (consider the dominoes ‘9’ has the most white dots, and ‘0’ is all black). The most important and interesting part is using IP to determine the best possible arrangement of dominoes. We define binary variables to express whether each double ‘9’ domino is placed in orientation v/h with the top left square covering square (i,j). The constraints include that each domino must be used s times (depened on how many sets), and each square must be covered exactly once. After the IP is solved, we can find the arrangement for all dominoes. The created pictures, look abstract when staring up close, but make sense when keeping a certain distance. It reminds me of a famous Chinese poet, living in the sixth century, who made a poem saying that “We never know the real look of Lu Mountain, as we are living in it.” Sometimes we stuck at some point, it might help if we jump out and look back from a larger scale, we may find more surrounding information that putting together make a whole story. It is also very interesting that the more sets of basic patterns we use, the more accurate the created picture resembles the original one; suppose the created pictures are zoomed to the same size. In this case, resolution is higher, and each single pattern becomes less distinguishable. Result is: our eyes are so perfectly fooled that we may not even be able to tell that there are several little monkeys on Monroe’s nose. We lose the details while we are obtaining the details!
Domino portraits have been generated most often using integer programming that provides optimal solutions, but these can be slow and do not scale well to larger portraits. Lately, Cambazard et al proposed a new approach that overcomes these limitations and provides high quality portraits. They combined techniques from operations research, artificial intelligence, and computer vision. Starting from a randomly generated template of blank domino shapes, a subsequent optimal placement of dominoes can be achieved in constant time when the problem is viewed as a minimum cost flow. The domino portraits one obtains are good, but not as visually attractive as optimal ones. By combining techniques from computer vision and large neighborhood search, the portraits got quickly improved. They observed many orders of magnitude reduction in search time.
Another topic that Dr. Bosch also discussed is TSP art. We lay down points to present a grey scaled picture, and use TSP algorithm to connect the points, in a way that we treat the points as different cities that the salesman need to visit, each visiting once, and then return to where he started. The total traveling distance should be the shortest. In regions where cities are more packed together, more traveling occurs. Compared with using Nearest-Neighborhood method in solving the TSP which resulted in crossed lines in the route, Lin-Kernighan heuristic produces higher quality with a better planned route.
I tried to create a TSP picture using my grey scaled photo, but stuck at how to distribute the points. As suggested by Dr. Bosch, grid-based method requires many dots and may lead to dot clumping, while Dr. Kaplan from University of Waterloo first applied the Weighted Voronoi stippling which uses optimization to space out a collection of points evenly while still conveying image tone; fewer dots are needed, and the appearance of TSP tour comes out more organic. Another approach is Ordered Dithering, which selectively turns pixels on and off in fixed patterns. Both methods produce city distributions suitable for the TSP, but yield dramatically different final images.
Australian artist Paul Brown also works on computational art. He developed a tile-based image generation system. His “chromos” is an animated time-based work. One tile can morph into other version of tiles with time, and they together create more possible connections that can be used, as showed by Dr. Bosch in his own work, to create pictures. Some formations of the figure turned out to be simplified with higher computational speed. Some of his other computer generated drawings use individual elements that evolve or propagate in accordance with a set of simple rules.
Ken Knowlton, pioneer of Computer Assisted Art, is the first person who uses computer to create mosaic pictures with symbols and objects conceived of using sets of dominoes. In 1981, he filed for a US Patent entitled “Representation of Designs” in which he proposed the use of dominoes to render monochrome images. Instead of IP, he used in forming pictures greedy algorithm, which is following the problem solving metaheuristic of making the locally choice at each stage with the hope of finding global optimum. It turns out to be “short-sighted” as it usually does not operate on all the data set. It makes commitments to certain choices too early which prevent it from finding the best overall solution later. Robert Silver, who is among the numerous artists constructing photomosaics, described the negative consequences of using greedy algorithm when making mosaics from the top down as “The quality of matches is worse at the bottom of the mosaic than at the top because the best images are used up first.”
In fact, much of the early work focused on geometric forms and on structure, instead of content. This was partly due to the restrictive available output devices at that time. Some early artists deliberately avoided recognizable content in order to concentrate on pure visual form. As new tools emerging, and computer techniques developing, they considered the computer an autonomous machine that would enable them to carry out visual experiments in an objective manner. But in Ken Knowlton’s opinion, mixtures of brash novelty and serious message are dicey and perhaps impossible as the new means of expression lead to new results: “provocative, crude, delicate, personal, grand, arrogant, humble, megalomaniacal, predictive, retrospective, sensitive and tasteless. In a way, disarray in the arts mirrors our troubled world and its new methods of building and destroying. What happens to the world, of course, is a much more serious matter than what happens to the arts. But the narrower and wider views exhibit this curious similarity: disproportionate attention to tangential issues”.
Fascinated with paradox and impossible figures, M.C. Escher from Holland used an idea of Roger Penrose’s to develop many intriguing works of art that explore and exhibit a wide range of mathematical ideas. He often worked directly from structures in plane and projective geometry, and finally capturing the essence of non-Euclidean geometries. Geometry of space and logic of space are the two broad areas that Escher’s work encompasses. One of my favorites is “Möbius Strip II”, which I think simply illustrates the nature of space itself: the unity of oppositeness. Another category of his work is self-reference, which is found in the way our worlds of perception reflect and intersect one another. His “Three Spheres II” makes use of reflective properties of a spherical mirror, which reminds me of the interesting fact that when I look into your eyes, I can see myself smiling, with your smile in my eyes. As Hofstatder noted, “every part of the world seems to contain, and be contained in, every other part ...”
And so we end where we began, with some thinking about math, art and the world. The computer assisted art is the integration of science and art, the aesthetic unity of mathematics and art. The seemingly tedious math is no longer just the abstract philosophic theory, instead, it is tangible visual impact and conceptual feelings; it is artistic creations, and moreover, it reveals concrete existence. It allows various views of how the world came into being and how it runs.
References:
[1] Robert Bosch. Opt art. In J. Christopher Beck and Barbara M. Smith, editors, CPAIOR, volume 3990 of Lecture Notes in Computer Science, page 1. Springer, 2006.
[2] Elwyn R. Berlekamp, Tom Rodgers, The Mathemagician and Pied Puzzler: A Collection in Tribute to Martin Gardner.
[3] Hadrien Cambazard, John Horan, Eoin O'Mahony, and Barry O'Sullivan. Fast and Scalable Domino Portrait Generation. Proceedings of CP-AI-OR 2008.
[4] Kenneth C. Knowlton. Representation of designs. U.S. Patent # 4,398,890
[5] http://www.oberlin.edu/math/faculty/bosch/making-tspart-page.html
[6] http://mrl.nyu.edu/~ajsecord/stipples.html
[7] http://www.mathacademy.com/pr/minitext/escher/
[8] http://www.paul-brown.com/WORDS/STEPPING.HTM
[9] http://en.wikipedia.org/wiki/Wiki