*This article was published as a part of the Data Science Blogathon*

## Introduction

Image Segmentation has long been an interesting problem in the field of image processing as well as to object detection. It is the problem of segmenting an image into regions that could directly benefit a wide range of computer vision problems, given that the segmentations were reliable and efficiently computed.

For example, image recognition can make use of segmentation results in matching to address problems such as figure-background separation and recognition by parts.

Felzenszwalb and Huttenlocher developed an approach for the above-mentioned segmentation problem in their paper, Efficient Graph-Based- Image- Segmentation, which is commonly referred to here as Felzenszwalb’s Algorithm.

## Felzenszwalb’s Algorithm.

Their goal was to develop a computational approach to image segmentation that is broadly useful, mush in the way that other low-level techniques such as edge detection are used in a wide range of computer vision tasks.

They believed that a good segmentation method should have the following properties:-

- The segmentation should capture visually important groupings or regions, which often reflect global aspects of the image.
- The method should be efficient, meaning it should run in almost linear time in the number of image pixels.

Although many methods had made considerable advances in segmenting images, most were slow and did not take into account that an object might have **invariance in intensity** and therefore would incorrectly segment that area.

To overcome the problems faced by previous methods, Felzenszwalb and Huttenlocher took a *graph-based approach* to segmentation. They formulated the problem as below:-

Let G = (V, E) be an undirected graph with vertices vi ∈ V, the set of elements to be segmented, and edges

(vi, vj ) ∈ E corresponding to pairs of neighboring vertices. Each edge (vi, vj ) ∈ E has a corresponding weight w((vi, vj )), which is a non-negative measure of the dissimilarity between neighboring elements vi and vj

.

In the case of image segmentation, the elements in V are pixels and the weight of an edge is some measure of the dissimilarity between the two pixels connected by that edge (e.g., the difference in intensity, color, motion, location, or some other local attribute).

**S** is a segmentation of a graph G such that **G’ = (V, E’), where E’ **⊂** ****E** . **S** divides **G** into **G’** such that it contains distinct components (or regions) **C**.

__Graph Construction__

__Graph Construction__

Two approaches for constructing a graph out of an image were considered:

**Grid Graph:**Each pixel is only connected with surrounding neighbors (8 other cells in total). The edge weight is the absolute difference between the intensity values of the pixels.

**Nearest Neighbor Graph**: Each pixel is a point in the feature space (x, y, r, g, b), in which (x, y) is the pixel location and (r, g, b) is the color values in RGB. The weight is the Euclidean distance between two pixels’ feature vectors.

__Some important concepts:-__

__Some important concepts:-__

Before learning about the criteria for a good graph partition, it is better to understand some concepts:

**Internal difference:****Int(C)**= max_{e∈MST(C,E)}**w(e)**, where MST is the minimum spanning tree of the components. A component ‘C’ can still remain connected even when we have removed all the edges with weights < Int(C). In other words, Internal Difference is the maximum edge weight that connects two nodes of the same component.

**Difference between two components**:**Dif (C1,C2)**=min_{vi∈C1,vj∈C2,(vi,vj)∈E}**w(vi,vj) and****Dif(C1,C2)=∞**if there is no edge in-between. this can also be understood as the difference between two components. The difference between the two components is the minimum weight

the edge that connects a node v_{i}

in component C_{1}to node v_{j}

in C_{2}.

**Minimum internal difference**:**MInt(C1,C2) = min(Int(C1) + τ(C1) , Int(C2) + τ(C2))**where**τ(C)=k/|C|**. This is the internal difference in the components C_{1}and C_{2}. It is governed by a factor**k**that we will understand a bit later.

__Predicate for segmentation__

__Predicate for segmentation__

To judge the quality of segmentation, a good pairwise region comparison is needed for two given regions say, C_{1} and C_{2}:

Only when this predicate is **True, **do we consider two components as independent. Otherwise, the segmentation is probably too fine and the components should be merged.

We have already defined the individual terms mentioned in the condition above, let’s now understand them better.

__Difference between two components__

__Difference between two components__

The difference between the two components is the minimum weight edge that connects a node v_{i} in component C_{1} to node v_{j} in C_{2}.

__Minimum Internal Difference__

__Minimum Internal Difference__

This is the **internal difference** in the components C_{1} and C_{2 }governed by the factor **k**. This factor **k **in the definition of **MInt** separates the understanding **Internal Difference** and **Minimum Internal Difference**. As we saw earlier **τ(C), **sets the threshold by which the components need to be different from

the internal nodes in a component. We know that:

**τ(C)=k/|C|,**

here, the properties of this constant **k** are as follows:

- If k is large, it causes a preference for larger objects.
- k does not set a minimum size for components.

Now considering this, we can understand **Minimum Internal Difference(****MInt(C1,C2)****)** and **Difference between two components(****Dif(C1,C2)****) ** in the same context:

The above picture should make the predicate more clear to understand and visualize.

Only when the Difference between two components is greater that the Minimum Internal Difference of the two components, can the two components be divided into two different components.

__Segmentation Algorithm and it’s working__

__Segmentation Algorithm and it’s working__

We have already seen and understood the **predicate, **which is at the heart of this algorithm. Given an input graph **G = (V, E)**, with **n** vertices and **m** edges. The output is a

segmentation of V into components** S = (C1, . . . , Cr)**. The algorithm is as follows:

Although the algorithm can seem daunting at first, it is basically doing what the predicate wants:

The algorithm follows a bottom-up procedure. Given **G=(V,E) **and **|V|=n, |E|=m**. Where |V| is the number of vertices(pixels) and |E| is the number of edges.

- Edges are sorted by weight in ascending order, labeled as e
_{1},e_{2},…,e_{m}. - Initially, each pixel stays in its own component, so we start with n components.
- Repeat for k=1,…,m:

- The segmentation snapshot at step k is denoted as Sk.
- We take the k-th edge in the order, ek=(v
_{i}, v_{j}). - If v
_{i}and v_{j}belong to the same component, do nothing and thus S^{k}=S^{k−1}. - If v
_{i}and v_{j}belong to two different components C_{i}^{k−1}and C_{j}^{k−1}as in the segmentation of S^{k−1}we want to merge them into one if w(v_{i},v_{j}) ≤ MInt(C_{i}^{k−1},C_{j}^{k−1}); otherwise do nothing.

*The entire segmentation process can be visualized as below:*

**This segmentation algorithm has many properties, the most important of them being:**

For any (finite) graph G = (V, E) there exists some segmentation S that is neither too coarse nor too fine.

*For more properties and proofs, you can view the original paper.*

*This algorithm is very easy to implement, as it comes defined in ***skimage** library.

**skimage**library.

#importing needed libraries import skimage.segmentation from matplotlib import pyplot as plt

#reading image img = plt.imread("/content/image1.jpg")

#performing segmentation #first for k=50 #seconf for k=1000 res1 = skimage.segmentation.felzenszwalb(img, scale=50) res2 = skimage.segmentation.felzenszwalb(img, scale=1000)

#printing the results fig = plt.figure(figsize=(12, 5)) ax1 = fig.add_subplot(121) ax2 = fig.add_subplot(122) ax1.imshow(res1); ax1.set_xlabel("k=50") ax2.imshow(res2); ax2.set_xlabel("k=1000") fig.suptitle("Graph based image segmentation") plt.tight_layout()

__Original Image__

__Result__

*It can be seen in the results that a low value of k leads to coarser segmentation, while the large value of k leads to the selection of larger objects and is therefore finer. This can be seen from the ball being properly segmented in the second picture but not in the first.*

__We can also mark the boundaries if we want:__

__We can also mark the boundaries if we want:__

* *

from skimage.data import camera from skimage.util import img_as_float #import function for marking boundaries from skimage.segmentation import mark_boundaries img = img_as_float(camera()[::2, ::2]) res3 = skimage.segmentation.felzenszwalb(img, scale=100) res4 = skimage.segmentation.felzenszwalb(img, scale=500) fig = plt.figure(figsize=(12, 5)) ax1 = fig.add_subplot(121) ax2 = fig.add_subplot(122) ax1.imshow(mark_boundaries(img, res3)); ax1.set_xlabel("With k=100") ax2.imshow(mark_boundaries(img, res4)); ax2.set_xlabel("With k=500") fig.suptitle("Plotting the boundaries")

__Original Image__

__Result__

__References__

https://davidstutz.de/implementation-of-felzenswalb-and-huttenlochers-graph-based-image-segmentation/ (for thumbnail)

__About me__

I am a sophomore at Birla Institute Of Technology, Mesra, currently pursuing Electrical and Electronics Engineering. My interests lie in the fields of Machine Learning and Deep Learning and like robotics.

You can connect with me at:

You can also view some of the fun projects I worked on with my brother at:

https://www.youtube.com/channel/UC6J46NEyQEjag9fnOuBJ5hw

*The media shown in this article on K-Means Clustering Algorithm are not owned by Analytics Vidhya and are used at the Author’s discretion.*