In this note, we propose an approach to initialize the Iterative Closest Point (ICP) algorithm to match unlabelled point clouds related by rigid transformations. The method is based on matching the ellipsoids defined by the points' covariance matrices and then testing the various principal half-axes matchings that differ by elements of a finite reflection group. We derive bounds on the robustness of our approach to noise and numerical experiments confirm our theoretical findings.

Predicting urban traffic flow is a challenging task, due to the complicated spatio-temporal dependencies on traffic networks. Urban traffic flow usually has both short-term neighboring and long-term periodic temporal dependencies. It is also noticed that the spatial correlations over different traffic nodes are both local and non-local. What’s more, the traffic flow is affected by various external factors. To capture the non-local spatial correlations, we propose a Dilated Attentional Graph Convolution (DAGC). The DAGC utilizes a dilated graph convolution kernel to expand the nodes’ receptive field and exploit multi-order neighborhood. Technically, the lower-order neighborhood corresponds to local spatial dependencies, while the higher-order neighborhood corresponds to non-local spatial dependencies between nodes. Based on DAGC, a Multi-Source Spatio-Temporal Network (MS-Net) is designed, which suffices to integrate long-range historical traffic data as well as multi-modal external information. MS-Net consists of four components: a spatial feature extraction module, a temporal feature fusion module, an external factors embedding module, and a multi-source data fusion module. Extensive experiments on three real traffic datasets demonstrates that the proposed model performs well on both the public transportation networks, road networks, and can handle large-scale traffic networks in particular the Beijing bus network which has more than 4,000 traffic nodes.

Abstract Digital videos such as those captured by a smartphone often exhibit exposure inconsistencies, a poorly exposed sky, or simply suffer from an uninteresting or plain looking sky. Professionals may edit these videos using advanced and time‐consuming tools unavailable to most users, to replace the sky with a more expressive or imaginative sky. In this work, we propose an algorithm for automatic replacement of the sky region in a video with a different sky, providing nonprofessional users with a simple yet efficient tool to seamlessly replace the sky. The method is fast, achieving close to real‐time performance on mobile devices and the user's involvement can remain as limited as simply selecting the replacement sky.

Abstract Fused deposition modeling based 3D‐printing is becoming increasingly popular due to it's low‐cost and simple operation and maintenance. While it produces rugged prints made from a wide range of materials, it suffers from an inherent printing limitation where it cannot produce overhanging surfaces of non‐trivial size. This limitation can be handled by constructing temporary support‐structures, however this solution involves additional material costs, longer print time, and often a fair amount of labor in removing it. In this paper we present a new method for partitioning general solid objects into a small number of parts that can be printed with no support. The partitioning is computed by applying a sequence of cutting‐planes that split the object recursively. Unlike existing algorithms, the planes are not chosen at random, rather they are derived from shape analysis routines that identify and resolve various commonly‐found geometric configurations. In addition, we guide this search by a revised set of conditions that both ensure the objects' printability as well as realistically model the printing capabilities of the printer at hand. Evaluation of the new method demonstrates its ability to efficiently obtain support‐free partitionings typically containing fewer parts compared to existing methods that rely on support‐structures.

We present a deep network to recover pixel values lost to clipping. The clipped area of the image is typically a uniform area of minimum or maximum brightness, losing image detail and color fidelity. The degree to which the clipping is visually noticeable depends on the amount by which values were clipped, and the extent of the clipped area. Clipping may occur in any (or all) of the pixel's color channels. Although clipped pixels are common and occur to some degree in almost every image we tested, current automatic solutions have only partial success in repairing clipped pixels and work only in limited cases such as only with overexposure (not under-exposure) and when some of the color channels are not clipped. Using neural networks and their ability to model natural images allows our neural network, DeclipNet, to reconstruct data in clipped regions producing state of the art results.

In general it requires at least 7 point correspondences to compute the fundamental matrix between views. We use the cross ratio invariance between corresponding epipolar lines, stemming from epipolar line homography, to derive a simple formulation for the relationship between epipoles and corresponding points. We show how it can be used to reduce the number of required points for the epipolar geometry when some information about the epipoles is available and demonstrate this with a buddy search app.

This paper proposes using sketch algorithms to represent the votes in Hough transforms. Replacing the accumulator array with a sketch (Sketch Hough Transform - SHT) significantly reduces the memory needed to compute a Hough transform. We also present a new sketch, Count Median Update, which works better than known sketch methods for replacing the accumulator array in the Hough Transform.

Computing the epipolar geometry from feature points between cameras with very different viewpoints is often error prone, as an object's appearance can vary greatly between images. For such cases, it has been shown that using motion extracted from video can achieve much better results than using a static image. This paper extends these earlier works based on the scene dynamics. In this paper we propose a new method to compute the epipolar geometry from a video stream, by exploiting the following observation: For a pixel p in Image A, all pixels corresponding to p in Image B are on the same epipolar line. Equivalently, the image of the line going through camera A's center and p is an epipolar line in B. Therefore, when cameras A and B are synchronized, the momentary images of two objects projecting to the same pixel, p, in camera A at times t1 and t2, lie on an epipolar line in camera B. Based on this observation we achieve fast and precise computation of epipolar lines. Calibrating cameras based on our method of finding epipolar lines is much faster and more robust than previous methods.

Computing the epipolar geometry between cameras with very different viewpoints is often problematic as matching points are hard to find. In these cases, it has been proposed to use information from dynamic objects in the scene for suggesting point and line correspondences. We propose a speed up of about two orders of magnitude, as well as an increase in robustness and accuracy, to methods computing epipolar geometry from dynamic silhouettes. This improvement is based on a new temporal signature: motion barcode for lines. Motion barcode is a binary temporal sequence for lines, indicating for each frame the existence of at least one foreground pixel on that line. The motion barcodes of two corresponding epipolar lines are very similar, so the search for corresponding epipolar lines can be limited only to lines having similar barcodes. The use of motion barcodes leads to increased speed, accuracy, and robustness in computing the epipolar geometry.

It is known that epipolar geometry can be computed from three epipolar line correspondences but this computation is rarely used in practice since there are no simple methods to find corresponding lines. Instead, methods for finding corresponding points are widely used. This paper proposes a similarity measure between lines that indicates whether two lines are corresponding epipolar lines and enables finding epipolar line correspondences as needed for the computation of epipolar geometry. A similarity measure between two lines, suitable for video sequences of a dynamic scene, has been previously described. This paper suggests a stereo matching similarity measure suitable for images. It is based on the quality of stereo matching between the two lines, as corresponding epipolar lines yield a good stereo correspondence. Instead of an exhaustive search over all possible pairs of lines, the search space is substantially reduced when two corresponding point pairs are given. We validate the proposed method using real-world images and compare it to state-of-the-art methods. We found this method to be more accurate by a factor of five compared to the standard method using seven corresponding points and comparable to the 8-point algorithm.

We introduce a simple and effective method for retrieval of videos showing a specific event, even when the videos of that event were captured from significantly different viewpoints. Appearance-based methods fail in such cases, as appearances change with large changes of viewpoints. Our method is based on a pixel-based feature, “motion barcode”, which records the existence/non-existence of motion as a function of time. While appearance, motion magnitude, and motion direction can vary greatly between disparate viewpoints, the existence of motion is viewpoint invariant. Based on the motion barcode, a similarity measure is developed for videos of the same event taken from very different viewpoints. This measure is robust to occlusions common under different viewpoints, and can be computed efficiently. Event retrieval is demonstrated using challenging videos from stationary and hand held cameras.

This paper proposes the use of complex variables to represent votes in the Hough transform for circle detection. Replacing the positive numbers classically used in the parameter space of the Hough transforms by complex numbers allows cancellation effects when adding up the votes. Cancellation and the computation of shape likelihood via a complex number's magnitude square lead to more robust solutions than the “classic” algorithms, as shown by computational experiments on synthetic and real datasets. We note a resemblance to methods used in quantum theory.

It has been observed that in most videos recorded by surveillance cameras the image size of an object is a linear function of the y coordinate of its image location. This simple linear relationship holds in the most common surveillance camera configurations, where objects move on a planar surface and the camera's X axis is parallel to that plane. This linear relationship enables us to easily perform and enhance several geometric tasks based on tracking an object over a few frames: (i) computing the horizon; (ii) computing the relative real world sizes of objects in the scene based on their image appearance; (iii) improving tracking by constraining an object's location and size. When the the camera's X axis is not parallel to the ground plane, after tracking a couple of objects it is possible to find the rotation which rectifies the video so that its new X axis is parallel to the ground plane.

We propose a data structure that captures global geometric properties in images: Histogram of Mirror Symmetry Coefficients. We compute such a coefficient for every pair of pixels, and group them in a 6-dimensional histogram. By marginalizing the HMSC in various ways, we develop algorithms for a range of applications: detection of nearly-circular cells, location of the main axis of reflection symmetry, detection of cell-division in movies of developing embryos, detection of worm-tips and indirect cell-counting via supervised classification. Our approach generalizes a series of histogram-related methods, and the proposed algorithms perform with state-of-the-art accuracy.

Most image dehazing algorithms require, for their operation, the atmospheric light vector, A, which describes the ambient light in the scene. Existing methods either rely on user input or follow error-prone assumptions such as the gray-world assumption. In this paper we present a new automatic method for recovering the atmospheric light vector in hazy scenes given a single input image. The method first recovers the vector's orientation, Â = A/∥A∥, by exploiting the abundance of small image patches in which the scene transmission and surface albedo are approximately constant. We derive a reduced formation model that describes the distribution of the pixels inside such patches as lines in RGB space and show how these lines are used for robustly extracting Â. We show that the magnitude of the atmospheric light vector,∥A∥, cannot be recovered using patches of constant transmission. We also show that errors in its estimation results in dehazed images that suffer from brightness biases that depend on the transmission level. This dependency implies that the biases are highly-correlated with the scene and are therefore hard to detect via local image analysis. We address this challenging problem by exploiting a global regularity which we observe in hazy images where the intensity level of the brightest pixels is approximately independent of their transmission value. To exploit this property we derive an analytic expression for the dependence that a wrong magnitude introduces and recover ∥A∥ by minimizing this particular type of dependence. We validate the assumptions of our method through a number of experiments as well as evaluate the expected accuracy at which our procedure estimates A as function of the transmission in the scene. Results show a more successful recovery of the atmospheric light vector compared to existing procedures.

Optical flow, the pixel level correspondences between a pair of images is an important problem in computer vision. Standard optical flow computation algorithms assume constant brightness and fail on specular surfaces. Earlier work to alleviate problems with specularity evaluate the illuminant chromaticity using a few correspondences in the images and then jointly optimize flow and appearance under the dichromatic model. We argue that the correspondences obtained by these methods are mostly pairs of pixels that are Lambertian thus giving a noisy estimate of the illuminant chromaticity. We suggest a new approach to evaluate the illuminant chromaticity which does not require exact correspondences and gives a better estimate of illuminant chromaticity. We use the evaluated chromaticity to project the input images on to a specular invariant color space and show that standard optical flow algorithms on this color space significantly improves the flow results. The suggested approach is simple, efficient and more importantly can utilize existing algorithms to compute optical flow on non Lambertian surfaces.

We describe a statistical approach to the problem of estimating the times of cell-division cycles in time-lapse movies of early mouse embryos. Our method is based on the likelihoods for cells of certain radii ranges to be in each frame — without actually locating or counting the cells. Computing the likelihoods consists of a voting scheme where votes come form quadruples of points in a way similar to the first step of the Randomized Hough Transform for ellipse detection. To locate divisions, we search for points of abrupt change in the matrix of likelihoods (built for all frames), and pick the two optimal division points using a dynamic programming algorithm. Our results for the first and second cell division cycles differ less than two frames from the medians of the annotated times in a database of 100 annotated videos, and outperform two other recent methods in the same set.

We present an ellipse finding and fitting algorithm that uses points and tangents, rather than just points, as the basic unit of information. These units are analyzed in a hierarchy: points with tangents are paired into triangles in the first layer and pairs of triangles in the second layer vote for ellipse centers. The remaining parameters are estimated via robust linear algebra: eigen-decomposition and iteratively reweighed least squares. Our method outperforms the state-of-the-art approach in synthetic images and microscopic images of cells.

The graph Laplacian operator, which originated in spectral graph theory, is commonly used for learning applications such as spectral clustering and embedding. In this paper we explore the Laplacian distance, a distance function related to the graph Laplacian, and use it for visual search. We show that previous techniques such as Matching by Tone Mapping (MTM) are particular cases of the Laplacian distance. Generalizing the Laplacian distance results in distance measures which are tolerant to various visual distortions. A novel algorithm based on linear decomposition makes it possible to compute these generalized distances efficiently. The proposed approach is demonstrated for tone mapping invariant, outlier robust and multimodal template matching.

We estimate illuminant chromaticity from temporal sequences, for scenes illuminated by either one or two dominant illuminants. While there are many methods for illuminant estimation from a single image, few works so far have focused on videos, and even fewer on multiple light sources. Our aim is to leverage information provided by the temporal acquisition, where either the objects or the camera or the light source are/is in motion in order to estimate illuminant color without the need for user interaction or using strong assumptions and heuristics. We introduce a simple physically-based formulation based on the assumption that the incident light chromaticity is constant over a short space-time domain. We show that a deterministic approach is not sufficient for accurate and robust estimation: however, a probabilistic formulation makes it possible to implicitly integrate away hidden factors that have been ignored by the physical model. Experimental results are reported on a dataset of natural video sequences and on the Gray Ball benchmark, indicating that we compare favorably with the state-of-the-art.

We propose a novel method for detecting and enhancing specular highlights from a video sequence, thereby obtaining a better visual perception of the specularity. To this end, we first generate a specularity map, defined over the space-time domain, by leveraging information provided by the temporal acquisition. We then amplify the highlights in each video frame to create the visual sensation of high dynamic range data. Results are illustrated on several videos taken under different acquisition scenarios.

Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy.

We present an efficient and noise robust template matching method based on asymmetric correlation (ASC). The ASC similarity function is invariant to affine illumination changes and robust to extreme noise. It correlates the given non-normalized template with a normalized version of each image window in the frequency domain. We show that this asymmetric normalization is more robust to noise than other cross correlation variants, such as the correlation coefficient. Direct computation of ASC is very slow, as a DFT needs to be calculated for each image window independently. To make the template matching efficient, we develop a much faster algorithm, which carries out a prediction step in linear time and then computes DFTs for only a few promising candidate windows. We extend the proposed template matching scheme to deal with partial occlusion and spatially varying light change. Experimental results demonstrate the robustness of the proposed ASC similarity measure compared to state-of-the-art template matching methods.

This paper presents a simple and efficient method to convolve an image with a Gaussian kernel. The computation is performed in a constant number of operations per pixel using running sums along the image rows and columns. We investigate the error function used for kernel approximation and its relation to the properties of the input signal. Based on natural image statistics we propose a quadratic form kernel error function so that the SSD error of the output image is minimized. We apply the proposed approach to approximate the Gaussian kernel by linear combination of constant functions. This results in a very efficient Gaussian filtering method. Our experiments show that the proposed technique is faster than state of the art methods while preserving similar accuracy.

Abstract Automatic photo enhancement is one of the long‐standing goals in image processing and computational photography. While a variety of methods have been proposed for manipulating tone and colour, most automatic methods used in practice, operate on the entire image without attempting to take the content of the image into account. In this paper, we present a new framework for automatic photo enhancement that attempts to take local and global image semantics into account. Specifically, our content‐aware scheme attempts to detect and enhance the appearance of human faces, blue skies with or without clouds and underexposed salient regions. A user study was conducted that demonstrates the effectiveness of the proposed approach compared to existing auto‐enhancement tools.

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

Non uniform kernels is important for many image processing algorithms. However, for large kernel sizes the filtering can become computationally expensive. We introduce cosine integral images (CII) which represent a large set of spatial and range filters, based on their frequency decomposition. The filtering requires a constant number of operations per image pixel, independent of filter size. We make use of CII to compute the Gabor filters, whose complexity is for the first time a constant O(l) operations per image pixel. We also improve previous constant time approximations of spatial Gaussian smoothing and bilateral filtering.

We present a new solution for real-time head pose estimation. The key to our method is a model-based approach based on the fusion of color and time-of-flight depth data. Our method has several advantages over existing head-pose estimation solutions. It requires no initial setup or knowledge of a pre-built model or training data. The use of additional depth data leads to a robust solution, while maintaining real-time performance. The method outperforms the state-of-the art in several experiments using extreme situations such as sudden changes in lighting, large rotations, and fast motion.

We present a new algorithm for a robust family of Earth Mover's Distances - EMDs with thresholded ground distances. The algorithm transforms the flow-network of the EMD so that the number of edges is reduced by an order of magnitude. As a result, we compute the EMD by an order of magnitude faster than the original algorithm, which makes it possible to compute the EMD on large histograms and databases. In addition, we show that EMDs with thresholded ground distances have many desirable properties. First, they correspond to the way humans perceive distances. Second, they are robust to outlier noise and quantization effects. Third, they are metrics. Finally, experimental results on image retrieval show that thresholding the ground distance of the EMD improves both accuracy and speed.

This paper describes a method for robust real time pattern matching. We first introduce a family of image distance measures, the "Image Hamming Distance Family". Members of this family are robust to occlusion, small geometrical transforms, light changes and non-rigid deformations. We then present a novel Bayesian framework for sequential hypothesis testing on finite populations. Based on this framework, we design an optimal rejection/acceptance sampling algorithm. This algorithm quickly determines whether two images are similar with respect to a member of the Image Hamming Distance Family. We also present a fast framework that designs a near-optimal sampling algorithm. Extensive experimental results show that the sequential sampling algorithm performance is excellent. Implemented on a Pentium 4 3 GHz processor, detection of a pattern with 2197 pixels, in 640 x 480 pixel frames, where in each frame the pattern rotated and was highly occluded, proceeds at only 0.022 seconds per frame.

This paper proposes a Riemannian geometric framework to compute averages and distributions of point configurations so that different configurations up to affine transformations are considered to be the same. The algorithms are fast and proven to be robust both theoretically and empirically. The utility of this framework is shown in a number of affine invariant clustering algorithms on image point data.

This paper presents a method for capturing and computing 3D parallax. 3D parallax, as used here, refers to vertical offset from the ground plane, height. The method is based on analyzing shadows of vertical poles (e.g., a tall building’s contour) that sweep the object. Unlike existing beam-scanning approaches, such as shadow or structured light, that recover the distance of a point from the camera, our approach measures the height from the ground plane directly. Previous methods compute the distance from the camera using triangulation between rays outgoing from the light-source and the camera. Such a triangulation is difficult when the objects are far from the camera, and requires accurate knowledge of the light source position. In contrast, our approach intersects two (unknown) planes generated separately by two casting objects. This omits the need to precompute the location of the light source. Furthermore, it allows a moving light source to be used. The proposed setup is particularly useful when the camera cannot directly face the scene or when the object is far away from the camera. A good example is an urban scene captured by a single webcam.

A meaningful affinity measure between pixels is essential for many computer vision and image processing applications. We propose an algorithm that works in the features’ histogram to compute image specific affinity measures. We use the observation that clusters in the feature space are typically smooth, and search for a path in the feature space between feature points that is both short and dense. Failing to find such a path indicates that the points are separated by a bottleneck in the histogram and therefore belong to different clusters. We call this new affinity measure the "Bottleneck Geodesic". Empirically we demonstrate the superior results achieved by using our affinities as opposed to those using the widely used Euclidean metric, traditional geodesics and the simple bottleneck.

We present a family of "normal" distributions over a matrix group together with a simple method for estimating its parameters. In particular, the mean of a set of elements can be calculated. The approach is applied to planar projective homographies, showing that using priors defined in this way improves object recognition.

The problem we study is: given N views and a subset of the (/sub 2//sup N/) interview fundamental matrices, which of the other fundamental matrices can we compute using only the pre-computed fundamental matrices. This has applications in 3D (three-dimensional) reconstruction and when we want to reproject an area of one view on another, or to compute epipolar lines when the correspondence problem is too difficult to compute between every two views. A complete solution using linear algorithms to compute the missing fundamental matrices are given for up to six views. In many cases problems with more than six views can also be handled.

Traditional audio coding is based on a perceptual compression paradigm that exploits psychoacoustic information to efficiently encode audio signals. Recently, extensive research has been conducted in order to understand how the brain encodes natural signals. These results suggest that the encoding process is very efficient in terms of redundancy reduction of the signal information. It could be that the psychoacoustic effects (such as the masking effect) are only a special case of a more general redundancy reduction mechanism that exists in the auditory pathway. Motivated by this work we propose a new audio coding scheme that is based on improved sound representation found by independent component analysis. Using a local linear, low rank, nonorthogonal transform, we remove additional redundancies in the signal. At low bitrates this coding scheme gives results superior to a legacy perceptual encoding scheme for different kinds of audio signals.

We present a new method for rendering high dynamic range images on conventional displays. Our method is conceptually simple, computationally efficient, robust, and easy to use. We manipulate the gradient field of the luminance image by attenuating the magnitudes of large gradients. A new, low dynamic range image is then obtained by solving a Poisson equation on the modified gradient field. Our results demonstrate that the method is capable of drastic dynamic range compression, while preserving fine details and avoiding common artifacts, such as halos, gradient reversals, or loss of local contrast. The method is also able to significantly enhance ordinary images by bringing out detail in dark regions.

We present a stochastic clustering algorithm which uses pairwise similarity of elements and show how it can be used to address various problems in computer vision, including the low-level image segmentation, mid-level perceptual grouping, and high-level image database organization. The clustering problem is viewed as a graph partitioning problem, where nodes represent data elements and the weights of the edges represent pairwise similarities. We generate samples of cuts in this graph, by using Karger's contraction algorithm (1996), and compute an "average" cut which provides the basis for our solution to the clustering problem. The stochastic nature of our method makes it robust against noise, including accidental edges and small spurious clusters. The complexity of our algorithm is very low: O(|E| log/sup 2/ N) for N objects, |E| similarity relations, and a fixed accuracy level. In addition, and without additional computational cost, our algorithm provides a hierarchy of nested partitions. We demonstrate the superiority of our method for image segmentation on a few synthetic and real images, both B&W and color. Our other examples include the concatenation of edges in a cluttered scene (perceptual grouping) and the organization of an image database for the purpose of multiview 3D object recognition.

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

We present an algorithm based on statistical learning for synthesizing static and time-varying textures matching the appearance of an input texture. Our algorithm is general and automatic and it works well on various types of textures, including 1D sound textures, 2D texture images, and 3D texture movies. The same method is also used to generate 2D texture mixtures that simultaneously capture the appearance of a number of different input textures. In our approach, input textures are treated as sample signals generated by a stochastic process. We first construct a tree representing a hierarchical multiscale transform of the signal using wavelets. From this tree, new random trees are generated by learning and sampling the conditional probabilities of the paths in the original tree. Transformation of these random trees back into signals results in new random textures. In the case of 2D texture synthesis, our algorithm produces results that are generally as good as or better than those produced by previously described methods in this field. For texture mixtures, our results are better and more general than those produced by earlier methods. For texture movies, we present the first algorithm that is able to automatically generate movie clips of dynamic phenomena such as waterfalls, fire flames, a school of jellyfish, a crowd of people, etc. Our results indicate that the proposed technique is effective and robust.

We present a fast factorization algorithm for estimating structure and motion simultaneously from points, lines, and/or directly from the image intensities under full perspective. It generalizes the Oliensis method for points to include lines and intensities as well.

We present a stochastic clustering algorithm which uses pairwise similarity of elements, based on a new graph theoretical algorithm for the sampling of cuts in graphs. The stochastic nature of our method makes it robust against noise, including accidental edges and small spurious clusters. We demonstrate the robustness and superiority of our method for image segmentation on a few synthetic examples where other recently proposed methods (such as normalized-cut) fail. In addition, the complexity of our method is lower. We describe experiments with real images showing good segmentation results.

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

We describe a set of image measurements which are invariant to the camera internals but are location variant. We show that using these measurements it is possible to calculate the self-localization of a robot using known landmarks and uncalibrated cameras. We also show that it is possible to compute, using uncalibrated cameras, the Euclidean structure of 3-D world points using multiple views from known positions. We are free to alter the internal parameters of the camera during these operations. Our initial experiments demonstrate the applicability of the method.

A method to compute motion models in real time from point-to-line correspondences using linear programming is presented. Point-to-line correspondences are the most reliable motion measurements given the aperture effect, and it is shown how they can approximate other motion measurements as well. Using an L/sub 1/ error measure for image alignment based on point-to-line correspondences and minimizing this measure using linear programming, achieves results which are more robust than the commonly used L/sub 2/ metric. While estimators based on L/sub 1/ are not theoretically robust, experiments show that the proposed method is robust enough to allow accurate motion recovery in hundreds of consecutive frames. The entire computation is performed in real-time on a PC with no special hardware.

We consider the problem of reconstructing the 3D coordinates of a moving point seen from a monocular moving camera, i.e., to reconstruct moving objects from line-of-sight measurements only. The task is feasible only when same constraints are placed on the shape of the trajectory of the moving point. We coin the family of such tasks as "trajectory triangulation". In this paper we focus on trajectories whose shape is a conic-section and show that generally 9 views are sufficient for a unique reconstruction of the moving point and fewer views when the conic is a known type (like a circle in 3D Euclidean space for which 7 views are sufficient). Experiments demonstrate that our solutions are practical. The paradigm of Trajectory Triangulation in general pushes the envelope of processing dynamic scenes forward. Thus static scenes become a particular case of a more general task of reconstructing scenes rich with moving objects (where an object could be a single point).

An on-line agglomerative clustering algorithm for nonstationary data is described. Three issues are addressed. The first regards the temporal aspects of the data. The clustering of stationary data by the proposed algorithm is comparable to the other popular algorithms tested (batch and on-line). The second issue addressed is the number of clusters required to represent the data. The algorithm provides an efficient framework to determine the natural number of clusters given the scale of the problem. Finally, the proposed algorithm implicitly minimizes the local distortion, a measure that takes into account clusters with relatively small mass. In contrast, most existing on-line clustering methods assume stationarity of the data. When used to cluster nonstationary data, these methods fail to generate a good representation. Moreover, most current algorithms are computationally intensive when determining the correct number of clusters. These algorithms tend to neglect clusters of small mass due to their minimization of the global distortion (Energy).

An algorithm is presented for finding the most probable image motion between two images from fuzzy point correspondences. In fuzzy correspondence a point in one image is assigned to a region in the other image. Such a region can be line (aperture effect) or a convex polygon. Noise and outliers are always present, and points may belong to different motions. The presented algorithm, which uses linear programming, recovers the motion parameters and performs outlier rejection and motion-segmentation at the same time. The linear program computes the global optimum without a need for initial guess.

We demonstrate a real time system for image registration and moving object detection. The algorithm is based on describing the displacement of a point as a probability distribution over a matrix of possible displacements. A small set of randomly selected points is used to compute the registration parameters. Moving object detection is based on the consistency of the probabilistic displacement of image points with the global image motion.

The Kalman filter is a very efficient optimal filter, however it has the precondition that the noises of the process and of the measurement are Gaussian. The authors introduce 'the general distribution filter' which is an optimal filter that can be used even where the distributions are not Gaussian. An efficient practical implementation of the filter is possible where the distributions are discrete and compact or can be approximated as such.

Traditionally, corners are found along step edges. In this paper we present an alternative approach-corners along ridges/troughs and local minima points. These features seem to be more reliable for tracking. A new approach for sub-pixel localization of these corners is suggested, using a local approximation of the image surface.

We define two measures on views: view likelihood and view stability. View likelihood measures the probability that a certain view of a given 3D object is observed; it may be used to identify typical, or "characteristic" views. View stability measures how little the-image changes as the viewpoint is slightly perturbed; it may be used to identify "generic" views. Both definitions are shown to be identical up to the prior probability of camera orientations, and determined by the 2D metric used to compare images. We analytically derive the stability and likelihood measures for two feature-based 2D metrics, where the most stable and most likely view is shown to be the flattest view of the 3D shape. Incorporating view likelihood or stability in 3D object recognition and 3D reconstruction increases the chance of robust performance. In particular, we propose to use these measures to enhance 3D object recognition and 3D reconstruction algorithms, by adding a second step where the most likely solution is selected among all feasible solutions. These applications are demonstrated using simulated and real images.

It has been established that certain trilinear forms of three perspective views give rise to a tensor of 27 intrinsic coefficients. We show in this paper that a permutation of the the trilinear coefficients produces three homography matrices (projective transformations of planes) of three distinct intrinsic planes, respectively. This, in turn, yields the result that 3D invariants are recovered directly-simply by appropriate arrangement of the tensor's coefficients. On a secondary level, we show new relations between fundamental matrix, epipoles, Euclidean structure and the trilinear tensor. On the practical side, the new results extend the existing envelope of methods of 3D recovery from 2D views-for example, new linear methods that cut through the epipolar geometry, and new methods for computing epipolar geometry using redundancy available across many views.>

The paper unifies most of the current literature on 3D geometric invariants from point correspondences across multiple 2D views by using the tool of elimination from algebraic geometry. The technique allows one to predict results by counting parameters and reduces many complicated results obtained in the past (reconstructuon from two and three views, epipolar geometry from seven points, trilinearity of three views, the use of a priori 3D information such as bilateral symmetry, shading and color constancy, and more) into a few lines of reasoning each. The tool of Grobner base computation is used in the elimination process. In the process we obtain several results on N view geometry, and obtain a general result on invariant functions of 4 views and its corresponding quadlinear tensor: 4 views admit minimal sets of 16 invariant functions (of quadlinear forms) with 81 distinct coefficients that can be solved linearly from 6 corresponding points across 4 views. This result has non trivial implications to the understanding of N view geometry. We show a new result on single view invariants based on 6 points and show that certain relationships are impossible. One of the appealing features of the elimination approach is that it is simple to apply and does not require any understanding of the underlying 3D from 2D geometry and algebra.>

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed.>

A method for fusing and integrating different 2D and 3D measurements for pose estimation is proposed. The 2D measured data is viewed as 3D data with infinite uncertainty in particular directions. The method is implemented using Kalman filtering. It is robust and easily parallelizable.>

This correspondence presents a statistically sound, simple and, fast method to estimate the parameters of a second degree curve from a set of noisy points that originated from the curve.>

We develop expressions for measuring the distance between 2D point sets, which are invariant to either 2D affine transformations or 2D similarity transformations of the sets, and assuming a known correspondence between the point sets. We discuss the image normalization to be applied to the images before their comparison so that the computed distance is symmetric with respect to the two images. We then give a general (metric) definition of the distance between images, which leads to the same expressions for the similarity and affine cases. This definition avoids ad hoc decisions about normalization. Moreover, it makes it possible to compute the distance between images under different conditions, including cases where the images are treated asymmetrically. We demonstrate these results with real and simulated images.>

Given a set of low resolution camera images, it is possible to reconstruct high resolution luminance and depth information, specially if the relative displacements of the image frames are known. We propose iterative algorithms for recovering hash resolution albedo and depth maps that require no a priori knowledge of the scene, and therefore do not depend on other methods, as regards boundary and initial conditions. The problem of surface reconstruction has been formulated as one of expectation maximization (EM) and has been tackled in a probabilistic framework using Markov random fields (MRF). As for the depth map, our method directly recovers surface heights without refering to surface orientations, while increasing the resolution by camera jittering. Conventional statistical models have been coupled with geometrical techniques to construct a general model of the world and the imaging process.>

This paper presents a method for interpretation of modeled objects that is general enough to cover articulated and other types of constrained models. The flexibility between components of the model are expressed as spatial constraints which are fused into the pose estimation during the interpretation process. The constraint fusion assists in obtaining the correct interpretation and in reducing the search of possible correspondences. The proposed method can handle any constraint (including inequalities) between any number of different components of the model. The framework is based on Kalman filtering.>

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

We develop expressions for measuring the distance between 2D point sets, which are invariant to either 2D affine transformations or 2D similarity transformations of the sets, and assuming a known correspondence between the point sets. Moreover, it makes it possible to compute the distance between images under different conditions, including cases where the images are treated asymmetrically. We demonstrate these results with real images.

Point displacement constraints constitute an attractive technique for interactive design of smooth curves, surfaces, and volumes. The user defines an arbitrary number of “control points” on the object and specifies their desired spatial location, while the system computes the object's degrees of freedom so that the constraints are satisfied. A constraint-based interface gives a feeling of direct manipulation of the object. In this article we introduce soft constraints , constraints which do not have to be met exactly. The softness of each constraint serves as a nonisotropic, local shape parameter enabling the user to explore the space of objects conforming to the constraints. Additionally, there is a global shape parameter which determines the amount of similarity of the designed object to a rest shape, or equivalently, the rigidity of the rest shape. We present an algorithm termed probabilistic point constraints (PPC) for implementing soft constraints. The PPC algorithm views constraints as stochastic measurements of the state of a static system. The softness of a constraint is derived from the covariance of the “measurement.” The resulting system of probabilistic equations is solved using the Kalman filter , a powerful estimation tool in the theory of stochastic systems. We also describe a user interface using direct-manipulation devices for specifying and visualizing covariances in 2D and 3D. The algorithm is suitable for any object represented as a parametric blend of control points, including most spline representations. The covariance of a constraint provides a continuous transition from exact interpolation to controlled approximation of the constraint. The algorithm involves only linear operations and allows real-time interactive direct manipulation of curves and surfaces on current workstations.

Fast algorithms for computing min, median, max, or any other order statistic filter transforms are described. The algorithms take constant time per pixel to compute min or max filters and polylog time per pixel, in the size of the filter, to compute the median filter. A logarithmic time per pixel lower bound for the computation of the median filter is shown.>

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

A general and flexible method for fusing and integrating different 2D and 3D measurements for pose estimation is proposed. The 2D measured data are viewed as 3D data with infinite uncertainty in a particular direction. This representation unifies the two categories of the absolute orientation problem into a single problem that varies only in the uncertainty values associated with the measurements. With this paradigm a uniform mathematical formulation of the problem is obtained, and different kinds of measurements that can be fused to obtain a better solution. The method, which is implemented using Kalman filtering, is robust and easily parallelizable.>

The concept of robustness in statistics is examined. Starting from the concepts of the breakdown point and equivariance properties of an estimator, the desired equivariance properties for shape fitting are defined, and high breakdown point methods with these properties are found.>

Most methods to reconstruct surfaces from their derivatives assume two orthogonal derivatives in perfect registration. The authors propose an approach to use derivatives in arbitrary directions and to register orthogonal derivatives if they are not registered. They also develop a method to integrate second derivatives in the reconstruction.>

We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint “noise regions.” We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity) and noise regions (circles, squares, polygons). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The authors propose an active solution of optimally recovering 3D scene depth from a sequence of pictures. The choice of the difference between camera locations for the different pictures in the sequence is described. The tradeoff between short and long distances between successive locations of the camera is shown in terms of occlusions perspective transformation, and exact triangulation.>

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

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

An approach to active depth perception using stereo methods is proposed. Active vision is characterized by gaze control for input-dependent data acquisition, coupled with a treatment of the reliability of the acquired information. An active solution is proposed for the task of computing 3D depth from an image sequence, where the camera can be controlled. After each phase of computation (between pictures), when information is still needed, the camera is placed in a new optimal position for the next picture. This process is repeated until sufficient accuracy is achieved. The proposed approach improves the ability to perform tasks in a noisy environment. The accuracy and reliability of solutions are improved, and the quantity of necessary data and computations is reduced.>

It is shown that by defining a suitable measure for the comparison of images, changes in resolution can be treated with the same tool as changes in color resolution. A gray-tone image, for example, can be compared to a half-tone image having only two colors (black and white), but of higher spatial resolution. A graph-theoretical definition of the basic measure used is introduced. This is followed by application to spatial resampling and gray-level requantization. This results in a hybrid treatment of resolution, and the possibility of trading spatial for gray-level resolution and vice versa.>

Universal sequences for graphs, a concept introduced by Aleliunas [M.Sc. thesis, University of Toronto, Toronto, Ontario, Canada, January 1978] and Aleliunas et al. [Proc. 20th Annual Symposium on Foundation of Computer Science, 1979, pp. 218–223] are studied. By letting $U(d,n)$ denote the minimum length of a universal sequence for d-regular undirected graphs with n nodes, the latter paper has proved the upper bound $U(d,n) = O(d^2 n^3 \log n)$ using a probabilistic argument. Here a lower bound of $U(2,n) = \Omega (n\log n)$ is proved from which $U(d,n) = \Omega (n\log n)$ for all d is deduced. Also, for complete graphs $U(n - 1,n) = \Omega ({{n\log ^2 n} / {\log \log n}})$. An explicit construction of universal sequences for cycles $(d = 2)$ of length $n^{O(\log n)} $ is given.

A signature is generated for a given picture by operating on it with different masks. The operations are gray level generalizations of ``shrink'' and ``expand'' for binary pictures using Serra's morphological methods [10]. The signature is a set of numbers, each corresponding to an application of an operator at a certain scale and direction, and can be used to analyze the discriminate textures. It is shown that this family of signatures includes as special cases several currently used texture descriptors.