Pattern Recognition in Origami
For more information:
History of Origami:
Web site of the Origami Group, part of Watanabe’s lab at Nagoya University
Shimanuki, Kato, Watanabe, “Recognition of Folding Process from Origami Drill Books”, in Proc. of 7th International Conference on Document Analysis and Recognition (ICDAR’03), pp. 550-554, 2003.
Shimanuki, Kato, Watanabe, “Constituting origami models from sketches,” Int. Conf. Pattern Recognition (ICPR’04).
Figure shows some of the processing steps from
frog drawing to origami folding model.
The link between origami and mathematics became widely known in 2003 when a MacArthur Award was given to Erik Demaine, a young mathematician now at MIT. Demaine and his co-authors solved a problem originally posed by Martin Gardner in a 1960 article in Scientific American. The problem was to determine the limits of polygonal shapes that can be made by folding a rectangular piece of paper and cutting it with a single straight cut. What Demaine, et al., found is that – surprisingly – there are no limits. Every polygonal shape can be produced. Furthermore, the mathematicians showed how to design computational geometry algorithms to tell the origami designer where to fold and cut. These mathematical results have generated a newfound interest in origami by scientists, including pattern recognition researchers.
Origami, from the Japanese words “oru” (to fold) and “kami” (paper), is a craft that is synonymous with Japanese culture, but traces its origins to China, perhaps as far back as the origins of paper in the first or second century. In 1797, Akisato Rito published a book, “How to Fold 1000 Cranes.” It was based on a Japanese custom that if a person folded 1000 cranes, he or she would be granted a wish. In the mid 20th century, in the context of industrialization and war, origami had declined in popularity. But a young girl and the 1000 cranes would bring about a renewed, worldwide interest in the art. An 11-year old Japanese girl, Sasaki Sadako developed leukemia as a result of radiation exposure from the Hiroshima bombing. When told of the custom, she endeavored to fold 1000 cranes, originally for her wish of good health, but ultimately for world peace. She died after making 644 cranes. But now each year on Peace Day in Japan (6 August), thousands of origami cranes are sent from around the world to be displayed at the Children’s Peace Memorial in Hiroshima.
I had been aware of some of this cultural and mathematical background of origami when I serendipitously came upon a paper presented at the recent ICPR in Cambridge entitled, “Constituting Origami Models from Sketches,” by Shimanuki, Kato, and Watanabe. Always excited to learn of new applications in pattern recognition, I asked the authors to further explain their motivation and work.
Hiroshi Shimanuki is a doctoral student in the Department of Information Engineering at Nagoya University. Wanting to combine his interests in image recognition and Japanese culture, he found Dr. Jien Kato at the university, who was already exploring origami in Professor Toyohide Watanabe’s laboratory. This laboratory, which included the complementary topics of computer vision, document image processing, and machine understanding, would be a perfect home to foster their interests.
The initial motivation for applying pattern recognition techniques to origami was to encourage more people to participate in the craft. The problem, as explained by Shimanuki, is that it is sometimes difficult for people – especially children – to understand and follow directions from the folding steps of most origami drill books. In particular, these steps cannot show all perspectives of the model. Therefore, this group proposed a system showing how a computer model of an origami piece can be created, then how the folding can be shown in 3-D, computer animated space. The computer model contains full information on the 3-D shape and this model is modified throughout the folding process. In this way, any intermediate folds can be viewed from different perspectives for better understanding of the steps toward the final result.
A second endeavor of this group was to start the origami not with existing folding instructions, but with a hand-drawn sketch of a target object, for instance an animal. The approach here was inspired in part by mathematicians’ use of geometrical techniques, but also incorporates pattern recognition and image processing techniques. Steps in this process are as follows. The target object is first hand-sketched. This sketch is skeletonized. Nodes are found from this skeleton and arranged to be symmetric and to fit onto a square that will be the origami paper. From these nodes, dividing polygons are computed that meet geometric constraints such that they will be the folded faces of the final result. Finally, the mountain and valley crease patterns are identified. After this, the folding steps generated here can be displayed using the computer animation approach described above.
Currently, there is a human component involved to adjust the automatically found fold locations to create a result that also incorporates the designer’s aesthetic sense. Shimanuki is working now to improve the process, and feels that other shape detection techniques than skeletonization might yield better results.
Now that the ancient art of origami has crossed bounds into the fields of mathematics and pattern recognition, perhaps we will see more researchers taking up the challenge that Demaine and Shimanuki have begun.