6539802
Robot localization using uncalibrated camera invariants
We describe a set of image measurements which are invariant to the camera internals but are location variant. We show that using these measurements it is possible to calculate the self-localization of a robot using known landmarks and uncalibrated cameras. We also show that it is possible to compute, using uncalibrated cameras, the Euclidean structure of 3-D world points using multiple views from known positions. We are free to alter the internal parameters of the camera during these operations. Our initial experiments demonstrate the applicability of the method.
30169882
Aspect graph construction with noisy feature detectors
Many three-dimensional (3D) object recognition strategies use aspect graphs to represent objects in the model base. A crucial factor in the success of these object recognition strategies is the accurate construction of the aspect graph, its ease of creation, and the extent to which it can represent all views of the object for a given setup. Factors such as noise and nonadaptive thresholds may introduce errors in the feature detection process. This paper presents a characterization of errors in aspect graphs, as well as an algorithm for estimating aspect graphs, given noisy sensor data. We present extensive results of our strategies applied on a reasonably complex experimental set, and demonstrate applications to a robust 3D object recognition problem.
1879700
Hand gesture modelling and recognition involving changing shapes and trajectories, using a Predictive EigenTracker
We present a novel eigenspace-based framework to model a dynamic hand gesture that incorporates both hand shape as well as trajectory information. We address the problem of choosing a gesture set that models an upper bound on gesture recognition efficiency. We show encouraging experimental results on a such a representative set.
18611387
Robust Fingerprint Classification Using An Eigen Block Directional Approach
This paper describes a method of fingerprint classification using Eigen Block Directional Fingerprints. The method we propose dispenses off with the preprocessing stages such as segmentation, binarisation, thinning etc. We determine the block directional representation of a fingerprint and the location of the core points in a set of template fingerprints which belong to the same class. In the next step, we determine the most prominent eigen vectors of each template, which we term as the Eigen Block Directional Fingerprints. To determine the classification of a fingerprint, we extract the Block Directional Fingerprint of the query image and determine the alignment parameters between the template and the query images using eigen tracker which minimises the robust error. We declare the class of the query image as the class of the Eigen Block Directional Fingerprint which result in the least robust error norm.
7441506
Derandomization and distinguishing complexity
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.
411400
Parity Problems in Planar Graphs
We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. This completely settles the question regarding the complexity of modular computation of the number of spanning trees in planar graphs. The techniques used rely heavily on algebraic-topology. In the spirit of counting problems modulo 2k, we also exhibit a highly parallel oplusL algorithm for finding the value of a Permanent modulo 2k. Previously, the best known result in this direction was Valiant's result that this problem lies in P.
12929901
Completeness of Neighbourhood Logic
This paper presents a completeness result for a first-order interval temporal logic, called Neighbourhood Logic (NL) which has two neighbourhood modalities. NL can support the specification of liveness and fairness properties of computing systems as well as formalisation of many concepts of real analysis. These two modalities are also adequate in the sense that they can derive other important unary and binary modalities of interval temporal logic. We prove the completeness result for NL by giving a Kripke model semantics and then mapping the Kripke models to the interval models for NL.
17398921
Design issues for a high-performance distributed shared memory on symmetrical multiprocessor clusters
Clusters of Symmetrical Multiprocessors (SMPs) have recently become the norm for high-performance economical computing solutions. Multiple nodes in a cluster can be used for parallel programming using a message passing library. An alternate approach is to use a software Distributed Shared Memory (DSM) to provide a view of shared memory to the application programmer. This paper describes Strings, a high performance distributed shared memory system designed for such SMP clusters. The distinguishing feature of this system is the use of a fully multi-threaded runtime system, using kernel level threads. Strings allows multiple application threads to be run on each node in a cluster. Since most modern UNIX systems can multiplex these threads on kernel level light weight processes, applications written using Strings can exploit multiple processors on a SMP machine. This paper describes some of the architectural details of the system and illustrates the performance improvements with benchmark programs from the SPLASH-2 suite, some computational kernels as well as a full fledged application. It is found that using multiple processes on SMP nodes provides good speedups only for a few of the programs. Multiple application threads can improve the performance in some cases, but other programs show a slowdown. If kernel threads are used additionally, the overall performance improves significantly in all programs tested. Other design decisions also have a beneficial impact, though to a lesser degree.
11274155
Minimum-Energy Broadcast Using Practical Directional Antennas in All-Wireless Networks
Energy-efficient broadcast communication is an important problem in wireless ad hoc networks. Previously, minimum-energy broadcast that exploits the broadcast nature of radio transmission has been studied and shown to be NP-complete for omnidirectional antennas. In this paper, we investigate the minimum-energy broadcast problem under a wide spectrum of directional antenna models, including sectored antennas with fixed sectors and beamwidth and antenna array-based smart antennas with varying degrees of beam orientation and beamwidth. We first propose the RF design and implementation of each model, which suggests the practical parameters of antennas under that model. We then show that the minimum-energy broadcast problem under each of the antenna models is NP-complete. Lastly, we present a heuristic algorithm based on BIP for the above problem under each directional antenna model and experimentally compare the energy efficiency of using different directional antennas using these heuristics. Our results show that using antennas with adjustable orientation and variable beamwidth gives the best results. For such antennas, the scanning angle is the dominant factor in improving the quality of the broadcast trees. The number of antennas per node is not that critical to obtaining a better broadcast tree as long as it is large enough to cover the entire 360◦ around a node so as to prevent network partitioning.