Let us look again at the requirements for the segmentation algorithm.

Methods that more or less meet the requirements are

called oversegmentation or super pixel methods.

They're called so because we can segment a region of

one object for a larger number of fragments.

Oversegmentation is the process by which the objects being segmented from

the background are themselves segmented or fractured into subcomponents.

During years of research into the problem of image segmentation,

many methods have been developed,

starting with heuristic methods like Region growing,

which we specify a set of initial points and

gradually attached to these points neighboring pixels that have the same characteristics.

Other approaches includes split and merge,

where we divide the image into regions until

the resultant regions are homogeneous, and energy-based methods.

One formula is the segmentation task in the form of optimization of

contours and then iteratively updates these contours.

Probably, the most advanced yet relatively simple approaches are clustering-based ones.

Let us discuss a few of those in more detail.

One of the efficient oversegmentation schemes is the Mean shift algorithm.

In Mean shift, one represents every pixel in the image with a feature vector, color,

histogram of gradients and pixels of filtered image may serve as features.

The idea of this approach is to search the feature space of

both pixels for areas with large probability density mass,

most of high dimensional feature distribution.

In this slide, we display the points in the feature space and find the density maximum.

To perform the search for a local density maximum,

we examined the neighborhood of every point in

the feature space and estimate the local density via

the non-parametric estimate known from statistics such as Kernel or Parzen estimates.

We may then compute the shift,

the direction in the image where density increases in the feature space.

When the procedure is complete for all points in the sample,

we cluster points according to the simplest possible rule.

A cluster is a group of points for which

the search procedure leads to the same mode of distribution.

You can see on the slide that Mean shift divides the segments fairly well by the colors.

Having this in mind, one may note that image segmentation is

nothing more than clustering in the feature space represented in pixels.

Lots of well-known clustering algorithms are based on k-means clustering,

an approach dividing points using some kind of a distance in the feature space.

SLIC or simple linear iterative clustering is

another unsupervised segmentation method which is base on

k-means and adopted to image segmentation task.

The idea of this algorithm is to compare

the pixels that are spaced apart from each other in the image by

a distance not more than s.

The hyperparameter s can later adjust the size of super pixels.

K-means requires initial approximation of cluster centers.

In SLIC, uniformly distributed points separated by the distance s are used.

As in the k-means algorithm,

the cluster satirists are updated until the summary change in

all clusters is less than the operating threshold.

Here you can see that SLIC method outperforms other oversegmentation methods

not only by the quality but in fact also by the computation coast.

In summary, oversegmentation as an approach to

segment images iteratively by splitting them into smaller subsegments,

a lot of approaches are developed and most of them are based on k-means clustering.

That concludes this section.