2010 International Workshop on Nonlinear Circuits,Communication and Signal Processing
NCSP'10, Waikiki, Hawaii, March 3-5, 2010

Restoration of Road Network Information by Using Cellular Neural Network
Yasuhiro Ueda† , Masakazu Kawahara† , Takashi Inoue† and Yoshifumi Nishio††Tokushima University
2–1 Minami-Josanjima, Tokushima, Japan
Email:{yasuhiro, kawahara, takashi, nishio}@ee.tokushima-u.ac.jp

Abstract

Sec. 3, we propose an algorithm for estimation. In the Sec. 4,
we show some computer simulation results using the proIn this study, we propose an algorithm for estimation of the posed algorithm. The Section 5 concludes the article.
original road from the hidden road by using cellular neuralnetworks (CNN). Our proposed algorithm is composed of two
2. Cellular Neural Networks [1]steps that is flowchart to detect the road and to connect theroad. From some simulation results, we are able to expect theIn this section, we describe the basic structure of CNN.
original road by various satellite images, hence we confirm CNN has M by N processing unit circuits called cells. Cells
that the eﬀectiveness of the proposed algorithm.
are arranged in a reticular pattern to M line by N row. We rep1. Introduction
The Cellular Neural Networks (CNN) [1] were introducedby Chua and Yang in 1988. The idea of CNN was inspired
from the architecture of the cellular automata and the neuralnetworks. A diﬀerent point from the conventional neural networks is that CNN has local connectivity property. Since thestructure of CNN resembles the structure of animals’ retina,
CNN can be used for various image processing applications[2]-[5]. CNN is composed of the basic circuit units calledcells. The cell contains linear and nonlinear circuit elements
which are typically linear capacitors, linear resistors, linear
and nonlinear controlled sources. Wiring weights of the cells
are established by parameters called the template. The template of CNN consists of three elements as the feedback template A, the control template B and the threshold value I. The
performance of CNN is decided by these templates.
In the image processing applications, the various images
like the medical image are used as an input image. The satellite image is also the one, it is used for the route search application. However, the road is sometimes hidden by the hurdle
like a cloud, it is bad eﬀect for obtaining correct results.
In this study, we propose how to prospect the original roadfrom the hidden road in the satellite image including obstacleby using CNN. Our algorithm for estimation of the originalroad is composed by two steps; the detection of the road andthe connection of the road. In the first step of our algorithm,
the hidden road by the obstacle is detected from the satellite
image as an input. In the second step, the detected road in thefirst step is connected. Finally, we can make estimation theoriginal road in the satellite image including the obstacle.
In the Sec. 2, we describe the conventional CNN. In theresent a cell C(i, j) using a variable i which denotes vertical
position and a variable j which denotes horizontal position.
The cell contains linear and nonlinear circuit elements. CNN
is an array of cells. Each cell is connected to its neighboring
cells according to a template. Usually, the same template isused for all the cells except for boundary cells. CNN has thefeatures of time continuity, spatial discreteness, nonlinearityand parallel processing capability.
The state equation and the output equation of the cell C(i, j)
are shown as follows.
State equation:
dv xi jdt=−v xi j +j+ri+r ∑∑A(i, j;k,l) vykl (t)k=i−r l= j−r+j+r
i+r ∑∑B(i, j;k,l) vukl (t) + I.

(1)

1(|v xi j (t) + 1| − |v xi j (t) − 1|).
2

(2)

k=i−r l= j−rOutput equation:
vyi j (t) =where v x , vy and vu represent a state, an output and an inputof the cell, respectively. In the Eq. (1), A is the feedback
template and B is the control template. These templates andthreshold value I are collectively called the general template.
The r-neighborhood of C(i, j) in CNN is defined byNr(i, j) = {C(k, l) | max { |k − i| , |l − j| } ≤ r,1 ≤ k ≤ M; 1 ≤ l ≤ N}.

(3)

where r is a positive integer number. In our study, we fix thevalue of r as 1.

- 540 -3. Proposed algorithm
In this section, we describe the proposed algorithm for estimation of the original road from the hidden road. Our proposed algorithm is composed of two steps that is flowchart todetect the road and to connect the road. Additionally, there
are two kinds of flowcharts to detect the road. We have to(a)(b)(c)
use both the flowcharts as the situation demands. One is thecase that the color of the road is diﬀerent from the color ofFigure 2: Edge detection. (a) Input image containing
the obstacle. The other is the case that the color of the road isalternating layers of gray scale objects. (b) Output imsame with the color of the obstacle.
age obtained by the conventional “Edge Detection” template. (c) Output image obtained by the proposed “ParticularEdge Detection” template.
3.1. How to detect the hidden roadIn this subsection, we describe two kinds of flowcharts how
to detect the roads.

We propose new template described as following equation.
Particular Edge Detection template: −2 −0.3 −2 −0.3 −2 171−0.3  −0.3
7147−2  , B = 0, I = I. (4)A1 =  −2 −0.3
171−0.3 

Input image

BinaryParticular Edge Detection
Logic DIFFERENCE−2

Hole Filling
Small Object Remover
Hidden road is detected.

(a)
Input image

Binary3.1.1. Used templates

Particular Edge Detection
Logic AND
Hole Filling
Small Object Remover

Hidden road is detected.

(b)
Figure 1:
Flowchart to detect the hidden road.
(a) Flowchart 1; The color of the road and of the obstacle
are same. (b) Flowchart 2; The color of the road and of theobstacle are diﬀerent.

The diﬀerent point between these flowcharts is that thethird processing is Logic AND or Logic DIFFERENCE. We
have to use both these flowcharts as the situation demands.

−0.3−2−0.3−2This template detects the edge of a object with a specified
density by changing a threshold value I. For example, weconsider an image containing three objects with diﬀerent densities shown in Fig. 2(a). The conventional “Edge Detection”
template detects all the edge of the three objects as Fig. 2(b).
Moreover, by using the conventional template, the two edgesof two overlapped objects, whose densities are similar, are detected as one edge. In contrast, “Particular Edge Detection”
template detects a edge of the specific density object and a
black object as Fig. 2(c). This is because that by changing thethreshold value I, the proposed template can detect only theedge of the object with the specified density even if the objects with the similar densities are overlapped. Furthermore,
the gray object with larger density than the threshold value
I is converged to black as the object on the right corner in
Fig. 2(c), and the object with smaller density than I is converged to white as the square object on the center.
Additionally, the convergence time of “Particular Edge Detection” template is overwhelmingly shorter than the conventional “Edge Detection” template. The output image as
Fig. 2(c) is not obtained whatever any templates are applied,
as far as we know. From these behaviors, we think that “Particular Edge Detection” template is appropriate to detect thehidden road.
Hole Filling template: 0 0 0 
 0 1 0 
A =  1 3 1  , B =  0 4 0  , I = 1.
(5)



0 0 00 1 0- 541 -This is a propagating template [6]. By using this template,white will spread from the boundary of the image, and thearea surrounded by white will be filled. In this study, wesuppose that the satellite image contains three objects; theobstacle such as a cloud, the road hidden by the obstacle
and the unnecessary objects such as buildings. We use thistemplate to remove the unnecessary objects. Please note thatmost roads are connected with the boundary of the image. If aboundary value is set as black, the unnecessary objects, which
is not connected with a boundary of the image, will be filledwith white.
By carrying out “Flowchart 1” or “Flowchart 2”, the roadhidden by the obstacle is detected from the satellite input image.
3.2. How to connect the hidden roadIn this subsection, we propose the flowchart how to connect
the road hidden by the cloud as the obstacle.

This template extends black to every directions.
Secondly, the gap between the two thick lines is filled by“Concave Location Filler” template [6].
Concave Location Filler template: 0.5 0.5 0.5  0 0

A =  0.5 3 0.5  , B =  0 2

0.5 0.5 0.50 0The template transforms all the objects to solid black concave
polygons with vertical, horizontal and diagonal edges only.
Thirdly, the contour of a black object is gradually cut downwith “Black and White Skeltonization” template [6].
Black and White Skeltonization template:
SKELBW1
0 
 0 0 0 
 1 1
−1  , I = −1.
A =  0 1 0  , B =  1 50000−1SKELBW2


 2
 0 0 0 
A =  0 1 0  , B =  0

Input image (Hidden road)Black Propagation

0Black and White
Skeletonization


0 

0  , I = 3.25. (7)00002
9−2−1



2 

0  , I = −2.
−1…
SKELBW8 2 0 −1  0 0 0 
A =  0 1 0  , B =  2 9 −2  , I = −2.

Logic OR

Black Propagation

00020−1(8)This template carries out the thinning process, hence the output image has only one pixel line.
Flowchart 3 connects the hidden road which is detected by“Flowchart 1” or “Flowchart 2”.

Concave Location Filler

Black and White Skeletonization

Logic OR

4. Simulation results
Original road is estimated.

In this section, we carry out two simulations. One is thecase that the colors of the obstacle and of of the roads are
Figure 3: Flowchart 3: Flowchart to connect the hidden road. same, and another is the case that it is diﬀerent.
4.1. Case 1: Same colors
3.2.1. Used templatesFirst, make detected road temporarily thick by “BlackPropagation” template to connect hidden road [6].
Black Propagation template: 0.25 0.25 0.25 
30.25  , B = 0, I = −1.
A =  0.25

0.25 0.25 0.25

(6)

Figure 4(a) is an input image. The road is hidden by
the cloud which exists on the center of the image. Figures 4(b) and (c) are an output images obtained by applying“Flowchart 1” to Fig. 4(a) and “Flowchart 3” to Fig. 4(b),respectively. Figure 4(d) shows the expected original road.
From Fig. 4(d), we can see the little error in the expected
road. However, the proposed algorithm could interpolate thehidden road. Therefore, we think that the proposed algorithm
is enough for estimation of the original road.

- 542 -

(a)

(b)

(a)

(b)

(c)

(d)

(c)

(d)

Figure 4: Simulation for an image including the obstacle
whose color is same as the hidden road. (a) Input image. (b) Output image obtained by “Flowchart 1.” (c) Output
image obtained by “Flowchart 3.” (d) Output image which isadded Fig. 4(c) to Fig. 4(b).

Figure 5: Simulation for an image including the obstacle
whose color is diﬀerent as the hidden road. (a) Input image. (b) Output image obtained by “Flowchart 2.” (c) Output
image obtained by “Flowchart 3.” (d) Output image which isadded Fig. 5(c) to Fig. 5(b).

References

4.2. Case 2: Diﬀerent colors
Figure 5(a) is an input image. The road is hidden by thecloud whose color is diﬀerent from the road. Figures 5(b) and(c) shows output images obtained by applying “Flowchart 2”
to Fig. 5(a) and “Flowchart 3” to Fig. 5(b), respectively. Figure 5(d) shows the expected original road. From Fig. 5(d), we
think the proposed algorithm could expect the original road.
According to our simulation, our proposed algorithm is effective for estimation of the original road in various satellite
images including the obstacle.

[1] L. O. Chua and L. Yang, “Cellular Neural Networks:Theory,”
IEEE Trans. Circuits Syst., vol. 32, pp. 1257–1272, Oct. 1988.
[2] F. Dirk and T. Ronald, “Coding of Binary Image Data using
Cellular Neural Networks and Iterative Annealing,” Proc. ofECCTD’03, vol. 1, pp. 229–232, Sep. 2003.
[3] M. Namba and Z. Zhang, “Cellular Neural Network for Associative Memory and Its Application to Braille Image Recognition,” Proc. of IJCNN’06, pp. 4716–4721, Jul. 2006.
[4] H. Koeppl and L.O. Chua, “An Adaptive Cellular Nonlinear
Network and its Application,” Proc. of NOLTA’07, pp. 15–18,Sep. 2007.
[5] L. O. Chua and L. Yang, “Cellular Neural Networks: Applications,” IEEE Trans. Circuits Syst., vol. 35, no. 10, pp. 1273–1290, Oct. 1988.

5. Conclusions
In this study, we have proposed an algorithm for restorationof road network information by using CNN. We were able to
make estimation the original road by various satellite images.
From simulation results, we have confirmed that our proposed
algorithm is eﬀective in the actual satellite images. In thefuture work, we should be selected the one of Flowcharts 1and 2 automatically. Additionally, the anticipated road are
one pixel line unlike the real road. Therefore, we would liketo size a line to the width of the real road.

[6] Cellular Sensory Wave Computers Laboratory Computer andAutomation Research Institute Hungarian Academy of Sciences, “Cellular wave Computing Library (Template, Algorithms, and Programs) Version 2.1”.

- 543 -