Computer Perception of Complex Patterns

Introduction

A software Pattern Perception System, PPS, has been recently developed for recognizing com­ plex line patterns by incorporating some of the perceptive characteristics observed in perceptual psychology. This approach to structured pattern recognition is introduced as an alternative to the contemporary syntax-directed analysis ap­ proaches (1)(2)(3), with the objective of (a) in­ creasing the flexibility and efficiency of the system, and (b) experimenting with various ways of enhancing the visual perceptive capability of computers. The purpose of this paper is to es­ tablish the psychological relevance of PPS and to describe the functional organization of the sys­ tem. Examples of PPS activities related to re­ cognition and class formation will also be pre­ sented and discussed in this paper. The detailed formal information structures and processing facilities, however, will be reported in another paper by these authors (4),

At present, PPS is implemented on the APL/ 360 on-line system utilizing extensively the dis­ tributive programming environment available in that language, While the concept of PPS is not confined by the programming language, we should point out that many of the numerical codes that were created represent a special symbolism based

on linear list· and arrays.

PPS and Perceptual Psychology

Seeing a pattern implies its isolation as a figural unit from the rest of the visual field, while perceiving it requires, in addition, the assignment of an organized representation to the pattern (5). This organized representation is referred to as the perceived pattern and is a product of the constructive aspect of perception. In PPS the analogous representation of a pattern consists of both a structured description which groups the pattern components into an hierarchy and a local description of the components in terms of a limited set of primitive forms.

Psychological experiments have shown that different subjects, when asked to memorize mean­ ingless patterns and reproduce them later in terms of perceptual units, decomposed patterns into various sets of components which were de­ pendent on the strategies used by the observers (6). Figure 1 illustrates three ways in which the pattern given in Fig. la can be decomposed, we call the strategy associated with the decom­ position in Fig. lb the continuity strategy, since each component is traced until it termin­ ates at a free end or at a junction with itself or another line. Figure lc exhibits another strategy which extracts the closed perimeter or outer boundary - a line which encloses the en­ tire pattern - and fills in the remaining com­ ponents. A third strategy operates by tracing around the simplest enclosed areas comprising the pattern. The components thus obtained are shown in Fig. ld, which differs from Fig. lb and lc in that it represents planar regions rather than lines. Thus, in both PPS and the human perceptive process, a segmentation of figural units is directed by some preconceived rules , as well as by the pattern features.

It has been recognized (5)(7) that compon­ ents or objects segregated after the preatten­ tive processes provide the potential framework for subsequent pattern synthesis and analysis. In general, the manner in which a pattern is segmented determines the reorganization of the components into an hierarchical description and further affects the pattern analysis. The way in which components are organized is of funda­ mental concern in cognitive psychology and also in the implementation of PPS. Figure 2a shows a complex pattern with components A, B, C, D and E. Figure 2b and 2c show two different hierarchical representations according to the choice of ref­ erence component with which the other components are grouped. Here, the representation of Fig.2b is intuitively judged to be simpler since it re­ quires only two levels. However, when two hier­ archical representations of the same pattern (Fig. 3) have an equal number of hierarchical levels, a further discriminating criterion is necessary to select the one with greater organ­ izational simplicity. At present, there is no objective measure of organizational simplicity (8). A method is needed to express and .extend the intuitive judgment used heretofore. The measure incorporated in PPS, which has been found to be consistent with intuition and within the system is one in which the structure exhibiting the lo~est average hierarchical level is judged to be the simplest, This measure for a given hierarchy can be represented by Lav' the aver­ age hierarchical level, where ni is the number of components at level i and N is the order of the greatest level. Figure 3b has one first-level, three second-lev­ el, two third-level and one fourth-level compon­ ent, yielding an average component hierarchical level of 2.43 versus that of 2. 57 obtained from the representation of Fig. 3c. Therefore, the structure· with component A as reference is pre­ ferred over that with component B, agreeing with common intuition. The recommended measure, termed the simplicity criterion in PPS, tends to choose a structure which groups the most compon­ ents at levels near the reference component. For structures with equal simplicity, local descrip­ tions are required in the selection of the refer­ ence .

The simplicity criterion may sometimes be superseded , particularly when the pattern con­ tains a meaningful subpattern (6) , i.e. , one that 1& recognized by the observer. In such cases , a familiar subpattern or a subpattern with distinc­ tive features may be extracted as a unit and used to group the remainder of the pattern. Figure 4a is a pattern with components A, B, C and D found from the continuity strategy and Fig. 4b shows the hierarchical structure with A as the refer­ ence. If the observer sees components C and D as the character "4", then the structure of Fig. 4c is the likely representation, even though it has more hierarchical levels. Of course, no pattern is completely meaningless, so that a continual tension is maintained between organizing a pat­ tern according to the simplicity criterion and organizing around a more or less familiar sub­ pattern.

The existence of hierarchical representa­ tions in human perception is supported by retinal stabilization studies (9)(10) , which indicate that a pattern disappears and reappears in frag­ ments that are closely grouped in a hierarchy. ~aningful or recognizable patterns tend to re­ main intact more than unfamiliar ones , indicating the influence of previous experience on percep­ tion.

Eye movement studies (11) have indicated that the preliminary observation of a painting or pattern is an essentially non-directed sur­ vey of the whole, during which an initial repre­ sentation is constructed. Focal attention is then brought to bear for a more detailed examina­ tion of interesting features. If non-directed processing is assumed , an objective measure for reorganizing the initial representation is re­ quired . Different observers or the same observer at different times may form various schemata of the same pattern (6 ) . The formation of a schema depends on the choice of reference , as well as the structure into which component sets are grouped. The susceptibility to variation in the structured description (due to indecision as to the choice of reference) may be viewed as an in­ dication of the instability of the organization of the perceived pattern. A pattern that can be represented by hierarchical structures of equal stability or simplicity is considered to be an ambiguous pattern. The perceived pattern may then shift from one representation to another. Figure Sa is a pattern that has been decomposed into two sets of two components each, shown in Fig. Sb and Fig. Sc, by the continuity and outer boundary heuristics , respectively. The two rep­ resentations have equal simplicity , although the decomposition into two triangles has more famil­ iar components and is thus more frequentl y seen as such. Therefore, in PPS, unambiguous patterns can be uniquely represented in an hierarchical structure of maximum simplicity, while ambiguous patterns may have more than one hierarchical structure of equal simplicity . Once a represen­ tation of maximum simplicity is achieved and the corresponding Lav obtained is much less than those of other representations , PPS will retain that as a stable representation unless it is re­ directed , by command, to consider another com­ ponent as a new reference. This process may re­ semble the phenomenon of fixation in which one representation completely eliminates a plausible alternative representation, except for deliberate efforts by the perceiver to reconstruct the pat ­ tern.

After the pattern is synthesized into an organizational whole, detailed processing of lo­ cal information proceeds. PPS divides the lines into segments of various curvatures and records junctions and angles at the same time. This processing is compatible with the results of ex­ perimental studies of the information content of lines and the manner in which they are processed. Hochberg (12) found that the eye fixates at points of discontinuity and at angles , while At­ tneave (13) showed that the information content of a contour is greatest at points where the con­ tour deviates from a straight line. Thus , in PPS all line components are expressed in the form of a code sequence of curve segments , angles and junctions. These components , together with their overall interconnected topological structure, constitute a complete description of a pattern.

Another important aspect of the greater flexibility and efficiency achieved by PPS in modelling perception is its information storage and retrieval processes, The retrieval and re­ cognition processes of PPS, in line with several respected hypotheses of visual memory (5)(14) , consist of two stages - primary and secondary. The former is a crude, wholistic and parallel "primary process," whereas the latter is an elaborate "secondary process" that includes deliberate manipulation of information by an ac­ tive agent. Thus, remembering is not only a pro­ cess of arousing "memory traces ," but also a con­ structive process making use of the stored infor­ mation to build something new - a method similar to the combination of preattentive and "analysis­ by-synthesis" processes noted in human perception (5).

In PPS the information structure of the pat­ tern universe (PU), containing the memory storage of pattern classes, and the organized description of a scene (D), are represented by a heterogene­ ous array with well-defined information fields. By using hash code techniques, detailed informa­ tion for each component in both arrays can be suppressed and reformed when necessary, whereas the joint occurrence of specific qualitative features (or partial characteristics) in each line component can be represented by a product of prime numbers known as the feature code and stored explicitly in both arrays. When a basic form has been segregated in D, with its feature characteristics extracted from the feature code, a parallel search process on the PU is performed to reduce the search space to a subset of PU con­ taining those pattern classes which share similar features with D in the basic form of their refer­ ence components. This search process, which op­ erates on the feature code, is efficient, paral­ lel and exhaustive, resembling the primary pro­ cessing of image recall. Besides this retrieval process of search for similarity, the patterns or subset of patterns stored can be called by a specific name or a class name. Regardless of the manner in which a subset of PU is called , the topological structure of D is subsequently com­ pared with each pattern cell of the subset se­ quentially, level by level, until a small subset of PU is retained for detailed analysis and com­ parison. Then, further details of components can be recalled and reformed by the hash code technique. A constructive process is then under­ way. Furthermore, if a certain subpattern of a scene is identified during the search, its rela­ tion to the other recognizable patterns or mean­ ingless subpatterns can also be deduced. Thus in PPS, identifying, interpreting, or classifying a pattern (or a group of patterns) involves

• (a) a crude parallel search of the memory,
• (b) a sequential search for structural similarity, and
• (c) a detailed synthesis and analysis pro­ cess after some images have been re­ called, (The synthesis or constructive process is more obvious when the ob­ jects being identified belong to the recursive pattern class,)

Functional Organization of PPS

The functional organization of PPS is shown schematically in Fig. 6, Here the major process­ ing units of the system are represented by round­ ed blocks, while the external and internal data are represented by square blocks. Rules or cri­ teria, external to the system, are enclosed in square brackets and some of the psychological counterparts are listed in quotations.

The Function TRACE

PPS accepts patterns that have been trans­ formed into a matrix representation , (Fig. 7), known as a field matrix, of l's and O's repre­ senting, respectively, the presence and absence of line sef"ents inside a mesh element. -Both the triangular and rectangular meshes are employed in PPS in the representation of a digitized pic­ ture, A function called TRACE traces along line segments according to several available rules. In PPS, the starting point of the trace process is arbitrary, * that is, no global syntax is re­ quired in the extraction of information from the field matrix, Components of the pattern are then encoded into a code string with junctions la­ belled and recorded. Thus , code strings are first recorded in terms of bearing segments (us­ ing the eight bearings to the eight immediately adjacent neighboring elements) and junction la­ bels are later reduced into sequences of curva­ ture, bearing and size triplets. These compon­ ent strings, together with a tentative structur­ al description, give the complete arbitrary des­ cription of the scene.

As an illustrative example , Fig. 7 is a complex pattern representing an apple outline interlinked to an enclosed character "3" shown with its associated field matrix. The field matrix is then processed and in this case the tip of the stem is chosen as the starting point. During the trace process , the function TRACE assigns separate labels to each junction, (VIZ. -2, -3, -4, -5, -6 in Fig. 8) according to the 6rder of trace. In addition to labelling , TRACE also records the junction type for each junction. Here , junctions -2, -3, -4, -5 and -6 are T-junctions , whereas -7 is an intersec­ tion. While tracing is in process , TRACE also records the bearing of each segment and encodes both the junction and bearing information in se­ quential codes, Figure 10 shows the code strings for all components. In terms of junction label and segment bearings, the code string of the apple stem is

-2 1 1 1 2

signifying that it has three segments in direc­ tion 1, one in direction 2 and terminates at the T-junction labelled as -2. This is then reduced to curvature, bearing and size triplets.

+A triangular scheme is under development for PPS which provides more segment orientation and makes the regeneration of the pattern from D more convenient,

*Except that the orientation and position should be recorded if the orientation and posi­ tion of the picture are desired.

In this example, one may note that the stem of the apple is chosen as the arbitrary reference and occupies level one of the tentative hierarchy. The apple outline thus assumes the second level as it has a junction (-2) in common with the stem. There are, in all, two third-level compon­ ents and one fourth-level component. Therefore, ·~ this arbitrary representation the following label notation is assumed

1 - reference component - stem

2 1 - second level component - apple outline

3 1 - third level component - T-junction with "3"

3 2 - .third level component - intersects with "3"

4 1 - fourth level component - character "3"

and the arbitrary topological descriptive string (ATDS) is as follows:

1 1 ~ (2 1 ~ (3 1 -j 4 1) ~ (3 2 X 4 1) ) .. [2)

with

X

=l ' ~

T- junctions.

Intersection of two components.

DoubleT-junctions of one component attaching to the other.

I Terminating component contained within a closed component.

Terminating component not contained within a closed component.

In the ATDS, each component is first listed and followed by pairs of < relation, component~ Thus, the component (1 1) has one pair and com­ ponent (2 1) has two relational pairs with com­ ponents (3 1) and (3 2), respectively.

Hence ,

A f-2 B

signifies that A attaches to Bat aT-junction, A being continuous and B terminating with B not enclosed in A. On the other hand ,

implies B is connected to A in a double T-junc­ tion with A continuous and B terminating, with B enclosed by the closed component A. With this tentative topological hierarchy, the ATDS with all its variables defined (i.e., (1 1), (2 1), etc.) contains all information required for the full description of the pattern.

The Function REORGANIZE

After the complete description of a pattern is stored i .n the system, PPS attempts to simulate the second level of the perceptive activities-­ the reorganization of the image into a meaning­ ful pattern according to various organizational criteria. As mentioned in the previous sections , one of the criteria PPS uses is organizational simplicity. With this criterion the unambiguous reference chosen is the apple outline, which is also the only closed component and has the great­ est length and number of junctions. Once a ref­ erence component is chosen, the function REOR­ GANIZE is able to transform the ATDS into a specific topological descriptive string, STDS, which is a specific topological description of the pattern.

In the previous example, the choice of a new reference would lead to a reorganization of the hierarchy as indicated by the following re­ assignment of hierarchical identifiers:

- apple outline

2 1 - intersecting arc

2 2 - stem

2 3 - connector between 113" and apple outline

3 1 - the number "3"

and the STDS would be

It should be noted that the hierarchical struc­ ture of the ATDS.contains four levels, while the STDS contains three. If we apply the simplicity criterion the ATDS yields an average hierarchical level of 2.6, while STDS has an average hierarch­ ical level of 2.0. Thus, as it should, the STDS displays a greater simplicity as measured by the simplicity criterion.

Although STDS contains the complete des­ cription of the pattern, it is transformed into a compact array for more efficient processing. This array, with well-defined information fields for each column, is called the description, D, of the pattern. The D resulting from STDS in Eq. [3] and component information from Fig. 7, is given in Fig. 10. In D, columns 1 and 2 comprise the referee label signifying the hier­ archical level and index of the component re­ spectively. In like manner , Columns 3 and 4 to­ gether are called the referent label , indicating to which component the referee is connected. Columns 1 through 4 are termed the linkage field as they list which components are linked. In D, special features of each component (such as "open-endedness," "self-intersection," etc.) are extracted and stored explicitly in terms of the product of prime numbers, each of the prime num­ bers represents a distinct component feature. This crude component feature information, ab­ stracted from each component string, is repre­ sented in a feature code (FC). A similar junc­ tion code (JC) describes the type of junction and the relations between the junction componen~.

FC and JC are stored in columns 5 and 6 of D re­ apectively. These codes will later be used to direct the extraction of a sub-universe of PU to reduce the search space in the recognition phase. In D, the detailed information of each component is not explicitly stored, but its corresponding hash code is stored in column 7 of D. The de­ tailed information is dumped to a "character pool" (a string of characters) and is recoverable (reconstructed) when detailed comparison of com­ ponents is required.

Pattern Class Generation

If an object pattern is distinct, unambigu­ ous and unique, such as a "circle," "square" or "apple," its representation in D can be trans­ ferred to the permanent memory storage to form the concept of square, circle or apple. In PPS, this permanent memory storage is known as the pattern universe, PU. The generation of a cell in the PU containing information which defines a class pattern is referred to as pattern class generation. Cells in the PU are modifiable. New cells can be added and old cells can be modified by adaptive learning or teaching by reinforce­ ment of local line forms or of the topological structure of the class pattern.

A class need not necessarily be named. If the pattern class of a PU cell is named, the hash code of the name will be stored in the name field (Fig. 11) and the cell can be recalled by name. If no name has been assigned, the cell can only be extracted by specific features existing in its reference or other components, or by simi­ larity of topological structure.

In general, the D of a stable pattern of fixed hierarchical structure is organizationally similar to its corresponding PU cell, except that the PU cell contains three additional col­ umn fields. They are: (a) class name field, (b) component status field, and (c) weighting factor field. In the PU cell, the component status field specifies the essential and non­ essential components comprising a pattern class definition. At the present stage, three types of status can be assigned in the component sta­ tus field. They are defined as follows:

Hence, in "cell-apple" of the PU in Fig. 11, the apple outline is essential and the stem is non-essential , but is not considered to be an object external to the pattern. This ~oncept is important in discerning an object embedded in a scene. Any additional part, attached to an iden­ tifiable object and not corresponding to a non­ essential component at its connection level, is considered to be external to the pattern. Hence , PPS is capable of determining how an identifiable pattern is related to another.

The weighting field in the PU cell contains the weighting factor, Wii' During adaptive learning it updates the tatio of the number of component occurrences to the number of similar patterns submitted. Hence, in PPS, the process of adaptive learning simply implies a continual matching of a set of given D's with their cor­ responding PU cell and a simultaneous modifica­ tion of the component weighting factors. If a threshold, e, is imposed on the weighting factor, a teaching scheme can be executed to modify the class concept (15). For instance, one can assign the following simple rule for adaptive learning based on an updated weighting factor,

A component of a D, assigned by name to a PU class, is inserted into the cell as non-essential if it fails to match any essential or non-essen­ tial components of the original class definition. If the new non-essential component occurs fre­ quently in subsequent D's, its corresponding Wi. in the PU cell increases. When W . > 9, its J status in the class definition be!Jmes essential. This happens when the class concept of a certain object is changing with time.

In the case of self-organization, the pat­ tern name might not be submitted to PPS. The generation of a class concept would then have to proceed through the identification phase . If a D matches all essential parts of a certain class pattern, it is assigned to the class. Additional information in that D then modifies the class by inserting non-essential components. If a certain component does not match in any PU cell, another class concept is introduced by the insertion of

a new PU cell derived from the D.

Like other syntax-directed analysis schemes. PPS can also handle a recursive definition of some simple pattern classes. In fact, PPS not only enables class to be defined in a recursive generative manner, but also enables a recursive class definition to be generated from an object that is composed of recursive components. The general strategy for collapsing similar or recur­

sive components is as follows :

1. Any connected set of components with a ter­ minator (a component which is not directly connected with a component of greater hier­ archal level than its own) is called a sub­ universe of D.

1. Subuniverses are specified by the number of distinct hierarchical levels they contain and the hierarchical level of the terminator.
2. During pattern class generation, subuniverses are generated component by component starting from a terminator (which is recognized in D as a referee having a lower level referent than itself).
3. By noting similarity in the linkage, feature and junction fields of D, topological simi­ larity of subuniverses can be recognized.
4. Topologically similar subuniverses which con­ tain terminators of the same hierarchical level can be collapsed into a subuniverse of an · identical structural class, allowing the inclusion of alternative terminators if necessary.
5. A pair of topologically similar subuniverses connected at corresponding components and whose terminators have different hierarchical levels is called a recursive realization,
6. By the use of certain rewriting rules, the pair displaying a recursive realization is combined into a recursive subuniverse with appropriate labels indicating a recursion pointer.
7. The same process is repeated until D cannot be reduced further.
8. The resulting D is then transferred to a pat­ tern cell which is called a recursion pattern class.

Figure 12 shows diagrammatically how a Mar­ kov t ype transformation is performed on a simple recursive pattern. The transformation continues until an irreducible recursive pattern class is obtained. Figure 13a shows diagrammatically a recursive realization at a certain stage of transformation; Figure 13b shows how the D is partitioned into such a realization and how sub­ se9.ue1,1t transformation is performed, (1* 1*) and (2" 1") are called a recursive pair, i.e., (2* 1*' will point to a component which can be recursive­ l y represented br t~e pattern identical to that subsequent to (1 1 ).

Conversely, the reverse productions can ex­ pand the recursive pattern class into an arbi­ trary version of a class,as well as recognizing objects that belong to the class.

Like all generative grammars , these produc­ tion rules have limitations in defining a speci­ fic class. The continuous refinement of this concept is one of the key objectives of PPS.

The Function RECOGNIZE

When a scene is transformed into a D with both the FC and the JC derived for each compon­ ent, a recalling process precedes the recogni­ tion and interpretation phases. The differen­ tial recalling process proceeds in the following manner:

1. Primitive forms (e.g., closed lines, open­ ended lines) are first recorded for subse­ quent processing. Each primitive form can be a center of focal attention and a poten­ tial candidate for a nucleation component about which a recognizable subpattern can be generated.
2. The primitive form of the least hierarchical level is processed first and continually ex­ pands to neighboring components as the iden­ tification process goes on.
3. The FC of the reference component is used to extract a subset of PU by searching in paral­ lel over the feature codes of the reference components of pattern cells. This yields a subset of PU for further matching.
4. Essential components , starting with those of least level , are then compared with the es­ sential components of the pattern cells with respect to linkage. feature and junction fields until a smaller subset of pattern cells is determined . This process continues until all essential components of a single PU cell or a subset of PU cells match the corresponding components in the subpattern of the D. Thus , at this stage. pattern classes with identified topological similari­ ty to some of the embedded objects in the D are identified. Further detailed search for local form match then continues.
5. The string code of each essential component is reconstructed using a hash code function. The string matching is performed by a scheme modified from the matching of genetic codes , developed by one of the authors (16)(17). Hence, both perfect match and partial match are performed, The former indicates the components are identical , while the latter implies the identification is fuzzy.
6. The same process is repeated for other primi­ tive forms unless they have been included in the essential part of the previously identi­ fied object, Components that do not belong to the non-essential part of the PU cell are considered as external to the object.

In the "apple-3" case, the apple outline and the character "3" are identified from their FC as primitive forms. Since the apple outline is at the least level, it is processed first and is found to match the essential component in the apple PU cell, whereas, the stem matches only the non-essential component and hence., is con­ sidered as part of the apple. The "3" is then identified in a like manner. The inersecting arc and the connector, in this case, do not match any of the non-essential parts in the apple PU cell or the "3" PU cell and will be considered as external and connecting. Thus, both the identification of embedded objects as well as the interpretation of their connections are com­ plete.

Conclusions

This paper has presented both the conceptual framework and a partial implementation of PPS. Although crude patterns such as the "apple-3" have been processed, some of the processing meth­ ods and concepts await further refinement. The manipulation and reproduction phases (see Fig. 6) are based on the triangular mesh scheme. The former phase involves the construction of a set of functions that can deform or transform com­ ponents of an object D. The latter phase then reproduces the results in another field matrix.

Although PPS is oriented towards developing computer visual perception, it should be men­ tioned that the information structures and pro­ cessing methodology developed can be applied to other data structures which are multi-linked.

Acknowledgement

This research is based on the doctoral dissertation of Edward L. Morofsky who was sup­ ported by the National Defense Education Act and the National Science Foundation at Carnegie­ Mellon University.