ECCTD 2005 - European Conference on Circuit Theory and Design, Cork Ireland, 29 August - 2 September 2005

Reversible Watermarking Technique Using Small-World
Cellular Neural Network
Kazuya Tsuruta ∗Abstract — Recently, the authors have proposed Small-World
Cellular Neural Network (SWCNN), which is constructed by introducing some random couplings between cells of the original
Chua-Yang CNN and we have reported some basic results using the concept of SWCNN. In this paper, we propose an image wartermarking technique that the connection topology ofSWCNN plays the role of “key” and investigate its features.

1 INTRODUCTION

Yoshifumi Nishio†
features.
2

NETWORK TOPOLOGY OF WATERMARKSWCNNIn this section, we describe the connection topology of SWCNN for watermark composed of a twodimensional M by N array structure.
The watermark SWCNN is obtained by introducing
random couplings between cells in the original ChuaYang CNN. We introduce a probability pc , which means
what percentage of CNN cells occur random coupling toanother cell. Namely, we choose a cell c(p, q) that connects to c(i, j) at random over the network. We repeat
this process for all cells with the probability pc .
We assume that, besides its local couplings, eachcell in the array has up to one random coupling to another cell, moreover, the coupling direction is unilateral. Thereby, for M × N array, it has M × N couplings
with maximum pc . Figure 1 shows a sketch map of theSWCNN consisting of 4 × 4 cells. Obviously, whenpc = 0, the SWCNN is completely the same with theoriginal CNN, and the maps correponding to 0 < pc < 1and pc = 1, shown in the middle part and the right handside of Fig. 1, respectively.

Studies of network map are very important, because
they help us to understand the basic features and requirements of various systems. So far many connection
topologies of network assumed to be either completely
regular or completely random have been studied in thepast. Cellular Neural Network (CNN) model invented
by Chua and Yang in 1988 [1] is a typical of thosecompletely local connectivities, which is presented as apreferred 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]-[3]. However, in many cases inreal life, many network topologies such as biological,
technological and social networks are known to be notcompletely random nor completely local but somewhere
in between. This was modeled in an interesting workby Watts and Strogatz in 1998 [4] as the small-worldmodel. The model is a network consisting of many local links and fewer long range ‘short cuts’. Therefore,
it has a high clustering coeﬃcient like regular lattices
and a short characteristic path length of typical random
pc=1
pc=0
Increasing randomness
networks. Interesting examples are shown by collaboration of movie stars, connectivity of internet web pages
Figure 1: A two-dimensional watermark SWCNN aror neural nets, etc.
Recently, the authors have proposed Small-World chitecture with diﬀerent probability pc .
Cellular Neural Network (SWCNN) [5, 6], which is
The state and output equation of each cell c(i, j) ofconstructed by introducing some random couplings between cells of the original Chua-Yang CNN. In [5, 6] the SWCNN is formulated by Eq. (1).
we have reported some basic results using the con
cept of SWCNN. In this paper, we propose an imageẋi j (t) = − xi j (t) + I +Ai j;kl ykl (t)wartermarking technique that the connection topologykl∈Nr (i, j)
of SWCNN plays the role of “key” and investigate its
Bi j;kl ukl (t) + Mi j;pq wc y pq (t)+∗ Dai Nippon Printing Co., Ltd., 1650-70 Okubara, Ushiku,Ibaraki, Japan, e-mail: Tsuruta-K2@mail.dnp.co.jp, tel: +81-298-752235, fax: +81-298-75-2302.
† Department of Electrical and Electronic Engineering, Tokushima
University, 2-1 Minami-Josanjima, Tokushima, Japan, e-mail:nishio@ee.tokushima-u.ac.jp, tel: +81 88 656 7470, fax: +81 88 656
7471.

0-7803-9066-0/05/$20.00 ©2005 IEEEkl∈Nr (i, j)

yi j (t) =1(|xi j (t) + 1| − |xi j (t) − 1|)2(i = 1, 2, ..., M, j = 1, 2, ..., N.)(1)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; xi j , yi j and ui j denote the state, input and output of the cell, respectively; M(i, j; p, q) describes thesmall-world map that is previously created by a programwith probability pc , if there is a coupling between one
cell c(i, j) and another cell c(p, q), then the M(i, j; p, q)
is equal to 1, otherwise zero; and wc stands for the coupling weight between the randomly coupled cells.
In order to investigate the features of the network, wecalculated the characteristic path length L(pc ) and theclustering coeﬃcient C(pc ) as varying pc . The characteristic path length L(pc ) is defined as the number ofedges in the shortest path between two vertices, averaged over all pairs of vertices [4]. The clustering coeﬃcient C(pc ) is defined as follows; Suppose that a vertex
v has kv neighbours; then at most kv (kv − 1)/2 edges canexist between them. Let Cv denote that fraction of theseallowable edges that actually exist. Define C(pc ) as theaverage of Cv over all v [4].

while a fragile watermark is able to detect alteration bybreaking the mark actively.
3.1

Watermark Generator

In CNN literature, pseudo-random pattern generator for
cryptograph and the watermarking technique based on
cellular automaton are described [7, 8]. In our method,
the watermark image is scrambled by randomly coupled cells, and its connection pattern plays the role ofkey. Moreover, pc = 1.0 is desirable to distribute thescrambled image uniformly. For example, we adopted
the template as follows: 0 0 0 
B = 0,
I = 0,A =  0 1 0  ,(2)
0 0 0
wc = −1.
Simulated results are shown in Fig. 3. We observefrom this simulation, the SWCNN can scramble the input image and the output pattern is not correlated with
the initial state image. Needless to say, the output imagechanges by adopting other keys.

1.2

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

0.8

0.6

0.4

0.2

00.0001

0.001

0.01

0.1

(a)

(b)

(c)(d)

1pc

Figure 2: Characteristic path length and clustering coeﬃcient of watermark SWCNN.
The results are shown in Fig. 2. Because we makea restriction such that one cell has at most one random
coupling, the clustering coeﬃcient does not approachzero even if pc becomes 1.0. However, the characteristic
path length becomes shorter and the network possesses
the feature of the small-world networks.

Figure 3: (a) 64 × 64 initial state image with pc = 1.0.
(b)-(d) Output images at t = 5τ, 10τ and 50τ.

As already mentioned, the watermark is generated by
the small-world map. Hence, it is able to generate waIn this section, we describe the watermark technique termark and to embed it to the host (input) image simulusing SWCNN. The watermark is a technique to em- taneously by SWCNN. The watermark SWCNN tembed some information to the target host image. The plate form becomes as:
watermark embedded to the host image is used for to 0 0 0  0 0 0 
 I = 0,detect a modification, authenticate a image and protect(3)
A =  0 a 0  , B =  0 b 0  , wc = c.
a copyright. Here, watermarks should be invisible for0 0 00 0 0observer. The watermark is classified into robust andThus, the cell’s state equation in the watermark
fragile technique. A robust watermark is intended to
SWCNN can be rewritten in the following form:
leave the mark by resisting attacks such as modificationẋi j = −xi j + a f (xi j ) + wi j
(4)and destroy the mark for copyright protection, mean3 IMAGE WATERMARKING USING SWCNN

where,f (xi j ) = 0.5(|xi j + 1| − |xi j − 1|),
wi j = 0.5c(|x pq + 1| − |x pq − 1|) + bui j .
Since we run the system backwards to recover thewatermark image from marked image, it is necessary tolimit the range of state value |xi j |≤ 1. From Eq. (4), forthe self-feedback a, the dynamic routes are shown inFig. 4.

(a)

(b)

(c)

(d).
xi, j

wi, j=1-a
1-1wi, j= -(1-a)

01-1slope=a-1

xi, jFigure 5: (a) Input (host) image. (b) Initial state (watermark) image. (c) Transient image at t = 1τ. (d)Watermarked output image with embedded Lena image(PSNR=57.34dB).

Figure 4: The dynamic routes of watermark SWCNN
with various wi j , where 0<a<1 and black dots in ẋi j - PSNR=51.34, 45.30, 39.21, 35.61 and 33.03, respecintercept denote the stable point.
tively. In this simulation, the watermark stand out moreclearly and PSNR decreases as the parameters increase.
From the above, we assume that the parameters areWe run the system backwards to recover the embedsatisfy the following conditions;ded image from the watermarked image, and this is a
| a | + | c | + | b | ≤ 1.
(5) private watermark that requires host and marked image.
Ordinarily, the output image is quantized to 8bit grayscale image in CNN, but because of quantization error,
3.2 Simulation
it is diﬃcult to recover the image completely. ThereIn the watermark SWCNN, the number of the key in- fore, we use 16bit quantized image for this purpose.
creases drastically as the image size increases. This fea- The simulation results are shown in Fig. 7. In this simture is suitable to embed a secret information (image).
ulation, the parameter set are the same as watermarking
Here, in order to evaluate the task, the peak signal to operation. Table 1 shows bit error rate (BER) and PSNR
noise ratio (PSNR) is investigated. PSNR is defined as: of recovered watermark image from diﬀerent key. It
is able to improve key sensitivity using A-Template ofs2max(6) neighbour cells. From Fig. 7, we observed that the waPSNR = 10 log 1  M−1 N−12
i=0
j=0 (sui j − syi j )MNtermarking SWCNN is reversible and its mapping plays
the role of key.
where sui j and syi j represent the pixel values of input andIn these simulation, we showed binary mark only.
marked image at cell position C(i, j). And smax is maxWhen
gray-scale images are used for watermark, reimum value, for 16bit quantized image, s2max = 655352 .
coverd image is not lossless. However, the recovered
Firstly, a binary Lena image is embedded to the hostmark is clearly visible for observer (PSNR of recovered
image with parameter set as: a = 0.005, b = 0.99 andgray-scale Lenna image is about 45dB).
c = −0.005. Simulation results are shown in Fig. 5.
The watermarked image Fig. 5(d) contains visually imperceptible scrambled Lena image.
The robustness can be improved by increasing the parameter a and |c|, or decreasing the parameter b. The
simulation results with diﬀerent parameter settings areshown in Fig. 6. Figure 6(a) is a host image andFig. 6(b)-(f) show the results after watermarking witha = −c = (1 − b)/2 = 0.01, 0.02, 0.04, 0.06 and 0.08.

(a)

(b)

(d)(e)(f)

Figure 6: Zoomed input and marked image. (a) Input
image. (b)-(f) Watermarked image with a=-c=(1-b)/2=0.01, 0.02, 0.04, 0.06 and 0.08. PSNR=51.34, 45.30,39.21, 35.61 and 33.03, respectively.

BER

PSNR[dB]

00.046
0.134
0.221
0.308
0.444

∞
13.34
8.74
6.55
5.11
3.53

Table 1: The results of extracting the embedded image
with diﬀerent key.

4(c)Key change rate

0 (correct key)
0.1
0.3
0.5
0.7
1.0

CONCLUSIONSIn this article, a watermarking technique using SWCNN
has been proposed and its features are investigated.
We designed template of SWCNN for the watermaked
image reversibly. Moreover, the proposed method isable to generate watermark and embed to the host image simultaneously. Although the techniques which
use pseudo-random pattern are existing, the proposed
method has shown a new potential of SWCNN. Our important future researchs are investigations of robustnessof the watermarking SWCNN and analyzing it in moredetail.
References[1] L.O. Chua and L. Yang, “Cellular neural networks: theory and applications,” IEEE Trans. Circuits & Syst.,
vol.35, no.10, pp.1257-1290, Oct. 1988.
[2] L.O. Chua and T. Roska, “The CNN paradigm,” IEEE
Trans. Circuits & Syst., vol.40, no.3, pp.147-156, Mar.
1993.
[3] Z. Yang, Y. Nishio and A. Ushida, “Characteristic of mutually coupled two-layer CNN and its stability,” Journal of Circuits, Systems, and Computes, vol.12, no.4,pp.473-490, Aug. 2003.
[4] D.J. Watts and S.H. Strogatz, “Collective dynamics ofsmall-world networks,” Nature 393, pp.440-442, 1998.

(a)

(b)

[5] K. Tsuruta, Z. Yang, Y. Nishio and A. Ushida, “Smallworld cellular neural networks for image processing applications,” Proceedings of ECCTD’03, vol.1, pp.225228, Sep. 2003.
[6] K. Tsuruta, Z. Yang, Y. Nishio and A. Ushida, “Diﬀusion analysis of diﬀusion-preserving small-world CNN,”
Proceedings of CNNA’04, pp.352-357, Jul. 2004.

(c)

(d)

Figure 7: Extracting embedded information. (a) Inputimage. (b) Marked image. (c) Recovered watermark
with correct key. (d) Output image with wrong key.

[7] K.R. Crounse, T. Yang and L.O. Chua “Pseudo-random
sequence generation using the CNN universal machine with application to cryptography,” Proceedings ofCNNA’96, pp.433-438, Jun. 1996.
[8] M.E. Yalçin, J. Vandewalle, P. Arena, A. Basile andL. Fortuna “Watermarking on CNN-UM for image andvideo authentication,” International Journal of Circuit
Theory and Applications, vol.32, pp.591-607, Apr. 2004.