CELL-SHEDDING TRANSFORMATIONS, EQUIVALENCE-RELATIONS, AND SIMILARITY MEASURES FOR SQUARE-CELL CONFIGURATIONS

A family of related techniques for the reduction of square-cell config urations (''animals'') to simpler ones by cell-shedding processes prov ide physically motivated, novel approaches for shape characterization and similarity criteria as well as similarity measures based on equiva lence relations. The two main algorithms, cs(k), k = 1, 2, involve the simultaneous ''shedding'' of all cells having precisely k sides expos ed on the periphery of the animal; the shedding steps are repeated as long as the resulting structure is an animal. Since the termination cr iteria of these two algorithms are different, they can be combined seq uentially into composite algorithms, leading to various alternative sh ape characterizations and equivalence relations. The third main algori thm, cs(32), involves incomplete elimination of peripheral cells of a given type, thus retaining some additional local shape features inheri ted from the original animal. Following the introduction of these tran sformations, some of their properties are derived and several examples are discussed. (C) 1997 John Wiley & Sons, Inc.