Nov 17, 2017

1. Super pixel segmentation method based on graph theory

Image segmentation based on graph theory is a top-down global segmentation method, the main idea is to divide the whole image as a weighted undirected graph, a graph corresponding to each pixel in the image node, adjacent relation graph corresponding pixels between the edge pixel differences between features of corresponding or similar weights on the side, and then in the map based on various segmentation criterion to divide the nodes in the graph, and then complete the image segmentation.

1.1 Graph- based method

1.2 Ncut method

1.3 Superpixel lattice method

For some of the current super pixel segmentation algorithm, the defect of the original image are missing important topology information, Moorer et al proposed a superpixel lattice unsupervised segmentation algorithm this method describes a greedy algorithm can maintain the topology of the image, although the increase of topological information constraints, but it is in speed keep the input and accuracy of segmentation performance of Superpixel lattice algorithm is a good image of the boundary map, to search for the minimum weight path through the image, at the boundary of minimum cost graph image segmentation with two direction in the horizontal and vertical search optimal path, continuously the image from the vertical and horizontal direction of two points to get the conventional super pixel grid.

In graph,

(a) the image is segmented from left to right from top to bottom, and each path is divided into two parts, and then four regions can be obtained, and the optimal path is searched in the preset strip;

(b) is increasing the horizontal and vertical direction of the path, so that the image is divided into nine regions

On the strategy of searching the optimal path, Moore et al have adopted two schemes: s- t minimal cut method and dynamic programming method, the former generates arbitrary topological paths, and the latter produces no regression paths, where the optimal path needs to satisfy three conditions:

A) each vertical and horizontal path is crossed only once;

B) any two vertical paths do not cross;

C) any two horizontal paths are not crossed.

Although the superpixel lattice algorithm has achieved good segmentation results, its segmentation quality still depends on the image boundary map, and implicitly stipulates that the image needs two mechanisms to divide evenly:a) The uniform distribution of image bands directly affects the uniform distribution of the paths;b) The least cost path strategy facilitates the formation of relatively straight and short paths on the image.Therefore, Moore et al. Added a priori information to the algorithm based on the algorithm in 2009, and proposed a superpixel partition based on scene shape priori. The probability density model is used to describe the spatial density of the image object boundary. An over-segmentation algorithm is adopted to make the super-pixel density approximately equal and to adapt to the local target boundary.

Subsequently, Moore et al. Proposed the lattice- cut method, it is a kind of unsupervised segmentation, using alternate optimal strategy choice, with a single image cut alternately in horizontal or vertical direction update super pixel boundary, considering image boundary and super pixel region of the consistency of the whole process can be used to produce super pixels from Fig. describes the figure 3,

(a) firstly, the image is divided into evenly spaced grid hyper pixels, and the pixels in the same sub pixel have the same tag;

(b) (d) establish Markov random field model, update the superlattice boundary of the pixel continuously alternately in horizontal and vertical methods, that is to change the label of the related pixels;

(E) (f) is updated vertically or horizontally. The pixel tag determines which vertical or horizontal stripe the pixel belongs to.

The Lattice- cut method is superior to the existing computational hyper pixel mesh algorithm, and its performance is comparable to some mesh segmentation algorithms without mesh constraints.

1.4 the method based on entropy rate