Modeling multivariate time series is a well-established problem with a wide range of applications from healthcare to financial markets. It, however, is challenging as it requires methods to (1) have high expressive power of representing complicated dependencies along the time axis to capture both long-term progression and seasonal patterns, (2) capture the inter-variate dependencies when it is informative, (3) dynamically model the dependencies of variate and time dimensions, and (4) have efficient training and inference for very long sequences. Traditional State Space Models (SSMs) are classical approaches for univariate time series modeling due to their simplicity and expressive power to represent linear dependencies. They, however, have fundamentally limited expressive power to capture non-linear dependencies, are slow in practice, and fail to model the inter-variate information flow. Despite recent attempts to improve the expressive power of SSMs by using deep structured SSMs, the existing methods are either limited to univariate time series, fail to model complex patterns (e.g., seasonal patterns), fail to dynamically model the dependencies of variate and time dimensions, and/or are input-independent. We present Chimera, an expressive variation of the 2-dimensional SSMs with careful design of parameters to maintain high expressive power while keeping the training complexity linear. Using two SSM heads with different discretization processes and input-dependent parameters, Chimera is provably able to learn long-term progression, seasonal patterns, and desirable dynamic autoregressive processes. To improve the efficiency of complex 2D recurrence, we present a fast training using a new 2-dimensional parallel selective scan. Our experimental evaluation shows the superior performance of Chimera on extensive and diverse benchmarks, including ECG and speech time series classification, long-term and short-term time series forecasting, and time series anomaly detection.

Advances in the field of visual-language contrastive learning have made it possible for many downstream applications to be carried out efficiently and accurately by simply taking the dot product between image and text representations. One of the most representative approaches proposed recently known as CLIP has quickly garnered widespread adoption due to its effectiveness. CLIP is trained with an InfoNCE loss that takes into account both positive and negative samples to help learn a much more robust representation space. This paper however reveals that the common downstream practice of taking a dot product is only a zeroth-order approximation of the optimization goal, resulting in a loss of information during test-time. Intuitively, since the model has been optimized based on the InfoNCE loss, test-time procedures should ideally also be in alignment. The question lies in how one can retrieve any semblance of negative samples information during inference in a computationally efficient way. We propose Distribution Normalization (DN), where we approximate the mean representation of a batch of test samples and use such a mean to represent what would be analogous to negative samples in the InfoNCE loss. DN requires no retraining or fine-tuning and can be effortlessly applied during inference. Extensive experiments on a wide variety of downstream tasks exhibit a clear advantage of DN over the dot product on top of other existing test-time augmentation methods.

We introduce a way to learn to estimate a scene representation from a single image by predicting a low-dimensional subspace of optical flow for each training example, which encompasses the variety of possible camera and object movement. Supervision is provided by a novel loss which measures the distance between this predicted flow subspace and an observed optical flow. This provides a new approach to learning scene representation tasks, such as monocular depth prediction or instance segmentation, in an unsupervised fashion using in-the-wild input videos without requiring camera poses, intrinsics, or an explicit multi-view stereo step. We evaluate our method in multiple settings, including an indoor depth prediction task where it achieves comparable performance to recent methods trained with more supervision. Our project page is at https://dimensions-of-motion.github.io/.

Aggressive data augmentation is a key component of the strong generalization capabilities of Vision Transformer (ViT). One such data augmentation technique is adversarial training (AT); however, many prior works [28,45] have shown that this often results in poor clean accuracy. In this work, we present pyramid adversarial training (PyramidAT), a simple and effective technique to improve ViT's overall performance. We pair it with a “matched” Dropout and stochastic depth regularization, which adopts the same Dropout and stochastic depth configuration for the clean and adversarial samples. Similar to the improvements on CNNs by AdvProp [61] (not directly applicable to ViT), our pyramid adversarial training breaks the trade-off between in-distribution accuracy and out-of-distribution robustness for ViT and related architectures. It leads to 1.82% absolute improvement on ImageNet clean accuracy for the ViT-B model when trained only on ImageNet-1K data, while simultaneously boosting performance on 7 ImageNet ro-bustness metrics, by absolute numbers ranging from 1.76% to 15.68%. We set a new state-of-the-art for ImageNet-C (41.42 mCE), ImageNet-R (53.92%), and ImageNet-Sketch (41.04%) without extra data, using only the ViT-B/16 backbone and our pyramid adversarial training. Our code is publicly available at pyramidat.github.io.

Image extrapolation extends an input image beyond the originally-captured field of view. Existing methods struggle to extrapolate images with salient objects in the foreground or are limited to very specific objects such as humans, but tend to work well on indoor/outdoor scenes. We introduce OCONet (Object COmpletion Networks) to extrapolate foreground objects, with an object completion network conditioned on its class. OCONet uses an encoder-decoder architecture trained with adversarial loss to predict the object’s texture as well as its extent, represented as a predicted signed-distance field. An independent step extends the background, and the object is composited on top using the predicted mask. Both qualitative and quantitative results show that we improve on state-of-the-art image extrapolation results for challenging examples.

Synthetic datasets play a critical role in pre-training CNN models for optical flow, but they are painstaking to generate and hard to adapt to new applications. To automate the process, we present AutoFlow, a simple and effective method to render training data for optical flow that optimizes the performance of a model on a target dataset. AutoFlow takes a layered approach to render synthetic data, where the motion, shape, and appearance of each layer are controlled by learnable hyperparameters. Experimental results show that AutoFlow achieves state-of-the-art accuracy in pre-training both PWC-Net and RAFT. Our code and data are available at autoflow-google.github.io.

Time-to-event analysis is an important statistical tool for allocating clinical resources such as ICU beds. However, classical techniques like the Cox model cannot directly incorporate images due to their high dimensionality. We propose a deep learning approach that naturally incorporates multiple, time-dependent imaging studies as well as non-imaging data into time-to-event analysis. Our techniques are bench-marked on a clinical dataset of 1,894 COVID-19 patients, and show that image sequences significantly improve predictions. For example, classical time-to-event methods produce a concordance error of around 30-40% for predicting hospital admission, while our error is 25% without images and 20% with multiple X-rays included. Ablation studies suggest that our models are not learning spurious features such as scanner artifacts and that models which use multiple images tend to perform better than those which only use one. While our focus and evaluation is on COVID-19, the methods we develop are broadly applicable.

While Markov Random Fields (MRFs) are widely used in computer vision, they present a quite challenging inference problem. MRF inference can be accelerated by preprocessing techniques like Dead End Elimination (DEE) [8] or QPBO-based approaches [18, 24, 25] which compute the optimal labeling of a subset of variables. These techniques are guaranteed to never wrongly label a variable but they often leave a large number of variables unlabeled. We address this shortcoming by interpreting pre-processing as a classification problem, which allows us to trade off false positives (i.e., giving a variable an incorrect label) versus false negatives (i.e., failing to label a variable). We describe an efficient discriminative rule that finds optimal solutions for a subset of variables. Our technique provides both per-instance and worst-case guarantees concerning the quality of the solution. Empirical studies were conducted over several benchmark datasets. We obtain a speedup factor of 2 to 12 over expansion moves [4] without preprocessing, and on difficult non-submodular energy functions produce slightly lower energy.

Markov Random Fields (MRFs) are a widely used graphical model, but the inference problem is NP-hard. For first-order MRFs with binary labels, Dead End Elimination (DEE) [7] and QPBO [2, 14] can find the optimal labeling for some variables, the much harder case of larger label sets has been addressed by Kovtun [16, 17] and related methods [12, 23, 24, 25], which impose substantial computational overhead. We describe an efficient algorithm to correctly label a subset of the variables for arbitrary MRFs, with particularly good performance on binary MRFs. We propose a sufficient condition to check if a partial labeling is optimal, which is a generalization of DEE's purely local test. We give a hierarchy of relaxations that provide larger optimal partial labelings at the cost of additional computation. Empirical studies were conducted on several benchmarks, using expansion moves [4] for inference. Our algorithm runs in a few seconds, and improves the speed of MRF inference with expansion moves by a factor of 1.5 to 12.

Higher-order Markov Random Fields, which can capture important properties of natural images, have become increasingly important in computer vision. While graph cuts work well for first-order MRF's, until recently they have rarely been effective for higher-order MRF's. Ishikawa's graph cut technique [1], [2] shows great promise for many higher-order MRF's. His method transforms an arbitrary higher-order MRF with binary labels into a first-order one with the same minima. If all the terms are submodular the exact solution can be easily found; otherwise, pseudoboolean optimization techniques can produce an optimal labeling for a subset of the variables. We present a new transformation with better performance than [1], [2], both theoretically and experimentally. While [1], [2] transforms each higher-order term independently, we use the underlying hypergraph structure of the MRF to transform a group of terms at once. For n binary variables, each of which appears in terms with k other variables, at worst we produce n non-submodular terms, while [1], [2] produces O(nk). We identify a local completeness property under which our method perform even better, and show that under certain assumptions several important vision problems (including common variants of fusion moves) have this property. We show experimentally that our method produces smaller weight of non-submodular edges, and that this metric is directly related to the effectiveness of QPBO [3]. Running on the same field of experts dataset used in [1], [2] we optimally label significantly more variables (96 versus 80 percent) and converge more rapidly to a lower energy. Preliminary experiments suggest that some other higher-order MRF's used in stereo [4] and segmentation [5] are also locally complete and would thus benefit from our work.

Graph cuts method such as α-expansion [4] and fusion moves [22] have been successful at solving many optimization problems in computer vision. Higher-order Markov Random Fields (MRF's), which are important for numerous applications, have proven to be very difficult, especially for multilabel MRF's (i.e. more than 2 labels). In this paper we propose a new primal-dual energy minimization method for arbitrary higher-order multilabel MRF's. Primal-dual methods provide guaranteed approximation bounds, and can exploit information in the dual variables to improve their efficiency. Our algorithm generalizes the PD3 [19] technique for first-order MRFs, and relies on a variant of max-flow that can exactly optimize certain higher-order binary MRF's [14]. We provide approximation bounds similar to PD3 [19], and the method is fast in practice. It can optimize non-submodular MRF's, and additionally can in- corporate problem-specific knowledge in the form of fusion proposals. We compare experimentally against the existing approaches that can efficiently handle these difficult energy functions [6, 10, 11]. For higher-order denoising and stereo MRF's, we produce lower energy while running significantly faster.

Sub modular functions can be exactly minimized in polynomial time, and the special case that graph cuts solve with max flow [19] has had significant impact in computer vision [5, 21, 28]. In this paper we address the important class of sum-of-sub modular (SoS) functions [2, 18], which can be efficiently minimized via a variant of max flow called sub modular flow [6]. SoS functions can naturally express higher order priors involving, e.g., local image patches, however, it is difficult to fully exploit their expressive power because they have so many parameters. Rather than trying to formulate existing higher order priors as an SoS function, we take a discriminative learning approach, effectively searching the space of SoS functions for a higher order prior that performs well on our training set. We adopt a structural SVM approach [15, 34] and formulate the training problem in terms of quadratic programming, as a result we can efficiently search the space of SoS priors via an extended cutting-plane algorithm. We also show how the state-of-the-art max flow method for vision problems [11] can be modified to efficiently solve the sub modular flow problem. Experimental comparisons are made against the OpenCV implementation of the Grab Cut interactive segmentation technique [28], which uses hand-tuned parameters instead of machine learning. On a standard dataset [12] our method learns higher order priors with hundreds of parameter values, and produces significantly better segmentations. While our focus is on binary labeling problems, we show that our techniques can be naturally generalized to handle more than two labels.

The current Editor-in-Chief announces that Professor David Forsyth will serve as the next Editor-in-Chief of the IEEE Transactions on Pattern Analysis and Machine Intelligence. David is well known within the computer vision community for the depth and breadth of his research contributions and interests. He has also served in a large number of leadership roles, including organizing the main vision conferences several times, coauthoring a widely used textbook, and running important committees. He has been an associate editor of TPAMI, and has been deeply involved in various discussions about the relationship between the computer vision community and the IEEE Computer Society. I have great confidence that David will uphold the high standards of the journal, and under his leadership it will continue to serve the community admirably. A breif professional biography of Prof. Forsyth is provided.

T year 2012 will mark the end of my term as Editor-in-Chief of the IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). I believe that we have made substantial progress on one of the core challenges that TPAMI faces, namely, the continued growth of machine learning. As I have mentioned, the IEEE does not have a journal whose focus is modern machine learning methods, such as SVMs. Yet many papers in this area are submitted to TPAMI. One factor is that machine learning falls within TPAMI’s scope statement, but perhaps a more important reason is the journal’s excellence in computer vision, an area where machine learning is having a substantial and increasing impact. There is no possibility for TPAMI to ignore this area and continue to thrive, so the journal out of necessity must rise to the challenge of becoming a leading publication in machine learning. My predecessor David Kriegman saw this development clearly, and responded by appointing Zoubin Gharamani, a famous machine learning expert, as an Associate Editor in Chief (AEIC). Zoubin served his complete 4-year term with distinction, and has now moved up to the TPAMI Advisory Board. Over the last few years the number of machine learning submissions has continued to grow substantially, and we have clearly needed additional help. Machine learning is an area where TPAMI faces some distinct challenges. TPAMI has not published a body of truly fundamental papers in machine learning that is comparable to our accomplishments in computer vision, biometrics, or other areas that are closer to the journal’s traditional strengths. As a result, many of the submissions we receive have fallen short of TPAMI’s high standards. This has posed a diffi cult problem because it is challenging to attract top-notch researchers in machine learning as reviewers or AEs when most of the papers they handle must be rejected, and many would, in all honesty, never be submitted to a major machine learning journal. My primary focus throughout my term as EIC has been to address this situation, and I am pleased to report signifi cant progress. As you know, Max Welling joined us as an AEIC. I am happy to announce that Neil Lawrence has also agreed to serve as an AEIC. Neil has served with distinction as an AE for TPAMI, is on the board of JMLR, and will be program chair for AISTATS. (I note with amusement that Max Welling also held these three roles, which suggests a simple automatic classifi er to detect TPAMI AEICs in machine learning!) Neil has published two books in machine learning, and is primarily interested in probabilistic models. With both Max and Neil on board as AEICs we now have suffi cient manpower to address our main challenges. We have raised the bar for machine learning papers to be sent out for review by rejecting papers early on that would have eventually been rejected anyway. Hopefully, the effects of this will be clearly felt by everyone involved in the reviewing process, and the authors of high-quality submissions will benefi t from the increased availability of reviewing resources. Coupled with this effort, Max and Neil are developing a number of high quality special issues on important topics in machine learning (see the call for papers on page 207 of this issue for the fi rst such initiative). The fi eld of machine learning has a major advantage in its commitment to Open Access, which is an issue that the IEEE (along with most publishers) is struggling with. The top journal in machine learning (JMLR) is Open Access, while perhaps the best conference (NIPS) is making its proceedings available in arXiv. This has enormous benefi ts to the machine learning community. I personally believe that TPAMI will, over time, end up moving to an Open Access model, and I will hazard a guess that this will be one of the main challenges that the next EIC will face. On the operational side, the reviewing process on the whole is fairly timely, although exceptions do occur for a variety of reasons, and I want to yet again apologize to the authors whose papers get stalled in the process for one reason or another. To provide some numbers, there were 999 submissions in 2010 (I must confess I was really hoping for one more to come in at the very end). We are on track for a similar number in 2011, with 795 received as I write. The acceptance rate for 2010 submissions so far is 14 percent, though it is important to realize this does not imply 86 percent have been rejected, since a number of such papers are still undergoing revisions. The typical time from submission to final decision is about six months, which is unchanged from last year. Approximately 30 percent of submissions are rejected without review; while this is unpleasant for the authors, it saves them time from having their paper rejected at the end of the full review process and lets them quickly revise their papers for submission to a more appropriate journal. I am happy to report that the issue with the print queue is now under control, and papers now typically appear in print approximately 5.5 months after the fi nal material is uploaded. Short papers are generally published even faster, and authors are urged to consider this option. Of course, papers continue to be published online quite quickly after acceptance. On the topic of online publication, TPAMI is now available in the IEEE Computer Society’s new OnlinePlus format, at a signifi cant discount to the print subscription price. Over time the number of subscribers to the printed journal is falling, and readers who wish to see this format continue should be sure to sign up for print subscriptions.

Higher-order Markov Random Fields, which can capture important properties of natural images, have become increasingly important in computer vision. While graph cuts work well for first-order MRF's, until recently they have rarely been effective for higher-order MRF's. Ishikawa's graph cut technique [8, 9] shows great promise for many higher-order MRF's. His method transforms an arbitrary higher-order MRF with binary labels into a first-order one with the same minima. If all the terms are submodular the exact solution can be easily found; otherwise, pseudo-boolean optimization techniques can produce an optimal labeling for a subset of the variables. We present a new transformation with better performance than [8, 9], both theoretically and experimentally. While [8, 9] transforms each higher-order term independently, we transform a group of terms at once. For n binary variables, each of which appears in terms with k other variables, at worst we produce n non-submodular terms, while [8, 9] produces O(nk). We identify a local completeness property that makes our method perform even better, and show that under certain assumptions several important vision problems (including common variants of fusion moves) have this property. Running on the same field of experts dataset used in [8, 9] we optimally label significantly more variables (96% versus 80%) and converge more rapidly to a lower energy. Preliminary experiments suggest that some other higher-order MRF's used in stereo [20] and segmentation [1] are also locally complete and would thus benefit from our work.

Optimization is a powerful paradigm for expressing and solving problems in a wide range of areas, and has been successfully applied to many vision problems. Discrete optimization techniques are especially interesting since, by carefully exploiting problem structure, they often provide nontrivial guarantees concerning solution quality. In this paper, we review dynamic programming and graph algorithms, and discuss representative examples of how these discrete optimization techniques have been applied to some classical vision problems. We focus on the low-level vision problem of stereo, the mid-level problem of interactive object segmentation, and the high-level problem of model-based recognition.

We consider pixel labeling problems where the label set forms a tree, and where the observations are also labels. Such problems arise in feature-space analysis with a very large label set, for instance in color image segmentation. In this case a tree of labels can be constructed via hierarchical clustering of the observations. This leads to an obvious distance function between two labels, namely their distance within the tree; such tree metrics have been extensively studied outside of computer vision. We provide fast algorithms that use graph cuts to exactly minimize the energy function for pixel labeling problems with tree metrics. Our work substantially improves a facility location algorithm of Kolen, which is impractical for large label sets L since it requires O(|L|) min cuts on large graphs. Our main technical contribution is a new ordering of swap moves that reduces the running time to the equivalent of O(log |L|) min cuts; as a result, we can handle realistic-sized color images in a few seconds.

2010 marks the 30th anniversary of the IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), although the precise timing is a matter of some debate (overly meticulous readers might point out that the first issue appeared in January 1979). However, it is indisputable that TPAMI celebrated its 20th anniversary in 2000, and the author will follow this tradition and declare this year to be our 30th anniversary. An anniversary, of course, is traditionally an occasion to look at the past for perspective and also to think about the future. For the 20th anniversary, TPAMI published a series of survey articles, and it is instructive to consider the areas represented: statistical pattern recognition, document image analysis, handwriting recognition, medical image analysis, sensing for ubiquitous computing, and content-based image retrieval. While many of these areas remain important, perhaps the most striking development of the last decade has been the growth of areas at the intersection of computer vision and other fields. Machine learning, of course, is the preeminent example, but graphics and discrete optimization have also gained considerable importance. Turning to the current state of the journal, TPAMI is in excellent shape. The standard way of measuring the overall excellence of a journal is the Thompson-ISI impact factor, and TPAMI in 2008 has surpassed even its impressive 2007 performance. The impact factor is now 5.96, and there were 24,674 total citations in 2008. This makes TPAMI not only the #1 IEEE (and thus IEEE CS) publication, but also #1 in both electrical engineering and artificial intelligence, as well as #3 in all of computer science. These numbers are all-time highs. The situation for journals in 2010 poses some obvious challenges, such as the growing popularity of new ways to disseminate research results, even within traditionalist institutions such as universities. Yet TPAMI is well positioned due to its nonprofit status, along with its long-established tradition of publishing high-impact papers. We can all look forward to the many exciting research developments that will no doubt appear in TPAMI in the coming decade.

The left ventricle in MR images presents many challenges for automated segmentation including poor contrast at desired tissue boundaries. Segmentation methods based on information from the image alone do not work well in such cases and additional constraints are necessary. In this paper, we propose a novel segmentation method that incorporates parametric shape priors, which do not require statistical training, to the graph cuts technique for robust and efficient segmentations of the left ventricle in cardiac images. We introduce novel terms accounting for shape prior/segmentation and shape prior/image fit to the graph cuts representation. The latter prevents a vicious cycle of bad segmentation/shape priors. We demonstrate the effectiveness of our method on real cardiac images with ground truth segmentations.

The four papers in this special section are extended versions of award-winning papers from the 2007 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2007).

Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. However, the tradeoffs among different energy minimization algorithms are still not well understood. In this paper we describe a set of energy minimization benchmarks and use them to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods graph cuts, LBP, and tree-reweighted message passing in addition to the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. Benchmarks, code, images, and results are available at http://vision.middlebury.edu/MRF/.

Parallel imaging is a powerful technique to speed up magnetic resonance (MR) image acquisition via multiple coils. Both the received signal of each coil and its sensitivity map, which describes its spatial response, are needed during reconstruction. Widely used schemes such as SENSE assume that sensitivity maps of the coils are noiseless while the only errors are in coil outputs. In practice, however, sensitivity maps are subject to a wide variety of errors. At first glance, sensitivity noise appears to result in an errors-in-variables problem of the kind that is typically solved using total least squares (TLSs). However, existing TLS algorithms are in general inappropriate for the specific type of block structure that arises in parallel imaging. In this paper, we take a maximum likelihood approach to the problem of parallel imaging in the presence of independent Gaussian sensitivity noise. This results in a quasi-quadratic objective function, which can be efficiently minimized. Experimental evidence suggests substantial gains over conventional SENSE, especially in nonideal imaging conditions like low signal-to-noise ratio (SNR), high g-factors and large acceleration, using sensitivity maps suffering from misalignment, ringing, and random noise.

Markov Random Fields (MRF’s) are an effective way to impose spatial smoothness in computer vision. We describe an application of MRF’s to a non-traditional but important problem in medical imaging: the reconstruction of MR images from raw fourier data. This can be formulated as a linear inverse problem, where the goal is to find a spatially smooth solution while permitting discontinuities. Although it is easy to apply MRF’s to the MR reconstruction problem, the resulting energy minimization problem poses some interesting challenges. It lies outside of the class of energy functions that can be straightforwardlyminimized with graph cuts. We show how graph cuts can nonetheless be adapted to solve this problem, and provide some theoretical analysis of the properties of our algorithm. Experimentally, our method gives very strong performance, with a substantial improvement in SNR when compared with widely-used methods for MR reconstruction.

The goal of deconvolution is to recover an image x from its convolution with a known blurring function. This is equivalent to inverting the linear system y = Hx. In this paper, we consider the generalized problem where the system matrix H is an arbitrary nonnegative matrix. Linear inverse problems can be solved by adding a regularization term to impose spatial smoothness. To avoid oversmoothing, the regularization term must preserve discontinuities; this results in a particularly challenging energy minimization problem. Where H is diagonal, as occurs in image denoising, the energy function can be solved by techniques such as graph cuts, which have proven to be very effective for problems in early vision. When H is nondiagonal, however, the data cost for a pixel to have a intensity depends on the hypothesized intensities of nearby pixels, so existing graph cut methods cannot be applied. This paper shows how to use graph cuts to obtain a discontinuity preserving solution to a linear inverse system with an arbitrary non-negative system matrix. We use a dynamically chosen approximation to the energy which can he minimized by graph cuts; minimizing this approximation also decreases the original energy. Experimental results are shown for MRI reconstruction from Fourier data

In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.

We address visual correspondence problems without assuming that scene points have similar intensities in different views. This situation is common, usually due to nonLambertian scenes or to differences between cameras. We use maximization of mutual information, a powerful technique for registering images that requires no a priori model of the relationship between scene intensities in different views. However, it has proven difficult to use mutual information to compute dense visual correspondence. Comparing fixed-size windows via mutual information suffers from the well-known problems of fixed windows, namely poor performance at discontinuities and in low-texture regions. In this paper, we show how to compute visual correspondence using mutual information without suffering from these problems. Using a simple approximation, mutual information can be incorporated into the standard energy minimization framework used in early vision. The energy can then be efficiently minimized using graph cuts, which preserve discontinuities and handle low-texture regions. The resulting algorithm combines the accurate disparity maps that come from graph cuts with the tolerance for intensity changes that comes from mutual information.

Medical imaging often involves the injection of contrast agents and the subsequent analysis of tissue enhancement patterns. Many important types of tissue have characteristic enhancement patterns; for example, in magnetic resonance (MR) mammography, malignancies exhibit a characteristic "wash out" temporal pattern, while in MR angiography, arteries, veins and parenchyma each have their own distinctive temporal signature. In such image sequences, there are substantial changes in intensities; however, this change is due primarily to the contrast agent rather than the motion of scene elements. As a result, the task of segmenting contrast-enhanced images poses interesting new challenges for computer vision. We propose a new image segmentation algorithm for image sequences with contrast enhancement, using a model-based time series analysis of individual pixels. We use energy minimization via graph cuts to efficiently ensure spatial coherence. The energy is minimized in an expectation-maximization fashion that alternates between segmenting the image into a number of nonoverlapping regions and finding the temporal profile parameters which best describe the behavior of each region. Preliminary experiments on MR mammography and MR angiography studies show the algorithm's ability to find an accurate segmentation.

Several new algorithms for visual correspondence based on graph cuts have recently been developed. While these methods give very strong results in practice, they do not handle occlusions properly. Specifically, they treat the two input images asymmetrically, and they do not ensure that a pixel corresponds to at most one pixel in the other image. In this paper, we present a new method which properly addresses occlusions, while preserving the advantages of graph cut algorithms. We give experimental results for stereo as well as motion, which demonstrate that our method performs well both at detecting occlusions and computing disparities.

Many tasks in computer vision involve assigning a label (such as disparity) to every pixel. A common constraint is that the labels should vary smoothly almost everywhere while preserving sharp discontinuities that may exist, e.g., at object boundaries. These tasks are naturally stated in terms of energy minimization. The authors consider a wide class of energies with various smoothness constraints. Global minimization of these energy functions is NP-hard even in the simplest discontinuity-preserving case. Therefore, our focus is on efficient approximation algorithms. We present two algorithms based on graph cuts that efficiently find a local minimum with respect to two types of large moves, namely expansion moves and swap moves. These moves can simultaneously change the labels of arbitrarily large sets of pixels. In contrast, many standard algorithms (including simulated annealing) use small moves where only one pixel changes its label at a time. Our expansion algorithm finds a labeling within a known factor of the global minimum, while our swap algorithm handles more general energy functions. Both of these algorithms allow important cases of discontinuity preserving energies. We experimentally demonstrate the effectiveness of our approach for image restoration, stereo and motion. On real data with ground truth, we achieve 98 percent accuracy.

N a letter to C. Huygens of 1679, G.W. Leibniz expressed his dissatisfaction with the standard coordinate treatment of geometric figures and maintained that we need yet another kind of analysis, geometric or linear, which deals directly with position, as algebra deals with magnitude (1). In fact, Leibniz initiated the study of the so-called geometry of positions (geometria situs) which, as L. Euler clearly put it in his famous 1736 Konigsberg bridges paper which had to mark the beginning of graph theory, concerned only with the determination of position, and its properties; it does not involve measurements nor calculations made with them (2). After about two centuries, this study developed into two of the richest branches of modern mathematics: graph theory and combinatorial topology. Mutatis mutandis, an analogous discontent is nowadays being felt among many researchers working in computer vision, a field that is currently dominated by purely geometric methods, who are increasingly making use of sophisticated graph-theoretic concepts, results, and algorithms. Indeed, graphs have long been an important tool in computer vision, especially because of their representational power and flexibility. However, there is now a renewed and growing interest toward explicitly formulating computer vision problems as graph problems. This is particularly advanta- geous because it allows vision problems to be cast in a pure, abstract setting with solid theoretical underpinnings and also permits access to the full arsenal of graph algorithms developed in computer science and operations research. Graph-theoretic problems which have proven to be relevant to computer vision include maximum flow, minimum spanning tree, maximum clique, shortest path, maximal common subtree/subgraph, etc. In addition, a number of fundamental techniques that were designed in the graph algorithms community have recently been applied to computer vision problems. Examples include spectral

The task of multicamera surveillance is to reconstruct the paths taken by all moving objects that are temporally visible from multiple non-overlapping cameras. We present a Bayesian formalization of this task, where the optimal solution is the set of object paths with the highest posterior probability given the observed data. We show how to efficiently approximate the maximum a posteriori solution by linear programming and present initial experimental results.

In this paper we address the problem of minimizing a large class of energy functions that occur in early vision. The major restriction is that the energy function's smoothness term must only involve pairs of pixels. We propose two algorithms that use graph cuts to compute a local minimum even when very large moves are allowed. The first move we consider is an /spl alpha/-/spl beta/-swap: for a pair of labels /spl alpha/,/spl beta/, this move exchanges the labels between an arbitrary set of pixels labeled a and another arbitrary set labeled /spl beta/. Our first algorithm generates a labeling such that there is no swap move that decreases the energy. The second move we consider is an /spl alpha/-expansion: for a label a, this move assigns an arbitrary set of pixels the label /spl alpha/. Our second algorithm, which requires the smoothness term to be a metric, generates a labeling such that there is no expansion move that decreases the energy. Moreover, this solution is within a known factor of the global minimum. We experimentally demonstrate the effectiveness of our approach on image restoration, stereo and motion.

Markov Random Fields (MRFs) can be used for a wide variety of vision problems. In this paper we focus on MRFs with two-valued clique potentials, which form a generalized Potts model. We show that the maximum a posteriori estimate of such an MRF can be obtained by solving a multiway minimum cut problem on a graph. We develop efficient algorithms for computing good approximations to the minimum multiway, cut. The visual correspondence problem can be formulated as an MRF in our framework; this yields quite promising results on real data with ground truth. We also apply our techniques to MRFs with linear clique potentials.

Organizing images into semantic categories can be extremely useful for searching and browsing through large collections of images. Not much work has been done on automatic image classification, however. In this paper, we propose a method for hierarchical classification of images via supervised learning. This scheme relies on using a good low-level feature and subsequently performing feature-space reconfiguration using singular value decomposition to reduce noise and dimensionality. We use the training data to obtain a hierarchical classification tree that can be used to categorize new images. Our experimental results suggest that this scheme not only performs better than standard nearest-neighbor techniques, but also has both storage and computational advantages. 1 Introduction The proliferation of the world-wide web has given easy access to an explosively growing volume of visual data. Unfortunately, this data on the web is both scattered and unorganized, making search and retrieval...

Early vision relies heavily on rectangular windows for tasks such as smoothing and computing correspondence. While rectangular windows are efficient, they yield poor results near object boundaries. We describe an efficient method for choosing an arbitrarily shaped connected window, in a manner that varies at each pixel. Our approach can be applied to several problems, including image restoration and visual correspondence. It runs in linear time, and takes a few seconds on traditional benchmark images. Performance on both synthetic and real imagery appears promising.

We present a method for computing dense visual correspondence based on general assumptions about scene geometry. Our algorithm does not rely on correlation, and uses a variable region of support. We assume that images consist of a number of connected sets of pixels with the same disparity, which we call disparity components. Using maximum likelihood arguments, at each pixel we compute a small set of plausible disparities. A pixel is assigned a disparity d based on connected components of pixels, where each pixel in a component considers d to be plausible. Our implementation chooses the largest plausible disparity component; however, global contextual constraints can also be applied. While the algorithm was originally designed for visual correspondence, it can also be used for other early vision problems such as image restoration. It runs in a few seconds on traditional benchmark images with standard parameter settings, and gives quite promising results.

We define a new image feature called the color correlogram and use it for image indexing and comparison. This feature distills the spatial correlation of colors, and is both effective and inexpensive for content-based image retrieval. The correlogram robustly tolerates large changes in appearance and shape caused by changes in viewing positions, camera zooms, etc. Experimental evidence suggests that this new feature outperforms not only the traditional color histogram method but also the recently proposed histogram refinement methods for image indexing/retrieval.

Automatic video browsing requires algorithms for detecting a variety of events, including production effects (e.g., scene breaks and captions) and moving objects. We present new methods that use edges and motion for detecting production effects and computing motion segmentation. Production effects, such as cuts, dissolves, wipes and captions, can be detected by looking for new edges that are far from previous edges. A global motion computation, is used to register consecutive images. We have also developed a method for motion segmentation, which does not require computing local optical flow. Our methods run at several frames per second on a Sparc workstation, and tolerate compression artifacts.

Color histograms are used to compare images in many applications. Their advantages are e#ciency, and insensitivity to small changes in camera viewpoint. However, color histograms lack spatial information, and this can cause images with very different appearances to have similar histograms. For example, a picture of fall foliage might contain a large number of scattered red pixels; this could have a similar color histogram to a picture of a single large red object. We describe a histogram-based method for comparing images that incorporates spatial information. While a color histogram counts the number of pixels with a given color, a color coherence vector #CCV# measures the spatial coherence of the pixels with a given color. If the red pixels in an image are members of large red regions, this color will have high coherence, while if the red pixels are widely scattered it will havelow coherence. CCV's can be computed at over 5 images per second on a standard workstation. A da...

Color histograms are widely used for content-based image retrieval. Their advantages are efficiency, and insensitivity to small changes in camera viewpoint. However, a histogram is a coarse characterization of an image, and so images with very different appearances can have similar histograms. We describe a technique for comparing images called histogram refinement, which imposes additional constraints on histogram based matching. Histogram refinement splits the pixels in a given bucket into several classes, based upon some local property. Within a given bucket, only pixels in the same class are compared. We describe a split histogram called a color coherence vector (CCV), which partitions each histogram bucket based on spatial coherence. CCVs can be computed at over 5 images per second on a standard workstation. A database with 15,000 images can be queried using CCVs in under 2 seconds. We demonstrate that histogram refinement can be used to distinguish images whose color histograms are indistinguishable.

No abstract available.

We extend the notion of class so that any Boolean combinations of classes is also a class. Boolean classes allow greater precision and conciseness in naming the class of objects governed a particular method. A class can be viewed as a predicate which is either true or false of any given object. Unlike predicates however classes have an inheritance hierarchy which is known at compile time. Boolean classes extend the notion of class, making classes more like predicates, while preserving the compile time computable inheritance hierarchy.