12928468
Distributed goal recognition algorithms for modular robots
Modular robots are systems composed of a number of independent units that can be reconfigured to fit the task at hand. When the modules are computationally independent, they form a large distributed system with no central controller. We are concerned with the ability of such modular robots to easily recognize the achievement (or lack thereof) of a given goal configuration. We present algorithms for a class of 2D and 3D modular robots, along with correctness and running time analysis. We have successfully implemented the 2D algorithm on the second-generation Crystalline Atomic robot, a self-reconfigurable modular robot under development in our laboratory and we present implementation details and experimental results.
15617422
R*-Histograms: efficient representation of spatial relations between objects of arbitrary topology
Representation of relative spatial relations between objects is often required in many multimedia database applications because spatial relations between objects in an image convey important information about the image. Quantitative representation of spatial relations taking into account shape, size, orientation and distance is often required. The R-Histogram is such a quantitative representation of spatial relations between two objects. However, this method only considers pixels on the object boundary, assuming that the objects are homeomorphic to a 2-ball. For objects with more complicated topology, we propose in this paper the R*-Histogram, a new extension to the R-Histogram. The R*-Histogram generalizes the R-Histogram by taking into account all the pixels in the objects. We also introduce an efficient O(kN log N) time algorithm to compute the R*-Histogram, which is asymptotically faster than the original O(N<sup>2</sup>) time algorithm for the R-Histogram even when k=O(n). Here, N=n<sup>2</sup> denotes the number of pixels in the processed n x n image and k is the number of different directions considered. The effectiveness of the R*-Histogram is evaluated empirically with a Query By Example (QBE) system on a database of 2000 synthetic images containing objects with complicated shape and topology. Experiments have shown that the similarly search results match human intuition very well.
46267544
Neighboring Feature Clustering
In spectral datasets, such as those consisting of MR spectral data derived from MS lesions, neighboring features tend to be highly correlated, suggesting the data lie on some low-dimensional space. Naturally, finding such low-dimensional space is of interest. Based on this real-life problem, this paper extracts an abstract problem, neighboring feature clustering (NFC). Noticeably different from traditional clustering schemes where the order of features doesn't matter, NFC requires that a cluster consist of neighboring features, that is features that are adjacent in the original feature ordering. NFC is then reduced to a piece-wise linear approximation problem. We use minimum description length (MDL) method to solve this reduced problem. The algorithm we proposed works well on synthetic datasets. NFC is an abstract problem. With minor changes, it can be applied to other fields where the problem of finding piece-wise neighboring groupings in a set of unlabeled data arises.
570803
Provable dimension detection using principal component analysis
We present simple algorithms for detecting the dimension k of a smooth manifold M ⊂ Rd from a set P of point samples, provided that P satisfies a standard sampling condition as in previous results. The best running time so far is O(d2O(k7 log k)) worst-case by Giesen and Wagner after the adaptive neighborhood graph is constructed in O(d|P|2) worst-case time. Given the adaptive neighborhood graph, for any l ≥ 1, our algorithm outputs the true dimension with probability at least 1-2-l in O(2O(k)kd(k + l log d)) expected time. Our experimental results validate the effectiveness of our approach in computing the dimension. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which outliers and a small perturbation of the samples are allowed.
14692168
Testbed implementation of delay/fault-tolerant mobile sensor network (DFT-MSN)
In this paper we present a testbed implementation of delay/fault-tolerant mobile sensor network (DFT-MSN) for pervasive information gathering. We develop a simple and efficient data delivery scheme tailored for DFT-MSN, which consists of two key components for data transmission and queue management, respectively. The former makes decision on when and where to transmit data messages based on the delivery probability, which reflects the likelihood that a sensor can deliver data messages to the sink. The latter decides which messages to transmit or drop based on the fault tolerance, which indicates the importance of the messages. We implement the proposed data delivery scheme and establish a DFT-MSN testbed by using Crossbow sensors. A small scale experiment is carried out, which shows the effectiveness and efficiency of DFT-MSN
3032688
Statistical Identification of Key Phrases for Text Classification
Algorithms for text classification generally involve two stages, the first of which aims to identify textual elements (words and/or phrases) that may be relevant to the classification process. This stage often involves an analysis of the text that is both language-specific and possibly domain-specific, and may also be computationally costly. In this paper we examine a number of alternative keyword-generation methods and phrase-construction strategies that identify key words and phrases by simple, language-independent statistical properties. We present results that demonstrate that these methods can produce good classification accuracy, with the best results being obtained using a phrase-based approach.
14888347
Error Resilient Mode Decision in Scalable Video Coding
Error resilient macroblock mode decision has been extensively investigated in the literature for single-layer video coding, for which error resilient mode decision is also called as intra refresh. In this paper, we present a loss-aware rate-distortion optimized macroblock mode decision algorithm for scalable video coding, wherein more macroblock coding modes than intra and inter are involved. Thanks to the good performance, the proposed method has been adopted into the joint scalable video model by the joint video team.
34251654
Near-Linear Time Approximation Algorithms for Curve Simplification
We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P? whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P? while ensuring that the error between P? and P is below a certain threshold. We consider two fundamentally different error measures -- Hausdorff and Frechet error measures. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ? > 0, compute a simplified polygonal curve P? whose error is less than ? and size at most the size of an optimal simplified polygonal curve with error ?/2. We consider monotone curves in the case of Hausdorff error measure and arbitrary curves for the Frechet error measure. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.