Abstract

We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players’ knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players’ knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case,(2t+ 1)-vertex connectivity is necessary and sufficient, where t is the number of nodes that can be corrupted by the adversary [DDWY93, SKR+05]. We introduce a novel model for quantifying players’ knowledge of network topology, denoted by T K. Given a directed graph G, influenced by a Byzantine adversary that can corrupt up to any t players, we give a necessary and sufficient condition for possibility of PRC over G for any arbitrary topology knowledge T K. It follows from our main characterization theorem that knowledge of up to d=⌊ n− 2t

Abstract

We address the problem of message authentication in communication networks which are resource constrained or are performance bound. Recent research has focused on development of symmetric key protocols for authentication in such networks. In these protocols, the sender generates a pool of keys -used to sign the messages, and distributes a different subset of keys -used to verify the signatures, to each user. However, in these protocols, users can collude to combine their keys and impersonate the sender by generating the sender signatures. In this work, we describe a family of collusion resistant symmetric key distribution protocols for authentication which address the problem of collusion. We show that the collusion resistance achieved using our protocols is practical (and hence, sufficient) for networks whose communication diameter is known or is within fixed bounds. Furthermore, we show that some existing protocols in literature are members of our family of protocols.

Abstract

This paper focuses on anti-magic labellings of planar graphs of type (a, b, c) introduced by Lih (Util. Math. 24 (1983), 165–197). We show that a certain class of planar graphs defined using the complete graphs and a class of planar graphs defined using the complete bipartite graphs are (1, 1, 0) and (1, 1, 1)-anti-magic under certain mild conditions.

Abstract

The study was conducted in order to compute the deviations in the Peak Ground Acceleration values as specified in the IS 1893 2002 for different regions from the values obtained from modern empirical attenuation formulae. For this purpose earthquake events catalogue was prepared for various earthquake that occurred from year 1984 to 2003 in peninsular India.

Abstract

Document image segmentation algorithms primarily aim at separating text and graphics in presence of complex layouts. However, for many non-Latin scripts, segmentation becomes a challenge due to the characteristics of the script. In this paper, we empirically demonstrate that successful algorithms for Latin scripts may not be very effective for Indic and complex scripts. We explain this based on the differences in the spatial distribution of symbols in the scripts. We argue that the visual information used for segmentation needs to be enhanced with other information like script models for accurate results.

Abstract

Super-resolution reconstruction algorithms assume the availability of exact registration and blur parameters. Inaccurate estimation of these parameters adversely affects the quality of the reconstructed image. However, traditional approaches for image registration are either sensitive to image degradations such as variations in blur, illumination and noise, or are limited in the class of image transformations that can be estimated. We propose an accurate registration algorithm that uses the local phase information, which is robust to the above degradations. We derive the theoretical error rate of the estimates in presence of non-ideal band-pass behavior of the filter and show that the error converges to zero over iterations. We also show the invariance of local phase to a class of blur kernels. Experimental results on images taken under varying conditions clearly demonstrates the robustness of our approach.

Abstract

We propose a novel approach to 3D hand geometry based person authentication using projected light patterns. Instead of explicitly computing a depth map of the palm for recognition, we capture the depth information in the deformations of a projected texture pattern, and use it directly for recognition. The deformed pattern is characterized using local texture measures, which can encode the certain depth characteristics of the palm. An authentication system built using the proposed technique achieves an equal error rate of 0.84% on a dataset of 1341 samples collected from 149 users, as opposed to 4.03% using traditional 2D features on an identical dataset. The approach is robust as well as computationally efficient and could be applied to other 3D object recognition problems as well.

Abstract

Text-dependent writer verification systems are preferred over text-independent systems due to the accuracy they achieve with small amount of data. However, text-dependent systems are prone to forgery. This paper proposes a novel boosting based framework for writerspecific text generation to increase the accuracy and a method of text variation to make the system robust to forgery. The approach is able to achieve error rates of 5% with just 6 words as compared to random(11%) or most discriminative(22%) primitive selection methods on a dataset containing 20 writers. Boosting based text selection also provides the flexibility to incorporate text variation across multiple authentications, which in turn makes the system robust to forgery

Abstract

Algorithms for classification of 3D objects either recover the depth information lost during imaging using multiple images, structured lighting, image cues, etc. or work directly the images for classification. While the latter class of algorithms are more efficient and robust in comparison, they are less accurate due to the lack of depth information. We propose the use of structured lighting patterns projected on the object, which gets deformed according to the shape of the object. Since our goal is object classification and not shape recovery, we characterize the deformations using simple texture measures, thus avoiding the error prone and computationally expensive step of depth recovery. Moreover, since the deformations encode depth variations of the object, the 3D shape information is implicitly used for classification. We show that the information thus derived can significantly improve the accuracy of object classification algorithms, and derive the theoretical limits on height variations that can be captured by a particular projector-camera setup. A 3D texture classification algorithm derived from the proposed approach achieves a ten-fold reduction in error rate on a dataset of 30 classes, when compared to state-of-the-art image based approaches. We also demonstrate the effectiveness of the approach for a hand geometry based authentication system, which achieves a four-fold reduction in the equal error rate on a dataset containing 149 users.

Abstract

Projector-Camera systems are extensively used for various applications in computer vision, immersive environments, visual servoing, etc. Due to gaps between neighboring pixels on the projector’s image plane and variations in scene depth, the mage projected onto a scene shows pixelation and blurring artifacts. In certain vision and graphics applications, it is desirable that a high quality composition of the scene and the projected image, excluding the artifacts, is captured, while retaining the scene characteristics. Localization of projected pixels can also help in dense estimation of scene shape. In this paper, we address the problem of localizing each of the projected pixels from a captured scene and restoring the captured image so that the pixelation and blurring artifacts of the projector are removed. We improve the quality of the captured image further by virtualizing a high resolution projector. i.e., we modify the captured image as if the scene were illuminated with a high-resolution projector. We propose robust solutions to these problems and demonstrate their effectiveness on scenes of different complexities.