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

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

Intro

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: