In many applications we want to find the number of clusters in a dataset. A common approach is to use a penalized k-means algorithm with an additive penalty term linear in the number of clusters. Obviously, the number of discovered clusters depends critically on the value of the coefficient of the penalty term, and an open problem is estimating the value of the coefficient in a principled manner. In this paper, we derive rigorous bounds for the coefficient of the additive penalty in k-means for ideal clusters. Although in practice clusters typically deviate from the ideal assumption, the ideal case serves as a useful guideline. Furthermore, we investigate k-means with multiplicative penalty, which generally produces a more reliable signature, compared to additive penalty, for the correct number of clusters in cases where the ideal cluster assumption holds. We also empirically investigate certain types of deviations from ideal cluster assumption. In such cases both types of penalties may suggest multiple, ambiguous solutions. We present a consensus-based approach to resolving these ambiguous solutions by combining the results of additive and multiplicative penalties.

Many digital signal and image processing methods involve computing the gradient of products of functions. However, the product rule for derivatives in continuous spaces, ∂(fg) = g∂f + f∂g, does not generally hold in discretized spaces. Hence, computing the gradient of products becomes ambiguous as the results depend on whether to treat the product fg as a single function or treat f and g as two separate functions and use the product rule. The two alternatives lead to different results, particularly for iterative solutions of differential equations since these small differences compound. Although this ambiguity is well-known, thus far a resolution has not been proposed in the literature. In this letter, we propose a mathematically rigorous procedure that selects the better alternative in the sense of yielding approximations that are closer to the continuous space results. As an example, we discuss the Perona-Malik anisotropic diffusion equation used in image processing.

We discuss the underlying physics of transport coefficients in the PDE image processing approach and present a more principled method for their construction. Transport coefficients in PDEs play important roles, e.g., the diffusion coefficient c in the Perona-Malik equation ∂u/∂t = ∇T(c∇u). Hence different models for c have been proposed in the literature. We present a physics-based method for constructing c and compare its performance with existing models. We also clarify an issue that arises in implementing the PDE approach. It is well-known that the product rule for derivatives in continuous spaces, namely, ∂(fg) = g∂f + f∂g, does not hold in discrete spaces. Thus computing such quantities as ∇T(c∇u) in spatially discretized images becomes ambiguous depending on which of the two alternatives we use, namely, whether to treat c∇u as a single function or treat c and ∇u as two functions and use the product rule. We examine this ambiguity and show which alternative is better in the sense of yielding approximations that are closer to the continuous space results.

We revisit the problem of matching a set of lines in the 2D image to a set of corresponding lines in the 3D model for the following reasons. (a) Existing algorithms that treat lines as infinitely long contain a flaw, namely, the solutions found are not invariant with respect to the choice of the coordinate frame. The source of this flaw is in the way lines are represented. We propose a frame-independent representation for sets of infinite lines that removes the non-invariance flaw. (b) Algorithms for finding the best rigid transform are nonlinear optimizations that are sensitive to initialization and may result in unreliable and expensive solutions. We present a new recipe for initialization that exploits the 3D geometry of the problem and is applicable to all algorithms that perform the matching in the 3D scene. Experiments show that with this initialization all algorithms find the best transform. (c) We present a new efficient matching algorithm that is significantly faster than existing alternatives, since it does not require explicit evaluation of the cost function and its derivatives.

The interest in face recognition is moving toward real-world applications and uncontrolled sensing environments. An important application of interest is automated surveillance, where the objective is to recognize and track people who are on a watchlist. For this open world application, a large number of cameras that are increasingly being installed at many locations in shopping malls, metro systems, airports, etc., will be utilized. While a very large number of people will approach or pass by these surveillance cameras, only a small set of individuals must be recognized. That is, the system must reject every subject unless the subject happens to be on the watchlist. While humans routinely reject previously unseen faces as strangers, rejection of previously unseen faces has remained a difficult aspect of automated face recognition. In this paper, we propose an approach motivated by human perceptual ability of face recognition which can handle previously unseen faces. Our approach is based on identifying the decision region(s) in the face space which belong to the target person(s). This is done by generating two large sets of borderline images, projecting just inside and outside of the decision region. For each person on the watchlist, a dedicated classifier is trained. Results of extensive experiments support the effectiveness of our approach. In addition to extensive experiments using our algorithm and prerecorded images, we have conducted considerable live system experiments with people in realistic environments.

Matching two sets of lines is a basic tool that has applications in many computer vision problems such as scene registration, object recognition, motion estimation, and others. Line sets may be composed of infinitely long lines or finite length line segments. Depending on line lengths, three basic cases arise in matching sets of lines: 1) finite-finite, 2) finite-infinite, and 3) infinite-infinite. Case 2 has not been treated in the literature. For Cases 1 and 3, existing algorithms for matching 3D line sets are not completely satisfactory in that they either solve special situations, or give approximate solutions, or may not converge, or are not invariant with respect to coordinate system transforms. In this paper, we present new algorithms that solve exactly all three cases for the general situation. The algorithms are provably convergent and invariant to coordinate transforms. Experiments with synthetic and real 3D image data are reported.

Methods for matching sets of 3D lines depend on whether line lengths are finite or infinite. In terms of line lengths, three basic cases arise in matching sets of lines: (1) finite to finite, (2) finite to infinite, and (3) infinite to infinite. For cases 1 and 2, which have not been treated in the literature, we present convergent iterative algorithms that (almost) always find the best match. For case 3, O.D. Faugeras and M. Hebert (FH) (1986) have proposed a popular iterative method that cannot be guaranteed to converge. We present an alternative approach that does converge. However, we also show that neither the FH solution, nor our solution is invariant with respect to coordinate transforms, which renders any best match meaningless. Thus, a satisfactory solution to case 3 does not yet exist. We discuss the underlying problem, which is the representation of infinite lines, and suggest alternatives that may lead to an invariant solution.

After the most prominent signal in an infrared image of the sky is extracted, the question is whether the signal corresponds to an aircraft. We present a new approach that avoids metric similarity measures and the use of thresholds, and instead attempts to learn similarity measures like those used by humans. In the absence of sufficient real data, the approach allows one to specifically generate an arbitrarily large number of training exemplars projecting near the classification boundary. Once trained on such a training set, the performance of our neural network-based system is comparable to that of a human expert and far better than a network trained only on the available real data. Furthermore, the results obtained are considerably better than those obtained using an Euclidean discriminator.

The problem of screening images of the skies to determine whether they contain aircraft or not is both of theoretical and practical interest. After the most prominent visual signal in the infrared image of the sky is extracted, the question is whether the signal is a correct match of an aircraft. Common approaches calculate the degree of similarity of the shape of the signal with a model aircraft using a similarity measure such as Euclidean distance, and make a decision based on whether the degree of similarity exceeds a (pre-specified) threshold. Our approach avoids metric similarity measures and the use of thresholds as it attempts to employ similarity measures used by humans. In the absence of sufficient real data, the approach allows to specifically generate an arbitrarily large number of training exemplars projecting near classification boundary. Once trained on such a training set, the performance of the neural network was comparable to that of a human expert, and far better than a network trained only on the available real data. Furthermore, the results were considerably better than those obtained using a Euclidean discriminator.

Image understanding often involves object recognition, where a basic question is how to decide whether a match is correct. Typically the best match (among a set of prestored objects) is assumed to be the correct match. This may work well in controlled environments (closed world). But, in uncontrolled environments (open world), the test object may not belong to the prestored object classes. In uncontrolled environments, a metric similarity measure (e.g. Euclidean) in conjunction with a threshold is used. However, based on psychophysical studies this is very different from, and far inferior to, human capabilities. To accept or reject a match, we introduce an approach that avoids metric similarity measures and the use of thresholds as it attempts to employ similarity measures used by humans. In the absence of sufficient real data, the approach allows to specifically generate an arbitrarily large number of training exemplars projecting near classification boundary. For aircraft detection, the performance of a neural network trained on such a training set, was comparable to that of a human expert, and far better than a network trained only on the available real data. Furthermore, the results were considerably better than those obtained using a Euclidean discriminator.

Quantization of the image plane into pixels results in the loss of the true location of features within pixels and introduces an error in any quantity computed from feature positions in the image. We derive closed-form, analytic expressions for the error distribution function, the mean absolute error (MAE), and the mean square error (MSE) due to triangular tessellation, for differentiable functions of an arbitrary number of independently quantized points, using a linear approximation of the function. These quantities are essential in examining the intrinsic sensitivity of image processing algorithms. Square and hexagonal pixels were treated in previous papers. An interesting result is that for all possible cases 0.99<D (T)/D S<1.13, where D (T) and D (S) are the MAE in triangular and square tessellations.

The acoustic lens is a high-resolution, forward-looking sonar for three dimensional (3-D) underwater imaging. We discuss processing the lens data for recreating and visualizing the scene. Acoustical imaging, compared to optical imaging, is sparse and low resolution. To achieve higher resolution, we obtain a denser sample by mounting the lens on a moving platform and passing over the scene. This introduces the problem of data fusion from multiple overlapping views for scene formation, which we discuss. We also discuss the improvements in object reconstruction by combining data from several passes over an object. We present algorithms for pass registration and show that this process can be done with enough accuracy to improve the image and provide greater detail about the object. The results of in-water experiments show the degree to which size and shape can be obtained under (nearly) ideal conditions.

We present a new algorithm for efficient matching of 3-D polygonal arcs. The algorithm is based on the decomposition of the arcs into sets of corresponding line segments with equal lengths. We derive a closed-form solution for the transformation that gives the best match between two sets of corresponding line segments (best in the sense of an L/sub 2/ norm distance measure), which enables the development of efficient arc matching algorithm. We apply this algorithm to the problem of finding a match between a short are and a piece of a long arc in real and synthetic images, and compare the results with alternative techniques in the literature.

Spatially quantized approximations of the Laplacian used in digital image processing are not rotationally invariant. We examine the anisotropy of 3/spl times/3 Laplacian operators for images quantized in square pixels, and derive, from optimizing criteria, the operator which has the minimum overall anisotropy.

In this paper, we consider two sets of corresponding 3D line segments of equal length. We derive a closed-form solution for the coordinate transform (rotation and translation) that gives the best match between the two sets; best in the sense of a least-squares distance measure between the sets. We use these results as the basis to construct efficient algorithms for solving other problems in computer vision. Specifically, we address the problem of matching polygonal arcs, that is, the problem of finding a match between a short arc and a piece of long arc.

The authors develop mathematical tools for estimating quantization error in hexagonal sensory configurations. These include analytic expressions for the average error and the error distribution of a function of an arbitrary number of independently quantized variables. These two quantities are essential for assessing the reliability of a given algorithm. They can also be used to compare the relative sensitivity of a particular algorithm to quantization error for hexagonal and other spatial samplings, e.g., square, and can have an impact on sensor design. Furthermore, it is shown that the ratio of hexagonal error to square error is bounded between 0.90 and 1.05.>

Reconstruction of 3D scenes using data from an acoustic imaging sonar is addressed. The acoustic lens is described, and issues concerning underwater 3D scene reconstruction from the lens data are examined. Two methods for visualizing objects in an acoustic snapshot of the ocean are discussed: mathematical morphology and a synthesis of 3D digital imaging with volume rendering.>

A class of inverse problems in remote sensing can be characterized byQ=F(x), whereFis a nonlinear and noninvertible (or hard to invert) operator, and the objective is to infer the unknowns,x, from the observed quantities,Q. Since the number of observations is usually greater than the number of unknowns, these problems are formulated as optimization problems, which can be solved by a variety of techniques. The feasibility of neural networks for solving such problems is presently investigated. As an example, the problem of finding the atmospheric ozone profile from measured ultraviolet radiances is studied

A scheme is developed to match range images in an environment where distinctive features are scarce. When each image overlaps with several other images, the match must also be performed at the global level. This is particularly challenging, because of the possibility of bending and compression in range images. The primitives used for local matching contours of constant range which are extracted from data are represented by means of a modified chain-code method. All best matches of pairs of contours are considered tentative until their geometrical implications are evaluated and a consistent majority has emerged. To do global matching a cost function is constructed and minimized. Terms contributing to the cost include violation of local matches as well as compression and bending in range images. The present global scheme is valid for any set of multiple overlapping range images, whether they contain distinctive features or not. This scheme has been used to map the floor of the ocean, where the range data are obtained by a multibeam echo-sounder system.>

Square and hexagonal spatial samplings, because of their processing ease, are used most widely in image and signal processing. The authors develop mathematical tools for estimating quantization error in hexagonal sensory configurations. These include analytic expressions for the average error and the error distribution of a function of an arbitrarily large number of hexagonally quantized variables. The two quantities (the average error and the error distribution) are essential in assessing the reliability of a given algorithm. The corresponding expressions for square spatial sampling are presented for comparison; they can be used to determine which sampling technique would result in less quantization error for a particular algorithm. Such a comparison is important due to the paramount role that quantization error plays in computational approaches to computer vision. Some general observations in regard to the relative accuracy of hexagonal vs. square quantization are also presented.>

Due to the important role that digitization error plays in the field of computer vision, a careful analysis of its impact on the computational approaches used in the field is necessary. The authors develop the mathematical tools for the computation of the average (or expected) error due to quantization. They can be used in estimating the actual error occurring in the implementation of a method. Also derived is the analytic expression for the probability density of error distribution of a function of an arbitrarily large number of independently quantized variables. The probability that the error of the function will be within a given range can thus be obtained accurately. The tools developed can be used in the analysis of the applicability of a given algorithm, hence revealing the intrinsic limitations of the approach.>

In fitting a straight line to a noisy image, the least-squares method becomes highly unreliable either when the noise distribution is nonnormal or when it is contaminated by outliers. The authors propose a nonparametric method, the median of the intercepts, to overcome these difficulties. This method is free of assumptions about the noise distribution and insensitive to outliers, and it does not require quantization of the parameter space. Thus, unlike the Hough transform, its outcome does not depend on the bin size. The method is efficient and its implementation does not involve practical difficulties such as local minima or poor convergence of iterative procedures.>

The authors develop the mathematical tools for the computation of the average error due to quantization. They can be used in estimating the actual error occurring in the implementation of a method. Also derived is the analytic expression for the probability density of error distribution of a function of an arbitrarily large number of independently quantized variables. The probability of the error of the function to be within a given range can thus be obtained accurately. In analyzing the applicability of an approach; it is necessary to determine whether the approach is capable of withstanding the quantization error. If it is not, then regardless of the accuracy with which the experiments are carried out, the approach will yield unacceptable results. The tools developed can be used in the analysis of the applicability of a given algorithm, hence revealing the intrinsic limitations of the approach.>