Abstract

Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world data sets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular work efficient solutions aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained for the pruned graph, the solution is extended to the entire graph. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-ofthe-art solutions. Such an improvement has the potential to speed up other applications that rely on these algorithms.

Abstract

In this work we consider a quantum network consisting of nodes and entangled states connecting them. In every node there is a single player. The players at the intermediate nodes carry out measurements to produce an entangled state between the initial and final node. Here we address the problem that how much classical as well as quantum information can be sent from initial node to final node. In this context, we present strong theorems which state that how the teleportation capability of this remotely prepared state is linked up with the fidelities of teleportation of the resource states. Similarly, we analyze the super dense coding capacity of this remotely prepared state in terms of the capacities of the resource entangled states. However, we first obtain the relations involving the amount of entanglement of the resource states with the final state in terms concurrence. These relations are quite similar to the bounds obtained in references [G. Gour, Phys. Rev. A 71, 012318 (2005); G. Gour, B.C. Sanders, Phys. Rev. Lett. 93, 260501 (2005)]. More specifically, in an arbitrary quantum network when two nodes are not connected, our result shows how much information, both quantum and classical can be transmitted between these nodes. We show that the amount of transferable information depends on the capacities of the inter connecting entangled resources. These results have a tremendous future application in the context of determining the optimal path in a quantum network to send the maximal possible information.

Abstract

It often happens in quantum information processing that we are given an entangled pair and asked to create more entangled pairs by using local quantum operations. This need arises from the fact that sometimes there is more priority on increasing number of participants in information processing scheme rather than on the efficiency of it. To address this we consider a 2⊗ 2 dimensional system and apply optimal universal quantum cloner to create more entangled pairs. Then we analyze the dependence of maximal fidelity of teleportation and super dense coding capacity on broadcasting and cloning fidelities. Since the amount of quantum correlation, namely entanglement and discord, between the participating subsystems play a vital role in the efficiency of information processing schemes, we further study the dependence of these quantum correlations, on broadcasting and cloning fidelities.

Abstract

This paper describes a novel tortuosity measure, based on the premise that tortuosity is a measure of deviation from an ideal non-tortuous vessel. Hence, we propose to model the overall shape of an ideal vessel as a quadratic polynomial at a larger scale while the deviations are modeled as quadratic polynomials at smaller scales. Thus, a given vessel center-line is decomposed as a sum of quadratic polynomials of decreasing scale. This Quadratic Polynomial Decomposition is used as a framework for defining a quantitative measure of tortuosity. As opposed to the existing proposed measures, our method can distinguish between the relative size, shapes and orientations of the vessel bends. The measure is position and scale invariant and satisfies two key desired properties: it varies directly with frequency of twists at fixed amplitude and it varies directly with amplitude of twists when their frequency is fixed. The proposed method has been tested on a standard data set containing 30 artery and 30 vein vessel segments, and shown to be among the best measures as compared to the results of existing methods.

Abstract

Diffusion Weighted Magnetic Resonance Imaging (DWI) is routinely used for early detection of cerebral ischemic changes in acute stroke. Fast acquisition with a standard echoplanar imaging technique generally compromises the image signal-to-noise ratio and in-plane resolution resulting in a reduction of the conspicuity and definition of lesions in the acquired data when viewed on a standard 8-bit display. We present a novel method for automatically and adaptively determining the window settings that enhance the contrast of the image relative to the ischemic lesions. The method performs a coarse segmentation of the lesions followed by contrast-to-noise ratio based computation of the optimal window parameters. The proposed method was tested on 24 datasets acquired with different protocols. The contrast improvement of the lesions is validated through a mirror region of interest analysis and by using the contrast improvement ratio metric. The average obtained improvement in contrast ranges from 25% to 60%. Preliminary results of segmentation showed a good reduction in the false positives and improvement in the lesion boundaries. A perception study of the windowed results against 8 radiologists was conducted. Reduction of 14.17% in the mean response time of detection was observed. Statistical analysis performed using t-test validates the reduction in mean response time to be significant. Results presented in the study show promise in the method.

Abstract

Population screening for sight threatening diseases based on fundus imaging is in place or being considered worldwide. Most existing programs are focussed on a specific disease and are based on manual reading of images, though automated image analysis based solutions are being developed. Exudates and drusen are bright lesions which indicate very different diseases, but can appear to be similar. Discriminating between them is of interest to increase screening performance. In this paper, we present a Bag of Words approach which can be used to design a system that can play the dual role of content based retrieval (of images with exudates or drusen) system and a decision support system to address the problem of bright lesion discrimination. The approach consists of a novel partitioning of an image into patches from which color, texture, edge and granulometry based features are extracted to build a dictionary. A bag of Words approach is then employed to help retrieve images matching a query image as well as derive a decision on the type of bright lesion in the given (query) image. This approach has been implemented and tested on a combination of public and local dataset of 415 images. The area under the curve for image classification is 0.90 and retrieved precision is 0.76.

Abstract

Abnormality detection is the first step performed by doctors during evaluation of medical images in image based diagnosis, followed by disease-specific evaluation of abnormalities. Perception studies have shown that experts primarily focus on abnormal structures during visual examination for diagnosis. One way to model this behavior in automated image analysis is through visual saliency computation. In this paper, we investigate the potential role of visual saliency for computer aided diagnosis algorithm design. We propose a framework for detecting abnormalities that uses visual saliency computation for sparse representation of the image data that preserves the essential features of a normal image. The proposed method is evaluated for the task of bright lesion detection and classification in color retinal images which is of significance in disease screening. An evaluation of the proposed approach on 5 publicly available datasets yielded area under ROC curve of 0.88 to 0.98 for the detection task and accuracies ranging from 0.93 to 0.96 for lesion discrimination. These results establish visual saliency as an alternate avenue for automated abnormality detection.

Abstract

In this paper, we present a semi-automated method to magnify small motions in videos. This method amplifies invisible or hidden motions in videos. To achieve motion magnification, we process the spatial and temporal information obtained from the video itself. Advantage of this work is that it is application independent. Proposed technique estimates required parameters to get desirable results. We demonstrate performance on 9 different videos. Motion magnification performance is equivalent to existing manual methods.

Abstract

In this paper, we present a novel automated method to detect motion in perfusion weighted images (PWI), which is a type of magnetic resonance imaging (MRI). In PWI, blood perfusion is measured by injecting an exogenous tracer called bolus into the blood flow of a patient and then tracking it in the brain. PWI requires a long data acquisition time to forma time series of volumes. Hence, motion occurs due to patient’s unavoidable movements during a scan, which in turn results into motion corrupted data. There is a necessity of detection of these motion artifacts on captured data for correct disease diagnosis.In PWI, intensity profile gets disturbed due to occurrence of motion and/or bolus passage through the blood vessels. There is no way to distinguish between motion occurrence and bolus passage. In this paper, we propose an efficient time-frequency analysis based motion detection method. We show that proposed method is computationally inexpensive and fast. This method is evaluated on a DSC-MRI sequence with simulated motion of different degrees. We show that our approach detects motion in a few seconds.

Abstract

In this paper, we propose a new security protocol for proxy signature by a hierarchy of proxy signers. In this protocol, the original signer delegates his/her signing capability to a predefined hierarchy of proxy signers. Given the documents of a security class to be signed by the original signer, our scheme suggests a protocol for the hierarchy of proxy signers to sign the document on behalf of the original signer. The concept of hierarchical access control limits the number of people who could sign the document to the people who have the required security clearances. User in a security class requires two secret keys: one which identifies his/her security clearance, and that can also be derived by a user of upper level security clearance and second is his/her private key which identifies him/her as a proxy signer for the signature generation. We show that our scheme is efficient in terms of computational complexity as compared to the existing related proxy signature schemes based on the hierarchical access control. Our scheme also supports addition and deletion of security classes in the hierarchy. We show through security analysis that our scheme is secure against possible attacks. Furthermore, through the formal security analysis using the AVISPA (Automated Validation of Internet Security Protocols and Applications) tool we show that our scheme is also secure against passive and active attacks.