OTCYMIST: Otsu-Canny minimal spanning tree for born-digital images

Text segmentation and localization algorithms are proposed for the born-digital image dataset. Binarization and edge detection are separately carried out on the three colour planes of the image. Connected components (CC's) obtained from the binarized image are thresholded based on their area and aspect ratio. CC's which contain sufficient edge pixels are retained. A novel approach is presented, where the text components are represented as nodes of a graph. Nodes correspond to the centroids of the individual CC's. Long edges are broken from the minimum spanning tree of the graph. Pair wise height ratio is also used to remove likely non-text components. A new minimum spanning tree is created from the remaining nodes. Horizontal grouping is performed on the CC's to generate bounding boxes of text strings. Overlapping bounding boxes are removed using an overlap area threshold. Non-overlapping and minimally overlapping bounding boxes are used for text segmentation. Vertical splitting is applied to generate bounding boxes at the word level. The proposed method is applied on all the images of the test dataset and values of precision, recall and H-mean are obtained using different approaches.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

A divisive scheme for constructing minimal spanning trees in coordinate space

An algorithm to generate a minimal spanning tree is presented when the nodes with their coordinates in some m-dimensional Euclidean space and the corresponding metric are given. This algorithm is tested on manually generated data sets. The worst case time complexity of this algorithm is O(n log2n) for a collection of n data samples.

Structure-potential relationship and nature of disorder in liquids and glassy solids

A method based on the minimal-spanning tree is extended to a collection of points in three dimensions. Two parameters, the average edge length and its standard deviation characterize the disorder. The structural phase diagram for a monatomic system of particles and the characteristic values for the uniform random distribution of points have been obtained. The method is applied to hard spheres and Lennard-Jones systems. These systems occupy distinct regions in the structural phase diagram. The structure of the Lennard-Jones system approaches that of the defective close-packed arrangements at low temperatures whereas in the liquid regime, it deviates from the close-packed configuration.

Dependence of diffusivity on density and solute diameter in liquid phase: A molecular dynamics study of Lennard-Jones system

Investigations into the variation of self-diffusivity with solute radius, density, and degree of disorder of the host medium is explored. The system consists of a binary mixture of a relatively smaller sized solute, whose size is varied and a larger sized solvent interacting via Lennard-Jones potential. Calculations have been performed at three different reduced densities of 0.7, 0.8, and 0.933. These simulations show that diffusivity exhibits a maximum for some intermediate size of the solute when the solute diameter is varied. The maximum is found at the same size of the solute at all densities which is at variance with the prediction of the levitation effect. In order to understand this anomaly, additional simulations were carried out in which the degree of disorder has been varied while keeping the density constant. The results show that the diffusivity maximum gradually disappears with increase in disorder. Disorder has been characterized by means of the minimal spanning tree. Simulations have also been carried out in which the degree of disorder is constant and only the density is altered. The results from these simulations show that the maximum in diffusivity now shifts to larger distances with decrease in density. This is in agreement with the changes in void and neck distribution with density of the host medium. These results are in excellent agreement with the predictions of the levitation effect. They suggest that the effect of disorder is to shift the maximum in diffusivity towards smaller solute radius while that of the decrease in density is to shift it towards larger solute radius. Thus, in real systems where the degree of disorder is lower at higher density and vice versa, the effect due to density and disorder have opposing influences. These are confirmed by the changes seen in the velocity autocorrelation function, self part of the intermediate scattering function and activation energy. (C) 2012 American Institute of Physics. http://dx.doi.org/10.1063/1.3701619]

Tree-ring based hydroclimate reconstruction over northern Vietnam from Fokienia hodginsii: eighteenth century mega-drought and tropical Pacific influence

We present here the first statistically calibrated and verified tree-ring reconstruction of climate from continental Southeast Asia.The reconstructed variable is March-May (MAM) Palmer Drought Severity Index (PDSI) based on ring widths from 22 trees (42 radial cores) of rare and long-lived conifer, Fokienia hodginsii (Po Mu as locally called) from northern Vietnam. This is the first published tree ring chronology from Vietnam as well as the first for this species. Spanning 535 years, this is the longest cross-dated tree-ring series yet produced from continental Southeast Asia. Response analysis revealed that the annual growth of Fokienia at this site was mostly governed by soil moisture in the pre-monsoon season. The reconstruction passed the calibration-verification tests commonly used in dendroclimatology, and revealed two prominent periods of drought in the mid-eighteenth and late-nineteenth enturies. The former lasted nearly 30 years and was concurrent with a similar drought over northwestern Thailand inferred from teak rings, suggesting a ``mega-drought'' extending across Indochina in the eighteenth century. Both of our reconstructed droughts are consistent with the periods of warm sea surface temperature (SST)anomalies in the tropical Pacific. Spatial correlation analyses with global SST indicated that ENSO-like anomalies might play a role in modulating droughts over the region, with El Nio (warm) phases resulting in reduced rainfall. However, significant correlation was also seen with SST over the Indian Ocean and the north Pacific,suggesting that ENSO is not the only factor affecting the climate of the area. Spectral analyses revealed significant peaks in the range of 53.9-78.8 years as well as in the ENSO-variability range of 2.0 to 3.2 years.

Matching sender and receiver: poikilothermy and frequency tuning in a tree cricket

Animals communicate in non-ideal and noisy conditions. The primary method they use to improve communication efficiency is sender-receiver matching: the receiver's sensory mechanism filters the impinging signal based on the expected signal. In the context of acoustic communication in crickets, such a match is made in the frequency domain. The males broadcast a mate attraction signal, the calling song, in a narrow frequency band centred on the carrier frequency (CF), and the females are most sensitive to sound close to this frequency. In tree crickets, however, the CF changes with temperature. The mechanisms used by female tree crickets to accommodate this change in CF were investigated at the behavioural and biomechanical level. At the behavioural level, female tree crickets were broadly tuned and responded equally to CFs produced within the naturally occurring range of temperatures (18 to 27 degrees C). To allow such a broad response, however, the transduction mechanisms that convert sound into mechanical and then neural signals must also have a broad response. The tympana of the female tree crickets exhibited a frequency response that was even broader than suggested by the behaviour. Their tympana vibrate with equal amplitude to frequencies spanning nearly an order of magnitude. Such a flat frequency response is unusual in biological systems and cannot be modelled as a simple mechanical system. This feature of the tree cricket auditory system not only has interesting implications for mate choice and species isolation but may also prove exciting for bio-mimetic applications such as the design of miniature low frequency microphones.

Females of a tree cricket prefer larger males but not the lower frequency male calls that indicate large body size

In the tree cricket Oecanthus henryi, females are attracted by male calls and can choose between males. To make a case for female choice based on male calls, it is necessary to examine male call variation in the field and identify repeatable call features that are reliable indicators of male size or symmetry. Female preference for these reliable call features and the underlying assumption behind this choice, female preference for larger males, also need to be examined. We found that females did prefer larger males during mating, as revealed by the longer mating durations and longer spermatophore retention times. We then examined the correlation between acoustic and morphological features and the repeatability of male calls in the field across two temporal scales, within and across nights. We found that carrier frequency was a reliable indicator of male size, with larger males calling at lower frequencies at a given temperature. Simultaneous playback of male calls differing in frequency, spanning the entire range of natural variation at a given temperature, revealed a lack of female preference for low carrier frequencies. The contrasting results between the phonotaxis and mating experiments may be because females are incapable of discriminating small differences in frequency or because the change in call carrier frequency with temperature renders this cue unreliable in tree crickets. (C) 2012 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.

An approximation to the QoS aware throughput region of a tree network under IEEE 802.15.4 CSMA/CA with application to wireless sensor network design

In the context of wireless sensor networks, we are motivated by the design of a tree network spanning a set of source nodes that generate packets, a set of additional relay nodes that only forward packets from the sources, and a data sink. We assume that the paths from the sources to the sink have bounded hop count, that the nodes use the IEEE 802.15.4 CSMA/CA for medium access control, and that there are no hidden terminals. In this setting, starting with a set of simple fixed point equations, we derive explicit conditions on the packet generation rates at the sources, so that the tree network approximately provides certain quality of service (QoS) such as end-to-end delivery probability and mean delay. The structures of our conditions provide insight on the dependence of the network performance on the arrival rate vector, and the topological properties of the tree network. Our numerical experiments suggest that our approximations are able to capture a significant part of the QoS aware throughput region (of a tree network), that is adequate for many sensor network applications. Furthermore, for the special case of equal arrival rates, default backoff parameters, and for a range of values of target QoS, we show that among all path-length-bounded trees (spanning a given set of sources and the data sink) that meet the conditions derived in the paper, a shortest path tree achieves the maximum throughput. (C) 2015 Elsevier B.V. All rights reserved.

Secondary attribute retrieval using tree data structures

Several techniques are known for searching an ordered collection of data. The techniques and analyses of retrieval methods based on primary attributes are straightforward. Retrieval using secondary attributes depends on several factors. For secondary attribute retrieval, the linear structures—inverted lists, multilists, doubly linked lists—and the recently proposed nonlinear tree structures—multiple attribute tree (MAT), K-d tree (kdT)—have their individual merits. It is shown in this paper that, of the two tree structures, MAT possesses several features of a systematic data structure for external file organisation which make it superior to kdT. Analytic estimates for the complexity of node searchers, in MAT and kdT for several types of queries, are developed and compared.

A comparative study of multiple attribute tree and inverted file structures for large bibliographic files

A variety of data structures such as inverted file, multi-lists, quad tree, k-d tree, range tree, polygon tree, quintary tree, multidimensional tries, segment tree, doubly chained tree, the grid file, d-fold tree. super B-tree, Multiple Attribute Tree (MAT), etc. have been studied for multidimensional searching and related problems. Physical data base organization, which is an important application of multidimensional searching, is traditionally and mostly handled by employing inverted file. This study proposes MAT data structure for bibliographic file systems, by illustrating the superiority of MAT data structure over inverted file. Both the methods are compared in terms of preprocessing, storage and query costs. Worst-case complexity analysis of both the methods, for a partial match query, is carried out in two cases: (a) when directory resides in main memory, (b) when directory resides in secondary memory. In both cases, MAT data structure is shown to be more efficient than the inverted file method. Arguments are given to illustrate the superiority of MAT data structure in an average case also. An efficient adaptation of MAT data structure, that exploits the special features of MAT structure and bibliographic files, is proposed for bibliographic file systems. In this adaptation, suitable techniques for fixing and ranking of the attributes for MAT data structure are proposed. Conclusions and proposals for future research are presented.

Bayesian and Decision Tree Approaches for Pattern Recognition Including Feature Measurement Costs

The minimum cost classifier when general cost functionsare associated with the tasks of feature measurement and classification is formulated as a decision graph which does not reject class labels at intermediate stages. Noting its complexities, a heuristic procedure to simplify this scheme to a binary decision tree is presented. The optimizationof the binary tree in this context is carried out using ynamicprogramming. This technique is applied to the voiced-unvoiced-silence classification in speech processing.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Effect of rodents on seed fate of five hornbill-dispersed tree species in a tropical forest in north-east India

Hornbills are important dispersers of a wide range of tree species. Many of these species bear fruits with large, lipid-rich seeds that could attract terrestrial rodents. Rodents have multiple effects on seed fates, many of which remain poorly understood in the Palaeotropics. The role of terrestrial rodents was investigated by tracking seed fate of five horn bill-dispersed tree species in a tropical forest in north-cast India. Seeds were marked inside and outside of exclosures below 6-12 parent fruiting trees (undispersed seed rain) and six hornbill nest trees (a post-dispersal site). Rodent visitors and seed removal ere monitored using camera traps. Our findings suggest that several rodent species. especially two species of porcupine were major on-site seed predators. Scatter-hoarding was rare (1.4%). Seeds at hornbill nest trees had lower survival compared with parent fruiting trees, indicating that clumped dispersal by hornbills may not necessarily improve seed survival. Seed survival in the presence and absence of rodents varied with tree species. Some species (e.g. Polyalthia simiarum) showed no difference, others (e.g. Dysoxylum binectariferum) experienced up to a 64%. decrease in survival in the presence of rodents. The differing magnitude of seed predation by rodents can have significant consequences at the seed establishment stage.