Minimum spanning trees for valley and ridge characterization in digital elevation maps

Texture synthesis employs neighbourhood matching to generate appropriate new content. Terrain synthesis has the added constraint that new content must be geographically plausible. The profile recognition and polygon breaking algorithm (PPA) [Chang et al. 1998] provides a robust mechanism for characterizing terrain as systems of valley and ridge lines in digital elevation maps. We exploit this to create a terrain characterization metric that is robust, efficient to compute and is sensitive to terrain properties.

Terrain regions are characterized as a minimum spanning tree derived from a graph created from the sample points of the elevation map which are encoded as weights in the edges of the graph. This formulation allows us to provide a single consistent feature definition that is sensitive to the pattern of ridges and valleys in the terrain Alternative formulations of these weights provide richer characteristicmeasures and we provide examples of alternate definitions based on curvature and contour measures.

We show that the measure is robust, with a significant portion derived directly from information local to the terrain sample. Global terrain characteristics introduce the issue of over- and underconnected valley/ridge lines when working with sub-regions. This is addressed by providing two graph construction strategies, which respectively provide an upper bound on connectivity as a single spanning tree, and a lower bound as a forest of trees.

Efficient minimum spanning tree algorithms are adapted to the context of terrain data and are shown to provide substantially better performance than previous PPA implementations. In particular, these are able to characterize valley and ridge behaviour at every point even in large elevation maps, providing a measure sensitive to terrain features at all scales.

The resulting graph based formulation provides an efficient and elegant algorithm for characterizing terrain features. The measure can be calculated efficiently, is robust under changes of neighbourhood position, size and resolution and the hybrid measure is sensitive to terrain features both locally and globally.

Capitanian (late Guadalupian, permian) global brachiopod palaeobigeography and latitudinal diversity pattern

A global database containing 3365 occurrences, 821 species and 251 genera of the Capitanian (Late Guadalupian, Permian) brachiopod faunas from 24 stations has been analyzed by cluster analysis using the Jaccard and Otsuka coefficients and the probabilistic index of similarity, nonmetric multidimensional scaling and minimum spanning tree. Two supergroups, three groups and six subgroups are revealed and interpreted as representing, respectively, two biotic realms (the Palaeoequatorial and Gondwanan Realms), two regions and six provinces. An additional realm (the Boreal Realm), based on the fauna from Spitsbergen, also appears recognizable although it also shows considerable similarities with southwestern North America and the northern margin of Gondwana as revealed by the statistical analysis. The Palaeoequatorial Realm can be further subdivided into the North America Region and the Asian Tethyan Region. The six biotic provinces are the Cathaysian Province in the Palaeotethys and Mesotethys, the Greenland-Svalbard Province in the Arctic region, the Austrazean Province in eastern Australia and New Zealand, the Grandian Province in western North America and the two transitional zones (the Himalayan Province in the southern temperate zone and the Sino–Mongolian–Japanese Province in the northern temperate zone). Polynomial regression analysis and rarefaction analysis indicate that the generic diversities of brachiopod faunas during the Capitanian peaked in the Palaeoequatorial Cathaysian Province and the two transitional zones (Himalayan Province and Sino–Mongolian–Japanese Province), but fell dramatically in the polar regions. The generic diversity of the Palaeoequatorial Grandian Province is apparently lower than in the two transitional zones of temperate palaeolatitudes, suggesting that the generic diversity of Capitanian brachiopod faunas does not exhibit a strict negative correlation with palaeolatitudes. This in turn would suggest that biogeographical determinants (such as geographical barriers, inhabitable area and ocean currents) other than latitude-related temperature control may also have played an important role in the dispersal of some brachiopods and the characterization of some local provinces and high diversities. The Capitanian global brachiopod palaeobiogeography is generally comparable with those in the Wuchiapingian and Changhsingian, but with some notable differences. These include: (1) that the Grandian Province of the Capitanian in western North America vanished after the end-Guadalupian regression, (2) that the western Tethyan Province of the Lopingian could not be distinguished in the Capitanian, and (3) that the Austrazean Province was larger in area than either in the Wuchiapingian or in the Changhsingian.

Data mining via minimal spanning tree clustering for prolonging lifetime of wireless sensor networks

Clustering is applied in wireless sensor networks for increasing energy efficiency. Clustering methods in wireless sensor networks are different from those in traditional data mining systems. This paper proposes a novel clustering algorithm based on Minimal Spanning Tree (MST) and Maximum Energy resource on sensors named MSTME. Also, specified constrains of clustering in wireless sensor networks and several evaluation metrics are given. MSTME performs better than already known clustering methods of Low Energy Adaptive Clustering Hierarchy (LEACH) and Base Station Controlled Dynamic Clustering Protocol (BCDCP) in wireless sensor networks when they are evaluated by these evaluation metrics. Simulation results show MSTME increases energy efficiency and network lifetime compared with LEACH and BCDCP in two-hop and multi-hop networks, respectively. © World Scientific Publishing Company.

Dynamic minimal spanning tree routing protocol for large wireless sensor networks

Hundreds or thousands of wireless sensor nodes with limited energy resource are randomly scattered in the observation fields to extract the data messages for users. Because their energy resource cannot be recharged, energy efficiency becomes one of the most important problems. LEACH is an energy efficient protocol by grouping nodes into clusters and using cluster heads (CH) to fuse data before transmitting to the base station (BS). BCDCP improves LEACH by introducing a minimal spanning tree (MST) to connect CHs and adopting iterative cluster splitting algorithm to choose CHs or form clusters. This paper proposes another innovative cluster-based routing protocol named dynamic minimal spanning tree routing protocol (DMSTRP), which improves BCDCP by introducing MSTs instead of clubs to connect nodes in clusters. Simulation results show that DMSTRP excels LEACH and BCDCP in terms of both network lifetime and delay when the network size becomes large.

Roadian – Wordian (Guadalupian, Middle Permian) global palaeobiogeography of brachiopods

A database of 4471 Roadian–Wordian (Guadalupian, Middle Permian) occurrences of 381 brachiopod genera in 44 different operational geographical units (stations) was analyzed by both Q-mode and R-mode quantitative methods. Four distinct brachiopod biogeographical realms and nine provinces, and 11 brachiopod associations are recognized. The Boreal Realm in the Northern Hemisphere includes the Verkolyman Province in the northern and northeastern Siberian Platform and the eastern European Province in the Ural seaway between the European and Siberian platforms. Both provinces are characterized by containing typical Boreal cold-water brachiopod associations. The Gondwanan Realm in the south also includes two provinces. The Austrazean Province in eastern Australia and New Zealand is probably the most stable province throughout the Permian and characterized by typical Gondwanan brachiopod associations. The Westralian Province centered in Western Australia is also characterized by typical Gondwanan brachiopods, but also demonstrates biogeographical links with the Tethyan stations. The Palaeoequatorial Realm located mainly in the palaeotropical zone contains highly diverse and abundant brachiopod faunas. Two regions/subrealms and four provinces are recognized within this realm. The North America Subrealm contains a distinct Grandian Province characterized by many endemic brachiopod genera and a few coldwater genera. East-central Alaska and Yukon Territory may constitute another brachiopod province. All the stations in the Tethyan Ocean (both Palaeotethys and Neotethys) constitute a distinct Asian–Tethyan Region/ Subrealm and incorporate three different provinces. The Cathaysian Province is comprised of the stations in South China and its surrounding terranes/blocks and a few stations in the northern and western margin of the Palaeotethys. Two transitional provinces (Sino–Mongolian–Japanese Province and Cimmerian Province) in the northern and southern temperate zones are also recognizable. The brachiopod fauna from the Mino Belt in Japan is well distinguished from those from other regions, and is hence assigned to the palaeoceanic Panthalassan Realm. Principal coordinates analysis and minimum spanning tree analysis suggest that a latitude-related thermal gradient was the major control for the palaeobiogeography of Roadian–Wordian global brachiopod faunas and for the latitudinal of pattern of decreasing brachiopod generic diversities from the equator to the poles. In addition, geographic separation and oceanic currents may also have played some role in the spatial distribution of brachiopods during Roadian–Wordian times.

A visual-numeric approach to clustering and anomaly detection for trajectory data

This paper proposes a novel application of Visual Assessment of Tendency (VAT)-based hierarchical clustering algorithms (VAT, iVAT, and clusiVAT) for trajectory analysis. We introduce a new clustering based anomaly detection framework named iVAT+ and clusiVAT+ and use it for trajectory anomaly detection. This approach is based on partitioning the VAT-generated Minimum Spanning Tree based on an efficient thresholding scheme. The trajectories are classified as normal or anomalous based on the number of paths in the clusters. On synthetic datasets with fixed and variable numbers of clusters and anomalies, we achieve 98 % classification accuracy. Our two-stage clusiVAT method is applied to 26,039 trajectories of vehicles and pedestrians from a parking lot scene from the real life MIT trajectories dataset. The first stage clusters the trajectories ignoring directionality. The second stage divides the clusters obtained from the first stage by considering trajectory direction. We show that our novel two-stage clusiVAT approach can produce natural and informative trajectory clusters on this real life dataset while finding representative anomalies.

Clustering versus evenly distributing energy dissipation in wireless sensor routing for prolong network lifetime

A novel Cluster Heads (CH) choosing algorithm based on both Minimal Spanning Tree and Maximum Energy resource on sensors, named MSTME, is provided for prolonging lifetime of wireless sensor networks. MSTME can satisfy three principles of optimal CHs: to have the most energy resource among sensors in local clusters, to group approximately the same number of closer sensors into clusters, and to distribute evenly in the networks in terms of location. Simulation shows the network lifetime in MSTME excels its counterparts in two-hop and multi-hop wireless sensor networks.

Ensembling MML causal discovery

This paper presents an ensemble MML approach for the discovery of causal models. The component learners are formed based on the MML causal induction methods. Six different ensemble causal induction algorithms are proposed. Our experiential results reveal that (1) the ensemble MML causal induction approach has achieved an improved result compared with any single learner in terms of learning accuracy and correctness; (2) Among all the ensemble causal induction algorithms examined, the weighted voting without seeding algorithm outperforms all the rest; (3) It seems that the ensembled CI algorithms could alleviate the local minimum problem. The only drawback of this method is that the time complexity is increased by δ times, where δ is the ensemble size.

A novel application of a microaccelerometer for target classification

This paper presents a novel method of target classification by means of a microaccelerometer. Its principle is that the seismic signals from moving vehicle targets are detected by a microaccelerometer, and targets are automatically recognized by the advanced signal processing method. The detection system based on the microaccelerometer is small in size, light in weight, has low power consumption and low cost, and can work under severe circumstances for many different applications, such as battlefield surveillance, traffic monitoring, etc. In order to extract features of seismic signals stimulated by different vehicle targets and to recognize targets, seismic properties of typical vehicle targets are researched in this paper. A technique of artificial neural networks (ANNs) is applied to the recognition of seismic signals for vehicle targets. An improved back propagation (BP) algorithm and ANN architecture have been presented to improve learning speed and avoid local minimum points in error curve. The improved BP algorithm has been used for classification and recognition of seismic signals of vehicle targets in the outdoor environment. Through experiments, it can be proven that target seismic properties acquired are correct, ANN is effective to solve the problem of classification and recognition of moving vehicle targets, and the microaccelerometer can be used in vehicle target recognition.

Finite-time consensus algorithm of multi-agent networks

This paper is concerned with leader-follower finite-time consensus control of multi-agent networks with input disturbances. Terminal sliding mode control scheme is used to design the distributed control law. A new terminal sliding mode surface is proposed to guarantee finite-time consensus under fixed topology, with the common assumption that the position and the velocity of the active leader is known to its neighbors only. By using the finite-time Lyapunov stability theorem, it is shown that if the directed graph of the network has a directed spanning tree, then the terminal sliding mode control law can guarantee finite-time consensus even under the assumption that the time-varying control input of the active leader is unknown to any follower.

Fast finite-time consensus of a class of high-order uncertain nonlinear systems

This paper poses and solves a new problem of consensus control where the task is to make the fixed-topology multi-agent network, with each agent described by an uncertain nonlinear system in chained form, to reach consensus in a fast finite time. Our development starts with a set of new sliding mode surfaces. It is proven that, on these sliding mode surfaces, consensus can be achieved if the communication graph has the proposed directed spanning tree. Next, we introduce the multi-surface sliding mode control to drive the sliding variables to the sliding mode surfaces in a fast finite time. The control Lyapunov function for fast finite time stability, motivated by the fast terminal sliding mode control, is used to prove the reachability of the sliding mode surface. A recursive design procedure is provided, which guarantees the boundedness of the control input.

Applying genetic algorithm for optimizing broadcasting process in ad-hoc network

Optimizing broadcasting process in mobile ad hoc network (MANET) is considered as a main challenge due to many problems, such as Broadcast Storm problem and high complexity in finding the optimal tree resulting in an NP-hard problem. Straight forward techniques like simple flooding give rise to Broadcast Storm problem with a high probability. In this work, genetic algorithm (GA) that searches over a population that represents a distinguishable ‘structure’ is adopted innovatively to suit MANETs. The novelty of the GA technique adopted here to provide the means to tackle this MANET problem lies mainly on the proposed method of searching for a structure of a suitable spanning tree that can be optimized, in order to meet the performance indices related to the broadcasting problem. In other words, the proposed genetic model (GM) evolves with the structure of random trees (individuals) ‘genetically’ generated using rules that are devised specifically to capture MANET behaviour in order to arrive at a minimal spanning tree that satisfies certain fitness function. Also, the model has the ability to give different solutions depending on the main factors specified such as, ‘time’ (or speed) in certain situations and ‘reachability’ in certain others.

Event extraction using behaviors of sentiment signals and burst structure in social media

Significant world events often cause the behavioral convergence of the expression of shared sentiment. This paper examines the use of the blogosphere as a framework to study user psychological behaviors, using their sentiment responses as a form of ‘sensor’ to infer real-world events of importance automatically. We formulate a novel temporal sentiment index function using quantitative measure of the valence value of bearing words in blog posts in which the set of affective bearing words is inspired from psychological research in emotion structure. The annual local minimum and maximum of the proposed sentiment signal function are utilized to extract significant events of the year and corresponding blog posts are further analyzed using topic modeling tools to understand their content. The paper then examines the correlation of topics discovered in relation to world news events reported by the mainstream news service provider, Cable News Network, and by using the Google search engine. Next, aiming at understanding sentiment at a finer granularity over time, we propose a stochastic burst detection model, extended from the work of Kleinberg, to work incrementally with stream data. The proposed model is then used to extract sentimental bursts occurring within a specific mood label (for example, a burst of observing ‘shocked’). The blog posts at those time indices are analyzed to extract topics, and these are compared to real-world news events. Our comprehensive set of experiments conducted on a large-scale set of 12 million posts from Livejournal shows that the proposed sentiment index function coincides well with significant world events while bursts in sentiment allow us to locate finer-grain external world events.