CNN'92

Symmetry Properties of Cellular Neural Networks on Square and Hexagonal Grids

Gerhard Seiler and Josef A. Nossek

Technische Universitat Munchen Lehrstuhl fur Netzwerktheorie und Schaltungstechnik

Arcisstr. 21, D-W-8000 Munchen 2, Germany Tel.: '49-89-2105 8512; Fax.: '49-89-2105 8504;

E-mail: geseG3nws.e-technik.tu-muenchen.de

Abstract Symmetry properties of cellular neural networks on square and hexagonal grids are investi- gated: While the symmetry inherent in a given problem should be reflected in the structure of a CNN designed to solve it, the degree of symmetry possible in the network is limited to the symmetry group of the grid it is defined on. The exact numbers of independently choosable entries in both square and hexagonal CNN-templates with different important kinds of symme- try are compared. As expected, the higher symmetry of the hexagonal grid leads to a significant reduction in the complexity of the templates.

1) Introduction In technology, sampling of spatial information is done on square grids. Nature, on the other hand, organizes its information processing elements in hexagonal arrays. Although the evolu- tionary success of this arrangement is probably due to the fact that it corresponds to the densest packing of circles in the plane, which arises naturally during cell growth on surfaces, it may also simply be better suited for many problems because of its higher degree of symmetry. In Cellular neural networks or CNNs as introduced by Chua and Yang [l], processing ele- ments are also often arranged Li a regular grid, and programming for a particular task is done by choosing a set of parameters which are arranged as a regular template. As will be shown, symmetrical tasks pose more smngent constraints on hexagonal templates than on square ones. In practice, this means that hexagonal systems may be easier to build. Symmetry may also be introduced as a design constraint in a more direct design method such as the one proposed in P I .

2) Coordinate Systems and Neighbourhoods On both grids, coordinate systems must be introduced. To eliminate boundary problems, the grids are supposed to be infinite and plane-filling.

Let ,5G be the square grid with the Cartesian coordinate system, as shown in Fig. 1. Individual cells are denoted by C(i, j), where i is the row index and j is the column index.

The r-neighbourhood NS(i, j) of a cell C(i, j) in SG, r E N being a positive integer and the superscript s denoting the square grid SG. is defined as in [ 11 as the following set of cells:

(1) Ns(i, j) := { C(k, 1) I max (b - 4, 11 -I) I r). In order to simplify notation, we will also allow neighbourhoods of coordinate pairs.

0-7803-0875-1192 $3.00 0 1 9921EEE 258

1

3

4

3) Symmetrical Problems Symmetry is the inviriance of an object under a group of actions. The symmetry groups of most image processing problems are continuous Liegroups. In electrical engineering systems, however, image data is sampled before being processed on a discrete grid, which leads at best to a discrete subgroup of the original Lie-group. Still, the symmetry inherent in an image processing problem should be reflected as closely as possible by structural symmetry of the processing array.

- 1 . 1 1.2 1,3 1,4

3 , l 3,2 3 ,3 3,4

4, 1 4 ,2 4 3 4,4

3.1) Space Invariance Let M be some space and T(M) the largest group of translations that leaves the structure of M unchanged. Then any image processing problem posed in M that is invariant under T(M) is space-invariant.

The translation group T(R2) of the real plane R2 is simply given by

259

The translation groups T(S9 and T(Y@ are isomorphic to T(Z*), the restriction of T(R2) to the integer lattice Z2, which performs only integer offsets:

T(Z2) = (tr: Z2 -+ Z2 I tr(i, j) = (i + Ai, j + Aj) A Ai, Aj E Z). (4)

Space invariance of the connection coefficients a" 1, implies:

(5) k, 1 - k+Ai. 1+Aj v ~ i , ~j E Z. i+Ai, j+Aj j a . . - a

1.J

The connection coefficients in space invariant CNNs therefore depend only on the cells' relative positions. This allows a description in terms of relative positions, the templures defined in [l]:

a(Ai, Aj) := ai* li+Ai, j+Aj t/ i, j, Ai, Aj E Z.

rmk = min (r I (a(i, j) = o v (i, j) e NAO, 0))).

(6)

If interactions are local, a unique minimal Neighbourhood N,(O, 0) of the template's origin (0, 0) with minimal f i t e rmin exists, which contains all non-zero coupling coefficients:

(7)

A template a(i, j) whose elements are only specified for (i, j) E N,(O, 0) (and which is assumed to be zero elsewhere) is called an r-template.

The numbers ns(r) and nh(r) of entries in square and hexagonal r-templates are simply

ns(r) = IN:(O, 01 = (2r + 1)2 = 4r2 + 4r + 1, (8)

nh(r) = )N,h(O, O)/ = 1 + 6 i = 1 + 3 r (r + 1) = 3r2 + 3r + 1. (9) i = l

For large r, a hexagonal r-template contains 25% less elements than a square one for the same r.

3.2) Isotropy Let M be some space, and R(M) the largest rotational symmetry group of the neighbourhocds defined in M. Then any space invariant problem defined on M that is also invariant under R(M) is isotropical.

The n-element rotation group Cn consists of all n rotations about integer multiples of+ 3600,

where E is the unit element and the smallest clockwise rotation e') generates the group:

cj;'+') := cc,l)o e), i E {I, 2, ..., n - 11,

C',) = E. (12)

(11)

Group theary proves, that the invariance of any object under the generators of a group implies its invariance under the whole group. The invariance of a square template under its rotational symmetry group R(Nf(0, 0)) = C4 is consequently implied by its invariance under Cy), whose action is defined by

CY): a(i, j) + au, -i). (13)

260

Thus, a necessary and sufficient condition for isotropy of square r-templates is

a(i, j) = a(i, -i) V (i, j) E NXO, 0). (14)

As (0,O) is the only fixed point of C y ) , and all other template entries are mapped on and are therefore identical to exactly thzee others, the number ni(r) of independently choosable elements on isotropical square r-templates is given by

ns(r) - 1 nT(r) = 1 + - - r 2 + r + - 1. 4 (15)

Similarly, a hexagonal template is invariant under its rotational symmetry group R(N!(O, 0)) = c6, if and only if it is invariant under dt ’, whose action in 9-& is defined by

CY): a(i, j) + a(i + j, -i). (16) A necessary and sufficient conmtion for isotropy of hexagonal r-templates is therefore

a(i, j) = a(i + j, -i) V (i, j) E N,h(O, 0). (17)

As (0,O) is the only fixed point of e’, and all other template enmes correspond to five others, the number nF(r) of independently choosable entries in isotropical hexagonal r-templates is

For large r, isotropical hexagonal r-templates contain only about half as many independent er.tries as square ones.

3.3) Complete Symmetry Let M be some space, and S(M) the (maximal) symmetry group of the neighbourhoods defined in M. Then a space invariant problem on M that is also invariant under S(M) is completely symmetrical. The symmetry group Cnv of a regular n-sided polygon consists of Cn and n reflections:

(19) c n v = G u ( o n (0) 3 o n (1) 9 .-.I o n (n - U} - If n is even, the reflections are defined by the orientation of their axes as follows:

All axes contain (0, 0),

4’) is horizontal,

+ is obtained from 4) by tilting it 180’ clockwise around (0,O).

By construction, Cnv is shown to be generated by 4’) and 4’). First,

cp := o(p 0 a’,O’, (20) which generates the subgroup Cn of Cnv as shown in (10) to (12). The other reflections are then obtained as follows:

0 ’ , 2 ’ ~ : = C ( ~ ) o o ( , ~ ~ o ~ - i ) , i E I 1, ..., $1, (21)

261

4 2 i + 1) := c$) o 41) o e-’), i E { I , ..., ;}. (22)

Hence, a template is completely symmetrical iff it is invariant under ofo) and of’) on its grid.

The symmetry axes of square templates are shown in Fig. 2. The actions of 02) and 0:) on square templates are defined by:

0:): a(i, j> + a(-i, j), (23)

oy): a(i. j) + a(i, i). A square template is therefore completely symmetrical, if and only if

a(i, j) = a(--i, j) A a(i, j) = a(i, i) V (i, j) E w(O, 0). (25) The number n&(r) of independent entries in a completely symmetrical square r-template is

Fig. 2: Possible symmetry axes of square templates (left) and hexagonal (right) templates.

Similarly, Fig. 2 also shows the symmetry axes of hexagonal templates. In hexagonal coordi- nates, the actions of or’ and 0;’ are defined by

0:): a(i, j) + a(-i, i + j), 0:’: a(i, j) + a(i, i),

(27)

(28) and consequently a hexagonal template is completely symmetrical if and only if

a(i, j) = a(-i, i + j) A a(i, j) = a(i, i) b’ (i, j) E NF(0, 0). (29) As the odd numbered axes intersect cells at even distances from the center, but run betwmn pairs of cells at odd distances, one best constructs different formulas for the number n&(r) of independent entries in completely symmetrical hexagonal r-templates for odd and even r:

(1 + n k s ( r h r = 2 i=y(y+1)=$(r2+4r+3)=-+r+1, r2- 1 (30)

4 i = 1

262

With the Gaul3 bracket [I: R -+ 2, which yields the largest integer smaller than or equal to its argument, one observes that, for odd r,

unrestricted

isotropical

completely symmetrical

which allows us to merge (30) and (31) into a Single final formula for n!&(r):

n&+(r) = - + r + 1. (33) E1 For large r, completely symmeaical hexagonal r-templates contain only about half as many independent entries as the corresponding square ones. Also, the total number of independent elements is much smaller than in the isompical case.

square hexagonal

3r2 + 3r + 1

r 2 + r : 1

4r2 + 4r + 1

r 2 + r + 1 2

[$ + r + 1 2

4) Conclusion For reference purposes, the results on the total numbers of independent entries in unrestricted, isotropical and completely symmetrical square. and hexagonal templates are m p i l e d in Table 1.

References

[ 13

[2]

[3]

L. 0. Chua and L. Yang. "Cellular Neural Networks: Theory", IEEE Trans. CAS 35,

G. Seiler, A. J. Schuler and J. A. Nossek, Design of Robust Cellular Neural Networks, report TIM-LNS-TR-91-13, Technische Universitst Miinchen (1990)

J. A. Nossek, G. Seiler, T. Roska and L. 0. Chua, "Cellular Neural Networks: Theory and Circuit Design", Int. Journal of Circuit Theory atid Appl., to be published in 1992

1257-1272 (1988)

263