Time multiplexing CNN simulator using RK7(5)

1,2

Osama H. Abdelwahed

1
2

and M. El-Sayed Wahed

Mathematics Department, Faculty of Science, Suez Canal University, Egypt

Department of Computer Science, Faculty of Computers and Informatics, Suez Canal University, Egypt

-************************Abstract

RK7(5) is a numerical method was used to minimize the local truncation error using selection step size algorithm.
Time multiplexing CNN simulator was modied using RK7(5) to improve the performance of the simulator and the
quality of the output image for edge detection. The results showed better performance than those in the literature.
Keywords Cellular neural network; Image processing; CNN simulator; RK7(5); Local truncation error
-************************-

Introduction

section (2) presented CNN in details. In Section (3)

time multiplexing CNN simulator was discussed.
Edge detection is considered to be one of the essential Section (4) presented the proposed method. Results of
steps in identifying an object in image processing. Many the performance of the simulator and edge detection
techniques have been proposed to detect edges in image were discussed in section (5). Section 6 discussed the
processing using cellular neural network(CNN) [8]. CNN Conclusion.
was introduced by Chua and Yang [3] in 1988. The main
properties of CNN are their local interactions among their
2
Overview of CNN
nearby cells in addition to their parallel processing which
is considered to be one of the most important aspects in Cellular neural network is a method used both the conCNN. CNN has many applications in image processing cepts of neural networks and cellular automata in which
like medical image segmentation, image denoising, and its cells are connected locally through their neighbors and
edge detection. Time multiplexing CNN simulator was processed in parallel through their interactions [3].
proposed by C.C. Lee and Jose Pineda de Gyvez [6] in
The r-neighborhood of CNN is dened as in the follow1994. They used the numerical integration algorithms ing:
Euler, the improved Euler and Runge Kutta method to
solve the dierential equations which represent CNN.
Nr (i, j) = {C(k, l)} | max
{|k i| , |l j|} r,
Their results for edge detection need to be improved and
i=1,M ;j=1,N
also the computation time need to be decreased. Another
(1)
work presented by V. Murugesh and K. Murugesan[8].
Where r > 0.
They introduced the numerical methods, RK-Gill [10]
The expression "1 neighborhood" is expressed for
and RK-Butcher [1, 2, 7], but unfortunately, the obtained r = 1, " 2 neighborhood" is expressed for r = 2, "3
results need to be improved. So we proposed RK7(5) neighborhood" is expressed for r = 3, etc. as illustrated
[12] as a numerical integration method used to minimize in Fig. (1).
the local truncation error using the selection step size
algorithm [11]. Our proposed method showed better
results than those in the literature. The obtained results
included both faster performance and better edge detection.
RK7(5) is proposed to achieve two targets: First, to
increase the eciency of the time multiplexing CNN
simulator by decreasing the needed simulation time; (a) 1 neighbor(b) 2 neighbor(c) 3 neighborhood
hood
Second, to improve the quality of the edge detection hood
results. The organization of the paper is as follows:
Figure 1: Examples of r neighborhood

Page 171

A two dimensional CNN with size equal to 4 has shown

in Fig. (2), where each cell has interactions with its nearby
cells locally for the 1 neighborhood case.

X
dxij
(t) = xij (t) +
A(i; j; k, l)ykl (t)+
dt
C(k,l)
X
B(i; j; k, l)ukl (t) + Iij

(6)

C(k,l)

The dierent values of the templates A and B and the

bias value I determines the type of application used in
CNN. For example, edge detection, noise removal, or pattern recognition has dierent template values.
The templates of CNN are space invariant i.e. for example the template B(i, j; i + 1, j) is the same for all values
at (i, j).

Time Multipexing CNN simulator

Figure 2: CNN structure with size = 4

The time multiplexing CNN simulator [6] was proposed

to solve the problem of hardware implementation. From
The most important operators in CNN are the tem- hardware point of view, may be there are thousands of
plates A and B which represent the output feedback and pixels need to be implemented using the single layer CNN
the input control respectively. They control the behavior simulator [5]. It is very dicult to manage this problem
because of the limitation of the hardware. Hence the time
of CNN in addition to the bias value I .
According to [3], the CNN equation is represented as in multiplexing algorithm was proposed to x this complex
problem by dividing the input image into a number of subthe following:
images whose size equal to to the size of the block of CNN
processors. In this case, each block will process a subimage using single layer CNN simulator till it converges.
X
The algorithm continues for the next sub-images using the
dxij
1
C
(t) =
xij (t) +
A(i; j; k, l)ykl (t)+
same procedure till the whole image will be processed [6].
dt
Rx
C(k,l)
Although the algorithm succeeded to solve the problem of
X
B(i; j; k, l)ukl (t) + Iij (2) the hardware limitation, some side eects appeared. The
border pixels for each sub-image have incorrect results beC(k,l)
cause there is no information for the neighbors which reIyx controls the behavior of the following output function sults in two erroneous values. The rst error is occurred
because of the eect of the template B. This error is comyij :
puted using the following formula [9]:

f (x) =

1
(|x + 1| |x 1|)
2

(3)

B
Eij
=

3
X

bi,j+1 sign (ui,j+1 )

(7)

i=1

Where,

Iyx

1
=
f (xij )
Ry

(4)

The output function yij = Iyx Ry can represented as in

the following:

yij = f (xij (t)) =

1
(|xij (t) + 1| |xij (t) 1|)
2

(5)

The general form of CNN dynamics is represented by

the following equation:

Where bi,j+1 represents the values missed by using the

template B due to the absence of the input signals ui,j+1 .
And sign() is the sign function which is used to represent
the pixel status either black or white. This error depends
on the input image and the template value.
The second error appeared as a result of the eect of the
template A. This error is evaluated using the following
equation:
A
Eij
=

3
X

ai,j+1 yi,j+1 (t)

(8)

i=1

Since ai,j+1 is the error obtained due to the template A

Page 172

because of the absence of the values of yi,j+1 (t).

B
A
To minimize the errors Eij
and Eij
, we exploit the
advantage of CNN in which there is a local interaction
B
among neighboring cells. First, to minimize the error, Eij
, we chose a belt of pixels from the input image equals
to the radius of the neighborhood of CNN around each
A
sub-image. Second to minimize the error, Eij
, the pixels
between adjacent sub-images were overlapped and each
cell in the border can interact with its neighbors as interior cells. The minimum overlap width is twice of the
neighborhood's radius of the CNN [9].
Although overlap property improved the interaction
among neighboring cells, the simulation time increased.
Fortunately, the big chance of having the pixels of each
sub-image all black or all white helped in reducing the
simulation time nearly to the time consumed in the case
of using single layer CNN simulator. Since all black-block
or all white-block will be simulated one time, after convergence all nal states were saved in the memory. Every
time all black-block or all white-block encountered again ,
their nal states are just restored from the memory since
there is no need for simulation again. The structure of
time multiplexing CNN simulator is demonstrated in Fig.
(3).

5. For each block, apply single layer CNN simulator [6]:

(a) Read block C

(b) Process all black-blocks or all white-blocks once
and after convergence, store their state values in
the memory
(c) for each black or white block encountered again,
just restore its state values from the memory
(d) If the block didn't converge yet, compute its new
state values using the equation (6) by applying
RK7(5)
(e) If the new state values are not the nal states(
didn't converge), go to (a)
A
B
(f) Compute the error tolerance Eij
and Eij
for the
templates A and B respectively for block C .

6. End
The most important point of the above steps will be the
proposed numerical integration algorithm RK7(5) that
will be presented in section (4.1). The main purpose of
this algorithm is to reduce the CPU time or simulation
time and to improve the edge detection results.

4
Figure 3: The structure of time multiplexing CNN simulator [9]

The steps of the time multiplexing CNN algorithm [9]

with RK7(5) are summarized as follows:
1. Read input image
2. Divide the input image into a number of m blocks

The numerical integration methods

Euler, RK-Gill [10] and RK-Butcher [1, 2] are three

numerical integration methods used in the literature to
solve the non linear dierential equations which represent
CNN dynamics. Section (4.1 ) discussed the proposed
numerical integration algorithm RK7(5).

4.1

The numerical integration method

RK7(5)

RK7(5) [12] was proposed as a new technique used in

3. Construct for each block, a belt of cells around it with
size equal to the radius of the neighborhood from the the time multiplexing CNN simulator[9] to improve the
performance of the time multiplexing CNN simulator
input image
and edge detection results. The algorithm is based
4. Between each two blocks construct an overlapped cells on minimizing the local truncation error and choosing
with size equal to the twice of the radius of the neigh- an adaptive step size value using the selection step size
borhood
algorithm. The equations of RK7(5) [12] are shown below:

Page 173

k1ij = f (xij (n ))
1 ij
k
18 1
0
1
k3ij = f (xij (n )) + k1ij
9
0
1
1
k4ij = f (xij (n )) + k1ij + k2ij
24
8
0
2183971
k5ij = f (xij (n )) +
k ij
4000000 1
8340813 ij 3968421 ij
k +
k

4000000 3
2000000 4
0
695768212 ij
k6ij = f (xij (n ))
k
746374411 1
1803549175 ij 3474507053 ij

k +
k
7007942496 3
6790877290 4
2188198899 ij
+
k
15264927763 5
0
118949348557 ij
k
k7ij = f (xij (n ))
8390623634 1
53094780276 ij 8415376229 ij
+
k
k
9800512003 3
2277049503 4
18647567697 ij 275514944893 ij

k +
k
10138317907 5
11905950217 6
0
30828057951 ij
k
k8ij = f (xij (n ))
7654644085 1
4511704 ij 16217851618 ij

k +
k
324729 3
1651177175 4
282768186839 ij 104400780537 ij
+
k
k
40694064384 5
15869257619 6
5409241639 ij
k
+
9600177208 7
0
133775720546 ij
k9ij = f (xij (n ))
k
26753383835 1
49608695511 ij 5989647201 ij
k
k
+
4066590848 3
7901259813 4
48035527651 ij 86266718551 ij

k +
k
5727379426 5
10188951048 6
7751618114 ij 2289274942 ij

k +
k
23575802495 7
8464405725 8
0

k2ij = f (xij (n )) +

The algorithm divides the input image into blocks

and single layer CNN simulator is applied for each
block. According to [4], The step size,h of p(q)order
RK methods is computed using the error per unit step
(EPUS) [11] by using the following equation:


hn+1 = f1 hn

tolerance
errn

1
 q+1

(10)

Where f1 is the factor of safety and hn+1 = xn+1 xn

is evaluated according to the estimation of errn which is
approximated using the equation[4]:

errn '

yn yn
hn

(11)

Since yn and yn are the estimated solutions of order pth

and qth respectively.
And tolerance represents the required tolerance.
If errn+1 tolerance, then yn+1 is applied otherwise,
Eq. (10) is recalculated by errn errn+1 .
So we propose Rk7(5) to get better results than those
in the literature by reducing the computation time and
improving the edge detection.

Simulation Results

The input image which is used for testing is the Mona Lisa
image. The edge detection results are shown in Fig. (4).
The input image and the edge detection results are shown
in Fig. (4a) and Fig. (4b) respectively.

The solution of RK7(5) is given below:

597988726 ij
k +
12374436915 1
3138312158 ij
480882843 ij
988558885 ij
k4 +
k5 +
k +
11968408119
7850665645
3512253271 6
5302636961 ij
1259489433 ij
1016647712 ij
k7 +
k8 +
k
26425940286
12163586030
23899101975 9
(9)
xij ((n + 1) ) = xij (n ) +

Our method is based on applying adaptive step size

selection method [4] in time multiplexing CNN simulator
using RK7(5).

(a) Input image

(b) Output image

Figure 4: Edge detection results

The performane results are shown in Fig. (5) since
the simulation results are shown in Fig. (5a) and the
maximum step size for all techniques are shown in Fig.
(5b). The results obtained by simulating a small image of
Mona Lisa for edge detection.

Page 174

Table (1) demonstrates that the results of the error

tolerances E A and E B and the local minimum truncation
error using RK7(5) are less than those in the literature.
The error tolerance represent the average of the error
tolerances of the blocks of the input image. Also the simulation time is better than using RK-Gill and RK-Butcher
methods found in the literature. So these results prove
that our proposed method is promising when compared
with those in the literature.

(a) Simulation time for 4 dierent techniques

So the proposed method improved the results found

in the literature by minimizing the error tolerances E A
and E B and the local truncation error for each step
which means that the obtained results using our proposed
method has a good impact in decreasing the CPU time
which is taken by the proposed simulator. In addition,
the edge detection results were better if they were compared by the results found in the literature.

(b) Maximum h for 4 dierent techniques:

1-Edge detection 2:Averaging template 3:Connected component

Conclusion

Our method used the selection step size algorithm to

get better results using RK7(5). The time multiplexing
CNN simulator using RK7(5) has shown better results for
both the simulation time and edge detection results. This
means that the performance of our method is better than
those in the literature. Also, the obtained results of the
error tolerances for the proposed method of time multiplexing CNN simulator is less than those found in the
literature. For future work, we are planning to present
more ecient numerical integration algorithms which can
improve the performance of the simulator in addition to
the quality of the output image for edge detection.

Figure 5: Performance results of the proposed method

References
From these results we notice that the value of the step
size h using our method is higher than those in the related
work. Hence the simulation time for the proposed method
is decreased. . We notice that the value of h is considered
to have a value to be increased to some range in order to
avoid the divergence status. On the other hand, the value
of h should be not very small because this implies more
computation time as in the case of using Euler method.

Method
Euler
RK-Gill
RK-Butcher
RK 6(4)

EA
0.785
0.676
0.543
0.329

EB
0.885
0.764
0.551
0.428

Local Truncation Error

0.7365
0.6542
0.5754
0.457

Table 1: Results of the error tolerances E A , E B and Local

Truncation Error

[1] M. Bader. A comparative study of new truncation error estimates and intrinsic accuracies of some
higher order runge-kutta algorithms. Computers and
Biomedical Research Chemistry, pages 121124, 1987.
[2] M. Bader. A new technique for the early detection of
stiness in coupled dierential equations and application to standard runge-kutta algorithms. Theoretical
Chemistry Accounts, pages 215219, 1988.
[3] L. O. Chua and L. Yang. Cellular neural networks:
Theory and applications. IEEE Trans. Circuits and
Systems, 1988.
[4] T. E. Hull, W. H. Enright, B. M. Fellen, and A. E.
Sedgwick. Comparing numerical methods for ordinary dierential equations. Comparing numerical
methods for ordinary dierential equations, 9:603
637, 1972.
[5] C.C. Lee and JP. de. Gyvez. Single-layer cnn simulator. In IEEE International Symposium on Circuits
and Systems, 1994.

Page 175

[6] C.C. Lee and JP. de. Gyvez. Time-multiplexing cnn

simulator. In Proc. IEEE Int. Symposium on Circuits
and Syst., pages 407410, Dec. 1994.
[7] K. Murugesan, S. Sekar, V. Murugesh, and J.Y. Park.
Numerical solution of an industrial robot arm control problem using the rk-butcher algorithm. Inter-

national Journal of Computer Applications in Technology, pages 132138, 2004.

[8] V. Murugesh and K. Murugesan. Comparison of Numerical Integration in Raster CNN Simulation, volume 3285. LNCS, Springer, 2004. 115-122.

[9] V. Murugesh and K. Murugesan. Simulation of timemultiplexing cellular neural networks with numerical
integration algorithms. In Lecture Notes in Computer
Science, volume 3991, pages 457464, 2006.
[10] S.C. Oliveira. Evaluation of eectiveness factor of
immobilized enzymes using rungekutta-gill method:
how to solve mathematical undetermination at particle center point? Bio Process Engineering, 20, 1999.
[11] L. F. Shampine. Some practical runge-kutta formulas.
Math. Comp., 46:135150, 1986.
[12] CH. Tsitouras and S. N. Papakostas. Cheap error
estimation for rungekutta methods. SIAM J. Sci.
Comput., 20(6):20672088, 1999.

Page 176