We propose a fully automatic approach to restore aged old line drawings. We decompose the task into two subtasks: the line extraction subtask, which aims to extract line fragments and remove the paper texture background, and the restoration subtask, which fills in possible gaps and deterioration of the lines to produce a clean line drawing. Our approach is based on a convolutional neural network that consists of two sub-networks corresponding to the two subtasks. They are trained as part of a single framework in an end-to-end fashion. We also introduce a new dataset consisting of manually annotated sketches by Leonardo da Vinci which, in combination with a synthetic data generation approach, allows training the network to restore deteriorated line drawings. We evaluate our method on challenging 500-year-old sketches and compare with existing approaches with a user study, in which it is found that our approach is preferred 72.7% of the time.

We tackle the problem of multi-label classification of fashion images, learning from noisy data with minimal human supervision. We present a new dataset of full body poses, each with a set of 66 binary labels corresponding to the information about the garments worn in the image obtained in an automatic manner. As the automatically-collected labels contain significant noise, we manually correct the labels for a small subset of the data, and use these correct labels for further training and evaluation. We build upon a recent approach that both cleans the noisy labels and learns to classify, and introduce simple changes that can significantly improve the performance.

In this work, we perform an experimental analysis of the differences of both how humans and machines see and distinguish fashion styles. For this purpose, we propose an expert-curated new dataset for fashion style prediction, which consists of 14 different fashion styles each with roughly 1,000 images of worn outfits. The dataset, with a total of 13,126 images, captures the diversity and complexity of modern fashion styles. We perform an extensive analysis of the dataset by benchmarking a wide variety of modern classification networks, and also perform an in-depth user study with both fashion-savvy and fashion-naïve users. Our results indicate that, although classification networks are able to outperform naive users, they are still far from the performance of savvy users, for which it is important to not only consider texture and color, but subtle differences in the combination of garments.

We present an integral framework for training sketch simplification networks that convert challenging rough sketches into clean line drawings. Our approach augments a simplification network with a discriminator network, training both networks jointly so that the discriminator network discerns whether a line drawing is real training data or the output of the simplification network, which, in turn, tries to fool it. This approach has two major advantages: first, because the discriminator network learns the structure in line drawings, it encourages the output sketches of the simplification network to be more similar in appearance to the training sketches. Second, we can also train the networks with additional unsupervised data: by adding rough sketches and line drawings that are not corresponding to each other, we can improve the quality of the sketch simplification. Thanks to a difference in the architecture, our approach has advantages over similar adversarial training approaches in stability of training and the aforementioned ability to utilize unsupervised training data. We show how our framework can be used to train models that significantly outperform the state of the art in the sketch simplification task, despite using the same architecture for inference. We also present an approach to optimize for a single image, which improves accuracy at the cost of additional computation time. Finally, we show that, using the same framework, it is possible to train the network to perform the inverse problem, i.e., convert simple line sketches into pencil drawings, which is not possible using the standard mean squared error loss. We validate our framework with two user tests, in which our approach is preferred to the state of the art in sketch simplification 88.9% of the time.

Banknotes generally have different designs according to their denominations. Thus, if characteristics of each design can be recognized, they can be used for sorting banknotes according to denominations. Portrait in banknotes is one such characteristic that can be used for classification. A sorting system for banknotes can be designed that recognizes portraits in each banknote and sort it accordingly. In this paper, our aim is to automate the configuration of such a sorting system by automatically detect portraits in sample banknotes, so that it can be quickly deployed in a new target country. We use Convolutional Neural Networks to detect portraits in completely new set of banknotes robust to variation in the ways they are shown, such as the size and the orientation of the face.

We propose a novel approach to unsupervised video segmentation based on the trajectories of Temporal Super-pixels (TSPs). We cast the segmentation problem as a trajectory-labeling problem and define a Markov random field on a graph in which each node represents a trajectory of TSPs, which we minimize using a new two-stage optimization method we developed. The adaption of the trajectories as basic building blocks brings several advantages over conventional superpixel-based methods, such as more expressive potential functions, temporal coherence of the resulting segmentation, and drastically reduced number of the MRF nodes. The most important effect is, however, that it allows more robust segmentation of the foreground that is static in some frames. The method is evaluated on a subset of the standard SegTrack benchmark and yields competitive results against the state-of-the-art methods.

Improvement in medical imaging technologies has made it possible for doctors to directly look into patients' bodies in ever finer details. However, since only the cross-sectional image can be directly seen, it is essential to segment the volume into organs so that their shape can be seen as 3D graphics of the organ boundary surfaces. Segmentation is also important for quantitative measurement for diagnosis. Here, we introduce a novel higher-precision method to segment multiple organs using graph cuts within medical images such as CT-scanned images. We utilize super voxels instead of voxels as the units of segmentation, i.e., the nodes in the graphical model, and design the energy function to minimize accordingly. We utilize SLIC super voxel algorithm and verify the performance of our segmentation algorithm by energy minimization comparing to the ground truth.

We present a novel approach for image completion that results in images that are both locally and globally consistent. With a fully-convolutional neural network, we can complete images of arbitrary resolutions by filling in missing regions of any shape. To train this image completion network to be consistent, we use global and local context discriminators that are trained to distinguish real images from completed ones. The global discriminator looks at the entire image to assess if it is coherent as a whole, while the local discriminator looks only at a small area centered at the completed region to ensure the local consistency of the generated patches. The image completion network is then trained to fool the both context discriminator networks, which requires it to generate images that are indistinguishable from real ones with regard to overall consistency as well as in details. We show that our approach can be used to complete a wide variety of scenes. Furthermore, in contrast with the patch-based approaches such as PatchMatch, our approach can generate fragments that do not appear elsewhere in the image, which allows us to naturally complete the images of objects with familiar and highly specific structures, such as faces.

We propose a novel data-driven approach for automatically detecting and completing gaps in line drawings with a Convolutional Neural Network. In the case of existing inpainting approaches for natural images, masks indicating the missing regions are generally required as input. Here, we show that line drawings have enough structures that can be learned by the CNN to allow automatic detection and completion of the gaps without any such input. Thus, our method can find the gaps in line drawings and complete them without user interaction. Furthermore, the completion realistically conserves thickness and curvature of the line segments. All the necessary heuristics for such realistic line completion are learned naturally from a dataset of line drawings, where various patterns of line completion are generated on the fly as training pairs to improve the model generalization. We evaluate our method qualitatively on a diverse set of challenging line drawings and also provide quantitative results with a user study, where it significantly outperforms the state of the art.

We present a novel technique to automatically colorize grayscale images that combines both global priors and local image features. Based on Convolutional Neural Networks, our deep network features a fusion layer that allows us to elegantly merge local information dependent on small image patches with global priors computed using the entire image. The entire framework, including the global and local priors as well as the colorization model, is trained in an end-to-end fashion. Furthermore, our architecture can process images of any resolution, unlike most existing approaches based on CNN. We leverage an existing large-scale scene classification database to train our model, exploiting the class labels of the dataset to more efficiently and discriminatively learn the global priors. We validate our approach with a user study and compare against the state of the art, where we show significant improvements. Furthermore, we demonstrate our method extensively on many different types of images, including black-and-white photography from over a hundred years ago, and show realistic colorizations.

In this paper, we present a novel technique to simplify sketch drawings based on learning a series of convolution operators. In contrast to existing approaches that require vector images as input, we allow the more general and challenging input of rough raster sketches such as those obtained from scanning pencil sketches. We convert the rough sketch into a simplified version which is then amendable for vectorization. This is all done in a fully automatic way without user intervention. Our model consists of a fully convolutional neural network which, unlike most existing convolutional neural networks, is able to process images of any dimensions and aspect ratio as input, and outputs a simplified sketch which has the same dimensions as the input image. In order to teach our model to simplify, we present a new dataset of pairs of rough and simplified sketch drawings. By leveraging convolution operators in combination with efficient use of our proposed dataset, we are able to train our sketch simplification model. Our approach naturally overcomes the limitations of existing methods, e. g., vector images as input and long computation time; and we show that meaningful simplifications can be obtained for many different test cases. Finally, we validate our results with a user study in which we greatly outperform similar approaches and establish the state of the art in sketch simplification of raster images.

We propose a novel segmentation method based on energy minimization of higher-order potentials. We introduce higher-order terms into the energy to incorporate prior knowledge on the shape of the segments. The terms encourage certain sets of pixels to be entirely in one segment or the other. The sets can for instance be smooth curves in order to help delineate pulmonary vessels, which are known to run in almost straight lines. The higher-order terms can be converted to submodular first-order terms by adding auxiliary variables, which can then be globally minimized using graph cuts. We also determine the weight of these terms, or the degree of the aforementioned encouragement, in a principled way by learning from training data with the ground truth. We demonstrate the effectiveness of the method in a real-world application in fully-automatic pulmonary artery-vein segmentation in CT images.

We propose a novel segmentation method based on higher-order graph cuts which enables the utilization of prior knowledge regarding anatomical shapes. We applied the method for segmentation of psoas major muscles by using combinations of logistic curves which representing their shapes. The higher-order terms consisting of variables (voxels) just inside or outside of the estimated shapes are added to the energy function to encourage the segmentation results to fit to the shapes. We verified the effectiveness of the method with 20 abdominal CT images. By comparing the segmentation results to the ground truth data prepared by a clinical expert, we validated the method where it achieved the Jaccard similarity coefficient (JSC) of 75.4 % (right major) and 77.5 % (left major). We also confirmed that the proposed method worked well for thick CT images.

We propose a novel approach for learning features from weakly-supervised data by joint ranking and classification. In order to exploit data with weak labels, we jointly train a feature extraction network with a ranking loss and a classification network with a cross-entropy loss. We obtain high-quality compact discriminative features with few parameters, learned on relatively small datasets without additional annotations. This enables us to tackle tasks with specialized images not very similar to the more generic ones in existing fully-supervised datasets. We show that the resulting features in combination with a linear classifier surpass the state-of-the-art on the Hipster Wars dataset despite using features only 0.3% of the size. Our proposed features significantly outperform those obtained from networks trained on ImageNet, despite being 32 times smaller (128 single-precision floats), trained on noisy and weakly-labeled data, and using only 1.5% of the number of parameters.

We propose a method for understanding a room from a single spherical image, i.e., reconstructing and identifying structural planes forming the ceiling, the floor, and the walls in a room. A spherical image records the light that falls onto a single viewpoint from all directions and does not require correlating geometrical information from multiple images, which facilitates robust and precise reconstruction of the room structure. In our method, we detect line segments from a given image, and classify them into two groups: segments that form the boundaries of the structural planes and those that do not. We formulate this problem as a higher-order energy minimization problem that combines the various measures of likelihood that one, two, or three line segments are part of the boundary. We minimize the energy with graph cuts to identify segments forming boundaries, from which we estimate structural the planes in 3D. Experimental results on synthetic and real images confirm the effectiveness of the proposed method.

We present an approach for the detection of buildings in multispectral satellite images. Unlike 3-channel RGB images, satellite imagery contains additional channels corresponding to different wavelengths. Approaches that do not use all channels are unable to fully exploit these images for optimal performance. Furthermore, care must be taken due to the large bias in classes, e.g., most of the Earth is covered in water and thus it will be dominant in the images. Our approach consists of training a Convolutional Neural Network (CNN) from scratch to classify multispectral image patches taken by satellites as whether or not they belong to a class of buildings. We then adapt the classification network to detection by converting the fully-connected layers of the network to convolutional layers, which allows the network to process images of any resolution. The dataset bias is compensated by subsampling negatives and tuning the detection threshold for optimal performance. We have constructed a new dataset using images from the Landsat 8 satellite for detecting solar power plants and show our approach is able to significantly outperform the state-of-the-art. Furthermore, we provide an in-depth evaluation of the seven different spectral bands provided by the satellite images and show it is critical to combine them to obtain good results.

本稿では,1 枚の球面画像から単純な部屋の形状を復元する手法を提案する.広い視野を持つ球面画像によって,よりロバストに部屋の構造を認識することができる.部屋の形状は,壁や天井や床といった長方形の面の境界の線分の集合で表される.提案手法では,高階エネルギー最小化によって,検出された線分を境界かそうでない線分に分類する.そして,境界の線分を用いて,壁や天井や床といった部屋を構成する面を推定する.実画像を用いて実験を行い,部屋を構成する面が正しく推定できることを検証した.

In medical image analysis, segmentation of medical images such as Computed Tomography (CT) volumetric images is necessary for further medical image analysis and computer aided intervention. We propose a method for medical image segmentation by higher-order energy minimization. Specifically, we introduce a higher-order term that describes the continuity around the edge points of a CT image. The parameters of the energy terms are determined according to various conditional probabilities learned from sample data with the ground truth. Then we minimize the energy using graph cuts and evaluate the effectiveness of the introduction of the term into the traditional energy.

Medical image segmentation, e.g., Computed Tomography (CT) volume segmentation, is necessary for further medical image analysis and computer aided intervention. In the standard energy minimization scheme for medical image segmentation, three terms exist in the energy: the data term, the Potts smoothing term, and the probabilistic atlas term. In this paper, we propose a novel potential function that extends the data term. The discriminability of the existing data term, which fully depends on how distinctive the objects of interest appear on CT volume, has problem when some of the objects have similar or same CT values. We overcome this limitation by considering the CT values of a pair of neighboring voxels. Increasing the voxel of interest to be evaluated, the data term become more discriminable even if some objects of interest have similar CT values. We also propose to learn the probability of the neighboring data term for each sub-region, not for each voxel. The proposed neighboring data term can be regarded as to combine the standard data term and the probabilistic atlas.

We present an appearance-based linear regression method for pose estimation from a single image of an asteroid, which can have any pose in the full space of three degree-of-freedom rotation parameters. The method is characterized by its division of the parameter space into multiple regions. Given a large number of training images with known pose parameters, we learn the relationship between the images and the pose parameters, separately for each parameter region, using the standard linear pose estimation. We also create a common subspace such that, when projected to it, the difference between images in the same parameter region tends to collapse. In estimating the pose of an input image, we project it onto the common subspace to determine the parameter region. We apply the method for pose estimation from asteroid images and report the experimental results.

There is a series of earth observation satellites called Landsat, which send a very large amount of image data every day such that it is hard to analyze manually. Thus an effective application of machine learning techniques to automatically analyze such data is called for. In surface object recognition, which is one of the important applications of such data, the distribution of a specific object on the surface is surveyed. In this paper, we propose and compare two methods for surface object recognition, one using the convolutional neural network (CNN) and the other support vector machine (SVM). In our experiments, CNN showed higher performance than SVM. In addition, we observed that the number of negative samples have a influence on the performance, and it is necessary to select the number of them for practical use.

多臓器の同時セグメンテーションを CRF を用いて行う手法を提案する．従来手法では，隣接画素間の影響を与える項は事前確率のみに基づいていたが，提案手法では，入力画像に依存する条件付確率に基づいた 1 階のデータ項を用いる．真値を伴うデータセットから学習した 1 階のデータ項を用いたセグメンテーション実験の結果を報告する．

一般物体認識では，近年 Deep Learning を用いた手法が注目されており，その １ つである Convolutional Neural Network （CNN） は特に優れた結果を示している．しかし，どのような構成の CNN が画像認識に有用であるかは理論的に示されておらず，ノウハウが必要なのが現状である．本研究では CNN を用いた一般物体認識手法において認識精度を変化させる要因の解析を行う．具体的には，Krizhevsky らの手法において，畳込み層のパラメータが認識精度に与える影響を解析するとともに，学習手法の変更が認識精度に与える影響を調べた．

画像からの物体・シーンの 3 次元形状の復元において，代表的な手法である多視点ステレオ法と照度差ステレオ法では，物体に対するカメラの位置と光源環境の双方が異なるときには，正確な 3 次元形状を推定することができない．より正確な復元を行うためには，各画像ごとの物体に対する光源方向の推定が必要である．本研究では，多視点照度差画像から 3 次元形状を復元するために必要な光源方向を，入力画像のみを用いて推定する手法を提案し，合成画像を使った予備的な実験の結果を報告する．

We propose a novel segmentation method based on multi-label graph cuts utilizing higher-order potentials to impose shape priors. Each higher-order potential is defined with respect to a candidate shape, and takes a low value if and only if most of the voxels inside the shape are foreground and most of those outside are background. We apply this technique to coronary lumen and plaque segmentation in CT angiography, exploiting the prior knowledge that the vessel walls tend to be tubular, whereas calcified plaques are more likely globular. We use the Hessian analysis to detect the candidate shapes and introduce corresponding higher-order terms into the energy. Since each higher-order term has any effect only when its highly specific condition is met, we can add many of them at possible locations and sizes without severe side effects. We show the effectiveness of the method by testing it on the standardized evaluation framework presented at MICCAI segmentation challenge 2012. The method achieved values comparable to the best in each of the sensitivity and positive predictive value, placing it at the top in average rank.

We introduce a method to reduce most higher-order terms of Markov Random Fields with binary labels into lower-order ones without introducing any new variables, while keeping the minimizer of the energy unchanged. While the method does not reduce all terms, it can be used with existing techniques that transforms arbitrary terms (by introducing auxiliary variables) and improve the speed. The method eliminates a higher-order term in the polynomial representation of the energy by finding the value assignment to the variables involved that cannot be part of a global minimizer and increasing the potential value only when that particular combination occurs by the exact amount that makes the potential of lower order. We also introduce a faster approximation that forego the guarantee of exact equivalence of minimizer in favor of speed. With experiments on the same field of experts dataset used in previous work, we show that the roof-dual algorithm after the reduction labels significantly more variables and the energy converges more rapidly.

We propose a HOG-based hand gesture recognition system running on a mobile device. Input data is a video of hand gesture taken by a mobile device. The input data is compared with a database storing hand gesture images, which was synthesized with rotation variation. The comparison is done based on their HOG features and the gesture corresponding to the best-matched image is returned as the result. The recognition algorithm is implemented on a client-server system. The proposed system is applied to American Sign Language (ASL) alphabet recognition problem. The experimental results show that the proposed recognition algorithm improves HOG's robustness under rotation change and compare processing time with different network configurations.

We extend the concept of generalized roof duality from pseudo-boolean functions to real-valued functions over multi-label variables. In particular, we prove that an analogue of the persistency property holds for energies of any order with any number of linearly ordered labels. Moreover, we show how the optimal submodular relaxation can be constructed in the first-order case.

We introduce a transformation of general higher-order Markov random field with binary labels into a first-order one that has the same minima as the original. Moreover, we formalize a framework for approximately minimizing higher-order multilabel MRF energies that combines the new reduction with the fusion-move and QPBO algorithms. While many computer vision problems today are formulated as energy minimization problems, they have mostly been limited to using first-order energies, which consist of unary and pairwise clique potentials, with a few exceptions that consider triples. This is because of the lack of efficient algorithms to optimize energies with higher-order interactions. Our algorithm challenges this restriction that limits the representational power of the models so that higher-order energies can be used to capture the rich statistics of natural scenes. We also show that some minimization methods can be considered special cases of the present framework, as well as comparing the new method experimentally with other such techniques.

e introduce a new technique that can reduce any higher-order Markov random field with binary labels into a first-order one that has the same minima as the original. Moreover, we combine the reduction with the fusion-move and Q B algorithms to optimize higher-order multi-label problems. hile many vision problems today are formulated as energy minimization problems, they have mostly been limited to using first-order energies, which consist of unary and pairwise clique potentials, with a few exceptions that consider triples, his is because of the lack of efficient algorithms to optimize energies with higher-order interactions. ur algorithm challenges this restriction that limits the representational power of the models, so that higher-order energies can be used to capture the rich statistics of natural scenes. o demonstrate the algorithm, we minimize a third-order energy, which allows clique potentials with up to four pixels, in an image restoration problem. he problem uses the Fields of Experts model, a learned spatial prior of natural images that has been used to test two belief propagation algorithms capable of optimizing higher-order energies. he results show that the algorithm exceeds the B algorithms in both optimization performance and speed.

Markov Random Field is now ubiquitous in many formulations of various vision problems. Recently, optimization of higher-order potentials became practical using higher-order graph cuts: the combination of i) the fusion move algorithm, ii) the reduction of higher-order binary energy minimization to first-order, and iii) the QPBO algorithm. In the fusion move, it is crucial for the success and efficiency of the optimization to provide proposals that fits the energies being optimized. For higher-order energies, it is even more so because they have richer class of null potentials. In this paper, we focus on the efficiency of the higher-order graph cuts and present a simple technique for generating proposal labelings that makes the algorithm much more efficient, which we empirically show using examples in stereo and image denoising.

In spite of the great progress in stereo matching algorithms, the prior models they use, i.e., the assumptions about the probability to see each possible surface, have not changed much in three decades. Here, we introduce a novel prior model motivated by psychophysical experiments. It is based on minimizing the total sum of the absolute value of the Gaussian curvature over the disparity surface. Intuitively, it is similar to rolling and bending a flexible paper to fit to the stereo surface, whereas the conventional prior is more akin to spanning a soap film. Through controlled experiments, we show that the new prior outperforms the conventional models, when compared in the equal setting.

Sometimes called the smoothing assumption, the prior model of a stereo matching algorithm is the algorithm's expectation on the surfaces in the world. Any stereo algorithm makes assumptions about the probability to see each surface that can be represented in its representation system. Although the past decade has seen much continued progress in stereo matching algorithms, the prior models used in them have not changed much in three decades: most algorithms still use a smoothing prior that minimizes some function of the difference of depths between neighboring sites, sometimes allowing for discontinuities.
However, one system seems to use a very different prior model from all other systems: the human vision system. In this paper, we first report the observations we made in examining human disparity interpolation using stereo pairs with sparse identifiable features. Then we mathematically analyze the implication of using current prior models and explain why the human system seems to use a model that is not only different but in a sense diametrically opposite from all current models. Finally, we propose two candidate models that reflect the behavior of human vision. Although the two models look very different, we show that they are closely related.

Any complete theory of human stereopsis must model not only how the correspondences between locations in the two views are determined and the depths are recovered from their disparity, but also how the ambiguity arising from such factors as noise, periodicity, and large regions of constant intensity are resolved and missing data are interpolated. In investigating this process of recovering surface structure from sparse disparity information, using stereo pairs with sparse identifiable features, we made an observation that contradicts all extant models. It suggests the inadequacy of retinotopic representation in modeling surface perception in this stage. We also suggest a possible alternative theory, which is a minimization of the modulus of Gaussian curvature. (c) 2005 Elsevier Ltd. All rights reserved.

The representation of objects in images as tree structures is of great interest to vision, as they can represent articulated objects such as people as well as other structured objects like arteries in human bodies, roads, circuit board patterns, etc. Tree structures are often related to the symmetry axis representation of shapes, which captures their local symmetries. Algorithms have been introduced to detect (i) open contours in images in quadratic time (ii) closed contours in images in cubic time, and (iii) tree structures from contours in quadratic time. The algorithms are based on dynamic programming and Single Source Shortest Path algorithms. However, in this paper, we show that the problem of finding tree structures in images in a principled manner is a much harder problem. We argue that the optimization problem of finding tree structures in images is essentially equivalent to a variant of the Steiner Tree problem, which is NP-hard. Nevertheless, an approximate polynomial-time algorithm for this problem exists: we apply a fast implementation of the Goemans-Williamson approximate algorithm to the problem of finding a tree representation after an image is transformed by a local symmetry mapping. Examples of extracting tree structures from images illustrate the idea and applicability of the approximate method.

We introduce a method to solve exactly a first order Markov Random Field optimization problem in more generality than was previously possible. The MRF shall have a prior term that is convex in terms of a linearly ordered label set. The method maps the problem into a minimum-cut problem for a directed graph, for which a globally optimal solution can be found in polynomial time. The convexity of the prior function in the energy is shown to be necessary and sufficient for the applicability of the method.

We describe anew form of energy functional for the modeling and identification of regions in images. The energy is defined on the space of boundaries in the image domain and can incorporate very general combinations of modeling information both from the boundary (intensity gradients, etc.) and from the interior of the region (texture, homogeneity, etc.). We describe two polynomial-time digraph algorithms for finding the global minima of this energy. One of the algorithms is completely general, minimizing the functional for any choice of modeling information. It runs in a few seconds on a 256x256 image. The other algorithm applies to a subclass of functionals, but has the advantage of being extremely parallelizable. Neither algorithm requires initialization.

We present a method for region identification in multiple images. A set of regions in different images and the correspondences on their boundaries can be thought of as a boundary in the multi-dimensional space formed by the product of the individual image domains. We minimize an energy functional on the space of such boundaries, thereby identifying simultaneously both the optimal regions in each image and the optimal correspondences on their boundaries. We use a ratio form for the energy functional, thus enabling the global minimization of the energy functional using a polynomial time graph algorithm, among other desirable properties. We choose a simple form for this energy that favours boundaries that lie on high intensity gradients in each image, while encouraging correspondences between boundaries in different images that match intensity values. The latter tendency is weighted by a novel heuristic energy that encourages the boundaries to lie on disparity or optical flow discontinuities, although no dense optical flow or disparity map is computed.

We propose a graph optimization method for the restoration of gray-scale images. We consider an arbitrary noise model for each pixel location. We also consider a smooth constraint where the potentials between neighbor pixels are convex functionals. We show how to map this problem to a directed flow graph. Then, a global optimal solution is obtained via the use of the maximum-flow algorithm. The algorithm runs in a polynomial time with respect to the size of the image.

We propose a method for segmenting gray-value images. By segmentation, we mean a map from the set of pixels To a small set of levels such that each connected component of the set of pixels with the same level forms a relatively large and "meaningful" region. The method finds a set of levels with associated gray values by first finding junctions in the image and their seeking a minimum set of threshold values that preserves the junctions. Then it finds a segmentation map that maps each pixel to the level with the closest gray value to the pixel data, within a smoothness constraint. For a convex smoothing penalty, we show the global optimal solution for an energy function that fits the data can be obtained in a polynomial time, by a novel use of the maximum-flow algorithm. Our approach is in contrast to a view in computer vision where segmentation is driven by intensity, gradient, usually not yielding closed boundaries.