Bregman divergences generalize measures such as the squared Euclidean distance and the KL divergence, and arise throughout many areas of machine learning. In this paper, we focus on the problem of approximating an arbitrary Bregman divergence from supervision, and we provide a well-principled approach to analyzing such approximations. We develop a formulation and algorithm for learning arbitrary Bregman divergences based on approximating their underlying convex generating function via a piecewise linear function. We provide theoretical approximation bounds using our parameterization and show that the generalization error $O_p(m^{-1/2})$ for metric learning using our framework matches the known generalization error in the strictly less general Mahalanobis metric learning setting. We further demonstrate empirically that our method performs well in comparison to existing metric learning methods, particularly for clustering and ranking problems.

Efficient graph-cut methods have been used with great success for labeling and denoising problems occurring in computer vision. Unfortunately, the presence of linear image mappings has prevented the use of these techniques in most discrete-amplitude image reconstruction problems. In this paper, we develop a graph-cut based framework for the direct solution of discrete amplitude linear image reconstruction problems cast as regularized energy function minimizations. We first analyze the structure of discrete linear inverse problem cost functions to show that the obstacle to the application of graph-cut methods to their solution is the variable mixing caused by the presence of the linear sensing operator. We then propose to use a surrogate energy functional that overcomes the challenges imposed by the sensing operator yet can be utilized efficiently in existing graph-cut frameworks. We use this surrogate energy functional to devise a monotonic iterative algorithm for the solution of discrete valued inverse problems. We first provide experiments using local convolutional operators and show the robustness of the proposed technique to noise and stability to changes in regularization parameter. Then we focus on nonlocal, tomographic examples where we consider limited-angle data problems. We compare our technique with state-of-the-art discrete and continuous image reconstruction techniques. Experiments show that the proposed method outperforms state-of-the-art techniques in challenging scenarios involving discrete valued unknowns.

In this paper we propose a graph cut method for solving a multi-label linear inverse problem with an arbitrary system matrix. Graph cuts are efficient methods for solving pixel-labeling and early vision problems. Energy function minimization problems that occur in image denoising are easily solved by graph cut techniques. However, applying graph cuts to inverse problems which have a non-diagonal system matrix becomes challenging, as a data cost of one pixel depends on intensities of other pixels. Such cost functions are not graph representable. In this paper, we propose an iterative method for minimization of energy functions occurring in inverse problems, where a graph-representable Taylor approximation of the original cost function is rapidly solved via a graph cut method at each iteration.

Visual surveillance applications such as object identification, object tracking, and anomaly detection require reliable motion detection as an initial processing step. Such a detection is often accomplished by means of background subtraction which can be as simple as thresholding of intensity difference between movement-free background and current frame. However, more effective background subtraction methods employ probabilistic modeling of the background followed by probability thresholding. In this case, the balance between false positives and false negatives (misses) is controlled by a threshold that needs to be adjusted heuristically depending on object sparsity. In this paper, we propose a different detection method that is based on false discovery rate control, a multiple-comparison procedure that applies thresholding in significance-score rather than probability space. The proposed approach allows explicit control of false positives and automatically adapts to object sparsity. The new method offers a qualitative improvement in real scenarios as well as a measurable performance gain over non-adaptive techniques when tested on synthetic sequences.

In this paper, we develop a new unified approach for laser radar range anomaly suppression, range profiling, and segmentation. This approach combines an object-based hybrid scene model for representing the range distribution of the field and a statistical mixture model for the range data measurement noise. The image segmentation problem is formulated as a minimization problem which jointly estimates the target boundary together with the target region range variation and background range variation directly from the noisy and anomaly-filled range data. This formulation allows direct incorporation of prior information concerning the target boundary, target ranges, and background ranges into an optimal reconstruction process. Curve evolution techniques and a generalized expectation-maximization algorithm are jointly employed as an efficient solver for minimizing the objective energy, resulting in a coupled pair of object and intensity optimization tasks. The method directly and optimally extracts the target boundary, avoiding a suboptimal two-step process involving image smoothing followed by boundary extraction. Experiments are presented demonstrating that the proposed approach is robust to anomalous pixels (missing data) and capable of producing accurate estimation of the target boundary and range values from noisy data.

Summary form only given. Despite significant recent progress in automatic target exploitation (ATE) and recognition (ATR), current ATE systems do not meet the requirements of modern battlefield environments. Next generation ATE systems must actively manage sensor resources, aggregate sensed information across multiple platforms and diverse signaling modalities, and adapt to increasingly agile adversaries and operating conditions. Thus, the fundamental research challenge is to develop an integrated systems theory that jointly treats information fusion, control, and adaptation using multiple, dynamic multimodal sensor platforms in resource constrained environments.

In this paper, we present a new approach for analysis of images for text-localization and extraction. Our approach puts very few constraints on the font, size and color of text and is capable of handling both scene text and artificial text well. In this paper, we exploit two well-known features of text: approximately constant stroke width and local contrast, and develop a fast, simple, and effective algorithm to detect character strokes. We also show how these can be used for accurate extraction and motivate some advantages of using this approach for text localization over other color-space segmentation based approaches. We analyze the performance of our stroke detection algorithm on images collected for the robust-reading competitions at ICDAR 2003.

We consider the problem of distributed target tracking of a linear dynamical system via networked sensors. Our setup consists of a set of sensors connected to a fusion center by means of communication links. Unreliable communication channels leads to communication delays and loss of information. To address this problem we model the arrival of messages from the sensors to the fusion center by a random process. The question arises as to what messages to encode for the fusion center. One possibility that has recently received much attention is to transmit local observations to the fusion center, which then fuses these intermittent observations through Kalman filtering techniques. In contrast we develop a scheme for fusion of intermittent local state estimates. The salient aspects of the scheme are: (a) efficiency, i.e., covariance of local estimate is no larger than covariance of observation; (b) robustness, i.e., the error covariance is bounded with high probability even under vanishing link-connectivity. In contrast, fusion of intermittent observations leads to unbounded errors even for moderate values for link-connectivity; (c) scalable performance, i.e., a K-node sensor network with K guaranteed communication links is inferior to an N-node sensor network with K functioning communication links on average

An important problem during industrial machining operations is the detection and classification of tool wear. Past research in this area has demonstrated the effectiveness of various feature sets and binary classifiers. Here, the goal is to develop a classifier which makes use of the dynamic characteristics of tool wear in a metal milling application and which replaces the standard binary classification result with two outputs: a prediction of the wear level (quantized) and a gradient measure that is the posterior probability (or confidence) that the tool is worn given the observed feature sequence. The classifier tracks the dynamics of sensor data within a single cutting pass as well as the evolution of wear from sharp to dull. Different alternatives to parameter estimation with sparsely-labeled training data are proposed and evaluated. We achieve high accuracy across changing cutting conditions, even with a limited feature set drawn from a single sensor.

In this paper, we develop a new approach to tomographic reconstruction problems based on geometric curve evolution techniques. We use a small set of texture coefficients to represent the object and background inhomogeneities and a contour to represent the boundary of multiple connected or unconnected objects. Instead of reconstructing pixel values on a fixed rectangular grid, we then find a reconstruction by jointly estimating these unknown contours and texture coefficients of the object and background. By designing a new "tomographic flow", the resulting problem is recast into a curve evolution problem and an efficient algorithm based on level set techniques is developed. The performance of the curve evolution method is demonstrated using examples with noisy limited-view Radon transformed data and noisy ground-penetrating radar data. The reconstruction results and computational cost are compared with those of conventional, pixel-based regularization methods. The results indicate that the curve evolution methods achieve improved shape reconstruction and have potential computation and memory advantages over conventional regularized inversion methods.

We develop a variational method for dynamic tomography using curve evolution with spatial-temporal regularization. We take into account both the dynamics of the object boundaries as well as the dynamics of region intensities. These quantities are jointly estimated through minimization of an appropriately defined energy function. The temporal correlation of the object boundary curves are included through a weighted area difference distance measure between curves. The intensity dynamics are captured through a simple autoregressive model. Curve evolution methods are used to solve for the optimal reconstruction, which are implemented with efficient level set techniques. The strength of this approach is demonstrated through the successful reconstruction of an object sequence based on observations of only a single projection angle over time.

In this paper, we present a new technique for determining the surface profile of a moderately rough interface between air and a homogeneous dielectric half-space. Based on sparsely sampled step-frequency ground penetrating radar measurements, the proposed inversion scheme uses a quasi-ray Gaussian beam fast forward model, coupled with a low-order parameterization of the surface profile in terms of B-splines. The profile estimation problem is posed as a parameter optimization problem, which is solved using a multiresolution continuation method via frequency hopping. Numerical experiments establish that the algorithm is efficient and yields accurate reconstructions throughout most of the illuminated region even in noisy environments, losing accuracy only in regions with very weak illumination.

In this paper, we develop a new active contour model for image segmentation using adaptive flows. This active contour model can be derived from minimizing a limiting form of the Mumford-Shah functional, where the segmented image is assumed to consist of piecewise constant regions. This paper is an extension of an active contour model developed by Chan-Vese. The segmentation method proposed in this paper adaptively estimates mean intensities for each separated region and uses a single curve to capture multiple regions with different intensities. The class of imagery that our new active model can handle is greater than the bimodal images. In particular, our method segments images with an arbitrary number of intensity levels and separated regions while avoiding the complexity of solving a full Mumford-Shah problem. The adaptive flow developed in this paper is easily formulated and solved using level set methods. We illustrate the performance of our segmentation methods on images generated by different modalities.

In this paper, we develop a new approach to tomographic reconstruction problems based on geometric curve evolution techniques. We use a low order parametric model to describe the shape and texture of the object support as well as the background. This model uses a set of texture coefficients to represent the object and background inhomogeneities and a contour to represent the boundary of multiple connected or unconnected objects. The problem of determining the unknown contour and texture coefficients of the object and background medium is then formulated as a non-linear estimation problem. By designing a new, "tomographic flow", the resulting problem is recast into a curve evolution problem and an efficient algorithm based on level set techniques is developed. The performance of the curve evolution method is demonstrated using examples with noisy Radon transformed data and noisy ground penetrating radar data. The reconstruction results and computational cost are compared with those of conventional regularization methods. The results indicate that our curve evolution methods achieve improved shape reconstruction with reduced computation requirements.

In this paper, we present a novel approach for frontal face detection in gray-scale images. We represent both faces and clutter by using two-dimensional wavelet decomposition. To characterize the statistical dependency between different levels of wavelet, we introduce a Hidden Markov Model (HMM), in which a number of discrete states at each level capture the diversity of faces as well as clutter. Our experiments indicate that the proposed algorithm outperforms conventional template-based methods such as matched filter and eigenface methods.

The estimation of local arterial structure and vascular deformation is hampered by regions of poor contrast and by the presence of ultrasound imaging artifacts such as speckle noise and specular reflections. Conventional methods for boundary extraction and velocity estimation can exhibit poor performance under these conditions. We demonstrate a new multi-stage processing scheme which uses a directionally sensitive variational energy segmentation to suppress noise and preserve image boundaries for robust extraction of the vessel contour. This contour information is used to generate a motion region-of-interest (mROI) for a modified optical flow scheme which estimates local boundary motion based only on image data lying within the mROI.

We develop a statistical approach for imaging weak-contrast objects buried under a rough soil/air interface using data from a ground penetrating radar array. The imaging system uses short-pulse electromagnetic plane waves as illumination signals. We develop an approximate physical model based on a flat soil/air interface and weak-scattering to relate the collected data to the buried objects. This model uses ray optics to represent the soil/air interface, and a Born approximation to model the weak contrast backscattering from the buried objects. In order to form images of objects buried under rough soil/air interfaces, we embed our model in a statistical framework to account for modeling errors and ill-posedness. The statistical framework leads to optimal reconstruction algorithms for buried objects. We evaluate the performance of the reconstruction algorithms for different soil/air interface realizations using data generated from detailed nonlinear electromagnetic simulations of ground penetrating radar.

We develop a new geometric curve evolution approach to tomographic reconstruction problems including multiple objects having different levels of intensity, and background with varying intensity. We use two contours to represent the boundaries of distinct object regions with different intensity levels and a set of basis functions and expansion coefficients to describe the background. By designing coupled "tomographic flows", the problem of estimating the two contours and intensity coefficients is recast into a curve evolution problem. A new "repelling" force between the two coupled curves is proposed for the reconstruction algorithms to accelerate convergence. The performance of the coupled curve evolution method is demonstrated via a Radon inversion example. The results show that our curve evolution method achieves improved shape reconstruction over comparable regularization techniques.

This paper presents a systematic and computable method for choosing the regularization parameter appearing in Tikhonov-type regularization based on non-quadratic regularizers. First, we extend the notion of the L-curve, originally defined for quadratically regularized problems, to the case of non-quadratic functions. We then associate the optimal value of the regularization parameter for these non-quadratic problems with the corner of the resulting generalized L-curve. We identify the corner of this L-curve as the point of tangency between a straight line of arbitrary slope and the L-curve. This definition results in a corresponding algebraic equation which the optimal regularization parameter must satisfy. This algebraic equation naturally leads to an iterative algorithm for the optimal value of the regularization parameter. The convergence of this iterative algorithm is established. Simulation results confirm that the proposed method yields values of the regularization parameters that result in good reconstructions for non-quadratic problems.

We examine the problem of edge-preserving smoothing from the perspective of explicit regions rather than the explicit edge approach of Shah (1996), Ambrosio and Tortorelli (1992), and others. We reformulate Mumford and Shah's (1985) original edge-preserving smoothing functional in terms of regions rather than their boundaries. We then introduce an energy functional that is similar to Ambrosio and Tortorelli's continuous approximation of Mumford and Shah's functional, but uses a region label function rather than an edge-strength function. We also show that the spatially discretized version of our energy functional results from a particular continuation method as applied to Mumford and Shah's energy functional. We base this continuation method on Hummel and Zucker's (1983) relaxation labeling approach to solving discrete Markov random field labeling problems. We demonstrate this approach for a test case.

Many large multidimensional space-time signal processing and data inversion applications (e.g. deconvolution) require some form of regularization to extract meaningful information. A popular approach to regularizing such problems in a statistical context is via a Gauss-Markov random field (GMRF) prior model in a maximum a posteriori (MAP) estimation framework. While providing good reconstructions, the high dimensionality of these problems can lead to prohibitive computational constraints which limit their practical applicability, particularly in real or near-real time applications. It has been shown that GMRF models possess a particular recursive structure. Conversely, complementary work in suboptimal filtering has been based on reduced order GMRF modeling. In, this work, we combine these two results to present a suboptimal filter design which repeatedly takes advantage of this recursive GMRF structure to subdivide a large problem into a series of smaller, more tractable problems. In this way we present a method for approximate, model-based, recursive solution to such high dimensional problems based on their inherent recursive structure.

The author formulates and solves a class of dynamic search problems for obtaining the closed-loop sequence of measurements which, under a symmetry condition on the probability distribution of the measurements, optimally selects among many candidate hypotheses. Under this condition, the optimal strategy is characterized by a simple index rule which depends only on the ordering of the conditional probabilities of the hypotheses given the past measurements. The author proves that this index rule is optimal independent of the number of measurements to be taken. The author illustrates with numerical examples that, when the symmetry conditions are relaxed, the index policies are suboptimal, but achieve performance which is close to optimal. The results can be applied to solve complex problems in fault diagnosis and search with unreliable tests.>

In this paper, we discuss the parallel asynchronous implementation of the Hungarian method for solving the classical assignment problem. Multiple augmentations and price rises are simultaneously attempted starting from several unassigned sources and using possibly outdated price and assignment information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show the validity of this algorithm and we demonstrate computationally that an asynchronous implementation is often faster than its synchronous counterpart. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Consideration is given to distributed dynamic resource allocation within a two-person team. Having different but overlapping responsibilities, two geographically separated human decision-makers (DMs) are to process multiple types of randomly arriving tasks with a set of renewable resources. To maximize the team reward for task processing, the DMs must coordinate on the assignment of common tasks (tasks of joint responsibility) and on the transfer of resources. A normative-descriptive approach is adopted to describe the human decision-making process in the above setting. The approach starts with a normative model that predicts the team's optimal decision-making and a human-in-the-loop experiment that generates experimental data. Human limitations and cognitive biases are then identified to explain differences between model predictions and experimental data. Incorporating human limitations and cognitive biases into the normative model, a normative-descriptive model is obtained. This model matches experimental data in almost all measures and provides insights to human decision-making behavior.>

A model of human decision-making in distributed detection problems is developed and described. The model, called TOSCA, involves a team of two decision-makers (DMs), a primary DM and a consultant, whose goal is to solve a sequential binary hypothesis-testing problem. The model is based on the work of J.D. Papastavrou and M. Athans (1986), which modeled the primary DM and the consultant as members of a team with a common goal. TOSCA extends their work by including other features involved in distributed detection and team decision-making. TOSCA extends the model of Papastavrou and Athans by not only developing a normative mathematical formulation with these features, but also designing and running an experimental paradigm with human subjects to generate descriptive data. After analyzing how humans deviated from predicted normative behavior, the parameters in the normative model were adjusted to reflect human statistical misperception, resulting in a normative-descriptive model.>

Martingale decomposition techniques are used to derive Markovian models for the error in smoothed estimates of processes described by linear models driven by white noise. These models, together with some simple Hilbert space decomposition ideas, provide a simple unified framework for examining a variety of problems involving the efficient assimilation of spatial data, which we refer to as mapping problems. Algorithms for several different mapping problems are derived. A specific example of map updating for a two-dimensional random field is included.

A research effort is summarized which addresses some of the current problems in interfacing systems theory and reliability. Reliability is roughly the probability that a system will perform according to specifications for a given amount of time. The reliability of a system depends on the structure of its components. Systems theory and control theory deal with the response characteristics of a system, which depend on the system dynamics. The concepts necessary to unify the structural and the dynamic properties of a system are defined. The result is a definition of what constitutes a reliable system, from the viewpoint of systems theory, and a methodology which can be used to determine if a given design allows a reliable control system design.

Given a diffusion process on{\bf R}^{n}described by a stochastic differential equation forward in time, we develop a corresponding stochastic differential equation in reverse time which yields the same sample paths. This stochastic differential equation can be used in problems of estimation and smoothing.