Dimensionality reduction is a fundamental task that aims to simplify complex data by reducing its feature dimensionality while preserving essential patterns, with core applications in data analysis and visualisation. To preserve the underlying data structure, multi-dimensional scaling (MDS) methods focus on preserving pairwise dissimilarities, such as distances. They optimise the embedding to have pairwise distances as close as possible to the data dissimilarities. However, the current standard is limited to embedding data in Riemannian manifolds. Motivated by the lack of asymmetry in the Riemannian metric of the embedding space, this paper extends the MDS problem to a natural asymmetric generalisation of Riemannian manifolds called Finsler manifolds. Inspired by Euclidean space, we define a canonical Finsler space for embedding asymmetric data. Due to its simplicity with respect to geodesics, data representation in this space is both intuitive and simple to analyse. We demonstrate that our generalisation benefits from the same theoretical convergence guarantees. We reveal the effectiveness of our Finsler embedding across various types of non-symmetric data, highlighting its value in applications such as data visualisation, dimensionality reduction, directed graph embedding, and link prediction.

Deep learning approaches to generic (non-semantic) segmentation have so far been indirect and relied on edge detection. This is in contrast to semantic segmentation, where DNNs are applied directly. We propose an alternative approach called Deep Generic Segmentation (DGS) and try to follow the path used for semantic segmentation. Our main contribution is a new method for learning a pixel-wise representation that reflects segment relatedness. This representation is combined with a CRF to yield the segmentation algorithm. We show that we are able to learn meaningful representations that improve segmentation quality and that the representations themselves achieve state-of-the-art segment similarity scores. The segmentation results are competitive and promising.

In contrast to human vision, common recognition algorithms often fail on partially occluded images. We propose characterizing, empirically, the algorithmic limits by finding a minimal recognizable patch (MRP) that is by itself sufficient to recognize the image. A specialized deep network allows us to find the most informative patches of a given size, and serves as an experimental tool. A human vision study recently characterized related (but different) minimally recognizable configurations (MIRCs) [1], for which we specify computational analogues (denoted cMIRCs). The drop in human decision accuracy associated with size reduction of these MIRCs is substantial and sharp. Interestingly, such sharp reductions were also found for the computational versions we specified.

In this paper, we propose a normal estimation method for unstructured 3D point clouds. This method, called Nesti-Net, builds on a new local point cloud representation which consists of multi-scale point statistics (MuPS), estimated on a local coarse Gaussian grid. This representation is a suitable input to a CNN architecture. The normals are estimated using a mixture-of-experts (MoE) architecture, which relies on a data-driven approach for selecting the optimal scale around each point and encourages sub-network specialization. Interesting insights into the network's resource distribution are provided. The scale prediction significantly improves robustness to different noise levels, point density variations and different levels of detail. We achieve state-of-the-art results on a benchmark synthetic dataset and present qualitative results on real scanned scenes.

Convolutional neural networks (CNNs) provide the current state of the art in visual object classification, but they are far less accurate when classifying partially occluded objects. A straightforward way to improve classification under occlusion conditions is to train the classifier using partially occluded object examples. However, training the network on many combinations of object instances and occlusions may be computationally expensive. This work proposes an alternative approach to increasing the robustness of CNNs to occlusion. We start by studying the effect of partial occlusions on the trained CNN and show, empirically, that training on partially occluded examples reduces the spatial support of the filters. Building upon this finding, we argue that smaller filter support is beneficial for occlusion robustness. We propose a training process that uses a special regularization term that acts to shrink the spatial support of the filters. We consider three possible regularization terms that are based on second central moments, group sparsity, and mutually reweighted L1, respectively. When trained on normal (unoccluded) examples, the resulting classifier is highly robust to occlusions. For large training sets and limited training time, the proposed classifier is even more accurate than standard classifiers trained on occluded object examples.

We present a two-step approach for modeling facial variations and class likelihoods over time. Unlike traditional approaches, we explicitly model the temporal domain that is often available, for example, in consumer photos or surveillance systems. Our combined approach draws upon the concepts of manifold transformation and semi-supervised graph-based propagation to simultaneously recognize faces across entire photo collections. Experiments on two datasets demonstrate improved face recognition accuracy.

A methodology for integrating multiple cues for tracking was proposed in several papers. These papers claim that, unlike other methodologies, conditional independence of the cues is not assumed. This brief communication 1) refutes this claim and 2) points out other major problems in the methodology.

In this paper we introduce a novel method that can efficiently estimate a family of hierarchical dense sets in high-dimensional distributions. Our method can be regarded as a natural extension of the one-class SVM (OCSVM) algorithm that finds multiple parallel separating hyperplanes in a reproducing kernel Hilbert space. We call our method q-OCSVM, as it can be used to estimate $q$ quantiles of a high-dimensional distribution. For this purpose, we introduce a new global convex optimization program that finds all estimated sets at once and show that it can be solved efficiently. We prove the correctness of our method and present empirical results that demonstrate its superiority over existing methods.

We propose an efficient, generalized, nonparametric, statistical Kolmogorov-Smirnov test for detecting distributional change in high-dimensional data. To implement the test, we introduce a novel, hierarchical, minimum-volume sets estimator to represent the distributions to be tested. Our work is motivated by the need to detect changes in data streams, and the test is especially efficient in this context. We provide the theoretical foundations of our test and show its superiority over existing methods.

Adaptive sampling schemes choose different sampling masks for different images. Blind adaptive sampling schemes use the measurements that they obtain (without any additional or direct knowledge about the image) to wisely choose the next sample mask. In this paper, we present and discuss two blind adaptive sampling schemes. The first is a general scheme not restricted to a specific class of sampling functions. It is based on an underlying statistical model for the image, which is updated according to the available measurements. A second less general but more practical method uses the wavelet decomposition of an image. It estimates the magnitude of the unsampled wavelet coefficients and samples those with larger estimated magnitude first. Experimental results show the benefits of the proposed blind sampling schemes.

In this work, we recover the 3D shape of mirrors, sunglasses, and stainless steel implements. A computer monitor displays several images of parallel stripes, each image at a different angle. Reflections of these stripes in a mirroring surface are captured by the camera. For every image point, the direction of the displayed stripes and their reflections in the image are related by a 1D homography matrix, computed with a robust version of the statistically accurate heteroscedastic approach. By focusing on a sparse set of image points for which monitor-image correspondence is computed, the depth and the local shape may be estimated from these homographies. The depth estimation relies on statistically correct minimization and provides accurate, reliable results. Even for the image points where the depth estimation process is inherently unstable, we are able to characterize this instability and develop an algorithm to detect and correct it. After correcting the instability, dense surface recovery of mirroring objects is performed using constrained interpolation, which does not simply interpolate the surface depth values but also uses the locally computed 1D homographies to solve for the depth, the correspondence, and the local surface shape. The method was implemented and the shape of several objects was densely recovered at submillimeter accuracy.

Nonnegative matrix factorization (NMF) approximates a given data matrix as a product of two low-rank nonnegative matrices, usually by minimizing the L2 or the KL distance between the data matrix and the matrix product. This factorization was shown to be useful for several important computer vision applications. We propose here two new NMF algorithms that minimize the Earth mover's distance (EMD) error between the data and the matrix product. The algorithms (EMD NMF and bilateral EMD NMF) are iterative and based on linear programming methods. We prove their convergence, discuss their numerical difficulties, and propose efficient approximations. Naturally, the matrices obtained with EMD NMF are different from those obtained with L2-NMF. We discuss these differences in the context of two challenging computer vision tasks, texture classification and face recognition, perform actual NMF-based image segmentation for the first time, and demonstrate the advantages of the new methods with common benchmarks.

Computer vision attention processes assign variable-hypothesized importance to different parts of the visual input and direct the allocation of computational resources. This nonuniform allocation might help accelerate the image analysis process. This paper proposes a new bottom-up attention mechanism. Rather than taking the traditional approach, which tries to model human attention, we propose a validated stochastic model to estimate the probability that an image part is of interest. We refer to this probability as saliency and thus specify saliency in a mathematically well-defined sense. The model quantifies several intuitive observations, such as the greater likelihood of correspondence between visually similar image regions and the likelihood that only a few of interesting objects will be present in the scene. The latter observation, which implies that such objects are (relaxed) global exceptions, replaces the traditional preference for local contrast. The algorithm starts with a rough preattentive segmentation and then uses a graphical model approximation to efficiently reveal which segments are more likely to be of interest. Experiments on natural scenes containing a variety of objects demonstrate the proposed method and show its advantages over previous approaches.

Nonnegative Matrix Factorization (NMF) approximates a given data matrix as a product of two low rank nonnegative matrices, usually by minimizing the L2or the KL distance between the data matrix and the matrix product. This factorization was shown to be useful for several important computer vision applications. We propose here a new NMF algorithm that minimizes the Earth Mover's Distance (EMD) error between the data and the matrix product. We propose an iterative NMF algorithm (EMD NMF) and prove its convergence. The algorithm is based on linear programming. We discuss the numerical difficulties of the EMD NMF and propose an efficient approximation. Naturally, the matrices obtained with EMD NMF are different from those obtained with L2NMF. We discuss these differences in the context of two challenging computer vision tasks - texture classification and face recognition - and demonstrate the advantages of the proposed method.

This paper addresses the “boundary ownership” problem, also known as the figure/ground assignment problem. Estimating boundary ownerships is a key step in perceptual organization: it allows higher-level processing to be applied on non-accidental shapes corresponding to figural regions. Existing methods for estimating the boundary ownerships for a given set of boundary curves model the probability distribution function (PDF) of the binary figure/ground random variables associated with the curves. Instead of modeling this PDF directly, the proposed method uses the 2.1D model: it models the PDF of the ordinal depths of the image segments enclosed by the curves. After this PDF is maximized, the boundary ownership of a curve is determined according to the ordinal depths of the two image segments it abuts. This method has two advantages: first, boundary ownership configurations inconsistent with every depth ordering (and thus very likely to be incorrect) are eliminated from consideration; second, it allows for the integration of cues related to image segments (not necessarily adjacent) in addition to those related to the curves. The proposed method models the PDF as a conditional random field (CRF) conditioned on cues related to the curves, T-junctions, and image segments. The CRF is formulated using learnt non-parametric distributions of the cues. The method significantly improves the currently achieved figure/ground assignment accuracy, with 20.7% fewer errors in the Berkeley Segmentation Dataset.

Kernel-based trackers aggregate image features within the support of a kernel (a mask) regardless of their spatial structure. These trackers spatially fit the kernel (usually in location and in scale) such that a function of the aggregate is optimized. We propose a kernel-based visual tracker that exploits the constancy of color and the presence of color edges along the target boundary. The tracker estimates the best affinity of a spatially aligned pair of kernels, one of which is color-related and the other of which is object boundary-related. In a sense, this work extends previous kernel-based trackers by incorporating the object boundary cue into the tracking process and by allowing the kernels to be affinely transformed instead of only translated and isotropically scaled. These two extensions make for more precise target localization. A more accurately localized target also facilitates safer updating of its reference color model, further enhancing the tracker's robustness. The improved tracking is demonstrated for several challenging image sequences.

We propose an unsupervised method for evaluating image segmentation. Common methods are typically based on evaluating smoothness within segments and contrast between them, and the measure they provide is not explicitly related to segmentation errors. The proposed approach differs from these methods on several important points and has several advantages over them. First, it provides a meaningful, quantitative assessment of segmentation quality, in precision/recall terms, which were applicable so far only for supervised evaluation. Second, it builds on a new image model, which characterizes the segments as a mixture of basic feature distributions. The precision/recall estimates are then obtained by a nonnegative matrix factorization (NMF) process. A third important advantage is that the estimates, which are based on intrinsic properties of the specific image being evaluated and not on a comparison to typical images (learning), are relatively robust to context factors such as image quality or the presence of texture. Experimental results demonstrate the accuracy of the precision/recall estimates in comparison to ground truth based on human judgment. Moreover, it is shown that tuning a segmentation algorithm using the unsupervised measure improves the algorithm's quality (as measured by a supervised method).

Blind sampling is a sampling scheme which uses no knowledge about the image except for the measurements it obtains. An adaptive blind sampling scheme makes use of that knowledge to wisely choose the next sample. In this work we consider generalised sampling, where each measurement is obtained by computing an inner product between the image and some mask. The context of this paper is second order statistical models for images. We discuss the reconstruction of images from arbitrary generalised sampling and present criteria for selecting an optimal mask from a dictionary (family) of masks, or from the set of all possible masks. The latter case leads to PCA. We further propose adaptive sampling schemes that produce different sets of sampling masks for different images, and experimentally verify the advantage of the adaptive schemes over nonadaptive ones.

This paper addresses the problem of visual tracking under very general conditions: a possibly non-rigid target whose appearance may drastically change over time; general camera motion; a 3D scene; and no a priori information except initialization. This is in contrast to the vast majority of trackers which rely on some limited model in which, for example, the target's appearance is known a priori or restricted, the scene is planar, or a pan tilt zoom camera is used. Their goal is to achieve speed and robustness, but their limited context may cause them to fail in the more general case. The proposed tracker works by approximating, in each frame, a PDF (probability distribution function) of the target's bitmap and then estimating the maximum a posteriori bitmap. The PDF is marginalized over all possible motions per pixel, thus avoiding the stage in which optical flow is determined. This is an advantage over other general-context trackers that do not use the motion cue at all or rely on the error-prone calculation of optical flow. Using a Gibbs distribution with respect to the first-order neighborhood system yields a bitmap PDF whose maximization may be transformed into that of a quadratic pseudo-Boolean function, the maximum of which is approximated via a reduction to a maximum-flow problem. Many experiments were conducted to demonstrate that the tracker is able to track under the aforementioned general context.

In this work we recover the 3D shape of mirroring objects such as mirrors, sunglasses, and stainless steel objects. A computer monitor displays several images of parallel stripes, each image at a different angle. Reflections of these stripes in a mirroring surface are captured by the camera. For every image point, the directions of the displayed stripes and their reflections in the image are related by a 1D homography which can be computed robustly and using the statistically accurate heteroscedastic model, without monitor-image correspondence, which is generally required by other techniques. Focusing on a small set of image points for which monitor-image correspondence is computed, the depth and the local shape may be calculated relying on this homography. This is done by an optimization process which is related to the one proposed by Savarese, Chen and Perona, but is different and more stable. Then dense surface recovery is performed using constrained interpolation, which does not simply interpolate the surface depth values, but rather solves for the depth, the correspondence, and the local surface shape, simultaneously at each interpolated point. Consistency with the ID homography is thus required. The proposed method as well as the method described in [A. Ripsman and M. Jenkin, IEEE Int. Symposium on Computational Intelligence (2001)] are inherently unstable on a small part of the surface. We propose a method to detect these instabilities and correct them. The method was implemented and the shapes of a mirror, sunglasses, and a stainless steel ashtray were recovered at sub-millimeter accuracy.

Kernel-based trackers aggregate image features within the support of a kernel (a mask) regardless of their spatial structure. These trackers spatially fit the kernel (usually in location and in scale) such that a function of the aggregate is optimized. We propose a kernel-based visual tracker that exploits the constancy of color and the presence of color edges along the target boundary. The tracker estimates the best affinity of a spatially aligned pair of kernels, one of which is color-related and the other of which is object boundary-related. In a sense, this work extends previous kernel-based trackers by incorporating the object boundary cue into the tracking process and by allowing the kernels to be affinely transformed instead of only translated and isotropically scaled. These two extensions make for more precise target localization. Moreover, a more accurately localized target facilitates safer updating of its reference color model, further enhancing the tracker's robustness. The improved tracking is demonstrated for several challenging image sequences.

We consider the problem of matching images to tell whether they come from the same scene viewed under different lighting conditions. We show that the surface characteristics determine the type of image comparison method that should be used. Previous work has shown the effectiveness of comparing the image gradient direction for surfaces with material properties that change rapidly in one direction. We show analytically that two other widely used methods, normalized correlation of small windows and comparison of multiscale oriented filters, essentially compute the same thing. Then, we show that for surfaces whose properties change more slowly, comparison of the output of whitening filters is most effective. This suggests that a combination of these strategies should be employed to compare general objects. We discuss indications that Gabor jets use such a mixed strategy effectively, and we propose a new mixed strategy. We validate our results on synthetic and real images.

A visual search is required when applying a recognition process on a scene containing multiple objects. In such cases, we would like to avoid an exhaustive sequential search. This work proposes a dynamic visual search framework based mainly on innerscene similarity. Given a number of candidates (e.g., subimages), we hypothesize is that more visually similar candidates are more likely to have the same identity. We use this assumption for determining the order of attention. Both deterministic and stochastic approaches, relying on this hypothesis, are considered. Under the deterministic approach, we suggest a measure similar to Kolmogorov's epsilon-covering that quantifies the difficulty of a search task. We show that this measure bounds the performance of all search algorithms and suggest a simple algorithm that meets this bound. Under the stochastic approach, we model the identity of the candidates as a set of correlated random variables and derive a search procedure based on linear estimation. Several experiments are presented in which the statistical characteristics, search algorithm, and bound are evaluated and verified.

Detecting salient structures is a basic task in perceptual organization. Saliency algorithms typically mark edge-points with some saliency measure, which grows with the length and smoothness of the curve on which these edge-points lie. Here, we propose a modified saliency estimation mechanism that is based on probabilistically specified grouping cues and on curve length distributions. In this framework, the Shashua and Ullman saliency mechanism may be interpreted as a process for detecting the curve with maximal expected length. Generalized types of saliency naturally follow. We propose several specific generalizations (e.g., gray-level-based saliency) and rigorously derive the limitations on generalized saliency types. We then carry out a probabilistic analysis of expected length saliencies. Using ergodicity and asymptotic analysis, we derive the saliency distributions associated with the main curves and with the rest of the image. We then extend this analysis to finite-length curves. Using the derived distributions, we derive the optimal threshold on the saliency for discriminating between figure and background and bound the saliency-based figure-from-ground performance.

Lighting variation is commonly handled by methods invariant to additive and multiplicative changes in image intensity. It has been demonstrated that comparing images using the direction of the gradient can produce broader insensitivity to changes in lighting conditions, even for 3D scenes. We analyze two common approaches to image comparison that are invariant, normalized correlation using small correlation windows, and comparison based on a large set of oriented difference of Gaussian filters. We show analytically that these methods calculate a monotonic (cosine) function of the gradient direction difference and hence are equivalent to the direction of gradient method. Our analysis is supported with experiments on both synthetic and real scenes

The size of five trie-based methods of sorting large collections of line segments in a spatial database is investigated analytically using a random lines image model and geometric probability techniques. The methods are based on sorting the line segments with respect to the space that they occupy. Since the space is two-dimensional, the trie is formed by interleaving the bits corresponding to the binary representation of the x and y coordinates of the underlying space and then testing two bits at each iteration. The result of this formulation yields a class of representations that are referred to as quadtrie variants, although they have been traditionally referred to as quadtree variants. The analysis differs from prior work in that it uses a detailed explicit model of the image instead of relying on modeling the branching process represented by the tree and leaving the underlying image unspecified. The analysis provides analytic expressions and bounds on the expected size of these quadtree variants. This enables the prediction of storage required by the representations and of the associated performance of algorithms that rely on them. The results are useful in the following two ways: They reveal the properties of the various representations and permit their comparison using analytic, nonexperimental criteria. Some of the results confirm previous analyses (e.g., that the storage requirement of the MX quadtree is proportional to the total lengths of the line segments). An important new result is that for a PMR and Bucket PMR quadtree with sufficiently high values of the splitting threshold (i.e., $\geq 4$) the number of nodes is proportional to the number of line segments and is independent of the maximum depth of the tree. This provides a theoretical justification for the good behavior and use of the PMR quadtree, which so far has been only of an empirical nature.The random lines model was found to be general enough to approximate real data in the sense that the properties of the trie representations, when used to store real data (e.g., maps), are similar to their properties when storing random lines data. Therefore, by specifying an equivalent random lines model for a real map, the proposed analytical expressions can be applied to predict the storage required for real data. Specifying the equivalent random lines model requires only an estimate of the effective number of random lines in it. Several such estimates are derived for real images, and the accuracy of the implied predictions is demonstrated on a real collection of maps. The agreement between the predictions and real data suggests that they could serve as the basis of a cost model that can be used by a query optimizer to generate an appropriate query evaluation plan.

Much work has been done in the field of visual object tracking, yielding a wide range of trackers, including ones aimed for multiple objects. In many cases, there may be a coupling between simultaneously tracked objects, e.g., the locations of some person's eyes. In such cases, tracking each object independently, or using any multitarget tracker ignoring this coupling, will be suboptimal. This paper addresses these cases and takes advantage of the coupling between the tracked objects to enhance the tracking performance. An analytically justified, probabilistic framework for cooperating between the individual trackers is suggested. The framework is fairly general, allowing to cooperate between any two trackers which output a probability density function of the tracked state, even when the objects are tracked in different state spaces. The framework is successfully tested on two different kinds of trackers, showing the benefit gained from the coupling exploitation.

THIS issue contains the second installment of the special issue on perceptual organization in computer vision. In the April issue of TPAMI, we published 11 papers addressing basic principles, algorithms, and applications. This month’s papers continue along these lines and raising new issues as well. The first paper in the special section contributes to one of the most significant trends in perceptual organization, the use of graph algorithms to efficiently find regions that globally optimize, or approximately optimize, a grouping property. P. Soundararajan and S. Sarkar present an analysis and experimental evaluation of a set of graph algorithms, showing that some of the common algorithms are practically equivalent with respect to performance. In the next paper, J.H. Elder, A. Krupnik, and L.A. Johnston describe a probabilistic formulation for contour grouping that combines Gestalt grouping cues with prior knowledge about the shape of the objects whose boundary is being detected. They apply this approach to the problem of detecting exact lake boundaries in satellite imagery. S. Wang and J.M. Siskind also study graph algorithms as a grouping mechanism. They present a novel algorithm based on the ratio of two properties of graph edges that are cut in a segmentation. This leads to a polynomial time algorithm that finds globally optimal groupings, which they then enhance using a set of heuristics. Finally, it is fitting that our issue concludes with S.-C. Zhu’s paper, which reviews a large set of past work on modeling visual patterns, an area fundamental to perceptual organization. Professor Zhu presents a broad taxonomy of methods, stressing the importance of generative models in image modeling. The 15 papers we have presented provide a wide range of viewpoints and attack a variety of problems using diverse tools. We find this appropriate since the challenges of perceptual organization are great and many angles on the problem should continue to be explored. Hopefully, the special section will provide a useful snapshot of the state of many of these approaches.

The problem of selecting a camera model is addressed here using the Geometric AIC (Akaike Information Criterion) proposed by Kanatani, which considers both the residual of the data fitting to the model as well as the complexity of the model. Camera models describe the geometrical relation between the 3D location of object points and the image location of their projections. The most commonly used camera models are the projective/perspective camera model and the affine camera model. Intuitively, the projective camera model, which is nonlinear and is characterized by more parameters, models the imaging geometry better, but also, is believed to lead to numerically less stable solutions. The affine camera model, which is an approximation to the projective camera model with less parameters, is recommended to be used when the object depth is much smaller than the object distance. However, there is no quantitative criterion for the decision: which camera model should be used, projective or affine? In this paper, the Geometric AIC criterion is used for deciding between the two camera models is the context of two tasks: estimating the projection matrix from 3D and corresponding 2D data, and estimating the fundamental matrix from two sets of 3D data. It is found that in most cases, it is the projective camera model which is more appropriate. Still, in the cases where the affine camera model is traditionally used, the measures of appropriateness of the two models are roughly the same (with a small advantage to the affine camera model).

The Karhunen-Loeve (KL) transform is an optimal method for approximating a set of vectors or images, which was used in image processing and computer vision for several tasks such as face and object recognition. Its computational demands and its batch calculation nature have limited its application. Here we present a new, sequential algorithm for calculating the KL basis, which is faster in typical applications and is especially advantageous for image sequences: the KL basis calculation is done with much lower delay and allows for dynamic updating of image databases. Systematic tests of the implemented algorithm show that these advantages are indeed obtained with the same accuracy available from batch KL algorithms.

We investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown region. More specifically, we consider robots which leave chemical odour traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multi-agent adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distributed fashion, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. Our algorithms can complete the traversal of the graph even if some of the agents die or the graph changes during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time.

This paper proposes a new, efficient, figure from ground method. At every stage the data features are classified to either "background" or "unknown yet" classes, thus emphasizing the background detection task (and implying the name of the method). The sequential application of such classification stages creates a bootstrap mechanism which improves performance in very cluttered scenes. This method can be applied to many perceptual grouping cues, and an application to smoothness-based classification of edge points is given. A fast implementation using a kd-tree allows to work on large, realistic images.

We consider a class of control tasks, which rely from partial visual information in a robotic setting. These tasks are hard in the sense that at every given moment, the available information is insufficient for the control task. Still, the amount of information collected throughout the control process is large and thus seems sufficient for carrying out the task. Such situations commonly arise when the object is frequently occluded from one of the cameras in a stereo pair or when only one moving camera is available. We propose a generic control rule for such tasks and characterize the conditions required for the success of the task. The analysis is based on the observation that mathematically, the behavior of such systems is related to a class of row-action (and POCS) optimization algorithms. In the second part of the paper we focus on one particular task from this class: position and orientation control with a single rotating camera. We show that this task may be carried out, in principle, for any camera movement, and suggest efficient control strategy and camera moving strategy. Interestingly, it seems that the advisable control law is not consistent with simple-minded intuition. We substantiate our claims by simulations and experiments on real data.

The Karhunen-Loeve (KL) transform is an optimal method for approximating a set of vectors, which was used in image processing and computer vision for several tasks. Its computational demands and its batch calculation nature have limited its application. Here we present a new, sequential algorithm for calculating the KL basis, which is faster in typical applications and is especially advantageous for image sequences: the KL basis calculation is done with much lower delay and allows for dynamic updating of object databases for recognition. Systematic tests of the implemented algorithm show that these advantages are indeed obtained with the same accuracy available from batch KL algorithms.

Model-based object recognition is a fundamental task of computer vision. In this paper we consider the performance of the popular geometric hashing (GH) algorithm for model based recognition and, in a probabilistic setting, examine the influence of some design decisions and derive several trade-offs between two measures of performance: reliability and time complexity. We also propose a variation of the GH algorithm, which alleviates some of its inherent problems and demonstrate its enhanced performance in experiments.

Describes an image representation, which is built over an edge map. The edges are grouped into straight line segments and properties of these segments are embedded sparsely in a three dimensional space. Specifically, the space is divided into layers, and segments associated with different (quantized) orientations are placed in different layers. Therefore we refer to this representation as a layered representation. This representation induces an implicit correspondence relation between line segments associated with close views of the same object. An induced image-based representation of objects is a collection of image representations corresponding to their different views. Standard subspace-based methods are used to approximate this collection with the Karhunen-Loeve (principal components) technique. Projection of the representation of a new, unfamiliar image onto this subspace is used for recognition and model-based filtering. In contrast to grey-level based subspace methods, this method is highly insensitive to clutter and occlusion.

This paper presents a generic method for perceptual grouping and an analysis of its expected grouping quality. The grouping method is fairly general: It may be used for the grouping of various types of data features, and to incorporate different grouping cues operating over feature sets of different sizes. The proposed method is divided into two parts: constructing a graph representation of the available perceptual grouping evidence, and then finding the "best" partition of the graph into groups. The first stage includes a cue enhancement procedure, which integrates the information available from multifeature cues into very reliable bifeature cues. Both stages are implemented using known statistical tools such as Wald's SPRT algorithm (1952) and the maximum likelihood criterion. The accompanying theoretical analysis of this grouping criterion quantifies intuitive expectations and predicts that the expected grouping quality increases with cue reliability. It also shows that investing more computational effort in the grouping algorithm leads to better grouping results. This analysis, which quantifies the grouping power of the maximum likelihood criterion, is independent of the grouping domain. To our best knowledge, such an analysis of a grouping process is given here for the first time. Three grouping algorithms, in three different domains, are synthesized as instances of the generic method. They demonstrate the applicability and generality of this grouping method.

Verification is the final decision stage in many object recognition processes. It is carried out by evaluating a score for every hypothesis and choosing the hypotheses associated with the highest score. This paper suggests a grouping-based verification paradigm, relying on the observation that a group of data features belonging to a hypothesized object instance should be a "good group". Therefore, it should support perceptual grouping information available from the image by grouping relations. The proposed score, which is the joint likelihood of these grouping cues, quantifies this observation in a probabilistic framework. Experiments with synthetic and real images show that the proposed method performs better in difficult cases.

Many recognition procedures rely on the consistency of a subset of data features with a hypothesis as the sufficient evidence to the presence of the corresponding object. We analyze here the performance of such procedures, using a probabilistic model, and provide expressions for the sufficient size of such data subsets, that, if consistent, guarantee the validity of the hypotheses with arbitrary confidence. We focus on 2D objects and the affine transformation class, and provide, for the first time, an integrated model which takes into account the shape of the objects involved, the accuracy of the data collected, the clutter present in the scene, the class of the transformations involved, the accuracy of the localization, and the confidence we would like to have in our hypotheses. Increasingly, it turns out that most of these factors can be quantified cumulatively by one parameter, denoted "effective similarity", which largely determines the sufficient subset size. The analysis is based on representing the class of instances corresponding to a model object and a group of transformations, as members of a metric space, and quantifying the variation of the instances by a metric cover.

A new method of farthest point strategy (FPS) for progressive image acquisition-an acquisition process that enables an approximation of the whole image at each sampling stage-is presented. Its main advantage is in retaining its uniformity with the increased density, providing efficient means for sparse image sampling and display. In contrast to previously presented stochastic approaches, the FPS guarantees the uniformity in a deterministic min-max sense. Within this uniformity criterion, the sampling points are irregularly spaced, exhibiting anti-aliasing properties comparable to those characteristic of the best available method (Poisson disk). A straightforward modification of the FPS yields an image-dependent adaptive sampling scheme. An efficient O(N log N) algorithm for both versions is introduced, and several applications of the FPS are discussed.

The departments of electrical engineering and computer science at Technion offer a broad spectrum of courses in digital and optical signals and imaging systems, and a research environment most suitable for specialization in image system engineering. We describe a few of the courses and discuss some issues related to their teaching.

We propose a technique for predicting the number of features that should be extracted from an image to guarantee reliable recognition in various feature-based recognition tasks. Our technique relies on the tools from learning theory, namely, the PAC learning framework and VC-dimension analysis. We derive the upper bounds on the required number of feature measurements for recognition tasks over the affine transformation space. These derivations can be readily applied to less general transformations. According to our predictions, more feature measurements are required for successful recognition when the objects involved are similar and when the hypothesized objects are complex. We present experimental results that qualitatively confirm these predictions.

A space-filling curve is a linear traversal of a discrete finite multidimensional space. In order for this traversal to be useful in many applications, the curve should preserve "locality". We quantify "locality" and bound the locality of multidimensional space-filling curves. Classic Hilbert space-filling curves come close to achieving optimal locality.

The localization and the recognition tasks are analyzed here relying on a probabilistic model, and independently of the recognition method used. Rigorous upper and lower bounds on the probability that a set of measurements is sufficient to localize an object within a certain precision, are derived. The bounds quantify the difficulty of the localization task regarding many of its aspects, including the number of measurements, the uncertainty in their position, the information they reveal, and the "ability of the objects to confuse the recognizer". Similar results are obtained for the recognition task. The asymptotic difficulty of recognition/localization tasks is characterized by a single parameter, thus making it possible to compare between different tasks. The bounds provide a theoretical benchmark to which experimentally measured performance of localization/recognition methods can be compared.>

Finding eigenvectors of a sequence of real images has usually been considered to require too much computation to be practical. Our spatial temporal adaptive (STA) method reduces the computational complexity of the approximate partial eigenvalue decomposition based on image encoding. Spatial temporal encoding is used to reduce storage and computation, and then, singular value decomposition (SVD) is applied. After the adaptive discrete cosine transform (DCT) encoding, blocks that are similar in consecutive images are consolidated. The computational economy of our method was verified by tests on different large sets of images. The results show that this method is 6 to 10 times faster than the traditional SVD method for several kinds of real images. The economy of this algorithm increases with increasing correlation within the image and with increasing correlation between consecutive images within a set. This algorithm is useful for pattern recognition using eigenvectors, which is a research field that has been active recently.

A new method of "farthest point strategy" (FPS) for progressive image acquisition is presented. Its main advantage is in retaining its uniformity with the increased density, providing an efficient means for sparse image sampling and display. In contrast to previously presented stochastic approaches, the FPS guarantees the uniformity in a deterministic min-max sense. Within this uniformity criterion, the sampling points are irregularly spaced, exhibiting superior antialiasing properties. A straightforward modification of the FPS yields an image-dependent adaptive sampling scheme. An efficient, O(N log(N)), algorithm for both versions is introduced, and several applications of the FPS are discussed.

Discrete space-filling curves are commonly used to reduce a multidimensional problem to a one-dimensional problem, and, as such, are exploited in a variety of image processing applications. The space-filling curve is essentially a linear traversal of the discrete multidimensional space. In order that this traversal be effective, the curve should preserve "locality", namely, that points close in the original multidimensional space be close in their ordering along the curve, and vice versa. We quantify "locality" and provide upper and lower bounds on the locality of multidimensional space-filling curves. We also bound the locality of the classic Hilbert space-filling curves, showing that they come close to achieving optimal locality.

Many recognition procedures rely on the consistency of a subset of data features with an hypothesis, as the sufficient evidence to the presence of the corresponding object. We analyze here the recognition and localization tasks using a probabilistic model and provide expressions for the sufficient size of such data subsets, that, if consistent, guarantee the validity of the hypotheses with arbitrary confidence. We focus on 2D objects and the affine transformation class, and provide, for the first time, an integrated model, which takes into account the shape of the objects involved, the accuracy of the data collected, the clutter present in the scene, the class of the transformations involved, the accuracy of the localization, and the confidence we would like to have in our hypotheses.

2-D shape boundary segmentation is required as a fundamental and important stage in the recognition of partially occluded objects. We introduce here a new segmentation method capable of extracting a controlled number of segments along a smooth boundary curve. This new approach is invariant to similarity transformation, and partial occlusion has only marginal influence on the segmentation of the visible part. The basic concept is to transform the curve into another one which intersects itself. Points of intersection of the new curve are re-transformed to the original curve and serve as endpoints of segments. Properties of the transform are discussed, and conditions for existence of intersection points are given. Simulation results of gray level images are presented, and advantages of our method over conventional approaches relying on singular points of the curvature are discussed.>

The process of learning the shape of an unknown convex planar object through an adaptive process of simple measurements called line probings, which reveal tangent lines to the object, is considered. A systematic probing strategy is suggested and an upper bound on the number of probings it requires for achieving an approximation with a pre-specified precision to the unknown object is derived. A lower bound on the number of probings required by any strategy for achieving such an approximation is also derived, showing that the gap between the number of probings required by the authors' strategy and the number of probings required by the optimal strategy is a logarithmic factor in the worst case. The proposed approach overcomes deficiencies of the classical geometric probing approach which is based on the polygonality assumption, and thus is not applicable for real robotic tasks.>

How difficult is it to find the position of a known object using random samples?We study this question, which is central to Computer Vision and Robotics, in a formal way.We compare the information complexity of two types of tasks: the task of irfenttjicat?on, in which all the student knows is a description of a natural class to which the object belongs, and the task of locafuatzon in which he knows that the target is a transformed image of some given object.We model localization as the task of learning the class of transformed instances of the given object.We apply some fundamental results from Algebraic Geometry to bound the VC-dimension of such 'transformed class' and compare it to the VC-dimension of some natural library classes to which the objects belong.We carry on the comparison to the scenario of learning under the uniform distribution, which leads us to calculating the ~-entropy of relevant classes.Our analysis provides a mathematical ground to the intuition that Localization is indeed much easier than Identification.

A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers.>

The problem of recovering the shape of planar objects from line or finger probings arises in robotics. This problem is addressed under the assumption that composite probings are made. One composite probing comprises several (k) line or finger probings done simultaneously. An investigation is conducted of planar polygon reconstruction from sequences of composite k-probings. For every value of k, a lower bound on the number of k-probings required for reconstruction under any strategy is obtained. Specific strategies which are provably almost optimal are provided.>

A 1:1 correspondence is established between digital straight lines which start at a fixed point and a simple set of quadruples of integer parameters. Such a representation by parameters is useful for enumeration, First, the authors show a 1:1 correspondence between point pairs in a planar set of points and the linear dichotomies of this set. Then, from the equivalence between digital lines and linear dichotomies of points on the digitization grid, they prove a 1:1 and 'onto' correspondence between digital straight lines starting at a fixed point and a well-defined set of pairs of grid points. It follows that four parameters uniquely represent any given digital line with a fixed starting point. An O(N) algorithm is given for determining the parameters from the digital line, as well as O(log N) algorithms for transforming between these parameters and the parameters suggested by L. Dorst and A.W.M. Smeulders (1984).>

A variation of the Hough Transform that is aimed at detecting digital lines has been recently suggested. Other Hough algorithms are intended to detect straight lines in the analog pre-image. These approaches arc analyzed and compared in terms of the relation between the achievable resolution and the required number of accumulators, using a definition of resolution that is based on the Geometric Probability measure of straight lines. It is shown that the "analog" approach is greatly superior in high resolution applications, where a "digital " Hough Transform would generally require an infeasibly large number of accumulators. The Hough Transform [2,4] is a well known technique for recognizing predefined features in edge maps. In this paper, the Hough Transform for detecting straight lines is considered. Most Hough algorithms consist of an incrementation stage, in which each edge point "votes " for the parameter-pairs of all possible straight lines on which it can lie, and an exhaustive search for peaks. These correspond to large collinear sets of edge-points. Originally, the slope-intercept (m,b) parametrization of straight lines had been employed in the Hough Transform. It has the advantage that an edge point corresponds to a straight line in the parameter space, thus voting is simple. Its drawback is that the parameter space is unbounded, implying some theoretical and practical difficulties. With normal (p,0) parametrization of straight lines, as suggested by [2], an edge point corresponds to a sinusoid in the parameter space, thus voting is somewhat more complex. The normal parametrization has the advantage that a bounded image leads to a bounded parameter space. Other straight-line parametrizations have also been suggested, see [4,11,17]. In most implementations of the Hough algorithm the parameter space is represented by a rectangular accumulator array, such that each accumulator corresponds to a rectangular, constant size domain in the parameter space. The quantization of the parameter space greatly influences the resolution and detection capabilities of the algorithm, as well as the computational and storage requirements; see

2D shape boundary segmentation is required as a fundamental and important stage in the recognition process of partially occluded objects. The authors introduce a segmentation approach which is invariant to similarity transformation and in which partial occlusion has only marginal influence on the segmentation of the visible part. The basic concept is to transform the curve into another curve which intersects itself. Points of intersection of the new curve are retransformed to the original curve and serve as endpoints of segments. Properties of the transform are discussed, and conditions for the existence of intersection points are given. Simulation results, showing substantial immunity to noise, are presented, and advantages of the proposed method over conventional approaches relying on singular points of the curvature are discussed.>

The size of five hierarchical geometric data structures is investigated analytically using random image models. Upper bounds and some lower bounds on the size of the structures are derived. The results are useful in predicting the storage required by the structures as well as the performance of algorithms that rely on them.>

The number of digital straight lines on an N*N grid is shown. A digital straight line is equivalent to a linear dichotomy of points on a square grid. The result is obtained by determining a way of counting the number of linearly separable dichotomies of points on the plane that are not necessarily in general position. The analysis is easily modified to provide a simple solution to a similar problem considered by C. Berenstein and D. Lavine (1988) on the number of digital straight lines from a fixed starting point.>

The number of different digital straight lines on an N*N square pixel array is studied. The problem is equivalent to finding the number of linear dichotomies of a planar set of N/sup 2/ points of an N*N grid. For any planar set of points, adjacent pairs are defined to be pairs of points from the set such that no other point from the set lie on the line segment between them. A one-to-one correspondence between linear dichotomies and adjacent pairs is proved. Then, the adjacent pairs of points of an N*N grid are counted, and the number of linear dichotomies, as well as the number of digital straight lines, follows. An asymptotic evaluation is proved and an efficient algorithm for finding L(N) for any particular N is given.>