 Open Access
 Total Downloads : 212
 Authors : Jagadishchandra. S. Naik, Dr. N. K. Misra
 Paper ID : IJERTV2IS80656
 Volume & Issue : Volume 02, Issue 08 (August 2013)
 Published (First Online): 21082013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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

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.

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.

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

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

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


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 4connected flood filling algorithm. Chandok et.al[4]has an approach for segmentation using kmeans clustering

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 kmeans 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.


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

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, kmeans and fuzzy cmeans 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, kmeans and fuzzy c means clustering to apply morphology and clustering to finally identify the texture for classification of navigable and nonnavigable regions for autonomous navigation.
Wavelet Transform, GLCM features
Gray Level conversion, Preprocessing
Feature Extraction
Clustering(k means,fuzzy cmeans
Morphological Dilation
Segmentation and Classification
End

Original Image


define cooccurrence 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

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.

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

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 Cooccurrence 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 cooccrrence 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.

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

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

kmeans and fuzzy cmeans 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 kmeans and fuzzy cmeans 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. Kmeans 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. Kmeans clustering re turns nx1 vector idx containing the cluster indices of each point. The objective function for kmeans clustering is given as

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

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

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

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 cmeans 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.


Morphology and Segmentation
Morphological processing is a collection nonlinear 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

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.

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 kmeans clustering algorithm to the
q 0.0363
0.8868
0.9899
0.9987
0.9652
regions where we identified navigable and nonnavigable
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 kmeans clustering algorithm to the
q 0.0363
0.8868
0.9899
0.9987
0.9652
regions where we identified navigable and nonnavigable
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 Kclustering and fuzzy cmeans 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 kmeans clustering with fuzzy cmeans clustering. Fuzzy cmeans 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.

The experiments were conducted in HP Z400 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 kmeans and
fuzzy cmeans 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 nonnavigable regions.
Algorithm is Implemented as follows.

Input the image

If the image is RGB convert to Gray Scale image

Pass the image through discrete wavelet transform.

Get the two levels of decomposition of wavelets.

Apply GLCM to the Approximation Level coefficients.

Calculate the selected haralick features and statistical parameters.

Apply kmeans clustering Algorithm.

Get the kmeans clustering Image.

Fill image regions and holes(Morphological dilation).

Apply fuzzy cmeans and Get the image.

Fill image regions and holes.

Segment the image and classify the image based on threshold.


The terrain classification method applied here uses wavelet method with kmeans 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 kmeans 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.

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

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

Original Image

Wavelet Image

kmeans Image

Morphologically dilated Image

Segmented Image
Figure 2: Terrain Image Sample1

Original Image

Wavelet Image

kmeans Image

Morphologically dilated Image

Segmented Image
Figure 3: Terrain Image Sample2
nal of WSCG, Vol11.No1, WSCG2003, February 3 7, 2003.



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.

.Chandok, Chaturvedi,Khurshid., An approach to Image Segmentation using kmeans clustering Algorithm, International Journal of Information Technology(IJIT),Volume1, Issue1,August2012.

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

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

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 kmeans clustering IJCSI international Journal of Computer Science Is sues,Vol.8, Issue 5, No 3, September 2011.

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

Aghajari.,D.C.Gharpure,Segmentation Evalua tion of salient object extraction using kmeans and fuzzy cmeans clustering International Journal of Advanced Electrical and Electron ics Engineering(IJAEEE),22788948. Volume1, Issue2,2012.