This is the abridged version of the document. Follow this link for the full version.

Research Status:
Shape Grammar Inference System

programming, research and report by Eric Hortop, Research Assistant

for
Drs. Cheryl Kolak Dudek and Lydia Sharman,
Faculty of Fine Arts, Concordia University

in connection with their research project to development new shape grammars using inference algorithmns to analyze the designs of Congolese Kuba cloth and Moroccan zillij mosaics, and provide methods to facilitate creating works of art using the same geometric language.

The first phase of this research is being funded by the Hexagram Institute for Research and Creation in Media Arts and Technologies, with additional funding from the Concordia Institute for Co-operative Education.

last update: 2 Sep 2002

Introduction

The Shape Grammar Inference System (ShaGrInS) is under development for the immediate purpose of extracting geometric rules for the construction of new designs from Moroccan Zillij mosaics and Congolese Kuba cloth. In the long term, it may be used to infer sets of these rules (shape grammars) from other designs. The system will take text files describing a set of designs, extract patterns from lists of representations of their constituent line segments, re-sorting and re-searching until cumulative complete "coverage" of each design is achieved. The system will then perform set operations on the patterns, looking for intersections and recursion structures, to turn the patterns into shape grammar rules. A second round of set operations will then generate a small set of common rules, a larger combined set of rules, or some other subset of all the rules it has derived from the designs it has been given. This output set can then be interpreted by hand by a person familiar with the idea of a shape grammar or reformatted into inputs for an existing or new shape grammar interpreter.

This document provides a survey of the approaches and issues involved in work to date on ShaGrInS. The approach involved is one of mutation and improvement of both a proposed grammar and of the methods used to extract rules for it. The system attempts to respond to the specific challenges posed by Kuba cloth and Zillij mosaics without overspecializing itself. As barriers to a working system are gingerly taken down, it becomes necessary to give some consideration to the degree of openness and accessibility of the system's inner workings to the public, and to assess the medium-term needs of the project. This document provides a snapshot of these concerns.

Approach

This system represents a departure from the usual ways of approaching shape grammars. Terry Knight proposes [KNIGHT_1994] that shape grammars represent an opportunity for designers and artists to be creative in defining a process of design: as shape grammars can be used for the automated design of particular objects, one deep creative undertaking (specifying a grammar for a language of designs) then results in the partially or completely automated generation of designs. This system takes a different approach to the use of shape grammars. It assumes that a given design can have an uncountably infinite number of shape grammars that generate it, and that a set of designs will have infinitely many sets of grammars (but only a subset of the grammars capable of generating any one of its designs) which include it in their languages. By constraining the types of rules available and the availability of vertices and edges of note in the design, we hope to reduce the inference of common grammars for sets of designs to a manageable task by granularizing the search space, making the search process more computer-friendly. These constraints should start by getting rid of trivial and imperceptible operations, and should reduce the number of accessible generating grammars... maybe only to a countably infinite set, but a more manageable one whose elements can be constructed by using a finite strings of spatial relations from the design itself. These grammars will contribute to an understanding of the designs studied, and provide an artist or designer with a set of constraints based on some source material. These constraints can then be used in their raw form to create new designs, fill in gaps or damaged areas in the original work with plausible interpolations or aid in the judging of relatedness of designs. They can also be transformed as described by Knight, changing the shapes, connection points or recursive structure to create new grammars and languages of designs.

Shape grammars, as defined by Stiny [STINY_1975] require that a part of a design matches the input half of a shape rule so long as it is congruent under a combination of linear transformations (scale, rotation, reflection, translation). If one keeps track of shapes as points in R² then when one rotates sets of points in the computer, potentially nasty roundoff errors result, making matching difficult. The ShaGrInS approach is to change take all the lines in a design, sort them in some way (usually trying many times, iterating over a variety of sorts) and convert them to a “step-turn” notation, where the step is noted as the ratio of the current line's length to the length of the previous line, and the turn is noted as the current line's orientation (in radians) minus the previous line's orientation, normalized into the range 0 ≤ turn < 2π. This results in a single shot at roundoff error for each line, and because everything is in relative units, “fuzzing” (allowing slightly different values to be considered equal) in comparisons can be done without a bias towards the recognition of matches involving small shapes.

The basic cycle of the grammar inference system is sort, convert, compress and repeat. No single application of this cycle is likely to generate enough rules to generate the whole design. The system needs to run several iterations of this cycle, trying to learn what makes a "good" (high-coverage) sort try related sort methods. In order to "learn" a good sort method for a particular group of designs, the system will use a genetic algorithm, testing and measuring a group of randomly generated sort orders, “mating” sort orders with each other proportional to coverage success, and repeating the test-evaluate-mate loop until a stopping condition is achieved. This technique is outlined in Koza's work on genetic programming [KOZA_1992]. The stopping condition could be attaining a certain level of coverage (e.g. enough to generate all designs, k₁ times as many rules as the minimum count of discovered rules required for complete coverage, enough that every line segment in the design can be generated by k₂ rules, etc.), or attaining a certain level of compression, or after some umber of generations. This condition should be configurable and should allow for Boolean combinations of rules (e.g. {"Minimal complete coverage" AND ["All line segments covered twice" OR "Three times the minimum number of rules" OR "Four hours elapsed"]} OR "Eight hours elapsed" should be a valid stopping condition).

Having a configurable system allows development of the system to go on on two levels. The general system, capable of handling all kinds of designs, can be developed and refined by programmers and engineers, while users and subject matter experts can tinker with settings particularly useful for their own projects. Hence the same core application could run optimized "Kuba settings", "Zillij settings", for another and "exploratory settings" could be packaged with the system an used for preliminary work on new types of design.

Software components

At present, two software components are under development. The Input Method supports the Main Program, not only by making it easier to enter data, but also by cleaning the data up (with user guidance) so that the Main Program can better make sense of it.

Main program

The main program is under development in ANSI Common LISP. LISP was chosen due to its prevalence as a language in shape grammar research, its cross-platform friendliness (open-source and commercial cross-platform interfaces, such as Garnet and CLIM exist, and cross-platform file management and timing are built in). LISP also has support for object-oriented programming (including advanced features like mixins and generic functions), flexible and rigid typing, the passing of instructions as data and a highly consistent syntax. These features make exploratory programming as well as maintenance and teaching of a system developed in LISP easier. IDEs for LISP include necessary features — like time profiling and a wide assortment of debugging tools — and nice ones like auto-indenting, syntax colouring and debugging of a running program. An exhaustive description of LISP is available in the Common Lisp HyperSpec [XANALYS_HYPERSPEC].

As of this writing, the main system converts between basic Cartesian coordinates, and a “step-turn” notation that makes comparing similar patterns at different orientations and scales easier. It has a wide assortment of tools built to analyze line and point intersections, compare orientations, do periodic data clean-ups, output debugging text and PostScript graphics instructions. It has a highly adjustable sort function with hooks for its integration into a genetic algorithm–based pattern–search algorithm.

The present approach to the main system is to build data structures and functions roughly in the order that they are called in the inference process. A library of recurring functions and structures has already been assembled, and most of the code for standardization and decomposition of a design into step-turn notation has been done.

Initial attempts to move from test data to real data (rectilinear Zillij designs) were foiled by the difficulty of going from tracings of scanned images of photographs (with inherent camera lens distortion, added to the not–entirely–consistent use of grout and placement of tiles, suggested the need for an input method that includes some geometric constraint tools to "clean up" the data into something more regular and reflective of the assumed intent and design processes of the original mosaic artisans.

Main program process

Completed portions are set in italics, to-do or semi-complete portions are not.

1. load all classes, recurring functions, constants; initialize global lists and random number generator
2. loop for all designs:
   1. load designs from LISP file
   2. break line segments down into non-crossing segments
   3. normalize line segment orientation
   4. initialize a group of sort schemata
   5. loop for at most a specified number of “generations”:
      1. loop over all the sort schemata:
         1. loop over all the designs:
            1. sort the design using the schema
            2. convert sorted line segments from Cartesian to step-turn notation
            3. pick out recurring patterns in the sorted list of line segments
            4. evaluate the “coverage” of the whole design by the recurring patterns
      2. “mate” schemata with a frequency proportional to their average success in “covering” entire designs with patterns of a predetermined complexity range
      3. place the “offspring” into the pool of sort schemata to be used in the next generation
3. perform set operation (union or intersect) to create a new global set of patterns from the design patterns
4. work out recursion structure over new global set
5. drop “islands” (rules in inaccessible portions of the recursion structure) from global set, or create new parallel global sets if distinction between the body of the recursion structure and the “islands” is unclear (the user should be able to set the acceptable level of ambiguity).
6. mark up resulting patterns and structures for output
7. generate PostScript graphical and text output from the marked-up information.

Input method

Work has begun on a Macromedia Flash-based input method for points and lines with built-in constraint solving and conversion to syntax which creates well-formed LISP code for use by the main program. Flash is a good choice for this job due to the availability of Flash players on a variety of platforms and its pre-existing tools for graphics, variable-sized arrays and collision detection.

The present algorithm is confused by overconstrained systems and sometimes generates counter-intuitive but technically correct design modifications. Sometimes it requires more than one pass to adapt to a change in points or rules. Present research focuses on getting this system to work with less-than-optimal sets of constraints and produce recognizable result patterns. This may be achieved by the use of implied constraints, cancellation and combination of constraints, and further opportunities for the user to provide different types of constraints and “hints” to the constraint solver.

The reasons for including a constraint-solving/pattern correcting input method are multiple. The possibilities for acting as a "spell check" for human operators are promising: if a mismeasurement occurs or a point is left out and good constraints have been given by the operator, the input method could challenge the user in real time to re-check their measurements or confirm the point. By experimenting with different constraint sets, operators can make and verify hypotheses about designs already entered. With some foreknowledge of the design practices used to create a pattern, operators can automate some correction for lens and perspectuve distortion in scanned photographs, or stretches and wrinkles in scanned cloth or prints. Such an input method could also be used for exploratory design in simple constraint systems.

The constraints used by the input method can be more or less strict to achieve the desired information richness or leanness in a design's data set. Fewer constraints and more complex designs lead to more complex grammars where more rules are applied less often in a more complex recursion structure. More constraints and/or simpler designs should lead to smaller, more elegant grammars, possobly with less opportunity for arbitrariness and variety (although very simple rule sets can potentially create very complex emergent behaviour).

Aesthetics research

Some understanding of the sources of the initial data is required to build a system which will interpret it and draw conclusions from it.

Zillij mosaics

Judging from previous research into Islamic traditions of pattern-making, it seems justified to clean up the point sets generated by scanning and tracing Zillij mosaics, to make band widths uniform, snap angles to appropriate values (as determined by the degrees of rotational symmetry) and adjust distances between points to allow the first two constraints to be satisfied. This gave rise to the work on the point input software. In addition, as the Kuba cloth tends to be rectilinear, similar rules can be applied (with manual verification) to the transcription process for Kuba cloth, reducing the chances of transcription error.

It is also apparent that the Zillij mosaics are very similar to metalwork in Islamic North Africa on doors and panels: an interesting application of the software would be to assess the similarity or difference of the results generated by the inference system.

Kuba cloth

Readings on the Internet and from Shoowa Design [MEURANT_1986] indicate that there has already been work on breaking Kuba cloth down into component patterns. Special attention will be paid to the conclusions of this research as they compare to those of previous research.

Possible directions

The comparison between the highly structured, elegant designs of the Zillij mosaics and the arbitrary, information-rich Kuba cloth suggests future investigations into modifying rule sets to vary information content. Investigations could be undertaken into creating a more arbitrary Zillij-like rule set (either prompting a human or using random processes to generate designs) or a deterministic, regular analogue to Kuba cloth. Would such variant designs give the same impressions as their inspiring designs? Will the introduction or reduction of “design noise” influence viewers' perceptions? Will it turn out that more regularity exists in Kuba designs than anticipated, or that the seemingly deterministic Zillij mosaics have eddies of random or arbitrary design? The application of shape grammar inference and the dissemination of the results should help answer these questions and raise others.

Shape grammar inference could also aid curatorial and conservation efforts to preserve and classify pattern-bearing objects. Educated guesses could be made at the relatedness of objects by comparing their inferred grammars. Where conservators have decided to undertake repair efforts on a damaged piece, shape grammar inference could suggest how to bridge a gap in a pattern or offer insight into the relative placement of fragments.

More design-oriented applications could include keeping product or communications design consistent by “vetting” new additions to a line or new templates and verifying that they don't increase the complexity of the “company grammar” substantially. Attempts to buld a consistent look and feel or make the operation of a device more intuitive could benefit from shape grammar inference from the device's comparison group (similar devices or the line of devices to be given a consistent look and feel). True 3D analysis is a long-term goal, but the analysis of control panels and work surfaces is within reach of a system fulfilling the present development goals.

Release options

At some point we need to decide whether the software used to assist in this research should be released to the public, and how.

Non-release

There may be a case for keeping the software unreleased and releasing / exhibiting only the results (analyses, art pieces). The only reason to do this, though, would seem to be awaiting a better time to release it in some other way, or if the release of non-repeatable pieces and research is highly beneficial. In essence, this is what we have been doing up to now. It leaves our options open for the future.

This approach (at least if continued indefinitely) has some drawbacks. Research results' credibility would suffer due to the hiding of some parts of the method of inquiry (particularly if that hiding renders the research non-repeatable). Outside suggestions and parallel research become less feasible, as commentators have to guess how the software is working, and parallel researchers have to start without the benefit of our tools and knowledge. Fellow researchers may be less likely to share their findings and techniques with us if we hide substantial parts of ours.

Release binaries only

Releasing only the binaries (the compiled program) allows us some control over how people use the software, while allowing others to repeat analyses we have done (provided they can get data for the repetitions), analyze other data with our methods, and get a vague sense of how our tools work. Such a release could be licensed in a variety of ways: paid or free licenses (with or without exceptions for academic, non-commercial, teaching or evaluation use), by specific request or publicly accessible, with redistribution or site use permissions or not. This approach gives others a chance to use our tools, while restricting the growth of a confusing flock of variants. It allows us to get feedback from users, and get the word out about the research. Differing distribution policies could be specified for “beta” (test) versions and “stable” or “final” versions, e.g. free for test versions — which may have a set expiration date and extra bug–reporting functions — but paid site licenses for milestone releases.

Disadvantages of this method tend to involve things getting very labour–intensive for us: users can only report bugs to us, and we fix them, and should someone want to run the software on an unanticipated platform, we would have to port and recompile it, or tell them to switch platforms. A support bottleneck situation could arise if the software gets even slightly popular.

Release binaries with source

The most open release strategy would be to release binaries of the application with source code. This would allow other parties to see exactly how the system works, giving them opportunities to understand its internal workings better, as well as create modified versions to suit their own needs (for example, changing the present PostScript output to PNG graphics, adding an input facility to read their favourite CAD program's files, or changing the adaptive sort algorithm to add Dutch-language or pile–height – difference sorting) without a lengthy reverse-engineering process. The software then becomes more useful to more people. Some (many, we hope) of these user modifications might make their way back to us, and could be integrated into our version or inspire changes. Variants customized to serve specific needs might also serve to increase awareness of the project.

Nonetheless, it is possible to retain some say in others' use of a program released as source plus binaries. A license can be attached to them, restricting their use, requiring the reproduction of credits and copyright information, requiring notification of the release of variants, or other terms. These restrictions are as binding as any license attached to downloadable software, and just as enforceable, i.e. companies and large organisations are likely to comply, individuals will vary in their compliance, and the cheaters will be nearly impossible to catch. These problems are not unique to distributions that include source code. One particularly popular, widely understood and carefully-written license is the GNU General Public License (GNU GPL).

The GNU General Public License

Free software is software that comes with permission for anyone to use, copy, and distribute, either verbatim or with modifications, either gratis or for a fee. In particular, this means that source code must be available. “If it's not source, it's not software.”

The GNU GPL [GNU_GPL] is a license which can be used to license a software program to the public. It protects the software's status as free software, as defined by the Free Software Foundation. In summary, free software is software which can be freely copied, used and modified by anyone who cares to do so. The GNU GPL also ensures that any derivative works based on the software are also released as free software if they are released at all. Provisions are made for the prominent attachment of notices stating modified versions' coverage under the license, changes made, and the original copyright information for the licensed work. A key feature of the license is that source code for any derived versions or redistributed copies must accompany the compiled code.

Software released under the GNU GPL is not released into the public domain, so as to prevent it from being integrated into non-GPL software (i.e. proprietary software, which generally has no provision for the inclusion of source code and generally has provisions against the creation of modified versions, or even attempts to view an actual or inferred copy of the proprietary software's source code).

The GNU GPL affects only distribution of the software. An individual or organization may use a modified version of the software internally without releasing source code, but as soon as they release the software, it must include source code and fall under the GNU GPL.

The GNU GPL does not forbid profiting from “free” software — it is considered free as in “free speech” as opposed to “free beer” [GNU_SELLING]. Individuals are still entitled to charge for copies of the software, documentation (although there exists a GNU documentation license — the GNU Free Documentation License [GNU_FDL] for those who want to write free documentation with a similar license). Direct profit could be made through the selling of packages with manuals, support, physical media, etc. This would be in addition to the benefits to all involved of having software tools tailored to their specific needs, good publicity, encouragement of related research, and constructive criticism from a traditionally very cooperative and ingenious Free Software community (from which came GNU/Linux, Emacs and countless smaller, more specialized free software).

Future needs

One or more additional technically-oriented researchers (preferably with experience and theoretical knowledge in graphics programming, compression and/or constraint programming, as well as a working knowledge of LISP and Perl) would help make programming and testing go much faster.

An Internet-accessible repository for code and data would make result sharing and coordination much easier. Some kind of access-control or locking system would make duplication of effort less likely. This repository would not need to be accessible to the public and could use a simple password system to keep sensitive or unfinished parts locked down. A publicly-accessible page with news and updates might stimulate interest in the project and encourage others to undertake parallel research or comment on the system, fuelling the development of the system itself as well as the more general discipline of computational shape grammar.

Access including the ability to install outside software to SPARC/X Window computing facilities would allow us to run an already-released geometric constraint solver by Hoffman et al. from Purdue University, analyzing the performance of or replacing entirely the present one running under Macromedia Flash. A minimum workspace of 20MB (including space to install the constraint software and keep data files) would be required. Remote access would be fine. Efforts will be made to secure these facilities through the Faculty of Engineering and Computer Science at Concordia. Such a SPARC workspace would complement, not replace, one or more desktop machines running ANSI Common LISP, Macromedia Flash and Perl.

Access to a workspace (on or off campus) capable of holding four people at computer terminals would provide a central meeting and hacking space. Ideally this space would have windows and adequate ventilation so as to reduce the health risks of long sessions of exploratory work. Such a space could be shared with other groups on a time-sharing basis, but some private storage (for books, notes, backup CDs and prints) would be necessary.

References

[GNU_CATEGORIES]

Free Software Foundation. Categories of Free and Non-Free Software. Boston, Massachusetts, USA: Free Software Foundation, 2001. URI: http://www.gnu.org/philosophy/categories.html

[GNU_FDL]

Free Software Foundation. GNU Free Documentation License, version 1.1. Boston, Massachusetts, USA: Free Software Foundation, 2000. URI: http://www.gnu.org/licenses/fdl.html

[GNU_GPL]

Free Software Foundation. GNU General Public License, version 2. Boston, Massachusetts, USA: Free Software Foundation, 1991. URI: http://www.gnu.org/licenses/gpl.html

[GNU_SELLING]

Free Software Foundation. Selling Free Software. Boston, Massachusetts, USA: Free Software Foundation, 2001. URI: http://www.gnu.org/philosophy/selling.html

[KNIGHT_1994]

Knight, Terry W. Transformations in Design. Cambridge, UK: Cambridge University Press, 1994.

[KOZA_1992]

Koza, John R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Massachusetts, USA: MIT, 1992. pp 17–62.

[MEURANT_1986]

Meurant, Georges. Shoowa Design. London, UK: Thames and Hudson, 1986.

[STINY_1975]

Stiny, George. Pictoral and Formal Aspects of Shape and Shape Grammars. Basel, Switzerland: Birkhäuser Verlag, 1975, pp 28–39; 122–126.

[XANALYS_HYPERSPEC]

Xanalys Incorporated. Common Lisp HyperSpec. Waltham, Massachusetts, USA: Xanalys, 2001. (downloaded June 2002) URI: http://www.lispworks.com/reference/HyperSpec/.

Acknowledgements