All notes
GraphCu

# Intro

### Ising model

Ising model is mathematical model of ferromagnetism and is easily to be applied in many other fields. Ising is a surname in German (pronounced izing, thus the chinese name 易辛模型), while in english it is pronounced aising.

### Weights

The weight setting $w=\frac{1}{1+\beta |\nabla i|}$ lets the edges at high contrast region having low weights, and edges at low contrast region having hight weights. The hyperbolic function $y=1/(1+x)$ decreases from 1 to 0 when $x$ goes from 0 to $\infty$. The derivative of the function is $y'=-1/(1+x)^2$, which is an increasing function from -1 to 0, and it means the hyperbolic weighting function drops mostly intensely at 0, and then drops slowlier when $x$ approaching $\infty$.

### Reference

• Iterative Narrowband-Based Graph Cuts Optimization for Geodesic Active Contours With Region Forces
• Computing Geodesics and Minimal Surfaces via Graph Cuts
• What Metric Can Be Approximiated by Geo-Cuts, or Global Optimization of Length/Area and Flux
• A Multilevel Banded Graph Cuts Method for Fast Image Segmentation

# Affinity measures

Manasi's page. Distance measure: $$aff(\mathbf x, \mathbf y) = \exp \left\{ - ((\mathbf x - \mathbf y)^t(\mathbf x - \mathbf y)/2 \sigma_d^2) \right\}$$ Intensity measure: $$aff(\mathbf x, \mathbf y) = \exp \left\{ - ((I(\mathbf x) - I(\mathbf y))^t(I(\mathbf x) - I(\mathbf y))/2 \sigma_I^2) \right\}$$

# Boykov2006

Title: Graph Cuts and Efficient N-D Image Segmentation.

The best features of combinatorial graph cuts methods in vision

• global optima
• practical efficiency
• numerical robustness
• ability to fuse a wide range of visual cues and constraints
• unrestricted topological properties of segments
• applicability to N-D problems

#### Intro

• Have interesting connections with earlier segmentation methods such as: snakes, geodesic active contours, and level-sets.
• The segmentation energies optimized by graph cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah style functionals.
• Compared to other graph-based methods: this graph cut approach is preceded by a number of graph-based methods for image “clustering” that use either combinatorial optimization algorithms (Wu and Leahy, 1993; Ishikawa and Geiger, 1998; Felzenszwalb and Huttenlocher, 2004; Veksler, 2000) or approximate spectral analysis techniques, e.g., normalized cuts (Shi and Malik, 2000), using only generic cues of coherence or affinity between pixels.
• This graph cut method is more like snakes (Kass et al., 1988; Cohen, 1991), active contours (Isard and Blake, 1998; Caselles et al., 1997), intelligent scissors (Mortensen and Barrett, 1998), live-wire (Falca ̃o et al., 1998), and many techniques based on level-sets (Sethian, 1999; Osher and Fedkiw, 2002). These methods integrate model-specific (boundary and region- based) visual cues, contextual information or even useful topological constraints in order to accurately delineate particular object(s) of interest.

#### Comparison

1. “region growing”, “thresholding”, split-and-merge: prone to many problems, most notably, to “leaking” through weak spots in object boundaries. Widely used due to simplicity and speed.
2. Typically, continuous surface functionals incorporate various “regional” and “boundary” properties of segments some of which can be geometrically motivated. In most cases, these methods use variational optimization techniques that can guarantee to find only a local minima of the corresponding energy functional.
3. All previous combinatorial methods for object segmentation use discrete variables whose values encode “direction” of a path along the graph. Many path-based methods use Dynamic Programming (DP) to compute optimal paths. For example, (Mortensen and Barrett, 1998) (intelligent scissors ) and (Falca ̃o et al., 1998) (live-wire) use Dijkstra algorithm while (Amir et al., 1990) (DP- snakes) use Viterbi algorithm.
4. All path-based methods can naturally encode boundary-based segmentation cues while the incorporation of region properties in segments is less obvious (Jermyn and Ishikawa, 1999; Reese, 1999). In any case, all path-based methods are limited to 2D applications because object boundary in 3D volumes can not be represented by a path.

##### Global optimum

In general, global solutions are attractive because of their potentially better stability. For example, imperfections in a globally optimal solution are guaranteed to directly relate to the cost function rather than to a numerical problem during minimization.

The computer vision community has produced a number of useful algorithms for localizing object boundaries in images. There are snakes (Kass et al., 1988; Cohen, 1991), active contours (Isard and Blake, 1998), geodesic active contours (Caselles et al., 1997; Yezzi et al., 1997), “shortest path” tech- niques (Mortensen and Barrett, 1998; Falca ̃o et al., 1998)

Variational methods (Optimisation in $\mathcal{R}^{\infty}$)Combinatorial methods (Optimasation in $\mathcal{Z}^n$)
Explicit boundary representationSnakes, BalloonsDynamic Programming, "path-based" graph methods (2D only)
Implicit boundary representationLevel-setsCombinatorial Graph Cuts

#### Applications

This technique from combinatorial optimization has already demonstrated a great potential for solving many problems in vision and graphics:

• Image restoration (Greig et al., 1989; Boykov et al., 2001)
• stereo (Roy and Cox, 1998; Ishikawa and Geiger, 1998; Boykov et al., 1998)
• multi-view reconstruction (Kolmogorov and Zabih, 2002; Vogiatzis et al., 2005; Lempitsky et al., 2006)
• texture synthesis (Kwatra et al., 2003).