Most robust estimators require tuning the parameters of the algorithm for the particular application, a bottleneck for practical applications. The paper presents the multiple input structures with robust estimator (MISRE), where each structure, inlier or outlier, is processed independently. The same two constants are used to find the scale estimates over expansions for each structure. The inlier/outlier classification is straightforward since the data is processed and ordered with the relevant inlier structures listed first. If the inlier noises are similar, MISRE's performance is equivalent to RANSAC-type algorithms. MISRE still returns the correct inlier estimates when inlier noises are very different, while RANSAC-type algorithms do not perform as well. MISRE's failures are gradual when too many outliers are present, beginning with the least significant inlier structure. Examples from 2D images and 3D point clouds illustrate the estimation.

Mean shift clustering is a powerful nonparametric technique that does not require prior knowledge of the number of clusters and does not constrain the shape of the clusters. However, being completely unsupervised, its performance suffers when the original distance metric fails to capture the underlying cluster structure. Despite recent advances in semi-supervised clustering methods, there has been little effort towards incorporating supervision into mean shift. We propose a semi-supervised framework for kernel mean shift clustering (SKMS) that uses only pairwise constraints to guide the clustering procedure. The points are first mapped to a high-dimensional kernel space where the constraints are imposed by a linear transformation of the mapped points. This is achieved by modifying the initial kernel matrix by minimizing a log det divergence-based objective function. We show the advantages of SKMS by evaluating its performance on various synthetic and real datasets while comparing with state-of-the-art semi-supervised clustering algorithms.

This paper presents an opinion on research progress in computer vision.

We propose a novel robust estimation algorithm—the generalized projection-based M-estimator (gpbM), which does not require the user to specify any scale parameters. The algorithm is general and can handle heteroscedastic data with multiple linear constraints for single and multicarrier problems. The gpbM has three distinct stages—scale estimation, robust model estimation, and inlier/outlier dichotomy. In contrast, in its predecessor pbM, each model hypotheses was associated with a different scale estimate. For data containing multiple inlier structures with generally different noise covariances, the estimator iteratively determines one structure at a time. The model estimation can be further optimized by using Grassmann manifold theory. We present several homoscedastic and heteroscedastic synthetic and real-world computer vision problems with single and multiple carriers.

We introduce a robust estimator called generalized projection based M-estimator (gpbM) which does not require the user to specify any scale parameters. For multiple inlier structures, with different noise covariances, the estimator iteratively determines one inlier structure at a time. Unlike pbM, where the scale of the inlier noise is estimated simultaneously with the model parameters, gpbM has three distinct stages-scale estimation, robust model estimation and inlier/outlier dichotomy. We evaluate our performance on challenging synthetic data, face image clustering upto ten different faces from Yale Face Database B and multi-body projective motion segmentation problem on Hopkins155 dataset. Results of state-of-the-art methods are presented for comparison.

Robust and fast 3D tracking of deformable objects, such as heart, is a challenging task because of the relatively low image contrast and speed requirement. Many existing 2D algorithms might not be directly applied on the 3D tracking problem. The 3D tracking performance is limited due to dramatically increased data size, landmarks ambiguity, signal drop-out or complex nonrigid deformation. In this paper, we present a robust, fast, and accurate 3D tracking algorithm: prediction based collaborative trackers (PCT). A novel one-step forward prediction is introduced to generate the motion prior using motion manifold learning. Collaborative trackers are introduced to achieve both temporal consistency and failure recovery. Compared with tracking by detection and 3D optical flow, PCT provides the best results. The new tracking algorithm is completely automatic and computationally efficient. It requires less than 1.5 s to process a 3D volume which contains millions of voxels. In order to demonstrate the generality of PCT, the tracker is fully tested on three large clinical datasets for three 3D heart tracking problems with two different imaging modalities: endocardium tracking of the left ventricle (67 sequences, 1134 3D volumetric echocardiography data), dense tracking in the myocardial regions between the epicardium and endocardium of the left ventricle (503 sequences, roughly 9000 3D volumetric echocardiography data), and whole heart four chambers tracking (20 sequences, 200 cardiac 3D volumetric CT data). Our datasets are much larger than most studies reported in the literature and we achieve very accurate tracking results compared with human experts' annotations and recent literature.

Mean shift clustering is a powerful unsupervised data analysis technique which does not require prior knowledge of the number of clusters, and does not constrain the shape of the clusters. The data association criteria is based on the underlying probability distribution of the data points which is defined in advance via the employed distance metric. In many problem domains, the initially designed distance metric fails to resolve the ambiguities in the clustering process. We present a novel semi-supervised kernel mean shift algorithm where the inherent structure of the data points is learned with a few user supplied constraints in addition to the original metric. The constraints we consider are the pairs of points that should be clustered together. The data points are implicitly mapped to a higher dimensional space induced by the kernel function where the constraints can be effectively enforced. The mode seeking is then performed on the embedded space and the approach preserves all the advantages of the original mean shift algorithm. Experiments on challenging synthetic and real data clearly demonstrate that significant improvements in clustering accuracy can be achieved by employing only a few constraints.

Breast cancer accounts for about 30% of all cancers and 15% of cancer deaths in women. Advances in computer-assisted analysis hold promise for classifying subtypes of disease and improving prognostic accuracy. We introduce a grid-enabled decision support system for performing automatic analysis of imaged breast tissue microarrays. To date, we have processed more than 1,00,000 digitized specimens (1200 x 1200 pixels each) on IBM's World Community Grid (WCG). As a part of the Help Defeat Cancer (HDC) project, we have analyzed that the data returned from WCG along with retrospective patient clinical profiles for a subset of 3744 breast tissue samples, and have reported the results in this paper. Texture-based features were extracted from the digitized specimens, and isometric feature mapping was applied to achieve nonlinear dimension reduction. Iterative prototyping and testing were performed to classify several major subtypes of breast cancer. Overall, the most reliable approach was gentle AdaBoost using an eight-node classification and regression tree as the weak learner. Using the proposed algorithm, a binary classification accuracy of 89% and the multiclass accuracy of 80% were achieved. Throughout the course of the experiments, only 30% of the dataset was used for training.

Large-scale, multisite collaboration has become indispensable for a wide range of research and clinical activities that rely on the capacity of individuals to dynamically acquire, share, and assess images and correlated data. In this paper, we report the development of a Web-based system, PathMiner , for interactive telemedicine, intelligent archiving, and automated decision support in pathology. The PathMiner system supports network-based submission of queries and can automatically locate and retrieve digitized pathology specimens along with correlated molecular studies of cases from "ground-truth" databases that exhibit spectral and spatial profiles consistent with a given query image. The statistically most probable diagnosis is provided to the individual who is seeking decision support. To test the system under real-case scenarios, a pipeline infrastructure was developed and a network-based test laboratory was established at strategic sites at the University of Medicine and Dentistry of New Jersey-Robert Wood Johnson Medical School, Robert Wood Johnson University Hospital, the University of Pennsylvania School of Medicine, Hospital of the University of Pennsylvania, The Cancer Institute of New Jersey, and Rutgers University. The average five-class classification accuracy of the system was 93.18% based on a tenfold cross validation on a close dataset containing 3691 imaged specimens. We also conducted prospective performance studies with the PathMiner system in real applications in which the specimens exhibited large variations in staining characters compared with the training data. The average five-class classification accuracy in this open-set experiment was 87.22%. We also provide the comparative results with the previous literature and the PathMiner system shows superior performance.

Analytic manifolds were recently used for motion averaging, segmentation and robust estimation. Here we consider the epipolar constraint for calibrated cameras, which is the most general motion model for calibrated cameras and is encoded by the essential matrix. The set of all essential matrices forms the essential manifold. We provide a theoretical characterization of the geometry of the essential manifold and develop a parametrization which associates each essential matrix with a unique point on the manifold. Our work provides a more complete theoretical analysis of the essential manifold than previous work in this direction. We show the results of using this parametrization with real data sets, while previous work concentrated on theoretical analysis with synthetic data.

This paper presents a novel learning based tracking model combined with object detection. The existing techniques proceed by linearizing the motion, which makes an implicit Euclidean space assumption. Most of the transformations used in computer vision have matrix Lie group structure. We learn the motion model on the Lie algebra and show that the formulation minimizes a first order approximation to the geodesic error. The learning model is extended to train a class specific tracking function, which is then integrated to an existing pose dependent object detector to build a pose invariant object detection algorithm. The proposed model can accurately detect objects in various poses, where the size of the search space is only a fraction compared to the existing object detection methods. The detection rate of the original detector is improved by more than 90% for large transformations.

Tracking the left ventricle (LV) in 3D ultrasound data is a challenging task because of the poor image quality and speed requirements. Many previous algorithms applied standard 2D tracking methods to tackle the 3D problem. However, the performance is limited due to increased data size, landmarks ambiguity, signal drop-out or non-rigid deformation. In this paper we present a robust, fast and accurate 3D LV tracking algorithm. We propose a novel one-step forward prediction to generate the motion prior using motion manifold learning, and introduce two collaborative trackers to achieve both temporal consistency and failure recovery. Compared with tracking by detection and 3D optical flow, our algorithm provides the best results and sub-voxel accuracy. The new tracking algorithm is completely automatic and computationally efficient. It requires less than 1.5 seconds to process a 3D volume which contains 4,925,440 voxels.

We present a new algorithm to detect pedestrian in still images utilizing covariance matrices as object descriptors. Since the descriptors do not form a vector space, well known machine learning techniques are not well suited to learn the classifiers. The space of d-dimensional nonsingular covariance matrices can be represented as a connected Riemannian manifold. The main contribution of the paper is a novel approach for classifying points lying on a connected Riemannian manifold using the geometry of the space. The algorithm is tested on INRIA and DaimlerChrysler pedestrian datasets where superior detection rates are observed over the previous approaches.

The non-negativity of color signals implies that they span a conical space with a hyperbolic geometry. We use perspective projections to separate intensity from chromaticity, and for 3-D color descriptors the chromatic properties are represented by points on the unit disk. Descriptors derived from the same object point but under different imaging conditions can be joined by a hyperbolic geodesic. The properties of this model are investigated using multichannel images of natural scenes and black body illuminants of different temperatures. We show, over a series of static scenes with different illuminants, how illumination changes influence the hyperbolic distances and the geodesics. Descriptors derived from conventional RGB images are also addressed.

Discontinuity preserving filtering of images is an important low-level vision task. With the development of new imaging techniques like diffusion tensor imaging (DTI), where the data does not lie in a vector space, previous methods like the original mean shift are not applicable. In this paper, we use the nonlinear mean shift algorithm to develop filtering methods for data lying on analytic manifolds. We work out the computational details of using mean shift on Symn+, the manifold of n times n symmetric positive definite matrices. We apply our algorithm to chromatic noise filtering, which requires mean shift over the Grassmann manifold G3,1, and obtain better results then standard mean shift filtering. We also use our method for DTI filtering, which requires smoothing over Sym3+.

We present a new algorithm to detect humans in still images utilizing covariance matrices as object descriptors. Since these descriptors do not lie on a vector space, well known machine learning techniques are not adequate to learn the classifiers. The space of d-dimensional nonsingular covariance matrices can be represented as a connected Riemannian manifold. We present a novel approach for classifying points lying on a Riemannian manifold by incorporating the a priori information about the geometry of the space. The algorithm is tested on INRIA human database where superior detection rates are observed over the previous approaches.

Object-based segmentation is a challenging topic. Most of the previous algorithms focused on segmenting a single or a small set of objects. In this paper, the multiple class object-based segmentation is achieved using the appearance and bag of keypoints models integrated over mean-shift patches. We also propose a novel affine invariant descriptor to model the spatial relationship of keypoints and apply the Elliptical Fourier Descriptor to describe the global shapes. The algorithm is computationally efficient and has been tested for three real datasets using less training samples. Our algorithm provides better results than other studies reported in the literature.

We propose a new robust estimator for camera pose estimation based on a recently developed nonlinear mean shift algorithm. This allows us to treat pose estimation as a clustering problem in the presence of outliers. We compare our method to RANSAC, which is the standard robust estimator for computer vision problems. We also show that under fairly general assumptions our method is provably better than RANSAC. Synthetic and real examples to support our claims are provided

We propose a simple and elegant algorithm to track nonrigid objects using a covariance based object description and a Lie algebra based update mechanism. We represent an object window as the covariance matrix of features, therefore we manage to capture the spatial and statistical properties as well as their correlation within the same representation. The covariance matrix enables efficient fusion of different types of features and modalities, and its dimensionality is small. We incorporated a model update algorithm using the Lie group structure of the positive definite matrices. The update mechanism effectively adapts to the undergoing object deformations and appearance changes. The covariance tracking method does not make any assumption on the measurement noise and the motion of the tracked objects, and provides the global optimal solution. We show that it is capable of accurately detecting the nonrigid, moving objects in non-stationary camera sequences while achieving a promising detection rate of 97.4 percent.

The mean shift algorithm is widely applied for nonparametric clustering in Euclidean spaces. Recently, mean shift was generalized for clustering on matrix Lie groups. We further extend the algorithm to a more general class of nonlinear spaces, the set of analytic manifolds. As examples, two specific classes of frequently occurring parameter spaces, Grassmann manifolds and Lie groups, are considered. When the algorithm proposed here is restricted to matrix Lie groups the previously proposed method is obtained. The algorithm is applied to a variety of robust motion segmentation problems and multibody factorization. The motion segmentation method is robust to outliers, does not require any prior specification of the number of independent motions and simultaneously estimates all the motions present.

In an errors-in-variables (EIV) model, all the measurements are corrupted by noise. The class of EIV models with constraints separable into the product of two nonlinear functions, one solely in the variables and one solely in the parameters, is general enough to represent most computer vision problems. We show that the estimation of such nonlinear EIV models can be reduced to iteratively estimating a linear model having point dependent, i.e., heteroscedastic, noise process. Particular cases of the proposed heteroscedastic errors-in-variables (HEIV) estimator are related to other techniques described in the vision literature: the Sampson method, renormalization, and the fundamental numerical scheme. In a wide variety of tasks, the HEIV estimator exhibits the same, or superior, performance as these techniques and has a weaker dependence on the quality of the initial solution than the Levenberg-Marquardt method, the standard approach toward estimating nonlinear models.

We propose a new method to estimate multiple rigid motions from noisy 3D point correspondences in the presence of outliers. The method does not require prior specification of number of motion groups and estimates all the motion parameters simultaneously. We start with generating samples from the rigid motion distribution. The motion parameters are then estimated via mode finding operations on the sampled distribution. Since rigid motions do not lie on a vector space, classical statistical methods can not be used for mode finding. We develop a mean shift algorithm which estimates modes of the sampled distribution using the Lie group structure of the rigid motions. We also show that proposed mean shift algorithm is general and can be applied to any distribution having a matrix Lie group structure. Experimental results on synthetic and real image data demonstrate the superior performance of the algorithm.

Estimation of camera pose is an integral part of augmented reality systems. Vision-based methods offer a flexible and accurate method for this estimation. Current vision based methods rely on markers to reduce the computation and increase robustness of the pose estimation. However, this limits the algorithm's applicability while being expensive since the markers also require maintenance. Alternatively, reconstructed scene features can be used for pose estimation but this can lead to a loss of accuracy. To avoid this we propose a two-stage balanced tracking method which does not require any visual markers in the scene. The first stage of our method is based on the sequential recovery of structure from motion which allows the system to learn the scene from a few frames in which the markers are visible. In the next stage, the learned features are used for camera tracking. The system ensures greater accuracy and reduces error drift due to its use of the HEIV estimator which is provably unbiased to the first degree. We also make use of a novel method for the detection and removal of outliers which are unavoidable in such systems. The experiments show the superiority of our method when compared to a nonlinear method based on Levenberg-Marquardt minimization.

One of the most commonly used clinical tests performed today is the routine evaluation of peripheral blood smears. In this paper, we investigate the design, development, and implementation of a robust color gradient vector flow (GVF) active contour model for performing segmentation, using a database of 1791 imaged cells. The algorithms developed for this research operate in Luv color space, and introduce a color gradient and L2E robust estimation into the traditional GVF snake. The accuracy of the new model was compared with the segmentation results using a mean-shift approach, the traditional color GVF snake, and several other commonly used segmentation strategies. The unsupervised robust color snake with L2E robust estimation was shown to provide results which were superior to the other unsupervised approaches, and was comparable with supervised segmentation, as judged by a panel of human experts.

A technique is presented to combine n data points, each available with point-dependent uncertainty, when only a subset of these points come from N < n sources, where N is unknown. We detect the significant modes of the underlying multivariate probability distribution using a generalization of the nonparametric mean shift procedure. The number of detected modes automatically defines N, while the belonging of a point to the basin of attraction of a mode provides the fusion rule. The robust data fusion algorithm was successfully applied to two computer vision problems: estimating the multiple affine transformations, and range image segmentation.

To solve the general point correspondence problem in which the underlying transformation between image patches is represented by a homography, a solution based on extensive use of first order differential techniques is proposed. We integrate in a single robust M-estimation framework the traditional optical flow method and matching of local color distributions. These distributions are computed with spatially oriented kernels in the 5D joint spatial/color space. The estimation process is initiated at the third level of a Gaussian pyramid, uses only local information, and the illumination changes between the two images are also taken into account. Subpixel matching accuracy is achieved under large projective distortions significantly exceeding the performance of any of the two components alone. As an application, the correspondence algorithm is employed in oriented tracking of objects.

The robust regression techniques in the RANSAC family are popular today in computer vision, but their performance depends on a user supplied threshold. We eliminate this drawback of RANSAC by reformulating another robust method, the M-estimator, as a projection pursuit optimization problem. The projection based pbM-estimator automatically derives the threshold from univariate kernel density estimates. Nevertheless, the performance of the pbM-estimator equals or exceeds that of RANSAC techniques tuned to the optimal threshold, a value which is never available in practice. Experiments were performed both with synthetic and real data in the affine motion and fundamental matrix estimation tasks.

Feature space analysis is the main module in many computer vision tasks. The most popular technique, k-means clustering, however, has two inherent limitations: the clusters are constrained to be spherically symmetric and their number has to be known a priori. In nonparametric clustering methods, like the one based on mean shift, these limitations are eliminated but the amount of computation becomes prohibitively large as the dimension of the space increases. We exploit a recently proposed approximation technique, locality-sensitive hashing (LSH), to reduce the computational complexity of adaptive mean shift. In our implementation of LSH the optimal parameters of the data structure are determined by a pilot learning procedure, and the partitions are data driven. As an application, the performance of mode and k-means based textons are compared in a texture classification study.

A new approach toward target representation and localization, the central component in visual tracking of nonrigid objects, is proposed. The feature histogram-based target representations are regularized by spatial masking with an isotropic kernel. The masking induces spatially-smooth similarity functions suitable for gradient-based optimization, hence, the target localization problem can be formulated using the basin of attraction of the local maxima. We employ a metric derived from the Bhattacharyya coefficient as similarity measure, and use the mean shift procedure to perform the optimization. In the presented tracking examples, the new method successfully coped with camera motion, partial occlusions, clutter, and target scale variations. Integration with motion filters and data association techniques is also discussed. We describe only a few of the potential applications: exploitation of background information, Kalman tracking using motion models, and face tracking.

A general non-parametric technique is proposed for the analysis of a complex multimodal feature space and to delineate arbitrarily shaped clusters in it. The basic computational module of the technique is an old pattern recognition procedure: the mean shift. For discrete data, we prove the convergence of a recursive mean shift procedure to the nearest stationary point of the underlying density function and, thus, its utility in detecting the modes of the density. The relation of the mean shift procedure to the Nadaraya-Watson estimator from kernel regression and the robust M-estimators; of location is also established. Algorithms for two low-level vision tasks discontinuity-preserving smoothing and image segmentation - are described as applications. In these algorithms, the only user-set parameter is the resolution of the analysis, and either gray-level or color images are accepted as input. Extensive experimental results illustrate their excellent performance.

The "direct methods" achieve global image registration without explicit knowledge of feature correspondences. We employ the motion gradient constraint as the relation between the motion parameters and the measured image gradients. While this relation appears as a linear system of equations, for any motion model (other than a translation) we show that the underlying noise process is data-dependent, i.e., heteroscedastic, a fact which must be taken into account in the parameter estimation process. The improvement obtained using the adequate procedure is confirmed for the 2D rigid motion model through comparison with the traditional total least square approach.

In many vision problems (e.g., stereo, motion) multiple structures can occur in the data, in which case several instances of the same model need to be recovered from a single data set. However, once the measurement noise becomes significantly large relative to the separation between the structures, the robust statistical methods commonly used in the vision community tend to fail. In this paper, we show that all these techniques are special cases of the general class of M-estimators with auxiliary scale, and explain their failure in the presence of noisy multiple structures. To be able to cope with data containing multiple structures the techniques innate to vision (Hough and RANSAC) should be combined with the robust methods customary in statistics. The implications of our analysis are illustrated by introducing a simple procedure for 2D multistructured data problematic for all known current techniques.

Reliable estimation of the trifocal tensor is crucial for 3D reconstruction from uncalibrated cameras. The estimation process is based on minimizing the geometric distances between the measurements and the corrected data points, the underlying nonlinear optimization problem being most often solved with the Levenberg-Marquardt (LM) algorithm. We employ for this task the heteroscedastic errors-in-variables (HEIV) estimator and take into account both the singularity of the multivariate tensor constraint and the bifurcation which can appear for noisy data. In comparison to the Gold Standard method, the new approach is significantly faster while having the same performance, and it is less sensitive to initialization when the data is close to degenerate. Analytical expressions for the covariances of the parameter and corrected image point estimates are available for the HEIV estimator and thus the confidence regions of the corrected measurements can be delineated in the images.

Computing the weighted average of the pixel values in a window is a basic module in many computer vision operators. The process is reformulated in a linear vector space and the role of the different subspaces is emphasized. Within this framework wellknown artifacts of the gradient-based edge detectors, such as large spurious responses can be explained quantitatively. It is also shown that template matching with a template derived from the input data is meaningful since it provides an independent measure of confidence in the presence of the employed edge model. The widely used three-step edge detection procedure - gradient estimation, non-maxima suppression, hysteresis thresholding - is generalized to include the information provided by the confidence measure. The additional amount of computation is minimal and experiments with several standard test images show the ability of the new procedure to detect weak edges.

A new method for real time tracking of non-rigid objects seen from a moving camera is proposed. The central computational module is based on the mean shift iterations and finds the most probable target position in the current frame. The dissimilarity between the target model (its color distribution) and the target candidates is expressed by a metric derived from the Bhattacharyya coefficient. The theoretical analysis of the approach shows that it relates to the Bayesian framework while providing a practical, fast and efficient solution. The capability of the tracker to handle in real time partial occlusions, significant clutter, and target scale variations, is demonstrated for several image sequences.

The Errors-in-Variables (EIV) model from statistics is often employed in computer vision though only rarely under this name. In an EIV model all the measurements are corrupted by noise while the a priori information is captured with a nonlinear constraint among the true (unknown) values of these measurements. To estimate the model parameters and the uncorrupted data, the constraint can be linearized, i.e., embedded in a higher dimensional space. We show that linearization introduces data-dependent (heteroscedastic) noise and propose an iterative procedure, the heteroscedastic EIV (HEIV) estimator to obtain consistent estimates in the most general, multivariate case. Analytical expressions for the covariances of the parameter estimates and corrected data points, a generic method for the enforcement of ancillary constraints arising from the underlying geometry are also given. The HEIV estimator minimizes the first order approximation of the geometric distances between the measurements and the true data points, and thus can be a substitute for the widely used Levenberg-Marquardt based direct solution of the original nonlinear problem. The HEIV estimator has however the advantage of a weaker dependence on the initial solution and a faster convergence. In comparison to Kanatani's renormalization paradigm (an earlier solution of the same problem) the HEIV estimator has more solid theoretical foundations which translate into better numerical behavior We show that the HEIV estimator can provide an accurate solution to most 3D vision estimation tasks, and illustrate its performance through two case studies: calibration and the estimation of the fundamental matrix.

An improved maximum likelihood estimator for ellipse fitting based on the heteroscedastic errors-in-variables (HEIV) regression algorithm is proposed. The technique significantly reduces the bias of the parameter estimates present in the direct least squares method, while it is numerically more robust than renormalization, and requires less computations than minimizing the geometric distance with the Levenberg-Marquardt optimization procedure. The HEIV algorithm also provides closed-form expressions for the covariances of the ellipse parameters and corrected data points. The quality of the different solutions is assessed by defining confidence regions in the input domain, either analytically or by bootstrap. The latter approach is exclusively data driven and it is used whenever the expression of the covariance for the estimates is not available.

The features employed in content-based retrieval are most often simple low-level representations, while a human observer judges similarity between images based on high-level semantic properties. Using textures as an example, we show that a more accurate description of the underlying distribution of low-level features does not improve the retrieval performance. We also introduce the simplified multiresolution symmetric autoregressive model for textures, and the Bhattacharyya distance based similarity measure. Experiments are performed with four texture representations and four similarity measures over the Brodatz and Vis Tex databases.

The process of discriminating among pathologies involving peripheral blood, bone marrow, and lymph node has traditionally begun with subjective morphological assessment of cellular materials viewed using light microscopy. The subtle visible differences exhibited by some malignant lymphomas and leukemia, however, give rise to a significant number of false negatives during microscopic evaluation by medical technologists. We have developed a distributed, clinical decision support prototype for distinguishing among hematologic malignancies. The system consists of two major components, a distributed telemicroscopy system and an intelligent image repository. The hybrid system enables individuals located at disparate clinical and research sites to engage in interactive consultation and to obtain computer-assisted decision support. Software, written in JAVA, allows primary users to control the specimen stage, objective lens, light levels, and focus of a robotic microscope remotely while a digital representation of the specimen is continuously broadcast to all session participants. Primary user status can be passed as a token. The system features shared graphical pointers, text messaging capability, and automated database management. Search engines for the database allow one to automatically identify and retrieve images, diagnoses, and correlated clinical data of cases from a "gold standard" database which exhibit spectral and spatial profiles which are most similar to a given query image. The system suggests the most likely diagnosis based on majority logic of the retrieved cases. The system was used to discriminate among three lymphoproliferative disorders and healthy cells. The system provided the correct classification in more than 83% of the cases studied. System performance was evaluated using rigorous statistical assessment and by comparison with human observers.

Recent advances in networking, robotics and computer technology allow real-time diagnosis, consultation, and education by using images obtained through remote microscopy. This paper presents a new approach in telepathology, the image guided decision support (IGDS) system, which integrates components for both remote microscope control and decision support. Using the micro-controller component the physician can command a robotic microscope from a distance, obtain high-quality images to be used in the diagnosis, and authorize other users to visualize the same images. The image understanding-based decision support component of the system locates, retrieves and displays cases which exhibit morphological profiles consistent to the case in question and suggests the most likely diagnosis based on majority logic. The IGDS system has a natural man-machine interface containing engines for speech recognition and voice feedback.

This paper addresses the problem of reliably estimating the coefficients of the parameterized image variety (PIV) associated with the set of weak perspective images of a rigid scene, with applications in image-based rendering. Exploiting the fact that the constraints defining the PIV are linear in its coefficients and bilinear in the image data, the estimation procedure is cast in the errors-in-variables framework and solved using the method proposed by Y. Leedan and P. Meer (1998) for this type of problems. The proposed approach has been implemented, and experiments with real data are shown to yield much better prediction power than the original method based on singular value decomposition. Extensions to the more difficult case of paraperspective projection are briefly discussed.

A new method for 3D rigid motion estimation is derived under the most general assumption that the measurements are corrupted by inhomogeneous and anisotropic, i.e., heteroscedastic noise. This is the case, for example, when the motion of a calibrated stereo-head is to be determined from image pairs. Linearization in the quaternion space transforms the problem into a multivariate, heteroscedastic errors-in-variables (HEIV) regression, from which the rotation and translation estimates are obtained simultaneously. The significant performance improvement is illustrated, for real data, by comparison with the results of quaternion, subspace and renormalization based approaches described in the literature. Extensive use as made of bootstrap, an advanced numerical tool from statistics, both to estimate the covariances of the 3D data points and to obtain confidence regions for the rotation and translation estimates. Bootstrap enables an accurate recovery of these information using only the two image pairs serving as input.

A nonparametric estimator of density gradient, the mean shift, is employed in the joint, spatial-range (value) domain of gray level and color images for discontinuity preserving filtering and image segmentation. Properties of the mean shift are reviewed and its convergence on lattices is proven. The proposed filtering method associates with each pixel in the image the closest local mode in the density distribution of the joint domain. Segmentation into a piecewise constant structure requires only one more step, fusion of the regions associated with nearby modes. The proposed technique has two parameters controlling the resolution in the spatial and range domains. Since convergence is guaranteed, the technique does not require the intervention of the user to stop the filtering at the desired image quality. Several examples, for gray and color images, show the versatility of the method and compare favorably with results described in the literature for the same images.

In many multi-media applications it is desirable to separate the influence of the illumination sources and imaging equipment from the properties of the depicted scene. The ability of the human visual system to solve this task in many situations is known as color constancy. Technical applications of these methods include automatic color correction and illumination independent search in image databases. Many conventional computational color constancy methods assume that the effect of an illumination change can be described by a matrix multiplication with a diagonal matrix. In this paper we introduce a color normalization algorithm which computes the unique color transformation matrix which normalizes a given set of moments computed from the color distribution of an image. This normalization procedure is a generalization of the channel independent color constancy methods since general matrix transformations are considered. We compare the performance of this new normalization method with conventional color constancy methods. The experiments show that diagonal transformation matrices provide a better illumination compensation. This shows that the color moments also contain significant information about the color distributions of the objects in the image which is independent of the illumination characteristics. In another set of experiments we use the unique transformation matrix as a descriptor of the set of moments which describe the global color distribution in the image. Combining the matrices computed from two such images describes the color differences between them. We then use this as a tool for color dependent search in image databases. This matrix based color search is computationally less demanding than histogram based color search tools.

A complete analysis of the statistical issues related to the estimation of a bilinear form, one of the fundamental problems in computer vision, is presented. It is shown why already at moderate noise levels most available techniques fail to provide a satisfactory solution. A new estimation procedure is proposed in which the nonlinear nature of the errors is taken into account and the implementation is based on the generalized singular value decomposition for superior numerical behavior. As an example, the ellipse fitting problem is discussed, and the performance of the new algorithm is compared with the current state-of-the-art.

A prototype system performing analysis, indexing and retrieval of pathology images to assist physicians in differential diagnosis of lymphoproliferative disorders is presented. Robust color segmentation is used to automatically analyse regions of interest in images of leukocytes. The shape of leukocyte nuclei, described through similarity invariant shape descriptors, represents the main attribute in the search query. Monte Carlo tests for stability and goal-directed evaluations of the system performance are also shown.

The prototype of a system to assist the physicians in differential diagnosis of lymphoproliferative disorders of blood cells from digitized specimens is presented. The user selects the region of interest (ROI) in the image which is then analyzed with a fast, robust color segmenter. Queries in a database of validated cases can be formulated in terms of shape (similarity invariant Fourier descriptors), texture (multiresolution simultaneous autoregressive model), color (L*u*/spl upsi/* space), and area, derived from the delineated ROI. The uncertainty of the segmentation process (obtained through a numerical method) determines the accuracy of shape description (number of Fourier harmonics). Ten-fold cross-validated classification over a database of 261 color 640/spl times/480 images was implemented to assess the system performance. The ground truth was obtained through immunophenotyping by flow cytometry. To provide a natural man-machine interface, most input commands are bimodal: either using the mouse or by voice. A speech synthesizer provides feedback to the user. All the employed computational modules are context independent and thus the same system can be used in a large variety of application domains.

We demonstrate the prototype of an image understanding based system to support decision making in clinical pathology. The system employs all four major low level vision queues (shape, texture, color, metric measures) in content-based retrieval of visual information. The reliability of the central module of the system, the fast color segmenter, makes possible on-line analysis of the query image. The user interface is bimodal (speech and mouse input), allowing a natural communication with the system.

We propose a novel image segmentation technique using the robust, adaptive least kth order squares (ALKS) estimator which minimizes the kth order statistics of the squares of residuals. The optimal value of k is determined from the data, and the procedure detects the homogeneous surface patch representing the relative majority of the pixels. The ALKS shows a better tolerance to structured outliers than other recently proposed similar techniques. The performance of the new, fully autonomous, range image segmentation algorithm is compared to several other methods.

A general technique for the recovery of significant image features is presented. The technique is based on the mean shift algorithm, a simple nonparametric procedure for estimating density gradients. Drawbacks of the current methods (including robust clustering) are avoided. Feature space of any nature can be processed, and as an example, color image segmentation is discussed. The segmentation is completely autonomous, only its class is chosen by the user. Thus, the same program can produce a high quality edge image, or provide, by extracting all the significant colors, a preprocessor for content-based query systems. A 512/spl times/512 color image is analyzed in less than 10 seconds on a standard workstation. Gray level images are handled as color images having only the lightness coordinate.

The information in a color image is always a function of the illuminating source, the geometry, the reflectance properties of the object and the characteristic of the camera. Separating the influence of the spectral distribution of the illumination and the reflectance properties of the object is known as the color constancy problem. Successful separation is important for vision and pattern recognition tasks, quality control in the graphic arts and image database applications. We describe an approach to the color constancy problem which is based on statistical assumptions about the distribution of colors. It uses the eigenvector system of the logarithmic spectra in a large database of color samples and employs methods from robust statistics to recover the illumination spectrum. We illustrate the performance of the algorithm with a simulation in which the effect of the illumination by the standard A-source is eliminated.

A new performance evaluation paradigm for computer vision systems is proposed. In real situation, the complexity of the input data and/or of the computational procedure can make traditional error propagation methods infeasible. The new approach exploits a resampling technique recently introduced in statistics, the bootstrap. Distributions for the output variables are obtained by perturbing the nuisance properties of the input, i.e., properties with no relevance for the output under ideal conditions. From these bootstrap distributions, the confidence in the adequacy of the assumptions embedded into the computational procedure for the given input is derived. As an example, the new paradigm is applied to the task of edge detection. The performance of several edge detection methods is compared both for synthetic data and real images. The confidence in the output can be used to obtain an edgemap independent of the gradient magnitude.

As the healthcare community has begun to rely increasingly upon digital technologies for acquisition, storage, and transmission of pictorial data, image compression has become an indispensable tool. We have investigated the feasibility of lossy compression in a well-defined task domain, the clinical assessment of digitized images of chromatic microscopic pathology specimens. The effect of compression was measured under two distinct perceptual criteria, just noticeable difference (j.n.d.) and largest tolerable distortion (l.t.d.), differing in the involvement required from subjects, who were experts in pathology. For standard JPEG compressed images it was found that when the experiment is performed under the l.t.d. criterion, a significantly larger compression ratio is reported as satisfactory. It is concluded that lossy compression holds promise for diagnostic telepathology.

The potential of lossy image compression is investigated in a well defined task domain, specifically, clinical assessment of chromatic, surgical and hematopathology specimens. Two criteria were employed, just noticeable difference and largest tolerable distortion. Compression tolerances differed among pathologists, but conformed to well defined upper and lower limits. The level of tolerable compression was significantly larger for the second criterion. It is concluded that lossy image compression is feasible for diagnostic pathology and may hold promise for telepathology applications.

A modular approach for extracting 3D information from a stack of 2D slices is presented. The bottom-up procedure makes extensive use of robust high breakdown point estimators adapted to image analysis. All the decision parameters are either derived from the data or are context-independent. A priori information is easy to integrate, and the reliability of the results can be verified by seeking the consensus among independent executions of the procedure.

A general method for eliminating the bias of nonlinear estimators using bootstrap is presented. Instead of the traditional mean bias we consider the definition of bias based on the median. The method is applied to the problem of fitting ellipse segments to noisy data. No assumption beyond being independent identically distributed is made about the error distribution and experiments with both synthetic and real data prove the effectiveness of the technique.

The correspondence between two coplanar sets of points (or lines) is established making use of a novel invariant representation of five-tuples of features. The projective/permutation (p/sup 2/) invariants are insensitive to the order of the features in the computation and thus provide a significant speedup in matching. Performance degradation due to the noise sensitivity of the invariants is avoided by using context independent constraints (noncollinearity of points, preservation of the convex hull); and by accumulating the feature correspondence hypotheses in a contingency table. Full projective correspondence can be recovered reliably for positional uncertainty of several pixels or in the presence of outliers.

The robust least-median-of-squares (LMedS) estimator, which can recover a model representing only half the data points, was recently introduced in computer vision. Image data, however, is usually also corrupted by a zero-mean random process (noise) accounting for the measurement uncertainties. It is shown that in the presence of significant noise, LMedS loses its high breakdown point property. A different, two-stage approach in which the uncertainty due to noise is reduced before applying the simplest LMedS procedure is proposed. The superior performance of the technique is proved by comparative graphs.>

The projective correspondence between planar point/line sets is determined using conic invariants. In each set six (4+2) randomly chosen points/lines define two conics to which two absolute projective invariants can be associated. Similar invariant values yield six-tuples matched between the sets. The order of features on a conic is not important and thus the probability of finding a match is maximized. Feature correspondence is recovered with a dynamic programming type analysis of the contingency table derived from the ensemble of matched six-tuples. The algorithm is very sensitive to feature accuracy, raising questions about the straightforward use of conic invariants in recognition of arbitrary objects. The procedures employed, however-affine invariant conic fitting to noisy data,-probabilistic two-stage matching and are of general interest.>

A clustering algorithm based on the minimum volume ellipsoid (MVE) robust estimator is proposed. The MVE estimator identifies the least volume region containing h percent of the data points. The clustering algorithm iteratively partitions the space into clusters without prior information about their number. At each iteration, the MVE estimator is applied several times with values of h decreasing from 0.5. A cluster is hypothesized for each ellipsoid. The shapes of these clusters are compared with shapes corresponding to a known unimodal distribution by the Kolmogorov-Smirnov test. The best fitting cluster is then removed from the space, and a new iteration starts. Constrained random sampling keeps the computation low. The clustering algorithm was successfully applied to several computer vision problems formulated in the feature space paradigm: multithresholding of gray level images, analysis of the Hough space, and range image segmentation.>

A novel multiresolution image analysis technique based on hierarchies of irregular tessellations generated in parallel by independent stochastic processes is presented. Like traditional image pyramids these hierarchies are constructed in a number of steps on the order of log(image-size) steps. However, the structure of a hierarchy is adapted to the image content and artifacts of rigid resolution reduction are avoided. Two applications of these techniques are presented: connected component analysis of labeled images and segmentation of gray level images. In labeled images, every connected component is reduced to a separate root, with the adjacency relations among the components also extracted. In gray level images the output is a segmentation of the image into a small number of classes as well as the adjacency graph of the classes.>

A systematic approach to least square approximation of images and of their derivatives is presented. Derivatives of any order can be obtained by convolving the image with a priori known filters. It is shown that if orthonormal polynomial bases are employed the filters have closed-form solutions. The same filter is obtained when the fitted polynomial functions have one consecutive degree. Moment-preserving properties, sparse structure for some of the filters, and the relationship to the Marr-Hildreth and Canny edge detectors are proven.>

Independent stochastic processes are used to generate in parallel irregular tessellations of an image. Recursive application of the procedure yields a multiresolution hierarchy adapted to the content of the image. The hierarchy is similar to traditional image pyramids: its height is of log (image size) order, but by being adapted to the input, it eliminates the artifacts frequently present in the latter. The output obtained at the apex of the hierarchy can be used for fast image analysis. The technique was applied to connected component labeling (labeled images) and segmentation (gray-level images).>

A blind noise variance algorithm that recovers the variance of noise in two steps is proposed. The sample variances are computed for square cells tessellating the noise image. Several tessellations are applied with the size of the cells increasing fourfold for consecutive tessellations. The four smallest sample variance values are retained for each tessellation and combined through an outlier analysis into one estimate. The different tessellations thus yield a variance estimate sequence. The value of the noise variance is determined from this variance estimate sequence. The blind noise variance algorithm is applied to 500 noisy 256*256 images. In 98% of the cases, the relative estimation error was less than 0.2 with an average error of 0.06. Application of the algorithm to differently sized images is also discussed.>

A novel hierarchical approach toward fast parallel processing of chain-codable contours is presented. The environment, called the chain pyramid, is similar to a regular nonoverlapping image pyramid structure. The artifacts of contour processing on pyramids are eliminated by a probabilistic allocation algorithm. Building of the chain pyramid is modular, and for different applications new algorithms can be incorporated. Two applications are described: smoothing of multiscale curves and gap bridging in fragmented data. The latter is also employed for the treatment of branch points in the input contours. A preprocessing module allowing the application of the chain pyramid to raw edge data is also described. The chain pyramid makes possible fast, O(log(image/sub -/size)), computation of contour representation in discrete scale-space.>

A method for parallel processing of chain-codable contours is described. The proposed hierarchical environment, called the chain pyramid, is similar to a regular nonoverlapping image pyramid structure. The chain pyramid makes possible the fast computation of contours. The artifacts of contour processing on pyramids are eliminated by a probabilistic allocation algorithm. Processing modules are developed for smoothing of curves, gap bridging in fragmented data, and treatment of branch points. Raw edge data are preprocessed before being input into the chain pyramid. Typical results are presented and briefly characterized.>

Construction of image pyramids is described as a two-di-mensional decimation process. Frequently employed generating kernels are compared to the optimal kernel that assures minimal information loss after the resolution reduction, i.e., the one corresponding to an ideal low pass filter. Physically realizable, optimal generating kernels are presented. The amount of computation required for generation of the image pyramid can be reduced significantly by employing half-band filters as components of the optimal kernel. Image pyramids generated by the optimal kernel show a better command of details than the ones generated by a simple 4 × 4 averaging, or a computationally equivalent kernel.