1. Introduction
The cellular neural network (CNN) in its standard form as defined by Chua and Yang has become a paradigm of analog, high-speed computation, with various applications in parallel signal processing, especially in image processing tasks. Within two decades this domain has extensively developed both theoretically and from the applications point of view. Although the mainstream research basically followed the standard CNN model, many other CNN models and architectures were proposed, envisaging new and more complex classes of applications.
We propose here an alternative CNN model, inspired from Hopfield-type recurrent networks. This new model has the same general architecture as the standard model, while the cell structure, preserving the basic elements, is modified from a dynamical point of view. The cell non-linearity, having a major role in CNN dynamics, no longer applies only to the current state variable as it does in the standard model, but to the whole information fed to the current cell, thereby leading to a different dynamic behavior. The new cell structure and state equations are presented and the dynamics and equilibrium points are analyzed.
The advantages of this model, which we call “CNN with overall non-linearity”, are a simpler design of the templates, and the fact that all voltages in the cells are limited to a fixed dynamic range regardless of template parameters; thus the boundedness problem regards the current range instead of voltage, which makes it less critical from an implementation point of view. The image processing capabilities of the proposed CNN model will be approached. Some new image processing tasks are proposed. We first analyze the behavior of the proposed CNN in processing binary images, then using so-called local rules we design the templates for several specific tasks, which are: convex corner detection, erasing thin lines, detection of closed curves, finding all paths between two selected points through a labyrinth, rotation detector, marked object reconstruction and finding the intersection points of one-pixel thin lines from two superposed binary images. Many other processing tasks both on binary or grayscale images are possible. Further research may focus on extending the range of applications of the proposed model.
Next some applications of CNNs in image linear filtering will be approached. In this range of applications, the cells of the CNN operate in the linear domain, and the system stability must be ensured. The design of CNN linear filters with high selectivity may lead in general to large-size templates. Due to the fact that local connectivity in CNNs is an essential restriction, the decomposition of a large-size template into small-size templates is often necessary. Fast linear filtering using parallel computing systems like CNNs may be useful in early vision aplications and pre-processing tasks. We will present some original and efficient design methods for several types of two-dimensional filters: circular, maximally-flat, elliptically-shaped, orientation-selective filters etc. We also propose a class of 2D linear filters which are designed starting from a desired shape in the frequency plane, described in polar coordinates. Using this method, some interesting filters can be designed, such as concave-shaped filters presenting narrow lobes in the frequency plane. A particular class are the zero-phase 2D filters, which are extensively used in image processing due to the absence of phase distortions. For all the proposed filters, the design starts from an imposed 1D prototype and uses rational approximations and various frequency transformations to obtain the 2D frequency response. The resulted filters are efficient, at the same time of low complexity and relatively high selectivity. The design methods are entirely analytical, but they could be combined with numerical optimization techniques. The filters can be implemented either digitally or on analog processing systems like CNNs. Further research also envisages an efficient and reliable implementation of this class of filters.
2. Cellular Neural Networks with Overall Nonlinearity
2.1. Equations and Circuit Model
The state equation of the current cell
and the output is given by the piece-wise linear function:
Here a new version of CNN is proposed (Matei, 2001), with a modified structure as compared to the standard one. The difference lies in the form of the state equation, which has the form:
For simplicity we used a single index for the cells, as in the case of 1D CNNs. Unlike the standard CNN, in this case the nonlinear function applies to the entire information gathered from the neighboring cells, i.e. state variables (
Let us denote by
where the inputs and bias are constant and were put together into the term
Multiplying both members of (3) by
having a form similar to (1), but in the new variable
2.2. System and Circuit Description
The modified CNN will be analytically described from dynamical point of view, as well as at circuit level. Figure 1 shows a block diagram representation of the dynamic behavior of the modified CNN, which can be compared to the standard CNN block diagram (Matei, 2001).
In this block diagram all the variables are vectors or matrices. The correlation sums in the state equation can be written as convolutions. The variable z at the input of the nonlinear block is:
and the matrix state equation of the modified CNN will be:
Unlike the standard CNN case (where the nonlinear block is placed in the feedback loop), in
the modified CNN it operates in the forward path. Here we must emphasize an important feature of the proposed CNN: the output is identical to the state variable
In Figure 1(b) we present the cell circuit of the modified CNN, which preserves the same elements as the standard CNN, but has a different structure. The major difference between the two structures lies in the location of the nonlinear element. In the standard CNN case, the nonlinear function applies to the state variable
2.3. Dynamics and Equilibrium Points
Using the Lyapunov method and the linear mapping (4) it can be proven that the modified CNN also has the property of convergence to a constant steady state following any transient. The stability properties are also established in Hopfield network theory (Haykin, 1994).
For standard CNNs, the state equation (1) is linear as long as all the state variables are less than one in absolute value,
In the following paragraph we proceed to an analysis of the dynamic behavior and a study of the equilibrium points of the modified CNN. We will use the so-called driving-point plot, which gives the state derivative
Using equation (5) which corresponds to a standard CNN in the state variable
In (8),
The case
The plots depicted in Figure 2 (b) were drawn for the particular values
The segment
has an identical form in
The points
The lines
become
In the diagram
We finally obtain:
2.4. Dynamic Range of Modified CNNs
For standard CNNs the following result has been proven in (Chua & Yang, 1988):
if we consider the normalized resistance value
The possibility of estimating the maximum dynamic range is very important from the implementation point of view, because it allows one to optimally design the circuit parameters in order to keep the voltage values within reasonable bounds.
In (Rodriguez-Vasquez et al., 1993) a new CNN model, called "full-range" model was introduced, adding a nonlinear term to the state equation, which confines the state value to the range [-1,1]. This simplifies the design, allowing for reduced area and power consumption in VLSI implementation.
Our approach gives in fact another solution to this problem, forcing the state and output values to be equal. Therefore, the proposed CNN with "overall non-linearity" is in fact a "full-range" model as well. In the modified CNN, this problem is solved by the form of the state equation itself. Indeed, at any equilibrium point, the current cell state variable is
Referring again to the circuit structure, the argument
Therefore in the case of proposed CNN with overall nonlinearity, the boundedness problem regards the current range instead of voltage, which makes it less critical from an implementation point of view. All voltage variations in the modified CNN are limited to a fixed range corresponding to the extreme pixel values, regardless of template parameters.
3. Applications of CNNs with Overall Nonlinearity
In this section we approach the image processing capabilities of the proposed CNN model. Some processing tasks will be proposed on binary (black and white) images. We first analyze the behavior of the proposed CNN model in processing binary images, then we design the templates for a few specific tasks, namely: convex corner detection, erasing thin lines, detection of closed curves, finding all paths between two selected points through a labyrinth, rotation detector, marked object reconstruction and finding the intersection points of one-pixel thin lines from two superposed binary images. Many other processing tasks on binary or grayscale images are possible.
A vast reference for different classes of standard CNN tasks is the CNN Software Library, a template catalog for a large range of analog processing operations on binary and grayscale images. These also include more complex analog algorithms which consist of sequences of elementary tasks which are fulfilled under digital control.
We use here the convention that the pixel value -1 corresponds to white, and the pixel value +1 corresponds to black. Generally, one binary image is loaded into the CNN as initial state, while another binary image may be applied to the array input. In this range of applications the system must behave as a bipolar CNN. A standard CNN is said to be bipolar if
Based on the information contained in the two images, the CNN must accomplish a given task upon the state image, according to a set of local rules for which the feedback and control templates are designed. If a given binary image is loaded as initial state, this implies that all cells are initially saturated. Depending on the chosen template parameters, the initial state of a given cell may be stable or unstable. If the state is stable, the corresponding pixel will remain unchanged (black or white); if on the contrary the state is unstable, the pixel may switch to the opposite state, following a transient evolution. Taking into account that we want to obtain a binary output image in response to the processed image, we impose that the cells which are initially unstable switch into the opposite state, therefore for a generic cell
Suppose that a given pixel is initially black, i.e.
The cell state value decreases exponentially from 1 to -1:
therefore the cell finally reaches a stable equilibrium point.
In the following paragraphs we present several tasks on binary images in order to show the image processing capabilities of the proposed CNN model with overall nonlinearity. For each of these tasks, the templates are designed and simulation results are provided.
3.1. Convex Corner Detection
Although the convex corner detection on binary images is implemented as well on standard CNNs, we show here the template design method for the proposed model. We assume a feedback template
The first step is to find the local rules according to the desired result. We have to take into account all the possible combinations of black and white pixels within a
Finding a solution to the above system is a linear programming problem which can be solved graphically or numerically. We finally reach the set of parameters:
3.2. Erasing Thin Lines
We intend to design a template which erases every thin line (one-pixel thick) from a binary image, leaving all other objects unchanged. For example, the test image in Figure 4(a) is loaded into the CNN as initial condition. We look for the feedback template
and we choose a convenient set of parameter values:
3.3. Detection of Closed Curves
In some applications it might be useful to discern between closed and open curves. These curves in turn may result from a previous processing, such as edge detection etc.
We design a CNN task which detects the one-pixel thin closed curves and deletes the open curves from a binary image. The absence of at least one pixel from a closed curve turns it into an open curve. Both the input and the initial state are used. The same binary image P is loaded as initial state and applied to input:
Applying the corresponding local rules, the set of inequalities is derived:
A convenient choice of parameters is:
3.4. Finding All Paths Between Two Selected Points Through a Labyrinth
A processing task related to the previous one is presented below. We consider a labyrinth made up of white one-pixel thin curves against a black background. In this case we suppose valid the convention that one pixel is possibly connected only to four neighbors (up, down, left, right). The target of the proposed task is to find all the existing paths between two given points situated in the labyrinth, which are marked by white pixels in the input image. A point is represented by one pixel, either on the input or state image.
The binary image P representing the labyrinth is loaded into the CNN as initial state (
The dynamic process which finds the routes between the chosen points is similar to the one used in application 3.3. The template parameters are designed such that all labyrinth routes with unmarked ends are gradually erased starting from end pixels which turn from black to white (cell outputs switch from -1 to +1). The templates are searched in the form:
and the following system results:
with convenient parameter values:
In Figure 6 a simulation example is shown. The input image (b) contains two white pixels on a uniform gray background (zero pixel value). The two pixels locate on the labyrinth image (a) (loaded as initial state) the points between which the routes are selected. At the end of dynamic propagation shown in (c), the output image (d) results.
More generally, routes can be found among several points in the labyrinth, or a single point is chosen and we find all the closed routes containing that point. The classical problem of finding the shortest path through a labyrinth is more complex and it can be solved through a CNN algorithm using several nonlinear templates, which are run sequentially under digital control.
3.5. Erasing Objects with Tilted Edges (Rotation Detector)
We will design a CNN task which detects in a binary image the compact convex or concave objects having only horizontal and vertical edges and removes all tilted objects or objects having at least one tilted edge. In particular the CNN can detect the rotation of such objects.
This is based on the discrete representation on an array of a straight line, in particular the edge of a compact object, with a certain slope. Due to the limited spatial resolution of the CNN array, any tilted edge will be mapped as a stair-like edge. An edge with the minimum angle will map into a staircase with only two stairs, while an edge with a slope of
and finally the following convenient values are found:
A simulation is presented in Figure 7. Image (a) contains several compact objects: a rectangle and a square placed horizontally and their rotated versions etc. The objects with at least one tilted edge are gradually eroded through a dynamic propagation, as shows the transient snapshot (b); the final image (c) preserves only objects with horizontal and vertical edges. Therefore, this task can be used to detect the rotation of simple objects (rectangles etc.).
A simulation is presented in Figure 7. Image (a) contains several compact objects: a rectangle and a square placed horizontally and their rotated versions etc. The objects with at least one tilted edge are gradually eroded through a dynamic propagation, as shows the transient snapshot (b); the final image (c) preserves only objects with horizontal and vertical edges. Therefore, this task can be used to detect the rotation of simple objects (rectangles etc.).
3.6. Marked Object Reconstruction
A binary image P containing compact shapes or curves is applied to the CNN input. From this image we intend to select certain objects which we want to preserve, and delete the others. The selection of objects is done by marking them with a black pixel, in the image loaded as initial state. Therefore at the input we have
A convenient set of parameters results as:
3.7. Finding the Intersection Points of One-Pixel Thin Lines from Two Binary Images
We consider two binary images
and a set of suitable parameter values is:
is the image (c) which contains only the intersection points of thin lines.
4. Applications of CNNs in Image Linear Filtering
Although cellular neural networks are basically designed for nonlinear operation, an important class of applications of CNNs in image processing is also linear filtering (Crounse & Chua, 1995). Generally, the two-dimensional spatial filters are most commonly designed in the frequency domain, by imposing a set of specifications, or starting from various 1D prototype filters with given characteristics and applying frequency transformations which finally lead to the desired 2D filter. For each specific method the filter stability must also be ensured. We will approach here only the IIR spatial filters. Generally the existing design methods of 2D IIR filters rely to a large extent on 1D analog filter prototypes, using spectral transformations from
When CNNs are used as stable linear filters, the image I to be filtered is usually applied at the input (U=I) and the initial state is usually zero (X=0). The CNN cells must not reach saturation during operation, which implies the restriction for the cell state:
The linear CNN filter is described by the spatial transfer function (Crounse & Chua, 1995):
where
An essential constraint for CNNs is local connectivity, specific to these parallel systems. Design specifications may lead to high-order 2D filters, requiring large-size templates, that cannot be directly implemented. The templates currently implemented are no larger than
For an 1D recursive CNN filter of order
The numerator and denominator of (32) can be factorized into first and second order polynomials in
with
A similar expression is valid for the denominator
Here we will discuss zero-phase IIR CNN filters, i.e. with real-valued transfer functions, which correspond to symmetric control and feedback templates. In IIR spatial filtering with a 2D filter
The image
which implies a cascade interconnection of IIR filters. The separable templates A and B can be written as convolution products, where
4.1. Design Methods for Circularly-Symmetric Filters
In this section we propose an efficient design technique for 2D circularly-symmetric filters, based on 1D prototype filters. Circular filters are currently used in many image processing applications. Given a 1D filter function
A currently-used approximation of the function
and corresponds to the
Let us consider a 1D filter
Applying DSFT and using trigonometric identities we finally get the transfer function as a ratio of polynomials in
Substituting
Therefore, the design of the 2D circular filter consists in substituting
Since the 1D prototype filter function can be factorized, the 2D circularly-symmetric filter is separable, a major advantage in implementation. The large-size template A corresponding to
If we use the
4.2. Maximally-Flat Zero-Phase Filters
We propose a method of designing 2D spatial filters of different types starting from approximations commonly used in temporal filters. However, we will design spatial filters which will preserve only the magnitude characteristics of their temporal prototypes, while the designed filters will be zero-phase; their frequency response will be real-valued. The design of the desired 2D filters will be achieved in several steps, detailed as follows.
The starting point is a discrete prototype filter of a given type and desired specifications, with a transfer function
Substituting
From the numerator
with
Let us consider as prototype a type 2 Chebyshev low-pass digital filter with the following specifications: order
Following the procedure described above, we finally get an approximation of the form (47). The numerator and denominator coefficients are given by the vectors:
and the factorization of the numerator and denominator of the 1D prototype function is :
To obtain a circularly-symmetric filter from the 1D factorized prototype function, we simply replace in (50) and (51)
where
where
4.3. Elliptically-Shaped Oriented Filters
Next we study a class of 2D low-pass filters having an elliptically-shaped horizontal section. These filters will be specified by imposing the values of the semi-axes of the ellipse, and the orientation is given by the angle of the large axis with respect to
An elliptically-shaped filter results from a circular one through the linear transformation:
where E and F are the stretching coefficients (
where the coefficients a, b and c are identified from relation (55).
Replacing the real frequency variables
The next step is to find the discrete approximation
Replacing the above operators in (58),
After re-arranging terms and identifying coefficients of the 2D Z transform, we obtain the matrix operator
The matrix
As anumerical example, taking the parameter values
Let us consider the simple 1D zero-phase prototype filter:
Applying the frequency transform (62), we obtain the 2D elliptically-shaped filter:
Since
In general, for a zero-phase prototype
For a design example, we take as 1D prototype a type-2 Chebyshev digital filter with
The real-valued transfer function approximating the magnitude of the filter
Figure 11 shows two elliptically-shaped filters based on (68), having a flat characteristic in the pass-band and a very low stop-band ripple. An advantage of this design method is that the filter characteristics in the vertical and horizontal plane are specified independently.
4.4. Directional Filters
There are several classes of 2D filters with orientation-selective frequency response, which find applications in many image processing tasks, such as edge detection, motion analysis, texture analysis etc. For instance, steerable filters which are synthesized as a linear combination of a set of basis filters (Freeman & Adelson, 1991). Another important class are the Gabor filters, efficiently implemented also on CNNs (Shi, 1998), with useful applications in image processing and computer vision. A particular class of filters, which can be also implemented on CNNs, are directional (orientation-selective) filters, which select narrow domains along specified directions in the frequency plane. Several design examples of 2D recursive directional filters with an arbitrary orientation were given in (Matei, 2004). They can be used in selecting lines with a given orientation in the input image.
The spatial orientation is specified by an angle
The 2D oriented filter
Next we will determine a convenient 1D to 2D complex transformation which allows an oriented 2D filter to be obtained from a 1D prototype filter. We will treat here the zero-phase filters, which sometimes are desirable in image processing tasks.
An accurate rational approximation (Chebyshev- Padé) of the cosine for
The range of approximation
Using the forward Euler method as in section 4.3, we obtain the discrete approximations (59) for
corresponding to an "orientation matrix" operator
The matrix
and can be realized using the pair of templates:
also depending only on the orientation angle
For a design example we use the 1D prototype filter from section 4.2, where
Using this method, some design examples are presented as follows.
1) With a zero-phase elliptic filter (Figure 12 (a)), we design a directional filter oriented at an angle
2) A simple and efficient low-pass zero-phase filter prototype has the frequency response:
where the value of
Directional filters may be used in detecting straight lines with a given orientation in an image (Matei, 2004). In order to demonstrate the directional selectivity of the proposed filters, we present an example of detecting lines with a given inclination from an image, by means of filtering with a 2D IIR oriented low-pass filter. The spectrum of a straight line is oriented in the plane (
angles, the filter selectivity has to be properly chosen. Another example is shown in Figure 15 (c), (d). The texture-type grayscale image (c) representing a portion of a straw-chair upper face is directionally filtered with the given parameter values and the result is image (d), which suggests a possible use in texture segmentation.
4.5. Filters Designed in Polar Coordinates
In this section we study a family of 2D zero-phase filters which can be designed starting from a specified shape in polar coordinates in the frequency plane. The contour plots of their frequency response can be defined as closed curves which can be described in terms of a variable radius
The proposed design method is based on zero-phase filter prototypes whose transfer function is real-valued and can be expressed as a ratio of polynomials in even powers of the frequency
where
Through this transformation we will be able to obtain low-pass type filters, symmetric about the origin, as in fact are most 2D filters currently used in image processing. The frequency transformation (82) is a mapping from the real frequency axis
Here the function
If the radial function
which is plotted in Figure 16 (b) in the range
As a first 1D prototype we consider a type-2 Chebyshev digital filter with the parameters: order
The magnitude of its transfer function in the range
Let us now consider the radial function with the form:
where
plotted for
Since
Finally we determine a transfer function of the 2D filter
A possible method is to express the function
function, which is an exact mapping of the z-plane to the s-plane. For our purposes the sample interval takes the value
Substituting
where
where
We next use the maximally flat filter prototype (87). We only have to make the substitution of (93) in
where
where
The designed filter has the frequency response and contour plot as in Figure 17 (a), (b). We remark that the filter is very selective simultaneously along both axes of the plane
We now present an example of image filtering using a selective four-lobe filter. This type of filter can be used in detecting lines with a given inclination from an image, as the directional filters discussed in section 4.4. The spectrum of a straight line is oriented in the plane
5. Conclusion
An alternative CNN model was proposed, in which the state equations are modified such that the piece-wise linear function operates on the entire information fed to the current cell, including input, feedback and offset term. The circuit structure, dynamic behavior and equilibrium points were analyzed. Through a linear transformation, the proposed model is shown to be equivalent to the standard CNN model. We aimed at making a connection between these two models and compare them from the recurrent neural network point of view. Certain advantages regarding implementation result from the limited voltage range. Several processing tasks on binary images were proposed, templates were designed and simulation results on test images are provided. The template design is relatively easy and can be optimized in order to obtain high robustness to parameter variations. A deeper insight into the proposed CNN dynamic behavior may lead to further image processing capabilities.
As regards the applications of CNNs in linear filtering, some original and efficient design methods were approached, for several types of two-dimensional filters: circular and elliptically-shaped filters, maximally-flat, orientation-selective filters etc. The design starts from an imposed 1D prototype filter and uses rational approximations and various frequency transformations to obtain the 2D frequency response. These analytical methods could be combined with numerical optimization techniques in order to realize an efficient design.
Even if theoretically all the presented spatial linear filters can be implemented in analog processing systems like CNNs, we have to take into account the fact that these analog filters may be very sensitive to template elements variations due to technological dispersion which is inherently present in any VLSI process. A systematic theoretical study on the effect of these dispersions on filter characteristics and stability can be found in (David, 2004). It has been found both analytically and through simulations that the sensitivity of the frequency response to process variations increases with filter selectivity. Since we have designed also some very selective filters, a sensitivity analysis has to be carried out in each case, to find out if a given filter can be reliably implemented. The filter robustness and stability requirements may imply strong constraints on the realization of filters with high selectivity. Further research also envisages an efficient and reliable implementation of this class of filters.
Acknowledgments
This work was supported by the National University Research Council under Grant PN2 – ID_310 “Algorithms and Parallel Architectures for Signal Acquisition, Compression and Processing”.
References
- 1.
Chua L. O. Yang L. 1988 Cellular Neural Networks: Theory , ,35 Oct.1988 - 2.
Crounse K. R. Chua L. O. 1995 Methods for Image Processing and Pattern Formation in Cellular Neural Networks- A Tutorial, IEEE Trans. on Circuits Systems, CAS-42 (10) - 3.
David E. Ansorge M. Goras L. Grigoras V. 2004 On the Sensitivity of CNN Linear Spatial Filters: Non-homogeneous Template Variations, Proc. of 8-th IEEE Int. Workshop on Cellular Neural Networks and their Applications, CNNA’2004,40 45 . Budapest, Hungary - 4.
Dudgeon D. E. Mersereau R. M. 1984 Multidimensional Digital Signal Processing , Englewood Cliffs, NJ: PrenticeHall, 1984 - 5.
Freeman W. T. Adelson E. H. 1991 The Design and Use of Steerable Filters , IEEE Trans. on Pattern Analysis and Machine Intelligence,13 9 Sept. 1991 - 6.
Hänggi M. Moschytz G. S. 2000 Cellular Neural Networks. Analysis, Design and Optimization, Kluwer Academic Publishers, Boston, 2000 - 7.
Haykin S. 1994 Neural Networks: A Comprehensive Foundation, Macmillan, 1994 - 8.
Matei R. 2001 Cellular Neural Networks with Modified Non-Linearity, Proc. of Int. Symp. Signal Processing and Information Technology, ISSPIT’2001,296 300 , Cairo, Egypt - 9.
Matei R. 2003 Oriented Low-Pass CNN Filters Based on Gaussian 1-D Prototype, Proceedings of 16th European Conf. on Circuit Theory and Design, ECCTD’2003, Vol.II,185 188 , Krakow, Poland - 10.
Matei R. 2004 Design Method for Orientation-Selective CNN Filters, Proceedings of International Symposium on Circuits and Systems ISCAS’2004,3 105 108 ,078038251 Vancouver, Canada, May 23-26, 2004 - 11.
Matei R. 2004 On the Design of a Class of Selective CNN Linear Filters, Proceedings of the 8-th IEEE International Workshop on Cellular Neural Networks and their Applications, CNNA’2004,153 158 , Budapest, Hungary - 12.
Matei R. 2006 Design of a Class of Maximally-Flat Spatial Filters, Proceedings of the IEEE International Symposium on Circuits and Systems ISCAS’2006,2165 2168 ,978-0-78039-389-9 May 21-24, 2006, Kos Island, Greece - 13.
Rodriguez-Vasquez A. et al. 1993 Current Mode Techniques for the Implementation of Continuous- and Discrete-Time Cellular Neural Networks, IEEE Transactions on Circuits and Systems-II,CAS-40 ,132 146 , March 1993 - 14.
Shi B. E. 1998 Gabor Type Filtering in Space and Time with Cellular Neural Networks, IEEE Trans. on Circuits and Systems, CAS-I,45 2 121 132 , Feb. 1998 - 15.
*** CNN Software Library (CSL) (Templates and Algorithms), version 3.1, Analogical and Neural Computing Laboratory, Computer and Automation Research Institute