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.

This is a study on the development of a road following vision-based guidance system for unmanned air vehicles (UAV) in real world applications. Currently, autonomous navigation requires the use of GPS. In many applications, however, dependence on GPS is undesirable. GPS signals are weak and can be jammed easily. Also, GPS waypoints may not be up-to-date. In recent years, vision-based navigation has been gaining popularity. Vision-based guidance requires existence of visible paths or extended landmarks for air vehicles to detect and follow. Roads are the most commonly available path to follow. Moreover, the abundance of events that happen along roads make them appealing subjects of surveillance. Many road detection (single images) and road tracking (videos) algorithms have been proposed in the literature. Fast detection and tracking has been the emphasis of those intended for UAVs. Due to the complexity of road detection, we not only need advanced software but also the most effective sensors. In this paper, we propose a road following algorithm that uses both RGB camera and hyperspectral sensor and report the results of actual test flights conducted in different locations and different seasons.

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.

Object extraction from an IR image background is of great interest both to the military and the commercial sector. A convenient and popular approach to object extraction is image thresholding. In this paper, we describe a new and easy to implement approach for extracting object(s) in single frame IR images, which has many similarities to image thresholding. Both on the basis of theoretical considerations and experimental results, however, our approach appears to be noticeably more dependable than image thresholding for IR images.

Matching sets of 3D lines is a basic tool in image registration, recognition, and other applications. In terms of line lengths, three basic cases arise in matching two sets of lines: (1) finite-finite; (2) finite-infinite; (3) infinite-infinite. Cases 1 and 2 have not been treated in the literature. We present a convergent, iterative algorithm that solves these two cases. Extensive tests show that the algorithm almost always converges to the best match, particularly when the hypothesized line correspondences are correct, or when noise does not substantially destroy the similarity of the two sets. Case 3 has been addressed by O.D. Faugeras and M. Hebert (see Int. J. Robotics Res., vol.5, no.3, p.27-52, 1986). They present an iterative technique that cannot be guaranteed to converge. To solve this case, we present a new method that converges. However, more importantly, we show that neither method is invariant to translation of the coordinate system. Therefore, a satisfactory solution for case 3 does not yet exist.

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.

Laplacian operators used in the literature for digital image processing are not rotationally invariant. We examine the anisotropy of 3 x 3 Laplacian operators for images quantized in square pixels, and find the operator which has the minimum overall anisotropy.

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

A scheme is developed to register range images in an environment where distinctive features are scarce. Another issue addressed here is conflicting situations that may arise from pair-wise registration of multiple overlapping range images whether or not they contain distinctive features. There can be two causes for this: (a) error in individual registrations or (b) compression or bending in range images. The authors develop a scheme for resolving such conflicts for the case where range images share a common reference surface, i.e. when the transformation matrix between two overlapping images involves only three components: two translations and one rotation. The authors implemented this scheme to map the floor of the ocean, where the range data is obtained by a multibeam echo-sounder system installed aboard a sailing ship producing multiple overlapping range images. The system developed is the first automated system for correctly registered mapping of the ocean floor; it is efficient and robust.>

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 present an algorithm for the calibration of a stereo system with small relative angles in an uncontrolled environment. This algorithm has two advantages: (1) it is more accurate than the existing algorithms in the computer vision and photogrammetry literatures; and (2) it provides useful insight into the problem of camera calibration and relative orientation. This is done by deriving explicit analytical solutions for the relative pan, tilt, and roll angles in terms of the world pan angle (gaze angle) and the coordinates of the feature points used in their computations. These solutions allow a better understanding of the problem of calibration in general by providing insight as to how errors due to quantization and uncertainty in the location of image centers affect the computation of rotation angles. The findings are likely to be of use even when the relative rotation angles are not small.>

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