CRFs model spatial coherence in classical and deep learning computer vision. The most common CRF is called pairwise, as it connects pixel pairs. There are two types of pairwise CRF: sparse and dense. A sparse CRF connects the nearby pixels, leading to a linear number of connections in the image size. A dense CRF connects all pixel pairs, leading to a quadratic number of connections. While dense CRF is a more general model, it is much less efficient than sparse CRF. In fact, only Gaussian edge dense CRF is used in practice, and even then with approximations. We propose a new pairwise CRF, which we call sparse non-local CRF. Like dense CRF, it has non-local connections, and, therefore, it is more general than sparse CRF. Like sparse CRF, the number of connections is linear, and, therefore, our model is efficient. Besides efficiency, another advantage is that our edge weights are unrestricted. We show that our sparse non-local CRF models properties similar to that of Gaussian dense CRF. We also discuss connections to other CRF models. We demonstrate the usefulness of our model on classical and deep learning applications, for two and multiple labels.

We propose a new image level weakly supervised segmentation approach for datasets with a single object class of interest. Our approach is based on a regularized loss function inspired by the classical Conditional Random Field (CRF) modeling. Our loss models properties of generic objects, and we use it to guide CNN towards segments that are more likely to correspond to the object, thus avoiding the need for pixel precise annotations. Training CNN with regularized loss is a difficult task for gradient descent. We develop an annealing algorithm which is crucial for a successful training. Furthermore, we develop an approach for hyperparameter setting for the most important components of our regularized loss. This is far from trivial, since there is no pixel precise ground truth for guidance. The advantage of our method is that we use a standard CNN architecture and an easy to interpret loss function, derived from classical CRF models. Furthermore, we apply the same loss function for any task/dataset. We first evaluate our approach for salient object segmentation and co-segmentation. These tasks naturally involve one object class of interest. Then we adapt our approach to image level weakly supervised multi-class semantic segmentation. We obtain state-of-the-art results.

It is well known that CNNs tend to overfit to the training data. Test-time adaptation is an extreme approach to deal with overfitting: given a test image, the aim is to adapt the trained model to that image. Indeed nothing can be closer to the test data than the test image itself. The main difficulty of test-time adaptation is that the ground truth is not available. Thus test-time adaptation, while intriguing, applies to only a few scenarios where one can design an effective loss function that does not require ground truth. We propose the first approach for test-time Salient Object Detection (SOD) in the context of weak supervision. Our approach is based on a so called regularized loss function, which can be used for training CNN when pixel precise ground truth is unavail-able. Regularized loss tends to have lower values for the more likely object segments, and thus it can be used to fine-tune an already trained CNN to a given test image, adapting to images unseen during training. We develop a regularized loss function particularly suitable for test-time adaptation and show that our approach significantly outperforms prior work for weakly supervised SOD.

CRF is a classical computer vision model which is also useful for deep learning. There are two common CRF types: sparse and dense. Sparse CRF connects only the nearby pixels, while dense CRF has global connectivity. Therefore dense CRF is a more general model, but it is much harder to optimize compared to sparse CRF. In fact, only a certain form of dense CRF is optimized in practice, and even then approximately. We propose a new sparse non-local CRF: it has a sparse number of connections, but it has both local and non-local ones. Like sparse CRF, the total number of connections is small, and our model is easy to optimize exactly. Like dense CRF, our model is more general than sparse CRF due to non-local connections. We show that our sparse non-local CRF can model properties similar to that of the popular Gaussian edge dense CRF. Besides efficiency, another advantage is that our edge weights are less restricted compared to Gaussian edge dense CRF. We design models that take advantage of this flexibility. We also discuss connection of our model to other CRF models. Finally, to prove the usefulness of our model, we evaluate it on the classical application of segmentation from a bounding box and for deep learning based salient object segmentation. We improve state of the art for both applications.

Fully connected pairwise Conditional Random Fields (Full-CRF) with Gaussian edge weights can achieve superior results compared to sparsely connected CRFs. However, traditional methods for Full-CRFs are too expensive. Previous work develops efficient approximate optimization based on mean field inference, which is a local optimization method and can be far from the optimum. We propose efficient and effective optimization based on graph cuts for Full-CRFs with quantized edge weights. To quantize edge weights, we partition the image into superpixels and assume that the weight of an edge between any two pixels depends only on the superpixels these pixels belong to. Our quantized edge CRF is an approximation to the Gaussian edge CRF, and gets closer to it as superpixel size decreases. Being an approximation, our model offers an intuition about the regularization properties of the Guassian edge Full-CRF. For efficient inference, we first consider the two-label case and develop an approximate method based on transforming the original problem into a smaller domain. Then we handle multi-label CRF by showing how to implement expansion moves. In both binary and multi-label cases, our solutions have significantly lower energy compared to that of mean field inference. We also show the effectiveness of our approach on semantic segmentation task.

Many computer vision problems require optimization of binary non-submodular energies. In this context, iterative submodularization techniques based on trust region (LSA-TR) and auxiliary functions (LSA-AUX) have been recently proposed [9]. They achieve state-of-the-art-results on a number of computer vision applications. In this paper we extend the LSA-AUX framework in two directions. First, unlike LSA-AUX which selects auxiliary functions based solely on the current solution, we propose to incorporate several additional criteria. This results in tighter bounds for configurations that are more likely or closer to the current solution. Second, we propose move-making extensions of LSA-AUX which achieve tighter bounds by restricting the search space. Finally, we evaluate our methods on several applications. We show that for each application at least one of our extensions significantly outperforms the original LSA-AUX. Moreover, the best extension of LSA-AUX is comparable to or better than LSA-TR on five out of six applications, achieving state-of-the-arts results on four out of six applications.

We propose an effective optimization algorithm for a general hierarchical segmentation model with geometric interactions between segments. Any given tree can specify a partial order over object labels defining a hierarchy. It is well-established that segment interactions, such as inclusion/exclusion and margin constraints, make the model significantly more discriminant. However, existing optimization methods do not allow full use of such models. Generic a-expansion results in weak local minima, while common binary multi-layered formulations lead to non-submodularity, complex high-order potentials, or polar domain unwrapping and shape biases. In practice, applying these methods to arbitrary trees does not work except for simple cases. Our main contribution is an optimization method for the Hierarchically-structured Interacting Segments (HINTS) model with arbitrary trees. Our Path-Moves algorithm is based on multi-label MRF formulation and can be seen as a combination of well-known a-expansion and Ishikawa techniques. We show state-of-the-art biomedical segmentation for many diverse examples of complex trees.

Many computer vision problems require optimization of binary non-submodular energies. We propose a general optimization framework based on local submodular approximations (LSA). Unlike standard LP relaxation methods that linearize the whole energy globally, our approach iteratively approximates the energy locally. On the other hand, unlike standard local optimization methods (e.g., gradient descent or projection techniques) we use non-linear submodular approximations and optimize them without leaving the domain of integer solutions. We discuss two specific LSA algorithms based on trust region and auxiliary function principles, LSA-TR and LSA-AUX. The proposed methods obtain state-of-the-art results on a wide range of applications such as binary deconvolution, curvature regularization, inpainting, segmentation with repulsion and two types of shape priors. Finally, we discuss a move-making extension to the LSA-TR approach. While our paper is focused on pairwise energies, our ideas extend to higher-order problems. The code is available online.

Convexity is a known important cue in human vision. We propose shape convexity as a new high-order regularization constraint for binary image segmentation. In the context of discrete optimization, object convexity is represented as a sum of three-clique potentials penalizing any 1- 0- 1 configuration on all straight lines. We show that these non-submodular potentials can be efficiently optimized using an iterative trust region approach. At each iteration the energy is linearly approximated and globally optimized within a small trust region around the current solution. While the quadratic number of all three-cliques is prohibitively high, we design a dynamic programming technique for evaluating and approximating these cliques in linear time. We also derive a second order approximation model that is more accurate but computationally intensive. We discuss limitations of our local optimization and propose gradual non-submodularization scheme that alleviates some limitations. Our experiments demonstrate general usefulness of the proposed convexity shape prior on synthetic and real image segmentation examples. Unlike standard second-order length regularization, our convexity prior does not have shrinking bias, and is robust to changes in scale and parameter selection.

Star-convexity prior is popular for interactive single object segmentation due to its simplicity and amenability to binary graph cut optimization. We propose a more general multi-object segmentation approach. Moreover, each object can be constrained by a more descriptive shape prior, "hedgehog". Each hedgehog shape has its surface normals locally constrained by an arbitrary given vector field, e.g. gradient of the user-scribble distance transform. In contrast to star-convexity, the tightness of our normal constraint can be changed giving better control over allowed shapes. For example, looser constraints, i.e. wider cones of allowed normals, give more relaxed hedgehog shapes. On the other hand, the tightest constraint enforces skeleton consistency with the scribbles. In general, hedgehog shapes are more descriptive than a star, which is only a special case corresponding to a radial vector field and weakest tightness. Our approach has significantly more applications than standard single star-convex segmentation, e.g. in medical data we can separate multiple non-star organs with similar appearances and weak edges. Optimization is done by our modified -expansion moves shown to be submodular for multi-hedgehog shapes.

Potts energy frequently occurs in computer vision applications. We present an efficient parallel method for optimizing Potts energy based on the extension of hierarchical fusion algorithm. Unlike previous parallel graph-cut based optimization algorithms, our approach has optimality bounds even after a single iteration over all labels, i.e. after solving only k-1 max-flow problems, where k is the number of labels. This is perhaps the minimum number of max-flow problems one has to solve to obtain a solution with optimality guarantees. Our approximation factor is O(log2k). Although this is not as good as the factor of 2 approximation of the well known expansion algorithm, we achieve very good results in practice. In particular, we found that the results of our algorithm after one iteration are always better than the results after one iteration of the expansion algorithm. We demonstrate experimentally the computational advantages of our parallel implementation on the problem of stereo correspondence, achieving a factor of 1.5 to 2.6 speedup compared to the serial implementation. These results were obtained with a small number of processors. The expected speedups with a larger number of processors are greater.

Binary energy optimization is a popular approach for segmenting a color image into foreground/background regions. To model the appearance of the regions, color, a relatively high dimensional feature, should be handled effectively. A full color histogram is usually too sparse to be reliable. One approach is to explicitly reduce dimensionality by clustering or quantizing the color space. Another popular approach is to fit GMMs for soft implicit clustering of the color space. These approaches work well when the foreground/background are sufficiently distinct. In cases of more subtle difference in appearance, both approaches may reduce or even eliminate foreground/background distinction. This happens because either color clustering is performed completely independently from the segmentation process, as a preprocessing step (in clustering), or independently for the foreground and independently for the background (in GMM). We propose to make clustering an integral part of segmentation, by including a new clustering term in the energy function. Our energy function with a clustering term favours clusterings that make foreground/background appearance more distinct. Thus our energy function jointly optimizes over color clustering, foreground/background models, and segmentation. Exact optimization is not feasible, therefore we develop an approximate algorithm. We show the advantage of including the color clustering term into the energy function on camouflage images, as well as standard segmentation datasets.

Many computer vision problems require optimization of binary non-submodular energies. We propose a general optimization framework based on local submodular approximations (LSA). Unlike standard LP relaxation methods that linearize the whole energy globally, our approach iteratively approximates the energies locally. On the other hand, unlike standard local optimization methods (e.g. gradient descent or projection techniques) we use non-linear submodular approximations and optimize them without leaving the domain of integer solutions. We discuss two specific LSA algorithms based on trust region and auxiliary function principles, LSA-TR and LSA-AUX. These methods obtain state-of-the-art results on a wide range of applications outperforming many standard techniques such as LBP, QPBO, and TRWS. While our paper is focused on pairwise energies, our ideas extend to higher-order problems. The code is available online.

Curvature has received increasing attention as an important alternative to length based regularization in computer vision. In contrast to length, it preserves elongated structures and fine details. Existing approaches are either inefficient, or have low angular resolution and yield results with strong block artifacts. We derive a new model for computing squared curvature based on integral geometry. The model counts responses of straight line triple cliques. The corresponding energy decomposes into submodular and supermodular pairwise potentials. We show that this energy can be efficiently minimized even for high angular resolutions using the trust region framework. Our results confirm that we obtain accurate and visually pleasing solutions without strong artifacts at reasonable runtimes.

Among image segmentation algorithms there are two major groups: (a) methods assuming known appearance models and (b) methods estimating appearance models jointly with segmentation. Typically, the first group optimizes appearance log-likelihoods in combination with some spacial regularization. This problem is relatively simple and many methods guarantee globally optimal results. The second group treats model parameters as additional variables transforming simple segmentation energies into high-order NP-hard functionals (Zhu-Yuille, Chan-Vese, Grab Cut, etc). It is known that such methods indirectly minimize the appearance overlap between the segments. We propose a new energy term explicitly measuring L1 distance between the object and background appearance models that can be globally maximized in one graph cut. We show that in many applications our simple term makes NP-hard segmentation functionals unnecessary. Our one cut algorithm effectively replaces approximate iterative optimization techniques based on block coordinate descent.

Radical prostatectomy is performed on approximately 40% of men with organ-confined prostate cancer. Pathologic information obtained from the prostatectomy specimen provides important prognostic information and guides recommendations for adjuvant treatment. The current pathology protocol in most centers involves primarily qualitative assessment. In this paper, we describe and evaluate our system for automatic prostate cancer detection and grading on hematoxylin & eosin-stained tissue images. Our approach is intended to address the dual challenges of large data size and the need for high-level tissue information about the locations and grades of tumors. Our system uses two stages of AdaBoost-based classification. The first provides high-level tissue component labeling of a superpixel image partitioning. The second uses the tissue component labeling to provide a classification of cancer versus noncancer, and low-grade versus high-grade cancer. We evaluated our system using 991 sub-images extracted from digital pathology images of 50 whole-mount tissue sections from 15 prostatectomy patients. We measured accuracies of 90% and 85% for the cancer versus noncancer and high-grade versus low-grade classification tasks, respectively. This system represents a first step toward automated cancer quantification on prostate digital histopathology imaging, which could pave the way for more accurately informed postprostatectomy patient care.

Many computer vision applications can be formulated as labeling problems. However, multilabeling problems are usually very challenging to solve, especially when some ordering constraints are enforced. We solve in this paper a five-parts labeling problem proposed in [6, 7]. In this model, one wants to find an optimal labeling for an image with five possible parts: “left”, “right”, “top”, “bottom” and “center”. The geometric ordering constraints can be read naturally from the names. No previous method can solve the problem with globally optimal solutions in a linear space complexity. We propose an efficient dynamic programming based algorithm which guarantees the global optimal labeling for the five-parts model. The time complexity is O(N1.5) and the space complexity is O(N), with N being the number of pixels in the image. In practice, it runs faster than previous methods. Moreover, it works for both 4-neighborhood and 8-neighborhood settings, and can be easily parallelized for GPU.

Inference on high-order graphical models has become increasingly important in recent years. We consider energies with simple 'sparse' high-order potentials. Previous work in this area uses either specialized message-passing or transforms each high-order potential to the pairwise case. We take a fundamentally different approach, transforming the entire original problem into a comparatively small instance of a submodular vertex-cover problem. These vertex-cover instances can then be attacked by standard pairwise methods, where they run much faster (4--15 times) and are often more effective than on the original problem. We evaluate our approach on synthetic data, and we show that our algorithm can be useful in a fast hierarchical clustering and model estimation framework.

We propose a novel patch-based image representation that is useful because it (1) inherently detects regions with repetitive structure at multiple scales and (2) yields a parameterless hierarchical segmentation. We describe an image by breaking it into coherent regions where each region is well-described (easily reconstructed) by repeatedly instantiating a patch using a set of simple transformations. In other words, a good segment is one that has sufficient repetition of some pattern, and a patch is useful if it contains a pattern that is repeated in the image. Our criterion is naturally expressed by the well-established minimum description length (MDL) principle. MDL prefers spatially coherent regions with consistent appearance and avoids parameter tuning. We minimize the description length (in bits) of the image by encoding it with patches. Because a patch is itself an image, we measure its description length by applying the same idea recursively: encode a patch by breaking it into regions described by yet simpler patches. The resulting hierarchy of inter-dependent patches naturally leads to a hierarchical segmentation. We minimize description length over our class of image representations (all patch hierarchies / partitions). We formulate this problem as a recursive multi-label energy. Existing optimization techniques are either inapplicable or get stuck in poor local minima. We propose a new hierarchical fusion (HF) algorithm for energies containing a hierarchy of 'label costs'. Our algorithm is a contribution in itself and should be useful for this new and difficult class of energies.

Saliency detection is a well researched problem in computer vision. In previous work, most of the effort is spent on manually devising a saliency measure. Instead we propose a simple algorithm that uses a dataset with manually marked salient objects to learn to de-tect saliency. Building on the recent success of segmentation-based approaches to object detection, our saliency detection is based on image superpixels, as opposed to individual image pixels. Our features are the standard ones often used in vision, i.e. they are based on color, texture, etc. These simple features, properly normalized, surprisingly have a performance superior to the methods with hand-crafted features specifically designed for saliency detection. We refine the initial segmentation returned by the learned classifier by performing binary graph-cut optimization. This refinement step is performed on pixel level to alleviate any potential inaccuracies due to superpixel tesselation. The initial ap-pearance models are updated in an iterative segmentation framework. To insure that the classifier results are not completely ignored during later iterations, we incorporate classi-fier confidences into our graph-cut refinement. Evaluation on the standard datasets shows a significant advantage of our approach over previous work. 1

Dynamic programming (DP) has been a useful tool for a variety of computer vision problems. However its application is usually limited to problems with a one dimensional or low treewidth structure, whereas most domains in vision are at least 2D. In this paper we show how to apply DP for pixel labeling of 2D scenes with simple “tiered” structure. While there are many variations possible, for the applications we consider the following tiered structure is appropriate. An image is first divided by horizontal curves into the top, middle, and bottom regions, and the middle region is further subdivided vertically into subregions. Under these constraints a globally optimal labeling can be found using an efficient dynamic programming algorithm. We apply this algorithm to two very different tasks. The first is the problem of geometric class labeling where the goal is to assign each pixel a label such as “sky”, “ground”, and “surface above ground”. The second task involves incorporating simple shape priors for segmentation of an image into the “foreground” and “background” regions.

Abstract Classic mosaic is an old and durable art form. Generating artificial classic mosaics from digital images is an interesting problem that has attracted attention in recent years. Previous approaches to mosaic generation are largely based on heuristics, and therefore it is harder to analyse, predict and improve their performance. In addition, previous methods have a number of disadvantages, such as requiring that the number of tiles in a mosaic is known a priori, or relying on extensive user interaction, or using heuristics for tile placement that lead to visible artefacts. We propose a classic mosaic generation algorithm that is based on a principled global optimization. Our approach is fully automatic. We design and optimize an objective function that incorporates the desired mosaic properties, such as tile alignment to significant image edges, prohibiting tile overlap, etc. Our optimization method is based on graph cuts, which proved to be a powerful optimization tool in graphics and computer vision. Experimental comparison to previous work demonstrate the advantages of our approach.

In the last decade, graph-cut optimization has been popular for a variety of labeling problems. Typically, graph-cut methods are used to incorporate smoothness constraints on a labeling, encouraging most nearby pixels to have equal or similar labels. In addition to smoothness, ordering constraints on labels are also useful. For example, in object segmentation, a pixel with a "car wheel" label may be prohibited above a pixel with a "car roof" label. We observe that the commonly used graph-cut \alpha-expansion move algorithm is more likely to get stuck in a local minimum when ordering constraints are used. For a certain model with ordering constraints, we develop new graph-cut moves which we call order-preserving. The advantage of order-preserving moves is that they act on all labels simultaneously, unlike \alpha-expansion. More importantly, for most labels \alpha, the set of \alpha-expansion moves is strictly smaller than the set of order-preserving moves. This helps to explain why in practice optimization with order-preserving moves performs significantly better than \alpha-expansion in the presence of ordering constraints. We evaluate order-preserving moves for the geometric class scene labeling (introduced by Hoiem et al.) where the goal is to assign each pixel a label such as "sky," "ground," etc., so ordering constraints arise naturally. In addition, we use order-preserving moves for certain simple shape priors in graph-cut segmentation, which is a novel contribution in itself.

In recent years, the graph cut algorithm has been successfully applied to image segmentation because it offers numerically robust global minimum. In the graph cut framework, a parameter is often used to weight the importance of the different terms of the energy function. Usually, a fixed setting of parameters is given by the developers of the segmentation algorithm, and they are expected to give satisfactory segmentations for the images similar to those that were used to tune the parameters. But when given a different class of images, the results might not be satisfactory. In fact, there is no fixed choice of parameters that will work for all images. For each particular image, parameters must be tuned to achieve best results. The goal of this thesis is to develop a measure of segmentation quality based on different features of segmentation. Then we can run the graph cut algorithm for different values of the parameter and choose the one that gives segmentation of the highest quality. Segmentation evaluation is closely tied to the question of what constitutes a good segmentation. While evaluating segmentation results is an important task in itself, in this thesis, segmentation evaluation is a crucial task since it forms an integral part of the proposed parameter selection method. We investigate several measures of segmentation quality and our measure of segmentation quality is based on intensity, gradient, contour continuity, and texture features. We approach the problem of segmentation quality as a binary classification problem (good segmentation vs. bad segmentation), and train a classifier using the AdaBoost algorithm. AdaBoost, in addition to the class label, provides confidence estimates. A high positive value indicates that the classifier is very confident that is in the positive class (i.e. a good segmentation). Thus instead of just a binary decision, namely a good or a bad segmentation, we take the confidence value as the final measure of segmentation goodness. A new way to normalize feature weights for the AdaBoost based classifier is developed, which is particularly suitable for our framework. Our approach to feature normalization is uniquely appropriate for the parameter selection problem, and leads to a big improvement in performance. The leave- one-out cross-validation error rate is 4.4%, meaning the top quality segmentation chosen for an image is a bad segmentation in only 4.4% of cases.

In the last decade, graph-cut optimization has been popular for a variety of pixel labeling problems. Typically graph-cut methods are used to incorporate a smoothness prior on a labeling. Recently several methods incorporated ordering constraints on labels for the application of object segmentation. An example of an ordering constraint is prohibiting a pixel with a ldquocar wheelrdquo label to be above a pixel with a ldquocar roofrdquo label. We observe that the commonly used graph-cut based alpha-expansion is more likely to get stuck in a local minimum when ordering constraints are used. For certain models with ordering constraints, we develop new graph-cut moves which we call order-preserving moves. Order-preserving moves act on all labels, unlike alpha-expansion. Although the global minimum is still not guaranteed, optimization with order-preserving moves performs significantly better than alpha-expansion. We evaluate order-preserving moves for the geometric class scene labeling (introduced by Hoiem et al.) where the goal is to assign each pixel a label such as ldquoskyrdquo, ldquogrounrdquo, etc., so ordering constraints arise naturally. In addition, we use order-preserving moves for certain simple shape priors in graphcut segmentation, which is a novel contribution in itself.

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

Optimization with graph cuts became very popular in recent years. Progress in problems such as stereo correspondence, image segmentation, etc., can be attributed, in part, to the development of efficient graph cut based optimization. Recent evaluation of optimization techniques shows that the popular expansion and swap graph cut algorithms perform extremely well for energies where the underlying MRF has the Potts prior, which corresponds to the assumption that the true labeling is piecewise constant. For more general priors, however, such as corresponding to piece-wise smoothness assumption, both swap and expansion algorithms do not perform as well. We develop several optimization algorithms for truncated convex priors, which imply piecewise smoothness assumption. Both expansion and swap algorithms are based on moves that give each pixel a choice of only two labels. Our insight is that to obtain a good approximation under piecewise smoothness assumption, a pixel should have a choice among more than two labels. We develop new "range" moves which act on a larger set of labels than the expansion and swap algorithms. We evaluate our method on problems of image restoration, in-painting, and stereo correspondence. Our results show that we are able to get more accurate answers, both in terms of the energy, which is the direct goal, and in terms of accuracy, which is an indirect, but more important goal.

In recent years, stereo correspondence algorithms based on graph cuts have gained popularity due to the significant improvement in accuracy over the local methods. Even though there has been a noticeable progress in efficient max-flow algorithms, the computational cost for graph cut stereo is still quite heavy, especially if the disparity search range is large. In this paper, we investigate and compare several ways of limiting the disparity search range. We show that the immediately obvious ideas based on thresholding or the hierarchical approach do not work reasonably well. We do, however, find that we can utilise the results of fast local correspondence methods for disparity range reduction of the more expensive graph cuts method. The idea is to understand and exploit the ways in which the local stereo correspondence methods fail. We are able to achieve 2.8 times average speed-up with only a modest degradation in performance, 1.7 % average energy increase. 1

Dynamic programming on a scanline is one of the oldest and still popular methods for stereo correspondence. While efficient, its performance is far from the state of the art because the vertical consistency between the scanlines is not enforced. We re-examine the use of dynamic programming for stereo correspondence by applying it to a tree structure, as opposed to the individual scanlines. The nodes of this tree are all the image pixels, but only the "most important" edges of the 4 connected neighbourhood system are included. Thus our algorithm is truly a global optimization method because disparity estimate at one pixel depends on the disparity estimates at all the other pixels, unlike the scanline based methods. We evaluate our algorithm on the benchmark Middlebury database. The algorithm is very fast; it takes only a fraction of a second for a typical image. The results are considerably better than that of the scanline based methods. While the results are not the state of the art, our algorithm offers a good trade off in terms of accuracy and computational efficiency.

We develop a fast and accurate variable window approach. The two main ideas for achieving accuracy are choosing a useful range of window sizes/shapes for evaluation and developing a new window cost which is particularly suitable for comparing windows of different sizes. The speed of our approach is due to the integral image technique, which allows computation of our window cost over any rectangular window in constant time, regardless of window size. Our method ranks in the top four on the Middlebury stereo database with ground truth, and performs best out of methods which have comparable efficiency.

We present a method for extracting dense features from stereo and motion sequences. Our dense feature is defined symmetrically with respect to both images, and it is extracted during the correspondence process, not in a separate preprocessing step. For dense feature extraction we use the graph cuts algorithm, recently shown to be a powerful optimization tool for vision. Our algorithm produces semi-dense answer, with very accurate results in areas where features are detected, and no matches in featureless regions. Unlike sparse feature based algorithms, we are able to extract accurate correspondences in some untextured regions, provided that there are texture cues on the boundary. Our algorithm is robust and does not require parameter tuning.

One of the earliest and still widely used methods for dense stereo correspondence is based on matching windows of pixels. The main difficulty of this method is choosing a window of appropriate size and shape. Small windows may lack sufficient intensity variation for reliable matching, while large windows smooth out disparity discontinuities. We propose an algorithm to choose a window size and shape by optimizing over a large class of "compact" windows. The word compact is used informally to reflect the fact that the ratio of perimeter to area of our windows is small. We believe that this is the first area based method which efficiently constructs nonrectangular windows. Fast optimization over compact windows is achieved via the minimum ratio cycle algorithm for graphs. The algorithm has only a few parameters which are easy to fix.

We present a new feature based algorithm for stereo correspondence. Most of the previous feature based methods match sparse features like edge pixels, producing only sparse disparity maps. Our algorithm detects and matches dense features between the left and right images of a stereo pair, producing a semi-dense disparity map. Our dense feature is defined with respect to both images of a stereo pair, and it is computed during the stereo matching process, not a preprocessing step. In essence, a dense feature is a connected set of pixels in the left image and a corresponding set of pixels in the right image such that the intensity edges on the boundary of these sets are stronger than their matching error (which is basically the difference in intensities between corresponding boundary pixels). Our algorithm produces accurate semi-dense disparity maps, leaving featureless regions in the scene unmatched It is robust, requires little parameter tuning, can handle brightness differences between images, and is fast (linear complexity).

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.

We present a new image segmentation algorithm based on graph cuts. Our main tool is separation of each pixel p from a special point outside the image by a cut of a minimum cost. Such a cut creates a group of pixels C/sub p/ around each pixel. We show that these groups C/sub p/ are either disjoint or nested in each other and so they give a natural segmentation of the image. In addition this property allows an efficient implementation of the algorithms because for most pixels p the computation of C/sub p/ is not performed on the whole graph. We inspect all C/sub p/ and discard those which are not interesting, for example if they are too small. This procedure automatically groups small components together or merges them into nearby large clusters. Effectively, our segmentation is performed by extracting significant non-intersecting closed contours. We present interesting segmentation results on real and artificial images.

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.

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.