Abstract

Edge detection is an important image processing technique used in face recognition. In this paper we propose an edge detection algorithm suitable for extracting edge maps from facial images under noisy conditions. We employ several improvised techniques like composite gradient variation measures, weighted wide convolution kernels and dual maxima detection. This helps in removing spurious edge points along stronger edges, extracting fine edge lines along facial boundaries and curvatures and suppressing noise. This is demonstrated by extracting edges from facial images degraded by Gaussian, speckle and salt and pepper noise. For performance measurement and evaluation Pratt's Figure of Merit and Signal to Noise statistics is used

Abstract

The current research focused on the issues related to human-bird conflicts and subsequent alternatives adopted by the migratory birds at Uppalapadu Lake (India). The study collates the information from field observations and literature surveys and draws conclusions based on the observation data. The study highlights the ways the local community, Forest Department, activist groups and other organizations participate in protecting the birds from harm. It also focuses on some of the management initiatives taken by the Forest Department that are helping the birds during their breeding periods. Overall, the research identifies the ecological importance of the lake with respect to birds and stresses the need for its protection and further expansion.

Abstract

In the present study, three large ecological plots of 3 ha each were surveyed in 3 different forest types of North Andaman Islands. Each 3-ha plot (30 sub-plots of 0.1 ha each) was classified into different classes based on site quality as either excellent, good, moderate or poor using an index developed by utilizing vegetation parameters such as species richness, diversity, density, among others. Analysis revealed most of the area to be under the good category in three forest communities, indicating that forests of North Andaman are potential sites of species richness and diversity. The “general limit of species assemblage” with respect to higher angiosperm taxa in North Andaman was observed based on two independent approaches of sampling: stratified random plots and the large area ecological plots. The general limit of species assemblage was in the range of 14-33 species. The present analysis provides a base …

Abstract

In this work, we study the problem of reporting and counting maximal points in a query rectangle for a set of n integer points that lie on an n×n grid. A point is said to be maximal inside a query rectangle if it is not dominated by any other point inside the query rectangle. Our model of computation is unit-cost RAM model with word size of O(logn) bits. For the reporting version of the problem, we present a data structure of size words and support querying in time where k is the size of the output. For the counting version, we present a data structure of size words which supports querying in . Both the data structures are static in nature. The reporting version of the problem has been studied in [1] and [5]. To the best of our knowledge, this is the first sub-logarithmic result for the reporting version and the first work for the counting version of the problem.

Abstract

The use of manycore architectures and accelerators, such as GPUs, with good programmability has allowed them to be deployed for vital computational work. The ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks that we highlight in this paper. It is of high interest therefore to develop a parallel, quality PRNG that also works in an on demand model. In this paper we investigate a CPU+GPU hybrid technique to create an efficient PRNG. The basic technique we apply is that of random walks on expander graphs. Unlike existing generators available in the GPU programming environment, our generator can produce random numbers on demand as opposed to a onetime generation. Our approach produces 0.07 GNumbers per second. The quality of our generator is tested with industry standard tests. We also demonstrate two applications of our PRNG. We apply our PRNG to design a list ranking algorithm which demonstrates the on-demand nature of the algorithm and a Monte Carlo simulation which shows the high quality of our generator.

Abstract

We consider the problem of reporting and counting maximal points in a given orthogonal query range in two-dimensions. Our model of computation is the pointer machine model. Let P be a static set of n points in ℝ2. A point is maximal in P if it is not dominated by any other point in P. We propose a linear space data structure that can support counting the number of maximal points inside a 3-sided orthogonal query rectangle unbounded on its right in O(logn) time. For counting the number of maximal points in a 4-sided orthogonal query rectangle, we propose an O(n logn) space data structure that can be constructed in O(n logn) time and queried upon in O(logn) time. This work proposes the first data structure for counting the number of maximal points in a query range. Das et al. proposed a data structure for the counting version in the word RAM model [WALCOM 2012]. For the corresponding reporting versions, we propose a linear size data structure for reporting maximal points inside a 3-sided query range in time O(logn + k), where k is the size of the output. We propose an O(n logn) size data structure for reporting the maximal points in a 4-sided orthogonal query range in time O(logn + k), where k is the size of the output. The methods we propose for reporting maximal points are simpler than previous methods and meet the best known bounds.

Abstract

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we calltextsc {Max-LPA}, both in terms of its convergence time and in terms of the" quality" of the communities detected.textsc {Max-LPA} is an instance of a class of community detection algorithms calledtextit {label propagation} algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version ofer random graphs with clusters where the probability , of an edge connecting nodes within a cluster is higher than , the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on and ( for any , , where is the number of nodes),textsc {Max-LPA} detects the clusters in just two rounds. Based on this and on empirical results, we conjecture thattextsc {Max-LPA} can correctly and quickly identify communities on clustereder graphs even when the clusters are much sparser, ie, with for some .

Abstract

Graphics processing units (GPUs) provide large computational power at a very low price, which position GPUs well as an ubiquitous accelerator. However, GPUs are space constrained, and hence applications developed for GPUs are space sensitive. Space-constrained computational devices such as GPUs can greatly benefit from representations that reduce space consumption drastically. One such representation is the succinct representation of trees. Succinct representation of trees generally allows for operations such as parent queries, least common ancestor queries, and so on. Mapping such a robust representation to the GPU for targeted applications can lead to substantial improvement in problem sizes that are processed at a given point of time. Space-saving methods such as succinct data structures remain largely unexplored on the GPU. In this work, a succinct representation of ordered trees on the GPU is explored, with application to discrete range searching (DRS). Based on the succinct representations found applicable, a space--saving solution for DRS is presented here. In our method, DRS is mapped to a least common ancestor query on a Cartesian tree. For space-efficient DRS queries, we store the succinct representation of the Cartesian tree of an array. Our method uses a maximum of 7.5 bits of additional space per element. Furthermore, the speed-up achieved by our method is in the range of 20--25 for preprocessing and 25--35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our preprocessing and querying methods obtain a speed-up of 6--8. We also study the applications of the DRS on the GPU. Efficient primitives expand the range of applications performed on the GPU. DRS is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. We suggest that graph algorithms that use the least common ancestor, can be enabled on the GPU based on DRS primitive. We also show some applications of DRS in tree queries and string querying.

Abstract

Sparse matrix-sparse/dense matrix multiplications, spgemm and csrmm, respectively, among other applications find usage in various matrix formulations of graph problems. Considering the difficulties in executing graph problems and the duality between graphs and matrices, computations such as spgemm and csrmm have recently caught the attention of HPC community. These computations pose challenges such as load balancing, irregular nature of the computation, and difficulty in predicting the output size. It is even more challenging when combined with the GPU architectural constraints such as memory accesses, limited shared memory, strict SIMD and thread execution. To address these challenges on a GPU, we evaluate three possible variations of matrix multiplication (Row-Column, Column-Row, Row-Row) and perform suitable optimizations targeted at sparse matrices. Our experiments indicate that the Row-Row formulation, which mostly outperforms the other formulations, is 3.5x faster on average compared to an optimized multi-core implementation in the Intel MKL library. We extend the Row-Row formulation to a CPU+GPU hybrid algorithm that simultaneously utilizes the CPU also. In this direction, we present heuristics to find the right amount of work division between the CPU and the GPU. Our hybrid row-row formulation of the spgemm operation performs 5.5x faster on average when compared to the optimized multi-core implementation in the Intel MKL library. Our experience indicates that it is difficult to identify right amount of work division between the CPU and the GPU. We therefore investigate a subclass of sparse matrices, band matrices, and present an analytical method to identify a good work division when multiplying two band matrices. Our GPU csrmm operation performs 2.5x faster on average when compared to a corresponding implementation in the cusparse library, which outperforms the Intel MKL library implementation.

Abstract

Accurate segmentation of the cup region from retinal images is needed to derive relevant measurements for glaucoma assessment. A novel, depth discontinuity (in the retinal surface)-based approach to estimate the cup boundary is proposed in this paper. The proposed approach shifts focus from the cup region used by existing approaches to cup boundary. The given set of images, acquired sequentially, are related via a relative motion model and the depth discontinuity at the cup boundary is determined from cues such as motion boundary and partial occlusion. The information encoded by these cues is used to approximate the cup boundary with a set of best-fitting circles. The final boundary is found by considering points on these circles at different sectors using a confidence measure. Four different kinds of data sets ranging from synthetic to real image pairs, covering different multiview scenarios, have been used to evaluate the proposed method. The proposed method was found to yield an error reduction of 16% for cup-to-disk vertical diameter ratio (CDR) and 13% for cup-to-disk area ratio (CAR) estimation, over an existing monocular image-based cup segmentation method. The error reduction increased to 33% in CDR and 18% in CAR with the addition of a third view (image) which indicates the potential of the proposed approach.