Description

12th AGILE International Conference on Geographic Information Science 2009 page 1 of 9 A Random Sets Model for Spatial Objects with Uncertain Boundaries Xi Zhao ab, Xiaoling Chen ac, Alfred Stein b a State

Information

Category:
## Products & Services

Publish on:

Views: 10 | Pages: 9

Extension: PDF | Download: 0

Share

Transcript

12th AGILE International Conference on Geographic Information Science 2009 page 1 of 9 A Random Sets Model for Spatial Objects with Uncertain Boundaries Xi Zhao ab, Xiaoling Chen ac, Alfred Stein b a State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Luo Yu road 129, Wuhan, HuBei, China b International Institute for Geo-Information Science and Earth Observation, Hengelosestraat 99, Enschede, Netherlands c The Key Laboratory of Poyang lake Wetland and Watershed Research, Jiangxi Normal University, Ziyang road 99, Nanchang,JiangXi, China 1. INTRODUCTION Several conceptual models and data models have been proposed for geographical phenomena with uncertainties that cannot easily be forced into current standard data models. These models of uncertain objects can be categorized into two groups. One group (Clementini and Di Felice 1996; Cohn and Gotts 1996; Roy and Stell 2001) considers the broad boundary of an object as a homogeneous twodimensional region instead of lines. The well-known Egg-Yolk model which describes uncertain region as a pair of crisp regions, one enclosing the other, is a typical example. The other group employs probability theory or fuzzy set theory to further represent gradual changes within the broad boundaries. Probabilistic models for depicting the positional uncertainties of these objects have been developed, distinguishing between point features (Thapa and Bossler 1992), line features (Dunn et al. 1990; Shi and Liu 2000) and polygon features (Shi and Wu 2003). Formal definitions of fuzzy regions and topological relations between them are provided by (Zhan 1998; Cheng et al. 2001; Schneider 2003; Dilo et al. 2007). Definitions of random/uncertain data types are also developed (Glemser and Fritsch 1998; Pfoser and Tryfona 2001; Tøssebro and Nygård 2002) and applied in uncertainty modeling applications (Glemser and Klein 2000). They applied probability theory directly on those spatial data types. However, data analysis when the data are sets, rather than points in spatial-temporal space, is not a nice situation to work with (Nguyen 2006). Therefore, there is a need to propose a general framework for set-valued observations. This paper aims to implement random sets based on probability theory in a GIS environment for handling regions with uncertain boundaries. A random sets data model is proposed to represent uncertain geographic regions and applied to spatial-temporal modeling, using a wetland monitoring case as an illustration. 2. UNCERTAINTY MODELING WITH RANDOM SET The term random sets firstly appeared to indicate region depending on chance (Kolmogoroff 1933). After the publication of the fundamental book of random set theory by Matheron (1975), various successful applications in spatial science appeared. Random sets are applicable and useful for general data fusion (Goodman et al. 1997), to address problems of determining the locations and identities of multi-targets from multi-sensor data with noise effects. Moreover, random sets are a basic tool in solving problems of geometrical statistics and image analysis (Molchanov 1998) and time series analysis (Nuñez-Garcia and Wolkenhauer 2002). It is the core of stochastic geometry, in which they are stochastic models of irregular or random geometrical structures. Stoyan (1998) applied random set theory in particle statistics to study shape fluctuations of sand grains, showing how random set as a set-theoretic method has its advantages and may act as a supplement of other powerful means such as multivariate statistics. Nguyen (2006) pointed out that uncertainties caused by subjectivity, 12th AGILE International Conference on Geographic Information Science 2009 page 2 of 9 impression and vagueness bear some relationship with random sets. More recent developments of random sets are provided by (Molchanov 2005; Nguyen 2006; Illian et al. 2008). In the following sections, basic concepts of random sets with respect to this research are introduced and random spatial data types are defined. 2.1 Random Sets Sets obtained at random can be considered as kinds of random sets. For example, a probability sampling design is a random experiment whose outcomes cannot be predicted with certainty in advance, so a sample in the surveying sampling is a set obtained at random, i.e. random set. Let (Ω, σ Ω, Ρr Ω ) be a probability space and (Ξ, σ Ξ, Ρr x ) a measure space. Every σ Ω - σ Ξ measurable mapping v: Ω - Ξ is called a random variable. The distribution or probability law of v is defined as Ρr v (A) = Ρr Ω (v -1 (A)) = Ρr Ω {ω : v(ω ) A } for A σ Ξ. A random set can be seen as a random variable from Ω to U where U is a set of subsets of Ξ, i.e. U P( Ξ ). Let (U, σ U, Ρr X ) be a measurable space and σ U is a σ - algebra defined on U, then a σ Ω - σ U mapping X: Ω U is a random set. It is a multivalued mapping between the space Ω and Ξ. Its distribution is defined as Ρr X (A ) = Ρr Ω (X -1 (A )) = Ρr Ω {ω X(ω ) A } for A σ U. When all elements of U are singletons, then random set X becomes a random variable. On the Euclidean space R n, a random set X associates a probability value to each element x R n, which quantifies how likely it is that x belongs to X. The random set X on R n is a function P x : R n [0,1]. This function is called the covering function of the random set, which takes values between 0 and 1. The set X a = {x R n P x (x) α} is called α-level set of X. The set X 0 = { x R n P x (x) 0 } is called the support set of X. The set X 1 = { x R n P x (x) = 1 } is called the core set of X. We denote the set of all random sets in R n by R(R n ). A typical situation where observations are sets rather than points in a sample space can be dealt with random sets. When we obtain data with low quality due to imperfection of acquiring procedure or measuring instruments, it is more informative to represent the observations as subsets containing the true values than to ascribe unique values (Nguyen 2006). 2.2 Random Spatial Data Types In our study we consider geo-space, i.e. the two-dimensional Euclidean space R 2, with geographic entities as subsets of R 2. Based on probability theory and random set concepts, we propose random objects, denoted Robject, to model geographic entities with uncertain characteristics. We model Robject as sets of points, homeomorphic to R 2. A Robject can be either determinate or indeterminate. A Robject is determinate if any of its component points has an exact position that can be mapped onto a single point. A Robject is indeterminate, if any of its component points can only be mapped to a set of points, i.e., the exact position is unknown. Random unit (R u ) is defined as basic elements of R 2 constructing primary data types. A random unit (R u ), denoted as (x, y, p), consists of a pair of coordinates (x, y) and a probability value indicating how likely this unit located at (x, y). The probability value is derived from probability density function which describes the likelihood for each unit to be at the position. For example, uniform distribution tells us that there is an equal chance for each unit. 12th AGILE International Conference on Geographic Information Science 2009 page 3 of 9 The random objects (Robject) is defined as: Robject { Ru R( R 2 ) (x, y) R 2, p(x, y) 0} (4) Three primary random data types: random point (R p ), random line (R l ) and random region (R r ) are defined below. The random point (R p ) is defined as a random set in R 2 that contains a finite collection of uncertain units with positive probability values, denoted as R p (R up1, R up2,, R upn ). The probability value attached with each uncertain unit is the likelihood that the point is in this location. The distribution of all elements in a random point is described by its covering function. The uncertain points with p i 0 form the support set and with p i =1 form the core set. It is used for spatially modeling a point-like geographic entity. This point entity can be an accident place that stochastically occurred, a pair of imprecise coordinates received by a GPS receiver, or a building that is recorded by mixed image pixels. The random line (R l ) is to model a linear object with a random component. We distinguish two ways in representing a random line. The first way is by a collection of uncertain lines associated with their probabilities, denoted as R l {(l 1, p 1 ), (l 2, p 2 ),, (l n, p n )}. For each component -uncertain line l i, it is constructed by a set of uncertain units with a same probability value p i, denote as (l i, p i ). The second way is by a collection of uncertain units that constitute the line, denoted R l (R up1, R up2,, R upn ). The probability value attached with each uncertain unit is that the likelihood of the line goes through the location of this unit. The distribution of all the elements of a random line is described by its covering function. The elements with p i 0 form the support set and with p i =1 form the core set. Random lines are used for spatially modeling a linear geographic entity, like a route from city A to city B, a contour line digitized from a scanned map, or a coastline interpreted from a satellite image. The random region (R r ) is a region with a random component. It can be modeled in two ways. The first way is by a collection of uncertain regions associated with their probabilities, denoted by R r {(r 1, p 1 ), (r 2, p 2 ),, (r n, p n )}. For each component -uncertain region r i, it is constructed by a set of uncertain units with a same probability value p i, denote as (r i, p i ). The second way is by uncertain units which form its random coverage, denoted by R r (R up1, R up2,, R upn ). The probability value attached to each uncertain unit is that the likelihood of the region covers the location of this unit. The distribution of all the elements of a random region is described by its covering function. The areas with p i 0 form the support set and with p i =1 form the core set. Random regions are used for spatially modeling areal geographic entities, such as clouds, dunes, field patches and lakes. 2.3 Estimation of the Covering Functions Since different specified probability measures lead to different random sets, there is a need to look at the distributions of random sets. In general, the question of interest is how to suggest random set models from empirical observations. In previous researches, there are different means of estimating probability distribution functions of random objects. The simplest way is to provide a set of standard functions such as the normal distribution and the uniform distribution. Another alternative is to adopt users definitions, which are often derived from sampled data. For example, Tøssebro and Nygård (2002) calculated probability of points in uncertain regions as the ratio between distance to support and the sum of distance to support and distance to core. However, the uncertainties often do not conform to normal distributions or are too complex to model by analytical approaches. In this case, we can adopt numerical approaches, such as Monte Carlo method, to obtain the empirical covering function of random sets, like in (Glemser and Klein 2000; Guo et al. 2008). Some researches also estimated uncertainty distribution from fuzzy membership functions (Pfoser and Tryfona 2001; Van de Vlag and Stein 2007). 12th AGILE International Conference on Geographic Information Science 2009 page 4 of 9 3. ILLUSTRATIVE EXAMPLES The case has its study area in the Poyang Lake national nature reserve (PLNNR) ( E, N), at the southern bank of the middle reach of Yangtze River, central China (Figure 1). Every year, the water level starts to rise in spring (March to May) due to flooding of its source rivers, and keeps its highest level in summer (June to August) as a consequence of flooding of the Yangtze River. The water level reduces from September onwards when the flood in the Yangtze River ebbs to remain stable at its lowest level from December to February. Wetland vegetation submerges in summer and greens up in autumn upon the recession of the Yangtze River, providing desirable habits and high quality forage for waterfowls (Wu and Ji 2002). Mapping the wetlands, especially modeling the form variance of lakes is of great importance for PLNNR managers and decision makers for both ecosystem dynamic monitoring and habitat assessment. Figure 1: Location of the Poyang Lake and the PLNNR (left) and the study area in the black box (right). Figure 2: Image object of Meixihu (in black) on the middle Infrared band of nine Landsat TM images of 2004 (The observing time from top to bot-tom and from left to right is 5 May, 22 June, 24 July, 9 August, 26 Sep-tember, 12 and 28 October, 29 November and 15 December) 12th AGILE International Conference on Geographic Information Science 2009 page 5 of 9 Figure 2 shows a series of Landsat TM images covering the Meixihu Lake within the PLNNR, which were acquired from May to December of 2004 for this wetland monitoring study. A topographic map of scale 1:10000 is used as the geographic reference data. The root mean squared error (RMSE) of all the geometric corrections was less than 10m. To extract image objects Meixihu from a single image, the split and merge method developed in (Lucieer and Stein 2002) was adopted to segment images and to quantify segmentation uncertainty by using Parbat software (http://parbat.lucieer.net/). In this method, ranges for the splitting thresholds and merging thresholds are chosen and are divided into N steps. At each step, object boundaries, in the form of segment edge pixels, are determined. At step k these boundary pixels are assigned the value 1 and non-boundary pixels the value 0 and are represented on a segment-boundary image. By summing these segmentations, an image with boundary stability index (BSI) for each pixel is generated to indicate the frequency of boundary location (0-1). Higher value of the index means more certainly about the boundary. Objects with a low degree of geometric uncertainty will remain the same at different segmentation levels. Objects with uncertain boundaries will change the shape and size gradually. We set thresholds in split and merge segmentation approach, let Parbat software segment N times, generate a set of N pixel clusters and calculate the BSI for each image pixel. BSI = n n I k k =0 (1) The number of segmentation steps n was set to 50 in our experiment. Boundaries in all the 50 segmentation results construct a random line that models the uncertain boundary of Meixihu. An image with a BSI map was calculated to depict object stability which represents the random line by uncertain points (figure 3a). This BSI map also indicates the empirical covering function of the random line. The final extracted boundaries in fig. 3b are constructed by pixels with the local maximum BSI values. Comparing the uncertain distribution in (figure 3a) with segmented boundaries in (figure 3b), we observe fewer pixels with high BSI values around the edge of the object on the left image than on the right image. In other words, the flooded Meixihu object has a thinner certain boundary than the dry Meixihu object. This result is consistent with our previous observation in figure 2 that the water boundary in the flooding season (June) looks less gradual than during the dry season (December). In this case, random set model which is constructed by multiple segmentations presents the uncertainties that may occur in image processing. The gradual object boundary modeled by random line can be used in further image analysis which may ask the inclusion of uncertainty. We now consider N image objects extracted from a time-series of N images that record the changing process of a dynamic entity. These N image objects construct a random area X for modeling its dynamic shape and size. Every year, the spatial extent of the lake changes with the same trend, but vary due to different environmental conditions, which is a typical stochastic process. In space and time, this Meixihu object can be considered as an object with uncertain boundaries due to its dynamic extents. The N image objects are considered as samples of a random set X. Pixels on each image that belong to one image object are assigned with value 1 and otherwise 0, then summed up and divided by N. This results in an image with object covering index (OCI) to indicate the frequency of object covering extent, i.e. covering function of the random set. Covering frequency in figure 4 can be interpreted as possibility which indicates the membership of the cell to the dynamic object flooded region. All cells with possibility larger than 0 were grouped to indicate the maximum extent of the flooded area. OCI = n I k k =0 (2) n 12th AGILE International Conference on Geographic Information Science 2009 page 6 of 9 (a) BSI map (b) Object boundary Figure 3: Meixihu area observed at June (left) and December (right). Figure 4: OCI map represent empirical covering function of random region modeling dynamic Meixihu Lake. 12th AGILE International Conference on Geographic Information Science 2009 page 7 of 9 Random set can be described by other random variables, whose values lie in a space mathematically simpler than the space of random area. Very simple random variables assigned to random set X are its area A(X) and its perimeter U(X). To explore the shape changes, we also need reprehensive shape index, which do not change as scale changes, compactness C(X). Compactness has a maximum value of 1 for a circle. The change of shape and presence of irregular boundaries will decrease the value. A( x) C( x) = 4π 2 U ( x) (3) To study the geometrical dynamic of Meixihu, several form parameters were derived and analyzed with other driving factor, i.e.water level. From the results shown in figure 5a, we can see the area and perimeter of Meixihu have the same change trend: the values increase rapidly from May to June then to around twice in July, followed by a decrease from September to December. There are two extreme points in the change curve of area index: the peak point in July and the second peak point in August. Compared with water extents in figure 2, we found that it was the topological change of Mixihu causes these abnormal points. The water in Meixihu was overflowed and merged with other water bodies of Poyang Lake in flooding months - July and August. Therefore, when calculating area and perimeter indices, newly flooded areas connected with Meixihu were regarded as parts of Meixihu object and counted in. Figure 5b shows the shape of the Meixihu object is most close to a circle in May. (a) area and perimeter (b) shape index (c) water level (d) relationship of shape index and water level Figure 5: Changes of area, perimeter, shape index and water level of Meixihu at nine image observation time. After the water level beginning to rise up, the object boundary becomes more and more irregular. The lowest compactness appears in September, when Meixihu was connected with a linear-shape object (a river). After flood recession, the lake will be disconnected with other water bodies again and the compactness shape index is expected to return back to the high level as it in May. However, Carex-dominated grassland green up on the newly exposure wet soil around the lake, which makes the object shape concave and thus the index still stay low. Figure 5c shows water level of the Meixihu lake, which was derived from daily recorded hydrological data averaged into month unit. We can see 12th AGILE International Conference on Geographic Information Science 2009 page 8 of 9 obviously, the change curves of both area and perimeter have the same trend with the water level fluctuation, while the curve of compactness shape index has inverse trend. To check the relationship of the water level and shape index, we found six pairs of data are quite well correl

Related Search

Geographic Information ScienceGeographic Information Science \u0026 Remote Proceedings of International Conference on ApIEEE International Conference on Computer SciGeographic Information SystemOntology (Information Science)Information ScienceInternational Conference on PopulationGeographic InformationGeographic Information Systems

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x