Extraction of Terrain Features Using Wavelet Packet Decomposition based identification and clustering for Autonomous Navigation

Extraction of Terrain Features Using Wavelet Packet Decomposition based identification and clustering for Autonomous Navigation

Extraction of Terrain Features Using Wavelet Packet Decomposition based identification and clustering for Autonomous Navigation

Jagadishchandra.S.Naik, Dr.N.K.Misra, ISRO Satellite Centre,

Bangalore,India 18 June 2013

1. Rover to moon or mars must require a proper path iden- tification to travel on terrain area without affecting the performance and controllability of vehicle.To enable au- tonomous navigation on terrain as moon or mars, the ter- rain should be analyzed and plan be made in real time to classify the terrain by extracting the features of ter- rain.This is done by taking the pictures surrounding the rover moving area and thereby using image processing techniques with proper algorithm to identify the path suit- able for navigation. We have presented here an algo- rithm with wavelet decomposition, clustering and feature extraction to identify suitable path quickly to navigate through a terrain.

2. The paper presents the extraction of features from lunar as well as other terrains to plan for path planning as well as smooth navigation of rovers over the terrain area.Several technologies have been adopted to get all the features of the terrain. First by taking pictures. Then applying different methodologies to those pictures to identify obstacles for navigation of rover, type of soil, craters, or any other specific features. Automatic rover navigation means it should identify path to navigate along the terrain to explore resources,identify areas for moon colonies etc., For safe navigation the rover should

   perceive the surrounding area by avoiding the difficult and hazardous regions by discriminating the path for traversal.Several methods have been employed in space applications to navigate through mars and moon terrain regions such as object recognition, changes in terrain regions, obstacle avoidance and path manipulation. The major problem in the mars and moon terrain regions is to identify the soily region where the wheels of the rover should not get struck.Lack of information and knowledge and improper analysis of the regionon linel stops navigation and traversal thereby mission has to be aborted.This has happened to NASAs mars exploration in 2006 which has struck several weeks This paper is mainly organized in the following way.

   1. How the terrain analysis is being carried out for traver- sal and navigation in an unknown region.

   2. Steps and methods derived for identifying textures, clustering and path classification.

   3. Finally we presented the results and the suitable algo- rithm for traversing the rover in the respective terrain.

3. Feature extraction methods provide ways to classify ter- rain into various regions for navigation of robot or ve- hicles over the terrain. This has been addressed by var- ious researchers with many methodologies and views. Padma et al[1] uses subbands of wavelets with GLCM

   features for identifying features in the script images. Aba- solo et.al.[2] uses wavelet based quadtree triangulation for identification of height and textures of the terrain. Soundara Pandian et.al[3] used feature extraction and classification based on wavelet packet decomposition and 4-connected flood filling algorithm. Chandok et.al[4]has an approach for segmentation using k-means clustering

   1. Block diagram for Processing

      Start

      algorithm for classification of regions.Umesh.KK et.al.[5] provides a method for web image retrieval using clus- tering of similarity distance computation.Zhegmo et.al[6] applies the k-means clustering with quantitative measures for several clusters. Morphological operations were used by Murthy et.al[7] for text extraction from the image. An- other line of approach for terrain feature identification and classification provides best way to clearly identify fea- tures and classify the image into various navigable and non navigable regions by clustering and segmentation al- gorithms using morphological flood filling and Wavelet based GLCM computation.

4. The issues of feature extraction method discussed in this proposed system from a given image are of various kind and can be segregated using various image processing techniques as binarization, wavelet transformation, clus- tering, morphological procedures, flood filling and classi- fication of texture. The propose system shown in section

   1. below presents a research methodology constitutes feature extraction of images of various terrain scenes de- ploying discrete wavelet packet transform, Gray level co- occurrence matrix, k-means and fuzzy c-means cluster- ing and segmentation. The prominent regions captured from the input binarized image are filtered using discrete wavelet packet transform.We have used the filtered im- ages of wavelet packet transform, k-means and fuzzy c- means clustering to apply morphology and clustering to finally identify the texture for classification of navigable and non-navigable regions for autonomous navigation.

      Wavelet Transform, GLCM features

      Gray Level conversion, Preprocessing

      Feature Extraction

      Clustering(k- means,fuzzy c-means

      Morphological Dilation

      Segmentation and Classification

      End

      1. Original Image

define co-occurrence of image matrix Pd(i,j) is the differ- ence in intensity between a pair of image pixels(i and j), that is distance d pixels apart in original in a given direc- tion.Energy associated with an image that is a measure of textural uniformity of an image is defined by equation.

d

d

Energy = \ \ P 2(i, j)

i j

Figure 1: Discrete Wavelet Transform

1. Discrete Wavelet Transform

Wavelet based methods provided better classification and extraction of features over the years in image processing application. It has been shown that wavelet based meth- ods continue to be powerful mathematical tools and offer computational advantage over other methods for texture classification[1].1D discrete wavelet transforms decom-

poses an input image into mean constituent and detailed

poses an input image into mean constituent and detailed

For a constant value of gray level, the energy measure reaches its maximum value of one. The larger energy cor- responds to a lower gray level value and the smaller en- ergy corresponds to higher gray level value.

1. Entropy: The entropy is a measure of disorder of im- age pixels. Entropy gives the average uncertainty of the information content.Entropy is inversely proportional to energy and is defined by equation

   Entropy = \ \ Pd(i, j)logPd(i, j)

   i

   j

   i

   j

   constituent by estimation with the help of high pass filter and low pass filter whereas 2D discrete wavelet transform decomposes an input image into four bands(LL(mean and constituent),LH, HL, and HH(detailed constituent)[7]. In this, we have tried to extract the features from both ap- proximate and detailed coefficients even through we are able to get many of the features for navigation by the ap-

   i

   j

   i

   j

2. Correlation: is the standard measure of image con- trast to analyse the linear dependency of gray levels of neighbouring pixels.It indicates the local variation across a gray level image.Correlation is formulated as

   \

   \

   \

   \

   M1 N1 µ)(j µ )

   proximation coefficients itself. The convntional filters and detection mechanisms as edge detection operators,

   Correlation =

   i=0

   (i

   j=0

   ij

   i g(i, j)

   maxima and minima operators are experimented to pro- vide the equivalent output too.On comparing with discrete wavelet transform, we felt it a better option as it can iden- tify maximum number of edges and features in a single manipulation that cannot be done by conventional algo- rithm. Gray Level Co-occurrence matrix method of iden- tification of textures have been used since they were pro- posed by Haralick in 1970s.We have calculated the se- lected textures of haralick namely contrast, correlation, energy and homogeneity and some common statistical

   features mean, variance and standard deviation.The haral-

   features mean, variance and standard deviation.The haral-

   where i and j are coordination of co-occrrence matrix. M and N represent total number of pixels in row and column of digital image. g(i,j) is the element in the co- occurrence matrix at the coordinates i and j. µi and i are the horizontal means and variances.

3. Contrast: This measures the amount of local pixel intensity variation within an image and is given by the equation

   Contrast = \ \(i j)2Pd(i, j)

   i

   j

   i

   j

   i

   j

   i

   j

   ick features are calculated with distance 1 and angle 0,45,

   90 and 135.

   4.2.1 Texture Features

   where Pd(i, j) is the image cooccurance matrix

4. Variance: The variance (2) is a measure of how intensity values in the image are far from the mean.The variance is defined as below.

1. Energy : is a measure of how gray level elements are distributed. For a image of intensity matrix I(i,j),we can

V ariance 2 =

n i=1

(Xi µ)2 N

where µ is the mean of intensity values and N is the number of pixels in an image.

6. Standard deviation:The standard deviation is a mea- sure of how spreads out intensity values in image are.A low standard deviation indicates that the pixel value tend to be very close to mean intensity, whereas high stan- dard deviation indicates that the pixel values are spread out over large range of values.

Standard deviation = 2

1. k-means and fuzzy c-means clustering

   Studies shows clustering techniques are capable of image segmentation and have better role in identifying the fea- tures of images. Several algorithms are available for seg- mentation and most widely used are k-means and fuzzy c-means algorithms. There were comparisons based on their capability to perform for segmentation purpose. K- means clustering algorithm was developed by J. Mac. Queen in 1967[9]. The procedure follows a simple and easy way to classify a given data set through a certain number of clusters fixed apriori. K-means clustering al- gorithm is an unsupervised clustering algorithm that clas- sifies the input data points into several classes based on their inherent distance from each other. The algorithm as- sumes the data features form of vector space and tries to find natural clustering i them[4]. In our experiments we have made use of MATLAB function kmeans that is as follows.

   idx = kmeans(X,k) this partitions the points in the nxp matrix X into k clusters. Rows of X corresponds to points, columns corresponds to variable. K-means clustering re- turns nx1 vector idx containing the cluster indices of each point. The objective function for k-means clustering is given as

   1. Place K points into the space represented by the ob- jects that are being clustered. These points represent ini- tial group centroids.

   2. Assign each object to the group that has the closest centroid.

   3. When all objects have been assigned, recalculate the positions of the K centroids.

   4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation of the objects into groups from which the metric to be minimized can be cal- culated.

      fuzzy c-means clustering(FCM) algorithm was first in- troduced by Dunn[9] and later extended by Bezdeck[9 ]. In this technique, the clustered are formed using hard par- titioning.The FCM works on the fact that a data point can belong to all groups with different grade of membership between 0 and 1.

2. Morphology and Segmentation

Morphological processing is a collection non-linear oper- ations related to the shape or morphology of features in an image.Morphological techniques probe an image with a small shape or template called a structuring element. The structuring element is positioned at all possible locations in the image and it isin comparison with the correspond- ing neighbourhood of pixels. Some operations test regard- less of whether the element fits within the neighbour- hood, whereas others test regardless of whether it hits or intersects the neighbourhood.The most basic morpho- logical operations are dilation and erosion. Dilation adds pixels to the boundaries of objects in an image, whereas erosion removes pixels on object boundaries. The number of pixels added or removed from the objects in an image depends on the size and shape of the structuring element used to process the image.

k

k

n

n

x(j)

vj i

x(j)

vj i

2

J =

j=1 i=1

J =

j=1 i=1

J =

j=1 i=1

J =

j=1 i=1

where x(j) v 2 is a choosen distance measure be-

1. System Overview

   i j

   tween a data point xi and the cluster centre vj , is an in- dicator of the distance of the n data points from their re- spective cluster centres. The algorithm ic composed of the following steps.

   For terrain traversal and navigation it is required to identify relevant features that should be easily com- putable and robust. The proposed method consists of decomposing the image into subband images. Texture

   is a measure of the variation in spatial intensity. The features of the texture include contrast, entropy, energy, variance etc., First the image in fed to the wavelet packet decomposition unit. Once the decomposed image is obtained it is submitted to Feature extractor that uses segmentation using entropy, range and standard deviation filters. We havedone the comparison of the data using Gray Level Cooccurrence matrix(GLCM) where we calculated the properties such as contrast, energy,entropy

   clusters and segmented, we have classified the regions using Morphological dilation of the gray image.

   Step 4: Segmentation is used to get the regions of interest. The clusters are segmented and classified w.r.t threshold. Matlab scripts are used to get the results.

2. Texture Features Table

   and correlation. After obtaining the DWT output we have

   classification is done through segmentation technique.	p 0.0263	0.7903	0.9938	0.9988	0.7579
   Then we applied k-means clustering algorithm to the	q 0.0363	0.8868	0.9899	0.9987	0.9652
   regions where we identified navigable and non-navigable	r 0.0002	0.5000	0.9999	1.0000	0.6253

   classification is done through segmentation technique.	p 0.0263	0.7903	0.9938	0.9988	0.7579
   Then we applied k-means clustering algorithm to the	q 0.0363	0.8868	0.9899	0.9987	0.9652
   regions where we identified navigable and non-navigable	r 0.0002	0.5000	0.9999	1.0000	0.625

   passed it to get region based maxima and minima and

   Image Contrast Correlation Energy Homogeneity Entropy

   regions of the terrain.This inturn,gives us plan to iden- tify a path for navigation of terrain for autonomous robots.

   Step 1:Our approach is to obtain features through wavelet decomposition of the image and that has been carried out in two levels. The result of that are approxi- mation(A), Horizontal(H), Vertical(V) and Diagonal(D) coefficients.Wavelet packet decomposition is a technique where a signal is passed through various filters(low pass and high pass)than the discrete wavelet transform.The intensity information is also evaluated to identify fea- tures.The statistical features mean, standard deviation and entropy is used by the algorithm after obtaining the results through DWPT. We have done the comparison of the features with the features obtained by gray level cooc- currence matrix(GLCM),in which we get the following features energy, entropy, contrast and correlation.

   Step2: The next step deals with K-clustering and fuzzy c-means clustering for feature extraction and classifi- cation. The algorithm is executed by using MATLAB functions to get clusters in the images. We have initially planned for navigable and non navigable regions using 2 clusters. We can also take up 3 clusters to identify less navigable if there is large area of resources in non navigable regions is blocked. We have identified 3 images of different dimensions, place and type where we have done comparison of the k-means clustering with fuzzy c-means clustering. Fuzzy c-means clustering gives better selection of features,but it has a drawback of using more CPU time for iterations.

   step 3:Next comes, identification of navigable and non navigable regions. Once after identifying different

   s 0.0048 0.4999 0.9992 0.9998 0.7281

   Table 1: Wavelet Decomposition Texture Features for Ap- proximation Details

   Image Contrast Correlation Energy Homogeneity Entropy

   x 26.2210	-0.2891	0.1599	0.3953	0.9652
   y 30.5677	-0.3511	0.2104	0.3800	0.9652
   y 6.7735	-0.1457	0.2591	0.6100	0.9652

   z 31.99675 -0.3620 0.2513 0.3958 0.9652

   Table 2: Wavelet Decomposition Texture Features for Di- agonal Details.

1. The experiments were conducted in HP Z-400 worksta- tion with intel Xeon(R) CPU of 3.19GHz, 16GB mem- ory and Windows7 operating system. Figure.2(a) and fig3(a).shows the images of 331x484x3 bits size and 1080x1920x3 bit size respectively. 20 different types of images are considered for experiment. The graphics card used is NVidia Quadro 2000.

   The input image is binarized into gray scale image that is then subjected to discrete wavelet transform. We have obtained the Gray Level Cooccurrence matrix for approx- imation and detailed coefficients of subband images.Then the processed images are subjected to both k-means and

   fuzzy c-means clustering protocol. The image is chosen based on the faster convergence rates of the algorithm. The better image is chosen from this set of outputs based on Morphological operations to fill the holes have been conducted on the images to remove small objects. Finally the image is segmented and classified to be used by the ap- plication of navigation. The results in fig.2 and 3 shows the output of two of such images that has gone through various processes.We can observe the marked areas that are not navigable in the segmented image. This clearly classifies the navigable and non-navigable regions.

   Algorithm is Implemented as follows.

   1. Input the image

   2. If the image is RGB convert to Gray Scale image

   3. Pass the image through discrete wavelet transform.

   4. Get the two levels of decomposition of wavelets.

   5. Apply GLCM to the Approximation Level coefficients.

   6. Calculate the selected haralick features and statistical parameters.

   7. Apply k-means clustering Algorithm.

   8. Get the k-means clustering Image.

   9. Fill image regions and holes(Morphological dilation).

   10. Apply fuzzy c-means and Get the image.

   11. Fill image regions and holes.

   12. Segment the image and classify the image based on threshold.

2. The terrain classification method applied here uses wavelet method with k-means clustering and fuzzy c- means clustering based on several iterations for conver- gence of the image as well as morphological dilation for segmentation and classification. This approach allows us to identify regions that can provide more accuracy than the other methods described in the past. Our method uses morphological dilation that helps in removing less non- navigable areas, in turn help for classification of regions for navigation.

   We can observe that we have used GLCM matrix method of extracting features, statistical as well as haralick. These features allows us to extract more of the characteristic fea- tures of the image. The morphological features takes us to shape and size of the objects that in turn help us to clas-

   sify regions for navigational purpose. The clustering pro- cess gives us the strength of the objects around and com- bination of it with GLCM features we can get the type of materials present. In addition to all this wavelet transfor- mation of the image provides the filtering of the normals of the process. This extraction method has an advantage of processing in a most faster and reliable way except for the underground holes or gaps or deep stuffs present under the ground.

In this paper, we have presented texture classification, fea- ture extraction aspects for classification of terrain for au- tonomous robot navigation. This method has several ad- vantages. This method allows us to choose amongst the algorithms based on the requirement of navigation as the terrain features are different in different places. Some- times the navigation may be completely blocked from the one side of the terrain to the other side because of non nav- igable area. In such cases, we have made use of k-means clustering and segmentation method by which we can ex- tract less navigable regions from non navigable regions. We have used flood filling of holes along with segmen- tation for classifying the terrain image.These algorithms are implemented using MATLAB. In future, the line of in- quiry may be used to develop improved method for identi- fying regions even in the rocky, hilly and muddy areas for navigation. In addition we have a plan to get better fea- ture extraction methods to identify the properties of the bodies around and also to apply neural network classifiers for intelligent extraction and navigation.

Acknowledgement The authors are grateful to Dr.S.K.Shivakumar, Director, ISRO Satellite Centre, Bangalore, India for his valuable support.

1. M.C.Padma, P.A.Vijaya, Wavelet packet Based Au- tomatic script Identification, International Journal of Image Processing, Volume 4. Issue(1).

2. Abasolo, Parales, Wavelet Analysis for New Reso- lution Model for large scale textured terrains, Jour-

   1. Original Image

   2. Wavelet Image

   3. k-means Image

   4. Morphologically dilated Image

   5. Segmented Image

      Figure 2: Terrain Image Sample1

      1. Original Image

      2. Wavelet Image

      3. k-means Image

      4. Morphologically dilated Image

      5. Segmented Image

         Figure 3: Terrain Image Sample2

         nal of WSCG, Vol11.No1, WSCG2003, February 3- 7, 2003.

3. Soundara Pandian, Priyanka Mathur.,Wavelet Packet Based Traversible Terrain Classification For Autonomous Robot Nvigation International Journal of Computer and Electrical Engineer- ing,Vol.4,No 5, October 2012.

4. .Chandok, Chaturvedi,Khurshid., An approach to Image Segmentation using k-means clustering Algorithm, International Journal of Information Technology(IJIT),Volume-1, Issue-1,August-2012.

5. Umesh K K and Suresha, Web Image Retrieval Using Clustering Approaches, AIAA 2011, Com- puter science and Information Technology,pp.27-36, 2011.

6. Zhengmao Ye, Habib Mahamadian, The Role of Quantitative Metrics in Enhancing Spatial Informa- tion Retrieval via Fuzzy K-means Clustering, , .

7. Narasimha Murthy KN, Kumaraswamy,A novel method for efficient text extraction from real time images with diversified background using Haar Dis- crete Wavelet Transform and k-means clustering IJCSI international Journal of Computer Science Is- sues,Vol.8, Issue 5, No 3, September 2011.

8. Sunita P.Aware, Implementation of Image Re- trieval using Co-occurrence matrix and Texton Co- occurrence Matrix, MEDHA-2012, Proceedings published by International Journal of Computer Ap- plication(IJCA) 2012..

9. Aghajari.,D.C.Gharpure,Segmentation Evalua- tion of salient object extraction using k-means and fuzzy c-means clustering International Journal of Advanced Electrical and Electron- ics Engineering(IJAEEE),2278-8948. Volume-1, Issue-2,2012.