Implementation of R-Trees for Spatial Image Processing and Cloud detection

Implementation of R-Trees for Spatial Image Processing and Cloud detection

Pathak Siddharth D.

Department of computer engineering AISSMS College of engineering, Pune, Maharashtra, India

Thakur Siddharth J. Department of computer engineering

AISSMS College of engineering, Pune, Maharashtra, India

Shitole Siddharth J. Department of computer engineering

AISSMS College of engineering, Pune, Maharashtra, India

D. P. Gaikwad Department of computer engineering

AISSMS College of engineering,

Pune, Maharashtra, India

Satam Tejas S.

Department of computer engineering AISSMS College of engineering, Pune, Maharashtra, India

AbstractVery large amount of data is generated by earth observing satellite. Hence there is pressing need for an intelligent image processing technique to process this huge amount of data in conventional method. Spatial images are used for weather monitoring and forecasting. The parameters from the spatial images are extrapolated for this purpose. The previous methods used for the processing of spatial data are quite unconventional in terms of processing speed. In this paper we present a bracing technique for processing of spatial images. R Tree is a top-down approach. We firstly segment the spatial image into subareas which acts as the nodes in the R-trees, these are further subdivided into subparts. The leaf nodes would give the features on map of smallest divided area. Secondly we retrieve the parameters from the leaf nodes which provides us exact values on the spatial image. Our approach has been tentatively validated against conventional ones yielding enhanced precision.

KeywordsR trees; Ostu binarize; spatial image; Cloud cover; forecasting.

1. INTRODUCTION

   Satellite images are used in day to day applications directly or indirectly. The data collected by the satellite imagery is in immensely vast amount. These images are not put into use directly by an organization. They need to be processed before deducing any results. Manual annotation needs to annotate every detail by human himself [1]. The conventional methods used to process images were using matrices, chains and graphs or in hierarchical pattern were pyramids, quad trees. These would take very long time to process such infinite data. Thus, we propose to make the use of R trees for this purpose. R trees is a dynamic data structure for spatial indexing, it is a depth

   balance tree. R trees can be used for storing geometric and multi-dimensional data.Here we intend to use the R trees to detect the overall cloud cover from the spatial images.

2. INTRODUCTION TO R TREES.

   1. Foundation of R Trees.

      B trees provided the base for R Trees. It is data structure for storing sorted data. B Tree is used often for data stored on long latency I/O because child nodes can be accessed together as a whole since they are in order. But, the major drawback regarding B Trees is that they cannot store geometric data and multi-dimensional data. This prompted the need for a data structure that organizes multi-dimensional data.

      R Trees was proposed by Antonin Guttmann in 1984. It is a depth balance tree. R Trees is a dynamic indexed structure used for spatial searching and organizes the region in minimum bounding regions (MBR). The leaf nodes of the tree point to actual objects.

   2. Operations performed on R Trees.

   Insertion in R Trees is carried out to insert in node through search and insert. If the node is which insertion is carried is out is completely filled, overflow occurs and hence the node is split. Deletion in R Tree can result into underflow, other nodes need to be inserted to maintain balance. Searching can be carried out in R Trees, it can be based on some predefined value of color. And finally splitting of node, it splits the region into multiple regions.There are three ways of splitting the

   node- Linear split, Quadratic split, Exponential split. The only criteria for splitting is MBR area enlargement.

   Below fig 2.1 shows the structure of R Tree.

   Fig 2.1 Structure of R Tree

   In the above described figure, R is the parent node, R1 and R2 are the intermediate nodes and R11, R12, R13, R14, R21, R22, R323 and R24 are the leaf nodes. All the nodes represent MBRs. The intermediate nodes point to the child nodes and leaf nodes represent the actual values on the image.

3. RELATED WORK

   For weather forecasts, generally experimental and dynamical approaches are considered. Weather forecasting systems virtually make use of combination of experimental and dynamical techniques. Lim etal proposed cloud field segmentation via multiscale convexity analysis [2]. In [3] multispectral classification of spatial images from meteorological department using pixel clustering is described. Satellite cloud image segmentation based on improved normalized cuts model was proposed by wenlong etal [2]. An area based, shape preserving morphological segmentation scheme for cloud extraction was developed by dipti etal [4]. Thus in case of natural calamities, the damage to the society and nation as a whole would be too great. Thus there is a pressing need to generate an intelligent computing system for interpretation of upcoming danger especially key out the cloud cover. This structure of this research paper is: section 4 describes the Ostu Binarization algorithm that is used to segment the cloud cover over the region. Section 5 explains the implementation of R Trees over these binarized images to detect the region covered by clouds. Eventually section 6 describes the conclusion and future scope.

4. CLOUD SEGMENTATION BY OSTU BINARIZATION

   A binary image is an image with only two values for its pixels (0 and 1 or 0 and 255). Binary images arise in digital image processing as a result of certain operations like segmentation, thresholding and dithering. Edges are crucial in image analysis and above algorithm is used to detect edges in image. To binarize our image, we use Ostus method created by Nobuyuki Ostu. The algorithm assumes that image to be thresholded contains two classes of pixels then calculates the optimum threshold separating those two classes so that their combined intra-class variance is minimal. The highlights of this algorithm is its speed and easiness of implementation.

   To binarize an image, we need to define the threshold. This can be done manually. The next step involves iterating through all possible threshold values and calculating a measure of spread for the pixel level each side of threshold i.e. pixel that either fall foreground or background. The objective is to find threshold value where sum of foreground and background spread is at its minimum.

   The figure 3.2 shows the Ostu binarized image of image 3.1

   Fig 3.1 Color composite image

   Fig 3.2Binarized image of above Color composite image

   1. Mathematical model of Ostu Binarization [5].

      q1and q2 represent the estimate of class probability defined as [5]:

      Sigmas are the individual class variance defined as [5]:

      And class means [5]:

      represents image histogram. The problem of minimizing within class variance is expressed as maximization problem of the between class variance. It is written as difference of total variance and within class variance [5]:

   2. Algorithmic approach of Ostu Binarization [5]:

      1. Separate the pixels into two clusters according to the threshold.

      2. Find the mean of each cluster.

      3. Square the difference between the means.

      4. Multiply by the number of piels in one cluster times the number in the other.

   By the mathematical model, steps taken are as [5]:

   1. Compute histogram and probabilities of each intensity level.

   2. Set up initial and

   3. Step through all possible threshold maximum intensity.

   4. Update and .

   5. Compute .

   6. The desired threshold corresponds to the maximum.

5. DETECTION OF CLOUD COVER USING R TREES

To present the execution of R Trees for detection of cloud cover, spatial images captured by KALPANA- I sector in

infrared band are taken from Indian Meteorological Department website.

Fig 5.1 Implementation of R Tree on Binarized image.

The rectangles denote the nodes of R Tree. Here, the red rectangles R1 and R2 are the parent node of the tree and are present at the level 0 in the tree. The yellow rectangles are the child nodes of the parent node R1. The children of R1 are R11, R12, R13 and R14. The green rectangles are the child nodes of the parent node R2. The child nodes of R2 are R21, R22, R23 and R24.

A. Methodology of implementation :

The latitudes and longitudes are mapping lines of earth. The latitude of India ranges from 7º30'N to 35ºN and longitude ranges from65º66'E to 97º30'E.

When the specific region is searched for the presence of cloud cover the R Tree will be searched from the root node until the region is found. The cloud cover will be identified by processing R Tree over binarized image.

The world-wide flat grid for easy computation is provided by the Universal Transverse Mercator coordinate (UTM). According to this subdivision, India is subdivided into grids of 16×16. The latitude and longitude are estimated roughly as follows:

Fig 5.2 approximate latitude & longitude mapping

The region to be searched for the cloud cover will be searched from the root node until the node of interest is found. With the help of R Trees, we do not need to scan the entire image for searching our index, instead the node pointing to the value which corresponds to the location of our index would be selected. And the data from root node is extracted.

Thus, R Trees provides better alternative to the conventional pixel by pixel processing on matrix.

CONCLUSION

This paper propose a new method of processing spatial images and cloud detection for weather forecasting using Ostu binarization and R Trees. There are other conventional ways for cloud detection, but the efficiency of R Trees is better than any other methods available. Hence, in future this technique can be used for weather monitoring and forecasting on larger scale.

ACKNOWLEDGMENT

This research was supported by numerous people. Were grateful to our research guide professor D. P. Gaikwad. The authors would like to thank department of Computer,AISSMS COE for their support.

REFERENCES

1. N. Laban, M. ElSaban, A. Nasr, and H. Onsi, Spatial Cloud Detection and Retrieval System for Satellite Images (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 3, No. 12, 2012.

2. Dr. Mohammed mansoor roomi, R Bhargavi, T.M Hajira rahima banu, Automatic identification of cloud cover regions using SURF (IJCSEIT) International Journal of computer science, engineering and information technology, Vol. 2, No.2, April 2012.

3. Isaac J.H. Leung, James E. Jordan, `Image Processing for Weather Satellite Cloud Segmentation," Electrical and Computer Engineering,Canadian Conference., vol.2, pp. 953-956,Sep 1995, in press.

4. Fei wenlong Lv hong wei zhihui Satellite cloud image segmentation based on improved normalized cuts model, Information Science and Engineering (ICISE), 2009 1st international conference.2009, in press.

5. http://zerocool.is-a-geek.net/?p=376, Java image binarization using Ostus binarization.