Abstract: Resolution of images for Geographical Information System (GIS) was usually desired to be as high as possible. The higher resolution of the image is larger its data size. The large data size of a high resolution image brings difficulties in dealing with it. Therefore, image compression is going to be required. But high compression rate cause of some distortion and losses. Restoration was a process by which an image suffering some form of distortion or degradation can be recovered to its original form. This research describes a framework for GIS image compression, decompression and restoration using neural networks.
INTRODUCTION
Geographic Information System (GIS) is an integrated system of computer hardware and software coupled with procedures and human analyst which together support the capture, management, manipulation, analysis, modeling and display of spatially referenced data. Data for a GIS comes in three basic forms, all of which are demonstrated in Fig. 1.
Spatial data: made up of points, lines and areas, is at the heart of every GIS. Spatial data forms the locations and shapes of map features such as buildings, streets, or cities.
Tabular data is information describing a map feature. For example, a map of customer locations may be linked to demographic information about those customers.
Image data includes such diverse elements as satellite images, aerial photographs and scanned data-data that's been converted from paper to digital format. Images can be displayed as maps along with other spatial data containing map features. Image data offers a quick way to get spatial data for a large area and is more cost- and time-effective than trying to collect layers of data like buildings, roads, lakes, etc., one at a time. However, image data is one file, or layer, so you can not break down the different components and attach data to them separately. Image data is the best choice if you need to add a point of reference to vector data without attaching additional information.
Each GIS image has minimum 256x256 pixels and 256 gray levels. Therefore 65536 bytes of memory is needed for an image of GIS. In an average sized computer, many tera-bytes of digital imaging data are generated every year, almost all of which has to be kept and archived.
| Fig. 1: | Spatial data, tabular data and image data illustrated in a
single map |
Archiving this large amount of image data in the computer memory is very difficult without any compression[1].
Currently used image compression techniques can be separated in two groups: lossless or reversible compression and lossy, or irreversible compression. Lossless compression allows the reconstruction of the original image data from the compressed image data. With lossy compression a higher compression rate is possible by allowing small difference between original images and reconstructed images. Large compression gains may be achieved only if data distortion is allowed i.e. when using lossy compression algorithms. Although the resulting distortion may be very small with respect to the signal to noise ratio, such algorithms is not lossless and hence does not guarantee that critical features will not be lost[2]. A combination of lossless and lossy compression is advantageous if only a subset of the data set is of interest to the physician and engineer. Lossy compression is also needed to facilitate fast browsing through a large database of images, since a rough data preview may be performed easily and efficiently by a lossy encoded version of the original data-set. In fact, a good approximation stored in a lossy way provides a preview image of much higher quality than a reduced resolution of the original image transmitted losslessly. The data omission in conventional lossy image compression is mostly based on commonly accepted models of the image[3]. In lossless algorithms like Huffman coding the compression ratio is limited and very low. In lossy compression algorithms we can obtain high compression rates but the MSE also increases. Because of this problem, we have to reduce noise of image as a MSE using one of the image restoration methods. This research study describes the development of a framework for adaptive image compression, decompression (or reconstruction) and restoration by using three neural networks structures for the GIS. Delphi is used to develop a windows-based image compression and restoration. Figure 2 describes block diagram of ANN technique for image compression and restoration.
NEURAL NETWORKS-BASED IMAGE COMPRESSION
Apart from the existing technology on image compression represented by series of image standards (JPEG, MPEG and H.26x), new technology such as neural networks and genetic algorithms are being developed to explore the future of image coding. Successful applications of neural networks to vector quantization have now become well established and other aspects of neural network involvement in this area are stepping up to play significant roles in assisting with those traditional compression techniques.
There are a various methods about lossy image compression techniques such as Vector quantization; transform coding, predictive coding and block truncation coding are some of the lossy compression techniques[1,4,5]. Artificial Neural Networks (ANN) can use for image compression and reconstruction. The basic back-propagation network can be further extended to construct a hierarchical neural network by adding two more hidden layers into the existing network, in which the three hidden layers are termed as combiner layer, compressor layer and decombiner layer. The structure can be shown in Fig. 3. The idea is to exploit correlation between pixels by inner hidden layer and to exploit correlation between blocks of pixels by outer hidden layers.
|
| |
| Fig. 2: | Block diagram of ANN technique for image compression and restoration |
| Fig. 3: | Hierarchical neural network structure |
From input layer to combiner ayer and decombiner layer to output layer, local connections are designed, which has the same effect as M fully connected neural sub-networks.
Training of such a neural network can be conducted in terms of: (i) Outer Loop Neural Network (OLNN) Training; (ii) Inner Loop Neural Network (ILNN) Training; and (iii) Coupling weight allocation for the Overall Neural Network.
ADAPTIVE BACK-PROPAGATION NEURAL NETWORK
Adaptive back-propagation neural network is designed to make the neural network compression adaptive to the content of input image. The general structure for a typical adaptive scheme can be illustrated in Fig. 4, in which a group of neural networks with increasing number of hidden neurons, (hmin, hmax), is designed. The basic idea is to classify the input image blocks into a few sub-sets with different features according to their complexity measurement. A fine tuned neural network then compresses each sub-set.
Training of such a neural network can be designed as: (a) parallel training; (b) serial training; and (c) activity based training;
| Fig. 4: | Adaptive neural network structure |
The parallel training scheme applies the complete training set simultaneously to all neural networks and use S/N (signal-to-noise) ratio to roughly classify the image blocks into the same number of sub-sets as that of neural networks. After this initial coarse classification is completed, each neural network is then further trained by its corresponding refined sub-set of training blocks.
Serial training involves an adaptive searching process to build up the necessary number of neural networks to accommodate the different patterns embedded inside the training images. Starting with a neural network with pre-defined minimum number of hidden neurons, hmin, the neural network is roughly trained by all the image blocks. The S/N ratio is used again to classify all the blocks into two classes depending on whether their S/N is greater than a pre-set threshold or not. For those blocks with higher S/N ratios, further training is started to the next neural network with the number of hidden neurons increased and the corresponding threshold readjusted for further classification. This process is repeated until the whole training set is classified into a maximum number of sub-sets corresponding to the same number of neural networks established.
In the next two training schemes, extra two parameters, activity A(Pl) and four directions are defined to classify the training set rather than using the neural networks. Hence the back propagation training of each neural network can be completed in one phase by its appropriate sub-set. The so called activity of the lth block is defined as:
| (1) |
| (2) |
where Ap(Pl(i,j)) is the activity of each pixel which concerns its neighboring 8 pixels as r and s vary from -1 to +1 in Eq 2.
ANN-BASE IMAGE RESTORATION
To restore an image degraded by a linear distortion, a restoration cost function is developed. The cost function is created using knowledge about the degraded image and an estimate of the degradation and possibly noise, suffered by the original image to produce the degraded image. The free variable in the cost function is an image, often denoted by and the cost function is designed such that minimizes the cost function is an estimate of the original image. A common class of cost functions is based on the Mean Square Error (MSE) between the original image and the estimate image. Cost functions based on the MSE often have a quadratic nature. The act of attempting to obtain the original image given the degraded image and some knowledge of the degrading factors is known as image restoration. The problem of restoring an original image, when given the degraded image, with or without knowledge of the degrading Point Spread Function (PSF) or degree and type of noise present is an ill-posed problem and can be approached a number of ways[6-11]. For all useful cases a set of simultaneous equations is produced which is too large to be solved analytically. Common approaches to this problem can be divided into two categories, inverse filtering or transform related techniques and algebraic techniques[1].
All linear image degradations can be described by their impulse response. Consider a Point Spread Function (PSF) of size P by P acting on an image of size N by M. In the case of a two-dimensional image, the PSF may be written as when noise is also present in the degraded image, as is often the case in real world applications, the image degradation model in the discrete case becomes[6]:
| (3) |
Where, f(x,y ) and g(x,y) and are the original and degraded images respectively and n(x,y) is the additive noise component of the degraded image. If h(x,y) is a linear function then by lexicographically ordering, f(x,y,), g(x,y) and n(x,y) into column vectors of size NM, we may restate (3) as a matrix operation[7]:
| (4) |
Where, g and f are the lexicographically organized degraded and original image vectors, n is the additive noise component and H is a matrix operator whose elements are an arrangement of the elements of h(x, y) such that the matrix multiplication of f with H performs the same operation as convolving f(x, y) with h(x, y). In general, H may take any form. However, if h(x,y) is spatially invariant with P<<min(N, M) then h(x, y; α, β) becomes h(x-α, y-β) in (3) and H takes the form of a block-Toeplitz matrix. If h(x, y) has a simple form of space variance then H may have a simple form, resembling a block-Toeplitz matrix. In this study, the degradation measure we consider minimizing starts with the constrained least square error measure[8]:
| (5) |
Where, f ˆ is the restored image estimate, λ. is a constant and D is a smoothness constraint operator. Since H is often a low pass distortion, D will be chosen to be a high pass filter. The second term in (5) is the regularization term. The more noise that exists in an image, the greater the second term in (5) should be, hence minimizing the second term will involve reducing the noise in the image at the expense of restoration sharpness. Choosing λ. becomes an important consideration when restoring an image. Too great a value of λ. will over-smooth the restored image, whereas too small a value of λ. will not properly sup-press noise.
Neural network image restoration approaches are designed to minimize a quadratic programming problem[7-11]. The general form of a quadratic programming problem can be stated as: Minimize the energy function associated with a neural network given by:
| (6) |
Comparing this with (5), W, b and c are functions of H, D, λ.. and n and other problem related constraints. In terms of a neural network energy function, the (i,j)th element of W corresponds to the interconnection strength between neurons (pixels) i and j in the network. Similarly, vector b corresponds to the bias input to each neuron. Equating the formula for the energy of a neural network with Eq. 5, the bias inputs and interconnection strengths can be found such that as the neural network minimizes its energy function, the image will be restored. From[11], setting L = MN, the interconnection strengths and bias inputs were shown to be:
| (7) |
| (8) |
where, wij is the interconnection strength between pixels i and j and b i is the bias input to neuron (pixel) i. In addition, hij is the (i,j)th element of matrix H from equation (4) and d ij is the (i,j)th element of matrix D from Eq. 5.
EXPERIMENTAL RESULTS
In this study, an adaptive three neural network algorithms were presented. This presented neural network algorithms have been divided such as image compression, decompression and restoration. As you can see in Fig. 1, first the image is compressed using ANN1 and then this compressed image is reconstructed by ANN2. This reconstructed image has some distortion and lossy. So the last stage the reconstructed image is made restoration by ANN3. The proposed windows-based image compression and restoration programs were implemented using Delphi (Fig. 5).
It can bee seen in Fig. 4, the input image is arranged into blocks of squares of 4x4, 6x6, 8x8, etc, pixels belong to user. Optimum learning rate was taken as 0,01 after 500 iterations (Fig. 6).
Several GIS images were used as a bmp file in experimental. All images have 256x256 digital gray-levels. The size of sample of GIS images, which are used as input to the adaptive neural networks, is approximately 50 Kbyte.
| Fig. 5: | Program monitoring |
| Fig. 6: | Errors of different learning rates |
| Fig. 7a-c: | Original GIS image-1 b) Reconstructed image c) Restorated
image |
| Table 1: | Experimental results |
The experiments were carried out with the number of squares of 2, 3, 4, 6 and 8 for the topographical image. Table 1 shows the experimental results for 1000 iterations.
Compression results from Artificial Neural Networks were taken in real-time. Mean Square Error (MSE) formulation is shown in Eq. 9. In addition, Peak Signal-to Noise Ratio (PSNR) formulation is given by using Eq. 10.
| (9) |
| (10) |
| Fig. 8a-c: | Original GIS image-2 b) Reconstructed image c) Restorated
image |
A number of experiments were conducted to evaluate the performance of the proposed method. Figure 7 and 8 show original, reconstructed and after restoration GIS images, respectively. For this images compression ratio is 1/10
CONCLUSIONS
The experimental result shown that the proposed method can compress the multi-spectral image GIS data. The compressibility of this method and the image distortion from quantizing process depends on the number of clusters used in adaptive neural network process. Neural network image compression technique is a lossly technique. So the reconstructed image has some distortion and noisy. It needs a restoration. It can be seen Fig. 5c and 6c, the GIS images are getting better after restoration.
These results show that the adaptive neural network algorithm appears to give extremely good performance for GIS image compression and may be very useful in practical implement the other type of images such as SAR images and digital picture archiving and communications systems. It should be noted that the above-mentioned PSNR and MSE can be varied and the selected areas can be adjusted to other types of images.