2004 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'04)
Hawaii, USA, Mar. 5-7, 2004.

On Two Types of Network Topologies of Small-World Cellular Neural Networks
Kazuya TSURUTA, Zonghuang YANG, Yoshifumi NISHIO and Akio USHIDA
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470
FAX:+81-88-656-7471
Email: tsuruta@ee.tokushima-u.ac.jp

1. Introduction

which is the same topology as SWCNN in [6].
The Added SWCNN is obtained by just adding some random couplings between cells in the original Chua-Yang CNN.
We introduce a probability pc , which means what percentageof the cells in the CNN occur to random coupling to anothercell. We assume that, besides its local couplings, each cell in
the array is only permitted a maximum of one random coupling to another cell. Thereby, for a M × N array, it has amaximum pc of M × N/2 pairs of cell couplings. Figure
1 shows a sketch map of the SWCNN consisting of 4 × 4
cells. Obviously, when pc = 0, the SWCNN is completely
the same with the original CNNs, and the maps correponding
to 0 < pc < 1 and pc = 1 are respectively shown in the
middle part and the right hand side of Fig. 1.

Studies of network map are very important, because they
help us to understand the basic features and requirements ofvarious systems. So far many connection topologies of network assumed to be either completely regular or completely
random have been studied in the past. Cellular Neural Network (CNN) model invented by Chua and Yang in 1988 [1]is a typical of those completely local connectivities, which ispresented as a preferred implementation of locally and regularly coupled neural networks. The CNN has been successfully used for various high-speed parallel signals processing
applications such as image processing, pattern recognition as
well as modeling of various phenomena in nonlinear systems[1]-[4]. However, in many cases in real life, many network
topologies such as biological, technological and social networks are known to be not completely random nor completely
local but somewhere in between. This was modeled in an interesting work by Watts and Strogatz in 1998 [5] as the smallworld model. The model is a network consisting of many local links and fewer long range ‘short cuts’. Therefore, it has
a high clustering coefficient like regular lattices and a short
pc=0
pc=1
characteristic path length of typical random networks. InterIncreasing randomness
esting examples are shown by collaboration of movie stars,
connectivity of internet web pages or neural nets, etc.
Figure 1: Added SWCNN architecture.
Recently, the authors have proposed Small-World Cellular
Neural Network (SWCNN) [6], which is constructed by introThe state equation of each cell c(i, j) of the SWCNN isducing some random couplings between cells of the original formulated by Eq. (1), and the output equation is defined by
Chua-Yang CNN. In [6] we have reported some basic results Eq. (2).
using the concept of SWCNN. In this article, we propose two
types of network topologies of the SWCNN and investigateẋij (t) = −xij (t)X+I
the features of the two SWCNNs.
+
A(i, j; k, l)ykl (t)c(k,l)∈Nr (i,j)

X

2. Network Topologies of SWCNN+

In this section, we describe the two types of the connection
topology of the SWCNN composed of a two-dimensional M
by N array structure.

+ wc M (i, j; p, q)ypq (t)The first network topology is named as “Added SWCNN”,- 113 -

(1)c(k,l)∈Nr (i,j)

yij (t) =2.1. Added SWCNN

B(i, j; k, l)ukl (t)1(|xij (t) + 1| − |xij (t) − 1|)2

i = 1, 2, ..., M, j = 1, 2, ..., N.

(2)where Nr (i, j) denotes the neighbor cells of radius r of acell c(i, j); A, B, and I are real constants called as feedback
template, control template and bias current, respectively; xij ,yij , uij denotes the state, input and output of the cell, respectively; M (i, j; p, q) describes the small-world map thatis randomly created by program with indicating the probability pc in advance, if there is a coupling between one cellc(i, j) and another cell c(p, q), then the M (i, j; p, q) is equal
to 1, otherwise is zero; and wc stands for the coupling weight
between the randomly coupled cells.
In order to investigate the features of the network, we calculated the characteristic path length L(pc ) and the clustering coefficient C(pc ) as varying pc . The characteristic path
length L(pc ) is defined as the number of edges in the shortest path between two vertices, averaged over all pairs of vertices [5]. The clustering coefficient C(pc ) is defined as follows; Suppose that a vertex v has kv neighbours; then at mostkv (kv − 1)/2 edges can exist between them. Let Cv denotethat fraction of these allowable edges that actually exist. Define C(pc ) as the average of Cv over all v [5].

in the Ref. [5]. Figure 3 shows a sketch map of the Rewired
SWCNN consisting of 4 × 4 cells.

pc=0

pc=1
Increasing randomness

Figure 3: Rewired SWCNN architecture.
The characteristic path length L(pc ) and the clustering coefficient C(pc ) are calculated in Fig. 4. The decrease of theclustering coefficient is quicker than the Added SWCNN.
However, the same restriction of the one cell with one short
cut makes the difference between the two networks small.
1.2

C(pc)/C(0)L(pc)/L(0)
1.0

1.2

C(pc)/C(0)L(pc)/L(0)
1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0
0.0001

0.2

0.001

0.01

0.1

1

pc
0
0.0001

0.001

0.01

0.1

1

Figure 4: Characteristic path length and clustering coefficientof Rewired SWCNN.

pc

Figure 2: Characteristic path length and clustering coefficientof Added SWCNN.
The results are shown in Fig. 2. Because we make a restriction such that one cell has at most one random coupling, theclustering coefficient does not approach zero even if pc becomes 1.0. However, the characteristic path length becomesshorter and the network possesses the feature of the smallworld networks.

3. APPLYING TO IMAGE PROCESSING
Image processing is one of important applications of the
CNN. As well known, many templates and algorithms used
for this purpose have been developed. In this section, we investigate the effect of applying the two types of SWCNNs toexisting image processing applications.
3.1. Gray-scale edge detection

2.2. Rewired SWCNN
The second network topology is named as “Rewired
SWCNN”.
The Rewired SWCNN is obtained by rewiring somecouplings between cells in the original Chua-Yang CNN.
Namely, we choose a cell and a coupling that connects it to
its nearest neighbour. We reconnect this coupling to anothercell chosen at random over the whole network. We repeat thisprocess for all cells with the probability pc . As a result, we
get a map which is more similar to the small-world network

The edge detection extracts edges of objects in a binary
image where each black pixel with at least one white nearest
neighbor is defined to be an edge cell. The template (3) isdesigned to work well for binary input images only.


0
A= 0
0

- 114 -

0
1
0


0
0 ,
0



−1
B =  −1
−1

−1
8
−1


−1
−1  , I = −1.
−1(3)

If the input image is a gray-scale image, the output may not
be a binary image, and will in general be gray-scale where
black pixels correspond to sharp edges, near-black pixels correspond to fuzzy edges, and near-white pixels correspond tonoise. The simulation result is shown in Fig. 5. Figure 5(a)is the input gray-scale image. Figure 5(b) is the output image
obtained by the original CNN. We apply the same input image to the SWCNN with different random coupling probabilities. Under the above template (3) and the random couplingweight wc = −0.5, the simulation results are shown in Figs.
5(c) and (d), which correspond to the coupling probabilities
pc = 0.5 and 1.0, respectively. Note that the Added SWCNN
and the Rewired SWCNN give the same output image for thistask, because the A template has the non-zero value only inthe center.
We observe from the simulations that the SWCNN can detect some edges such as the pillar in the left hand side of
the image, the pattern of the hat, the face characters, etc.
that can not be detected by the original CNN by using the
SWCNN. Moreover, the ability of the edge detection become
higher with the probability increases. Therefore, we can conclude from these simulation results that the application of the
SWCNN to the gray-scale edge detection problem could improve the efficiency of the original CNN.

contours in a binary image. This temple is shown as follows.




0 1 0
0 0 0
A =  1 3 1  , B =  0 4 0  , I = −1.
0 1 0
0 0 0
(4)
This is a propagating template, the computing time is proportional to the length of the image.
Simulated results are shown in Figs. 6 and 7. For thistask, the original CNN and the Added SWCNN work well as
Fig. 6. However, the Rewired SWCNN can not work as Fig. 7
because of the lack of the designed template values.

(a)

(b)

Figure 6: Hole-filling by original CNN and Added SWCNN.
(a) Input image. (b) Output image.

(a)

(b)

(a)

(b)

Figure 7: Hole-filling by Rewired SWCNN with pc =0.01 andwc =-0.9. (a) Output image after 5 sec. (b) Output image afterconvergence.
(c)

(d)

In order to evaluate the ability of the SWCNN, we investigated the convergence speed of the CNNs for this task. The
result is shown in Fig. 8. From the figure, we can say that
Figure 5: Gray-scale edge detection. (a) Input and initial state the Added SWCNN converges more quicker than the original
image. (b) Output image by the original CNN. (c)-(d) Output CNN. The behavior of the Rewired SWCNN is different fromimages by SWCNN with p = 0.5 and 1.0.
the others, because the network settles down to the different
output.
3.3. Smoothing with binary output
3.2. Hole-filling

The output image obtained by this template is a binary image where black (white) pixels correspond to the locations in
Hole-filling is defined as filling the interior of all closed an initial state image where the average of pixels intensities- 115 -

140
Original CNN
Added SWCNN
Rewired SWCNN

120
100

∆x

80
60

(a)

40

(b)

20

Figure 10: Smoothing by Added SWCNN. (a) pc =0.1 and
wc =0.5. (b) pc =1.0 and wc = 0.5.

0
0

10

20

30

40

50
Time

60

70

80

90

100

Figure 8: Convergence speed of the three CNNs (pc =1.0,
wc =-0.9).
over the r=1 feedback convolution window is positive (negative).




0 1 0
0 0 0
A =  1 2 1  , B =  0 0 0  , I = 0.
0 1 0
0 0 0

(a)

(b)

(5) Figure 11: Smoothing by Rewired SWCNN. (a) pc =0.1 and
wc =0.5. (b) pc =0.5 and wc = 0.5.
We carried out computer simulations of the three CNNs
with this template. Figure 9(a) shows the input image andplates designed for the original CNN, the obtained outputs
9(b) shows the output image by the orignal CNN. Figure
were not sufficient for the tasks. However, we confirmed that
10 shows the outputs obtained by the Added SWCNN with
the SWCNN could improve the convergence speed and could
different pc . Figure 11 shows the outputs obtained by theachieve the different image processing tasks.
Rewired SWCNN with different pc . We can observe that
Our important future researchs are design of the template
the Added SWCNN works similarly to the original CNN but
for the SWCNN, investigations of the convergence speed of
the outputs of the Rewired SWCNN look like the images obthe SWCNN, and analysis of the stability of the SWCNN.
tained by different templates.
References[1] L.O. Chua and L. Yang, “Cellular neural networks: theory andapplications,” IEEE Trans. Circuits & Syst., vol.35 pp.12571290, Oct. 1988.
[2] L.O. Chua and T. Roska, “The CNN paradigm,” IEEE Trans.
Circuits & Syst., vol.40, pp.147-156, Mar. 1993.

(a)

(b)

Figure 9: Smoothing by original CNN. (a) Input image. (b)Output image.

4. CONCLUSIONSIn this article, we have proposed two types of network
topologies of the SWCNN and investigate the features of the
two SWCNNs. We have applied the two SWCNN to several basic image processings. Because we used the tem-[3] T. Roska, L. Kék, L. Nemes, A. Zarandy and P. Szolgay “CNN
software LIBRARY: templates and algorithms”, Version7.3,
Analogical and Neural Computing Laboratory, Computer andAutomation Institute, Hungarian Academy of Sciences, 1999.
[4] Z. Yang, Y. Nishio and A. Ushida, “Image processing of twolayer CNNs – applications and their stability –,” IEICE Trans.
Fundamentals, vol.E85-A, no.9, pp.2052-2060, Sep. 2002.
[5] D.J. Watts and S.H. Strogatz, “Collective dynamics of smallworld networks”, Nature 393, pp.440-442, 1998.
[6] K. Tsuruta, Z. Yang, Y. Nishio and A. Ushida, “Small-world
cellular neural networks for image processing applications,”
Proceedings of ECCTD’03, vol.1, pp.225-228, Sep. 2003.

- 116 -