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

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

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.

Abstract

Retinopathy of prematurity (ROP) is a vascular disease in premature infants. This is characterized by abnormal vessel growth and subsequent fibrosis in the peripheral retina. The prognosis of ROP relies on information on the presence of abnormal growth and their location. Diagnosis is based on a series of images obtained with a wide field of view camera (such as RetCam), to capture the complete retina. In this paper, we present a novel and efficient hierarchal mosaicing algorithm, for neonatal images of varying quality. We employ a vessel-based quality metric and exploit the knowledge of the retinal structure to automatically select a subset of images from a given set, to construct a good quality mosaic. Such mosaics can aid the assessment of ROP by providing a comprehensive and complete view of the entire retina. The hierarchal approach underlying the method makes it possible to complete the mosaicing task in close to real time. The proposed method has been tested on 14 sets of data with each set consisting of 6-35 retinal images acquired using RetCam and the generated mosaics are found to be of good quality as validated by a clinical expert.

Abstract

The task of detecting peri-papillary indicators associated with the glaucoma is challenging due to the high degree of intra and inter-image variations commonly seen in colour retinal images. The existing approaches based on direct modeling of the region of interest failto handle such image variations which compromises detection accuracy.In this paper, a novel detection strategy is proposed which exploits the saliency property associated with these indicators. The region of interest is modeled as a region substantially different from the adjacent image regions. This dissimilarity information is derived at the feature level, be-tween the target and its adjacent regions. Based on the proposed strategy,two novel methods are presented for the detection of peri-papillary atrophy and RNFL defect from colour retinal images. Two different datasets have been used to evaluate the performance of developed solutions. The obtained results are encouraging and establish the strength of the pro-posed strategy in handling high degree of image variations. The preliminary results and comparative evaluation with direct modeling strategy show viability of proposed strategy to be used in the glaucoma assessment task.

Abstract

Diffusion Weighted MR Imaging (DWI) is routinely used for early detection of cerebral ischemic stroke.DWI with higher b-values (b=2000) provide improved sensitivity, higher conspicuity and reduced artifacts and thus improve the detectability of smallest infarcts than conventional DWI (b=1000). We propose a novel framework for accurately detecting stroke regions by combining information from multiple sources:b2000,b1000 data and the apparent diffusion coefficient map.The detected lesions are finally segmented using an active contour approach. The proposed method was tested on 41 datasets acquired with different protocols. A comparison of our method with a leading method [3] validates the effectiveness of our approach. The mediandice coefficient, sensitivity and specificity for stroke segmentation were 0.84, 87.07% and 99.90% respectively.The strength of the proposed method is its ability to capture (and accurately segment) the small (and large) lesions in the data which are often missed by segmentation methods operating on a single b-value data.

Abstract

This paper addresses the data corruption that occurs due to patient motion during a scan which is particularly a problem in perfusion weighted MRI due to long scan times. Motion correction is typically the rate-limiting step in processing as each volume has to be registered to a reference volume. This is compounded by the dynamically varying contrast in the volume series due to passage of an injected contrast agent. We propose an efficient two stage motion correction method, consisting of motion detection and a 2-pass registration method for aligning the motion-corrupted volumes. A 2D block-wise phase correlation in central slices is used for the first stage. Alignment employs a strategy which is sensitive to the status of the bolus in the volume and is based on gamma-variate function fitting for intensity correction to handle dynamic contrast in DSC-MRI. Evaluation of the approach shows that it is fast and accurate.

Abstract

Several computational visual saliency models have been pro-posed in the context of viewing natural scenes. We aim to investigate the relevance of computational saliency models in medical images in the context of abnormality detection.We report on two studies aimed at understanding the role of visual saliency in medical images. Diffuse lesions in ChestX-Ray images, which are characteristic of Pneumoconiosis and high contrast lesions such as ‘Hard Exudates’ in retinal images were chosen for the study. These approximately correspond to conjunctive and disjunctive targets in a visual search task. Saliency maps were computed using three popular models namely Itti-Koch [7], GBVS [3] and SR [4].The obtained maps were evaluated against gaze maps and ground truth from medical experts. Our results show that GBVS is seen to perform the best(Mdn. ROC area= 0.77) for chest X-Ray images while SRperforms the best (ROC area= 0.73) for retinal images,thus asserting that searching for conjunctive targets calls for a more local examination of an image while disjunctive targets call for a global examination. Based on the results of the above study, we propose extensions for the two best performing models. The first extension makes use of top down knowledge such as lung segmentation. This is shown to improve the performance of GBVS to some extent. Inthe second case the extension is by way of including multi-scale information. This is shown to significantly (by 28.76%)improve abnormality detection. The key insight from these studies is that bottom saliency continues to play a predominant role in examining medical images.

Abstract

The blood perfusion measurement is done by injecting a bolus of contrast agent in the brain followed by imaging over a period of time (scan). This process can extend into minutes and hence any patient motion mid-scan results in corrupted data. This is often observed in dynamic magnetic resonance(MR) imaging for both susceptibility (DSC) and contrast enhanced (DCE) scans. Motion correction done after scanning is typically the most time-intensive step in the entire measurement process since it involves registering each volume in the time-series to a reference volume. We argue that detecting the presence of motion prior to correction can mitigate this problem by reducing the number of volumes to be corrected. The challenge in motion detection is that the injected contrast alters the signal intensity as a function of time leading to false alarms. We present a robust multi-stage method: subdivision of the time series data into bolus and non bolus phases; clustering-based identification of bolus-affected pixels followed by correction of their intensity using a Gamma variate function fitting-based method and a 2Dblock-wise phase correlation for detecting motion between adjacent volumes in DSC-MRI data. The proposed method was tested on a DSC MR sequence with simulated motion of varying degrees. The experimental results show that the entropy of the derived motion fields is a good metric for detecting and categorizing the motion. The proposed scheme when applied prior to correction can achieve on average a37% reduction in the time required for motion correction