A set of vectors S ⊆ R d is ( k 1 , ε ) -clusterable if there are k 1 balls of radius ε that cover S . A set of vectors S ⊆ R d is ( k 2 , δ ) -far from being clusterable if there are at least k 2 vectors in S , with all pairwise distances at least δ . We propose a probabilistic algorithm to distinguish between these two cases. Our algorithm reaches a decision by only looking at the extreme values of a scalar valued hash function, defined by a random field , on S ; hence, it is especially suitable in distributed and online settings. An important feature of our method is that the algorithm is oblivious to the number of vectors: in the online setting, for example, the algorithm stores only a constant number of scalars, which is independent of the stream length. We introduce random field hash functions, which are a key ingredient in our paradigm. Random field hash functions generalize locality-sensitive hashing (LSH). In addition to the LSH requirement that “nearby vectors are hashed to similar values”, our hash function also guarantees that the “hash values are (nearly) independent random variables for distant vectors”. We formulate necessary conditions for the kernels which define the random fields applied to our problem, as well as a measure of kernel optimality, for which we provide a bound. Then, we propose a method to construct kernels which approximate the optimal one.

Collision-avoiding motion planning for articulated robotic arms is one of the major challenges in robotics. The difficulty of the problem arises from its high dimensionality and the intricate geometry of the feasible space. Our goal is to seek large convex domains in configuration space, which contain no obstacles. In these domains, simple linear trajectories are guaranteed to be collision free, and can be leveraged for further optimization. To find such domains, practitioners have harnessed a methodology known as Sum-Of-Squares (SOS) Programming. SOS programs, however, are notorious for their poor scaling properties, which makes it challenging to employ them for complex problems. In this paper, we explore a simple formulation for a two-dimensional arm, which results in smaller SOS programs than previous suggested ones. We show that this formulation can express a variety of scenarios in a unified manner.

Tracking the value of a function computed from a dynamic, distributed data stream is a challenging problem with many real-world applications. Continuously forwarding data updates can be costly, yet complex functions are difficult to evaluate when data is not centralized. One general approach to continuous distributed monitoring is the Geometric Monitoring (GM) family of techniques. GM reduces the functional monitoring problem to a set of local constraints that each node checks locally, and uses a simple protocol to update those constraints as needed.While most work on GM focuses on reducing the number of messages exchanged by the common GM protocol, with one recent notable exception, there has been little attention to reducing the size of those messages, which impacts bandwidth.We propose the Distance Scheme: a novel bandwidth-efficient variation of the GM protocol that reduces the size of most monitoring messages in GM to a single scalar, and is compatible with the large body of prior work on GM. We apply it to monitor three different functions using three real-world datasets, and show it substantially reduces bandwidth while requiring fewer messages to be transmitted than the current state-of-the-art approach. We further describe a value-based scheme that, while typically outperformed by the Distance Scheme, is simpler to apply, matches state-of-the-art bandwidth performance with fewer messages, and is also compatible with existing work.

As data becomes dynamic, large, and distributed, there is increasing demand for what have become known asdistributed stream algorithms. Since continuously collecting the data to a central server and processing it there is infeasible, a common approach is to definelocalconditions at the distributed nodes, such that—as long as they are maintained—some desirableglobalcondition holds. Previous methods derived local conditions focusing on communication efficiency. While proving very useful for reducing the communication volume, these local conditions often suffer from heavy computational burden at the nodes. The computational complexity of the local conditions affects both the runtime and the energy consumption. These are especially critical for resource-limited devices like smartphones and sensor nodes. Such devices are becoming more ubiquitous due to the recent trend toward smart cities and the Internet of Things. To accommodate for high data rates and limited resources of these devices, it is crucial that the local conditions be quickly and efficiently evaluated. Here we propose a novel approach, designated CB (for Convex/Concave Bounds). CB defines local conditions using suitably chosen convex and concave functions. Lightweight and simple, these local conditions can be rapidly checked on the fly. CB’s superiority over the state-of-the-art is demonstrated in its reduced runtime and power consumption, by up to six orders of magnitude in some cases. As an added bonus, CB also reduced communication overhead in all the tested application scenarios.

The following is a very common question in numerous theoretical and application-related domains: given a graph G, does it satisfy some given property? For example, is G connected? Is its diameter smaller than a given threshold? Is its average degree larger than a certain threshold? Traditionally, algorithms to quickly answer such questions were developed for static and centralized graphs (i.e. G is stored in a central server and the list of its vertices and edges is static and quickly accessible). Later, as dictated by practical considerations, a great deal of attention was given to on-line algorithms for dynamic graphs (where vertices and edges can be added and deleted); the focus of research was to quickly decide whether the new graph still satisfies the given property. Today, a more difficult version of this problem, referred to as the distributed monitoring problem, is becoming increasingly important: large graphs are not only dynamic, but also distributed, that is, G is partitioned between a few servers, none of which "sees" G in its entirety. The question is how to define local conditions, such that as long as they hold on the local graphs, it is guaranteed that the desired property holds for the global G. Such local conditions are crucial for avoiding a huge communication overhead. While defining local conditions for linear properties (e.g. average degree) is relatively easy, they are considerably more difficult to derive for non-linear functions over graphs. We propose a solution and a general definition of solution optimality, and demonstrate how to apply it to two important graph properties - the spectral gap and the number of triangles. We also define an absolute lower bound on the communication overhead for distributed monitoring, and compare our algorithm to it, with excellent results. Last but not least, performance improves as the graph becomes larger and denser - that is, when distributing it is more important.

Entropy is a fundamental property of data and a key metric in many scientific and engineering fields. Entropy estimation has been extensively studied, but almost always under the assumption that there is a single data stream, seen in its entirety by one node running the estimation algorithm. Multiple distributed data sources are becoming increasingly common, however, with applications in signal processing, computer science, medicine, physics, and more. Centralizing all data can be infeasible, for example in networks of battery or bandwidth limited sensors, so entropy estimation in distributed streams requires new, communication-efficient approaches.

As data becomes dynamic, large, and distributed, there is increasing demand for what have become known as distributed stream algorithms. Since continuously collecting the data to a central server and processing it there incurs very high communication and computation complexities, it is advantageous to define local conditions at the nodes, such that -- as long as they are maintained -- some desirable global condition holds.

A canonical problem in computer vision is category recognition (e.g., find all instances of human faces, cars etc., in an image). Typically, the input for training a binary classifier is a relatively small sample of positive examples, and a huge sample of negative examples, which can be very diverse, consisting of images from a large number of categories. The difficulty of the problem sharply increases with the dimension and size of the negative example set. We propose to alleviate this problem by applying a "hybrid" classifier, which replaces the negative samples by a prior, and then finds a hyperplane which separates the positive samples from this prior. The method is extended to kernel space and to an ensemble-based approach. The resulting binary classifiers achieve an identical or better classification rate than SVM, while requiring far smaller memory and lower computational complexity to train and apply.

We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition.

Least squares regression is widely used to understand and predict data behavior in many fields. As data evolves, regression models must be recomputed, and indeed much work has focused on quick, efficient and accurate computation of linear regression models. In distributed streaming settings, however, periodically recomputing the global model is wasteful: communicating new observations or model updates is required even when the model is, in practice, unchanged. This is prohibitive in many settings, such as in wireless sensor networks, or when the number of nodes is very large. The alternative, monitoring prediction accuracy, is not always sufficient: in some settings, for example, we are interested in the model's coefficients, rather than its predictions. We propose the first monitoring algorithm for multivariate regression models of distributed data streams that guarantees a bounded model error. It maintains an accurate estimate using a fraction of the communication by recomputing only when the precomputed model is sufficiently far from the (hypothetical) current global model. When the global model is stable, no communication is needed.

Carpooling for commuting can save cost and helps in reducing pollution. An automatic Web based Global CarPooling Matching Service (GCPMS) for matching commuting trips has been designed. The service supports carpooling candidates by supplying advice during their exploration for potential partners. Such services collect data about the candidates, and base their advice for each pair of trips to be combined, on an estimate of the probability for successful negotiation between the candidates to carpool. The probability values are calculated by a learning mechanism using, on one hand, the registered person and trip characteristics, and on the other hand, the negotiation feedback. The problem of maximizing the expected value of carpooling negotiation success was formulated and was proved to be NP-hard. In addition, the network characteristics for a realistic case have been analyzed. The carpooling network was established using results predicted by the operational FEATHERS activity based model for Flanders (Belgium).

Emerging large-scale monitoring applications rely on continuous tracking of complex data-analysis queries over collections of massive, physically-distributed data streams. Thus, in addition to the space- and time-efficiency requirements of conventional stream processing (at each remote monitor site), effective solutions also need to guarantee communication efficiency (over the underlying communication network). The complexity of the monitored query adds to the difficulty of the problem --- this is especially true for non-linear queries (e.g., joins), where no obvious solutions exist for distributing the monitored condition across sites. The recently proposed geometric method, based on the notion of covering spheres, offers a generic methodology for splitting an arbitrary (non-linear) global condition into a collection of local site constraints, and has been applied to massive distributed stream-monitoring tasks, achieving state-of-the-art performance. In this paper, we present a far more general geometric approach, based on the convex decomposition of an appropriate subset of the domain of the monitoring query, and formally prove that it is always guaranteed to perform at least as good as the covering spheres method. We analyze our approach and demonstrate its effectiveness for the important case of sketch-based approximate tracking for norm, range-aggregate, and join-aggregate queries , which have numerous applications in streaming data analysis. Experimental results on real-life data streams verify the superiority of our approach in practical settings, showing that it substantially outperforms the covering spheres method.

Modern scale-out services are comprised of thousands of individual machines, which must be continuously monitored for unexpected failures. One recent approach to monitoring is latent fault detection, an adaptive statistical framework for scale-out, load-balanced systems. By periodically measuring hundreds of performance metrics and looking for outlier machines, it attempts to detect subtle problems such as misconfigurations, bugs, and malfunctioning hardware, before they manifest as machine failures. Previous work on a large, real-world Web service has shown that many failures are indeed preceded by such latent faults. Latent fault detection is an offline framework with large bandwidth and processing requirements. Each machine must send all its measurements to a centralized location, which is prohibitive in some settings and requires data-parallel processing infrastructure. In this work we adapt the latent fault detector to provide an online, communication- and computation-reduced version. We utilize stream processing techniques to trade accuracy for communication and computation. We first describe a novel communication-efficient online distributed variance monitoring algorithm that provides a continuous estimate of the global variance within guaranteed approximation bounds. Using the variance monitor, we provide an online distributed outlier detection framework for non-stationary multivariate time series common in scale-out systems. The adapted framework reduces data size and central processing cost by processing the data in situ, making it usable in wider settings. Like the original framework, our adaptation admits different comparison functions, supports non-stationary data, and provides statistical guarantees on the rate of false positives. Simulations on logs from a production system show that we are able to reduce bandwidth by an order of magnitude, with below 1% error compared to the original algorithm.

Interest in stream monitoring is shifting toward the distributed case. In many applications the data is high volume, dynamic, and distributed, making it infeasible to collect the distinct streams to a central node for processing. Often, the monitoring problem consists of determining whether the value of a global function, defined on the union of all streams, crossed a certain threshold. We wish to reduce communication by transforming the global monitoring to the testing of local constraints, checked independently at the nodes. Geometric monitoring (GM) proved useful for constructing such local constraints for general functions. Alas, in GM the constraints at all nodes share an identical structure and are thus unsuitable for handling heterogeneous streams. Therefore, we propose a general approach for monitoring heterogeneous streams (HGM), which defines constraints tailored to fit the data distributions at the nodes. While we prove that optimally selecting the constraints is NP-hard, we provide a practical solution, which reduces the running time by hierarchically clustering nodes with similar data distributions and then solving simpler optimization problems. We also present a method for efficiently recovering from local violations at the nodes. Experiments yield an improvement of over an order of magnitude in communication relative to GM.

Emerging large-scale monitoring applications rely on continuous tracking of complex data-analysis queries over collections of massive, physically-distributed data streams. Thus, in addition to the space- and time-efficiency requirements of conventional stream processing (at each remote monitor site), effective solutions also need to guarantee communication efficiency (over the underlying communication network). The complexity of the monitored query adds to the difficulty of the problem -- this is especially true for nonlinear queries (e.g., joins), where no obvious solutions exist for distributing the monitor condition across sites. The recently proposed geometric method offers a generic methodology for splitting an arbitrary (non-linear) global threshold-monitoring task into a collection of local site constraints; still, the approach relies on maintaining the complete stream(s) at each site, thus raising serious efficiency concerns for massive data streams. In this paper, we propose novel algorithms for efficiently tracking a broad class of complex aggregate queries in such distributed-streams settings. Our tracking schemes rely on a novel combination of the geometric method with compact sketch summaries of local data streams, and maintain approximate answers with provable error guarantees, while optimizing space and processing costs at each remote site and communication cost across the network. One of our key technical insights for the effective use of the geometric method lies in exploiting a much lower-dimensional space for monitoring the sketch-based estimation query. Due to the complex, highly nonlinear nature of these estimates, efficiently monitoring the local geometric constraints poses challenging algorithmic issues for which we propose novel solutions. Experimental results on real-life data streams verify the effectiveness of our approach.

Planar shape interpolation is widely used in computer graphics applications. Despite a wealth of interpolation methods, there is currently no approach that produces shapes with a bounded amount of distortion with respect to the input. As a result, existing interpolation methods may produce shapes that are significantly different than the input and can suffer from fold-overs and other visual artifacts, making them less useful in many practical scenarios. We introduce a novel shape interpolation scheme designed specifically to produce results with a bounded amount of conformal (angular) distortion. Our method is based on an elegant continuous mathematical formulation and provides several appealing properties such as existence and uniqueness of the solution as well as smoothness in space and time domains. We further present a discretization and an efficient practical algorithm to compute the interpolant and demonstrate its usability and good convergence behavior on a wide variety of input shapes. The method is simple to implement and understand. We compare our method to state-of-the-art interpolation methods and demonstrate its superiority in various cases.

The goal of this paper is to solve the following basic problem: Given discrete noisy samples from a continuous signal, compute the probability distribution of its distance from a fixed template. As opposed to the typical restoration problem, which considers a single optimal signal, the computation of the entire probability distribution necessitates integrating over the entire signal space. To achieve this, we apply path integration techniques. The problem is studied in one and two dimensions, and an accurate solution as well as an efficient approximation scheme are provided.

An important problem in distributed, dynamic databases is to continuously monitor the value of a function defined on the nodes, and check that it satisfies some threshold constraint. We introduce a monitoring method, based on a geometric interpretation of the problem, which enables to define local constraints at the nodes. It is guaranteed that as long as none of these constraints is violated, the value of the function did not cross the threshold. We generalize previous work on geometric monitoring, and solve two problems which seriously hampered its performance: as opposed to the constraints used so far, which depend only on the current values of the local data, here we incorporate their temporal behavior. Also, the new constraints are tailored to the geometric properties of the specific monitored function. In addition, we extend the concept of safe zones for the monitoring problem, and show that previous work on geometric monitoring is a special case of the proposed extension. Experimental results on real data reveal that the new approach reduces communication by up to three orders of magnitude in comparison to existing approaches, and considerably narrows the gap between achievable results and a newly defined lower bound on communication complexity.

Property testing is a rapidly growing field of research. Typically, a property testing algorithm proceeds by quickly determining whether an input can satisfy some condition, under the assumption that most inputs do not satisfy it. If the input is "far" from satisfying the condition, the algorithm is guaranteed to reject it with high probability. Applying this paradigm to image detection is desirable since images are large objects and a lot of time can be saved by quickly rejecting images which are "far" from satisfying a certain condition the user is interested in. Further, typically most inputs are, indeed, "far" from the sought images. We demonstrate this by analyzing the problem of deciding whether a binary image can be partitioned according to a template represented by a rectangular grid, and introduce a quick "rejector," which tests an image extracted from the input image, but whose size, as well as the time required to construct it, are constants which are independent of the input image size. With high probability, the rejector dismisses the inputs which are "far" from the template.

Abstract We define a generalized distance function on an unoriented 3D point set and describe how it may be used to reconstruct a surface approximating these points. This distance function is shown to be a Mahalanobis distance in a higher‐dimensional embedding space of the points, and the resulting reconstruction algorithm a natural extension of the classical Radial Basis Function (RBF) approach. Experimental results show the superiority of our reconstruction algorithm to RBF and other methods in a variety of practical scenarios.

The goal of athreshold queryis to detect all objects whose score exceeds a given threshold. This type of query is used in many settings, such as data mining, event triggering, and top-kselection. Often, threshold queries are performed overdistributed data. Given database relations that are distributed over many nodes, an object's score is computed by aggregating the value of each attribute, applying a given scoring function over the aggregation, and thresholding the function's value. However, joining all the distributed relations to a central database might incur prohibitive overheads in bandwidth, CPU, and storage accesses. Efficient algorithms required to reduce these costs exist only for monotonic aggregation threshold queries and certain specific scoring functions. We present a novel approach for efficiently performing general distributed threshold queries. To the best of our knowledge, this is the first solution to the problem of performing such queries with general scoring functions. We first present a solution for monotonic functions, and then introduce a technique to solve for other functions by representing them as a difference of monotonic functions. Experiments with real-world data demonstrate the method's effectiveness in achieving low communication and access costs.

A fundamental problem in distributed computation is the distributed evaluation of functions. The goal is to determine the value of a function over a set of distributed inputs, in a communication efficient manner. Specifically, we assume that each node holds a time varying input vector, and we are interested in determining, at any given time, whether the value of an arbitrary function on the average of these vectors crosses a predetermined threshold.

An important class of queries over sensor networks are network-wide aggregation queries. In this work we study a class of aggregation queries which we refer to as aggregate threshold queries. The goal of an aggregate threshold query is to continuously monitor the network and give a notification every time an aggregated value crosses a predetermined threshold value. Aggregate threshold queries are of particular importance in a wireless sensor environment, since they allow network-wide events to be detected, with a minimum expenditure of energy. Such network-wide events might include, for example, the variance in sensor readings exceeding a certain threshold. We present an efficient algorithm for implementing arbitrary aggregate threshold queries over sensor networks. Our algorithm is based on a novel geometric approach by which an arbitrary aggregate threshold query can be split into a set of numerical constraints on the readings of the individual sensors. These constraints are used by the individual sensors to monitor their readings. The constraints are constructed so that as long as none of the constraints are violated, it is guaranteed that the aggregated value has not crossed the threshold. Experiments we performed on real-world data indicate that by employing these constraints, sensors are able to reduce the number of transmissions required for implementing the query by orders of magnitude, thus significantly reducing energy consumption.

Monitoring data streams in a distributed system is the focus of much research in recent years. Most of the proposed schemes, however, deal with monitoring simple aggregated values, such as the frequency of appearance of items in the streams. More involved challenges, such as the important task of feature selection (e.g., by monitoring the information gain of various features), still require very high communication overhead using naive, centralized algorithms. We present a novel geometric approach which reduces monitoring the value of a function (vis-à-vis a threshold) to a set of constraints applied locally on each of the streams. The constraints are used to locally filter out data increments that do not affect the monitoring outcome, thus avoiding unnecessary communication. As a result, our approach enables monitoring of arbitrary threshold functions over distributed data streams in an efficient manner. We present experimental results on real-world data which demonstrate that our algorithms are highly scalable, and considerably reduce communication load in comparison to centralized algorithms.

In this paper we discuss object detection when only a small number of training examples are given. Specifically, we show how to incorporate a simple prior on the distribution of natural images into support vector machines. SVMs are known to be robust to overfitting; however, a few training examples usually do not represent well the structure of the class. Thus the resulting detectors are not robust and highly depend on the choice of the training examples. We incorporate the prior on natural images by requiring that the separating hyperplane will not only yield a wide margin, but also that the corresponding positive half space will have a low probability to contain natural images (the background). Our experiments on real data sets show that the resulting detector is more robust to the choice of training examples, and substantially improves both linear and kernel SVMwhen trained on 10 positive and 10 negative examples.

This paper offers a path planning algorithm based on splines. The sought path avoids the obstacles, and is smooth and short. Smoothing is used as an integral part of the algorithm, and not only as a final improvement to a path found by other methods. In order to avoid a very difficult optimization over all the path's points, it is modeled by a sequence of splines defined by a gradually increasing number of knots

Monitoring data streams in a distributed system is the focus of much research in recent years. Most of the proposed schemes, however, deal with monitoring simple aggregated values, such as the frequency of appearance of items in the streams. More involved challenges, such as the important task of feature selection (e.g., by monitoring the information gain of various features), still require very high communication overhead using naive, centralized algorithms. We present a novel geometric approach by which an arbitrary global monitoring task can be split into a set of constraints applied locally on each of the streams. The constraints are used to locally filter out data increments that do not affect the monitoring outcome, thus avoiding unnecessary communication. As a result, our approach enables monitoring of arbitrary threshold functions over distributed data streams in an efficient manner. We present experimental results on real-world data which demonstrate that our algorithms are highly scalable, and considerably reduce communication load in comparison to centralized algorithms.

This paper suggests a new measure of symmetry for bifurcating structures, which relies not only on topology and ordering, but also on quantitative properties (e.g. length of branches). This measure is based on the amount of energy required to symmetrize the structure, hence is especially suitable to biological structures. It is tested by its ability to differentiate between two classes of leaves.

Classification based on decision trees is one of the important problems in data mining and has applications in many fields. In recent years, database systems have become highly distributed, and distributed system paradigms such as federated and peer-to-peer databases are being adopted. In this paper, we consider the problem of inducing decision trees in a large distributed network of high dimensional databases. Our work is motivated by the existence of distributed databases in healthcare and in bioinformatics, and by the vision that these database are soon to contain large amounts of genomic data, characterized by its high dimensionality. Current decision tree algorithms would require high communication bandwidth when executed on such data, which is not likely to exist in large-scale distributed systems. We present an algorithm that sharply reduces the communication overhead by sending just a fraction of the statistical data. A fraction which is nevertheless sufficient to derive the exact same decision tree learned by a sequential learner on all the data in the network. Extensive experiments using standard synthetic SNP data show that the algorithm utilizes the high dependency among attributes, typical to genomic data, to reduce communication overhead by up to 99%. Scalability tests show that the algorithm scales well with both the size of the dataset, the dimensionality of the data, and the size of the distributed system.

Classification based on decision trees is one of the important problems in data mining and has applications in many fields. In recent years, database systems have become highly distributed, and distributed system paradigms, such as federated and peer-to-peer databases, are being adopted. In this paper, we consider the problem of inducing decision trees in a large distributed network of genomic databases. Our work is motivated by the existence of distributed databases in healthcare and in bioinformatics, and by the emergence of systems which automatically analyze these databases, and by the expectancy that these databases will soon contain large amounts of highly dimensional genomic data. Current decision tree algorithms require high communication bandwidth when executed on such data, which are large-scale distributed systems. We present an algorithm that sharply reduces the communication overhead by sending just a fraction of the statistical data. A fraction which is nevertheless sufficient to derive the exact same decision tree learned by a sequential learner on all the data-in the network. Extensive experiments using standard synthetic SNP data show that the algorithm utilizes the high dependency among attributes, typical to genomic data, to reduce communication overhead by up to 99 percent. Scalability tests show that the algorithm scales well with both the size of the data set, the dimensionality of the data, and the size of the distributed system.

This paper offers a natural extension of the newly introduced "anti-face" method to event detection, in both the gray-level and feature domains. For the gray-level domain, spatio-temporal templates are created by stacking the individual frames of the video sequence, and the detection is performed on these templates. In order to recognize the motion of features in a video sequence, the spatial locations of the features are modulated in time, thus creating a one-dimensional vector which represents the event in the detection process. The following applications are presented: 1) detection of an object under three-dimensional (3-D) rotations in a video sequence simulated from the COIL database; 2) visual recognition of spoken words; and 3) recognition of two-dimensional and 3-D sketched curves. The technique is capable of detecting 3-D curves in viewing directions which substantially differ from those in the training set. The resulting detection algorithm is very fast and can successfully detect events even in very low resolution. Also, it is capable of discriminating the desired event from arbitrary events, and not only from those in a negative training set. Possible applications of the techniques offered in this paper are in man-machine interaction, surveillance, and search and summarization in video databases.

The introduction of the joint image manifold allows to treat the problem of recovering camera motion and epipolar geometry as the problem of fitting a manifold to the data measured in a stereo pair. The manifold has a singularity and boundary, therefore care must be taken when fitting it. This paper reviews the notion of joint image manifold, and how previous motion recovery methods can be viewed in its context, and then offers a new fitting method, which improves upon previous results, especially when the extent of the data and/or the motion are small.

This paper presents a natural extension of the newly introduced "anti-face" method to event detection, both in the image and in the feature domains. In the case of the image domain (video sequences) we create spatio temporal templates by stacking the video frames, and the detection is performed on these templates. In order to recognize the motion of features in a video sequence, the spatial locations of the features are modulated in time, thus creating a one-dimensional vector which re resents the event The following applications of anti-sequences are presented 1) Detection of an object under 3D rotations in a video sequence simulated from the COIL database, 2) Visual speech recognition of spoken words, and 3) Recognition of symbols sketched with a laser pointer. The resulting detection algorithm is very fast, and is robust enough to work on small images. Also, it is capable of discriminating the desired event-template from arbitrary events, and not only events in a "negative training set".

This paper focuses on the detection of objects with Lambertian surface under both varying illumination and pose. We offer to apply a novel detection method that proceeds by modeling the different illuminations from a small number of images in the training set; this automatically voids the illumination effects, allowing fast illumination invariant detection, without having to create a large training set. It is demonstrated that the method "fits in" nicely with previous work about the modeling of the set of object appearances under varying illumination. In the experiments, an object was correctly detected under image plane rotations in a 15-degrees range, and a wide variety of different illuminations.

This paper offers a novel detection method, which works well even in the case of a complicated image collection. It can also be applied to detect 3D objects under different views. The detection problem is solved by sequentially applying very simple filters (or detectors), which are designed to yield small results on the multitemplate (hence antifaces), and large results on "random" natural images. This is achieved by making use of a simple probabilistic assumption on the distribution of natural images, which is borne out well in practice. Only images which passed the threshold test imposed by the first detector are examined by the second detector, etc. The detectors are designed to act independently so that their false alarms are uncorrelated; this results in a false alarm rate which decreases exponentially in the number of detectors. The algorithm's performance compares favorably to the well-known eigenface and support vector machine based algorithms, but is substantially faster.

We present a simple paradigm for fitting models, parametric and nonparametric, to noisy data, which resolves some of the problems associated with classical MSE algorithms. This is done by considering each point on the model as a possible source for each data point. The paradigm can be used to solve problems which are ill-posed in the classical MSE approach, such as fitting a segment (as opposed to a line). It is shown to be nonbiased and to achieve excellent results for general curves, even in the presence of strong discontinuities. Results are shown for a number of fitting problems, including lines, circles, elliptic arcs, segments, rectangles, and general curves, contaminated by Gaussian and uniform noise.

We offer a simple paradigm for fitting models, parametric and non-parametric, to noisy data, which resolves some of the problems associated with classic MSE algorithms. This is done by considering each point on the model as a possible source for each data point. The paradigm also allows to solve problems which are not defined in the classical MSE approach, such as fitting a segment (as opposed to a line). It is shown to be non-biased, and to achieve excellent results for general curves, even in the presence of strong discontinuities. Results are shown for a number of fitting problems, including lines, circles, segments, and general curves, contaminated by Gaussian and uniform noise.

A problem which often arises while fitting implicit polynomials to 2D and 3D data sets is the following: although the data set is simple, the fit exhibits undesired phenomena, such as loops, holes, extraneous components, etc. Previous work tackled these problems by optimizing heuristic cost functions, which penalize some of these topological problems in the fit. The paper suggests a different approach-to design parameterized families of polynomials whose zero-sets are guaranteed to satisfy certain topological properties. Namely, we construct families of polynomials with star-shaped zero-sets, as well as polynomials whose zero-sets are guaranteed not to intersect an ellipse circumscribing the data or to be entirely contained in such an ellipse. This is more rigorous than using heuristics which may fail and result in pathological zero-sets. The ability to parameterize these families depends heavily on the ability to parameterize positive polynomials. To achieve this, we use some powerful results from real algebraic geometry.

A general paradigm for recognizing 3D objects is offered, and applied to some geometric primitives (spheres, cylinders, cones, and tori). The assumption is that a curve on the surface was measured with high accuracy (for instance, by a sensory robot). Differential invariants of the curve in one method and differential properties of curves and surfaces in the other are then used to recognize the surface. The motivation is twofold: the output of some devices is not surface range data, but such curves. So, surface invariants, which may be simpler in some cases, cannot always be obtained. Also, a considerable speedup is obtained by using curve data, as opposed to surface data which usually contains a much higher number of points.

We treat the use of more complex higher degree polynomial curves and surfaces of degree higher than 2, which have many desirable properties for object recognition and position estimation, and attack the instability problem arising in their use with partial and noisy data. The scenario discussed in this paper is one where we have a set of objects that are modeled as implicit polynomial functions, or a set of representations of classes of objects with each object in a class modeled as an implicit polynomial function, stored in the database. Then, given partial data from one of the objects, we want to recognize the object (or the object class) or collect more data in order to get better parameter estimates for more reliable recognition. Two problems arising in this scenario are discussed: 1) the problem of recognizing these polynomials by comparing them in terms of their coefficients; and 2) the problem of where to collect data so as to improve the parameter estimates as quickly as possible. We use an asymptotic Bayesian approximation for solving the two problems. The intrinsic dimensionality of polynomials and the use of the Mahalanobis distance are discussed.

An effective approach has appeared in the literature for recognizing a 2D curve or 3D surface objects of modest complexity based on representing an object by a single implicit polynomial of 3/sup rd/ or 4/sup th/ degree, computing a vector of Euclidean or affine invariants which are functions of the polynomial coefficients, followed by Bayesian object recognition of the invariants, thus producing a low computational cost robust recognition. This paper extends the approach, as well as an initial work on mutual invariants recognizers, to the recognition of objects too complicated to be represented by a single polynomial. Hence, an object to be recognized is partitioned into patches, each patch is represented by a single implicit polynomial, mutual invariants are computed for pairs of polynomials for pairs of patches, and the object recognition is via a Bayesian recognition of vectors of self and mutual invariants. We discuss why the complete object geometry can be captured by the geometry of pairs of patches, how to design mutual invariants, and how to match patches in the data with those in the database at a low computational cost. The approach is a low computational cost recognition of partially occluded articulated objects in an arbitrary position and in noise by recognizing the self or joint geometry of one or more patches.

This paper treats some of the problem in recognizing the geometry of objects composed of groups of curves that undergo arbitrary affine transformations, providing the objects can be invariantly segmented into groups of curves representable by third degree implicit polynomials. As an illustrative example, the authors treat the problem of representing and recognizing portions of roads in aerial images. The approach the authors develop is to represent each road segment in a disc by a third degree implicit-polynomial, and recognition of road geometry is then Bayesian recognition of a vector of mutual algebraic invariants for the polynomials within such a disc. The mutual affine invariants developed and used are for pairs of polynomials. This is a new powerful approach to dealing with the recognition of complex curves.

Regularization looks for an interpolating function which is close to the data and also "smooth". This function is obtained by minimizing an error functional which is the weighted sum of a "fidelity term" and a "smoothness term". However, using only one set of weights does not guarantee that this function will be the MAP estimate. One has to consider all possible weights in order to find the MAP function. Also, using only one combination of weights makes the algorithm very sensitive to the data. The solution suggested here is through the Bayesian approach: a probability distribution over all weights is constructed and all weights are considered when reconstructing the function or computing the expectation of a linear functional on the function space.

Implicit polynomials have proved themselves as having excellent representation power for complicated objects, and there is growing use of them in computer vision, graphics, and CAD. A must for every system that tries to recognize objects based on their representation by implicit polynomials are invariants, which are quantities assigned to polynomials that do not change under coordinate transformations. In the recognition system developed at the Laboratory for Engineering Man-Machine Studies in Brown University (LEMS), it became necessary to use invariants which are explicit and simple functions of the polynomial coefficients. A method to find such invariants is described and the new invariants presented. This work addresses only the problem of finding the invariants; their stability is studied in another paper.>

This paper introduces and focuses on two problems. First is the representation power of closed implicit polynomials of modest degree for curves in 2-D images and surfaces in 3-D range data. Super quadrics are a small subset of object boundaries that are well fitted by these polynomials. The second problem is the stable computationally efficient fitting of noisy data by closed implicit polynomial curves and surfaces. The attractive features of these polynomials for Vision is discussed.>

The problem addressed is the matching of corresponding regions in two images, even when the image intensity may be smoothly varying without distinctive edges. Corresponding small regions are assumed to be related by affine transformations. The matching is done by using a new class of low computational cost affine invariants. This approach also computes the affine transformation, and is ideal for applications to 3-D motion estimation and 3-D surface reconstruction, image alignment, etc. No feature extraction, segmentation or epipolar constraint is required. The advantage of the authors' approach over area matching is that it handles large baselines, i.e., the distance between camera positions, where the differences in orientation and linear distortion of two areas being compared is large.>

The authors present a robust low-computational-cost system for recognizing freeform objects in 3-D range data or in 2-D curve data in the image plane. Objects are represented by implicit polynomials, i.e., 3-D algebraic surfaces or 2-D algebraic curves of degrees greater than two, and are recognized by computing and matching vectors of their algebraic invariants, which are functions of their coefficients that are invariant to translations, rotations, and general linear transformations. Implicit polynomials of fourth degree can represent complicated asymmetric free-form shapes. A design of Bayesian recognizers for these models and their invariants that results in low-computational-cost recognizers robust to noise, partial occlusion, and other perturbations of the data sets is considered. This work extends the work of D. Keren et al. (1992) by developing and using new invariants for 3-D surface polynomials and applying the Bayesian recognizer to operating on invariants.>

In order to use interpolated data wisely, it is important to have reliability and confidence measures associated with it. A method for computing the reliability at each point of any linear functional of a surface reconstructed using regularization is presented. The proposed method is to define a probability structure on the class of possible objects and compute the variance of the corresponding random variable. This variance is a natural measure for uncertainty, and experiments have shown it to correlate well with reality. The probability distribution used is based on the Boltzmann distribution. The theoretical part of the work utilizes tools from classical analysis, functional analysis, and measure theory on function spaces. The theory was tested and applied to real depth images. It was also applied to formalize a paradigm of optimal sampling, which was successfully tested on real depth images.>

Two problems pertinent to using implicit higher degree polynomials in real-world robust systems are dealt with: (1) characterization and fitting algorithms for the subset of these algebraic curves and surfaces that is bounded and exists largely in the vicinity of the data; (2) a Mahalanobis distance for comparing the coefficients of two polynomials, to determine whether the curves or surfaces that they represent are close over a specified region. These tools make practical use of geometric invariants for determining whether one implicit polynomial curve or surface is a rotation, translation, or an affine transformation of another. The approach is ideally suited to smooth curves and smooth curved surfaces that do not have detectable features.>

A digitized waveform is approximated by segments whose total description length is minimal for a given error bound. This approximation can be computed efficiently and can be used for segmentation. Some applications involving the use of one-dimensional methods to segment two-dimensional gray-scale and range images are shown.>

Regularization has become an important tool for solving many ill-posed problems in approximation theory-for example, in computer vision-including surface reconstruction, optical flow, and shape from shading. The authors attempt to determine whether the approach taken in regularization is always the correct one, and to what extent the results of regularization are reliable. They consider as an example a case in which regularization has been used to reconstruct a surface from sparse data, and attempt to determine how strongly the height of the surface at a certain point can be relied upon. These questions are answered by defining a probability distribution on the class of surfaces considered, and computing its expectation and variance. The variance can be used, for instance, to construct a safety strip around the interpolated surface that should not be entered if collision with the surface is to be avoided.>