Search

We introduce a new deep learning method for point cloud comparison. Our approach, named Deep Point Cloud Distance (DPDist), measures the distance between the points in one cloud and the estimated surface from which the other point cloud is sampled. The surface is estimated locally using the 3D modified Fisher vector representation. The local representation reduces the complexity of the surface, enabling effective learning, which generalizes well between object categories. We test the proposed distance in challenging tasks, such as similar object comparison and registration, and show that it provides significant improvements over commonly used distances such as Chamfer distance, Earth mover’s distance, and others.

The human visual system correctly groups features and can even interpret random-dot videos induced by imaging natural dynamic scenes. Remarkably, this happens even if perception completely fails when the same information is presented frame by frame. We study this property of surprising dynamic perception with the first goal of proposing a new detection and spatio-temporal grouping algorithm for such signals when, per frame, the information on objects is both random and sparse. The algorithm is based on temporal integration and statistical tests of unlikeliness, the a contrario framework. The striking similarity in performance of the algorithm to the perception by human observers, as witnessed by a series of psychophysical experiments, leads us to see in it a simple computational Gestalt model of human perception.

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., Comment: Submitted to ICPR2020

Modern robotic systems are often equipped with a direct three-dimensional (3-D) data acquisition device, e.g., LiDAR, which provides a rich 3-D point cloud representation of the surroundings. This representation is commonly used for obstacle avoidance and mapping. Here, we propose a new approach for using point clouds for another critical robotic capability, semantic understanding of the environment (i.e., object classification). Convolutional neural networks (CNNs), that perform extremely well for object classification in 2-D images, are not easily extendible to 3-D point clouds analysis. It is not straightforward due to point clouds’ irregular format and a varying number of points. The common solution of transforming the point cloud data into a 3-D voxel grid needs to address severe accuracy versus memory size tradeoffs. In this letter, we propose a novel, intuitively interpretable, 3-D point cloud representation called 3-D modified Fisher vectors. Our representation is hybrid as it combines a coarse discrete grid structure with continuous generalized Fisher vectors. Using the grid enables us to design a new CNN architecture for real-time point cloud classification. In a series of performance analysis experiments, we demonstrate competitive results or even better than state of the art on challenging benchmark datasets while maintaining robustness to various data corruptions.

Current successful approaches for generic (non-semantic) segmentation rely mostly on edge detection and have leveraged the strengths of deep learning mainly by improving the edge detection stage in the algorithmic pipeline. This is in contrast to semantic and instance segmentation, where DNNs are applied directly to generate pixel-wise segment representations. We propose a new method for learning a pixel-wise representation that reflects segment relatedness. This representation is combined with an edge map to yield a new segmentation algorithm. We show that the representations themselves achieve state-of-the-art segment similarity scores. Moreover, the proposed combined segmentation algorithm provides results that are either state of the art or improve upon it, for most quality measures., Comment: CVPR 2020. arXiv admin note: substantial text overlap with arXiv:1909.11735

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., Comment: Code will be available after publication. Figure quality reduced to fit size requirement. Higher quality images will be available in the final paper

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.

The a contrario approach is a principled method for making algorithmic decisions that has been applied successfully to many tasks in image analysis. The method is based on a background model (or null hypothesis) for the image. This model relies on independence assumptions and characterizes images in which no detection should be made. It is often image dependent, relying on statistics gathered from the image, and therefore adaptive. In this paper we propose a generalization for background models which relaxes the independence assumption and instead uses image dependent second order properties. The second order properties are accounted for thanks to graphical models. The modified a contrario technique is applied to two tasks: line segment detection and part-based object detection, and its advantages are demonstrated. In particular, we show that the proposed method enables reasonably accurate prediction of the false detection rate with no need for training data.

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.

The Mean Shift tracker is a widely used tool for robustly and quickly tracking the location of an object in an image sequence using the object's color histogram. The reference histogram is typically set to that in the target region in the frame where the tracking is initiated. Often, however, no single view suffices to produce a reference histogram appropriate for tracking the target. In contexts where multiple views of the target are available prior to the tracking, this paper enhances the Mean Shift tracker to use multiple reference histograms obtained from these different target views. This is done while preserving both the convergence and the speed properties of the original tracker. We first suggest a simple method to use multiple reference histograms for producing a single histogram that is more appropriate for tracking the target. Then, to enhance the tracking further, we propose an extension to the Mean Shift tracker where the convex hull of these histograms is used as the target model. Many experimental results demonstrate the successful tracking of targets whose visible colors change drastically and rapidly during the sequence, where the basic Mean Shift tracker obviously fails.

An effective and efficient texture analysis method, based on a new criterion for designing Gabor filter sets, is proposed. The commonly used filter sets are usually designed for optimal signal representation. We propose here an alternative criterion for designing the filter set. We consider a set of filters and its response to pairs of harmonic signals. Two signals are considered separable if the corresponding two sets of vector responses are disjoint in at least one of the components. We propose an algorithm for deriving the set of Gabor filters that maximizes the fraction of separable harmonic signal pairs in a given frequency range. The resulting filters differ significantly from the traditional ones. We test these maximal harmonic discrimination (MHD) filters in several texture analysis tasks: clustering, recognition, and edge detection. It turns out that the proposed filters perform much better than the traditional ones in these tasks. They can achieve performance similar to that of state-of-the-art, distribution based (texton) methods, while being simpler and more computationally efficient.

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 present an algorithm for recovering the orientation (attitude) of a satellite-based camera. The algorithm matches stars in an image taken with the camera to stars in a star catalogue. The algorithm is based on a geometric voting scheme in which a pair of stars in the catalogue votes for a pair of stars in the image if the angular distance between the stars of both pairs is similar. As angular distance is a symmetric relationship, each of the two catalogue stars votes for each of the image stars. The identity of each star in the image is set to the identity of the catalogue star that cast the most votes. Once the identity of the stars is determined, the attitude of the camera is computed using a quaternion-based method. We further present a fast tracking algorithm that estimates the attitude for subsequent images after the first algorithm has terminated successfully. Our method runs in comparable speed to state of the art algorithms but is still more robust than them. The system has been implemented and tested on simulated data and on real sky images.

The calculation of salient structures is one of the early and basic ideas of perceptual organization in computer vision. Saliency algorithms typically mark edge-points with some saliency measure, growing with the length and the smoothness of the curve on which this edge-point lies. We consider a generalization [M. Lindenbaum and A. Berengolts, 2000] of the Ullman-Shaashua saliency measure (1998) and aim to analyze the saliency measure in a probabilistic context: regarding the basic grouping information (grouping cues) as random variables, we use ergodicity and asymptotic analysis to derive the saliency distribution associated with the main curves ("figure") and with the rest of the image ("background"). We further consider finite-length curves and analyze their saliency values. We observed several discrepancies between the observed distributions and the predictions we supply, discuss their sources and propose a way to account for them. Then, based on the derived distributions we show how to set threshold on the saliency for deciding optimally between figure and background, how to choose cues which are usable for saliency, and how to estimate bounds on the saliency performance.

Over the past few years researchers have been investigating the enhancement of visual tracking performance by devising trackers that simultaneously make use of several different features. In this paper we investigate the combination of synchronous visual trackers that use different features while treating the trackers as "black boxes". That is, instead of fusing the usage of the different types of data as has been performed in previous work, the combination here is allowed to use only the trackers' output estimates, which may be modified before their propagation to the next time step. We propose a probabilistic framework for combining multiple synchronous trackers, where each separate tracker outputs a probability density function of the tracked state, sequentially for each image. The trackers may output either an explicit probability density function, or a sample-set of it via Condensation. Unlike previous tracker combinations, the proposed framework is fairly general and allows the combination of any set of trackers of this kind, even in different state-spaces of different dimensionality, under a few reasonable assumptions. The combination may consist of different trackers that track a common object, as well as trackers that track separate, albeit related objects, thus improving the tracking performance of each object. The benefits of merely using the final estimates of the separate trackers in the combination are twofold. Firstly, the framework for the combination is fairly general and may be easily used from the software aspects. Secondly, the combination may be performed in a distributed setting, where each separate tracker runs on a different site and uses different data, while avoiding the need to share the data. The suggested framework was successfully tested using various state-spaces and datasets, demonstrating that fusing the trackers' final distribution estimates may indeed be applicable.

Most existing inductive learning algorithms work under the assumption that their training examples are already tagged. There are domains, however, where the tagging procedure requires significant computation resources or manual labor. In such cases, it may be beneficial for the learner to be active, intelligently selecting the examples for labeling with the goal of reducing the labeling cost. In this paper we present LSS—a lookahead algorithm for selective sampling of examples for nearest neighbor classifiers. The algorithm is looking for the example with the highest utility, taking its effect on the resulting classifier into account. Computing the expected utility of an example requires estimating the probability of its possible labels. We propose to use the random field model for this estimation. The LSS algorithm was evaluated empirically on seven real and artificial data sets, and its performance was compared to other selective sampling algorithms. The experiments show that the proposed algorithm outperforms other methods in terms of average error rate and stability.

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.

Efficient exploration of large networks is a central issue in data mining and network maintenance applications. In most existing work there is a distinction between the active ‘searcher’ which both executes the algorithm and holds the memory and the passive ‘searched graph’ over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which a noncentralized group of one or more lightweight autonomous agents traverse the network in a completely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and reduced load on the busy nodes due to the small amount of memory and computing resources required by the agent in each node. Algorithms for network covering based on this paradigm could be used in today’s Internet as a support for data mining and network control algorithms. Recently, a vertex ant walk ( VAW ) method has been suggested [I.A. Wagner, M. Lindenbaum, A.M. Bruckstein, Ann. Math. Artificial Intelligence 24 (1998) 211–223] for searching an undirected, connected graph by an a(ge)nt that walks along the edges of the graph, occasionally leaving ‘pheromone’ traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd, where n is the number of vertices and d the diameter of the graph. In this work we further investigate the performance of the VAW method on dynamic graphs, where edges may appear or disappear during the search process. In particular we prove that (a) if a certain spanning subgraph S is stable during the period of covering, then the VAW method is guaranteed to cover the graph within time nds, where ds is the diameter of S, and (b) if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd(( log Δ / log (1/p))+((1+p)/(1−p))) , where Δ is the maximum vertex degree in the graph. We also show that (c) if G is a static tree then it is covered within time 2n.

The paper presents a new approach for shape recovery based on integrating geometric and photometric information. We consider 3D bilaterally symmetric objects, that is, objects which are symmetric with respect to a plane (e.g., faces), and their reconstruction from a single image. Both the viewpoint and the illumination are not necessarily frontal. Furthermore, no correspondence between symmetric points is required. The basic idea is that an image taken from a general, non frontal viewpoint, under non-frontal illumination can be regarded as a pair of images. Each image of the pair is one half of the object, taken from different viewing positions and with different lighting directions. Thus, one-image-variants of geometric stereo and of photometric stereo can be used. Unlike the separate invocation of these approaches, which require point correspondence between the two images, we show that integrating the photometric and geometric information suffice to yield a dense correspondence between pairs of symmetric points, and as a result, a dense shape recovery of the object. Furthermore, the unknown lighting and viewing parameters, are also recovered in this process. Unknown distant point light source, Lambertian surfaces, unknown constant albedo, and weak perspective projection are assumed. The method has been implemented and tested experimentally on simulated and real data.

We consider a robotic setting and a class of control tasks that rely on partial visual information. These tasks are difficult in the sense that at every given moment, the available information is insufficient for the control task. This implies that the image Jacobian, which relates the image space and the control space, is no longer of full rank. However, the amount of information collected throughout the control process is still 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 optimization algorithms which are special cases of POCS (Projection On Convex Sets) 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 can be carried out, in principle, for any camera rotation and suggest efficient control and camera moving strategies. We substantiate our claims by simulations and experiments. Interestingly, it seems that the advisable control law is not consistent with simple intuition.

This paper proposes a new, efficient, figure from ground discrimination method. This algorithm is based on the assumption that background data features can be more easily detected than figure data features, thus emphasizing the background detection task (and implying the name of the method). Along the iterative labeling process, data features are sequentially and permanently labeled as “background,” while more global information is being collected to assist with the coming decisions, until the process converges. This procedure creates a bootstrap mechanism which improves performance in very cluttered scenes. The 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 one to work on large, realistic images.

We analyze the amount of data needed to carry out various model-based recognition tasks in the context of a probabilistic data collection model. We focus on objects that may be described as semi-algebraic subsets of a Euclidean space. This is a very rich class that includes polynomially described bodies, as well as polygonal objects, as special cases. The class of object transformations considered is wide, and includes perspective and affine transformations of 2D objects, and perspective projections of 3D objects. We derive upper bounds on the number of data features (associated with non-zero spatial error) which provably suffice for drawing reliable conclusions. Our bounds are based on a quantitative analysis of the complexity of the hypotheses class that one has to choose from. Our central tool is the VC-dimension, which is a well-studied parameter measuring the combinatorial complexity of families of sets. It turns out that these bounds grow linearly with the task complexity, measured via the VC-dimension of the class of objects one deals with. We show that this VC-dimension is at most logarithmic in the algebraic complexity of the objects and in the cardinality of the model library. Our approach borrows from computational learning theory. Both learning and recognition use evidence to infer hypotheses but as far as we know, their similarity was not exploited previously. We draw close relations between recognition tasks and a certain learnability framework and then apply basic techniques of learnability theory to derive our sample size upper bounds. We believe that other relations between learning procedures and visual tasks exist and hope that this work will trigger further fruitful study along these lines.

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.

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 identification of an unknown object from labeled examples input, and the task of localization in which the identity of the target is known and its location in some background scene has to be determined. We carry out the comparison of these tasks using two measuring rods for the complexity of classes of sets; The Vapnik-Chervonenkis dimension and the e-entropy of relevant classes. The VC-dimension analysis yields bounds on the sample complexity of performing these tasks in the PAC-learning scenario whereas the e-entropy parameter reflects the complexity of the relevant learning tasks when the examples are generated by the uniform distribution (over the background scene). Our analysis provides a mathematical ground to the intuition that localization is indeed much easier than identification. Our upper-bounds on the hardness of localization are established by applying a new, algebraic-geometry based, general tool for the calculation of the VC-dimension of classes of algebraically defined objects. This technique was independently discovered by Goldberg and Jerrum. We believe that our techniques will prove useful for further VC-dimension estimation problems.

We propose a mathematical model for learning the high-density areas of an unknown distribution from (unlabeled) random points drawn according to this distribution. While this type of a learning task has not been previously addressed in the computational learnability literature, we believe that this it a rather basic problem that appears in many practical learning scenarios. From a statistical theory standpoint, our model may be viewed as a restricted instance of the fundamental issue of inferring information about a probability distribution from the random samples it generates. From a computational learning angle, what we propose is a few framework of unsupervised concept learning. The examples provided to the learner in our model are not labeled (and are not necessarily all positive or all negative). The only information about their membership is indirectly disclosed to the student through the sampling distribution. We investigate the basic features of the proposed model and provide lower and upper bounds on the sample complexity of such learning tasks. We prove that classes whose VC-dimension is finite are learnable in a very strong sense, while on the other hand,ε-covering numbers of a concept class impose lower bounds on the sample size needed for learning in our models. One direction of the proof involves a reduction of the density-level learnability to PAC learning with respect to fixed distributions (as well as some fundamental statistical lower bounds), while the sufficiency condition is proved through the introduction of a generic learning algorithm.

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.

Background models are often used in video surveillance systems to find moving objects in an image sequence from a static camera. These models are often built under the assumption that the foreground objects are not known in advance. This assumption has led us to model background using one-class SVM classifiers. Our model belongs to a family of block-based nonparametric models that can be used effectively for highly complex scenes of various background distributions with almost the same configuration parameters for all examined videos. Experimental results are reported on a variety of test videos from the Background Models Challenge (BMC) competition.

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. >

Most segmentation methods are based on a relatively simple score, designed to lend itself to relatively efficient optimization. We take the opposite approach and suggest more complex segmentation scores that are based on a mixture of on-line and off-line learning processes and rely on rich descriptors. The score is evaluated by a segmentation process which uses exploration-exploitation to search for good segments in various scales and shapes. We test our algorithm in a foreground-background segmentation task, given a minimal prior which is just a single seed point inside the object of interest. Results on two image databases are presented and compared with earlier approaches.

This paper proposes a novel approach for pedestrian re-identification. Previous re-identification methods use one of 3 approaches: invariant features; designing metrics that aim to bring instances of shared identities close to one another and instances of different identities far from one another; or learning a transformation from the appearance in one domain to the other. Our implicit approach models camera transfer by a binary relation R={(x,y)|x and y describe the same person seen from cameras A and B respectively}. This solution implies that the camera transfer function is a multi-valued mapping and not a single-valued transformation, and does not assume the existence of a metric with desirable properties. We present an algorithm that follows this approach and achieves new state-of-the-art performance.

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. >

Dennis Gabor is mainly known for the invention of optical holography and the introduction of the so-called Gabor functions in communications. A few people know that he was also interested in image processing. In a paper entitled “Information theory in electron microscopy” (Laboratory Investigation14(6), 801–807 (1965)), written in 1965, he examined the problem of image deblurring and was the first to suggest a method for edge enhancement based on principles widely accepted today and implemented in advanced image processing systems. In this paper his ideas are reviewed, their relation to contemporary methods is shown, and some simulations he could not do in 1965 are performed.

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.

We present two novel contributions to the problem of region classification in scenery/landscape images. The first is a model that incorporates local cues with global layout cues, following the statistical characteristics recently suggested in [1]. The observation that background regions in scenery images tend to horizontally span the image allows us to represent the contextual dependencies between background region labels with a simple graphical model, on which exact inference is possible. While background is traditionally classified using only local color and textural features, we show that using new layout cues significantly improves background region classification. Our second contribution addresses the problem of correct results being considered as errors in cases where the ground truth provides the structural class of a land region (e.g., mountain), while the classifier provides its coverage class (e.g., grass), or vice versa. We suggest an alternative labeling method that, while trained using ground truth that describes each region with one label, assigns both a structural and a coverage label for each land region in the validation set. By suggesting multiple labels, each describing a different aspect of the region, the method provides more information than that available in the ground truth.

This work focuses on characterizing scenery images. We semantically divide the objects in natural landscape scenes into background and foreground and show that the shapes of the regions associated with these two types are statistically different. We then focus on the background regions. We study statistical properties such as size and shape, location and relative location, the characteristics of the boundary curves and the correlation of the properties to the region's semantic identity. Then we discuss the imaging process of a simplified 3D scene model and show how it explains the empirical observations. We further show that the observed properties suffice to characterize the gist of scenery images, propose a generative parametric graphical model, and use it to learn and generate semantic sketches of new images, which indeed look like those associated with natural scenery.

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.

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 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 L2 NMF. 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.

The problem of recovering the shape of planar objects arises in robotics. This work deals with this problem under the assumption that composite double probings are made. Two kinds of double probes are considered and their use for reconstructing convex planar polygons is investigated. For both kinds of probes, lower bounds on the number of probings required for reconstruction under any strategy are obtained and specific strategies which are proven to be almost optimal are provided.

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 are 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.

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.

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).

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.

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.

Retrieving images using object shapes usually requires to specify the major (or salient) structures in the image. Detecting salient structures is a basic task in perceptual organization. Saliency algorithms depend on grouping cues and mark edge-points with some saliency measure, which typically grows with the length and smoothness of the curve on which these edge-points lie. We consider a particular saliency mechanism [20] and focus on one aspect of its design: how different image measurements should be combined to get an effective grouping cue, leading to better specifications of the salient structures. We discuss 5 different combination methods, based, respectively, on a common heuristic, on Bayesian considerations (two versions), on optimizing a figure-ground separation measure using recent analysis results, and on incorporation of global information using bootstrap. Three of these cues are refinements of older methods and two are completely new. The advantage of the later methods is demonstrated.

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.

Gabor features are a common choice for texture analysis. The particular set of Gabor filters used for extracting the features is usually designed for optimal signal representation. We propose here an alternative criterion for designing the filter set. We consider a set of filters and its response to pairs of harmonic signals. Two signals are considered separable if the corresponding two sets of vector responses are disjoint in at least one of the components. We look for the set of Gabor filters that maximizes the fraction of separable harmonic signal pairs. The resulting filters are significantly different from the traditional ones. We test these maximal harmonic discrimination (MHD) filters using two texture discrimination methods, and describe their advantages over traditional filters.

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 inner-scene 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.

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.