An intelligent approach towards automatic shape modelling and object extraction from satellite images using cellular automata-based algorithms

Abstract

Automatic feature extraction has witnessed the use of many intelligent methodologies over the past decade. However, inadequate modelling of feature shape and contextual knowledge has limited the detection accuracy. In this article, we present a framework for accurate feature shape modelling and contextual knowledge representation using advanced techniques such as Vector Machines, Cellular Neural Network (CNN), coreset, and Cellular Automata (CA). CNN was found to be effective in modelling different complex features, and the complexity of the approach was considerably reduced using corset optimization. Spectral and spatial information was dynamically combined using adaptive kernels when representing contextual knowledge. The methodologies were compared with contemporary methods using different statistical measures. Application of the algorithms to satellite images revealed considerable success. The methodology was also effective in providing intelligent interpolation and interpretation of random features.

Keywords:

• cellular automata
• remote sensing
• object extraction

Introduction

Detection and identification of objects from satellite images is a prerequisite of many remote sensing applications. However, accurate and robust detection have been affected by various factors such as geometrical complexity, noise, vague boundaries, mixed pixel problems, and fine characteristics of detailed structures (Daniel, Hong, and Zhang 2006; Jacek, James, and Gene 2004). Accuracy attainable using pixel-based classification techniques has been limited due to increased resolution of images which in turn popularized object-based approaches (Vapnik 1998; García 2012). Different existing object extraction algorithms are specific to the features and adopt computationally complex methods (Yuan 2009; Sunil et al. 2004; Daxiang 2012). The efficiency of these methods tends to be situation and image-specific due to the involvement of various parameters like spatial and spectral resolution and sensor characteristics (Trinder and Li 1995; Mnih and Hinton 2010).

There has been a great deal of recent research on improving the accuracy of feature-based strategies (Pengcheng, Zhao, and Feng 2010; Carlos et al. 2012). Computing techniques such as neural networks, genetic algorithms, and fuzzy logic followed by probabilistic concepts such as random field variations have been extensively applied (Lari and Ebadi 2011; Wang et al. 2009; Chi 2004). Research has also involved many object enhancement filters as well as intensity-based approaches (Jenssen et al. 2003; Haralick, Watson, and Laffey 1983). N-dimensional classifiers as well as random field concepts and different transformation techniques have also been used (Hosseini and Homayoun 2009; Kumar and Hebert 2003; Chang and Kuo 2006). Contextual information is a key factor for real-time detection to avoid ambiguity. Knowledge-based classification approaches such as predicate calculus have also been recently used in this context (Porway et al. 2008; Harvey 2008; Pengcheng, Zhao, and Feng 2010).

Different image interpretation features such as tone, texture, pattern, and colour are generally adopted for feature detection. Modelling of shape is less exploited in this context and is a major factor in distinguishing different entities (Lindi 2004). Our studies have found that inverse mapping of Cellular Automata (CA) using Genetic Algorithm (GA) can be efficiently used for modelling feature shapes. Literature reviews of work in this field also revealed that CA-based approaches are suitable for various image processing tasks (Orovas and Austin 1998; Mitchell, Crutchfield, and Das 1993). The optimal use of CA seems to improve feature detection accuracies to a great extent as revealed from our investigations.

Predicate calculus rule sets used for context representation fail to represent spatial relations effectively as they lack an image compatible form (Mitchell, Crutchfield, and Das 1993; Meghan and Congalton 2011; Dadon et al. 2011). CA can be used as an alternative as it can represent image rules more effectively (Orovas and Austin 1998). Rule sets can be set by using a neural net, thus generating a Cellular Neural Network (CNN). Spectral and spatial information can be combined to increase the separability between classes to yield higher detection accuracy (Mercier and Lennon 2004). Support Vector Machine (SVM) approaches are supervised and not useful for clustering (Huang, Davis, and Townshend 2002; Lee, Schmidt, and Greiner 2005); however, the adaptive kernel strategy introduced by Srivastava (2004) may help in exploiting the n-dimensional classifier concept for achieving an unsupervised strategy. The main obstruction in the modelling of features using the CNN approach is increased computational complexity, which can be effectively tackled using an approximation by coreset (to be discussed).

In this article, we present an object extraction methodology in which CNN is used for modelling feature shape, and adaptive kernel strategy along with corset optimization is adopted to convert the technique to an unsupervised approach. Automatic object modelling, adaptive kernel mapping, automatic interpretation, and intelligent interpolation are salient features of this work. The accuracy of the methodologies is compared with contemporary approaches using different satellite images of the study areas.

Theoretical background

Cellular neural network

CNN (Orovas and Austin 1998; Mitche11, Crutchfiel, and Das 1993) is an analogue parallel computing paradigm defined in space and characterized by locality of connections between processing elements (cells or neurons). An uncoupled CNN can be described as a simple non-linear equation as it converges towards a steady state output over a longer time interval. CNN is effectively used for modelling object shape to improve detection accuracy. Random rules governing the shape of a feature can be identified by evolving the feature from a single state using CNN. Abstract representations of objects are obtained by evolving features continuously until they can be separated from the background.

Multiple attractor cellular automata

MACA is a special type of CA with different local rules applied to different cells and will converge to certain attractor states on continuous execution (Weunsh et al. 2003; Sikdar et al. 2000). In an n-cell MACA with 2 ^m attractors, there exist m-bit positions at which attractors give pseudo-exhaustive 2 ^m patterns. MACA is effectively used for feature interpretation. In order to identify an object, MACA is initialized with the pattern and operated for maximum (depth) number of cycles till it converges to an attractor. Pseudo Exhaustive Field (PEF) bits after convergence are extracted from attractor to identify class patterns and are compared with stored rules to interpret the object.

Mixture density kernel

Mercier Kernel functions can be viewed as a measure of similarity between two data points that are embedded in a high, possibly infinite dimensional feature space (Mercier and Lennon 2003). Mixture Density Kernel (MDK) is a gram matrix that measures the number of times an ensemble of mixture density estimates agree that two points arise from the same mode of probability density function (Srivastava 2004). It is described using Equation (1)(1), where “M” is the number of clusters, C is the number of mixture components in each probabilistic model, P (C_m /X_i ) is the probability that data point “X_i ” belongs to cluster “C_m ”, and Z is the normalization function:

(1)

MDKs are used to integrate an adaptive kernel strategy to the Support Vector Random Field (SVRF)-based clustering. This strategy facilitates learning of kernels directly from image data instead of using static kernels.

Support vector random field

SVRF (Schnitzspan, Mario, and Bernt 2008) is a Discrete Random Field (DRF)-based extension for SVM. It considers interactions of adjacent data points while preserving the same appealing generalization properties as SVM. SVRF consists of observation-matching potential and local-consistency potential functions among which the former captures relationships between observations and class labels, while the latter models relationships between labels and observations at each data point. SVRF function is presented in Equation (2)(2), where Γ _i (X) is a function that computes features from observations X for location “i”, O(yi, i(X)) is an SVM-based observation matching potential, V(yi, yj, X) is a (modified) DRF pair wise potential, and Z is a partitioning (normalizing function):

(2)

SVRF is used to implement initial clustering to segment various objects for an accurate detection and interpretation.

Coreset

Coreset (Agarwal, Aronov, and Sharir 2001; Badoiu, Har-Peled, and Indy 2002) is a small subset of a point set, which is used to compute a solution that approximates a solution of an entire point set. Let μ be a measure function (e.g. width of a point set) from P ₁ and P ₂ (subsets of real numbers (R^d )) to non-negative real numbers (R ⁺ U{0}), such that P ₁ C P ₂ and μ(P ₁) ≤ μ(P ₂). Given a parameter ε > 0, we call a subset Q C P as an ε-Coreset of P (with respect to μ) if (1 − ε)μ(P) ≤ μ(Q). Coreset optimizations can be used to reduce the number of pixels required to represent an object without altering its shape. Hence it is used to reduce the complexity of CA-based inverse evolution.

Experiment

Data set description

Different satellite images of Bhopal and Chandrapur were used as test images for comparing the performance of various algorithms. Details of the satellite data used for these investigations are summarized in Table 1. The ground reference information was collected using a Global Navigation Satellite Systems (GNSS) survey conducted over Bhopal and Chandrapur during October and November 2012, respectively.

Table 1 Details of the image data sets

	Image	Satellite	Date of procurement	Resolution (m)
1	LISS 4	IRS-P5	November 2012	5.8
2	LISS 3	IRS-P5	November 2012	23.5
3	LANDSAT-TM	LANDSAT	November 2012	30

Methodology

A schematic representation of the adopted methodology is presented in Figure 1. CA along with edge information is first used to obtain an abstract object representation of different features in the image (details in Section 3.2.1). Edges are detected using a Canny operator and the information is used by various stages. The image is clustered using the adaptive SVRF approach and the process is enhanced with boundary information as well as abstract object representation from the details in Section 3.2.2. Detected objects along with boundary information are optimized using corset approach to reduce the complexity of shape modelling (details in Section 3.2.3). The approximated objects along with edge information are used to model feature shapes using CNN and MACA. Detected objects are further interpreted using a shape-rule mapping which stores a mapping between objects and MACA rules (details in Section 3.2.4). The interpreted objects are further interpolated using interpolation rules (details in Section 3.2.5). A semi-automatic approach can be accomplished to enable refined detection based on interpretability of extracted features by storing specialized rules. For example, feeble roads can be distinguished from clearly visible ones by defining an interpolation threshold based on the discontinuities in the primary extraction.

Figure 1. Image processing methodology.

Object extraction

Once the edges are detected using the Canny operator, a CA-based region growing strategy is used to approximately extract objects. Each pixel is assigned a state, namely “B” for boundary pixel, “NB” for non-boundary pixel, and “NR” for non-region pixels. Initially, boundary pixel states are assigned as “B” and non-boundary pixel states as “UB”. The “NB” pixel state is changed to “NR” iteratively if it is near to a boundary pixel. The whole procedure is repeated until no further state change is experienced, thereby detecting different objects in the image. Object information derived in this stage is used for effective clustering, that is for determining seed pixel position, cluster boundaries, and a number of objects rather than adopting a random approach.

Clustering

Clustering is accomplished using an SVRF approach that employs a MDK. The position of seed pixels for each object as well as the number of objects and their boundaries is decided by using the feature-specific information derived from the object extraction step (Section 3.2.1). MDKs are used since it avoids the static nature of the usual kernel-based strategies and facilitates adjusting the kernel parameters directly from data. Interpretation of MDK function (Equation (1)(1)) using Baye's rule as given in Equation (3)(3) implies that it measures the ratio of probability with which two points arise from the same mode, compared with an unconditional joint distribution.

(3)

Thus, Equation (3)(3) implies that the kernel tells us the amount of information gained by knowing that two points are drawn from the same mode and that the kernel parameters can be directly learned from data distribution. Adopted kernels include contextual information by incorporating both spectral and spatial information using CA rules. Composite kernel concept is used to incorporate contextual information, i.e. given X = {x ₁, x ₂,…, x_m }^T be spectral characteristics of an M-band multispectral imagery and Y = {y ₁, y ₂,…, y_n }^M be spatial characteristics, then the possible spectral and spatial kernels can be denoted as , and , respectively. Preferably a weighted combination of kernels is adopted as discussed by Hosseini and Homayoun (2009) such that and the value of tuning parameter () is adjusted based on feature metadata using a GA-based approach. Thus, parameters of MDKs are adjusted automatically based on ensembles, and hence can be exploited to incoporate contextual information as well as adaptive kernel strategy for SVRF.

Coreset optimization

Objects in satellite images may span over a long distance and hence a reduction in the number of pixels (n) is needed to accomplish object modelling in acceptable complexity range. Approximation of features using a corset-based approach helps to reduce the number of pixels considerably without losing the original shape. Thus, features are approximated without affecting the results of inverse modelling (Back and Ron 2005). For a given feature with “F” pixels, a line corset (k, ε) is constructed so that it resembles the feature with much fewer pixels, K<<F. Given any n points in R^d , a (k, ε) line coreset of size polygon log(n) ^x can be constructed in nd.k^O(1) = O(n) time, given x = 2^{O( k )} (1 ̸ε ) ^{d +2 k} log ^4k (n).A (1 + ε), where d is the dimension of real plane, and k and ε are coreset prameters.

The epsilon parameter (ε) which varies from 0 to 0.49 is selected based on the varaibility of CA rules for a particular feature, i.e. if a feature is having many possible representations (e.g. rivers can be in many shapes; however, buildings will be mostly rectangular or square), then ε = 0.49, otherwise it is zero. The parameters such as K-line segments that are required for the coreset generation are derived from the edge information and abstract object representation. GA is used along with coreset to implement a shape preserved approximation. The most suitable possibilities of approximations are selected using GA that measures the similarity of shapes by comparison of Pseudo Exahustive Field (PEF) bits.

Object interpretation

CNN along with GA can be effectively used to find rules that iterate from a given initial state to a desired final state. This inverse mapping or evolution is exploited to model feature shapes, and CNN rules are used to evolve a particular feature to distinguish it. Rules corresponding to various features are thus deduced and are mapped in a prolog database. In addition to feature interpretation, these rules are also used to guide mutation and crossover of GA to increase efficiency. Entropies and dimensions give a generalized measure for configurations generated by cellular automaton evolution. The (set) dimension or limiting (topological) entropy for a set of cellular automaton configurations is defined by Equation (4)(4) where N(X) gives the number of distinct sequences of X site values that appear.

(4)

Thus, the inverse evolution can be attained in less than time, provided that the features will converge to lower class CA configurations. Coreset-based optimization is used for feature approximation so that objects can be effectively mapped to lower CA classes. MACA is automatically initialized with the most likely patterns to identify the class of an object in less than time.

Intelligent interpolation

Interpolations of features such as road or river are accomplished by using CA rules integrated with stored predicate rules. For example, given a feature such as a road, training experience or stored rules are used to set the threshold value for particular evolution rule to be adopted. Once a pattern for an object is found and stored in the Prolog database, from then onwards corset-based optimization will be used to estimate likeness of an object to that pattern. Then MACA is automatically initialized with the most appropriate pattern to identify the class in less than time.

Results

Investigations using the feature extraction process applied to various satellite images (details in Table 1) revealed that considerable success was achieved with the approach. The system accurately detected various features such as air strips, roads, rivers, and coal mines better than the existing methodologies. Kappa statistics and overall accuracy along with areal extent comparisons were adopted for an object-specific accuracy evaluation of the different techniques. We have used a confusion matrix strategy for objects of different classes and computed kappa statistics (Congalton 1991) as well as overall accuracy (Nasset 1996; Roy et al. 2010) with larger values of both indicating a better method. Ground reference information was collected using Google earth data and a GNSS survey over the study areas using a Trimble R3 Differential Geographic Positioning System (DGPS). Different features such as rivers, roads, lakes, and urban structures were considered for comparative evaluation. The results of the comparative analysis are summarized in Table 2.

Table 2 Comparative analysis

	Sensor	Methodology	Kappa statistics	Overall accuracy (%)
1	LISS 3	Mahalanobis	0.90	91.4
		Minimum distance	0.91	92.8
		Maximum likelihood	0.93	94.8
		Parallelepiped	0.93	94.6
		Feature space	0.94	95.1
		CNN approach	0.97	97.8
2	LISS 4	Mahalanobis	0.91	92.1
		Minimum distance	0.92	93.5
		Maximum likelihood	0.94	95.1
		Parallelepiped	0.94	95.8
		Feature space	0.95	95.3
		CNN	0.98	98.6
3	LANDSAT-TM	Mahalanobis	0.78	81.4
		Minimum distance	0.81	82.3
		Maximum likelihood	0.84	85.8
		Parallelepiped	0.83	84.6
		Feature space	0.82	83.3
		CNN	0.89	91.8

For all image data sets (LISS 4, LISS 3, LANSAT), the kappa value as well as overall accuracy was greater using the CNN method when compared to traditional methods.

The performances of these methodologies was also evaluated by comparing the areal extent of various extracted features with their actual area. Features, namely, lakes, coal mines, and parks were selected for comparative analysis, because these features were well defined and had fixed geometry that was distinguishable using most of the recent methods. Original surface areas of various extracted features were calculated by manual digitization using ERDAS software and the comparative analysis of results is presented in Table 3.

Tanle 3 Comparative analysis of a real accuracy

	Sensor	Feature	Reference area (km²)	Methodology	Areal extent (km²)
1	LISS 3	Lake	32.48	Mahalanobis	24.31
				Minimum distance	23.40
				Maximum likelihood	25.12
				Parallelepiped	26.24
				Feature space	26.87
				CNN approach	28.92
2	LISS 3	Parks	2.13	Mahalanobis	0.51
				Minimum distance	0.72
				Maximum likelihood	1.53
				Parallelepiped	1.14
				Feature space	1.46
				CNN approach	1.94
3	LISS 4	Lake	32.81	Mahalanobis	25.42
				Minimum distance	24.31
				Maximum likelihood	27.37
				Parallelepiped	28.58
				Feature space	26.82
				CNN	29.32
4	LISS 4	Parks	2.37	Mahalanobis	0.82
				Minimum distance	0.89
				Maximum likelihood	1.45
				Parallelepiped	1.37
				Feature space	1.56
				CNN	2.17
5	LANDSAT	Open cast coal mines	36.48	Mahalanobis	22.14
				Minimum distance	48.40
				Maximum likelihood	31.12
				Parallelepiped	28.74
				Feature space	30.91
				CNN approach	35.13
6	LANDSAT	Water body	7.88	Mahalanobis	3.23
				Minimum distance	4.81
				Maximum likelihood	5.51
				Parallelepiped	5.08
				Feature space	5.32
				CNN approach	7.42

Comparative analyses of areal extent also indicated that the CNN approach yields better results. As evident from Table 3, areas of features extracted using CNN closely resemble the areas calculated through ground reference information and digitization.

The visual results of a sample of features extracted by the system are provided in Figure 2 which also reveals the accuracy of the CNN approach.

Figure 2. Features extracted from LISS 3 imagery using the CNN methodology. (a) Original LISS 3 image, (b) extracted airport tarmac, and (c) cloud shadow.

Tarmac as well as cloud shadow was extracted from the LISS 3 imagery of Bhopal (Figure 2).

Figure 3 presents two additional extractions of the road network form the panchromatic imagery of Bhopal, that is, some roads are clearly visible, however, some are not continuous and clear (feeble). Figure 3b shows the refined detection where unambiguous roads are extracted based on connectivity rules. Figure 3c shows a coarse extraction of roads where even feeble roads are extracted but with a few breaks, that is, roads which are not clearly visible are also detected. These figures illustrate the capability of the system for customized modelling (semi-automatic approach) by changing the contextual or interpolation/interpretation rules as discussed in the methodology.

Figure 3. Road network information extracted from the PAN image using the CNN method. (a) Original image, (b) road network, and (c) road network.

Detection and extraction of a river using LANDSAT multispectral imagery of the Chandrapur area is shown in Figure 4. The intelligent interpolation and interpretation has been utilized to accurately extract the river without breaks and also to distinguish it from the nearby mining areas.

Figure 4. River extracted from LANDSAT multispectral imagery. (a) Original image and (b) river.

Open cast coal mine areas detected from LANDSAT imagery are presented in Figure 5 which illustrates the random modelling capability of the CNN-based strategy.

Figure 5. Mine areas extracted from LANDSAT multispectral imagery. (a) Original image and (b) Open cast mine areas.

Certain features such as roads required a semi-automatic approach for detection rather than a complete automatic method, that is a priori training was required to distinguish poorly defined road networks. The method failed to distinguish between shadows of clouds and clouds, but this can be solved using effective training. The main disadvantage of the method is its computational complexity which can be improved by corset optimization and similar approximation techniques. Complexity can be further reduced by storing the detected rule variations where optimization methods such as GA can be exploited to optimize the strategy. This research provides a basic framework. Further research is needed to optimize it. Integration of a fuzzy approach to the inverse mapping also seems to be promising since fuzzy/neutrosophic cognitive maps can be exploited for effectively organizing and selecting the CA rules.

Conclusion

Feature shape modelling and context knowledge representation are two important factors in distinguishing features, and ignoring its consideration has hindered the accuracy of traditional detection techniques. We discussed a CNN-based approach that could effectively model feature shapes and contextual knowledge. Recent random modelling and intelligent methodologies were adopted to present a framework. The study revealed that the CNN-based method outperformed contemporary approaches in terms of accuracy. Complexity of the approach was considerably reduced using corset-based approximation. The proposed framework has proven to be intelligent with reference to accurate interpolation and interpretation. Disambiguation of features, enhanced detection, self-learning, minimal human interpretation, and reliability are features of the system. Further research is needed on the improvement of the proposed framework, especially on parallelizing and optimizing different operations for complexity reduction. Effective representation of different context rules also needs further improvement and techniques such as fuzzy cognitive maps seem to be promising in this context.