Symmetry Analysis of Two-Dimensional Patterns for Computer Vision

1. INTRODUCTION

Two fundamental properties of a two-dimensional pattern are its rotational and mirror symmetries. These properties are important in the recognition and location of patterns, because they can be used to locate key features that determine the orientations of the patterns and differentiate them from those that are similar. These properties are especially important in performing industrial vision tasks, in which symmetrical, or almost symmetrical, parts are common. For example, Figure 1 is a part to be picked up and added to a subassembly. It is two-fold rotationally symmetric ti.e.~ its appearance is unchanged by a rotation of 1o0 degrees). If it is occasionally presented upside down, it would be impor t ant to know that it is not mirror­ symmetric (the relative orientation of the holes with respect to a line joining their c~nters is d i f'ferent. in the mirror image). Since the pattern is not mirror-symmetric, a vision system could detect upside-down parts and instruct the manipulator to turn them over before adding them to the subassemblies.

Current industrial vision systems, like SRI's vision module [5] and Bausch and Lomb's OMNICON [2), recognize patterns on the basis of such global features as the area and perimeter of a pattern, because statistical pattern recognition techniques can easily model such features. Since these simple vision systems do not use local features, such as holes and cornersi or their symmetries, they cannot automatical y determine the orientation of the pattern in Figure 1 or distinguish it from its mirror image.

A few artificial intelligence programs have performed symmetry analysis. ~vans' program, whi ch worked geometric-analogy problems, tested the primitive ligures to see whether they were mirror-symmetric about a horizontal or vertical axis l J]. Gips' program analyzed two 3-dimensional strings of cubes to determine whe~her they were rotational or mirror transformations of each other [4). Perkins' program [7] used a form of correlation to determine whether a pat tern was rotationally symmetric. That program, like its counterparts, was not intended to perform a general-p11rpose symmetry analysis aimed at understanding local features, structures of local features, and their properties. It is precisely this kind of comprehensive understanding that is the purpose of the research reported in this paper.

*This work was supported by NSF under grant APR75-13074.

In a recent paper Wechsler l8] describes an algorithm that decomposes two-dimensional patterns into mirror-symmetric components. His approach employs the same mathematical descriptions and tests for symmetry as are referred to in this paper, but his goal is to describe regions rather than c haracteri~e structures of local fea t ures .

2. REPRESENTATION~

We shall now define a representation scheme based on a set of structural primitives for patterns. The intent is to identify important constructs{ their properties and relationships, and to def ne a convenient way to describe patterns.

Pattern symmetries are determined by the properties of groups of "similar" features. Features are defined as similar if (1) they have the same description (i.e. 1 type, size, and shape), (2) they are equid1stant from the pattern's center of gravity, and (3) they have the same orientation with respect to a line from the pattern's center of gravity to their own. Therefore, if two features are similar, the pattern can be rotated about its center of gravity so that one feature is repositioned at the other feature's original position and orientation. For example, the two holes in Figure 1 are similar.

Groups of similar features are important because they form structures of features that limit the potential number of rotational symmetries for the pattern. In particular if a pattern is M-fold rotationally symmetric and it contains a structure of features that is N-fold rotationally symmetric, M must be a divisor of N.

The representation scheme describes patterns in terms of these structures of features. Since the features in a structure are similar, the structures can be represented by one example of the feature and a list of angular positions. Individual features can either be simple{ such as a corner~ or complex, such as the ent re pattern in rigure 1. Co~lex features are described in terms of structures of other features. Therefore, the representation scheme describes patterns as trees in which the nodes represent individual features or structures of features. Figure 2 shows the two types of nodes. The "descriptions" of individual features correspond to the global features used by simple vision systems.

FEATURE

POSITION

ORIENTATION

ROTATIONAL SYMMETRY

DESCRIPTION: TYPE

SIZE

SHAPE

POINTER TO LIST OF STRUCTURES

FIGURE 2 NODES IN THE REPRESENTATION

STRUCTURE OF FEATURES

POSITION

ORIENTATION

ROTATIONAL SYMMETRY

POINTER TO SAMPLE FEATURE

NUMBER OF OCCURRENCES

POINTER TO LIST OF ANGULAR POSITIONS

Every node in a tree that represents a pattern has a position, orie~tation, and rotational d t symmetry. The "lear n~es, which correspon o simple tor primitive) featurest have inherent values for these properties. he values for the other nodes are functions of their inherent values and the values of the nodes directly beneath them. An important part of the representation scheme is the set of conventions that specify these functional relationships. Unfortunately, these conventions cannot be described for lack of space, but may be found in [ 6].

3. SYMHETRY ANALYSIS

In this section we briefly describe algorithm for performing the symmetry analyses.

3.1 Rotational Symmetry An~lysis Given a pattern, the rotat onal symmetry analysis builds a tree to describe it and, in the processt determines its rotational symmetry. he algorithm is as follows:

RotSymm(PATTERN) =

Create a new feature node for the PATTERN Fill in the description of the PATTERN Set the node's list or structures to empty If the PATTERN is complex then For each subpatterni call RotSymm(subpat) Group together simi ar subpatterns For each group Create a new structure node Add it to the list of structures Select a sample feature for the struct. fill in the number of occurrences and angular positions of the features Delete the unused feature nodes Compute the position, symmetry, and orientation of the structure Compute positionl symmetry, and orientation of the PATTEHN .

Return a pointer to the PATTERN's node

The rotational symmetry of the pattern is the symmetry of the topmost feature node in the tree description.

3.2 Mirror sy~etr~ t~alysrs Given a tree ~scr p on o a pattern, the mirror symmetry analysis builds a tree to describe the mirror image of the pattern and, if the two trees are similar, declares the pattern to be mirror-symmetric.

Two short recursive procedures can build the mirror image tree. One produces the mirror image of a feature node the other produces a mirror image of a structure-of-features n~e. Since the similarity of two patterns is independent of their orientation, the mirror image of a pattern can be formed by reflecting it about any axis, not necessarily an axis of mirror symmetry. Therefore, it is not necessary to locate an axis of mirror symmetry to determine whether or not a pattern is mirror-symmetric. The mirror image of a feature node can be formed by reflecting its position and orientation about the X-axis and replacing each structure in the list of substructures by its mirror image, The mirror image of a structure can be formed by reflecting its position and orientation about the X-axis, replacing the sample feature by its mirror image and reflecting all the angular positions in the list of occurrences about the X-axis.

The mirror symmetry analysis could be performed without constructing the mirror image tree, but the algorithm would be more complicated.

4. ~XPERIMENTAL ~

The experimental system is an extension of the vision system developed by Agio at SRI International [1], which performs a connectivity analysis of binary p,ictures and produces a tree description of the 'blobs" in the picture. (A blob is a connected region of uniform color.) The symmetry analysis converts blob descriptions into the symmetry representation and performs the mirror symmetry analysis. The features it uses are holes, elongations (i.e., axes with the minimum second moments), and minimum and maximum radii. The analysis automatically locates these features, groups them into structures of features, and determines their symmetries . Sample results are shown in Figure 3. The pattern in Fi~re 3a is not rotationally symmetric, but 1t is mirror-symmetric. The pattern in Figure 3b is three-fold rotationally symmetric, but not mirror-symmetric. The pattern in Figure 3c is two-fold rotationally symmetric, but not mirror-symmetric.

Since the algorithms analyze digital images, thresholds are required for making some of the decisions. For example, how close to perfect symmetry does a set of features have to be for the program to call it symmetric? The program automat1cally establishes these thresholds on the basis of the pattern being analyzed and a model of the expected pixel errors. These thresholds, however, can be interactively overridden.

5. DISCUSSIO~

One of the basic goals of this research is to simplify the process of producing programs for recognizing and locating patterns. Ultimately this means the development of a system that can be trained by showing it examples. Such a system would determine the symmetries of a pattern locate key features, choose the most cost/e ffective features to use at run time, and produce a program to perform the task. In contrast thereto, the current program is limited to determining the symmetries and locating some key features.