## Graph Based Segmentation Method

The graph segmentation method (GSM) segments an image by treating it as a graph G = (V, E) where V the set of vertices are the pixels and E the set of edges are pairs of pixels. Using a weight function w(e), where e is an edge (vi, Vj), the weights of the edges are computed and the edges are sorted by weight in a nondecreasing order. Initially, each pixel vi is segmented into its own component Ci.

For each edge (vi, v j) in the list, a decision criterion D is applied and a decision is made whether or not to merge the components Ci and Cj. After this decision is made on each edge in the list, the result is a list of the final components of the segmented image.

The input image is first smoothed by a given smoothing parameter a. Input constant k determines the size preference of the components by changing the threshold function t (C) (see Figs. 9.14 and 9.15).

The decision criteria D is a comparison between the difference between components Ci and Cj and the minimum internal difference among Ci and Cj. The difference between two components is defined as the minimum weight of the edges that connect the two components:

|lnpuHmage|

Smooth

Imagj^^> ^_I Smoothing parameter

Smoothed Image; treat as graph G = (V, E) with n vertices and m edges -— 1 -

Compute weight of edges with weight function w(e), where e is (vi, v) and (v,, v), E

List of weights of Edges E I

Sort Edges E by nondecreasing edge weight

Edges E sorted by weight r

Segment each pixel (vertex v,) into its own component C,

Constant k

n segmented _ components

For each edge in sorted edge list, apply the decision criterion D to begin merging components

### Segmented Image

Figure 9.14: Graph segmentation method (GSM). The input image is smoothed given a smoothing parameter. The image is treated as a graph, with each pixel treated like a vertex. An edge is a pair of pixels. Using a weight function w(e), the weights of the edges are computed and the edges are listed by weight in a nondecreasing order. Initially, each pixel is segmented into its own component. For each edge in the list, a decision criterion D is applied and the components are merged accordingly. Input constant k determines the size preference of the components by changing the threshold function. The result is a segmented image made up of the final merged components.

The minimum internal difference among two components Ci and Cj is defined as the minimum of the sum of the internal difference and the threshold function of each component:

MInt(Ci, Cj) = min(Int(Ci) + r(Ci), Int(Cj) + r(Cj)), (9.13)

where the internal difference Int(C) of a component C is defined as the maximum weight in the minimum spanning tree MST(C, E) of the component: For each edge (vi,Vj) in sorted edge list, com between Ci and Cj and compute the minir difference among Ci and Cj.

n segmented components and list of sorted edges -- * --

For each edge (vi,Vj) in sorted edge list, com between Ci and Cj and compute the minir difference among Ci and Cj.

im im

Merge Cx and Cj

Merge Cx and Cj

Do not merge Cx and C

Do not merge Cx and C

Are all edges evaluated?

Figure 9.15: Decision criterion D for the graph segmentation method (GSM). After the list of edge weights are sorted and each pixel is segmented into its own component, the decision criterion is D is applied to each edge. The constant k is used in determining the threshold function. First the difference between the two components to which the two pixels making up the edge belong is computed. Then the minimum internal difference among those two components is computed. If the difference between the two components is greater than the minimum internal difference among them, then D applied to the two components is true, and the two components are not merged because there is evidence for a boundary between them. Otherwise, if the difference between the two components is less than or equal to the minimum internal difference, then the D applied to the two components is false, and the two components are merged into one component which contains both pixels of the edge. This decision criterion is applied to all the edges of the list, and the final result is a segmentation of the pixels into components.

and where the threshold function t (C) is defined as where k is the input constant and |C | is the size of the component C.

Internal Difference tilKTIC.B)

Difference between two components

Difference between two components r(C) =

| Tkeskold Fuurtioii

Mmmwmi Ijitemal Difference

Figure 9.16: Graph segmentation method (GSM) equations. The internal difference of a component is the maximum edge weight of the edges in its minimum spanning tree. The difference between two components is the minimum edge weight of the edges formed by two pixels, one belonging to each component. The threshold function of a component is the constant k divided by the size of that component, where the size of a component is the number of pixels it contains. The minimum internal difference among two components is the minimum value of the sum of the internal difference and the value of the threshold function of each component.

If the difference between the two components is greater than the minimum internal difference among the two components, then the two components are not merged. Otherwise, the two components are merged into one component.