N Lermé

F Malgouyres
email: francois.malgouyres@math.univ-toulouse.fr

M Lermé

M Malgouyres

A Reduction Method For Graph Cut Optimization

Keywords: reduction, graph cuts, segmentation, filtering

In a couple of years, graph cuts methods appeared as a leading method in computer vision and graphics due to their efficiency in computing globally optimal solutions. Such an approach remains however impractical for large-scale problems due to the memory requirements for storing the graphs.

Among strategies to overcome this situation, an existing strategy consists in reducing the size of these graphs by only adding the nodes which satisfy a local condition. In the image segmentation context, this means for instance that when unary terms are locally strong, the remaining nodes are typically located in a thin band around the object of interest to segment. In this paper, we empirically prove on a large number of experiments that the distance between the global minimizer and the minimizer obtained with an heuristic test, remains very low. In addition to this preliminary work, we detail existing strategies to reduce the memory footprint of graph cuts and provide extra parameters for further reducing the graphs and removing isolated speckles and islands due to noise in the segmentation.

I. INTRODUCTION

Graph cuts are a discrete optimization method based on maximum-flow / minimum-cut (maxflow / min-cut) computations in graphs for minimizing energies frequently arising in computer vision and graphics. Since last decades, this technique is become a cornerstone beside these communities for solving a wide range of problems such as denoising, segmentation, registration, stereo, scene reconstruction, optical flow, etc. We refer the reader to [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] for typical applications of graph cuts. Since seminal work of [START_REF] Greig | Exact maximum a posteriori estimation for binary images[END_REF] for denoising binary images, graph cuts have known a quick development (after a 10 year silence) mainly due to the introduction of a fast max-flow algorithm [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] and efficient heuristics for solving multi-labels tasks [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF].

In parallel, technological advances in image acquisition have both increased the amount and the diversity of data to process. As an illustration, in the satellite SPOT-5 launched by Arianespace in 2002, the high geometric resolution sensors can capture multispectral and panchromatic images with an imaging swath of 60 km × 60 km. Each image has a size of 12000 × 12000 which amounts to about 1GB of data. Similarly, latest medical imaging systems are able to acquire 3D and 3D+t volume data with several billions of voxels.

Although graph cuts can efficiently solve a wide range of problems, their huge memory consumption remains a drawback. To obtain high-resolution output, graph cuts usually build massive multidimensional grid-like graphs containing billions of nodes and even more edges. These graphs do not fit in memory. Currently, most of the max-flow algorithms are totally impracticable to solve such large scale optimization problems. To overcome this situation, some amount of work has recently been done in this direction and a number of heuristics [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Kohli | Uncertainty driven multi-scale energy optimization[END_REF], [START_REF] Li | Lazy Snapping[END_REF], [START_REF] Stawiaski | Computing approximate geodesics and minimal surfaces using watershed and graph-cuts[END_REF], [START_REF] Cigla | Region-based image segmentation via graph cuts[END_REF] and exact1 methods [START_REF] Delong | A scalable graph-cut algorithm for N-D grids[END_REF], [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF], [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF], [START_REF] Lempitsky | Global optimization for shape fitting[END_REF] have been proposed. However, the heuristics generally either fail to fully capture shape complexities [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Kohli | Uncertainty driven multi-scale energy optimization[END_REF] or strongly depend on a low-level segmentation tool [START_REF] Li | Lazy Snapping[END_REF], [START_REF] Stawiaski | Computing approximate geodesics and minimal surfaces using watershed and graph-cuts[END_REF], [START_REF] Cigla | Region-based image segmentation via graph cuts[END_REF].

In this paper, we give a simple condition for testing if a node in a graph is really useful to the max-flow computation [START_REF] Lermé | Reducing graphs in graph cut segmentation[END_REF]. The reduced graph is progressively built by only adding the nodes which satisfy this condition. This leads to a straightforward algorithm with a worstcase additional complexity similar to a convolution. Thus, in the manner of [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Kohli | Uncertainty driven multi-scale energy optimization[END_REF], [START_REF] Lempitsky | Global optimization for shape fitting[END_REF],

the remaining nodes are typically located in a narrow band surrounding the object edges to segment. However, unlike [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Li | Lazy Snapping[END_REF], [START_REF] Stawiaski | Computing approximate geodesics and minimal surfaces using watershed and graph-cuts[END_REF], [START_REF] Cigla | Region-based image segmentation via graph cuts[END_REF], the proposed method can accurately segment thin structures without requiring any other low-level segmentation tool. Experiments clearly show that the solutions obtained on the reduced graphs are identical to the solutions obtained on the whole graphs. Furthermore, the time required by the reduction algorithm is sometimes compensated by the time for computing the max-flow on the reduced graph. This paper complements the preliminary work of [START_REF] Lermé | Reducing graphs in graph cut segmentation[END_REF] by giving algorithmic details, a detailed bibliography on the subject and a large number of experiments for segmenting multidimensional grayscale and color images. Also, two extra parameters are introduced for both further reducing the size of the graphs and removing small segments in the segmentation due to noise. We want also to mention that the method described in this paper is protected by a patent [START_REF]Reduction of "vision graphs[END_REF] and has already been applied to minimize an energy designed for interactive lung tumor segmentation [START_REF] Lermé | Fast and memory efficient segmentation of lung tumors using graph cuts[END_REF].

The rest of this document is organized as follows. In Section II, we present the state-of-the-art of methods to overcome the memory problem of graph cuts. We review in Section III the graph cuts framework in the image segmentation context. Then, we detail our strategy for reducing graphs in Section IV and present a large number of experiments for segmenting 2D, 2D+t and 3D grayscale/color images using two different energy models. We finally provide an in-depth look for measuring the influence of the reduction parameters in Section IV.

II. STATE-OF-THE-ART

The methods present in the literature for getting round the well known memory problem of graph cuts can be divided into two main categories: single-machine algorithms and parallelized/distributed algorithms. Let us now review these algorithms in this order.

A. Sequential strategies

To our best knowledge, Li et al. seem to be the first ones to tackle the problem of memory consumption of graph cuts [START_REF] Li | Lazy Snapping[END_REF]. Their algorithm works as follows. First, the image is partitioned into small and numerous homogeneous regions thanks to a low-level segmentation algorithm such as watershed [START_REF] Li | Lazy Snapping[END_REF], [START_REF] Stawiaski | Computing approximate geodesics and minimal surfaces using watershed and graph-cuts[END_REF] or mean shift [START_REF] Cigla | Region-based image segmentation via graph cuts[END_REF]. A region adjacency graph is produced where each region corresponds to a node in the graph. Then, the max-flow is computed on this graph for getting the segmentation. The underlying assumption is that the final contours are embedded into the pre-segmentation. While this observation is generally not theoretically guaranteed, it is often verified when working on natural images not corrupted by noise. Although this approach drastically reduce the computational burden of graph cuts (about 6x faster according to [START_REF] Li | Lazy Snapping[END_REF]), the results strongly depend on the low-level segmentation algorithm used and its noise-sensitivity. Moreover, as fairly observed in [START_REF] Stawiaski | Computing approximate geodesics and minimal surfaces using watershed and graph-cuts[END_REF], this approach generally gives better results when oversegmentation occurs, losing the main benefit of such a reduction.

Others have also reported band-based heuristics using a multi-resolution scheme [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF]. The principle is to segment a low-resolution image/volume and propagate the solution to the finer level by only building the graph in a narrow band surrounding the interpolated foreground/background interface at that resolution. More specifically, the acceleration strategy consists of three stages: first, a pyramid of images is built with a coarsening operator (coarsening). Next, the coarsest image is segmented and its contours are extracted (segmentation at coarsest level). Finally, the contours are dilated and interpolated at the next higher resolution for building a new reduced graph (uncoarsening). This process continues until the bottom of the pyramid is reached. Such an approach greatly reduces time and memory consumption of standard graph cuts (about 8x faster and 4x less memory according to [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF]). Nevertheless, it generally fails to recover thin structures and is limited to the segmentation of roundish objects. In medical imaging, this is a real drawback since elongated structures like blood vessels are ubiquitous. Moreover, the parameter controlling the band dilation during the projection, plays an important role. Indeed, one usually needs this parameter to be large enough to fully capture details of various shapes complexities. On the other side, wider bands reduce the computational benefits and may also introduce potential outliers far away from the desired object contours.

To avoid the loss of details, Lombaert et al. [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF] used the information from a Laplacian pyramid. At each level, the bands are extended by including pixels whose value significantly differs between the image and the "coarsened-uncoarsened image". The idea is to capture thin structures which are not visible in the coarse image. This inclusion is controlled by a thresholding parameter which provides a smooth transition between [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF] and traditional graph cuts. Although the previous problem is notably reduced, it is still present for low-contrasted details.

Kohli et al. recently proposed a finer band-based technique. In contrast to [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], they first define an energy from the full resolution image instead of the low resolution image. Experiments show that this strategy results in significant improvements in both time and segmentation accuracy. But mostly, they compute uncertainty estimates using min-marginals2 and use them to determine which regions belong to the reduced graph. Such an approach allows to compute solutions very close to the global optimum.

In words, the motivation of [START_REF] Kohli | Uncertainty driven multi-scale energy optimization[END_REF] is clearly similar to [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF], but the strategy used is slightly different since the pyramid of images is restricted to a single one. Although this heuristic cannot ensure the retrieval of thin structures and details, their experiments indicate they are properly recovered for a wide range of parameters, and more robustly than [START_REF] Sinop | Accurate banded graph cut segmentation of thin structures using laplacian pyramids[END_REF], [START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF].

Lempitsky and Boykov presented more recently an interesting touch-expand algorithm that is able to minimize binary energy functions with graph cuts in a narrow band, while ensuring the global optimality on the solution [START_REF] Lempitsky | Global optimization for shape fitting[END_REF]. The principle is to make a band evolve around the object to segment by expanding the band when the min-cut touches its boundary. This process is iterated until the band no longer evolves. Although the algorithm quickly converges toward the global optimal solution, it strongly depends on the initialization and no bound on the band size is given. Thus, the band can progressively increase to encompass the whole volume in the worst case. However, depending on the initialization, the bands are reasonably small in the context of [START_REF] Lempitsky | Global optimization for shape fitting[END_REF] (volume reconstruction). As far as we know, this strategy has not yet been adapted to image segmentation. In particular, the benefit of this strategy strongly depends on the design of an initial band.

Finally, the approach described in [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF] is interesting and complements our work. They simplify the graphs by identifying simple edges. An edge (a, b) is said to be simple if its weight is either greater than the sum of all edge weights adjacent to a (except b) or greater than the sum of all edge weights adjacent to b (except a). This test indeed ensures that these edges are not part of the minimum cut since they cannot be saturated by any flow. Once identified, two nodes connected by a simple edge are merged together with their common edges. This process is repeated until no such edge is found. Experiments reveal that most simple edges lie between terminal nodes and pixel nodes, leading to better sparsification when unary terms are locally strong. Even with weak unary terms (strong regularization) and poor initializations 3 , the algorithm performed always faster than graph cuts.

B. Parallelized/distributed strategies

In a recent paper, Delong and Boykov design a method for solving the max-flow problem for graphs which do not fit in memory. They propose a new parallelized max-flow algorithm yielding near-linear speedup with the number of processors [START_REF] Delong | A scalable graph-cut algorithm for N-D grids[END_REF]. As an illustration, on a standard computer, segmenting a volume of size 512 × 512 × 256 takes about 100 secs on a single core against less than 20 secs on eight cores. However, numerical experiments also show that the acceleration of this scheme is very limited since it needs a large number of processors to reach the near-linear speedup and is sensitive to the amount of physical memory. Furthermore, the proposed algorithm clearly remains less efficient on small graphs than standard graph cuts and can only be applied to grid-like graphs.

More recently, Strandmark and Kahl in [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] introduced an original approach for minimizing binary energy functions in a parallelized/distributed fashion using the max-flow algorithm of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF].

The idea is to decompose the original problem into optimizable sub-problems, solve them independently and update them according to the results of the adjacent problems. This process is iterated until convergence. The key point is that optimality is guaranteed by dual decomposition.

More precisely, the solutions to the sub-problems are constrained to be equal on an overlap.

They solve the original problem by finding a saddle point of the Lagrangian of the constrained problem. This min-max problem is solved by alternating minimization over its primal variables and maximization over its dual variables. The minimizations are done independently of each other on the processing elements. The maximization combines the results obtained on the overlapping bands. It consists in an update of the dual variables. To reflect this change, the weights in the graphs corresponding to the sub-problems are modified and the corresponding solutions are recomputed. This scheme is repeated until the solutions of the variables on the overlap are equal. This iterative scheme is efficient since only a few edge costs change between iterations and then search trees can be efficiently reused [START_REF] Kohli | Dynamic graph cuts for efficient inference in markov random fields[END_REF]. Moreover, the number of edge costs which change decrease as the number of iterations increase.

Experiments in [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] for image segmentation and stereo clearly demonstrate that both faster processing on multi-core computers and the ability to solve large scale problems over a distributed network. As an illustration, such an approach is able to segment a graph requiring 131GB of memory in 38 secs. To our best knowledge, the proposed work is the first to segment 4D volume data of moderate size using graph cuts while keeping optimality on the solution. Furthermore, in the image segmentation context, the algorithm is stable over a large range of values of the regularization parameter. Nevertheless, the algorithm is slower for solving some instances where the object to segment is not uniformly spread over the image. Also, notice that the proposed strategy is only effective for graphs for which the max-flow algorithm of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] is. In particular, the latter becomes less effective than a push-relabel algorithm for dense graphs.

III. GRAPH CUTS FRAMEWORK

A. Energy minimization via graph cuts

Consider an image I : P ⊂ Z d → [0, 1] c (d > 0, c > 0) as a function, mapping each point (called pixel) p ∈ P to a value I p ∈ [0, 1] c . We define a binary segmentation as a mapping u assigning each element of P with the value 0 for the background and 1 for the object and we write u ∈ {0, 1} P . In the energy minimization approach, a popular strategy consists in minimizing a Markov Random Field of the form [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[END_REF]:

E(u) = β • p∈P E p (u p ) + (p,q)∈N E p,q (u p , u q ), (1)
among u ∈ {0, 1} P and for a fixed β ∈ R + . The neighborhood system N ⊂ P 2 is a subset of all pixel pairs (p, q) ∈ P 2 . In this context, we will use the following standard neighborhoods:

N 0 = {(p, q) ∈ P 2 | d i=1 |q i -p i | = 1} or, N 1 = {(p, q) ∈ P 2 | |q i -p i | ≤ 1 ∀1 ≤ i ≤ d},
where p i denotes the i th coordinate of p. In what follows, "connectivity 0" and "connectivity 1" respectively refer to the use of N 0 and N 1 neighborhoods4 .

In equation ( 1), the data term E p (•) is the cost for assigning the label u p to the pixel p without regards to its neighbors. On the other hand, the smoothness term E p,q (•) assumes that the boundaries of the segmentations are smooth. More precisely, it penalizes pixel pairs (p, q)

having different labels. It can also be used to better align boundaries of the segmentation on the image edges having a strong gradient. Notice that we only consider pairwise interactions between pixels and do not consider models using higher order terms.

Consider now a weighted directed graph G = (V, E, c) where V = P ∪{s, t} is the set of nodes, E ⊂ V 2 is the set of edges and c : E → R + is a weighting function defining the edge capacities.

The terminal nodes s and t are respectively called the source and the sink. Additionally, we split the set of edges E into two disjoint sets E n and E t denoting respectively n-links (neighborhood links) and t-links (terminal links):

E n = {(p, q) ∈ E | (p, q) ∈ P 2 }, E t = {(s, p) ∈ E | p ∈ P} {(p, t) ∈ E | p ∈ P}. (2)
We denote by C = (S, T ) a s-t cut which is a partition of V such that s ∈ S and t ∈ T . For any s-t cut C in G, we define the value of C by:

v(C) = (p,q)∈E p∈S,q∈T c(p, q).
We also define u C ∈ {0, 1} P as the underlying segmentation of C in G:

u C p =    0 if p ∈ T 1 if p ∈ S , ∀p ∈ P.
In other words, pixels in S belong to the object and those in T to the background.

Notice first that C → u C makes a one-to-one correspondence between s-t cuts in G and the segmentations of the image. Then, the key idea of graph cuts is to build a graph G such that for any s-t cut C in G, we have:

v(C) = E(u C ) + K, (3)
for some additional constant K ∈ R independent of C. When pairwise terms are submodular, i.e. when they satisfy

E p,q (0, 0) + E p,q (1, 1) ≤ E p,q (0, 1) + E p,q (1, 0), ∀(p, q) ∈ N ,
G can be constructed as described in [START_REF] Kolmogorov | What energy functions can be minimized via graph cuts?[END_REF]. Then, (3) guarantees that the min-cut in G corresponds to a minimizer of (1). Moreover, as it is well known, the min-cut can be efficiently computed using a max-flow algorithm such as [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF]. Again, once the min-cut C * is computed in G with a max-flow algorithm, u C * minimizes (1). In the next sections, we review two classical energy models for segmenting images with graph cuts.

B. TV+L 2 energy model

Initially introduced by Rudin, Osher and Fatemi [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF], the TV+L 2 (ROF) model and its variants have been a very active research topic in image restoration. This model has also successfully demonstrated his efficiency for segmenting cars in video [START_REF] Ranchin | Total variation and graph cuts approaches for variational segmentation[END_REF]. It is only defined on grayscale images but can of course be applied to a grayscale image resulting from a multichannel image.

In the image segmentation context, the solution is taken as a level-set 5 of the minimizer u * of

L-2 µ=0 (p,q)∈N w p,q |u µ p -u µ q | T V (u) +β u -I 2 2 , β ∈ R + , (4)
where L denotes the maximum intensity of I, . 2 denotes the Euclidean distance in R P , I ∈ R P is initial data T V (u) denotes the Total Variation of u ∈ R P and w p,q is a weight proportional to the distance between p and q. While the second term maintains a proximity to a level-set of I, the solution is regularized by the first one. Expressing the two terms of ( 4) in terms of level-sets, we observe that the µ level-set of u * is a minimizer of the binary energy

(p,q)∈N w p,q |u µ p -u µ q | T V (u µ ) +2β p∈P u µ p [(µ - 1 2 ) -I p ] + I p , (5)
among u µ ∈ {0, 1} P (see [START_REF] Darbon | Exact optimization of discrete constrained total variation minimization problems[END_REF]). The latter problem has the form described in (1) and can be minimized by a graph cut. We remind that this formulation cannot handle color images. In practice, color images need to be converted into grayscale images before they are segmented.

C. Boykov-Jolly energy model

In [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[END_REF], authors introduced an energy model for segmenting images using graph cuts. Unlike the previous model, the user can provide object (O ⊂ P) and background seeds (B ⊂ P) in an interactive fashion. The role of these seeds is twofold: reducing the cuts space and computing probability distributions of the intensity for the object and the background. Formally, we have:

   E p (1) = -log P(I p |p ∈ O) E p (0) = -log P(I p |p ∈ B)
and

E p,q (u p , u q ) = B p,q • |u p -u q |, (6)
where P(.) is a probability density function, I p ∈ [0, 1] c denotes the intensity at voxel p and B p,q is a weighting function used to map similarity between voxels to graph weights. The distribution of the object and the background are generally estimated either using normalized histograms or Gaussian mixture models. As usual, the data term favors the belonging of each pixel p ∈ P to the object or the background class while the smoothness term penalizes neighboring pixels p and q having different labels. In its simplest form, the weight of this penalization only depends on the gradient and favors boundaries with a strong gradient. Notice that the weight can also embed more complex features such as textures or gradient direction. The most common choices for these weighting functions come from the influential work of Perona and Malik on anisotropic diffusion [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF] and are used by almost every graph-based segmentation algorithms:

Gaussian: B p,q = 1 p-q 2 exp - Ip-Iq 2 2 2σ 2 , (7)
Reciprocal:

B p,q = 1 p-q 2 1 1+ Ip-Iq ω ω , (8)
where σ ∈ R + , ω > 1 represent free parameters, . 2 is the Euclidean norm (either in R d or R c ) and . ω is the ω norm. Notice that some work has been recently done to study the difference between the Gaussian and the Reciprocal weightings in a medical context (see [START_REF] Grady | Weights and topology: A study of the effects of graph construction on 3D image segmentation[END_REF]).

The experimental results in [START_REF] Grady | Weights and topology: A study of the effects of graph construction on 3D image segmentation[END_REF] show that the Reciprocal weighting (8) outperforms the Gaussian weighting [START_REF] Li | Lazy Snapping[END_REF] in terms of both absolute performance achieved on segmentation differences and stability over β values. In this paper, all experiments use the Gaussian weighting.

IV. REDUCING GRAPHS

A. Principle

As we have seen before, the memory usage for segmenting high-resolution data by graph cuts can be prohibitive. As an illustration, the max-flow algorithm of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] (version 3.0) allocates 28 P +16 E n bytes 6 , where the operator ' ' stands for cardinality of a set. One can easily observe that for a fixed amount of RAM, the maximum volume size decreases quickly as the dimension d increases. Nevertheless, as showed in [START_REF] Lermé | Reducing graphs in graph cut segmentation[END_REF], most of the nodes in the graph are useless during the max-flow computation since they are not traversed by any flow (see Figure 1). Ideally, one would like to extract the smallest possible graph G = (V , E ) from G = (V, E) while keeping the max-flow value f * in G identical or very close to the max-flow value f * in G. In words, we want to minimize the relative size of the reduced graph defined as

ρ = V V , (9)
under the constraint that f * f * . In fact, this is an ideal optimization problem which we will not try to solve since the method for determining G also needs to be (very) fast. In order to represent the potential of this idea, we represent on the middle image of Figure 1, the flow only passing through the t-links when computing the segmentation of the image of Figure 1 with the TV+L 2 model (see Section III-B). Light gray pixels (resp. dark gray pixels) indicates that a positive amount of flow passed from the source s to a node p (resp. from a node p to the sink t), for any pixel p ∈ P. Similarly, we represent on the right image of Figure 1 the outflow only passing n-links using the same model and parameters. This time, the gray is proportional to the sum of the flow leaving any node p. For the middle and the right images, gray (resp. black) First, let us introduce some terminology before describing our method for building G . In accordance with the graph construction given in [START_REF] Kolmogorov | What energy functions can be minimized via graph cuts?[END_REF], we consider (without loss of generality) that a node is linked to at most one terminal:

(s, p) ∈ E t ⇒ (p, t) ∈ E t , ∀p ∈ P.
We also summarize the t-links capacities for any node p ∈ P by:

c(p) = c(s, p) -c(p, t).
For any B ⊂ Z d (in practice, B will be a square centered at the origin) and p ∈ P, we denote by B p the set translation of B by the point p:

B p = {q + p | q ∈ B}.
For Z ⊂ P and B ⊂ Z d , we denote by Z B the dilation of Z by the structuring element B as: We also define, for any Z ⊂ P, the maximal amount of flow that might get in and out through the n-links by

Z B = {p + q | q ∈ B, p ∈ Z} = p∈Z B p .
P in (Z) = p ∈Z,q∈Z (p,q)∈N c(p, q), P out (Z) = p∈Z,q ∈Z (p,q)∈N c(p, q).
Finally, we define the maximum amount of flow passing through the t-links and the flow orientation by

A(Z) = p∈Z |c(p)|, O(Z) = p∈Z sign(c(p)),
where the function sign(•) is defined as:

sign(t) =          1 if t > 0, 0 if t = 0, - 1 otherwise.
The intuitive idea for building G is to remove from the nodes of G any Z ⊂ P such that

   either O(Z B ) = + Z B and A(Z B \ Z) ≥ P out (Z B ) , or O(Z B ) = -Z B and A(Z B \ Z) ≥ P in (Z B ) . (10)
As an illustration of these conditions, the last (resp. first) condition of the test [START_REF] Delong | A scalable graph-cut algorithm for N-D grids[END_REF] implies that all the flow that might get in (resp. out of) the region Z B does so by traversing its boundary and can be absorbed (resp. provided) by the band Z B \ Z (see Figure 2).

Building such sets Z is done by testing each individual pixel p ∈ Z. In order to do so, we know that the conjunction of conditions [START_REF] Delong | A scalable graph-cut algorithm for N-D grids[END_REF] for every set {p}, where p ∈ Z, implies (10) for Z. Considering B, a square window of size (2r + 1) (r > 0) centered at the origin, an even more conservative test for p ∈ Z is:

   either ∀q ∈ B p , c(q) ≥ +δ , or ∀q ∈ B p , c(q) ≤ -δ . ( 11
)
where δ = P (B) (2r+1) 2 -1 . Here, P (B) denotes the perimeter of B, i.e:

P (B) = max( {(p, q) : p ∈ B, q ∈ B and (p, q) ∈ N }, {(q, p) : p ∈ B, q ∈ B and (q, p) ∈ N }).
The main advantage of [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] is that it can be easily computed. If moreover

c(p, q) ≤ 1 (p, q) ∈ E,
(which is true for the energies described in Section III-B and III-C 7 ) and ( 11) holds, one can easily checks that the condition [START_REF] Delong | A scalable graph-cut algorithm for N-D grids[END_REF] holds for Z = {p}. For instance, the first condition of [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] implies:

A(B p \ {p}) = q∈Bp\{p} |c(q)|, ≥ [(2r + 1) 2 -1] • δ, ≥ P (B), ≥ P out (B p ).
In words, for any node p ∈ Z satisfying the first (resp. second) condition of [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF], all its neighbors q ∈ B p are only linked to s (resp. t) and the flow that might get in (resp. out) through t-links in B p \ {p} suffices to saturate the n-links going out of (resp. in) B p . The node p is useless and can be removed from G. Therefore, we consider G a subgraph of G such that V = P ∪ {s, t}, where:

P = {p ∈ P | (11) does not hold for p}.
The experiments presented in Section IV-C.3 confirm the dependence between the size of the reduced graph and the model parameters (see Figure 3). Indeed, when minimizing (1) via graph cuts as described in Section III-A, the t-links capacities are all multiplied by β. Thus, it is straightforward to observe that the condition [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] is more difficult to satisfy as β decreases. In such a situation, we need a larger window radius for decreasing δ in order to diminish the size β is small, the role of the regularization term E p,q (•) is increased. Notice also that when the window radius is increased, there is generally less chance that the test is satisfied for the entire window. Conversely, we can afford large δ and therefore small window radius when β is large.

Thus, the reduced graph consists of narrow bands around the object edges.

Additionally, we investigate some ways to relax the condition [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] for further reducing the size of the reduced graph. A simple way is to multiply δ by a factor γ ∈ [0, 1]. Then, as γ decreases to 0, the condition (11) can be satisfied for a larger number of nodes. Typically, when γ = 0, we only test the sign of contracted capacities (see [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF]). Another way is to allow some nodes in

   either {q ∈ B p | c(q) ≥ +δ • γ} ≥ η • B p , or {q ∈ B p | c(q) ≤ -δ • γ} ≥ η • B p . (12)
Unlike the window radius parameter, γ and η parameters can further decrease the graph size but do not offer any guarantee on the final segmentation. However, for time-critical applications, this can be particularly useful when optimality does not represent a major constraint. As regard to the parameter η, it can also be used to remove noise in the segmentation.

In contrast to the test described in [START_REF] Malgouyres | A non-heuristic reduction method for graph cut optimization[END_REF], we do not have any theoretical guarantees about the nature of the minimizer found with the proposed test. Nevertheless, the numerical experiments presented in Section IV-C.3 exhibit important reduction rates while keeping a low pixel error on segmentations. But most importantly, these experiments show that the relative max-flow error between f * and f * (see Appendix I) is generally null. This tendency is also confirmed by the experiments of [START_REF] Malgouyres | A non-heuristic reduction method for graph cut optimization[END_REF] where both tests are compared and depict similar performance. In the next section, we detail a fast algorithm for building G .

B. Algorithmic considerations 1) Unoptimized algorithm

From the Section IV-A, an easy-to-implement non-optimized algorithm emerges: for each pixel p of the input image, we can check if the condition [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF] holds by browsing the window of radius r centered at p. If so, we do not add the node to G . Since the neighborhood of each pixel is visited exactly once, the graph construction resembles a convolution and has a worst-case complexity of O( P B). Notice that δ is computed only once. When a node cannot be removed from G, we connect it to its constructed neighbors. We keep track of these neighbors with an array of dimension (d -1).

2) Incremental algorithm

For large window radii, the unoptimized algorithm becomes inefficient as soon as the image size and d increase. Nevertheless, one can observe that the condition ( 12) can be decomposed as sums along the dimensions d yielding an algorithm with a complexity of O( P), except for image borders. We now detail this incremental algorithm in the 2D case with a connectivity 0.

We consider a square window B of size (2r + 1), (r > 0). First, for any point p ∈ P and δ ≥ 0, we define

g δ (p) =    1 if c(p) ≥ +δ , 0 otherwise. (13)
We either denote g δγ (p) or g δγ (i, j) for any pixel p = (i, j) ∈ P (it will never be ambiguous once in context). In what follows, we only describe the computation of {q ∈ B p | c(q) ≥ +δ • γ}.

The other case can easily be deduced by adapting the definition of [START_REF] Lempitsky | Global optimization for shape fitting[END_REF]. The key idea is to decompose {q ∈ B p | c(q) ≥ +δ • γ} as two sums where the first one sums over each row in a column while the second one sums over all columns. First, we introduce an array M whose size is the image width, where each element contains the sum of the values of g δγ (•) over a vertical segment of B p . More precisely, if we denote M i 0 ,j 0 the state of table M at the beginning of the computation at the pixel p = (i 0 , j 0 ) ∈ P, we have:

M i 0 ,j 0 [i] =    +r l=-r g δγ (i, j 0 + l) if i ≤ i 0 + r, +r l=-r g δγ (i, j 0 + l -1) if i > i 0 + r, (14)
except for image borders. Additionally, we maintain a variable N i 0 ,j 0 summing the elements of M along an interval of size 2r + 1:

N i 0 ,j 0 = +r c=-r M i 0 ,j 0 [i 0 + c],
∀(i, j) ∈ P.

We trivially have N i 0 ,j 0 = {q ∈ B p | c(q) ≥ δ • γ}, for p = (i 0 , j 0 ). Then, for ensuring the property ( 14) at the next pixel p = (i 0 + 1, j 0 ) ∈ P, we update M before N with:

M i 0 +1,j 0 [i 0 + r + 1] ← M i 0 ,j 0 [i 0 + r + 1] -g δγ (i 0 + r + 1, j 0 -r -1) + g δγ (i 0 + r + 1, j 0 + r) N i 0 +1,j 0 ← N i 0 ,j 0 -M i 0 +1,j 0 [i 0 -r] + M i 0 +1,j 0 [i 0 + r + 1]
The contracted capacities are only evaluated once: when shifting from one position to the next one. Therefore, the optimized algorithm builds the reduced graph with a complexity of O( P), except for image borders. In particular, the complexity becomes independent of the window radius. Also, one can notice that the cost of such an algorithm is directly proportional to the cost for evaluating the contracted capacities. However, for the energy models presented in this document, these capacities can be efficiently pre-computed and stored in lookup tables. The memory storage required by the incremental graph construction algorithm lies in the table M which is of dimension d -1. Thus, the extra memory usage is negligible with respect to both the image and the graph size.

The unoptimized algorithm remains quite general and can be extended in various ways. For instance, one can imagine an adaptive version where r varies automatically according to the image content. This forces us to guess the optimal window radius r * for each node. This can be done by examining all window radii in a fixed range {0, . . . , r max } (r max > 1) until r * is found.

Unlike the unoptimized algorithm, the worst-case complexity now becomes O( P • T (r max ))

← 2 -0 + 1 = 3 N 13,2 ← N 12,2 -M 13,2 [11] + M 13,2 (14)
← 8 -2 + 3 = 9

Fig. 4: Illustration of the incremental algorithm for a 2D image with r = 1, γ = 1 and η = 1.

In this example, only the node corresponding to the pixel p = (13, 2) is added to G since

|N 13,2 | = (2r + 1) 2 = 9. figure
where T (r max ) denotes the cost for examining all nodes for an increasing radius up to r max .

Although this approach permits to build smaller graphs, the construction of the graphs suffers from a higher computational cost. It becomes also more difficult to avoid repetitive evaluations of the contracted capacities like in the incremental algorithm.

Notice also that the reduction can easily be parallelized. First, due to the locality of data and operations, the unoptimized algorithm could also be easily parallelized on GPU since the result of condition ( 12) can be independently evaluated on each node. Secondly, when the reduced graph contains several connected components, we could solve the max-flow on each connected component independently. In some situations (such as the segmentation of noisy images), this approach could be very efficient since the max-flow computation would become trivial for a large amount of connected components whose nodes are all linked to the same terminal 8 .

8 Indeed, the condition [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF] does not imply that both terminals are linked to the non-terminals nodes unless we have γ = 0 and η = 1.

C. Numerical experiments

In the subsequent sections, all experiments are performed on an Athlon Dual Core 6000+ 3GHz with 2GB of RAM using the max-flow algorithm 9 of [1] 10 . Running times include the graph construction, the max-flow computation as well as the construction of the solution. Times are averaged over 10 runs.

1) The window radius parameter

The Figure 5 measures the impact of the window radius with respect to speed and memory usage and compares these results to standard graph cuts (bottom row) for segmenting 2D and 2D+t data (top row) in connectivity 1. On the bottom row, the blue curves with squares correspond to time consumption and the red curves with triangles correspond the memory of the reduced graphs. Standard graph cuts correspond to r = 0.

First, the segmentations obtained by standard graph cuts and reduced graph cuts are identical.

We also observe that the reduced graph cuts are always faster and requires less memory than the former except for the image "plane". One can also observe that both curves are approximately convex and the minimal relative size of the reduced graph (denoted by ρ * ) is reached for some radius r * > 0. Notice that r * naturally depends both on the image structure and the model parameters. The intuitive reason for both curves to be approximately convex is that each individual test of ( 12) can be satisfied more easily when r increase, since δ decreases with r.

Nevertheless, when r is larger, the condition becomes more and more difficult to satisfy because a larger number of individual test must hold. Notice that this experiment is chosen to illustrate the behavior when r change. However, we generally take r = 1 for most of the images used (see Tables I andII). 9 Since the reduction algorithm takes advantage of grid graphs, we want to point out that any max-flow algorithm implementation can easily be specialized on grid graphs to use less memory. A straightforward specialization of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] v3.0 with integer/float capacities on 32-bit targets can be reduced to 24 bytes per node and 4 per edge. This reduces the amount of memory needed of 2/3 in 2D and 3/4 in 3D. We call, for q ∈ {0, . . . , N b -1} c ,

H k = {p ∈ B | q i N b ≤ (I p ) i < q i+1 N b , ∀1 ≤ i ≤ c} B
where we remind that I p ∈ [0, 1] c and (I p ) i is the i th channel of I p . We then approximate

P(I p |p ∈ B) by (G σ * H) Ip
where G σ is a Gaussian kernel of standard deviation σ . In what follows, we always take σ = 1.

In practice, we use the same number of bins N b for the object and the background.

Notice that, as it is well known, when the number of bins N b is too large, H q is null for most q ∈ {0, . . . , N b -1} c . Such observation grows as the number of channels c increases. As a result, II. figure

P(I p |p ∈ B)
is not accurately estimated and (the learned distribution law overfits the samples) most contracted capacities of the graph are set to 0. In practice, the model behaves as if we had β = 0. On the other hand, when N b is too small, the best possible estimate approximates P(I p |p ∈ B) by a piecewise constant function made of large square pieces. This time, H q is not null for a larger part of q ∈ {0, . . . , N b -1} c but P(I p |p ∈ B) is roughly approximated.

Therefore, the number of bins N b should be a trade-off between these two situations. In practice, we adapt the number of bins to the number of channels. Following results of the Figure 6, we empirically choose a number of cells N b = 256 and N b = 50 for grayscale and color images, respectively. Smoothing distributions allows to further increase the number of cells where H q is not null and can further reduce the size of the graph.

3) Numerical experiments on 2D, 2D+t and 3D images

For segmenting 2D, 2D+t and 3D grayscale/color images in connectivity 1, we compare the performance of standard graph cuts against reduced graph cuts in terms of speed, memory consumption and provide measures for assessing the differences between the segmentations obtained with standard graph cuts and reduced graph cuts.

Let us now describe our experimental procedure. For each image, the seeds and the model "white-buttons" (6.91%) "rice" (21.77%) "zen-garden" (94.72%) "sweets" (83.97%)

"ct-thorax" (7.87%) "cells" (17.46%) "circles+N (0, 20)" (94.85%) parameters are manually optimized getting the best segmentation. Using these seeds and parameters, a reference segmentation is computed with standard graph cuts: the same seeds and parameters are then used for the reduced graph cuts. The differences between the segmentations are estimated using three evaluation measures (DSC, MSASD and VO, see Appendix I) as well as on the value of the flow in the graphs (see Appendix I). Also, the window radius r * for which the relative size of the graph ρ * is minimum, is estimated. For both tables, notice that some 2D images comes from the popular Berkeley segmentation dataset 11 .

The results obtained using a TV+L 2 model (see Section III-B) are summarized in Table I.

Similarly, the results obtained using a Boykov-Jolly model (see Section III-C) are summarized in Table II. Segmentation results are also illustrated using a TV+L 2 and a Boykov-Jolly model in Figure 7 and 8, respectively.

For both models, we observe that our algorithm generally outperforms standard graph cuts in terms of memory while the differences between both segmentations is generally null (or remain extremely small). For some of the 2D+t and 3D images, standard graph cuts fail to compute the segmentation while our algorithm is able to segment them in a reasonable time. Nevertheless, the relative size of the reduced graphs of some noisy images like "circles+N (0, 20)", "zen-garden"

or "cells" is particularly large. This result reflects the fact that a lot of neighboring nodes are linked to opposite terminals. The density of nodes linked to s and t is directly correlated to the amount of noise in the image. Thus, an ideal situation consists of large area of nodes linked to the same terminal separated by smooth borders. Notice that when these areas contain few nodes linked to wrong terminals, we can obtain good reduction performances by relaxing [START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] with the parameter η (see ( 12)).

For some instances, the reduced graph cuts are even faster than standard graph cuts. In words, it means that the time required by the reduction is compensated by the time for allocating the useless nodes and the computation of the max-flow on the reduced graph. However, the difference is generally small and becomes smaller as r * increases. In that case, most of the time of the reduction is indeed spent on the borders. This drawback increases with the number of channels.

As an illustration, the time spent on the borders for segmenting a color image of size 481 × 321 can represent more than 50% of the time for reducing the graph with r = 5. This percentage can rise to 80% for r = 10. Although it significantly reduces performances, this also confirms that the reduction is fast almost everywhere. Therefore, a better management of borders would lead to a substantial increase of speed of the proposed algorithm. However, this situation does not occurs often since we generally have r * = 1.

Another important point is that our algorithm can allocate a larger amount of memory. This situation typically occurs when β is too small, leading to a very large relative size of the reduced graph (see image "circles+N (0, 20)"). Since we do not know the size of G before running our algorithm, we sometimes need to reallocate an extra memory space for storing the following nodes and edges. In practice, the max-flow algorithm of [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] reallocates memory by adding the half of the size of the memory storage used by nodes and edges. In order to avoid reallocations, we can adapt simple strategies to get an upper bound on the number of nodes and edges belonging to G . For instance, we can use [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF] by testing individually each pixel p ∈ P with δ 1 or by randomly polling some amount of pixels in the image.

Let us now describe the results obtained in Tables I and II. For the TV+L 2 model, the average "red-starfish" (13.95%) "horses" (5.60%) "snow-and-clouds" (15.24%) "text1" (50.18%)

"interview-man1" (6.91%) "fluorescent-cell" (5.88%) "ct-thorax" (17.30%) "circles+N (0, 20)" (94.57%) The minimal relative size of the reduced graph is indicated in parenthesis below each image. figure

relative size of the reduced graph is 33.5% with a standard deviation of 47.39%. For 21 images out of 28, reduced graph cuts allocate less memory than standard graph cuts. Similarly, for 11 images out of 28, reduced graph cuts are faster than standard graph cuts. For some instances, the optimal window radius is far from being equal to one because the boundary of the segmentation is very rigid for avoiding undesired objects (see image "zen-garden" and "sweets" in Figure 7).

This leads to a small value of β and therefore a large window radius r * for lowering δ in order to obtain a smaller graph.

For the Boykov The Figure 9 illustrates the role of the parameter γ using the same model, images and parameters as in Figure 5. This experiment shows how far the condition (11) can be relaxed while nearly having an exact solution. In Figure 9, the window radii are chosen to minimize the memory consumption. The differences between the segmentations with the standard graph cuts and the reduced graph cuts are estimated using two evaluation measures: the DSC and the MSASD (see Appendix I). Then, we display the DSC (green curve), the MSASD (purple curve) well and the execution time (blue curve) and the memory consumption (red curve) over a fixed range of γ values ranging from 0 to 1. As γ decreases to 0, we naturally observe that we get a coarser approximation of the solution. In practice, we obtain nearly exact solutions for γ ≥ 0.5. For γ < 0.4, the solution is slightly different but remains close from the original segmentation.

5) The parameter η

A lower bound for η For a fixed window radius, notice first that the value of η must be sufficiently large for keeping the graph in a whole piece (see Figure 10). Below some value (denoted by η min ), the reduced graph can be unfortunately split into several connected components and pixels can be wrongly labeled in the segmentation. A lower bound of such a value can be easily be computed by considering an image consisting of two contrasted areas separated by a vertical edge. An easy estimate of η min is to impose that η min permits to segment these two contrasted areas. In order to do so, we want the test [START_REF] Scheuermann | Slimcuts: Graphcuts for high resolution images using graph reduction[END_REF] to be false for any pixel p located on the boundary between these areas. For such a pixel, we have (e.g. if we assume c(p) ≥ +δγ):

{q ∈ B p | c(q) ≥ +δγ} = (r + 1)(2r + 1) d-1 .

As a consequence, if η ≤ (r + 1)(2r + 1) d-1 (2r + 1) d , the pixel p does not belong to the reduced graph G . Since we want to avoid the situation, we therefore must have: η > (r+1)(2r+1) d-1

(2r+1) d = 1 -r 2r+1 = η min . (15)
Thus, as r tends to infinity, the maximum proportion of nodes allowed being linked to opposite terminals tends to 50%. Notice that this lower bound no longer holds in connectivity 0. Indeed, the lower bound can be too small in areas with high-curvature and the reduced graph would be disconnected into multiple pieces (see Figure 10). Consequently, the min-cut is no longer ensured of being fully contained in G .

Further reducing the graphs using η

We now detail how the parameter η can be used for reducing the memory usage. The Figure 11 illustrates how far the condition (11) can be relaxed for further reducing graphs while getting nearly the same segmentation. In this experiment, the segmentation and the reduced graph are shown for segmenting a synthetic noisy 2D image with a Boykov-Jolly model using connectivity 1. Since the condition (12) becomes easier to satisfy when η decreases, the graph around the object contours becomes thicker. The middle and the bottom rows correspond respectively to close-ups of the red and cyan areas.

Observe the reduced split into multiple pieces as soon as η ≤ η min . figure

Denoising using η

The parameter η can be also used for denoising the segmentation. Indeed, it can be tuned to remove small regions of the segmentation and therefore denoise it. This behavior is illustrated in Figure 12 for segmenting a 3D noisy image from a confocal microscope with a Boykov-Jolly model. In this picture, white spots correspond to cell nuclei in a mouse cerebellum. Observe how the denoising acts for small values of η: small regions in the graph and in the segmentation are progressively removed as η decreases. Typically, this parameter is useful for denoising images corrupted by a noise behaving like an impulsive noise. Finally, unlike traditional filters, our method does not require any pre or post-processing steps.

Fig. 1 :

 1 Fig. 1: Illustration of the flow passing through t-links (middle) and n-links (right) for segmenting a synthetic 2D image (left) using a TV+L 2 model. On the middle image, light gray pixels (resp. dark gray pixels) indicates that a positive amount of flow passed from s to p (resp. from p to t). On the right image, the gray is proportional to the sum of the flow leaving any node p. On the middle and the right images, gray (resp. black) areas correspond respectively to the nodes not traversed by any flow in the graph. figure

Fig. 2 :

 2 Fig. 2: Principle of the reduction. Red area and arrows (resp. green area arrows) denote the flow which get in (resp. out of) Z B . The nodes from Z are removed since Z satisfies (10). Remaining nodes are typically located in the narrow band Z B \ Z. figure

Fig. 3 :

 3 Fig. 3: Tuning of the window radius for segmenting a synthetic 2D image with a TV+L 2 model in connectivity 1. From left to right: reduced graphs are superimposed in yellow on the original image for the window radius r = 1, 8, 15, 22. The relative size of the reduced graph is indicated below each image. figure

B

  p to fail complying with the test. The proportion of nodes satisfying the test is controlled by a parameter called η ∈ [0, 1]. Then, as η decreases, the condition (11) can be satisfied more easily since a larger proportion of nodes can be connected to opposite terminals. Embedding these two extra parameters leads to the following condition:

Fig. 5 : 2 )

 52 Fig. 5: Influence of window radius (bottom row) for segmenting 2D and 2D+t images (top row) with a TV+L 2 model in connectivity 1. On the bottom row, blue curve with squares and red curve with triangles correspond respectively to execution time and the amount of memory allocated for the graph. Standard graph cuts correspond to a window radius equal to 0. figure

Fig. 6 :

 6 Fig. 6: Evolution of the relative size of the reduced graph (blue curve) and the distance between a ground truth image obtained from Table II with the number of bins N b . The distance between both segmentations is measured with the DSC (red curve) and the SRMSSD (green curve). Seeds and parameters are the same as those used in TableII. figure

Fig. 7 :

 7 Fig. 7: Segmentation results using a TV+L 2 model in connectivity 1. The segmentation is superimposed on the original image by transparency. The minimal relative size of the reduced graph is indicated in parenthesis below each image. figure

Fig. 8 :

 8 Fig. 8: Segmentation results using a Boykov-Jolly model in connectivity 1. The segmentation (bottom row) as well as seeds (top row) are superimposed on the original image by transparency.

Fig. 9 : 4 )

 94 Fig. 9: Influence of the parameter γ (bottom row) for segmenting 2D and 2D+t images (top row) with a TV+L 2 model in connectivity 1. On the bottom row, blue curve with squares and red curve with triangles correspond respectively to the gain in time and the amount of memory allocated for the reduced graph. Green curves with circles and purple curves with diamonds correspond respectively to the DSC and the MSASD between γ-parametrized segmentations and the segmentations obtained with standard graph cuts. figure

Fig. 10 :

 10 Fig. 10: Illustration of the lower bound η min for segmenting a 2D synthetic image using a TV+L 2 model. In this experiment, η min 0.523 and we set r = 10 using connectivity 1. On all images, the pixels belonging to V are superimposed in yellow to the original image by transparency.

Fig. 11 :Fig. 12 :

 1112 Fig. 11: Memory gain when segmenting a 2D synthetic image corrupted by 10% of impulsive noise, using a Boykov-Jolly model (left). Top row shows the nodes of the reduced graph in light gray while bottom row shows the corresponding segmentation. In this experiment, we set r = 3, γ = 1 and use connectivity 1. In this experiment, η min 0.571. figure

  -Jolly model, the average relative size of the reduced graph is 19.24% with a standard deviation of 31.09%. For 29 images out of 31, reduced graph cuts allocate less memory than standard graph cuts. Similarly, for 17 images out of 31, reduced graph cuts are faster than standard graph cuts.

	MSASD	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	0.0000	NSR	NSR	NSR	NSR	0.0000	NSR	NSR
	VO (%)	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	99.9460	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	NSR	NSR	NSR	NSR	100.0000	NSR	NSR
	DSC (%)	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	99.9730	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	100.0000	NSR	NSR	NSR	NSR	100.0000	NSR	NSR
	r * RME	14 0.0000	10 0.0000	13 0.0001	1 0.0000	1 0.0000	6 0.0011	4 0.0001	22 0.0000	1 0.0000	1 0.0000	3 0.0016	1 0.0001	1 0.0001	1 0.0000	1 0.0000	1 0.0000	3 0.0000	1 0.0000	1 0.0002	1 0.0000	1 0.0002	1 NSR	1 NSR	1 NSR	1 NSR	1 0.0138	1 NSR	1 NSR
	ρ * (%)	49.89	94.72	79.85	5.74	8.64	76.39	99.83	83.97	10.56	28.78	95.32	18.83	7.97	7.51	1.71	1.14	37.06	6.91	21.77	18.84	2.93	15.04	18.83	13.36	7.87	94.85	17.46	12.63
	Standard GC Reduced GC	Time Memory Time Memory	0.12 22.90 Mb 0.42 14.54 Mb	0.12 22.90 Mb 0.27 22.90 Mb	0.26 22.90 Mb 0.48 22.90 Mb	0.18 38.91 Mb 0.11 2.05 Mb	2.68 917.26 Mb 1.67 78.95 Mb	0.20 38.91 Mb 0.33 35.09 Mb	0.07 9.70 Mb 0.13 9.70 Mb	0.81 71.28 Mb 2.51 71.28 Mb	0.82 285.39 Mb 0.57 25.76 Mb	0.36 116.84 Mb 0.36 35.09 Mb	0.23 38.91 Mb 0.34 38.91 Mb	0.19 38.91 Mb 0.15 6.93 Mb	0.18 38.91 Mb 0.11 3.08 Mb	0.13 33.39 Mb 0.09 2.26 Mb	0.12 34.20 Mb 0.06 623.05 Kb	0.12 35.61 Mb 0.07 415.38 Kb	0.27 72.53 Mb 0.28 35.09 Mb	0.06 13.33 Mb 0.03 934.60 Kb	0.04 9.70 Mb 0.04 2.05 Mb	0.08 17.64 Mb 0.05 3.08 Mb	0.16 37.21 Mb 0.09 1.01 Mb	OM 4.72 Gb 8.96 771.00 Mb	OM 3.43 Gb 8.50 771.00 Mb	OM 6.40 Gb 10.42 1.13 Gb	OM 17.33 Gb 21.43 1.17 Gb	5.01 874.57 Mb 7.16 874.57 Mb	OM 6.92 Gb 14.23 1.13 Gb	OM 2.91 Gb 6.00 342.67 Mb
	Volume name Size	plane 481 ×321	zen-garden 481 ×321	oriental-man 321 ×481	ct-thorax-z 512 ×512	book 3012 ×2048	cells-z 512 ×512	beans 256 ×256	sweets 800 ×600	text1 1600 ×1200	text2 1024 ×768	yeasts1 512 ×512	yeasts2 512 ×512	angiography1 512 ×512	angiography2 350 ×643	f117 588 ×392	black-cat 600 ×400	viking-symbol2 660 ×740	white-buttons 300 ×300	rice 256 ×256	blood-cells 425 ×280	poppy 409 ×613	interview-girl 320 ×240 ×150	interview-old-man 256 ×256 ×128	interview-woman 352 ×288 ×154	ct-thorax 409 ×409 ×252	circles-pyramid+sigma20 128 ×128 ×128	cells 409 ×409 ×101	brain-p3 181 ×217 ×181
	@	@	@ @										2D												2D+t			3D

TABLE I :

 I Standard graph cuts (GC) are compared to our algorithm in terms of speed (in secs) and memory for segmenting data using a TV+L 2 model in connectivity 1. Label OM stands for "Out of Memory" while label NSR

	RME DSC (%) VO (%) MSASD	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0001 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0000 99.7832 99.5674 0.0000	0.0000 100.0000 100.0000 0.0000	0.0007 100.0000 100.0000 0.0000	0.0000 100.0000 100.0000 0.0000	0.0023 99.9981 99.9962 0.0000	NSR NSR NSR NSR	NSR NSR NSR NSR	NSR NSR NSR NSR	NSR NSR NSR NSR	NSR NSR NSR NSR	NSR NSR NSR NSR	0.0043 100.0000 100.0000 0.0000	0.0029 100.0000 100.0000 0.0000	NSR NSR NSR NSR	stands for "No Segmentation
	r *	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	1	1	1	1	1	1	1	1	1	1	1
	ρ * (%)	5.54	90.75	1.17	23.30	15.24	2.46	1.46	13.95	1.51	5.07	4.95	6.40	2.25	8.03	5.60	56.00	4.30	10.85	8.18	48.91	50.18	5.13	6.91	3.21	6.20	15.44	5.88	17.30	94.57	51.38	24.38
	Standard GC Reduced GC	Time Memory Time Memory	0.20 22.90 Mb 0.15 1.37 Mb	0.22 22.90 Mb 0.34 22.90 Mb	0.22 22.90 Mb 0.12 276.92 Kb	0.19 22.90 Mb 0.21 6.93 Mb	0.19 22.90 Mb 0.15 4.62 Mb	0.19 22.90 Mb 0.13 623.05 Kb	0.18 22.90 Mb 0.13 304.97 Kb	0.19 22.90 Mb 0.15 3.08 Mb	0.21 22.90 Mb 0.15 304.97 Kb	0.20 22.90 Mb 0.13 1.37 Mb	0.20 22.90 Mb 0.15 1.01 Mb	0.21 22.90 Mb 0.16 1.37 Mb	0.18 22.90 Mb 0.13 623.05 Kb	0.20 22.90 Mb 0.14 2.05 Mb	0.20 22.90 Mb 0.14 1.37 Mb	0.20 22.90 Mb 0.25 15.59 Mb	0.19 22.90 Mb 0.13 934.60 Kb	0.44 38.91 Mb 0.29 4.62 Mb	7.54 917.26 Mb 5.06 78.95 Mb	0.46 38.91 Mb 0.49 23.39 Mb	2.15 285.39 Mb 2.49 177.63 Mb	0.59 72.53 Mb 0.39 3.39 Mb	OM 6.40 Gb 18.75 514.00 Mb	OM 7.55 Gb 19.86 228.44 Mb	OM 10.03 Gb 28.91 532.00 Mb	OM 7.96 Gb 32.51 1.13 Gb	OM 9.39 Gb 30.08 514.00 Mb	OM 3.71 Gb 17.25 771.00 Mb	8.13 874.57 Mb 11.41 874.57 Mb	9.27 1.23 Gb 9.78 771.00 Mb	OM 2.91 Gb 14.45 771.00 Mb
	@ Volume name @ Size	@ @ eagle-c 481 ×321	zen-garden-c 481 ×321	columns-c 481 ×321	red-flowers-c 481	snow-and-clouds-c 481 ×321	marker-c 481 ×321	pyramid-c 481 ×321	red-starfish-c 481 ×321	black-cow-c 481 ×321	church2-c 481 ×321	2D snake2-c 481 ×321 birds2-c 321 ×481	eagle2-c 481 ×321	greek-temple-c 481 ×321	horses4-c 481 ×321	meadow-and-mountains-c 481 ×321	traditional-houses-c 481 ×321	ct-thorax-z 512 ×512	book 3012 ×2048	cells-z 512 ×512	text1 1600 ×1200	viking-symbol2 660 ×740	interview-man1-c 320 ×240 ×203	interview-man2-c 426 ×240 ×180	2D+t plane-take-off-c 492 ×276 ×180	talk-c 370 ×276 ×190	fluorescent-cell-c 478 ×396 ×121	ct-thorax 245 ×245 ×151	3D cells circles-pyramid+sigma20 128 ×128 ×128 230 ×230 ×57	brain-p3 181 ×217 ×181	Reference".	table

TABLE II :

 II Standard graph cuts (GC) are compared to our algorithm in terms of speed (in secs) and memory for segmenting data using a Boykov-Jolly model in connectivity 1. Label OM

		plane -1443 × 963	cells -1536 × 1536	lena -2048 × 2048	woman -211 × 172 × 92	stands for "No Segmentation
	hal-00606921, version 3 -3 Jul 2012	Image "plane"	Image "cells"	Image "lena"	Image "woman"	stands for "Out of Memory" while label NSR	Reference". Color images are suffixed by "c" in their names.	table

July 3, 2012 DRAFT

By exact, we mean that the maximum flow value remains unchanged and any solution is guaranteed to be a global minimizer.July 3,

DRAFT

The min-marginal encodes the confidence associated with a variable being assigned the label in the optimal solution. The minmarginal of a variable x corresponds to the energy obtained by fixing it to a particular label and minimizing over all remaining variables. The exact min-marginals can be determined exactly and efficiently by reusing previous max-flow computations.

July 3, 2012 DRAFT

The energy model used is the one proposed by Boykov and Jolly in[START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[END_REF] (see Section III-C).July 3, 2012 DRAFT

As an illustration, each pixel has respectively 4 and 8 neighbors in 2D, 6 and 26 neighbors in 3D and finally 8 and 80 neighbors in 4D, for N0 and N1 neighborhoods. July 3, 2012 DRAFT

In this setting, we denote by u µ = {p ∈ P | u µ p = 1} the µ level-set of u at the level µ where u µ p = 1 {up≥µ} .July 3, 2012 DRAFT

We remind that P is the set of pixels/voxels and En denotes the set of n-links (see[START_REF] Greig | Exact maximum a posteriori estimation for binary images[END_REF]).July 3, 2012 DRAFT

If the condition[START_REF] Strandmark | Parallel and distributed graph cuts by dual decomposition[END_REF] does not hold, δ can for instance be multiplied by max (p,q)∈N c(p, q). July 3, 2012 DRAFT

The code is freely available at http://pub.ist.ac.at/~vnk/software.html July 3, 2012 DRAFT

The dataset is freely available at http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ July 3, 2012 DRAFT

APPENDIX I EVALUATION AND REDUCTION MEASURES

Let SG, GT ⊂ {0, 1} N (N > 0) denote respectively a machine-obtained segmentation and the ground truth. The function ∂S : {0, 1} N → {0, 1} N will correspond to the border of any set S ⊂ {0, 1} N which is formally defined as ∂S = {p ∈ S| ∃(p, q) ∈ N , q ∈ S}.