2005 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'05)
Hawaii, USA, Mar. 4-6, 2005.

Reversible Watermarking Using Small-World Cellular Neural Network
Kazuya TSURUTA and Yoshifumi NISHIO
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
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 completelyrandom 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]-[3]. 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 shortcharacteristic path length of typical random networks. Interesting examples are shown by collaboration of movie stars,
connectivity of internet web pages or neural nets, etc.
Recently, the authors have proposed Small-World CellularNeural Network (SWCNN) [6, 7], which is constructed by introducing some random couplings between cells of the original Chua-Yang CNN. In [6, 7] we have reported some basic
results using the concept of SWCNN. In this paper, we propose an image wartermarking technique that the connection
topology of SWCNN plays the role of “key” and investigate
its features.

The watermark SWCNN is obtained by introducing random couplings between cells in the original Chua-Yang CNN.
We introduce a probability pc , which means what percentageof CNN cells occur random coupling to another cell. Namely,
we choose a cell c(p, q) that connects to c(i, j) at random overthe network. We repeat this process for all cells with the probability pc .
We assume that, besides its local couplings, each cell in thearray 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 the SWCNN consisting of 4 × 4cells. Obviously, when pc = 0, the SWCNN is completely
the same with the original CNN, and the maps correponding
to 0 < pc < 1 and pc = 1, shown in the middle part and theright hand side of Fig. 1, respectively.

pc=0

Increasing randomness

Figure 1: A two-dimensional watermark SWCNN architecture with different probability pc .
The state equation of each cell c(i, j) of the SWCNN isformulated by Eq. (1), and the output equation is defined byEq. (2).
ẋi j (t) = − xi j (t) + I +2. Network Topologies of Watermark SWCNN

pc=1

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

- 21 -+X

X
A(i, j; k, l)ykl (t)c(k,l)∈Nr (i, j)

B(i, j; k, l)ukl (t) + wc M(i, j; p, q)y pq (t)c(k,l)∈Nr (i, j)(1)

1(|xi j (t) + 1| − |xi j (t) − 1|)2(i = 1, 2, ..., M, j = 1, 2, ..., N.)(2) authenticate a image and protect a copyright. Here, watermarks should be invisible for observer. The watermark isclassified into robust and fragile technique. A robust watermark is intended to leave the mark by resisting attacks suchwhere Nr (i, j) denotes the neighbor cells of radius r of a cell as modification and destroy the mark for copyright protection,c(i, j); A, B, and I are real constants called as feedback tem- meanwhile a fragile watermark is able to detect alteration byplate, control template and bias current, respectively; xi j , yi j breaking the mark actively.
and ui j denote the state, input and output of the cell, respectively; M(i, j; p, q) describes the small-world map that is previously created by a program with indicating the probability 3.1. Watermark Generator
pc , if there is a coupling between one cell c(i, j) and another
In CNN literature, pseudo-random pattern generator forcell c(p, q), then the M(i, j; p, q) is equal to 1, otherwise zero;
cryptographand the watermarking technique based on celluand wc stands for the coupling weight between the randomly
larautomaton
are described [8, 9]. In our method, the watercoupled cells.
mark image is scrambled by randomly coupled cells, and its
In order to investigate the features of the network, we calconnection pattern plays the role of key. Moreover, pc = 1.0
culated the characteristic path length L(pc ) and the clusteris desirable to distribute the scrambled image uniformly. For
ing coefficient C(pc ) as varying pc . The characteristic pathexample, we adopted the template as follows:
length L(pc ) is defined as the number of edges in the short
est path between two vertices, averaged over all pairs of ver 0 0 0 
B = 0,tices [5]. The clustering coefficient C(pc ) is defined as folI = 0,A =  0 1 0  ,(3)lows; Suppose that a vertex v has kv neighbours; then at most
wc = −1.
0 0 0kv (kv − 1)/2 edges can exist between them. Let Cv denote thatfraction of these allowable edges that actually exist. Define
Simulated results are shown in Fig. 3. We observe fromC(pc ) as the average of Cv over all v [5].
this simulation, the SWCNN can scramble the input image
and the output pattern is not correlated with the initial state
1.2
C(p )/C(0)image. Needless to say, the output image changes by adopting
L(p )/L(0)1.0other keys.
yi j (t) =

cc

0.8

0.6

0.4

0.2

0
0.0001

0.001

0.01

0.1

1

pc

(a)

(b)

(c)

(d)

Figure 2: Characteristic path length and clustering coefficientof watermark 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. Image Watermarking Using SWCNN

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

In this section, we describe the watermark technique usAs already mentioned, the watermark is generated by theing SWCNN. The watermark is a technique to embed some
information to the target host image. The watermark embed- small-world map. Hence, it is able to generate watermark
ded to the host image is used for to detect a modification, and to embed it to the host (input) image simultaneously by- 22 -SWCNN. The watermark SWCNN template form becomes
as:




 0 0 0 
 0 0 0 




A =  0 a 0  , B =  0 b 0  , wc = c, I = 0. (4)
0 0 00 0 0

results with different parameter settings are shown in Fig. 6.
Figure 6(a) is a host image and Fig. 6(b)-(f) show the results
after watermarking with a = −c = (1 − b)/2 = 0.02, 0.04,0.06, 0.08 and 0.1, respectively.
We run the system backwards to recover the embedded image from the watermarked image, and this is a private waterThus, the cell’s state equation in the watermark SWCNN mark that requires host and marked image. Ordinarily, theoutput image is quantized to 8bit grayscale image in CNN,
can be rewritten in the following form:
but because of quantization error, it is difficult to recover theẋi j = −xi j + f (xi j ) + wi j(5) image completely. Therefore, we use 16bit quantized image
for this purpose. The simulation results are shown in Fig. 7.
where,The parameter set are the same as watermarking operation.
From Fig. 7, we observed that the watermarking SWCNN isf (xi j ) = 0.5a(|xi j + 1| − |xi j − 1|),reversible.
wi j = 0.5c(|x pq + 1| − |x pq − 1|) + bui j .
Since we run the system backwards to recover the watermark image from marked image, it is necessary to limit therange of state value |xi j | ≤ 1. From Eq. (5), for the selffeedback a, the dynamic routes are shown in Fig. 4.

.
xi, jwi, j=1-a(a)(b)(c)(d)

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

01xi, j-1slope=a-1

Figure 4: The dynamic routes of watermark SWCNN with Figure 5: (a) Input (host) image. (b) Initial state (watermark)various wi j , where 0 < a < 1 and black dots in ẋi j -intercept image. (c) Transient image at t = 1τ. (d) Watermarked output
image with embedded Lena image.
denote the stable point.
From the above, we assume that the parameters are satisfy
the following conditions;| a | + | c | + | b | ≤ 1.

(6)

3.2. Simulation
In the watermark SWCNN, the number of the key increases
drastically as the image size increases. This feature is suitableto embed a secret information (image). In this simulation, thesecret Lena image is embedded to the host image with parameter set as: a = 0.005, b = 0.99 and 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

4. Conclusions
In 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 is able to generatewatermark and embed to the host image simultaneously. Although the techniques which use pseudo-random pattern areexisting, the proposed method has shown a new potential ofSWCNN. Our important future researchs are investigations ofrobustness of the watermarking SWCNN and analyzing it inmore detail.

- 23 -References[1] L.O. Chua and L. Yang, “Cellular neural networks: theoryand 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.

(a)

(b)
[3] 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.
[4] Z. Yang, Y. Nishio and A. Ushida, “Characteristic of mutuallycoupled two-layer CNN and its stability,” Journal of Circuits,Systems, and Computes, vol.12, no.4, pp.473-490, Aug. 2003.

(c)[5] D.J. Watts and S.H. Strogatz, “Collective dynamics of smallworld networks,” Nature 393, pp.440-442, 1998.

(d)[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.

(e)[7] K. Tsuruta, Z. Yang, Y. Nishio and A. Ushida, “Diffusion analysis of diffusion-preserving small-world CNN,” Proceedings ofCNNA’04, pp.352-357, Jul. 2004.

(f)

Figure 6: Zoomed input and marked image. (a) Input(host)image. (b)-(f) Watermarked image with a = −c = (1 − b)/2 =0.02, 0.04, 0.06, 0.08 and 0.1, respectively.

(a)

(b)

(c)

(d)

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

Figure 7: Extracting embedded information. (a) Input image.
(b) Marked image. (c) Transient image at t = 6τ. (d) Recovered watermark output images.

- 24 -